Teoremas Y Postulados De álgebra De Boole

TEOREMAS Y POSTULADOS DEL ALGEBRA DE BOOLE. POSTULADOS DE MORGAN

1. Propiedad de cierre.

Para un conjunto s se dice que es cerrado para un operador binario si para cada elemento de S el operador binario especifica una regla para obtener un elemento único de S.

Para el conjunto N = {1,2,3,4,…} es cerrado con respecto al operador binario (+) por las reglas de la adición aritmética, ya que para que cualquier elemento a,b pertenecientes a N por la operación a + b = c el conjunto de los números naturales no esta cerrado con respecto al operador binario (-) por la regla de la resta aritmética, debido a que 2-3 = -1 y 2,3 pertenecen a N pero -1 no pertenece a N.

2. Ley asociativa.

El operador binario (*) es un conjunto S es asociativo siempre que

x*y*z = x*(y*z) para toda x, y pertenecientes a S.

3. Ley conmutativa.

Un operador binario (*) para un conjunto S es conmutativo siempre que:

x*y = y*x para toda x,y pertenecientes a S.

4. Elemento identidad.

El conjunto S tendrá un elemento identidad multiplicativo “identidad (*)” en S si existe un e perteneciente a S con la propiedad e*x = x*e =e para cada x pertenecientes a S.

5. Inversa.

El conjunto S tiene un elemento identidad (e) con respecto al operador (*) siempre que para cada x perteneciente a S exista un elemento y perteneciente a S tal que x*y=e.

6. Ley distributiva.

Si el operador (*) y el operador (.), son operadores binarios de S, (*) se dice que es distributivo sobre (.).

Siempre que:

x*(y . z) = (x*y) . (x*z)

- El operador binario (+) define la adición.

- Identidad aditiva es el cero.

- La inversa aditiva define la sustracción.

- El operador binario (.) define la multiplicación.

- Identidad multiplicativa es 1.

- Inversa multiplicativa de A es igual a 1/A define la división esto es A * 1/A = 1

- La única ley distributiva aplicable es la de operador (.) sobre el operador +

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

Para definir formalmente el álgebra de Boole se emplean postulados de Huntington.

1.

a) Cierre con respecto al operador (+)

b) Cierre con respecto al operador (.)

2.

a) Un elemento identidad con respecto al operador (+), designado por el cero x+0 =0+x=x

b) Un elemento identidad con respecto al operador (.) designado por el uno x*1=1*x=x

3.

a) Conmutativo con respecto al operador (+) : x+y = y+x

b) Conmutativo con respecto al operador (.) : x*y =y*x

4.

a) El operador (.) es distributivo sobre el operador (+) : x.(y+z) = (x.y) + (y.z)

b) El operador (+) es distributivo sobre el operador (.) : x+(x.z) = (x+y) . (x+z)

5. Para cada elemento de x pertenencia a B existe un elemento x’ complemento perteneciente a B denominado complemento de x tal que:

a) x+x’ = 1

b) x’ = 0

6. Existen cuando menos dos elementos x,y pertenecientes a B tal que x diferente de y. Por lo tanto tenemos que el álgebra de Boole difiere de la aritmética y del álgebra ordinaria en la sig:

a) Los postulados Huntington: no incluyen al ley asociativa, no obstante esta ley es valida para el álgebra booleana (para ambos operadores)

b) La ley distributiva del operador (+) sobre el operador (.) esto es: x+(y.z) = (x+y).(x+z), la cual es valida para el álgebra de boole pero no para el álgebra ordinaria.

c) El álgebra booleana no tiene inversa aditiva a multiplicativa, por lo tanto no hay operaciones de sustracciones o división.

d) El postulado 5 define un operador llamado completo que no se encuentra en el álgebra ordinaria.

e) En el algebra de Boole se define un conjunto B de dos elementos (0 y 1) y el álgebra ordinaria trata con el conjunto de los números reales.

Postulado 2 a) x + 0 = x b) x . 1 = x

Postulado 5 a) x + x’ = 1 b) x . x’ = 0

Teorema 1 a) x + x = x b) x . x = x

Teorema 2 a) x + 1 = 1 b) x . 0 = 0

Teorema 3 involución (x’)’ = x

Teorema 3 conmutativo a) x + y = y + x b) xy = yx

Teorema 4 asociativo a) x + (y + z) = (x + y) +z b) x (yz) = (xy) z

Postulado 4 distributivo a) x (y + z) = xy +xz b) x + yz = (x + y)(x+z)

Teorema 5 morgan a) ( x + y)’ = x’ y’ b) (xy) = x’ + y’

Teorema 6 absorción a) x + xy = x b) x (x + y) = x

Ejemplos:

x + x = x x + xy = x

x + x = (x + x) . 1 x . 1 + xy = x

x + x = (x + x) (x + x’) x (1 + y) = x

x + x = x + xx’ x (y + 1) = x

x + x = x + 0 x (1) = x

x + x = x x = x

Las variables booleanas pueden tomar varios valores de 1 ó 0.

Una función booleana es una expresión formada por variables binarias.

Ejemplo:

F1 = xyz’

Para F1 considerar que es igual a 1 si:

x = 1; y = 1 ; z’ = 1; de otra manera F1 = 0.

Por lo tanto tendremos que una función booleana también puede representarse en una tabla de verdad. Para representar una función booleana en una tabla de verdad se necesita una lsit de 2ncombinaciones de 1 y 0 de las n variables binarias, y una columna que muestra combinaciones para las cuales f es igual a 1 ó 0.

x y z F1 F2 F3 F4

0 0 0 0 0 1 0

0 0 1 0 1 0 0

0 1 0 1 0 0 0

0 1 1 1 1 1 1

1 0 0 1 0 0 1

1 0 1 0 0 1 1

1 1 0 1 1 1 1

1 1 1 0 1 0 1

F1 = x’yz’ + x’yz + xy’z + xyz’ = x’y (z+z’) + xz’ (y+y’) = x’y + xz’

F2 = x’y’z + x’yz + xyz’ + xyz = x’z (y+y’) + xy (z+z’) = x’z + xy

F3 = x’y’z’ + x’yz + xy’z + xyz’

F4 = x’y’z + xy’z’ + xy’z + xyz’ + xyz

= xy’ (z+z’) + xy (z+z’) + x’yz

= xy’ + xy + x’yz

= x (y+y’) + x’yz

...