2

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?

Mary Star
  • 13,956
  • 2
    This may help a bit $$(x\land\bar y)\lor(z\land\bar y)=(x\lor z)\land\bar y$$ Then this with $\bar y$ at the front just combines to give the same thing – John Doe Apr 30 '19 at 17:14
  • 1
    From an intuitive viewpoint, the last OR on the LHS is superfluous, because $y$ already has to be false for $\bar{y}$ to be true, which makes $\bar{x}\lor\bar{y}$ true. – Adrian Keister Apr 30 '19 at 17:15
  • Do you mean the following? \begin{align} \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 ]&= \bar y\land \left [\left (z\land \bar x\right )\lor(x\lor z)\land\bar y\right ] \ & =\left [\bar y\land \left (z\land \bar x\right )\right ]\lor\left [\bar y\land(x\lor z)\land\bar y\right ] \ & = \left [\bar y\land \left (z\land \bar x\right )\right ]\lor\left [\bar y\land(x\lor z)\right ]\end{align} Ho could we continue? @JohnDoe – Mary Star Apr 30 '19 at 17:21
  • Could you explain that further to me? @AdrianKeister – Mary Star Apr 30 '19 at 17:27

1 Answers1

2

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} $$

雨が好きな人
  • 2,555
  • 1
  • 8
  • 18
  • Do you mean the following? \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)\ & =\left [(\bar y \land \bar x) \lor (\bar y \land \bar y) \right ]\land (x \lor z)\ & = \left [(\bar y \land \bar x) \lor 0 \right ]\land (x \lor z) \ & = (\bar y \land \bar x) \land (x \lor z)\end{align} How could we continue? – Mary Star Apr 30 '19 at 18:02
  • 1
    Check my edited version. $(\bar y \land \bar y) = \bar y$, rather than $0$. – 雨が好きな人 Apr 30 '19 at 18:06
  • I got it!! Thank you so much!!! :-) – Mary Star Apr 30 '19 at 21:42