J u m p t o c o n t e n t
M a i n m e n u
M a i n m e n u
N a v i g a t i o n
● M a i n p a g e
● C o n t e n t s
● C u r r e n t e v e n t s
● R a n d o m a r t i c l e
● A b o u t W i k i p e d i a
● C o n t a c t u s
● D o n a t e
C o n t r i b u t e
● H e l p
● L e a r n t o e d i t
● C o m m u n i t y p o r t a l
● R e c e n t c h a n g e s
● U p l o a d f i l e
S e a r c h
Search
A p p e a r a n c e
● C r e a t e a c c o u n t
● L o g i n
P e r s o n a l t o o l s
● C r e a t e a c c o u n t
● L o g i n
P a g e s f o r l o g g e d o u t e d i t o r s l e a r n m o r e
● C o n t r i b u t i o n s
● T a l k
( T o p )
1
P r o o f
2
C o n s e n s u s
3
A p p l i c a t i o n s
4
H i s t o r y
5
R e f e r e n c e s
6
F u r t h e r r e a d i n g
T o g g l e t h e t a b l e o f c o n t e n t s
C o n s e n s u s t h e o r e m
8 l a n g u a g e s
● E s p a ñ o l
● ف ا ر س ی
● F r a n ç a i s
● Հ ա յ ե ր ե ն
● I t a l i a n o
● Р у с с к и й
● T ü r k ç e
● Z a z a k i
E d i t l i n k s
● A r t i c l e
● T a l k
E n g l i s h
● R e a d
● E d i t
● V i e w h i s t o r y
T o o l s
T o o l s
A c t i o n s
● R e a d
● E d i t
● V i e w h i s t o r y
G e n e r a l
● W h a t l i n k s h e r e
● R e l a t e d c h a n g e s
● U p l o a d f i l e
● S p e c i a l p a g e s
● P e r m a n e n t l i n k
● P a g e i n f o r m a t i o n
● C i t e t h i s p a g e
● G e t s h o r t e n e d U R L
● D o w n l o a d Q R c o d e
● W i k i d a t a i t e m
P r i n t / e x p o r t
● D o w n l o a d a s P D F
● P r i n t a b l e v e r s i o n
A p p e a r a n c e
F r o m W i k i p e d i a , t h e f r e e e n c y c l o p e d i a
Theorem in Boolean algebra
Variable inputs
Function values
x
y
z
x
y
∨
x
¯
z
∨
y
z
{\displaystyle xy\vee {\bar {x}}z\vee yz}
x
y
∨
x
¯
z
{\displaystyle 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
Karnaugh map of AB ∨ A C ∨ BC . Omitting the red rectangle does not change the covered area.
In Boolean algebra , the consensus theorem or rule of consensus [1] is the identity:
x
y
∨
x
¯
z
∨
y
z
=
x
y
∨
x
¯
z
{\displaystyle xy\vee {\bar {x}}z\vee yz=xy\vee {\bar {x}}z}
The consensus or resolvent of the terms
x
y
{\displaystyle xy}
and
x
¯
z
{\displaystyle {\bar {x}}z}
is
y
z
{\displaystyle 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
{\displaystyle y}
includes a term that is negated in
z
{\displaystyle z}
(or vice versa), the consensus term
y
z
{\displaystyle yz}
is false; in other words, there is no consensus term.
The conjunctive dual of this equation is:
(
x
∨
y
)
(
x
¯
∨
z
)
(
y
∨
z
)
=
(
x
∨
y
)
(
x
¯
∨
z
)
{\displaystyle (x\vee y)({\bar {x}}\vee z)(y\vee z)=(x\vee y)({\bar {x}}\vee z)}
x
y
∨
x
¯
z
∨
y
z
=
x
y
∨
x
¯
z
∨
(
x
∨
x
¯
)
y
z
=
x
y
∨
x
¯
z
∨
x
y
z
∨
x
¯
y
z
=
(
x
y
∨
x
y
z
)
∨
(
x
¯
z
∨
x
¯
y
z
)
=
x
y
(
1
∨
z
)
∨
x
¯
z
(
1
∨
y
)
=
x
y
∨
x
¯
z
{\displaystyle {\begin{aligned}xy\vee {\bar {x}}z\vee yz&=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\end{aligned}}}
Consensus [ edit ]
The consensus or consensus term of two conjunctive terms of a disjunction is defined when one term contains the literal
a
{\displaystyle a}
and the other the literal
a
¯
{\displaystyle {\bar {a}}}
, an opposition . The consensus is the conjunction of the two terms, omitting both
a
{\displaystyle a}
and
a
¯
{\displaystyle {\bar {a}}}
, and repeated literals. For example, the consensus of
x
¯
y
z
{\displaystyle {\bar {x}}yz}
and
w
y
¯
z
{\displaystyle w{\bar {y}}z}
is
w
x
¯
z
{\displaystyle w{\bar {x}}z}
.[2] The consensus is undefined if there is more than one opposition.
For the conjunctive dual of the rule, the consensus
y
∨
z
{\displaystyle y\vee z}
can be derived from
(
x
∨
y
)
{\displaystyle (x\vee y)}
and
(
x
¯
∨
z
)
{\displaystyle ({\bar {x}}\vee z)}
through the resolution 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 ), then LHS = RHS (in Boolean algebra).
Applications [ edit ]
In Boolean algebra, repeated consensus is the core of one algorithm for calculating the Blake canonical form of a formula.[2]
In digital logic , including the consensus term in a circuit can eliminate race hazards .[3]
History [ edit ]
The concept of consensus was introduced by Archie Blake in 1937, related to the Blake canonical form .[4] It was rediscovered by Samson and Mills in 1954[5] and by Quine in 1955.[6] Quine coined the term 'consensus'. Robinson used it for clauses in 1965 as the basis of his "resolution principle ".[7] [8]
References [ edit ]
^ a b Frank Markham Brown, Boolean Reasoning: The Logic of Boolean Equations , 2nd edition 2003, p. 81
^ Rafiquzzaman, Mohamed (2014). Fundamentals of Digital Logic and Microcontrollers (6 ed.). p. 65. ISBN 1118855795 .
^ "Canonical expressions in Boolean algebra", Dissertation, Department of Mathematics, University of Chicago, 1937, ProQuest 301838818 , reviewed in J. C. C. McKinsey, The Journal of Symbolic Logic 3 :2:93 (June 1938) doi :10.2307/2267634 JSTOR 2267634 . The consensus function is denoted
σ
{\displaystyle \sigma }
and defined on pp. 29–31.
^ Edward W. Samson, Burton E. Mills, Air Force Cambridge Research Center, Technical Report 54-21, April 1954
^ Willard van Orman Quine , "The problem of simplifying truth functions", American Mathematical Monthly 59 :521-531, 1952 JSTOR 2308219
^ John Alan Robinson , "A Machine-Oriented Logic Based on the Resolution Principle", Journal of the ACM 12 :1: 23–41.
^ Donald Ervin Knuth , The Art of Computer Programming 4A : Combinatorial Algorithms , part 1, p. 539
Further reading [ edit ]
Roth, Charles H. Jr. and Kinney, Larry L. (2004, 2010). "Fundamentals of Logic Design", 6th Ed., p. 66ff.
R e t r i e v e d f r o m " https://en.wikipedia.org/w/index.php?title=Consensus_theorem&oldid=1230035177 "
C a t e g o r i e s :
● B o o l e a n a l g e b r a
● T h e o r e m s i n l a t t i c e t h e o r y
● T h e o r e m s i n p r o p o s i t i o n a l l o g i c
H i d d e n c a t e g o r i e s :
● A r t i c l e s w i t h s h o r t d e s c r i p t i o n
● S h o r t d e s c r i p t i o n i s d i f f e r e n t f r o m W i k i d a t a
● T h i s p a g e w a s l a s t e d i t e d o n 2 0 J u n e 2 0 2 4 , a t 0 6 : 0 5 ( U T C ) .
● T e x t i s a v a i l a b l e u n d e r t h e C r e a t i v e C o m m o n s A t t r i b u t i o n - S h a r e A l i k e L i c e n s e 4 . 0 ;
a d d i t i o n a l t e r m s m a y a p p l y . B y u s i n g t h i s s i t e , y o u a g r e e t o t h e T e r m s o f U s e a n d P r i v a c y P o l i c y . W i k i p e d i a ® i s a r e g i s t e r e d t r a d e m a r k o f t h e W i k i m e d i a F o u n d a t i o n , I n c . , a n o n - p r o f i t o r g a n i z a t i o n .
● P r i v a c y p o l i c y
● A b o u t W i k i p e d i a
● D i s c l a i m e r s
● C o n t a c t W i k i p e d i a
● C o d e o f C o n d u c t
● D e v e l o p e r s
● S t a t i s t i c s
● C o o k i e s t a t e m e n t
● M o b i l e v i e w