1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Wow, thanks a million Rebecca & Cameron! Even looking at these proofs, my head starts to spin... I think it may take a while for me to get the hang of this. Either way, you guys are life saves - cheers! $\endgroup$ – echo Sep 29 '13 at 23:16
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ (+1) I wasn't looking forward to working through that one. Imagine my relief when I got the alert that you'd already done it while I was working on the other two! $\endgroup$ – Cameron Buie Sep 29 '13 at 22:41
  • $\begingroup$ Greatly appreciate this! Seems to be the more difficult of the 3.. $\endgroup$ – echo Sep 29 '13 at 23:17
  • $\begingroup$ Hey Rebecca, would it at all be possible for you to break down the first and third problems the same way you've done this one? This is exactly how I'm being taught to do proofs; and while Cameron and Brian's solutions are detailed, they've got me a bit confused. I can't seem to follow what theorems and laws are being used. If it's not too much trouble, I would greatly appreciate it! $\endgroup$ – echo Sep 30 '13 at 1:31
  • $\begingroup$ Well, that sounds a bit much. I'd be just copy/pasting Cameron's answer and filling in the "by commutativity", and so on. $\endgroup$ – Rebecca J. Stones Sep 30 '13 at 1:51
  • $\begingroup$ Alright, thanks anyways! I'll just do my best to figure out what's being used for each step. $\endgroup$ – echo Sep 30 '13 at 1:59
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! I think I'll start trying to understand these two before the second... they seem a bit more.. bit-sized if you will. $\endgroup$ – echo Sep 29 '13 at 23:18

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.