Three Boolean Algebra Proofs - I just don't get it!

Question

I'm having a very difficult time proving the following 3 expressions:

$$\begin{align*} &x\cdot y\cdot z+x'\cdot z=y\cdot z+x'\cdot z\\ &x\cdot y+y\cdot z+x'\cdot z=x\cdot y+x'\cdot z\\ &(x'\cdot z'+x'\cdot y+x'\cdot z+x\cdot y)'=x\cdot y' \end{align*}$$

I need to show what law/theorem/postulate is used for each step of the proof - and I don't even know where to start. The last time I did any sort of algebra was at least 7 years ago, and even then it was very basic.

Being thrown into Boolean algebra, only provided a sheet with all the theorems/etc... is proving to be impossible for me. I understand the methodology behind mathematical proofs and boolean simplification, I just don't see what theorems/laws can be used when I look at these....

Any help would be greatly appreciated here!

Answer 1

Essentially, we manipulate the equation in whatever way possible, trying to make the left-hand side look like the right-hand side. There's no real magic method here, we just keep trying until we succeed.

In the second example, we can do:

$\small \begin{align*} x\cdot y+y\cdot z+x'\cdot z &= x\cdot y + 1 \cdot (y\cdot z)+x'\cdot z & \text{identity for } \cdot \\ &= x\cdot y + (x+x') \cdot (y\cdot z)+x'\cdot z & \text{complementation } x+x'=1\\ &=x\cdot y + x\cdot (y\cdot z)+x'\cdot (y\cdot z)+x'\cdot z & \text{distributivity} \\ &=x\cdot y + (x\cdot y)\cdot z+x'\cdot (y\cdot z)+x'\cdot z & \text{associativity} \\ &=(x\cdot y) \cdot 1 + (x\cdot y)\cdot z+x'\cdot (y\cdot z)+x'\cdot z & \text{identity for } \cdot \\ &=(x\cdot y) \cdot (1 + z)+x'\cdot (y\cdot z)+x'\cdot z & \text{associativity} \\ &=(x\cdot y) \cdot (1 + z)+x'\cdot (y\cdot z)+x'\cdot z & \text{distributivity} \\ &=(x\cdot y) \cdot 1+x'\cdot (y\cdot z)+x'\cdot z & \text{annihilator for } + \\ &=x\cdot y+x'\cdot (y\cdot z)+x'\cdot z & \text{identity for } \cdot \\ &=x\cdot y+(x'\cdot z) \cdot y+x'\cdot z & \text{assoc. and comm. of } \cdot \\ &=x\cdot y+(x'\cdot z) \cdot y+(x'\cdot z) \cdot 1 & \text{identity for } \cdot \\ &=x\cdot y+(x'\cdot z) \cdot (y+1) & \text{distributivity} \\ &=x\cdot y+x'\cdot z & \text{annihilator for } +, \\ \end{align*} $

as desired.

Answer 2

The last one is arguably the simplest of them. $$\begin{align}x'\cdot z'+x'\cdot y+x'\cdot z+x\cdot y &= x'\cdot z'+x'\cdot z+x'\cdot y+x\cdot y\\ &= x'\cdot(z'+z)+(x'+x)\cdot y\\ &= x'\cdot 1+1\cdot y\\ &= x'+y,\end{align}$$ so by DeMorgan's laws, $$(x'\cdot z'+x'\cdot y+x'\cdot z+x\cdot y)'=(x'+y)'=(x')'\cdot y'=x\cdot y'.$$

