Reduce ((y ⊕ z) ⇒ (x + y)) ⇒ yz to disjunctive normal form (DNF)

Question

How can I reduce this boolean function to disjunctive normal form? $$((y ⊕ z) ⇒ (x + y)) ⇒ yz$$ It may be possible to do using truth tables, but I am not sure. If it's possible to give examples with explanation to understand the steps? Thanks

Answer 1

To write a DNF, we're looking for the cases (actually disjunction of cases) in a conjunctive form that make the function false, so that negating them yields a conjuction of disjunctions that makes the function true.

An implication is false if and only if the premise is true and the conclusion false. Therefore we're looking for the case $(y\oplus z)\Rightarrow(x+y)$ true and $yz$ false. $yz$ is false iff at least one of $y$, $z$ is false.

The implication $(y\oplus z)\Rightarrow(x+y)$ is always true if $y\oplus z$ is false, i.e. $y=z=\text{true}$ or $y=z=\text{false}$. Since one of $y,z$ is false, $y=z=\text{false}$ regardless of $x$ i.e. the conjunction $(\neg y\land \neg z)$ makes the function false.

Else, the implication $(y\oplus z)\Rightarrow(x+y)$ is true if $y\oplus z$ is true and $x+y$ is true. Since one of $y,z$ is false, either $y$ false and $x$ true and $z$ true i.e. $(x \land \neg y \land z)$, or $z$ false and $y$ true regardless of $x$ i.e. $(y \land \neg z)$ make the function false.

Therefore, the following expression is equivalent to the given function

$$\neg((\neg y\land \neg z)\lor(x \land \neg y \land z)\lor(y \land \neg z))$$

i.e. (with a bit of reduction, the $y$ and $\neg y$ cancel each other after factoring $\neg z$)

$$(z) \land (\neg x \lor y \lor \neg z) $$

and again removing the $\neg z$ given the $(z)$ in the conjunction,

$$(z) \land (\neg x \lor y) $$

which is the DNF you're looking for.