词条 | Consensus theorem | ||||||||||||||||||||||||||||||||||||||||||||||||||
释义 |
In Boolean algebra, the consensus theorem or rule of consensus[1] is the identity: The consensus or resolvent of the terms and is . 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 includes a term which is negated in (or vice versa), the consensus term is false; in other words, there is no consensus term. The conjunctive dual of this equation is: ProofConsensus{{anchor|Consensus}}{{anchor|Opposition}}The consensus or consensus term of two conjunctive terms of a disjunction is defined when one term contains the literal and the other the literal , an opposition. The consensus is the conjunction of the two terms, omitting both and , and repeated literals. For example, the consensus of and is .[2] The consensus is undefined if there is more than one opposition. For the conjunctive dual of the rule, the consensus can be derived from and 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). ApplicationsIn 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] HistoryThe 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] References1. ^Frank Markham Brown, Boolean Reasoning: The Logic of Boolean Equations, 2nd edition 2003, p. 44 2. ^1 Frank Markham Brown, Boolean Reasoning: The Logic of Boolean Equations, 2nd edition 2003, p. 81 3. ^M. Rafiquzzaman, Fundamentals of Digital Logic and Microcontrollers, 6th edition (2014), {{ISBN|1118855795}}, p. 75 4. ^"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) {{DOI|10.2307/2267634}} {{jstor|2267634}} 5. ^Edward W. Samson, Burton E. Mills, Air Force Cambridge Research Center, Technical Report 54-21, April 1954 6. ^Willard van Orman Quine, "The problem of simplifying truth functions", American Mathematical Monthly 59:521-531, 1952 {{jstor|2308219}} 7. ^John Alan Robinson, "A Machine-Oriented Logic Based on the Resolution Principle", Journal of the ACM 12:1: 23–41. 8. ^Donald Ervin Knuth, The Art of Computer Programming 4A: Combinatorial Algorithms, part 1, p. 539 Further reading
2 : Boolean algebra|Theorems in propositional logic |
||||||||||||||||||||||||||||||||||||||||||||||||||
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。