Algebra de Boole.

Introducción.

A Aristóteles le corresponde el mérito de ser fundador de la lógica cuando propuso los primeros catorce silogismos, los teólogos y filósofos medievales añadieron otros cincos tipos de silogismos a los catorce de Aristóteles. Estas diecinueve leyes constituyeron durante cientos de años los fundamentos de la enseñanza de la lógica.

En 1847, el maestro de escuela y matemático George Boole (1815-1864) publicó un panfleto titulado The Mathematical Analysis of Logic (Análisis matemático de la lógica), donde estableció un sistema de axiomas a partir de los cuales, se podían deducir nuevas proposiciones. Para representar las proposiciones, Boole utilizó símbolos algebraicos como x ,y deduciendo nuevas proposiciones aplicando las operaciones algebraicas.

La idea de sustituir proposiciones por símbolos se le había ocurrido anteriormente a otros, pero fue Boole el primero que produjo un sistema consistente y fácilmente manejable, por lo que significo ser nombrado profesor del Queens College (actualmente University College) de Irlanda, aunque no tenía grado académico de profesor.

George Boole presentó el primer tratamiento sistemático de la lógica y para ello, desarrolló un sistema algebraico, conocido ahora como Álgebra de Boole. Además de sus aplicaciones al campo de la lógica, el álgebra de Boole ha tenido dos aplicaciones importantes: el tratamiento de conjuntos mediante las operaciones de unión e intersección que ha servido de base a la teoría de la probabilidad y el diseño de circuitos digitales combinacionales.

En 1913, los logicistas Alfred North Whitehead y Bertrand Russell, usando símbolos creado por el matemático y logicista Giuseppe Peano, desarrollaron el sistema axiomático de las proposiciones.

Definición de álgebra de Boole y Teoremas

Definición

Un álgebra booleana es un sistema algebraico constituido por un conjunto B junto con dos operaciones + (como la adición) y ´ (como la multiplicación) definida sobre el conjunto, tales que para cualesquiera elementos a, b, y c de B se verifica las siguientes propiedades :

A1. a+bÎB

M1. a´bÎB

A2. a+(b+c)=(a+b)+c

M2. a´ (b´c)=(a´b) ´c

M3. Existe un elemento único 0ÎB tal que para todo aÎB, a+0=0+a = a.

M3. Existe un elemento único 1ÎB tal que para todo aÎB, a´1=1´a = a.

A5. a+b=b+a

M5. a´b=b´a

D1. a´ (b+c)=a´b+a´c

D2. (a+b) ´c=a´c+b´c

D3. a+(b´c)= (a+b)´(a +c)

D4. (a´b) + c=(a+ c)´(b+ c)

C1. Para todo aÎB existe un elemento único a'ÎB tal que a+ a'=1 y a ´a'=0.

Teorema: Para todo elemento a, a+ a = a y a´ a = a.

Prueba:

a+ a=(a+ a)(1) M3

=(a+ a)(a+ a') C1

= a +aa' D3

=a+0 C1

=a. A3

La prueba de aa se obtiene por dualidad:

aa=aa+0 A3

=aa+aa' C1

= a(a+ a') D1

=a1 C1

=a M3

Teorema: Para todo elemento a, a+1=a y a´0=0.

Prueba:

a+ 1=1(a+ 1) M3

= (a+ a')(a+ 1) C1

= a +a' 1 D3

=a+ a' M3

=1. C1

Ejemplo: Sea B=í1,0ý y sean las operaciones + y ´ definidas como sigue:

+	1	0
1	1	1
0	1	0

´	1	0
1	1	0
0	0	0

Entonces B, o más precisamente, la terna (B,+, ´) es un álgebra de Boole.

El álgebra de Boole es un sistema axiomático abstracto que se puede interpretar por diferentes modelos. La siguiente tabla incluye la simbología de los tres modelos del álgebra de Boole.

Algebra de Proposiciones	Símbolos	Algebra de Circuitos	Símbolos	Algebra de Conjuntos	Símbolos
Proposición	P,Q,R,......	Circuitos	X,Y,Z,.....	Elementos	a,b,c,....
Conjunción	&	En serie	´	Intersección	Ç
Disyunción	Ú	En paralelo	+	Unión	È
Negación	–	Complemento	'	Complemento	'
Contradicción	C	Abierto	0	Vacío	Æ
Tautología	T	Cerrado	1	Universal	U
Implicación	Þ	Implicación	Þ	Implicación	Þ
Equivalencia	Û	Igualdad	=	Igualdad	=

Circuitos.

Una de las primeras aplicaciones no matemáticas de la lógica simbólica fue vista en la tesis de maestría de Claude Shannon en 1937. Shannon mostró cómo la lógica podría usarse como ayuda al diseñar circuitos eléctricos. Su trabajo fue inmediatamente adoptado por los diseñadores de computadoras. Estas computadoras pudieron simplificarse en la etapa de desarrollo y construirse por menos dinero, usando las ideas de Shannon.

Un interruptor es un dispositivo que sirve para cerrar o abrir un circuito eléctrico. Un circuito eléctrico puede contener varios dispositivos eléctricos como interruptores, resistencias, etc.

Un interruptor tiene dos estados, llamados estado abierto y estado cerrado.

Estado cerrado: cuando el interruptor está cerrado fluye la corriente.

Estado abierto: cuando el interruptor está abierto la corriente no paso.

Estado cerrado del interruptor = 1.

Estado abierto del interruptor = 0.

Estos circuitos pueden reducirse a dos fundamentales: circuitos en serie y circuitos en paralelos.

Circuitos en Serie.

En su forma más elemental un circuito en serie esta formado por dos interruptores denotado por X e Y, y unido por una sola línea de flujo de corriente.

X	Y	Corriente
1	1	Pasa
1	0	No pasa
0	1	No pasa
0	0	No pasa

Circuitos en Paralelo.

Otra forma de conectar dos interruptores X e Y, es por medio del circuito e paralelo, en donde la corriente puede pasar alternativamente por el interruptor X o por el interruptor Y o por los dos interruptores a la vez.

X	Y	Corriente
1	1	Pasa
1	0	Pasa
0	1	Pasa
0	0	No pasa

Circuitos en Serie y en Paralelos.

Los circuitos en serie y en paralelo se pueden combinar entre sí para obtener nuevos circuitos.

Complementación de Circuitos.

Así como las operaciones de la conjunción y de la disyunción tienen su equivalente en los circuitos, así también lo tiene la operación de la negación, por la operación de la Complementación.

Los estados entre los interruptores X y X ' se expresan por medio de la tabla análoga a la negación.

Ejercicios

Construya los siguientes circuitos:

a) X+(YxZ)

b) X+(Y+Z)

c) (XxY)+(ZxW)

