Introducción álgebra de Boole (página 2)

Partes: 1, 2

Teorema: A+A = A (T. Idempotencia)
Hacer una operación OR consigo mismo da el mismo resultado
A
A

X
A=A

Teorema: A•A = A (T. Idempotencia)
Hacer una operación AND consigo mismo da el mismo resultado
A
A

X
A=A

Teorema: A = A (T. Involución)
Si negamos algo dos veces volvemos al principio
A

X
X=A

Teorema: A + AB = A (T. Absorción I)
A
B
X

Teorema A + AB = A + B (T. Absorción II)
Si A es 1 la salida es 1 Si A es 0 la salida es B

ABXY
X=Y

De Morgan ayuda a simplificar circuitos digitales usando NORs y NANDs.
A • B = A + B
A + B = A • B
Igual para n variables
Leyes de De Morgan (2 variables)

(Gp:) A +B +C + D = A • B • C • D

Leyes de De Morgan (más de 2 variables)

Análisis Booleano de Funciones Lógicas
El propósito de este apartado es obtener expresiones booleanas simplificadas a partir de un circuito
Se examina puerta a puerta a partir de sus entradas
Se simplifica usando las leyes y propiedades booleanas.

Cálculo de la expresión algebraica de salida (ejemplo 1)

(A + B) (CD) = (A + B) + (CD) = A + B + CD
X e Y son iguales

X = (A+B) C + CD + B
= (A+B) C · CD + B
= (A+B) C · (CD + B)
= A B C · (C +D +B)
= A B C C + A B C D +A B C B
= A B C D

Cálculo de la expresión algebraica de salida(ejemplo 2)

Los circuitos son iguales

Puerta a puerta a partir de sus entradas

X= AB+(C+D)
X= AB + C+ D
Ejemplo 3

X = (AB)(CD)
X = ABCD
Ejemplo 4

Ejemplo 5

X = ABCD +A
Simplificando:
X = A + BCD

Ejemplo 6

X = (AB+B)BC
Usando la propiedad distributiva:
X = ABBC +BBC
X = ABC + BBC
X = ABC + 0•C
X = ABC + 0
X = ABC
En la siguiente transparencia se ve cómo las dos cosas son lo mismo

Ejemplo 7

X = (A +AB) +(B(C+D))
X = (A + B) + (B(C + D))
X = (A + B) + (BC + BD)
X = A + B + BC + BD
X = A + B + C + BD

X = A + B + C + D

Expresiones booleanas desde tablas de verdad

Suma de productos

Y= A·B·C+B·C·D+A·C·D o directamente
Y= ABC+BCD+ACD

Producto de sumas

Y=(A+B+C)·(D+C)·(E+F)

Sumas de Productos (SP)
F= ABCD + ABCD + ABCD+ ABCD ? F es suma de productos
Sea una función F(ABCD) que sólo es 1 para los casos:
0011, 1011, 1110, 1111
(Gp:) Cuando ABCD=0011, únicamente la expresión producto ABCD es 1.
Cuando ABCD=1011, únicamente la expresión producto ABCD es 1
…y así sucesivamente… resultando que

Productos de Sumas (PS)
F=ABCD+ABCD+ABCD+ABCD+ABCD
(Gp:) Cuando ABCD=0010, sólo la suma A+B+C+D es 0.
Cuando ABCD=0100, sólo la suma A+B+C+D es 0, …
…y así sucesivamente…

(Gp:) La función F es 0 (o bien F es 1)
cuando ABCD=0010
o cuando ABCD=0100
o cuando ABCD=0111
o cuando ABCD=1010
o cuando ABCD=1101
y en ningún otro caso más.

(Gp:) F=(A+B+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D)(A+B+C+D)
? F es producto de sumas

De Morgan
Sea una función F(ABCD) que sólo es 0 para los casos:
0010, 0100, 0111,
1010, 1101

Se usa para minimizar el número de puertas requeridas en un circuito digital. Es adecuado en vez de usar leyes y propiedades cuando el circuito es grande y/o la función es de entre 3 a 6 variables
Un MK contiene en la misma tabla de verdad de la función pero dispuesta en dos dimensiones.

Celdas adyacentes: En direcciones y, dependiendo del tamaño del MK, la adyacencia puede existir doblando el mapa sobre sí mismo o mediante reflexión en ejes verticales y horizontales
Emplea un código Gray, que se caracteriza porque entre los códigos consecutivos de celdas adyacentes se diferencian en 1 bit.

Minimización de funciones lógicas Mapa de Karnaugh
3 var
4 var
5 var
Espejo

