FOL: First-Order Logic Flashcards
(39 cards)
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
