Models of Computation - Mathematics 450 - Spring 2005
For HW #27
Here I will use v for OR, ^ for AND, and ~ for NOT. Thus, {x1 v
~x2} means {x1, x2}
(in Wilf's notation).
Explain why {x1 v x2 v ... v xk}
is equivalent to {x1 v z} ^ {~z v x2 v ... v xk}.
"Equivalent" means one is true iff the other is.
Is {x1 v x2 v ... v xk} equivalent to
{x1 v x2 v z} ^ {~z v x3 v ... v xk}?
Why?
Explain how, by repeatedly applying part b. above, we can arrive at
expression (5.4) at the top of page 187 in Wilf.
It may seem that by repeatedly applying part a. above, we might
actually be able to reduce SAT to 2SAT (instead of just to 3SAT, as in
Wilf). Explain why this will not work.
Wilf, page 187, line -8 says: "We remark, in passing, that the
problem '2SAT' is in P."
Can you prove this?