Matemáticas Discretas

Enunciado 1 de algebra de Boole y álgebra de proposiciones
Teorema lB (principio de dualidad). Demostrar que cada aserción o identidad
algebraica deducible de los postulados del álgebra de Boole sigue siendo válida si
las operaciones " + " y " . " y los elementos identidad (1 y 0) se intercambian entre
si.
Ver Solución.
Tomando los postulados (a) de Huntigton e intercambiando en ellos losoperadores y elementos identidad resulta:
1 a)
2 a)

a+b=b+a
a+0=a

3 a)

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

4 a)

a + a’ = 1

a.b=b.a
a.1=a
a . (b + c) = (a .b) + (a .
c)
a . a’ = 0

(1 b
(2 b
(3 b
(4 b

Es decir, que a partir de los postulados (a) se obtienen los postulados (b). Esto
demuestra lo que nos habíamos propuesto.

Enunciado 2 de algebra de Boole y álgebra deproposiciones
Demostrar que para todos los elementos a, b, c de un álgebra de Boole se
verifican los siguientes teoremas:
Idempotencia:
Elemento unidad:
Absorción :
Asociatividad:
Complemento único:
Involución:
En cualquier álgebra
booleana:
Leyes de Morgan
Relación de orden:
Sobre conjuntos:

a+a=a
;
a.a=a
a+1=1
;
a.0=0
a + (a . b) = a
;
a . (a + b) = a
a + (b + c) = (a +b) + c ;
a . (b . c) = (a . b) . c
El elemento a' asociado al a es único
(a')' = a
0' = 1

;

1' = 0

(a + b)' = a' . b'
(a . b)' = a' + b'
;
si a b
a' + b = 1
;
si a b
a' . b = 0
Cada álgebra booleana que pueda formarse es
isomorfa al álgebra de conjuntos.

Ver Solución.
Respuesta 2
En los casos que precede solo demostraremos una parte de cada teorema,
deduciendo la otradel 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]adonde 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 anteriory 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
Portodo 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 :

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
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...