Embed Size (px)
Citation preview
INTRODUCCION:
Álgebra de Boole (también llamada Retículas booleanas) en informática y matemática,
es una estructura algebraica que conforman las operaciones lógicas Y, O y NO, 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 que fue el primero en definirla como parte de un sistema
lógico a mediados del siglo XIX. El álgebra de Boole fue un intento de utilizar las
técnicas algebraicas para tratar expresiones de la lógica proposicional. 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.
En el nivel de lógica digital de una computadora, lo que comúnmente se llama
hardware, y que está formado por los componentes electrónicos de la máquina, se
trabaja con diferencias de tensión, las cuales generan funciones que son calculadas por
los circuitos que forman el nivel. Estas funciones, en la etapa de diseño del hardware,
son interpretadas como funciones de Boole.
Asimismo, se plantean dos formas canónicas de las funciones booleanas, que son útiles
para varios propósitos, tales como el de determinar si dos expresiones representan o no
la misma función. Pero para otros propósitos son a menudo difíciles, por tener más
operaciones que las necesarias. Particularmente, cuando estamos construyendo los
circuitos electrónicos con que implementar funciones booleanas, el problema de
determinar una expresión mínima para una función es a menudo crucial. No resultan de
la misma eficiencia en dinero y tiempo, principalmente, dos funciones las cuales
calculan lo mismo pero donde una tiene menos variables y lo hace en menor tiempo.
Como solución a este problema, se plantea un método de simplificación, que hace uso
de unos diagramas especiales llamados mapas o diagramas de Karnaugh, y el cual tiene
la limitación de poder trabajar adecuadamente sólo con pocas variables.
Se realizan estas presentaciones con el fin de demostrar la afinidad existente entre el
álgebra de Boole y la lógica proposicional, y con el objeto de cimentar el procedimiento
de simplificación presentado en la lógica de proposiciones.
Álgebra de Booleana.
El algebra de boole es toda clase o conjunto de elementos que pueden tomar dos valores
perfectamente diferenciados, que designaremos por 0 y 1 y que están relacionados por
dos operaciones binarias denominadas suma (+) y producto (.) (La operación producto
se indica generalmente mediante la ausencia de símbolo entre dos variables lógicos).
4.1 Teoremas y Postulados.
TEOREMAS
La manera de demostrar los teoremas siguientes se puede basar en ideas intuitivas
producto de la familiaridad con algún álgebra booleana en particular, (en diagramas de
Venn, o bien, en circuitos con switches o en tablas de verdad) con la única condición de
que se respete al pie de la letra los 6 postulados fundamentales. En estas notas sólo se
usan razonamientos basados en los seis postulados. el hecho de que cada postulado tiene
dos incisos los cuales son duales uno del otro.
O Principio de Dualidad. Si una expresión booleana es verdadera, su expresión dual
también lo es.
O Expresiones duales. Dos expresiones se dicen duales una de la otra, si una se puede
obtener de la otracambiando las operaciones ( + ) por (.) y viceversa y cambiando los
O's por 1 's y viceversa.
Teorema 1. Multiplicación por cero
a) A.0 = 0
b) A+1 = 1
Explicación:
A.0 = A.0 + 0 0 es el neutro de la suma
= A.0 + A.A el producto de una variable por su complemento da 0
= A.(0 + A) distributividad
= A.(A) una variable más el neutro no se altera
= 0 una variable por su complemento da 0
Teorema 2. Absorción
a) A + AB = A
b) A(A + B) = A
F De aquí en adelante, de acuerdo al principio de dualidad demostrar sólo un inciso de
los siguientes teoremas y automáticamente el inciso dual quedará demostrado.
Explicación:
A + AB = A.1 + AB 1 es el neutro del producto
= A(1 + B) distributividad
= A(1) Teorema 1
= A es el neutro del producto
Este teorema se puede usar en diversos casos de simplificación, basta con usar
identificar en una suma, una expresión que se repite primero en forma aislada y luego
multiplicando a otra expresión.
Teorema 3. Cancelación
a) A + AB = A + B
b) A(A + B) = A B
Explicación:
A + AB = (A+A)(A+B) distributividad
= 1.(A+B) la suma de una variable con su complemento es 1
= A+B 1 es el neutro del Producto
Este teorema se puede usar en la simplificación de expresiones cuando encontramos una
expresión sumada Con su complemento multiplicado por otra expresión (o el dual).
Teorema 4. Cancelación
a) AB + AB = B
b) (A+B)(A+B)=B
Explicación:
AB + AB = (A+A )B distributividad
= 1.B la suma de una variable con su complemento es 1
= B 1 es el neutro del producto
Para usar este resultado hay que identificar dos términos que tienen un factor común y
el término que no es común en una de ellas es el complemento del de la otra.
Teorema 5. Idempotencia
a) A.A = A
b\ A+A= A
La demostración del inciso (b) de este teorema es inmediata del teorema de absorción,
ya que A + A =
A+ A.1.
Este teorema implica que cuando existen términos semejantes en una expresión, basta
con escribir uno de ellos, o bien, que un término puede "desdoblarse" tantas veces como
se quiera. Obsérvese que también esto implica que An = A para cualquier número n
entero positivo.
Teorema 6. Consenso
a) AB + AC + BC = AB + AC
b) (A+B)(A+C)(B+C) = (A+B)( A+C)
Explicación:
AB +AC + BC = AB +AC + BC(A +A) A+A es el neutro de la multiplicación
= AB +AC +ABC +ABC distributividad
= (AB +ABC) + AC +ABC) conmutatividad y asociatividad
= AB + AC absorción
La clave para usar este teorema es encontrar dos términos que contengan una expresión
en uno afirmada y en otro negada, anotar los términos con los que están multiplicando
uno y otro y buscar otro elemento que sea la multiplicación de estos últimos dos, éste
último elemento es el que se puede eliminar.
Teorema 7. Teorema de De Morgan
a) AB = A+B
b) A+B = AB
El teorema de De Morgan se puede generalizar al caso de más de dos variables
booleanas, por ejemplo, para 3 variables, tenemos que A+B+C = (A+B )C = ABC, en
forma similar, A.B.C = (A.B )+C = A+B+C , y así sucesivamente para más de tres
variables.
Teorema 8. Involución
a) A=A
Teorema 9. Complementos de los neutros
a) 0 = 1, b) 1 = 0
Postulados
1.- La suma lógica de una variable a y 1 es siempre 1. f (a + 1) = 1
2.- La suma lógica de un 0 y una variable a, siempre da el valor de la variable a. f (a +
0) = a
3.- La suma lógica de una variable consigo misma, siempre da en la salida el mismo
valor de la variable. f (a + a) = a
4.- La suma lógica de una variable y la inversa de ésta siempre da en la salida 1, ya que
al menos uno de ellos vale 1. f (a + not a) = 1
5.- La multiplicación lógica de una variable a y un 1 siempre da como resultado el valor
de la variable a. f (a · 1) = a
6.- La multiplicación lógica de un cero y una variable a, da en la salida un 0. f (a · 0) = 0
7.- La multiplicación lógica de una variable a consigo misma, da como resultado el
valor de la variable a. f (a · a) = a
8.- La multiplicación lógica de una variable a por la inversa de ésta, dará a la salida
siempre 0. f (a · not a) = 0
4.2 Optimización de expresiones booleanas.
Las expresiones booleanas se usan para determinar si un conjunto de una o más
condiciones es verdadero o falso, y el resultado de su evaluación es un valor de verdad.
Los operandos de una expresión booleana pueden ser cualquiera de los siguientes:
Expresiones relacionales: que comparan dos valores y determinan si existe o no
una cierta relación entre ellos (ver más adelante), tal como mfn<10;
Funciones booleanas: tal como p(v24), que regresa un valor de verdad (estos se
explican bajo "Funciones booleanas").
Las expresiones relacionales permiten determinar si una relación dada se verifica entre
dos valores. La forma general de una expresión relacional es:
Expresión-1 operador-de-relación expresión-2
Donde:
expresión-1 es una expresión numérica o de cadena
operador-de-relación es uno de los siguientes:
o = Igual
o <> No igual (diferente de)
o < Menor que
o <= Menor o igual que
o > Mayor que
o >= Mayor o igual que
o : Contiene (puede ser usado sólo en expresiones de cadena)
expresión-2 es una expresión del mismo tipo que expresión-1, o sea, expresión-
1 y expresión-2 deben ser ambas expresiones numéricas o ambas expresiones de
cadena.
Los operadores de relación = <> < <= > >= tienen su significado convencional cuando
se aplican a expresiones numéricas (dentro de los límites de precisión de los valores
numéricos definidos bajo "Expresiones numéricas"). Cuando se comparan expresiones
de cadena, se aplican las siguientes reglas:
Excepto por el operador ":" (contiene), las cadenas se comparan exactamente en
la forma en que ocurren, o sea, las letras mayúsculas y minúsculas se comparan
de acuerdo con el código ASCII que les corresponde (p.ej. A será considerada
menor que a);
Dos expresiones de cadena no son consideradas iguales, a menos que tengan la
misma longitud. Si dos expresiones generan cadenas de diferente longitud que
son idénticas, carácter por carácter, hasta el total de la longitud de la más corta,
entonces, la más corta será considerada menor que la más larga.
El operador: (contiene), busca una cadena de caracteres (definida por expresión-2) en
otra cadena (definida por expresión-1). Si el segundo operando existe en cualquier parte
del segundo operando, el resultado es Verdadero (TRUE). Este operador es insensible al
hecho de que los caracteres se hallen en mayúsculas o minúsculas: por lo que las letras
minúsculas se consideran iguales a su letra mayúscula correspondiente. Por ejemplo, el
resultado de:
v10: 'química'
Será Verdadero (True) si, y sólo si, el campo 10 contiene la cadena química. en caso
contrario, el resultado será Falso (False). Nótese que el segundo operando puede ser
cualquier cadena o carácter, y no necesita ser una palabra como tal. Por lo tanto, en este
ejemplo, el resultado será Verdadero no sólo si el campo 10 contiene la palabra química,
sino también si contuviera bioquímica, fotoquímicas, químicamente, etc.
Los operandos de una expresión booleana pueden combinarse con los operadores
siguientes:
NOT (NO) Este operador produce el valor Verdadero, si su operando es Falso; y
el valor Falso, si su operando es Verdadero. El operador NOT sólo puede usarse
como operador signo +, o sea, siempre se aplica a la expresión booleana que le
sigue;
AND (Y) Este operador produce el valor Verdadero si ambos operandos son
Verdadero. Si cualquiera de los dos operandos es Falso, entonces el resultado
será Falso;
OR (O) Este operador realiza una operación O-inclusivo. El resultado es
Verdadero si cualquiera de los dos operandos, o ambos son Verdadero. En caso
contrario, es Falso.
Al evaluar expresiones booleanas, y en ausencia de paréntesis, CDS/ISIS ejecutará las
operaciones NOT en primer lugar, después las operaciones AND, y finalmente las OR.
Las series de dos o más operadores del mismo nivel, se ejecutan de izquierda a derecha.
Se pueden usar paréntesis para alterar el orden de evaluación: las expresiones dentro de
paréntesis se evalúan antes, y las expresiones entre paréntesis internos a otros, son
evaluadas antes que las expresiones externas a los paréntesis.
4.3 Aplicación del algebra booleana (compuertas lógicas).
Una manera generalizada de representar las funciones lógicas es el uso de símbolos o
bloques lógicos denominados puertas o compuertas lógicas. Estas puertas en general
representan bloques funcionales que reciben un conjunto de entradas (variables
independientes) y producen una salida (variable dependiente). Una de las ventaja de
usar éstos símbolos es que por ser una representación entrada / salida permiten la
“interconexión” de puertas (la salida de una con la entrada de otra) para representar
funciones más complejas a partir de funciones sencillas. Otra ventaja es el hecho de que
los bloques sencillos (puertas con pocas entradas) se encuentran disponibles en circuitos
integrados comerciales, de aquí que un diagrama de puertas lógicas corresponde
directamente a un diagrama de alambrado de circuito lógico.
Salida A
La compuerta IF es la más sencilla de todas
Compuerta IF (SI)
La compuerta IF se representa
con un triángulo.
La puerta lógica IF, llamada SI en castellano, realiza la función booleana de la igualdad.
En los esquemas de un circuito electrónico se simboliza mediante un triangulo, cuya
base corresponde a la entrada, y el vértice opuesto la salida. Esto significa que si en su
entrada hay un nivel de tensión alto, también lo habrá en su salida; y si la entrada se
encuentra en nivel bajo, su salida también estará en ese estado. En electrónica,
generalmente se utilizan compuertas IF como amplificadores de corriente (buffers en
ingles), para permitir manejar dispositivos que tienen consumos de corriente elevados
desde otros que solo pueden entregar corrientes más débiles
Compuerta NOT (NO)
El circulo en la salida significa
negación.
Esta compuerta presenta en su salida un valor que es el opuesto del que esta presente en
su única entrada. En efecto, su función es la negación, y comparte con la compuerta IF
la característica de tener solo una entrada. Se utiliza cuando es necesario tener
disponible un valor lógico opuesto a uno dado. Se simboliza en un esquema eléctrico en
el mismo símbolo que la compuerta IF, con un pequeño circulo agregado en su salida,
que representa la negación.
Compuerta AND (Y)
Compuertas AND de 2 y 4
Entradas
Con dos o más entradas, esta compuerta realiza la función booleana de la
multiplicación. Su salida será un “1” cuando todas sus entradas también estén en nivel
alto. En cualquier otro caso, la salida será un “0”. El operador AND se lo asocia a la
multiplicación, de la misma forma que al operador SI se lo asociaba a la igualdad. En
efecto, el resultado de multiplicar entre si diferentes valores binarios solo dará como
resultado “1” cuando todos ellos también sean 1, como se puede ver en su tabla de
verdad. Matemáticamente se lo simboliza con el signo “x”.
Compuerta OR (O)
La función booleana que realiza la compuerta OR es la asociada a la suma, y
matemáticamente la expresamos como “+”. Esta compuerta presenta un estado alto en
su salida cuando al menos una de sus entradas también esta en estado alto. En cualquier
otro caso, la salida será 0. Tal como ocurre con las compuertas AND, el número de
entradas puede ser mayor a dos.
A la izquierda, compuertas AND de 2 y 4 entradas
Compuerta NAND (NO Y)
Agregando una etapa NOT a una
compuerta AND obtenemos una
NAND.
Cualquier compuerta lógica se puede negar, esto es, invertir el estado de su salida,
simplemente agregando una compuerta NOT que realice esa tarea. Debido a que es una
situación muy común, se fabrican compuertas que ya están negadas internamente. Este
es el caso de la compuerta NAND: es simplemente la negación de la compuerta AND
vista anteriormente. El pequeño círculo en su salida es el que simboliza la negación. El
numero de entradas debe ser como mínimo de dos, pero no es raro encontrar NAND de
3 o mas entradas.
Compuerta NOR (NO O)
De forma similar a lo explicado con la compuerta NAND, una compuerta NOR es la
negación de una compuerta OR, obtenida agregando una etapa NOT en su salida.
Agregando una etapa NOT a una compuerta AND obtenemos
una NAND.
Compuerta XOR (O Exclusivo)
XOR es la función ideal para
sumar dígitos binarios.
La compuerta OR vista anteriormente realiza la operación lógica correspondiente al O
inclusivo, es decir, una o ambas de las entradas deben estar en 1 para que la salida sea 1.
Un ejemplo de esta compuerta en lenguaje coloquial seria “Mañana iré de compras o al
cine”. Basta con que vaya de compras o al cine para que la afirmación sea verdadera. En
caso de que realice ambas cosas, la afirmación también es verdadera. Aquí es donde la
función XOR difiere de la OR: en una compuerta XOR la salida será 0 siempre que las
entradas sean distintas entre si. En el ejemplo anterior, si se tratase de la operación
XOR, la salida seria 1 solamente si fuimos de compras o si fuimos al cine, pero 0 si no
fuimos a ninguno de esos lugares, o si fuimos a ambos.
Compuerta NXOR (No O Exclusivo)
XOR + NOT = NXOR
No hay mucho para decir de esta compuerta. Como se puede deducir de los casos
anteriores, una compuerta NXOR no es más que una XOR con su salida negada, por lo
que su salida estará en estado alto solamente cuando sus entradas son iguales, y en
estado bajo para las demás combinaciones posibles.
4.3.1 Mini y maxi términos.
MINTÉRMINO (mi): Término producto en el que aparecen todas las variables, ya
sean complementadas o sin complementar.
FÓRMULA CANÓNICA DISYUNTIVA O DE MINTÉRMINOS: suma de
mintérminos (Suma de Productos).
Dada la lista completa de mintérminos y asignando 1’s y 0’s arbitrariamente a las
variables, siempre hay un, y sólo un, mintérmino que toma el valor 1. Un mintérmino es
un término producto que es 1 exactamente en una línea de la tabla de Verdad.
La fórmula compuesta por todos los mintérminos será idénticamente 1. Cada fórmula de
conmutación puede expresarse como suma de mintérminos. Y esa fórmula es única.
NOTACIÓN: Un mintérmino se designa por “mi” siendo i el número decimal
correspondiente de la tabla de verdad. Para el producto, el 0 se asocia a la variable
complementada y el 1 a la variable sin complementar.
EJEMPLO:
C B A F(C,B,A)
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1
F(C,B,A) = m0 + m2 + m3 +m7 = S m(0,2,3,7)
F(C,B,A) = C’·B’·A’ + C’·B·A’ + C’·B·A + C·B·A
O bien
F(C,B,A) = C·B·A + C·B·A + C·B·A + C·B·A
MAXTÉRMINO (Mi): término suma en el que aparecen todas las variables, ya sean
complementadas o sin complementar.
FÓRMULA CANÓNICA CONJUNTIVA O DE MAXTÉRMINOS: producto de
maxtérminos (Producto de sumas).
Dada la lista completa de maxtérminos y asignando 1’s y 0’s arbitrariamente a las
variables, siempre hay un y sólo un maxtérmino que toma el valor 0. Un maxtérmino es
un término suma que es 0 exactamente en una línea de la tabla de verdad. La fórmula
compuesta por todos los maxtérminos será idénticamente 0. Cada fórmula puede
expresarse como producto de maxtérminos. Y es única.
NOTACIÓN: Un maxtérmino se designa por “Mi” siendo i el número decimal
correspondiente de la tabla de verdad. En la suma, el 1 se asocia a la variable
complementada y el 0 a la variable sin complementar.
EJEMPLO:
C B A F(C,B,A)
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1
F(C,B,A) = M1 · M4 · M5 · M6 = P M(1,4,5,6)
F(C,B,A) = (C+B+A’) · (C’+B+A) · (C’+B+A’) · (C’+B’+A)
O bien: F(C,B,A) = (C+B+A) · (C+B+A) · (C+B+A) · (C+B+A)
CONVERSIÓN Y MANIPULACIÓN DE FÓRMULAS
El complemento de una fórmula de mintérminos está formado por la suma de los
mintérminos que no aparecen.
El complemento de una fórmula de maxtérminos está formado por el producto de los
maxtérminos que no aparecen.
mi’ = Mi
Mi’ = mi
La transformación de una fórmula de mintérminos (disyuntiva) en otra de maxtérminos
(conjuntiva) se basa en la doble complementación,
(F’)’ = F
Para FUNCIONES INCOMPLETAS en la tabla de verdad aparecerá una X o una letra
d (del inglés don’t care) refiriéndose a términos sin especificar.
C B A F(C,B,A)
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 X
1 0 0 0
1 0 1 X
1 1 0 0
1 1 1 1
F(C,B,A) = S m(0,2,7) + F(3,5)
F(C,B,A) = P M(1,4,6) · F(3,5)
Complemento de una función incompleta: otra función incompleta con los mismos
términos “no importa” y el complemento de la función completa. Las fórmulas de
mintérminos y de maxtérminos de las funciones incompletas.
4.3.2 Representación de expresiones booleanas con circuitos lógicos.
And. La operación And requiere que todas las señales sean simultáneamente verdaderas
para que la salida sea verdadera. Así, el circuito de la figura necesita que ambos
interruptores estén cerrados para que la luz encienda.
Los estados posibles del circuito se pueden modelar en la Tabla de Verdad que tiene
asociada. Sabemos que los interruptores sólo pueden tener dos estados, abiertos o
cerrados, si el interruptor abierto se representa mediante el cero (0 o falso) y el cerrado
mediante el valor uno (1 o verdadero) entonces en la tabla de verdad asociada se puede
ver la situación que se describía en el párrafo anterior, cuando se decía que la luz sólo
prende cuando ambos interruptores están cerrados, es decir, si A = 1 y B = 1 entonces L
= 1.
La compuerta lógica es una forma de representar la operación And pero en el ámbito de
los circuitos electrónicos, para ese caso A y B son las señales de entrada (con valores =
0 1) y L es la señal de salida.
Para efectos de este curso, la operación And la representaremos como la función And(
A, B ), donde A y B serían los parámetros de entrada (los mismos valores de A y B en
el circuito) y L = And( A, B ), correspondería a la forma de asignación de valor a L. En
este caso el parámetro de salida es la misma función And.
Or. La operación Or tiene similares características a la operación And, con la diferencia
que basta que una señal sea verdadera para que la señal resultante sea verdadera. En la
figura se puede ver tal situación.
Note que en el circuito los interruptores están en paralelo, por lo cual basta que uno de
ellos esté cerrado para que el circuito se cierre y encienda la luz.
La operación Or también tiene una representación funcional como Or( A, B ) donde A y
B serían los parámetros de entrada (los mismos valores de A y B en el circuito) y L =
Or( A, B ), correspondería a la forma de asignación de valor a L. En este caso, el
parámetro de salida es la misma función Or.
Not: La última de la tres operaciones fundamentales, la cual también se conoce como
negación, complemento o inversión, es mucho más simple que las anteriores. En la
figura se puede observar el circuito, que en este caso tiene la particularidad de que al
estar el interruptor abierto la luz enciende, cuando él está en posición de cerrado la luz
permanecería apagada.
La notación funcional para esta operación será Not( A ), donde A corresponde a la señal
de entrada y Not( A ) corresponde al valor complementario de A.
Con las operaciones básicas ya definidas es posible redefinir el Algebra de una manera
más formal, por ejemplo, dándole el nombre de Dominio Lógico y caracterizandolo de
la siguiente manera:
Dominio Lógico ( l ð Dominio Lógico ) = ( { 0, 1 }, { l: And( l, l ), l:Or( l, l ), l:Not( l )
} )
Note que cada una de las operaciones o funciones de este dominio se ha explicitado
claramente la cantidad y el tipo de parámetros con los cuales ellas operan (operandos) y
el tipo de valor que la operación devuelve, en este caso todos los parámetros son del
tipo lógico ( l ).
Así, cuando se habla del dominio del computador al resolver un problema, este dominio
tiene como base el dominio recién descrito. Los circuitos electrónicos que dan vida al
computador pueden ser representados todos mediante este Dominio Lógico.
Bibliografía
Matemática discreta Kolmant
http://www.terra.es/personal/jftjft/ algebra/Boole/algboole.htm
http://www.zabalnet.com/intro/cursos/03_algebra.htm
http://www.ncc.up.pt/~zp/aulas/9899/me/trabalhos/
alunos/circuitos_logicos/algboole.html
