Construct a logic expression

3.2 Logic Gates and Logic Circuits

Objective

By the end of this lesson you will be able to construct a logic expression, a truth table, and a logic circuit from any of the following:

• a written description (English),
• a circuit diagram, or
• a truth table.

You will also be able to simplify Boolean expressions using Boolean algebra and, for A‑Level, minimise them with Karnaugh maps.

1. Required Logic Gates (two‑input only)

Gate	Boolean Symbol	Logic Symbol	Truth Table (A, B → Output)
AND	$A\!\cdot\!B$		A B Output 0 0 0 0 1 0 1 0 0 1 1 1
OR	$A + B$		A B Output 0 0 0 0 1 1 1 0 1 1 1 1
NOT (inverter)	$\overline{A}$ or $\lnot A$		A Output 0 1 1 0
NAND	$\overline{A\!\cdot\!B}$		A B Output 0 0 1 0 1 1 1 0 1 1 1 0
NOR	$\overline{A + B}$		A B Output 0 0 1 0 1 0 1 0 0 1 1 0
XOR	$A \oplus B$		A B Output 0 0 0 0 1 1 1 0 1 1 1 0

Note: In the Cambridge syllabus every gate (except NOT) has exactly two inputs. When a problem requires a three‑input AND, OR, etc., you must cascade

2. Operator Precedence

• NOT (¬) – highest
• AND (·) – next
• XOR (⊕) – evaluated after AND
• OR (+) – lowest

Always use parentheses to make the intended order explicit, especially when mixing AND, XOR and OR.

3. Constructing Truth Tables

3.1 From a Problem Statement (English)

1. List every distinct condition and assign a single‑letter variable.
2. Create a column for each variable and one column for the required output.
3. Write every possible combination of inputs – for n variables there are $2^{n}$ rows.
4. For each row, evaluate the English condition and place 1 (true) or 0 (false) in the output column.

3.2 From a Logic Expression

1. Set up the same input columns as above.
2. Apply the operator precedence (NOT → AND → XOR → OR) to evaluate the expression for each row.
3. Record the result in the output column.

3.3 From a Logic Circuit

1. Identify all input variables and the final output node.
2. Label each gate with its Boolean symbol.
3. Follow the signal flow from the inputs through each gate, evaluating the gate function for every row of the input combinations.

Worked Example – Alarm System

Problem: “The alarm sounds if the door is open and the system is armed, or if a fire is detected while the system is not armed.”

• $D$ – Door open
• $A$ – System armed
• $F$ – Fire detected
• $S$ – Alarm sounds (output)

Boolean expression (derived in Section 4.1):

$S = (D\!\cdot\!A) + (F\!\cdot\!\overline{A})$

D	A	F	$\overline{A}$	$D\!\cdot\!A$	$F\!\cdot\!\overline{A}$	S
0	0	0	1	0	0	0
0	0	1	1	0	1	1
0	1	0	0	0	0	0
0	1	1	0	0	0	0
1	0	0	1	0	0	0
1	0	1	1	0	1	1
1	1	0	0	1	0	1
1	1	1	0	1	0	1

4. Deriving Logic Expressions

4.1 English → Boolean

1. Identify each distinct condition and give it a single‑letter variable.
2. Translate the condition into a Boolean clause using the gate definitions (AND = “both”, OR = “either”, NOT = “not”).
3. Combine the clauses with the appropriate operators; use parentheses to show the intended grouping.

4.2 From a Truth Table (Canonical Sum‑of‑Products)

1. Write the complete truth table, marking the rows where the output is 1.
2. For each “1” row, write a product (AND) term that is true only for that row:
   • Use the variable itself if the input is 1.
   • Use its complement (¬) if the input is 0.
3. Join all product terms with OR. The result is the **canonical sum‑of‑products (SOP)** expression.
4. Optionally simplify the SOP using Boolean algebra (Section 5) or Karnaugh maps (A‑Level).

4.3 From a Logic Circuit

1. Label every gate with its Boolean symbol.
2. Starting at the output, replace each gate by its algebraic form, working backwards toward the inputs.
3. Continue until the expression contains only the original input variables.

Worked Example – Deriving the Alarm Expression from the Circuit

• Top AND gate → $D\!\cdot\!A$
• Bottom AND gate → $F\!\cdot\!\overline{A}$ (the NOT gate provides $\overline{A}$)
• OR gate combines the two products → $(D\!\cdot\!A) + (F\!\cdot\!\overline{A})$

5. Constructing Logic Circuits

5.1 From a Problem Statement

1. Write the Boolean expression using the steps in Section 4.1.
2. Replace each operator by its corresponding gate symbol (AND → •, OR → +, NOT → ⊼, NAND/NOR → bubble, XOR → ⊕).
3. Draw the gates with two inputs (except NOT) and connect them exactly as the parentheses dictate.

5.2 From a Truth Table (Sum‑of‑Products Method)

1. Form the canonical SOP expression (Section 4.2).
2. Implement each product term with a two‑input AND gate; use a NOT gate for any complemented variable.
3. Combine all product terms with a single two‑input OR gate. If more than two product terms are needed, cascade additional OR gates.

5.3 From a Logic Expression

