Ejercicios Finales M Discreta - Apia Guzman 1st

Vista previa del material en texto

Matematica Discreta
Finales resueltos
Año 2020/2021
Recopilacion de finales dictados durante la cuarentena de
COVID - 19
Preparense para el COVID-20…
(Lean la introduccion)
Por Apia Guzman 1st
1
Introduccion
Buenos dias, señor/señora lector/lectora. Bah, buenas noches, porque para mi son las 6 de la mañana en este 
momento. 
Me gustaria aclarar algunas observaciones previas a la lectura de este texto. Comprendo que la posibilidad de que 
te saltes esta introduccion y vayas directo a los finales resueltos es alta, pero si estas leyendo esto, solo te pido que
me des unos minutos.
El objetivo de este texto no es el ser una mera recopilacion de enunciados de finales con sus respectivas respuestas
de verdadero o falso, sino el de brindar una explicacion de por que la veracidad o falsedad de las diversas 
proposiciones. A lo largo de la lectura, notaran que no solo se justificaran las opciones elegidas como verdaderas 
sino tambien las falsas. Se tratara de abarcar la mayor cantidad de conceptos posibles para no dejar cabos sueltos a
la hora de justificar una respuesta, de manera que la lectura pueda ser comoda para tanto un estudiante que recien 
comienza a estudiar para un examen, como para aquel que ya se encuentra avanzado en sus estudios. Notaran 
ademas que en algunas ocasiones se brindaran una explicacion de conceptos o propiedades que se utilizaran para 
justificar la veracidad o falsedad de una justificacion. ESTE TEXTO NO ES RESUMEN TEORICO.
Por otra parte, mi objetivo al presentar este texto no es el que se utilice como un libro de literatura, si no como un 
material de consulta. Mi interes esta en que el lector se atreva a resolver los ejercicios por si mismo, siendo critico 
a la hora de analizar problemas, recurriendo a material teorico si lo precisace, y tomandose el tiempo necesario 
para resolver un ejercicio. Me interesa que este texto se utilice como ultimo recurso: cuando, luego de haberse 
quemado la cabeza de tanto pensar, de haber leido y releido la teoria, y de haber investigado sobre los temas por 
cuenta propia, el estudiante reconozca que no posee los conocimientos para justificar una proposicion. A raiz de 
esto, me gustaria aclarar que, al igual que ustedes, yo tambien soy estudiante y estoy preparando la materia para 
rendir un examen. Esto significa que cabe la posibilidad de que existan errores en algunos desarrollos. Intentare 
que no, pero soy humano, y algo puede escaparse de mis manos.
Me encuentro preparando la materia hace varias semanas, y el resultado de ello es, mismamente, el presente texto.
Bajo la experiencia de haber estudiado tanto, me gustaria brindar algunas recomendaciones a la hora de estudiar y 
practicar ejercicios:
• Tomense un buen tiempo para desarrollar justificaciones. Los problemas no se resuelven en 5 minutos, ni 
10 ni 15. Si bien existen trucos que permiten resolver los ejercicios en menos tiempo del mencionado, 
estos solo se adquieren con la abundante practica, y empapandose de teoria, investigando hasta los 
detalles mas pequeños. No se frustren si un ejercicio no les sale en 10 minutos, es completamente normal,
y solo la practica hara que desarrollen herramientas para ahorrarse tiempo.
• Al estudiar, desarrollen justificaciones de sus elecciones lo mas completas posibles. Justifiquen tanto lo 
verdadero como lo falso. Desarrollen mediante conceptos teoricos hasta lo mas pequeño. No asuman nada
como obvio, pues es esto lo que los traiciona al final. Cuestionen sus propios conocimiento. ¿Pero por 
que esto es verdadero? Hagan un buen desarrollo y luego intenten derrumbarlo. Como si fuese una torre, 
sus desarrollos deben ser solidos, sin agujeros, e inquebrantables. Duden de hasta lo que yo haya 
desarrollado.
• La materia no es dificil. Tiene su complejidad como toda matematica y, como toda matematica, requiere 
que se le dedique un buen tiempo. No se asusten si se topan con cosas que no entienden. Todos partimos 
desde el inicio en algun momento. Sean curiosos. Investiguen lo que no entiendan. Sientansen 
hambrientos de conocimiento. Hablen con otros compañeros de estudio y debatan e investiguen juntos. 
Esto hara mas amena la materia, y les permitira aprender aun mas rapido. El conocimiento esta ahi afuera.
Vayan a por el.
2
• A la hora de sentarse a resolver un ejercicio, confien en sus conocimientos. Lean tranquilamente el 
enunciado y la opciones brindadas. Analicen en que contexto se encuentran, que elementos participan del 
problema, y entonces sabran sobre que bases apoyarse para encontrar la solucion a lo planteado.
• De haberles ido mal, tengan presente que todo estudio siempre aporta algo nuevo. Siempre suma, aunque 
no haya sido suficiente para aprobar un examen. No bajen los brazos. Analicen que cosas de su examen 
fueron correctas y que cosas incorrectas, e investiguen acerca de ellos. Sera importante enfocarse en 
aquellos temas que se encuentran flojos, pero tambien sera importante no ignorar lo que se nos dio bien. 
Todo puede mejorarse. Siempre se puede aprender algo nuevo. De la investigacion de teoria y con la 
ejercitacion practica desarrollaran nuevas tecnicas que les permitiran afrontar nuevamente los problemas 
de manera mas sencilla. Un desaprobado solo nos demuestra que podemos ser mejores, y que podemos 
aprender aun mas.
Por ultimo, de encontrarse algun error en algun ejercicio, sientanse libres de corregirlo. Solo les pido que, de 
hacerlo, no borren el desarrollo erroneo, y desarrollen su propia explicacion a continuacion. Esto permitira a los 
demas lectores leer el camino errado que se ha tomado, entender por que esta mal, y luego leer cual es el 
verdadero camino a la respuesta correcta. Si se desease añadir otros ejercicios con sus respectivas justificaciones, 
intenten ser lo mas claros posibles, explicando hasta lo mas pequeño, sea verdadero o falso. Esto es para que 
estudiantes con cualquier nivel de conocimiento puedan entender y aprender de lo que desarrollen.
Les deseo muchos exitos. Espero que logren lo que se propongan.
Apia Guzman 1st
3
Resolucion
a) Falso. Recordemos que d+(G) refiere a los grados entrantes del grafo (es decir, las cantidad de aristas que
terminan en un vertice v).
Demostraremos la falsedad del enunciado mediante un contraejemplo.
Como se puede notar en el grafo de la derecha:
• deg+(1) = 1
• deg+(2) = 0
• deg+(3) = 2
• deg+(4) = 3
Por definicion, la excentricidad de un vertice u es la maxima
distancia entre u y todos los vertices del grafo. Partiendo de este
concepto, el radio de un grafo no es otra cosa que la
excentricidad minima del grafo mismo. Podemos notar que el
radio r(G) = 1, dado que la excentricidad del vertice 2 es,
justamente, 1.
Consejo: Graficar el grafo. Es un torneo de cuatro vertices; por ende solo dibujarian cuatro vertices y seis 
aristas. Visualizar el enunciado es la clave para entender el problema. Recuerden que un torneo es un grafo 
completo cuyas aristas tienen una orientacion.
b) Falso. En este caso, se nos da d-(G) que refiere a los grados salientes del grafo (lo contrario al concepto 
de grados entrantes).
4
Observemos d-(G)
Apa... ¿Acaso podemos reciclar el grafo del inciso anterior?
No caben dudas, ¿no?
¿En serio no lo ven?
¿De verdad?
Bueno, expliquemos por que podemos reciclar el grafo anterior. La explicacion es muy sencilla:
Precisamos un grafo con la siguiente sucesion de grados: d-(G) = (0, 1, 2, 3).
Podriamos, y vamos a, asignar estos grados a los vertices del grafo:
• deg-(1) = 2
• deg-(2) = 3
• deg-(3) = 1
• deg-(4) = 0
Observen el grafo, y veran que precisamente esta asignacion es valida.
Se nos afirma que el grafo G es fuertemente conexo. Por definicion, un grafo fuertemente conexo es un 
grafo que para todo vertice u del mismo, existe un camino (path) que lo conecte con todos los vertices 
restantes. De esta manera, podemos notar que no existe camino que conecte al vertice a cualquier vertice con
el vertice 2; en conclusion, no es un grafo fuertemente conexo.
Consejo: Tan soloobservando d-(G) = (0, 1, 2, 3) se nota que uno de los vertices (no importa cual realmente) 
posee grado saliente dev-(u) = 3, lo cual quiere decir que tres aristas salen de el. Dado a que G es un torneo, 
el maximo grado que puede tener cada vertice es 3, lo cual nos permite concluir que, si tres aristas salen del 
vertice u, no hay lugar para que una arista incida en ese vertice; entonces no hay forma de que exista un 
camino que conecte a cualquier vertice de G con u.
d) Falso. Analicemos el enunciado: grafo simple G, 9 vertices, 28 aristas, preguntan si es conexo.
Pensemos el caso contrario. ¿Cuando G no es conexo? Cuando al menos un vertice de G no esta conectado a 
ninguno de los vertices restantes (cuidado, ahora trabajamos con grafos no orientados).
Podriamos imaginar el caso donde aislamos uno de los vertices y utilizamos los 8 vertices restantes para 
unirlos con las 28 aristas que se nos permite. Pero, si hacemos esto, podriamos llegar al caso donde estos 8 
vertices se unan todos con todos entre si. Traducido a lenguaje matematico, podriamos llegar al caso donde G
posea como subgrafo a K8 (el grafo completo de 8 vertices). Si ocurre esto, y quisiesemos añadir una arista 
mas, no quedaria otra opcion que unirla con el noveno vertice que aislamos inicialmente, logrando que 
inevitablemente G sea un grafo conexo. Pero no es lo que queremos, por ahora.
Pensemos en K8: ¿cuantas aristas posee? La mejor forma de responder a esto es utilizando la formula para 
hallar cuantas aristas posee un grafo completo de n vertices Kn (que nombre mas oportuno jaja): n(n-1)/2. 
Utilizando la formula llegamos a que K8 posee 28 aristas. Alto. ¿28 no era la cantidad de aristas de nuestro 
grafo G?
Efectivamente, G posee 28 aristas. Y dado a que G posee un subgrafo de 8 vertices que en el caso mas 
completo sera un K8, podemos acomodar las 28 aristas sin ningun problema en los 8 vertices que aislamos, 
5
formando un K8, pero mucho mas importante, logrando dejar el noveno vertice aislado sin ninguna arista que
lo conecte con otro.
A continuacion procedemos a graficar G:
e) Verdadero. Para la resolucion de este enunciado vamos a realizar un procedimiento similar al explicado 
en el enunciado anterior. Grafo simple G, n = 7, m = 16, preguntan si es conexo.
¿Cuando no es conexo? Si aislamos un septimo vertice y dejamos 6 de lado¿Posee G mas aristas que un K6?
K6 posee exactamente 15 vertices. En este caso, G supera en cantidad de aristas a K6. En consecuencia, habra
una arista que inevitablemente se conectara al septimo vertice, otorgando conexividad al grafo.
Consejo: Notese como las deducciones realizadas en los incisos d y e no precisaron realmente la graficacion 
de algun grafo. Habra casos donde los grafos sean tan inmensos que graficarlos no seria un buen camino a 
tomar. Es importante desarrollar la habilidad de analizar cada detalle de los enunciados, ya que estos estan 
hechos para que podamos resolverlos en pocos minutos (la anterior proposicion solo es valida para estos 
examenes de carácter multiple choice).
f) Falso. ¿Otra vez torneos?
Podemos demostrar la falsedad de dos maneras: la primera y la segunda jaja no no me recursen. Vamos a 
demostrarlo de dos maneras diferentes.
I) Partamos de que un torneo es un digraph. Entonces, para que un digraph sea euleriano, para todo 
vertice v de G: deg+(v) = deg-(v). Si d+(G) = (1, 1, 2, 2), y este es un torneo, entonces Si d-(G) = (1, 1, 2, 2), 
debido a que cada vertice tiene 3 aristas, y si m (con m < 3) de esas aristas son entrantes, entonces 3 – m 
seran salientes. Si, por ejemplo, deg+(v) = m = 2,
entonces deg-(v) = 3 – m = 3 – 2 = 1. Esto no cumple
la proposicion inicial. Entonces G no es euleriano.
II) ¡Grafiquemos! 
¿Existe un camino que incluya todas las aristas y acabe
en el mismo vertice del cual se inicio?
6
Si lo encuentran, les regalo un alfajor Capitan del Espacio.
Spoiler: no les regalo nada.
g) Falso. Dado el analisis realizado en el inciso f, ¿cree usted que exista un grafo con dichas suceciones de 
grados?
 Si
 No
