Cambridge O Level2210

Boolean logic

Computer Science 2210 Chapter Notes

What this chapter covers

Boolean logic
ShareWhatsAppPost
Boolean logic notes

Unable to load PDF

The notes viewer could not load. Please refresh the page.

Read online free. Download a watermarked copy with a free account.

Read the notes

The full Boolean logic notes as text: skim, search, and jump between subtopics.

~16 min read

In this chapter

  1. 1Logic Gates and Truth Tables
  2. 2Universal Gates: NAND and NOR
  3. 3The Exclusive OR (XOR) Gate
  4. 4From Expressions to Logic Circuits
  5. 5Analysing Circuits with Truth Tables
  6. 6From Truth Tables to Logic Expressions
  7. 7Applying Logic to Problem Statements

1. Logic Gates and Truth Tables

At the heart of every computer are millions of tiny electronic switches called logic gates. These gates process binary information, which only has two states: 1 (True, or ON) and 0 (False, or OFF). A logic gate takes one or more binary inputs and produces a single binary output based on a specific rule. We use a truth table to show every possible combination of inputs and the resulting output for a gate. The three most fundamental gates are NOT, AND, and OR.

X = NOT A (also written as X = Ā)

X = A AND B (also written as X = A.B)

X = A OR B (also written as X = A + B)

Key term

Truth Table: A diagram in table form that shows all possible input combinations and their corresponding output for a given logic system.

Examiner insight

Examiners expect you to have the shapes and truth tables for the basic gates memorised perfectly. Marks are often lost for drawing an AND gate shape for an OR gate.

Fun fact

The entire central processing unit (CPU) of a computer is essentially a vast, complex network of interconnected logic gates.

Worked example 16 marks

Complete the truth tables for a NOT gate, a 2-input AND gate, and a 2-input OR gate.

  1. 1

    Step 1: For the NOT gate, the output is the opposite of the single input. If A is 0, X is 1. If A is 1, X is 0.

  2. 2

    NOT Gate Truth Table:

    AX
    01
    10
  3. 3

    Step 2: For the AND gate, the output is 1 only if BOTH inputs A AND B are 1. Otherwise, the output is 0.

  4. 4

    AND Gate Truth Table:

    ABX
    000
    010
    100
    111
  5. 5

    Step 3: For the OR gate, the output is 1 if EITHER input A OR B (or both) is 1. It is only 0 if both inputs are 0.

  6. 6

    OR Gate Truth Table:

    ABX
    000
    011
    101
    111

Recap

  • Logic gates are the basic building blocks of digital circuits.
  • A NOT gate inverts its single input.
  • An AND gate outputs 1 only when all its inputs are 1.
  • An OR gate outputs 1 if at least one of its inputs is 1.
  • A truth table lists all possible input-output combinations.
  • Binary values are 1 (True/ON) and 0 (False/OFF).

Quick check

  1. What is the output of a 2-input AND gate if the inputs are 1 and 0?1 mark
  2. Draw the standard logic symbol for a 2-input OR gate.1 mark

2. Universal Gates: NAND and NOR

While AND, OR, and NOT are the basic gates, there are two other very important gates: NAND (Not AND) and NOR (Not OR). A NAND gate gives the opposite output of an AND gate. A NOR gate gives the opposite output of an OR gate. They are called 'universal gates' because you can create any other type of logic gate (AND, OR, NOT, etc.) by combining only NAND gates or only NOR gates. This property makes them very important in designing physical computer chips.

X = A NAND B (also written as X = NOT(A AND B) or X = A.B with a bar over it)

X = A NOR B (also written as X = NOT(A OR B) or X = A + B with a bar over it)

Key term

Universal Gate: A logic gate, such as NAND or NOR, from which any other logic gate or Boolean function can be constructed.

Common pitfall

A common mistake is to think NAND means 'NOT A and NOT B'. It actually means 'NOT (A AND B)', which is very different. Always perform the primary gate logic first, then invert the result.

Fun fact

The Apollo Guidance Computer, which took astronauts to the Moon, was built almost entirely from thousands of three-input NOR gates to simplify manufacturing and improve reliability.

Worked example 14 marks

Construct the truth tables for a 2-input NAND gate and a 2-input NOR gate.

  1. 1

    Step 1: To find the NAND truth table, first think of the AND gate outputs (0, 0, 0, 1) and then invert them.

  2. 2

    NAND Gate Truth Table:

    ABX
    001
    011
    101
    110
  3. 3

    Step 2: To find the NOR truth table, first think of the OR gate outputs (0, 1, 1, 1) and then invert them.

  4. 4

    NOR Gate Truth Table:

    ABX
    001
    010
    100
    110

