Exercises 133- Find a CNF for each of the following formulas, and prove that each formula is a
tautology.
(a) (p Ap) +-p
(b) (p A (p -* q)) - q(c) (p -+(r - q)) -((p A r) -)- q)
(d) (p -- r) (--r - p)
- (a) Show that the following formula in CNF is unsatisfiable:
(p V q) A (p V --q) A (-'p V q) A (-p V --q)
(b) Show that the following formula in CNF is unsatisfiable:(p V q V r) A (p V -q V r) A (-p V q V r) A (--p V --q V r)
A (p V q V -'r) A (p V -q V --r) A (-'p V q V -"r) A (-p V -,q V -,r)
Can you find an easier argument than just writing the entire truth table?
(c) Generalize the above to some class of CNF formulas on an arbitrary number n > 1
of proposition letters, and prove it by induction on n.- (a) Prove that the formula -p is not equivalent to any formula built from the proposi-
tion letters T and F using only A and V plus parentheses.
(b) Prove that the formula p V q is not equivalent to any formula built from the propo-
sition letters using only +*.
(c) Prove that there is a formula not equivalent to any formula built from the proposi-
tion letters using only v. (See Exercise 22 in Section 2.4.)
(d) Prove that there is a formula not equivalent to any formula built from the proposi-
tion letters using only -) plus parentheses.- Write pseudocode for a program that, given a formula 0, finds (i) a logically equivalent
formula 0' in CNF and (ii) a logically equivalent formula 0" in DNF The algorithm
should be recursive (similar to an induction on formulas) and should not involve the
construction of truth tables. Prove the algorithm works. This gives an alternate proof
of the theorem that every formula is equivalent to a formula in CNE
Definition A k-term is a conjunction of k literals. A k-DNF formula is a disjunction of
k-terms.
- (a) Show that every formula containing only k (different) proposition letters is equiv-
alent to a k-DNF formula.
(b) Show that p ++ q is not equivalent to any 1 -DNF formula.
(c) Show that for every natural number k (including 0), there is a formula contain-
ing only k + 1 (different) proposition letters that is not equivalent to any k-DNF
formula.
13. (a) Find the resolvant of (p V q) and (-'p V r) on p.
(b) Find the resolvant of (p V q V r V s) and (-p V -q V t) on p.
(c) Find the resolvant of (p V q) and -p on p.
(d) Find the resolvant of (p) and (-p) on p.
(e) Which resolvant above from parts (a) through (d) is a tautology? Which is tauto-
logically false?- Write resolution refutations of the following sets of clauses. Include line numbers and
justifications, as in Example 12.