Nombre:......................................

Clase:..........................................

gga
Universidad FPT

Matemáticas
discretas y sus aplicaciones
Cuaderno de ejercicios

Trần Trọng Huỳnh - 2020

1
Capítulo 1: Los fundamentos: lógica y pruebas
1.1 Lógica proposicional
1. ¿Cuáles de estas oraciones son proposiciones? ¿Cuáles son los valores de verdad de
aquellas que son proposiciones?
a) Boston es la capital de Massachusetts. b) Miami es la capital de Florida.
c) 2 + 3 = 5. d) 5 + 7 = 10.
e) x + 2 = 11. f ) Responde esta pregunta.
2. ¿Cuál es la negación de cada una de estas proposiciones?

a) Mei tiene un reproductor MP3. b) No hay contaminación en Nueva

Jersey. d) El verano en Maine es caluroso y
c) 2 + 1 = 3.
soleado.
3. Sean p y q las proposiciones
p:Compré un billete de lotería esta semana.
q : Gané el premio mayor del millón de dólares.
Expresa cada una de estas proposiciones como una oración en inglés.

a) p b) p ∨ q c) p → q

d) p ∧ q e) p ↔ q f)p→q
g) p ∧ q h) p ∨ (p ∧ q)
4. Sean p y q las proposiciones
p :Está bajo cero.
q :Está nevando.
Escribe estas proposiciones utilizando p y q y conectivos lógicos (incluyendo negaciones).
a) Hace bajo cero y está nevando.
b) Hace bajo cero pero no nieva.
c) No hace bajo cero y no está nevando.
d) O está nevando o hace frío (o ambas cosas).
5. Sean p y q las proposiciones
p : Conduces a más de 65 millas por hora.

2
q :Te ponen una multa por exceso de velocidad.
Escribe estas proposiciones utilizando p y q y conectivos lógicos (incluyendo negaciones).
a) No conduzcas a más de 65 millas por hora.
b) Conduces a más de 65 millas por hora, pero no recibes una multa por exceso de
velocidad.
c) Recibirás una multa por exceso de velocidad si conduces a más de 65 millas por hora.
d) Si no conduce a más de 65 millas por hora, no recibirá una multa por exceso de
velocidad.
e) Conducir a más de 65 millas por hora es suficiente para recibir una multa por exceso de
velocidad.
f ) Recibes una multa por exceso de velocidad, pero no conduces a más de 65 millas por hora.
g) Siempre que recibes una multa por exceso de velocidad, estás conduciendo a más de 65
millas por hora.
6. Determinar si estos bicondicionales son verdaderos o falsos.
a) 2 + 2= 4 Si y solo si 1 + 1 = 2.
b) 1 + 1 = 2 Si y solo si 2 + 3 = 4.
c) 1 + 1= 3 Si y solo si Los monos pueden volar.
Capítulo 1: Los fundamentos: lógica y pruebas......................................................................................2
1.1 Lógica proposicional.....................................................................................................................2
1.2- Equivalencias proposicionales..............................................................................................8
1.4 Predicados y cuantificadores.........................................................................................................9
1.5 Reglas de inferencia....................................................................................................................11
Capítulo 2: Estructuras básicas: conjuntos, funciones, secuencias y sumas.........................................13
2.1 Conjuntos...............................................................................................................................13
2.2 Operaciones de conjuntos......................................................................................................16
2.3 Funciones...............................................................................................................................17
d) f
(n)=...............................................................................................................................................17
2.4 Secuencias y sumas................................................................................................................19
Capítulo 3: Los fundamentos: algoritmos, números enteros y matrices...............................................21
3.1 Algoritmos..............................................................................................................................21
3.2 El crecimiento de las funciones..............................................................................................23

3
 3.3 Complejidad de los algoritmos....................................................................................................24
3.4 Los números enteros y la división...............................................................................................25
3.5 Números primos y máximos comunes divisores.........................................................................27
3.6 Números enteros y algoritmos....................................................................................................29
Capítulo 4: Inducción y recursión.........................................................................................................30
4.1 Inducción matemática.................................................................................................................30
4.2 Inducción fuerte..........................................................................................................................31
4.3 Definiciones recursivas e inducción estructural.....................................................................32
4.4 Algoritmos recursivos............................................................................................................34
Capítulo 5-7: Contando.........................................................................................................................35
5.1 Los conceptos básicos del conteo...............................................................................................35
7.1 Relaciones de recurrencia......................................................................................................38
7.3 Algoritmos de divide y vencerás y relaciones de recurrencia.....................................................39
Capítulo 8: Relaciones..........................................................................................................................40
8.1 Relaciones y sus propiedades.................................................................................................40
8.2 Relaciones n-arias y sus aplicaciones....................................................................................42
8.3 Representando relaciones.......................................................................................................44
<1 1
1............................................................................................................................................49
101A..................................................................................................................................................49
8.5 Relaciones de equivalencia.........................................................................................................51
Capítulo 9: Gráficos..............................................................................................................................56
9.1 Gráficos y modelos de gráficos..............................................................................................56
9.2 Terminología de gráficos y tipos especiales de gráficos........................................................57
9.3 Representación de gráficos e isomorfismo de gráficos..........................................................60
9.4 Conectividad..........................................................................................................................64
9.5 Caminos de Euler y Hamilton................................................................................................66
9.6 Problemas de la ruta más corta...............................................................................................68
Capítulo 10: Árboles.............................................................................................................................69
2.1 Introducción a los árboles......................................................................................................69
10.2 Aplicaciones de los árboles.......................................................................................................70
10.3 Travesía de árboles.............................................................................................................72
10.4 Árboles de expansión.........................................................................................................75
10.4 Árboles de expansión mínimos.................................................................................................82
a)
b) Si los monos pueden volar, entonces 1 + 1 = 3.

4
7. Determina si cada una de estas afirmaciones condicionales es verdadera o falsa.
a) Si 1 + 1 = 3, entonces existen los unicornios. b) Si 1 + 1 = 3, entonces los perros pueden
volar.
c) Si 1 + 1 = 2, entonces los perros pueden volar. d) Si 2 + 2 = 4, entonces 1 + 2 = 3.
8. Escribe cada una de estas afirmaciones en la forma “si p, entonces q”
a) Es necesario lavar el coche del jefe para ascender.
b) Los vientos del sur implican un deshielo primaveral.
c) Una condición suficiente para que la garantía sea válida es que hayas comprado el
ordenador hace menos de un año.
d) Willy es atrapado cada vez que hace trampa.
e) Solo podrás acceder al sitio web si pagas una tarifa de suscripción.
f ) Para ser elegido es necesario conocer a las personas adecuadas.
g) Carol se marea cada vez que está en un barco.
9. ¿Cuántas filas aparecen en una tabla de verdad para cada una de estas proposiciones
compuestas?

a) p → p b) (p ∨ r) ∧ (q ∨ s) c) q ∨ p ∨ s ∨ r ∨ t ∨ u

d) (p ∧ r ∧ t) ↔ (q ∧ t) e) (q → p) ∨ (p → q) f) (p ∨ t) ∧ (p ∨ s)

g) (p → r) ∨ (s → t) ∨ (u → v) h) (p ∧ r ∧ s) ∨ (q ∧ t) ∨ (r ∧ t)
10. Construya una tabla de verdad para cada una de estas proposiciones compuestas.

a) p ∧ p b) p ∨ pc) (p ∨ q) → q d) (p ∨ q) → (p ∧ q)
e) (p → q) ↔ (q → p) f) (p → q) → (q → p)
11. Construya una tabla de verdad para cada una de estas proposiciones compuestas.

a) p → pb) p ↔ p c) p ⊕ (p ∨ q) d) (p ∧ q) → (p ∨ q)

e) (q → p) ↔ (p ↔ q) f) (p ↔ q) ⊕ (p ↔ q)
12. ¿Cuál es el valor de x después de que se encuentra cada una de estas afirmaciones en un
programa de computadora, si x = 1 antes de que se alcance la afirmación?
a) si x + 2 = 3 entonces x := x + 1

5
b) si (x + 1 = 3) O (2x + 2 = 3) entonces x := x + 1
c) si (2x + 3 = 5) Y (3x + 4 = 7) entonces x := x + 1
d) si (x + 1 = 2) XOR (x + 2 = 3) entonces x := x + 1

6
13. Encuentre el OR bit a bit, el AND bit a bit y el XOR bit a bit de cada uno de estos pares
de cadenas de bits.
a) 101 1110, 010 0001 b) 1111 0000, 1010 1010
c) 00 0111 0001, 10 0100 1000 d) 11 1111 1111, 00 0000 0000
15. Evalúa cada una de estas

b) (0 1111 ∧ 1 0101) ∨ 0 1000

expresiones.

a) 1 1000 ∧ (0 1011 ∨ 1 1011)

d) (1 1011 ∨ 0 1010) ∧ (1 0001 ∨ 1
c) (0 1010 ⊕ 1 1011) ⊕ 0 1000 1011)

7
1.2- Equivalencias proposicionales
1. Demuestre que cada una de estas afirmaciones condicionales es una tautología utilizando
tablas de verdad.

a) (p ∧ q) → p b) p → (p ∨ q) c) p → (p → q)

d) (p ∧ q) → (p → q) e) (p → q) → p f) (p → q) → q

2. Demuestre que cada una de estas afirmaciones condicionales es una tautología utilizando
tablas de verdad.

a) [p ∧ (p ∨ q)] → q b) [(p → q) ∧ (q → [a)]→(pag→ a)

c) [p ∧ (p → q)] → q d) [(p ∨ q) ∧ (p → r)∧ (q→ [a)] →r

3. Determinar si (pág. ∧ (pág →q))→ q es una tautología.

4. Determinar si (q∧ (pág → q)) → p es una tautología.

5. Demuestre que (p ∨ q) ∧ (p ∨ r) → (q ∨ r) es una tautología.

6. Demuestre que (p → q) → r y p → (q → r) no son lógicamente equivalentes.

7. Demuestre que (p ∧ q) → r y (p → r) ∧ (q → r) no son lógicamente equivalentes.

8. Demuestre que (p → q) → (r → s) y (p → r) → (q → s) no son lógicamente equivalentes.

9. Encuentra el dual de cada una de estas proposiciones compuestas.

a) p ∨ q b) p ∧ (q ∨ (r ∧ T)) c) (p ∧ q) ∨ (q ∧ F)

8
1.4 Predicados y cuantificadores
1. Sea P(x) la afirmación “x ≤ 4”. ¿Cuáles son estos valores de verdad?
a) P(0) b) P(4) c) P(6)
2. Sea P(x) la afirmación “la palabra x contiene la letra a”. ¿Cuáles son estos valores de
verdad?
a) P (naranja) b) P (limón) c) P (verdadero) d) P (falso)
3. Sea Q(x, y) el enunciado “x es la capital de y”. ¿Cuáles son estos valores de verdad?
a) Q(Denver, Colorado) b) Q(Detroit, Michigan)
c) Q(Massachusetts, Boston) d) Q(Nueva York, Nueva York)
4. Indique el valor de x después de que se ejecute la declaración si P(x) entonces x := 1,
donde P(x) es la declaración “x > 1”, si el valor de x cuando se alcanza esta declaración es
a) x = 0. b) x = 1. c) x = 2.
5. Sea P(x) la afirmación “x pasa más de cinco horas cada día de la semana en clase”, donde
el dominio de x consiste en todos los estudiantes. Expresa cada uno de estos

