De Morgan; positive NAND equals negative NOR

De Morgan's theorems

First theorem: the complement of a sum (OR) of variables equals the product (AND) of their complements.

$$\overline{A + B} = \bar{A} \cdot \bar{B}$$

Second theorem: the complement of a product (AND) of variables equals the sum (OR) of their complements.

$$\overline{A \cdot B} = \bar{A} + \bar{B}$$

In words: "break the bar and change the sign".

Proof by truth table

For all four input combinations, column 3 equals column 4 and column 5 equals column 6, so both theorems are proved.

Diagrams

 Theorem 1: NOR = bubbled AND
 A --|‾‾‾\             A --o|‾‾‾\
     | OR  )o-- Y   =       | AND )-- Y
 B --|___/             B --o|___/

 Theorem 2: NAND = bubbled OR
 A --|‾‾‾\             A --o|‾‾‾\
     | AND )o-- Y   =       | OR  )-- Y
 B --|___/             B --o|___/

 (o = inversion bubble)

Positive NAND = negative NOR

Consider a gate whose voltage table is:

Positive logic (H = 1, L = 0):

Output is 0 only when both inputs are 1: a NAND gate.

Negative logic (H = 0, L = 1), same circuit:

Output is 1 only when both inputs are 0: a NOR gate.

Algebraically: going to negative logic complements all inputs and the output:

$$\begin{aligned} Y_{neg} &= \overline{\,\overline{\bar A \cdot \bar B}\,} \\ &= \bar A \cdot \bar B \\ &= \overline{A + B} \quad (\text{De Morgan}) \end{aligned}$$

Hence positive-logic NAND is equivalent to negative-logic NOR.