Download Álgebra de Boole Definición axiomática

Álgebra de Boole
Álgebra de Boole
Definición axiomática
El álgebra de Boole es un Sistema Matemático consistente en un conjunto
de elementos (B) y dos operaciones matemáticas (+ y  ) que cumple
los siguientes postulados:
Postulados de Huntington
p1: Postulado del cierre: Si x, y  B
(a) x + y  B
(b) x  y  B
p2 : Postulado de los elementos de identidad: para x  B
(a)  un elemento de identidad con respecto al operador + denominado elemento
nulo es designado por el símbolo 0 y cumple: x + 0 = 0 + x = x
(b)  un elemento de identidad con respecto al operador  denominado elemento
unidad es designado por el símbolo 1 y cumple : x1 = 1x = x
Álgebra de Boole
Definición axiomática
p3 : Propiedad conmutativa:  x,y  B
(a) x+y = y+x
(b) xy = yx
p4 : Propiedad distributiva:  x,y,z  B
(a) x(y+z) = xy + xz
(b) x+(yz) = (x+y)  (x+z)
p5 : Axiomas del complemento:  x B  x’  B que cumple:
(a) x + x’ = 1
(b) x  x’ = 0
p6 : Existen al menos dos elementos x, y  B / x ≠ y
Álgebra de Boole
Convenciones
- La representación del operador  puede omitirse:
a  b también puede representarse como ab
- El operador  tiene precedencia respecto al +
(a  b) + (c  d)  ab +cd
Álgebra de Boole.
Teoremas.
T0: Principio de dualidad: cada teorema deducible de los postulados
de un álgebra booleana puede transformarse en un segundo teorema
válido sin más que intercambiar las operaciones + y  entre sí, así
como los elementos 0 y 1.
T1 : Teorema de idempotencia
(a) x + x = x
(b) x · x = x (b es la dual de a)
T2 : Teorema de los elementos dominantes
(a) x + 1 = 1
(b) x · 0 = 0 (b es la dual de a)
Álgebra de Boole.
Teoremas.
T3 : Ley involutiva
(x’)’ = x
T4 : Teorema de absorción
(a) x + xy = x
(b) x · (x+y) = x
T5 : Teorema del consenso
(a) x + (x’y) = x+y
(b) x · (x’+y) = xy
Álgebra de Boole.
Teoremas.
T3 : Ley involutiva
(x’)’ = x
T4 : Teorema de absorción
(a) x + xy = x
(b) x · (x+y) = x
T5 : Teorema del consenso
(a) x + (x’y) = x+y
Dem: x + x’y = <distrib> (x + x’) · (x + y) = <complement> 1 · (x + y) = <ident> x + y
(b) x · (x’+y) = xy
Álgebra de Boole.
Teoremas.
Teorema del consenso generalizado
(a) xy + x’z + yz = xy + x’z
Dem:
xy + x’z + yz = <elemento unidad>
xy + x’z + yz1 = <complemento>
xy + x’z + yz(x + x’) = <distributiva>
xy + x’z + xyz + x’yz = <conmutativa>
xy + xyz + x’z + x’yz = <absorción>
xy + x’z
(b) x · (x’+y) = xy
Álgebra de Boole.
Teoremas.
T6 : Teorema asociativo
(a) x+(y+z)= (x+y)+z
(b) x(yz)=(xy) z
T7 : Leyes de DeMorgan
(a) (x+y)’ = x’y’
(b) (xy)’ = x’ + y’
Álgebra de Boole.
Teoremas.
Ley de DeMorgan generalizada
x1  x2  x3  ...  xn  x1·x2 ·x3 ·...·xn
n
x
i 1
i
n
  xi
i 1
x1·x2 ·x3 ·...·xn  x1  x2  x3  ...  xn
n
n
i 1
i 1
 xi   xi
Álgebra de Conmutación
Álgebra de Conmutación
•
•
•
Nuestro objetivo es establecer una relación entre el álgebra de Boole y
los circuitos.
Para ello introduciremos un tipo particular del álgebra de Boole
denominada álgebra de conmutación.
En este álgebra:
B={0,1}
x
0
0
1
1
y
0
1
0
1
x+y
(operación
OR)
0
1
1
1
xy
(operación AND)
0
0
0
1
x
x'
0
1
1
0
En este álgebra se cumplen los postulados y teoremas descritos anteriormente