Ejercicios de álgebra de Boole

Respuesta al ejercicio 2

En los casos que precede solo demostraremos una parte de cada teorema, deduciendo la otra del principio de dualidad.

Idempotencia

Por los axiomas 4b y 2a tenemos :

a + 0 = a + (a . a' ) = a

y aplicando el axioma 3 a :

a + (a . a' ) = (a + a) . (a + a') = a

Finalmente, por los axiomas 4 a y 2 b :

(a + a) . (a + a') = (a + a) . 1 = a + a = a

Demostrado

Elemento unidad

Partiendo del axioma 2 b y aplicando también los axiomas 3 a, 2 b y 4 a, tenemos :

1 + a = 1 . (1 + a) = (a + a') . (1 + a) = a + a' . 1 = a + a' = 1

Demostrado.

Absorción

Aplicando los axiomas 2b y 3b, el teorema anterior y el axioma 3b de nuevo

a + a.b = a.l + a.b = a(l + b) = a.l = a

Demostrado

Asociatividad

Para este teorema demostraremos antes que se cumple

a[(a + b) + c] = [(a + b) + c]a = a

Esto es : (por el postulado 3b) :

a[(a+b) + c] = a(a+b) + a.c = a + a.c = a = [(a+b) + c]a

donde hemos aplicado reiteradamente el teorema de absorci6n y finalmente el axioma de conmutatividad.
Con el anterior resultado supongamos que se tiene

x = [(a+b) + c] . [a + (b + c)]

aplicando los axiomas de distributividad nos queda :

[(a+b) + c]a + [(a+b) + c].(b+c) = a + [(a+b) + c].(b.c)

donde hemos aplicado el resultado anterior. Aplicando de nuevo la distributividad, e1resultado anterior y el teorema de absorción :

a + {[(a+b) + c].b + [(a+b) + c].c} = a + {b + [(a+b) + c].c} = a + (b + c)

Por otro lado, aplicando los axiomas de distributividad, el resultado anterior y el teorema de absorción, tenemos también :

x = [(a + b) + c]. [a + (b + c)] = (a + b) [a + (b + c)] + c[a + (b + c)] =
= (a + b)[a + (b + c)] + c = {a [a + (b + c)] + b[a + (b + c)]} + c = (a + b) + c

Por todo ello, teniendo en cuenta la propiedad transitiva de la igualdad:

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

Demostrado.

Elemento único

Para demostrar que el complemento definido por el postulado 4 es único, supongamos que existen dos elementos a'₁ y a'₂ que lo satisfacen. Esto es :

a + a'₁ = 1 ; a + a'₂ = 1 ; a.a'₁ = 0 ; a.a'₂ = 0

por los postulados 2b y 3b tendremos :

a'₂ = 1.a'₂ = (a + a'₁).a'₂ = a.a'₂ + a'₁ . a'₂ = 0 + a'₁ . a'₂ = a.a'₁ + a'₁.a'₂ = (a + a'₂).a'₁ = 1.a'₁ + a'₁

Demostrado.

Involución

Para demostrar el teorema de involución tenemos :

(a')' . a' = 0 ; (a')' + a' = 1
a . a' = 0 ; a + a' = 1

en consecuencia, tanto (a')' como a son complementos de a' por lo que, teniendo en cuenta el teorema anterior, se deberá cumplir :

(a')' = a

demostrado.

Propiedad de los elementos identidad de un álgebra de Boole

Teniendo en cuenta los axiomas 2 y 4 :

1' = 1' . 1 = 0 ; 0' = 0'+ 0 = 1

Demostrado.

Leyes de Morgan

Para demostrar las leyes de Morgan tenemos en cuenta que el complementario de cualquier elemento de un álgebra de Boole es único. Tenemos :

\((a+b)·(\bar{a}·\bar{b}) = a·(\bar{a}·\bar{b}) + b·(\bar{a}·\bar{b}) = (a·\bar{a})·\bar{b}+(b·\bar{b})·a = 0+0 = 0 \)

donde hemos aplicado el axioma de distributividad y el de conmutatividad y los teoremas de asociatividad y elemento unidad.

\((a+b)+(\bar{a}·\bar{b}) = (a+b+\bar{a})·(a+b+\bar{b}) = [(a+\bar{a}) + b]·[a+(b+\bar{b})] = \)

\( = (1+b)·(a+1) = 1 \)

donde hemos aplicado los axiomas de distributividad conmutatividad y complementación y el teorema del elemento unidad.
Puesto que \((\bar{a}·\bar{b})\) cumple los axiomas requeridos para ser el complementario de (a+b) y éste debe ser único, hemos llegado donde queríamos.

Demostrado.

Relación de orden

Veamos ahora si la ecuación a' + b = 1 define una relación de orden :

Reflexiva : \(\forall a \in B \; \Rightarrow \; a'+a=1 \; \Rightarrow \; aRa \)

Antisimétrica : Si \(a'+a = 1 \wedge a'+b =1 \; \Rightarrow \; a = b \) por el complemento único.

Transitiva : Si \( aRb \; \Rightarrow \; a' + b = 1 \; y \; a' \) es el complementario de b y si \( bRc \; \Rightarrow \; b' + c = 1 \; \) y c es el complementario de b'

De lo anterior se deduce:

c = b ⇒ a' + c = 1 ⇒ a R c

La implicación recíproca (a ≤ b ⇒ a' + b = 1 ) es trivial.

Demostrado

Sobre conjuntos

Para demostrar el último apartado consideramos las relaciones:

\(\cap \; \leftrightarrow \; ^\prime·^\prime \quad ; \quad \cup \; \leftrightarrow \; ^\prime + ^\prime \quad ; \quad \emptyset \; \leftrightarrow \; 0 \quad ; \quad E \; \leftrightarrow \; 1 \quad ; \quad C(S) \leftrightarrow \; S' \)

con esta transformación se comprueba fácilmente que el álgebra de conjuntos cumple los postulados de Huntington y, en consecuencia, es un álgebra de Boole.

Demostrado.