CS14Logic Gates, Truth Tables and Boolean Expressions

A computer's processor is built from millions of tiny switches. Groups of them form logic gates, which work on binary values: 1 (on, true) and 0 (off, false).

• Logic gate (AQA): “an electronic component that takes one or more binary inputs and performs a basic logical operation (such as AND, OR and NOT) to produce a single binary output.”
• You need four gates: NOT, AND, OR and XOR. You don't need NAND or NOR.
• NOT has one input. It flips it: 1 becomes 0 and 0 becomes 1.
• AND outputs 1 only when both inputs are 1.
• OR outputs 1 when at least one input is 1 (so also when both are).
• XOR (exclusive OR) outputs 1 when exactly one input is 1: the inputs are different.
• Learn the shapes. AND has a flat back and a round front (a D shape). OR has a curved back and a pointed front. XOR is an OR with an extra curved line behind it. NOT is a triangle with a small circle at its tip.

The four gates in the shapes AQA uses, with the Boolean expression for each.

Logic gate

An electronic component that takes one or more binary inputs and performs a basic logical operation (such as AND, OR and NOT) to produce a single binary output.

XOR

Exclusive OR: the output is 1 when exactly one input is 1.

Truth table (AQA): “a representation of the output of a logical expression or circuit for all possible combinations of input variables.”

• Two inputs give 4 rows: 00, 01, 10, 11.
• AND and OR differ in two rows (01 and 10). OR and XOR differ only in the last row (11).
• A quick way to remember: AND is 1 in one row, OR is 0 in one row, XOR is 1 when the inputs differ.
• AQA accepts T and F instead of 1 and 0, but not a mixture of the two in one table.

Truth table

A representation of the output of a logical expression or circuit for all possible combinations of input variables.

A Boolean expression describes a circuit in one line. AQA uses its own symbols, and you must use them when a question asks for a Boolean expression.

• AQA's example: (A AND B) OR (NOT C) is written (A . B) + C.
• Use brackets to show which part is worked out first, for example A . (B + C) is not the same as (A . B) + C.
• A bar over a group negates the whole group: A + B means NOT (A + B). Make sure the bar covers exactly what is negated.
• In this notation + means OR, not adding. 1 + 1 is 1.

Boolean expression

A way of writing a logic circuit using inputs and the operators . (AND), + (OR), ⊕ (XOR) and an overbar (NOT).

Questions can have up to three inputs. Each extra input doubles the number of rows: n inputs give 2ⁿ rows.

• List the inputs in binary counting order: 000, 001, 010, 011, 100, 101, 110, 111. That way you can't miss a row or repeat one.
• A quick pattern: the first column is four 0s then four 1s; the second is 0 0 1 1 0 0 1 1; the third alternates 0 1 0 1 0 1 0 1.
• For a three-input AND (A . B . C), the output is 1 only in the last row. For a three-input OR, it is 0 only in the first row.

When a circuit has more than one gate, add a working column for the output of each gate before the final output.

• Step 1: label the output of each gate (D, E…). Step 2: fill in each working column from the inputs. Step 3: fill in the output from the working columns.
• Work down a whole column at a time, not across a row: it's quicker and you make fewer slips.
• Check one row at the end by following it through the circuit by hand.

Q = (A . B) + C̄, with the two gate outputs labelled D and E.

Start at the inputs and work towards the output, writing an expression for each gate's output as you go.

• Write each gate's output in brackets, then put it into the next gate's expression.
• For the circuit in the previous section: the AND gate gives (A . B), the NOT gate gives C, and the OR gate joins them: Q = (A . B) + C.
• Check the order of the inputs doesn't matter for the gate: A . B is the same as B . A, and A ⊕ B is the same as B ⊕ A.
• Check your answer by testing one row of the truth table in your expression.

Work the other way: find the part of the expression worked out first (inside the brackets, and any bars over single inputs) and draw that gate first.

• Draw the inputs down the left-hand side and the output on the right.
• Each operator is one gate: . is an AND gate, + is an OR gate, ⊕ is an XOR gate, and each bar is a NOT gate.
• Draw a NOT gate straight after an input that has a bar over it.
• Join the gates with straight lines. A dot where wires meet shows they are connected; wires that only cross have no dot.
• Up to three inputs are used in AQA's circuits, and each gate (apart from NOT) has two inputs.

Many questions describe a real system with sensors or switches. Turn the words into gates, then into an expression or a circuit.

• First, give each input and output a letter (usually the question does this) and say what 1 means for each, for example D = 1 when the soil is dry.
• Then find the gates from the wording, and use brackets to keep the parts together.
• Interpreting results: once the truth table is complete, read off the rows where the output is 1. They tell you exactly when the system switches on.

A watering pump runs when the soil is dry and either it is morning or the override button is pressed.

A circuit can have more than one output. A circuit that adds two bits, A and B, needs two: a sum bit (S) and a carry bit (C).

• 1 + 1 = 2, which is 10 in binary: sum 0, carry 1. That's why two outputs are needed.
• The sum column matches XOR: S = A ⊕ B.
• The carry column matches AND: C = A . B.
• The same inputs feed both gates: the dots on the wires show where they branch.

Adding two bits: XOR gives the sum, AND gives the carry.