Funciones lógicas
Hemos adelantado que la definición de un operador entre 2 variables ay b, exige
definir el resultado (0 o 1) para las 4 combinaciones de valores posibles que
pueden presentar a y b (mostradas en la Tabla-1 ), y que pueden existir 16
de estas funciones. Para 3 variables hay que
definir 23 = 8 resultados, y pueden existir 23 de estas funciones. En general,
para definir una función entre n variables hay que definir 2n valores, y pueden
ser definidas 2n^2 funciones distintas. Así pues, el arsenal de funciones
distintas en función del número de variables implicadas es el siguiente:
Tabla-4 |
Valores de a
| 0 | 1 | Función |
f0(a) | 0 | 0 | f(a) = 0 |
f1(a) | 0 | 1 | f(a) = a (identidad) |
f2(a) | 1 | 0 | f(a) = a (inverso) |
f3(a) | 1 | 1 | f(a) = 1 |
|
* Para una variable: 21 combinaciones, 21^2 funciones.
Este caso es el representado en la Tabla-4. En ella vemos que aparte de las dos
seudo funciones (f0 y f3), f1 es una identidad (transforma la variable en
si misma). Queda f2 como
auténtica función (la inversión ya estudiada anteriormente).
Nota: Esta tabla de verdad debe leerse de la siguiente forma: la
función f0 aplicada sobre a produce un resultado 0 con cualquier valor (0 o 1)
que tenga a.Por su parte f1 aplicada sobre a produce un resultado 0 o 1 según
el valor (0 o 1) que tenga a (en realidad no modifica el valor de a).La función
f2 aplicada sobre a produce un resultado que es el inverso de a.Finalmente, f3
aplicada sobre aproduce siempre un 1, independientemente del valor (0 o 1) de
a. |
* Para 2 variables: hay 22 combinaciones 22^2 =16 funciones, que se han
representado en la Tabla-5 (incluyen las 4 posibilidades correspondientes
a 1 variable).
* Para 3 variables: 23 = 8
combinaciones. Las posibilidades de asignar 0/1 a estas combinación es 23^2 =
256.
* Para n variables: 2n combinaciones.
Las posibilidades de asignar 0/1 a estas combinación es 2n^2.
|
A continuación definimos las 16 operaciones posibles entre 'dos'
variables lógicas (denominadas conectivas). Vemos que están incluidas algunas
que no lo son realmente (resultados que no dependen de los valores de las
variables independientes), y que están también las de una sola variable. En la
Tabla-5 se han señalado estas 16 posibilidades.
Vemos que las funciones marcadas con 1©, f0 y f15, no son realmente funciones,
valen 0 y 1 (falso y cierto) respectivamente, con independencia de los valores
a y b. Las marcadas con 2© son las de una variable ya comentadas.
Es digno de destacarse que estas 16 funciones no son independientes entre sí.
Pueden expresarse en función de tres de ellas: AND, OR y NOT. A continuación se
comentan las mas interesantes, las tablas de verdad de cada operación las
dejamos referidas a esta tabla.
§5.1 F7 La operación Suma, inclusive-OR, Reunión, Unión (tiene
todos estos nombres), se define mediante la tablade verdad adjunta.
Inclusive OR |
a | b s |
0 | 0 0 |
0 | 1 1 |
1 | 0 1 |
1 | 1 1 |
|
En lenguaje coloquial diríamos que la salida o resultante es cierta si lo es
alguna de las variables (entradas).
Notación:
s = a + b
s = a OR b
La notación utilizada puede ser cualquiera de las señaladas. Recuerde: el
operador + no tiene nada que ver con la suma tradicional (aritmética).
Propiedades:
Conmutativa: s = a + b = b + a
Asociativa: s = a+(b+c) = (a+b)+c = a+b+c
Producto |
a | b s |
0 | 0 0 |
0 | 1 0 |
1 | 0 0 |
1 | 1 1 |
|
§5.2 F1 Operación Producto, AND, Intersección: La salida es
cierta si son simultáneamente ciertas las dos entradas.Notación:s = a . b
= abs = a AND bs = a Y bPropiedades:Conmutativa: s = ab =
baAsociativa: s = (ab)c = a(bc) = abc |
§5.3 F8 Operación Not-Or, NOR: La salida es cierta si ninguna
de las entradas lo es.
Notación: s = a ↓ b = a+b
Propiedades:
Conmutativa: s = a ↓ b = b ↓ a
No asociativa: a ↓ (b ↓ c) ≠ (a ↓ b) ↓ c ≠
a+b+c
§5.4 F14 Operación Not-And, NAND: La salida es cierta
siempre que no sean simultáneamente ciertas las dos entradas.
Notación: s = a b = ab ≠ a.b
Propiedades
Conmutativa: s = a b = b a
No asociativa: a (b c) ≠ (a b) c ≠ abc
a a = a = aa
§5.5 F6 Operación Exclusive-OR, EOR: La salida es
cierta cuando solo una de lasentradas es cierta.
Notación: s = a b
Propiedades:
Conmutativa: s = a b = b a
Asociativa: a (b c) = (a b) c = a b c
§5.6 F9 Operación Exclusive-Not-OR, ENOR: Esta función
es la negación de la anterior. Se llama también Equivalencia, porque según
puede verse en su tabla de verdad, mantiene en la salida un 1 lógico solo
cuando a = b.
Notación: s = a b
§5.7 F11/F13 Función Implicación.
s = a
b |
a | b | s |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 1 | 1 |
s = b
a |
a | b | s |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 1 |
1 | 1 | 1 |
|
Notación:
s = a
b Debe leerse: a implica b
s = b
a Debe leerse: b implica a
Si una variable s está definida respecto a otras dos mediante una expresión de
implicación de este tipo: s = a b, debe entenderse que a implica a b en el sentido
siguiente: Supongamos que la variable lógica a representa si un ser vivo
pertenece a la raza humana, y que la variable b representa si un ser vivo es de
sangre caliente (1) o fría (0). La variable s, definida mediante la ecuación s
= a
b representa la condición que podría enunciarse mas o menos así: 'Si
es ser humano su sangre debe ser de caliente necesariamente'. La variable
s representa esta implicación, indicándonos en cada caso si puede ser cierta o
no cada una de las combinaciones de valores a y b, en el supuesto de que la
implicación sea consistente.Veamos las posibilidades en este ejemplo analizando
la tabla de verdad:
a no es humano (a=0), b no es de sangre caliente (b=0) Podría ser cierto?
Si (s = 1)
a no es humano (a=0), b si es de sangre caliente (b=1) Podría ser cierto?
Si (s = 1)
a si es humano (a=1), b no es de sangre caliente (b=0) Podría ser cierto?
No (s = 0)
a si es humano (a=1), b si es de sangre caliente (b=1) Podría ser
cierto? Si (s = 1)
§5.8 F2/F4 Funciones de negación de implicación, NOT
implicación.
Observamos que estas funciones son la negación de las anteriores.
Notación:
F2: s = a
b Debe leerse: a NOT implica b
F4: s = b
a Debe leerse: b NOT implica a
Las tablas de verdad pueden construirse a partir de las anteriores (§5.7),
cambiando los ceros por unos y viceversa (negando los valores correspondientes)
en la columna s.
Principios de Diseño de Lógica Combinatoria
Los sistemas digitales combinatorios son aquellos cuyas salidas sólo dependen
de las entradas actuales. Los circuitos de este tipo no pueden contener lazos
de retroalimentación. En análisis de circuitos combinacionales, se empieza con
un diagrama lógico y se obtiene una descripción formal de la función realizada
por el circuito, ya sea una tabla de verdad o una expresión lógica. En la
síntesis, se comienza con una descripción formal y se termina con un diagrama
lógico. El diseño es una estrategia para resolver unproblema por medio de la
síntesis.
Puerta lógica
Una puerta lógica, o compuerta lógica, es un dispositivo electrónico que es la
expresión física de un operador booleano en la lógica de conmutación. Cada
puerta lógica consiste en una red de dispositivos interruptores que cumple las
condiciones booleanas para el operador particular. Son esencialmente circuitos
de conmutación integrados en un chip.
Claude Elwood Shannon experimentaba con relés o interruptores electromagnéticos
para conseguir las condiciones de cada compuerta lógica, por ejemplo, para la
función booleana Y (AND) colocaba interruptores en circuito serie, ya que con
uno solo de éstos que tuviera la condición 'abierto', la salida de la
compuerta Y sería = 0, mientras que para la implementación de una compuerta O
(OR), la conexión de los interruptores tiene una configuración en circuito
paralelo.
La tecnología microelectrónica actual permite la elevada integración de
transistores actuando como
conmutadores en redes lógicas dentro de un pequeño circuito integrado. El chip
de la CPU es una de las máximas expresiones de este avance tecnológico.
Lógica directa
Puerta SI
Símbolo de la función lógica SI a) Contactos, b) Normalizado y c) No
normalizado
La puerta lógica SI, realiza la función booleana igualdad. En la práctica se
suele utilizar como
amplificador de corriente (buffer en inglés).
La ecuación característica que describeel comportamiento de la puerta SI es:
Su tabla de verdad es la siguiente:
Tabla de verdad puerta SI |
Entrada A | Salida A |
0 | 0 |
1 | 1 |
Puerta Y (AND)
Símbolo de la función lógica Y a) Contactos, b) Normalizado y c) No normalizado
La puerta lógica Y, más conocida por su nombre en inglés AND, realiza la
función booleana de producto lógico. Su símbolo es un punto (·), aunque se
suele omitir. Así, el producto lógico de las variables A y B se indica como AB,
y se lee A y B o símplemente A por B.
La ecuación característica que describe el comportamiento de la puerta AND es:
Su tabla de verdad es la siguiente:
Tabla de verdad puerta AND |
Entrada A | Entrada B | Salida AB |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Su definición se puede dar, como una compuerta que entrega un 1 lógico sólo si
todas las entradas están a nivel alto 1.
Puerta O (OR)
Símbolo de la función lógica O. a) Contactos, b) Normalizado y c) No normalizado
La puerta lógica O, más conocida por su nombre en inglés OR, realiza la
operacion de suma lógica. Su símbolo es el más (+). Así la suma lógica de las
variables A y B se indica como A + B y se lee A o B o simplemente A más B. En
la figura de la derecha pueden observarse sus símbolos en electrónica.
La ecuación característica que describe el comportamiento de la puerta OR es:
Su tabla de verdad es la siguiente:
Tabla deverdad puerta OR |
Entrada A | Entrada B | Salida A + B |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
Podemos definir la puerta O como aquella que proporciona a su salida un 1
lógico si al menos una de sus entradas está a 1.
Puerta O-exclusiva (XOR)
Símbolo de la función lógica O-exclusiva. a) Contactos, b) Normalizado y c) No
normalizado
La puerta lógica O-exclusiva, más conocida por su nombre en inglés XOR, realiza
la función booleana A'B+AB'. Su símbolo es el más (+) inscrito en un círculo.
En la figura de la derecha pueden observarse sus símbolos en electrónica.
La ecuación característica que describe el comportamiento de la puerta XOR es:
Su tabla de verdad es la siguiente:
Tabla de verdad puerta XOR |
Entrada A | Entrada B | Salida A B |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Se puede definir esta puerta como aquella que proporciona un 1, sólo si las dos
entradas son distintas, esto es, 1 y 0 ó 0 y 1.
Lógica negada
Puerta NO (NOT)
Símbolo de la función lógica NO a) Contactos, b) Normalizado y c) No
normalizado
La puerta lógica NO (NOT en inglés) realiza la función booleana de inversión o
negación de una variable lógica.
La ecuación característica que describe el comportamiento de la puerta NOT es:
Su tabla de verdad es la siguiente:
Tabla de verdad puerta NOT |
Entrada A | Salida |
0 | 1 |
1 | 0 |
Se puede definir como unapuerta que proporciona
el estado inverso del
que esté en su entrada.
Puerta NO-Y (NAND)
Símbolo de la función lógica NO-Y. a) Contactos, b) Normalizado y c) No
normalizado
La puerta lógica NO-Y, más conocida por su nombre en inglés NAND, realiza la operación
de producto lógico negado. En la figura de la derecha pueden observarse sus
símbolos en electrónica.
La ecuación característica que describe el comportamiento de la puerta NAND es:
Su tabla de verdad es la siguiente:
Tabla de verdad puerta NAND |
Entrada A | Entrada B | Salida |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Podemos definir la puerta NO-Y como aquella que proporciona a su salida un 0
lógico únicamente cuando todas sus entradas están a 1.
Puerta NO-O (NOR)
Símbolo de la función lógica NO-O. a) Contactos, b) Normalizado y c) No
normalizado
La puerta lógica NO-O, más conocida por su nombre en inglés NOR, realiza la
operacion de suma lógica negada. En la figura de la derecha pueden observarse
sus símbolos en electrónica.
La ecuación característica que describe el comportamiento de la puerta NOR es:
Su tabla de verdad es la siguiente:
Tabla de verdad puerta OR |
Entrada A | Entrada B | Salida |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 0 |
Podemos definir la puerta NO-O como aquella que proporciona a su salida un 1
lógico sólo cuando todas sus entradas están a 0. La puertalógica NOR constituye
un conjunto completo de operadores.
Puerta equivalencia (XNOR)
Símbolo de la función lógica equivalencia. a) Contactos, b) Normalizado y c) No
normalizado
La puerta lógica equivalencia, más conocida por su nombre en inglés XNOR,
realiza la función booliana AB+A'B'. Su símbolo es un punto (·) inscrito en un
círculo. En la figura de la derecha pueden observarse sus símbolos en
electrónica. La ecuación característica que describe el comportamiento de la
puerta XOR es:
Su tabla de verdad es la siguiente:
Tabla de verdad puerta XNOR |
Entrada A | Entrada B | Salida |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Se puede definir esta puerta como aquella que proporciona un 1 lógico, sólo si
las dos entradas son iguales, esto es, 0 y 0 ó 1 y 1.
Puertas lógicas triestado
Las puertas lógicas triestado (de tres estados), son un tipo de puertas es las
cuales la salida tiene, además de los niveles alto y bajo, un tercer estado de
alta impedancia normalmente representado por Z. El estado Z se implementa
únicamente para facilitar el diseño de los circuitos, y no contiene ninguna
información. Esta característica se utiliza en circuitos en los cuales las salidas
de varias puertas lógicas se conectan a una única entrada, (evitando así un
cortocircuito). Una entrada de control activa una única salida a la vez,
dependiendo de la operación lógica requerida por eldiseñador, mientras que las
otras salidas se mantienen en el estado Z de alta impedancia (también
denominado 'deshabilitado').
Álgebra de Boole
El álgebra booleana es la teoría matemática que se aplica en la lógica
combinatoria. Las variables booleanas son símbolos utilizados para representar
magnitudes lógicas y pueden tener sólo dos valores posibles: 1 (valor alto) ó 0
(valor bajo).
Operaciones Booleanas y Compuertas Básicas
Las operaciones boolenas son posibles a través de los operadores binarios
negación, suma y multiplicación, es decir que estos combinan dos o más
variables para conformar funciones lógicas. Una compuerta es un circuito útil
para realizar las operaciones anteriormente mencionadas.
Inversión o negación (complemento)
Esta operación se indica con una barra sobre la variable o por medio de un
apóstrofe en el lado superior derecho de la variable, en este curso emplearemos
esta última notación. El apóstrofe (’) es un operador algebraico que invierte
el valor de una variable, es decir, si X denota la señal de entrada de un
inversor, entonces X’ representa el complemento de tal señal.
Ejemplo
Sí X = 0 entonces X’ = 1.
En la tabla de verdad 2.1.1. se muestra el resultado de la inversión lógica.
Ecuación | Entrada A | Salida B |
B=A’ | 0 | 1 |
| 1 | 0 |
Tabla 2.1.1. Tabla de verdad del
inversor
El símbolo lógico de la negación booleana serepresenta en la figura 2.1.1.
Figura 2.1.1. Inversor.
Suma booleana
La representación matemática de una suma booleana de dos variables se hace por
medio un signo más entre las dos variables.
Ejemplo
La suma booleana de las variables A y B se enuncia de la siguiente forma,
X = A + B
La suma booleana es 1 si alguna de las variables lógicas de la suma es 1 y es 0
cuando todas las variables son 0. Esta operación se asimila a la conexión
paralela de contactos.
La tabla de verdad de la suma se muestra en la tabla 2.1.2.
Entrada A | Entrada B | Salida X |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
Tabla 2.1.2.Tabla de Verdad de la función OR
En circuitos digitales, el equivalente de la suma booleana es la operación OR y
su símbolo lógico se representa en la figura 2.1.2.
Figura 2.1.2. Símbolo lógico para la compuerta OR.
Con la correspondiente ecuación X= A + B.
El inverso de la función OR es la función NOR. La tabla de verdad se muestra en
la tabla 2.1.3.
Entrada A | Entrada B | Salida X |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 0 |
Tabla 2.1.3.Tabla de verdad de la función NOR
El símbolo lógico de la compuerta NOR se representa en la figura 2.1.3.
Figura 2.1.3. Símbolo lógico para la compuerta NOR
Con la correspondiente ecuación X= (A+B)’
La suma booleana difiere de la suma binaria cuando se suman dos unos. En lasuma
booleana no existe acarreo.
Multiplicación booleana
La representación matemática de una multiplicación booleana de dos variables se
hace por medio un signo punto (·) entre las dos variables.
La multiplicación booleana de las variables A y B se enuncia de la siguiente
forma,
X = A · B
La multiplicación booleana es 1 si todas las variables lógicas son 1, pero si
alguna es 0, el resultado es 0. La multiplicación booleana se asimila a la
conexión serie de contactos.
La tabla de verdad de la multiplicación booleana se muestra en la tabla 2.1.4.
Entrada A | Entrada B | Salida X |
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Tabla 2.1.4. Tabla de verdad de la función AND
En circuitos digitales, el equivalente de la multiplicación booleana es la
operación AND y su símbolo se representa en la figura 2.1.4.
Figura 2.1.4. Símbolo lógico de la función AND
con la correspondiente ecuación X= A·B
El inverso de la función AND es la función NAND. La tabla de verdad se muestra
la tabla 2.1.5.
Entrada A | Entrada B | Salida X |
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Tabla 2.1.5.Tabla de verdad de la función NAND
El símbolo lógico de la compuerta NAND se representa en la figura 2.1.5.
Tabla 2.1.5. Símbolo lógico de la función NAND
Con la correspondiente ecuación X = (A·B)’
La interactividad 2.1.1 muestra las compuertasmás importantes.
Interactividad 2.1.1. Compuertas Básicas
Propiedades de las Operaciones Booleanas
Las operaciones booleanas están regidas por tres leyes similares a las del álgebra
convencional. Estas incluyen las leyes conmutativas de la suma y la
multiplicación y la ley distributiva.
Leyes conmutativas en dos variables
1. Ley conmutativa de la suma se enuncia como
sigue
X + Y = Y + X
En aplicación a los circuitos digitales, podríamos decir que no importa el
orden de conexión de las entradas a una compuerta OR.
2. Ley conmutativa de la multiplicación
X·Y = Y· X
En aplicación a los circuitos digitales, podríamos decir que no importa el
orden de conexión de las entradas a una compuerta AND.
Leyes asociativas en tres variables
1. Ley asociativa de la adición, se escribe en forma algebraica de la siguiente
forma
A + ( B + C ) = ( A + B ) + C
En la figura 2.1.6 se muestra la aplicación de la propiedad a las compuertas
OR,
Figura 2.1.6. Ley asociativa de la adición
2. Ley asociativa de la multiplicación
A·( B· C) = ( A·B )· C
En la figura 2.1.7 se muestra la aplicación de la propiedad a las compuertas
AND,
Figura 2.1.7. Ley asociativa de la multiplicación
Ley distributiva para tres variables
En el álgebra de Boole, la multiplicación lógica se distribuye sobre la suma
lógica,
A·( B + C ) = A·B + A·C
En la figura 2.1.8 se muestra la aplicación de lapropiedad a las compuertas AND
y OR,
Figura 2.1.8. Ley distributiva para tres variables
Álgebra de Boole (Continuación)
Teoremas Booleanos
Los teoremas booleanos son enunciados siempre verdaderos, lo que permite la
manipulación de expresiones algebraicas, facilitando el análisis ó síntesis de
los circuitos digitales. Los teoremas booleanos son los siguientes:
1. X + 0 = X
2. X + 1 = 1
3. X·0 = 0
4. X·1 = X
5. (X’)’=X
6. X + X = X
7. X·X = X
8. X + X’ = 1
9. X.X’= 0
10. X + XY = X
11. X +X’·Y = X + Y
12. X·Y + X·Y’ = X (Teorema de combinación)
13. (X +Y)(X + Y’) = X + X·Y’ + X·Y = X
14. X·Y + X·Z + Y·Z’ = XZ + Y·Z’ (Consenso)
El teorema 12 se conoce como
la ley distributiva para tres variables.
Demostración teorema 12:
X·Y + X·Y’ = X
Utilizando la ley distributiva para tres variables
X·Y + X·Y’= X·(Y+Y’)
Aplicando el teorema 8 se tiene,
X·Y + X·Y’= X·1
Dando como resultado,
X·Y + X·Y’= X
Esta expresión indica que la suma de dos productos canónicos adyacentes, es
decir que difieren en una sola de las variables, se reduce al producto de los
demás términos suprimiéndose dicha variable. El teorema 13 es otro caso del teorema de
combinación. Los teoremas 12 y 13 se utilizarán en las lecciones siguientes de
forma sistemática para sintetizar circuitos lógicos con los métodos de mapas de
karnaugh y el algortimo deQuine-McCluskey. (ver lección 4).
Teoremas de DeMorgan
Los teoremas de DeMorgan demuestran la equivalencia entre las puertas NAND y
negativa - OR, y las puertas NOR y negativa – AND.
1. El complemento de la suma de variables es igual al producto de los
complementos de las variables.
(X1 + X2 +..+ Xn)’ = X1’ · X2’ · .. · Xn’
En el caso de dos variables se tiene,
(X + Y)’ = X’ · Y’
El circuito equivalente a la ecuación anterior se muestra en la figura 2.1.9.
Figura 2.1.9. Símbolo lógico para la compuerta NOR.
Ejemplo
Obtener una compuerta OR utilizando compuertas NAND.
Y = (A + B) = [(A + B)’]’ = (A’·B’)’
Figura 2.1.10. Compuerta OR utilizando compuertas NAND
1. El complemento del
producto de variables es igual a la suma de los complementos de las variables.
(X1 · X2 ·..· Xn)’ = X1’ + X2’ + ..+ Xn’
En el caso de dos variables se tiene,
(X · Y)’ = X’ + Y’
El circuito equivalente en dos variables a la ecuación se muestra en la figura
2.1.11.
Figura 2.1.11. Símbolo lógico para la compuerta NOR.
Ejemplo
Obtener una compuerta AND utilizando compuertas NOR.
Y = A·B = [(A.B)’]’ = (A’+B’)’
Figura 2.1.12. Circuito lógico para la compuerta AND
Simplificación de Expresiones Lógicas
El objetivo de la simplificación de expresiones lógicas es reducir la expresión
al menor número posible de términos. Las expresiones lógicas se pueden
simplificar utilizando losteoremas anteriores.
Ejemplo
F = A·B’·C + A·B’C’
F = A·B’·(C + C’)
F = A·B’
Ejemplo
F= (A’+B)·(A+B’)
F = A·A’ + A’·B’ + A·B + B·B’
F = A’·B’ + A·B
Ejemplo
F = [(A’ + C)·(B + D’)]’
F = (A’ + C)’+(B + D’)’
F= A·C’ + B’·D
Ejemplo
F = (X + Z’)·(Z + W·Y)’ + (V·Z + W·X’)·(Y + Z)’
F = (X + Z’)·[Z’·(W’ + Y’)] + [(V·Z + W·X’)·(Y’·Z’)]
F = (X + Z’)·(Z’·W’ + Z’·Y’) + V·Y’·Z·Z’ + W·X’·Y’·Z’
F = W’·X·Z’ + X·Y’·Z’ + Z’·Z’·W’ + Z’·Z’·Y’ + W·X’·Y’·Z’
F = W’·X·Z’ + X·Y’·Z’ + W’·Z’ + Y’·Z’ + W·X’·Y’·Z’
F = W’·Z’·(1 + X) + Y’·Z’·(1 + X) + W·X’·Y’·Z’
F = W’·Z’ + Y’·Z’ + W·X’·Y’·Z’
F = W’·Z’ + Y’·Z’·(1 + W·X’)
F = Z’·(W’ + Y’)
Implementación de Funciones Lógicas mediante Compuertas.
La forma más fácil de encontrar la expresión de un circuito lógico consiste en
comenzar con las entradas situadas más a la izquierda e ir avanzando hasta la
salida de cada compuerta lógica, obteniendo la expresión para cada una de
ellas. Al final del
recorrido se debe tener la expresión para todo el circuito. La expresión
resultante podemos simplificarla para obtener una más sencilla y así obtener un
circuito más reducido.
Ejemplo
Encontrar la expresión para el circuito de la figura.
Figura 2.1.13. Símbolo lógico para la compuerta NOR.
1. La expresión de la compuerta NOR situada a la izquierda cuyas entradas son A
y B es (A+B)’. Esta es la primera entrada de la compuerta AND situada a
laderecha.
2. La expresión de la compuerta AND cuyas entradas son (A+B)’ y C es (A+B)’·C.
3. La salida de la compuerta AND es la primera entrada de la compuerta OR del
extremo derecho. Por lotanto, la expresión de esta compuerta OR es [(A+B)’·C]+D.
Síntesis de Diseño de Circuitos Combinatorios
Síntesis se entiende como
la obtención de circuitos lógicos, a partir de una descripción inicial que
utiliza el lenguaje convencional y luego es transferida a una tabla de verdad.
Una tabla de verdad es una representación básica de una función lógica, en la
cual se listan las salidas del
circuito lógico para las posibles combinaciones de entrada. Las combinaciones
de entrada están ordenadas por renglones (líneas) y cada renglón contiene su
salida respectiva. Por ejemplo, la tabla de verdad para una función lógica de 3
variables, tendrá 8 líneas para 8 combinaciones de entrada, conteniendo cada
línea, su salida respectiva. En la tabla 2.2.1. se ilustra una función de 3
variables para el caso mencionado.
Renglón o línea | A | B | C | Función de salida | Mintérmino | Maxtérmino |
0 | 0 | 0 | 0 | F(0,0,0) | A'·B'·C' | A+B+C |
1 | 0 | 0 | 1 | F(0,0,1) | A'·B'·C | A+B+C' |
2 | 0 | 1 | 0 | F(0,1,0) | A'·B·C' | A+B'+C |
3 | 0 | 1 | 1 | F(0,1,1) | A'·B·C | A+B'+C' |
4 | 1 | 0 | 0 | F(1,0,0) | A·B'·C' | A'+B+C |
5 | 1 | 0 | 1 | F(1,0,1) | A·B'·C | A'+B+C' |
6 | 1 | 1 | 0 | F(1,1,0) |A·B·C' | A'+B'+C |
7 | 1 | 1 | 1 | F(1,1,1) | A·B·C | A'+B'+C' |
Tabla 2.2.1.Funciones de salida, maxtérminos y mintérminos
En general, la tabla de verdad para una función lógica de n variables tendrá 2n
líneas. En la interactividad 2.2.1. se pueden introducir los datos de la
función de salida y obtener el correspondiente mintérmino y máxtérmino.
Interactividad 2.2.1. Funciones de salida, maxtérminos y mintérminos
Métodos para Sintetizar Circuitos Lógicos
Los métodos para sintetizar circuitos lógicos requieren en primer lugar, la
comprensión de algunos conceptos, entre ellos:
* Literal: Variable o el complemento de una variable.
Ejemplo: X’, Y’, X, Y.
* Dominio de una expresión booleana: Es el conjunto de variables contenido en
una expresión booleana.
Ejemplo: Determine el dominio de la expresión X’·Y·Z + X·Y’·Z·W.
El dominio es X, Y, Z, W.
* Término normal: Un producto o término suma en donde ninguna variable aparece
repetida.
Ejemplo de término repetido: X·Y·Y, Z·X’·X’·Y
Ejemplo de término no repetido: X’·Y·Z, Z·Y’·X
* Término producto: Un solo literal o el producto lógico (multiplicación
booleana) de dos o más literales.
Ejemplo: X’, X·Y’, Z·Y, X·Y’·Z
Un término producto es 1 sólo para una combinación de valores de las variables.
Ejemplo: El término producto X·Y'·Z es 1 sólo para X=1, Y=0 y Z=1 y es 0 para
el resto de combinaciones. El valor enbinario será 101 ó 5 en decimal.
* Término suma: Un solo literal o una suma lógica (suma booleana) de dos o más
literales.
Ejemplo: X, X + Y’,X’+Z’, X+Y+Z, X+Y’+Z’
Un término suma es 1 cuando cualquier literal que lo compone es 1.
Ejemplo: El término X+Y’+Z’ es 0 para X=0 ó Y=1 ó Z=1 y es 1 para el resto de
combinaciones. El valor en binario será 011 ó 3 en decimal.
* Suma de productos: Suma lógica de términos productos (Ver tabla 2.2.1).
Ejemplo: X’+ X·Y’ + Z·Y + X·Y’·Z
Forma estándar de la suma de productos
Una suma de productos no se encuentra en su forma estándar cuando alguno de los
términos producto no contiene alguna de las variables del dominio de la expresión.
Ejemplo
X’·Y·Z + X·Y’·Z·W. El dominio es X, Y, Z, W. El primer término producto no
contiene el literal W ó W'.
Ejemplo
X'·Y·Z'.W + X·Y·Z·W. En cada uno de los términos de la expresión aparecen todas
las variables del
dominio. Por lo tanto, la suma de productos está en su forma estándar.
* Producto de sumas: Producto lógico de términos suma (Ver tabla 2.2.1).
Ejemplo: X·(X+Y’)·(X’+Z’)·(X+Y+Z)·(X+Y’+Z’).
Forma estándar del producto de sumas
Un producto de sumas no se encuentra en su forma estándar cuando alguno de los
términos suma no contiene alguna de las variables del dominio de la expresión.
Ejemplo
(X’+W+Z')·(X'+Y’+Z+W')·(X+Y). El dominio es X, Y, Z, W. El primer término suma
no contiene elliteral Y ó Y'. El tercer término suma no contiene los literales
Z ó Z' y W ó W'.
Ejemplo
(X'·Y·Z'.W)·(X·Y'·Z·W). En cada uno de los términos de la expresión aparecen
todas las variables del
dominio. Por lo tanto, el producto de sumas está en su forma estándar.
* Mintérmino: Es un término de producto con n literales en el cual hay n
variables. De n variables obtenemos 2n mintérminos.
Ejemplo de mintérminos de 3 variables: X’·Y’.Z’, X’.Y’.Z, X’.Y.Z’, X’.Y.Z,
X.Y’.Z’, X.Y’.Z, X.Y.Z’, X.Y.Z. (Ver tabla 2.2.1.).
* Maxtérmino: Es un término de suma con n literales en el cual hay n variables.
De n variables obtenemos 2n maxtérminos. (Ver tabla 2.2.1.).
Ejemplo de maxtérminos de 3 variables: X+Y+Z, X+Y+Z’, X+Y’+Z, X+Y’+Z’, X’+Y+Z,
X’+Y+Z’, X’+Y’+Z, X’+Y’+Z’. (Ver tabla 2.2.1.).
Los métodos existentes para sintetizar circuitos lógicos son:
* Suma de productos (SDP)- Lección 3.
* Producto de sumas (PDS) - Lección 3.
* Mapas de Karnaugh - Lección 4.
* Algoritmo de Quine – McCluskey - Lección 5.
Representación por Suma de Productos y Producto de Sumas
En la lección anterior vimos las definiciones básicas para comprender los
métodos de síntesis de circuitos lógicos. En esta lección se explicarán los dos
primeros de estos métodos para sintetizar circuitos lógicos.
Método de Suma de Productos (SDP)
La suma de productos de una función lógica es la suma de los
mintérminoscorrespondientes a las líneas de la tabla de verdad para las que la
función produce una salida igual a 1. La función obtenida es la suma de
productos.
Ejemplo
Obtener la suma de productos para la función lógica de la tabla 2.3.1.
Línea | A | B | C | Función de salida F1 |
0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 |
2 | 0 | 1 | 0 | 1 |
3 | 0 | 1 | 1 | 0 |
4 | 1 | 0 | 0 | 1 |
5 | 1 | 0 | 1 | 1 |
6 | 1 | 1 | 0 | 0 |
7 | 1 | 1 | 1 | 1 |
Tabla 2.3.1.Tabla de verdad para la función lógica F1
La función puede ser expresada conformando un término mínimo por cada
combinación de variables que producen un 1 en la función para luego obtener la
suma de todos los términos. La función lógica para la tabla 2.3.1 se determina
expresando las combinaciones 010, 100, 101 y 111 como A'·B·C', A·B'·C', A·B'·C
y A·B·C:
F1= ï“ï€ A,B,C( 2,4,5,7)= A'·B·C' + A·B'·C' + A·B'·C + A·B·C.
Cada mintérmino de la función anterior representa una compuerta AND de tres
entradas y la implementación de la función es posible a través de la aplicación
de la operación OR a las salidas de las cuatro compuertas AND. Por tanto, el
número total de compuertas AND dependerá del total de mintérminos de la
expresión. El circuito se muestra en la figura 2.3.1.
Figura 2.3.1. Circuito lógico para la función lógica F1.
En una suma de productos se cumple la igualdad de la función al valor lógico 1
si al menos uno desus términos productos es igual a 1.
Ejemplo
Obtener la suma de productos para la función lógica de la tabla 2.3.2.
A | B | F2 |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Tabla 2.3.2.Tabla de verdad de la función F2.
En la tabla de verdad existen dos condiciones para las cuales la salida es 1.
Estas son las siguientes:
1. La primera se presenta cuando A es Bajo(0) y B es Alto(1). El resultado 1 de
esta condición se puede expresar como
el producto lógico:
A’·B
2. La segunda condición se presenta cuando A es 1 y B es 0. Esta condición
ocasiona un resultado 1, si el producto lógico es:
A·B’
Como cualquiera de estas 2 condiciones hace que la salida sea 1, entonces la
función lógica que los representa es la suma lógica de los productos anteriores:
F2= A’·B + A·B’ = A ïƒ…ï€ B
La representación de la función anterior con compuertas OR y AND se muestra en
la figura 2.3.2.
Figura 2.3.2. Función F2 utilizando compuertas AND Y OR
Esta función corresponde a la función OR exclusiva, cuya compuerta se representa
en la figura 2.3.3.
Figura 2.3.3. Símbolo lógico de la función OR - exclusiva.
Ejemplo
Obtener la función SDP para la función lógica de la tabla 2.3.3. Simplificar la
función y dibujarla.
A | B | F3 |
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Tabla 2.3.3.Tabla de verdad de la función F3
Utilizando suma deproductos para las líneas 1 y 4 de la tabla se obtiene,
F3=A'·B'+ A·B, simplificando
F3=(A+B)’ + A·B
F3= (Aï€ ïƒ… B)'
El circuito lógico de la función anterior se muestra en la figura 2.3.4.
Figura 2.3.4. Función F3 utilizando compuertas AND, NOR y OR.
El símbolo lógico de la compuerta NOR - Exclusiva se muestra en la figura
2.3.5.
Figura 2.3.5. Símbolo lógico de la función NOR - exclusiva
Conversión de una expresión lógica a formato de suma de productos
La metodología empleada en la transformación de una suma de productos a su
forma estándar se basa en el teorema 6 (Ver lección 1 parte 2), que establece
que una variable sumada con su complemento es siempre igual a 1; A + A' = 1.
Los pasos son los siguientes:
1. Los términos producto que no contengan la(s) variable(s) del dominio, multiplicarlos por un término
formado por dicha variable más el complemento de la misma (teorema 6).
2. Repetir el paso 1 para todos los términos de la expresión que no contengan
todas las variables (o sus complementos) del
dominio. Resolver los términos intervenidos.
Ejemplo
Convertir la expresión booleana A·B.C' + B·C + A' a su forma estándar.
El dominio de la expresión es el conjunto de variables A, B y C. Se observa la
falta de formato estándar para el segundo y tercer término producto. Sobre
ellos se aplicará el procedimiento, para luego volver a agrupar toda la
expresión:
Término B·CB·C = B·C ·(A+A') = A·B·C + A'·B·C
Término A
A' = A'·(C+C') = A'·C+A'·C' ; la expresión aún no tiene el formato estándar,
entonces multiplicamos cada término por (B+B')
A'·C·(B+B') +A'·C'·(B+B') = A'·B·C + A'·B'·C + A'·B·C' + A'·B'·C'
La expresión en su formato estándar es:
A·B.C' + B·C + A' = A·B·C + A'·B·C + A'·B·C + A'·B'·C + A'·B·C' + A'·B'·C'
Método de producto de sumas (PDS)
El producto de sumas de una función lógica es la multiplicación de los
maxtérminos correspondientes a las líneas de la tabla de verdad para las que la
función produce una salida igual a 0. La función obtenida es el producto de
sumas.
Ejemplo
Obtener el producto de sumas para la función lógica de la tabla 2.3.4.
Renglón o línea | A | B | C | Función de salida F4 |
0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 |
2 | 0 | 1 | 0 | 1 |
3 | 0 | 1 | 1 | 0 |
4 | 1 | 0 | 0 | 0 |
5 | 1 | 0 | 1 | 1 |
6 | 1 | 1 | 0 | 1 |
7 | 1 | 1 | 1 | 1 |
Tabla 2.3.4.Tabla de verdad para la función lógica F4
La función puede ser expresada conformando un término máximo para cada
combinación de variables que producen un 0 en la función y luego obtener el
producto de todos los términos. La función lógica para la tabla 2.3.4 se
determina expresando las combinaciones 000, 001, 011 y 110 como (A+B+C),(A+B+C'),(A+B'+C') y (A'+B+C).
La función lógica es la siguiente:
F4= ï“ï€ A,B,C( 0,1,3,4)=(A+B+C)·(A+B+C')·(A+B'+C')·(A'+B+C).
Cada maxtérmino de la función anterior representa una compuerta OR de tres
entradas y la implementación de la función es posible a través de la aplicación
de la operación AND a las salidas de las cuatro compuertas AND. Por tanto, el
número total de compuertas AND dependerá del
total de mintérminos de la expresión. El circuito se muestra en la figura
2.3.6.
Figura 2.3.6. Circuito lógico para la función lógica F4
Un producto de sumas es igual a 0 si al menos uno de los términos suma es igual
a 0.
Ejemplo
Obtener el producto de sumas para la función lógica de la tabla 2.3.5.
A | B | F5 |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Tabla 2.3.5.Tabla de verdad de la función OR - exclusiva
Considere el complemento de la función de Boole F5. Este puede obtenerse de la
tabla 2.3.5. formando un término mínimo por cada combinación que produce un
cero y luego haciendo la suma de los términos. El complemento de F5 se expresa
así:
F5' = A'·B' + A·B
La expresión F5 se obtiene la negar F5':
F5 = (F5')' = (A'·B' + A·B)' =(A'·B')'·(A·B)' = [(A')'+(B')']·(A'+B') =
(A+B)·(A'+B')
Si cualquiera de los términos del PDS es cero, la función es cero.
De los 2 métodos anteriores, se pueden escoger algunos criterios para aplicar
un método u otro, siendo estos los siguientes:
* Si en la última columna de la tabla de verdad, o sea en la columna que indica
losresultados, sí predominan los ceros es más conveniente utilizar las suma de
productos.
* Si en la columna que indica los resultados, predominan los unos, es más
conveniente utilizar el método del producto de sumas
Mapas de Karnaugh
Un mapa de Karnaugh es una representación gráfica de una función lógica a
partir de una tabla de verdad. El número de celdas del mapa es igual al número de combinaciones
que se pueden obtener con las variables de entrada. Los mapas se pueden
utilizar para 2, 3, 4 y 5 variables.
Mapa de Karnaugh empleando Suma de Productos (SDP)
La simplificación de expresiones lógicas mediante el mapa de Karnaugh utiliza
un método gráfico basado en la Suma de Productos.
Mapa de Karnaugh de tres variables
El mapa de Karnaugh se construye a partir de la tabla de verdad de la función
lógica. El mapa por medio de una matriz de 8 celdas, representa los ocho
mintérminos posibles que se pueden obtener con tres variables, en un arreglo de
una matriz de 2x4. Por tanto, la primera fila contiene el primer valor posible
('0') y la segunda fila el valor ('1').
Las variables 2 y 3 se agrupan por columna y se distribuyen en las cuatro
columnas de acuerdo a las combinaciones posibles para obtener los mintérminos
requeridos. Sus valores son 00, 01, 10 y 11. Por ejemplo, la celda m2
corresponde al mintérmino 2, ubicado en la fila 0 y la columna 10. La unión de
estos dos números da elnúmero 010, cuyo equivalente es el término A’·B·C’ ó el
decimal 2. La tabla 2.4.1. muestra el mapa de Karnaugh para 3 variables.
Línea | A | B | C | Mintérmino | Mintérmino mx | Función de Salida |
0 | 0 | 0 | 0 | A’·B’·C’ | m0 | F(0,0,0) |
1 | 0 | 0 | 1 | A’·B’·C | m1 | F(0,0,1) |
2 | 0 | 1 | 0 | A’·B·C’ | m2 | F(0,1,0) |
3 | 0 | 1 | 1 | A’·B·C | m3 | F(0,1,1) |
4 | 1 | 0 | 0 | A·B’·C’ | m4 | F(1,0,0) |
5 | 1 | 0 | 1 | A·B’·C | m5 | F(1,0,1) |
6 | 1 | 1 | 0 | A·B·C’ | m6 | F(1,1,0) |
7 | 1 | 1 | 1 | A·B·C | m7 | F(1,1,1) |
(a)
(b) | (c) |
Tabla 2.4.1. Mapa de tres variables
La característica de ordenamiento de un mapa de Karnaugh radica en el cambio de
un solo bit en los términos de las celdas adyacentes de filas y columnas. En la
tabla 2.4.1. las entradas BC se colocan secuencialmente, cambiando cada vez una
sola variable, por eso resulta el orden: 00, 01, 11 y 10. En la interactividad
2.4.1., la pulsación de cada cuadro activa el mintérmino correspondiente.
Por ejemplo, la variable C está negada en m4 y m5 no lo está, mientras que A y
B no cambia. Las celdas de los bordes superior e inferior e izquierdo y derecho
también cumplen esta condición al agruparlas unas a otras. En el teorema 12 de
la lección 1, se demuestra que la suma de los términos mínimos en celdas adyacentes
pueden sersimplificadas en un término AND de dos literales. Por consiguiente,
aplicando el teorema para los términos m4 y m5 del mapa se tiene:
m4 + m5 = A·B’·C’ + A·B’·C = A·B’·(C’+C) = A·B
Los términos m4 y m6 se pueden asociar de la misma forma:
m4 + m6 = A·B’·C’ + A·B·C’ = A·C’·(B’+B) = A·C’
Ejemplo
Simplificar la función F1= ïƒ¥ï€ (m3, m4, m5, m6, m7).
F1 = ïƒ¥ï€ (m3, m4, m5, m6, m7) = A’·B·C + A·B’·C’+ A·B’·C + A·B·C’+ A·B·C
Aplicando el teorema 6 de la lección 1 para el término A·B·C.
F1 = ïƒ¥ï€ (m3, m4, m5, m6, m7) = ïƒ¥ï€ (m4, m5, m6, m7)
+ï€ ïƒ¥ï€ (m3, m7) = [A·B’·C’+ A·B’·C + A·B·C’+ A·B·C] + [A’·B·C +
A·B·C].
El primer término en la sumatoria es el grupo 1 y el segundo término
corrresponde al grupo 2. En un mapa de karnaugh, los mintérminos de cada grupo
se relacionarían a través de lazos independientes.
Desarrollando la expresión,
F1 = [A·B’·(C’+C) + A·B·(C’+ C)] + [B·C·(A’+A)]= A·B’·(1) + A·B·(1) + B·C·(1) =
A·(B’+B) + B·C = A + B·C.
El mapa se construye colocando un 1 en las celdas correspondientes a los
mintérminos presentes en la función de salida. Por ejemplo, para el término
F(1,1,0)= A·B·C’ = 1 se situaría un 1 en la celda 110. Para
los mintérminos no presentes en la función se pone un 0. Por ejemplo el término
F(0,0,1)= A’·B'·C = 0, será una celda con valor 0 en la celda 001.
Después de situar los unos en el mapa, se procede con la agrupación de 1s, la
determinación del
término productocorrespondiente a cada grupo y la suma de los términos producto
obtenidos. La determinación del término
producto se realiza de acuerdo los siguientes criterios:
1.Una celda representa un mintérmino, dando como resultado un término de cuatro
literales.
2. Dos celdas agrupadas pueden representar la asociación de dos mintérminos,
dando como
resultado un término de dos literales.
3.Cuatro celdas agrupadas pueden representar la asociación de cuatro
mintérminos, dando como
resultado un término de un literal.
4. Ocho celdas agrupadas representan un valor de función igual a 1.
Ejemplo
Sea la función del
ejemplo anterior, simplificarla por medio del
método del
mapa.
La tabla de verdad del ejemplo anterior es la siguiente,
Línea | A | B | C | Salida F |
0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 1 | 0 |
2 | 0 | 1 | 0 | 0 |
3 | 0 | 1 | 1 | 1 |
4 | 1 | 0 | 0 | 1 |
5 | 1 | 0 | 1 | 1 |
6 | 1 | 1 | 0 | 1 |
7 | 1 | 1 | 1 | 1 |
Tabla 2.4.2. Tabla de verdad de la función F1.
El mapa de Karnaugh se configura de acuerdo a los mintérminos iguales a 1 y las
celdas se agrupan tal como
en la figura 2.4.1.
Figura 2.4.1. Mapa de Karnaugh de la función F1.
El primer grupo se forma con los mintérminos m4, m5, m6 y m7 y el segundo grupo
con los mintérminos m3 y m7.
Del primer grupo resulta el término A ya que para las cuatro columnas de la
tabla existentransiciones entre las variables B y C. El segundo grupo da como
resultado el término BC por el cambio existente en la variable A.
En total, la función queda reducida a la expresión:
F1 = A + B·C
Mapa de Karnaugh de cuatro variables
La construcción de un mapa de Karnaugh de 4 variables es similar al de 3
variables. La diferencia radica en el número de variables de entrada. El mapa
por medio de una matriz de 16 celdas, representa los 16 mintérminos posibles
(24) que se pueden obtener con cuatro variables de entrada, en un arreglo de 4
x 4. La disposición de celdas en el mapa se muestra en la tabla 2.4.3.
Línea | A | B | C | D | Mintérmino | Mintérmino mx | Función de Salida |
0 | 0 | 0 | 0 | 0 | A’·B’·C’·D’ | m0 | F(0,0,0,0) |
1 | 0 | 0 | 0 | 1 | A’·B’·C’·D | m1 | F(0,0,0,1) |
2 | 0 | 0 | 1 | 0 | A’·B’·C·D’ | m2 | F(0,0,1,0) |
3 | 0 | 0 | 1 | 1 | A’·B’·C·D | m3 | F(0,0,1,1) |
4 | 0 | 1 | 0 | 0 | A’·B·C’·D’ | m4 | F(0,1,0,0) |
5 | 0 | 1 | 0 | 1 | A’·B·C’·D | m5 | F(0,1,0,1) |
6 | 0 | 1 | 1 | 0 | A’·B·C·D’ | m6 | F(0,1,1,0) |
7 | 0 | 1 | 1 | 1 | A’·B·C·D | m7 | F(0,1,1,1) |
8 | 1 | 0 | 0 | 0 | A·B’·C’·D’ | m8 | F(1,0,0,0) |
9 | 1 | 0 | 0 | 1 | A·B’·C’·D | m9 | F(1,0,0,1) |
10 | 1 | 0 | 1 | 0 | A·B’·C·D’ | m10 | F(1,0,1,0) |
11 | 1 | 0 | 1 | 1 | A·B’·C·D | m11 |F(1,0,1,1) |
12 | 1 | 1 | 0 | 0 | A·B·C’·D’ | m12 | F(1,1,0,0) |
13 | 1 | 1 | 0 | 1 | A·B·C’·D | m13 | F(1,1,0,1) |
14 | 1 | 1 | 1 | 0 | A·B·C·D’ | m14 | F(1,1,1,0) |
15 | 1 | 1 | 1 | 1 | A·B·C·D | m15 | F(1,1,1,1) |
(a)
(b) | (c) |
Tabla 2.4.3. Mapa de cuatro variables
Por ejemplo, la celda m9 corresponde al mintérmino 9, ubicado en la fila 10 y
la columna 01. La unión de estos dos números da el número 1001, cuyo
equivalente es el término A·B’·C’·D -ó el decimal 9.
La minimización por medio de un mapa de 4 variables se puede efectuar con las
celdas adyacentes entre sí y las celdas de los bordes que se pueden concatenar
para reducir la expresión. Por ejemplo, m13 y m15 son celdas adyacentes así como m0, m8, m2 y m10.
El mapa se construye colocando un 1 en las celdas correspondientes a los
mintérminos presentes en la función de salida. Por ejemplo, para el término
F(1,1,0,0)= A·B·C’·D’ = 1 se situaría un 1 en la celda 1100. Para
los mintérminos no presentes en la función se pone un 0. Por ejemplo el término
F(1,1,1,1)= A·B·C·D = 0, será una celda con valor 0 en la celda 1111.
Igual que en el mapa de 3 variables, se procede con la agrupación de 1s, la
determinación del
término producto correspondiente a cada grupo y la suma de los términos
producto obtenidos.
Las reglas para reducir términos en un mapa de Karnaugh de 4 variables son las
siguientes:1.Una celda representa un mintérmino, dando como resultado un término de cuatro
literales.
2. Dos celdas agrupadas pueden representar la asociación de dos mintérminos,
dando como
resultado un término de tres literales.
3.Cuatro celdas agrupadas pueden representar la asociación de cuatro
mintérminos, dando como
resultado un término de dos literales.
4.Ocho celdas agrupadas pueden representar la asociación de ocho mintérminos,
dando como
resultado un término de un literal.
5. Dieciséis celdas agrupadas pueden representan un valor de función igual a 1.
Ejemplo
Simplíquese la función de Boole F2= ïƒ¥ï€ (m1, m3, m8, m10, m12, m14)
Figura 2.4.2. Mapa de Karnaugh de la función F2.
El primer grupo se forma con los mintérminos m1 y m3 y el segundo grupo se
forma con los mintérminos m8, m10 y m12, m14.
Del primer
grupo resulta el término A’·B’·D ya que en la columna 1 no se presentan cambios
para las variables A y B y se presenta transición en la variable C en las
columnas 2 y 3. El segundo grupo da como
resultado el término A·D’. La razón radica en la simplificación de la variable
B en la tercera y cuarta fila y en la variable C en la primera y cuarta
columna.
Sumando los mintérminos obtenidos se tiene la ecuación simplificada:
F2 = A’·B’·D + A·D’
Mapas de Karnaugh empleando Producto de Sumas (PDS)
La simplificación de expresiones lógicas mediante el mapa de Karnaugh también
es posiblemediante el método de producto de sumas. En este método, cada celda
representa un maxtérmino.
La construcción del
mapa es similar a la suma de productos. La diferencia radica en que cada celda
representa un maxtérmino. Por ejemplo, la celda m2 corresponde al maxtérmino 2,
ubicado en la fila 0 y la columna 10. La unión de estos dos números da el
número 010, cuyo equivalente es el término A+B’+C. La figura 2.4.3. muestra el
mapa de Karnaugh para 3 variables.
Figura 2.4.3. Mapa de tres variables.
La representación de la función lógica se hace simplemente copiando los ceros
de la tabla de verdad en las celdas del
mapa. Este método es más apropiado cuando en la columna de resultados de la
tabla de verdad predominan los ceros.
Ejemplo
Utilizar el mapa de Karnaugh para minimizar el producto de sumas,
F3 = (A+B+C)·(A’+B+C)·(A+B’+C)·(A’+B’+C)
Los maxtérminos se trasladan a cada una de las celdas del mapa de Karnaugh y
las celdas se agrupan tal como en la figura 2.4.4.
Figura 2.4.4. Mapa de Karnaugh de la función F3
El término suma para cada grupo se muestra en la figura y la suma de productos
resultante es:
F3 = C
Ejemplo
Utilizar el mapa de Karnaugh para minimizar el producto de sumas,
F4 =
(A+B+C+D)·(A+B’+C)·(A+B’+C’+D’)·(A’+B’+C+D’)·(A’+’B+C’+D’)·(A’+B+C+D’)·(A’+B+C’+D’)·(A’+B'+C+D’)
El segundo término tiene que ampliarse a (A+B’+C+D)·(A+B’+C+D’). La función
completa se pasaal mapa de karnaugh mostrado en la figura 2.4.5.
Figura 2.4.5. Mapa de Karnaugh de la función F4
El término suma para cada grupo se muestra en la figura 2.4.5. y el producto de
sumas resultante es:
F4 = (A+C+D)·(B'+D')·(A'+D')
Condiciones de No Importa
Hasta el momento se ha asumido que la función es igual a 0 en los casos donde
la función no es igual a 1. En algunas aplicaciones esta suposición no es
siempre verdadera ya que existen combinaciones de entrada que no presentan. En
un mapa de Karnaugh estas combinaciones de entrada sirven de herramienta para
simplificar la función y su representación se hace por medio de una X en la
celda del
mapa. Según la agrupación que convenga se asume un valor de 1 ó 0 para la X con
el fin de obtener la expresión más simple.
Ejemplo
Simplificar la función de Boole F5 =ï€ ï“ï€ (m0, m4, m7, m9) con
condiciones de importa, NI = ï“ï€ (m1, m5, m11, m14).
Los mintérminos se marcan con un 1, las condiciones de no importa con una X y
las celdas restantes con 0.
El mapa de Karnaugh de la función F5 se muestra en la figura 2.4.6.
Figura 2.4.6. Mapa de Karnaugh de la función F5
En suma de productos obtenemos,
F5 = A’·C’·D’ + A'·B’·C’ + A’·B·C·D + A·B'·D
__
Algoritmo de Quine – McCluskey
El empleo del
mapa de Karnaugh es conveniente cuando la función a minimizar no contiene más
de cinco o seis variables. En estos casos, empleamos un
procedimientosistemático, llamado el algoritmo de Quine–McCluskey, el cual
produce una expresión normalizada y simplificada. El algoritmo debe obedecer a
un conjunto de pasos que se verán a través de un ejemplo.
Ejemplo
Simplificar la función de Boole usando el algoritmo de Quine-McCluskey.
F1 = | ïƒ¥ï€ (m1, m2, m3, m6, m7, m8, m9, m10, m15) |
F1 = | A’·B’·C’·D + A’·B’·C·D’+ A’·B’·C·D + 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. Enumerar en una tabla todos los mintérminos en forma binaria, organizados
según el número de unos que contenga. La aplicación de este paso se muestra en
la tabla 2.5.1.
Mintérminos | A | B | C | D | Grupo |
1 | 0 | 0 | 0 | 1 | Grupo 1 |
2 | 0 | 0 | 1 | 0
8 | 1 | 0 | 0 | 0
3 | 0 | 0 | 1 | 1 | Grupo 2 |
6 | 0 | 1 | 1 | 0
9 | 1 | 0 | 0 | 1
10 | 1 | 0 | 1 | 0
7 | 0 | 1 | 1 | 1 | Grupo 3 |
15 | 1 | 1 | 1 | 1 | Grupo 4 |
Tabla 2.5.1. Mintérminos agrupados según la cantidad de unos
2. Entre los grupos adyacentes buscar los mintérminos que sólo difieren en un
bit en la misma posición, para hallar los primeros implicantes primos.
La metodología consiste en comparar el primer mintérmino con el resto de los
términos del
segundo grupo. Así, los términos del segundo
grupo se comparan con los mintérminos del
grupo siguiente. De la forma anterior, seprocede con los demás mintérminos de
los demás grupos. Los mintérminos utilizados se les pone una marca (√ )
con el fin de ir diferenciando los términos utilizados y la variable apareada
en el proceso se reemplaza con un guión para denotar la eliminación de la
variable. Los términos no marcados en la tabla son los primeros implicantes
primos (PIX). Los mintérminos utilizados se les pone una marca (√ ) con
el fin de ir diferenciando los términos utilizados y la variable apareada en el
proceso anterior se reemplaza con un guión para denotar la eliminación de la
variable.
Mintérmino | A | B | C | D | Mintérmino | A | B | C | D | PIx | Mintérmino | A
| B | C | D | PIx |
1 √ | 0 | 0 | 0 | 1 | 1–3 | 0 | 0 | - | 1 | PI2 | 2–6 - 3-7 | 0 | - | 1 |
- | PI1 |
2 √ | 0 | 0 | 1 | 0 | 1–9 | - | 0 | 0 | 1 | PI3 | 2-3 - 6-7 | 0 | - | 1 |
- | |
8 √ | 1 | 0 | 0 | 0 | 2–3 √ | 0 | 0 | 1 | - | | |
| | | | |
3 √ | 0 | 0 | 1 | 1 | 2–6 √ | 0 | - | 1 | 0 | | |
| | | | |
6 √ | 0 | 1 | 1 | 0 | 2–10 | - | 0 | 1 | 0 | PI4 | | |
| | | |
9 √ | 1 | 0 | 0 | 1 | 8–9 | 1 | 0 | 0 | - | PI5 | | |
| | | |
10 √ | 1 | 0 | 1 | 0 | 8-10 | 1 | 0 | - | 0 | PI6 | | |
| | | |
7 √ | 0 | 1 | 1 | 1 | 3–7 √ | 0 | - | 1 | 1 | | |
| | | | |
15 √ | 1 | 1 | 1 | 1 | 6–7 √ | 0 | 1 | 1 | - | | |
| | | | |
| | | | | 7-15 | - | 1 | 1 | 1 | PI7 |
| | | | | |
Tabla 2.5.2. Implicantes primos de la función F1
3. Construir una tabla que enumere los implicantes primos y los mintérminos
contenidos por cada implicante primo. La letra X en la tabla 2.5.3 indica el
mintérmino contenido en cada implicado por fila. Por ejemplo, en la tabla se
observa en el primer renglón los mintérminos 2, 3, 6 y 7 para el primer
implicante primo. El resto de la tabla se construye de forma similar.
Implicante Primo | 1 | 2 | 3 | 6 | 7 | 8 | 9 | 10 | 15 |
* PI1 | | X | X | X | X | | | | |
PI2 | X | | X | | | | | | |
PI3 | X | | | | | | X | | |
PI4 | | X | | | | | | X | |
PI5 | | | | | | X | X | | |
PI6 | | | | | | X | | X | |
* PI7 | | | | | X | | | | X |
Tabla 2.5.3. Selección de implicantes primos esenciales
En la tabla se seleccionan las columnas de los mintérminos que contengan
solamente una cruz. En este ejemplo, hay dos mintérminos cuyas columnas tienen
una sola cruz: 6 y 15. Es decir, la selección del primer implicado PI1 (A’·C) garantiza
que el término mínimo 6 está incluido en la función. De la misma forma, el
término mínimo 7 está cubiertopor el primer implicado PI7 (A'·B·C·D). Los
primeros implicados que cubren los mintérminos con una sola cruz, se llaman
primeros implicados esenciales (en la tabla se encuentran marcados con un
asterisco) y son indispensables en la construcción de la función.
4. Seleccionar en cada columna los mintérminos que estén cubiertos por los
primeros implicados esenciales. Por ejemplo, el primer implicado esencial * PI1
(A’·C) cubre los mintérminos 2, 3, 6 y 7. De la misma forma, el primer
implicado esencial *PI7 (A'·B·C·D) cubre los mintérminos 7 y 15. Hasta el
momento la selección de primeros implicados cubre los mintérminos 2, 3, 6, 7 y
15 excepto 1, 8, 9 y 10. Estos términos mínimos deben ser seleccionados por
medio de otros primeros implicados esenciales. En la tabla 2.5., la selección
de los primeros implicados PI3 y PI6 garantiza el cubrimiento de los términos
mínimos 1, 8, 9 y 10. En la tabla 2.5.4. se muestra el proceso de selección.
Implicante Primo | 1 | 8 | 9 | 10 |
PI2 | X | | | |
*PI3 | X | | X | |
PI4 | | | | X |
PI5 | | X | X | |
*PI6 | | X | | X |
Tabla 2.5.4. Selección de primeros implicados esenciales
La función simplificada se obtiene de la suma de los primeros implicados
hallados:
F= PI1 + PI3 +PI6 + PI7
F= (0-1-) + (-001) + (10-0) + (-111)
F = A'·C + B’·C’·D + A·B’·D’ + B·C·D
