IGCSE Computer Science 0478 — 10 Boolean Logic Hangman

The 30 key terms

1bit

A bit is a single binary digit that is either 0 or 1, like a switch that is off (0) or on (1). A group of 8 bits is called a byte.

2Boolean

A data type with only two possible values: true or false (yes or no). Used for yes/no fields, TRUE and FALSE in a spreadsheet, and the result of a comparison such as 5>3.

3logic gate

An electronic component that takes one or two binary inputs (0 or 1) and gives one binary output (0 or 1) by a fixed rule. Processors are built from many gates.

4A, B, C and X

In a logic circuit, the inputs are labelled with capital letters A, B and C on the left, and the single output is labelled X on the right.

5truth table

A table listing every input combination in its rows, with the output in the last column. Two inputs give 2^2 = 4 rows, in the order 00, 01, 10, 11.

6NOT

A logic gate with one input that outputs the opposite value: 0 becomes 1 and 1 becomes 0. It is drawn as a triangle with a small circle and written X = NOT A.

7AND

A logic gate with two inputs that outputs 1 only when both inputs are 1; otherwise it outputs 0. Written X = A AND B, drawn as a D shape, with truth table output 0 0 0 1.

8X = A OR B

The OR gate has two inputs, A and B. Its output X is 1 when at least one input is 1, and 0 only when both are 0. Its truth table output column is 0 1 1 1.

10NOT: 1 input, others: 2

NOT has exactly one input. AND, OR, NAND, NOR and XOR each have exactly two inputs. No three-input gates in this course, so join two gates for three inputs.

11NAND

A gate with two inputs that outputs 0 only when both inputs are 1. It is the opposite of AND (AND followed by NOT). Its truth table output is 1 1 1 0. Written X = A NAND B.

12X = NOT (A OR B)

The NOR gate: output X is 1 only when both inputs A and B are 0. It is OR followed by NOT, so the truth table output is 1 0 0 0. Its symbol is OR with a small circle.

13X = A XOR B

The XOR (exclusive OR, or EOR) gate has two inputs and outputs 1 only when the inputs are different. Its truth table output is 0 1 1 0. Its symbol is the OR shape with an extra curve at the input.

14XOR

Exclusive OR: outputs 1 when exactly one input is 1. When A and B are both 1 it outputs 0, but OR outputs 1 in that row. XOR means one or the other, but not both.

15output circle

A small circle on a gate's output means NOT: AND becomes NAND and OR becomes NOR. XOR has no circle; its symbol is OR with an extra curved line at the input side.

16output column

Read the output column for rows 00, 01, 10, 11 to name the gate: AND 0001, OR 0111, NAND 1110, NOR 1000, XOR 0110.

17X = A AND B

A logic expression for one gate: write the output X, an equals sign, then the input letters joined by the gate name in capitals, such as X = NOT A or X = A XOR B.

18(A AND B) OR C

Brackets show which gate is worked out first. Here A AND B is done first, then its result goes into OR with C. A AND (B OR C) uses the same letters but gives a different output.

19NOT (A AND B)

NOT before a bracket flips the whole bracket's result. In (NOT A) AND B, NOT flips only input A, so NOT (A AND B) gives different results.

22intermediate column

An extra truth table column for a bracket or gate output, such as P = A AND B. It is filled in first, so the final output X can be worked out step by step from earlier columns.

23X = (A AND B) OR C

Fill all 8 rows of A, B and C: work out the bracket (A AND B) in an extra column first, then combine it with C using OR to get output X.

24logic circuit

A diagram of logic gates joined by wires. Inputs are on the left, the output is on the right, and each wire carries 0 or 1. A dot where a wire splits is a junction.

25trace a circuit

Write the input values on the wires, then work gate by gate from left to right, writing each gate's output on its output wire until you reach the final output X.

26trace each row

Follow one row of input values through each gate in the circuit, write each gate's output in an extra column, then copy the final value of X into the truth table.

30one gate per operator

Draw every gate in the given expression, one for each operator, even if a shorter circuit has the same truth table. Never combine or remove gates.

31junction dot

A dot drawn where wires join, so one input can feed two gates. Wires that cross with no dot are not connected. Draw inputs on the left and the output on the right.

32key word = gate

Words in a problem statement point to a gate: both/and = AND, either/or = OR, not = NOT, neither...nor = NOR, not both = NAND, only one of = XOR.

36X = (A AND NOT B) OR (NOT A AND B)

To write an expression from a truth table, take each row with output 1 and join its inputs with AND, adding NOT to any input that is 0. Then join those rows with OR.

383 inputs, 1 output

A circuit here has at most three inputs (A, B, C) and exactly one output X. With 3 inputs the truth table has 8 rows (2 x 2 x 2). Gates with two inputs can be combined to handle the third input.

39equivalent

A circuit, expression and truth table are equivalent when each gives the same output X for the same inputs. Check by working out X row by row in each one and comparing the results.

40common logic mistakes

Mixing up NAND/AND or OR/XOR, rows out of binary order, NOT on the wrong part, missing brackets or columns, wrong input counts, or simplifying a circuit that must be drawn as given.