Assignment 3
1. (a) Show that {P, Q, ¬(P ∧Q)} is an unsatisfiable 3-element set, each of whose 2-element subsets is satisfiable.
(b) For every n ≥ 3, find an example of an unsatisfiable n-element set, each of whose (n − 1)-element subsets is satisfiable.
2. Show that ϕ is a tautology if and only if {¬ϕ} is unsatisfiable.
3. Use the DPP to decide whether the following sets of clauses are satis- fiable.
(a) {{¬Q, T}, {P, ¬Q}, {¬Q, ¬S}, {¬P, ¬R}, {P, ¬R, S}, {Q, S, ¬T}, {¬P, S, ¬T}, {Q, ¬S}, {Q, R, T}}
(b) {{¬Q, R, T}, {¬P, ¬R}, {¬P, S, ¬T}, {P, ¬Q}, {P, ¬R, S}, {Q, S, ¬T}, {¬Q, ¬S}, {¬Q, T}}
4. Decide whether each of the following arguments are valid by first con-verting to a question of satisfiability of clauses (see the Proposition on page 3 of Week 3 Slides), and then using the DPP.
(Note that using DPP is not the easiest way to decide validity for these arguments, so you may want to use other methods to check your an-swers, but do not submit them with your assignment.)
(a) (P → Q), (Q → R), (R → S), (S → T) therefore (P → T).
(b) (P ∨ Q), (Q ∨ R), (R ∨ S), (S ∨ T) therefore (P ∨ T).
(c) (P → Q), (Q → R), ¬R, therefore ¬P.