# Satisfying a t-variable boolean clause

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.

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.