Binary and Boolean logic
Introduced| English | Meaning |
|---|---|
| Boolean algebra/ˈbuːlɪən ˈældʒɪbrə/ | A mathematical system for combining and manipulating true-or-false values using logical operations. |
| bit/bɪt/ | A binary digit, taking the value zero or one. |
| binary arithmetic/ˈbaɪnəri əˈrɪθmətɪk/ | binary arithmetic |
| byte/baɪt/ | A group of eight bits, commonly used as a unit of data storage. |
| truth table/truːθ ˈteɪbl/ | A table listing the output of a logical expression or circuit for every combination of inputs. |
| logic gate/ˈlɒdʒɪk ɡeɪt/ | A device or operation that applies a Boolean rule to one or more inputs to produce an output. |
| logic circuit/ˈlɒdʒɪk ˈsɜːkɪt/ | A combination of logic gates connected to implement a Boolean function. |
A two-value rule can still have several inputs
- Boolean algebra 布尔代数 uses true and false with operations such as AND, inclusive OR and NOT.
- A processor can implement arithmetic using digital logic. Abstract Boolean reasoning examines a stated input/output rule, rather than proving every detail of a real computer.
Keep bit arithmetic and truth values distinct
- Binary arithmetic 二进制运算 carries at 2: binary $1+1=10$. A bit 位 is one binary digit and a byte 字节 is eight bits.
- A bit pattern can encode an unsigned value, a signed value or other information. Specify its width and interpretation before calling its value 255 or inverting it.
In binary, what is 1 + 1?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
There is no digit for two, so it carries — the same rule as 9 + 1 in decimal.
Evaluate every Boolean combination
- A truth table 真值表 for n unrestricted Boolean inputs has $2^n$ rows. Include intermediate expressions to make grouping visible.
- Identical outputs in every row prove two expressions equivalent for those Boolean inputs. That does not establish circuit timing, authentication security or physical reliability.
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?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
2³ = 8. Every input doubles the number of combinations.
Two Boolean expressions have identical truth tables. What follows?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Matching every row over the same Boolean inputs proves abstract Boolean equivalence. It does not establish physical timing or real-system security.
A complete two-input table. In row order 00, 01, 10, 11, AND outputs 0, 0, 0, 1; inclusive OR outputs 0, 1, 1, 1; NOT A outputs 1, 1, 0, 0. A single matching row is not enough to prove two expressions equivalent.
"A AND B" is true on exactly one row of its truth table.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Only the row where both inputs are 1. That single row is the whole definition.
Follow connections through the circuit
- A logic gate 逻辑门 implements a specified operation. A logic circuit 逻辑电路 connects those operations, with outputs feeding later inputs.
- Build intermediate columns according to that dependency order. De Morgan can rewrite NOT of an AND as OR of the negated inputs, but must negate both inputs.
Simplify and verify separately. $(A\land B)\lor(A\land\neg B)=A$ by distributivity and $B\lor\neg B$ being true. Sheet 4.3 checks all four rows and separately tests fixed-width bitwise operations.
In logic, when is "A OR B" false?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Inclusive OR is false only when both inputs are false. Both true gives true; this question uses inclusive OR explicitly.
Inclusive OR is true when both inputs are true. Bitwise NOT inverts only the stated positions: four-bit NOT of 1100 is 0011, unsigned 3, rather than an unspecified signed or infinite-width value.