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...


2 Answers 2


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:


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.


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.