Estructuras Discretas

´
ALGEBRAS DE BOOLE

0.1.

´
Algebras de Boole

´
Definici´n 0.1.1 Un Algebra de Boole es una sextupla (B, +, ·, , 0, 1),
o
donde B es un conjunto, 0(llamado elemento cero) y 1 (llamado elemento
identidad) son elementos distintos de B , +, · son operaciones binarias
+ : BxB → B
(a, b) → a + b (suma de a y b)
· : BxB → B
(a, b) → a · b (producto de a y b)
es una operaci´n unitariao
:B→B
a → a ( a a se le llama complemento de a)
tales que para todo a, b ∈ B se cumplen los siguientes axiomas:
B1) a + b = b + a, a · b = b · a (leyes conmutativas)
B2) a + 0 = a, a · 1 = a (leyes de identidad)
B3) a · (b + c) = (a · b) + (a · c), a + (b · c) = (a + b) · (a + c) (leyes distributivas)
B4) a + a = 1, a · a = 0 (leyes de complementaci´n)
o
´
Observaci´n 0.1.1
o
1. Enun Algebra de Boole (B, +, ·, , 0, 1), cuando se
sobreentienden quienes son +, ·, , 0, 1, se suele decir por comodidad el
´
Algebra de Boole B
´
2. Debe quedar claro que en un Algebra de Boole (B, +, ·, , 0, 1), 0 y 1 son
simbolos, no debe creerse que necesariamente los ’n´meros’ 0, 1 est´n
u
a
en B , sino que en B existen dos elementos que se simbolizan por 0, 1
que cumplen con losaxiomas B 2, B 4 anteriores
3. El 0 es el unico elemento que cumple con los axiomas B 2 y B 4, igual´
mente 1
1

4. Para cada a existe s´lo un a que cumple con B 4
o
Ejemplo 0.1.1 Sea B un conjunto de proposiciones tales que si p, q ∈ B ,
´
entonces p ∧ q, p ∨ q, ∼ p, ∼ q ∈ B . Entonces (B, ∨, ∧, ∼, F, V ) es un Algebra
de Boole
∨ = +, ∧ = ·, ∼= , 0 = F (una contradicci´n), 1 = V (unatautolog´a).
o
ı
Sabemos que B satisface los axiomas B 1, B 2, B 3, B 4 por la teor´a del capitulo
ı
1
Observaci´n 0.1.2 Las leyes del ´lgebra proposicional se dan en t´rminos
o
a
e
de la relaci´n de equivalencia l´gica y no en t´rminos de la relaci´n de igualo
o
e
o
dad, como se exigen el los axiomas B 1, B 2, B 3, B 4. Este problema se resuelve
tomando en lugar de B , el conjuntocociente de B por la relaci´n (de equivo
alencia) equivalencia l´gica
o
Ejemplo 0.1.2 Sea U un conjunto no vac´o. (P (U ), , , , ∅, U ) es un
ı
´
Algebra de Boole
P (U ) = B , = +, = ·, = , 0 = ∅, 1 = U . Sabemos que P (U ) satisface
los axiomas B 1, B 2, B 3, B 4 por la teor´a del capitulo 2
ı
Ejemplo 0.1.3 Sea B un conjunto con s´lo dos elementos, digamos B =
o
{a, b}. Definamos lasoperaciones +, ·, como sigue
a + a = a, b + b = b, a + b = b + a = b
a · a = a, b · b = b, a · b = b · a = a
a = b, b = a
´
´
Entonces (B, +, ·, , a, b) es un Algebra de Boole, llamada Algebra de Boole
de todo o nada
Si U = {x} (un conjunto con s´lo un elemento), entonces (P (U ), , , , ∅, U )
o
´
es un Algebra de Boole de todo o nada
De igual manera si B = {F, V } (contradicci´n, tautolog´entonces (B, ∨, ∧, ∼
o
ıa),
´
, F, V ) es un Algebra de Boole de todo o nada tambi´n
e
´
Teorema 0.1.1 Sea (B, +, ·, , 0, 1) un Algebra de Boole
1. a + b = 1 ∧ a · b = 0 ⇒ b = a (unicidad del complemento)
2

2. (a ) = a (ley de involuci´n)
o
3. b · a = c · a ∧ b · a = c · a ⇒ b = c
´
Definici´n 0.1.2 Sea (B, +, ·, , 0, 1) un Algebra de Boole. El dual de un
o
´
enunciado en estaAlgebra de Boole, es el enunciado que se obtiene intercambiando + con · y 0 con 1 en el enunciado original
Ejemplo 0.1.4

1. El dual de a + 1 = 1 es a · 0 = 0

2. El dual de a · (b + c) = (a · b) + (a · c) es a + (b · c) = (a + b) · (a + c)
3. El dual de a + a = 1 es a · a = 0
Teorema 0.1.2 (Principio de dualidad)
´
En un Algebra de Boole, el dual de un teorema es un teorema
Veamos laimportancia de este teorema
´
Teorema 0.1.3 Sea (B, +, ·, , 0, 1) un Algebra de Boole. Entonces para todo
a, b, c ∈ B se cumple que:
1. a + a = a, a · a = a (leyes de idempotencia)
2. a + 1 = 1, a · 0 = 0 (leyes de identidad)
3. 1 = 0, 0 = 1 (leyes de complementaci´n)
o
4. a · (a + b) = a, a + (a · b) = a (leyes de absorci´n)
o
5. a + (b + c) = (a + b) + c, a · (b · c) = (a · b) · c...