Simplification of Boolean expression

Question

Good night, you guys!

I’m doing a job that I have to simplify a boolean algebraic expression of a circuit:

And the simplest expression I could find was this:

But I think it might be simpler, someone would have a better solution than this?

Answer 1

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

The first NOR gate in the figure produces that:

(1) j = NOT (a OR b OR c)

The door NOT below that NOR:

(2) k = NOT b

The door XOR:

(3) m = d XOR k

The NOT gate above the XOR:

(4) n = NOT d

The penultimate door NAND:

(5) p = NOT (j AND n)

The final door:

(6) f = NOT (p AND m)

Replacing (5) in (6):

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

Replacing (4) in (7):

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

Replacing (3) in (8):

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

Replacing (2) in (9):

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

Replacing (1) in (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 inner 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 on (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 the parentheses:

(15) f = NOT (a OR b OR c OR d) OR NOT (d XOR NOT b)

Applying of 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, to group the NOT d AND alguma-coisa. Or group the NOT b AND alguma-coisa. Let’s start with the NOT d:

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

By 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 is 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. Soon:

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

By 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 the 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)

By 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 is 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. Soon:

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

By 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 a result:

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

Answer 2

This answer is a solution through truth-table analysis. I also posted another response based on boolean expression reduction.

Let’s see how the truth-table looks:

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, put them in order CABD and swapping lines of agreement to stay in the order where the numbers of the left four columns 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 those of the second, with the exception of each first row (0000 and 1000). Let’s see what’s special about these lines (and for this part, the C it 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 in 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 amounts to (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 again, we can simplify (NOT A AND NOT B AND NOT C AND NOT D) 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)