Consider the clause A x y z u w Show that there is a set of

Consider the clause A = x y z u w. Show that there is a set of 4-clauses B so that A is satisfiable if and only if conjunctive normal form (CNF) using all clauses in B is satisfiable. Note: you can use new variables in B.

Solution

A formula in conjunctive normal form (CNF) is propositional formula which is a conjunction of clauses (A) (x1 x2 ¬x4) (x2 ¬x3) x5 is a CNF formula

How SAT is different from 3SAT?In SAT clauses might have arbitrary length: 1, 2, 3, . . . variables: ( x y z w u ) ( ¬x ¬y ¬z w u ) ( ¬x )

In 3 SATISFIABLE every clause must have exactly 3 different literals. To reduce from an instance of SAT to an instance of 3SAT, we must make all clauses to have exactly 3 variables... Basic idea

(A) Pad short clauses so they have 3 literals.

(B) Break long clauses into shorter clauses.

(C) Repeat the above till we have a 3CNF.

Clauses with more than 3 literals Let c = 1 · · · k. Let u1, . . . uk3 be new variables. Consider c = ( 1 2 u1 ) ( 3 ¬u1 u2 ) ( 4 ¬u2 u3 ) · · · ( k2 ¬uk4 uk3 ) ( k1 k ¬uk3 ) .

c is satisfiable if and only if c is satisfiable.

Another way to see it — reduce size of clause by one:

c = ( 1 2 . . . k2 uk3 ) ( k1 k ¬uk3 ) .