# Help with simplifying boolean functions algebraically

I have 2 boolean functions that I am having some difficulty solving algebraically.

NOTE: ~ means NOT, & means AND, + means OR

1) $(\sim b~\&~\sim d)+(b~\&~\sim c~\&~d)+(b~\&~c~\&~d)+(a~\&~\sim b~\&~d)$ Here is what I got:

\begin{align*} &=(b~\&~d)~\&~(\sim c+c)+(\sim b~\&~\sim d)+(a~\&~\sim b~\&~d)\\ &=(b~\&~d)+(\sim b~\&~\sim d)+(a~\&~\sim b~\&~d)\\ &=(a~\&~\sim b~\&~d) \end{align*}

How can this be? Doesn't the variable $c$ have to exist as well in the simplification for the function to be logically equivalent?

I have a similar issue with the next question:

2) $(a+b)~\&~(a+\sim b)$

Using the boolean distributive identity of $A + B \cdot C = (A + B) \cdot (A + C)$

\begin{align*} &=a+(b~\&~\sim b)\\ &=a \end{align*}

Once again, don't I need $b$ or $\sim b$ in the simplification?

-
Your simplification for 1) is incorrect. If $b=0,d=0$, then the lhs is $1$ but the rhs is $0$. It should be (~ b & ~d)+(b & d) + (a & d). – copper.hat Jan 23 '13 at 3:00
Where does the ~b go in the expression (a & ∼b & d)? I now see that (b & d)+(∼b & ∼d) does not simplify to 0. – JT9 Jan 23 '13 at 3:25
$(B \land D) \lor (A \land \lnot B \land D) = (B \land D) \lor (A \land B \land D) \lor (A \land \lnot B \land D) =(B \land D) \lor (A \land D)$. – copper.hat Jan 23 '13 at 4:24
Here is a simple way to see a variable disappearing: $B \lor \lnot B = \top$. – copper.hat Jan 23 '13 at 4:27

It’s quite possible for a variable to disappear in a simplification. Just as in ordinary algebra you can have $ab-(a-1)(b-1)-b+1=ab-(ab-a-b+1)-b+1=a$, so in Boolean algebra you can have $(a+b)~\&~(a+\sim b)=a+(b~\&~\sim b)=a$.

However, your first calculation isn’t entirely correct: $(b~\&~d)+(\sim b~\&~\sim d)+(a~\&~\sim b~\&~d)$ is not equivalent to $(a~\&~\sim b~\&~d)$. The first expression is true when $b$ and $d$ are both true; the second is not.

Added: Here’s the truth table for $(a+b)~\&~(a+\sim b)$; I’ve used $1$ and $0$ for true and false, respectively.

$$\begin{array}{c|c|c|c|c} a&b&a+b&a+\sim b&(a+b)~\&~(a+\sim b)\\ \hline 0&0&0&1&0\\ 0&1&1&0&0\\ 1&0&1&1&1\\ 1&1&1&1&1 \end{array}$$

As you can see, the column for $(a+b)~\&~(a+\sim b)$ is identical to the column for $a$, so the two expressions must be equivalent.

-
I see that now. Thank you! I see algebraically how we reach only a in the second problem. However, going to the truth table, how are they the same? Or does it not matter in that regard since we simplified it using algebra techniques? – JT9 Jan 23 '13 at 3:28
@JTWheeler: Let me add the truth table to my answer and explain how it shows that they are the same. – Brian M. Scott Jan 23 '13 at 3:35
That makes perfect sense now! I guess I was confused about the number of variables. I thought because it was a single term, the truth table would only contain a single 0 and a single 1 while the table with both a and b has 4 entries for each variable. I was just over-thinking the problem! – JT9 Jan 23 '13 at 3:47
@JTWheeler: It happens; I’m glad to get it straightened out for you. – Brian M. Scott Jan 23 '13 at 3:56