Otra manera de simplificarfuncioneses representándolas enmapasde Karnaugh. Esto es equivalente a resolver las simplificaciones por teoremas. Sin embargo, mucha gente considera que resulta más fácil visualizar las simplificaciones si se presentan gráficamente.
Los mapas de Karnaugh pueden aplicarse a dos, tres, cuatro y cinco variables. Para másvariables, la simplificación resulta tan complicada que conviene en ese caso utilizar teoremas mejor. Para efectos de clase, veremos las simplificaciones de dos, tres y cuatro variables.
MÉTODO DE REDUCCIÓN DE MAPAS DE KARNAUGH
El Álgebra de Boole, resuelve problemas que dependiendo del número de términos que tenía la función canónica, siendo el número de compuertas lógicas utilizadas igual al número de términos obtenidos MÁS UNO; por lo tanto, los circuitos obtenidos son de dos niveles de conmutación con un tiempo mínimo de retardo, pero que de ninguna manera es el más sencillo ni el más económico.
Los mapas de Karnaugh es uno de los métodos más prácticos. Se puede decir que es el más poderoso, cuando el número de variables de entrada es menor o igual a seis; más allá, ya no es tan práctico. En general, el mapa de Karnaugh se considera como la forma gráfica de una tabla de verdad o como una extensión del diagrama de Venn.
Antes de explicar cómo se utiliza el mapa de Karnaugh en la minimización de funciones, veremos cómo se obtiene el mapa. Esto nace de la representación geométrica de los números binarios. Un número binario de n bits, puede representarse por lo que se denomina un punto en un espacio N. Para entender lo que se quiere decir con esto, considérese el conjunto de los números binarios de un bit, es decir 0 o 1. Este conjunto puede representarse por dos puntos en un espacio 1; esto es, por dos puntos unidos por una línea.
Para una función booleana de n variables x1,...xn,
un producto booleano en el que cada una de las n variables
aparece una sola vez (negada o sin negar) es llamado minterms. Es
decir, un minterms es una expresión lógica de n variables
consistente únicamente en el operador conjunción lógica (AND) y el operador
complemento o negación (NOT).
Por ejemplo, abc, ab'c y abc'
son ejemplos de minterms para una función booleana con las tres variables a, b y c.
En general, uno asigna a cada minterm (escribiendo las variables que lo
componen en el mismo orden), un índice basado en el valor binario del minterm.
un término negado, como a' es considerado como el numero binario 0
y el término no negado a es considerado como un 1. Por
ejemplo, se asociaría el número 6 con abc'(1102),
y nombraríamos la expresión con el nombre m6. Entonces m0 de
tres variables esa'b'c'(0002) y m7 debería
ser abc(1112).
Función equivalente
Se puede observar que cada minterm solo devuelve 'verdadero' con una
sola entrada de las posibles. Por ejemplo, el minterm 5, ab' c,
es verdadero solo cuando a y c son ciertos y b es
falso - la entrada a = 1, b = 0, c = 1 da resultado 1.
Si tenemos una tabla de verdad de una función lógica, es posible
escribir la función como "suma de productos". Por ejemplo, dada la
tabla de verdad
abf(a, b)
0 0 1
0 1 0
1 0 1
1 1 0
Observamos que las filas con resultado 1 son la primera y la tercera,
entonces podremos escribir f como la suma de los minterms m0 y m2.
Si queremos verificar esto:
f(a,b) = m0 + m2 =
(a'b')+(ab')
Tendremos que la tabla de verdad de la función, calculándola
directamente, será la misma.
Maxitérminos
Un maxterm es una expresión lógica de n variables
que consiste únicamente en la disyunción lógica y el operador complemento o
negación. Los maxterms són una expresión dual de los minterms. En vez de usar
operaciones AND utilizamos operaciones OR y procedemos de forma similar.
Por ejemplo, los siguientes son maxterms:
a+b'+c
a'+b+c
El complemento de un minterm es su respectivo maxterm. Esto puede ser
fácilmente verificado usando la Ley de Morgan. Por ejemplo:
m1' = M1
(a'b)' = a+b'
Para indexar maxterms lo haremos justo de la forma contraria a la que
seguimos con los minterms. Se asigna a cada maxterm un índice basado en el
complemento del número binario que representa (otra vez asegurándonos que las
variables se escriben en el mismo orden, usualmente alfabético). Por ejemplo,
podemos asignar M6 (Maxterm 6) al maxterma'+b'+c.
De forma similar M0 de tres variables debería ser a+b+c y M7 es a'+b'+c'.
Función equivalente
Se puede ver fácilmente que un maxterm sólo da como resultado un cero
para una única entrada de la función lógica. Por ejemplo, el maxterm 5, a'+b+c',
es falso solo cuando a yc son ciertos y b es
falso - la entrada a = 1, b = 0, c = 1 da como resultado un cero.
Si tenemos una tabla de verdad de una función lógica, es posible
escribir la función como "producto de sumas". Por ejemplo, dada la
tabla de verdad
abf(a, b)
0 0 1
0 1 0
1 0 1
1 1 0
Observamos que las filas que tiene como salida un 0 son la segunda y la
cuarta, entonces podemos escribir f como un producto de
maxterms M1 y M3.
Si queremos verificar esto:
f(a,b) = M1M3 =
(a+b')(a'+b')
Tendremos que la tabla de verdad de la función, calculándola
directamente, será la misma
2.1TEOREMAS Y POSTULADOS DEL
ALGEBRA DE BOOLE. POSTULADOS DE MORGAN
1. Propiedad de cierre.
Para un conjunto s se dice que es cerrado
para un operador binario si para cada elemento de S el operador binario
especifica una regla para obtener un elemento único de S.
Para el conjunto N = {1,2,3,4,…} es
cerrado con respecto al operador binario (+) por las reglas de la adición
aritmética, ya que para que cualquier elemento a,b pertenecientes a N por la
operación a + b = c el conjunto de los números naturales no esta cerrado con
respecto al operador binario (-) por la regla de la resta aritmética, debido a
que 2-3 = -1 y 2,3 pertenecen a N pero -1 no pertenece a N.
2. Ley asociativa.
El operador binario (*) es un conjunto S
es asociativo siempre que
x*y*z = x*(y*z) para toda x, y pertenecientes a S.
3. Ley conmutativa.
Un operador binario (*) para un conjunto S es conmutativo
siempre que:
x*y = y*x para toda x,y pertenecientes a S.
4. Elemento identidad.
El conjunto S tendrá un elemento identidad multiplicativo
“identidad (*)” en S si existe un e perteneciente a S con la propiedad e*x =
x*e =e para cada x pertenecientes a S.
5. Inversa.
El conjunto S tiene un elemento identidad (e) con respecto al
operador (*) siempre que para cada x perteneciente a S exista un elemento y
perteneciente a S tal que x*y=e.
6. Ley distributiva.
Si el operador (*) y el operador (.), son operadores binarios
de S, (*) se dice que es distributivo sobre (.).
Siempre que:
x*(y . z) =
(x*y) . (x*z)
- El operador
binario (+) define la adición.
- Identidad aditiva es el cero.
- La inversa aditiva define la sustracción.
- El operador binario (.) define la multiplicación.
- Identidad multiplicativa es 1.
- Inversa multiplicativa de A es igual a 1/A define la división esto es A
* 1/A = 1
- La única ley distributiva aplicable es la de operador (.) sobre el operador +
(.) sobre (+) a(b+c)=(a.b) +(a.c)
Para definir formalmente el álgebra de Boole se emplean postulados de
Huntington.
1.
a) Cierre con respecto al operador (+)
b) Cierre con respecto al operador (.)
2.
a) Un elemento identidad con respecto al operador (+), designado por el cero
x+0 =0+x=x
b) Un elemento identidad con respecto al operador (.) designado por el uno
x*1=1*x=x
3.
a) Conmutativo con respecto al operador (+) : x+y = y+x
b) Conmutativo con respecto al operador (.) : x*y =y*x
4.
a) El operador (.) es distributivo sobre el operador (+) : x.(y+z) = (x.y) +
(y.z)
b) El operador (+) es distributivo sobre el operador (.) : x+(x.z) = (x+y) .
(x+z)
5. Para cada elemento de x pertenencia a B existe un
elemento x’ complemento perteneciente a B denominado complemento de x tal que:
a) x+x’ = 1
b) x’ = 0
6. Existen cuando
menos dos elementos x,y pertenecientes a B tal que x diferente de y. Por
lo tanto tenemos que el álgebra de Boole difiere de la aritmética y del álgebra
ordinaria en la sig:
a) Los
postulados Huntington: no incluyen al ley asociativa, no obstante esta ley es
valida para el álgebra booleana (para ambos operadores)
b) La ley distributiva del operador (+) sobre el operador (.)
esto es: x+(y.z) = (x+y).(x+z), la cual es valida para el álgebra de boole pero
no para el álgebra ordinaria.
c) El álgebra booleana no tiene inversa aditiva a
multiplicativa, por lo tanto no hay operaciones de sustracciones o división.
d) El postulado 5 define un operador llamado completo que no
se encuentra en el álgebra ordinaria.
e) En el algebra de Boole se define un conjunto B de dos
elementos (0 y 1) y el álgebra ordinaria trata con el conjunto de los números
reales.
Postulado
2
a) x + 0 =
x
b) x . 1 = x
Postulado
5 a) x + x’ =
1
b) x . x’ = 0
Teorema 1
a) x + x =
x
b) x . x = x
Teorema 2
a) x + 1 =
1
b) x . 0 = 0
Teorema 3 involución (x’)’ = x
Teorema 3 conmutativo a) x +
y = y +
x
b) xy = yx
Teorema 4 asociativo a)
x + (y + z) = (x + y) +z b) x (yz) = (xy) z
Postulado 4 distributivo a) x (y
+ z) = xy
+xz b) x
+ yz = (x + y)(x+z)
Teorema 5 morgan a) ( x + y)’ = x’
y’
b) (xy) = x’ + y’
Teorema 6 absorción a)
x + xy =
x
b) x (x + y) = x
Ejemplos:
x + x =
x
x + xy = x
x + x = (x + x) .
1
x . 1 + xy = x
x + x = (x + x) (x + x’)
x (1 + y) = x
x + x = x +
xx’
x (y + 1) = x
x + x = x +
0
x (1) = x
x + x =
x
x = x
Las variables booleanas pueden tomar varios valores de 1 ó 0.
Una función booleana es una expresión formada por variables binarias.
Ejemplo:
F1 = xyz’
Para F1 considerar que es igual a 1 si:
x = 1; y = 1 ; z’ = 1;
de otra manera F1 = 0.
Por lo tanto tendremos que una función booleana también puede representarse en
una tabla de verdad. Para representar una función booleana en una tabla
de verdad se necesita una lsit de 2ncombinaciones de 1 y 0 de las n variables
binarias, y una columna que muestra combinaciones para las cuales f es igual a
1 ó 0.
Cuando una función se incrementa con compuertas lógicas, cada literal en la
función denota una entrada a una compuerta.
1. Cada
literal denota la entrada a una compuerta.
2. Cada termino se implanta con una compuerta.
Por el momento nos limitaremos a la minimización por literales. Por lo
cual debe quedar muy claro que en la manipulación algebraica no hay reglas
especificas a seguir a que garanticen la respuesta final.
Ejemplo: Reducir las siguientes funciones booleanas.
El complemento de una función F es F’ obteniendose por el intercambio de 1’s y
0’s y de 0’s y 1’s.
Ejemplo:
(A+B+C)’ =
(A+X)’ para X = B+C
A’ . X’ ? A’ . (B+C)’ ? A’ . B’ .C’
(A+B+C+D+E+F+……..I)
(A’.B’.C’.D’.E’.F’…….I’)
La forma generalizada de D’Morgan enuncia que el complemento de una función se
obtiene del intercambio de los operadores AND y OR y complementando cada
literal.
F1 = (x’yz’
+ x’y’z)’ = (x+y’+z . x+y+z’)
F2 = ? x (y’z’+yz)? = x’ + ? x (y+z).(y’+z’)?
Otra forma más simple para derivar el complemento de una función es tomar el
dual de la función y complementar cada literal.
Hay que recordar que el cual de una función se obtiene por el intercambio de
los operadores AND y OR y los 1’s y los 0’s.
Ejemplo:
F1 = x’yz’ + x’y’z el dual: F1 = (x+y’+z) . (x+y+z’)
Las variables pueden ser normales (x) ó complemento (x’).
Cuando tenemos un conjunto de n variables nosotros podemos formar 2n
miniterminos de acuerdo a la siguiente tabla:
Para n=3 2n-1 combinaciones iniciando a partir de cero.
Cada minitérmino lo obtenemos de un
término AND de las n variables y complementado cada variable si el número
binario que representa es un 0 y no complementando si es un 1.
Cada minitermino
se representa por mj donde j representa el equivalente decimal del número
binario del minitermino de la misma forma podemos tener los maxiterminos con
las n variables formando un término OR para cada maxitermino.
En estas se hace
la consideración de que cada variable no complementada corresponde al bit 0 y
complementada al bit 1.
El complemento de una función booleana lo
podemos obtener al formar miniterminos para cada combinación que produce un
cero en la función y aplicando el operador OR a esos términos.
Las funciones booleanas expresadas como una suma de miniterminos o productos de
maxiterminos se dice que esta en forma canónica.
2.3. SIMPLIFICACION DE
FUNCIONES
Suma de miniterminos.
Como sabemos cualquier función booleana
puede expresarse como una suma de miniterminos. La suma de estos
elementos que son los que definen una función booleana son aquellos que dan los
1’s de la función en una tabla de verdad.
Algunas veces es conveniente expresar la
función booleana en la forma de suma de miniterminos. Si no puede hacerse
en esta forma entonces puede realizarse primero por la expansión de la
expresión en una suma de los términos AND.
Después cada término se inspecciona para ver
si contiene todas las variables, si se han perdido una o más variables, se
aplica el operador AND con una expresión x+x’ en donde x es una de las
variables perdidas.
Ejemplo: Expresar la función F = A+B’C en una
suma de miniterminos.
F = ABC+ABC’+AB’C+AB’C’+AB’C+A’B’C
F = A’B’C+AB’C’ +AB’C+ABC’+ABC
F = m1+ m4+m5+ m6+ m7
F(A,B,C)=SUM(1,4,5,6,7)
La sumatoria representa al operador OR que opera en los términos y números
siguientes son los minitérminos de la función.
Las letras entre paréntesis que siguen a F forman una lista
de las variables en el orden tomado cuando el minitérmino se convierte en un
término AND.
Producto de los maxitérminos.
Para expresar una función booleana como un producto de maxitérminos, primero
debe llevarse a una forma de términos OR. Esto es posible al uso de la
ley distributiva; esto es si x+yz = (x+y) (x+z); para cualquier variable
perdida x en cada término se opera a OR con xx’.
Álgebra
de Boole (también llamada álgebra booleana) en informática y matemática, es una
estructura algebraica que esquematiza las operaciones lógicas Y, O, NO y SI
(AND, OR, NOT, IF), así como el conjunto de operaciones unión, intersección y
complemento.
Se denomina así en honor a George Boole (2 de
noviembre de 1815 a 8 de diciembre de 1864), matemático inglés autodidacta, que
fue el primero en definirla como parte de un sistema lógico, inicialmente en un
pequeño folleto: The Mathematical Analysis of Logic,1 publicado en 1847, en
respuesta a una controversia en curso entre Augustus De Morgan y sir William
Rowan Hamilton. El álgebra de Boole fue un intento de utilizar las técnicas
algebraicas para tratar expresiones de la lógica proposicional. Más tarde fue extendido
como un libro más importante: An Investigation of the Laws of Thought on Which
are Founded the Mathematical Theories of Logic and Probabilities (también
conocido como An Investigation of the Laws of Thought2 o simplemente The Laws
of Thought3 ), publicado en 1854.
En
la actualidad, el álgebra de Boole se aplica de forma generalizada en el ámbito
del diseño electrónico. Claude Shannon fue el primero en aplicarla en el diseño
de circuitos de conmutación eléctrica biestables, en 1948. Esta lógica se puede
aplicar a dos campos:
• Al análisis, porque es una forma
concreta de describir como funcionan los circuitos.
• Al diseño, ya que teniendo una función
aplicamos dicha álgebra, para poder desarrollar una implementación de la
función.
Definición
Dado
un conjunto: formado cuando menos por
los elementos: en el que se ha
definido:
• Una operación unaria interna, que
llamaremos complemento:
En
esta operación definimos una aplicación que, a cada elemento a de B, le asigna
un b de B.
Para
todo elemento a en B, se cumple que existe un único b en B, tal que b es el
complemento de a.
• La operación binaria interna, que
llamaremos suma:
por
la que definimos una aplicación que, a cada par ordenado (a, b) de B por B, le
asigna un c de B.
Para
todo par ordenado (a, b) en B por B, se cumple que existe un único c en B, tal
que c es el resultado de sumar a con b.
• La operación binaria interna, que
llamaremos producto:
Con
lo que definimos una aplicación que, a cada par ordenado (a, b) de B por B, le
asigna un c de B.
Para
todo par ordenado (a, b) en B por B, se cumple que existe un único c en B, tal
que c es el resultado del producto a y b.
Dada
la definición del álgebra de Boole como una estructura algebraica genérica,
según el caso concreto de que se trate, la simbología y los nombres de las
operaciones pueden variar.
Axiomas
necesarios
Diremos
que este conjunto y las operaciones así definidas: son un álgebra de boole, si cumple las
siguientes axiomas:
• 1a: La ley asociativa de la suma:
• 1b: La ley asociativa del producto:
• 2a: Existencia del elemento neutro para
la suma:
• 2b: Existencia del elemento neutro para
el producto:
• 3a: La ley conmutativa de la suma:
• 3b: La ley conmutativa del producto:
• 4a: Ley distributiva de la suma
respecto al producto:
• 4b: Ley distributiva del producto
respecto a la suma:
• 5a: Existe elemento complemento para la
suma:
• 5b: Existe elemento complemento para el
producto:
Teoremas
fundamentales
Partiendo
de los cinco axiomas anteriores, se pueden deducir y demostrar los siguientes
teoremas fundamentales:
• 6a: Ley de idempotencia para la suma:
• 6b: Ley de idempotencia para el
producto:
• 7a: Ley de absorción para la suma:
• 7b: Ley de absorción para el producto:
• 8a: Ley de identidad para la suma:
• 8b: Ley de identidad para el producto:
• 9: Ley de involución:
• 10: Ley del complemento:
• 11: Leyes de De Morgan:
Orden
en el álgebra de Boole
Sea: un álgebra de Boole, sean a, b dos elementos
del conjunto, podremos decir entonces que a antecede a b y lo denotamos:
si
se cumple alguna de las siguientes condiciones:
Estas
cuatro condiciones se consideran equivalentes y el cumplimiento de una de ellas
implica necesariamente el cumplimiento de las demás. Definiendo un conjunto
parcialmente ordenado.
Si
se cumple que:
Para
los valoras a, b de , que cumples qua a
antecede a b, o que b antedede a a, se dice que a y b son comparables.
Si
se cumple que:
Para
los valoras a, b de , que cumples qua a
no antecede a b, y que b no antedede a a, se dice que a y b son no comparables.
Principio
de dualidad
El
concepto de dualidad permite formalizar este hecho: a toda relación o ley
lógica le corresponderá su dual, formada mediante el intercambio de los
operadores suma con los de producto, y de los
con los .
Otras
formas de notación del álgebra de Boole
En
Lógica binaria se suele emplear la notación
, común en la tecnología digital, siendo la forma más usual y la más cómoda
de representar.
Por
ejemplo las leyes de De Morgan se representan así:
Cuando
el álgebra de Boole se emplea en electrónica, suele emplearse la misma
denominación que para las puerta lógica AND (Y), OR (O) y NOT (NO), ampliándose
en ocasiones con X-OR (O exclusiva) y su negadas NAND (NO Y), NOR (NO O) y
X-NOR (equivalencia). las variables pueden representarse con letras mayúsculas
o minúsculas, y pueden tomar los valores {0, 1}
Empleando
esta notación las leyes de De Morgan se representan:
En
su aplicación a la lógica se emplea la notación y las variables pueden tomar los valores {F,
V}, falso o verdadero, equivalentes a {0, 1}
Con
la notación lógica las leyes de De Morgan serían así:
En
el formato de Teoría de conjuntos el Álgebra de Boole toma el aspecto:
En
esta notación las leyes de De Morgan serían así:
Otra
forma en la álgebra de conjuntos del Álgebra de Boole, las leyes de De Morgan
serían así:
Desde
el punto de vista práctico existe una forma simplificada de representar
expresiones booleanas. Se emplean apóstrofos (') para indicar la negación, la
operación suma (+) se representa de la forma normal en álgebra, y para el
producto no se emplea ningún signo, las variables se representan, normalmente
con una letra mayúscula, la sucesión de dos variables indica el producto entre
ellas, no una variable nombrada con dos letras.
La
representación de las leyes de De Morgan con este sistema quedaría así, con
letra minúsculas para las variables:
y
así, empleando letras mayúsculas para representar las variables:
Todas
estas formas de representación son correctas, se utilizan de hecho, y pueden
verse al consultar bibliografía. La utilización de una u otra notación no
modifica el álgebra de Boole, solo su aspecto, y depende de la rama de las
matemáticas o la tecnología en la que se esté utilizando para emplear una u
otra notación.
Estructuras
algebraicas que son Álgebra de Boole
Hay
numerosos casos de distintas análisis de estructuras algebraicas que
corresponden al álgebra de Boole, aunque en apariencia son muy diferentes, su
estructura es la misma, vamos a ver algunos de ellos, con el propósito de hacer
palpable las similitudes en la estructura y los distintos ámbitos de aplicación
y distinta terminología para referirse a las operaciones o a las variables,
veámoslos.
Lógica
binaria
Artículo
principal: Lógica binaria
Artículo
principal: Sistema digital
Artículo
principal: Sistema binario
Artículo
principal: Tabla de verdad
Artículo
principal: Sistema combinacional
Artículo
principal: Formas canónicas (álgebra de Boole)
Artículo
principal: Circuito de conmutación
Una
serie de temas, aparentemente tan distintos, tiene dos cosas en común, la
lógica binaria basada en los ceros y los unos y el álgebra de Boole, posiblemente
la forma más conocida de este álgebra, que en ocasiones da lugar a la
interpretación que el álgebra de Boole es la lógica binaria exclusivamente, así
el conjunto en este caso está formado
por dos elementos {0,1}, o {F, V}, o {no, sí}, dos valores contrapuestos, que
son las dos posibles alternativas entre dos situaciones posibles, aquí, sin
perdida de la generalidad, tomaremos el conjunto: {0,1} como ya hemos dicho:
Donde:
• La operación unaria interna, que
llamaremos negación:
La
operación unaria interna negación, definimos una aplicación que a cada elemento
a de {0,1}, le asigna un b de {0,1}.
Para
todo elemento a en {0.1}, se cumple que existe un único b en {0,1}, tal que b
es la negación de a. Como se ve en la tabla.
• La operación binaria interna, que
llamaremos suma:
Con
la operación suma definimos una aplicación que, a cada par ordenado (a, b) de B
por B, le asigna un c de B.
Para
todo par ordenado (a,b) en B por B, se cumple que existe un único c en B, tal
que c es el resultado de sumar a con b.
• la operación binaria interna, que
llamaremos producto:
Con
la operación producto definimos una aplicación que, a cada par ordenado (a, b)
de B por B, le asigna un c de B.
Para
todo par ordenado (a, b) en B por B, se cumple que existe un único c en B, tal
que c es el resultado del producto a y b. Como se puede ver en la tabla.
Axiomas
Así es un álgebra de boole al cumplir los
siguientes axiomas:
• 1a: La ley asociativa de la suma:
• 1b: La ley asociativa del producto:
• 2a: Existencia del elemento neutro para
la suma:
• 2b: Existencia del elemento neutro para
el producto:
• 3a: La ley conmutativa de la suma:
• 3b: La ley conmutativa del producto:
• 4a: Ley distributiva de la suma
respecto al producto:
• 4b: Ley distributiva del producto
respecto a la suma:
• 5a: Existe elemento complementario para
la suma:
• 5b: Existe elemento complementario para
el producto:
Luego es álgebra de boole.
Teoremas
fundamentales
Partiendo
de estos axiomas se puede demostrar los siguientes teoremas:
.jpg)
