De Morgan; negative OR equals positive AND

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.

Algebraic proof (Theorem 1): let $X = A + B$, $Y = \bar A \bar B$. Then $X + Y = A + B + \bar A\bar B = A + B + \bar B = 1$ and $XY = A\bar A\bar B + B\bar A\bar B = 0$, so $Y = \bar X$. Theorem 2 follows by duality.

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)

Negative-logic OR = positive-logic AND

Take a gate whose output is HIGH only when both inputs are HIGH:

Positive logic (H = 1): Y = 1 only for A = B = 1 → AND.

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

Y = 0 only when both inputs are 0 → OR.

Algebraically: a negative-logic OR, seen in positive logic, has all inputs and the output complemented:

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

So the negative-logic OR gate is the same circuit as the positive-logic AND gate.