Create and complete truth tables from logic expressions or circuits

Boolean Logic (Topic 10 – Cambridge IGCSE 0478)

1. Quick‑Reference Symbol Cheat‑Sheet

Gate	Algebraic Symbol	Gate Symbol	Meaning
AND	\(A\cdot B\)		True only when both inputs are 1
OR	\(A + B\)		True when at least one input is 1
NOT	\(\overline{A}\)		Inverts the input (1→0, 0→1)
XOR	\(A\oplus B\)		True when exactly one input is 1
NAND	\(\overline{A\cdot B}\)		True except when both inputs are 1
NOR	\(\overline{A + B}\)		True only when both inputs are 0

2. Truth Tables for the Standard 2‑Input Gates

Gate	Inputs	Output
AND	00, 01, 10, 11	0, 0, 0, 1
OR	00, 01, 10, 11	0, 1, 1, 1
NOT (single input)	0, 1	1, 0
XOR	00, 01, 10, 11	0, 1, 1, 0
NAND	00, 01, 10, 11	1, 1, 1, 0
NOR	00, 01, 10, 11	1, 0, 0, 0

3. Operator Precedence (Order of Evaluation)

1. Parentheses ( )
2. NOT (\(\overline{\;}\) or ¬)
3. AND (·) and NAND
4. OR (+) and NOR
5. XOR (⊕)

When two operators have the same precedence, evaluate from left to right.

4. Maximum Gate‑Input Restriction

The syllabus limits every gate to **two inputs** (the NOT gate has one). If a circuit needs more than two inputs, combine them using additional two‑input gates.

5. Building a Truth Table from a Boolean Expression

1. List the distinct variables. Write them alphabetically (e.g., A, B, C).
2. Generate all possible input combinations. With n variables there are \(2^{n}\) rows. Use binary counting (00…0, 00…1, … 11…1).
3. Evaluate the expression row‑by‑row. Follow the precedence rules. It is often helpful to add intermediate columns for sub‑expressions.

Example 1 – Expression \((A\cdot B)+\overline{C}\)

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

6. Building a Truth Table from a Logic Circuit

1. List the input variables alphabetically.
2. Give each gate a short name (e.g., D = A·B).
3. Create a column for the output of **every** gate before the final output.
4. Fill the table row‑by‑row using the same binary‑counting order as for expressions.

Example 2 – Circuit with Three Gates

Inputs: A, B, C

• Gate 1: AND \(D = A\cdot B\)
• Gate 2: NOT \(E = \overline{C}\)
• Gate 3: OR \(F = D + E\) (final output)

A	B	C	D = A·B	E = \(\overline{C}\)	F = D+E
0	0	0	0	1	1
0	0	1	0	0	0
0	1	0	0	1	1
0	1	1	0	0	0
1	0	0	0	1	1
1	0	1	0	0	0
1	1	0	1	1	1
1	1	1	1	0	1

7. Designing a Logic Circuit from a Truth Table

1. Identify every row where the output is 1 – these are the **minterms**.
2. Write each minterm as an AND of the input variables, using NOT for any input that is 0 in that row.
3. Combine all minterms with OR gates. If an OR (or AND) would need more than two inputs, split it into a chain of two‑input gates.

Example 3 – From Truth Table to Circuit

A	B	C	Y
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	0

Rows 2, 3 and 5 give the minterms:

\[ \begin{aligned} m_2 &: \overline{A}\,\overline{B}\,C \\ m_3 &: \overline{A}\,B\,\overline{C} \\ m_5 &: A\,\overline{B}\,\overline{C} \end{aligned} \]

Combined:

\[ Y = \overline{A}\,\overline{B}\,C \;+\; \overline{A}\,B\,\overline{C} \;+\; A\,\overline{B}\,\overline{C} \]

The circuit uses three two‑input AND gates feeding a three‑input OR, which is implemented as two two‑input OR gates (to respect the two‑input rule).

8. Designing a Logic Circuit from a Problem Statement (Real‑World Scenario)

Problem: “A home‑security alarm should sound when motion is detected AND the door is open OR when smoke is detected.”

1. Identify the required inputs:
   
   • M = motion detector (1 = motion)
   • D = door sensor (1 = open)
   • S = smoke detector (1 = smoke)
2. Translate the English statement into a Boolean expression using the standard symbols:
   \[ \text{Alarm} = (M\cdot D) + S \]
3. Check the expression against the two‑input rule – it already uses only two‑input gates.
4. Draw the circuit:
   • Gate 1 (AND): \(P = M\cdot D\)
   • Gate 2 (OR): \(\text{Alarm} = P + S\)
   (Both gates are two‑input, so no extra splitting is required.)

9. De Morgan’s Laws (Simplification & Circuit Conversion)

• \(\displaystyle\overline{A + B} = \overline{A}\cdot\overline{B}\) (NOR → AND of NOTs)
• \(\displaystyle\overline{A\cdot B} = \overline{A} + \overline{B}\) (NAND → OR of NOTs)

These identities let you replace a NOT of a compound expression with a combination of opposite gates, which is useful when the exam limits you to NAND or NOR gates only.

Example: \(\overline{(A + B)}\cdot(A\oplus B)\) becomes \((\overline{A}\cdot\overline{B})\cdot(A\oplus B)\) using the first law.

10. Practice Questions

1. Complete the truth table for \(\overline{(A + B)}\cdot(A\oplus B)\). Required columns: A, B, \(A+B\), \(\overline{(A+B)}\), \(A\oplus B\), Result.
2. The circuit below has inputs X, Y.
   • Gate A: NAND \(P = \overline{X\cdot Y}\)
   • Gate B: NOT \(Q = \overline{X}\)
   • Gate C: NOR \(Z = \overline{P + Q}\) (final output)
   Construct a truth table with columns X, Y, P, Q, Z.
3. Explain why the expression \(A\cdot\overline{A}\) always yields 0 and relate this to the logical concept of a contradiction.

11. Answers & Marking Guidance (for teachers)

1. A	B	A+B	\(\overline{(A+B)}\)	A⊕B	Result
   0	0	0	1	0	0
   0	1	1	0	1	0
   1	0	1	0	1	0
   1	1	1	0	0	0

   All rows give 0 → the expression is a contradiction.

2. X	Y	P = \(\overline{X\cdot Y}\)	Q = \(\overline{X}\)	Z = \(\overline{P+Q}\)
   0	0	1	1	0
   0	1	1	1	0
   1	0	1	0	0
   1	1	0	0	1

3. \(A\cdot\overline{A}\) requires A to be 1 **and** 0 at the same time – an impossibility. Therefore the expression always evaluates to 0. In logical terminology this is a contradiction, i.e. a statement that can never be true.

12. Tips for Exam Success

• Always list variables alphabetically in the header row.
• Generate rows by binary counting (00, 01, 10, 11…) – never omit a combination.
• When a circuit has several gates, create an intermediate column for **each** gate before the final output.
• Cross‑check every intermediate result against the appropriate gate’s truth table.
• Respect the two‑input limit: split any larger gate into a chain of two‑input gates.
• If you need to sketch a circuit quickly, keep the standard symbols from the cheat‑sheet handy.

Reference: Cambridge IGCSE Computer Science (0478) – Topic 10: Boolean Logic, Specification 2024.