Home Notes Papers

Boolean logic

Paper 2

This section is examined in Paper 2.

Fundamental Logic Gates
Boolean logic uses binary values: 0 (False/Off) and 1 (True/On). The basic building blocks are logic gates. Each gate performs a specific logical operation on one or more inputs to produce a single output.
Truth Table (Inputs A, B → Output Z)
0,0→0 | 0,1→0 | 1,0→0 | 1,1→1
0,0→0 | 0,1→1 | 1,0→1 | 1,1→1
0→1 | 1→0
0,0→1 | 0,1→1 | 1,0→1 | 1,1→0
0,0→1 | 0,1→0 | 1,0→0 | 1,1→0
0,0→0 | 0,1→1 | 1,0→1 | 1,1→0
Understanding the 'Bubble': In logic gate symbols, a small circle at the output is called a bubble. It represents a NOT operation (inversion). For example, a NAND gate is an AND gate followed by a NOT gate. The bubble inverts the result of the AND operation.
Logic Expression Notation
Cambridge accepts multiple notations for Boolean expressions. You must be consistent with the notation used in the question paper or your own work.

  1. Text-based: Uses words like AND, OR, NOT. Example: A AND B
  2. Symbolic: Uses symbols like ∧ (AND), ∨ (OR), ¬ or ̅ (NOT). Example: A ∧ B or A·B
  3. Overline: A bar over the variable indicates NOT. Example: Ā or \bar{A}

Key Rule: When writing expressions, use parentheses ( ) to define the order of operations, just like in mathematics.

De Morgan's Laws
De Morgan's Laws are critical for simplifying complex Boolean expressions and converting between gate types. They describe how to distribute a NOT operation across AND/OR gates.

Law 1: The negation of an AND operation is equivalent to the OR of the negations.
\overline{A \cdot B} = \bar{A} + \bar{B}
(NOT (A AND B) is the same as (NOT A) OR (NOT B))

Law 2: The negation of an OR operation is equivalent to the AND of the negations.
\overline{A + B} = \bar{A} \cdot \bar{B}
(NOT (A OR B) is the same as (NOT A) AND (NOT B))

Why this matters: These laws allow you to replace a complex gate combination with a simpler one, or to convert a circuit into one using only NAND gates (which are universal).

Deriving Logic Expressions from Circuits
Question: Write the logic expression for a circuit where:

  1. Inputs A and B go into an AND gate.
  2. Input C goes into a NOT gate.
  3. The outputs of step 1 and step 2 go into an OR gate.

Step-by-step Derivation:

  1. Identify the first layer: A AND B → (A AND B)
  2. Identify the second layer: NOT C → (NOT C) or (\bar{C})
  3. Identify the final layer: The outputs of 1 and 2 go into an OR gate.

Final Expression:
(A \text{ AND } B) \text{ OR } (\text{NOT } C)
Or symbolically:
(A \cdot B) + \bar{C}

Complex Example: Derive the expression for Z = (\text{NOT } A \text{ OR } B) \text{ AND } (B \text{ XOR } C).

  1. Break it down by brackets:
    • Part 1: NOT A OR B → (\bar{A} + B)
    • Part 2: B XOR C → (B \oplus C)
  2. Combine with the central operator (AND):
    Z = (\bar{A} + B) \cdot (B \oplus C)
Completing a Truth Table

Question: Complete the truth table for Z = A \text{ NAND } (B \text{ OR } C).

Strategy: Work from left to right, creating intermediate columns if necessary.

  1. Inputs: List all 8 combinations of A, B, C (000 to 111).
  2. Intermediate Column 1 (B \text{ OR } C):
    • If B=0, C=0 → Output 0
    • Otherwise → Output 1
  3. Final Column (A NAND Intermediate):
    • Recall: NAND is 0 only if BOTH inputs are 1.
    • Input A and Intermediate must both be 1 for Z to be 0.
