HOME

TheInfoList



OR:

In
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 i ...
, 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 is 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 is 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 m ...
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 i ...
. 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 o ...
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 inputs that produces a single binary output. Depending on the context, the term may refer to an ideal logic gat ...
, 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 ...
s.


History

The concept of consensus was introduced by Archie Blake in 1937, related to 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 o ...
."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 1960s ...
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 s ...
, ''
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 comp ...
'' 4A: ''Combinatorial Algorithms'', part 1, p. 539


References


Further reading

* Roth, Charles H. Jr. and Kinney, Larry L. (2004, 2010). "Fundamentals of Logic Design", 6th Ed., p. 66ff. {{DEFAULTSORT:Consensus Theorem Boolean algebra Theorems in lattice theory Theorems in propositional logic