Digital Logic

De Morgan's theorems

De Morgan's theorems tell how to complement a sum or a product of variables.

Theorem 1: The complement of a sum equals the product of the complements.

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

So a NOR gate equals a bubbled AND gate (AND with inverted inputs).

Theorem 2: The complement of a product equals the sum of the complements.

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

So a NAND gate equals a bubbled OR gate (OR with inverted inputs).

Proof by truth table

Column 4 = column 5 and column 7 = column 8 for every input, so both theorems are proved.

Algebraic proof of Theorem 1: if $X = A + B$ and $Y = \bar A \bar B$, then $X + Y = A + B + \bar A \bar B = A + B + \bar B = 1$ and $X \cdot Y = A \bar A \bar B + B \bar A \bar B = 0$. Since $X + Y = 1$ and $XY = 0$, Y is the complement of 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)

XOR using minimum NAND gates

$Y = A \oplus B = A\bar B + \bar A B$. It can be built with 4 two-input NAND gates:

$$\begin{aligned} G_1 &= \overline{AB} \\ G_2 &= \overline{A \cdot G_1} = \overline{A \cdot \overline{AB}} \\ G_3 &= \overline{B \cdot G_1} = \overline{B \cdot \overline{AB}} \\ Y &= \overline{G_2 \cdot G_3} = A\,\overline{AB} + B\,\overline{AB} \\ &= A(\bar A + \bar B) + B(\bar A + \bar B) \\ &= A\bar B + \bar A B = A \oplus B \end{aligned}$$

 A --+-------------[NAND G2]--+
     |              |         |
     +--[NAND G1]---+         +--[NAND G4]-- Y
     |              |         |
 B --+-------------[NAND G3]--+

G1 output feeds one input of both G2 and G3; A goes to G2, B goes to G3; G2 and G3 feed G4.

Positive and negative logic

• Positive logic: the higher voltage level represents logic 1 and the lower level represents logic 0. Example in TTL: +5 V = 1, 0 V = 0.
• Negative logic: the higher voltage level represents logic 0 and the lower level represents logic 1. Example: +5 V = 0, 0 V = 1 (or in a –5 V system, –5 V = 1, 0 V = 0).

The same physical circuit gives a different logic function depending on which convention is used. Changing from positive to negative logic means complementing every input and output bit.

Proof: positive XOR = negative XNOR

Take a gate working as XOR in positive logic. Its voltage table (H = high, L = low):

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

This is XOR: $Y = A \oplus B$.

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

Output is 1 when both inputs are equal, which is XNOR: $Y = \overline{A \oplus B}$.

Algebraic proof: in negative logic the function becomes the complement of positive XOR with complemented inputs:

$$\begin{aligned} Y_{neg} &= \overline{\bar A \oplus \bar B} \\ &= \overline{\bar A B + A \bar B} \\ &= \overline{A \oplus B} = A \odot B \end{aligned}$$

(since $\bar A \oplus \bar B = A \oplus B$). Hence the positive-logic XOR gate is the same circuit as a negative-logic XNOR gate.

An XOR gate gives $Y = A \oplus B = A\bar B + \bar A B$. With NAND gates only, the minimum is four 2-input NAND gates.

Derivation

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

So the gates are:

• $G_1 = \overline{AB}$
• $G_2 = \overline{A \cdot G_1}$
• $G_3 = \overline{B \cdot G_1}$
• $Y = \overline{G_2 \cdot G_3}$

Circuit

 A --+-----------------|‾‾\
     |                 |G2 |o--+
     |  |‾‾\      +----|__/    |   |‾‾\
     +--|G1 |o----+            +---|G4 |o-- Y
     +--|__/      +----|‾‾\    +---|__/
     |                 |G3 |o--+
 B --+-----------------|__/

Verification

Output Y is 1 only when the inputs differ, which is the XOR function. Total: 4 NAND gates.

In a digital circuit the two logic states are shown by two voltage levels. Which level is called 1 decides whether the system uses positive or negative logic.

• Positive logic: HIGH voltage = logic 1, LOW voltage = logic 0. Example: in TTL, +5 V = 1 and 0 V = 0. Most systems use positive logic.
• Negative logic: HIGH voltage = logic 0, LOW voltage = logic 1. Example: +5 V = 0 and 0 V = 1; or in an ECL / –5 V system, –5 V = 1 and 0 V = 0.

  Positive logic       Negative logic
  +5V ---- 1           +5V ---- 0
   0V ---- 0            0V ---- 1

