Apunte Matematica Discreta - Algebra De Boole
Páginas: 32 (7876 palabras)
Publicado: 25 de octubre de 2012
ÁLGEBRAS BOOLEANAS
Unidad 4
ÁLGEBRAS BOOLEANAS
ÁLGEBRAS BOOLEANAS
George Boole, famoso matemático del siglo XIX, en el año 1854 escribió el libro “The Laws of Thought”, que
contribuyó para el desarrollo de una teoría lógica que utilizaba símbolos en lugar de palabras.
En el año 1938, C. E. Shannon, quien en 1936 obtuvo los títulos de ingeniero electricista y matemático en laUniversidad de Michigan, aceptó la posición de asistente de investigación en el departamento de ingeniería eléctrica
en el Instituto de Tecnología de Massachusetts (MIT). Trabajó en el computador analógico más avanzado de esa
era: Vannevar Bush's Differential Analyzer. En su tesis de maestría en el MIT, demostró cómo el álgebra booleana se
podía utilizar en el análisis y la síntesis de la conmutacióny de los circuitos digitales. Este fue el puntapié que
convirtió al álgebra booleana en un medio indispensable para el análisis y el diseño de computadoras electrónicas.
Veremos a continuación el concepto de Álgebra de Boole -que no debe resultarnos extraño ya que, en definitiva, es
un caso particular de las redes vistas en la unidad anterior-, subálgebra de Boole, homomorfismo (o morfismo) eisomorfismo para estas Álgebras.
Más adelante nos ocuparemos de las funciones booleanas.
Comencemos con la definición de Álgebra de Boole:
B es un Algebra de Boole sii B es una red distributiva y complementada.
es un lgebra de Boole s
complementada.
Podemos
cualesquiera
Podemos decir que un conjunto parcialmente ordenado en el cual dos elementos cualesquiera tienen una
parcialmenteúnica
superior mínima una única
única cota superior mínima y una única cota inferior máxima, complementado y distributivo se conoce
máxima, complementado distributivo
como Álgebra Boole.
como Álgebra de Boole.
De la definición vamos a inferir algunas observaciones:
El conjunto B está ordenado.
El primer elemento de B es
0B .
El último elemento de B es 1B .
Mínima cota superiorm.c.s {a,b} = a
Máxima cota inferior
m.c.i {a,b} = a
b
b
B
B
(B; ; ) es un álgebra de Boole si y sólo si cumple los siguientes 5 axiomas:
1. : B²
B; : B² B
2. a B,
b B: a b = b
a
b=b a
B, b B, c B: a (b c) = (a b) (a c)
a (b c) = (a b) (a c)
B tal que a B: a 0 B = a
B tal que a B: a
1B = a
B,
a B tal que a a = 1B
a a = 0B
a
3.
a
4.
0B
1B
5.
a
1Unidad4
ÁLGEBRAS BOOLEANAS
Un Algebra de Boole es un sistema dual y por lo tanto se verifica el Principio de Dualidad.
Este tema lo podés consultar en el capítulo 14 del libro de la cátedra.
e
Los siguientes ejemplos pueden aclarar algunas dudas:
1. ({0, 1}; ; ) cuyas tablas de operaciones son las siguientes:
01
001
111
01
000
101
Es el Álgebra de Boole trivial con elsiguiente Diagrama de Hasse:
1
0
2. D10 = {x
tales que x | 10}, con a
Su diagrama de Hasse es el siguiente:
a | b es un Algebra de Boole.
b
10
2
5
1
a
b
c
d
Tomemos los átomos para generar los números x = 2 . 5 , y = 2 . 5
con a, b, c, d {0, 1}
2
Unidad4
ÁLGEBRAS BOOLEANAS
Entonces operemos x e y con
y
D
D
para ver si cumplen conlas propiedades:
a) Veamos si son operaciones cerradas en D10 :
x
x
D
D
y = 2a
y = 2a
Por lo tanto
D
c
. 5b
c
. 5b
e
d
d
D10
D10
son operaciones cerradas en D10 .
D
b). Comprobemos ahora si son conmutativas:
x
x
Por lo tanto
D
D
D
y = 2a c . 5b
= 2c a . 5d
=y Dx
y = 2a c . 5b
= 2c a . 5d
=y Dx
e
d
b
porconmutatividad del
d
b
por conmutatividad del
son operaciones conmutativas en D10 .
D
c). Probemos la distributividad de ambas operaciones:
e
f
Sea z = x = 2 . 5 , con e y f
x
D
(y
D
z) =
=
=
=
Esto verifica la distributividad de
es decir
x
D
x
(y
D10 , y
z) = (x
D
d) Encontremos el
{0, 1}
2a . 5b D ( 2c . 5d D 2e . 5f) reemplazando los...
Unidad 4
ÁLGEBRAS BOOLEANAS
ÁLGEBRAS BOOLEANAS
George Boole, famoso matemático del siglo XIX, en el año 1854 escribió el libro “The Laws of Thought”, que
contribuyó para el desarrollo de una teoría lógica que utilizaba símbolos en lugar de palabras.
En el año 1938, C. E. Shannon, quien en 1936 obtuvo los títulos de ingeniero electricista y matemático en laUniversidad de Michigan, aceptó la posición de asistente de investigación en el departamento de ingeniería eléctrica
en el Instituto de Tecnología de Massachusetts (MIT). Trabajó en el computador analógico más avanzado de esa
era: Vannevar Bush's Differential Analyzer. En su tesis de maestría en el MIT, demostró cómo el álgebra booleana se
podía utilizar en el análisis y la síntesis de la conmutacióny de los circuitos digitales. Este fue el puntapié que
convirtió al álgebra booleana en un medio indispensable para el análisis y el diseño de computadoras electrónicas.
Veremos a continuación el concepto de Álgebra de Boole -que no debe resultarnos extraño ya que, en definitiva, es
un caso particular de las redes vistas en la unidad anterior-, subálgebra de Boole, homomorfismo (o morfismo) eisomorfismo para estas Álgebras.
Más adelante nos ocuparemos de las funciones booleanas.
Comencemos con la definición de Álgebra de Boole:
B es un Algebra de Boole sii B es una red distributiva y complementada.
es un lgebra de Boole s
complementada.
Podemos
cualesquiera
Podemos decir que un conjunto parcialmente ordenado en el cual dos elementos cualesquiera tienen una
parcialmenteúnica
superior mínima una única
única cota superior mínima y una única cota inferior máxima, complementado y distributivo se conoce
máxima, complementado distributivo
como Álgebra Boole.
como Álgebra de Boole.
De la definición vamos a inferir algunas observaciones:
El conjunto B está ordenado.
El primer elemento de B es
0B .
El último elemento de B es 1B .
Mínima cota superiorm.c.s {a,b} = a
Máxima cota inferior
m.c.i {a,b} = a
b
b
B
B
(B; ; ) es un álgebra de Boole si y sólo si cumple los siguientes 5 axiomas:
1. : B²
B; : B² B
2. a B,
b B: a b = b
a
b=b a
B, b B, c B: a (b c) = (a b) (a c)
a (b c) = (a b) (a c)
B tal que a B: a 0 B = a
B tal que a B: a
1B = a
B,
a B tal que a a = 1B
a a = 0B
a
3.
a
4.
0B
1B
5.
a
1Unidad4
ÁLGEBRAS BOOLEANAS
Un Algebra de Boole es un sistema dual y por lo tanto se verifica el Principio de Dualidad.
Este tema lo podés consultar en el capítulo 14 del libro de la cátedra.
e
Los siguientes ejemplos pueden aclarar algunas dudas:
1. ({0, 1}; ; ) cuyas tablas de operaciones son las siguientes:
01
001
111
01
000
101
Es el Álgebra de Boole trivial con elsiguiente Diagrama de Hasse:
1
0
2. D10 = {x
tales que x | 10}, con a
Su diagrama de Hasse es el siguiente:
a | b es un Algebra de Boole.
b
10
2
5
1
a
b
c
d
Tomemos los átomos para generar los números x = 2 . 5 , y = 2 . 5
con a, b, c, d {0, 1}
2
Unidad4
ÁLGEBRAS BOOLEANAS
Entonces operemos x e y con
y
D
D
para ver si cumplen conlas propiedades:
a) Veamos si son operaciones cerradas en D10 :
x
x
D
D
y = 2a
y = 2a
Por lo tanto
D
c
. 5b
c
. 5b
e
d
d
D10
D10
son operaciones cerradas en D10 .
D
b). Comprobemos ahora si son conmutativas:
x
x
Por lo tanto
D
D
D
y = 2a c . 5b
= 2c a . 5d
=y Dx
y = 2a c . 5b
= 2c a . 5d
=y Dx
e
d
b
porconmutatividad del
d
b
por conmutatividad del
son operaciones conmutativas en D10 .
D
c). Probemos la distributividad de ambas operaciones:
e
f
Sea z = x = 2 . 5 , con e y f
x
D
(y
D
z) =
=
=
=
Esto verifica la distributividad de
es decir
x
D
x
(y
D10 , y
z) = (x
D
d) Encontremos el
{0, 1}
2a . 5b D ( 2c . 5d D 2e . 5f) reemplazando los...
Leer documento completo
Regístrate para leer el documento completo.