[Maths] 6.3.1 algebras de boole

Logica Matemática. Algebras de Boole

1. ÁLGEBRAS DE BOOLE
para Computación
By Miguel Pérez Fontenla, January 2012

2. By Miguel Pérez Fontenla, January 2012

3. ALGEBRAS DE BOOLE
Álgebra de Boole en informática y matemáticas, es una estructura algebraica que
esquematiza las operaciones lógicas Y, O , NO y Si (AND, OR, NOT, IF)
Definición: Álgebra de Boole

4. ALGEBRAS DE BOOLE
Sea un conjunto B, con dos operaciones binarias
suma +, y
producto *, y otra operación unitaria llamada
complemento ‘,
y, al menos, dos elementos neutros llamados
cero 0 y
unidad 1,
Se dice pues que la séxtupla {B, +, *, ‘, 0, 1} es un álgebra de Boole si verifica las propiedades:
•Conmutativa,
•Distributiva,
•Identidad,
•Complemento,
Definición: Álgebra de Boole
,
* *
a b b a
a b B
a b b a
+ = +ì
" Î í
=î
( )( )( )
( )( )( )
* *
, ,
* * *
a b c a b a c
a b c B
a b c a b a c
+ = + +ìï
" Î í
+ = +ïî
0
*1
a a
a B
a a
+ =ì
" Îí
=î
' 0
* ' 1
a a
a B
a a
+ =ì
" Îí
=î

5. ALGEBRAS DE BOOLE
Definición: Enunciado dual
A los enunciados obtenidos de cambiar
•la operación + por la * y
•los 1 por 0
( y viceversa) se le denomina enunciado dual del enunciado dado.
Teorema o principio de dualidad
Cualquier dual de un teorema de un álgebra de Boole es también un teorema.
Ejemplo
Si demostramos que es cierta la ley Distributiva: a *(b + c) (a *b) + (a *c)
≡
También quedará demostrada su dual: a + (b *c) (a + b) *(a + c)
≡
PRINCIPIO DE DUALIDAD

6. ALGEBRAS DE BOOLE
Definición: Enunciado dual
A los enunciados obtenidos de cambiar
•la operación + por la * y
•los 1 por 0
( y viceversa) se le denomina enunciado dual del enunciado dado.
Teorema o principio de dualidad
Cualquier dual de un teorema de un álgebra de Boole es también un teorema.
Ejemplo
Si demostramos que es cierta la ley Distributiva: a *(b + c) (a *b) + (a *c)
≡
También quedará demostrada su dual: a + (b *c) (a + b) *(a + c)
≡
PRINCIPIO DE DUALIDAD

7. ALGEBRAS DE BOOLE
Conjuntos


una colección de conjuntos cerrados. Entonces {,, ,
⋃ ⋂
c
, ,
∅
∅ } es un álgebra de Boole.
Las proposiciones lógicas
Sea S

el conjunto de las proposiciones lógicas. La séxtupla formada por {e, , , ,
∧ ∨ ∼
f, τ } es un álgebra
de Boole.
Las clase de las congruencias módulo m.
Sea D = { 1, 2, 5, 7, 10, 14, 35, 70 } de todos los divisores de 70.
{D, +, *, ‘, 1, 70} es un álgebra de Boole donde
•a + b = MCM(a,b) (mínimo común múltiplo de a y b)
•a * b = MCD(a,b) (máximo común divisor de a y b)
•a’ = 70/a
•1 es el elemento cero
•70 es el elemento unidad
EJEMPLOS DE ALGEBRAS DE BOOLE

8. ALGEBRAS DE BOOLE
TEOREMAS BASICOS
Propiedad Ley Ley dual
1.- Ley Conmutativa a + b = b + a a * b = b * a
2.- Ley Asociativa (a + b) + c ≡ a + (
b
+ c) (a * b) * c ≡ a * ( *
b
c)
3.- Ley Distributiva a *(b + c) ≡ (a *) +
b
(a *c) a + (b *c) ≡ (a + )
b
*(a + c)
4.- Ley de Idempotencia a + a ≡ a a * a ≡ a
5.- Ley de Identidad a + 1 ≡ 1
a + 0 ≡ a
a * 0 ≡ 0
a * 1 ≡ a
6.- Ley de Complemento a + a’ ≡ 1
0’ ≡ 1
a * a’ ≡ 0
1’ ≡ 0
7.- Ley de involución (a’)’ ≡ a (a’)’ ≡ a
8.- Ley de Morgan ∼(a + b) ≡ ∼a * ∼b ∼(a * b) ≡ ∼a + ∼b

9. ALGEBRAS DE BOOLE
Teorema: Unicidad del complemento
Sea B un álgebra de Boole y sean a, x
∊
B, se verifica que si
a + x = 1
a * x = 0 (dual) entonces x = a’
Teorema: Leyes de redundancia
Sea B un álgebra de Boole y sean a, b
∊
B, entonces se verifica:
Propiedad Ley Ley dual
1ª Ley de redundanciaa + (a * b) = a a * (a + b) = a
2ª Ley de redundanciaa * (a’ + b) = a * b a + (a’ * b) = a + b

10. ALGEBRAS DE BOOLE
EQUIVALENCIAS
Algebra de Conjuntos Algebra de proposiciones Algebras de Boole
Unión ⋃ Disyunción ∨ Suma +
Intersección ⋂ Conjunción ∧ Producto ·
Complementario
c
Negación ∼ Complemento ‘
Conjunto vacío ∅ Falsedad f Elemento 0 0
Conjunto universal U Tautología τ Elemento 1 1

