How to reduce a logical statement?
Asked Answered
T

9

7

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?

Thou answered 20/3, 2009 at 15:35 Comment(0)
C
10

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.

Celinacelinda answered 20/3, 2009 at 15:46 Comment(1)
so are their programs available to do this?Thou
G
8

Karnaugh maps? Logic expression reduction?

Gerstner answered 20/3, 2009 at 15:38 Comment(0)
A
4

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.

Afroasian answered 20/3, 2009 at 15:39 Comment(0)
A
3

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.

Azote answered 20/3, 2009 at 15:39 Comment(0)
S
2

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

Skeptic answered 20/3, 2009 at 15:53 Comment(0)
S
1

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

Sixtieth answered 20/3, 2009 at 17:45 Comment(0)
N
1

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?

Nonalignment answered 20/3, 2009 at 18:17 Comment(0)
E
1

SOP minimal form:

y = a | b&c | c&d;

POS have the same cost (number of gates to implement logic diagram):

y = (a|c)&(a|b|d);
Erasmoerasmus answered 7/5, 2012 at 12:58 Comment(0)
I
0

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 (???)) :(

Incommodious answered 20/3, 2009 at 17:4 Comment(0)

© 2022 - 2024 — McMap. All rights reserved.