Start here “It’s not true that (I’m
hungry or I’m tired)” means “I’m not
hungry and I’m not tired.” When you
push a NOT inside the brackets, OR turns into AND. That simple switch is
De Morgan’s Law, and it lets you rebuild any gate from other gates.
Enlarge diagram ↗ Open full size diagram ↗ A NOR gate does the same job as
an AND gate with both inputs flipped. A NAND gate does the same job as
an OR gate with both inputs flipped.
Law
Formula
In words
1 ( A + B ) ‾ = A ‾ ⋅ B ‾ \overline{\left(A + B\right)} = \overline{A} \cdot \overline{B} ( A + B ) = A ⋅ B NOT ( A OR B ) = ( NOT A ) AND ( NOT B ) \operatorname{NOT} \left(A \operatorname{OR} B\right) = \left(\operatorname{NOT} A\right) \operatorname{AND} \left(\operatorname{NOT} B\right) NOT ( A OR B ) = ( NOT A ) AND ( NOT B )
2 ( A ⋅ B ) ‾ = A ‾ + B ‾ \overline{\left(A \cdot B\right)} = \overline{A} + \overline{B} ( A ⋅ B ) = A + B NOT ( A AND B ) = ( NOT A ) OR ( NOT B ) \operatorname{NOT} \left(A \operatorname{AND} B\right) = \left(\operatorname{NOT} A\right) \operatorname{OR} \left(\operatorname{NOT} B\right) NOT ( A AND B ) = ( NOT A ) OR ( NOT B )
Recipe to “break the bar”: split the
bar over each variable, and flip the sign (+ ↔︎
·).
It works for any number of variables:
( A + B + C ) ‾ = A ‾ ⋅ B ‾ ⋅ C ‾ \overline{\left(A + B + C\right)} = \overline{A} \cdot \overline{B} \cdot \overline{C} ( A + B + C ) = A ⋅ B ⋅ C ( A ⋅ B ⋅ C ) ‾ = A ‾ + B ‾ + C ‾ \overline{\left(A \cdot B \cdot C\right)} = \overline{A} + \overline{B} + \overline{C} ( A ⋅ B ⋅ C ) = A + B + C
A
B
A + B A + B A + B ( A + B ) ‾ \overline{\left(A + B\right)} ( A + B ) A ‾ \overline{A} A B ‾ \overline{B} B A ‾ ⋅ B ‾ \overline{A} \cdot \overline{B} A ⋅ B
0
0
0
1 1
1
1
0
1
1
0 1
0
0
1
0
1
0 0
1
0
1
1
1
0 0
0
0
The two bold columns match in every row, so the law is true.
Gate
Same as
NOR = ( A + B ) ‾ \overline{\left(A + B\right)} ( A + B ) AND with both inputs inverted
NAND = ( A ⋅ B ) ‾ \overline{\left(A \cdot B\right)} ( A ⋅ B ) OR with both inputs inverted
This is useful when you don’t have every type of
gate . For example, a chip with only NAND gates can still build
ORs (more in Week 3).
F = A + B + C → F ‾ = ( A + B + C ) ‾ = F = A + B + C \to \overline{F} = \overline{\left(A + B + C\right)} = F = A + B + C → F = ( A + B + C ) = A ‾ ⋅ B ‾ ⋅ C ‾ \overline{A} \cdot \overline{B} \cdot \overline{C} A ⋅ B ⋅ C
F says: at least one of A, B, C is 1.
F ‾ \overline{F} F all of A, B, C are 0. These are exact opposites, as expected.
In one line: To push a NOT through brackets, flip
every variable and swap AND ↔︎ OR. So NOR = AND \operatorname{NOR} = \operatorname{AND} NOR = AND NAND = OR \operatorname{NAND} = \operatorname{OR} NAND = OR Exam words: De Morgan’s
law, complement, break the bar, NAND equivalence, NOR equivalence,
bubble pushing.
Apply De Morgan: ( X ⋅ Y ‾ ) ‾ = \overline{\left(X \cdot \overline{Y}\right)} = ( X ⋅ Y ) =
X ‾ + Y \overline{X} + Y X + Y Y ‾ \overline{Y} Y
A NOR gate is the same as an ___ gate with inverted inputs.
AND.
Simplify ( A ‾ + B ‾ ) ‾ \overline{\left(\overline{A} + \overline{B}\right)} ( A + B )
A ⋅ B A \cdot B A ⋅ B 