Atlas & Maps

Definición de Álgebra de Boole

0

 [Matemáticas]

Parte de las matemáticas que estudia la lógica matemática desde un punto de vista algebraico, mediante la consideración del conjunto de fórmulas proposicionales como elementos un cierto tipo de estructuras algebraicas, las álgebras de Boole. A esta rama del álgebra también se le llama álgebra lógica.

Este punto de vista lo planteó por primera vez el matemático británico George Boole en su obra An investigation into the Laws of Thought, on Which are founded the Mathematical Theories of Logic and Probabilities (‘Investigación sobre las leyes del pensamiento, sobre las cuales están fundadas las teorías matemáticas de la lógica y la probabilidad’) publicada en 1854. En ella, Boole utilizaba por primera vez las estructuras algebraicas que a posteriori recibirían su nombre. La definición axiomática de las álgebras de Boole fue concretada definitivamente por el matemático estadounidense Edward Huntington en 1904.

Con la llegada de los procesadores informáticos el álgebra de Boole ha adquirido una gran importancia. Las proposiciones lógicas se pueden identificar con los interruptores de un circuito electrónico, que estarán encendidos cuando las proposiciones sean ciertas, y apagados cuando sean falsas.

Definición axiomática

Un álgebra de Boole es una estructura algebraica definida sobre un conjunto B que consta de dos operaciones binarias internas +, • y una operación unaria ‘, que, dados a, b, c elementos de B, verifican las siguientes propiedades:

1. Propiedades conmutativas:

a + b = b + a
a • b = b • a

2. Propiedades asociativas:

(a + b) + c = a + (b + c)
(a • b) • c = a • (b • c)

3. Propiedades distributivas:

(a + b) • c = (a • c) + (b • c)
(a • b) + c = (a + c) • (b + c)

4. Existencia de elemento neutro: Existen dos elementos 0, 1 en el conjunto B que son lo elementos neutros para cada una de las operaciones.

a + 0 = a
a • 1 = a

5. Existencia del elemento complementario:

a + a’ = 0
a • a’ = 1

Las álgebras de Boole en las que los elementos neutros 1, 0 son distintos se llaman propias; en caso contrario se habla de álgebras de Boole impropias.

Existen varios ejemplos de álgebras de Boole, pero el más importante es el que forman las proposiciones lógicas de dos valores (verdadero-falso) sobre las que se aplican las operaciones de disyunción () y de conjunción () lógicas y en la que se consideran como los complementarios de los elementos los obtenidos con el operador negación lógica (). Esta estructura es en la que se basó Boole para realizar sus estudios de lógica, y son las que en la actualidad se entienden como el álgebra de Boole. Véase Lógica matemática.

Otro ejemplo de álgebra de Boole es la formada por las partes de un conjunto X dado, P(X), con las operaciones unión () e intersección (), para la que el complementario se obtiene con la propia complementación de conjuntos. Esta álgebra de Boole y la del ejemplo anterior se relacionan muy fácilmente, ya que se puede identificar la pertenencia a un conjunto con el cumplimiento de una proposición (el conjunto de los coches descapotables es el conjunto de elementos que cumplen la afirmación “el coche es descapotable”). De esta forma se comprueba que la unión de conjuntos se corresponde con la disyunción lógica, y la intersección se identifica con la conjunción. Lo mismo ocurre con el conjunto complementario y el operador negación. De hecho, Boole se dio cuenta de esta equivalencia, e intentó reducir el lenguaje de la lógica a un lenguaje equivalente al de los conjuntos. Véase Teoría de conjuntos.

Propiedades de las álgebra de Boole

Dados dos elementos x, y del álgebra de Boole B, las siguientes propiedades se deducen de las propiedades axiomáticas que definen este tipo de álgebras:

a) Los elementos del conjunto son idempotentes con respecto a las dos operaciones:

x + x = x
x • x = x

b) Maximalidad del elemento neutro para • con respecto a la operación + :

x + 1 = 1

c) Minimalidad del elemento neutro para + con respecto a la operación • :

x • 0 = 0

d) Dado un elemento cualquiera de B, el complementario de su complementario es el elemento dado (involución):

(x’)’ = x

e) Propiedades de inmersión o absorción:

x + (x • y) = x
x • (x + y) = x

f) Leyes de De Morgan para las dos operaciones:

(x + y)’ = x’• y’
(x • y)’ = x’+ y’

Principio de dualidad

Dada una expresión X en un álgebra de Boole, se define su expresión dual XD como la resultante de intercambiar las operaciones binarias y los elementos neutros en la expresión inicial.