Example: a circuit has this voltage table:

• In positive logic (H = 1): Y = 1 only when A = B = 1, so it is an AND gate.
• In negative logic (H = 0): Y = 0 only when A = B = 0, so it is an OR gate.

So positive AND = negative OR, and similarly positive OR = negative AND, positive NAND = negative NOR, positive XOR = negative XNOR. The physical gate is the same; only the meaning of the levels changes.

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$ and $Y = \bar A \bar B$. Then $X + Y = A + B + \bar A \bar B = A + B + \bar B = 1$ and $X Y = A\bar A \bar B + B \bar A \bar B = 0$. A variable that ORs with X to give 1 and ANDs with X to give 0 is $\bar X$, so $\overline{A+B} = \bar A \bar B$. Theorem 2 follows by duality.

Importance of De Morgan's laws

De Morgan's laws, $\overline{A+B} = \bar A \bar B$ and $\overline{AB} = \bar A + \bar B$, are important because:

1. They let us complement any Boolean expression (break the bar, change AND ↔ OR).
2. They convert SOP forms to NAND-NAND and POS forms to NOR-NOR circuits, so any circuit can be built with one type of universal gate, which reduces IC types and cost.
3. They show gate equivalences: NAND = bubbled OR, NOR = bubbled AND; useful for reading and drawing circuits with active-low signals.
4. They help in simplifying expressions and in proving positive/negative logic equivalences.

XOR from 2-input NAND gates

$Y = A \oplus B = A\bar B + \bar A B$ needs four 2-input NAND gates.

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

Gates: $G_1 = \overline{AB}$, $G_2 = \overline{A G_1}$, $G_3 = \overline{B G_1}$, $Y = \overline{G_2 G_3}$.

 A --+---------------[NAND G2]--+
     |                 |        |
     +--[NAND G1]--G1--+        +--[NAND G4]-- Y
     |                 |        |
 B --+---------------[NAND G3]--+

Positive and negative logic

• Positive logic: HIGH voltage = logic 1, LOW voltage = logic 0 (e.g. TTL: +5 V = 1, 0 V = 0).
• Negative logic: HIGH voltage = logic 0, LOW voltage = logic 1 (e.g. +5 V = 0, 0 V = 1).

The same physical gate performs a different logic function in the two systems, because changing the convention complements every input and output. Example: a gate whose output is HIGH only when both inputs are HIGH is an AND gate in positive logic but an OR gate in negative logic.

XNOR using NAND gates only

$Y = A \odot B = \overline{A \oplus B}$. First build XOR with 4 NAND gates, then invert it with a fifth NAND gate whose two inputs are tied together ($\overline{X \cdot X} = \bar X$). Minimum: 5 NAND gates.

$$\begin{aligned} G_1 &= \overline{AB} \\ G_2 &= \overline{A G_1} \\ G_3 &= \overline{B G_1} \\ G_4 &= \overline{G_2 G_3} = A \oplus B \\ Y &= \overline{G_4 \cdot G_4} = \overline{A \oplus B} = AB + \bar A \bar B \end{aligned}$$

 A --+-----------[NAND G2]--+
     |              |       |
     +--[NAND G1]---+       +--[NAND G4]--+--[NAND G5]-- Y
     |              |       |             +--|
 B --+-----------[NAND G3]--+       (inputs tied: NOT)

Y is 1 when both inputs are equal, which is XNOR.

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.

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.

(−47) + (27) using 2's complement

Use 8-bit signed numbers (range −128 to +127).

Step 1: +47 and +27 in binary

• $47 = 32 + 8 + 4 + 2 + 1 = 0010\ 1111$
• $27 = 16 + 8 + 2 + 1 = 0001\ 1011$

Step 2: 2's complement of 47 (to get −47)

 +47            = 0010 1111
 1's complement = 1101 0000
 add 1          = 1101 0001  (= -47)

Step 3: Add

   -47  =  1101 0001
 + +27  =  0001 1011
 -------------------
           1110 1100

No carry out of the MSB, and the sign bit is 1, so the result is negative and is in 2's complement form.

