Use the following logic gate symbols: NOT, AND, OR, NAND, NOR, XOR

3.2 Logic Gates and Logic Circuits

Learning Outcomes (Cambridge AS & A‑Level Computer Science 9618)

• Identify the graphical symbols for the six basic logic gates: NOT, AND, OR, NAND, NOR, XOR.
• State the Boolean function and a typical programming‑style expression for each gate.
• Construct a complete truth table for each gate.
• Design a logic circuit from a given Boolean expression (expression → circuit).
• Derive the Boolean expression represented by a given circuit diagram (circuit → expression).
• Explain why NAND and NOR are *universal* gates and design simple circuits using only NAND or only NOR.
• (A‑Level extension) Simplify Boolean expressions using algebraic identities and Karnaugh maps, and show the impact on the number of gates required.
• Understand basic practical considerations – gate delay, fan‑in and fan‑out.

1. Gate Symbols, Boolean Functions & Typical Expressions

The table summarises the standard graphical symbol (textual form), the Boolean function and a typical programming‑style expression for each of the six basic gates.

2. Truth Tables for the Six Basic Gates

2.1 NOT Gate

2.2 AND Gate

2.3 OR Gate

2.4 NAND Gate

2.5 NOR Gate

2.6 XOR Gate

3. Universal Gates – NAND and NOR

Both NAND and NOR can be used to build any Boolean function; they are therefore called *universal* gates. Knowing how to construct the basic gates from NAND (or NOR) is a common exam requirement.

3.1 Building AND, OR and NOT with NAND only

• NOT using NAND: \(\overline{A}=A\;\text{NAND}\;A\)
• AND using NAND: \(A·B=\overline{\,\overline{A·B}\,}= (A\;\text{NAND}\;B)\;\text{NAND}\;(A\;\text{NAND}\;B)\)
• OR using NAND: \(A+B=\overline{\overline{A}\;\cdot\;\overline{B}}=

  (\;A\;\text{NAND}\;A\;)\;\text{NAND}\;(\;B\;\text{NAND}\;B\;)\)

Example – AND using only NAND

3.2 Building AND, OR and NOT with NOR only

• NOT using NOR: \(\overline{A}=A\;\text{NOR}\;A\)
• OR using NOR: \(A+B=\overline{\,\overline{A+B}\,}= (A\;\text{NOR}\;B)\;\text{NOR}\;(A\;\text{NOR}\;B)\)
• AND using NOR: \(A·B=\overline{\overline{A}\;+\;\overline{B}}=

  (\;A\;\text{NOR}\;A\;)\;\text{NOR}\;(\;B\;\text{NOR}\;B\;)\)

4. Constructing Circuits – From Boolean Expression to Diagram

When a problem statement provides a Boolean expression, follow these systematic steps:

1. Identify each distinct sub‑expression (product terms, negations, etc.).
2. Select the appropriate gate for every sub‑expression.
3. Connect the outputs of earlier gates to the inputs of later gates, respecting the order of operations (parentheses first, then NOT, then AND, then OR).
4. Label every input and the final output clearly.
5. Check the design against a truth table (optional but recommended).

Example 1 – Implement \(F = (A·B) + \lnot C\)

1. AND sub‑expression: A·B → use an AND gate.
2. NOT sub‑expression: ¬C → use a NOT gate.
3. OR the two results: use an OR gate.

5. Constructing Circuits – From Diagram to Boolean Expression

Read the diagram from left to right (inputs → gates → output) and translate each gate back into its Boolean form.

Example 2 – Deriving the expression from a mixed‑gate circuit

1. First gate: NAND(A,B) → \(\overline{A·B}\).
2. Second gate: XOR of the NAND output with D → \(\overline{A·B}\;\oplus\;D\).
3. Overall expression: Y = \(\overline{A·B} \oplus D\).

6. Practical Considerations

• Gate delay: each gate introduces a small propagation time. In a cascade, total delay ≈ (number of gate levels) × (typical gate delay). Keep the number of levels low for faster circuits.
• Fan‑in: the maximum number of inputs a gate can accept (e.g. a 2‑input AND has fan‑in = 2). Larger fan‑in may increase delay and power consumption.
• Fan‑out: the number of gate inputs that can be driven by a single output. Most TTL/CMOS gates can drive several inputs; exceeding the recommended fan‑out can cause voltage‑level problems.

7. Simplifying Boolean Expressions (A‑Level Extension)

Algebraic identities and Karnaugh maps (K‑maps) are the two main techniques.

7.1 Key Boolean Identities

