/Users/billy/gits/moc-2021/problem-sets/ps03.dvi
School of Computing and Information Systems
COMP30026 Models of Computation Problem Set 3
9–13 August 2021
Content: conversion to CNF, resolution for propositional logic, logical consequence
The exercises
P3.1 Put the following formulas in reduced CNF (conjunctive normal form):
(a) ¬(A ∧ ¬(B ∧ C))
(b) A ∨ (¬B ∧ (C ∨ (¬D ∧ ¬A)))
(c) ((A ∨B)⇒ (C ∧D))
(d) A ∧ (B ⇒ (A⇒B))
P3.2 Find the reduced CNF of ¬((¬B ⇒¬A)⇒ ((¬B ⇒ A)⇒ B)) and express the result as a set
of sets of literals. Then determine whether a refutation of the set is possible.
P3.3 Use resolution to show that each of these formulas is a tautology:
(a) (P ∨Q)⇒ (Q ∨ P )
(b) (¬P ⇒ P )⇒ P
(c) ((P ⇒Q)⇒ P )⇒ P
(d) P ⇔ ((P ⇒Q)⇒ P )
P3.4 For each of the following clause sets, write down a propositional formula in CNF to which it
corresponds. Which of the resulting formulas are satisfiable? Give models of those that are.
(a) {{A,B}, {¬A,¬B}, {¬A,B}}
(b) {{A,¬B}, {¬A}, {B}}
(c) {{A}, ∅}
(d) {{A,B}, {¬A,¬B}, {B,C}, {¬B,¬C}, {A,C}, {¬A,¬C}}
P3.5 Consider these assumptions:
(a) If Ann can clear 2 meters, she will be selected.
(b) If Ann trains hard then, if she gets the flu, the selectors will be sympathetic.
(c) If Ann trains hard and does not get the flu, she can clear 2 meters.
(d) If the selectors are sympathetic, Ann will be selected.
Does it follow that Ann will be selected? Does she get selected if she trains hard? Use any of
the propositional logic techniques we have discussed, to answer these questions.
P3.6 Consider the following four statements:
(a) The commissioner cannot attend the function unless he resigns and apologises.
(b) The commissioner can attend the function if he resigns and apologises.
(c) The commissioner can attend the function if he resigns.
(d) The commissioner can attend the function only if he apologises.
Identify the basic propositions involved and discuss how to translate the statements into
propositional logic. In particular, what is the translation of a statement of the form “X does
not happen unless Y happens”? Identify cases where one of the statements implies some other
statement in the list.
P3.7 Letting F and G be two different formulas from the set
{(P ∧Q) ∨R, (P ∨Q) ∧R, P ∧ (Q ∨R), P ∨ (Q ∧R)}
list all combinations that satisfy F |= G.
P3.8 In this week’s lecture, a claim is made that the formula
(P ∧Q ∧R) ∨ (¬P ∧ ¬Q ∧ ¬R) ∨ (¬P ∧R) ∨ (Q ∧ ¬R)
is logically equivalent to the simpler
¬P ∨Q
with both being in reduced disjunctive normal form (RDNF). Show that the claim is correct.
P3.9 In the previous question we saw that this formula F :
(P ∧Q ∧R) ∨ (¬P ∧ ¬Q ∧ ¬R) ∨ (¬P ∧R) ∨ (Q ∧ ¬R)
is independent of R. We may say that the formula depends on R syntactically (because R
occurs in it), but not semantically. Find a smallest possible CNF formula, equivalent to F ,
that depends syntactically on P , Q and R.
P3.10 Using resolution, show that the set {{P,R,¬S}, {P, S}, {¬Q}, {Q,¬R,¬S}, {¬P,Q}} of clauses
is unsatisfiable.