Si usted escogio No, enhorabuena, puede retirarse; vaya al comedor y pidase un café, se lo merece. Si, en 
cambio, escogio Si, quedese sentadito y lea la siguiente explicacion.
Dado G un torneo, y dada d+(G) = (1, 1, 2, 2), como se menciono anteriormente, cada vertice tiene deg(v) 
= 3, por definicion de torneo. Los vertices de G poseen deg+(v) = 1 o deg+(v) = 2.
• Si deg+(v) = 1, entonces deg-(v) = 2.
• Si deg+(v) = 2, entonces deg-(v) = 1.
Esto no da lugar a que un vertice posea deg-(v) = 0 o deg-(v) = 3. Por ende, d-(G) = (0, 1, 2, 3) no es una 
opcion posible.
7
Resolucion
a) Falso. Si asumimos que el enunciado es correcto, entonces tenemos tres formas de corroborarlo:
1. ∑
k=1
n
λ (k )=0
2. ∑
k=1
n
λ (k )2=2m
8
3. ∑
k=1
n
λ (k )3=6τ
Aclaracion: λ(k) significa λk. Τ es la cantidad de triangulos de grafo.
El espectro de G es σ(G) = (-2, -2, 0, 2, 2). Entonces:
1. -2 -2 + 0 +2 + 2 = 0. Se cumple
2. 4 + 4 + 0 + 4 + 4 = 16 != 2*5. No se cumple.
No es necesario probar mas nada. El espectro no coincide con el grafo.
b) Falso. Esto se deduce rapido. Si tenemos un grafo simple G de n = 5 y d(G) = (2, 2, 3, 3, 4), entonces 
(deduciendo de la sucesion grafica) se deduce que hay un vertice u en el cual inciden 4 aristas. Esto quiere decir 
que este vertice esta conectado con los cuatro vertices restantes por una sola arista, y entonces, su excentricidad 
e(u) = 1. Esto choca con la proposicion de que r(G) = 2, dado que e(u) < r(G), y entonces r(G) debe ser 1, 
arruinando el enunciado por completo.
c) Falso. Para probar este enunciado, utilizaremos la siguiente propiedad:
• Sea G conexo: G es euleriano sii para todo vertice u: d(u) es par.
En base a A(G), grafiquemos G:
En el grafo de la izquierda se etiquetaron las aristas, para formar el grafo arista de G ( L(G) ) a la derecha.
d(L(G)) = (2, 2, 3, 3, 4). Dado que algunos grados son impares, esto no cumple con la propiedad enunciada 
anteriormente.
d) Falso. La matriz de adyacencia de este grafo es exactamente
la misma que la del inciso c, y por ende el grafo.
Procedamos a graficar, entonces, su complemento G’:
9
Dado que no existe un ciclo que incluya a todos los vertices, G’ no es hamiltoniano, y por ende el enunciado es 
falso.
e) Falso. Procederemos de la misma manera que en inciso a.
1. -2 -1 + 0 + 1 + 2 = 0. Se cumple.
2. 4 + 1 + 0 + 1 + 4 = 10. Se cumple.
3. - 8 – 1 + 0 + 1 +8 = 0 != 1. No se
cumple.
g) Verdadero. Nuevamente, la mejor forma de ver esto es graficando. Si d(G) = (0, 2, 2, 3, 3), entonces d(G’) = 
(1, 1, 2, 2, 4). Mmmh, ¿donde vi esta sucesion grafica yo? ↑↑↑↑↑↑↑↑↑↑↑
10
Resolucion
Consejazo: R1 y R2 son relaciones sobre un conjunto A. Imaginenlas como matrices de relacion.
Ley de simetria: Si aRb, entonces bRa. En una matriz, si aij = aji.
Ley de antisimetria: Si aRb y bRa, entonces a = b. En una matriz, si aij = 1, entonces aji = 0.
a) Falso. Lo demostraremos mediante un contraejemplo:
Sea A(R1) = 
y sea B(R2) =
R1 es simetrica y R1 C R2, pero R2 no es simetrica.
11
c) Falso.
Sea A(R1) = 
y sea B(R2) =
R1 y R2 son antisimetricas, pero la suma de ambas es simetrica:
d) Falso.
Sea A(R1) = 
y sea B(R2) =
R2 es simetrica y R1 C R2, pero R1 no es simetrica.
e) Verdadero.
12
Si R2 es antisimetrica, entonces, si a esta relacionada con b, b no esta relacionada con a, a no ser 
que a = b. Esto quiere decir que las relaciones que no se encuentren presenten en R1 pero si en R2 
no supondran un cambio en la antisimetria. Visto desde el punto de vista de las matrices, en R2 aij = 
1 y aji = 0, o aij = 0 y aji = 0. R1, al no poseer algunas de las relaciones de R2, lo que en R2 es aij = 
1 y aji = 0, en R1 sera aij = 0 y aji = 0, manteniendo la asimetria.
Ejemplo:
Sea A(R1) =
y sea B(R2) =
R2 es antisimetrica y R1 C R2. Noten que b1,3 = 1, y, removiendolo en R1, a1,3 = 0, y esto no afecta 
su antisimetria.
f) Falso. En el inciso c, R1 y R2 son relaciones de equivalencia,pero la suma de ambas anula la 
antisimetria, por lo que R1 + R2 no es de equivalencia.
13
Resolucion
Nos presentan dos conjuntos:
• B1 = {1, 2, 3, 6}
14
• B2 = {a, b, c, d}
Ademas se nos presenta una funcion f: B1 → B2, dada por la siguiente tabla:
B1 f(B2)
1 c
2 a
3 b
6 d
Dado que se establece una funcion biyectiva de B1 a B2, afirmamos que B2 es un isomorfismo de B1. Entonces 
podemos establecer algunas equivalencias:
• Atomos de B2: {a, b}
• Neutros de B2: {c, d}
a) Falso. Por definicion, una de las invariantes de los isomorfismos son los atomos del algebra. Si 2 y 3 son los 
atomos de B1, entonces los atomos de B2 seran f(2) = a y f(3) = b.
b) Verdadero. Procedamos a resolver la ecuacion:
= ab + cd’ 
= 2*3 + 1*6’ (Isomorfismo)
= 1 + 1*1 (Ax. Complemento / Complemento)
= 1 (P. Idempotencia)
= c (Isomorfismo)
d) Falso. Procedamos a resolver la ecuacion:
= (ad + bc)a
= (2*6 + 1*3)*2 (Isomorfismo)
= (2 + 1)*2 (Ax. Neutro / P. Acotacion)
= 2*2 (Ax. Neutro)
= 2 (P. Idempotencia)
= a (Isomofirmo)
e) Falso. 
a’ = f’(2) = f(2’) = f(3) = b
Consejo: recuerden que f’(a) = f(a’).
15
f) Falso.
= c’ + d
= 1’ + 6 (Isomorfismo)
= 6 + 6 (Complemento)
= 6 (P. Idempotencia)
= d (Isomorfismo)
g) Falso.
= (a’ + b’)(c’ + d)
= (2’ + 3’)(1’ + 6) (Isomorfismo)
= (3 + 2)(6 + 6) (Complemento)
= 6*6 (Ax. Complemento / P. Idempotencia)
= 6 (Ax. Neutro)
= d
16
Resolucion
Si bien en este ejercicio no se encuentran todas las soluciones del multiple choice, no sera necesario, pues vamos a
resolver el ejercicio de manera analitica, y no por descarte de falsos.
17
Si bien una vez dominado el procedimiento no es necesario, para facilitar la explicacion, partamos dibujando el 
grafo:
El enunciado nos presenta la tabla de precios de una
aerolinea entre 5 ciudades: A, B, C, D y E. En base al
surtido de precios, nos piden que indiquemos cual tabla
de las presentadas constituye la tabla de vuelos
combinados mas baratos (aunque no esten todos los
items, creanme, por favor).
Comencemos planteando un caso particular: Siendo el
costo del vuelo directo desde A hacia B (lo notaremos
(A, B) ) es igual a 50, ¿hay alguna combinacion de
vuelos que logre reducir ese costo? Pues bien, si la hay:
(A, E) = 10; (E, B) = 25
Entonces el costo de (A, E, B) sera 10 + 25 = 35. Esto
quiere decir que el vuelo combinado mas barato (A, B)
vale 35.
La manera ideal de realizar esta busqueda es observando qué vuelos (A, X) (siendo X un vuelo combinado que no 
hace parada en B) poseen un precio menor a (A, B). Una vez encontrados los X / (A, X) < (A, B), habra que 
observar los precios de los vuelos (X, B) y encontrar cual de las combinaciones resultantes es la mas barata. En 
sintesis:
min((A, X) + (X, B)) / (A, X) + (X, B) < (A, B)
Si repetimos este proceso con todos los vuelos que partan de A,
llegaremos a la siguiente tabla:
Evaluemos los vuelos que parten de B. ¿Existe un vuelo combinado
(B, X, C) tal que su precio sea menor al de (B, C)? Para hallarlo,
tendremos que revisar nuevamente todos aquellos vuelos (B, X) que
sean mas baratos que (B, C) (¡incluso los que modificamos
previamente cuando buscamos los vuelos mas baratos que parten de
A!).
Repitiendo este proceso, llegaremos a la siguiente tabla:
Y, al finalizar el recorrido por todos los vuelos, la tabla final de vuelos combinados mas baratos sera la siguiente:
18
Recomiendo fuertemente una vez terminada la tabla, si tienen tiempo, que repasen todas las combinaciones para 
ver que no se les haya escapado ningún vuelo mas barato. Noten que graficar el grafo realmente no es relevante 
para resolucion, pero si sirve para visualizar la tabla.
19
Resolucion
Recordatorio: x | y <=> y mod x = 0 (O sea, el resto de y / x sea igual a 0).
Comencemos visualizando quien es D30. Siendo D30 el conjunto de divisores positivos de 30, D30 = (1, 2, 3, 5, 6, 
10, 15, 30) (Les dejo de tarea chequear que esto sea correcto). Ademas, nos definen las operaciones de suma y 
multiplicacion, y el orden parcial (estos fueron los ingredientes elegidos para crear un conjunto parcialmente 
ordenado).
¿Por que no graficamos el diagrama de Hasse?
¿Y quienes son los conjuntos A1, A2 y A3? Vamos a
averiguar eso:
A1)
x <= 6*15
x <= mcd(6, 15)
20
x <= 3
Entonces A1 es un subconjunto de D30 que contiene a todo x / x <= 3, es decir, tal que x | 3. Entonces concluimos 
que:
A1 = (1, 3)
A2)
x + 3 <= 6
mcm(3, x) <= 6
Notemos que el resultado de mcm(3, x) sera un conjunto donde evaluemos todos los elementos pertenecientes a 
D30. Hagamos una pequeña tablita para ello
x mcm(3, x)
1 3
2 6
3 3
5 15
6 6
10 30
15 15
30 30
Siendo el conjunto B = mcm(3, x) = (3, 6, 15, 30), ¿Para que elementos b de dicho conjunto es verdadera la 
proposicion mcm(3, x) <= 6? La respuesta es: solo para 3, 6.
Entonces A2 = (3, 6)
A3)… NO, MENTIRA.
(3, 6) son los elementos del conjunto B que responden a b <= 6. Pero nosotros queremos encontrar elementos de 
A2, ¿no?
Entonces, reformulando el conjunto por su ley de membresia:
A2 = {x perteneciente a D30 / mcm(3, x) C (3, 6)}
Volviendo a revisar la tablita, podemos concluir que A2 = (1, 2, 3, 6).
A3)
6 <= x
Entonces, ¿que buscamos? (x / 6 mod x = 0)
Una cuenta muy sencilla. A3 = (6, 30).
Ahora que ya tenemos todos los conjuntos, hay uno de los incisos que podriamos, y vamos a resolver.
21
e) Falso. Observando el diagrama de Hasse se puede concluir que el maximo de A2
existe, y es 30.
¡Excelente! Ya descartamos una de las opciones. Y el resto de las opciones involucran
a la ecuacion dada. Asi que, trabajemos la ecuacion. Nos piden:
• Cardinal del conjunto solucion X.
• Solucion minimal.
Muy facil, ¿no?
¿No? Bueno.
Trabajemos un poco la ecuacion para extraer algunos datos.
Llamemos B a A1 y C a A2 + A3
C = (1, 2, 3, 6, 30)
Entonces A1 + X = A2 + A3 se convierte en B + X = C. Trabajemos con esta nueva expresion, mucho mas comoda 
que la anterior:
B + X = C
(B + X)C’ + (B + X)’C = ∅ (Usamos la igualdad X = Y <=> XY’ + X’Y = )∅
BC’ + XC’ + B’CX’ = ∅ (P. Distributiva / P. De Morgan)
De esta manera nos queda un bonito sistema de ecuaciones:
• BC’ = ∅
• XC’ = ∅
• B’CX’ = ∅
Y esta es toda la informacion que necesitamos. Podemos deducir entonces dos cosas:
• Para que la ecuacion tenga solucion, B C.⊂
• B’C X C⊂ ⊂
B’C = A1’C = (2, 6, 30)
C = 
Respectivamente, B’C es la solucion minimal, mientras que C es la solucion maximal.
Esto ya nos permite descartar la opcion d:
d) Falso.
Para calcular el cardinal de X, basta con restar el cardinal de C por el de B’C y usarlo como exponente de 2. Es 
decir: |X| = 2|B’C| - |C|. Esto es debido a que el conjunto X contendra todas los conjuntos posibles que contengan 
como minimo los elementos de B’C y se les vaya combinando elementos de C, sin superar al conjunto C. En este 
caso, X = {(2, 6, 30), (1, 2, 6, 30), (2, 3, 6, 30), (1, 2, 3, 6, 30)}
Notese que |X| = 4, lo cual es la cantidad de soluciones posibles a la ecuacion planteada. Esto resulta de lo mismo 
que hacer 25-3 = 4.
22
Finalmente, conociendo la solucion minimal y la cantidad de soluciones, podemos afirmar que las opciones a y 
c son falsas, dejandonos como verdadera la opcion b.
23
Resolucion
Quien posea vista de aguila notara que en las opciones a, b y e se presentan grafos con la misma sucesion grafica, 
y se piden los complementos. Quien tenga una vista aun mas aguda notara que en la opcion g se presenta una 
sucesion grafica que casualmente resulta ser la sucesion grafica del complemento del grafo de las opciones a, b y 
e (Si no lo ven, tomen cada grado de la sucesion grafica deg(v) de G y conviertanlos en n(G) – deg(v)).
 Aprovechemos la ocasión para dibujar estos grafos:
