2
$\begingroup$

$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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .