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

...