FOL: First-Order Logic

Question 1

Which famous example proves the limitations of TFL?

Answer 1

1. Socrates is a person - p
2. All people are mortal - q
3. Therefore, socrates is mortal - .:r

Question 2

Singular term

Answer 2

an expression that purports to refer to one object e.g. names, definite descriptions

Question 3

predicate

Answer 3

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’

Question 4

What is a formalisation key? What are the rules for them?

Answer 4

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:

1. The domain must be non-empty (not in free logic)
2. every name must pick out exactly one thing in the domain (no empty names/multiples)
3. A member of the domain can be picked out by one name, many names or no names

Question 5

What is a quantifier, which types are there in FOL? what do their negations mean?

Answer 5

The amount of something
Universal Quantifier: ∀ - everything, all
¬∀ - not everything, this could mean something
Existential Quantifier: ∃ - some, at least one, a few
¬∃ - nothing

Question 6

What is the existential quantifier equivalent of ∀xLx

Answer 6

∀xLx≡¬∃x¬Lx

Question 7

What is an empty predicate?

Answer 7

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.

Question 8

FOL validity

Answer 8

An argument of FOL is valid iff there is no interpretation making the premises true and the conclusion false

Question 9

what is an interpretation?

Answer 9

1. specification of a domain
2. For each name we care to consider, a specification of the object it denotes
3. For each non-logical predicate we care to consider a specification of the objects it is true for

Question 10

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

Answer 10

(a) ∀x(Hx→Px)
(b) ∃x(Hx&Lx)
(c) ¬∀x(Hx→Px) or ∃x(Hx&Px)
(d) ¬∃x(Hx&Lx) or ∀x(Hx→¬Lx)

Question 11

What is a model?

Answer 11

The model is a valid, potential formalisation key that is used to describe a set of sentences

Question 12

How do you demonstrate invalidity in FOL?

Answer 12

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.

Question 13

What are the rules used when proving validity in FOL (e.g. TI)

Answer 13

1. Tautological implication TI: one formula G is tautologically implied by other formulas F1, F2, …, Fn iff (F1 & F2 & … & Fn)→G is a tautology.
2. 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.
3. 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.
4. 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
5. 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]

Question 14

What are the types of TI?

Answer 14

(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

Question 15

when is a sentence of FOL a logical truth?

Answer 15

It is true under all interpretations

Question 16

What is a conditional proof?

Answer 16

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}

Question 17

What is inconsistency in FOL

Answer 17

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.

Question 18

Monadic FOL

Answer 18

FOL that only uses predicates with acidity one e.g. Fx

Question 19

Polyadic FOL

Answer 19

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

Question 20

acidity of a predicate

Answer 20

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

Question 21

Ambiguos names

Answer 21

α, β, γ - acts as a proper name but when the specifics are unknown. For example if ∃xFx, Fα means there is something with the property F

Question 22

Transitivity

Answer 22

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.

Question 23

the scope of a quantifier

Answer 23

the part of the formula which is governed by the quantifier

Question 24

bound

Answer 24

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

Question 25

free variable

Answer 25

a variable that is not bound e.g. z is free in ∃x(Qx v ∀y Ryz).

Question 26

a sentence in FOL

Answer 26

a formula in which all variables are bound - no free variables

Question 27

what does the term ‘free for the variable xi’ mean?

Answer 27

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.

Question 28

What rule governs assumptions?

Answer 28

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)

Question 29

What rule(s) governs universal Generalisation?

Answer 29

You cannot use UG on flagged or subscripted variables

Question 30

What rule(s) governs existential Generalisation?

Answer 30

1. If the potential replaced name is ambiguous, then you cannot EG over a flagged or subscripted variable
2. you cannot EG over a variable that is already bound over

Question 31

What rule(s) governs universal specification?

Answer 31

For any formula F and any term t, F[t | xi] may be inferred from ∀xiF provided t is free for xi in F.

Question 32

What rule(s) governs existential specification?

Answer 32

1. when introducing an ambiguous name subscript the name with the relevant variable
2. don’t use an ambiguous name that already exists in the proof

Question 33

How would you use identity to express ‘at least 2 apples’ in FOL

Answer 33

∃x∃y(Ax&Ay&¬x=y)

Question 34

How would you use identity to express ‘at least 3 apples’ in FOL

Answer 34

∃x∃y∃z(Ax&Ay&Az&¬x=y&¬y=z&¬x=z)

Question 35

How would you use identity to express ‘at most 2 apples’ in FOL

Answer 35

∀x∀y∀z((Ax&Ay&Az)→(x=y v y=z v x=z))

Question 36

How would you use identity to express ‘exactly 2 apples’ in FOL

Answer 36

∃x∃y(Ax&Ay&¬x=y &∀z(Az→(x=z v y=z)))

Question 37

What rules govern the behaviour of identity in proofs in FOL?

Answer 37

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

Question 38

What is Leibniz’s law

Answer 38

If two things are identical they have the exact same properties - this means you can infer from ‘Fa’ and ‘a=b’ that Fb

Question 39

logical proof

Answer 39

derived from no premises