a) ∃xP(x) b) ∀xP(x) c) ∃x P(x) d) ∀x P(x)

6. Traduzca estas afirmaciones al español, donde C(x) es “x es un comediante” y F(x) es “x
es divertido” y el dominio está formado por todas las personas.

a) ∀x(C(x) → F(x)) b) ∀x(C(x) ∧ F(x))

c) ∃x(C(x) → F(x)) d) ∃x(C(x) ∧ F(x))
x2
7. Sea P(x) la afirmación “x = ”. Si el dominio está formado por números enteros, ¿cuáles
son estos valores de verdad?
a) P(0) b) P(1) c) P(2)
d) P(-1) e) ∃xP(x) f ) ∀xP(x)
8. Sea Q(x) la afirmación “x + 1 > 2x”. Si el dominio consta de todos los números enteros,
¿cuáles son estos valores de verdad?

a) Q(0) b) Q(-1) c) Q(1)

d) ∃xQ(x) e) ∀xQ(x) f ) ∃xQ(x)

9. Determinar el valor de verdad de cada una de estas afirmaciones si el dominio consta de

9
todos los números enteros.

a) ∀n(n + 1 > n) b) ∃n(2n = 3n) c) ∃n(n = -n) c) ∀n(3n ≤ 4n)

10. Determine el valor de verdad de cada una de estas afirmaciones si el dominio consta de
todos los números reales.

a) ∃x(x3 = -1) b) ∃x(x4 < x2)

c) ∀x((-x)2 = x2) d) ∀x(2x > x)

11. Determine el valor de verdad de cada una de estas afirmaciones si el dominio de todas
las variables consta de todos los números enteros.

a) ∀n(n2 ≥ 0) b) ∃n(n2 = 2) c) ∀n(n2 ≥ n) d) ∃n(n2 < 0)

12. Supongamos que el dominio de la función proposicional P(x) consiste en los números
enteros 0, 1, 2, 3 y 4. Escribe cada una de estas proposiciones utilizando disyunciones,
conjunciones y negaciones.

a) ∃xP(x) b) ∀xP(x) c) ∃xP(x)

d) ∀xP(x) e) ∃xP(x) f ) ∀xP(x)

13. Supongamos que el dominio de la función proposicional P(x) consiste en los números
enteros 1, 2, 3, 4 y 5. Exprese estas afirmaciones sin utilizar cuantificadores, utilizando
únicamente negaciones, disyunciones y conjunciones.

a) ∃xP(x) b) ∀xP(x) c) ∃xP(x) d) ∀xP(x)

1
0
1.5 Reglas de inferencia
1. Encuentre la forma argumental para el siguiente argumento y determine si es válido.
¿Podemos concluir que la conclusión es verdadera si las premisas son verdaderas?

Si Sócrates es humano, entonces Sócrates es mortal.

Sócrates es humano.

∴ Sócrates es mortal.
2. Utilice reglas de inferencia para demostrar que las hipótesis “Randy trabaja duro”, “Si
Randy trabaja duro, entonces es un chico aburrido” y “Si Randy es un chico aburrido,
entonces no conseguirá el trabajo” implican la conclusión “Randy no conseguirá el trabajo”.
3. Para cada una de estas colecciones de premisas, ¿qué conclusión o conclusiones
relevantes se pueden extraer? Explique las reglas de inferencia utilizadas para obtener cada
conclusión de las premisas.
a) “Si me tomo el día libre, llueve o nieva”. “Me tomé libre el martes o me tomé libre el
jueves”. “El martes hacía sol”. “El jueves no nevó”.
b) “Si como comida picante, entonces tengo sueños extraños”. “Tengo sueños extraños si
hay truenos mientras duermo”. “No tuve sueños extraños”.
c) “O soy inteligente o tengo suerte”. “No tengo suerte”. “Si tengo suerte, ganaré la lotería”
d) “Cada estudiante de informática tiene un ordenador personal”. “Ralph no tiene un
ordenador personal”. “Ann tiene una computadora personal”.
e) “Lo que es bueno para las corporaciones es bueno para Estados Unidos”. “Lo que es
bueno para Estados Unidos es bueno para ti”. “Lo bueno para las corporaciones es que
compren muchas cosas”.
f ) “Todos los roedores roen su comida”. “Los ratones son roedores”. “Los conejos no roen su
comida”. “Los murciélagos no son roedores.
4. Determina si cada uno de los siguientes argumentos es válido o no.
a) A todos los loros les gusta la fruta. Mi mascota no es un loro. Por lo tanto, a mi pájaro
mascota no le gusta la fruta.
b) Todo aquel que come granola todos los días es saludable. Linda no está sana. Por eso,
Linda no come granola todos los días.
c) Ningún hombre es una isla. Manhattan es una isla. Por lo tanto, Manhattan no es un
hombre.

1
1
d) Un coche descapotable es divertido de conducir. El coche de Isaac no es un descapotable.
Por lo tanto, el coche de Isaac no es divertido de conducir.
e) Si Mai sabe francés, Mai es inteligente. Pero Mai no sabe francés. Entonces ella no es
inteligente.
f) Lin no puede ir a pescar si no tiene una bicicleta. La semana pasada, Lin fue a pescar con
sus amigos. Por eso, ella tiene una bicicleta.

1
2
Capítulo 2: Estructuras básicas: conjuntos, funciones,
secuencias y sumas
2.1 Conjuntos
1. Enumere los miembros de estos conjuntos.
a) {x | x es un número real tal que x2 = 1}
b) {x | x es un entero positivo menor que 12}
c) {x | x es el cuadrado de un entero y x < 100}
d) {x | x es un entero tal que x2 = 2}
2. Para cada uno de los siguientes conjuntos, determine si 2 es un elemento de ese conjunto.
a) {x ∈ R | x es un entero mayor que 1} b) {x ∈ R | x es el cuadrado de un entero}
c) {2,{2}} d) {{2},{{2}}} e) {{2},{2,{2}}} f ) {{{2}}}
3. Determina si cada una de estas afirmaciones es verdadera o falsa.
a) 0 ∈ ∅ b) ∅ ∈ {0} do) {0} ⊂ ∅ d) ∅ ⊂ {0}
Capítulo 1: Los fundamentos: lógica y pruebas....................................................................................2
1.1 Lógica proposicional...................................................................................................................2
1.2- Equivalencias proposicionales............................................................................................8
1.4 Predicados y cuantificadores.......................................................................................................9
1.5 Reglas de inferencia..................................................................................................................11
Capítulo 2: Estructuras básicas: conjuntos, funciones, secuencias y sumas.......................................13
2.1 Conjuntos.............................................................................................................................13
2.2 Operaciones de conjuntos....................................................................................................16
2.3 Funciones.............................................................................................................................17
d) f
(n)=.............................................................................................................................................17
2.4 Secuencias y sumas..............................................................................................................19
Capítulo 3: Los fundamentos: algoritmos, números enteros y matrices.............................................21
3.1 Algoritmos............................................................................................................................21
3.2 El crecimiento de las funciones............................................................................................23
3.3 Complejidad de los algoritmos..................................................................................................24
3.4 Los números enteros y la división.............................................................................................25

1
3
 3.5 Números primos y máximos comunes divisores.......................................................................27
3.6 Números enteros y algoritmos..................................................................................................29
Capítulo 4: Inducción y recursión.......................................................................................................30
4.1 Inducción matemática...............................................................................................................30
4.2 Inducción fuerte........................................................................................................................31
4.3 Definiciones recursivas e inducción estructural...................................................................32
4.4 Algoritmos recursivos..........................................................................................................34
Capítulo 5-7: Contando.......................................................................................................................35
5.1 Los conceptos básicos del conteo.............................................................................................35
7.1 Relaciones de recurrencia....................................................................................................38
7.3 Algoritmos de divide y vencerás y relaciones de recurrencia...................................................39
Capítulo 8: Relaciones........................................................................................................................40
8.1 Relaciones y sus propiedades...............................................................................................40
8.2 Relaciones n-arias y sus aplicaciones..................................................................................42
8.3 Representando relaciones.....................................................................................................44
<1 1
1..........................................................................................................................................49
101A................................................................................................................................................49
8.5 Relaciones de equivalencia.......................................................................................................51
Capítulo 9: Gráficos............................................................................................................................56
9.1 Gráficos y modelos de gráficos............................................................................................56
9.2 Terminología de gráficos y tipos especiales de gráficos......................................................57
9.3 Representación de gráficos e isomorfismo de gráficos........................................................60
9.4 Conectividad........................................................................................................................64
9.5 Caminos de Euler y Hamilton..............................................................................................66
9.6 Problemas de la ruta más corta.............................................................................................68
Capítulo 10: Árboles...........................................................................................................................69
2.1 Introducción a los árboles....................................................................................................69
10.2 Aplicaciones de los árboles.....................................................................................................70
10.3 Travesía de árboles...........................................................................................................72
10.4 Árboles de expansión.......................................................................................................75
10.4 Árboles de expansión mínimos...............................................................................................82

4. ¿Cuántos elementos tiene cada uno de estos conjuntos donde a y b son elementos
distintos?

1
4
a) P({a, b, {a, b}}) b) P({∅, a, {a}, {{a}}}) c) P(P(∅))
5. Encuentra A2 y A3 si
a) A = {1, 3} b) A = {1, a}

6. Sea A = {1,2,3) y B =
{1, a ). Qué es el cardinalidad de
cada uno de estos ¿conjuntos?

a) A x B b) A2 c) P (B) d) P (BxA) e) A • B
7. Encuentra la verdad conjunto de cada uno de estos predicados donde esta el dominio
el colocar de números enteros.
a) P(x): x2 < 3 b) Q(x): x2
>x c) R(x): 2x + 1 = 0

1
5
2.2 Operaciones de conjuntos
1. Sea A = {1, 2, 3, 4, 5} y B = {0, 3, 6}. Encontrar
a) A ∪ B b) A ∩ B c) A - B d) B - A.
2. Sea A = {a, b, c, d, e} y B = {a, b, c, d, e, f, g, h}. Encontrar
a) A ∪ B b) A ∩ B c) A - B d) B - A.
3. Encuentra los conjuntos A y B si A - B = {1, 5, 7, 8}, B - A = {2, 10} y A ∩ B = {3,
6, 9}.
4. Sean A y B conjuntos. Demuestre que
a) (A ∩ B) ⊆ A b) A ⊆ (A ∪ B) c) A - B ⊆ A
d) A ∩ (B - A) = ∅ e) A ∪ (B - A) = A ∪ B f) A ⊕ B = (A ∪ B) - (A ∩ B).
5. Supongamos que el conjunto universal es U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Exprese
cada uno de estos conjuntos con cadenas de bits donde el bit i de la cadena es 1 si i está en
el conjunto y 0 en caso contrario.
a) {3, 4, 5} b) {1, 3, 6, 10} c) {2, 3, 4, 7, 8, 9}

1
6
2.3 Funciones
1. ¿Por qué f no es una función de R a R si

a) ¿f(x) = b) f(x) = x ? c) f(x) = + x2 +1

1/x?Determinar si f es una función de Z a R si
2.

a) f(n) = ±n b) f(n)= n2+1 c) f ( 1

número 2-

3. Encuentra estos valores

n) = 4

a) r1.1i b) -0, 11 do)

d)
R4i L3. 21
mi) 5.2 1 e) L2J

4. Determinar si cada una de estas funciones desde {a, b, c, d} hasta sí misma es

biunívoca (sobre) a) f (a) = b, y (b) = a, f(c) = c, f(d) = d
b)f (a) =b, y (b) = b, f(c) = d, f(d) = c
c)f (a) =d, y (b) = b, f(c) = c, f(d) = d
5. Determinar si cada una de estas funciones de Z a Z es biunívoca (sobre)

a) f(n) = n - 1 b) f(n) = n2 + 1 c) f(n) = n3 d) f

(n)=

6. Determinar si f : Z × Z → Z es sobreyectiva si
a) f(m, n) = 2m - n b) f(m, n) = m2 - n2 c) f(m, n) = m + n + 1
c) f(m, n) = |m| - |n| e) f(m, n) = m2 - 4 f) f(m, n) = m + n
7. Determinar si cada una de estas funciones es una biyección de R a R.
a) f(x) = -3x + 4 b) f(x) = -3x2 + 7 c) f(x) = (x + 1)/(x + 2) d) f(x) = x5 + 1
8. Sea S = {-1, 0, 2, 4, 7}. Encuentra f (S) si a) f (x) = 1 b) f (x) = 2x + 1
9. Sea f la función de R a R
definida por f (x) = x2. Encontrar
c)
f(x)=

a) f-1({1}) b) f -1({x | 0 < x < 1}) c) f -1({x | x > 4})

1
7
2.4 Secuencias y sumas
1. 1. Encuentra estos términos de la secuencia {an}, donde an = 2 (-3)n + 5n.

a) a0 b)a1 c)a4 d)a5

2. ¿Cuál es el término a8 de la secuencia {an} si an es igual a

a) ¿2n-1? b) 7? c) 1 + (-1)n? d)-(-2)n?

3. Encuentre los primeros cinco términos de la secuencia definida por cada una de estas
relaciones de recurrencia y condiciones iniciales.
2
a) an = ban-1, ao = 2 b) an = an -1, a1 = 2 c) un = un-1 + 3an-2, año = 1, ai = 2

4. Encuentra la solución a cada una de estas relaciones de recurrencia y condiciones

iniciales.

a) an = -an-1, a0 = 5 b) un = un-1 + 3, a0 = 1 c) un = un-1 - n, a0 = 4

d ) an = 2nan-1, a0 = 3 mi) un = 5an-1 - 6an-2, a0 = 2, a1 = -1

5. ¿Cuales son los valores de estas sumas?

Capítulo 1: Los fundamentos: lógica y pruebas.....................................................................................2

1.1 Lógica proposicional.....................................................................................................................2
1.2- Equivalencias proposicionales.............................................................................................8
1.4 Predicados y cuantificadores.........................................................................................................9
1.5 Reglas de inferencia....................................................................................................................11
Capítulo 2: Estructuras básicas: conjuntos, funciones, secuencias y sumas........................................13
2.1 Conjuntos...............................................................................................................................13
2.2 Operaciones de conjuntos......................................................................................................16
2.3 Funciones...............................................................................................................................17
d) f
(n)=...............................................................................................................................................17

1
8
 2.4 Secuencias y sumas................................................................................................................19
Capítulo 3: Los fundamentos: algoritmos, números enteros y matrices...............................................21
3.1 Algoritmos.............................................................................................................................21
3.2 El crecimiento de las funciones.............................................................................................23
3.3 Complejidad de los algoritmos...................................................................................................24
3.4 Los números enteros y la división..............................................................................................25
3.5 Números primos y máximos comunes divisores........................................................................27
3.6 Números enteros y algoritmos....................................................................................................29
Capítulo 4: Inducción y recursión........................................................................................................30
4.1 Inducción matemática.................................................................................................................30
4.2 Inducción fuerte..........................................................................................................................31
4.3 Definiciones recursivas e inducción estructural....................................................................32
4.4 Algoritmos recursivos............................................................................................................34
Capítulo 5-7: Contando........................................................................................................................35
5.1 Los conceptos básicos del conteo...............................................................................................35
7.1 Relaciones de recurrencia......................................................................................................38
7.3 Algoritmos de divide y vencerás y relaciones de recurrencia.....................................................39
Capítulo 8: Relaciones..........................................................................................................................40
8.1 Relaciones y sus propiedades.................................................................................................40
8.2 Relaciones n-arias y sus aplicaciones....................................................................................42
8.3 Representando relaciones.......................................................................................................44
<1 1
1...........................................................................................................................................49
101A..................................................................................................................................................49
8.5 Relaciones de equivalencia.........................................................................................................51
Capítulo 9: Gráficos..............................................................................................................................56
9.1 Gráficos y modelos de gráficos..............................................................................................56
9.2 Terminología de gráficos y tipos especiales de gráficos.......................................................57
9.3 Representación de gráficos e isomorfismo de gráficos..........................................................60

1
9
 9.4 Conectividad..........................................................................................................................64
9.5 Caminos de Euler y Hamilton................................................................................................66
9.6 Problemas de la ruta más corta..............................................................................................68
Capítulo 10: Árboles.............................................................................................................................69
2.1 Introducción a los árboles......................................................................................................69
10.2 Aplicaciones de los árboles.......................................................................................................70
10.3 Travesía de árboles.............................................................................................................72
10.4 Árboles de expansión.........................................................................................................75
10.4 Árboles de expansión mínimos.................................................................................................82

Capítulo 3: Los fundamentos: algoritmos, números

enteros y matrices
3.1 Algoritmos
1. Enumere todos los pasos utilizados por el algoritmo "max" para encontrar el máximo de
la lista 1, 8, 12, 9, 11, 2, 14, 5, 10, 4.
2. Diseñe un algoritmo que encuentre la suma de todos los números enteros en una lista.
3. Enumere todos los pasos utilizados para buscar 9 en la secuencia 1, 3, 4, 5, 6, 8, 9, 11
utilizando
a) una búsqueda lineal b) una búsqueda binaria.
4. Describe un algoritmo que inserta un entero x en la posición apropiada en la lista a1, a2, . . .
, an de enteros que están en orden creciente.
5. Utilice la ordenación de burbuja para ordenar 3, 1, 5, 7, 4, mostrando las listas obtenidas
en cada paso.
6. Consideremos el algoritmo de búsqueda lineal:
procedimiento búsqueda lineal(x: entero, a1,a2,...,an: enteros distintos)

2
0
 yo := 1
mientras (i ≤ n y x + ai )
yo := yo + 1
si i ≤ n entonces ubicación := i
De lo contrario, ubicación := 0
lugar de retorno
Dada la secuencia an: 3, 1, 5, 7, 4, 6. ¿Cuántas comparaciones se requieren para buscar x = 7?

2
1
3.2 El crecimiento de las funciones
1. Determinar si cada una de estas funciones es O(x).
a) f(x) = 10 b) f(x) = 3x + 7 c) f(x) = x2 + x + 1 d) f(x) = 5 logx
2. Determinar si cada una de estas funciones es O(x2).
a) f(x) = 17x + 11 b) f(x) = x2 + 1000 c) f (x) = x logaritmo de x
x4

d)
f(x)= 2 y)
f(x)=2x f) ) f(x) = (x3 + 2x)/(2x + 1)

3. Encuentre el menor entero n tal que f (x) sea O(xn) para cada una de estas funciones.
a) f(x) = 2x3 + x2 logaritmo de x b) f(x) = 3x3 + (logx)4
c) f(x) = (x4 + x2 + 1)/(x3 + 1) d) f(x) = (x4 + 5 logx)/(x4 + 1)
4. Determina si x3 es O(g(x)) para cada una de estas funciones g(x).
a) g(x) = x2 b) g(x) = x3 c) g(x) = x2 + x3
c) g(x) = x2 + x4 y) g(x) = 3x f) g(x) = x3/2

5. Ordene las funciones n, 1000 log n, n log n, 2n!, 2n, 3n y n2/1 000 000 en una lista de
modo que cada función sea grande-O de la siguiente función.
6. Proporcione una estimación lo mejor posible para cada una de estas funciones.
a) (n2 + 8)(n + 1) b) (n log n + n2)(n3 + 2) c) (n! + 2n)(n3 + log(n2 + 1))

2
2
3.3 Complejidad de los algoritmos
1. Consideremos el algoritmo:
procedimiento giaithuat(a1, a2, …, an : enteros)
cuenta:= 0
para i:= i a n hacer
si ai > 0 entonces cuenta: = cuenta + 1
imprimir(contar)
Proporcione la mejor complejidad big-O para el algoritmo anterior.
2. Consideremos el algoritmo:
procedimiento GT(n : entero positivo)
F:=1
para i:= 1 a n hacer
F: = F * i
Imprimir(F)
Proporcione la mejor complejidad big-O para el algoritmo anterior.
3. Consideremos el algoritmo:
procedimiento max(a ,a ,...,a : reales )
máximo:=a
para i:=2 a n
si máx
Proporcione la mejor complejidad big-O para el algoritmo anterior.

2
3
3.4 Los números enteros y la división
1. ¿17 divide a cada uno de estos números?
a) 68 b) 84 c) 357 d) 1001
2. ¿Cuáles son el cociente y el resto cuando?
a) 19 es divisible por 7? b) -111 es dividido por 11? c) 789 es dividido por 23?
d) 1001 es divisible por 13? e) 0 es divisible por 19? f ) 3 es dividido por 5?
3. Supongamos que a y b son números enteros, a ≡ 4 (mod 13) y b ≡ 9 (mod 13).
Encuentra el entero c con 0 ≤ c ≤ 12 tal que
a) c ≡ 9a (mód 13). b) c ≡ 11b (mód 13). c) c ≡ a + b (mód 13).
d) c ≡ 2a + 3b (mod 13). e) c ≡ a2 + b2 (mod 13). f ) c ≡ a3 - b3 (mód 13).
4. Evalúa estas cantidades.
a) 13 mod 3 b) -97 mod 11 c) 155 módulo 19 d) -221 módulo 23
5. Encuentra una div m y un módulo m cuando
a) a = -111, m = 99. b) a = -9999, m = 101.
c) a = 10299, m = 999. c) a = 123456, m = 1001.
6. Decide si cada uno de estos números enteros es congruente con 5 módulo 17.
a) 80 b) 103 c)-29 d)-122
7. Encuentra cada uno de estos valores.
a) (992 mod 32)3 mod 15 b) (34 mod 17)2 mod 11
c) (193 mod 23)2 mod 31 d) (893 mod 79)4 mod 26
8. Convierte la expansión decimal de cada uno de estos números enteros en una expansión
binaria.
a) 23 b) 45 c) 241 d) 1025
9. Convierte la expansión binaria de cada uno de estos números enteros en una expansión
decimal.
a) (1 1011)2 b) (10 1011 0101)2
c) (11 1011 1110)2 d) (111 1100 0001 1111)2

