IB Computer Science Topic A1.2.5 Constructing Logic…

Logic Diagrams: Turning a Boolean Expression into a Circuit

Definition

Logic diagrams

Logic diagrams are visual representations of how logic gates are connected and interact within a circuit.

A logic diagram is the circuit that a Boolean expression describes, drawn with one gate symbol per operator.
Reading a diagram tells you what a circuit does, and drawing one turns a written requirement into something that can be built.
The same circuit can usually be drawn several ways, and the version with fewer gates is cheaper, uses less power and switches faster.

Note

A logic diagram carries the same information as a truth table or a Boolean expression.
The three are interchangeable, and exam questions move between them in both directions.
Constructing and reading truth tables is covered in A1.2.4.

Every gate has a fixed symbol, and a diagram drawn with invented shapes earns no marks.
The bubble on the output of a symbol means the output is inverted.
1. NAND is the AND symbol with a bubble, NOR is the OR symbol with a bubble, and XNOR is the XOR symbol with a bubble.

Gate	Symbol shape	Boolean notation	Reads as
AND	Flat back, rounded front	A . B	A AND B
OR	Curved back, pointed front	A + B	A OR B
NOT	Triangle with an output bubble	NOT A (or A with a bar)	NOT A
NAND	AND shape plus output bubble	NOT (A . B)	NOT (A AND B)
NOR	OR shape plus output bubble	NOT (A + B)	NOT (A OR B)
XOR	OR shape with a second curved back line	A (+) B	A XOR B
XNOR	XOR shape plus output bubble	NOT (A (+) B)	A XNOR B

Common Mistake

The bubble sits on the output side of the symbol, not the input side.
A bubble drawn on an input line means that input is inverted before the gate acts, which is a different circuit.
Drawing an AND symbol and writing NAND next to it scores nothing, because the symbol is what is being assessed.

Identify and label the inputs and the output before drawing anything.
1. Inputs go on the left, usually A, B and C, and the output on the right, usually Q.
Work outward from the innermost bracket, because the gate for the innermost bracket is drawn first.
Let the logic flow left to right, so every wire carries a value forward and never doubles back.
Give each gate exactly one output, which may then branch to feed several later gates.
1. A branching wire carries the same value to every gate it reaches.

Tip

Count the operators in the expression to get the number of gates before you draw.
Q = (A OR B) AND NOT C has three operators, so the diagram needs three gates.
If your finished drawing has a different number, you have added or dropped an operation.

A requirement written in words has to be translated into inputs, an output and a gate.
An alarm that sounds only when both sensors are triggered is an AND condition, because both inputs must be 1.

Example

A security system sounds an alarm only when a motion sensor and a door sensor are both triggered.
Inputs: M for the motion sensor, D for the door sensor.
Output: A for the alarm.
Expression: A = M . D
Gate: a single AND gate, because the word only when signals that both conditions are required.

Combining gates lets a circuit do arithmetic, which is how the ALU adds binary numbers.
A half adder adds two single bits and produces two outputs: a sum bit and a carry bit.
1. The sum bit is 1 when exactly one input is 1, which is XOR behaviour.
2. The carry bit is 1 only when both inputs are 1, which is AND behaviour.
So the circuit is S = A (+) B and C = A . B, with A and B each branching to feed both gates.

A	B	S = A XOR B	C = A AND B	Binary result
0	0	0	0	00
0	1	1	0	01
1	0	1	0	01
1	1	0	1	10

The last row is the point of the carry: 1 + 1 = 2, which needs two bits, and the carry column supplies the second one.

Analogy

A half adder does the same job as column addition on paper.
The sum bit is the digit you write down and the carry bit is the digit you carry to the next column.
Chaining these circuits together is how a CPU adds two eight-bit numbers.

Boolean algebra rewrites an expression into an equivalent one with fewer operators, and fewer operators means fewer gates to draw.
Each rule below can be checked against a truth table, and every rule holds for all input values.

Common Mistake

De Morgan's laws are the ones most often applied halfway.
Moving the NOT inside the bracket requires two changes: negate each variable and swap AND for OR.
Writing NOT (A . B) = NOT A . NOT B keeps the operator unchanged and is wrong.
A quick check is to test one row: with A = 1 and B = 0, NOT (A . B) = 1, NOT A + NOT B = 1, but NOT A . NOT B = 0.

The simplest simplifications remove operations that do nothing at all.
An input ANDed with itself is unchanged, and an input negated twice is unchanged.

Example

Original expression: (A . A) + (NOT (NOT B))
Idempotent law: A . A simplifies to A, which removes the AND gate.
Involution law: NOT (NOT B) simplifies to B, which removes both NOT gates.
Simplified expression: A + B
The circuit drops from four gates to one, with identical behaviour on every input.

De Morgan's laws are what let a NOT be moved across a bracket so that terms can then be factorised.
Start from Q = NOT (A + B) + (A . NOT B), which needs five gates as written.
1. Apply De Morgan to the first term: NOT (A + B) becomes NOT A . NOT B.
2. The expression is now (NOT A . NOT B) + (A . NOT B), and NOT B appears in both terms.
3. Factorise NOT B out using the distributive law: NOT B . (NOT A + A).
4. Apply the complement law: NOT A + A = 1, giving NOT B . 1.
5. Apply the identity law: NOT B . 1 = NOT B.

Q = NOT B, so five gates collapse into a single NOT gate and input A turns out not to affect the output at all.

Exam technique

Name the law at every step of a simplification, because the marks are for the method rather than the final line.
Write one law per line and keep the expression on the left of the page so the chain is easy to follow.
If a question asks you to draw the simplified circuit, redraw it from the final expression rather than editing the original diagram.

You are given	You are asked for	Route
A written requirement	A logic diagram	Identify inputs and output, pick the gate, draw left to right
A Boolean expression	A logic diagram	One gate per operator, innermost bracket first
A logic diagram	A truth table	One column per gate, trace each row (A1.2.4)
A complex expression	A simpler diagram	Apply Boolean laws, then redraw from the final expression

Active recall