Understand and define the functions of: NOT, AND, OR, NAND, NOR and XOR (EOR) gates

3.2 Logic Gates and Logic Circuits

Learning Objective (Syllabus 3.2)

Students will be able to understand and define the functions of the six basic logic gates – NOT, AND, OR, NAND, NOR and XOR (EOR) – and to apply this knowledge by:

• drawing and recognising the standard IEC gate symbols,
• constructing truth tables from Boolean expressions and from circuit diagrams,
• converting between Boolean expressions and circuit diagrams (SOP, POS, NAND‑only, NOR‑only),
• designing simple circuits using SOP/POS and using only NAND or only NOR gates, and
• interpreting multi‑input (3‑ or 4‑input) gates.

1. Gate Definitions, Symbols & Multi‑Input Forms

Gate	Standard IEC Symbol	Typical Boolean Form	Multi‑input Note
NOT (Inverter)		\(\overline{A}\)	always a single input
AND		\(A\cdot B\) (or \(AB\))	2‑, 3‑ or 4‑input versions are permitted; output = 1 only when **all** inputs are 1
OR		\(A+B\)	2‑, 3‑ or 4‑input versions are permitted; output = 1 when **any** input is 1
NAND		\(\overline{A\cdot B}\)	same fan‑in as AND; output = 0 only when **all** inputs are 1
NOR		\(\overline{A+B}\)	same fan‑in as OR; output = 1 only when **all** inputs are 0
XOR (EOR – Exclusive OR)		\(A\oplus B\)	normally shown as a 2‑input gate; for 3‑ or 4‑input versions the output is 1 when an **odd** number of inputs are 1

Key Symbol Features to Recognise in Exam Papers

• Bubble (circle) on the output side – indicates logical NOT.
• Triangle alone – NOT (inverter) gate.
• Flat back – AND gate.
• Curved back – OR gate.
• Extra curved line on the input side – XOR/EOR.
• Basic shape + bubble – NAND (AND + bubble) or NOR (OR + bubble).

2. Truth‑Table Construction

2.1 Standard 2‑Input Truth Tables (Reference)

NOT Gate (1‑input)

A	\(\overline{A}\)
0	1
1	0

AND Gate (2‑input)

A	B	A·B
0	0	0
0	1	0
1	0	0
1	1	1

OR Gate (2‑input)

A	B	A+B
0	0	0
0	1	1
1	0	1
1	1	1

NAND Gate (2‑input)

A	B	\(\overline{A·B}\)
0	0	1
0	1	1
1	0	1
1	1	0

NOR Gate (2‑input)

A	B	\(\overline{A+B}\)
0	0	1
0	1	0
1	0	0
1	1	0

XOR (EOR) Gate (2‑input)

A	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

2.2 Multi‑Input Truth Tables (3‑ and 4‑input)

AND Gate – 3‑input

A	B	C	A·B·C
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	1

… (remaining 11 rows omitted for brevity) …

OR Gate – 4‑input

A	B	C	D	A+B+C+D
0	0	0	0	0
0	0	0	1	1
0	0	1	0	1
0	0	1	1	1
0	1	0	0	1
1	1	1	1	1

XOR – 3‑input (odd‑parity)

A	B	C	A⊕B⊕C
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

2.3 Building a Truth Table from a Boolean Expression (AO2)

Worksheet – Step‑by‑Step

1. List every distinct input variable (e.g. \(A,B,C\)).
2. Create a column for each variable and a final column for the whole expression.
3. Write all possible binary combinations – for \(n\) variables there are \(2^{n}\) rows.
4. Evaluate the expression row‑by‑row, using the gate tables as a reference.

Example: Derive the truth table for \(F = \overline{A}\,B + C\).

A	B	C	\(\overline{A}\)	\(\overline{A}\,B\)	F\)
0	0	0	1	0	0
0	0	1	1	0	1
0	1	0	1	1	1
0	1	1	1	1	1
1	0	0	0	0	0
1	0	1	0	0	1
1	1	0	0	0	0
1	1	1	0	0	1

2.4 Building a Truth Table from a Circuit Diagram

1. Label each gate with its Boolean operation.
2. Identify intermediate signals (e.g. \(D\), \(E\)) and write their algebraic forms.
3. Proceed from the left‑most (or bottom‑most) inputs towards the output, evaluating each intermediate column.

Worked Example (3‑input circuit):

• Inputs: \(A, B, C\).
• Gate 1: 3‑input NAND → \(D = \overline{A\cdot B\cdot C}\).
• Gate 2: NOT of \(D\) → \(E = \overline{D} = A\cdot B\cdot C\).
• Gate 3: XOR of \(E\) with \(A\) → \(F = E\oplus A\).

The truth table is produced by adding columns for \(D\), \(E\) and finally \(F\) using the rows for all eight combinations of \(A,B,C\).

3. Converting Between Boolean Expressions and Circuit Diagrams

3.1 Expression → Circuit (SOP)

1. Write the expression in **sum‑of‑products** (each product = AND, the sum = OR).
2. For every product term:
   • Place an AND gate.
   • Insert NOT gates on any complemented literals.
3. Feed all AND outputs into a single OR gate.
4. Optional: simplify first (Boolean algebra or K‑map) to reduce gate count.

3.2 Expression → Circuit (POS)

1. Rewrite the function in **product‑of‑sums** form.
2. Each sum term becomes an OR gate (with NOTs on complemented literals).
3. All OR outputs are combined with a single AND gate.

3.3 Circuit → Expression (Reading a Diagram)

