How to reduce a logical statement?

Question

I'm pretty sure I can remember doing something like this in one of my college level courses and that there was some kind of formula to it, but my mind is failing me beyond that.

Given the statement: ( a OR b OR d ) AND ( a OR c )

I'm pretty sure that this can be reduced to: ( a OR b OR d OR c )

But I cannot remember how I would go about proving it.

Maybe it was a series of logic tables?

Answer 1

You cannot reduce "( a OR b OR d ) AND ( a OR c )" to "( a OR b OR d OR c )" because the former is not satisfied with "c=true, a,b,d=false", whereas the latter is. So you can't prove the reduction correct either :)

In general, there are many ways to reduce Boolean formulae in size, and it is also a question of what you want to optimize (total size? average number of condition evaluations?). Karnaugh maps work only for a small number of variables. Reducing big Boolean formulaes into smaller ones is an advanced topic that is key in e.g. automatic logical circuit design.