Consensus theorem

In Boolean algebra, the consensus theorem or rule of consensus^[1] is the identity:

${\displaystyle xy\vee {\bar {x}}z\vee yz=xy\vee {\bar {x}}z}${\displaystyle xy\vee {\bar {x}}z\vee yz=xy\vee {\bar {x}}z}

The consensus or resolvent of the terms ${\displaystyle xy}${\displaystyle xy} and ${\displaystyle {\bar {x}}z}${\displaystyle {\bar {x}}z} is ${\displaystyle yz}${\displaystyle yz}. It is the conjunction of all the unique literals of the terms, excluding the literal that appears unnegated in one term and negated in the other. If ${\displaystyle y}${\displaystyle y} includes a term that is negated in ${\displaystyle z}${\displaystyle z} (or vice versa), the consensus term ${\displaystyle yz}${\displaystyle yz} is false; in other words, there is no consensus term.

The conjunctive dual of this equation is:

${\displaystyle (x\vee y)({\bar {x}}\vee z)(y\vee z)=(x\vee y)({\bar {x}}\vee z)}${\displaystyle (x\vee y)({\bar {x}}\vee z)(y\vee z)=(x\vee y)({\bar {x}}\vee z)}

${\displaystyle {\begin{aligned}xy\vee {\bar {x}}z\vee yz&=xy\vee {\bar {x}}z\vee (x\vee {\bar {x}})yz\\&=xy\vee {\bar {x}}z\vee xyz\vee {\bar {x}}yz\\&=(xy\vee xyz)\vee ({\bar {x}}z\vee {\bar {x}}yz)\\&=xy(1\vee z)\vee {\bar {x}}z(1\vee y)\\&=xy\vee {\bar {x}}z\end{aligned}}}${\displaystyle {\begin{aligned}xy\vee {\bar {x}}z\vee yz&=xy\vee {\bar {x}}z\vee (x\vee {\bar {x}})yz\\&=xy\vee {\bar {x}}z\vee xyz\vee {\bar {x}}yz\\&=(xy\vee xyz)\vee ({\bar {x}}z\vee {\bar {x}}yz)\\&=xy(1\vee z)\vee {\bar {x}}z(1\vee y)\\&=xy\vee {\bar {x}}z\end{aligned}}}

The consensus or consensus term of two conjunctive terms of a disjunction is defined when one term contains the literal ${\displaystyle a}${\displaystyle a} and the other the literal ${\displaystyle {\bar {a}}}${\displaystyle {\bar {a}}}, an opposition. The consensus is the conjunction of the two terms, omitting both ${\displaystyle a}${\displaystyle a} and ${\displaystyle {\bar {a}}}${\displaystyle {\bar {a}}}, and repeated literals. For example, the consensus of ${\displaystyle {\bar {x}}yz}${\displaystyle {\bar {x}}yz} and ${\displaystyle w{\bar {y}}z}${\displaystyle w{\bar {y}}z} is ${\displaystyle w{\bar {x}}z}${\displaystyle w{\bar {x}}z}.^[2] The consensus is undefined if there is more than one opposition.

For the conjunctive dual of the rule, the consensus ${\displaystyle y\vee z}${\displaystyle y\vee z} can be derived from ${\displaystyle (x\vee y)}${\displaystyle (x\vee y)} and ${\displaystyle ({\bar {x}}\vee z)}${\displaystyle ({\bar {x}}\vee z)} through the resolution inference rule. This shows that the LHS is derivable from the RHS (if A → B then A → AB; replacing A with RHS and B with (y ∨ z) ). The RHS can be derived from the LHS simply through the conjunction elimination inference rule. Since RHS → LHS and LHS → RHS (in propositional calculus), then LHS = RHS (in Boolean algebra).

In Boolean algebra, repeated consensus is the core of one algorithm for calculating the Blake canonical form of a formula.^[2]

In digital logic, including the consensus term in a circuit can eliminate race hazards.^[3]

The concept of consensus was introduced by Archie Blake in 1937, related to the Blake canonical form.^[4] It was rediscovered by Samson and Mills in 1954^[5] and by Quine in 1955.^[6] Quine coined the term 'consensus'. Robinson used it for clauses in 1965 as the basis of his "resolution principle".^{[7] [8]}

• Roth, Charles H. Jr. and Kinney, Larry L. (2004, 2010). "Fundamentals of Logic Design", 6th Ed., p. 66ff.

• Boolean algebra
• Theorems in lattice theory
• Theorems in propositional logic

• Articles with short description
• Short description is different from Wikidata