1. Start at the output gate and work backwards.
2. Replace each gate by its Boolean operator, adding brackets where necessary.
3. Continue until only primary inputs remain.

3.4 NAND‑Only Implementation (Functional Completeness)

Key identities:

• \(\overline{X}=X\;{\rm NAND}\;X\)
• \(X\cdot Y = \overline{\,X\;{\rm NAND}\;Y\,}\) → NAND followed by a NOT.
• \(X+Y = (\,\overline{X}\;{\rm NAND}\;\overline{Y}\,)\) → two NAND‑based NOTs feeding a NAND.

Example – Convert \(F = A\overline{B}+ \overline{C}\) to NAND‑only:

1. \(\overline{B}=B\;{\rm NAND}\;B\) and \(\overline{C}=C\;{\rm NAND}\;C\).
2. First product: \(A\overline{B}= \overline{\,A\;{\rm NAND}\;(\overline{B})\,}\) → NAND then NOT (another NAND with tied inputs).
3. Second product is simply \(\overline{C}\) (already a NAND‑based NOT).
4. OR of the two products: use the NAND‑OR identity → NAND the two NOT‑outputs and then NAND the result with itself.

3.5 NOR‑Only Implementation (Dual of NAND)

Key identities:

• \(\overline{X}=X\;{\rm NOR}\;X\)
• \(X+Y = \overline{\,X\;{\rm NOR}\;Y\,}\) → NOR followed by a NOT.
• \(X\cdot Y = (\,\overline{X}\;{\rm NOR}\;\overline{Y}\,)\) → two NOR‑based NOTs feeding a NOR.

Example – Convert \(F = (A+B)\cdot\overline{C}\) to NOR‑only follows the same pattern, using the identities above.

4. Designing Simple Circuits (AO2 + AO3)

Exam‑style Problem

Design a circuit that implements the Boolean function \(F = (A \land \overline{B}) \lor (\overline{A} \land C)\). Show:

• the Boolean expression in SOP form,
• the complete truth table,
• a neat circuit diagram using only AND, OR and NOT gates, and
• an alternative implementation using **only NAND gates**.

Step 1 – SOP Form (already given)

\[ F = A\overline{B} + \overline{A}C \]

Step 2 – Truth Table

A	B	C	\(\overline{B}\)	\(\overline{A}\)	A\overline{B}	\(\overline{A}C\)	F
0	0	0	1	1	0	0	0
0	0	1	1	1	0	1	1
0	1	0	0	1	0	0	0
0	1	1	0	1	0	1	1
1	0	0	1	0	1	0	1
1	0	1	1	0	1	0	1
1	1	0	0	0	0	0	0
1	1	1	0	0	0	0	0

Step 3 – Circuit Using AND, OR, NOT

1. Two NOT gates produce \(\overline{B}\) and \(\overline{A}\).
2. Two AND gates: one for \(A\overline{B}\), the other for \(\overline{A}C\).
3. An OR gate combines the two AND outputs to give \(F\).

Diagram (hand‑drawn in the exam booklet) – the connections are:

• Input A → AND₁ (direct) and → NOT₁ → AND₂.
• Input B → NOT₂ → AND₁.
• Input C → AND₂ (direct).
• Outputs of AND₁ and AND₂ → OR → F.

Step 4 – NAND‑Only Implementation

1. Generate the required NOTs with NANDs: \(\overline{B}=B\;{\rm NAND}\;B\), \(\overline{A}=A\;{\rm NAND}\;A\).
2. Form the two products:
   • \(A\overline{B}= \overline{\,A\;{\rm NAND}\;(\overline{B})\,}\) → NAND then NOT (another NAND with tied inputs).
   • \(\overline{A}C = \overline{\,(\overline{A})\;{\rm NAND}\;C\,}\) → same pattern.
3. OR the two products using the NAND‑OR identity:
   • First NAND the two product‑outputs → \(P = (A\overline{B})\;{\rm NAND}\;(\overline{A}C)\).
   • Finally, NOT the result: \(F = P\;{\rm NAND}\;P\).

The final diagram uses only NAND symbols; the total gate count is eight NANDs (two for the NOTs, two for the product inversions, one for the product‑NAND, and one final NOT‑NAND).

AO3 Checklist – What Examiners Look For

• Correct SOP (or POS) form is shown.
• Truth table contains all \(2^{n}\) rows and matches the expression.
• Circuit diagram is neat, labelled, and uses the required gate set.
• For NAND‑only (or NOR‑only) designs, every NOT is realised by a gate with both inputs tied together.
• Brief justification is given (e.g., “NAND is functionally complete, therefore any Boolean function can be built using only NAND gates”).
• Gate count is mentioned – useful for the “efficiency” part of AO3.

5. Summary Table – Multi‑Input Gate Behaviour

Gate	Output = 1 when…	Output = 0 when…
AND (n‑input)	All n inputs are 1	At least one input is 0
OR (n‑input)	At least one input is 1	All n inputs are 0
NAND (n‑input)	Any input is 0 (i.e., not all 1)	All n inputs are 1
NOR (n‑input)	All n inputs are 0	Any input is 1
XOR (n‑input, odd‑parity)	An odd number of inputs are 1	An even number of inputs are 1 (including zero)

---

These notes now cover every requirement of Cambridge AS & A‑Level Computer Science Syllabus 3.2, provide clear multi‑input information, include step‑by‑step worksheets, demonstrate both SOP/POS and NAND‑only/NOR‑only conversions, and give a concrete AO3 checklist for exam preparation.