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 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
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.