Recap

  • A NAND gate is an AND gate followed by a NOT gate.
  • A NOR gate is an OR gate followed by a NOT gate.
  • NAND and NOR are known as universal gates.
  • The small circle on the output of a gate symbol always means 'NOT' or 'invert'.

Quick check

  1. What is the output of a 2-input NAND gate if both inputs are 1?1 mark
  2. What is the only input combination that gives an output of 1 for a NOR gate?1 mark

3. The Exclusive OR (XOR) Gate

The Exclusive OR, or XOR gate, is a special type of gate. It gives a 1 output only when the inputs are different from each other. If the inputs are the same (both 0 or both 1), the output is 0. This is different from a standard OR gate, which would give a 1 output if both inputs were 1. Think of it as 'one or the other, but not both'. XOR gates are very useful for tasks like checking if two binary numbers are different or in data encryption.

X = A XOR B (also written as X = A ⊕ B)

Key term

XOR (Exclusive OR): A logic gate that produces a true (1) output only when its inputs are different.

Examiner insight

Examiners often use XOR gates in more complex logic circuit problems to test a deeper understanding beyond the basic AND/OR/NOT gates.

Common pitfall

Confusing the XOR gate with the OR gate is the most frequent error. Remember the key difference: for an OR gate, 1 OR 1 is 1. For an XOR gate, 1 XOR 1 is 0.

Worked example 12 marks

A logic gate with two inputs, A and B, produces the output X shown in the truth table below. Identify the gate and draw its logic symbol.

ABX
000
011
101
110
  1. 1

    Step 1: Analyse the truth table. The output X is 1 only when the inputs A and B are different (rows 2 and 3).

  2. 2

    Step 2: When the inputs are the same (A=0, B=0 or A=1, B=1), the output is 0.

  3. 3

    Step 3: This behaviour matches the definition of an Exclusive OR (XOR) gate.

  4. 4

    Step 4: Draw the standard symbol for an XOR gate, which is like an OR gate with an extra curved line on the input side.

Recap

  • An XOR gate outputs 1 only when its inputs are different.
  • An XOR gate outputs 0 when its inputs are the same.
  • The XOR gate's behaviour can be summarised as 'the odd one out detector'.
  • Do not confuse XOR with OR; their outputs differ when both inputs are 1.

Quick check

  1. What is the output of a 2-input XOR gate if the inputs are 1 and 1?1 mark

4. From Expressions to Logic Circuits

A logic expression is an algebraic way of representing a logic circuit. For example, a circuit with inputs A and B going into an AND gate, with the result then OR'd with input C, can be written as X = (A AND B) OR C. To draw a logic circuit from an expression, you must follow the order of operations, just like in maths: Brackets first, then NOT, then AND, then OR. Work from the inside of the brackets outwards, drawing the gates for each operation and connecting them as you go.

Order of Operations: Brackets, NOT, AND, OR

Notation: A AND B = A.B

Notation: A OR B = A+B

Notation: NOT A = Ā

Key term

Logic Expression: A mathematical statement using Boolean operators (AND, OR, NOT) to represent the logic of a circuit or system.

Examiner insight

Examiners award marks for correctly identifying the order of operations. A common mistake is to draw the gates in the order they appear in the expression, ignoring brackets and precedence rules.

Fun fact

Boolean algebra, the maths behind logic expressions, was invented by George Boole in the 1840s, over 100 years before the first electronic computers were built.

Worked example 14 marks

Draw the logic circuit that corresponds to the Boolean expression X = (A OR B) AND (NOT C).

  1. 1

    Step 1: Identify the inputs: A, B, and C.

  2. 2

    Step 2: Address the operations in brackets first. The expression (A OR B) requires an OR gate with inputs A and B.

  3. 3

    Step 3: Address the NOT operation. The expression (NOT C) requires a NOT gate with input C.

  4. 4

    Step 4: Identify the final operation. The AND operator connects the results of the first two parts. Draw an AND gate.

  5. 5

    Step 5: Connect the output of the (A OR B) gate to one input of the final AND gate. Connect the output of the (NOT C) gate to the other input of the final AND gate.

  6. 6

    Step 6: Label the final output as X.