2
4
10. Convierte la expansión octal de cada uno de estos números enteros en una expansión
binaria.
a) (572)8 b) (1604)8 c) (423)8 d) (2417)8
11. Convierte cada una de las siguientes expansiones a expansión decimal.
a) (1021)3 b) (325)7 c) (A3)12 d) (401)5 e) (12B7)13
12. Convertir 69 a
a) una expansión binaria b) una expansión de base 6 c) una expansión de base 9
11. Suponga que a mod 3 = 2 y b mod 6 = 4, encuentre ab mod 3.

2
5
3.5 Números primos y máximos comunes divisores
1. Determinar si cada uno de estos números enteros es primo
Capítulo 1: Los fundamentos: lógica y pruebas.................................................................................2
1.1 Lógica proposicional................................................................................................................2
1.2- Equivalencias proposicionales.........................................................................................8
1.4 Predicados y cuantificadores....................................................................................................9
1.5 Reglas de inferencia...............................................................................................................11
Capítulo 2: Estructuras básicas: conjuntos, funciones, secuencias y sumas....................................13
2.1 Conjuntos...........................................................................................................................13
2.2 Operaciones de conjuntos..................................................................................................16
2.3 Funciones...........................................................................................................................17
d) f
(n)=...........................................................................................................................................17
2.4 Secuencias y sumas...........................................................................................................19
Capítulo 3: Los fundamentos: algoritmos, números enteros y matrices..........................................21
3.1 Algoritmos.........................................................................................................................21
3.2 El crecimiento de las funciones.........................................................................................23
3.3 Complejidad de los algoritmos...............................................................................................24
3.4 Los números enteros y la división..........................................................................................25
3.5 Números primos y máximos comunes divisores....................................................................27
3.6 Números enteros y algoritmos................................................................................................29
Capítulo 4: Inducción y recursión....................................................................................................30
4.1 Inducción matemática.............................................................................................................30
4.2 Inducción fuerte......................................................................................................................31
4.3 Definiciones recursivas e inducción estructural................................................................32
4.4 Algoritmos recursivos.......................................................................................................34
Capítulo 5-7: Contando....................................................................................................................35
5.1 Los conceptos básicos del conteo...........................................................................................35
7.1 Relaciones de recurrencia..................................................................................................38
7.3 Algoritmos de divide y vencerás y relaciones de recurrencia................................................39
Capítulo 8: Relaciones.....................................................................................................................40
8.1 Relaciones y sus propiedades............................................................................................40
8.2 Relaciones n-arias y sus aplicaciones................................................................................42
8.3 Representando relaciones..................................................................................................44
<1 1
1.......................................................................................................................................49

2
6
 101A.............................................................................................................................................49
8.5 Relaciones de equivalencia.....................................................................................................51
Capítulo 9: Gráficos.........................................................................................................................56
9.1 Gráficos y modelos de gráficos.........................................................................................56
9.2 Terminología de gráficos y tipos especiales de gráficos...................................................57
9.3 Representación de gráficos e isomorfismo de gráficos.....................................................60
9.4 Conectividad......................................................................................................................64
9.5 Caminos de Euler y Hamilton...........................................................................................66
9.6 Problemas de la ruta más corta..........................................................................................68
Capítulo 10: Árboles........................................................................................................................69
2.1 Introducción a los árboles..................................................................................................69
10.2 Aplicaciones de los árboles..................................................................................................70
10.3 Travesía de árboles........................................................................................................72
10.4 Árboles de expansión.....................................................................................................75
10.4 Árboles de expansión mínimos............................................................................................82

2. ¡Encuentra la factorización prima de 10!

3. ¿Cuáles números enteros positivos menores que 12 son primos entre sí con respecto a
12?
4. ¿Qué números enteros positivos menores que 30 son relativamente primos con respecto
a 30?
5. Encuentre estos valores de la función φ de Euler.
a) φ(4) b) φ(10) c) φ(13)
6. ¿Cuáles son los máximos comunes divisores de estos pares de números enteros?
a) 37 · 53 · 73, 211 · 35 · 59 b) 11 · 13 · 17, 29 · 37 · 55 · 73 c) 2331, 2317
d) 41 · 43 · 53, 41 · 43 · 53 e) 313 · 517, 212 · 721

2
7
3.6 Números enteros y algoritmos
1. Supongamos que se producen números pseudoaleatorios utilizando: xn+1 = (3xn + 11) mod
13. Si x3 = 5, encuentre x2 y x4.

2. Supongamos que se producen números pseudoaleatorios utilizando: xn+1 = (2xn + 7) mod

9.

a) Si x0 = 1, encuentre x2 y x3 b) Si x3 = 3, encuentre x2 y x4.

3. Usando la función f(x) = (x + 10) mod 26 para cifrar mensajes. Responda cada una de
estas preguntas.

a) Cifrar el mensaje STOP b) Descifrar el LEI del mensaje

4. ¿Qué ubicaciones de memoria asigna la función hash h(k) = k mod 101 a los registros de
clientes de compañías de seguros con estos números de seguro social?

a) 104578690 b) 432222187

5. Utilice el algoritmo euclidiano para encontrar

a) mcd(14, 28) b) mcd(8, 28) c) mcd(100, 101) d) mcd(28,35)

e) mcm(7, 28) f) mcm(12, 28) g) mcm(100, 101) h) mcm(28,35)

2
8
Capítulo 4: Inducción y recursión
4.1 Inducción matemática
1. Sea P(n) la afirmación de que 12 + 22 + 32 + ... + n2 n(n+1)
Para lo
(2n+1) positivo
entero n.
a) ¿Cuál es la afirmación P (1)?
b) Demuestre que P (1) es verdadero, completando el paso base de la prueba.
c) ¿Qué es la hipótesis inductiva?
d) ¿Qué necesitas demostrar en el paso inductivo?
e) Complete el paso inductivo, identificando dónde utiliza la hipótesis inductiva.

2. Sea P(n) la afirmación de que 1

1
+ + + ... + - - <
1 2
n es un entero mayor que 49 número 2 norte
, donde
de 1.
a) ¿Cuál es la afirmación P (2)?
b) Demuestre que P (2) es verdadera, completando el paso base de la prueba.
c) ¿Qué es la hipótesis inductiva?
d) ¿Qué necesitas demostrar en el paso inductivo?
e) Completa el paso inductivo.
3. Demuestre la afirmación "6 divide a n3 - n para todos los números enteros n ≥ 0".
4. Demuestre que 3n< n! si n es un entero mayor que 6.
5. Demuestre que 2n > n2 si n es un entero mayor que 4.
1-yo1- -1- 1- -1- -yo-1— . - /
6. Demuestre que para cada entero —1 9
positivo n, 1 +—— +—— +... +—— > 2 n +1
número 1
7. Demuestre que ln n
< >- siempre que n sea un entero positivo.
i= 1i

2
9
4.2 Inducción fuerte
1. Sea P(n) la afirmación de que se puede formar un franqueo de n centavos utilizando
solo sellos de 3 centavos y sellos de 5 centavos. Las partes de este ejercicio describen una
fuerte prueba de inducción de que P(n) es verdadero para n ≥ 8.
a) Demuestre que las afirmaciones P (8), P (9) y P (10) son verdaderas, completando así
el paso base de la prueba.
b) ¿Cuál es la hipótesis inductiva de la prueba?
c) ¿Qué necesitas demostrar en el paso inductivo?
d) Complete el paso inductivo para k ≥ 10.
2. Sea P (n) la afirmación de que se puede formar un franqueo de n centavos utilizando
solo sellos de 4 centavos y sellos de 7 centavos. Las partes de este ejercicio describen una
fuerte prueba de inducción de que P(n) es verdadero para n ≥ 18.
a) Demuestre que las afirmaciones P(18), P(19), P(20) y P(21) son verdaderas,
completando así el paso base de la prueba.
b) ¿Cuál es la hipótesis inductiva de la prueba?
c) ¿Qué necesitas demostrar en el paso inductivo?
d) Complete el paso inductivo para k ≥ 21.

3
0
4.3 Definiciones recursivas e inducción estructural
1. Encuentra f(1), f(2), f(3) y f(4) si f(n) se define recursivamente por f(0) = 1 y para n = 0,
1, . . .
a) f(n+1) = f(n)+2 b) f(n+1) = 3f(n)
c) f(n+1) = 2f(n) d) f(n+1) = f(n)2+f(n)+1
2. Encuentra f (2), f (3), f (4) y f (5) si f se define recursivamente por f (0) = -1, f (1) = 2, y
para n = 1, 2, . . .
a) f(n+1) = f(n)+3f(n-1) b) f(n+1) = f(n)2f(n-1)
c) f(n+1) = 3f(n)2 - 4f(n-1)2 d) f(n+1) = f(n-1)/f(n)
3. Encuentra f (2), f (3), f (4) y f (5) si f se define recursivamente por f (0) = f (1) = 1 y para
n = 1, 2, . . .
a) f(n+1) = f(n) - f(n-1) b) f(n+1) = f(n)f(n-1)
c) f(n+1) = f(n)2 + f(n-1)3 d) f(n+1) = f(n)/f(n-1)
4. Determinar si cada una de estas definiciones propuestas es una definición recursiva válida
de una función f del conjunto de números enteros no negativos al conjunto de números
enteros. Si f está bien definida, encuentre una fórmula para f(n) cuando n es un entero no
negativo y demuestre que su fórmula es válida.
a) f(0) = 0, f(n) = 2f (n - 2) para n ≥ 1
b) f(0) = 1, f(n) = f (n - 1) - 1 para n ≥ 1
c) f(0) = 2, f(1) = 3, f (n) = f (n - 1) - 1 para n ≥ 2
d) f(0) = 1, f(1) = 2, f (n) = 2f (n - 2) para n ≥2
e) f(0) = 1, f(n) = 3f (n - 1) si n es impar y n ≥1 y f (n) = 9f (n - 2) si n es par y n ≥ 2
5. Dar una definición recursiva de la secuencia {an}, n = 1, 2, 3, . . . si
a) un = 6n b) an = 2n + 1 do) un = 10n d) un = 5
e) un = 4n - 2 f) an = 1 + (-1)n gramo) un = n(n + 1) h) an = n2
6. Sea F la función tal que F(n) es la suma de los primeros n números enteros positivos. Dar
una definición recursiva de F(n).
7. Dar una definición recursiva de cada uno de estos conjuntos.

