Tarea 1
Victoria Zarzosa Rodríguez
ÁLGEBRAS DE BOOLE
Ejemplos
1) Si S es un conjunto, entonces ((S), , ) es álgebra de Boole.
A B = AB
A B =AB
2) Sea Dn = { z / z divide a n } con las operaciones
a b = mcm {a, b}
a b = mcd {a, b}
Teorema
(Dn, , ) es un álgebra de Boole n = p1 p2 ... pk
con pi números primosdistintos dos a dos y distintos de 1.
1
Departamento de Matemática Aplicada. ETSIInf. UPM.
Victoria Zarzosa Rodríguez
3) El conjunto de Boole = {0, 1} con las operaciones definidas por
las tablas siguientes es un álgebra de Boole
x
y xy
x
y xy
0
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
0
1
1
1
1
1
1
2Departamento de Matemática Aplicada. ETSIInf. UPM.
Victoria Zarzosa Rodríguez
4) Sea n = { 0, 1 }n = { ( x1, x2, ..., xn ) / xi }
en el que se definen las siguientes operaciones:
(x1, x2, ..., xn) (y1, y2, ..., yn) = (x1 y1, x2 y2, ..., xn yn)
(x1, x2, ..., xn) (y1, y2, ..., yn) = (x1 y1, x2 y2, ..., xn yn)
elemento neutro para la suma o
mínimo 0 = (0, ..., 0) elemento neutro para el producto o máximo 1 = (1, ..., 1)
complementario
(x1, x2, ..., xn) ´ = (x1´, x2´, ..., xn´)
Entonces ( n, , ) es un álgebra de Boole.
3
Departamento de Matemática Aplicada. ETSIInf. UPM.
Victoria Zarzosa Rodríguez
Teorema
Si (A, , ) es un álgebra de Boole, entonces se verifican las
siguientes propiedades:
1. absorción del neutro
1 x = 1,2. involutiva
0 x = 0
( x ´)´ = x
(el complementario de cada elemento es único)
3. leyes de De Morgan
(x y)´ = x ´ y ´
(x y)´ = x ´ y ´
4
Departamento de Matemática Aplicada. ETSIInf. UPM.
Victoria Zarzosa Rodríguez
ISOMORFISMOS DE ÁLGEBRAS DE BOOLE
Sean ( A, , ), ( A´, ´, ´ ) álgebras de Boole.
La aplicación
f : A A´ es un homomorfismo si
f (a b) = f (a) ´ f (b)
f (a b) = f (a) ´ f (b)
Las álgebras de Boole ( A, , ) y ( A´, ´, ´ ) son isomorfas
si existe un homomorfismo biyectivo entre ellas.
5
Departamento de Matemática Aplicada. ETSIInf. UPM.
Victoria Zarzosa Rodríguez
Teorema
Si
(A, , )
es un álgebra de Boole finita entonces existe un
conjunto finito S tal que (A, , ) y ((S), , ) sonisomorfas.
Teorema
Si S es un conjunto finito con card S = n, entonces ((S), , ) y
( n, , )
son álgebras de Boole isomorfas.
Teorema
Si (A, , ) es un álgebra de Boole finita entonces
card A = 2n,
para algún n
6
Departamento de Matemática Aplicada. ETSIInf. UPM.
Victoria Zarzosa Rodríguez
Ejemplos
1) Las álgebras de Boole
(D, mcm, mcd) y (({a, b, c}),, ) son isomorfas.
La aplicación f : D ({a, b, c}) es un isomorfismo:
f (1) =
f (2) = { a }
f (3) = { b }
f (5) = { c }
f (6) = f (2 . 3) = { a, b }
f (10) = f (2 . 5) = { a, c }
f (15) = f (3 . 5) = { b, c }
f (30) = f (2 . 3 . 5) = { a, b, c }
7
Departamento de Matemática Aplicada. ETSIInf. UPM.
Victoria Zarzosa Rodríguez
2) Las álgebras de Boole
(({a, b, c}), ,) y ( 3, , ) son isomorfas.
La aplicación f : ({a, b, c}) ( 3, , ) es un isomorfismo:
f () = (0, 0, 0)
f ({ a }) = (1, 0, 0)
f ({ b }) = (0, 1, 0)
f ({ c }) = (0, 0, 1)
f ({ a, b }) = (1, 1, 0)
f ({ a, c }) = (1, 0, 1)
f ({ b, c }) = (0, 1, 1)
f ({ a, b, c }) = (1, 1, 1)
8
Departamento de Matemática Aplicada. ETSIInf. UPM.
Victoria Zarzosa Rodríguez
VARIABLES BOOLEANASLos ordenadores representan la información usando bits.
Un bit ( binary digit ) tiene dos valores posibles
1 (uno)
0 (cero)
V ( verdadero)
F (falso)
(John W. Tukey, 1946)
Una variable booleana es una variable que toma dos valores:
{uno, cero}
{verdadero, falso}
{si, no}
Una variable booleana se puede representar usando un bit.
Las cadenas de bits son...
Regístrate para leer el documento completo.