Mapas de Karnaugh de 3 variables
00
01
11
10
0
1
A
A
B C
B C
B C
B C
Código Gray
0
1
3
2
4
5
7
6
1
1
1
1
1
0
0
0
Una celda a 1 implica a 3 variables
Dos celdas adyacentes a 1 implican a 2 variables
Cuatro celdas adyacentes a 1 implican a 1 variable
Ocho celdas adyacentes a 1 constituyen función de valor 1
(Gp:) F = C + AB

Mapa de Karnaugh de 4 variables
Código Gray

A B
A B
A B
A B
C D C D C D C D
(Gp:) 00
(Gp:) 01
(Gp:) 11
(Gp:) 10

(Gp:) 00
(Gp:) 01
(Gp:) 11
(Gp:) 10

Una celda a 1 implica a 4 variables
Dos celdas adyacentes a 1 implican a 3 variables
Cuatro celdas adyacentes a 1 implican a 2 variables
Ocho celdas adyacentes a 1 implican a 1 variable
Dieciséis celdas adyacentes a 1 constituyen función de valor 1

Ejemplo 1. X = A B C D + A B C D + A B C D + A B C D + A B C D + A B C D
00 01 11 10
C D C D C D C D
1
1
1
1
1
1
X = ABD + ABC + CD
Intentar con reducciones booleanas
(Gp:) 00
(Gp:) 01
(Gp:) 11
(Gp:) 10

Código Gray

A B
A B
A B
A B
(Gp:) 00
(Gp:) 01
(Gp:) 11
(Gp:) 10

Ejemplo 2. Z = B C D + B C D + C D + B C D + A B C

A B
A B
A B
A B
C D C D C D C D
1
1
1
1
1
1
1
1
1
1
1
1
X = C + A B + B D
(Gp:) 00
(Gp:) 01
(Gp:) 11
(Gp:) 10

(Gp:) 00
(Gp:) 01
(Gp:) 11
(Gp:) 10

Ejemplo 3. Dado un circuito encontrar otro más sencillo usando Mapas de Karnaugh
Primero lo pasamos a Suma de Productos

Y= A + B + B C + ( A + B ) ( C + D)

Y = A B + B C + A B ( C + D )

Y = A B + B C + A B C + A B D

Y = A B + B C + A B C A B D
Y = A B + B C + (A + B + C ) ( A + B + D)
Y = A B + B C + A + AB + A D + AB + B + BD + AC + BC + CD
Sacando factor común A (en rojo) y B (en azul), queda
Y = A B + A (1+…) + B(1+…) + CD = A + B + B + C D = 1

A B
A B
A B
A B
C D C D C D C D
1
1
1
Z = 1
1
1
1
1
1
1
1
1
1
1
1
1
1
(Gp:) 00
(Gp:) 01
(Gp:) 11
(Gp:) 10

(Gp:) 00
(Gp:) 01
(Gp:) 11
(Gp:) 10

Mapa de Karnaugh de 5 variables
Una celda a 1 implica a 5 variables
Dos celdas adyacentes a 1 implican a 4 variables
Cuatro celdas adyacentes a 1 implican a 3 variables
Ocho celdas adyacentes a 1 implican a 2 variables
Dieciséis celdas adyacentes a 1 implican a 1 variable

SIMPLIFICACIÓN POR KARNAUGH
1) Realizar agrupaciones de 1's, con sus adyacentes, lo mayor posibles, pero siempre en cantidades potencias de 2.
2) No dejar ningún 1 sin agrupar. Puede ocurrir que un 1 pertenezca a más de una agrupación. No se pueden coger agrupaciones totalmente contenidas en otras.
3) Por cada agrupación de 1's resulta un producto de variables. Cuanto más 1's se agrupen, más sencilla resultará la expresión de esa agrupación.
4) En cada agrupación, cada una de las variables puede aparecer en alguno de los siguientes casos:
a) Si siempre vale 1 —–> Se pone afirmada.
b) Si siempre vale 0 —–> Se pone negada.
c) Si cambia de valor (50% de los casos un valor y el otro 50% otro valor) —–> No se pone.
5) La expresión de la función booleana será la suma lógica de todos los productos que hayan salido (expresión como Suma de Productos)

Diseñar un sistema de alarma
Sensores disponibles
1. V = Ventana (V=0 CERRADA, V=1 ABIERTA)
2. P = Puerta (P=0 CERRADA, P=1 ABIERTA)
C = Calefacción (C=0 APAGADA, C=1 ENCENDIDA)
4. A = Aire acondicionado (A=0 APAGADO, A=1 ENCENDIDO)
5. I = Alarma de proximidad de intruso (I=0 NO HAY INTRUSO,
I=1 SÍ HAY INTRUSO)

