Consensus theorem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Variable inputs Function values
x y z xy \vee \bar{x}z \vee yz xy \vee \bar{x}z
0 0 0 0 0
0 0 1 1 1
0 1 0 0 0
0 1 1 1 1
1 0 0 0 0
1 0 1 0 0
1 1 0 1 1
1 1 1 1 1

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

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

The consensus or resolvent of the terms xy and \bar{x}z is yz. It is the conjunction of all the unique literals of the terms, excluding the literal which appears unnegated in one term and negated in the other.

The conjunctive dual of this equation is:

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

Proof[edit]

   LHS = 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
       = RHS

Consensus[edit]

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{a}, an opposition. The consensus is the conjunction of the two terms, omitting both a and \bar{a}, and repeated literals; the consensus is undefined if there is more than one opposition. For example, the consensus of \bar{x}yz and w\bar{y}z is w\bar{x}z.[2]

The consensus can be derived from (x\vee y) and (\bar{x} \vee z) through the resolution inference rule. This shows that the LHS is derivable from the RHS (if AB then AAB; replacing A with RHS and B with (yz) ). 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).

Digital logic circuitry[edit]

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

History[edit]

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

Notes[edit]

  1. ^ Frank Markham Brown, Boolean Reasoning: The Logic of Boolean Equations, 2nd edition 2003, p. 44
  2. ^ Frank Markham Brown, Boolean Reasoning: The Logic of Boolean Equations, 2nd edition 2003, p. 81
  3. ^ "Canonical expressions in Boolean algebra", Dissertation, Dept. of Mathematics, U. of Chicago, 1937, reviewed in J. C. C. McKinsey, The Journal of Symbolic Logic 3:2:93 (June 1938) doi:10.2307/2267634 JSTOR 2267634
  4. ^ Edward W. Samson, Burton E. Mills, Air Force Cambridge Research Center Technical Report 54-21, April 1954
  5. ^ W.V. Quine, "The problem of simplifying truth functions", American Mathematical Monthly 59:521-531, 1952
  6. ^ J. Alan Robinson, "A Machine-Oriented Logic Based on the Resolution Principle", Journal of the ACM 12:1: 23–41.
  7. ^ D.E. Knuth, The Art of Computer Programming 4A: Combinatorial Algorithms, part 1, p. 539

References[edit]

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