A B C B OR C A NAND (B OR C)
0 0 0 0 1
0 0 1 1 1
0 1 0 1 1
0 1 1 1 1
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 0
⚠︎ Drawing Logic Gates
Error: Drawing gates with indistinct shapes (e.g., making an AND gate look like a rectangle, or forgetting the bubble on NAND/NOR).

Correct Understanding: Cambridge examiners award marks for distinctive shape.

  • The AND gate must have a flat back and curved front.
  • The OR gate must have a curved back and pointed front.
  • The NOT gate is a triangle with a circle (bubble) at the tip.
  • NAND/NOR/XOR must clearly show the base gate plus the distinguishing feature (extra line for XOR, bubble for NAND/NOR).

Why this matters: If the gate shape is ambiguous, the examiner cannot verify your logic. Always draw large, clear symbols.

⚠︎ Truth Table Output Errors

Error: The final output column is the exact opposite of the correct answer (all 0s become 1s and vice versa).

Correct Understanding: This usually happens when you forget a NOT operation or misinterpret a NAND/NOR gate.

  • Remember: NAND is the inverse of AND. If AND gives 1, NAND gives 0.
  • Double-check the last gate in your circuit. If it ends in a bubble (NOT), invert your previous result.
Writing Logic Expressions
Context: When asked to write a logic expression from a circuit diagram.

Examiner Acceptance: Examiners accept expressions that clearly show the order of operations. Use parentheses ( ) to group inputs for each gate. For example, (A AND B) OR C is clearer than A AND B OR C because it removes ambiguity about whether A is ANDed with (B OR C) or (A AND B).

Reasoning: This directly addresses the requirement for unambiguous logical structure. Without parentheses, the precedence of operations might be misinterpreted.

Example: For a circuit where A and B are ANDed, then that result is ORed with C, write: (A AND B) OR C. Do not write A AND B OR C unless you are certain of standard precedence rules, as it risks ambiguity.

Using De Morgan's Laws

Context: When asked to simplify an expression or convert a circuit to use only NAND gates.

Examiner Acceptance: Examiners look for the correct application of the rule: 'Break the bar, change the sign.'

  • If you have \overline{A \cdot B}, break the bar over A and B, and change AND (\cdot) to OR (+). Result: \bar{A} + \bar{B}.
  • If you have \overline{A + B}, break the bar over A and B, and change OR (+) to AND (\cdot). Result: \bar{A} \cdot \bar{B}.

Reasoning: This demonstrates understanding of logical equivalence. Simply stating the law without applying it correctly will not gain marks.

Example: Simplify \overline{(A \text{ OR } B) \text{ AND } C}.

  1. Apply De Morgan's to the outer AND: \overline{(A \text{ OR } B)} + \bar{C}
  2. Apply De Morgan's to the inner OR: (\bar{A} \cdot \bar{B}) + \bar{C}
Past Paper Style Questions
Q:
Draw a logic circuit for the expression Z = (\text{NOT } A \text{ OR } B) \text{ AND } (B \text{ XOR } C).
A:

The circuit must contain:

  1. A NOT gate with input A.
  2. An OR gate with inputs from step 1 and input B.
  3. An XOR gate with inputs B and C.
  4. An AND gate taking the outputs from step 2 and step 3 as its inputs.
  5. All connections must be correct.
Q:
Write the logic expression for a circuit where X is the output of an AND gate (inputs A, B), Y is the output of a NOT gate (input C), and Z is the output of an OR gate (inputs X, Y).
A:
Z = (A \text{ AND } B) \text{ OR } (\text{NOT } C)
Or symbolically: Z = (A \cdot B) + \bar{C}
Q:
Complete the truth table for Z = A \text{ NOR } B.
A:
A B Z
0 0 1
0 1 0
1 0 0
1 1 0

(Note: NOR is 1 only when both inputs are 0)

Q:
Simplify the expression \overline{A \cdot B} using De Morgan's Laws.
A:
\bar{A} + \bar{B}
(Break the bar, change AND to OR)
Beta v0.7.8 Free while we're in beta — it transitions to paid post launch. Thank you for supporting us at this stage!