Lista 5. Matemáticas Discretas.

Nestor Colin Hernandez

27 de diciembre de 2022

Fecha de Entrega: miércoles 11 y/o jueves 12 de enero 2023 al inicio de la clase y con un máximo de 15 minutos,
por lo cual se recomienda que unan sus listas un dı́a antes y discutan sus ejercicios que no hayan podido resolver.
La tarea será entregada en los nuevos equipos que establezcan para este tercer parcial (4 y 6 personas) y la dinámica
de entrega será la misma: elegirán un patrón cı́clico para repartirse los ejercicios:

A1: 1,7 A2: 2,8 A3: 3,9 A4: 4,10 A5: 5,11 A6: 6,12

A1: 1,5,9 A2: 2,6,10 A3: 3,7,11 A4: 4,8,12

Sus soluciones serán en hojas de rehuso u hojas blancas. Traté de ordenar sus hojas para le entrega, por ejemplo
procure hacer un ejercicio por hoja y al final ordenan el trabajo de todos. Agregará una caratula con los integrantes
del equipo mencionando a un costado de su nombre los ejercicios que resolvió. En su caratula también agregará
una tabla como la siguiente:

Ejercicio 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 Final

Puntaje

Finalmente, recuerde que la calificación de la tarea depende de la persona con quien trabaje y como presenta su
solución, ası́ que es altamente recomendable que estén en contacto sobre los avances de la tarea o elijan un dı́a para
discutir los problemas que crean convenientes, no lo dejen al final y simplemente unan los problemas. Adicionalmente
y si el tiempo lo permite elegiré al azar a un compañero cuando les entregue la tarea y le preguntaré la idea de la
solución, dependiendo de la respuesta podrá restar puntos a su tarea, ası́ como también el no entregar su tarea con
las instrucciones descritas anteriormente resta puntos.

1. Sea U el conjunto de enteros positivos. Sea S la colección de subconjuntos X de U que satisfacen que ya sea X o
X c es finito. Demuestre que (S, ∅, U, ∪, ∩, c ) es un álgebra booleana.
2. Sea S = {1, 2, 3, 6}. Defina
6
x + y = mcm( x, y), x · y = mcd( x, y) x0 =
x
para x, y ∈ S. Demuestre que (S, +, ·, 0 , 1, 6) es un álgebra booleana.
3. Sea S = {1, 2, 4, 8}. Defina + y · como en el ejercicio anterior y defina x 0 = 8/x. Demuestre que (S, +, ·, 0 , 1, 8)
no es un álgebra booleana.
4. Escriba el dual de cada afirmación y pruebe las afirmaciones tanto del dual como la original de las siguientes
afirmaciones:

a. ( x + y)( x + 1) = x + xy + y.
b. Si x + y = x + z y x + y = x + z, entonces y = z.
c. x + x (y + 1) = x.

1
5. Encuentre la forma normal disyuntiva y conjuntiva de cada una de las siguientes funciones:

w x y z f(w,x,y,z) w x y z f(w,x,y,z)
1 1 1 1 1 1 1 1 1 0
1 1 1 0 0 1 1 1 0 0
1 1 0 1 1 1 1 0 1 1
1 1 0 0 0 1 1 0 0 1
1 0 1 1 0 1 0 1 1 1
1 0 1 0 0 1 0 1 0 1
1 0 0 1 0 1 0 0 1 0
1 0 0 0 1 1 0 0 0 1
0 1 1 1 1 0 1 1 1 0
0 1 1 0 0 0 1 1 0 1
0 1 0 1 0 0 1 0 1 1
0 1 0 0 0 0 1 0 0 1
0 0 1 1 1 0 0 1 1 0
0 0 1 0 0 0 0 1 0 1
0 0 0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1

6. Reduzca las tablas anteriores mediante el uso de diagramas de Karnaugh y dibuje el circuito combinatorio
correspondiente.

7. La documentación para el lenguaje de programación Java recomienda que, cuando se define un método equivale
a para un objeto éste debe de ser una relación de equivalencia. Es decir, si R está definida como sigue:

