PadhaikoAll subjects

Logic Gates

Digital Logic (ENEX 152)

Open in the Padhaiko app

2.1 Basic gates and their equivalents

A logic gate is a circuit with one or more inputs and one output that implements a Boolean function. The three basic gates are AND, OR and NOT.

Basic Gates
GateExpressionOutput is 1 whenSymbol shape
ANDAll inputs are 1D shape
ORAt least one input is 1Curved (shield) shape
NOT (inverter)The input is 0Triangle with a bubble
Truth Tables of AND, OR and NOT
ABANDORNOT A
00001
01011
10010
11110

A bubble on an input or output means inversion. A gate with inputs has rows in its truth table. Any gate can be rebuilt from other gates, which gives its equivalents: for example OR is the same as an AND with inverters on all inputs and the output, .

2.2 Universal gates and their equivalents

NAND () and NOR () are called universal gates because any logic function can be built using only NAND gates or only NOR gates.

NAND and NOR Truth Table
ABNANDNOR
0011
0110
1010
1100
Basic Gates Built from NAND or NOR Only
FunctionUsing NAND onlyUsing NOR only
NOT Tie both inputs together: Tie both inputs together:
AND NAND followed by a NAND inverter (2 gates)Invert A and B with NORs, then NOR them (3 gates)
OR Invert A and B with NANDs, then NAND them (3 gates)NOR followed by a NOR inverter (2 gates)

2.3 Exclusive gates and their equivalents

XOR gives 1 when the inputs are different (odd number of 1s). XNOR gives 1 when the inputs are equal.

XOR and XNOR
ABXOR XNOR
0001
0110
1010
1101

Equivalents:

Useful identities: , , , . An XOR works as a controlled inverter: with control it inverts the other input, with it passes it.

2.4 Positive and negative logic

In positive logic the HIGH voltage is logic 1 and the LOW voltage is logic 0. In negative logic it is the other way round: HIGH is 0 and LOW is 1. The physical circuit is the same; only the interpretation changes, and the function of a gate changes with it.

Gate Function in Positive and Negative Logic
Physical gatePositive logicNegative logic
ANDANDOR
ORORAND
NANDNANDNOR
NORNORNAND
XORXORXNOR

This is the duality principle: converting a positive-logic truth table to negative logic means complementing every input and output column, and the result is the dual function.

2.5 De'Morgan's laws

Theorem

De Morgan's laws

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

For variables: .

Rule to apply them: break the bar and change the operator (AND to OR, OR to AND). So a NAND is the same as an OR gate with inverted inputs (bubbled OR), and a NOR is the same as an AND gate with inverted inputs (bubbled AND).

2.6 Applications of logic gates


Worked Examples

Example 1

1 (8 marks)

Realise (a) the XOR function and (b) the function using only NAND gates. Count the NAND gates required in each case, and check the circuits by listing all inputs.

XOR with NAND gates. Let the first gate be . Feed and into a second NAND to get , feed and into a third NAND to get , and join and in a fourth NAND: . This takes 4 NAND gates.

Check by substitution. For : , , , so . For : , , . For : , , . This is the XOR table.

Two-level NAND-NAND for .

Use and (two NANDs) followed by a third NAND: . This needs 3 NAND gates.

Answer:

XOR needs 4 NAND gates; needs 3 NAND gates in a two-level NAND-NAND circuit.

Example 2

2 (6 marks)

A gate has the following voltage table: it outputs HIGH only when both inputs are HIGH. Find the function in positive logic and in negative logic, and write the negative-logic truth table.

Voltage table. With H and L for HIGH and LOW: LL gives L, LH gives L, HL gives L and HH gives H.

Positive logic (H = 1, L = 0). The output is 1 only for input 11, so the gate is a 2-input AND: .

Negative logic (H = 0, L = 1). Replace H by 0 and L by 1 in every row: input 11 gives output 1, 10 gives 1, 01 gives 1, 00 gives 0. The output is 1 whenever any input is 1 (negative-logic inputs), so the same gate is a 2-input OR: .

Answer:

The same physical gate is an AND gate in positive logic and an OR gate in negative logic.

Example 3

3 (6 marks)

Use De Morgan's laws to simplify and draw its truth table.

Apply the outer bar. The bar over a product becomes a sum of complements: .

Apply the laws once more. and , so .

Truth table. for (four rows) and for (one row), so for .

Answer:

, which is 1 for the five rows 000, 001, 011, 101 and 111.


Exercises

Exercises: Logic Gates

Question 1

Why are NAND and NOR called universal gates? Build an inverter, an AND gate and an OR gate from NOR gates only.

A gate is universal if every Boolean function can be built from it alone. Since AND, OR and NOT are enough for any function, a gate that can make all three is universal.

NOT: connect both NOR inputs together: . OR: a NOR followed by a NOR inverter: . AND: invert each input with a NOR and NOR the results: .

Answer:

NAND and NOR can each produce NOT, AND and OR, so any function can be built from either one alone. Inverter: 1 NOR, OR: 2 NORs, AND: 3 NORs.

Question 2

Prove De Morgan's law using a truth table, and use it to show that a NOR gate equals an AND gate with inverted inputs.

List all four input pairs. For : LHS , RHS . For : LHS , RHS . For : LHS , RHS . For : LHS , RHS .

The two columns are identical in all four rows, so the law is true. The left side is the NOR output and the right side is an AND of and , which is an AND gate with inverted (bubbled) inputs.

Answer:

holds in all four rows (1, 0, 0, 0); so NOR is a bubbled-input AND.

Question 3

Show that by listing the truth table, and write the XNOR expression. Find the value of for and for .

Rows: : ; : ; : ; : . This equals the XOR table (0, 1, 1, 0).

XNOR is the complement: .

Three-input XOR is 1 for an odd number of 1s. For there are three 1s, so the result is 1. For there is one 1, so the result is 1.

Answer:

; XNOR ; and .

Question 4

A positive-logic NAND gate is used in a system with negative logic. Which gate does it become? Verify with its truth table.

In positive logic the NAND output is 1 for inputs 00, 01, 10 and 0 for 11. Negative logic complements every input and output: input 11 (positive 00) gives output 0 (positive 1); input 10 (positive 01) gives 0; input 01 gives 0; input 00 (positive 11) gives 1 (positive 0).

So in negative logic the output is 1 only when both inputs are 0, which is , the NOR function.

Answer:

A positive-logic NAND gate acts as a NOR gate in negative logic.

Question 5

Design an alarm that sounds when the key is absent () and the door is open (), or when the power is on () and the guard is removed (). Write the function and give the number of gates for an AND-OR NOT realisation.

First condition: . Second condition: . The alarm is on if either is true: .

Gates: two inverters ( and ), two AND gates and one OR gate, five gates in total. With a NAND-only version the same function needs two inverters and three NANDs.

Answer:

: 2 NOT + 2 AND + 1 OR = 5 gates.

← IntroductionBoolean Algebra and K-Maps →