Plan
School of Computing and Information Systems COMP30026 Models of Computation Tutorial Week 3
19–21 August 2020
If at all possible, make sure you go over these questions before you get to the tute. Questions 24 and 25 are about translating English statements into propositional logic. This type of question often triggers more discussion, compared to the rest—feel free to continue discussing on Piazza.
The exercises
19. 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))
20. 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.
21. Using resolution, show that the set {{A, B, ¬C}, {¬A}, {A, B, C}, {A, ¬B}} of clauses is un- satisfiable.
22. Use resolution to show that each of these formulas is a tautology:
(a) (P∨Q)⇒(Q∨P) i (b) (¬P⇒P)⇒P
(c) ((P ⇒Q)⇒P)⇒P (d) P ⇔((P ⇒Q)⇒P)
23. 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}}
24. Consider these assumptions:
ask A
cs
FK D T117F
(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.
DT
TF
dk
OS ㄒ
(c) If Ann trains hard and does not get the flu, she can clear 2 meters.
s
TTC
(d) If the selectors are sympathetic, Ann will be selected.
K
S
Does it follow that Ann will be selected? Does she get selected if she trains hard? Use any of
S5
the propositional logic techniques we have discussed, to answeTr these questions.
25. (Drill.) 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.
26. (Drill.) 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.
27. (Drill.) 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.
28. (Drill.) 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,
7SP
QQ
that depends syntactically on P, Q and R.
29. (Drill.) Using resolution, show that the set {{P, R, ¬S}, {P, S}, {¬Q}, {Q, ¬R, ¬S}, {¬P, Q}}
of clauses is unsatisfiable.
GPVQVDM
PVQVTRJQJR.SI RnSRSnRQ7QP
Q
上