Algebra Boolea

ÁLGEBRA DE BOOLE
DEFINICION Sea A un conjunto en el que se definen dos operaciones binarias: Suma ∨ : A × A → A y Producto ∧ : A × A → A. Se dice que (A, ∨, ∧) es un Álgebra de Boole si las operaciones verifican las siguientes propiedades: 1) Idempotente x∨x=x x∧x=x x ∨ y = y ∨ x, x∧y=y∧x 2) Conmutativa 3) Asociativa x ∨ (y ∨ z) = (x ∨ y) ∨ z, x ∧ (y ∧ z) = (x ∧ y) ∧ z 4) Absorción x ∨ (x ∧ y) =x, x ∧ (x ∨ y) = x 5) Existe elemento neutro para la suma 0, llamado el elemento mínimo y existe elemento neutro para el producto 1, llamado el elemento máximo: x ∨ 0 = x, x∧1=x 6) ∀ x ∈ A, ∃ un único x´ ∈ A, llamado el complementario de x tal que x ∨ x´ = 1, x ∧ x´ = 0 x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z) x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z) 7) Distributiva TEOREMA Si el conjunto (A, ∨, ∧) es un Álgebrade Boole, entonces se verifican las siguientes propiedades: 1) Absorción del neutro 1 ∨ x = 1, 0∧x=0 2) Involutiva (x´)´ = x (el complementario de cada elemento es único) 3) Leyes de De Morgan (x ∨ y)´ = x´ ∧ y´ (x ∧ y)´ = x´ ∨ y´ DEM. 1) 1 ∨ x = ( x ∨ x´ ) ∨ x = ( x ∨ x ) ∨ x´ = x ∨ x´ = 1 0 ∧ x = 0 ∧ x = ( x ∧ x´ ) ∧ x = ( x ∧ x ) ∧ x´ = x ∧ x´ = 0 2) Si x ∨ x´ = 1 y x´ ∨ x´´ = 1, si x ∧ x´ = 0 yx´ ∧ x´´ = 0, entonces x = x´´ 3) (x ∨ y) ∨ (x´ ∧ y´) = [x ∨ y ∨ x´] ∧ [x ∨ y ∨ y´] = (1 ∨ y) ∧ (x ∨ 1) = 1 ∧ 1 = 1 (x ∨ y) ∧ (x´ ∧ y´) = [x ∧ y´ ∧ x´] ∨ [y ∧ x´ ∧ y´] = (0 ∧ y´ ) ∨ (0 ∧ x´ ) = 0 ∨ 0 = 0 (x ∧ y) ∨ (x´ ∨ y´) = [x ∨ y´ ∨ x´] ∧ [x´ ∨ y ∨ y´] = (1 ∨ y´ ) ∧ (x´ ∨ 1) = 1 ∧ 1 = 1 (x ∧ y) ∧ (x´ ∨ y´) = [x ∧ y ∧ x´] ∨ [y ∧ x ∧ y´] = (0 ∧ y) ∨ (0 ∧ x) = 0 ∨ 0 = 0 EJEMPLOS 1. Si S es unconjunto, entonces (℘(S), ∪, ∩) es un Álgebra de Boole. 2. Sea Dn = {z ∈ Ν / z divide a n} con las siguientes operaciones: x ∨ y = mcm { x, y }, x ∧ y = mcd { x, y }, que verifican que n es el elemento máximo y 1 es el elemento mínimo. (Dn, ∨, ∧) es un Álgebra de Boole si y sólo si n = p1 p2 ... pk con pi números primos distintos dos a dos y distintos de 1. 3. El conjunto de Boole Β = {0, 1} con lasoperaciones definidas por las tablas siguientes es un Álgebra de Boole: ∨ 0 1 0 0 1 1 1 1 ∧ 0 1 0 0 0 1 0 1

Dpto. Matemática Aplicada. Facultad de Informática. UPM.

Matemática Discreta

Victoria Zarzosa Rodríguez

4. Se considera el conjunto de Boole Β = {0, 1}. En el conjunto Βn = {0, 1}n = {(x1, x2, ..., xn) / xi ∈ Β} 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)

• •
• •

se verifican las propiedades Idempotente, Conmutativa, Asociativa y Absorción existe elemento neutro para la suma (0, ..., 0) = 0, llamado mínimo y existe elemento neutro para el producto (1, ..., 1) = 1, llamado máximo existe el complementario del elemento: (x1, x2,..., xn)´ = (x1´, x2´, ..., xn´) se verifica la propiedad Distributiva Entonces ( Βn, ∨, ∧ ) es un Álgebra de Boole.

FUNCIONES BOOLEANAS DEFINICIÓN Una función booleana de n variables es una aplicación f : Βn → Β tal que 0 f (x1, x2, ..., xn) =  ∀ (x1, x2, ..., xn) ∈ Βn. 1 “Cualquier posible distribución de 2n ceros y unos puede ser el conjunto de valores de una función booleana” TABLAS DEVERDAD Una representación de una función booleana puede venir dada por una tabla de la forma x1 0 0 ...... 0 1 ...... 1 x2 0 0 ...... 1 0 ...... 1 ...... ...... ...... ...... ...... ...... ...... ...... xn 0 1 ...... 0 0 ...... 1 f (x1, x2, ..., xn) f (0, 0, ..., 0) f (0, 0, ..., 1) ...... f (0, 1, ..., 0) f (1, 0, ..., 0) ...... f (1, 1, ..., 1)

EXPRESIONES BOOLEANAS DEFINICIÓN Sea { x1, x2,..., xn } un conjunto de n variables. Se define una expresión de Boole o polinomio de Boole en las variables { x1, x2, ..., xn } de forma recursiva como sigue: 1. x1, x2, ..., xn son expresiones de Boole. 2. 0, 1 son expresiones de Boole. 3. Si E1 (x1, x2, ..., xn), E2 (x1, x2, ..., xn) son expresiones de Boole, entonces E1 ∨ E2, E1 ∧ E2, E1´ son expresiones de Boole. 4. No existen expresiones de...