COS4807/203/0/2020
Tutorial Letter 203/0/2020
Formal Logic
COS4807
Year module
Department of Computer Science
School of Computing
CONTENTS
Solutions to Assignment 3
university
Define Tomorrow. of south africa
, SOLUTIONS TO ASSIGNMENT 3
Question 1 (20)
(i) To prove that the formula A = ∃x¬(p(x) → q(x)) → ¬(∃xp(x) → ∀xq(x)) is valid, we must
show that it is true in all interpretations.
Let I be an interpretation in which the antecedent of the formula is true. In other words,
vI (∃x¬(p(x) → q(x))) = T . Then vσI (¬(p(x) → q(x))) = T for some assignment σI (by the
semantics of existential quantification, as stated in Theorem 7.22) and vσI (p(x) → q(x)) = F for
some assignment σI (by the truth values for negation). Then vσI (p(x)) = T and vσI (q(x)) = F
for some assignment σI (by the truth values for implication). But then vI (∃xp(x)) = T and
vI (∀xq(x)) = F (by Theorem 7.22). From this we conclude that vI (∃xp(x) → ∀xq(x)) = F
(by the truth values for for implication) and vI (¬(∃xp(x) → ∀xq(x))) = T (by the truth values
for negation).
We have shown that if the antecedent of the formula is true in I , then the consequent is true
in I . Since I is an arbitrary interpretation, we conclude that the who formula is true in any
interpretation.
(ii) To prove that B = ∃x∃yp(x, y) ↔ ∀x∀y¬p(x, y) is unsatisfiable, we must show that it is false in
all interpretations.
Let I be an arbitrary interpretation of B.
vI (∃x∃yp(x, y)) = T iff vσI (p(x, y)) = T for some assignment σI (by Theorem 7.22)
iff vσI (¬p(x, y)) = F for some assignment σI
(by the truth values for negation)
iff vI (∀x∀y¬p(x, y)) = F (by Theorem 7.22)
Since vI (∃x∃yp(x, y)) = T iff vI (∀x∀y¬p(x, y)) = F , we conclude that vI (∃x∃yp(x, y)) 6=
vI (∀x∀y¬p(x, y)), and thus that vI (∃x∃yp(x, y) ↔ ∀x∀y¬p(x, y)) = F (by the truth values for
equivalence). Since I is an arbitrary interpretation, we conclude that B is unsatisfiable.
Question 2 (10)
(i) Consider the formula A = ∀x(p(x) ↔ ∃y(q(y) ∧ r(x, y))). Under the given interpretation, this
formula states that for all natural numbers x, x is stange iff there is an odd number y such that
x has y distinct divisors.
(ii) To prove that A is falsifiable, we need to specify an interpretation in which it is false. There are
many possibilities. Here are a few:
(a) We can use the interpretation given for part (i), but just change the interpretation of pred-
icate p, say to the relation prime. Under this interprepretation, formula A states that all
prime numbers have an odd number of distinct divisors. This is obviously not true for any
prime number, because every prime number has exactly 2 distinct divisors, namely 1 and
itself.
(b) We can change the interpretation of predicate q, say to the unary relation even. Under
this interprepretation, formula A states that all strange numbers have an even number of
distinct divisors. This is obviously not true, according to the definition of strange numbers.
2
Tutorial Letter 203/0/2020
Formal Logic
COS4807
Year module
Department of Computer Science
School of Computing
CONTENTS
Solutions to Assignment 3
university
Define Tomorrow. of south africa
, SOLUTIONS TO ASSIGNMENT 3
Question 1 (20)
(i) To prove that the formula A = ∃x¬(p(x) → q(x)) → ¬(∃xp(x) → ∀xq(x)) is valid, we must
show that it is true in all interpretations.
Let I be an interpretation in which the antecedent of the formula is true. In other words,
vI (∃x¬(p(x) → q(x))) = T . Then vσI (¬(p(x) → q(x))) = T for some assignment σI (by the
semantics of existential quantification, as stated in Theorem 7.22) and vσI (p(x) → q(x)) = F for
some assignment σI (by the truth values for negation). Then vσI (p(x)) = T and vσI (q(x)) = F
for some assignment σI (by the truth values for implication). But then vI (∃xp(x)) = T and
vI (∀xq(x)) = F (by Theorem 7.22). From this we conclude that vI (∃xp(x) → ∀xq(x)) = F
(by the truth values for for implication) and vI (¬(∃xp(x) → ∀xq(x))) = T (by the truth values
for negation).
We have shown that if the antecedent of the formula is true in I , then the consequent is true
in I . Since I is an arbitrary interpretation, we conclude that the who formula is true in any
interpretation.
(ii) To prove that B = ∃x∃yp(x, y) ↔ ∀x∀y¬p(x, y) is unsatisfiable, we must show that it is false in
all interpretations.
Let I be an arbitrary interpretation of B.
vI (∃x∃yp(x, y)) = T iff vσI (p(x, y)) = T for some assignment σI (by Theorem 7.22)
iff vσI (¬p(x, y)) = F for some assignment σI
(by the truth values for negation)
iff vI (∀x∀y¬p(x, y)) = F (by Theorem 7.22)
Since vI (∃x∃yp(x, y)) = T iff vI (∀x∀y¬p(x, y)) = F , we conclude that vI (∃x∃yp(x, y)) 6=
vI (∀x∀y¬p(x, y)), and thus that vI (∃x∃yp(x, y) ↔ ∀x∀y¬p(x, y)) = F (by the truth values for
equivalence). Since I is an arbitrary interpretation, we conclude that B is unsatisfiable.
Question 2 (10)
(i) Consider the formula A = ∀x(p(x) ↔ ∃y(q(y) ∧ r(x, y))). Under the given interpretation, this
formula states that for all natural numbers x, x is stange iff there is an odd number y such that
x has y distinct divisors.
(ii) To prove that A is falsifiable, we need to specify an interpretation in which it is false. There are
many possibilities. Here are a few:
(a) We can use the interpretation given for part (i), but just change the interpretation of pred-
icate p, say to the relation prime. Under this interprepretation, formula A states that all
prime numbers have an odd number of distinct divisors. This is obviously not true for any
prime number, because every prime number has exactly 2 distinct divisors, namely 1 and
itself.
(b) We can change the interpretation of predicate q, say to the unary relation even. Under
this interprepretation, formula A states that all strange numbers have an even number of
distinct divisors. This is obviously not true, according to the definition of strange numbers.
2