a) A = {2, 5, 8, 11, 14, …} b) B = {…, -5, -1, 3, 7, 10, …}

c) C = {3, 12, 48, 192, 768, …} d) D = {1, 2, 4, 7, 11, 16, …}

3
1
8. La inversión de una cadena es la cadena que consta de los símbolos de la cadena en orden
inverso. La inversión de la cuerda w se denota por wR. Encuentre la inversión de las siguientes
cadenas de bits.

a) 0101 b) 1 1011 c) 1000 1001 0111

9. ¿Cuándo una cadena pertenece al conjunto A de cadenas de bits definidas recursivamente

por λ ∈ A, 0x1 ∈ A si x ∈ A, donde λ es la cadena vacía?

3
2
4.4 Algoritmos recursivos
1. Proporcione un algoritmo recursivo para calcular nx siempre que n sea un entero positivo
y x sea un entero, utilizando solo la suma.
2. Consideremos un algoritmo recursivo para calcular el n-ésimo número de Fibonacci:
procedimiento Fibo(n : entero positivo)
si n = 1 devuelve 1
De lo contrario, si n = 2, devuelve 1
de lo contrario, devuelve Fibo(n – 1) + Fibo(n – 2)
¿Cuántas sumas (+) se utilizan para encontrar Fibo(6) mediante el algoritmo anterior?
3. Proporcione un algoritmo recursivo para encontrar la suma de los primeros n números
enteros positivos impares.
4. Consideremos el siguiente algoritmo:
procedimiento tinh(a: número real; n: entero positivo)
Si n = 1 devuelve un

de lo contrario, devuelve un •tinh(a, n-1).

a) ¿Cuál es la salida si las entradas son: n = 4, a = 2,5? Explica tu respuesta.

b) Demuestre que el algoritmo calcula n •a utilizando inducción matemática.

5. Consideremos el siguiente algoritmo:
procedimiento F(a1, a2, a3, ...,an: enteros)
si n = 0 devuelve 0
de lo contrario devuelve an + F(a1, a2, a3, ...,an-1)
Encontrar
a) F(1,3,5) b) F(1,3,5) c) F(1,2,3,5,9)

3
3
Capítulo 5-7: Contando
5.1 Los conceptos básicos del conteo
1. ¿Cuántas cadenas de bits diferentes de longitud siete hay?
2. ¿Cuántas matrículas diferentes se pueden hacer si cada una contiene una secuencia de
tres letras mayúsculas en inglés seguidas de tres dígitos (y no se prohíbe ninguna secuencia
de letras, incluso si es obscena)?
3. Funciones de conteo: ¿Cuántas funciones hay desde un conjunto con m elementos hasta
un conjunto con n elementos?
4. Contar funciones uno a uno: ¿cuántas funciones uno a uno hay desde un conjunto con
m elementos hasta uno con n elementos?
5. Contar funciones biyectivas: ¿Cuántas funciones biyectivas hay desde un conjunto con
m elementos hasta uno con n elementos?
6. Cada usuario de un sistema informático tiene una contraseña, que tiene entre seis y ocho
caracteres, donde cada carácter es una letra mayúscula o un dígito. Cada contraseña debe
contener al menos un dígito. ¿Cuántas contraseñas posibles hay?
7. ¿Cuántas cadenas de bits de longitud ocho comienzan con un bit 1 o terminan con dos
bits 00?
8. ¿Cuántas cadenas de bits de longitud cuatro no tienen dos 1 consecutivos?
9. ¿Cuántas cadenas de bits de longitud diez comienzan y terminan con 1?
10. ¿Cuántos números enteros positivos hay entre 5 y 31?
a) son divisibles por 3? b) son divisibles por 4? c) son divisibles por 3 y por 4?
11. ¿Cuántos números enteros positivos hay entre 50 y 100?
a) son divisibles por 7? b) son divisibles por 11? c) ¿son divisibles tanto por 7 como
por 11?
12. ¿Cuántos números enteros positivos menores que 1000?
a) son divisible ¿para las 7? b) ¿Son divisibles por 7 pero no por 11?
c) son divisible por ambos 7 y 11? d) ¿Son divisibles por 7 o por 11?
e) son divisible por exactamenteuno de 7 y 11? F ) ¿No son divisibles ni
por 7 ni por 11?
g) ¿Tienen dígitos distintos? h) ¿Tienen dígitos distintos y son pares?
13. ¿Cuántos números enteros positivos entre 100 y 999 inclusive?

3
4
a) son divisibles por 7? b) son impares?

3
5
c) ¿tienen los mismos tres dígitos d) no son divisibles por 4?
decimales?
f ) no son divisibles ni por 3 ni por
e) son divisibles por 3 o 4? 4?
g) ¿Son divisibles por 3 pero no por h) ¿Son divisibles por 3 y 4?
14. ¿Cuántas funciones biunívocas hay desde un conjunto de cinco elementos hasta
conjuntos con el siguiente número de elementos?
a) 4 b) 5 c) 6 d) 7
15. ¿Cuántas cadenas de bits de longitud siete comienzan con dos 0 o terminan con tres 1?
16. ¿Cuántas cadenas de bits de longitud 10 comienzan con tres 0 o terminan con dos 0?
17. ¿Cuántas cadenas de bits de longitud 8 comienzan con 11 o terminan con 00?
18. Sea B el conjunto {a, b, c}. ¿Cuántas funciones hay desde B2 hasta B?
19. ¿Cuántas cadenas de bits con una longitud de 10 tienen exactamente tres 1 y terminan
en 0?
20. Un juego que consiste en lanzar una moneda al aire termina cuando el jugador obtiene
dos caras seguidas, dos cruces seguidas o lanza la moneda cuatro veces. ¿De cuantas
maneras puede terminar el juego?

3
6
7.1 Relaciones de recurrencia
1. a) Encuentra una relación de recurrencia para el número de permutaciones de un
conjunto con n elementos.
b) Utilice esta relación de recurrencia para encontrar el número de permutaciones de un
conjunto con n elementos usando iteración.
2. a) Encuentre una relación de recurrencia para el número de cadenas de bits de longitud
n que no contengan tres 0 consecutivos.
b) ¿Cuales son las condiciones iniciales?
c) ¿Cuántas cadenas de bits de longitud siete no contienen?
¿tres 0 consecutivos?
3. ¿Cuál es la solución de la relación de recurrencia an = an-1 + 2an-2 con a0 = 2 y a1 = 7?

3
7
7.3 Algoritmos de divide y vencerás y relaciones de
recurrencia
1. ¿Cuántas comparaciones se necesitan para una búsqueda binaria en un conjunto de 64
elementos?
2. Supongamos que f(n) = f(n/3) + 1 cuando n es un entero positivo divisible por 3 y f(1) =
1. Encontrar
a) f(3) b) f(27) do) f(729)
3. Supongamos que f(n) = 2f(n/2) +3 cuando n es un número par positivoentero, y
f(1) = 5. Encontrar
a) f(2) b) f(8) do) f(64) d) f(1024).
4. Supongamos que f(n) = f(n/5) + 3n cuando n es positivo entero divisible por
5, y f(1) = 4.
Encontrar
a) f(5) b) f(125) c) f(3125)

3
8
Capítulo 8: Relaciones
8.1 Relaciones y sus propiedades
1. ¿Cuántas relaciones binarias de A a B se pueden construir?
2. ¿Cuántas relaciones hay en el conjunto A?
3. ¿Cuántas relaciones hay en el conjunto {1,2,3,4} que contienen el par (1,2) y (1,3)?

3}, donde (a, b) ∈ R si y solo si

4. Enumere los pares ordenados en la relación R desde A = {0, 1, 2, 3, 4} hasta B = {0, 1, 2,

a) a = b b) a + b = 4 c) a > b d) a | b
e) mcd(a, b) = 1 f ) mcm(a, b) = 2
5. Sea A = {1, 2, 3, 4, 5, 6}
a) Enumere todos los pares ordenados en la relación R = {(a, b) | a divide b} en A.
b) Muestre esta relación gráficamente.
c) Mostrar esta relación en forma de tabla.
6. Para cada una de estas relaciones en el conjunto {1, 2, 3, 4}, decida si es reflexiva, si es
simétrica, si es antisimétrica y si es transitiva.
a) {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (3, 4)} b) {(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 4)} c)
{(2, 4), (4, 2)} d) {(1, 2), (2, 3), (3, 4)} e) {(1, 1), (2, 2), (3, 3), (4, 4)} f ) {(1, 3), (1, 4), (2,
3), (2, 4), (3, 1), (3, 4)}

antisimétrica y/o transitiva, donde (a, b) ∈ R si y solo si

7. Determinar si la relación R en el conjunto de todas las personas es reflexiva, simétrica,

a) a es más alto b) a y b nacieron el mismo día.

que b.
c) a tiene el mismo nombre que d) a y b tienen un abuelo común
b.
simétrica, antisimétrica y/o transitiva, donde (x, y) ∈ R si y solo si
8. Determinar si la relación R en el conjunto de todos los números reales es reflexiva,

a) x + y = 0 b) x = ±y c) x - y es un número racional
d) xy ≥ 0 y)xy = 0 g)xy > 1.

3
9
simétrica, antisimétrica y/o transitiva, donde (x, y) ∈ R si y solo si
9. Determinar si la relación R en el conjunto de todos los números enteros es reflexiva,

a) x ≠ y b) xy ≥ 1 c) x = y + 1 o x = y - 1
d) x ≡ y (mod 7) e) x es un múltiplo de y

por R-1, es el conjunto de pares ordenados {(b, a) | (a, b) ∈ R}. La relación complementaria
Sea R una relación de un conjunto A a un conjunto B. La relación inversa de B a A, denotada

R es el conjunto de pares ordenados {(a, b) | (a, b) / ∈ R}.

10. Sean R1 = {(1, 2), (2, 3), (3, 4)} y R2 = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3,
3), (3, 4)} relaciones de {1, 2, 3} a {1, 2, 3, 4}. Encontrar
a) R1 ∪ R2 b) R1 ∩ R2 c) R1 - R2

d) R-1 y R e) R © R,

11. Sea R la relación {(1, 2), (1, 3), (2, 3), (2, 4), (3, 1)}, y sea S la relación {(2, 1), (3, 1),
(3, 2), (4, 2)}. Encuentra S ◦ R
12. a) Enumere las 16 relaciones diferentes en el conjunto {0, 1}
b) ¿Cuáles de las relaciones son
a) reflexivo? b) ¿irreflexivo? c) simétrico?
d) ¿antisimétrico? e) ¿asimétrico? f ) transitivo?
13. Sea R la relación en el conjunto {1, 2, 3, 4, 5} que contiene los pares ordenados (1, 1), (1,
2), (1, 3), (2, 3), (2, 4), (3, 1), (3, 4), (3, 5), (4, 2), (4, 5), (5, 1), (5, 2) y (5, 4). Encontrar
a) R2 b) R3 c) R4 d) R5

