Boolean algebra In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas in e ...

, the consensus theorem or rule of consensus is the identity: :

xy \vee \barz \vee yz = xy \vee \barz

The consensus or resolvent of the terms

xy

and

\barz

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

y

includes a term which is negated in

z

(or vice versa), the consensus term

yz

is false; in other words, there is no consensus term. The conjunctive dual of this equation is: :

(x \vee y)(\bar \vee z)(y \vee z) = (x \vee y)(\bar \vee z)

Proof

\begin
     xy \vee \barz \vee yz &=  xy \vee \barz \vee (x \vee \bar)yz \\
            &=  xy \vee \barz \vee xyz \vee \baryz \\
            &=  (xy \vee xyz) \vee (\barz \vee \baryz) \\
            &= xy(1\vee z)\vee\barz(1\vee y) \\
            &=  xy \vee \barz
      \end

Consensus

The consensus or consensus term of two conjunctive terms of a disjunction is defined when one term contains the literal

a

and the other the literal

\bar

, an opposition. The consensus is the conjunction of the two terms, omitting both

a

and

\bar

, and repeated literals. For example, the consensus of

\baryz

and

w\barz

w\barz

.Frank Markham Brown, ''Boolean Reasoning: The Logic of Boolean Equations'', 2nd edition 2003, p. 81 The consensus is undefined if there is more than one opposition. For the conjunctive dual of the rule, the consensus

y \vee z

can be derived from

(x\vee y)

and

(\bar \vee z)

through the

resolution Resolution(s) may refer to: Common meanings * Resolution (debate), the statement which is debated in policy debate * Resolution (law), a written motion adopted by a deliberative body * New Year's resolution, a commitment that an individual mak ...

inference rule In the philosophy of logic, a rule of inference, inference rule or transformation rule is a logical form consisting of a function which takes premises, analyzes their syntax, and returns a conclusion (or conclusions). For example, the rule of ...

. 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 In propositional logic, conjunction elimination (also called ''and'' elimination, ∧ elimination, or simplification)Hurley is a valid immediate inference, argument form and rule of inference which makes the inference that, if the conjunction ' ...

inference rule. Since RHS → LHS and LHS → RHS (in

propositional calculus Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...

), then LHS = RHS (in Boolean algebra).

Applications

In Boolean algebra, repeated consensus is the core of one algorithm for calculating the

Blake canonical form In Boolean logic, a formula for a Boolean function ''f'' is in Blake canonical form (BCF), also called the complete sum of prime implicants, the complete sum, or the disjunctive prime form, when it is a disjunction of all the prime implicants of ...

of a formula. In

digital logic A logic gate is an idealized or physical device implementing a Boolean function, a logical operation performed on one or more Binary number, binary inputs that produces a single binary output. Depending on the context, the term may refer to an id ...

, including the consensus term in a circuit can eliminate

race hazard A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events. It becomes a bug when one or more of ...

History

The concept of consensus was introduced by Archie Blake in 1937, related to the

."Canonical expressions in Boolean algebra", Dissertation, Department of Mathematics, University of Chicago, 1937, reviewed in J. C. C. McKinsey, ''The Journal of Symbolic Logic'' 3:2:93 (June 1938) It was rediscovered by Samson and Mills in 1954 and by Quine in 1955. Quine coined the term 'consensus'.

Robinson Robinson may refer to: People and names * Robinson (name) Fictional characters * Robinson Crusoe, the main character, and title of a novel by Daniel Defoe, published in 1719 Geography * Robinson projection, a map projection used since the 1960 ...

used it for clauses in 1965 as the basis of his " resolution principle".

Donald Ervin Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...

, ''

The Art of Computer Programming ''The Art of Computer Programming'' (''TAOCP'') is a comprehensive monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. Volumes 1–5 are intended to represent the central core of com ...

'' 4A: ''Combinatorial Algorithms'', part 1, p. 539

Proof

Consensus

Applications

History

References

Further reading