Cambridge IGCSE0478

Boolean logic

Computer Science 0478 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.

~14 min read

In this chapter

  1. 1The Building Blocks: Basic Logic Gates
  2. 2Universal and Exclusive Gates
  3. 3Combining Gates: Logic Circuits and Expressions
  4. 4Testing Circuits: Creating Truth Tables
  5. 5Reverse Engineering: Truth Tables to Expressions
  6. 6From Problem to Solution

1. The Building Blocks: Basic Logic Gates

At the heart of every computer are millions of tiny electronic switches called logic gates. These are the fundamental building blocks of all digital circuits. A logic gate takes one or more binary inputs (represented as 0 for 'off' or 'low voltage', and 1 for 'on' or 'high voltage') and produces a single binary output. There are three fundamental gates you must know: AND, OR, and NOT. Each performs a simple logical function.

X = A AND B (Notation: A . B)

X = A OR B (Notation: A + B)

X = NOT A (Notation: ¬A or Ā)

Key term

Logic Gate: A basic building block of a digital circuit that performs a logical operation on one or more binary inputs to produce a single binary output.

Common pitfall

Mixing up the symbols for the AND gate (D-shape) and the OR gate (curved input side). Remember 'AND' has a 'D' in it.

Worked example 13 marks

An AND gate has two inputs, A and B. Draw the symbol for the AND gate and complete its truth table. The output is labelled X.

  1. 1

    Step 1: Draw the standard symbol for an AND gate. It looks like the letter 'D' with two input lines (A, B) on the flat side and one output line (X) on the curved side.

  2. 2

    Step 2: Create a truth table with columns for A, B, and X. Since there are two inputs, there will be 2^2 = 4 rows for all possible input combinations.

  3. 3

    Step 3: List the input combinations: 0 0, 0 1, 1 0, 1 1.

  4. 4

    Step 4: For each row, calculate the output X. The rule for an AND gate is: the output is 1 ONLY IF both input A AND input B are 1. Otherwise, the output is 0.

  5. 5

    Step 5: Complete the table: A=0, B=0 -> X=0; A=0, B=1 -> X=0; A=1, B=0 -> X=0; A=1, B=1 -> X=1.

Recap

  • A logic gate is a component that controls the flow of electricity based on logical rules.
  • The AND gate outputs 1 only if all its inputs are 1.
  • The OR gate outputs 1 if at least one of its inputs is 1.
  • The NOT gate is an inverter; it flips the input value (0 becomes 1, 1 becomes 0).

Quick check

  1. Draw the standard logic gate symbol for a two-input OR gate.1 mark
  2. What is the output of a NOT gate if the input is 1?1 mark

2. Universal and Exclusive Gates

Beyond the basic three, there are other important gates. NAND (Not-AND) and NOR (Not-OR) are called 'universal gates' because any other logic function can be created using only NAND gates, or only NOR gates. This simplifies chip design. The XOR (Exclusive OR) gate is also very useful. It outputs 1 only when its inputs are different.

X = A NAND B (Notation: ¬(A . B))

X = A NOR B (Notation: ¬(A + B))

X = A XOR B (Notation: A ⊕ B)

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

Confusing the XOR gate with the OR gate. For inputs 1 and 1, OR gives 1, but XOR gives 0. Remember XOR means 'one or the other, but not both'.

Fun fact

The computer that guided the Apollo missions to the Moon was built almost entirely from thousands of three-input NOR gates. Using just one type of gate simplified the design and manufacturing process.

Worked example 12 marks

Complete the truth table for a two-input XOR gate with inputs A and B, and output X.

  1. 1

    Step 1: Set up a truth table with columns A, B, and X, and 4 rows for the input combinations.

  2. 2

    Step 2: List the input combinations: 0 0, 0 1, 1 0, 1 1.

  3. 3

    Step 3: Apply the XOR rule: the output is 1 only if the inputs are different. 'Exclusive' means one or the other, but not both.

  4. 4

    Step 4: Fill in the output column X: A=0, B=0 (same) -> X=0; A=0, B=1 (different) -> X=1; A=1, B=0 (different) -> X=1; A=1, B=1 (same) -> X=0.

Worked example 22 marks

Draw the symbol for a two-input NAND gate and state its output when both inputs are 1.

  1. 1

    Step 1: The symbol for a NAND gate is the same as an AND gate (a 'D' shape) but with a small circle on the output line. This circle signifies inversion (the 'N' in NAND).

  2. 2

    Step 2: Consider the inputs A=1 and B=1.

  3. 3

    Step 3: First, perform the AND operation: 1 AND 1 = 1.

  4. 4

    Step 4: Then, perform the NOT operation (the circle): NOT 1 = 0. So the final output is 0.

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.
  • An XOR gate outputs 1 only when its inputs are different.
  • NAND and NOR are called universal gates.
  • The small circle on a gate symbol always means 'NOT' or 'invert'.

Quick check

  1. What is the output of a two-input NOR gate if both inputs are 0?1 mark

3. Combining Gates: Logic Circuits and Expressions

Single logic gates are useful, but the real power comes from combining them into logic circuits to perform complex tasks. We can represent these circuits using a type of algebra called Boolean algebra. A logic expression is a mathematical way of showing the relationship between the inputs and the output of a logic circuit. When reading a circuit to create an expression, work from the inputs on the left to the final output on the right. Use brackets to show the order in which the gates are evaluated, just like in regular maths.

Key term

Logic Expression: A mathematical representation using Boolean algebra to describe the function of a logic circuit.

Examiner insight

Examiners award marks for correctly identifying intermediate outputs and using brackets to show the correct order of operations in the final expression.

Common pitfall

Forgetting to use brackets. In the expression X = (A AND B) OR C, the brackets are crucial. Without them, A AND B OR C is ambiguous. The rule is that gates 'earlier' in the circuit (further left) should be bracketed.

Worked example 13 marks

A logic circuit has three inputs A, B and C. A and B are inputs to an AND gate. The output of this AND gate and the input C are the inputs to an OR gate. The final output is X. Write the logic expression for this circuit.

  1. 1

    Step 1: Identify the first operation. Inputs A and B go into an AND gate. The expression for this part is (A AND B). We use brackets to group this operation.

  2. 2

    Step 2: Identify the next operation. The output of the first gate, which is (A AND B), and the input C go into an OR gate.

  3. 3

    Step 3: Combine the parts. The final expression is the result of the OR operation. So, X = (A AND B) OR C.

  4. 4

    Step 4: Write the final expression using standard notation: X = (A . B) + C.

Recap

  • To write an expression from a circuit, work from left (inputs) to right (output).
  • Label the output of each gate as an intermediate step.
  • Use brackets to group operations and maintain the correct order.
  • The final expression describes the entire circuit's logic from input to output.

Quick check

  1. Write the logic expression for a circuit where input A is inverted, and then the result is ANDed with input B. The output is Y.2 marks

4. Testing Circuits: Creating Truth Tables

A logic expression or circuit diagram tells us how a system is built, but a truth table tells us what it does. A truth table is a powerful tool that lists every possible combination of inputs and shows the resulting output for each case. This allows us to test a circuit's logic exhaustively. The number of rows in a truth table is determined by the number of inputs(n) using the formula 2^n. For 3 inputs, you need 2^3 = 8 rows. To make it easier to calculate the final output, it's good practice to add extra 'workspace' columns for the outputs of intermediate gates.

Number of rows = 2^n (where n is the number of inputs)

Key term

Truth Table: A table that lists all possible combinations of input values and the corresponding output of a logic circuit or expression.

Common pitfall

Making mistakes when filling in the input combinations. Students should use a systematic binary counting method (000, 001, 010, 011...) to ensure all combinations are covered without duplication or omission.

Worked example 14 marks

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

  1. 1

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

  2. 2

    Step 2: Set up the table with columns for the inputs A, B, C, an intermediate column for the bracketed part (A AND B), and a final column for the output X.

  3. 3

    Step 3: Fill in the input columns with all 8 unique binary combinations, counting from 000 to 111. This is a systematic way to ensure no combination is missed. (000, 001, 010, 011, 100, 101, 110, 111).

  4. 4

    Step 4: Calculate the intermediate column. Let's call it P = (A AND B). For each row, calculate A AND B. This will be 1 only when A=1 and B=1.

  5. 5

    Step 5: Calculate the final output column X = P OR C. For each row, take the value in your intermediate column P and OR it with the value in column C. The result is 1 if P is 1, or if C is 1, or both.

  6. 6

    Step 6: The final truth table will show the output X for every combination of A, B, and C.

Recap

  • A truth table shows all possible outputs for all possible inputs.
  • The number of rows in a truth table is 2 to the power of the number of inputs.
  • Always fill in the input combinations systematically, like counting in binary.
  • Use intermediate columns for parts of the expression (e.g., within brackets) to avoid errors.

Quick check

  1. How many rows are needed in a truth table for a logic circuit with inputs P, Q, R, and S?1 mark

5. Reverse Engineering: Truth Tables to Expressions

A key skill is to work backwards: given a truth table, how do you find the logic expression and circuit that produces it? The most common method is called 'Sum of Products'. You focus only on the rows where the final output is 1. For each of these '1' rows, you write an AND expression that would produce a 1 for that specific input combination. If an input in that row is 0, you must use a NOT on it. Finally, you take all these individual AND expressions and link them together with OR gates. This gives you one large expression that satisfies the entire truth table.

Key term

Sum of Products (SOP): A method of writing a Boolean expression by ORing together several AND terms, typically derived from the '1' outputs in a truth table.

Examiner insight

Marks are often awarded for correctly identifying the rows with a '1' output, writing the correct AND terms for each (including any necessary NOTs), and then combining them with OR operators.

Common pitfall

Forgetting to apply the NOT operator to inputs that are 0 in a row you are analysing. The AND term for a row must evaluate to 1, so any 0 inputs must be inverted to 1.

Worked example 14 marks

A system has two inputs, A and B, and one output, X. The truth table is given below. Find the logic expression for X.

