/Users/billy/gits/moc-2021/problem-sets/ps04.dvi
School of Computing and Information Systems
COMP30026 Models of Computation Problem Set 4
16–20 August 2021
Content: Solving problems with propositional logic (part 1), translating natural language to
predicate logic (part 2).
Part 1 – Propositional Logic
P4.1 On the Island of Knights and Knaves, everyone is a knight or knave. Knights always tell the
truth. Knaves always lie. You meet three people, let us call them A, B and C. A says to you:
“If I am a knight then my two friends here are knaves.” Use propositional logic to determine
whether this statement gives you any real information. What, if anything, can be deduced
about A, B, and C?
P4.2 Low-level programming languages (including C) offer bitwise operators, including bitwise nega-
tion, conjunction, disjunction and exclusive or. Bitwise means the logical operation is applied
bit for bit, across whole words, with 0 representing false and 1 representing true. In such
languages an expression like 53 ⊕ 42 evaluates to 31, because the exclusive or operator ⊕ is
applied bit by bit to the binary representations of 53 and 42:
. . . 0 1 1 0 1 0 1
. . . 0 1 0 1 0 1 0
. . . 0 0 1 1 1 1 1
and this yields the binary representation of 31.
When the task is to swap the contents of two registers on a machine with few registers available,
an old idea is the “xor trick”. To swap the contents of R1 and R2, rather than call upon a
third register, we can perform three xor operations on R1 and R2.
R1 := R1 ⊕R2
R2 := R1 ⊕R2
R1 := R1 ⊕R2
Explain why that has the desired effect.
P4.3 Given these six formulas:
F1 : (P ⇒¬Q) ∧ (P ⇒¬R)
F2 : (P ⇒¬Q) ∨ (P ⇒¬R)
F3 : (Q ∧R)⇒¬P
F4 : P ∨Q ∨R
F5 : ¬P ∨ ¬Q ∨ ¬R
F6 : P ⇒¬(Q ∧R)
group logically equivalent formulas together.
P4.4 A graph colouring is an assignment of colours to nodes so that no edge in the graph connects
two nodes of the same colour. The graph colouring problem asks whether a graph can be
coloured using some fixed number of colours. The question is of great interest, because many
scheduling problems are graph colouring problems in disguise. The case of three colours is
known to be hard (NP-complete).
How can we encode the three-colouring problem in propositional logic, in CNF to be precise?
(One reason we might want to do so is that we can then make use of a SAT solver to determine
colourability.) Using propositional variables
• Bi to mean node i is blue,
• Gi to mean node i is green,
• Ri to mean node i is red;
• Eij to mean i and j are different but connected by an edge,
write formulas in CNF for these statements:
(a) Every node (0 to n inclusive) is coloured.
(b) Every node has at most one colour.
(c) No two connected nodes have the same colour.
For a graph with n+ 1 nodes, what is the size of the CNF formula?
P4.5 In the Week 3 lecture we saw that conjunctive normal form (CNF) and disjunctive normal
form (DNF) are not canonical. For example, (¬P∨¬Q∨¬R)∧(P∨Q∨R)∧(P∨¬R)∧(¬Q∨R)
and the logically equivalent P ∧ ¬Q are both in reduced CNF. It would be nice if equivalent
formulas were syntactically identical. For one thing, equivalence checking would then become
much simpler, just checking that the given formulas are the same.
It turns out that we can achieve this if we use exclusive or (⊕) instead of or (∨). XNF
(exclusive-or normal form) can express every possible Boolean function. In XNF, a Boolean
function is expressed as a sum of products, with addition corresponding to exclusive or, ⊕,
and multiplication corresponding to conjunction, ∧. For example, instead of P ∧ (Q⇔R) we
write P ⊕ (P ∧Q)⊕ (P ∧R). Actually we usually abbreviate this to P ⊕ PQ⊕ PR, with the
understanding that a “product” PQ is a conjunction. We call an expression like this—one
that is written as a sum of products—a polynomial. Each summand (like PQ) is a monomial.
The connective ¬ is not used in XNF, only ⊕ and ∧. To compensate, one of the truth value
constants, t, is needed. If F is a formula in XNF then F ⊕ t is its negation. The other
constant, f , is not needed. This is because f is like zero: It is a “neutral element” for ⊕ (that
is, F ⊕ f is just F ) and it is an “annihilator” for ∧ (F ∧ f is just f). So we can’t have f in a
monomial, because the entire monomial disappears if f enters it. And we don’t need f as a
monomial, because “adding” f really adds nothing.
In this “Boolean ring” algebra, we are really dealing with arithmetic modulo 2, with ∧ playing
the role of multiplication, and ⊕ playing to role of addition. Given this, express these in XNF:
(a) ¬P (b) P ∧Q (c) P ∧ ¬Q (d) P ⇔Q (e) P ∨Q (f) P ∨ (Q ∧R)
Note that ∧ distributes over ⊕, but not the other way round. Also note carefully “cancelling
out” properties. If we conjoin the monomials PQR and PRST , we get PQRST ; that is,
“duplicates disappear”. However, if we have F = µ1 ⊕ µ2 ⊕ µ3 and F
′ = µ2 ⊕ µ3 ⊕ µ4 and we
want to find F ⊕ F ′, then we find that “duplicates cancel out pairwise”: F ⊕ F ′ = µ1 ⊕ µ4.
This happens because F ⊕ F = f for all Boolean functions F .
Given this, turn these into XNF:
(g) ¬(P ⊕Q)
(j) Q ∧ (P ⊕ PQ⊕ t)
(h) (P ⊕Q) ∧R
(k) Q ∨ (P ⊕ PQ)
(i) (PQ⊕ PQR⊕R) ∧ (P ⊕Q)
Part 2 – Predicate Logic
P4.6 Translate the following formulas into predicate logic, using D(x) for “x is a duck”, M(x) for
“x is muddy”, F (x, y) for “x follows y” and R(x, y) for “x is muddier y”. Use the constant a
as a name for Jemima, and b for Louise.
(i) Every duck who follows a muddy duck is
muddy
(ii) Any muddy duck is muddier than any
duck that isn’t muddy
(iii) Jemima is muddier than any duck who is
muddier than Louise
(iv) There is a duck who is muddier than
Louise, but not as muddy as Jemima
(v) Given any two ducks, one is muddier
than the other
(vi) Given any three ducks, if the first is mud-
dier than the second, and the second is
muddier than the third, then the first is
muddier than the third
P4.7 Translate the following formulas into predicate logic, using D(x) for “x is a duck”, M(x) for
“x is muddy”, E(x) for “x is an egg”, L(x, y) for “x lays y”, and R(x, y) for “x is muddier
y”. Use the constant a as a name for Jemima, and b for Louise.
(i) Not every duck lays an egg
(ii) Every duck doesn’t lay an egg
(iii) There is a duck that doesn’t lay an egg
(iv) There isn’t a duck who lays every egg
(v) Louise is not muddier than every duck
(vi) Louise is not muddier than any duck
(vii) Every egg has a duck who layed it
(viii) Not every egg is layed by a muddy duck
(ix) If every duck is muddy then no duck lays
an egg
P4.8 Consider the following predicates: C(x), which stands for “x is a cat”, M(x), which stands for
“x is a mouse”, and L(x, y), which stands for “x likes y”. Express the statement “No mouse
likes a cat who likes mice” as a formula in first-order predicate logic. Here “likes mice” means
“likes every mouse”.
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.
P4.10 In the following formulas, identify which variables are bound to which quantifiers, and which
variables are free.
(i) ∀y(D(x) ∧ ∃x(E(y)⇔ L(x, y)))
(ii) ∃z(E(z) ∧M(y))⇒∀y(E(z) ∧M(y))
(iii) ∃x((E(x) ∧M(y))⇒∀y(E(x) ∧M(y)))
(iv) ∀z(∃z(D(z))⇒D(z))
(v) ∃u((D(z) ∧ ∀x(M(x)⇒D(x)))⇒∀z(L(x, z)))
(vi) ∀x(∀y(M(x)⇒D(x)) ∧ ∃y(D(y) ∧ ∀y(L(y, x))))