Ene 172014

 

George Boole

Matemático británico especializado en temas de lógica, nacido el 2 de noviembre de 1815 y murió el 8 de diciembre de 1864.

Como inventor del álgebra de Boole, marcaría los fundamentos de la aritmética computacional moderna, Boole es considerado como uno de los fundadores del campo de las Ciencias de la Computación. En 1854 publicó “An Investigation of the Laws of Thought” en el que desarrollaba un sistema de reglas que le permitían expresar, manipular y simplificar problemas lógicos y filosóficos cuyos argumentos admiten dos estados (verdadero o falso) por procedimientos matemáticos.

Gracias a el se desarrollo toda la matemática que hace posible hacer funcionar los computadores de hoy en día.

Definición de álgebra de Boole

Sea K un conjunto en el cual se definen dos operaciones binarias, + y *, y una operación unitaria denotada   ; sean 0 y 1 dos elementos diferentes de K. Tendremos la siguiente séxtupla:

(K, +, *, , 0, 1)

Se denomina álgebra de Boole si se cumplen los siguientes axiomas (proposiciones que se consideran evidentes y se aceptan sin requerir demostración previa) para cualesquiera de los elementos a, b, c del conjunto K:

Conmutatividad:

a + b = b + a
a * b = b * a

Distributividad:

a + (b * c) = (a + b) * (a + c)
a * (b + c) = (a * b) + (a * c)

Identidad:

a + 0 = a
a * 1 = a

Complemento:

a + a = 1
a * a = 0

Terminología y convenciones:

  • Las operaciones + y * se denominan suma y producto , respectivamente.
  • La operación a se denomina complemento de a .
  • El elemento 0 se denomina elemento cero (neutro respecto de la suma).
  • El elemento 1 se denomina elemento unidad (neutro respecto del producto).
  • Por convención, omitimos el símbolo *, usándose en su lugar la yuxtaposición, como en el siguiente ejemplo:  a + bc = ( a + b ) ( a + c ).
  • Por convención, establecemos que + es más fuerte que *,  y * es más fuerte que   

por ejemplo:

a + b * c significa a + ( b * c ) y no (a + b) * c

a * b significa a * ( b ) y no ( a * b )

Dualidad

El dual de cualquier enunciado es el enunciado obtenido de intercambiar las operaciones + y *, e intercambiar los elementos neutros 0 y 1 en el enunciado original. Por ejemplo:

el dual de (1 + a ) * ( b + 0) = b

es

(0 * a ) + ( b * 1) = b

Con esta definición de dualidad puede observarse que, en la definición de álgebra de Boole, los axiomas anteriores son duales, dicho de otro modo el dual de cualquier axioma de K también es un axioma. En consecuencia, se cumple el siguiente teorema:

Principio de dualidad

En un álgebra de Boole, el dual de cualquier teorema es también un teorema. Esto significa que, si cualquier teorema es una consecuencia de los axiomas de un álgebra de Boole, entonces el dual también es una consecuencia de estos axiomas ya que se puede probar usando el dual en cada paso de la demostración original.

Teoremas básicos

Utilizando los axiomas de la definición de un álgebra de Boole, pueden demostrarse los siguientes teoremas:

Sean a , b , c elementos cualesquiera de un álgebra de Boole , se cumple:

Idempotencia:

a + a = a
a * a = a

Acotamiento:

a + 1 = 1
a * 0 = 0

Absorción:

a + ( a * b ) = a
a * ( a + b ) = a

Asociatividad:

( a + b ) + c = a + ( b + c )
( a * b ) * c = a * ( b * c )

Sea a un elemento cualquiera de un álgebra de Boole , se cumple:

Unicidad del complemento:

Si a + x = 1 y a * x = 0, entonces x = a

Involución:
_
a = a

0 = 1

1 = 0

Teorema : Leyes de Morgan

a + b = a * b
a * b = a + b

Es importante decir que el álgebra de Boole es la estructura algebraica de la lógica de enunciados . Si se reemplazan las variables a , b , c , … por variables proposicionales, la suma y el producto por la disyunción y la conjunción respectivamente, el complemento por la negación, la igualdad por el condicional, y 1 y 0 por V y F respectivamente, todos los axiomas y teoremas del álgebra de Boole se transforman en axiomas o teoremas de la lógica de enunciados. Por ejemplo:

a * ( b + c ) = ( a * b ) + ( a * c ) p ∧ (q ∨ r) ↔ (p ∧ q) ∨ (p ∧ r)
a + a = a p ∨ p ↔ p
a + ( a * b ) = a p ∨ (p ∧ q) ↔ p
a * b = a + b ¬(p ∧ q) ↔ ¬p ∨ ¬q

Forma de suma de productos

Considérese un conjunto de variables a, b, c, d, e, …

Una expresión booleana E en estas variables es o una variable o una expresión construida con estas variables y usando las operaciones booleanas +, * o . Por ejemplo, las siguientes son expresiones booleanas:

( a + bc ) + ( abc + ab )
(( abc + b ) + ac )

Un literal es una variable o una variable complementada. Por ejemplo, a, a , b, b son literales.

Un producto fundamental es un literal o un producto de dos o más literales en el cual no hay dos literales con la misma variable. Por ejemplo, ac , abc , a, b , bc , abc son productos fundamentales. En cambio, abac y abcb no son productos fundamentales: el primero contiene a y a , mientras que el segundo contiene b dos veces.

Una expresión booleana E está en forma de suma de productos si E es un producto fundamental o una suma de dos o más productos fundamentales. Por ejemplo, la siguiente expresión está en suma de productos:

ac + abc + abc

Pero la siguiente expresión no está en forma de suma de productos:

ac + aba + abc

ya que el segundo término no es un producto fundamental y es un termino innecesario.



Contenido relacionado




 Deja un Comentario

(Requerido)

(Requerido)