Logic Definitions Flashcards
Set
Collection of ‘objects’, objects in the collection are elements of that set
When are two sets identical?
They have the same elements
Ordered pair
Two components with a specific and fixed order
A binary relation R is reflexive on a set S iff…
For all elements d of set S the pair <d,d> is an element of R (loop arrow)
A binary relation R is symmetric on a set S iff
For all elementd d, e of S: if <d,e> is an element of R then <e,d> is an element of R (two way arrows)
A binary relation R is assymetric on a set S iff
For no elements d, e of set S: <d,e> is an element of R and <e,d> is an element of R (no two way arrows)
A binary relation R is antisymmetric on a set S iff
For no two distinct elements d, e of S: <d, e> is an element of R and <e, d> is an element of R
A binary relation R is transitive on a set S iff
For all elements d, e, f of S: if <d, e> and <e, f> are elements of R, then <d,f> is an element of R (shortcut)
A binary relation R is symmetric iff
It is symmetric on all sets
A binary relation R is asymmetric iff
It is asymmetric on all sets
A binary relation R is antisymmetric iff
It is antisymmetric on all sets
A binary relation R is transitive iff
It is transitive on all sets
A binary relation R is an equivalence relation on S iff
R is reflexive on S, symmetric on S and transitive on S
Binary relation R is a function iff
For all d, e, f: if <d,e> is an element of R and <d, f> is an element of R, then e=f
Domain of a function R
Is the set {d: there is an e such that <d, e> is an element of R}
Elements of the domain are inputs or arguments of the function
The range of a function R
Is the set {e: there is a d such that <d, e> is an element of R}
Elements of the range are outputs or values of the function
R is a function into the set M iff
All elements of the range of the function are in M
Binary relation
Is a set containing only ordered pairs
Declarative sentence
A sentence that is true or false
Argument
Declarative sentences (premises) + declarative sentence (conclusion)
An argument is logically valid iff
There is no interpretation under which the premisses are all true and the conclusion is false
Interpretation
Assigning meaning to the subject-specific terms (logical terms are untouched)
Argument is propositionally valid iff
there is no (re-interpretation) under which the sentences in the argument such that all premisses are true and yet the conclusion is false
A set of sentences is logically consistent iff
There is at least one interpretation under which all sentences in the set are true
A sentence is logically true iff
It is true under any interpretation
A sentence is a contradictiom iff
It is false under all interpretations
Sentences are logically equivalent iff
They are true under the exact same interpretations
Syntax
Expressions of language bare of their meanings (grammar)
Semantics
Meanings of the expressions of language
Sentence letters
P, Q, R…
Sentence of L1
All sentence letters are sentences of L1
If 🦄 and 🌷are sentences of L1 then their negation, conjunction, disjunction etc are sentences of L1
Nothing else is a sentence of L1
🦄 and🌷have to be replaced by sentences of L1
Dropping brackets
Outer brackets may be ommitted if the sentence is not part of another sentence
Inner brackets may be ommitted if (1) the order does not matter or (2) and+or are stronger than if+iff
An L1 structure
Is an assignment of exactly one truth value to every sentence of L1
A sentence 🦄 of L1 is logically true iff
🦄 is true in all L1 structures (only T-s in main column)
A sentence 🦄 is a contradiction iff
🦄 is not true in any L1 structure (only F-s in the main column)
Sentences 🦄 and 🌷 are logically equivalent iff
🦄 and 🌷 are true in exactly the same L1 structures
Tautology
A logically true sentence
Let 🌵 be a set of sentences of L1 and 🦄 a sentence of L1. The argument with the sentences in 🌵 as premisses and 🦄 as conclusion is valid iff
There is no L1 structure in which all sentences in 🌵 are true and 🦄 is false
If 🦄 and all sentences of 🌵 are L1 sentences in 🌵then
🌵 I= 🦄 (🌵 logically implies 🦄 ) iff
The set containing all sentences in 🌵 and not 🦄 are inconsistent
An L1 structure is a counterexample to the argument which has 🌵 as a set of premisses and 🦄 as a conclusion iff
There is an L1 structure where all premisses are true but the conclusion is false
A set 🌵 of L1 sentences is semantically consistent iff
There is an L1 structure A such that under that structure the truth value of all sentences in 🌵 is true
Truth functionality (characterisation)
A connective is truth-functional iff the truth value of the compound sentence cannot be changed by replacing a direct subsentence with another sentence having the same truth value (no question marks in truth table)
Ambiguity
There can be multiple correct formalizations for one sentence
An English sentence is a tautology iff
Its formalization in propositional logic is true (iff its formalization is a tautology, its formalization is propositionally valid)
An English sentence is a propositional contradiction iff
Its formalization in propositional logic is a contradiction
A set of English sentences is propositionally consistent iff
The set of all their formalizations in propositional logic is semantically consistent
An argument in English is propositionally valid iff
Its formalization in L1 is valid
Every propositionally valid argument is also valid but not every valid argument is propositionally valid
Predicate letter
All expressions of the form Pnk are predicate letters where n and k are either missing or are numerals
Arity
Value of the upper index of a predicate letter
Constants
a, b, c…
Variables
x, y, v
Atomic formulae of L2
If Z is a predicate letter of arity n and each of t1, t2…tn is a variable or constant then Zt1..tn is an atomic formula of L2
Quantifier
An expression Av or Ev where v is a variable
Formulae of L2
1) All atomic formulae of L2 are formulae of L2
2) if 💐 and 🌹 are formulae of L2 then adding conjunction, disjunction, arrow etc to them makes the new thing makes also formula of L2
3) if v is a variable and 💐 is a formula then adding a quantifier to the atomjc formula makes the new thing a formula of L2
Free and bound occurences of variables
1) all occurrences of variables in atomic formulae are free
2) The occurrences of a variable that are free in formulae are also free in the conjunction, disjunction etc of those formulae
3) in a formula with a quantifier no occurrence of the variable v is free, all occurrences of variables other than v that are free in the original formula are also free in the new one
A variable occurs freely in a formula iff
There is at least one free occurrence of the variable in the formula
Sentence of L2
A formula of L2 where no variable occurs freely in the formula
L2 structure
An L2 structure is an ordered pair (D,I) where D is some non-empty set and I is a function from a set of all constants, sentence letters and predicate letters such that the value of every constant is an element of D, the value of every sentence letter is a truth value T or F and the value of every n-ary predicate letter is an n-ary relation
A variable assignment over an L2 structure A
Assigns an element of thr domain DA of A to each variable
Universal quantifier is true iff
It is true for all variable assignments beta over A differing from alpha in v at most
Some quantifier is true iff
It is true for at least one variable assignment beta over A differing from alpha in v at most
For a (L2) formula to be true
The variable(s) or constant(s) had to be members of the set of the n-ary predicate letter
Adequacy
Soundness (if single turnstyle then double turnstyle) + completeness (if double turnstyle then single turnstyle)
A set of L2 sentences is syntactically consistent iff
It is not the case that any sentence whatsoever can be proved from the premisses in the set
A set of sentences in L2 are semantically consistent iff
They are syntactically consistent
Scope of a quantifier or connective in a sentence of L2
Is the occurrence of the smallest L2 formula that contains the occurrence of the quantifier or connective and is a part of that sentence
Extensionality
If constants, sentence letters and predicate letters are replaced in an L2 sentence by other constants, sentence letters and predicate letters (respectively) that have the same extension in a given L2 structure then the truth-value of the sentence in that L2 structure does not change
Atomic formulae of L=
All atomic formulae of L2 are atomic formulae of L=. Furhtermore, if s and t are variables or constant, then s=t is an atomic formula of L=
Double turnstyle
Valid argument
Logically implies
(Syntax)
Single turnstile
It is provable from
(Semantics)
Connective
Expressions that can be used to combine or modify english sentences to form a sentence
