Final Examination, Semester 1 2018
LOGIC
(COMP2620 and PHIL2080)
Specimen answers
Page 1 of 11 – LOGIC – (COMP2620, PHIL2080)
A1 (a) ] In first order logic, what is a term?
A term is the result of applying an n-ary function symbol to n terms (i.e.
terms in virtue of this definition). This includes the case n = 0 where the
term is a name.
A1 (b) State the rule ∃E.
X ` ∃vAvm Y,A ` B (m not in B or in any formula in Y )
∃E
X,Y ` B
A1 (c) Express ∃(x : ∀(y : Rxy) Fy) ¬∀(z : Rxz) Gz using unrestricted (unary)
quantifiers.
∃x(∀y(Rxy→Fy)∧¬∀z(Rxz→Gz))
A1 (d) What are numerically indefinite quantifiers?
’At least n’ and ’at most n’ for a given natural number n. These can be
expressed in first order logic with identity as
∀x1 . . . ∀xn−1∃y(Fy ∧x1 6= y ∧ . . . ∧xn−1 6= y)
∃x1 . . . ∃xn∀y(Fy→(x1 = y ∨ . . . ∨xn = y))
A1 (e) Briefly, what is the sorites paradox?
It is a logical puzzle regarding vague predicates P such that the truth
value of P (a) seems insensitive to small changes in some aspect of a but
sensitive to large changes in that aspect of a, although the large change
is made up of small ones. This creates apparent counter-examples to→E
and similar foms of inference where these are iterated many times.
Page 2 of 11 – LOGIC – (COMP2620, PHIL2080)
A2 (a) Use a semantic tableau to show that the following sequent is valid:
∀x(Fx→∃y(Gy ∨Rxy)),¬∃x(Fx∧Gx) ` ∀x(Fx→∃y(¬Fy ∨Rxy))
1. t: ∀x(Fx→∃y(Gy ∨Rxy))
2. t: ¬∃x(Fx∧Gx)
3. f: ∀x(Fx→∃y(¬Fy ∨Rxy))
4. f: ∃x(Fx∧Gx) from 2
5. f: Fa→∃y(¬Fy ∨Ray) from 3
6. t: Fa
7. f: ∃y(¬Fy ∨Ray)
8. t: Fa→∃y(Gy ∨Ray) from 1
9. f: Fa
×
t: ∃y(Gy ∨Ray)
10. t: Gb∨Rab
11. f: ¬Fb∨Rab from 7
12. f: ¬Fb
13. f: Rab
14. t: Fb
15. t: Gb t: Rab
×
from 10
16. f: Fb∧Gb from 4
17. f: Fb
×
f: Gb
×
Page 3 of 11 – LOGIC – (COMP2620, PHIL2080)
A2 (b) The following is a “model” produced by Logic for Fun.
thing | 0 1 2
------+------------------
F | TRUE TRUE FALSE
R | 0 1 2
--+------------------
0 | FALSE FALSE FALSE
1 | TRUE FALSE TRUE
2 | FALSE FALSE TRUE
a = 1
b = 1
c = 2
A2 (b.i) Re-express this as an interpretation in the technical set-theoretic style,
defining the domain D and interpretation function I.
The domain of the interpretation is the sort “thing”: D = {0, 1, 2}
The interpretation function assigns values to the symbols in the vocabu-
lary:
I(a) = 1
I(b) = 1
I(c) = 2
I(F ) = {0, 1}
I(R) = {〈1, 0〉, 〈1, 2〉, 〈2, 2〉}
A2 (b.ii) Explain, with detailed reference to the evaluation conditions for con-
nectives and quantifiers how the formula
∀x∀y((Rxy→Ryx)→(Fx→Fy))
gets its truth value for this interpretation.
Consider the interpretation I[a←0,b←2]. Call it K for brevity. Since it is a
b-variant of an a-variant of I, we know K(F ) = I(F ) and K(R) = I(R).
Clearly, K(a) = 0 and K(b) = 2. Now:
truth value because
Rab false for K 〈0, 2〉 /∈ K(R)
Rab→Rba true for K Rab false for K
Fa true for K 0 ∈ K(F )
Fb true for K 2 /∈ K(F )
Fa→Fb false for K Fa true, Fb false for K
(Rab→Rba)→(Fa→Fb) false for K truth table for →
∀y((Ray→Rya)→(Fa→Fy)) false for I[a←0] (Rab→Rba)→(Fa→Fb)
false for a b-variant
∀x∀y((Rxy→Ryx)→(Fx→Fy)) false for I ∀y((Ray→Rya)→(Fa→Fy)
false for an a-variant
Page 4 of 11 – LOGIC – (COMP2620, PHIL2080)
2c.i The following natural deduction proof in propositional logic has some parts
missing. Fill in the gaps to make a valid proof. Note that all discharges
of assumptions are as given in the right column.
(1) A
(2) A
(3) A
(4) q→r 3 [ ]
(5) p
(6) 5
(7) 2, 4 [ ]
(8) s 7
(9) 8 [3]
(10) 9
(11) 1, 6 [5], 10 [2]
1 (1) p∨¬(q→r) A
2 (2) ¬(q→r) A
3 (3) r A
3 (4) q→r 3 [ ] →I
5 (5) p A
5 (6) p∨ (r→s) 5 ∨I
2, 3 (7) ¬¬s 2, 4 [ ] RAA
2, 3 (8) s 7¬¬E
2 (9) r→s 8 [3] →I
2 (10) p∨ (r→s) 9 vI
1 (11) p∨ (r→s) 1, 6 [5], 10 [2] ∨E
Page 5 of 11 – LOGIC – (COMP2620, PHIL2080)
2c.ii Prove in the natural deduction calculus:
∀x∃y(Rxy ∧¬Fy),∀x(¬Gx→Fx) ` ∀x∃y(Gy ∧Rxy
1 (1) ∀x∃y(Rxy ∧¬Fy) A
2 (2) ∀x(¬Gx→Fx) A
1 (3) ∃y(Ray ∧¬Fy) 1 ∀E
4 (4) Rab∧¬Fb A (instance of 3, for ∃E)
4 (5) Rab 4 ∧E
4 (6) ¬Fb 4 ∧E
7 (7) ¬Gb A
2 (8) ¬Gb→Fb 2 ∀E
2, 7 (9) Fb 7, 8→E
2, 4 (10) ¬¬Gb 6, 9 [7] RAA
2, 4 (11) Gb 10¬¬E
2, 4 (12) Gb∧Rab 5, 11 ∧I
2, 4 (13) ∃y(Gy ∧Ray) 12 ∃I
1, 2 (14) ∃y(Gy ∧Ray) 3, 13 [4] ∃E
Page 6 of 11 – LOGIC – (COMP2620, PHIL2080)
B1 (a)
∃xFx∨∃xGx, ∀x((Fx∨Gx)→Hx) ` ∃xHx
1 (1) ∃xFx∨∃xGx A
2 (2) ∀x((Fx∨Gx)→Hx) A
3 (3) ∃xFx A (left disjunct for ∨E)
4 (4) Fa A (instance of 3 for ∃E)
2 (5) (Fa∨Ga)→Ha 2 ∀E
4 (6) Fa∨Ga 4 ∨I
2, 4 (7) Ha 5, 6→E
2, 4 (8) ∃xHx 7 ∃I
2, 3 (9) ∃xHx 3, 8 [4] ∃E
10 (10) ∃xGx A (right disjunct for ∨E)
11 (11) Ga A (instance of 10 for ∃E)
11 (12) Fa∨Ga 11 ∨I
2, 11 (13) Ha 5, 12→E
2, 11 (14) ∃xHx 13 ∃I
2, 10 (15) ∃xHx 10, 14 [11] ∃E
1, 2 (16) ∃xHx 1, 9 [3], 15 [10] ∨E
B1 (b)
∀x(Fx→(x = f(x)∨Gx)) ` ∀x(Fx→(Gf(f(x))→Gx))
1 (1) ∀x(Fx→(x = f(x)∨Gx)) A
2 (2) Fa A
3 (3) Gf(f(a)) A
1 (4) Fa→(a = f(a)∨Ga) 1 ∀E
1, 2 (5) a = f(a)∨Ga 2, 4→E
6 (6) a = f(a) A
6 (7) a = f(f(a)) 6, 6 =E
3, 6 (8) Ga 3, 7 =E
9 (9) Ga A
1, 2, 3 (10) Ga 5, 8 [6], 9 [9] ∨E
1, 2 (11) Gf(f(a))→Ga 10 [3] →I
1 (12) Fa→(Gf(f(a))→Ga) 11 [2] →I
1 (13) ∀x(Fx→(Gf(f(x))→Gx)) 12 ∀I
Page 7 of 11 – LOGIC – (COMP2620, PHIL2080)
B1 (c)
∀(x : ∃yRxy) (Fx∨Gx), ∃(x : ¬Fx) Rxa ` ∃(x : Gx) ∃yRxy
1 (1) ∀(x : ∃yRxy) (Fx∨Gx) A
2 (2) ∃(x : ¬Fx) Rxa A
3 (3) ¬Fb A
4 (4) Rba A
4 (5) ∃yRby 4 ∃I
1, 4 (6) Fb∨Gb 1, 5 ∀ER
7 (7) Fb A
3, 7 (8) ¬¬Gb 3, 7 [ ] RAA
3, 7 (9) Gb 8¬¬E
10 (10) Gb A
1, 3, 4 (11) Gb 6, 9 [7], 10 [10] ∨E
1, 3, 4 (12) ∃(x : Gx) ∃yRxy 5, 11 ∃IR
1, 2 (13) ∃(x : Gx) ∃yRxy 2, 12 [3,4] ∃ER
Page 8 of 11 – LOGIC – (COMP2620, PHIL2080)
B2 We know that all truth functions can be represented using conjunction and
negation (∧ and ¬) only.
Define disjunction (∨ ) and implication (→) in terms of conjunction and
negation. Show that the introduction and elimination rules ∨I, ∨E, →I
and→E are all derivable on your definitions using ∧I, ∧E, RAA and¬¬E
only.
Similarly, the existential quantifier can be defined in terms of the universal
one by taking ∃vA to mean ¬∀v¬A. Show that the rules ∃I and ∃E are
derivable on that definition using ∀I and ∀E and the negation rules. For
instance, for ∃I , you must show that if a sequent X `Atv is provable then
so is X ` ¬∀v¬A.
This question is not actually very complicated or difficult, although most
students who attempted it scored badly on it.
Defining disjunction and implication is easy:
A∨B =df ¬(¬A∧¬B)
A→B =df ¬(A∧¬B)
In terms of these definitions, we may write the introduction and elimina-
tion rules using conjunction and negation. ∨I becomes:
A
∨I
¬(¬A∧¬B)
A
∨I
¬(¬B ∧¬A)
To derive these, we need to show that if any sequent X `A is derivable,
then so are X ` ¬(¬A∧¬B) and X ` ¬(¬B ∧¬A). This is not difficult:
X (1) A proved somehow
2 (2) ¬A∧¬B A
2 (3) ¬A 2 ∧E
X (4) ¬(¬A∧¬B) 1, 3 [2] RAA
There proof of the other ∨I rule is exactly similar, with the conjuncts in
the4 opposite order, and is omitted here. ∨E is slightly more complicated.
It reads
X ` ¬(¬A∧¬B) Y,A `C Z,B `C
∨E
X,Y, Z `C
We suppose that the three input sequents are all derivable, and proceed
thus:
Page 9 of 11 – LOGIC – (COMP2620, PHIL2080)
X (1) ¬(¬A∧¬B) proved somehow
2 (2) A A
Y, 2 (3) C proved somehow
4 (4) B A
Z, 4 (5) C proved somehow
6 (6) ¬C A
Y, 6 (7) ¬A 3, 6 [2] RAA
Z, 6 (8) ¬B 5, 6 [4] RAA
Y,Z, 6 (9) ¬A∧¬B 7, 8 ∧I
X,Y, Z (10) ¬¬C 1, 9 [6] RAA
X,Y, Z (11) C 10¬¬E
For→E we need to show that if X ` ¬(A∧¬B) and Y `A are both deriv-
able, then so is X,Y `B. This follows the same pattern as above:
X (1) ¬(A∧¬B) proved somehow
Y (2) A proved somehow
3 (3) ¬B A
Y, 3 (4) A∧¬B 2, 3 ∧I
X,Y (5) ¬¬B 1, 4 [3] RAA
X,Y (6) B 5¬¬E
→I is not so trivial. We really need to appeal to “cut” in the form: if
X `A and Y,A `B then X,Y `B. This will not be proved here; it is
done by induction on the length of proofs, and is straightforward. Given
cut, it is not hard to emulate →I with ∧ and ¬. Suppose X,A `B is
derivable. Then:
1 (1) A∧¬B A
1 (2) A 1 ∧E
X,A (3) B proved somehow
X, 1 (4) B 2, 3 cut
1 (5) ¬B 1 ∧E
X (6) ¬(A∧¬B) 4, 5 [1] RAA
The analogous proof that the existential quantifier rules can be derived
using the universal quantifier and negation is rather similar. For ∃I ,
suppose that we have a proof of X `Atv. We need to show that it can be
extended to a proof of the sequent X ` ¬∀x¬A:
Page 10 of 11 – LOGIC – (COMP2620, PHIL2080)
X (1) Atv proved somehow
2 (2) ∀x¬A A
2 (3) ¬Atv 2 ∀E
X (4) ¬∀x¬A 1, 3 [2] RAA
Finally, ∃E on the suggestyed definition reads
X ` ¬∀v¬Avm Y,A ` B (m not in B or Y )
∃E
X,Y ` B
As before, suppose the two input sequents are provable, and that m does
not occur in Y or in B. Then:
X (1) ¬∀v¬Avm proved somehow
2 (2) A A
Y, 2 (3) B proved somehow
4 (4) ¬B A
Y, 4 (5) ¬A 3, 4 [2] RAA
Y, 4 (6) ∀v¬Avm 5 ∀I
X,Y (7) ¬¬B 1, 7 [4] RAA
X,Y (8) B 7¬¬E
Page 11 of 11 – LOGIC – (COMP2620, PHIL2080)