Logic circuits
Introduced| English | Meaning |
|---|---|
| logic circuit/ˈlɒdʒɪk ˈsɜːkɪt/ | A combination of logic gates connected to implement a Boolean function. |
| Boolean expression/ˈbuːlɪən ekˈspreʃn/ | An expression whose value is true or false. |
| problem statement/ˈprɒbləm ˈsteɪtmənt/ | A clear description of the problem to be solved and the required outcome. |
| truth table/truːθ ˈteɪbl/ | A table listing the output of a logical expression or circuit for every combination of inputs. |
| sum of products/sʌm ɒv ˈprɒdʌkts/ | sum of products |
| half adder/hɑːf ˈædə/ | A logic circuit that adds two single binary digits and produces a sum bit and a carry bit. |
Three sensors, two gates, one decision
- A microwave oven heats only when the door is closed and the start button has been pressed and the timer has not reached zero.
- Three sensors give three 0/1 signals. Two AND gates combine them into one signal that switches the magnetron. Open the door and the output drops to 0 at once.
- Every safety interlock, every alarm and every processor instruction is a decision like this, built from the six gates of the last lesson.
- This lesson is about building and reading those circuits, and moving between the four ways of writing the same decision.
Four views of one function
- A logic circuit 逻辑电路 is a network of gates that carries out a Boolean expression 布尔表达式.
- The same function can be written as a problem statement 问题陈述 in English, as an expression, as a circuit diagram, or as a truth table 真值表. The exam asks you to move in every direction between them.
- The paper writes expressions in words,
X = (A AND NOT B) OR (B AND C), and accepts the algebraic form $X = A\overline{B} + BC$, where a dot or nothing is AND, a plus is OR and a bar is NOT. Use whichever the question uses.
Gates wired together to carry out one Boolean expression
Expression to circuit
- Draw one gate per operator, starting from the innermost brackets.
- For
X = (A AND B) OR (NOT C): an AND gate on A and B, a NOT gate on the C wire, and an OR gate combining the two results. - Inputs on the left, the single output on the right, every line ending at a gate input or the output, and the output labelled X.
One gate for each operator in the expression
Logic circuits
gates combine into circuits
Each gate has a fixed rule; chaining them builds every circuit — start with one gate.
For $X = (A \cdot B) + \overline{C}$ with $A=1, B=1, C=1$, what is $X$?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
$A \cdot B = 1$, and $\overline{C} = 0$. $X = 1 + 0 = 1$.
Worked example: circuit to expression
- Work forwards from the inputs and label every intermediate output.
- In the circuit below, B passes through a NOT gate. A and NOT B feed an AND gate: call its output P, so
P = A AND NOT B. B and C feed a second AND gate:Q = B AND C. - P and Q feed the OR gate, so
X = P OR Q = (A AND NOT B) OR (B AND C). - Labelling P and Q is not decoration. It is what lets you fill the truth table one gate at a time.
Label every intermediate output before you write the expression
In the worked circuit, the second AND gate's output is Q = B AND ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
B and C feed the lower AND gate. Labelling that output Q lets the truth table be filled one gate at a time.
Circuit to truth table
- For $n$ inputs there are $2^{n}$ rows: two inputs give 4, three give 8, four give 16. List them in binary counting order.
- Give the table a column for each intermediate output as well as the final one, so every row is checked one gate at a time.
- Fill the columns left to right: first the NOT, then each AND, then the OR.
How many rows does a truth table have for a circuit with 3 inputs?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$2^n$ rows; for 3 inputs, $2^3 = 8$.
How many rows for 4 inputs?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
$2^4 = 16$ rows.
Worked example: the eight rows
- The circuit from the worked example above, with columns for NOT B, P, Q and X:
| A | B | C | NOT B | P | Q | X |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 | 1 |
- X is 1 in four of the eight rows. Check any one against the expression: row 1 0 0 has A = 1 and NOT B = 1, so P = 1, so X = 1.
For X = (A AND NOT B) OR (B AND C), which of these input rows give X = 1? Select all that apply.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Row 011 makes Q = 1; row 100 makes P = 1. In row 110, B = 1 kills P and C = 0 kills Q; in row 001 both terms are 0.
Truth table to expression: sum of products
- Sum of products 积之和: for each row whose output is 1, write an AND of the inputs, putting NOT on any input that is 0 in that row. Then OR those terms together.
- A table that is 1 only on (A = 0, B = 1) and (A = 1, B = 0) gives
(NOT A AND B) OR (A AND NOT B), which is exactly A XOR B. - Simplify only if the question asks; the unsimplified sum of products earns the marks.
In the sum-of-products method, for each row whose output is 1 you write:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Each 1-row becomes an AND term (NOT the 0 inputs); you then OR all those terms together.
In sum-of-products, you OR together one AND-term for every row whose output is 1.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Each output-1 row becomes an AND term (NOT-ing the 0 inputs); ORing those terms gives an expression that is 1 on exactly those rows.
The half adder
- Adding two bits gives a sum bit and a carry bit: 1 + 1 = 10 in binary.
- The sum column is 0, 1, 1, 0, which is XOR. The carry column is 0, 0, 0, 1, which is AND. Two gates make a half adder 半加器.
- It is the standard example of reading gates straight off a truth table, and the first piece of every processor's arithmetic unit.
Each input pair flows through the gates: XOR gives the sum, AND gives the carry, so 1 + 1 = 10
Half adder
Wire XOR and AND to the same two inputs: XOR gives the sum bit, AND gives the carry. Click A and B.
In a half adder, which gate produces the carry bit?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The carry is 1 only when both bits are 1, which is AND. The sum is 1 when the bits differ, which is XOR.
From a problem statement
- Turn the English into Boolean one clause at a time before drawing anything.
- "A and B" is
A AND B. "A or B, or both" isA OR B. "exactly one of A and B" isA XOR B. - "neither A nor B" is
A NOR B. "not both" isA NAND B. "unless" usually means AND NOT.
Match each English phrase to the single gate that implements it.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
both = AND, differ = XOR, neither = NOR, not-both = NAND.
Worked example: a machine alarm
- An alarm X sounds when the guard is open (A = 1) and either the motor is running (B = 1) or the temperature is high (C = 1).
- "Either B or C" is
B OR C. "A and that" isX = A AND (B OR C). The brackets around the OR are essential. - X = 1 needs A = 1 and at least one of B, C equal to 1: the rows (1, 0, 1), (1, 1, 0) and (1, 1, 1). Three rows out of eight, and A = 0 can never sound the alarm.
- The circuit is one OR gate on B and C feeding one AND gate with A.
For the alarm X = A AND (B OR C), the alarm can sound when A = 0 provided both B and C are 1.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
The AND with A means A = 1 is required in every row where X = 1. With A = 0 the output is 0 whatever B and C do.
Marks that slip away
A AND B OR Cwithout brackets is ambiguous, and the examiner reads it as you did not intend. Bracket the OR before ANDing it.- A wire that goes nowhere, or an output with no label, loses the circuit mark even when the gates are right.
- A NOT on an input is a gate on the diagram, not a bar written over the letter.
- Three inputs mean eight rows. A table with fewer rows cannot be marked as complete.
You've got it
- expression → circuit: one gate per operator, innermost brackets first, inputs left, labelled output right
- circuit → expression: label each intermediate output (P, Q) and combine; circuit → truth table: $2^{n}$ rows with a column per gate
- truth table → expression: sum of products, one AND-term per output-1 row, ORed together; XOR + AND make the half adder
- problem → Boolean: exactly one = XOR, neither = NOR, not both = NAND; bracket the OR inside an AND