Lesson 1.2 · Chapter 1: Bits and rules
Rules and what they allow
Read ¬, ∧, ∨, → and ⊕ by the states they rule out, and learn what makes a set of variables free.
From John Cullen’s knotlab guide
Rules and relations. A rule, or constraint, rules out some joint states. A system of rules allows exactly the states that break none of its rules. The guide reads a system only through the set of states it allows, which is called its relation. Two systems that allow the same states are the same relation, however differently they are written.
Symbols. Rules are written with these symbols:
| Written | Read aloud | Rules out |
|---|---|---|
| ¬A | not A | A = 1 |
| A ∧ B | A and B | every state except A = B = 1 |
| A ∨ B | A or B, or both | A = B = 0 |
| A → B | if A, then B | A = 1 with B = 0 |
| A = B | A equals B | A = 1 with B = 0, and A = 0 with B = 1 |
| A ≠ B | A differs from B | A = B = 0, and A = B = 1 |
| A ⊕ B ⊕ c = 0 | parity: an even number of A, B and c are 1 (⊕ is addition mod 2) | the four states with an odd number of 1s |
| not-all-equal(A, B, c) | the three are not all the same | 000 and 111 |
A warning about the arrow. The arrow causes most misreadings. A → B is the logician's "if A, then B", and it rules out one case only: A = 1 with B = 0. It says nothing when A = 0. It is not a step in time, a cause or a computation.
Clauses and CNFs. A clause is an "or" of letters, each of which may be
negated, such as ¬A ∨ ¬B ∨ c. Each letter in a clause is a literal, and the
number of literals is the clause's width. A clause rules out exactly one
assignment of its own variables, the one that makes every literal false: ¬A ∨
¬B ∨ c rules out A = 1, B = 1, c = 0 and allows the other seven states. A list
of clauses that must all hold is a CNF, and a CNF whose clauses have at
most two literals each is a 2-CNF (at most three: a 3-CNF). Every relation
can be written as a CNF, with one clause of full width for each excluded state.
On the knotlab command line, ~ stands for ¬, spaces separate the literals of
a clause, and semicolons separate clauses, so (¬A ∨ c) ∧ (¬B ∨ c) is typed ~A c; ~B c.
Free and constrained. Two words carry the rest of the guide. A set of variables is free, or unconstrained, when every combination of their values occurs in some allowed state. Otherwise it is constrained. Take A ≠ B, with a third variable c that no rule mentions. It allows 010, 011, 100 and 101, and:
- A alone is free, since A = 0 and A = 1 both occur;
- the pair A, B is constrained, since 00 and 11 never occur;
- the pair A, c is free, since 00, 01, 10 and 11 all occur.
Being free is a statement about what can happen together, not about any single state.