INSTITUTO UNIVERSITARIO TECNOLOGIA DE ADMINISTRACION INDUSTRIAL
EXTENSION VALENCIA
SECCION DE INFORMATICA
CATEDRA DE LOGICA

ALGEBRA BOOLEANA

Las algebras booleanas, estudiadas por primera vez en detalle por George Boole, constituyen un area de las matematicas que ha pasado a ocupar un lugar prominente con el advenimiento de la computadora digital. Son usadas ampliamente en el diseño de circuitos de distribución y computadoras, y sus aplicaciones van en aumento en muchas otras areas. En el nivel de lógica digital de una computadora, lo que comúnmente se llama hardware, y que esta formado por los componentes electrónicos de la maquina, se trabaja con diferencias de tensión, las cuales generan funciones que son calculadas por los circuitos que forman el nivel. Éstas funciones, en la etapa de diseña del hardware, son interpretadas como funciones de boole.

En el presente trabajo se intenta dar una definición de lo que es un algebra de boole; se tratan las funciones booleanas, haciendo una correlación con las fórmulas proposicionales. 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 engorrosas, por tener mas 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 menudocrucial. 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.

George Boole

(Lincoln, Reino Unido, 1815 - Ballintemple, actual Irlanda, 1864) Matematico britanico. Procedía de una familia venida a menos y tuvo que desestimar la idea de convertirse en monje al verse obligado a mantener a sus padres. A los doce años el interés de George se volcó en los idiomas y recibió instrucción en latín en una librería local. Llegó a ser tan habil en el uso del latín que provocó controversia. Una de sus traducciones del latín de una Oda del poeta Horacio era tan buena que el maestro de la escuela local no creía que alguien tan joven hubiese podido escribir con tanta profundidad y precisión. Boole no estudió un grado académico, se decantó por la enseñanza y a los dieciséis años fue nombrado profesor auxiliar de colegio. En esta época su interés por los idiomas continua y se plantea ingresar en la Iglesia para continuar aprendiendo latín y griego. A los dieciséis años enseñaba matematicas en un colegio privado y mas tarde fundó uno propio.



No obstante, George Boole continuó su formación en matematicas, estudiando por su cuenta. Comenzó a estudiar algebra y producto de sus investigaciones publica su primer tratadomatematico ‘Transaction of the Royal Society’ una aplicación de los métodos algebraicos par la solución de ecuaciones diferenciales. Por este trabajo recibió la distinción de la Real Sociedad que le otorgó una medalla y fue nominado para una catedra de matematicas en el Queens Collage de Cork en 1849. Allí enseñó durante el resto de su vida, ganandose fama de dedicado y eminente profesor.

El gran descubrimiento de Boole fue aplicar una serie de símbolos a operaciones lógicas y hacer que estos símbolos y operaciones –por elección cuidadosa– tuvieran la misma estructura lógica que el algebra convencional. En el algebra de Boole, los símbolos podían manipularse según reglas fijas que producirían resultados lógicos.

En 1854 publicó Investigación sobre las leyes del pensamiento, libro que trataba por completo de la lógica simbólica y su algebra. La influencia de esta lógica matematica sobre las matematicas modernas tendría una evolución lenta: si en un primer momento no parecía mas que un intrincado juego de palabras, mas adelante se vio que era de lo mas útil, y hasta completamente indispensable para conseguir la matematica lógica. Boole se casó a la edad de cuarenta años y tuvo cinco hijas, a las que no llegó a ver adolescentes.
En 1857 fue elegido como miembro académico de la Real Sociedad, recibiendo también honores por sus trabajos, de las universidades de Oxford y Dublín. En 1859 publica ‘Tratado de las ecuaciones diferenciales’ en el que traduce las ecuaciones diferenciales. En 1860 publica ‘Tratado sobre el calculo de diferencias finitas’ donde trata losmétodos generales de probabilidad y métodos para el calculo de dichas diferencias. Publicó alrededor de cincuenta escritos y fue uno de los primeros en investigas las propiedades basicas de los números, tales como la propiedad distributiva que fundamentó los temas de algebra.
Murió a los cuarenta y nueve años, debido a un resfriado que afectó a sus pulmones.

Algebra Booleana

El Algebra de Boole (también llamada Retículas booleanas) en informatica y matematica, es una estructura algebraica que rigorizan 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), matematico inglés que fue el primero en definirla como parte de un sistema lógico a mediados del siglo XIX. Específicamente, el algebra de Boole fue un intento de utilizar las técnicas algebraicas para tratar expresiones de la lógica proposicional. En la actualidad, el algebra de Boole se aplica de forma generalizada en el ambito 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 1938.

El algebra booleana es un sistema matematico deductivo centrado en los valores cero y uno (falso y verdadero). Un operador binario ' º ' definido en éste juego de valores acepta un par de entradas y produce un solo valor booleano, por ejemplo, el operador booleano AND acepta dos entradas booleanas y produce una sola salida booleana.

