TEOREMAS DE BOOLE

TEOREMAS DE BOOLE

Definición

Un álgebra de Boole es un conjunto en el que:

1- Se han definido dos funciones binarias (que necesitan dos parámetros) que llamaremos aditiva (que representaremos por x + y) y multiplicativa (que representaremos por xy) y una función monaria (de un solo parámetro) que representaremos por x'.

2- Se han definido dos elementos (que designaremos por 0 y 1)

y 3- Tiene las siguientes propiedades:

a) Conmutativa respecto a la primera función: x + y = y + x

b) Conmutativa respecto a la segunda función: xy = yx

c) Asociativa respecto a la primera función: (x + y) + z = x + (y +z)

d) Asociativa respecto a la segunda función: (xy)z = x(yz)

e) Distributiva respecto a la primera función: (x +y)z = xz + yz

f) Distributiva respecto a la segunda función: (xy) + z = (x + z)( y + z)

g) Identidad respecto a la primera función: x + 0 = x

h) Identidad respecto a la segunda función: x1 = x

i) Complemento respecto a la primera función: x + x' = 1

j) Complemento respecto a la segunda función: xx' = 0

Propiedades del álgebra de Boole

Idempotente respecto a la primera función: x + x = x

Idempotente respecto a la segunda función: xx = x

Maximalidad del 1: x + 1 = 1

Minimalidad del 0: x0 = 0

Involución: x'' = x

Inmersión respecto a la primera función: x + (xy) = x

Inmersión respecto a la segunda función: x(x + y) = x

Ley de Morgan respecto a la primera función: (x + y)' = x'y'

Ley de Morgan respecto a la segunda función: (xy)' = x' + y'

Función booleana

Una función booleana es una aplicación de A x A x A x ....A en A, siendo A un conjunto cuyos elementos son 0 y 1 y tiene estructura de álgebra de Boole.

Supongamos que cuatro amigos deciden ir al cine si lo quiere la mayoría. Cada uno puede votar si o no. Representemos el voto de cada uno por xi. La función devolverá sí (1) cuando el numero de votos afirmativos sea 3 y en caso contrario devolverá 0.

Si x1 vota 1, x2 vota 0, x3 vota 0 y x4 vota 1 la función booleana devolverá 0.

Producto mínimo (es el número posible de casos) es un producto en el que aparecen todas las variables o sus negaciones.

El número posible de casos es 2n.

Siguiendo con el ejemplo anterior. Asignamos las letras A, B, C y D a los amigos. Los posibles casos son:

Votos Resultado

ABCD

1111 1

1110 1

1101 1

1100 0

1011 1

1010 0

1001 0

1000 0

0111 1

0110 0

...