Algebra

NOCIONES SOBRE
´
ALGEBRA DE BOOLE

1. Definici´n y propiedades generales
o
2. Funciones booleanas en el ´lgebra de Boole binaria
a
3. Simplificaci´n de funciones booleanas
o
4. El m´todo de simplificaci´n de Quine-McCluskey
e
o

1

1. Definici´n y propiedades generales
o
El ´lgebra de Boole es una estructura matem´tica que, como tal, abarca un
a
a
abanico de situaciones cuyacomponente com´n es la que se formula en su
u
definici´n.
o
En particular, el ´lgebra de Boole tiene aplicaci´n en la s´
a
o
ıntesis de redes de
conmutaci´n, en el estudio de circuitos digitales y en el an´lisis y prograo
a
maci´n mediante ordenador.
o
Definici´n de ´lgebra de Boole
o
a
Un conjunto B dotado de dos leyes de composici´n interna (suma y producto)
o
tiene estructura de´lgebra de Boole si se verifican las propiedades siguientes.
a
(1) Las dos leyes son asociativas.
(a + b) + c = a + (b + c)
(a b) c = a (b c)

∀ a, b, c ∈ B

(2) Las dos leyes son conmutativas.
a+b=b+a
ab = ba

∀ a, b ∈ B

(3) Cada ley tiene elemento neutro.
∃0 ∈ B/ a + 0 = a
∃1 ∈ B/ a1 = a

∀a ∈ B
∀a ∈ B

(4) Para cada elemento a ∈ B existe un unico elemento a ∈ B, llamado
´complementario de a, tal que
a+a=1
aa = 0
(5) Cada ley es distributiva respecto a la otra.
a (b + c) = a b + a c
a + (b c) = (a + b) (a + c)
2

∀ a, b, c ∈ B

Estos cinco pares de propiedades se consideran propiedades primitivas que
caracterizan la estructura de ´lgebra de Boole. Tambi´n reciben el nombre
a
e
de axiomas del ´lgebra de Boole. El resto de propiedades se deduce a partira
de ´stas.
e
Ejemplos de ´lgebras de Boole
a
(1) Consideremos un conjunto U al que nos referiremos como universo.
Llamamos conjunto de las partes del conjunto U al conjunto formado
por todos los subconjuntos del conjunto U ; lo denotamos por P(U ).
Si el n´mero de elementos de U es card U = n entonces card P(U ) = 2n .
u
Todo conjunto P(U ) con las operaciones uni´n de conjuntos, ∪, eino
tersecci´n de conjuntos, ∩, tiene estructura de ´lgebra de Boole.
o
a
El elemento neutro de la uni´n de conjuntos es el conjunto vac´ ∅,
o
ıo,
mientras que el neutro de la intersecci´n es el conjunto universo U .
o
El elemento complementario de cualquier subconjunto A ∈ P(U ) es el
complementario en el sentido de conjuntos:
A = {x ∈ U /x ∈ A}
o o
(2) Una proposici´n l´gica es unenunciado declarativo que puede ser verdadero o falso, pero no ambas cosas a la vez. El conjunto de las proposiciones l´gicas con las operaciones disyunci´n (o, ∨) y conjunci´n (y, ∧)
o
o
o
tiene estructura de ´lgebra de Boole.
a
(3) El ´lgebra de Boole binaria, formada unicamente por dos elementos:
a
´
B = { 0, 1 }
Principio de dualidad del ´lgebra de Boole
a
Toda propiedad que puedadeducirse de las propiedades primitivas o de
cualquier otra propiedad derivada de ´stas da lugar a otra propiedad que
e
se obtiene intercambiando:
- las operaciones suma y producto,
- los s´
ımbolos 0 y 1.
La propiedad as´ obtenida recibe el nombre de propiedad dual de la inicial.
ı
El principio de dualidad es consecuencia de la propia estructura de ´lgbra de
a
Boole, ya que cada par depropiedades en su definici´n est´ formada por una
o
a
y por su dual.
3

Propiedades en un ´lgebra de Boole
a
Las siguientes propiedades son consecuencia de las propiedades primitivas.
(1) Involuci´n.
o

x = x,

(2) Idempotencia.
(3) x 0 = 0,

x + x = x,

x + 1 = 1,

(4) Absorci´n.
o

∀ x ∈ B.
x x = x,

∀ x ∈ B.

∀ x ∈ B.

x + xy = x
x (x + y) = x

∀ x, y ∈ B.(5) Los neutros son rec´
ıprocamente complemetarios.
(6) x + x y = x + y,

x (x + y) = x y,

(7) Leyes de De Morgan.

0 = 1,

1 = 0.

∀ x, y ∈ B.

(1a Ley)

x + y = xy

(2a Ley)

xy = x + y

∀ x, y ∈ B.

Demostraci´n
o
(1) Basta comprobar que x hace el papel de complemetario de x.
x+x=x+x=1

∧

xx = xx = 0

Las dos primeras igualdades se deducen de las respectivas...