Ejercicios de álgebra de Boole
Demostrar que para todos los elementos a, b, c de un álgebra
de Boole se verifican los siguientes teoremas:
| |
Idempotencia: |
a + a = a |
; |
a . a = a |
| |
Elemento unidad: |
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 |
| |
Complemento único: |
El elemento a' asociado al a
es único |
| |
Involución: |
(a')' = a |
| |
En cualquier álgebra booleana: |
0' = 1 |
; |
1' = 0 |
| |
Leyes de Morgan |
(a + b)' = a' . b' |
; |
(a . b)' = a' + b' |
| |
Relación de orden: |
si a ≤ b ⇒ a' + b = 1 |
; |
si a ≤ b ⇒ a' . b = 0 |
| |
Sobre conjuntos: |
Cada álgebra booleana que pueda formarse
es isomorfa al álgebra de conjuntos. |
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 absorción
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
:
\(\begin{array}{l} a + {[(a+b) + c].b + [(a+b) + c].c} = \\
\\ = a + {b + [(a+b) + c].c} = a + (b + c) \end{array} \)
Por otro lado, aplicando los axiomas de distributividad, el resultado
anterior y el teorema de absorción, tenemos también
:
\(\begin{array}{l}
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
\end{array} \)
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'
1 y
a'
2 que lo satisfacen.
Esto es :
a + a'1 = 1 ; a
+ a'2 = 1 ; a.a'1
= 0 ; a.a'2 = 0
por los postulados 2b y 3b tendremos :
\( \begin{array}{l}
a'_2 = 1.a'_2 = (a + a'_1).a'_2 = a.a'_2 + a'_1 . a'_2 = 0 +
a'_1 . a'_2 = \\
\\
= a.a'_1 + a'_1.a'_2 = (a + a'_2).a'_1 = 1.a'_1 + a'_1
\end{array}\)
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 :
\(\begin{array}{l}
(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
\end{array} \)
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.
Problemas
resueltos - ÁLGEBRA
DE PROPOSICIONES Y DE BOOLE
|
|
|
|