El principio de dualidad dice que si una expresión X es deducible a partir de los axiomas que definen un álgebra de Boole B, entonces su expresión dual XD también lo es. De esta forma se puede deducir una expresión partiendo de su expresión dual.

Funciones booleanas

Son aplicaciones del producto cartesiano B x B x B x …. x B en B, con B={0, 1} un álgebra de Boole. En el lenguaje informático a estas aplicaciones también se les llama funciones de conmutación.

Desde el punto de vista lógico, las funciones booleanas son las posibles evaluaciones como verdaderas o falsas de las expresiones proposicionales que indican dichas funciones, por lo que, además de representarse con las expresiones algebraicas habituales, las funciones boolenanas también se suelen expresar mediante tablas de verdad. Por ejemplo, la función F(X, Y, Z) = (X•Y+X•Z)•Y se puede representar mediante la siguiente tabla de verdad:

X | Y | Z | (X•Y+X•Z)•Y
—+—+—+————–
1 | 1 | 1 | 1
1 | 0 | 1 | 0
1 | 1 | 0 | 1
1 | 0 | 0 | 0
0 | 1 | 1 | 0
0 | 0 | 1 | 0
0 | 0 | 0 | 0

Las formas algebraicas más habituales en las que se expresan estas funciones son las que se conocen como formas canónicas, que están formadas por sumas de mintérminos o por productos de maxtérminos. Un mintérmino es un término formado por un producto en el que aparecen exactamente una de cada una de las variables, con o sin complementar. Un maxtérmino es un término formado por una suma en la que aparecen exactamente una de cada una de las variables, con o sin complementar. Aunque las funciones booleanas se pueden expresar de muchas formas diferentes, lo interesante de las expresiones canónicas es que son únicas.

Existen dos resultados que se suelen utilizar para expresar una función booleana en forma canónica, los conocidos como teoremas de expansión:

Teorema 1:
Para obtener la forma canónica de mintérminos se multiplica por un elemento de la forma (X+X’) donde falte una variable para que el término se complete.

Teorema 2:
Para obtener la forma canónica de maxtérminos se suma un elemento de la forma (X•X’) donde falte una variable para que el término se complete.

El ejemplo anterior se expresa en las dos formas canónicas de la manera siguiente:

Expresión canónica de mintérminos:

F(X,Y,Z) = (X•Y + X•Z)•Y = X•Y•Y + X•Z•Y =
= X•Y•(Z + Z’)+ X•Y•Z = X•Y•Z + X•Y•Z’ + X•Y•Z =
= X•Y•Z + X•Y•Z’

Expresión canónica de maxtérminos:

F(X,Y,Z) = (X•Y+X•Z)•Y = (X+Y•Y’+Z•Z’)•(Y+Z+X•X’)•(Y+Z•Z’+X•X’) =
= (X+Y+Z)•(X+Y’+Z)•(X+Y+Z’)•(X+Y’+Z’)•(Y+Z+X)•(Y+Z+X’)•
•(Y+X+Z)•(Y+X’+Z)•(Y+X+Z’)•(Y+X’+Z’) =
= (X+Y+Z)•(X+Y’+Z)•(X+Y+Z’)•(X+Y’+Z’)•(X’+Y+Z)

Las funciones booleanas pueden llegar a ser muy complejas y, para su manejo, es necesario simplificarlas, lo cual puede resultar bastante engorroso. Para llevar a cabo esta labor de una forma más sencilla se utilizan lo que se conoce como diagramas de Karnaugh.

Como se ha comentado antes, se pueden identificar los estados verdadero-falso de las proposiciones lógicas con los estados encendido-apagado de los interruptores electrónicos. De esta forma, la conjunción () equivale a dos interruptores puestos en serie (para que circule la corriente los dos interruptores tendrán que estar encendidos), y la disyunción () equivale a dos interruptores puestos en paralelo (no pasa corriente sólo si los dos interruptores están apagados). En esencia, esta es la forma como las funciones booleanas se utilizan para representar circuitos lógicos.

Temas relacionados

Lógica matemática.
Circuitos Lógicos.

Enlaces en Internet

http://medusa.unimet.edu.ve/sistemas/bpis03/algebradeboole.htm; El álgebra de Boole desde un punto de vista informático. En español.

http://www.dte.us.es/tec_inf/itis/fund_comp/fctema2.pdf; Las funciones booleanas, maxtérminos y mintérminos. En español.

Bibliografía

ALDANA, F., ESPARZA R. y MARTINEZ P.M., Electrónica Industrial: Técnicas Digitales, Boixareu.

Álgebra de Boole

Fuente: Britannica

So, what do you think ?