Writing a circuit as an expression
Three notations for the same circuit, the order operators are applied in, and going between words and symbols.
Why write it down at all
A drawing of a circuit is a good way to see it and a poor way to think about it. Two drawings can be the same circuit with the gates shuffled about, and you would not spot it. Drawings cannot be compared, checked or made smaller by any rule you could write down. Text can. So the first move in this stage is to stop drawing gates and start writing them, as an expression: a single line of symbols that says exactly what a circuit computes.
Three ways of writing the same thing
Three groups of people use boolean algebra, and each writes it their own way. Logicians and maths books write AND as ∧, OR as ∨ and NOT as ¬ in front of the thing it inverts. Engineers write AND by putting the letters side by side, OR as a plus sign, and NOT as a bar drawn over the top of whatever is inverted; since a bar is hard to type, this site writes that bar as a prime, so a with a bar over it appears as a'. Programmers write AND as &&, OR as || and NOT as !, and the single characters & and | are accepted too, so a & b | !c is fine. Type any of them into the tools on this site, or the words and, or and not, and they are all read the same way.
Each row says the same thing: "a and b, or not c". It is one idea in three costumes, and it is worth being able to read all three, because you will meet each of them.
Why?: why three notations?
Because three different trades arrived at the same algebra from different directions. The maths symbols came from logic, the plus and the bar from the engineers who first drew circuits with them, and the programming symbols from the languages that needed them on a keyboard. None is better. The engineering one is the shortest, which is why textbooks and data sheets lean on it; the maths one is what the reference pages on this site use, and the programming one is the easiest to type into the tools.
The order of operations
In arithmetic, 2 + 3 × 4 is 14, not 20, because multiplication is done before addition. Boolean algebra has the same kind of rule. NOT is done first, then AND, then OR. So a ∧ b ∨ c means "a and b, or c": the AND happens first, and the OR joins its result with c. It is no accident that engineers write AND like multiplication and OR like addition; the order is the same as the one you already know.
When you want a different order, you write brackets, exactly as in arithmetic. a ∧ (b ∨ c) means "a, and at least one of b and c", which is a different circuit. Try the expression below. It has two AND parts joined by an OR, and the NOTs apply only to the single letter after them.
Common mistake: reading a ∧ b ∨ c as a ∧ (b ∨ c)
Without brackets, AND grabs only its neighbours. In a ∧ b ∨ c the AND joins a and b and nothing else; c stands on its own, joined to the rest by the OR. Set a to 0 and c to 1: the unbracketed form gives 1, because c alone is enough, while a ∧ (b ∨ c) gives 0, because a is required. If you are ever unsure, write the brackets in. They are never wrong, only sometimes unnecessary.
From a circuit to an expression, and back
To write down a circuit, start at the output and work backwards. The last gate before the output is the outermost operation of the expression, and each of its inputs is either a plain input name or a smaller circuit, which you write the same way. To build a circuit from an expression, do the reverse: the outermost operation is the last gate, and each part inside it is a gate before it. Brackets appear wherever the order of operations would otherwise split something that belongs together.
Worked example. An OR gate takes a and b. Its output and c go into an AND gate, and the AND gate's output goes through a NOT gate. Write the expression for the final output.
The OR gate gives a ∨ b. The AND gate joins that whole result with c, so it needs brackets round the OR, or the AND would grab only b: (a ∨ b) ∧ c. The NOT gate inverts all of that, so it needs brackets round everything: ¬((a ∨ b) ∧ c). Reading it back, the outermost operation is the NOT, which is the last gate; inside it is the AND, the gate before; and inside that is the OR, the first gate. Three gates, three operations.
Reading a value off an expression
To find what an expression gives for particular inputs, replace each letter with its value and work from the inside out: NOTs first, then ANDs, then ORs, and anything in brackets before the thing outside it. Take a ∧ ¬b ∨ ¬a ∧ c with a = 1, b = 0 and c = 1. The NOTs first: ¬b is 1 and ¬a is 0. Then the ANDs: 1 ∧ 1 is 1 and 0 ∧ 1 is 0. Then the OR: 1 ∨ 0 is 1. That is exactly what the widget above does for whichever row you have clicked, and a truth table is nothing more than this done for every row.
What to remember
- An expression is a circuit written as text, using AND, OR, NOT and brackets.
- Maths writes ∧ ∨ ¬, engineering writes ab + c with a bar (a prime here), programming writes && || !.
- NOT is done first, then AND, then OR. Brackets change that order.
- The last gate before the output is the outermost operation of the expression.
- To evaluate, put the values in and work from the inside out.
Build it: a circuit from an expression in the simulator.
Check yourself
Get 5 right in a row and the lesson is done. A wrong answer costs the run, not the lesson.
An OR gate takes d and b, and its output goes through a NOT gate. What is the expression for the NOT gate's output?
Already know this? and come back to the quiz any time.