ABX
000
011
101
110
  1. 1

    Step 1: Identify the rows where the output X is 1. These are row 2 (A=0, B=1) and row 3 (A=1, B=0).

  2. 2

    Step 2: For the first '1' row (A=0, B=1), write an AND expression. To get a 1, we need to invert A. So the expression is (NOT A AND B).

  3. 3

    Step 3: For the second '1' row (A=1, B=0), write an AND expression. To get a 1, we need to invert B. So the expression is (A AND NOT B).

  4. 4

    Step 4: Combine these two expressions with an OR operator. This is the 'Sum' (OR) of 'Products' (AND terms).

  5. 5

    Step 5: The final logic expression is X = (NOT A AND B) OR (A AND NOT B). Note: This is the expression for an XOR gate!

Recap

  • To get an expression from a truth table, use the Sum of Products method.
  • Find every row where the output is 1.
  • For each of those rows, write an AND expression that is true only for that row's inputs (use NOT for any 0s).
  • OR all the AND expressions together to get the final expression.
  • This expression can then be used to draw the corresponding logic circuit.

Quick check

  1. A truth table has a '1' output for the row A=1, B=0, C=1. What is the AND term for this row?2 marks

6. From Problem to Solution

The ultimate goal of learning Boolean logic is to solve real-world problems. This involves translating a description of a system's behaviour, given in English, into a formal logic expression, circuit, or truth table. The key is to break the problem down: identify the inputs (the conditions), the output (the action), and the logical relationships ('and', 'or', 'not', 'unless') that connect them.

Key term

Problem Statement: A description in natural language of the conditions under which a system should operate, which can be translated into a logical representation.

Examiner insight

Examiners look for a clear translation of the problem's conditions into the correct logical operators. Show your thinking by defining what your variables (e.g., A=1 means...) represent.

Common pitfall

Misinterpreting the English language. For example, 'A unless B' usually means 'A if NOT B'. It is vital to carefully convert the problem's wording into precise logical operations.

Worked example 13 marks

A car's warning alarm (A) will sound if the driver's seatbelt (S) is not fastened AND the engine (E) is on. Let S=1 mean the seatbelt is fastened, and E=1 mean the engine is on. Write the logic expression for the alarm A.

  1. 1

    Step 1: Identify the inputs and output. Inputs: S (seatbelt), E (engine). Output: A (alarm).

  2. 2

    Step 2: Translate the conditions. The alarm sounds if 'seatbelt is NOT fastened'. Since S=1 means fastened, 'not fastened' is represented by NOT S.

  3. 3

    Step 3: The second condition is 'the engine is on'. Since E=1 means the engine is on, this is represented by E.

  4. 4

    Step 4: Identify the logical connector. The problem states the conditions are linked by 'AND'.

  5. 5

    Step 5: Combine the parts into a final expression. The alarm A is on when (NOT S) is true AND E is true. So, A = (NOT S) AND E.

Recap

  • Read the problem statement carefully to identify all inputs and the final output.
  • Assign binary values (1 for true/on, 0 for false/off) to each condition.
  • Translate words like 'and', 'or', 'but not', 'unless' into their corresponding logic gates.
  • Build the logic expression piece by piece.
  • From the final expression, you can draw the logic circuit or create the truth table.

Quick check

  1. A security light (L) turns on if a sensor detects motion (M) OR a button (B) is pressed. 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 single logic gate that would generate the following truth table: | A | B | X | |---|---|---| | 0 | 0 | 1 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 0 |1 mark
  2. Write the logic expression for the following logic circuit. The inputs are A, B, C and the output is X. [Image of a circuit showing (A NOR B) AND C]3 marks
  3. A logic circuit is represented by the expression Z = (A AND NOT B) OR (B AND C). Complete the truth table for this circuit, showing all workings. | A | B | C | Workspace | Z | |---|---|---|---|---| | 0 | 0 | 0 | | | | 0 | 0 | 1 | | | | 0 | 1 | 0 | | | | 0 | 1 | 1 | | | | 1 | 0 | 0 | | | | 1 | 0 | 1 | | | | 1 | 1 | 0 | | | | 1 | 1 | 1 | | |5 marks
  4. Explain why the NAND gate is known as a 'universal gate'.2 marks
  5. Draw a logic circuit to represent the expression Y = NOT(A OR B) AND C.4 marks
  6. A greenhouse heating system (H) turns on if the temperature (T) is below 20°C AND it is nighttime (N). The heater also turns on if a manual override switch (M) is activated, regardless of other conditions. Define binary values for the inputs and write a logic expression for H.4 marks
  7. Derive the logic expression for the given truth table, simplifying your answer if possible. | A | B | X | |---|---|---| | 0 | 0 | 1 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | 1 |4 marks
  8. What is the key difference in the output between a two-input OR gate and a two-input XOR gate? Give a specific example of inputs where their outputs differ.2 marks
  9. A logic circuit has four inputs. How many possible input combinations are there, and therefore, how many rows would its full truth table contain?2 marks
  10. Consider the truth table below. Write a logic expression in Sum of Products form to represent the output Z. | S | T | P | Z | |---|---|---|---| | 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 |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