Teorema de consenso

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. ${\estilo de visualización xy}$${\displaystyle {\bar {x}}z}$${\estilo de visualización yz}$${\estilo de visualización y}$${\estilo de visualización z}$${\estilo de visualización 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)}$

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

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. ${\estilo de visualización a}$${\displaystyle {\bar {a}}}$${\estilo de visualización 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)}$

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]

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]}

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