FOL: First-Order Logic Flashcards
Which famous example proves the limitations of TFL?
- Socrates is a person - p
- All people are mortal - q
- Therefore, socrates is mortal - .:r
Singular term
an expression that purports to refer to one object e.g. names, definite descriptions
predicate
the result of deleting one or more singular terms from a sentence and replacing them with variables e.g. Socrates is a person becomes the predicate ‘Px: X is a person’
What is a formalisation key? What are the rules for them?
Tells you what predicates and names refer to. It also includes the domain e.g. Px: X is a person, S: socrates, Mx: X is mortal.
RULES:
- The domain must be non-empty (not in free logic)
- every name must pick out exactly one thing in the domain (no empty names/multiples)
- A member of the domain can be picked out by one name, many names or no names
What is a quantifier, which types are there in FOL? what do their negations mean?
The amount of something
Universal Quantifier: ∀ - everything, all
¬∀ - not everything, this could mean something
Existential Quantifier: ∃ - some, at least one, a few
¬∃ - nothing
What is the existential quantifier equivalent of ∀xLx
∀xLx≡¬∃x¬Lx
What is an empty predicate?
A predicate that has no members e.g. Ux: X is a unicorn, you can use ∀ in these circumstances (e.g. all unicorns have horns ∀x(Ux→Hx) where Hx: x has a horn) but not ∃x because there is nothing in the sex of Ux (e.g. you cannot say ∃x(Ux&Hx) some unicorns have horns). Statements made about empty predicates are vacuously true because with a false antecedent all conditionals are true.
FOL validity
An argument of FOL is valid iff there is no interpretation making the premises true and the conclusion false
what is an interpretation?
- specification of a domain
- For each name we care to consider, a specification of the object it denotes
- For each non-logical predicate we care to consider a specification of the objects it is true for
Domain: Everyone
Hx: X is in the lecture hall
Px: X is a philosopher
Lx: X is a logician
Using the above formalisation key, say:
(a) Everyone in the lecture hall is a philosopher
(b) Someone in the lecture hall is a logician
(c) Not everyone in the lecture hall is a philosopher
(d) no one in the lecture hall is a logician
(a) ∀x(Hx→Px)
(b) ∃x(Hx&Lx)
(c) ¬∀x(Hx→Px) or ∃x(Hx&Px)
(d) ¬∃x(Hx&Lx) or ∀x(Hx→¬Lx)
What is a model?
The model is a valid, potential formalisation key that is used to describe a set of sentences
How do you demonstrate invalidity in FOL?
Provide an interpretation (i.e. potential formalisation key) that makes the premises of the argument true but the conclusion false - this can be done using an infinite (e.g. natural numbers) or finite domain (e.g. {1, 2, 3, 4, 5}) and must be done intuitively. The negation of a logical falsity is a logical truth.
What are the rules used when proving validity in FOL (e.g. TI)
- Tautological implication TI: one formula G is tautologically implied by other formulas F1, F2, …, Fn iff (F1 & F2 & … & Fn)→G is a tautology.
- Universal Specification US: you can take any formula with a universal quantifier on a variable C at the front and infer from it the formula obtained by dropping the quantifier and if you like replacing the occurence of X by any variable or individual constants.
- Universal Generalisation UG: If you have a formula of the form Fx involving unquantified variable X, then you may infer ∀x(Fx) in which the unquantified variable is quantified over.
- Existential Generalisation EG: If G is a formula that results from formula F by at most replacing either an ambiguous name or an individual constant by a variable X, then ∃x(Gx) can be inferred from Fx
- existential Specification ES: the formula F[α/x] can be inferred from the formula ∃xFx (where F[α/x] is the formula obtained by substituting α for x]
What are the types of TI?
(a) MODUS PONENS: from P and P→Q infer Q
(b) MODUS TOLLENS: from ¬Q and P→Q infer ¬P
(c) SIMPLIFICATION: from P&Q infer P or Q
(d) DISJUNCTIBVE SYLLOGISM: from P v Q and ¬P infer Q
(e) HYPOTHETICAL SYLLOGIS; From P→Q and Q→R infer Q→R
when is a sentence of FOL a logical truth?
It is true under all interpretations
What is a conditional proof?
If the Formula G can be derived from a set of premises {Pi} and formula F then the the formula F→G can be derived just from {Pi}
What is inconsistency in FOL
A set of sentences of FOL, s = {s1, s2, …, Sn} is inconsistent iff the sentence s1&…&Sn is logically false i.e. its negation is derivable from no premises.
Monadic FOL
FOL that only uses predicates with acidity one e.g. Fx
Polyadic FOL
FOL that uses relations as well as predicates, this means predicates that have acidity of more than one - remember in polyadic FOL, you must quantify over every variable used in the relation e.g. ∀x∃yLx,y
acidity of a predicate
the number of variables:
e.g Fx - acidity 1
Rxy - acidity 2 - this is also known as a 2-place relation
Rxyz - acidity 3 - this is also known as a 3-place relation
Ambiguos names
α, β, γ - acts as a proper name but when the specifics are unknown. For example if ∃xFx, Fα means there is something with the property F
Transitivity
In mathematics, a binary relation R over a set X is transitive if whenever an element a is related to an element b and b is related to an element c then a is also related to c. Transitivity (or transitiveness) is a key property of both partial order relations and equivalence relations. Transitivity sometimes makes reading off a finite interpretation impossible.
the scope of a quantifier
the part of the formula which is governed by the quantifier
bound
An occurence of variable xi is BOUND iff it is either the variable in a quantifier ∀xi or ∃xi or it lies in the scope of a quantifier on xi
free variable
a variable that is not bound e.g. z is free in ∃x(Qx v ∀y Ryz).
a sentence in FOL
a formula in which all variables are bound - no free variables
what does the term ‘free for the variable xi’ mean?
A term is free for the variable xi in formula F iff no free occurence of xi in F lies within the scope of any quantifier on xj where xj is a variable in t.
e. g. x is not free for y in ∃xRxy
e. g. z is free for y in Py→∃y(Qy→Ryz)
This can create a problem because you could introduce a variable into the scope of the quantifier over that term unduly.
What rule governs assumptions?
you must flag (i.e. mark with x) free variables (i.e. variables not contained within the scope of a quantifier) when making assumptions until they can be suitably discharged (usually at CP conditional proof)
What rule(s) governs universal Generalisation?
You cannot use UG on flagged or subscripted variables
What rule(s) governs existential Generalisation?
- If the potential replaced name is ambiguous, then you cannot EG over a flagged or subscripted variable
- you cannot EG over a variable that is already bound over
What rule(s) governs universal specification?
For any formula F and any term t, F[t | xi] may be inferred from ∀xiF provided t is free for xi in F.
What rule(s) governs existential specification?
- when introducing an ambiguous name subscript the name with the relevant variable
- don’t use an ambiguous name that already exists in the proof
How would you use identity to express ‘at least 2 apples’ in FOL
∃x∃y(Ax&Ay&¬x=y)
How would you use identity to express ‘at least 3 apples’ in FOL
∃x∃y∃z(Ax&Ay&Az&¬x=y&¬y=z&¬x=z)
How would you use identity to express ‘at most 2 apples’ in FOL
∀x∀y∀z((Ax&Ay&Az)→(x=y v y=z v x=z))
How would you use identity to express ‘exactly 2 apples’ in FOL
∃x∃y(Ax&Ay&¬x=y &∀z(Az→(x=z v y=z)))
What rules govern the behaviour of identity in proofs in FOL?
I1: t=t for any term t can be derived from the empty set of premises. This is because logical truths (of which identity is one) comes from no premises at all
I2: Let t1…tn and s1…sn be terms. then if for all i ∈ {1, … , n}, si is free for ti in F, the formula F’ obtained from F by replacing some or all of si with some or all occurrences of ti may be inferred from F and the formulas s1=t1, …, sn=tn
Leibniz’s Law: If two things are identical they have the exact same properties - this means you can infer from ‘Fa’ and ‘a=b’ that Fb
What is Leibniz’s law
If two things are identical they have the exact same properties - this means you can infer from ‘Fa’ and ‘a=b’ that Fb
logical proof
derived from no premises
