Algebra BOleana

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

...