For the first one, since $a+1=1$ for all $a,$ then we can proceed by $$\begin{align}x\cdot y\cdot z+x'\cdot z &= x\cdot y\cdot z+x'\cdot (y+1)\cdot z\\ &= x\cdot y\cdot z+x'\cdot y\cdot z+x'\cdot 1\cdot z\\ &= (x+x')\cdot y\cdot z+x'\cdot z\\ &= 1\cdot y\cdot z+x'\cdot z\\ &= y\cdot z+x'\cdot z.\end{align}$$

I see that Rebecca has already worked through the second one. I will concur heartily with her that there isn't just one magic method. Some problems are amenable to a few slick tricks. Some may require a great deal more manipulation, and several of the rules are used. Keep at it, and get a lot of practice, to see how and when certain methods help us.

Answer 3

I don’t know what theorems you’ve already proved, but I expect that the laws available to you are the ones shown here using slightly different notation ($\land$ for $\cdot$, $\lor$ for $+$, and $\neg$ for $'$).

For the first problem, note that for any $u$ and $x$ we have $u=x\cdot u+x'\cdot u$; here’s a proof using just the basic laws.

$$\begin{align*} u&=u\cdot 1&&\text{identity}\\ &=u\cdot(x+x')&&\text{complements}\\ &=u\cdot x+u\cdot x'&&\text{distributivity}\\ &=x\cdot u+x'\cdot u&&\text{commutativity} \end{align*}$$

Now let $u=y\cdot z$: you get

$$y\cdot z=x\cdot(y\cdot z)+x'\cdot(y\cdot z)\;,$$

and since the operations are associative we can drop the parentheses and write simply $$y\cdot z=x\cdot y\cdot z+x'\cdot y\cdot z\;.$$

Substitute this into the righthand side of the equation that you’re trying to prove:

$$y\cdot z+x'\cdot z=x\cdot y\cdot z+x'\cdot y\cdot z+x'\cdot z\;.\tag{1}$$

Now notice that the last two terms have a common factor of $x'\cdot z$:

$$\begin{align*} x'\cdot y\cdot z+x'\cdot z&=y\cdot(x'\cdot z)+1\cdot(x'\cdot z)\\ &=(y+1)\cdot(x'\cdot z)\\ &=1\cdot(x'\cdot z)\\ &=x'\cdot z\;, \end{align*}$$

where I’ll leave it to you to justify the steps.

Thus, the righthand side of $(1)$ reduces to $x\cdot y\cdot z+x'\cdot z$, which is exactly what you want.

You’re probably wondering at this point how I found that calculation. Part of it was experience; here’s a slightly different approach that may make the idea a bit clearer.

You might notice that every term of the original equation has a factor of $z$; if we could show that $$x\cdot y+x'=y+x'\;,$$ we could multiply through by $z$ to get the desired result.

At this point it can be helpful to think of $x,y$, and $z$ as statements that can be true or false and interpret $\cdot$, $+$, and $'$ as and, or, and not, respectively. Then $x\cdot y+x'$ is true when $x$ and $y$ are both true or $x$ is false, and $y+x'$ is true when $y$ is true or $x$ is false. These are pretty clearly the same: they’re both true when $x$ is false, and otherwise they’re both true if and only if $y$ is true. The $x$ in $x\cdot y$ isn’t really imposing an extra restriction, since the $x'$ term already covers all situations in which $x$ is false. In other words, we should split ‘$y$ is true’ into two cases: ‘$y$ is true and so is $x$’, and ‘$y$ is true but $x$ is false’. In Boolean algebraic terms that’s just saying that $y=x\cdot y+x\cdot y$, which follows from the calculation $y=1\cdot y=(x+x')\cdot y=x\cdot y+x'\cdot y$. Thus, $y+x'=x\cdot y+x'\cdot y+x'$, and you can then use one of the absorption laws to say that $x'\cdot y+x'=x'$ and hence that $y+x'=x\cdot y+x'$.

In my first argument I did essentially the same thing, splitting $y\cdot z$ into $x\cdot y\cdot z+x'\cdot y\cdot z$, because I recognized that the second term would absorb into the $x'\cdot z$ that was already there.

---

In the second problem you should notice that the two sides differ only in that the lefthand side has an extra $y\cdot z$; clearly you should try to show that it can be absorbed into the other two terms. It makes sense that this should be possible: if $y$ and $z$ are both true, then either $x$ is true, and therefore $x$ and $y$ are true, or $x$ is false, and therefore $x$ is false and $z$ is true. The first case is covered by $x\cdot y$, and the second by $x'\cdot z$. Thus, you should write $y\cdot z$ as $(x+x')\cdot(y\cdot z)$, multiply out to get $x\cdot y\cdot z+x'\cdot y\cdot z$, and absorb those terms into the existing $x\cdot y$ and $x'\cdot z$. The whole thing is very similar to the first problem; there’s just a bit more of it.

---

For the third one you’ll probably want to have proved the De Morgan laws, $(x\cdot y)'=x'+y'$ and $(x+y)'=x'\cdot y'$. Note too that inside the parentheses you can combine three terms: $$x'\cdot z'+x'\cdot y+x'\cdot z=x'\cdot(z'+y+z)\;,$$ and $z'+y+z$ simplifies enormously.