x R y ⇔ x.equivalea(y) para todos los objetos e la clase,

entonces R debe ser una relación de equivalencia. Suponga que al tratar de optimizar algunas de las matemáticas
de una aplicación gráfica, un programador crea un objeto denominado punto, que consta de dos coordenadas en
el plano. El programa define un método equivale a como sigue: Si p y q son puntos cualesquiera, entonces

p.equivalea(q) ⇔ la distancia entre p y q es menor o igual a ε

donde ε es un pequeño número positivo que depende de la resolución de la pantalla del equipo. ¿Es el método
equivale a definido por el programador una relación de equivalencia? Justifique su respuesta.
8. Sea X = {1, 2, 3, 4, 5}. Represente las siguientes relaciones en un grafo y determine si son relaciones de equi-
valencia; en caso de ser de equivalencia represente las clases de equivalencia en el mismo grafo y si es posible
también como conjunto.

a. {(1, 1), (2, 2), (3, 3), (4, 4)(5, 5), (1, 5), (5, 1), (3, 5), (5, 3), (1, 3), (3, 1)}.
b. {( x, y) | 4 divide a x − y}.
c. {( x, y) | 3 divide a x + y}.

d. {( x, y) | x divide a 2 − y}

9. Sea X el conjunto de todas las formas de enunciados con tres proposiciones atómicas p, q y r. Definamos la
relación R sobre X como sigue: Para una proposición P y Q en X

PRQ si y sólo si P≡Q

Pruebe que R es una relación de equivalencia y además proporcione el número de clases de equivalencias posibles
mencionando la caracterı́stica principal que comparten los elementos de cada clase de equivalencia.

2
10. Sea X = {1, 2, 3, 4, 5}, Y = {3, 4} y C = {1, 3}. Defina una relación R sobre P ( X ) como

AR B si A ∪ Y = B ∪ Y.

a. Pruebe que R es una relación de equivalencia.

b. Encuentre los elementos de la clase de equivalencia [C ].

c. ¿Cuántas clases de equivalencia hay? Liste un representante de cada clase de equivalencia.

11. Sea X = {1, 2, . . . , 6}. Defina una relación sobre X × X como ( a, b)R (c, d) si ad = bc.

a. Pruebe que R es una relación de equivalencia sobre X × X.

b. Represente X × X en el plano cartesiano junto con el origen (0, 0), luego de esto trace las posibles rectas que
parten del origen a cada uno de los puntos. Es cierto que los puntos que pertenecen a las misma recta se
encuentran relacionados bajo R.
c. Liste un representante de cada clase de equivalencia y describa la relación en términos familiares quizás le
ayude el inciso (b).

12. ¿Es posible hacer un camino alrededor de la ciudad cuyo mapa se muestra a continuación, comenzando y
terminando en el mismo punto y cruzando cada puente exactamente una vez? Si es ası́, ¿cómo puede hacerse?

13. Decida si los siguientes grafos tienen un circuito de Euler. Cuáles tienen un circuito de Hamilton. Si lo tienen,
muestre uno.

14. Cuáles de los siguientes grafos tiene un camino de Euler y un circuito de Hamilton.

3
15. Cuál de los siguientes grafos tienen un camino de Euler, un ciclo de Euler o ambos?

16. Encuentre la longitud de una ruta más corta de a a i. De a a z. Encuentre la ruta más corta de a a z.

17. Encuentre la longitud de la ruta más corta entre cada par de vértices en la gráfica ponderada desde el vértice a,
ası́ como también el camino con dicho valor.

18. Encuentre el orden en que los vértices se procesan usando los recorridos, preorden, enorden y postorden de los
siguientes árboles

EXTRA! Un árbol n-ario completo es un árbol con raı́z, donde cada vértice interno tiene n hijos. Si T es un árbol
n-ario completo con k vértices internos, ¿cuántos vértices tiene T?, ¿cuántos vértices terminales tiene T?