Teorema de consenso

Teorema del álgebra de Boole

Mapa de Karnaugh de AB ∨ A C ∨ BC . Omitir el rectángulo rojo no cambia el área cubierta.

En el álgebra de Boole , el teorema de consenso o regla de consenso ^[1] es la identidad:

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

El consenso o resolutivo de los términos y es . Es la conjunción de todos los literales únicos de los términos, excluyendo el literal que aparece no negado en un término y negado en el otro. Si incluye un término que se niega en (o viceversa), el término de consenso es falso; en otras palabras, no hay término de consenso. ${\displaystyle xy}$ ${\displaystyle {\bar {x}}z}$ ${\displaystyle yz}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle yz}$

El dual conjuntivo de esta ecuación es:

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

Prueba

${\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}}}$

Consenso

El consenso o término de consenso de dos términos conjuntivos de una disyunción se define cuando un término contiene el literal y el otro el literal , una oposición . El consenso es la conjunción de los dos términos, omitiendo tanto y , como los literales repetidos. Por ejemplo, el consenso de y es . ^[2] El consenso es indefinido si hay más de una oposición. ${\displaystyle a}$ ${\displaystyle {\bar {a}}}$ ${\displaystyle a}$ ${\displaystyle {\bar {a}}}$ ${\displaystyle {\bar {x}}yz}$ ${\displaystyle w{\bar {y}}z}$ ${\displaystyle w{\bar {x}}z}$

Para el dual conjuntivo de la regla, el consenso puede derivarse de y a través de la regla de inferencia de resolución . Esto muestra que el LHS es derivable del RHS (si A → B entonces A → AB ; reemplazando A con RHS y B con ( y ∨ z ) ). El RHS puede derivarse del LHS simplemente a través de la regla de inferencia de eliminación de conjunción . Dado que RHS → LHS y LHS → RHS (en cálculo proposicional ), entonces LHS = RHS (en álgebra de Boole). ${\displaystyle y\vee z}$ ${\displaystyle (x\vee y)}$ ${\displaystyle ({\bar {x}}\vee z)}$

Aplicaciones

En el álgebra de Boole, el consenso repetido es el núcleo de un algoritmo para calcular la forma canónica de Blake de una fórmula. ^[2]

En la lógica digital , incluir el término de consenso en un circuito puede eliminar los riesgos de carrera . ^[3]

Historia

El concepto de consenso fue introducido por Archie Blake en 1937, relacionado con la forma canónica de Blake . ^[4] Fue redescubierto por Samson y Mills en 1954 ^[5] y por Quine en 1955. ^[6] Quine acuñó el término "consenso". Robinson lo utilizó para cláusulas en 1965 como base de su " principio de resolución ". ^{[7] [8]}

Referencias

1. Frank Markham Brown  [d] , Razonamiento booleano: la lógica de las ecuaciones booleanas , 2.ª edición, 2003, pág. 44
2. Frank Markham Brown, Razonamiento booleano: la lógica de las ecuaciones booleanas , 2.ª edición, 2003, pág. 81
3. Rafiquzzaman, Mohamed (2014). Fundamentos de lógica digital y microcontroladores (6.ª ed.). pág. 65. ISBN 1118855795.
4. "Expresiones canónicas en álgebra de Boole", Tesis, Departamento de Matemáticas, Universidad de Chicago, 1937, ProQuest  301838818, reseñado en JCC McKinsey, The Journal of Symbolic Logic 3 :2:93 (junio de 1938) doi :10.2307/2267634 JSTOR  2267634. ​​La función de consenso se denota y define en las páginas 29-31. ${\displaystyle \sigma }$
5. Edward W. Samson, Burton E. Mills, Centro de Investigación de la Fuerza Aérea de Cambridge, Informe técnico 54-21, abril de 1954
6. Willard van Orman Quine , "El problema de simplificar las funciones de verdad", American Mathematical Monthly 59 :521-531, 1952 JSTOR  2308219
7. John Alan Robinson , "Una lógica orientada a máquinas basada en el principio de resolución", Journal of the ACM 12 :1: 23–41.
8. Donald Ervin Knuth , El arte de la programación informática 4A : Algoritmos combinatorios , parte 1, pág. 539

Lectura adicional

• Roth, Charles H. Jr. y Kinney, Larry L. (2004, 2010). "Fundamentos del diseño lógico", 6.ª edición, pág. 66 y siguientes.