CS计算机代考程序代写 /Users/billy/gits/moc-2021/problem-sets/ps04.dvi

/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))))