1. Identify the innermost parentheses – they become the first gates.
2. Proceed outward, adding a gate for each operator.
3. If an operator has more than two inputs, split it into several two‑input gates (cascading). For example, a three‑input AND $A\!\cdot\!B\!\cdot\!C$ is built as $(A\!\cdot\!B)\!\cdot\!C$ using two AND gates.

Worked Example – Light Control Circuit

• Variables: $M$ (motion), $D$ (dark), $S$ (manual switch), $T$ (timer active)
• Expression: $L = (M\!\cdot\!D) + (S\!\cdot\!\overline{T})$

6. Boolean Algebra – Simplifying and Minimising

6.1 Core Identities (useful for AS‑Level)

• Identity: $A + 0 = A,\; A\!\cdot\!1 = A$
• Null: $A + 1 = 1,\; A\!\cdot\!0 = 0$
• Idempotent: $A + A = A,\; A\!\cdot\!A = A$
• Complement: $A + \overline{A} = 1,\; A\!\cdot\!\overline{A} = 0$
• De Morgan: $\overline{A + B} = \overline{A}\!\cdot\!\overline{B}$, $\overline{A\!\cdot\!B} = \overline{A} + \overline{B}$
• Distributive: $A\!\cdot\!(B + C) = (A\!\cdot\!B) + (A\!\cdot\!C)$, $A + (B\!\cdot\!C) = (A + B)\!\cdot\!(A + C)$

6.2 Karnaugh Maps (A‑Level minimisation)

K‑maps provide a visual method for simplifying SOP or POS expressions.

• For two variables, the map is a 2 × 2 grid. Fill the cells with the output values from the truth table.
• Group adjacent 1’s in powers of two (1, 2, 4, 8 …). Each group yields a simplified product term.
• Combine the terms to obtain the minimal expression.

Example (2‑variable K‑map):

	B=0	B=1
A=0	0	1
A=1	1	1

Grouping the three 1’s gives the minimal expression $A + \overline{B}$.

6.3 Flip‑Flops (Sequential Logic – A‑Level)

While this unit focuses on combinational circuits, A‑Level students must recognise the two basic types of flip‑flops used in sequential circuits:

• SR (Set‑Reset) flip‑flop: inputs S and R control the stored state; the characteristic table is $Q_{next}=S+\overline{R}\!\cdot\!Q$.
• JK flip‑flop: a refinement of SR that eliminates the illegal “1‑1” condition; characteristic equation $Q_{next}=J\!\cdot\!\overline{Q}+ \overline{K}\!\cdot\!Q$.

In circuit diagrams they are shown with a rectangle containing the name (e.g., “SR”) and clock input symbols. Understanding these symbols is essential for Paper 3 questions on sequential circuit design.

7. A‑Level Extension Box

For students planning to sit the A‑Level Computer Science examination, the following topics extend the material covered above:

• Minimisation of Boolean expressions using Karnaugh maps (3‑ and 4‑variable maps).
• Design of combinational circuits from Karnaugh‑derived expressions.
• Sequential circuit design: SR, JK, D and T flip‑flops; timing diagrams; state tables.
• Implementation of arithmetic circuits (half‑adder, full‑adder, binary subtractor).
• Use of NAND‑only and NOR‑only implementations (gate‑level optimisation).

8. Common Pitfalls

• Applying NOT to the wrong variable (e.g., writing $F\!\cdot\!A$ instead of $F\!\cdot\!\overline{A}$).
• Confusing “either … or … but not both” with simple OR – it requires an XOR gate.
• Omitting parentheses; remember the precedence order NOT → AND → XOR → OR.
• Assuming a gate can have more than two inputs; always cascade two‑input gates.
• Mixing logical operators (used in Boolean expressions) with bit‑wise operators (used in programming). In the syllabus, “AND”, “OR”, “NOT” refer to logical operations on binary values.
• Neglecting the exclusive nature of XOR – it outputs 1 only when exactly one input is 1.

9. Summary Checklist

• Identify all input variables and give each a clear symbol.
• Translate English conditions into Boolean clauses using the correct gate definitions.
• Write the Boolean expression with explicit parentheses.
• Check operator precedence (NOT → AND → XOR → OR) or add parentheses to avoid ambiguity.
• Draw the corresponding two‑input circuit, cascading gates where necessary.
• Validate your work by constructing a truth table or testing a few input combinations.
• If required (A‑Level), simplify the expression using Boolean algebra, Karnaugh maps, or NAND/NOR‑only techniques.

10. Practice Questions

1. Expression construction: Write a Boolean expression for “The sprinkler activates if the temperature exceeds a threshold and it is not raining, or if the soil moisture is low.” (Define variables yourself.)
2. Truth table from expression: For $Y = \overline{A}\!\cdot\!B + A\!\cdot\!\overline{C}$, produce the complete truth table.
3. Derive expression from truth table: Given the table below, write the canonical sum‑of‑products expression and then simplify it using Boolean algebra.

A	B	C	Output
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

4. Circuit drawing: From the expression $Z = (P + Q)\!\cdot\!\overline{R}$, draw the two‑input logic circuit, showing all gates and connections.
5. A‑Level challenge (K‑map): Minimise the expression $F(A,B,C,D) = \sum m(1,3,4,6,9,11,12,14)$ using a 4‑variable Karnaugh map.