Simplify Boolean Expression Given Truth Table

Question

I have the truth table above which gives the minterm expression

$$F = (\neg a \land \neg b \land c) \lor (\neg a \land b \land \neg c) \lor (a \land \neg b \land \neg c) \lor (a \land b \land c)$$

but I'm unsure how to simplify it using boolean algebra to prove it is the XOR of a, b, and c.

Yes, I know that's the final solution, but I'm not sure how to get there in steps. — smd, Jan 20 '16 at 23:45
You can notice that there are an odd number of ones in each column where the expression evaluates as one. — Element118, Jan 20 '16 at 23:46
Yes, I know, but I have to prove it using boolean algebra not just by the definition of XOR — smd, Jan 20 '16 at 23:51

score 0 · Accepted Answer · answered Jan 21 '16 at 01:20

We know that $x \veebar y = (\neg x \land y) \lor (x \land \neg y)$.

Note that, by combining terms with $a$ and combining terms with $\neg a$:

$$\begin{align*} F &= (\neg a \land \neg b \land c) \lor (\neg a \land b \land \neg c) \lor (a \land \neg b \land \neg c) \lor (a \land b \land c) \\ &= (\neg a \land (\neg b \land c)) \lor (\neg a \land (b \land \neg c)) \lor (a \land (\neg b \land \neg c)) \lor (a \land (b \land c)) \\ &= (\neg a \land ((\neg b \land c) \lor (b \land \neg c))) \lor (a \land ((\neg b \land \neg c) \lor (b \land c))) \\ &= (\neg a \land (b\veebar c)) \lor (a \land \neg((\neg b \land c) \lor (b \land \neg c))) \\ &= (\neg a \land (b\veebar c)) \lor (a \land \neg(b\veebar c)) \\ &= a \veebar (b \veebar c) = a \veebar b \veebar c \end{align*}$$

Simplify Boolean Expression Given Truth Table

1 Answers1