Step 4: Find its magnitude (take 2's complement)

 result         = 1110 1100
 1's complement = 0001 0011
 add 1          = 0001 0100  = 20

Check: $-47 + 27 = -20$.

Answer: $(-47) + (27) = (1110\ 1100)_2$ in 2's complement $= -20_{10}$

De Morgan's laws

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

Examples

• $\overline{A + B + C} = \bar A \bar B \bar C$ and $\overline{ABC} = \bar A + \bar B + \bar C$ (extended to 3 variables).
• $\overline{(A + \bar B)C} = \overline{A + \bar B} + \bar C = \bar A B + \bar C$.
• Check with A = 1, B = 0: $\overline{1 + 0} = 0$ and $\bar 1 \cdot \bar 0 = 0 \cdot 1 = 0$.

XOR gate using only 3-input NAND gates

A 3-input NAND gives $\overline{XYZ}$. If one input is tied to logic 1 (HIGH, e.g. +5 V through a resistor), it behaves as a 2-input NAND: $\overline{X \cdot Y \cdot 1} = \overline{XY}$. (Tying the unused input to one of the used inputs also works, since $XX = X$.) So the 4-NAND XOR circuit is built with four 3-input NAND gates:

$$\begin{aligned} G_1 &= \overline{A \cdot B \cdot 1} = \overline{AB} \\ G_2 &= \overline{A \cdot G_1 \cdot 1} \\ G_3 &= \overline{B \cdot G_1 \cdot 1} \\ Y &= \overline{G_2 \cdot G_3 \cdot 1} = A\bar B + \bar A B = A \oplus B \end{aligned}$$

 A --+-------------[NAND3 G2]--+
     |               |    1 -->|
     +--[NAND3 G1]---+         +--[NAND3 G4]-- Y
     |   1 -->|      |         |    1 -->|
 B --+-------------[NAND3 G3]--+
                          1 -->|
 (1 --> : third input tied to logic HIGH)

A half subtractor subtracts one bit B from another bit A and gives a Difference (D) and a Borrow (Bo).

$$D = A \oplus B, \qquad B_o = \bar A B$$

 A --+--[XOR]------------ D
 B --+--|
 A --[NOT]--[AND]-------- Bo
 B ---------|

Verilog HDL description

// Half subtractor: gate-level (structural) model
module half_sub_gate (input A, B, output D, Bo);
  wire An;              // complement of A
  xor g1 (D, A, B);     // D  = A XOR B
  not g2 (An, A);       // An = A'
  and g3 (Bo, An, B);   // Bo = A'B
endmodule

// Same circuit: dataflow model
module half_sub_df (input A, B, output D, Bo);
  assign D  = A ^ B;    // difference
  assign Bo = ~A & B;   // borrow
endmodule

Test bench (simulation)

module tb;
  reg A, B; wire D, Bo;
  half_sub_df uut (A, B, D, Bo);
  initial begin
    $monitor("A=%b B=%b D=%b Bo=%b", A, B, D, Bo);
    {A,B} = 2'b00; #10 {A,B} = 2'b01;
    #10 {A,B} = 2'b10; #10 {A,B} = 2'b11;
    #10 $finish;
  end
endmodule

Simulation output matches the truth table, e.g. A=0 B=1 D=1 Bo=1 and A=1 B=1 D=0 Bo=0.

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.

Importance of De Morgan's laws

De Morgan's laws ($\overline{A+B} = \bar A\bar B$, $\overline{AB} = \bar A + \bar B$) are used to:

• complement Boolean expressions easily;
• convert AND-OR (SOP) circuits to NAND-NAND and OR-AND (POS) circuits to NOR-NOR;
• build every gate from one universal gate (NAND or NOR), reducing chip types and cost;
• show gate equivalences such as NAND = bubbled OR and NOR = bubbled AND.

NOR gate from 2-input NAND gates

Required: $Y = \overline{A + B}$. By De Morgan, $A + B = \overline{\bar A \cdot \bar B}$, so:

$$\begin{aligned} G_1 &= \overline{A \cdot A} = \bar A \\ G_2 &= \overline{B \cdot B} = \bar B \\ G_3 &= \overline{\bar A \cdot \bar B} = A + B \\ Y &= \overline{G_3 \cdot G_3} = \overline{A + B} \end{aligned}$$

Four NAND gates are needed: two as input inverters, one to make OR, and one as the output inverter.

 A --[NAND G1]-- A' --+
   (inputs tied)      +--[NAND G3]-- A+B --[NAND G4]-- Y
 B --[NAND G2]-- B' --+                  (inputs tied)

Commutative laws

The order of variables in an OR or AND operation does not change the result.

• $A + B = B + A$
• $A \cdot B = B \cdot A$

Example: $\bar A + C = C + \bar A$; with A = 1, B = 0: $1 \cdot 0 = 0 \cdot 1 = 0$. In hardware, swapping the inputs of an AND or OR gate does not change its output.

Associative laws

The grouping of variables in an OR or AND operation does not change the result.

• $A + (B + C) = (A + B) + C$
• $A \cdot (B \cdot C) = (A \cdot B) \cdot C$

Example: with A = 1, B = 0, C = 1: $1 \cdot (0 \cdot 1) = 0$ and $(1 \cdot 0) \cdot 1 = 0$. So a 3-input AND can be built from two 2-input AND gates in any order.

Proof of $A + \bar A B = A + B$

Using the distributive law $X + YZ = (X + Y)(X + Z)$:

$$\begin{aligned} A + \bar A B &= (A + \bar A)(A + B) \\ &= 1 \cdot (A + B) \\ &= A + B \end{aligned}$$

Truth-table check:

In positive logic HIGH = 1 and LOW = 0; in negative logic HIGH = 0 and LOW = 1. Changing the convention complements every input and output bit of the same physical gate.

Take a gate that acts as XOR in positive logic. Its voltage table:

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

Y = 1 when inputs differ: XOR, $Y = A \oplus B$.

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

Rearranged in normal order (00, 01, 10, 11) the output is 1, 0, 0, 1: Y = 1 when inputs are equal: XNOR.

Algebraic proof: complement inputs and output of the positive-logic XOR:

$$\begin{aligned} Y_{neg} &= \overline{\bar A \oplus \bar B} \\ &= \overline{\bar A \bar{\bar B} + \bar{\bar A} \bar B} \\ &= \overline{\bar A B + A \bar B} \\ &= \overline{A \oplus B} = AB + \bar A \bar B = A \odot B \end{aligned}$$

Hence positive-logic XOR is equivalent to negative-logic XNOR.

$F = (A+B)(C+D)E$ is a product of sums (POS). A POS form maps directly to a NOR-NOR circuit, using double inversion and De Morgan's law.

$$\begin{aligned} F &= (A+B)(C+D)E \\ &= \overline{\overline{(A+B)(C+D)E}} \\ &= \overline{\overline{A+B} + \overline{C+D} + \bar E} \quad (\text{De Morgan}) \end{aligned}$$

So:

• $G_1 = \overline{A + B}$ (2-input NOR)
• $G_2 = \overline{C + D}$ (2-input NOR)
• $G_3 = \overline{E + E} = \bar E$ (NOR used as inverter)
• $F = \overline{G_1 + G_2 + G_3}$ (3-input NOR)

 A --[NOR G1]--(A+B)'--+
 B --|                 |
 C --[NOR G2]--(C+D)'--+--[NOR G4]-- F
 D --|                 |   (3-input)
 E --[NOR G3]-- E' ----+
   (inputs tied)

Total: 4 NOR gates (three 2-input, one 3-input). If only 2-input NORs are allowed, G4 can be replaced by: $G_4' = \overline{G_1 + G_2}$, $G_5 = \overline{G_4' + G_4'}$ (= $G_1 + G_2$), $F = \overline{G_5 + G_3}$, giving 6 gates.

Check: A = 1, B = 0, C = 0, D = 1, E = 1 → $G_1 = 0$, $G_2 = 0$, $G_3 = 0$, F = 1; and $(1)(1)(1) = 1$.

Universal gates

The universal gates are NAND and NOR. They are called universal because any Boolean function, and every other gate (NOT, AND, OR, XOR, XNOR), can be built using only NAND gates or only NOR gates. For example, with NAND only: NOT A = $\overline{A A}$, AND = NAND followed by NOT, OR = $\overline{\bar A \bar B}$. This lets a whole circuit be made from one type of IC (e.g. 7400), which simplifies manufacture and reduces cost.

XOR using only NAND gates

$Y = A \oplus B = A\bar B + \bar A B$ needs four 2-input NAND gates.

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

Gates: $G_1 = \overline{AB}$, $G_2 = \overline{A G_1}$, $G_3 = \overline{B G_1}$, $Y = \overline{G_2 G_3}$.

 A --+---------------[NAND G2]--+
     |                 |        |
     +--[NAND G1]--G1--+        +--[NAND G4]-- Y
     |                 |        |
 B --+---------------[NAND G3]--+

NAND and NOR gates are called universal gates because each of them alone can realise the three basic operations NOT, AND and OR, and therefore any Boolean function. A complete circuit can thus be made using only one type of gate (e.g. 7400 quad NAND or 7402 quad NOR), which reduces inventory, cost and design effort.

Using NAND only

 NOT: A --[NAND]-- A'      (inputs tied)
 AND: A,B --[NAND]--[NAND]-- AB
 OR : A --[NAND]-- A' --+
      B --[NAND]-- B' --+--[NAND]-- A+B

Using NOR only

 NOT: A --[NOR]-- A'
 OR : A,B --[NOR]--[NOR]-- A+B
 AND: A --[NOR]-- A' --+
      B --[NOR]-- B' --+--[NOR]-- AB

Example: $Y = AB + CD$ can be done with three NAND gates: $Y = \overline{\overline{AB} \cdot \overline{CD}}$ (NAND-NAND form of an SOP).

HDL

A Hardware Description Language (HDL) is a computer language used to describe the structure and behaviour of digital circuits in text form. The description can be simulated to check the design and synthesised into gates for an FPGA, CPLD or ASIC. Common HDLs are Verilog and VHDL. A design can be written at gate level (structural), dataflow (assign equations) or behavioural (always blocks) level.

2-to-4 line decoder

Inputs A1 A0 and enable E; exactly one output goes HIGH for each input code when E = 1.

$D_0 = E\bar A_1 \bar A_0$, $D_1 = E\bar A_1 A_0$, $D_2 = E A_1 \bar A_0$, $D_3 = E A_1 A_0$

Verilog (dataflow model)

module decoder2to4 (input A1, A0, E,
                   output D0, D1, D2, D3);
  assign D0 = E & ~A1 & ~A0; // 00
  assign D1 = E & ~A1 &  A0; // 01
  assign D2 = E &  A1 & ~A0; // 10
  assign D3 = E &  A1 &  A0; // 11
endmodule

Verilog (gate-level model)

module decoder2to4_g (input A1, A0, E,
                     output D0, D1, D2, D3);
  wire n1, n0;
  not (n1, A1);           // A1'
  not (n0, A0);           // A0'
  and (D0, E, n1, n0);
  and (D1, E, n1, A0);
  and (D2, E, A1, n0);
  and (D3, E, A1, A0);
endmodule

With E = 1 and A1A0 = 10, simulation gives D3D2D1D0 = 0100.

$Y = A \oplus B$. Build XNOR with 4 NOR gates and invert it with a fifth NOR (inputs tied). Minimum: 5 NOR gates.

$$\begin{aligned} G_1 &= \overline{A + B} \\ G_2 &= \overline{A + G_1} = \bar A B \\ G_3 &= \overline{B + G_1} = A \bar B \\ G_4 &= \overline{G_2 + G_3} = \overline{A \oplus B} \\ Y &= \overline{G_4 + G_4} = A \oplus B \end{aligned}$$

 A --+-----------[NOR G2]--+
     |              |      |
     +--[NOR G1]----+      +--[NOR G4]--[NOR G5]-- Y
     |              |      |          (inputs tied)
 B --+-----------[NOR G3]--+

Positive and negative logic

• Positive logic: HIGH voltage = logic 1, LOW voltage = logic 0 (e.g. TTL: +5 V = 1, 0 V = 0).
• Negative logic: HIGH voltage = logic 0, LOW voltage = logic 1 (e.g. +5 V = 0, 0 V = 1).

The same physical gate performs a different logic function in the two systems, because changing the convention complements every input and output. Example: a gate whose output is HIGH only when both inputs are HIGH is an AND gate in positive logic but an OR gate in negative logic.

De Morgan's theorem for 3 variables

Theorem 1: $\overline{A + B + C} = \bar A \cdot \bar B \cdot \bar C$

Theorem 2: $\overline{A \cdot B \cdot C} = \bar A + \bar B + \bar C$

Verification by truth table

Columns 4 and 5 are identical, and columns 6 and 7 are identical for all 8 combinations, so both theorems hold for 3 variables.

Algebraic check (using the 2-variable law with $X = B + C$):

$$\begin{aligned} \overline{A + B + C} &= \overline{A + X} = \bar A \cdot \bar X \\ &= \bar A \cdot \overline{B + C} = \bar A \bar B \bar C \end{aligned}$$

Similarly, $\overline{A(BC)} = \bar A + \overline{BC} = \bar A + \bar B + \bar C$.

 3-input NOR = bubbled 3-input AND
 3-input NAND = bubbled 3-input OR

De Morgan's laws

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

Example: $\overline{\bar A + B} = A \bar B$ and $\overline{A \bar C} = \bar A + C$.

2-input XNOR using only NOR gates

$Y = A \odot B = AB + \bar A \bar B = \overline{A\bar B + \bar A B}$ needs four 2-input NOR gates (the dual of the 4-NAND XOR).

$$\begin{aligned} G_1 &= \overline{A + B} \\ G_2 &= \overline{A + G_1} = \bar A (A + B) = \bar A B \\ G_3 &= \overline{B + G_1} = \bar B (A + B) = A \bar B \\ Y &= \overline{G_2 + G_3} = \overline{\bar A B + A \bar B} = A \odot B \end{aligned}$$

 A --+---------------[NOR G2]--+
     |                 |       |
     +--[NOR G1]---G1--+       +--[NOR G4]-- Y
     |                 |       |
 B --+---------------[NOR G3]--+

Y = 1 only when A = B, which is the XNOR function.

Positive and negative logic

• Positive logic: HIGH voltage = 1, LOW voltage = 0. Example: TTL with +5 V = 1, 0 V = 0.
• Negative logic: HIGH voltage = 0, LOW voltage = 1. Example: +5 V = 0, 0 V = 1.

Example: a gate gives a HIGH output only when both inputs are HIGH (L L → L, L H → L, H L → L, H H → H).

• In positive logic this is 00→0, 01→0, 10→0, 11→1: an AND gate.
• In negative logic this is 11→1, 10→1, 01→1, 00→0: an OR gate.

So positive AND = negative OR (and positive NAND = negative NOR, positive XOR = negative XNOR).

Ex-NOR gate using only NOR gates

$Y = A \odot B = AB + \bar A \bar B = \overline{A\bar B + \bar A B}$ needs four 2-input NOR gates (the dual of the 4-NAND XOR).

$$\begin{aligned} G_1 &= \overline{A + B} \\ G_2 &= \overline{A + G_1} = \bar A (A + B) = \bar A B \\ G_3 &= \overline{B + G_1} = \bar B (A + B) = A \bar B \\ Y &= \overline{G_2 + G_3} = \overline{\bar A B + A \bar B} = A \odot B \end{aligned}$$

 A --+---------------[NOR G2]--+
     |                 |       |
     +--[NOR G1]---G1--+       +--[NOR G4]-- Y
     |                 |       |
 B --+---------------[NOR G3]--+

Universal gates

A universal gate is a gate that alone can implement NOT, AND and OR, and hence any Boolean function. NAND and NOR are universal gates.

Examples with NAND only:

• NOT: $\overline{A \cdot A} = \bar A$
• AND: NAND followed by a NAND inverter, $\overline{\overline{AB}} = AB$
• OR: $\overline{\bar A \cdot \bar B} = A + B$

Examples with NOR only:

• NOT: $\overline{A + A} = \bar A$
• OR: NOR followed by a NOR inverter
• AND: $\overline{\bar A + \bar B} = AB$

 OR from NAND:
 A --[NAND]-- A' --+
 B --[NAND]-- B' --+--[NAND]-- A+B

Positive and negative logic

• Positive logic: HIGH level = logic 1 and LOW level = logic 0 (e.g. +5 V = 1, 0 V = 0).
• Negative logic: HIGH level = logic 0 and LOW level = logic 1.

The same circuit changes its logic name when the convention changes. A gate with output HIGH only when both inputs are HIGH is AND in positive logic but OR in negative logic; similarly positive NAND = negative NOR.

A 3-input XNOR gives $Y = \overline{A \oplus B \oplus C}$. Use the 4-NOR XNOR block twice and one NOR inverter.

Since $\overline{A \oplus B} \odot C = \overline{\overline{A \oplus B} \oplus C} = A \oplus B \oplus C$, two XNOR blocks give XOR, and a final NOR inverter gives XNOR:

$$\begin{aligned} P &= A \odot B = \overline{A \oplus B} \quad (4 \text{ NOR}) \\ Q &= P \odot C = A \oplus B \oplus C \quad (4 \text{ NOR}) \\ Y &= \overline{Q + Q} = \overline{A \oplus B \oplus C} \quad (1 \text{ NOR}) \end{aligned}$$

Each XNOR block: $G_1 = \overline{X+Z}$, $G_2 = \overline{X+G_1}$, $G_3 = \overline{Z+G_1}$, out $= \overline{G_2+G_3}$.

 A --+
     +--[XNOR: 4 NOR]-- P --+
 B --+                      +--[XNOR: 4 NOR]-- Q
                       C ---+                  |
                 Y --[NOR, inputs tied]--------+

Total: 9 NOR gates.

Y = 1 when an even number of inputs are 1.

A 3-input XOR gives $Y = A \oplus B \oplus C = (A \oplus B) \oplus C$. Each 2-input XOR needs 4 NAND gates, so cascade two 4-NAND XOR blocks: 8 NAND gates.

Block 1: $P = A \oplus B$ $G_1 = \overline{AB}$, $G_2 = \overline{A G_1}$, $G_3 = \overline{B G_1}$, $P = \overline{G_2 G_3}$

Block 2: $Y = P \oplus C$ $G_5 = \overline{PC}$, $G_6 = \overline{P G_5}$, $G_7 = \overline{C G_5}$, $Y = \overline{G_6 G_7}$

 A --+-------[G2]--+
     +--[G1]--+    +--[G4]--P--+-------[G6]--+
 B --+-------[G3]--+           +--[G5]--+    +--[G8]-- Y
                           C --+-------[G7]--+
 (all gates are 2-input NAND)

Y = 1 when an odd number of inputs are 1.

De Morgan's theorems

De Morgan's theorems tell us how to complement a sum or a product of variables.

Theorem 1: The complement of a sum equals the product of the complements.

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

Theorem 2: The complement of a product equals the sum of the complements.

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

In words: to complement an expression, change every OR into AND (and every AND into OR) and complement each variable. So a NOR gate is the same as an AND gate with inverted inputs ("bubbled AND"), and a NAND gate is the same as an OR gate with inverted inputs ("bubbled OR").

Proof by truth table

Column 4 equals column 5 for all inputs, which proves Theorem 1. Column 7 equals column 8, which proves Theorem 2.

Algebraic proof of Theorem 1: if $X = A+B$ and $Y = \overline{A}\,\overline{B}$, then $Y$ is the complement of $X$ only if $X+Y=1$ and $X\cdot Y=0$.

$$\begin{aligned} X+Y &= A+B+\overline{A}\,\overline{B} = A + B + \overline{A} = 1 \\ X\cdot Y &= (A+B)\overline{A}\,\overline{B} = A\overline{A}\,\overline{B} + B\overline{A}\,\overline{B} = 0+0 = 0 \end{aligned}$$

So $\overline{A+B} = \overline{A}\,\overline{B}$. Theorem 2 follows by duality.

X-NOR gate using NOR gates only

$$Y = A \odot B = AB + \overline{A}\,\overline{B}$$

Four NOR gates are enough:

1. $G_1 = \overline{A+B}$
2. $G_2 = \overline{A + G_1} = \overline{A}\,(A+B) = \overline{A}B$
3. $G_3 = \overline{B + G_1} = \overline{B}\,(A+B) = A\overline{B}$
4. $Y = \overline{G_2 + G_3} = \overline{\overline{A}B + A\overline{B}} = AB + \overline{A}\,\overline{B}$

A ──┬──────────────┐
    │              [NOR]── G2 ──┐
    ├──[NOR]── G1 ─┤            [NOR]── Y = A XNOR B
    │              [NOR]── G3 ──┘
B ──┴──────────────┘

(G1 = NOR(A,B); G2 = NOR(A,G1); G3 = NOR(B,G1); Y = NOR(G2,G3).)

The output is 1 only when A = B, so the circuit is an X-NOR gate. (With NAND gates, four NANDs give X-OR and a fifth NAND used as an inverter gives X-NOR.)