a) Falso. Recordemos algunas definiciones:
• Excentricidad: maxima distancia entre un vertice u y todos los vertices del grafo G.
• Radio: excentricidad minima de G.
• Diametro: excentricidad maxima de G.
Sabiendo esto, y observando el grafico, resulta evidente que r(G’) = 1 y ϕ(G’) = 2.b) Falso. Nuevamente repasemos algunas definiciones:
• Corte de aristas: conjunto de aristas F E(G) / G - F tiene mas de una componente, y la remocion de solo⊆
algunas aristas de F no desconecta los vertices de G.
24
• Arista-conectividad: minimo cardinal de F / G - F es disconexo. Es decir, la minima cantidad de aristas 
que se deben desconectar para hacer de G un grafo disconexo.
El enunciado afirma que λ(G) = 3. Sin embargo podemos observar que, por ejemplo, removiendo dos aristas 
podemos aislar al vertice 2, logrando que G sea disconexo. Esto quiere decir que λ(G) = 2.
c) Verdadero. Tan facil como encontrar un grafo que cumpla dichas condiciones.
Partamos de la base de que G posee 5 vertices y 4 aristas. ¿Podemos acomodar estas aristas de manera que su 
radio sea 2 y su diametro sea 3?
e) Falso.
• Corte de vertices: conjunto de vertices S V(G) / G - S tiene mas de una componente, y la remocion de ⊆
solo algunos vertices de S no desconecta G.
• Vertice-conectividad: minimo cardinal de S / G - S es disconexo. Es decir, la minima cantidad de vertices 
que se deben remover para hacer de G un grafo disconexo.
Tan sencillo como remover el vertice 5, y desconectaremos el grafo. κ(G’) = 1.
f) Falso. Siendo n = 5 y m = 4, podria existir un grafo que contenga como subgrafo a K3, y como bien dice una 
propiedad muy importante:
• Si G contiene a un grafo completo Kn => κ(G) >= κ(Kn)
Ademas, κ(Kn) = n. Por consiguiente, el numero cromatico de dicho G seria mayor a 3.
Como ejemplo, para no dejarlos con las ganas, les dibujo este grafo:
25
g) Falso. Si d(G) = (2, 2, 2, 2, 4), entonces d(G’) = (0, 2, 2, 2, 2). A partir de esto, tenemos la siguiente formula 
para calcular la cantidad de aristas de un grafo a partir de su sucesion grafica:
∑
k=1
n
deg (v)=2 m
Con esto, logramos llegar a que la cantidad de aristas de G’ es m = 4, cantidad insuficiente de aristas para formar 
un K4.
26
Resolucion
El ejercicio nos propone una combinacion de conjuntos de veracidad correspondientes a ciertas proposiciones. Y, 
observando las opciones de respuesta, notamos que todas involucran ecuaciones de proposiciones. Por lo que seria
ideal tener, de alguna manera, las areas pintadas del cuadro escritas en forma de formula, ¿o no?
El procedimiento para ello es el escribir la formula en Forma Normal Disyuntiva (FND), la cual se obtiene a 
partir de la “suma” de las areas pintadas (tambien podria realizarse con la Forma Normal Conjuntiva (FNC); yo 
recomiendo la FND ya que es mas intuitiva o, al menos, es la que mas practique y mejores resultados me dio).
27
= pqr’ + p’qr’ + p’qr + p’q’r
Se ve sencilla, ¿no? Lo siguiente que debemos hacer es tomar cada una de las opciones de respuesta, y ver cual 
nos conduce a esta misma expresion.
a) Falso. Para comenzar, recordemos lo siguiente: p → q = p’ + q. Resolvamos la ecuacion:
= pr → q’
= (pr)’ + q’
= p’ + r’ + q’ (P. De Morgan)
= p’(q + q’)(r + r’) + r’(p + p’)(q + q’) + (p + p’)q’(r + r’) (Usamos la P. Complemento a la inversa)
= p’qr + p’qr’ + p’q’r + p’q’r’ + pqr’ + pq’r’ + p’qr’ + p’q’r’ + pq’r + p’q’r + pq’r’ + p’q’r’ (P. Distributiva)
= p’qr + pq’r + pqr’ + p’q’r + p’qr’ + pq’r’ + p’q’r’ (Eliminamos los elementos repetidos, y llegamos a la FND)
c) Falso.
(p’q → rp’) + pqr
Notemos algo de esta formula: uno de los terminos que se esta sumando es pqr. Ya que este termino es una 
conjuncion de los conjuntos de veracidad, este se mantendra igual durante el camino de llevar la formula a su 
FND. Dado que pqr no se encuentra en la FND de la proposicion de las regiones sombreadas del cuadro, ya 
podemos ir descartando esta opcion (si no me creen, les propongo desarrollar la formula y llevarla a la FND para 
probar que el termino pqr se mantiene sin cambios).
d) Verdadero. Para comenzar, recordemos lo siguiente: p ↔ q = pq + p’q’
= pr ↔ (q + r)’
= pr(q + r)’ + (pr)’(q+r)
28
= prq’r’ + (p’ + r’)(q + r) (P. De Morgan / P. De Morgan)
=F + p’(q + r) + r’(q + r) (P. Complemento / P. Distributiva)
= p’q + p’r + qr’ + rr’ (P. Neutro / P. Distributiva)
= p’q(r + r’) + p’(q + q’)r + (p + p’)qr’ (P. Neutro / P. Complemento, pero al reves)
= p’qr + p’qr’ + p’qr + p’q’r + pqr’ + p’qr’ (P. Distributiva)
= p’qr + p’qr’ + p’q’r + pqr’ (Eliminamos los elementos repetidos)
e) Falso.
= (q + r) → (pq + r)
= (q + r)’ + (pq + r)
= q’r’ + pq + r (P. De Morgan)
= (p + p’)q’r’ + pq(r + r’) + r (P. Complemento, pero al reves)
= pq’r’ + p’q’r’ + pqr + pqr’ + r (P. Distributiva)
Noten que, aunque no llegamos a la FND, ya hay terminos presentes que no se encuentran en la FND original, por
lo que ya podemos descartar esta opcion. Y a partir de ahora, cada vez que encontremos una conjuncion que no se 
encuentra en la proposicion dada por el enunciado, la descartaremos)
f) Falso.
= (r + p’) ↔ (pr’)’
= (r + p’)(pr’)’ + (r + p’)’(pr’)
= (r + p’)(p’ + r) + (pr’)(pr’) (P. De Morgan / P. De Morgan)
= (p’ + r) + pr’ (P. Idempotencia / P. Idempotencia)
= p’+ (p + r)(r + r’) (P. Distributiva)
= p’ + p + r (P. Complemento)
= r (P. Complemento)
Podemos detenernos en esta parte y analizar a lo que hemos llegado. Siendo la formula igual a r, esto querria decir
que el unico conjunto de veracidad seria el circulo R, y nada mas. Sin embargo al ver el cuadro, notamos que eso 
no es cierto: mientras que no todo el circulo R se encuentra pintado, hay sectores fuera del circulo R pertenecen al 
conjunto de veracidad dado.
g) Falso.
= (q + pr) → pr
= (q + pr)’ + pr
= (pr)’q’ + pr (P. De Morgan)
A esta altura, ese pr ya me suena medio raro. Trabajemos con eso:
29
= (pr)’q’ + pr(q + q’) (P. Complemento al reves)
= (pr)’q’ + pqr + pq’r (P. Distributiva)
Nuevamente, observando que el termino pqr es una conjuncion que no aparece en la FND original, vamos a 
descartar instantaneamente esta opcion.
30
Resolucion
a) Falso. Comencemos graficando el grafo correspondiente a R:
Es un buen punto de partida. Sin embargo, lo que en realidad nos estan
pidiendo es la clausura transitiva de R. ¿y que demonios era la clausura
transitiva? Una clausura transitiva es la relacion binaria mas pequeña que,
siendo transitiva, contiene al conjunto de pares de la relacion binaria
original.
Un bardo, ¿no? Demos una idea pero en criollo:
Recordemos el concepto de transitividad: Si aRb y bRc, entonces aRc.
Entonces, ¿que debemos hacer? Convertir R en una relacion transtiva. Y ya
que son pocos elementos, vamos a hacerlo a ojo.
• Si a1Ra3 y a3Ra4, entonces agregamos a1Ra4.
• Si a2Ra3 y a3Ra4, entonces agregamos a2Ra4.
Dibujemos entonces la clausura transitiva de R:
La consigna afirma que el numero cromatico de este grafo es 2. Pero, si
pintamos los vertices con la minima cantidad de colores posibles, llegamos a
que su numero cromatico es 3.
31
b) Falso. Grafiquemos un contraejemplo: 
Analizemos si cumple con lo enunciado en la proposicion:
• n(G) = 7, lo cual coincide con el cardinal de A.
• Representa un diagrama de Hasse, por ende, es ordenado.
• Su maximo es 7, mientras que su minimo es 1.
¿Es euleriano? Bueno, dado que un diagrama de Hasse es un grafo no
orientado, poodemos usar la propiedad de que un grafo es euleriano sii
para todo v perteneciente a V(G): deg(v) es par. Y de hecho, se cumple.
El grado de todos los vertices es dos; por ende, par. Entonces si es
euleriano.
c) Falso. Si d(G) = (2, 2, 3, 3, 4, 4), entonces ya podemos afirmar que d(G’) = (1, 1, 2, 2, 3, 3). Entonces, 
grafiquemos todos los grafos posibles que posean esta sucesion grafica pero no que no sean isomorfos entre si:
Noten como el ultimo ejemplo
nos da un G’ disconexo, y como
una de las propiedades de los
grafos es que la arista-
conectividad siempre sera menor
o igual al grado del vertice con
el grado mas bajo, entonces 
λ(L(G’)) = 0.
32
d) Falso. Observando la sucesion grafica del grafo, se puede ver que uno de los vertices posee 5 aristas. Esto 
querria decir que uno de los vertices (no importa cual) esta conectado con todos los vertices, lo cual provoca que 
inevitablementeel diametro de G sea 2, siempre.
e) Falso. Ahi les va un contraejemplo:
f) Falso. Pensemos como contraejemplo el diagrama de Hasse correspondiente a D30 (el conjunto de los divisores 
enteros de 30):
Como se alcanza a observar, se puede asignar una
coloracion de manera que el numero cromatico del
grafo sea 2, y sin embargo la cantidad de atomos de
D30 es 3: {2, 3, 5}.
g) Verdadero. Por descarte de las opciones anteriores.
33
Resolucion
No hay resolucion para este ejercicio maldito. Si ven esto en un examen, corran por sus vidas y recursen. Si son 
valientes, dejen la carrera y estudien algo mas facil como administracion de empresas. No sometan su vida ante 
este demonio.
34
Jasjasjkajs mentira chinchulin como no va a haber resolucion.
Se nos presenta un conjunto A de tan solo tres elementos: {1, 2, 3}; y un conjunto F = {f: A → A} ¿Que carajo 
singifica esto? Que F contiene a todas las funciones posibles que toman como dominio a A y como imagen a A. 
Como ejemplo, podriamos tener la funcion f(i) (que toma valores de A y devuelve valores de A) y definir su 
respuesta en base a qué parametro:
i f(i)
1 3
2 2
3 2
Es similar a lo que haciamos en primaria cuando aprendivamos funciones. Dibujabamos el conjunto Dominio, el 
conjunto Imagen, y tirabamos flechitas que uniesen ambos conjuntos.
Ademas de todo, nos definen una relacion binaria (uf) la cual dice:
fRg sii ∑
i=1
3
f (i)=∑
i=1
3
g (i)
¿Que quiere decir este choclo que a primer viste se ve espantoso? Traduzcamoslo a criollo: una funcion f ϵ F se 
relaciona con una funcion g ϵ F si y solo si f(1) + f(2) + f(3) = g(1) + g(2) + g(3).
Propongamos un g(i):
i g(i)
1 1
2 3
3 3
¿f se relaciona con g? Veamoslo: 
f(1) + f(2) + f(3) = g(1) + g(2) + g(3)
3 + 2 + 2 = 1 + 3 + 3
7 = 7
Efectivamente, f se relaciona con g.
Por ultimo, se nos presenta un elemento particular del conjunto F: u(i). Esta funcion se encuentra definida de la 
siguiente manera:
i u(i)
1 1
2 1
3 1
Con los datos aclarados, creo que es buen momento de comenzara a resolver el ejercicio.
35
Una buena manera de empezar es observando que de los seis items, tres afirman que R es una relacion de 
equivalencia, pues una buena opcion seria comenzar probandolo:
• Reflexividad: f(i) se relaciona con f(i). Esto es verdadero, puesto que ∑
i=1
3
f (i)=∑
i=1
3
f ( i) .
• Simetria: Si f(i) se relaciona con g(i), entonces g(i) se relaciona con f(i). Nuevamente, es verdadero ya 
que si ∑
i=1
3
f (i)=∑
i=1
3
g (i) , entonces ∑
i=1
3
g(i)=∑
i=1
3
f (i) .
• Transitividad: Si f(i) se relaciona con g(i) y g(i) se relacion con h(i), entonces f(i) se relaciona con h(i). 
Muy facil: si ∑
i=1
3
f (i)=∑
i=1
3
g (i) y ∑
i=1
3
g(i)=∑
i=1
3
h (i) , entonces ∑
i=1
3
f (i)=∑
i=1
3
h(i) . Y esto es
cierto, claramente.
Finalmente, R es una relacion de equivalencia.
a) Falso. Siendo x ϵ F, se nos presenta la siguiente ecuacion: x ∘ u = u. Aunque pueda parecer extraño, el 
operador ∘ es un amigo desde hace mucho tiempo. Asi es, es la operación composicion. Vamos a reformular la 
ecuacion: x( u(i) ) = u(i)
Bien, ¿en que casos ocurre esto? Veamos. La funcion u(i) devuelve, no importa el valor que tome, siempre 1. Esto 
quiere decir que x( u(i) ) = x(1), dado que x solo recibe los valores que u(i) devuelve y, justamente, solo son 1’s. 
Del lado derecho de la ecuacion ocurre algo similar. Por definicion, u(i) = 1 para i = 1, 2, 3; Con este analisis, 
podemos reescribir la ecuacion de la siguiente forma: x(1) = 1. ¡Excelente! Esta es una obligacion (y la unica) que
nos plantea la ecuacion. Esto quiere decir que x(2) y x(3) pueden tomar cualquier valor del conjunto imagen A, 
pues lo unico que interesa es que x(1) = 1.
Dado que x(2) y x(3) pueden tomar tres valores, independientemente uno del otro, la cantidad de soluciones 
(funciones x(i) que satisfacen la ecuacion) posibles sera ni mas ni menos que 32 = 9, lo cual no concuerda con el 
enunciado, que afirma que la cantidad de soluciones es 8. Si no se ve, les dejo este diagrama de arbol:
36
b) Falso. Ya hemos probado que es una relacion de equivalencia. Ahora nos queda probar que el cardinal del 
conjunto cociente es 8.
La definicion formal del conjunto cociente es la siguiente: Sea F un conjunto donde se ha introducido una 
relacion de equivalencia R, el conjunto cociente sera F/R = {[f1], [f2], …, [fn]}, donde [fi] = {x ϵ F: xRfi}.
De esta manera, si definimos fk como una funcion A→ A tal que ∑
j=1
3
f ( j)=k , entonces [fk] sera la clase de 
equivalencia que contiene funciones pertenecientes a F tal que la suma de sus soluciones sea igual a k. En este 
momento cabe preguntarse: ¿Pero cuantos valores puede tomar k? Bien, pensemoslo un poco. El valores mas 
pequeños que pueden tomar las soluciones de una funcion tal que {x(1) = 1, x(2) = 1, x(3) = 1} (tal como ocurre 
con u(i)), lo cual, sumandolos, nos da 3. Por otra parte, los valores mas altos que pueden tomar las soluciones 
seran {x(1) = 3, x(2) = 3, x(3) = 3}, cuya suma da 9. Dado que x(i) puede ser cualquier valor dentro del conjunto 
A, podemos decir que 3⩽k⩽9 . Entonces, F/R = { [fk] / 3⩽k⩽9 }, lo cual no deja con que [F/R] = 7.
c) Falso. Si queremos averiguar cual es el cardinal de la clase de equivalencia de [u], solo tenemos que 
preguntarnos: ¿cuantas funciones pertenecientes a F existen tal que ∑
j=1
3
f ( j)=3 ? Debemos hallar a, b, c ϵ A 
de manera que f(1) = a, f(2) = b, f(3) = c, y que a + b + c = 3. Y, la unica manera de satisfacer esta ecuacion, es 
que a = b = c = 1. Por ende, la clase de equivalencia solo posee una sola funcion (no dos como dice el 
enunciado), y es u(i).
d) Verdadero. Vuelvan a ver el procedimiento del inciso b).
f) Falso. Si bien es cierto que la matriz de adyacencia es simetrica, el cardinal de F es 27, y por lo tanto su matriz 
sera de 27x27. Esto se ve facilmente en un diagrama de arbol, o en una tabla de funciones:
x(1) x(2) x(3)
1 1 1 1
2 2
3 3
4 2 1
5 2
6 3
7 3 1
8 2
9 3
10 2 1 1
11 2
37
12 3
13 2 1
14 2
15 3
16 3 1
17 2
18 3
19 3 1 1
20 2
21 3
22 2 1
23 2
24 3
25 3 1
26 2
27 3
38
Resolucion
Ultra-archi-mega-recomendacion: Para estos tipos de ejercicios (que creanme, abundan) que debemos deducir el 
automata en base al lenguaje que acepta, conviene muchisimo graficar con birome el automata definido en la 
tabla, y luego dibujar con lapiz las aristas que propone cada inciso, de manera que sea facil borrar una opcion si no
es correcta, sin borrar todo el automata.
Recordemos que, para que un lenguaje sea el aceptado por un automata, el lenguaje debe poder aceptar todas las 
palabras que deriven de dicho lenguaje, y nada mas.
Notemos, ademas, que en todas las opciones, (q2, b) = q3. Entonces, como es 100% probable que esta arista este 
presente, no nos preocuparemos por ella.
Antes de comenzar, graficaremos el automata (o, lo que podemos). No se preocupen, para cada opcion 
graficaremos su automata completo correspondiente:
39
a) Verdadero. Realicemos un pequeño analisis de la situacion.
Debido a la funcion de transicion y al lenguaje aceptado por el
automata, las palabras formadas por (a + ba + bba)* siempre
desembocaran en q0. En consecuencia, para quedar en un estado
aceptable, las unicas palabras que puede tomar el automata (a partir de
lo anterior) son: nada (λ), b, o bb; lo que, casualmente, es (λ + b +
bb). 
¿Por que, en este ultimo tramo, no cabe lugar para una a? Pues
porque, de haberla, esta parte de la palabra seria parte de la primera
parte del lenguaje: (a + ba + bba)*
b) Falso. 
Propongamos la siguiente palabra: bbbb. Sencilla, ¿no? Y asi de sencilla como la ven, el automata la acepta (vean 
que termina en q2), y sin embargo, no es una palabra que sea generada por le lenguaje. De hecho, podria afirmar 
que todas las palabras generadas por (λ + b + bb(bb)*) son aceptadas por el automata.
40
c) Falso.
Propongamos la siguiente palabra: bba. Esta palabra es generada por el lenguaje, y sin embargo no es aceptada 
por elautomata.
d) Falso.
Prueben la misma palabra que usamos en el inciso c), ya que ocurre exactamente lo mismo.
e) Falso.
41
Probemos una palabra distinta: bbba. Nuevamente, esta palabra no es generada por el lenguaje, pero si es 
aceptaada por el automata.
42
Resolucion
a) Falso.
Dado el enunciado, podemos reescribirlo de la siguiente manera: 
∫
0
1
f 2(t)=0⇔∀ t∈[0 ,1] : f ( t)=0
¿Que quiere decir esto? Dos cosas:
• Si ∫
0
1
f 2(t)=0 , entonces ∀ t ∈[0 ,1] : f (t)=0 .
• Si ∀ t ∈[0 ,1] : f (t)=0 , entonces ∫
0
1
f 2(t)=0 .
¿Como podemos probar su falsedad? Probando que alguna de las dos proposiciones es falsa.
Pensemos un poco. ¿Cuando una integral definida puede dar 0? Si recuerdan el concepto de funciones impares de
Analisis Matematico 1, bingo, es por ahi; si no, lo defino rapidamente: una funcion impar es una funcion que 
satisface la siguiente relacion: f(-x) = -f(x). ¿Que es lo que nos importa de estas funciones? Que una de las 
propiedades mas importantes que poseen este tipo de funciones
es que la integral definida entre -t y t = 0; es decir:
∫
−t
t
f (x)=0 . Ejemplo de este tipo de funciones hay varios:
x, x3, sen(x), etc. Para trabajar con funciones sencillas y solo
enfocarnos en el enunciado, trabajaremos con la funcion f(t) = t.
Pero… existe un problema con esta f(t):
∫
0
1
f (t)=∫
0
1
t dt= t
2
2
(de0 a 1)=1
2
. Esto no da 0… ¿Como
podemos hacer para que esta integral de 0? 
43
Una buena opcion es la de generar un desplazamiento de la funcion de manera que la integral definida entre 0 y 1 
de 0. Es decir, definimos una nueva funcion f(t) = t + c, donde c es una constante que desplaza a la funcion por el 
eje de las ordenadas. Entonces:
∫
0
1
f (t)=∫
0
1
t +c dt=∫
0
1
t dt +∫
0
1
c dt=0.5+(ct)(desde 0a 1)=0,5+c=0
Entonces, si 0,5 + c = 0, c = -0,5 .
 f(t) = t – 0.5
