Two-place rules and the majority vote

Two-place rules. A two-place rule mentions two variables, and every two-place rule can be written as a 2-CNF: A → B is ¬A ∨ B, A = B is (¬A ∨ B) ∧ (A ∨ ¬B), and A ≠ B is (A ∨ B) ∧ (¬A ∨ ¬B). One test separates what two-place rules can say from what they cannot, and the test is a vote.

The vote. The majority of three states is the state that takes, in each variable, the value that at least two of the three take. The majority of 010, 100 and 111 is 110: A is 0, 1 and 1, so 1; B is 1, 0 and 1, so 1; and c is 0, 0 and 1, so 0.

• A 2-CNF is closed under majority: whenever it allows three states, it allows their majority. Classical (Schaefer 1978), and the reason is short. Each clause of a 2-CNF mentions at most two variables, say x and y, and rules out one combination of their values. At least two of the three states agree with the majority on x, and at least two agree with it on y, so one of the three agrees with it on both. That state is allowed, so it does not have the ruled-out combination, and neither does the majority.
• Witnesses do not help. When a system is closed under majority, so is its shadow on any set of variables: complete three allowed states of the shadow to allowed states of the system, and the majority of the completions completes the majority of the three. So a 2-CNF stays closed under majority with any witnesses forgotten.
• No knot on three variables is closed under majority. Take an excluded state of a knot, such as the atom's 110. Its three neighbours, 010, 100 and 111, are allowed (lesson 2.2), and their majority is 110 itself.

So no 2-CNF, with or without witnesses, defines the atom or any other knot on three variables. The next lesson states the general theorem, and its positive counterpart for three-place rules.