Tarea 1

Departamento de Matemática Aplicada. ETSIInf. UPM.

Victoria Zarzosa Rodríguez

ÁLGEBRAS DE BOOLE
Ejemplos
1) Si S es un conjunto, entonces ((S), , ) es álgebra de Boole.
A  B = AB

A  B =AB

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 xy

x

y xy

0

0

0

0

0

0

0

1

1

0

1

0

1

0

1

1

0

0

1

1

1

1

1

1

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