Dada una tabla de verdad, es bastante sencillo imprimir una expresión booleana que sea “técnicamente correcta” (aunque explicaré en breve por qué uno desearía un poco más que la expresión booleana ingenua).
Trabajaré con ejemplos triviales y luego con un ejemplo más difícil, con suerte le dará una idea de cómo abordar este tipo de problema:
Aquí hay una tabla de verdad simple (estoy usando 1 = verdadero, 0 = falso):
- ¿Cuál es la respuesta a la pregunta (ab) ^ 3?
- ¿Se puede predecir la lotería entendiendo la psicología del número?
- ¿Cómo debo convertirme en un genio matemático en la clase 11?
- ¿Cuál podría ser la razón científica detrás del coeficiente intelectual extraordinario de Srinivasa Ramanujan (que lo había hecho dominar la trigonometría avanzada cuando tenía solo 12 años y comenzar a investigar los números de Bernouli a la edad de 17 años sin mucha "orientación")?
- Cómo encontrar el valor de log2040
Alguna notación:
1 = verdadero
0 = falso
. = lógico Y
+ = OR lógico
[matemáticas] \ bar {A} [/ matemáticas] = lógico NO de A
[matemáticas] \ bar {B} A [/ matemáticas] = NO B y A
Ejemplo 1:
Acerca de
0 0 0
0 1 1
1 0 1
1 1 0
(Puede notar que es el equivalente de una puerta XOR de 2 entradas).
Para construir la expresión booleana para esta tabla de verdad, puede escribir la expresión como una suma lógica de productos lógicos (SOP) o un producto lógico de sumas (POS). Las expresiones resultantes serán equivalentes, pero personalmente me gusta SOP porque implica menos paréntesis al escribirlo.
Para escribir el booleano en forma SOP, examinamos la tercera columna de la tabla y vemos que Out = verdadero cuando A = 0 y B = 1, y Out = verdadero cuando A = 1 y B = 0.
Entonces
[matemáticas]
Fuera = \ bar {A} B + A \ bar {B}
[/matemáticas]
Ya sea [math] \ bar {A} B [/ math] o [math] A \ bar {B} [/ math] dará como resultado que la expresión sea verdadera, por lo que los llamamos “implicantes”.
Tenga en cuenta que esto técnicamente se denomina “POS canónico” porque cada producto lógico en la suma contiene todas las variables (es decir, cada producto tiene una A y una B).
Escribir el formulario POS para XOR es más complicado porque hay muchos negativos dobles y será difícil de explicar intuitivamente en la gramática inglesa.
En cambio, usaré las Leyes / Teoremas de DeMorgan para reorganizar la expresión booleana (el álgebra booleana es algo así como el álgebra regular: puede agrupar cosas y negar ambos lados).
[matemáticas] Fuera = \ bar {A} B + A \ bar {B} [/ matemáticas]
[matemáticas] Fuera = \ overline {(\ overline {\ bar {A} B}) (\ overline {A \ bar {B}})} [/ math]
[matemáticas] Out = \ overline {(A + \ bar {B}) (\ bar {A} + B)} [/ math]
Ejemplo 2
Ahora supongamos que tenemos una tabla de verdad de 3 variables:
A B C Out
——————
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0
Escribir el SOP es fácil: solo examine las filas para las que Out = 1
[matemáticas]
Out = \ bar {A} \ bar {B} \ bar {C} + \ bar {A} \ bar {B} C + A \ bar {B} \ bar {C} + AB \ bar {C}
[/matemáticas]
Nuevamente, esta es una forma de SOP canónica ya que cada producto tiene A, B y C.
Notarás que la expresión anterior deja algo que desear con compacidad.
¡Tenga en cuenta que entre los dos primeros términos del producto (términos mínimos), el valor de C es irrelevante si A y B son ambos 0! Independientemente de si C es 0 o 1 en este caso, Out será verdadero independientemente.
Entonces podemos combinar los dos primeros términos en uno:
[matemáticas]
Out = \ bar {A} \ bar {B} + A \ bar {B} \ bar {C} + AB \ bar {C}
[/matemáticas]
Podemos llevar esto más lejos, observando que un caso similar es válido para B entre los dos últimos términos (solo un bit cambia entre los dos últimos implicantes para que podamos descartar el bit redundante):
[matemáticas]
Fuera = \ bar {A} \ bar {B} + A \ bar {C}
[/matemáticas]
Es bastante fácil escribir formas minimizadas de SOP y POS si utilizamos una técnica un poco más avanzada llamada “mapa de Karnaugh” que nos permite visualizar (hasta alrededor de 5 variables de entrada como máximo) la “cobertura” de la función lógica.
