Plan
School of Computing and Information Systems COMP30026 Models of Computation Tutorial Week 4
26–28 August 2020
This is the last tutorial covering propositional logic. If you have time, do Exercise 34 and learn more about exclusive or normal form (XNF). Alternatively (or additionally), you may want to spend a bit of time on any more general questions you have, on the various logic concepts and/or Haskell. A reminder that Grok Worksheet 1 is due on 30 August.
The exercises
30. 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?
11111. Low-levelprogramminglanguages(includingC)offerbitwiseoperators,includingbitwisenega- 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:
…0110101 …0101010 …0011111
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.
32. 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.
33. 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?
34. 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 P Q) 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)
PVQR P QROPQR
Note that ∧ distributes over ⊕, but not the other way round. Also note carefully “cancelling
out” properties. If we conjoin the monomials P QR and P RST , we get P QRST ; 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) (h) (P ⊕Q)∧R (i) (PQ⊕PQR⊕R)∧(P ⊕Q)
(j) Q∧(P ⊕PQ⊕t) (k) Q∨(P ⊕PQ)
I tOtftOtP tOtQD
HotP n CtOtQD C t A t t O tC E n Q
toELOt QOtPOtPQ to to QOtPOtPQ
Q O t PO tP Q
P r t
C MQ