3
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.
The formula is correct. Your intention is to have fewer port levels
and
/dooror
?– Jefferson Quesado
This issue deals with one of the tools used to decrease the depth to the minimum possible of n-ary gates, the Karnaugh map: https://answall.com/q/228005/64969
– Jefferson Quesado
I’m sorry I switched NOR with NAND. I already got both answers.
– Victor Stafusa