4
0
8.2 Relaciones n-arias y sus aplicaciones
TABLA 1 Estudiantes.
Nombre del Número de Importante GPA
estudiante identificación
Ciencias de la
Ackerman 231455 Computación 3.88
Adán 888323 Física 3.45
Chou 102147 Ciencias de la 3.49
Buen amigo 453876 Computación
Matemáticas 3.45
Rao 678543 Matemáticas 3.90
Stevens 786576 Psicología 2.99

1. ¿Qué dominios son claves primarias para la relación n-aria que se muestra en la Tabla 1,
asumiendo que no se agregarán n-tuplas en el futuro?
2. ¿Es el producto cartesiano del dominio de los principales campos de estudio y el dominio
de los GPA una clave compuesta para la relación n-aria de la Tabla 1, asumiendo que nunca
se agregan n-tuplas?
3. a) Encuentra los registros de los estudiantes de ciencias de la computación en la relación
n-aria R que se muestra en la Tabla 1.
b) Encuentre los registros de los estudiantes que tienen un promedio de calificaciones
superior a 3.5 en esta base de datos.
c) Encuentre los registros de estudiantes de ciencias de la computación que tienen un GPA
superior a 3.5.
4. ¿Qué resulta cuando se aplica la proyección P1,3 a las 4-tuplas (2, 3, 0, 4), (Jane Doe, 234111001,
Geografía, 3.14) y (a1, a2, a3, a4)?
5. ¿Qué relación resulta cuando se aplica la proyección P1,4 a la relación de la Tabla 1?
6. ¿Cuál es la tabla que se obtiene cuando se aplica la proyección P2 a la relación de la Tabla 1?
7. ¿Qué relación resulta cuando se utiliza el operador de unión J2 para combinar la relación que se
muestra en las Tablas 5 y 6?

TABLA 5 Tareas docentes. TABLA 6 Horario de clases.

Número de Número de
curso Coume
Profesor Departamento Departamento Habitación Tiempo
Ciencias de la
Cruz Zoología 335 518 N521 2:00 p.m.
Computación
Cruz Zoología 412 Matemáticas 575 N502 3:00 PJ1

Farber Psicología 501 Matemáticas 611 N52I 4:00 p.m.

Farber Psicología 617 Física 544 B505 4:00 p.m.

Gramática Física 544 Psicología 501 Al 00 3:00 p.m.

Gramática Física 551 Psicología 617 ¡A! Él) 11:00 AH.
Rosas Ciencias de la 518 Zoología 335 Al 00 9:00 AM
Computación
Rosas Matemáticas 575 Zoología 412 Al 00 8:00 AM

4
1
8.3 Representando relaciones

b) si a ∈ A, b ∈ B y a > b. ¿Cuál es la matriz que representa R?

1. Supongamos que A = {1, 2, 3} y B = {1, 2}. Sea R la relación de A a B que contiene (a,

2. Sea A = {1, 2, 3} y B = {1, 2, 3, 4, 5}. ¿Qué pares ordenados están en la relación R

representada por la matriz?

SEÑO
Capítulo 1: Los fundamentos: lógica y pruebas..........................................................................2
R
1.1 Lógica proposicional..........................................................................................................2
1.2- Equivalencias proposicionales.............................................................................................8
1.4 Predicados y cuantificadores.........................................................................................................9
1.5 Reglas de inferencia....................................................................................................................11
Capítulo 2: Estructuras básicas: conjuntos, funciones, secuencias y sumas.........................................13
2.1 Conjuntos...............................................................................................................................13
2.2 Operaciones de conjuntos......................................................................................................16
2.3 Funciones...............................................................................................................................17
d) f
(n)=...............................................................................................................................................17
2.4 Secuencias y sumas................................................................................................................19
Capítulo 3: Los fundamentos: algoritmos, números enteros y matrices...............................................21
3.1 Algoritmos.............................................................................................................................21
3.2 El crecimiento de las funciones.............................................................................................23
3.3 Complejidad de los algoritmos...................................................................................................24
3.4 Los números enteros y la división...............................................................................................25
3.5 Números primos y máximos comunes divisores.........................................................................27
3.6 Números enteros y algoritmos....................................................................................................29
Capítulo 4: Inducción y recursión.........................................................................................................30
4.1 Inducción matemática.................................................................................................................30
4.2 Inducción fuerte..........................................................................................................................31
4.3 Definiciones recursivas e inducción estructural.....................................................................32
4.4 Algoritmos recursivos............................................................................................................34
Capítulo 5-7: Contando.........................................................................................................................35
5.1 Los conceptos básicos del conteo...............................................................................................35
7.1 Relaciones de recurrencia......................................................................................................38

4
2
 7.3 Algoritmos de divide y vencerás y relaciones de recurrencia.....................................................39
Capítulo 8: Relaciones..........................................................................................................................40
8.1 Relaciones y sus propiedades.................................................................................................40
8.2 Relaciones n-arias y sus aplicaciones....................................................................................42
8.3 Representando relaciones.......................................................................................................44
<1 1
1...........................................................................................................................................49
101A..................................................................................................................................................49
8.5 Relaciones de equivalencia.........................................................................................................51
Capítulo 9: Gráficos..............................................................................................................................56
9.1 Gráficos y modelos de gráficos..............................................................................................56
9.2 Terminología de gráficos y tipos especiales de gráficos........................................................57
9.3 Representación de gráficos e isomorfismo de gráficos..........................................................60
9.4 Conectividad..........................................................................................................................64
9.5 Caminos de Euler y Hamilton................................................................................................66
9.6 Problemas de la ruta más corta..............................................................................................68
Capítulo 10: Árboles.............................................................................................................................69
2.1 Introducción a los árboles......................................................................................................69
10.2 Aplicaciones de los árboles.......................................................................................................70
10.3 Travesía de árboles.............................................................................................................72
10.4 Árboles de expansión.........................................................................................................75
10.4 Árboles de expansión mínimos.................................................................................................82

¿Reflexivo, simétrico y/o antisimétrico?

3. Supongamos que las relaciones R1 y R2 en un conjunto A están representadas por las
matrices
01) (101)
00

∪ R2 ,
yM 011 ¿Cuáles son las matrices que representan R1
Sra. 1
{0
R
10) (110)
R1 ∩ R2 y S ◦R

5.

4
3
a) ¿Cuáles son los pares ordenados en la relación R representada por el gráfico dirigido que
se muestra en la Figura?

b) Determinar si las relaciones para los gráficos dirigidos que se muestran en la Figura son
reflexivas, simétricas, antisimétricas y/o transitivas.

4
4
6.

a) ¿Cuáles son los pares ordenados en la relación R representada por el gráfico dirigido que
se muestra en la Figura?

b) Determinar si las relaciones para los gráficos dirigidos que se muestran en la Figura son
reflexivas, simétricas, antisimétricas y/o transitivas.

7. Representa cada una de estas relaciones en {1, 2, 3} con una matriz y un gráfico dirigido

a) {(1, 1), (1, 2), (1, 3)}

b) {(1, 2), (2, 1), (2, 2), (3, 3)}

c) {(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)}

d) {(1, 3), (3, 1)}

8. Representa cada una de estas relaciones en {1, 2, 3} con una matriz y un gráfico dirigido
Capítulo 1: Los fundamentos: lógica y pruebas 2
1.1 Lógica proposicional 2
1.2- Equivalencias proposicionales 8
1.4 Predicados y cuantificadores 9
1.5 Reglas de inferencia 11
Capítulo 2: Estructuras básicas: conjuntos, funciones, secuencias y sumas 13
2.1 Conjuntos 13
2.2 Operaciones de conjuntos 16
2.3 Funciones 17
d) f
(n)= 17
2.4 Secuencias y sumas 19

4
5
Capítulo 3: Los fundamentos: algoritmos, números enteros y matrices 21
3.1 Algoritmos 21
3.2 El crecimiento de las funciones 23
3.3 Complejidad de los algoritmos 24
3.4 Los números enteros y la división 25
3.5 Números primos y máximos comunes divisores 27
3.6 Números enteros y algoritmos 29
Capítulo 4: Inducción y recursión 30
4.1 Inducción matemática 30
4.2 Inducción fuerte 31
4.3 Definiciones recursivas e inducción estructural 32
4.4 Algoritmos recursivos 34
Capítulo 5-7: Contando 35
5.1 Los conceptos básicos del conteo 35
7.1 Relaciones de recurrencia 38
7.3 Algoritmos de divide y vencerás y relaciones de recurrencia 39
Capítulo 8: Relaciones 40
8.1 Relaciones y sus propiedades 40
8.2 Relaciones n-arias y sus aplicaciones 42
8.3 Representando relaciones 44
<1 1
1 49
101A 49
8.5 Relaciones de equivalencia 51
Capítulo 9: Gráficos 56
9.1 Gráficos y modelos de gráficos 56
9.2 Terminología de gráficos y tipos especiales de gráficos 57
9.3 Representación de gráficos e isomorfismo de gráficos 60
9.4 Conectividad 64
9.5 Caminos de Euler y Hamilton 66
9.6 Problemas de la ruta más corta 68
Capítulo 10: Árboles 69
2.1 Introducción a los árboles 69

4
6
 10.2 Aplicaciones de los árboles 70
10.3 Travesía de árboles 72
10.4 Árboles de expansión 75
10.4 Árboles de expansión mínimos 82

9. Enumere los pares ordenados en las relaciones en {1, 2, 3} correspondientes a estas

matrices (donde las filas y columnas corresponden a los números enteros enumerados en
orden creciente).

101A
10
(111) 0 1 0
01
a) b) 1 0 1 1 0 1
11
< 1
1 1
01
0 1 0
?

4
7
10. Sean R1 y R2 relaciones en un conjunto A representado por las matrices

‘ 0 1 0) ‘ 0 1 0)
RESONA y EL SEÑOR
111 0 1 1
=
NCIA
. 10 .1 1
1)
Encuentra las matrices que representan

a) R •R b) R Arkansas do) RoR d) R•R

e) R22 f) R13 gramo) R12 h) R14

11. Dibuje el gráfico dirigido que representa la relación {(a, a), (a, b), (b, c), (c, b), (c, d), (d,
a), (d, b)}

12. Enumere los pares ordenados en las relaciones representadas por los grafos dirigidos.

4
8
8.5 Relaciones de equivalencia
1. Sea R la relación en el conjunto de números reales tal que aRb si y sólo si a - b es un
entero. ¿Es R una relación de equivalencia?
2. Sea R la relación sobre el conjunto de números enteros tal que aRb si y sólo si a = b o a
= -b. ¿Cuál es la clase de equivalencia de un número entero para la relación de equivalencia
R?
3. ¿Cuáles son las clases de equivalencia de 0 y 1 para la congruencia módulo 4?

4. Enumere los pares ordenados en la relación de equivalencia R producida por la partición

A1 = {1, 2, 3}, A2 = {4, 5} y A3 = {6} de S = {1, 2, 3, 4, 5, 6}.

5. ¿Cuáles son los conjuntos en la partición de los números enteros que surgen de la
congruencia módulo 4?

6. ¿Cuáles de estas relaciones en {0, 1, 2, 3} son relaciones de equivalencia? Determinar

las propiedades de una relación de equivalencia de las que carecen las otras.
Capítulo 1: Los fundamentos: lógica y pruebas 2
1.1 Lógica proposicional 2
1.2- Equivalencias proposicionales 8
1.4 Predicados y cuantificadores 9
1.5 Reglas de inferencia 11
Capítulo 2: Estructuras básicas: conjuntos, funciones, secuencias y sumas 13
2.1 Conjuntos 13
2.2 Operaciones de conjuntos 16
2.3 Funciones 17
d) f
(n)= 17
2.4 Secuencias y sumas 19
Capítulo 3: Los fundamentos: algoritmos, números enteros y matrices 21
3.1 Algoritmos 21
3.2 El crecimiento de las funciones 23
3.3 Complejidad de los algoritmos 24
3.4 Los números enteros y la división 25
3.5 Números primos y máximos comunes divisores 27
3.6 Números enteros y algoritmos 29
Capítulo 4: Inducción y recursión 30
4.1 Inducción matemática 30

4
9
 4.2 Inducción fuerte 31
4.3 Definiciones recursivas e inducción estructural 32
4.4 Algoritmos recursivos 34
Capítulo 5-7: Contando 35
5.1 Los conceptos básicos del conteo 35
7.1 Relaciones de recurrencia 38
7.3 Algoritmos de divide y vencerás y relaciones de recurrencia 39
Capítulo 8: Relaciones 40
8.1 Relaciones y sus propiedades 40
8.2 Relaciones n-arias y sus aplicaciones 42
8.3 Representando relaciones 44
<1 1
1 49
101A 49
8.5 Relaciones de equivalencia 51
Capítulo 9: Gráficos 56
9.1 Gráficos y modelos de gráficos 56
9.2 Terminología de gráficos y tipos especiales de gráficos 57
9.3 Representación de gráficos e isomorfismo de gráficos 60
9.4 Conectividad 64
9.5 Caminos de Euler y Hamilton 66
9.6 Problemas de la ruta más corta 68
Capítulo 10: Árboles 69
2.1 Introducción a los árboles 69
10.2 Aplicaciones de los árboles 70
10.3 Travesía de árboles 72
10.4 Árboles de expansión 75
10.4 Árboles de expansión mínimos 82
a)

b) {(0, 0),(0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 2), (3, 3)}

7. ¿Cuáles de estas relaciones en el conjunto de todas las personas son relaciones de

equivalencia? Determinar las propiedades de una relación de equivalencia de las que
carecen las otras.

a) {(a, b) | a y b tienen la misma edad}

b) {(a, b) | a y b tienen los mismos padres}

5
0
c) {(a, b) | a y b comparten un padre común}

d) {(a, b) | a y b se han conocido}

8. ¿Cuáles de estas relaciones en el conjunto de todas las funciones de Z a Z son relaciones

de equivalencia? Determinar las propiedades de una relación de equivalencia de las que
carecen las otras.

a) {(f, g) | f(1) = g(1)} b) {(f, g) | f (0) = g(0) o f (1) = g(1)}

c) {(f, g) | f (x) - g(x) = 1 para todo x ∈ d) {(f, g) | para algún C ∈ Z, para todo x
Z} ∈ Z, f
(x) - g(x) = C}

5
1
9. Determinar si la relación con el gráfico dirigido que se muestra es una relación de
equivalencia

10. Determinar si las relaciones representadas por estas matrices cero-uno son relaciones de
equivalencia
‘ 1010^ ‘ 1110 ^
(111) 0 10 1 1110
a) 0 1 1 10 10 1110
I11 . 0 10 1)
1) . 0 0 0 1)

11. ¿Cuáles de estas colecciones de subconjuntos son particiones de {1, 2, 3, 4, 5, 6}?

a) {1, 2},{2, 3, 4},{4, 5, 6} b) {1}, {2, 3, 6}, {4}, {5}
c) {2, 4, 6}, {1, 3, 5} d) {1, 4, 5}, {2, 6}
12. Sea R={(1,1), (2,2), (3,3), (1,2), (2,1), (4,4), (4,5), (5,4), (5,5)} una relación de
equivalencia en el conjunto {1,2,3,4,5}. ¿Cuántas clases de equivalencia con respecto a R?
13. Enumere los pares ordenados en las relaciones de equivalencia producidas por estas
particiones de {a, b, c, d, e, f, g}.
a) {a, b}, {c, d}, {e, f, g} b) {a}, {b}, {c, d}, {e, f}, {g}
c) {a, b, c, d}, {e, f, g} d) {a, c, e, g}, {b, d}, {f}

5
2
Capítulo 9: Gráficos
9.1 Gráficos y modelos de gráficos
1. Determinar si el gráfico mostrado tiene aristas dirigidas o no dirigidas, si tiene múltiples
aristas y si tiene uno o más bucles.

2. Construya un gráfico de precedencia para el siguiente

programa:
S1: x := 0 S2: x := x + 1 S3: y := 2

S4: z := y S5: x := x + 2 S6: y := x + z S7: z := 4

5
3
9.2 Terminología de gráficos y tipos especiales de gráficos
1. Encuentra el número de vértices, el número de aristas y el grado de cada vértice en el
gráfico no dirigido dado. Identifica todos los vértices aislados y colgantes.

2. Encuentra la suma de los grados de los vértices de cada gráfico en los Ejercicios 1 y
verifica que sea igual al doble del número de aristas del gráfico.
3. ¿Puede existir un grafo simple con 15 vértices cada uno de grado cinco?
4. Determinar el número de vértices y aristas y encontrar el grado de entrada y de salida de
cada vértice para el multigrafo dirigido dado

5
4
5. Dibuje estos gráficos.
a) K7 b) K1,8 c) K4,4
c) C7 e) W7 f ) Q4
6. Determinar si el gráfico es bipartito

5
5
7. ¿Para qué valores de n estos gráficos son bipartitos?
a) Kn b) Cn c) En d) Pregunta

8. Cómomuchos vérticesy cuantos bordes Haz esto ¿Qué gráficos tienen?

a) Kn b) Cn c) En d) kilómetros e) Qn
9. Encontrar elsecuencias de grados para cada uno delgráficos en Ceremonias 6.
10. Encuentra la secuencia de grados de cada uno de los siguientes gráficos.
a) K4 b) C4 c) W4 d) K2,3 e) Q3
11. ¿Cuántas aristas tiene un grafo si su secuencia de grados es 4, 3, 3, 2, 2? Dibuje un
gráfico como este.
12. ¿Cuántas aristas tiene un grafo si su secuencia de grados es 5, 2, 2, 2, 2, 1? Dibuje un
gráfico como este.
13. Determinar si cada una de estas secuencias es gráfica. Para los que lo sean, dibujen un

5
6
gráfico que tenga la secuencia de grados dada.
a) 5, 4, 3, 2, 1, 0 b) 6, 5, 4, 3, 2, 1 c) 4, 4, 3, 2, 1
d) 3, 3, 3, 2, 2, 2 e) 3, 3, 2, 2, 2, 2 f) 3, 2, 2, 1, 0

5
7
9.3 Representación de gráficos e isomorfismo de gráficos
1. Utilice una lista de adyacencia para representar el gráfico dado.

2. Representa el gráfico del Ejercicio 1 con una matriz de

adyacencia.
3. Representa cada uno de estos gráficos con una matriz de adyacencia.
a) K4 b) K1,4 c) K2,3 c) C4 e) W4 f ) Q3
4. Dibuje un gráfico con la matriz de adyacencia dada
' 0011A
(121A 0 0 10
(010)
a) 1 0 b) 2 0 110 1
I01 . 1110 )
. 02

5
8
5. Determinar si el par de gráficos dado es isomorfo.

6. ¿Son isomorfos los gráficos simples con las siguientes matrices de

adyacencia?
10 1 1
0
1,10
0 1 0 0
0 1 1 1
0 1 1 0 0 1
0 1 ’ 1 0 0 1
1 oj_1 1 1 0
c) 0 1 yo 0 1
I 0 0 0 0
I 0 0 0 1
0 1 0 1 0

7. Determinar si el par de gráficos dirigidos dado son isomorfos.

5
9
6
0
9.4 Conectividad
1. ¿Cada una de estas listas de vértices forma un camino en el siguiente gráfico? ¿Qué
caminos son sencillos? ¿Que son los circuitos? ¿Cuáles son las longitudes de los que son
caminos?
a) a, e, b, c, b b) a, e, a, d, b, c, ac) e, b, a, d, b, ed) c, b, d, a, e, c

2. ¿Cada una de estas listas de vértices forma un camino en el siguiente gráfico? ¿Qué
caminos son sencillos? ¿Que son los circuitos? ¿Cuáles son las longitudes de los que son
caminos?
a) a, b, e, c, b b) a, d, a, d, a c) a, d, b, e, a d) a, b, e, c, b, d, a

3. Encuentra el número de caminos de longitud n entre dos vértices diferentes en K4 si n

es
a) 2 b) 3 c) 4 d) 5
4. Encuentra el número de caminos entre c y d en la gráfica de longitud.
a) 2 b) 3 c) 4 d) 5 e) 6 f) 7

6
1
5. Encuentra todos los vértices de corte del gráfico
dado.

6
2
9.5 Caminos de Euler y Hamilton
1. Determinar si el gráfico dado tiene un circuito de Euler. Construya un circuito así cuando
exista.

2. Determinar si el gráfico dirigido que se muestra tiene un circuito de Euler. Construya un

circuito de Euler si existe.

6
3
3. ¿Para qué valores de n estos gráficos tienen un circuito de Euler?
a) Kn b) Cn c) En d) Pregunta
4. Para qué valores de m y n el grafo bipartito completo Km,n tiene una
a) ¿Circuito de Euler? b) ¿Camino de Euler?
5. Determinar si la gráfica dada tiene un circuito de Hamilton. Si es así, busque un circuito
así.

6
4
9.6 Problemas de la ruta más corta
1. ¿Cuál es la longitud de la ruta más corta entre a y z en el gráfico ponderado que se
muestra en la Figura?

2. Encuentre la ruta más corta entre a y z en el gráfico ponderado dado.

6
5
Capítulo 10: Árboles
2.1 Introducción a los árboles
1. ¿Cuáles de estos gráficos son árboles?

2. ¿Cuáles de estos gráficos son árboles?

3. Construya un árbol binario completo de altura 4 y un árbol 3-ario completo de altura 3.

4. ¿Cuáles grafos bipartitos completos Km,n, donde m y n son números enteros positivos, son
árboles?

5. ¿Cuántas aristas tiene un árbol con 10.000 vértices?

6. ¿Cuántos vértices tiene un árbol 5-ario completo con 100 vértices internos?

7. ¿Cuántas aristas tiene un árbol binario completo con 1000 vértices internos?

8. ¿Cuántas hojas tiene un árbol trianual completo con 100 vértices?

6
6
10.2 Aplicaciones de los árboles
1. Forme un árbol de búsqueda binario para las palabras matemáticas, física, geografía,
zoología, meteorología, geología, psicología y química (usando orden alfabético).
2. Utilice la codificación Huffman para codificar los siguientes símbolos con las frecuencias
enumeradas: A: 0,08, B: 0,10, C: 0,12, D: 0,15, E: 0,20, F: 0,35. ¿Cuál es el número
promedio de bits utilizados para codificar un carácter?
3. Construya un árbol de búsqueda binario para las palabras plátano, melocotón, manzana,
pera, coco, mango y papaya usando orden alfabético.
4. Construya un árbol de búsqueda binario para las palabras enología, frenología,
campanología, ornitología, ictiología, limnología, alquimia y astrología utilizando el orden
alfabético.
5. ¿Cuántas comparaciones se necesitan para localizar o agregar cada una de estas palabras
en el árbol de búsqueda del Ejercicio 3, comenzando desde cero cada vez?
a) pera b) plátano c) kumquat d) naranja
6. ¿Cuántas comparaciones se necesitan para localizar o agregar cada una de las palabras en
el árbol de búsqueda del Ejercicio 4, comenzando desde cero cada vez?
a) quiromancia b) etimología c) paleontología d) glaciología
7. ¿Cuáles de estos códigos son códigos de prefijo?
a) 11, y: 00, tamaño: es: 01
un: 10,
b) a: 0, y: 1, t: 01, es: 001
c) a: 101, y: 11, Número es: 011, número: 010
: 001,
d) a: 010, y: 11, Número es: 1011, número: 1001, yo:
: 011, 10101
8. Construya el árbol binario con códigos de prefijo que representen estos
esquemas de codificación.
a) 11, y: 0, 101, s: 100
un:
b) a: 1, y: 01, Número: 001,s: 0001, número: 00001
c) a: 1010, y: 0, 11, s: 1011, número: 1001, yo: 10001
t:
9. ¿Cuáles son los códigos para a, e, i, k, o, p y u si el esquema de codificación está
representado por este árbol?

6
7
10. Dado el esquema de codificación a: 001, b: 0001, e: 1, r: 0000, s: 0100, t: 011, x: 01010,
encuentre la palabra representada por

a) 01110100011 b) 0001110000

c) 0100101010 d) 01100101010

11. Utilice la codificación de Huffman para codificar estos símbolos con las frecuencias
dadas: a: 0,20, b: 0,10, c: 0,15, d: 0,25, e: 0,30. ¿Cuál es el número promedio de bits
necesarios para codificar un carácter?

12. Utilice la codificación de Huffman para codificar estos símbolos con las frecuencias
dadas: A: 0,10, B: 0,25, C: 0,05, D: 0,15, E: 0,30, F: 0,07, G: 0,08. ¿Cuál es el número
promedio de bits necesarios para codificar un símbolo?

13. Construya dos códigos de Huffman diferentes para estos símbolos y frecuencias: t: 0,2,
u: 0,3, v: 0,2, w: 0,3.

6
8
10.3 Travesía de árboles
1. ¿Cuál es el árbol ordenado con raíz que representa la expresión ((x + y)↑2) + ((x - 4)/3) ?
2. ¿Cuál es la forma del prefijo para ((x + y) ↑ 2) + ((x - 4)/3) ?

3. ¿Cuál es el valor de la expresión del prefijo + - ∗ 2 3 5/↑ 2 3 4 ?

4. ¿Cuál es la forma postfija de la expresión ((x + y) ↑ 2) + ((x - 4)/3) ?

5. ¿Cuál es el valor de la expresión posfija 7 2 3 ∗ - 4 ↑ 9 3/+ ?

6. a) Represente la expresión ((x + 2) ↑ 3) ∗ (y -(3 + x)) - 5 utilizando un árbol binario.

Escribe esta expresión en
b) notación de prefijo c) notación sufija d) notación infija
7. a) Representa las expresiones (x + xy) + (x/y) y x + ((xy + x)/y) utilizando árboles
binarios.
Escribe estas expresiones en
b) notación de prefijo c) notación sufija d) notación infija

8. a) Represente las proposiciones compuestas (p ∧ q) ↔ (p ∨ q) y (p ∧ (q ↔ p)) ∨ q

utilizando árboles raíz ordenados.
Escribe estas expresiones en
b) notación de prefijo c) notación sufija d) notación infija

9. a) Represente (A ∩ B) - (A ∪ (B - A)) utilizando un árbol raíz ordenado.

Escribe esta expresión en
b) notación de prefijo c) notación sufija d) notación infija
10. Dibuje el árbol enraizado ordenado correspondiente a cada de Estas expresiones
aritméticas escritas
en notación de prefijo. Luego escribe cada expresión usando infijo notación.

a) + ∗ + - 5 3 2 1 4 b) ↑ + 2 3 - 5 1 do) ∗ / 9 3 + ∗ 2 4 - 7 6
11. ¿Cuál es el valor de cada una de estas expresiones de prefijo?

a) - ∗ 2 / 8 4 3 b) ↑ - ∗ 3 3 ∗ 4 2 5
c) + - ↑ 3 2 ↑ 2 3 / 6 - 4 2 d) ∗ + 3 + 3 ↑ 3 + 3 3 3

6
9
a) 5 2 1 - - 3 1 4 ++ ∗ b) 9 3 / 5 + 7 2 - ∗ c) 3 2 ∗ 2 ↑ 5 3 - 8 4 / ∗
12. ¿Cuál es el valor de cada una de estas expresiones postfijas?

-
13. Determinar el orden en el que un recorrido en preorden visita los vértices del árbol raíz
ordenado dado.

14. ¿En qué orden se visitan los vértices del árbol con raíz ordenado en el Ejercicio 13
utilizando un recorrido en orden?
15. ¿En qué orden se visitan los vértices del árbol con raíz ordenado en el Ejercicio 13
utilizando un recorrido de postorden?

7
0
10.4 Árboles de expansión
1. ¿Cuántas aristas se deben eliminar de un gráfico conexo con n vértices y m aristas para
producir un árbol de expansión?

2. Encuentre un árbol de expansión para el gráfico que se muestra eliminando aristas en

circuitos simples.

a.

b.

7
1
do.

d.

7
2
m
i.

F
.

3. Encuentra un árbol de expansión para cada

uno de estos gráficos.
7
3
a) K5 b) K4,4 c) K1,6
d) Q3 e) C5 f) W5

4. Dibuje todos los árboles de expansión de los gráficos simples dados.

a.

b.

do.

5. Utilice la búsqueda en profundidad y la búsqueda en amplitud para producir un árbol de

expansión para el gráfico simple dado. Elija a como la raíz de este árbol de expansión y
suponga que los vértices están ordenados alfabéticamente.

a.

7
4
b.

d
o.

7
5
6. Utilice la búsqueda en profundidad y la búsqueda en amplitud para encontrar un árbol de
expansión de cada uno de estos gráficos.
a) W6, comenzando en el vértice de grado 6 b) K5
Capítulo 1: Los fundamentos: lógica y pruebas.....................................................................................2
1.1 Lógica proposicional.....................................................................................................................2
1.2- Equivalencias proposicionales.............................................................................................8
1.4 Predicados y cuantificadores........................................................................................................9
1.5 Reglas de inferencia....................................................................................................................11
Capítulo 2: Estructuras básicas: conjuntos, funciones, secuencias y sumas........................................13
2.1 Conjuntos...............................................................................................................................13
2.2 Operaciones de conjuntos......................................................................................................16
2.3 Funciones...............................................................................................................................17
d) f
(n)=...............................................................................................................................................17
2.4 Secuencias y sumas................................................................................................................19
Capítulo 3: Los fundamentos: algoritmos, números enteros y matrices...............................................21
3.1 Algoritmos.............................................................................................................................21
3.2 El crecimiento de las funciones.............................................................................................23
3.3 Complejidad de los algoritmos...................................................................................................24
3.4 Los números enteros y la división..............................................................................................25
3.5 Números primos y máximos comunes divisores........................................................................27
3.6 Números enteros y algoritmos....................................................................................................29
Capítulo 4: Inducción y recursión........................................................................................................30
4.1 Inducción matemática.................................................................................................................30
4.2 Inducción fuerte..........................................................................................................................31
4.3 Definiciones recursivas e inducción estructural....................................................................32
4.4 Algoritmos recursivos............................................................................................................34
Capítulo 5-7: Contando........................................................................................................................35
5.1 Los conceptos básicos del conteo...............................................................................................35
7.1 Relaciones de recurrencia......................................................................................................38
7.3 Algoritmos de divide y vencerás y relaciones de recurrencia.....................................................39
Capítulo 8: Relaciones..........................................................................................................................40
8.1 Relaciones y sus propiedades................................................................................................40
8.2 Relaciones n-arias y sus aplicaciones....................................................................................42
8.3 Representando relaciones......................................................................................................44

7
6
 <1 1
1...........................................................................................................................................49
101A..................................................................................................................................................49
8.5 Relaciones de equivalencia.........................................................................................................51
Capítulo 9: Gráficos.............................................................................................................................56
9.1 Gráficos y modelos de gráficos.............................................................................................56
9.2 Terminología de gráficos y tipos especiales de gráficos.......................................................57
9.3 Representación de gráficos e isomorfismo de gráficos..........................................................60
9.4 Conectividad..........................................................................................................................64
9.5 Caminos de Euler y Hamilton................................................................................................66
9.6 Problemas de la ruta más corta..............................................................................................68
Capítulo 10: Árboles.............................................................................................................................69
2.1 Introducción a los árboles......................................................................................................69
10.2 Aplicaciones de los árboles.......................................................................................................70
10.3 Travesía de árboles.............................................................................................................72
10.4 Árboles de expansión.........................................................................................................75
10.4 Árboles de expansión mínimos.................................................................................................82

7
7
10.4 Árboles de expansión mínimos
1. Las carreteras representadas en este gráfico son todas de tierra. Las longitudes de las
carreteras entre pares de ciudades se representan mediante pesos de arista. ¿Qué caminos se
deben pavimentar para que haya un camino de caminos pavimentados entre cada par de
pueblos de modo que se pavimente una longitud mínima de camino? (Nota: Estos pueblos
están en Nevada).

Manhattan

Beatty

2. Utilice el algoritmo de Prim y el algoritmo de Kruskal para encontrar un árbol de

expansión mínimo para el gráfico ponderado dado a.

7
8
 un 1 b

b.

d
o.

7
9
2

8
0