I have the following boolean algebra equations. They are supposed to be equivalent for $ab=FF, FT, TF$. I can show it with truth tables, but how can I prove it algebraically? $$ \begin{cases} x_1 = \neg (b \lor y_1) \\ \tag 1 y_1 = \neg (a \lor x_1) \\ \end{cases} $$ $$ \begin{cases} x_2 = \neg (\neg a \land y_2) \\ \tag 2 y_2 =\neg (\neg b \land x_2) \end{cases} $$ Starting with $x_1=x_2$: \begin{align} \neg (b \lor y_1)&= \neg (\neg a \land y_2) \\ \neg b \land \neg y_1&= a\lor\neg(y_2)\\ \end{align} I'm stuck here.

For $y_1=y_2$ I have: \begin{align} \neg (a \lor x_1) &= \neg (\neg b \land x_2) \\ \neg a \land \neg x_1 &= b \lor \neg x_2 \\ \end{align} I'm also stuck here, how to proceed?

  • $\begingroup$ What do you mean by them being "equivalent for ab = ....". What is equivalent to what and in what sense? $\endgroup$
    – Bram28
    Apr 20 '20 at 16:32

I would just plug in those different truth-value combination for $a$ and $b$.

So, for example, when $ab=FF$, you get:

$$ \begin{cases} x_1 = \neg (F \lor y_1) = \neg y_1\\ \tag 1 y_1 = \neg (F \lor x_1) = \neg x_1 \\ \end{cases} $$ $$ \begin{cases} x_2 = \neg (\neg F \land y_2) = \neg (T \land y_2) = \neg y_2\\ \tag 2 y_2 =\neg (\neg F \land x_2) = \neg (T \land x_2) = \neg x_2\\ \end{cases} $$

You can see these two sets of equations are equivalent, in that you can set $x_1=x_2$ and $y_1 = y_2$ to get the same equations.

Do the same for the other truth-value pairs ... and finally show that you do not get an equivalence when $ab=TT$.

I am not sure how to just take the equations and solve for $a$ and $b$ ... also because it is not clear that you always need to have that $x_1=x_2$ and $y_1=y_2$ in order to get equivalence: in the above example you can also set $x_1=y_2$ and $y_1=x_2$ to demonstrate equivalence.


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.