Entradas variables | Valores de función | |||
X | y | 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 |
En álgebra de Boole , el teorema de consenso o regla de consenso [1] es la identidad:
El consenso o resolución de los términos. y es . Es la conjunción de todos los literales únicos de los términos, excluyendo el literal que aparece innecesario en un término y negado en el otro. Si incluye un término que se niega en (o viceversa), el término consenso Es falso; en otras palabras, no existe un término de consenso.
El dual conjuntivo de esta ecuación es:
Prueba
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 ambos y y literales repetidos. Por ejemplo, el consenso de y es . [2] El consenso no está definido si hay más de una oposición.
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 se puede derivar del LHS simplemente mediante la regla de inferencia de eliminación de conjunción . Desde RHS → LHS y LHS → RHS (en cálculo proposicional ), entonces LHS = RHS (en álgebra booleana).
Aplicaciones
En á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 lógica digital , incluir el término de consenso en un circuito puede eliminar los peligros de la 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 las cláusulas en 1965 como base de su " principio de resolución ". [7] [8]
Referencias
- ^ Frank Markham Brown, Razonamiento booleano: La lógica de las ecuaciones booleanas , 2ª edición 2003, p. 44
- ^ a b Frank Markham Brown, Razonamiento booleano: La lógica de las ecuaciones booleanas , 2ª edición 2003, p. 81
- ^ M. Rafiquzzaman, Fundamentos de lógica digital y microcontroladores , sexta edición (2014), ISBN 1118855795 , p. 75
- ^ "Expresiones canónicas en álgebra booleana", Disertación, Departamento de Matemáticas, Universidad de Chicago, 1937, revisada en JCC McKinsey, The Journal of Symbolic Logic 3 : 2: 93 (junio de 1938) doi : 10.2307 / 2267634 JSTOR 2267634
- ^ Edward W. Samson, Burton E. Mills, Centro de investigación de Cambridge de la fuerza aérea, Informe técnico 54-21, abril de 1954
- ^ Willard van Orman Quine , "El problema de simplificar las funciones de verdad", American Mathematical Monthly 59 : 521-531, 1952 JSTOR 2308219
- ^ John Alan Robinson , "Una lógica orientada a la máquina basada en el principio de resolución", Diario del ACM 12 : 1: 23–41.
- ^ Donald Ervin Knuth , El arte de la programación informática 4A : Algoritmos combinatorios , parte 1, p. 539
Otras lecturas
- Roth, Charles H. Jr. y Kinney, Larry L. (2004, 2010). "Fundamentos del Diseño Lógico", 6ª Ed., P. 66ff.