/Users/billy/gits/moc-2021/problem-sets/solps04.dvi
The University of Melbourne
School of Computing and Information Systems
COMP30026 Models of Computation
Sample Answers to Tutorial Exercises, Week 4
Part 1 – Propositional Logic
P4.1 Let the propositional variable A stand for “A is a knight” and similarly for B and C. Note
that if A makes statement S then we know that A⇔ S holds. Or we can consider the two
possible cases for A separately: Either A is a knight, and A’s statement can be taken face
value; or A is a knave, in which case the negation of the statement holds, that is,
(
A ∧
(
A⇒ (¬B ∧ ¬C)
)
)
∨
(
¬A ∧ ¬
(
A⇒ (¬B ∧ ¬C)
)
)
We can rewrite the implications:
(
A ∧
(
¬A ∨ (¬B ∧ ¬C)
)
)
∨
(
¬A ∧ ¬
(
¬A ∨ (¬B ∧ ¬C)
)
)
Then, pushing negation in and using the distributive laws, we get
(
A ∧ (¬B ∧ ¬C)
)
∨
(
¬A ∧A ∧ (B ∨ C)
)
The second disjunct is false, so the formula is equivalent to A ∧ ¬B ∧ ¬C. So A must be a
knight, and B and C are knaves.
P4.2 Let us call the initial contents of R1 and R2 x and y, respectively. We want to see what
happens to the individual bits in x and y, but since the ⊕ works bitwise, we can just consider
x and y in their entirety.
• After the first assignment, R1 holds x⊕ y, and R2 holds y.
• So after the second assignment, R1 holds x⊕ y, and R2 holds x⊕ y ⊕ y, that is, x.
• So after the third assignment, R2 holds x, and R1 holds x⊕ y ⊕ x, that is, y.
P4.3 The formulas F2, F3, F5, and F6 are logically equivalent. Grouping the formulas into sets of
equivalent formulas, we get
{{F1}, {F4}, {F2, F3, F5, F6}}
This can easily be verified by completing the truth tables.
P4.4 These are the clauses generated:
(a) For each node i generate the clause Bi ∨Gi ∨Ri. That’s n+ 1 clauses of size 3 each.
(b) For each node i generate three clauses: (¬Bi ∨¬Gi)∧ (¬Bi ∨¬Ri)∧ (¬Gi ∨¬Ri). That
comes to 3n+ 3 clauses of size 2 each.
(c) For each pair (i, j) of nodes with i < j we want to express Eij ⇒ (¬(Bi ∧Bj) ∧ ¬(Gi ∧ Gj) ∧ ¬(Ri ∧ Rj). This means for each pair (i, j) we generate three clauses: (¬Eij ∨ ¬Bi ∨¬Bj)∧ (¬Eij ∨¬Gi ∨¬Gj)∧ (¬Eij ∨¬Ri ∨¬Rj). There are n(n+1)/2 pairs, so we generate 3n(n+ 1)/2 clauses, each of size 3. Altogether we generate 3n+ 3 + 6n+ 6 + 9n(n+ 1)/2 literals, that is, 9(n+ 1)(n/2 + 1). P4.5 (a) ¬P becomes P ⊕ t . With XNF it is perhaps more natural to use 0 for f and 1 for t. We really are dealing with arithmetic modulo 2, ⊕ playing the role of addition, and ∧ playing the role of multiplication. (b) P ∧Q is unchanged, or we can write simply PQ . (c) P ∧ ¬Q can be written P (Q⊕ t), so by “multiplying out” we get PQ⊕ P . (d) P ⇔Q becomes P ⊕Q⊕ t (since biimplication is the negation of exclusive or). (e) P ∨Q becomes P ⊕Q⊕ PQ , as truth tables will confirm. But how could we discover that solution? Well, we now know how to deal with negation and disjunction, and so we can make use of the fact that P ∨ Q ≡ ¬(¬P ∧ ¬Q). This way we arrive at t⊕ ((t⊕P )(t⊕Q)). Now all we need to do is to simplify that formula (come on, do it). (f) Using the insight from part (e), we transform P ∨ (Q ∧R) to P ⊕QR⊕ PQR . (g) Negation is just ‘⊕ t’, so we can write ¬(P ⊕Q) as P ⊕Q⊕ t . (h) For (P ⊕Q) ∧R, we just “multiply out”, to get PR⊕QR . (i) Given (PQ⊕ PQR⊕R) ∧ (P ⊕Q) we again multiply out. There will be six products, but some will cancel out: PQP ⊕ PQRP ⊕ PR⊕ PQQ⊕ PQRQ⊕QR = PQ⊕ PQR⊕ PR⊕ PQ⊕ PQR⊕QR = PR⊕QR (j) Given Q ∧ (P ⊕ PQ⊕ t) we multiply out, to get PQ⊕ PQ⊕Q, that is, Q . (k) From part (e) we know that A∨B ≡ A⊕B ⊕AB. Applying that to Q∨ (P ⊕ PQ) we obtain the formula Q⊕ P ⊕ PQ⊕ (Q(P ⊕ PQ)). Multiplying out, we get Q⊕ P ⊕ PQ⊕ PQ⊕ PQ = P ⊕Q⊕ PQ (So the formula in (k) must be equivalent to P ∨Q.) 2 Part 2 - Predicate Logic P4.6 (i) ∀x((D(x) ∧ ∃y(D(y) ∧M(y) ∧ F (x, y)))⇒M(x)) (ii) ∀x((D(x) ∧M(x))⇒∀y((D(y) ∧ ¬M(y))⇒R(x, y))) (iii) ∀x((D(x) ∧R(x, b))⇒R(a, x)) (iv) ∃x(D(x) ∧R(x, b) ∧ ¬R(x, a)) (v) ∀x∀y((D(x) ∧D(y))⇒ (R(x, y) ∨R(y, x))) (vi) ∀x∀y∀z((D(x) ∧D(y) ∧D(z))⇒ ((R(x, y) ∧R(y, z))⇒R(x, z))) P4.7 (i) ¬∀x(D(x)⇒∃y(E(y) ∧ L(x, y))) (ii) ∀x(D(x)⇒¬∃y(E(y) ∧ L(x, y))) (iii) ∃x(D(x) ∧ ¬∃y(E(y) ∧ L(x, y))) (iv) ¬∃x(∀y(E(y)⇒ L(x, y))) (v) ¬∀x(D(x)⇒R(a, x)) (vi) ∀x(D(x)⇒¬R(a, x)) (vii) ∀y(E(y)⇒∃x(D(x) ∧ L(x, y))) (viii) ¬∀y(E(y)⇒∃x(M(x) ∧D(x) ∧ L(x, y))) (ix) (∀x(D(x)⇒M(x)))⇒ (∀x(D(x)⇒¬∃y(L(x, y) ∧ E(y)))) P4.8 Here is how we might capture “z is a mouse”: M(z), and here is how we can say that “x is a cat who likes mice”: C(x)∧∀y(M(y)⇒L(x, y)). Now we want to say that if both of those two statements are true then z does not like x, and that’s that case no matter which z and which x we are talking about: ∀x∀z ( M(z) ∧ C(x) ∧ ∀y(M(y)⇒ L(x, y))⇒¬L(z, x) ) Now, as a bonus exercise, turn that into clausal form! P4.9 For any formula G and variable x, ¬∀xG ≡ ∃x¬G, and ¬∃xG ≡ ∀x¬G. Interpret the formula ¬∀x(D(x)⇒ ∃y(E(y) ∧ L(x, y))) in natural language, then use these equivalences to “push the negation” through each of the quantifiers and connectives, and re-interpret the result in natural language. Reflect on why these are saying the same thing. ¬∀x(D(x)⇒ ∃y(E(y) ∧ L(x, y))) says “It’s not the case that every duck lays an egg”. If we push negation all the way in, the resulting equivalent formula is ∃x(D(x) ∧ ∀y(E(y)⇒¬L(x, y))). This says that there is a duck which doesn’t lay any egg at all, i.e. taking any particular egg, we claim the duck doesn’t lay that egg. P4.10 In the following formulas, identify which variables are bound to which quantifiers, and which variables are free. (i) In ∀y(D(x) ∧ ∃x(E(y) ⇔ L(x, y))) the first occurrence of x is free and the second is bound to the existential quantifier. Both y’s are bound to the universal quantifier (ii) In ∃z(E(z) ∧ M(y)) ⇒ ∀y(E(z) ∧ M(y)), the first occurrence of z is bound to the existential quantifier, and the second is free. The first occurrence of y is free and the second is bound to the universal quantifier. 3 (iii) In ∃x((E(x) ∧ M(y)) ⇒ ∀y(E(x) ∧ M(y))), both occurences of x are bound to the existential quantifier. The first occurrence of y is free and the second is bound to the universal quantifier. (iv) In ∀z(∃z(D(z))⇒D(z)), the first occurrence of z is bound to the existential quantifier, and the second is bound to the universal quantifier. (v) In ∃u((D(z) ∧ ∀x(M(x)⇒D(x)))⇒ ∀z(L(x, z))), the first occurrence of z is free, and the second is bound to the ∀z. The first two occurrences of x are bound to the ∀x, and the second is free. (vi) In ∀x(∀y(M(x) ⇒ D(x)) ∧ ∃y(D(y) ∧ ∀y(L(y, x)))), all occurrences of x are bound to the ∀x. The first occurrence of y is bound to the ∃y, and the second is bound to the last ∀y. 4