Boolean expression simplification

This answer is a solution by reducing Boolean expressions. I also posted another response based on truth table analysis .

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

The XOR port:

(3) m = d XOR k

The NOT port above 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) into (6):

(7) f = NOT (NOT (j AND n) AND m)

Substituting (4) into (7):

(8) f = NOT (NOT (j AND NOT d) AND m)

Substituting (3) into (8):

(9) f = NOT (NOT (j AND NOT d) AND (d XOR k))

Substituting (2) into (9):

(10) f = NOT (NOT (j AND NOT d) AND (d XOR NOT b))

Substituting (1) into (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))

Once 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))

Again:

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 from 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)

Considering that (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)

Considering that 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)

Considering that (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 NOT d AND alguma-coisa . Or group 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 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)

Well, NOT b OR b is true! Then:

(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 b into evidence again:

(24a) f = (NOT d AND ((NOT a AND NOT c) OR b)) OR (d AND NOT b)

Distributing NOT d AND :

(25a) f = (NOT d AND NOT a AND NOT c) OR (NOT d AND b) OR (d AND NOT b)

Considering that (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 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)

Well, NOT d OR d is true! Then:

(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 b into evidence again:

(24b) f = (NOT b AND ((NOT a AND NOT c) OR d)) OR (NOT d AND b)

Distributing NOT b AND :

(25b) f = (NOT b AND NOT a AND NOT c) OR (NOT b AND d) OR (NOT d AND b)

Considering that (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 the 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 through truth-table analysis. I also posted another response based on reduction of Boolean expressions .

Let's see what the truth table looks like:

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, putting them in order CABD and swap lines accordingly to be in the order where the numbers in 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 F values in the first half of the table are almost identical to the second, except for the first line of each (0000 and 1000). Let's see what's special about these lines (and for that part, C does not 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 a are B XOR D cases.

Returning to the first line of each half of the table:

C A B D F
0 0 0 0 1
1 0 0 0 0

This is equivalent to (NOT A AND NOT B AND NOT C AND NOT D) .

Adding the two subexpressions we have:

(NOT A AND NOT B AND NOT C AND NOT D) OR (B XOR D)

However, if you look at the table again, 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 come up with 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)