Algebra Boleana

Algebra Booleana
Matemáticas Discretas

Algebra Booleana
 En 1954 George Boole creo
un sistema de lógica
matemática a lo que ahora
llamamos:

Algebra Booleana

Algebra Booleana
 Uninterruptor eléctrico puede
encenderse o apagarse.
“Verdadero” = “Encendido”
“Falso” = “Apagado”

1
0

Algebra Booleana
 Sea 𝐵 = 0,1 . Definamos la suma, producto y complemento para loselementos de 𝐵 como:
a) Suma:
𝟎+ 𝟎= 𝟎
𝟎+ 𝟏= 𝟏
𝟏+ 𝟎= 𝟏
𝟏+ 𝟏= 𝟏
b) Producto:
𝟎∙ 𝟎=
𝟏∙ 𝟎=
𝟎∙ 𝟏=
𝟏∙ 𝟏=

𝟎
𝟎
𝟎
𝟏

c) Complemento:
𝟎= 𝟏
𝟏= 𝟎

¿Deja Vu?

Algebra Booleana
 Una variable𝑥 es una 𝒗𝒂𝒓𝒊𝒂𝒃𝒍𝒆 𝒃𝒐𝒐𝒍𝒆𝒂𝒏𝒂 si
𝑥 solo toma valores de 𝐵. En consecuencia:
𝒙+ 𝒙= 𝒙
𝒙𝟐 = 𝒙

𝒙 ∙ 𝒙 = 𝒙𝒙 = 𝒙
 Si 𝑥, 𝑦 son variables booleanas entonces:
1) 𝟏 + 𝒚 = 𝟎 si y solo si 𝒙 = 𝒚 = 𝟎

2) 𝒙𝒚 = 𝟏si y solo si 𝒙 = 𝒚 = 𝟏

Algebra Booleana
 Ejemplo: Sea 𝑓: 𝐵3 → 𝐵, donde 𝑓(𝑥, 𝑦, 𝑧) = 𝑥𝑦 + 𝑧. Esta
función booleana queda determinada evaluando 𝑓 para cada
una de las ocho posibles asignacionesa las variables 𝑥, 𝑦, 𝑧:
𝒙

𝒚

𝒛

𝒙𝒚

𝒇 𝒙, 𝒚, 𝒛 = 𝒙𝒚 + 𝒛

0

0

0

0

0

0

0

1

0

1

0

1

0

0

0

0

1

1

0

1

1

0

0

0

0

10

1

0

1

1

1

0

1

1

1

1

1

1

1

Algebra Booleana
Ejercicio: Encuentre el valor de cada una de las siguientes
expresiones booleanas si los valores de lasvariables booleanas
𝑤. , 𝑥, 𝑦 y 𝑧 son 1, 1, 0 y 0, respectivamente:

a)
b)
c)
d)
e)

𝑥𝑦+ 𝑥 𝑦
𝑤𝑥 + 𝑦 + 𝑦𝑧
𝑤𝑥 + 𝑦𝑧 + 𝑤𝑦 + (𝑤 + 𝑦)(𝑥 + 𝑦)
𝑤+ 𝑥𝑦
𝑤𝑥 + 𝑥𝑦 + 𝑦𝑧

Leyes de Algebra Booleana
1

f=fx=x

2

𝑓+ 𝑔= 𝑓 𝑔
𝑓𝑔 = 𝑓 + 𝑔

𝑥+ 𝑦= 𝑥𝑦
𝑥𝑦 = 𝑥 + 𝑦

Leyes de DeMorgan

3

𝑓+ 𝑔= 𝑔+ 𝑓
𝑓𝑔 = 𝑔𝑓

𝑥+ 𝑦= 𝑦+ 𝑥
𝑥𝑦 = 𝑦𝑥

Leyes Conmutativas

4

𝑓 + 𝑔 + 𝑕 = (𝑓 + 𝑔) + 𝑕
𝑓 𝑔𝑕 = 𝑓𝑔 𝑕𝑥 + 𝑦 + 𝑧 = (𝑥 + 𝑦) + 𝑧
x 𝑦𝑧 = 𝑥𝑦 𝑧

Leyes Asociativas

5

𝑓 + 𝑔𝑕 = (𝑓 + 𝑔)(𝑓 + 𝑕)
𝑓 𝑔 + 𝑕 = 𝑓𝑔 + 𝑓𝑕

𝑥 + 𝑦𝑧 = (𝑥 + 𝑦)(𝑥 + 𝑧)
x 𝑦 + 𝑧 = 𝑥𝑦 + 𝑥𝑧

Leyes Distributivas

6

𝑓+ 𝑓=...