Para cualquier sistema algebraico existen unaserie de postulados iniciales, de aquí se pueden deducir reglas adicionales, teoremas y otras propiedades del sistema, el algebra booleana a menudo emplea los siguientes postulados

• Cerrado. El sistema booleano se considera cerrado con respecto a un operador binario si para cada par de valores booleanos se produce un solo resultado booleano.

• Conmutativo. Se dice que un operador binario ' º ' es conmutativo si A º B = B º A para todos los posibles valores de A y B.

• Asociativo. Se dice que un operador binario ' º ' es asociativo si (A º B) º C = A º (B º C) para todos los valores booleanos A, B, y C.

• Distributivo. Dos operadores binarios ' º ' y ' % ' son distributivos si A º (B % C) = (A º B) % (A º C) para todos los valores booleanos A, B, y C.

• Identidad. Un valor booleano I se dice que es un elemento de identidad con respecto a un operador binario ' º ' si A º I = A.

• Inverso. Un valor booleano I es un elemento inverso con respecto a un operador booleano ' º ' si A º I = B, y B es diferente de A, es decir, B es el valor opuesto de A.

Para nuestros propósitos basaremos el algebra booleana en el siguiente juego de operadores y valores

- Los dos posibles valores en el sistema booleano son cero y uno, a menudo llamaremos a éstos valores respectivamente como falso y verdadero.

- El símbolo ·  representa la operación lógica AND. Cuando se utilicen nombres de variables de una sola letra se eliminara el símbolo ·,  por lo tanto AB representa la operación lógica AND entre las variables A y B, a esto también le llamamos el productoentre A y B.

- El símbolo '+' representa la operación lógica OR, decimos que A+B es la operación lógica OR entre A y B, también llamada la suma de A y B.

- El complemento lógico, negación ó NOT es un operador unitario, en éste texto utilizaremos el símbolo ' ' ' para denotar la negación lógica, por ejemplo, A' denota la operación lógica NOT de A.

- Si varios operadores diferentes aparecen en una sola expresión booleana, el resultado de la expresión depende de la procedencia de los operadores, la cual es de mayor a menor, paréntesis, operador lógico NOT, operador lógico AND y operador lógico OR. Tanto el operador lógico AND como el OR son asociativos por la izquierda. Si dos operadores con la misma procedencia estan adyacentes, entonces se evalúan de izquierda a derecha. El operador lógico NOT es asociativo por la derecha.

Utilizaremos ademas los siguientes postulados

• P1 El algebra booleana es cerrada bajo las operaciones AND, OR y NOT

• P2 El elemento de identidad con respecto a ·  es uno y con respecto a +  es cero. No existe elemento de identidad para el operador NOT

• P3 Los operadores ·   y + son conmutativos.

