The University of Melbourne
School of Computing and Information Systems COMP30026 Models of Computation
Sample Answers to Tutorial Exercises, Week 4
30. 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:
Ah A F 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.
31. 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.
32. The formulas F2, F3, F5, and F6 are logically equivalent. Grouping the formulas into sets of
equivalent formulas, we get
1
{{F1}, {F4}, {F2, F3, F5, F6}} This can easily be verified by completing the truth tables.
33. 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).
34. (a)
(b) (c) (d) (e)
¬P becomes . 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.
P ∧ Q is unchanged, or we can write simply .
P ∧ ¬Q can be written P (Q ⊕ t), so by “multiplying out” we get .
P ⇔ Q becomes (since biimplication is the negation of exclusive or).
P ∨ Q becomes , 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
P⊕t
PQ
PQ⊕P
P⊕Q⊕t
P⊕Q⊕PQ
t Q P POD t ⊕ ((t ⊕ P )(t ⊕ Q)). Now all we need to do is to simplify that formula (come on, do it).
potatoPQ oubleNegation
(f) Using the insight from part (e), we transform P ∨ (Q ∧ R) to
(g) Negation is just ‘⊕t’, so we can write ¬(P ⊕Q) as P ⊕Q⊕t .
.
QAR
P ⊕QR⊕PQR
T
QR
(h) For (P ⊕ Q) ∧ R, we just “multiply out”, to get .
(i) Given (P Q ⊕ P QR ⊕ 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
=
(j) Given Q∧(P ⊕PQ⊕t) we multiply out, to get PQ⊕PQ⊕Q, that is, .
(k) Frompart(e)weknowthatA∨B≡A⊕B⊕AB. ApplyingthattoQ∨(P⊕PQ)we
obtain the formula Q ⊕ P ⊕ P Q ⊕ (Q(P ⊕ P Q)). Multiplying out, we get Q⊕P⊕PQ⊕PQ⊕PQ=
(So the formula in (k) must be equivalent to P ∨ Q.)
PR⊕QR
PR⊕QR
Q
P⊕Q⊕PQ
2