Boolean expression simplification
Good Night, guys!
I'm doing a job that I have to simplify a Boolean algebraic expression of a circuit:
And the simplest expression I found was this:
But I think it might be simpler, would anyone have a better solution than this?
2 answers
This answer is a solution by reducing Boolean expressions. I also posted another answer based on Table analysis-truth .
The first nor port in the figure produces this:
(1) j = NOT (a OR b OR c)
The not port below this NOR:
(2) k = NOT b
A port XOR:
(3) m = d XOR k
The port not above the XOR:
(4) n = NOT d
The penultimate NAND port:
(5) p = NOT (j AND n)
The final port:
(6) f = NOT (p AND m)
Substituting (5) for (6):
(7) f = NOT (NOT (j AND n) AND m)
Replacing (4) with (7):
(8) f = NOT (NOT (j AND NOT d) AND m)
Replacing (3) with (8):
(9) f = NOT (NOT (j AND NOT d) AND (d XOR k))
Replacing (2) with (9):
(10) f = NOT (NOT (j AND NOT d) AND (d XOR NOT b))
Replacing (1) with (10):
(10) f = NOT (NOT (NOT (a OR b OR c) AND NOT d) AND (d XOR NOT b))
This is the equivalent expression. Now, let's simplify it. Applying Morgan's law in the innermost parentheses of (10):
z = NOT (a OR b OR c)
f = NOT (NOT (z AND NOT d) AND (d XOR NOT b))
z = NOT a AND NOT b AND NOT c
(11) f = NOT (NOT ((NOT a AND NOT b AND NOT c) AND NOT d) AND (d XOR NOT b))
Applying Morgan's law again in (11):
z = NOT ((NOT a AND NOT b AND NOT c) AND NOT d)
x = (NOT a AND NOT b AND NOT c)
y = NOT d
z = NOT (x AND y)
z = NOT x OR NOT y
z = NOT (NOT a AND NOT b AND NOT c) OR d
(12) f = NOT ((NOT (NOT a AND NOT b AND NOT c) OR d) AND (d XOR NOT b))
Again:
z = NOT (NOT a AND NOT b AND NOT c)
z = a OR b OR c
(13) f = NOT (((a OR b OR c) OR d) AND (d XOR NOT b))
Of new:
x = ((a OR b OR c) OR d)
y = (d XOR NOT b)
f = NOT (x AND y)
f = NOT x OR NOT y
(14) f = NOT ((a OR b OR c) OR d) OR NOT (d XOR NOT b)
Simplifying parentheses:
(15) f = NOT (a OR b OR c OR d) OR NOT (d XOR NOT b)
Applying Morgan again:
z = NOT (a OR b OR c OR d)
z = NOT a AND NOT b AND NOT c AND NOT d
(16) f = (NOT a AND NOT b AND NOT c AND NOT d) OR NOT (d XOR NOT b)
Whereas (x XOR NOT y) is the equivalent of (x <-> y), then:
(17) f = (NOT a AND NOT b AND NOT c AND NOT d) OR NOT (d <-> b)
Whereas NOT (x <-> y) is the equivalent of (x XOR y), then:
(18) f = (NOT a AND NOT b AND NOT c AND NOT d) OR (d XOR b)
Whereas (x XOR y) is equivalent to (x AND NOT y) OR (NOT x AND y):
(19) f = (NOT a AND NOT b AND NOT c AND NOT d) OR (d AND NOT b) OR (NOT d AND b)
Now, we have two possibilities, group the NOT d AND alguma-coisa. Or group the NOT b AND alguma-coisa. Let's start with NOT d:
(20a) f = (NOT d AND ((NOT a AND NOT b AND NOT c) OR b)) OR (d AND NOT b)
Distributing the OR b:
(21a) f = (NOT d AND (NOT a OR b) AND (NOT b OR b) AND (NOT c OR b)) OR (d AND NOT b)
Now, NOT b OR b it's true! So:
(22a) f = (NOT d AND (NOT a OR b) AND TRUE AND (NOT c OR b)) OR (d AND NOT b)
And we have to (x AND TRUE) = x. Logo:
(23a) f = (NOT d AND (NOT a OR b) AND (NOT c OR b)) OR (d AND NOT b)
Putting the b in evidence again:
(24a) f = (NOT d AND ((NOT a AND NOT c) OR b)) OR (d AND NOT b)
Distributing the NOT d AND:
(25a) f = (NOT d AND NOT a AND NOT c) OR (NOT d AND b) OR (d AND NOT b)
Whereas (NOT d AND b) OR (d AND NOT b) is the same as (d XOR b):
(26a) f = (NOT a AND NOT c AND NOT d) OR (d XOR b)
If we had grouped with NOT b instead of NOT d:
(20b) f = (NOT b AND ((NOT a AND NOT c AND NOT d) OR d)) OR (NOT d AND b)
Distributing the OR d:
(21b) f = (NOT b AND (NOT a OR d) AND (NOT c OR d) AND (NOT d OR d)) OR (NOT d AND b)
Now, NOT d OR d it's true! So:
(22b) f = (NOT b AND (NOT a OR d) AND (NOT c OR d) AND TRUE) OR (NOT d AND b)
And we have to (x AND TRUE) = x. Logo:
(23b) f = (NOT b AND (NOT a OR d) AND (NOT c OR d)) OR (NOT d AND b)
Putting the b in evidence again:
(24b) f = (NOT b AND ((NOT a AND NOT c) OR d)) OR (NOT d AND b)
Distributing the NOT b AND:
(25b) f = (NOT b AND NOT a AND NOT c) OR (NOT b AND d) OR (NOT d AND b)
Whereas (NOT b AND d) OR (NOT d AND b) is the same as (d XOR b):
(26b) f = (NOT a AND NOT b AND NOT c) OR (d XOR b)
We have as results:
-
f = (NOT a AND NOT c AND NOT d) OR (d XOR b). -
f = (NOT a AND NOT b AND NOT c) OR (d XOR b).
These are the possible solutions.
This answer is a solution by means of table-truth analysis. I also posted another response based on boolean expression reduction .
Let's see how the table looks-truth:
A B C D F
0 0 0 0 1
0 0 0 1 1
0 0 1 0 0
0 0 1 1 1
0 1 0 0 1
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 0
1 0 0 1 1
1 0 1 0 0
1 0 1 1 1
1 1 0 0 1
1 1 0 1 0
1 1 1 0 1
1 1 1 1 0
Let's rearrange the columns, placing in order CABD and swapping the rows accordingly to stay in order where the numbers of the four columns on the left grow in binary order from 0000 to 1111:
C A B D F
0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 0
0 1 0 0 0
0 1 0 1 1
0 1 1 0 1
0 1 1 1 0
1 0 0 0 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 0
1 1 0 0 0
1 1 0 1 1
1 1 1 0 1
1 1 1 1 0
Note that the values of F of the first half of the table are almost identical to the second, except for the first row of each (0000 and 1000). Let's see what's special about these lines (and for that part, the C doesn't matter):
A B D F
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 0
Note that the cases where the output is one are the cases B XOR D.
Returning to the first row of each half of the table:
C A B D F
0 0 0 0 1
1 0 0 0 0
This then equals (NOT A AND NOT B AND NOT C AND NOT D).
Joining the two subexpressions we have:
(NOT A AND NOT B AND NOT C AND NOT D) OR (B XOR D)
However, if we look at the table, you can simplify (NOT A AND NOT B AND NOT C AND NOT D) by cutting one (but not both) subexpressions NOT B or NOT D. Thus, we arrive at two possible solutions:
(NOT A AND NOT B AND NOT C) OR (B XOR D)(NOT A AND NOT C AND NOT D) OR (B XOR D)