Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

Please help. Thank you!

share|improve this question
    
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

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.