• Identity \(A + \overline{A} = 1\)
• Null law \(A·0 = 0,\; A+0 = A\)
• Idempotent \(A·A = A,\; A+A = A\)
• Complement \(A·\overline{A}=0,\; A+\overline{A}=1\)
• De Morgan’s \(\overline{A·B}= \overline{A} + \overline{B}\) and \(\overline{A+B}= \overline{A}·\overline{B}\)
• Distributive \(A·(B+C)=A·B + A·C\)

7.2 Worked K‑Map Simplification

Minimise the 3‑variable function

\[

F(A,B,C)=\sum m(1,2,4,5,6,7)

\]

1. Fill the 3‑variable K‑map (AB as rows, C as columns).

2. Form the largest possible groups of 1s (powers of two):

• Group 1: the four 1s covering columns C=1 (covers minterms 1,3,5,7) → gives term \(C\).
• Group 2: the four 1s covering rows AB=01 and 11 (covers minterms 2,3,6,7) → gives term \(B\).
• Group 3: the two 1s at (AB=10, C=0) and (AB=00, C=0) → gives term \(\overline{C}·\overline{A}\).

3. Minimal SOP expression:

\[

F = C + B + \overline{A}\,\overline{C}

\]

4. Gate count after simplification (using only 2‑input gates):

• NOT for \(\overline{A}\) and \(\overline{C}\) – 2 gates.
• AND for \(\overline{A}\,\overline{C}\) – 1 gate.
• OR to combine the three terms – 2 OR gates (first OR combines \(C\) and \(B\), second OR adds \(\overline{A}\,\overline{C}\)).
• Total = 5 gates (compared with 7 gates for the original SOP).

7.3 Simplification Using NAND‑Only Design (example)

Design \(F = A·B\) using only NAND gates (see Section 3). The final circuit uses two NAND gates, saving one gate compared with the naïve implementation (AND + NOT). This illustrates the practical benefit of recognising universal‑gate designs.

8. Worked Example – Full Design Process

Problem Statement

Design a circuit that implements

\[

F = (A·B) + \lnot C + (D·E)

\]

Step 1 – Build the Diagram (Expression → Circuit)

1. AND gate for \(A·B\).
2. NOT gate for \(\lnot C\).
3. AND gate for \(D·E\).
4. OR gate that combines the three results.

Step 2 – Truth Table for the Circuit

Step 3 – Derive the Expression from the Diagram (Circuit → Expression)

Reading Figure 4 from left to right:

• First AND → \(A·B\)
• NOT → \(\lnot C\)
• Second AND → \(D·E\)
• OR combines them → \(F = (A·B) + \lnot C + (D·E)\)

9. Practice Tasks

1. Expression → circuit & truth table
   

   \(G = \lnot (X·Y) + (X·\lnot Y)\)
   

   • Draw the circuit (use a NAND for the first term, a NOT for \(\lnot Y\), an AND, then an OR).
   • Complete the 4‑row truth table for inputs X, Y and output G.

2. Circuit → expression
   

   (Insert a diagram of a NOR feeding an XOR, for example.)
   

   Write the Boolean expression represented by the circuit.

3. Simplification
   

   Simplify \(H = (P·Q) + (P·\lnot Q) + (\lnot P·Q)\) using algebraic identities.
   

   State the minimal number of 2‑input gates required after simplification.

4. Universal‑gate design
   

   Which combination of the six basic gates yields the fewest gates for the function \(J = A \oplus B \oplus C\)?
   

   (Hint: use two XOR gates in cascade; an alternative using only NANDs requires more gates.)

5. Gate‑delay analysis
   

   The circuit in Figure 4 has three gate levels. If each gate has a propagation delay of 10 ns, what is the worst‑case delay from any input to the output F?

10. Common Pitfalls

• NAND vs NOR – NAND is the negation of AND; NOR is the negation of OR. Do not confuse the two.
• XOR meaning – XOR is true only when the inputs differ. It is not “OR but not AND”.
• Signal flow – always draw inputs on the left and let the signal move to the right; this avoids wiring ambiguities.
• Parentheses – when converting a circuit to an expression, use parentheses to preserve the intended order of operations.
• Gate‑delay oversight – a circuit with many cascaded gates will be slower; aim to minimise the number of levels.

11. Summary

To succeed in the Cambridge AS & A‑Level Computer Science exam you must:

• Know the symbols, Boolean functions and truth tables for NOT, AND, OR, NAND, NOR and XOR.
• Be able to translate freely between Boolean expressions and gate‑level diagrams.
• Recognise that NAND and NOR are universal and be comfortable designing simple circuits with them only.
• Apply Boolean algebra and Karnaugh‑map techniques to simplify expressions and reduce the number of gates.
• Consider practical aspects such as gate delay, fan‑in and fan‑out when evaluating a design.

Mastery of these points will give you a solid foundation for both the AS and the A‑Level extensions of the 3.2 Logic Gates and Logic Circuits topic.