Tecnólogo en Informática
Sede Maldonado
Matemática Discreta y Lógica I. Primer semestre.
Práctico 5 - Álgebra de Boole
1) Calcula, en caso de que existan, los valores de la variable 𝑥 que satisfacen las siguientes ecuaciones:
a) 𝑥 ∙ 1 = 0
b) 𝑥+𝑥 =0
c) 𝑥∙1=𝑥
d) 𝑥 ∙ 𝑥̅ = 1
2) Calcula la tabla de valores de las siguientes funciones booleanas
a) 𝐹(𝑥, 𝑦, 𝑧) = 𝑥̅ 𝑦
b) 𝐹(𝑥, 𝑦, 𝑧) = 𝑥 + 𝑦𝑧
c) 𝐹(𝑥, 𝑦, 𝑧) = 𝑥𝑦̅ + (𝑥𝑦𝑧
̅̅̅̅̅)
d) 𝐹(𝑥, 𝑦, 𝑧) = 𝑥(𝑦𝑧 + 𝑦̅ 𝑧̅)
3) ¿Qué valores de las variables booleanas 𝑥 e 𝑦 satisfacen la igualdad 𝑥𝑦 = 𝑥 + 𝑦?
4) Demuestra que 𝑥𝑦̅ + 𝑦𝑧̅ + 𝑥̅ 𝑧 = 𝑥̅ 𝑦 + 𝑦̅𝑧 + 𝑥𝑧̅
5) Comprueba que se cumplen las propiedades asociativas.
6) Comprueba que se cumplen las propiedades de De Morgan.
7) Comprueba que se cumplen las propiedades de complemento.
8) Demuestra que se cumplen las siguientes relaciones:
a) 𝑥⨁𝑦 = (𝑥 + 𝑦)(𝑥𝑦
̅̅̅)
b) 𝑥⨁𝑦 = (𝑥𝑦̅) + (𝑥̅ 𝑦)
9) Demuestra la veracidad o falsedad de las siguientes relaciones:
a) 𝑥⨁(𝑦⨁𝑧) = (𝑥⨁𝑦)⨁𝑧
b) 𝑥 + (𝑦⨁𝑧) = (𝑥 + 𝑦)⨁(𝑥 + 𝑧)
c) 𝑥⨁(𝑦 + 𝑧) = (𝑥⨁𝑦) + (𝑥⨁𝑧)
10) Calcula los duales de las siguientes expresiones booleanas:
a) 𝑥 + 𝑦
b) 𝑥̅ 𝑦̅
c) 𝑥𝑦𝑧 + 𝑥̅ 𝑦̅𝑧̅
d) 𝑥𝑧̅ + 𝑥 ⋅ 0 + 𝑥̅ ⋅ 1
Prof. Rosana Alvarez Año 2017
Tecnólogo en Informática
Sede Maldonado
Matemática Discreta y Lógica I. Primer semestre.
PROPIEDADES DEL ALGEBRA DE BOOLE (Rosen-cap.10, adaptadas con material de fing)
Propiedad Nombre
𝑥̿ = 𝑥 Propiedad de involución
𝑥+𝑥 =𝑥 Propiedad de idempotencia
𝑥∙𝑥 =𝑥
𝑥+0=𝑥 Propiedad del elemento neutro
𝑥∙1=𝑥
𝑥+1=1 Propiedades de neutros cruzados o
𝑥∙0=0 de acotación
𝑥+𝑦 =𝑦+𝑥 Propiedades conmutativas
𝑥∙𝑦 =𝑦∙𝑥
𝑥 + (𝑦 + 𝑧) = (𝑥 + 𝑦) + 𝑧 Propiedades asociativas
𝑥(𝑦𝑧) = (𝑥𝑦)𝑧
𝑥 + 𝑦𝑧 = (𝑥 + 𝑦)(𝑥 + 𝑧) Propiedades distributivas
𝑥(𝑦 + 𝑧) = 𝑥𝑦 + 𝑥𝑧
(𝑥𝑦
̅̅̅) = 𝑥̅ + 𝑦̅ Propiedades de De Morgan
̅̅̅̅̅̅̅
(𝑥 + 𝑦) = 𝑥̅ 𝑦̅
𝑥 + 𝑥𝑦 = 𝑥 Propiedades de absorción
𝑥(𝑥 + 𝑦) = 𝑥
𝑥 + 𝑥̅ = 1 Propiedad de complemento.
𝑥𝑥̅ = 0 Propiedad de complemento
DUALIDAD
El dual de una expresión booleana se obtiene intercambiando entre si la suma y el producto booleanos, así
como los ceros y los unos. En la tabla de las propiedades anteriores, se observa dicha dualidad en las filas 2
a la 8.
Ejemplos: 𝑥(𝑦 + 0) es dual de 𝑥 + (𝑦. 1)
𝑥. 1 + (𝑦 + 𝑧) es dual de (𝑥 + 0). (𝑦. 𝑧)
Principio de dualidad: El dual de una función booleana F representada por una expresión booleana, es la
función representada por el dual de la expresión.
Prof. Rosana Alvarez Año 2017
Tecnólogo en Informática
Sede Maldonado
Matemática Discreta y Lógica I. Primer semestre.
Representación de Funciones Booleanas
Toda función booleana se puede representar mediante una suma booleana de productos booleanos de
variables y variables complementadas. Por lo tanto, toda función booleana se puede representar
utilizando los tres operadores booleanos: +, y .
Desarrollo de suma de productos o forma normal disyuntiva.
Toda función booleana se puede representar como suma de productos.
A partir de los valores, obtener la expresión booleana.
Ejemplo
x y z F G Para representar F, necesitamos una expresión que valga 1 cuando
1 1 1 0 0 𝑥 = 𝑧 = 1 e 𝑦 = 0 y que valga 0 en otro caso. Esta, se construye
1 1 0 0 1 mediante un producto booleano: 𝐹(𝑥, 𝑦, 𝑧) = 𝑥𝑦̅𝑧.
1 0 1 1 0
1 0 0 0 0 Para G: 𝐺(𝑥, 𝑦, 𝑧) = 𝑥𝑦𝑧̅ + 𝑥̅ 𝑦𝑧̅
0 1 1 0 0
0 1 0 0 1
0 0 1 0 0
0 0 0 0 0
Literal: es una variable booleana o una variable booleana complementada.
Minitérmino en las variables booleanas x1, …, xn es un producto booleano de n literales y vale 1 para
una sola combinación de sus variables.
Entonces dada una función booleana, se puede construir una suma booleana de minitérminos que
valga 1 cuando esta función booleana vale 1 y 0 cuando la función valga 0.
Ejercicios
11) Calcula el producto booleano de las variables 𝑥, 𝑦, 𝑧 o de sus complementos que valga 1 si y solo si:
a) 𝑥 = 𝑦 = 0, 𝑧 = 1
b) 𝑥 = 0, 𝑦 = 1, 𝑧 = 0
c) 𝑥 = 0, 𝑦 = 𝑧 = 1
d) 𝑥=𝑦=𝑧=0
12) Halla la forma normal disyuntiva de las funciones booleanas siguientes
a) 𝐹(𝑥, 𝑦) = 𝑥̅ + 𝑦
b) 𝐹(𝑥, 𝑦) = 𝑥𝑦̅
c) 𝐹(𝑥, 𝑦) = 𝑦̅
d) 𝐹(𝑥, 𝑦, 𝑧) = 𝑥 + 𝑦 + 𝑧
Prof. Rosana Alvarez Año 2017
Tecnólogo en Informática
Sede Maldonado
Matemática Discreta y Lógica I. Primer semestre.
e) 𝐹(𝑥, 𝑦, 𝑧) = (𝑥 + 𝑧)𝑦
f) 𝐹(𝑥, 𝑦, 𝑧) = 𝑥
g) 𝐹(𝑥, 𝑦, 𝑧) = 𝑥𝑦̅
Otra forma de hallar una expresión booleana que representa una función booleana es la forma normal
conjuntiva que consiste en construir un producto cuyos factores son sumas de literales.
13) Halla una suma booleana que a 𝑥 o 𝑥̅ , 𝑦 o 𝑦̅, a 𝑧 o 𝑧̅ y que valga 0 si y solo si:
a) 𝑥 = 𝑦 = 1, 𝑧 = 0
b) 𝑥 = 𝑦 = 𝑧 = 0
c) 𝑥 = 𝑧 = 0, 𝑦 = 1
14) Calcula la forma normal conjuntiva del ejercicio 2.
Completitud funcional
Como toda función booleana se puede representar utilizando el conjunto de operadores {+, ,
}
Si usamos las leyes de De Morgan, podemos eliminar todas las sumas booleanas: 𝑥 + 𝑦 = ̅̅̅̅
𝑥̅ 𝑦̅
Y para eliminar los productos, usamos 𝑥𝑦 = ̅̅̅̅̅̅̅̅
𝑥̅ + 𝑦̅
Entonces {+,
} es funcionalmente completo, { ,
} también lo es.
15) Expresa las siguientes funciones booleanas utilizando los operadores i) ,
ii) +,
a) 𝐹(𝑥, 𝑦, 𝑧) = 𝑥 + 𝑦̅(𝑥̅ + 𝑧)
̅̅̅̅̅̅̅
b) 𝐹(𝑥, 𝑦, 𝑧) = (𝑥 + 𝑦̅)
c) 𝐹(𝑥, 𝑦, 𝑧) = 𝑥̅ (𝑥 + 𝑦̅ + 𝑧)
Podemos considerar dos nuevos operadores funcionalmente completos: NAND | y NOR
x y NAND | NOR
1 1 0 0
1 0 1 0
0 1 1 0
0 0 1 1
Prof. Rosana Alvarez Año 2017