Al fin. Hallamos la funcion que necesitabamos… NO, aun no. Queda una sola cuestion mas. La consigna dice que
∫
0
1
f 2(t)=0 . Ay, tan cerca… ¿Como solucionamos esto? Recontra facil: Redefinamos f(t) = (t – 0,5)0,5 . 
AHORA SI, tenemos nuestra funcion tan buscada que cumple con esa integral.
Pero, ¿por que en principio nos interesaba buscar una funcion asi? Porque, si son observadores, nuestra nueva 
funcion f(t) = (t – 0,5)0,5 no cumple con una de las proposiciones que presenta la consigna:
∀ t ∈[0 ,1] : f (t)=0 (tarea para la casa: probar que para nuestra f(t) esta proposicion no se cumple). Esto 
provoca que esta proposicion no sea condicion necesaria y suficiente para que la integral definida de 0 en ese 
rango.
b) Falso. Vamos a resolver la ecuacion para ver bajo que condiciones se cumple esta ecuacion:
P + Q = P + R
(P + Q)’(P + R) + (P + Q)(P + R)’ = ∅
P’Q’(P + R) + (P + Q)P’R’ = ∅ (P. De Morgan)
P’Q’R + P’QR’ = ∅ (P. Distributiva / P. Complemento)
P’(Q’R + QR’) = (P. Distributiva)∅
Con eso llegamos a que la condicion necesaria para que la ecuacion sea verdad es (Q ’ R+QR’)⊆P .
Incluso podriamos dar un contraejemplo
Sean:
P = (1, 2, 5)
Q = (1, 2, 3, 4, 5, 6)
R = (1, 2, 3, 4, 5, 6)
Noten como R⊈P y Q⊈P , y sin embargo la ecuacion se satisface: P + Q = Q; y P + R = R, y resulta ser 
que Q = R.
c) Verdadero. ¿Soluciones convergentes? ¿Que es eso? ¿Se come?
¿Cuando una solucion de una ecuacion de recurrencia es convergente? Cuando esta, al tender al infinito, resulta en
un numero concreto. Eso mismo plantearemos ahora.
Dado que en la ecuacion de recurrencia todas las incognitas estan siendo multiplicadas por constantes, podemos 
resolverla mediante el metodo del homogeneo
44
Xhn)
Siendo 2xn+3 – 3xn+2 – 3xn+1 + 2xn = 0,
la ecuacion caracteristica sera 2r3 – 3r2 – 3r + 2 = 0
Utilizando calculadora (no me jodan, no voy a resolverla a mano), se puede factorizar en (r + 1)(2r – 1)(r – 2) = 0.
Por ende, con sus raices a mano, podemos definir a la solucion homogenea:
Xhn = A*(-1)n + B(1/2)n + C*2n
Xpn) Dado que 2xn+3 – 3xn+2 – 3xn+1 + 2xn = -2, Xpn = D. Entonces
2D – 3D – 3D + 2D = -2
- 2D = -2
D = 1
En este sentido, Xn = A*(-1)n + B(1/2)n + C*2n + 1
Aclaremos dos cosas:
• Al tender a infinito, el valor de B es despreciable, por lo que no influye en el valor de convergencia.
• Como solo buscamos soluciones convergentes, tanto C como A deben ser igual a 0. Caso contrario, la 
solucion diverge.
Por lo que, ignorando esto, la solucion convergente para todos los B posibles (dado que C = A = 0) seria 1.
d) Falso. Esta opcion esta hecha para que se seleccione cuando el alumno no
se ha sentado ni 30 segundos a interpretar el enunciado. Prestando atencion,
se puede pensar rapidamente un contraejemplo.
Sea x = a+ b, inf(a + b, a + b) = a+ b, lo cual es distinto a b + c.
Curiosamente, si la consigna diciese: ∀ x∈B : inf ( x ,ab)=bc , esto
seria verdadero, dado a que como a, b y c son atomos, ab = 0, y bc = 0, y el
inf(x, 0) = 0 en todos los casos.
f) Falso. INCREIBLE, TENEMOS LAS FORMAS NORMALES DISYUNTIVAS DE LOS CONJUNTOS DE 
VERACIDAD. Bueno, solo el de p. Vamos a trabajar un poquito el de q:
= xz’ + yz
= x(y + y’)z’ + (x + x’)yz (P. Complemento, pero al reves)
= xyz’ + xy’z’+ xyz + x’yz (P. Distributiva)
Ahora tenemos la Forma Normal Disy… Esperen, ¿p es igual a q? 
Aclaracion: Recuerden que por definicion, si p es igual a q, eso quiere decir que p esta contenida en q y q esta 
contenida en p.
45
Resolucion
a) Falso. Si x e y fuesen atomos, entonces xy = 0, pero y no seria el complemento de x.
b) Verdadero. Dado que nos encontramos en un algebra de Boole, por definicion, el 1 es el maximo de esta 
algebra. Dado que la multiplicacion de dos elementos en un algebra de Boole dara como resultado siempre la cota 
inferior maxima en comun de los dos elementos, para que esta cota inferior maxima sea 1 (el maximo elemento 
del algebra), no queda otra que ambos factores de la multiplicacion sean igual a 1.
d) Falso.
y(x + y + z)(x’ + y + z)(x’ + y’ + z)(x + y + z’) = (xz’)’
(xx’ + y + zz’)(x + y + z)(x’ + y + z)(x’ + y’ + z)(x + y + z’) = (x’ + z) (P. Complemento)
(x’ + y’ + z’)(x + y’ + z’)(x’ + y’ + z)(x + y’ + z)(x + y + z)(x’ + y + z)(x’ + y’ + z)(x + y + z’) = (x’ + yy’ + z) (P. 
Distributiva / P. Complemento)
(x’ + y’ + z’)(x + y’ + z’)(x’ + y’ + z)(x + y’ + z)(x + y + z)(x’ + y + z)(x + y + z’) = (x’ + y + z)(x’ + y’ + z)
Dado que llegamos a las Formas Normales Conjuntivas de ambos lados de la iguadad, y son distintas, este 
enunciado es falso.
e) Falso. Si x = 1, por propiedad de Acotacion:
x + y = x + z
1 + y = 1+ z
1 = 1
46
f) Falso. y = x’ (?
47
Resolucion
Demosle un nombre a las proposiciones que componen esta gran proposicion:
• p = “La suma de dos numeros reales es menor que 50” → x + y < 50.
• q = “Al menos uno de los numeros es menor a 25” → x < 25 o y < 25.
La proposicion dada por el enunciado seria p → q. Esto se puede leer como. “Que la suma
de dos numeros reales sea menor a 50 implica que al menos uno de los numeros es menor a
25”.
Podemos probar que esta proposicion es verdadera mediante una llegada al absurdo:
Sabiendo que x + y < 50, pero suponiendo que x >= 25 e y >= 25:
= x+ y < 25 + 25
= x – 25 < 25 – y
Dado que x es mayor a 25, ∀ x∈[25 ,+∞] :(x−25)⊂[0 ,+∞] (en criollo, para todo x >= 25, x – 25 se 
encontrar dentro del conjunto de los reales positivos y cero.
Dado que y es mayor a 25, ∀ y∈[25 ,+∞] :(25− y )⊂[−∞ , 0] (en criollo, para todo y >= 25, 25 - y se 
encontrar dentro del conjunto de los reales negativos y cero.
Teniendo esto en cuenta, podemos ver que la inecuacion nos queda como “un numero
positivo (o cero) es estrictamente menor que otro numero negativo (o cero)”, lo cual
evidentemente es absurdo. 
Esto quiere decir que el conjunto P de pares de numeros reales (x, y) que cumplen x + y <
50 se encuentra contenido dentro del conjunto Q de pares de numeros reales (x, y) tales que
al menos uno de ellos es menor a 25.
a) Falso. “La negacion de la contraria es falsa”
48
(p’ → q’)’ = F
(p + q’)’ = F
p + q’ = T
q → p = T
Esto esta diciendo que la proposicion: “Que almenos uno de dos numeros reales es menor a 25 implica que su 
suma es menor que 50”, es verdadera. Sin embargo esto es falso. Por ejemplo, 20 + 40 >= 50, y sin embargo 20 < 
25.
c) Falsa. “La negacion es verdadera”
(p → q)’ = T
p → q = F
Esto directamente niega que la proposicion dada en el enunciado sea verdadera, pero como ya probamos que 
evidentemente es verdadera, esta proposicion es falsa.
d) Verdadero. “La contrarreciproca es verdadera”
q’ → p’ = T
q + p’ = T
p’ + q = T
p → q = T
Esto esta afirmando que la proposicion dada por el enunciado es verdadera siempre, cosa que ya hemos probado 
que es cierta.
e) Falso. “La contraria es verdadera”
p’ → q’ = T
p + q’ = T
q’ + p = T
q → p = T
Esta proposicion es exactamente igual a la planteada a la de la opcion a. Vamos a descartarla inmediatamente.
f) Falso. “La reciproca es falsa”
q → p = F
En este caso, se afirma que la proposicion: “Que al menos uno de dos numeros reales es menor a 25 implica que 
su suma es menor que 50”, es siempre falsa. Nuevamente, esto es incorrecto, pues podriamos dar como ejemplo10
+ 30 < 50, de manera que 10 < 25, resultando la proposicion q → p verdadera.
49
Resolucion
Vamos a revisar la ecuacion para obtener algunos datos de vital importancia:
AX + BX´= Ø 
Para que esto sea verdadero:
• AX = Ø
• BX’ = Ø
Lo cual resulta ser:
• X A’⊂
• B X⊂
Es decir, B X A’. Podemos deducir como condicion necesaria para que la ecuacion tenga solucion que B ⊂ ⊂ ⊂
A’.
a) Falso. Sean A y B conjuntos tales que B A’, y sea X = B:⊆
• BB’ = Ø, por la propiedad del complemento.
• AB = Ø, Dado que B es un subconjunto de A’, y por esto, contiene elementos que no estan presentes en A.
b) Falso. Como probamos anteriormente, no es necesario que B sea igual a A’. Basta con que B este contenido en 
A’ para que la ecuacion posea solucion.
c) Falso. Si B = A’, entonces X posee una sola solucion, y es A’. Noten que como B = A’, entonces A’ X A’, y⊂ ⊂
no queda otra que sea A’ sea la unica solucion.
e) Falso. ¿A = B’? More like B = A’.
(Utilicen la propiedad del complemento y prueben que ambas igualdades representan lo mismo)
50
f) Veradero. Vamos a desarrollar un poquito: A B’ → AB = Ø → BA = Ø → B A’. ¿Adivinen que? Esta es ⊂ ⊂
la condicion necesaria que obtuvimos al principio.
51
Resolucion
Uf, nos quieren hacer trabajar. Que paja…
Dado el grafo G, y la relacion R, tenemos que ver que elementos del conjunto A estan relacionados para poder 
definir E(G). Por suerte es un proceso sencillo: Solo debemos fijarnos que Ai∩Aj sea distinto de Ø.
Al hacerlo, nos queda el siguiente grafo:
De paso, probemos si R es una relacion de equivalencia (dos de las opciones lo afirman):
• Reflexividad: Para todo 1 <= i <= 6, Ai∩Ai = Ai, por lo que si es reflexiva.
• Simetria: Dado que Ai∩Aj = Aj∩Ai, R es simetrica.
• Transitividad: Como ejemplo, A2RA3 y A2RA4, y sin embargo A3∩ A4 = Ø. R no es transitiva.
Comprobamos asi que R no es una relacion de equivalencia.
b) Falso. R no es una relacion de equivalencia.
52
c) Falso. r(G) = 2, ϕ(G) = 3.
d) Verdadero. El camino (A1A3A2A6A5A4A1) evidencia que G es hamiltoniano, y ademas, deg(A1) = 3, deg(A2) = 
3, deg(A3) = 2, deg(A4) = 4, deg(A5) = 3. deg(A6) = 3, por lo que d(G) = (2, 3, 3, 3, 3, 4)
e) Falso. G no es bipartito, pues no es posible crear dos grupos V1 y V2 que cumplan las caracteristicas de un grafo
bipartito.
f) Falso. Ya hemos probado que R no es una relacion de equivalencia.
g) Falso. Probar si es planar o no es un bodrio, pero lo vamos a hacer igual:
Podemos utilizar la siguiente propiedad del grafo plano triangular: Si G es planar, entonces m <= 3(n-2). Siendo 
m = 9, y n = 6, 9 <= 12. La propiedad se cumple, por ende G es planar, pero por las dudas vamos a graficarlo:
Bueno, pareciera que κ(G) = 4, ¿no?
53
Resolucion
Para comenzar, me gustaria probar una de las propiedades mas importantes de los grafos aristas. No solo para que 
lo entienda usted, señor lector, sino para mi propia practica y goze. La propiedad dice asi:
Si G es euleriano => L(G) es euleriano y hamiltoniano.
Recontra picante, ¿no?
Pasemos a probar que esto es, en definitiva, cierto.
Recordando las palabras del gran padre celestial, Leonhard Euler, padre de los grafos eulerianos: Un grafo G es 
euleriano sii ∀ v∈V (G): deg(v)es par . Un capo Euler. Creo la teoria de grafos, definio uno en especifico 
y le puso su nombre. ¿Y vos que hiciste, chinchulin?
Dado que G es euleriano, eso quiere decir que su sucesion grafica esta compuesta solo por valores pares. 
Interesante. ¿Donde podemos enganchar esta idea?
Muy bien, otro groso misterioso definio la siguiente propiedad para los grafos aristas:
Si u∈V (L(G))correspondea la arista xy∈E(G) :deg(u)=d (x)+d ( y )−2 . O sea, tenemos dos 
propiedades de cosas distintas, conectadas por un concepto en comun: la cantidad de aristas que inciden en los 
vertices.
Me gustaria que hagamos una pausa, y preguntarte: ¿Ya descubriste por donde va el asunto? ¿Podrias seguir 
completando esta prueba? 
¿No? Dale man. ¿En serio no se te ocurre nada? 
¿Y le preguntaste a Messi si sabe?
¿No sabe tampoco?
Bueno, voy a tener que seguir yo. Pamplinas…
54
Partiendo de las siguientes ideas:
• Para que L(G) sea euleriano, cada vertice u (que representa la arista xy en G) debe tener grado par.
• deg(u) = deg(x) + deg(y) – 2.
Como G es euleriano, eso querra decir que para todo vertice x o y perteneciente a G: deg(x) es par (deg(y) tambien
es par). Eso quiere decir que deg(x) + deg(y) tambien es par, y si a eso le resto 2, seguira siendo par. Y, como esto 
ocurre con todos los vertices de G, deg(u) = deg(x) + deg(y) – 2 siempre sera par. Por ende, como el grado de 
cada vertice u de L(G) es par, entonces L(G) es euleriano.
Pero banquen. Tambien es hamiltoniano, ¿no? Bueno, esto ocurre porque el circuito euleriano presente en G se 
convertira en un ciclo hamiltoniano en L(G). O sea, como cada arista que forma el circuito euleriano se convertira 
en un vertice de L(G), y cada arista del circuito son adyacentes una con otra, esto provocara que todos los vertices 
que representan aristas del circuito se conecten entre si, formando asi un ciclo que sera hamiltoniano.
a) Falso. Definamos las proposiciones:
• p = “G es euleriano”.
• q = “L(G) es euleriano.”
La proposicion del enunciado dice: “Una condicion suficiente para que L(G) sea euleriano es que G sea 
euleriano” (p → q). Su contraria es: “Una condicion suficiente para que L(G) no sea euleriano es que G no sea 
euleriano”(p’ → q’), lo cual es lo mismo que decir: “Si G no es euleriano, entonces L(G) no es euleriano”.
p’ → q’ = p + q’ = q → p = T
“Una condicion suficiente para que G sea euleriano es que L(G) sea euleriano”
Es decir, Si L(G) es euleriano, entonces G es euleriano.
Esta premisa, de entrada, puedo asegurarles que es falsa. Lo se, lo lei en un libro de teoria. Pero, ¿como lo 
probamos?
Si bien la mencionamos anteriormente, volvamos a definir que significa que un grafo sea euleriano: Un grafo G 
es euleriano sii ∀ v∈V (G): deg(v)es par .
Por otra parte, hablemos de una de las propiedades de los grafos aristas:
Si u∈V (L(G))correspondea la arista xy∈E(G) :deg(u)=d (x)+d ( y )−2 .
(No nos detendremos a probar estas propiedades ya que no va al caso del examen).
Pensemos estas dos ideas en conjunto. Estamos buscando que L(G) sea euleriano, pero G no lo sea. Para ello, todo
vertice de L(G) debe tener grado par, mientras que en G con que al menos uno de sus vertices tenga grado impar 
bastaria para que este no sea euleriano. Por ende, mirando la formula deg(u) = d(x) + d(y) – 2, queremos que tanto
d(x) como d(y) sea impares, para todo vertice x, y perteneciente a V(G), de manera que al sumarlos y restarle 2, 
deg(u) sea par. De esta forma, para todo G tal que la sucesion grafica d(G) este compuesta por grados impares, 
L(G) tendra una sucesion grafica d(L(G)) compuesta por solo grados pares, siendo entonces G no euleriano y 
L(G) euleriano, demostrando asi lafalsedad del enunciado. MOSTRAR UN EJEMPLO. Dale Tinefe del pasado 
gg.
55
Aclaracion: L(G) no es un digraph. Las flechas marcan el circuito euleriano.
b) Definamos las proposiciones:
• p = “G es euleriano”.
• q = “L(G) es hamiltoniano”.
La proposicion del enunciado dice: “Una condicion suficiente para que L(G) sea hamiltoniano es que G sea 
euleriano” (p → q). Su contraria es: “Una condicion suficiente para que L(G) no sea hamiltoniano es que G no 
sea euleriano”(p’ → q’), lo cual es lo mismo que decir: “Si G no es euleriano, entonces L(G) no es euleriano”.
p’ → q’ = p + q’ = q → p = T
“Una condicion suficiente para que G sea euleriano es que L(G) sea hamiltoniano”
Nuevamente, falso. ¿Como lo se? Pues por el ejemplo que presente en el inciso a. L(G) es hamiltoniano, pero G 
no es euleriano. Pero esto es solo un contraejemplo. Si bien alcanza, ¿podemos probar que realmente esto es falso 
de manera mas “analitica”? Ya que tirar grafos al azar hasta encontrar uno que justo encaje como contraejemplo es
muchisimo riesgo para un examen.
Pues… no es tan sencillo. Definir que hace a un grafo hamiltoniano no es algo que se haya logrado hacer. Pese a 
esto, hay teoremas que se acercan a una buena definicion. Para probar la falsedad de este ejercicio, tomaremos 
prestado el teorema de Dirac, que dice lo siguiente:
Sea G = (V, E) conexo simple con |v| = n >= 3. Si ∀ v∈V (G): deg(v)≥n
2
, entonces G es hamiltoniano.
Entonces, recordando la propiedad loca de los grafos aristas, lo que necesitaremos para que L(G) sea hamiltoniano
sera que: deg( x)+deg ( y)−2≥m
2
. Super ambiguo. No sabemos la sucesion grafica de G, ni su cantidad de 
vertices o aristas. Mmmh… ¿Existe algun caso de grafos donde conozcamos su cantidad de vertices, aristas, y los 
grados de cada vertice?
¡Si! ¡Los grafos completos! Intentemos con estos tipos de grafos.
56
Para Kn sabemos que n(G) = n, m(G) = n(n-1)/2, y para todo vertice v: deg(v) = n – 1.
Esto quiere decir que:
(n – 1) + (n – 1) – 2 >= (n(n-1)/2)/2
2n – 4 >= n(n-1)/4
8n – 16 >= n(n-1)
8n – 16 >= n2 – n
0 >= n2 – 9n + 16
¿Saben que quiere decir esto? Que si para cierto n par (mayor a 3, ya que lo pide Dirac), esta inecuacion se 
cumple, entonces esto quiere decir que Kn no sera euleriano, pero L(Kn) sera hamiltoniano. Podriamos hacer tres 
cosas: tirar valores aleatorios de n hasta encontrar alguno que satisfaga la inecuacion, poner en practica los 
conocimiento de analisis matematico 1 para encontrar todos los valores de n que satisfagan la inecuacion, o 
graficarla. Yo opto por lo tercero:
¿Que valores pares mayores a 3 encontramos que
satisfagan la ecuacion? 4 y 6.
Esto quiere decir que K4 y K6 no son eulerianos (ya que sus
vertices no tienen grado par), pero sus grafos aristas
correspondientes si son hamiltonianos (por lo que
acabamos de probar). ¡Y miren que loco! El ejemplo que
graficamos en el inciso a no es mas ni menos que K4 :)
c) Falso. Que lindo, un ejercicio facil al fin. Recordemos la siguiente propiedad de los grafos aristas: Si G = (V, E)
con n = |V(G)| y m = |E(G)|, entonces: m(L(G))=[ 1
2
∑
k=1
n
deg2(Vk)]−m .
Veamos si esto se cumple para la sucesion grafica dada:
m(L(G)) = (32 + 32 + 42 + 42 + 42)/2 – (3 + 3 +4 +4 + 4)/2
m(L(G)) = [(9 + 9 + 16 + 16 + 16) – 18]/2
m(L(G)) = (66 – 18)/2
m(L(G)) = 48/2
m(L(G)) = 24.
d) Falso. Definamos las proposiciones:
57
• p = “G es euleriano”.
• q = “L(G) es euleriano”.
La proposicion dice: “Una condicion necesaria para que G sea euleriano es que L(G) sea euleriano” (q’ → p’). 
La proposicion reciproca seria: “Una condicion necesaria para que L(G) sea euleriano es que G sea 
euleriano”(p’ → q’), lo cual es lo mismo que afirmar: “Si G no es euleriano, entonces L(G) no es euleriano”.
p’ → q’ = p + q’ = q → p = T
“Una condicion suficiente para que G sea euleriano es que L(G) sea euleriano”.
Esta proposicion es falsa, y ademas la hemos probado en el inciso a.
f) Falso. Les tiro alto contraejemplo: 
g) Falso. Definamos las proposiciones:
• p = “G es euleriano”.
• q = “L(G) es euleriano”.
La proposicion dice: “Una condicion necesaria para que G sea euleriano es que L(G) sea euleriano”(q’ → p’). 
Su contraria seria: “Una condicion necesaria para que G no sea euleriano es que L(G) no sea euleriano”(q → p),
lo cual es lo mismo que afirmar: “Si L(G) es euleriano, entonces G es euleriano”.
Por tercera vez, esto es falso, y lo hemos justificado en el inciso a.
e) Verdadero. Por descarte de las opciones anteriores.
58
Resolucion
a) Falso. Probemos que R es una relacion de equivalencia:
• Reflexividad: GRG sii G es isomorfo a G. Claramente cierto. Podemos formar una f: G → G / f(gi) = gi.
• Simetria: Si G es isomorfo a H, H es isomorfo a G. Nuevamente cierto. Si existe una f: G → H / f(gi) = 
hi, entonces existe una funcion m: H → G / m(hi) = gi. m(h) resulta ser f-1(h).
• Transitividad: Si G es isomorfo a H con funcion f: G → H y H es isomorfo a K con funcion m: H → K, 
entonces G es isomorfo a K, con funcion compuesta m(f(gi)) = ki.
Entonces, R es una relacion de equivalencia.
Para determinar el cardinal del conjunto cociente F/R, hay que determinar cuantos tipos de grafos no isomorfos 
poseen dicha sucesion grafica. Para demostrar la veracidad, debemos encontrar 4 grafos que no sean isomorfos. 
Para demostrar falsedad, este numero debe ser distinto a 4.
Vamos a aprovechar una de las propiedades mas potentes del isomorfismo: Si G es isomorfo a H, entonces G’ es 
isomorfo a H’. Por lo que, para facilitarnos el trabajo, buscaremos isomorfismos para grafos de d(G’) = (1, 1, 2, 2, 
3, 3). Fijense como se reduce la cantidad de aristas… esto facilita muchisimo el trabajo.
Recordemos que una de las caracteristicas mas importantes de los grafos es que comparten: orden, tamaño, grado 
minimo, grado maximo, radio, diametro, longitud de sus ciclos (y cantidad de ellos), sucesion creciente de 
grados, espectro, numero cromatico, indice cromatico. ¿Por que seleccione algunas caracteristicas en negrita? 
Ya que los grados pertenecientes a F tienen una sucesion de grados determinada, todas las caracteristicas que no 
he resaltado en negrita quedan condicionadas por esta sucesion. Por ende, sera facil probar que dos grafos no son 
isomorfos con tan solo no coincidir en alguno de estos atributos.
A continuacion, para demostrar su falsedad, intentare buscar al menos 5 grafos que posean dicha sucesion grafica 
y no sean isomorfos entre si. ¿Por que 5? Porque, si encuentro menos de 4, entonces no podre estar seguro de que 
existan mas grafos isomorfos y que estos lleguen a ser 4; si encuentro exactamente 4 y nada mas, esta proposicion 
sera verdadera; si encuentro mas de 4, entonces estara probada la falsedad.
59
c) Falso. “Para todo grafo G perteneciente a F, el centro de G es distinto de la periferia de G”.
El centro de un grafo es el conjunto de vertices de excentricidad minima, mientras que la periferia es el conjunto 
de vertices de excentricidad maxima.
Para que C(G) != P(G), r(G) != ϕ(G). Eso quiere decir que encontrando un grafo tal que r(G) = ϕ(G) 
demostrariamos que la proposicion es falsa. Y de hecho, existe un G perteneciente a F tal que su radio es igual a 
su diametro, los cuales valen ambos 2:
d) Falso. “Para todo grafo G perteneciente a F, G’ es conexo”.
60
Nooooooo, eso no es cierto. Como vimos en el inciso a, d(G’) = (1, 1, 2, 2, 3, 3), y esta sucesion grafica me esta 
pidiendo a gritos que una esos dos vertices cuyo grado es 1 entre si:
e) Verdadero. ¿Que determina que un grafo sea planar? Bueno, como mencionamos varias veces, si un grafo es 
simple y planar con n >= 3, entonces m <= 3(n – 2). Por otra parte tambien esta bueno saber que si n > 3 y no 
existen ciclos de longitud 3, entonces a <= 2n – 4.
Probemos entonces el primer teorema dado. 
2m = 2 + 2 + 3 + 3 + 4 + 4
2m = 18
m = 9
9 <= 3(6 – 2)
9 <= 12.
Dado que se cumple el primer teorema, podemos afirmar que todos los grafos de F son planares.
f) Falso. Basta presentar un grafo que no sea hamiltonianoYyyy tenemos uno. El del inciso c.
g) Falso.
61
Resolucion
Dibujemos el automata que nos presentan (o lo que se pueda):
Noten como en las opciones siempre figura que (q0, a) = q0
aparece siempre, por lo que lo incluiremos como una arista
inamovible.
a) Falso. Un contraejemplo podria ser la palabra abbab, que deriva del lenguaje L, pero que no es aceptado por el 
automata.
62
b) Verdadero. No solo acepta todas las palabras generadas por el lenguaje, sino que no acepta ninguna otra 
palabra que no surja del lenguaje.
d) Falso. La palabra bbb es aceptada por el automata, pero no es generada por el lenguaje.
e) Falso. La palabra abbaab es generada por el Lenguaje, pero no es aceptada por el automata.
f) Falso. La palabra bbb no es generada por el lenguaje, pero si aceptada por el automata.
63
64
Resolucion
Wait a minute… ¿Que es F? F es el conjunto de todos los grafos simples tales que d(G) = (1, 1, 2, 2, 3, 3). ¿Se 
acuerdan de hace dos ejercicios anteriores, en la pagina 64, donde nuestra F eran los grafos simples que d(G) = (2,
2, 3, 3, 4, 4)? Bueno, pareciese que ahora vamos a analizar los complementos de los grafos de ese ejercicio. Una 
buena y facil, al fin….
a) Falso. ¡Buenisimo! G’ tiene sucesion grafica (2, 2, 3, 3, 4, 4). Entonces, la proposicion afirma que todos los 
grafos que posean dicha sucesion grafica seran hamiltonianos. Y eso es falso. Lo hemos probado dos ejercicios 
antes, mediante un contraejemplo, que nuevamente lo propongo aquí:
b) Falso. ¿Recuerdan que hace dos ejercicios tuvimos que probar esto mismo pero para los G / d(G) = (2, 2, 3, 3, 
4, 4,), y para hacerlo, tomamos la propiedad de que los complementos de dos grafos isomorfos tambien son 
65
isomorfos, y por lo tanto, probamos que el cardinal del conjunto cociente para grafos de d(G) = (1, 1, 2, 2, 3, 3) 
era mayor a 4? Bueno, esa justificacion se aplica exactamente igual a este ejercicio. En vez de copiar y pegar la 
explicacion, los invito a releerla, ya que insisto, es exactamente lo mismo.
d) Falso. Noten como la secuencia grafica se nos presta para formar un triangulo. Dada la propiedad de los 
numeros cromaticos: Si G contiene un subgrafo Kn, entonces su numero cromatico sera mayor o igual a n; si lo 
gramos que G contenga un triangulo, entonces κ(G) > 2 inevitablemente. Y de hecho tenemos varios grafos que 
contienen al menos un triangulo.
e) Verdadero. Nuevamente, debido a que d(G’) = (2, 2, 3, 3, 4, 4), esto ya lo hemos probado dos ejercicios antes, 
en el inciso e.
f) Falso. Esta viene de yapa. El ejemplo presentado en el inciso a es un ejemplo de G’ conexo.
g) Falso. Y esto se puede mostrar nuevamente mediante un contraejemplo. Fijense como los dos 1’s de la sucesion
grafica podrian unirse juntos y aislarse de los otros cuatro vertices sin ningun problema.
66
Resolucion
Resolveremos primero el inciso g, ya que voy dar unas explicaciones que seran fundamentales para justificar 
procedimientos de otros ejercicios.
g) Verdadero. 
Consideremos algunas restricciones que nos presentan los grafos de este conjunto:
Llamemos w(n) a los vertices tal que deg(w(n)) = n. Solo por comodidad.
Tenemos dos w(4) que evidentemente se conectaran con al menos un w(1). Si ocurriese que uno de los w(4) se 
conectase con ambos w(1), entonces los vertices w(1) no aceptarian mas incidencia de aristas, por lo que el otro 
w(4) solo podria conectarse con tres vertices, lo cual no es legal en este conjunto. En consecuencia, cada w(4) se 
conectara solo con un w(1), dejandole solo una posibilidad a cada w(4): que se conecte con un w(1), el otro w(4) y
con w(a) y w(b).
Reciprocamente, los w(1) no podrian conectarse entre si, ya que restringirian a los w(4) a solo conectarse con 3 
vertices. Tampoco podrian conectarse a los w(a) y w(b), ya que tambien restringirian a los w(4) a conectarse con 3
vertices nuevamente. Piensen que si un w(1) se conecta con, por ejemplo, w(a), y el otro w(1) se conecta a un 
w(4), entonces ambos w(1) quedarian restringidos, dejando al otro w(4) solo tres vertices para conectarse. En 
consecuencia, cada w(1) se conectara si o si con un solo w(4).
Gracias a este analisis de restricciones que nos presentan los grafos de este conjunto, podemos determinar la 
invarianza en 4 vertices (los dos w(1) y los dos w(4)), dejando a los w(a) y w(b) de tomar la cantidad de aristas 
que quieran siempre y cuanto respeten dichas restricciones. De esta forma, w(a) y w(b) solo pueden tomar dos 
configuraciones posibles:
67
De esta manera, siendo R una relacion tal que GRH si G es isomorfo a H (de equivalencia, ya lo hemos probado 
anteriormente), el cardinal de su conjunto cociente (el grupo de grafos isomorfos entre si) sera 2. Los unicos tipos 
de grafos no isomorfos que pertenecen a F son los dos mostrados arriba.
b) Falso. Dos de los vertices poseen grado 1, lo cual quiere decir que solo una arista incide en ellos. Si le 
otorgasemos una orientacion a esa arista, seria de entrada o de salida, por lo que solo podrian haber caminos que 
entrasen o saliesen del grafo, respectivamente. Entonces este grafo no podria ser fuertemente conexo.
c) Falso. Ya probamos que F esta compuesto solo por dos grafos no isomorfos: G1 / d(G1) = (1, 1, 2, 2, 4, 4), y G2 /
d(G2) = (1, 1, 3, 3, 4, 4). Entonces d(G1’) = (1, 1, 3, 3, 4, 4) y d(G2’) = (1, 1, 2, 2, 4, 4). Estas sucesiones graficas si
pertenecen a F; por ende, los complementarios pertenecen a F tambien.
d) Falso. Curiosamente, los dos grafos no isomorfos de F son complementarios entre si (se puede deducir de la 
explicacion del inciso c). Como ninguno de los dos es no conexo, entonces esta proposicion es falsa.
68
e) Falso. El indice cromatico de ambos grafos es 4.
f) Falso. Observando los dos posibles grafos de F, notamos que ninguno de los dos posee ciclos hamiltonianos.
69
Resolucion
Dado que los incisos c y e hablan de la misma ecuacion de recurrencia, vamos a resolverla en este momento:
xn+2 + 2xn+1 + xn = 4; x0 + x1 = 2. Utilizaremos el metodo del homogeneo para resolver ecuaciones de recurrencia.
Xhn) xn+2 + 2xn+1 + xn = 0
Su ecuacion caracteristica es r2 + 2r + 1 = 0. Utilizando una calculadora cientifica, podemos resolverla. Llegamos 
a que r1, 2 = -1. Entonces la parte homogenea sera:
Xhn = A(-1)n + Bn(-1)n
Xpn) Como la ecuacion esta igualada a 4, entonces la solucion sera una constante C.
C + 2C + C = 4
4C = 4
C = 1
Xpn = 1
En definitiva: xn = A(-1)n + Bn(-1)n + 1
Ahora, como x0 + x1 = 2, es lo mismo que x1 = 2 – x0. Armemos un sistema de ecuaciones:
• x0 = A + 1
70
• 2 – x0 = - A – B + 1
Reemplazando x0 en la ecuacion de abajo:
2 – A – 1 = - A – B + 1
1 – A = - A – B + 1
- A = - A – B
B = 0
Entonces xn = A(-1)n + 1
b) Falso. Una muy buena idea seria graficar el diagrama de Hasse de esta algebra de Boole, ¿no?
Dada las definiciones de los conjuntos dados, el primer conjunto estara
compuesto por {a, a + b, a + c, 1}, mientras que el segundo estara
compuesto por {b, a + b, b + c, 1}. La interseccion de estos conjuntos
dara el conjunto {a + b, 1}.
Tarea: Probar que, definitivamente, los dos conjuntos dados por la
consigna estan compuestos por esos elementos. Pista: apliquen la
definicion de orden natural a los distintos elementos del algebra según
diga cada conjunto.
c) Falso. Ya que hemos resuelto la ecuacion de recurrencia, nos quedo xn = A(-1)n + 1. A simple vista podemos 
notar que para A != 0, xn oscila entre 1 + A y 1 – A. De esta manera, mientras A != 0, la solucion no sera 
convergente.
d) Falso. xn+2 + axn+1 + bxn = cn; un = (1 – n)2, vn = 1 – 2n.
Dado que un y vn son soluciones de la ecuacion, la resta sera solucion del homogeneo.
= un - vn
= (1 – n)2 – (1 – 2n)
= 1 – 2n + n2 – (1 – 2n)
= n2
Entonces:
(n + 2)2 + a(n + 1)2 + bn2 = 0
n2 + 4n + 4 + an2 + 2an + a + bn2 = 0
(1 + a + b)n2 + (4 + 2a)n + (4 + a)1 = 0
• 1 + a + b = 0
• 4 + 2a = 0
• 4 + a = 0
Igualemos las dos ultimas ecuaciones:
71
4 + 2a = 4 + a
2a = a
2 = 1
Hemos llegado a un absurdo. Por ende, no existeuna ecuacion que satisfaga lo pedido en la proposicion.
e) Verdadero. Hemos notado que xn = A(-1)n + 1. Cuando A = 0, xn = 1, por lo cual se encuentra acotada entre 1 
y 1 (suena raro, pero es asi). Cuando A != 0, xn se encontrara acotado entre 1 + A y 1 – A.
f) Falso. Habra que desarrollar un poco las proposiciones dadas para llegar a algo.
= (p ↑ q) ↑ (pr)
= ( (pq)’(pr) )’ (Definicion de funcion de Sheffer)
= pq + (pr)’ (P. De Morgan)
= pq + p’ + r’ (P. De Morgan)
A simple vista, pareciese que pq + p’ + r’ != p’ + q + r’. Pero sigamos desarrollando un poco mas:
= pq + p’ + r’
= pq + p’ + p’q + r’ (P. Absorcion)
= (p + p’)q + p’ + r’ (P. Distributiva)
= q + p’ + r’ (P. Complemento)
Ahora si. Llegamos a la conclusion de que ambos terminos son iguales.
g) Falso. Siendo M= A∈B(2x 2) , habra que probar si R / ARB sii det(A) = det(B) es una relacion de 
equivalencia:
• Reflexividad: ARA sii det(A) = det(A). Evidentemente, verdadero para toda matriz posible.
• Simetria: Si det(A) = det(B), entonces det(B) = det(A). Nuevamente, verdadero.
• Transitividad: Si det(A) = det(B) y det(B) = det©, entonces det(A) = det(C). Verdaderisimo.
R es una relacion de equivalencia. Ahora, dado a que las clases de equivalencia estan determinadas por el valor del
determinante de las matrices que las componen, y estamos ante una matriz de 2x2 binaria, recordando que la 
formula del determinante de una matriz de 2x2 es ad – bc, entonces tenemos las siguientes posibilidades:
• ad = 1, bc = 1: det(A) = 0.
• ad = 1, bc = 0: det(A) = 1.
• ad = 0, bc = 1: det(A) = -1.
• ad = 0, bc = 0: det(A) = 0.
Eso quiere decir que det (A )⊂(−1, 0 ,1) ,∀ A∈M . En consecuencia, solo habra 3 tipos de clases de 
equivalencia, siendo el cardinal del conjunto cociente |M/R| = 3.
72
Resolucion
Se viene uno picante…
Dentro del dominio Df contenido en ℝ de la funcion f: Df → ℝ , la relacion xSy se da sii f(x) ≤ f(y).
Para cada opcion, vamos a definir bien cada parte.
a) Falso. Grafiquemos f(x).
Comprobemos que S es una relacion de orden,
para una f: R+ → R:
• Reflexividad: f(x) ≤ f(x). Cierto, dado que
f(x) = f(x).
• Antisimetria: Si f(x) ≤ f(y) y f(y) ≤ f(x),
entonces x = y. Claramente cierto por
como esta definida la relacion. La unica
forma para que se cumpla que f(x) ≤ f(y)
y f(y) ≤ f(x) es que x = y (al menos bajo
esta funcion f).
• Transitividad: Si f(x) ≤ f(y) y f(y) ≤ f(z),
y f(x) ≤ f(z). Dado a que f es una funcion
monotona decreciente, esta propiedad se
cumple.
Hemos probado que S es una relacion de orden. Ahora, ¿cual es el conjunto de cotas superiores de {5}? Seran 
todos los x tal que f(5) ≤ f(x), y este conjunto esta compuesto por todas las x que sean menores a 5; es decir: (0, 
5].
73
b) Falso. Proponiendo una f: R → R / f(x) = x2, Podemos notar que esta funcion no cumple con la propiedad de 
antisimetria: f(-1) ≤ f(1) y f(1) ≤ f(-1), y sin embargo -1 ≠ 1.
c) Falso. Definen f(x) = xex. Grafiquemos la funcion:
Vamos a ver si S es una relacion de orden bajo esta
funcion f:
• Reflexividad: f(x) ≤ f(x), porque valen
exactamente lo mismo.
• Antisimetria: Encontrar un valor exacto
para contradecir esta propiedad esta dificil.
Pero pueden ver que entre -∞ y 0 la
funcion pasa de ser decreciente a creciente.
Por lo que habran unas x e y / f(x) = f(y) y 
x ≠ y. Una buena forma de probar esto
analiticamente seria analizando la imagen
de f(x) en (-∞, 0], los limites lim
x →−∞
f (x ) y lim
x=0
f (x) , y su primera derivada en dicho rango.
Por no cumplir la propiedad de antisimetria, esta proposicion es falsa.
d) Falso. Jeje, miren el inciso b.
e) Verdadero. La definicion de inyectividad de una funcion es cuando a elementos distintos del Dominio le 
corresponden distintos elementos de la imagen. Es decir que si f(a) = f(b), entonces a = b. Teniendo esta regla en 
mente, verifiquemos si todas las funciones inyectivas son de orden:
• Reflexividad: esto es cierto, incluso si f no es reflexiva. Para todo x, f(x) ≤ f(x).
• Antisimetria: “Si f(x) ≤ f(y) y f(y) ≤ f(x), entonces x = y”. Que f(x) ≤ f(y) y f(y) ≤ f(x) implica que f(x) = 
f(y) (como ya hemos visto varias veces anteriormente). Y por definicion de inyectividad, esta propiedad 
se cumple.
• Transitividad: “Si f(x) ≤ f(y) y f(y) ≤ f(z), entonces f(x) ≤ f(z)”. Sencillamente, f(x) ≤ f(y) ≤ f(z), asi que se 
cumple.
74
Queda probando entonces que para toda funcion inyectiva, S es una relacion de orden.
g) Falso. Todas estas veces que hemos probado que S es relacion de orden, hemos probado que S es reflexiva y 
transitiva para cualquier tipo de funcion. De hecho, si observan la ultima justificacion en el inciso anterior, notaran
que S es reflexiva y transtiva para toda funcion f: Df → R. Solo nos queda probar que, para cualquier f, S sea 
simetrica:
• Simetria: “Si f(x) ≤ f(y), entonces f(y) ≤ f(x)”. Esto es completamente falso, dado que solo se cumpliria si 
f(x) = f(y). Pero ya hemos vistos varios ejemplos donde esto no se cumple.
75
Resolucion
a) Verdadero. Como hemos hecho en ejercicios anteriores, analicemos que restricciones nos impone la ley de 
membresia de F:
Llamemos w(n) a los vertices que deg(w(n)) = n, solo por comodidad. Tenemos un w(1) y un w(5). Dado que n(G)
= 6, w(5) se unira con todos los vertices. En consecuencia, w(5) y w(1) estaran unidos mediante una arista). Por 
otra parte, poseemos un w(3), que se encontrara unido a w(5) pero no a w(1). Por ende, tendra dos aristas 
conectadas a w(a), w(b), w(c), lo que provocara que a = 1, b = 2 y c = 2 (no necesariamente. Esto quiere decir que 
estos tres vertices tendran estos grados, pero no exactamente los marcados). Si sumamos incrementamos un grado 
de dos vertices distintos, simulariamos el agregado de una arista al grafo, por lo que se me ocurren las siguientes 
sucesiones graficas:
• (1, 1, 2, 2, 3, 5)
• (1, 2, 2, 3, 3, 5)
• (1, 1, 3, 3, 3, 5)
• (1, 3, 3, 3, 3, 5)
Hasta ahora tenemos 4 sucesiones graficas distintas, lo cual indicaria que hay al menos 4 grafos no isomorfos 
pertenecientes a F, y por ende, |F/R| tiene cardinal de a menos 4. Grafiquemos estos grafos:
76
Pero no nos quedemos solo con estos grafos. ¿Existira alguno mas que no sea isomorfos a estos cuatro? Ya 
sabemos que no puede haber otros con una sucesion grafica distinta a la de estos, por lo que, de existir un grafo 
nuevo no isomorfo, este debera tener alguna de estas cuatro sucesiones graficos, pero diferir de ese en alguna de 
estas caracteristicas: radio, diametro, cantidad y longitud de ciclos, numero cromatico, indice cromatico, espectro.
Lamentablemente no se me ocurre otra forma analitica de proseguir. Pero si podemos afirmar algunas cosas 
interesantes: 
• El radio y el diametro es el mismo para todos los grafos pertenecientes a F (mas adelante explicare por 
que), por lo que descartamos fijarnos en el radio y el diametro para determinar el isomorfismo.
• No existen dos grafos no isomorfos que posean sucesion grafica (1, 1, 2, 2, 3, 5). Esto es debido a que no 
importa que vertices elijas para asignarle el grado 3: todos seran isomorfos entre si. Comiencen 
graficando w(1) y w(5), y veran que no importa cual de los cuatros vertices eligen para w(3), todos seran 
isomorfos entre si.
• No existen dos grafos no isomorfos que posean sucesion grafica (1, 3, 3, 3, 3, 5). Esto es debido 
nuevamente a las restricciones que w(1) y w(5) nos presentan. Nuevamente, partan de graficar w(1) y 
w(5), y luego grafiquen los demas vertices. Siempre se llega al mismo grafo (ignorando los isomorfos).
• No existen dos grafos no isomorfos que posean sucesion grafica (1, 1, 3, 3, 3, 5). Esto es debido a que, 
partiendo del grafo de sucesion (1, 1, 2, 2, 3, 5), se añade una arista en los unicos vertices de grado 2, 
siendo la unica forma de llegar a la sucesion grafica (1, 1, 3, 3, 3, 5) (ignorando grafos isomorfos).
• No existen dos grafos no isomorfos que posean sucesion grafica (1, 2, 2, 3, 3, 5). Esto debido a que 
partiendo del grafo de sucesion (1, 1, 2, 2, 3, 5), solo se pueden tomar dos configuraciones