Question

Q2. Convert the following instance of SAT problem to an instance of 3SAT problenm

Answer 1

We will convert SAT instance into 3SAT instance by adding free variable such that each clause has only 3 variables .

So here is the solution:-

$(x_1 \vee x_2 \vee a_1) \wedge (\neg a_1 \vee x_3 \vee a_2) \wedge (\neg a_2 \vee x_4 \vee a_3) \wedge (\neg a_3 \vee x_5 \neg x_5)$

$\wedge (y_1 \vee y_2 \vee b_1) \wedge (\neg b_1 \vee \neg y_3 \vee b_2) \wedge (\neg b_2 \vee y_4 \vee y_5)$

$\wedge (z_1 \vee z_2 \vee c_1) \wedge (z_1 \vee z_2 \vee \neg c_1)$

$\wedge (w_1 \vee d_1 \vee d_2) \wedge (w_1 \vee \neg d_1 \vee d_2) \wedge (w_1 \vee d_1 \vee \neg d_2) \wedge (w_1 \vee \neg d_1 \vee \neg d_2)$

In above formula we have added free variable just to make each clause containing exactly 3 literals, but the satisfiability still depends upon original variables and not on free variables.

Please comment for any clarification.