Binary and Boolean logic
| English | Chinese | Pinyin |
|---|---|---|
| Boolean algebra | 布尔代数 | bù ěr dài shù |
| binary arithmetic | 二进制运算 | èr jìn zhì yùn suàn |
| bit | 位 | wèi |
| byte | 字节 | zì jié |
| truth table | 真值表 | zhēn zhí biǎo |
| logic gate | 逻辑门 | luó jí mén |
| logic circuit | 逻辑电路 | luó jí diàn lù |
True, false, and the machine underneath
- A processor cannot add. It can only combine trues and falses, billions of times a second.
- Boolean algebra 布尔代数 is the mathematics of those two values, with AND, OR and NOT.
- Everything a computer does is built from them, which is why discrete mathematics sits beside the computing modules.
Binary arithmetic
- Binary arithmetic 二进制运算 works like decimal, but carries at 2 instead of at 10.
- $1 + 1 = 10$ in binary: no digit for two, so it carries.
- A bit 位 is one binary digit; a byte 字节 is eight, which is why 255 keeps appearing.
In binary, what is 1 + 1?
There is no digit for two, so it carries — the same rule as 9 + 1 in decimal.
Truth tables
- A truth table 真值表 lists every input combination and the output for each.
- With $n$ inputs there are $2^n$ rows — two inputs give four, three give eight.
- It is a complete proof: if two expressions have the same truth table, they are equivalent for every possible input, with nothing left to check.
Flip the inputs and watch the output
AND is true only when both are; OR is false only when neither is.
How many rows does a truth table with three inputs have?
2³ = 8. Every input doubles the number of combinations.
Two Boolean expressions have identical truth tables. What follows?
The inputs are finite, so checking them all is a complete proof rather than evidence.
AND, OR and NOT, in one table.
| A | B | A AND B | A OR B | NOT A |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 |
AND is 1 only on the last row; OR is 0 only on the first. Reading those two sentences off the table is faster than remembering the definitions, and it is what the table is for.
"A AND B" is true on exactly one row of its truth table.
Only the row where both inputs are 1. That single row is the whole definition.
Logic gates and circuits
- A logic gate 逻辑门 is the physical form of a Boolean operation.
- A logic circuit 逻辑电路 wires gates together, and its behaviour is found by tracing signals through it.
- To analyse a circuit, build the truth table column by column: one column per gate, in the order the signals arrive.
A truth table settles any Boolean question completely. There are only finitely many inputs, so checking them all is a proof, not evidence. Nothing else in this module gives you certainty that cheaply.
In logic, when is "A OR B" false?
Logical OR is inclusive, so both being true still makes it true. Everyday "or" usually is not.
"OR" in logic is inclusive: A OR B is true when both are true. Everyday English usually means "one or the other, not both", and that mismatch is the most reliable trap in the unit.