Boolean algebra: Why does the equation hold?

80 Views Asked by At

I want to show that $$\bar y\land (x\lor z)\land (\bar x \lor \bar y) = \bar y\land (x\lor z)$$

I have done the following: \begin{align*}\bar y\land (x\lor z)\land (\bar x \lor \bar y) &=\bar y\land \left [(x\lor z)\land (\bar x \lor \bar y)\right ]\\ & =\bar y\land \left [\left ((x\lor z)\land \bar x\right )\lor \left ((x\lor z)\land \bar y\right )\right ] \\ & = \bar y\land \left [\left (\left (x\land \bar x\right )\lor \left (z\land \bar x\right )\right )\lor \left (\left ( x\land \bar y\right )\lor \left (z\land \bar y\right )\right )\right ] \\ & = \bar y\land \left [\left (0\lor \left (z\land \bar x\right )\right )\lor \left (\left ( x\land \bar y\right )\lor \left (z\land \bar y\right )\right )\right ] \\ & = \bar y\land \left [\left (z\land \bar x\right )\lor \left ( x\land \bar y\right )\lor \left (z\land \bar y\right )\right ]\end{align*} Is everything correct so far? How can we continue?

1

There are 1 best solutions below

3
On BEST ANSWER

You want to show $$\bar y\land (x\lor z)\land (\bar x \lor \bar y) = \bar y\land (x\lor z)$$

Intuitively, the left hand side of this says that $y$ must be false (because we have $\bar y \land \dots$), and so $(\bar x \lor \bar y)$ is a tautology—it is always true. So we can rewrite this as $\bar y \land (x \lor z)$, which is exactly the right hand side. So they are equivalent statements.

More rigorously,

$$ \begin{align} \bar y \land (x \lor z) \land (\bar x \lor \bar y) \\ =\bar y \land (\bar x \lor \bar y) \land (x \lor z) && \text{commutativity} \\ =\bar y \land (x \lor z) && \text{absorption} \\ \end{align} $$

The ‘absorption’ law we just used is a standard identity but if you really want proof,

$$ \begin{align} x \land (x \lor y) \\ =(x \land x) \lor (x \land y) && \text{distributive} \\ =x \lor (x \land y) && \text{idempotent} \\ =(x \land 1) \lor (x \land y) && \text{identity} \\ =x \land (1 \lor y) && \text{distributive} \\ =x \land 1 && \text{annulment} \\ =x && \text{identity} \\ \end{align} $$