Download CAPITULO 6 .- ÁLGEBRA DE BOOLE INTRODUCCIÓN.

D.I.I.C.C
Arquitectura de Sistemas Computacionales
CAPITULO 6 .- ÁLGEBRA DE BOOLE
INTRODUCCIÓN.
E
n 1854 George Boole introdujo una notación simbólica para el tratamiento
de variables cuyo valor podría ser verdadero o falso (variables binarias)
Así el álgebra de Boole nos permite manipular relaciones proposicionales
y cantidades binarias. Aplicada a las técnicas digitales se utiliza para la
descripción y diseño de circuitos más económicos. Las expresiones booleanas
serán una representación de la función que realiza un circuito digital. En estas
expresiones booleanas se utilizarán las tres operaciones básicas (AND, OR
NOT) para construir expresiones matemáticas en las cuales estos operadores
manejan variables booleanas (lo que quiere decir variables binarias).
El estudio de los sistemas numéricos nos ha permitido visualizar que
el sistema binario tiene una implementación natural mediante algún
dispositivo electrónico como por ejemplo, un interruptor que habilita o
deshabilita una variable eléctrica como son Voltaje e Intensidad de
corriente.
El estudio de los códigos nos entregó una forma compacta para la
representación de números y símbolos alfanuméricos de uso habitual en
nuestro lenguaje. En lo que sigue, estudiaremos la base técnica en la cual
se sustenta el funcionamiento de los diferentes circuitos electrónicos
digitales, los cuales permiten desarrollar funciones específicas.
6.1 ÁLGEBRA DE BOOLE.
Un conjunto ℜ sobre el cual se han definido operaciones binarias (+, *), se
llama álgebra de Boole, si cumple los postulados:
Postulado 1: La multiplicación y la suma son conmutativas.
i) a+b=b+a
ii) a·b=b·a
Postulado 2: ℜ contiene elementos neutros, 0 y 1, con respecto a la + y a
la *, tal que:
i) a+0=a
ii) a·1=a
Capitulo 6.- Álgebra de Boole
Página 1
D.I.I.C.C
Arquitectura de Sistemas Computacionales
Postulado 3: Cada operación es distributiva respecto a la otra, es decir:
∀ a, b, c ∈ ℜ se verifica que:
i) a+b·c = (a+b)·(a+c)
ii) a·(b+c) = a·b + a·c
Postulado 4: Cada operación tiene elemento inverso, es decir:
∀ a ∈ ℜ ∃ a ∈ ℜ tal que:
i) a+ a =1
ii) a· a =0
Un álgebra de boole satisface el principio de dualidad:
"Todo teorema deducible de los 4 postulados de un álgebra
Booleana sigue siendo válido si se intercambian los símbolos + y *,
los elementos 0 y 1 entre si."
En consecuencia basta demostrar uno de los enunciados para
posteriormente deducir el otro por dualidad.
Ejemplo 1: Demostrar que ∀ a ∈ ℜ a+a=a.
Dem:
(a+a) = (a+a)·1
= (a+a)(a+ a )
= a+(a· a )
= a+0
=a
/por postulado 2
/por postulado 4
/por postulado 3
/por postulado 4
/por postulado 2
Ejemplo 2: Demostrar que ∀ a ∈ ℜ a·0=0.
Dem:
(a·0) =
=
=
=
=
(a·0)+0
a·0+a· a
a·( a +0)
a· a
0
/por
/por
/por
/por
/por
postulado
postulado
postulado
postulado
postulado
2
4
3
2
4
Ejemplo 3: Demostrar que ∀ a,b ∈ ℜ a+a·b=a
Dem:
a+a·b = a·1+a·b
= a·(1+b)
= a·1
=a
/por
/por
/por
/por
postulado 2
postulado 3
demostración anterior
postulado 2
Ejercicios. Demostrar:
a) a·a = a
b) a+1 = 1 c) a·(a+b) = a
Capitulo 6.- Álgebra de Boole
d) a·( a +b) = a·b
Página 2
D.I.I.C.C
Arquitectura de Sistemas Computacionales
6.1.1 Teoremas del Álgebra de Boole
1. Regla del cero y la unidad
a) X + 0 = X
b) X + 1 = 1
c) X · 1 = X
d) X · 0 = 0
2. Idempotencia o potencias iguales
a) X + X = X
b) X · X = X
3. Complementación
a) x +
x=1
b) X * X = 0
4. Involución
5. Conmutatividad
a) conmutatividad del “+”
X+Y=Y+X
b) conmutatividad del “·”
X· Y=Y ·X
6. Asociatividad
a) asociatividad del “+”
X + (Y + Z) = (X + Y) + Z
b) asociatividad del “·”
X · (Y · Z) = (X · Y) · Z
7. Distribuitividad
a) distribuitividad del “+”
X + (Y · Z) = (X + Y) · (X + Z)
b) distribuitividad del “·”
X · (Y + Z) = (X · Y) + (X · Z)
8. Leyes de absorción
a) X · (X + Y)= X
e) X + X·Y = X
b) X · (
f) X +
c)
+ Y)= X·Y
· (X + Y)=
d) (X + Y) · (X +
·Y
)= X
Capitulo 6.- Álgebra de Boole
g)
·Y = X + Y
+ X·Y =
+Y
h) X·Y + X· = X
Página 3
D.I.I.C.C
Arquitectura de Sistemas Computacionales
9. Teoremas de DeMorgan
a)
c)
b)
d)
10. Teoremas generalizados de DeMorgan
a)
b)
Dualidad
Los postulados y teoremas presentados anteriormente están
representados en pares. La razón es que cada teorema posee lo que
llamamos un dual. El dual de una expresión se obtiene intercambiando las
ocurrencias de OR por AND, 0 por 1 y viceversa.. Si un teorema es valido,
también lo será su dual, En efecto siguiendo el dual de la demostración del
teorema, se obtiene la demostración del dual del teorema.
Por ejemplo dado el postulado 0+0 = 0 se obtiene el dual haciendo 1·1 = 1
6.1.2 FUNCIONES BOOLEANAS.
Sea ℜ = {a,b,c,...} un álgebra Booleana, definimos:
Constante: Un valor dado que puede tomar un elemento de ℜ , como por
ejemplo 0 y 1.
Variable: Un símbolo que representa un elemento de ℜ .
Función: Combinación finita de elementos de ℜ a través de los operadores
“·” y “+”.
Nº de variables de una función: Es el número de elementos distintos que
aparecen en una función, considerándose que una variable y su
complemento son una única variable.
a+b ⇒ 2 variables
x+ x ⇒ 1 variable
Ejercicios: Simplificar:
a) f(x,y)
= (x+y) + ( x + y ) · y
= (x+y) + x · y + y · y
= (x+y) + x · y
= x+y+ x + y
=1
Capitulo 6.- Álgebra de Boole
Página 4
D.I.I.C.C
Arquitectura de Sistemas Computacionales
b) f(w,x,y,z) = x + x·y·z + x ·y·z + w·x + w ·x + x ·y
=
x + x ·y·z + x + x ·y
=
x + yz + x+y
=
x+y+y·z
=
x+y
6.1.3 Formas Canónicas
Definiciones:
Literal: se refiere a una variable o a su complemento (por ej. A, X,
)
Termino Producto (POS): Es un grupo de literales que se encuentran
relacionados entre si por un AND (por ej. A·B, C·A,
·Y·Z )
Termino Suma (SOP): Es un grupo de literales que se encuentran
relacionados entre si por un OR (por ej. A+B, C+A,
+Y+Z )
Termino Normal: Término producto o termino suma en el que un literal no
aparece más de una vez
Termino Canónico: Término en el que se encuentra exactamente uno de
cada uno de los literales de la función. Si el término canónico es un
producto, se denominará mintermino ( ∑ (m) ). Si es una suma se
denominará maxtermino ( ∏ (M ) ).
Forma Normal de una función: Es la que está constituida por términos
normales. Puede estar en la forma suma de términos productos o
productos de términos sumas.
Forma Canónica de una función: Es aquella constituida exclusivamente
por términos canónicos que aparecen una sola vez.
6.1.4 Forma canónica de funciones booleanas
La importancia de la forma canónica estriba en el hecho de ser UNICA.
Como se mostró anteriormente una función puede tener infinidad de
representaciones, pero solo una representación en forma canónica.
Capitulo 6.- Álgebra de Boole
Página 5
D.I.I.C.C
Arquitectura de Sistemas Computacionales
Existen dos formas canónicas de una función: Suma De Productos o
Producto de Sumas. (También de una manera mas formal Suma de
minterminos o Producto de maxterminos)
Para obtener algebraicamente la forma canónica de una función se puede
utilizar los teoremas de expansión canónica:
Teorema 1: Para obtener la forma canónica de una función suma de productos
se multiplicará por un termino de la forma (X +
que el termino sea canónico.
) donde falte un literal para
Teorema 2: Para obtener la forma canónica de una función
sumas se sumará un termino de la forma X ·
el termino sea canónico.
producto de
donde falte un literal para que
6.1.4.1 Forma canónica suma de productos (SOP):
Es aquella constituida exclusivamente por términos canónicos productos
(minterminos) sumados que aparecen una sola vez.
Por ejemplo: F ( X , Y , Z ) = X Y Z + X Y Z + X Y Z + XY Z + XYZ
Para simplificar la escritura en forma de suma canónica de productos, se
utiliza una notación especial. A cada mintermino se le asocia un número binario
de n bits resultantes de considerar como 0 las variables complementadas y
como 1 las variables no complementadas. Así por ejemplo el mintermino
Z
corresponde a combinación X=0, Y=0, Z=1 que representa el numero binario
001, cuyo valor decimal es 1. A este mintermino lo identificaremos entonces
como m1.
De esta forma, la función: F ( X , Y , Z ) = X Y Z + X Y Z + X Y Z + XY Z + XYZ
se puede expresar como: F(X,Y,Z) =
sumatoria de los minterminos 1,4,5,6,7
m(1, 4,5,6,7) que quiere decir la
6.1.4.2 Forma canónica producto de sumas (POS):
Es aquella constituida exclusivamente por términos canónicos sumas
(maxterminos) multiplicados que aparecen una sola vez.
Por ejemplo: F ( X , Y , Z ) = ( X + Y + Z )( X + Y + Z )( X + Y + Z )
Capitulo 6.- Álgebra de Boole
Página 6
D.I.I.C.C
Arquitectura de Sistemas Computacionales
Análogamente al caso anterior, podemos simplificar la expresión de la
función, indicando los maxterminos. Sin embargo, en este caso se hace al
contrario de antes. A cada maxtermino se le asocia un número binario de n bits
resultantes de considerar como 1 las variables complementadas y como 0 las
+ Y + Z
variables no complementadas. Así por ejemplo el maxtermino
corresponde a combinación X=1, Y=0, Z=0 que representa el numero binario
100, cuyo valor decimal es 4. A este maxtermino lo identificaremos entonces
como M4.
De esta forma, la función: F ( X , Y , Z ) = ( X + Y + Z )( X + Y + Z )( X + Y + Z )
Se puede expresar como: F(X,YZ) =
producto de los maxterminos 0,2,3
En resumen, cada mintermino se asocia
con la combinación de entrada para la
que la función produciría un 1, y cada
maxtérmino con la combinación para la
que produciría un 0.
En la tabla de la derecha se muestran
los minterminos y los maxterminos
asociados con cada combinación en una
tabla de verdad de 3 variables. De
acuerdo con esta tabla para determinar
el término producto o suma se hace lo
siguiente: para los minterminos cada
variable no complementada se asocia
con
un
1
y
cada
variable
complementada se asocia con 0. Para
los maxtérminos la regla es la inversa.
M(0,2,3) que quiere decir el
Valor
X Y Z Mintermino
decimal
0
000
1
001
2
010
3
011
4
100
5
101
6
110
7
111
X Y Z =m0
Maxtermino
X +Y +Z =M0
X Y Z =m1
X +Y +Z =M1
X Y Z =m2
X +Y +Z =M2
X Y Z =m3
X +Y +Z =M3
X Y Z =m4
X +Y +Z =M4
X Y Z =m5
X +Y +Z =M5
X Y Z =m6
X +Y +Z =M6
X Y Z =m7
X +Y +Z =M7
Ejemplo 1. Exprese la siguiente función como una suma de minterminos: Hay
dos formas de resolver este problema. F = X + Y Z .
Capitulo 6.- Álgebra de Boole
Página 7
D.I.I.C.C
Arquitectura de Sistemas Computacionales
Forma 1. Se puede obtener la tabla de verdad de la expresión y entonces
tomar los minterminos.
X Y Z F= X +YZ minterminos
0 0 0
0
0 0 1
1
0 1 0
0
0 1 1
0
1 0 0
1
1 0 1
1
1 1 0
1
1 1 1
1
XYZ
Se evalúa la función para todas las combinaciones y
se toman los minterminos de la tabla para los cuales
la función vale 1.
__
__
_
_
La respuesta es :F= X Y Z + X Y Z + X Y Z + X Y Z + X Y Z
XYZ
Otra notación que podemos utilizar es:
XYZ
F=
XYZ
que quiere decir la sumatoria de los minterminos
1,4,5,6,7
m(1, 4,5,6,7)
XYZ
Forma 2. Aplicando los teoremas de expansión canónica para las variables
faltantes.
_
X + YZ
_
_
_
_
X ( Y+ Y ) ( Z + Z ) + Y Z ( X + X )
_
_
_
_ _
( X Y + X Y ) ( Z + Z ) + YZ X + Y Z X
_
_
__
_
__
X Y Z + X YZ + X YZ + X YZ + X Y Z + X YZ
__
__
_
_
X Y Z + X YZ + X YZ + X YZ + X Y Z
Ejemplo 2. Exprese la siguiente función como un producto de maxterminos:
_
F = X +YZ
De nuevo, se puede resolver construyendo una tabla de verdad o con
manipulación algebraica.
Capitulo 6.- Álgebra de Boole
Página 8
D.I.I.C.C
Arquitectura de Sistemas Computacionales
Forma 1. Se obtiene la tabla de verdad de la función. Tomando los
maxterminos desde la tabla de verdad, la respuesta es:
X Y Z F= X +YZ maxterminos
0 0 0
0
0 0 1
1
0 1 0
0
0 1 1
0
1 0 0
1
1 0 1
1
1 1 0
1
1 1 1
1
Se evalúa la función para todas las combinaciones y se
(X+Y+Z) toman los maxtermino de la tabla para los cuales la
función vale 0.
(X+Y+Z)
(X+Y+Z)
_
_ _
La respuesta es: F = ( X + Y + Z ) ( X + Y + Z ) ( X + Y + Z )
Otra notación que podemos utilizar es:
F=
M(0,2,3)
que quiere decir el producto de los maxterminos 0,2,3
Forma 2. Aplicando el teorema de expansión canónica.
_
X +YZ
_
( X +Y ) ( X + Z )
_
_
_
( X + Y + Z Z ) (X + Z + YY )
_
_ _
_
( X +Y+ Z ) ( X +Y+ Z ) ( X + Z +Y ) ( X + Z +Y )
_
_ _
_
( X +Y+ Z ) ( X +Y+ Z ) ( X +Y+ Z ) ( X +Y+ Z )
_
_ _
( X +Y+ Z ) ( X +Y+ Z ) ( X +Y+ Z )
_
_ _
( X +Y+ Z ) ( X +Y+ Z ) ( X +Y+ Z )
Note la simetría que existe entre la suma de productos y el producto de sumas
de una expresión. Si mi es el mintermino para la combinación i, y Mi es el
maxtermino.
m i =M i
Para convertir de una forma canónica a otra se intercambian los signos
y
y se reemplazan los números correspondientes a las combinaciones no
incluidas el la forma original. Por ejemplo:
M(2,4,6) =
Capitulo 6.- Álgebra de Boole
m(0,1,3,5,7)
Página 9
D.I.I.C.C
Arquitectura de Sistemas Computacionales
6.1.4.3 Forma normal de funciones booleanas
Otra manera importante de expresar expresiones booleanas es la forma
normal. Tiene la misma estructura básica suma de productos o producto de
sumas, pero no se requiere que los términos sean minterminos o maxterminos.
Por ejemplo:
La siguiente es una forma normal suma de productos:
__
XY+XYZ
La siguiente es una forma normal producto de sumas:
_
(Y+X)(X+Z)(Y)
A lo largo de este curso la forma que se utilizará con preferencia será la de
suma de productos
6.1.5 Compuertas Lógicas:
Un computador digital, como su nombre lo indica, es un sistema
digital que realiza diversas operaciones de cómputo. La palabra Digital
implica que la información que se representa en el computador por medio
de variables que toman un número limitado de valores discretos o
cuantizados. Estos valores son procesados internamente por componentes
que pueden mantener un número limitado de estados discretos. Los dígitos
decimales por ejemplo, proporcionan 10 valores discretos (0 .. 9). Como
sabemos en la práctica, los computadores funcionan más confiablemente si
sólo utilizan dos estados equiprobables. Debido
al
hecho que los
componentes electrónicos atienden a dos estados (encendido / apagado) y
que la lógica humana tiende a ser binaria (esto es, cierto o falsa, si o no)
se utiliza el sistema binario y se dice que son binarias.
Los computadores digitales utilizan el sistema de números binarios,
que tiene dos dígitos 0 y 1. Un dígito binario se denomina un bit. La
información está representada en los computadores digitales en grupos de
bits. Utilizando diversas técnicas de codificación los grupos de bits pueden
hacerse que representen no solamente números binarios sino también
otros símbolos discretos cualesquiera, tales como dígitos decimales o letras
de alfabeto. Utilizando arreglos binarios y diversas técnicas de codificación,
los dígitos binarios o grupos de bits pueden utilizarse para desarrollar
Capitulo 6.- Álgebra de Boole
Página 10
D.I.I.C.C
Arquitectura de Sistemas Computacionales
conjuntos completos de instrucciones para realizar diversos tipos de
cálculos.
La información binaria se representa en un sistema digital por
cantidades físicas denominadas señales. Las señales eléctricas tales como
voltajes existen a través del sistema digital en cualquiera de dos valores
reconocibles y representan un a variable binaria igual a 1 o 0. Por ejemplo,
un sistema digital particular puede emplear una señal de 3 [volts ] para
representar el binario “1” y 0.5 [volts ] para el binario ”0”. La siguiente
ilustración muestra un ejemplo de una señal binaria.
Como se muestra en la figura, cada valor binario tiene
una
desviación aceptable del valor nominal. La región intermedia entre las dos
regiones permitidas se cruza solamente durante la transición de estado.
Los terminales de entrada de un circuito digital aceptan señales binarias
dentro de las tolerancias permitidas y los circuitos responden en los
terminales de salida con señales binarias que caen dentro de las tolerancias
permitidas.
La lógica binaria tiene que ver con variables binarias y con
operaciones que toman un sentido lógico. Es utilizada para escribir, en
forma algebraica o tabular. La manipulación y procesamiento de
información binaria. La manipulación de información binaria se hace por
circuitos lógico que se denominan Compuertas. Las compuertas son
bloques del hardware que producen señales del binario 1 ó 0 cuando se
satisfacen los requisitos de entrada lógica. Las diversas compuertas lógicas
se encuentran comúnmente en sistemas de computadores digitales. Cada
compuerta tiene un símbolo gráfico diferente y su operación puede
describirse por medio de una función algebraica. Las relaciones entrada salida de las variables binarias para cada compuerta pueden representarse
en forma tabular en una tabla de verdad.
A continuación se detallan los nombres, símbolos, gráficos, funciones
algebraicas, y tablas de verdad de ocho compuertas.
Capitulo 6.- Álgebra de Boole
Página 11
D.I.I.C.C
Arquitectura de Sistemas Computacionales
Compuerta AND:
Cada compuerta tiene una o dos variables de entrada designadas por
A y B y una salida binaria designada por x. La compuerta AND
produce la unión lógica AND: esto es: la salida es 1 si la entrada A y la
entrada B están ambas en el binario 1: de otra manera, la salida es 0. Estas
condiciones también son especificadas en la tabla de verdad para la
compuerta AND. La tabla muestra que la salida x es 1 solamente cuando
ambas entradas A y B están en 1. El símbolo de operación algebraico de la
función AND es el mismo que el símbolo de la multiplicación de la
aritmética ordinaria (*). Podemos utilizar o un punto entre las variables o
concatenar las variables sin ningún símbolo de operación entre ellas. Las
compuertas AND pueden tener más de dos entradas y por definición, la
salida es 1 si cualquier entrada es 1.
Compuerta OR:
La compuerta OR produce la función OR inclusiva, esto es, la salida
es 1 si la entrada A o la entrada B o ambas entradas son 1; de otra
manera, la salida es 0. El símbolo algebraico de la función OR es
(+), similar a la operación de aritmética de suma. Las compuertas OR
pueden tener más de dos entradas y por definición la salida es 1 si
cualquier entrada es 1.
Compuerta NOT (Inversor):
El circuito inversor invierte el sentido lógico de una señal binaria.
Produce el NOT, o función complemento. El símbolo algebraico
utilizado para el complemento es una barra sobra el símbolo de la
variable binaria. Si la variable binaria posee un valor 0, la compuerta NOT
cambia su estado al valor 1 y viceversa. El círculo pequeño en la salida de
un símbolo gráfico de un inversor designa un complemento lógico. Es decir
cambia los valores binarios 1 a 0 y viceversa.
Compuerta Separador:
Un símbolo triángulo por sí mismo designa un circuito separador no
produce ninguna función lógica particular puesto que el valor binario
de la salida es el mismo de la entrada. Este circuito se utiliza
simplemente para amplificación de la señal. Por ejemplo, un separador
que utiliza 3 volts para el binario 1 producirá una salida de 3 volts cuando
la entrada es 3 volts. Sin embargo, la corriente suministrada en la entrada
es mucho más pequeña que la corriente producida en la salida. De ésta
manera, un separador puede excitar muchas otras compuertas que
Capitulo 6.- Álgebra de Boole
Página 12
D.I.I.C.C
Arquitectura de Sistemas Computacionales
requieren una cantidad mayor de corriente que de otra manera no se
encontraría en la pequeña cantidad de corriente aplicada a la entrada del
separador.
Compuerta NAND:
Es el complemento de la función AND, como se indica por el símbolo
gráfico que consiste en un símbolo gráfico AND seguido por un
pequeño círculo. La designación NAND se deriva de la abreviación
NOT - AND. Una designación más adecuada habría sido AND invertido
puesto que Es la función AND la que se ha invertido.
Compuerta NOR:
La compuerta NOR es el complemento de la compuerta OR y utiliza
un símbolo gráfico OR seguido de un círculo pequeño. Tanto las
compuertas NAND como la NOR pueden tener más de dos entradas,
y la salida es siempre el complemento de las funciones AND u OR,
respectivamente.
Compuerta OR exclusivo (XOR):
La compuerta OR exclusiva tiene un símbolo gráfico similar a la
compuerta OR excepto por una línea adicional curva en el lado de
la entrada. La salida de esta compuerta es 1 si cada entrada es 1
pero excluye la combinación cuando las dos entradas son 1. La función OR
exclusivo tiene su propio símbolo gráfico o puede expresarse en términos de
operaciones complementarias AND, OR.
Compuerta NOR exclusivo (XOR):
El NOR exclusivo como se indica por el círculo pequeño en el símbolo
gráfico. La salida de ésta compuerta es 1 solamente si ambas
entradas son tienen el mismo valor binario. Nosotros nos referiremos
a la función NOR exclusivo como la función de equivalencia. Puesto que las
funciones OR exclusivo y funciones de equivalencia no son siempre el
complemento la una de la otra. Un nombre más adecuado para la operación
OR exclusivo sería la de una función impar; esto es, la salida es 1 si un
número impar de entrada es 1. Así en una función OR (impar) exclusiva de
tres entradas, la salida es 1 si solamente la entrada es 1 o si todas las
entradas son 1. La función de equivalencia es una función par; esto es, su
salida es 1 si un número par de entradas es 0. Para un función de
equivalencia de tres entradas, la salida es 1 si ninguna de las entradas son
0 (todas las entradas son 1) o si dos de las entradas son 0 (una entrada es
1). Una investigación cuidadosa revelará que el OR exclusivo y las
funciones de equivalencia son el complemento la una de la otra cuando las
Capitulo 6.- Álgebra de Boole
Página 13
D.I.I.C.C
Arquitectura de Sistemas Computacionales
compuertas tienen un número par de entradas, pero las dos funciones son
iguales cuando el número de entradas es impar. Estas dos compuertas
están comúnmente disponibles con dos entradas y solamente en forma rara
se encuentran con tres o más entradas.
RESUMEN COMPUERTAS LÓGICAS:
Símbolo
Algebraica
Tabla de Verdad
Función
AND
aA
X = A * b ⇒ AB
OR
X = A+ B
Inversor (Not)
X = A' ⇒ A
Separador
X =A
NAND
X = ( AB )'
Capitulo 6.- Álgebra de Boole
Página 14
D.I.I.C.C
Arquitectura de Sistemas Computacionales
Símbolo
Algebraico
Tabla de Verdad
Función
NOR
X = ( A + B)'
OR (Exclusivo XOR)
X = A ⊕ B ⇒ A B + AB
NXOR (Exclusivo, Equivalencia)
X = A ⊗ B⇒ A B + AB
Tabla Resumen de Compuertas Lógicas
NAND
OR
NOR
Var Var AND
(+)
A
B
(*)
aA
0
0
1
1
0
1
0
1
0
0
0
1
1
1
1
0
0
1
1
1
1
0
0
0
OR EX ( ⊕ )
NOREX ( ⊗ )
A B + AB
A B + AB
0
1
1
0
1
0
0
1
Retomemos el teorema DeMorgan:
El teorema DeMorgan es muy importante al tratar compuertas NOR y
NAND. Expresa que una compuerta NOR que realiza la función (x + y)’ es
equivalente a la expresión función xy’. Similarmente, una función NAND
Capitulo 6.- Álgebra de Boole
Página 15
D.I.I.C.C
Arquitectura de Sistemas Computacionales
puede ser expresada bien sea por (xy)’ o por x’ + y’ por esta razón, las
compuertas NOR y NAND tienen dos símbolos gráficos distintos como se
muestra en la figura:
En vez de representar una compuerta NOR por el símbolo gráfico OR
seguido por un círculo, nosotros podemos representarla por un símbolo
gráfico AND precedido por círculos en todas las entradas. El inversor AND
para la compuerta NOR proviene del teorema DeMorgan y de la convención
de que los círculos pequeños denotan complementación. Similarmente la
compuerta NAND también posee dos símbolos gráficos.
Para ver cómo se utiliza la manipulación del álgebra Booleana para
simplificar circuitos digitales considere el diagrama lógico de la siguiente
figura. La salida de la primera compuerta NAND es, por el teorema
DeMorgan , (AB)’ = A’ + B. La salida del circuito es la operación NAND de
este término y B’.
x= ( A’ + B ) * B’ ]‘
Diagrama lógico.
Utilizando el teorema DeMorgan dos veces, obtenemos:
x = ( A’ + B )’ + B = AB’ + B
Note que el teorema DeMorgan ha sido aplicado tres veces ( para
demostrar su utilización ) pero podría ser aplicado solamente una vez de la
siguiente manera:
x = [ ( AB’ )* B´ ] ‘ = AB’ + B
La expresión para x
puede simplificarse por aplicación de las
relaciones mencionadas anteriormente:
Capitulo 6.- Álgebra de Boole
Página 16
D.I.I.C.C
Arquitectura de Sistemas Computacionales
x = AB’ + B
= B + AB’
= ( B + A) ( B + B’ )
= ( B + A) * 1
=B+A=A+B
El resultado final produce una función OR y puede ser implementado
con una sola compuerta OR como se muestra en la figura parte (b) del
diagrama lógico. Uno Puede demostrar que dos circuitos
producen
relaciones binarias idénticas Entrada - Salida simplemente obteniendo la
tabla de verdad para cada uno de ellos.
6.1.6
Mapas de Karnaugh.
Dentro de las representaciones esquemáticas de una función Booleana,
ésta es una de las más útiles. La idea es representar en forma más
compactas las tablas que representan a la función.
DEFINICIONES BÁSICAS:
Definición 1: Minterm de n variables (m)
Es el producto Booleano de las n variables, donde cada variable
está presente en su valor verdadero o falso. En otras palabras
corresponde a un término producto normal.
Definición 2: Maxterm de n variables (M)
Es la suma Booleana de las n variables donde cada variable
está presente en su valor verdadero o falso. Se puede decir
que corresponde a un término suma normal.
TEOREMA:
Cualquier
representarse:
función
Booleana
f(x1,
x2,...,xn)
puede
i) Como forma canónica de suma de producto.
ii) Como forma canónica de producto de sumas.
La función F puede describirse como:
F(x,y,z)=Σm(2,3,5)
F(x,y,z)= ΠM(0,1,4,6,7)
Capitulo 6.- Álgebra de Boole
Página 17
D.I.I.C.C
Arquitectura de Sistemas Computacionales
Obs: F (x,y,z)=Σm(0,1,4,6,7)
F (x,y,z)=ΠM(2,3,5)
Esto es válido para cualquier nº de variables de entrada.
Ejemplo para 4 variables
F(x,y,z,w) = Σm (0,1,3,5,7,15)
= Π M (2,4,6,8,9,10,11,12,13,14)
6.2 Simplificación de circuitos lógicos:
La complejidad del diagrama lógico que implementa una función
Booleana está directamente relacionado con la complejidad de la expresión
algebraica a partir de la cual la función se implementa. La representación de
la tabla de verdad de una función es única pero la función puede aparecer
en muchas formas diferentes como se expresa algebraicamente. La
expresión puede simplificarse utilizando las relaciones básicas del álgebra
Booleana. Este procedimiento sin embargo. es algunas veces difícil porque
carece de reglas específicas para predecir cada uno de los pasos sucesivos
en el proceso de manipulación. El método del mapa proporciona un
procedimiento simple, y directo para simplificar funciones Booleanas . Este
método puede mirarse como un arreglo gráfico de una tabla de verdad que
permite una interpretación fácil para elegir el mínimo número de variables
que se necesitan para expresar la función algebraicamente. El método del
mapa también se le conoce con el nombre de Mapa de Karnaugh y
diagrama de Veitch.
Cada una de las combinaciones de la variable en una tabla de verdad
se denomina un Miniterm. Por ejemplo, tenemos la siguiente tabla de
verdad:
Esta tabla posee ocho miniterm. Una función de “n” variables cuando
se expresa por medio de una tabla
de verdad tendrá 2n minterm,
Capitulo 6.- Álgebra de Boole
Página 18
D.I.I.C.C
Arquitectura de Sistemas Computacionales
equivalente a 2n números binarios obtenidos de los n dígitos. Una función
Booleana será igual a 1 para algunos miniterm y a 0 para los otros. La
información contenida en una tabla de verdad puede expresarse en forma
compacta enumerando el decimal equivalente de aquellos, miniterm que
producen un 1 para la función
Por ejemplo la tabla anterior puede
expresarse de la siguiente forma:
F (x,y,z) = ∑ (1,4,5,6,7)
Las letras en paréntesis enumeran las variables binarias en el orden
que ellas aparecen en la tabla de verdad. El símbolo “ ∑ “ se utiliza para la
suma de los miniterms que siguen en el paréntesis. Los miniterms que
producen en la salida un 1 para la función se enumeran con su equivalente
decimal respectivo. Los miniterms que no aparecen en la lista son los que
producen 0 para la función Booleana.
El mapa es un diagrama hecho de cuadrados, en que cada cuadrado
representa un miniterm. Los cuadrados a los miniterm que producen 1 para
la función se marcan con un “1” y los restantes con “0” o se dejan vacíos.
Para reconocer varios patrones y combinar cuadrados marcados por 1 en el
mapa, es posible derivar las expresiones algebraicas alternas para la
función, a partir de las cuales se puede seleccionar la más conveniente.
Los mapas para las funciones de dos, tres y cuatro variables se
muestran en la siguiente figura.
a).- Mapa de dos variables
b).- Mapa de tres variables
Capitulo 6.- Álgebra de Boole
Página 19
D.I.I.C.C
Arquitectura de Sistemas Computacionales
C).- Mapa de cuatro variables
El número de cuadrados en un mapa de “n” variables es 2n minitern
y son listados por un número decimal equivalente para fácil referencia.
Los números de miniterms son asignados en un arreglo ordenado de tal
manera que los cuadrados adyacentes representen los miniterms que
difieren solamente en una variable. Los nombres de las variables son
listados a través de ambos lados de la línea diagonal en la esquina del
mapa. Los 1 y 0 marcados a lo largo de cada fila y de cada columna
designan el valor de las variables. Cada variable debajo de los paréntesis
contiene la mitad de los cuadrados en el mapa en donde aquella variable
aparece sin comillas (no complementada). La variable aparece con un
comilla (complementada) en la mitad de los cuadrados. Toda la información
que aparece en los mapas de la figura, no siempre es necesaria, en ésta
oportunidad se muestra solamente a modo explicativo.
El miniterm representado por un cuadrado es determinado de la
asignación binaria de las variables a lo largo de los bordes izquierdo y
superior del mapa.
A continuación se muestran algunos ejemplos de representación en
mapa de Karnaugh de distintas funciones a partir de su tabla de verdad,
éste mapa representará los valores a minimizar cuando la función arroje un
valor igual a 1.
a)
X
0
0
1
1
Mapa de Karnaugh para representar dos variables
Y
0
1
0
1
F(x,y)
0
1
0
1
x 0
y
0 0 0
1 1 1
Capitulo 6.- Álgebra de Boole
1
2
0
3 1
Página 20
D.I.I.C.C
Arquitectura de Sistemas Computacionales
b) Mapa de Karnaugh para representar tres variables
X
0
0
0
0
1
1
1
1
Y
0
0
1
1
0
0
1
1
Z
0
1
0
1
0
1
0
1
F(x,y)
0
1
1
0
1
1
0
1
z
xy
00
0
0
0
1
1
01
2
1
3
1
11
6
4
0
7
0
10
1
5
1
1
c) Mapa de Karnaugh para representar cuatro variables
A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
Capitulo 6.- Álgebra de Boole
B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
F(A,B,C,D)
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
Página 21
D.I.I.C.C
Arquitectura de Sistemas Computacionales
Naturalmente hemos representado la forma más simple que
corresponde a lo más 2 entradas. Nuestro estudio apunta a la realización de
funciones Booleanas. En general, cada variable será representativa de
alguna condicionante que pudiera tener sólo 2 valores de verdad.
Una serie de condicionantes y la o las acciones que se deseen
ejecutar de acuerdo al estado de dichas condiciones podrán ser
representadas por una expresión Booleana.
Dicha expresión Booleana podrá posteriormente implementarse
mediante circuitos electrónicos capaces de reconocer 2 estados (0,1). Lo
que a continuación se estudia es la forma de obtener una expresión lo más
simple posible para la representación de una función. De esta forma
podremos posteriormente obtener un circuito electrónico menos complejo.
6.3 Minimizacion de funciones booleanas.
Veamos un ejemplo:
F(a,b,c,d) = Σ m (5,6,9,10,13,14)
= a · b· c ·d + a · b·c·d + a · b· c·d + a · b·c·d + a· b· c ·d + a · b·c·d
(1)
= a · b · c · d + a · b · c · d + a · c · d · (b + b) + a · c · d · (b + b)
= a · b· c ·d + a · b·c·d + a· c·d + a ·c·d
= c · d · (a · b + a) + c · d · (a + a · b)
= c · d · (a + b) + c · d · (a + b)
Capitulo 6.- Álgebra de Boole
Página 22
D.I.I.C.C
Arquitectura de Sistemas Computacionales
= (c · d + c · d) · (a + b)
(2)
= a·c·d +a·c·d + b·c·d + b·c·d
(1)
(2)
(3)
(3)
6 AND de 4 entradas + 1 OR de 6 entradas.
2 OR de 2 entradas + 3 AND de 2 entradas.
4 AND de 3 entradas + 1 OR de 4 entradas.
Observaciones: El circuito (2) es más simple pero debe notarse que las
señales A y B en el caso (2) pasan a través de 3 niveles previo a procesar la
salida.
Cualquier suma de producto o producto de suma puede realizarse por
circuitos de 2 niveles donde estos pueden ser AND - OR / OR - AND /NAND
- NAND/NOR - NOR. Este tipo de expresiones se dice una expresión de 2º
orden o circuito de 2º orden.
Un circuito como el (2) que corresponde a uno de mayor orden se
dice un circuito factorizado. Este nombre proviene del hecho de que el
proceso a partir de uno de 2º orden es muy similar a un proceso de
factorización del álgebra convencional.
Este tipo de factorización se basa principalmente en prueba y error y
en la habilidad para recordar que cierto tipo de productos tienen dicha
factorización.
A continuación se desarrolla un proceso de minimización en el cual se
obtienen expresiones de 2º orden.
Definición: Una expresión suma de productos de 2º orden se dirá mínima
si:
a) No existe una expresión equivalente con menos productos
b) No hay una expresión equivalente que contenga el mismo número de
productos, pero con menos cantidad de variables
Igual enunciado vale para expresiones de producto de sumas, en las
cuales se debe reemplazar producto por suma y viceversa.
Nota: Puede existir más de una representación mínima.
Ejemplo:
A)
Sea f(a,b,c) = Σm (0,1,4,6)
= a· b·c + a · b·c +a· b·c +a·b·c
Capitulo 6.- Álgebra de Boole
Página 23
D.I.I.C.C
Arquitectura de Sistemas Computacionales
Notemos que los 2 primeros términos se combinan para dar:
a · b · c + a · b · c = a · b · (c + c)
= a·b
y los otros 2 dan:
a · b · c + a · b · c = a · c(b + b)
= a·c
Por lo tanto, f= a · b + a · c
Observaciones:
i) m0 y m1 son adyacentes, en ellos sólo cambia la variable “c”.
ii) al unir m0 y m1 observamos que no aparece la variable que marca la
distancia entre ambos minterm, es decir la variable “c”.
iii) igual caso entre m4 y m6.
B) Sea f(a,b,c,d) = Σm(5,7,10,13,15)
= a · b· c ·d + a · b·c·d + a· b·c·d + a · b· c ·d +a · b·c·d
m5
m7
m10 m13
m15
m13 y m15 son adyacentes
m5 y m7 son adyacentes
ambos grupos son adyacentes entre sí.
m5+m7+m13+m15 = a · b · c · d + a · b · c · d + a · b · c · d + a · b · c · d
= bd
Luego, en la agrupación restante se han eliminado A y C, las
cuales son las variables que cambian de valor. Así agrupando 2k minterm
adyacentes pueden eliminarse k variables de una función.
Por lo tanto,
f(a,b,c,d)= b · d + a · b · c · d
C) f(a,b,c,d)= Σm (0,8,12,14,5,7)
Minimizar de la forma anterior es más complicado que si se
aplica un mapa de Karnaugh.
Capitulo 6.- Álgebra de Boole
Página 24
D.I.I.C.C
Arquitectura de Sistemas Computacionales
En efecto:
Del mapa de Karnaugh se obtienen las siguientes ecuaciones:
(a)
b·c·d
(b)
a·b·d
(c)
a ·b·d
a:
Por lo tanto, la función es: f = b · c · d + a · b · d + a · b · d y es equivalente
f = d (bc + ab ) + abd , por lo tanto el circuito asociado sería:
Este circuito, posee los siguientes componentes: 5 compuertas AND,
2 compuertas OR y 3 NOT.
D) f(a,b,c,d) = Σm (0,1,2,3,13,15)
Capitulo 6.- Álgebra de Boole
Página 25
D.I.I.C.C
Arquitectura de Sistemas Computacionales
AB
CD
00
01
11
10
00
1
0
0
0
01
a 01
0
0
1 b
0
11
01
0
0
1
0
10
1
0
0
0
Del mapa de Karnaugh se obtienen las siguientes ecuaciones:
(a) a · b
(b) a · b · d
Por lo tanto, la función es: f = a · b + a · b · d y el circuito asociado es:
E) f(a,b,c,d) = Σm(0,2,8,12,13)
Capitulo 6.- Álgebra de Boole
Página 26
D.I.I.C.C
Arquitectura de Sistemas Computacionales
Del mapa de Karnaugh se obtienen las siguientes ecuaciones:
(a) a · b · d
(b) a · b · c
(c) a · c · d
Por lo tanto, la función es: f = a · b · d + a · b · c + a · c · d y es equivalente
a: f = ab d + ac (b + d ) cuyo circuito asociado es:
Del mapa de Karnaugh se obtienen las siguientes ecuaciones:
(a) a · b · d
(b) b · c · d
(c) a · b · c
Capitulo 6.- Álgebra de Boole
Página 27
D.I.I.C.C
Arquitectura de Sistemas Computacionales
Por lo tanto, la función es: f = a · b · d + b · c · d + a · b · c y es equivalente a:
f = b d ( a + c ) + abc cuyo circuito asociado es:
Como podemos apreciar en este ejemplo existen 2 formas mínimas,
dependiendo de como se agrupen las celda adyacentes (los 1´).
CONDICIONES SUPERFLUAS.
Son casos en los que la salida no está definida frente a una cierta
combinación de entrada pudiendo ocurrir que dicha combinación de entrada
nunca se de.
Como ejemplo se puede citar un semáforo, el cual no puede tener la
luz roja y verde encendida al mismo tiempo.
Capitulo 6.- Álgebra de Boole
Página 28