Algebra Booleana

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 sond u a l e s 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 otra cambiando 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)d i s t r i b u t i v i d a d

= A.(A) una variable más el neutro no se altera

=0una variable por su complemento da 0

Teorema 2. Absorción

a) A + AB = A

b) A(A + B) = A

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 + AB1es el neutro del producto

= A(1 + B)d i s t r i b u t i v i d a d

= A(1)T e o r e m a1

=Aes 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)d i s t r i b u t i v i d a d

= 1.(A+B) la suma de una variable con su complemento es1

= A+B1es 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 )Bd i s t r i b u t i v i d a d

= 1.B la suma de una variable con su complemento es1

=B1es 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 +A BCd i s t r i b u t i v i d a d

= (AB +ABC) +AC +ABC) conmutatividad y asociatividad

= AB +A Cabsorció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)A B =A+B

b)A + B =A B

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 =A B C, en forma similar, A . B . C = (A.B )+C =A+B+C , y así sucesivamente para más de tres variables.

a)A=A

Teorema 9. Complementos de losneutros

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 +n ot 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: y

Expresión es 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; y

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: y

Expresión-1 es una expresión numérica o de cadena y operador de relación es uno de los siguientes: o = Igual o <> No igual (diferente de) o

< Menor que o <= Menor o igual queo > Mayor que o >= Mayor o igual que o

: Contiene (puede ser usado sólo en expresiones

...