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):
- Cómo simplificar [matemáticas] \ izquierda (\ frac {27a ^ 9} {125b ^ 3} \ derecha) ^ \ frac {-2} {3} [/ matemáticas]
- Si se permiten repeticiones, ¿de cuántas maneras puede seleccionar K de N sin tomar 2 elementos consecutivos?
- ¿Cómo manejas el fracaso personalmente y como instructor?
- ¿Cómo se eleva un número o matriz a una potencia matricial?
- Si Rita puede correr alrededor de las cuadras 5 veces en 20 minutos, ¿cuántas veces puede correr alrededor de la cuadra en una hora?
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.