Recap

  • Logic expressions are an algebraic way to describe logic circuits.
  • The order of operations is Brackets, NOT, AND, OR.
  • When drawing a circuit from an expression, start with the operations inside brackets.
  • The final operation in the expression corresponds to the final gate in the circuit.

Quick check

  1. In the expression P = Q AND R OR S, which logical operation is performed last?1 mark

5. Analysing Circuits with Truth Tables

To understand exactly what a complex logic circuit does, we can create a truth table for it. This process systematically tests every possible input combination. The key is to be methodical. First, list all the inputs (e.g., A, B, C). The number of rows you need is 2^n, where n is the number of inputs. Then, create extra 'intermediate' columns for the output of each individual gate as you work through the circuit. Finally, use these intermediate values to calculate the final output column.

Number of rows in a truth table = 2^n (where n is the number of inputs)

Key term

Intermediate Value: A temporary output from one part of a logic circuit that serves as an input to another part within the same circuit.

Examiner insight

Examiners look for a clear, logical layout in truth tables. Clearly labelled intermediate columns are crucial for earning full marks, even if your final answer is correct.

Common pitfall

Forgetting to include columns for intermediate steps in the truth table is a huge risk. It makes it very easy to make calculation errors and you will lose marks for not showing your working.

Worked example 15 marks

Produce a truth table for the logic circuit represented by the expression X = A AND (B OR NOT C).

  1. 1

    Step 1: Identify the number of inputs. There are 3 inputs (A, B, C), so we need 2^3 = 8 rows in our table.

  2. 2

    Step 2: Set up the table with columns for the inputs A, B, and C, and list all 8 possible binary combinations.

  3. 3

    Step 3: Create an intermediate column for the innermost operation, 'NOT C'. Fill this column by inverting the values in the C column.

  4. 4

    Step 4: Create another intermediate column for the bracketed operation, 'B OR NOT C'. Use the B and 'NOT C' columns to calculate these values.

  5. 5

    Step 5: Create the final column for X. This is 'A AND (result from step 4)'. Use the A column and the 'B OR NOT C' column to calculate the final output.

  6. 6

    Completed Truth Table:

    ABCNOT CB OR NOT CX = A AND (B OR NOT C)
    000110
    001000
    010110
    011010
    100111
    101000
    110111
    111011

Recap

  • For a circuit with 'n' inputs, its truth table must have 2^n rows.
  • Use intermediate columns to show the output of each individual gate.
  • Work methodically from the inputs through to the final output.
  • Double-check your work; a single error in an intermediate column will lead to an incorrect final result.

Quick check

  1. How many rows would a truth table for a logic circuit with 4 inputs have?1 mark

6. From Truth Tables to Logic Expressions

You can also work backwards, creating a logic expression and circuit from a completed truth table. The standard method is to focus only on the rows where the final output is 1. For each of these rows, you write an AND expression that is true only for that specific combination of inputs. If an input in that row is 0, you use a NOT on it. Once you have an AND expression for every row that results in a 1, you simply join all these expressions together with OR gates. This is called the 'sum-of-products' method.

Key term

Sum-of-Products: A method of creating a logic expression from a truth table by OR-ing together all the AND terms that correspond to a '1' output.

Examiner insight

Marks are often awarded for correctly deriving the individual AND expressions (the 'products') for each '1' output, before you combine them with ORs (the 'sum').

Worked example 14 marks

A system has three inputs, A, B, C, and one output, X. The truth table is shown below. Derive the logic expression for X.

ABCX
0000
0010
0101
0110
1000
1011
1100
1111
  1. 1

    Step 1: Identify all rows where the output X is 1. These are rows 3, 6, and 8.

  2. 2

    Step 2: For the first '1' output (row 3): A=0, B=1, C=0. To make this combination result in a 1 using AND, we need (NOT A) AND B AND (NOT C).

  3. 3

    Step 3: For the second '1' output (row 6): A=1, B=0, C=1. The AND expression is A AND (NOT B) AND C.

  4. 4

    Step 4: For the third '1' output (row 8): A=1, B=1, C=1. The AND expression is A AND B AND C.

  5. 5

    Step 5: Combine these three AND expressions with OR operators to form the final logic expression.

  6. 6

    Final Expression: X = (NOT A AND B AND NOT C) OR (A AND NOT B AND C) OR (A AND B AND C)

