Boolean Logic
The six gates every circuit is built from, and the four questions the exam asks about them.
AND| A | B | Output |
|---|---|---|
| 0 | 0 | |
| 0 | 1 | |
| 1 | 0 | |
| 1 | 1 |
//What a gate actually is
A logic gate is a rule, not a thing you have to understand electrically. One or two wires go in, one wire comes out, and every wire is either OFF (written 0) or ON (written 1) — never anything in between. The gate's rule says what the output is for each setting of the inputs, and that rule never changes. Learn the six rules and everything else in this topic is bookkeeping.
1 = ON = true = high
0 = OFF = false = low
+--------+
A ----| |
| gate |---- Q
B ----| |
+--------+
Q depends ONLY on A and B, and only on their values right now.//The six gates, in one table
This is the table everything else depends on. You must be able to write it from memory without hesitating, because every question below starts by looking a row up in it. NAND is AND with the answer flipped, NOR is OR with the answer flipped, and XOR is the awkward one: it means one or the other, but NOT both.
A B | AND OR NAND NOR XOR
----+---------------------------
0 0 | 0 0 1 1 0
0 1 | 0 1 1 0 1
1 0 | 0 1 1 0 1
1 1 | 1 1 0 0 0
NOT has one input: NOT 0 = 1 NOT 1 = 0
AND is 1 only when BOTH are 1
OR is 1 when AT LEAST ONE is 1
NAND is 0 only when BOTH are 1 (NOT AND)
NOR is 1 only when BOTH are 0 (NOT OR)
XOR is 1 when they are DIFFERENT//Three ways of writing the same thing
A circuit, an expression and a truth table are three ways of writing one idea, and the whole of this topic is translating between them. Every logic question on the paper is one of four translations, and each one has a method you can follow without being clever. The four sections after this are those four methods.
EXPRESSION
Q = (A AND B) OR C
/ \
/ \
CIRCUIT --------- TRUTH TABLE
The four questions:
1. expression -> circuit "draw a logic circuit for..."
2. circuit -> truth table "complete the truth table..."
3. circuit -> expression "write a logic expression for..."
4. truth table -> expression "write the logic expression for..."//Question 1 — draw the circuit for an expression
Work from the inside out. The brackets tell you the order: whatever is inside the innermost brackets is the first gate you draw, and the operation written outside all the brackets is the LAST gate you draw, the one whose output is Q. Give every input its own line on the left, and let a line split if the same input is used twice.
METHOD
1. Find the innermost brackets. Draw that gate first.
2. Work outwards, one bracket at a time.
3. The operation outside everything is the last gate. Its output is Q.
WORKED: Q = NOT (A OR (B AND C))
step 1 innermost is (B AND C) B --+
AND --- X
C --+
step 2 next is A OR X A --+
OR --- Y
X --+
step 3 the NOT is outside everything Y --- NOT --- Q
CHECK: read your own circuit back as words. "NOT (A OR (B AND C))".
If it does not read the same as the question, a wire is wrong.//Question 2 — complete the truth table for a circuit
Do not try to do a whole row in your head. Give every gate in the circuit a letter, add one COLUMN per gate, and fill the table column by column, left to right. Each column only ever depends on columns you have already filled, so you are never doing more than one gate at a time. The intermediate columns are worth marks on their own — write them even when the question only asks for the final output.
METHOD
1. Label every gate output: X, Y, Z...
2. Write the input rows in binary counting order (see the last note).
3. One column per label, then the final output column.
4. Fill each column completely before starting the next.
WORKED: X = A AND B Y = NOT C Q = X OR Y
A B C | X = A AND B | Y = NOT C | Q = X OR Y
------+-------------+-----------+------------
0 0 0 | 0 | 1 | 1
0 0 1 | 0 | 0 | 0
0 1 0 | 0 | 1 | 1
0 1 1 | 0 | 0 | 0
1 0 0 | 0 | 1 | 1
1 0 1 | 0 | 0 | 0
1 1 0 | 1 | 1 | 1
1 1 1 | 1 | 0 | 1
Notice the X column ignores C completely, and the Y column ignores A and B.
That is normal, and it is why doing one column at a time is so much easier
than doing one row at a time.//Question 3 — write the expression for a circuit
This is question 1 backwards and it is easier, because you can do it with a pencil on the diagram itself. Start at the inputs and walk forwards. Write the output of each gate ON the wire that leaves it, in brackets. When you reach the final gate, the thing written on its output wire is the answer.
METHOD
1. Write A, B, C on the input wires.
2. For each gate, write what comes OUT of it on its output wire,
in brackets: (A AND B), (NOT C), and so on.
3. Keep going until you reach Q. Copy down what is written there.
WORKED:
A ---+
AND --- write (A AND B) here
B ---+ |
OR --- write ((A AND B) OR (NOT C)) here = Q
C --- NOT --- write (NOT C) here
Q = (A AND B) OR (NOT C)
The outermost brackets can be dropped: Q = (A AND B) OR NOT C.
Never drop the inner ones.//Question 4 — write the expression for a truth table
This is the one that looks impossible and is actually the most mechanical of the four. You only care about the rows where the output is 1 — every other row can be ignored completely. Each of those rows becomes one AND term, and the terms are joined with OR. The method never fails, whatever the table says, and it is worth full marks even when a shorter answer exists.
METHOD -- the name for it is SUM OF PRODUCTS
1. Look down the output column. Circle every row where it is 1.
2. Turn each circled row into one AND term:
write every input that is 1 as itself,
write every input that is 0 with a NOT,
join them with AND.
3. Join all the terms together with OR. That is the answer.
WORKED: -- the table below is a past paper question, unchanged
R S T | Q
------+---
0 0 0 | 0
0 0 1 | 1 <-- circled
0 1 0 | 0
0 1 1 | 0
1 0 0 | 0
1 0 1 | 0
1 1 0 | 1 <-- circled
1 1 1 | 0
row 0 0 1 -> R is 0, S is 0, T is 1 -> (NOT R) AND (NOT S) AND T
row 1 1 0 -> R is 1, S is 1, T is 0 -> R AND S AND (NOT T)
Q = ((NOT R) AND (NOT S) AND T) OR (R AND S AND (NOT T))
TO DRAW IT: one AND per circled row (with the NOTs in front), then one OR
joining them. Two circled rows means two ANDs and one OR.
CHECK: count your AND terms. It must equal the number of circled rows.//When the long method is not the short answer
The sum-of-products method always works, and sometimes it works far too hard. Before you write eight gates, look at the output column as a whole and ask what it is describing. Three tables come up again and again, and each one is a single gate or a pair. Getting the short answer is not required for the marks on a 'write the expression' question, but it is required whenever the question says 'simplify' — and it saves you a page of drawing.
Only ONE row has output 0
-> that is NAND (0 only when both are 1)
or NOR (0 in every row except 0 0)
The long method would give you three AND terms for the SAME thing.
The output is 1 when the inputs are DIFFERENT
-> XOR. Two inputs, one gate.
The output is 1 when an ODD number of inputs are 1
-> XOR chained: (A XOR B) XOR C. Two gates instead of four AND terms.
The output is 1 when AT LEAST TWO of three inputs are 1
-> (A AND B) OR (A AND C) OR (B AND C). Three ANDs, not four.
ALWAYS worth doing: if two of your AND terms are identical except that one
has X and the other has NOT X, that variable drops out and the two terms
become one. (A AND B) OR (A AND NOT B) = A//Turning a sentence into logic
Paper 2 often gives you a situation in words instead of a table — a safety system, a vending machine, a car. Give each condition a letter first and write the letters down, because half the marks lost here are lost by mixing up which letter meant what. Then look for the joining words: they translate one for one into gates.
and -> AND
or -> OR
not / unless / fails -> NOT
either ... or ... but not both -> XOR
neither ... nor ... -> NOR
WORKED
"The machine runs when the guard is closed (G) AND the button is
pressed (B), unless the emergency stop is pressed (E)."
G = 1 when the guard is closed
B = 1 when the button is pressed
E = 1 when the emergency stop is pressed
"unless E" means AND NOT E
M = (G AND B) AND (NOT E)//De Morgan's law
Two facts that let you move a NOT through a bracket, and they are the only Boolean algebra IGCSE needs. They are worth knowing here because they explain why NAND and NOR turn up everywhere, and because AS Level examines them by name. Say it as: break the bar, change the sign.
NOT (A AND B) = (NOT A) OR (NOT B)
NOT (A OR B) = (NOT A) AND (NOT B)
WHY, in words:
"not both of them are on" is the same as "at least one is off"
"neither of them is on" is the same as "both of them are off"
CHECK IT with a table - two columns that match in all four rows is a proof:
A B | NOT(A AND B) | (NOT A) OR (NOT B)
----+--------------+--------------------
0 0 | 1 | 1
0 1 | 1 | 1
1 0 | 1 | 1
1 1 | 0 | 0//NAND on its own can build anything
A NAND gate with both of its inputs joined to the same wire behaves as a NOT. Once you have NOT, you can build AND (a NAND followed by a NOT) and OR (De Morgan: invert both inputs, then NAND them). This is why NAND is called a universal gate, and why a real chip can be manufactured out of one kind of part repeated millions of times.
NOT A = A NAND A
A AND B = NOT (A NAND B)
= (A NAND B) NAND (A NAND B)
A OR B = (NOT A) NAND (NOT B) [De Morgan]
= (A NAND A) NAND (B NAND B)
So: one part, three gates, and from those three, everything else.//How many rows, and in what order
The commonest lost mark in this topic is a missing row. The number of rows is fixed by the number of inputs — two inputs give 4 rows, three give 8, four give 16 — and the rows must be written in binary counting order, starting at all zeros. Write the whole empty table out before you fill anything in, and you cannot lose one.
n inputs -> 2^n rows
2 inputs (4 rows) 3 inputs (8 rows)
0 0 0 0 0
0 1 0 0 1
1 0 0 1 0
1 1 0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
A quick way to write them: the last column alternates 0 1 0 1 ...,
the one before it goes 0 0 1 1 0 0 1 1 ..., the one before that
0 0 0 0 1 1 1 1 ... Each column changes half as often as the one
to its right.KEY TERMS
CHECK YOURSELF
1.For which inputs does XOR output 1?
2.A NAND gate with both inputs set to 1 outputs:
3.A circuit has 3 inputs. How many rows does its truth table need?
4.A truth table has three rows where the output is 1. Using sum of products, how many AND terms will the expression have?
5.A row of a truth table reads R = 0, S = 1, T = 1, and the output is 1. What is the AND term for that row?
6.When you draw the circuit for Q = NOT (A OR (B AND C)), which gate do you draw LAST?
7.Why add a column for every gate when completing a truth table, instead of only the final output?
8.A two-input truth table has output 0 in exactly one row — the row where both inputs are 1. Which single gate is it?
9.How do you make a NAND gate behave as a NOT gate?
10.A question says SIMPLIFY the logic circuit. Is a correct sum-of-products expression enough for full marks?