Consensus theorem
Encyclopedia
Variable inputs Function values
X Y Z xy + x'z + yz xy + 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 is a simplification of the following terms:
xy + x'z + yz = xy + x'z


Proof for this theorem is:

LHS
Sides of an equation
In mathematics, LHS is informal shorthand for the left-hand side of an equation. Similarly, RHS is the right-hand side. Each is solely a name for a term as part of an expression; and they are in practice interchangeable, since equality is symmetric...

 = xy + x'z + (x + x' )yz
= xy + x'z + xyz + x'yz
= xy + xyz + x'z + x'yz
= xy(1 + z) + x'z(1 + y)
= xy + x'z
= RHS

The dual of this equation is:
(x' + z)(y + z) = (x + y)(x' + z)

The consensus term, refers to the redundant term, (y + z). It can be derived from (x+y) and (x' +z) through the resolution
Resolution (logic)
In mathematical logic and automated theorem proving, resolution is a rule of inference leading to a refutation theorem-proving technique for sentences in propositional logic and first-order logic...

 inference rule. This shows that the LHS is derivable from the RHS (if AB then AAB; 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
Propositional calculus
In mathematical logic, a propositional calculus or logic is a formal system in which formulas of a formal language may be interpreted as representing propositions. A system of inference rules and axioms allows certain formulas to be derived, called theorems; which may be interpreted as true...

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

In digital logic, including the consensus term can eliminate race hazards.
The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK