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

Karnaugh maps? Logic expression reduction?

Answer 2

Karnaugh maps, the key is to "draw" all possible inputs and indicate their outputs. Then you can start to filter out the inputs that do not make a difference to the output thus reducing the map. Once it is optimised you can then produce your logic from it.

Answer 3

A Karnaugh map is your friend here:

http://en.wikipedia.org/wiki/Karnaugh_map

You'll kind of have to build it in reverse from the above equations, but it's a good tool to tell you if it can be reduced further.

Answer 4

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.

Answer 5

( a OR b OR d ) AND ( a OR c )

This mean when a is true, everything is true!

=> a OR { (b OR d) AND ( c) }

=> a OR ( b AND C) OR ( d and C )

i think the result ( a OR b OR d OR c ) is wrong, but give me a hand when its wrong.

Answer 6

Yes, you can prove it. You can't reduce it to ( a OR b OR d OR c )

Look at the 3rd line below. Your reduction would fail to generate the proper answer.

Just run it through:

A B C D
0 0 0 0 = 0
0 0 0 1 = 0
0 0 1 0 = 0
.
.
.
1 0 0 0 = 1
1 0 0 1 = 1

So far I've got (A OR (???)) :(

Answer 7

a or {(b OR d) AND c}

Reasoning: If "a", then the statement is true. else, you need b or d (to satisfy the first portion of the statement) and c (satisfies the second half for cases when !a

Answer 8

Using Karnaugh maps:

This is a OR b OR d:

 \ab
cd\ 00 01 11 10
---+-----------+
00 |  | X| X| X|
01 | X| X| X| X|
11 | X| X| X| X|
10 |  | X| X| X|
   +-----------+

This is a OR c:

 \ab
cd\ 00 01 11 10
---+-----------+
00 |  |  | X| X|
01 |  |  | X| X|
11 | X| X| X| X|
10 | X| X| X| X|
   +-----------+

Intersecting them, we get:

 \ab
cd\ 00 01 11 10
---+-----------+
00 |  |  | X| X|
01 |  |  | X| X|
11 | X| X| X| X|
10 |  | X| X| X|
   +-----------+

Obviously, this is a OR (something), where the (something) is:

    00 01
11 | X| X|
10 |  | X|

Since the (something) isn't a rectangle, it requires two expressions, which could be either AND'ed or OR'ed together, depending on how we want to approach it. We'll use OR in this example, since it gives a simpler expression.

In this case, we can group the two X's next to each other with two more to fill the entire cd line, so cd can be one of the expressions. We can also group the two on top of each other with the two to their right to form a square. This square represents the expression bc, since both a and d vary within the square.

So the final expression is a OR ((c AND d) OR (b AND d)), or a + cd + bd. Much nicer, isn't it?