Logic Gates
Open in the Padhaiko app2.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.
| Gate | Expression | Output is 1 when | Symbol shape |
|---|---|---|---|
| AND | All inputs are 1 | D shape | |
| OR | At least one input is 1 | Curved (shield) shape | |
| NOT (inverter) | The input is 0 | Triangle with a bubble |
| A | B | AND | OR | NOT A |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 |
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.
| A | B | NAND | NOR |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 0 |
| Function | Using NAND only | Using 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.
| A | B | XOR | XNOR |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Equivalents:
- (sum of products form).
- (product of sums form).
- XOR from four NAND gates: with , .
- (the XNOR is the equality function).
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.
| Physical gate | Positive logic | Negative logic |
|---|---|---|
| AND | AND | OR |
| OR | OR | AND |
| NAND | NAND | NOR |
| NOR | NOR | NAND |
| XOR | XOR | XNOR |
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
De Morgan's laws
- The complement of a product equals the sum of the complements: .
- 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
- Enable / inhibit control: an AND gate passes a signal only when the enable input is 1; an OR gate passes it only when the enable is 0.
- Parity generation and checking: a chain of XOR gates gives 1 for an odd number of 1s (odd parity).
- Comparison: an XNOR gate shows whether two bits are equal.
- Arithmetic: XOR and AND form the half adder (Chapter 4).
- Safety interlocks and alarms: a machine starts only when guard AND power AND key conditions are all 1.
- Selection and decoding: AND gates with inverters detect one particular input pattern.
Worked Examples
1
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.
XOR needs 4 NAND gates; needs 3 NAND gates in a two-level NAND-NAND circuit.
2
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: .
The same physical gate is an AND gate in positive logic and an OR gate in negative logic.
3
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 .
, which is 1 for the five rows 000, 001, 011, 101 and 111.
Exercises
Exercises: Logic Gates
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: .
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.
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.
holds in all four rows (1, 0, 0, 0); so NOR is a bubbled-input AND.
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.
; XNOR ; and .
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.
A positive-logic NAND gate acts as a NOR gate in negative logic.
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.
: 2 NOT + 2 AND + 1 OR = 5 gates.