El sistema de alarma debe activarse cuando:
1. La puerta está abierta y la calefacción encendida (P=1, C=1)
La puerta está abierta y el aire acondicionado encendido (P=1, A=1)
La puerta está abierta con una alarma de proximidad de intruso (P=1, I=1)
La ventana está abierta y la calefacción encendida. (V=1, C=1)
La ventana está abierta y el aire acondicionado encendido (V=1, A=1)
6. La ventana está abierta con una alarma de proximidad de intruso (V=1, I=1)

Función sistema de alarma F de variables V, P, C, A, I

Rellenando el mapa…(P=1, C=1)
V P

V P

V P

V P
(Gp:) 00
(Gp:) 01
(Gp:) 11
(Gp:) 10

(Gp:) 000
(Gp:) 001
(Gp:) 011
(Gp:) 010
(Gp:) 110
(Gp:) 111
(Gp:) 101
(Gp:) 100

(Gp:) C A I C A I C A I C A I C A I C A I C A I C A I

F (V, P, C, A, I)=PC+…

Rellenando el mapa…(P=1, A=1)
V P

V P

V P

V P
(Gp:) 00
(Gp:) 01
(Gp:) 11
(Gp:) 10

(Gp:) 000
(Gp:) 001
(Gp:) 011
(Gp:) 010
(Gp:) 110
(Gp:) 111
(Gp:) 101
(Gp:) 100

C A I C A I C A I C A I C A I C A I C A I C A I
F (V, P, C, A, I)=PC+PA+…

Rellenando el mapa…(P=1, I=1)
V P

V P

V P

V P
(Gp:) 00
(Gp:) 01
(Gp:) 11
(Gp:) 10

(Gp:) 000
(Gp:) 001
(Gp:) 011
(Gp:) 010
(Gp:) 110
(Gp:) 111
(Gp:) 101
(Gp:) 100

C A I C A I C A I C A I C A I C A I C A I C A I
F (V, P, C, A, I)=PC+PA+PI+…

Rellenando el mapa…(V=1, C=1)
V P

V P

V P

V P
(Gp:) 00
(Gp:) 01
(Gp:) 11
(Gp:) 10

(Gp:) 000
(Gp:) 001
(Gp:) 011
(Gp:) 010
(Gp:) 110
(Gp:) 111
(Gp:) 101
(Gp:) 100

C A I C A I C A I C A I C A I C A I C A I C A I
F (V, P, C, A, I)=PC+PA+PI+VC+…

Rellenando el mapa…(V=1, A=1)
V P

V P

V P

V P
(Gp:) 00
(Gp:) 01
(Gp:) 11
(Gp:) 10

(Gp:) 000
(Gp:) 001
(Gp:) 011
(Gp:) 010
(Gp:) 110
(Gp:) 111
(Gp:) 101
(Gp:) 100

C A I C A I C A I C A I C A I C A I C A I C A I
F (V, P, C, A, I)=PC+PA+PI+VC+VA+…

Rellenando el mapa…(V=1, I=1)
V P

V P

V P

V P
(Gp:) 00
(Gp:) 01
(Gp:) 11
(Gp:) 10

(Gp:) 000
(Gp:) 001
(Gp:) 011
(Gp:) 010
(Gp:) 110
(Gp:) 111
(Gp:) 101
(Gp:) 100

C A I C A I C A I C A I C A I C A I C A I C A I
F (V, P, C, A, I)=PC+PA+PI+VC+VA+VI

V P
V P
V P
V P
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Podemos agrupar así…
F = P C+ P A + P I + VC + VA + V I
¿Cuántos chips necesito para esto?
(Gp:) 00
(Gp:) 01
(Gp:) 11
(Gp:) 10

(Gp:) 000
(Gp:) 001
(Gp:) 011
(Gp:) 010
(Gp:) 110
(Gp:) 111
(Gp:) 101
(Gp:) 100

C A I C A I C A I C A I C A I C A I C A I C A I

O usando los ceros…
F = C A I + V P
Sólo dos chips
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
(Gp:) 000
(Gp:) 001
(Gp:) 011
(Gp:) 010
(Gp:) 110
(Gp:) 111
(Gp:) 101
(Gp:) 100

(Gp:) 00
(Gp:) 01
(Gp:) 11
(Gp:) 10

0
0
0
0
0
0
0
0
0
0
0
V P
V P
V P
V P
C A I C A I C A I C A I C A I C A I C A I C A I
F = C A I + V P

Patillaje de los circuitos 7404 y 7454
7404 7454

Conexionado físico
F

Circuito diseñado
F

Ya sabes…
Leyes y propiedades del Algebra de Boole
Simplificar funciones utilizando el Algebra de Boole
Analizar circuitos mediante Algebra de Boole y simplificarlos
Pasar de una tabla de verdad a Suma de Productos y Producto de Sumas
Utilizar Mapas de Karnaugh para simplificar funciones lógicas