A query about reducting SAT to 3SAT when there are more than 3 literals in a clause

210 Views Asked by At

$C=a∨b∨c∨d∨e$ is a clause in SAT

$D= (a∨b∨x)∧ (¯x∨c∨y)∧ (¯y∨d∨e)$ is the another form of C to make sure every clause has only threeliterals

Is D true when C is true and false when C is false? Why?

I think when $a,x,y=true$ and $b,c,d,e=false$, then C is true but D is false.

1

There are 1 best solutions below

0
On

The transformation you're using guarantees that there is a satisfying assignment for D whenever there is one for C and vice versa. It does not guarantee that any random setting of the new variables in D will produce a satisfying assignment if you copy the variable assignments from C. You must specifically set the new variables in D to satisfy any clauses left unsatisfied.