d) (X+Y)x(Z+W)

e) (XxYxZ)+(X’xY’xZ’)

f) (X+Y+Z)x(X’+Y’+Z’)

Traduzca a formula los siguientes circuitos:

Simplificar los circuitos:

Algebra de Boole o Función Interruptor.

Axioma 1: a+ b= b +a ; a´b= b ´a.

Axioma 2: a+(b+c)=(a+b)+c ; a´(b´c)=(a´b) ´c

Axioma 3: a´(b+c)=(a´b)+(a´c) ; a+(b´c)=(a+b)´(a+c)

Axioma 4: a´1=a ; a+0=a

Axioma 5: a+a'=1; a´a'=0

Otras funciones: a+1=1; a´0=0; a+a=a; a+(a´b)=a+b; a´(a+b)=a;

Funciones Booleanas.

Una función booleana es una expresión derivada al aplicar un número finito de aplicaciones de las operaciones +, ´ y a los elementos de un álgebra de Boole.

Ejemplos.

a) F(x,y)= xy'+xy

b) F(x,y)= x+xy

La lógica y sus aplicaciones

La interpretación del álgebra de Boole a los circuitos eléctricos fue sugerida por primera vez en 1910 por Paul S. Ehrenfest en Rusia y en 1936 en Japón. Pero el primer gran documento que introdujo a los diseñadores de computadoras se titulo "A symbolic Analysis of Relay and Switching Circuits" de Claude E. Shannon en 1938.

Desde la publicación del documento de Shannon, el álgebra de Boole se constituyó en un instrumento esencial en el diseño de las computadoras, al permitir simplificar los circuitos y reducir eficientemente el Hardware de las computadoras.

La primera aplicación de la lógica simbólica a los negocios se ubica en 1936 y fue realizada por el matemático Edmund C. Berkeley. Trabajando para una compañía de seguro, trató de simplificar las reglas bajo las cuales se distribuían las primas entre los asegurados. Redujo a una simple regla, las múltiples disposiciones utilizadas por las aseguradoras en la formulación de las pólizas de los asegurados, ahorrando con ello cantidades considerables de dinero.

Otra aplicación esta en el estudio de las relaciones entre más de 10.000 millones de células nerviosas del cerebro humano, la Universidad de Illinois aplicó el documento Principia Mathematical de Russell y Whitehead, en la que se sugirió que el estudio de la cibernética, en el que se analiza las similitudes entre el cerebro humano y las computadoras fuera realizadas aplicando las leyes de la lógica simbólica.

Uno de los grandes problemas en la construcción de las primeros computadoras fue reducir el número de tubos. El Eniac, primera computadora construida, contenía 20.000 tubos y más de 500.000 conexiones. En la construcción de Mark III, todo electrónico, los ingenieros decidieron que 9 era el número mínimo de tubos. No obstante, los matemáticos T. Kalin y W. Burkhart de la Universidad de Harvard demostraron, aplicando lógica simbólica que su número era 6, lo que implicó una economía de un tercio, en términos de costo, tiempo de procesamiento y el correspondiente aumento en su eficiencia.

Aplicaciones a Circuitos de Distribución.

En un avión de prueba hay tres pilotos con interruptores cada uno. Una luz roja se enciende cuando uno de ellos indica peligro y se enciende la luz verde cuando los tres señalan que se puede seguir la prueba. Calcular la tabla booleana y trazar el circuito correspondiente.

X	Y	Z	R	V
1	1	1	1	0
1	1	0	1	0
1	0	1	1	0
1	0	0	1	0
0	1	1	1	0
0	1	0	1	0
0	0	1	1	0
0	0	0	0	1

Función booleana.

Luz Roja: R = xyz+xyz’+xy’z+x’yz+xy’z’+x’yz’+x’y’z = (x’+y’+z’)’=x+y+z.

Función booleana.

Luz Verde: V =x’y’z’