11. ALGEBRAS DE BOOLE
EXPRESIONES DE BOOLE: SUMAS DE PRODUCTOS
Definición: Expresión o función Booleana
Sean x
1
, x
2
, ..., x
n
B. Se denomina expresión booleana (o función booleana)
∊
de esas variables a cualquier expresión construida con ellas y las operaciones
booleanas +, * y ‘.
Definición: Literal
Un literal es una variable o una variable complementada, es decir ó x ó x’ (o
cualquier otra letra y, y’,z’,..)
Definición: Producto fundamental
Un producto fundamental es un producto de dos o más literales donde
ninguno tiene la misma variable
Ejemplo
Son productos fundamentales xy’z, x’y’, zx’t’
No son productos fundamentales x’x, y’, zx’yx

12. ALGEBRAS DE BOOLE
Proposición
Todo producto de Boole se puede reducir a 0 o a un producto fundamental
Definición: Inclusión
Un producto fundamental P
1
se dice incluído en otro P
2
, si todos los literales
que conforman P
1
son también literales de P
2
.
Proposición
Si un producto fundamental P
1
está incluído en otro P
2
entonces P
1
+ P
2
= P
1
.
Ejemplo
xy’ + xy’z’ = xy’ + (xy’) z’ = xy’

13. ALGEBRAS DE BOOLE
Definición: Suma de Productos o minterm
Una expresión de Boole E se dice que está en forma de suma de productos
(o también denominada minterm que viene de mínimo término) si E es la
suma de uno o varios productos fundamentales, donde ninguno de ellos está
contenido en otro.
Ejemplo
E
1
= xyz + xy’ + xy’z’ (no!)
E
2
= xyz + x’y’ + xy’z’ (Si!)
Definición: producto de sumas o maxterm
Una expresión de Boole E se dice que está en forma de producto de sumas
(o también denominada maxterm que viene de término máximo) si E es
producto de sumas donde en cada una de los multiplicandos están sumadas
todas las variables, complementadas o no..
Ejemplo
E
1
= (x+y+z)(x+y’+z’)(x’+y+z’) (si!)
E
2
= (x+y+z)(x+z+z’)(x’+y+z’)’ (no!)

14. ALGEBRAS DE BOOLE
Proposición
Toda expresión de Boole se puede poner en forma de suma de productos
Demostración
Usamos, por este orden, las siguientes leyes:
1º) Aplicamos las Leyes de Morgan y leyes de involución.
Así suprimimos los complementos de los paréntesis existentes y los dobles complementos que
aparezcan.
2º) Aplicamos la ley distributiva
Así eliminamos cuantos paréntesis nos queden, quedando la expresión en suma de productos
3º) Aplicamos las leyes conmutativa, idempotencia, identidad y complemento
Así transformamos cada producto en 0 o en un producto fundamental.
4º) Aplicamos la ley de absorción
Dejando la expresión en forma de suma de productos

15. ALGEBRAS DE BOOLE
Ejemplo
Transformar en suma de productos la expresión E = ((ab’)’ + c)((a + b’)c’ + (b’ + c)’) =...
Solución
Por la ley de Morgan ...= ((a’ + b’’) + c)((a + b’)c’ + b’’c’) = ...
Por el complemento ...= ((a’ + b) + c)((a + b’)c’ + bc’) = ...
Por la distributiva ...= (a’ + b + c)(ac’ + b’c’ + bc’) = ...
Por la distributiva ...= a’ac’ + a’b’c’ +a’bc’ + bac’ + bb’c’ + bbc’ + cac’ + cb’c’ + cbc’ = ...
Por la conmutativa ...= aa’c’ + a’b’c’ +a’bc’ + abc’ + bb’c’ + bbc’ + acc’ + b’cc’ + bcc’ = ...
Por el complemento ...= 0c’ + a’b’c’ +a’bc’ + abc’ + 0c’ + bbc’ + a0 + b’0 + b0 = ...
Por la identidad ...= 0 + a’b’c’ + a’bc’ + abc’ + 0 + bbc’ + 0 + 0 + 0 = ...
Por la idempotencia ...= a’b’c’ + a’bc’ + abc’ + bc’ = ...
Por la absorción ...= a’b’c’ + bc’

16. ALGEBRAS DE BOOLE
Definición: Forma completa o canónica de suma de productos
Una expresión de Boole E no nula se dice que está en forma completa (también le podemos llamar
canónica disyuntiva) de suma de productos cuando está en forma de suma de productos y en cada
producto se usan todas las variables que componen E

Ejemplo
En el ejemplo previo la expresión resultante E = a’b’c’ + bc’ no está en forma completa de suma de
productos pues el segundo sumando no contiene la variable c.

Teorema
Toda expresión de Boole E no nula se puede escribir como forma completa de suma de productos y
dicha expresión es única.

Ejemplo
La expresión anterior E = a’b’c’ + bc’ se consigue escribir en forma completa de suma de productos
con solo realizar el proceso siguiente
E = a’b’c’ + bc’ = ...
Por la identidad ...= a’b’c’ + bc’1 = ...
Por el complemento...= a’b’c’ + (a + a’)bc’ = ...
Por la distributiva...= a’b’c’ + abc’ + a’bc’
Resultando finalmente E = a’b’c’ + abc’ + a’bc’

17. ALGEBRAS DE BOOLE

18. ALGEBRAS DE BOOLE