Recap

  • To derive an expression from a truth table, focus on the rows where the output is 1.
  • For each row with a '1' output, write an AND expression for that specific input combination.
  • If an input is 0 in that row, use a NOT on that input in your AND expression.
  • Combine all the AND expressions together using ORs.

Quick check

  1. A row in a truth table with output 1 has inputs A=1, B=0. What is the corresponding AND expression?1 mark

7. Applying Logic to Problem Statements

Boolean logic is used to design and control real-world systems. A 'problem statement' is a description of a system in plain English. Your task is to translate this description into a logic system. The process is:

  1. Identify the inputs (conditions that can be true or false) and the final output.
  2. Assign a letter (e.g., A, B, C) to represent each input.
  3. Write a logic expression that captures the rules described in the statement. Look for keywords: 'and' suggests an AND gate, 'or' suggests an OR gate, 'not' or 'unless' suggests a NOT gate.
  4. From the expression, you can then draw the logic circuit and/or create the truth table.

Key term

Problem Statement: A description in natural language of a scenario or set of conditions that can be modelled using Boolean logic.

Examiner insight

Examiners want to see that you can systematically break down a word problem. Always clearly state which letter corresponds to which input condition before you write the expression.

Worked example 15 marks

A greenhouse heating system (H) should switch on if the temperature (T) is low AND it is night-time (N). It should also switch on if the 'manual override' switch (M) is activated, regardless of other conditions. Write the logic expression and draw the logic circuit for H.

  1. 1

    Step 1: Identify inputs and output. Inputs are T (Temperature low), N (Night-time), M (Manual override). The output is H (Heating on). We assume 1 means 'true' for all (e.g., T=1 means temp is low).

  2. 2

    Step 2: Translate the first condition: 'temperature (T) is low AND it is night-time (N)'. This becomes (T AND N).

  3. 3

    Step 3: Translate the second condition: '...OR if the 'manual override' switch (M) is activated'. This becomes OR M.

  4. 4

    Step 4: Combine the conditions to form the full expression: H = (T AND N) OR M.

  5. 5

    Step 5: Draw the circuit. Create an AND gate for T and N. Take the output of this AND gate and the input M, and feed them into a final OR gate. The output of the OR gate is H.

Recap

  • First, identify all the inputs and the single output from the problem description.
  • Assign a capital letter to each input and the output.
  • Translate keywords like 'and', 'or', 'but not' into logic operators.
  • Build the logic expression based on the rules in the statement.
  • Use the final expression to draw the circuit or create the truth table.

Quick check

  1. A security light (L) turns on if motion is detected (M) AND it is dark (D). Write the logic expression for L.1 mark

End-of-chapter exercise

Test yourself on the whole chapter. Work through these before moving on.

  1. Draw the standard logic gate symbols for a 2-input NOR gate and a 2-input XOR gate.2 marks
  2. Write the logic expression for the following statement: 'A warning light X is on if the pressure P is high AND the temperature T is high, OR if a test button B is pressed.'2 marks
  3. A logic circuit has 4 inputs. How many rows would be required in its truth table?1 mark
  4. Draw the logic circuit for the expression F = NOT(A AND B) OR C.4 marks
  5. Complete the truth table for the logic expression X = (A XOR B) AND C. You must show columns for any intermediate values.5 marks
  6. The following truth table describes a logic system with inputs P, Q and output R. Write the logic expression for R.3 marks
  7. A car has a warning system. A buzzer (B) sounds if the driver's seatbelt (D) is NOT fastened when the engine (E) is on. The buzzer also sounds if the headlights (H) are left on when the engine (E) is off. Produce the logic expression for B.4 marks
  8. For the logic circuit shown, write the logic expression for the output X and then create the corresponding truth table.6 marks
  9. A logic gate is described by the following truth table. Identify the single gate. | A | B | X | |---|---|---| | 0 | 0 | 1 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 0 |1 mark
  10. From the logic expression derived in question 7, B = (NOT D AND E) OR (H AND NOT E), draw the corresponding logic circuit diagram.5 marks

Go deeper

Practise and revise with member-only material for this chapter.

Workbook

Exam-style practice questions with full worked solutions.

Unlock with a plan

Chapter at a Glance

A single-page summary of every key idea for fast revision.

Unlock with a plan

Free notes are just the start.

Unlock every Workbook and Chapter at a Glance, and generate your own worksheets and predicted papers.

Explore plans

Related chapters

Number systemsTypes and methods of data transmissionComputer architectureTypes of software and interruptsThe internet and the world wide webAutomated systems