# How can I simplify the following Product of Sums: ab+ac'+a'b'+a'c+b'c'+bc?

I started with POS: (a+b+c)(a+b'+c)(a'+b+c)(a'+b+c')

and after a long while, I got: ab+ac'+a'b'+a'c+b'c'+bc

and then I'm not sure how to simplify this. I thought maybe I can cancel the ab with a'b', and b'c' with bc and end with ac'+a'c but it doesn't seem to be right if I look at the truth table...

Update It turns out that your initial simplification was incorrect. Here's a correct one. First, observe that $$(p+q)(p+q') = pp+pq'+pq+qq'=p +p(q'+q)+0 = p+p1=p$$ so for the first two terms in your POS we have $$((a+c)+b)((a+c)+b') = a+c$$ and, similarly, for the last two terms we have $$((a'+b)+c)((a'+b)+c') = a'+b$$ so the full product simplifies to $$(a+c)(a'+b)\quad\text{ or, if you prefer }\quad ab+a'c+bc$$ At this stage you haven't simplified this as much as possible. If you construct truth tables, you'll discover that $ab+a'c+bc=ab+a'c$, in other words the $bc$ term isn't needed here. It isn't obvious how one would discover that unless you've seen Karnaugh maps, for instance.

This is a valid simplification of your problem:

(b+c)(a+c)(a'+b)


I used Microsoft Z3 - http://rise4fun.com/Z3 with the following code:

(declare-const a Bool)
(declare-const b Bool)
(declare-const c Bool)
(assert (and (or a b c) (or a (not b) c)(or (not a) b c)(or (not a) b (not c))))
(apply ctx-solver-simplify)


I'm sure you could prove this equality using Natural Deduction or some other rules if you like.

(a'c)+(ab) is the shortest equivalent of that expression at the top of the answer.