2
$\begingroup$

For a given clause: $$\varphi = x_1 \vee x_2 \vee x_3 \vee \dots \vee x_t$$ We construct a new clause: $$\psi = (x_1 \leftrightarrow \overline{y_1}) \wedge \bigl((\overline{y_1}\vee x_2)\leftrightarrow \overline{y_2}\bigr) \wedge \dots \wedge \bigl((\overline{y_{t-1}} \vee x_t) \leftrightarrow \overline{y_t} \bigr) \wedge (\overline{y_t}) $$

Prove:

  1. Let $a_1,\dots,a_t$ to be a satisfying assignment for $\varphi$ then one unique assignment $b_1,\dots,b_t$ exists for the variables $y_1,\dots,y_t$ such that $a_1,\dots,a_t,b_1,\dots,b_t$ satisfies $\psi$.
  2. Let $a_1,\dots,a_t,b_1,\dots,b_t$ be an assignment that satisfies $\psi$ then $a_1,\dots,a_t$ is an assignment that satisfies $\varphi$.

I could understand that the value of $y_t$ has to be $False$ and that $a_1 = \overline{x_1}$, and that maybe this could imply on the values of the rest of the variables. As for the second proof, my approach was to prove the counter-positive claim which is: if $a_1,\dots,a_t$ does not satisfy $\varphi$ then $a_1,\dots,a_t,b_1,\dots,b_t$ does not satisfy $\psi$. Note that the only assignment that does not satisfy $\varphi$ is $x_i = False \, \forall x_i$.

Any guidance and assistance are appreciated, thanks.

$\endgroup$
2
$\begingroup$

For 1:

Let $a_1,\dots,a_t$ to be a satisfying assignment for $\varphi$. Now suppose $a_1,\dots,a_t,b_1,\dots,b_t$ satisfies $\psi$.

Let $i$ be the smallest index with $a_i = True$

Since we need to satisfy $(\overline{y_{i-1}}\vee x_i)\leftrightarrow \overline{y_i}$, and since $x_i$ is satisfied, that means that $\overline{y_{i-1}}\vee x_i$ is satisfied, and hence we need to satisfy $\overline{y_i}$, meaning that we need to set $b_i=False$. Moreover, once we have satisfied $\overline{y_i}$, we will have satisfied $\overline{y_i}\vee x_{i+1}$, and since we need to satisfy $(\overline{y_i}\vee x_{i+1})\leftrightarrow \overline{y_{i+1}}$, we see that we need to satisfy $\overline{y_{i+1}}$, i.e. we need to set $b_{i+1}=False$. And this of course repeats for all higher indices, i.e. we need to set $b_j=False$ for all $i \le j \le t$ (which, by the way, will satisfy $\overline{y_t}$, so we're good at the 'tail end' of $\psi$.

OK, if $i=1$, then this will in fact fix all $b_i$'s (and this will satisfy $x_1 \leftrightarrow \overline{y_1}$, so there is indeed one unique assignment. If $i>1$, then $a_1=False$, meaning that $x_1$ is not satisfied, meaning that we have to satisfy $x_1 \leftrightarrow \overline{y_1}$ by not satisfying $\overline{y_1}$, i.e. by setting $b_1=True$. But this means that if $i>2$, then $\overline{y_1}\vee x_2$ is not satisfied, and hence to satisfy $\bigl((\overline{y_1}\vee x_2)\leftrightarrow \overline{y_2}\bigr)$ we need to not satisfy $\overline{y_2}$, i.e. we need to set $b_2=True$. This repeats, until we get to $i-1$. Since we need to satisfy $ (\overline{y_{i-2}}\vee x_{i-1})\leftrightarrow \overline{y_{i-1}}$, and since $\overline{y_{i-2}}\vee x_{i-1}$ is not satisfied, we must not satisfy $\overline{y_{i-1}}$, i.e. we must set $b_{i-1} = True$.

And there you have it: in order to satisfy $\psi$, we are forced to set $b_j=True$ for all $1 \le j < i$, and $b_j=False$ for all $i \le j \le t$, where $i$ is the smallest index with $a_i = True$

For 2:

Yes, you are right, proving the contrapositive is a good way to go. So: assume $a_1,\dots,a_t$ does not satisfy $\varphi$. Then, as you correctly point out, we have $a_i=False$ for all $1 \le i \le t$. So, since none of $x_i$ is satisfied, $\psi$ is satisfied iff $$\psi' = (\neg \overline{y_1}) \wedge \bigl(\overline{y_1}\leftrightarrow \overline{y_2}\bigr) \wedge \dots \wedge \bigl(\overline{y_{t-1}} \leftrightarrow \overline{y_t} \bigr) \wedge (\overline{y_t}) $$ is satisfied, and that means we need to satisfy $\overline{y_t}$, and since we need to satisfy $\overline{y_{t-1}} \leftrightarrow \overline{y_t} $ we therefore also need to satisfy $\overline{y_{t-1}}$, etc. all the way down to $\overline{y_1}$ .. but that does not satisfy $\neg \overline{y_1}$. Hence, there is no possible way to satisfy $\psi'$, and therefore also no way to satisfy $\psi$.

Of course, we could have used the proof for 1) here as well, since that showed that if $a_j=False$ for all $1 \le j \le i$, we must set $b_j=True$ for all $1 \le j \le i-1$. So, since in fact $a_j=False$ for all $1 \le j \le t$, we get that $b_j=True$ for all $1 \le j \le t-1$. But since we need to satisfy $\bigl((\overline{y_{t-1}} \vee x_t ) \leftrightarrow \overline{y_t} \bigr)$, and since $b_{t-1}=True$, we have that neither $x_t$ nor $\overline{y_{t-1}}$ are satisfied, meaning that $\overline{y_{t-1}} \vee x_t $ is not satisfied either, and hence we must not satisfy $\overline{y_t}$. But since that is the last term of $\psi$, $\psi$ will not be satisfied.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.