• P4 ·   y + son distributivos uno con respecto al otro, esto es, A· (B+C) = (A·B (A·C) y A+ (B·C) = (A+B) ·(A+C).

• P5 Para cada valor A existe un valor A' tal que A·A' = 0 y A+A' = 1. Éste valor es el complemento lógico de A.

• P6 ·   y + son ambos asociativos, ésto es, (AB) C = A (BC) y (A+B C = A+ (B+C).

El Algebra de Boole es una estructura algebraica que puede ser considerada desde distintos puntosde vista matematicos:

El algebra de Boole es un retículo (A, , +), donde el conjunto A esta formado por dos elementos A=, como retículo presenta las siguientes propiedades:

1. Ley de Idempotencia:





2. Ley de Asociatividad





3. Ley de Conmutatividad





4. Ley de Cancelativo





Como anillo

El Algebra de Boole tiene Estructura algebraica de Anillo:

Grupo abeliano respecto a (+)

El conjunto A= es un Grupo abeliano respecto a (+):

1. (+) es una operación interna en A:



2. Es asociativa



3. Tiene elemento neutro



4. Tiene elemento simétrico



5. es conmutativa:



Grupo abeliano respecto a (·)

El conjunto A= es un Grupo abeliano respecto a ():

6. () es una operación interna en A:



7. Es asociativa



8. Tiene elemento neutro



9. Tiene elemento simétrico



10. es conmutativa:



Distributivo

El conjunto A= es un Grupo abeliano respecto a (+) y () y es distributiva:

11. La operación (+) es distributiva respecto a ()





12. La operación () es distributiva respecto a (+):





Como resultado podemos decir que el Algebra de Boole tiene Estructura algebraica de anillo conmutativo y con elemento neutro respecto a las dos operaciones (+) y ().Operaciones

Hemos definido el conjunto A = como el conjunto universal sobre el que se aplica el algebra de Boole, sobre estos elementos se definen varias operaciones, veamos las mas fundamentales:

Operación suma

|a |b |a + b |
|0 |0 |0 |
|0 |1 |1 |
|1 |0 |1 |
|1 |1 |1 |

La operación suma (+) asigna a cada par de valores a, b de A un valor c de A:



Su equivalencia en lógica de interruptores es un circuito de dos interruptores en paralelo.

[pic]

Si uno de los valores de a o b es 1, el resultado sera 1, es necesario que los dos sumandos sean 0, para que el resultado sea 0.

|

Operación producto

|a |b |a b|
|0 |0 |0 |
|0 |1 |0 |
|1 |0 |0 |
|1 |1 |1 |

La operación producto () asigna a cada par de valores a, b de A un valor c de A:



Esta operación en lógica de interruptores es un circuito en serie de dos interruptores



solo si los dos valores a y b son 1, el resultado sera 1, si uno solo de ellos es 0 el resultado sera 0.

|

Operación negación

|a ||
|0 |1 |
|1 |0 |

La operación negación presenta el opuesto del valor de a:



Un interruptor inverso equivale aesta operación:



|

Operaciones combinadas

|a |b
|0 |0 |1 |
|0 |1 |1 |
|1 |0 |0 |
|1 |1 |1 |

Partiendo de estas tres operaciones elementales se pueden realizar otras mas complejas, que podemos representar como ecuaciones booleanas, por ejemplo:



Que representado en lógica de interruptores es un circuito de dos interruptores en paralelo, siendo el primero de ellos inverso.

[pic]

La distinta secuencia de valores de a y b da los resultados vistos en la tabla de verdad.

pic]

Leyes fundamentales

El resultado de aplicar cualquiera de las tres operaciones definidas a variables del sistema booleano resulta en otra variable del sistema, y este resultado es único.

1. Ley de idempotencia





2. Ley de involución



3. Ley conmutativa





4. Ley asociativa





5. Ley distributiva











6. Ley de cancelación





7. Leyes de De Morgan





Principio de dualidad

El concepto de dualidad permite formalizar este hecho: a toda relación o ley lógica le correspondera su dual, formada mediante el intercambio de losoperadores unión (suma lógica) con los de intersección (producto lógico), y de los 1 con los 0.

Ademas hay que cambiar cada variable por su negada. Esto causa confusión al aplicarlo en los teoremas basicos, pero es totalmente necesario para la correcta aplicación del principio de dualidad. Véase que esto no modifica la tabla adjunta.

Adición |Producto |
|1 |
|2 |
|3 |
|4 |
|5 |
|6 |
|7 |
|8 |
|9 |

Otras formas de notación del algebra de Boole

En matematica se emplea la notación empleada hasta ahora (, + , ) siendo laforma mas usual y la mas cómoda de representar.

Por ejemplo las leyes de De Morgan se representan así:





Cuando el algebra de Boole se emplea en electrónica, suele emplearse la misma denominación que para las puerta lógica AND (Y), OR (O) y NOT (NO), ampliandose en ocasiones con X-OR (O exclusiva) y su negadas NAND (NO Y), NOR (NO O) y X-NOR (equivalencia). las variables pueden representarse con letras mayúsculas o minúsculas, y pueden tomar los valores

Empleando esta notación las leyes de De Morgan se representan:





En su aplicación a la lógica se emplea la notación y las variables pueden tomar los valores , falso o verdadero, equivalentes a

Con la notación lógica las leyes de De Morgan serian así:





En el formato de Teoría de conjuntos el Algebra de Boole toma el aspecto:

En esta notación las leyes de De Morgan serian así:





Desde el punto de vista practico existe una forma simplificada de representar expresiones booleanas. Se emplean apóstrofes (') para indicar la negación, la operación suma (+) se representa de la forma normal en algebra, y para el producto no se emplea ningún signo, las variables se representan, normalmente con una letra mayúscula, la sucesión de dos variables indica el producto entre ellas, no una variable nombrada con dos letras.

La representación de las leyes de De Morgan con este sistema quedaría así, con letra minúsculas para las variables





y así,empleando letras mayúsculas para representar las variables:





Todas estas formas de representación son correctas, se utilizan de hecho, y pueden verse al consultar bibliografía. La utilización de una u otra notación no modifica el algebra de Boole, solo su aspecto, y depende de la rama de las matematicas o la tecnología en la que se este utilizando para emplear una u otra notación.

Algebra de Boole aplicada a la informatica

Se dice que una variable tiene valor booleano cuando, en general, la variable contiene un 0 lógico o un 1 lógico. Esto, en la mayoría de los lenguajes de programación, se traduce en false (falso) o true (verdadero), respectivamente.

Una variable puede no ser de tipo booleano, y guardar valores que, en principio, no son booleanos; ya que, globalmente, los compiladores trabajan con esos otros valores, numéricos normalmente aunque también algunos permiten cambios desde, incluso, caracteres, finalizando en valor booleano. ..

El 0 lógico



El valor booleano de negación suele ser representado como false, aunque también permite y equivale al valor natural, entero y decimal (exacto) 0, así como la cadena 'false', e incluso la cadena '0'.

El 1 lógico



En cambio, el resto de valores apuntan al valor booleano de afirmación, representado normalmente como true, ya que, por definición, el valor 1 se tiene cuando no es 0. Cualquier número distinto de cero se comporta como un 1 lógico, y lo mismo sucede con casi cualquier cadena (menos la 'false', en caso de ser ésta la correspondiente al 0 lógico).