Separata Matemática Discreta

matriz
MATEMATICA
DISCRETA
MATEMÁTICA DISCRETA 1
Contenido
LÓGICA PROPOSICIONAL ................................................................................................... 2
CUANTIFICADORES ............................................................................................................. 4
MÉTODOS DE DEMOSTRACIÓN ....................................................................................... 11
PRINCIPIO DE INDUCCIÓN MATEMÁTICA EN 𝐙 + .......................................................... 14
RECURSIVIDAD ................................................................................................................... 23
CARDINALIDAD ................................................................................................................... 21
CONGRUENCIA ................................................................................................................... 31
RELACIONES SQL .............................................................................................................. 34
TÉCNICAS DE CONTEO ..................................................................................................... 38
NÚMEROS DE STIRLING .................................................................................................... 42
GRAFOS ............................................................................................................................... 47
CIRCUITO Y TRAYECTORIA DE EULER ........................................................................... 59
COLOREADO DE GRAFOS................................................................................................. 66
ALGORITMO DE DIJKSTRA ................................................................................................ 68
CONVERSIONES POLACOS: ............................................................................................. 77
2023-0
LÓGICA PROPOSICIONAL
Se refiere al uso de las leyes lógicas e inferencias lógicas para deducir nuevas proposiciones
que pueden ser verdaderas o falsas.
Proposición: es un enunciado que afirma o niega, no puede ser una frase exclamativa o
interrogativa.
Siendo el cálculo proposicional el uso de dichas leyes lógicas e inferencias las cuales se
usan con las premisas, dando una tesis o conclusión lógica.
Las premisas siempre son verdaderas.
E1. Demuestre que t ^ s se puede deducir de las premisas p → q, q→~t, p ν (t ^ s), r
▪ P1: p → q (premisa)
▪ P2: q→~r (premisa)
▪ P3: p→~r (P1, P2, SH)
▪ P4: r (premisa)
▪ P5: ~p (P3, P4, M. Tollens)
▪ P6: p ν (t ^ s) (premisa)
▪ P7: ~p ^ (p ν (t ^ s)) (P5, P6, combinación)
▪ P8: (t ^ s) (P7, Silogismo disyuntivo)
E2: Dadas las premisas
p ^ q, p→(r ^ q), r→(s ν t), ~s
Deducir t usando el cálculo proposicional
▪ P1: p ^ q (premisa)
▪ P2: p→(r ^ q) (premisa)

▪ P3: ~p ν (r ^ q) (P2, condicional)
▪ P4: p ( P1, simplificación)
▪ P5: r ^ q (P3, P4, Silogismo Disyuntivo)
▪ P6: r (P5, simplificación)
▪ P7: r→(s ν t)
▪ P8: s ν t (P6, P7, MP)
▪ P9: ~s (premisa)
▪ P10: t (P8, P9, Silogismo Disyuntivo)
▪ E3: (~p ν
▪ ~q)→(r ^ s), r → t, ~t , deducir p
▪ P1: r→ t (premisa)
▪ P2: ~t (premisa)
▪ P3: ~r
▪ P4: ~r ν ~s (P3, adición)
▪ P5: ~(r ^ s) (P4, Morgan)
▪ P6: (~p ν ~q) →(r ^ s) (premisa)
▪ P7: ~(~p ν ~q) (P5, P6, Modus Tollens)
▪ P8: p ^ q (P7, Morgan, doble negación)
▪ P9: p (P8, simplificación)

CUANTIFICADORES
P(x) es verdadera para todos los valores de x en el universo del discurso, el cuantificador
universal se denota como ∀ x P(x).
❖ Cuantificador existencial: (GE)

Cuando ∃ al menos un elemento que hace que P(x) sea verdadero y se denota por medio
de la notación ∃ x P(x), siendo P(x) la proposición en función de x.
❖ Regla de especificación universal: (EU)

Es la regla de inferencia que establece que es posible concluir que P(c) es verdadero si ∀ x
P(x) es verdadero donde c es un miembro arbitrario del universo del discurso, esta regla
recibe también el nombre de instancion universal.
❖ Regla de especificación existencial: (EE)

Es la regla que permite concluir que P(c) es verdadero si ∃x P(x) que sea verdadero, donde
c no es un miembro arbitrario del universo, sino para el que P(c) es verdadero.
❖ Regla de generalización universal (GU):

Es la regla que establece ∀xP(x) es verdadero si P(c) lo es donde c es miembro arbitrario
del universo del discurso.
❖ Regla de generalización existencial (GE):

Es una regla que se usa para concluir que ∃ 𝑥 𝑃(𝑋) es verdadero, cuando P© lo es, donde x
es un miembro particular del universo del discurso.
REGLAS DE INTERCAMBIO DE CUANTIFICADORES
a) ∀ x P(x) Ξ ∃ x ~P(x)
b) ∃ x P(x) Ξ ∀ x ~P(x)
c) ∀ x ~P(x) Ξ ∃ x P(x)
d) ∃ x ~P(x) Ξ ∀ x P(x)
Ejemplos:
∃ x (C(x) ^ B(x))
∀ x (B(x)→A(x))
∵ ∃x(C(x) Â(x))
Observación:
Basta que haya una proposición donde haya existencia la tesis o conclusión final debe
ser con existencia.
▪ E1: ∃x(C(x)^B(x)), ∀x(B(x)→A(x)) (premisa) POR TANTO SE CUMPLE:

∃x(C(x)Â(x))
▪ P1: ∃x(C(x)^B(x)) (premisa)
▪ P2: C(a)^B(a) (P1, EE)
▪ P3: ∀x(B(x)→A(x)) (premisa)
▪ P4: B(a)→A(a) (P3, EU)
▪ P5: B(a) (P2, simplificación)
▪ P6: A(a) (P4,P5,MP)
▪ P7: C(a) (P2, simplificación)
▪ P8: C(a) ^ A(a) (P6,P7, combinación)
▪ P9: ∃x(C(x)Â(x)) (P8, GE)
E2:
▪ ∀ x(P(x) ν Q(x))
▪ ∃ x ~P(x)
▪ ∀ x(~Q(x) ν R(x))
▪ ∀x(S(x)→~R(x))
∃ x ~S(x)
E3:
▪ P1: ∀x[ W(x)→C(x)]

▪ P2: ∀x[W(x)^L(x)→Q(x)]
▪ P3: W(r)^~Q(r)
▪ P4: Q(i)^~C(i)
~L(r)^~W(i)
▪ P5: W(r)^L(r)→Q(r) (P2, EU)

▪ P6: ~Q(r) (P3,SC)
▪ P7: ~(W(r)^ L(r)) (P5,P6,MT)
▪ P8: ~W(r)ν ~L(r) (P7, Morgan)
▪ P9: W(r) (P3, SC)

▪ P10: ~L(r) (P8,P9, SD)
▪ P11: W(i) →C(i) (P1, EU)
▪ P12: ~(C(i)) (P4,SC)
▪ P13: ~W(i) (P11,P12;MT)
▪ P14: ~L(r)^~W(i) (P10,P13,combinacion)
E4:
▪ P1: ∀x(stgo(x)→km(x))
▪ P2: ∃x(stgo(x)^~océano(x))
∃x (km(x)^~oceano(x))
▪ P3: stgo(a)^~oceano(a) (P2, EE)

▪ P4: stgo(a)→km(a) (P1,EU)
▪ P5: stgo(a) (P3, simplificacion)
▪ P6: km(a) (P4,P5,modus ponens)
▪ P7: ~oceano(a) (P3, simplificacion)
▪ P8: km(a)^~oceano(a) (P6,P7, combinacion)
▪ P9: ∃x(km(x)^~oceano(x)) (P8, generalización de la existencia)
PREDICADOS
Consiste en reemplazar frases proposicionales por variables proposicionales para

luego aplicar el cálculo proposicional y llegar a una conclusión que puede ser verdad
o falso.
Ejemplo:
Todas las personas de la ciudad de Ica están a menos de 10 km del océano. Alguien
de Ica no ha visto nunca el océano. Entonces quien está a menos de 10 km del océano
nunca lo ha visto.
Llevando a predicados.
Ica(x): x es de Ica
Km(x): está a menos de 10km del oceano
oceano(x): x ha visto el oceano
Entonces el argumento (conjunto de proposiciones)

Queda:
∀ x (Ica(x)→km(x))
∃ x (Ica(x)^~oceano(x))
∃ x (km(x)^~oceano(x))
Observa que cuando es para todo se pone una implicancia cuando es existencia se
pone la conjunción.
E2: Si la banda no pudiera tocar rock o las bebidas no llegasen a tiempo, la fiesta de
año nuevo tendría que cancelarse y Alicia se enojaría. Si la fiesta se cancelara habría
que devolver el dinero. No se devolvió el dinero. Por lo tanto, la banda pudo tocar
rock.
p: la banda pudo tocar

q: las bebidas llegaron a tiempo
r: la fiesta se cancela
s: Alicia se enoja
d: devolver el dinero
▪ P1: ~p ν ~q → r ^ s
▪ P2: r → d
▪ P3: ~d
▪ P4: ~r (P2, P3, MT)

▪ P5: ~r ν ~s (P4, adición)
▪ P6: ~(r ^ s) (P5, Morgan)
▪ P7: ~( ~p ν ~q) (P6, P1, MT)
▪ P8: ~(~(p ^ q)) (P7, Morgan)
▪ P9: p ^ q (P8, doble negación)
▪ P10 p (P9 SC)
E3:
A alguien del curso le gusta resolver problemas de geometría. Todas las personas a
las que le gusta resolver problemas de geometría se preocupan por saber
trigonometría. Por tanto, hay alguien en este curso que se preocupa por resolver
problemas de trigonometría.
P(x): x es alguien del curso

Q(x): a x le gusta resolver problemas de geometría
R(x): x se preocupa por saber trigonometría
▪ P1: ∃ x (P(x)^Q(x))
▪ P2: ∀ x (Q(x)→R(x))
∃ x (P(x)^R(x))
▪ P3: P(a)^Q(a) (P1, EE)

▪ P4: Q(a)→R(a) (P2, EU)
▪ P5: Q(a) (P3, SC)
▪ P6: ~Q(a) v R(a) (P4, condicional)
▪ P7: Q(a)^R(a) (P5, P6, absorcion)
▪ P8: R(a) (P7, SC)
▪ P9: P(a) (P3, SC)
▪ P10: P(a)^R(a) (P8, P9, combinacion)
▪ P11: ∃x(P(x)^R(x)) (P10, EE)
Si Juan toma el autobús, luego Juan pierde su cita. Si el autobús llega tarde, diseñar la expresión lógica
Formulación
𝑅 ⟶ (𝑄 → 𝑃)
𝑅 → (∼ 𝑄 ∨ 𝑃)
∼ 𝑅 ∨∼ 𝑄 ∨ 𝑃
∼𝑄
Q ∼𝑄∨𝑃
P 𝑆 =∼ 𝑅 ∨∼ 𝑄 ∨ 𝑃
∼𝑅
Simbología
• 𝐴∪𝐵 A
𝐴∪𝐵
• 𝐴∩𝐵 A
𝐴∩𝐵
• ̅̅̅̅̅̅̅
𝐴∪𝐵
• ̅̅̅̅̅̅̅
𝐴∩𝐵
((𝑝 ∧ 𝑞 ∧ 𝑟) ∨ (∼ 𝑝 ∧ 𝑞 ∧ 𝑟) ∨ (𝑝 ∧ 𝑞 ∧ 𝑟)) ∧ (𝑠 ∨ 𝑥)
((𝑝 ∧ 𝑞 ∧ 𝑟) ∨ (∼ 𝑝 ∧ 𝑞 ∧ 𝑟)) ∧ (𝑠 ∨ 𝑥)
[(𝑞 ∧ 𝑟) ∧ (𝑝 ∨∼ 𝑝)] ∧ (𝑠 ∨ 𝑥)
[(𝑞 ∧ 𝑟)] ∧ (𝑠 ∨ 𝑥)
MÉTODOS DE DEMOSTRACIÓN
❖ Método Directo
(𝑝 → 𝑞)
Se basa en el principio de la ley lógica implicancia o condicional, es decir, se parte del hecho
que es verdadero y se debe llegar a que la tesis “q” también es verdadera.
Ejemplo
• Si m es impar entonces 𝑚2 es impar.

Demostración
Sea 𝑚 = 2𝑘 + 1; 𝑘 ∈ 𝑍 + y definición de 𝑚 impar entonces si elevamos 𝑚 al cuadrado
𝑚2 = (2𝑘 + 1)2 = 2𝑘 2 + 2𝑘 + 1
= 2(𝑘 2 + 𝑘) + 1
Cerradura/completitud
Pero al ser 2(𝑘 2 + 𝑘) es par, lo reemplazamos 𝑘 2 + 𝑘 por 𝑘1 , 2𝑘1 + 1 es impar por ende si 𝑚
es impar 𝑚2 es impar.
❖ Método Indirecto
Se basa en la contra positiva es decir demostrar 𝑝 → 𝑞 es equivalente a demostrar ~𝑞 → ~𝑝.
Por ejemplo demostrar
Si 𝑛2 es impar entonces 𝑛 es impar
p → q
es más fácil demostrar con la contra positiva es decir:
Si 𝑛 es par entonces 𝑛2 es par
~𝑞 → ~𝑝
Lo cual es cierto por ser 𝑛 par entonces 𝑛 = 2𝑘, 𝑘 ∈ 𝑍 + elevando al cuadrado 𝑛2 = 4𝑘 ⇒

2(2𝑘)2 es par
Por equivalencia quedaría demostrado que si 𝑛2 es impar entonces 𝑛 es impar
• Método por el absurdo

Implica negar la tesis asumiéndola como verdad al llegar a una contradicción, entonces la
tesis asumida es falsa por ende es verdad la tesis inicial.
Por ejemplo:
√2 es irracional
Demostración
Negando la tesis decimos que √2 es racional; al ser racional puede expresarse como un
quebrado
Entonces:
𝑝
√2 =
𝑞
Donde p y q son números primos entre si es decir su divisor común es 1
Elevando al cuadrado
𝑝2
2 = 2 → 2𝑞 2 = 𝑝2
𝑞
Por ende 𝑝2 es par, es decir tiene un divisor que es 2 y puede representarse p como 2k;
donde 𝑘 ∈ 𝑍 +
Reemplazando:
2𝑞 2 = (2𝑘)2 = 4𝑘 2
𝑞 2 = 2𝑘 2 → 𝑞 2 es par y tiene como divisor a 2
Pero se había asumido inicialmente que p y q eran primos entre sí; es decir solo el número
1 los dividía, pero observamos que tienen otro divisor 2; por ende no son primos entre si o
relativos, implica que la tesis asumida de que √2 era racional es falsa por ende
√2 𝑒𝑠 𝑖𝑟𝑟𝑎𝑐𝑖𝑜𝑛𝑎𝑙.
PROPIEDAD DEL BUEN ORDEN
Todo conjunto que pertenece a los números enteros positivos tiene un elemento mínimo
llamado cota inferior.
Demostración:
Sean los números enteros positivos 1, 2, 3,…,𝑥1 , 𝑥2 ,…, 𝑥𝑛 ; si extraemos un subconjunto

(𝑥1 , 𝑥2 , … , 𝑥𝑛 )
𝑥1 debe ser el elemento minimo si negamos ello quiere decir que hay otro elemento minimo.
Tendría que ser 𝑥1 − 1 pero 𝑥1 − 1 ya no pertenece a dicho subconjunto, por ende hay una
contradicción.
Por lo tanto 𝑥1 es el mínimo de dicho subconjunto.

PRINCIPIO DE INDUCCIÓN MATEMÁTICA EN 𝐙 +

Se debe cumplir lo siguiente:
1) 𝑃(0) 𝑒𝑠 𝑣𝑒𝑟𝑑𝑎𝑑
2) 𝑃(𝑘) → 𝑃(𝑘+1) 𝑒𝑠 𝑣𝑒𝑟𝑑𝑎𝑑
∴ 𝑃(𝑚) 𝑒𝑠 𝑣𝑒𝑟𝑑𝑎𝑑 𝑝𝑎𝑟𝑎 𝑐𝑢𝑎𝑙𝑒𝑠𝑞𝑢𝑖𝑒𝑟𝑎 𝑚, 𝑚 𝑝𝑒𝑟𝑡𝑒𝑛𝑒𝑐𝑒 𝑎 𝑍 +
Demostración:
De igual manera usamos el método del absurdo y decimos que existe un conjunto que
pertenece a 𝑍 + tal que 𝑃(𝑥) 𝑒𝑠 𝑓𝑎𝑙𝑠𝑜.
Sea el conjunto x = { 𝑥 1, 𝑥2, … , 𝑥𝑘 } entonces por la propiedad del buen orden, x tiene un
elemento mínimo en este caso 𝑥1 y 𝑃(𝑥1 ) es falso, entonces:
𝑥1 − 1 ≠ 0 𝑦𝑎 𝑞𝑢𝑒 𝑃(0) Es verdadero, entonces 𝑥1 − 1 > 0
Pero por la 2da proposición del principio de inducción matemática:

𝑃(𝑥 1 −1) => 𝑃(𝑥 1 −1 + 1) 𝑒𝑠 𝑣𝑒𝑟𝑑𝑎𝑑
Pero 𝑃(𝑥 1 −1 + 1) = 𝑃(𝑥1 ) es verdad, lo cual contradice que 𝑃(𝑥1 ) sea falso.
Por ende la existencia de que había un conjunto x en el cual su o sus elementos hacían que
𝑃(𝑥1 ) sea falso no se da.
∴ 𝑃(𝑚) 𝑒𝑠 𝑣𝑒𝑟𝑑𝑎𝑑 ∀ 𝑛 𝑞𝑢𝑒 𝑝𝑒𝑟𝑡𝑒𝑛𝑒𝑐𝑒 𝑎 𝑍 +
E1:
• Demostrar que 𝑎2𝑛 − 1 es divisible por a+1.
Solución:
Si n=1
𝑎2 − 1 = (𝑎 − 1)( 𝑎 + 1)
(𝑎 − 1)( 𝑎 + 1)
=𝑎−1
( 𝑎 + 1)
𝑎2 − 1 𝑒𝑠 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑝𝑜𝑟 𝑎 + 1
Si n=k
𝑎2𝑘 − 1, asumiendo que es verdad (Hipótesis inductiva) es divisible por a+1
Si n=k+1
𝑎2(𝑘+1) − 1 = 𝑎2𝑘+2 − 1
𝑎2 . 𝑎2𝑘 − 1
𝑎2 (𝑎2𝑘 − 1) + (𝑎2 − 1)
Por hipótesis Es divisible

inductiva es por (a+1)
divisible por
(a+1)
∴ 𝑎2(𝑘+1) − 1 𝑒𝑠 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑝𝑜𝑟 (𝑎 + 1)
∴ 𝑎2(𝑛) − 1 𝑒𝑠 𝑑𝑖𝑣𝑖𝑠𝑖𝑏𝑙𝑒 𝑝𝑜𝑟 (𝑎 + 1)
E2:
• Demostrar que 6.7𝑚 − 2. 3𝑚 es múltiplo de 4.

Solución:
Si m=1
6.71 − 2. 31 = 36 ……………. Es múltiplo de 4
Si m=k
6.7𝑘 − 2. 3𝑘 , asumiendo que es verdad (Hipótesis inductiva)
Si m=k+1
6.7𝑘+1 − 2. 3𝑘+1 = 6.7𝑘+1 − 2. 3𝑘+1 − 2.3𝑘 . 4 + 2.3𝑘 . 4 Sumando y restando 2.3𝑘 . 4
Desdoblando el 3 k+1
6.7𝑘+1 − 3.2. 3𝑘 − 2.3𝑘 . 4 + 2.3𝑘 . 4
= 6.7𝑘 . 7 − 7. (2. 3𝑘 ) + 4. (2.3𝑘 )
= 7. (6.7𝑘 − 2. 3𝑘 ) + 4. (2.3𝑘 )
4° H.I 4°
∴ 6.7𝑚 − 2. 3𝑚 𝑒𝑠 𝑚𝑢𝑙𝑡𝑖𝑝𝑙𝑜 𝑑𝑒 4
E3:
• (r(cos 𝜃 + 𝑖 sin 𝜃))𝑛 = r 𝑛 (cos(𝑛𝜃) + 𝑖 sin(𝑛𝜃)) ; n∈Z

Probar que cumple para n que pertenece a z
(r(cos 𝜃 + 𝑖 sin 𝜃))𝑛 =rn ( (cosn 𝜃 + 𝑖 sin 𝑛𝜃))
Para n=0
(r(cos 𝜃 + 𝑖 sin 𝜃))𝑛 = (r(cos 𝜃 + 𝑖 sin 𝜃))0 = 1
Para n>0
(r(cos 𝜃 + 𝑖 sin 𝜃))1 = r1 (cos(1. 𝜃) + 𝑖 sin(1. 𝜃))
= r(cos 𝜃 + 𝑖 sin 𝜃)
Para n=k (Hipótesis inductiva)
(r(cos 𝜃 + 𝑖 sin 𝜃))𝑘 = r 𝑘 (cos(𝑘𝜃) + 𝑖 sin(𝑘𝜃))
Para n=k+1
𝑘+1
(r(cos 𝜃 + 𝑖 sin 𝜃)) = r 𝑘+1 (cos 𝜃 + 𝑖 sin 𝜃)𝑘 (cos 𝜃 + 𝑖 sin 𝜃)1
= 𝑟. r 𝑘 (cos(𝑘. 𝜃) + 𝑖 sin(𝑘. 𝜃))(cos 𝜃 + 𝑖 sin 𝜃)
= r 𝑘+1 [(cos(𝑘. 𝜃) cos θ − sin(𝑘. 𝜃) sin 𝜃)+
𝑖(cos(𝑘. 𝜃) sin 𝜃 + sin(𝑘. 𝜃) cos 𝜃)]
=r 𝑘+1 (cos((𝑘 + 1). 𝜃) + 𝑖 sin((𝑘 + 1). 𝜃))
Para n<0
Sea n= -m, m ∈ 𝑍+
(r(cos 𝜃 + 𝑖 sin 𝜃))𝑛 = (r(cos 𝜃 + 𝑖 sin 𝜃))−𝑚

1 cos(𝑚𝜃)−𝑖 sin(𝑚𝜃)
=r-m ((cos 𝜃+𝑖 sin 𝜃)𝑚 )(cos(𝑚𝜃)−𝑖 sin(𝑚𝜃))
Multiplicando por su conjugada tanto al numerador como denominador.

1 cos(𝑚𝜃)−𝑖 sin(𝑚𝜃)
=r-m ((cosm 𝜃+𝑖 sin 𝑚𝜃) )(cos(𝑚𝜃)−𝑖 sin(𝑚𝜃))
Recordando el seno de un ángulo negativo sale el signo como negativo y del coseno siempre
es positivo.
=r-m ( cos(𝑚𝜃) − 𝑖 sin(𝑚𝜃) )………. Pero n=-m ➔ -n=m
= r -m ( cos(−𝑛. 𝜃) − 𝑖 sin(−𝑛. 𝜃))
=r n( cos(𝑛. 𝜃) + 𝑖 sin(𝑛. 𝜃))
Por lo tanto se cumple que : cumple para n que pertenece a z
(r(cos 𝜃 + 𝑖 sin 𝜃))𝑛 =r n( cos(𝑛. 𝜃) + 𝑖 sin(𝑛. 𝜃))
PROPIEDADES
1) ∑𝑛𝑖=1 𝑘 = 𝑘. ∑𝑛𝑖=1 1 = kn demostración = k+k+…………….+k=kn
2) ∑𝑛𝑖=1 𝑘𝑎𝑖 = 𝑘. ∑𝑛𝑖=1 𝑎𝑖 =ka1+ka2+……………..+k an =k(a1+ a2++……………..+ an)

=k*∑𝑛𝑖=1 𝑎𝑖
3) ∑𝑛𝑖=1(𝑎𝑖 ± 𝑏𝑖 ) = ∑𝑛𝑖=1 𝑎𝑖 ± ∑𝑛𝑖=1 𝑏𝑖
4) ∑𝑛𝑖=𝑚(𝐹𝑖 − 𝐹𝑖−1 ) = 𝐹𝑛 − 𝐹𝑚−1 (propiedad telescópica)
Ejemplo de telescópica:
∑ 5𝑘
𝑘=1
∑(5𝑘 − 5𝑘−1 ) = 5𝑛 − 50
𝑘=1
𝑛 𝑛
∑ 5𝑘 − ∑ 5𝑘−1 = 5𝑛 − 1
𝑘=1 𝑘=1
𝑛 𝑛
1
∑ 5 − ∑ 5𝑘 = 5𝑛 − 1
𝑘
5
𝑘=1 𝑘=1
𝑛
4
∑ 5𝑘 = 5𝑛 − 1
5
𝑘=1
𝑛
5 𝑛
∑ 5𝑘 = (5 − 1)
4
𝑘=1
DIAGRAMAS DE KARNAUGHT
6-9 COMPRUEBE LOS AGRUPAMIENTOS

A\BC 00 01 11 10
𝑓2 = (1,2,3,4,5,7)
0 1 1 1
𝑓2 = 𝐶 + 𝐴𝐵̅ + 𝐴̅𝐵 1 1 1 1
A\BC 00 01 11 10
𝑓3 = (0,1,3,6)
0 1 1 1
𝑓3 = 𝐴𝐵̅ + 𝐴̅𝐶 + 𝐴𝐵𝐶̅ 1 1
A\BC 00 01 11 10
𝑓4 = (0,1, ,4,5,6)
0 1 1
𝑓4 = 𝐵̅ + 𝐴𝐶̅ 1 1 1 1
A\BC 00 01 11 10
𝑓6 = (3,4,5,6)
0 1
𝑓6 = 𝐴𝐵̅ + 𝐴𝐶̅ + 𝐴̅𝐵𝐶 1 1 1 1
6-13
0,1,2,3,16,17,18,19,10,14 AB\CDE 000 001 011 010 110 111 101 100
𝑓1 = ( )
, 15,13,24,30,31,29 00 1 1 1 1
01 1 1 1 1
11 1 1 1 1
10 1 1 1 1
AB\CDE 000 001 011 010 110 111 101 100

𝑓2 = (9,11,25,27,29,31,21,23) 00
01 1 1
𝑓2 = 𝐴𝐵̅𝐸 + 𝐵𝐶E
11 1 1
10 1 1 1 1
AB\CDE 000 001 011 010 110 111 101 100

𝑓3 = (0,1,16,17,4,5,20,21,28,29,31) 00 1 1 1 1
01
𝑓3 = 𝐵̅𝐷
̅ + 𝐴𝐶𝐷
̅ + 𝐴𝐵𝐶𝐸
11 1 1 1
10 1 1 1 1
AB\CDE 000 001 011 010 110 111 101 100

𝑓4 = (8,16,24,0,4,12,28,20) 00 1 1
01 1 1
̅ 𝐸̅
𝑓4 = 𝐷
11 1 1
10 1 1
AB\CDE 000 001 011 010 110 111 101 100

𝑓5 = (0,1,2,3,4,6,9,10,11,13,33,34,35,36) 000 1 1 1 1 1 1
001 1 1 1 1
̅̅̅̅̅̅̅̅ + 𝐴̅𝐵̅𝐷
𝑓5 = 𝐴𝐵𝐶𝐷 ̅ 𝐸̅
011
010
110
111
101
100 1 1 1 1
AB\CDE 000 001 011 010 110 111 101 100

𝑓6 = 𝐴̅𝐵𝐶𝐷
̅ 𝐹 + 𝐵𝐶𝐷
̅ 𝐸𝐹̅ + 𝐵𝐶𝐷𝐸̅ + 𝐴𝐵𝐶𝐷
̅ + 𝐴𝐵𝐶𝐸𝐹̅
000
001
011 1 1 1 1 1
010
110
111
101
100 1 1 1 1 1 1 1
AB\CDE 000 001 011 010 110 111 101 100

000 1 1
𝑓7 = 𝐴𝐵̅𝐸𝐹̅ + 𝐴̅𝐵̅𝐶𝐸̅ + 𝐴̅𝐶 𝐷
̅ 𝐸𝐹̅
001 1 1
011 1 1 1 1 1
010
110
111
101 1 1
100 1 1
ABC\DEF 000 001 011 010 110 111 101 100

000
𝑓8 = 𝐴̅𝐵𝐶̅ + 𝐴𝐶𝐷 001
011
010 1 1 1 1 1 1 1 1
110 1 1 1 1
111
101
100 1 1 1 1
CARDINALIDAD
Dados los conjuntos:
A, B la cardinalidad en A o B es
|A U B| = |A| + |B| - |AB|
• Cardinalidad es cantidad de elementos.
Demostración:
Sea: A/B = { x1, x2, x3,… , xr}
B/A = { y1, y2, y3,… , ys}
Elementos que están en A y B = {s1, s2, s3, … , sm}
|AUB| = r+m+s … (α)
Ahora
|A| = r+m
|B| = s+m |A| + |B| - |AB| = r+m+s+m-m
|AB| = m = r+s+m .. (β)

Como α= β
|AUB| = |A| + |B| - |AB|
Para un número finito de conjuntos A1, A2, A3,…, An
|A1 U A2 U A3 U ,,, U An| = ∑𝑖 |𝐴𝑖| - ∑𝑖<j |𝐴𝑖 ∩ 𝐴𝑗| + ∑𝑖<j<k |𝐴𝑖 ∩ 𝐴𝑗 ∩ 𝐴𝑘| - …
+ (−1)𝑛+1 |A1 ∩ A2 ∩ … ∩ An|
E1.
Determine el número de enteros positivos “n” tales que 1 ≤ n ≤ 100 y “n” no es divisible entre
2,3 o 5
Una vez resuelto plantee el plantee el algoritmo para hallar cuales son estos números.
U = 100 |A| + |B| + |C| - |AB| - |AC| - |BC| + |ABC|
A = 2̇ 50 + 33 + 20 - 16 – 10 – 6 + 3 = 74
B = 3̇ 100 – 74 = 26
C = 5̇
i=1
While i<=100
If (i%2!=0 y i%3!=0 y i%5!=0 y i%6!=0 y i%10!=0 y i%10!=0 y ic%30!=0)
Imprime i
end if
i=i+1
End while
E2.
De 200 estudiantes, 50 toman el curso de matemáticas discretas, 140 el curso de economía

y 24 ambos, como ambos cursos programaron sus exámenes el día siguiente, solo los
estudiantes que no estén en ninguno de estos cursos podrán ir a la fiesta de la noche
siguiente, se quiere ver cuantos estudiantes irán a la fiesta.
Si se tiene 4 conjuntos e interceptados de 3 en 3 es el vacío a cuanto equivale la fórmula:
|AUBUCUD| = |A| + |B |+ |C| + |D| - |A∩B| - |B∩C| - |C∩D| - |A∩D| + |A∩B∩C| + |A∩C∩D|
+ |B∩C∩D| - |A∩B∩C∩D|
= |A| + |B |+ |C| + |D| - ( |A∩B| + |B∩C| + |C∩D| + |A∩D| )
RECURSIVIDAD
Es un proceso repetitivo de la función recursiva llamándose así mismo varias veces hasta
retornar al punto de partida.
Ejemplo: plantear la función recursiva del factorial de un número.
1 𝑚=0
𝑓𝑎𝑐𝑡(𝑚) = {
𝑚 ∗ 𝑓𝑎𝑐𝑡(𝑚 − 1) 𝑠𝑖 𝑚 ≥ 1
fact(2) =2*fact(2-1)=2*fact(1)=2*1*fact(0)=2*1*1=2
E2.
Si se tiene
1+2+3+………+ m
Su función recursiva es
1 𝑠𝑖 𝑚 = 1
𝑆(𝑚) = {
𝑚 + 𝑆(𝑚 − 1) 𝑠𝑖 𝑚 > 1
S(3)=3+S(2)=3+2+S(1)=3+2+1=6
E3.
La función recursiva de la potencia de un número donde m є N es
1 𝑚=0
𝑝𝑜𝑡(𝑥, 𝑚) = {
𝑥. 𝑝𝑜𝑡(𝑥, 𝑚 − 1) 𝑠𝑖 𝑚 > 0
Pot(3,2)=3*pot(3,1)=3*3*pot(3,0)=3*3*1=9
E4
Dada el algoritmo plantee su función recursiva
MCD(x , y)
Mientras (x!=y)
If (x>y)
x=x-y
Else
y=y-x
End if
Fin mientras
Return x
Fin
Mcd(4,6)=
Y=6-4=2
X=4-2=2
Función Recursiva
𝑥 𝑥=𝑦
𝑀𝐶𝐷(𝑥, 𝑦) = {𝑀𝐶𝐷(𝑥 − 𝑦, 𝑦) 𝑥>𝑦
𝑀𝐶𝐷(𝑥, 𝑦 − 𝑥) 𝑥<𝑦
E 4.
Es Aᵉ Matriz exponencial
P1 Lee m//Dimensión
P2 for(i=1 to m)
for(j=1 to m)
lee A[i][j]
B[i][j] =A[i][j]
fin for
fin for
P3 Lee e// Lee exponente
P4 for x=2 to e
For i=1 to m
For j=1 to m
P[i][j]=0
For k=1 to m
P[i][j] = P[i][j]+A[i][k]*B[k][j]
Fin for
Fin for
For i=1 to m
For j=1 to m
B[i][j] =P[i][j]
fin for
fin for
Fin for //e
P5 //impresión
For i=1 to m
For j=1 to m
Imprime P[i][j]
Fin for
Fin for
𝐴 𝑒=1
𝑃𝑚(𝐴, 𝑒) {
𝐴𝑥 𝑃𝑚(𝐴, 𝑒 − 1) 𝑒 > 1
ALGUNOS ALGORITMOS RECURSIVOS
Accion Buscar()
Inicio A(1)=100,A(2)=20 , A(3)=35
Leer V
r=BuscaRecur(A,1,n,V)
si r=n+1
Escribir “No existe Valor”
FinSi
Else
Escribir “si existe el Valor en la posicion”+r
Fin
Accion BusSecRecur(A,i,n,V)
Inicio
si i<=n
si( A[i]=V)
retornar i
sino
Retornar BusSec Buscar(A, i+1,n,V)
finsi
finsi
Fin
No existe, 𝑖>𝑛
𝑓(A, i, N, V) = {
f(A, i + 1, n, V), 𝑖≤𝑛
Accion Buscar(A,N)
Inicio
pos=0
Leer Val
Escribir BusBin(A,pos,l-1)
Si pos=0
Escribir V “No se encuentra#
Sino
Escribir V “Se encontró en la posision” pos
Finsi
Accion Busbin(A,izq,der,val)
Inicio
Si izq=der
Retornar izq
Sino
X=(izq+der)/2
Si val<A[x]
Retornar BusBin(A,izq, k,val)
Sino
Retornar BusBin(A,der+1,j,val)
Finsi
Finsi
Fin
• A es el arreglo
• N es el tamaño del arreglo
• Val es el valor a buscar
E1.
n+1 si m = 0
ACK(m, n) { ACK(m − 1,1) si n=0
ACK(m − 1, ACK(m, n − 1)) 𝑠𝑖 𝑚 ≠ 0 𝑦 𝑛 ≠ 0
ACK(3,2)=?
Hallar: ACK(1,1) =?
ACK(1,1) = ACK(0,ACK(1,0))
=ACK(0,ACK(0,1))
=ACK(0,2)
=3
E2.
Si queremos repartir n objetos en k cajas iguales, podemos utilizar la formula recursiva
S(n,k) = S(n-1,k-1)+k*S(n-1,k)
Satisface:
S(n,1)=1, S(n,n)=1
Implemente su Algoritmo recursivo colocar 3 bolas de diferentes colores en 2 cajas iguales

{𝑎, 𝑏, 𝑐}
S(3,2)=S(2,1)+2*S(2,2)=1+2*1=3
a bc c ab a cb a
Accion repartir (n,k)
Inicio
Leer n,k
Si(k=1) || (n==k)
Retornar 1
Sino
Retornar repatir(n-1,k-1) + k*repartir(n-1,k)
Finsi
Fin
OTRO ALGORITMO BUSQUEDA RECURSIVA
LA FUNCION SERÍA :
BusquedaB(lista, valor, 0, n_elementos-1)={
Lo encontró Si lista[mitad] == v
BusquedaB(lista, v, mitad + 1, sup); Si (v > lista[mitad])
BusquedaB(lista, v, inf, mitad - 1); Si v< lista[mitad }
RELACIÓN RECURSIVA
Es un proceso repetitivo en el que cada término se puede expresar en términos anteriores.
Sn=C1 Sn-1+ C2 Sn-2+….+ Ck Sn-k
Donde S0, S1 son condiciones iniciales
E1.
𝑆𝑛 =2*𝑆n-1+ 1, 𝑆0 =0
Halle la formula iterativa (formula no recursiva)
=2 x(2 x 𝑆n-2+1) + 1 = 22 𝑆n-2+2+1 , Así hasta cuando sea S n-n
22 (2S n-3 +1)+2+1=23 S n-3+22 +2+1
23 (2S n-4 +1)+22 +2+1=24 S n-4 +23 +22 +2+1
………….
=2𝑛 𝑆0 + 2𝑛−1 + ⋯ … … +2+1
= 2𝑛 𝑆0 + 2𝑛−1 + ⋯ … … + 22 + 2 + 1
= 2𝑛 ∗ 0 + 2𝑛−1 + ⋯ … … + 22 + 2 + 1
= 2𝑛 ∗ 0 + 2𝑛−1 + ⋯ … … + 22 + 2 + 1 s=2𝑛−1 + ⋯ … … + 22 + 2 + 1
= 2𝑛−1 + ⋯ … … + 22 + 2 + 1 = 2𝑛 − 1 formula iterativa 2*s=2n + 2 n-1 +2 n-2 +…+22+2+1-1

2s=2n + s-1-> 2s-s=2n -1->s=2n -1
E2.
Dada la relación recursiva

𝑛 𝑛
𝑆𝑛 = 𝑆 [ 2 ] + 𝑆 [ 3 ] ; 𝑆0 = 0 𝑦 𝑆1 = 1
Halle 𝑆16
𝑆16 = 𝑆8 + 𝑆5 Donde [] es mínimo entero
= 𝑆4 + 𝑆2 + 𝑆2 + 𝑆1
= 𝑆2 + 𝑆1 + 𝑆1 + 𝑆0 + 𝑆1 + 𝑆0 + 𝑆1 = S
S1+S0+𝑆1 + 𝑆1 + 𝑆0 + 𝑆1 + 𝑆0 + 𝑆1 =5
E3.
Haga la relación recursiva, para la cantidad de movimientos en el problema de las torres de

Hanoi y muestre la fórmula iterativa.
𝑇𝑛 = 2 𝑇𝑛−1 + 1
𝑇0 = 0
𝑇1 = 1
𝑇2 = 3
=2𝑛 − 1
E4.
Dado 𝑆𝑛 = 3 𝑆𝑛−1 ; 𝑆0 = 1
Halle 𝑆6
𝑆6 = 3𝑆5
= 3 . 3𝑆4
= 3 . 3 .3 𝑆3
= 33 . 3 𝑆2
= 34 . 3 𝑆1
= 35 . 3 𝑆0
= 36 . 1 = 729
RECURRENCIAS RECURSIVAS. HALLAR LA SOLUCIÓN ITERATIVA DE LA FUNCIÓN

DE FIBONACCI.
Fn=Fn-1+Fn-2
CONGRUENCIA
Es un término usado en la teoría de números para designar que dos números enteros a y b
tienen el mismo resto al dividirlos por un número natural m≠0, llamado el módulo, esto se
expresa utilizando la notación
𝑎 ≅ 𝑏(𝑚𝑜𝑑 𝑚)
𝑎 − 𝑏 = 𝑘𝑚
Se lee a congruente con b módulo m
• El resto de a entre m es el resto de b entre m

𝑎 𝑚𝑜𝑑 𝑚 ≈ 𝑏 𝑚𝑜𝑑 𝑚
• También se puede decir que m divide exactamente a la diferencia de a y b

𝑚|𝑎 − 𝑏
• “a” se puede escribir como la suma de b y un múltiplo de m

∃𝑘 ∈ℤ , 𝑎 = 𝑏 + 𝑘𝑚
PROPIEDADES
1. Reflexividad
𝑎 ≅ 𝑎 ( 𝑚𝑜𝑑 𝑚)
2. Simetría
Si 𝑎 ≅ 𝑏(𝑚𝑜𝑑 𝑚) entonces 𝑏 ≅ 𝑎(𝑚)
3. Transitividad
Si 𝑎 ≅ 𝑏(𝑚𝑜𝑑 𝑚) y 𝑏 ≅ 𝑐(𝑚𝑜𝑑 𝑚) entonces también 𝑎 ≅ 𝑐(𝑚𝑜𝑑 𝑚)
Ahora si 𝑎 ≅ 𝑏(𝑚𝑜𝑑 𝑚) y k es un entero entonces también se cumple:
• 𝑎 + 𝑘 ≅ 𝑏 + 𝑘(mod m)
• 𝑘𝑎 ≅ 𝑘𝑏(𝑚𝑜𝑑 𝑚)
• 𝑎𝑘 ≅ 𝑏 𝑘 (𝑚𝑜𝑑 𝑚) , 𝑘 > 0
EJERCICIOS PROPUESTOS
E1.
Si 𝑎 ≅ 𝑏(𝑚𝑜𝑑 𝑚) ↔ 𝑎 − 𝑏 = 𝑘𝑚 , 𝑘 𝜖 ℤ
Por hipótesis inductiva
𝑎𝑘 = 𝑏 𝑘 (𝑚𝑜𝑑 𝑚) ↔ 𝑎𝑘 − 𝑏 𝑘 = 𝑘1 𝑚 … (𝐻𝐼) , 𝑘1 ∈ ℤ
• Para n=k+1
𝑎𝑘+1 = 𝑏 𝑘+1 (𝑚𝑜𝑑 𝑚)
𝑎𝑘+1 − 𝑏 𝑘+1= 𝑎𝑘 . 𝑎 − 𝑏 𝑘 . 𝑏 + 𝑎𝑘 . 𝑏 − 𝑎𝑘 . 𝑏
= 𝑎𝑘 (𝑎 − 𝑏) + 𝑏(𝑎𝑘 − 𝑏 𝑘 )
= 𝑎𝑘 (𝑘𝑚) + 𝑏(𝑘1 𝑚)
𝑎𝑘+1 − 𝑏 𝑘+1 = (𝑎𝑘 𝑘 + 𝑏𝑘1 )𝑚
𝑎𝑘+1 − 𝑏 𝑘+1 = 𝑘3 𝑚 , 𝑘3 ∈ ℤ
𝑎𝑘 ≅ 𝑏 𝑘 ( 𝑚𝑜𝑑 𝑚)
E2.
𝑘𝑎 ≅ 𝑘𝑏(𝑚𝑜𝑑 𝑚)
Por hipótesis inductiva
𝑘𝑎 − 𝑘𝑏 = 𝑚𝑘1 , 𝑘1 ∈ ℤ
• 𝑛 =𝑘+1
(𝑘 + 1)𝑎 − (𝑘 + 1)𝑏 = 𝑚(𝑘 + 1)
𝑎𝑘 + 𝑎 − (𝑏𝑘 + 𝑏) = (𝑎𝑘 − 𝑏𝑘) + 𝑎 − 𝑏
= 𝑘1 𝑚 + 𝑘𝑚
= (𝑘1 + 𝑘)𝑚
= 𝑘2 𝑚 , ∃ 𝑘2 ∈ ℤ
𝑘𝑎𝑘 ≅ 𝑘𝑏 𝑘 (𝑚𝑜𝑑 𝑚)
E3.
𝐴 = {1,2,3}
𝐴𝑥𝐴 = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}
❖ 𝑅1 = {(1,1), (2,1), (3,3)}

Su matriz booleana
1 0 0
𝑀𝑅1 = [1 0 0]
0 0 1
▪ No es reflexiva
❖ 𝑅2 = {(1,2), (2,2), (3,3)}

Su matriz booleana
0 1 0
𝑀𝑅2 = [0 1 0]
0 0 1
❖ 𝑅3 = {(1,1), (1,2), (2,2), (2,3), (3,3)}

Su matriz booleana
1 1 0
𝑀𝑅3 = [0 1 1]
0 0 1
▪ Es reflexiva
❖ 𝑅4 = {(1,2), (2,1), (3,2), (3,3)}

Su matriz booleana
0 1 0
𝑀𝑅4 = [1 0 0]
0 1 1
▪ No es reflexiva
▪ No es simétrica
▪ No es transitiva
❖ 𝑅5 = {(1,2), (2,1), (1,1)}

Su matriz booleana
1 1 0
𝑀𝑅5 = [1 0 0]
0 0 0
▪ No es reflexiva
▪ Es simétrica
▪ Es transitiva
RELACIONES SQL
T1 T2
A B A B
1 2 1 3
3 1 2 2
2 1 3 2
Intersección
T1ᴖ T2
A B
2 2
Select t1.a, t2.b from t1, t2 where t1. a = t2 and t1.b = t2.b
PRODUCTO CARTESIANO DE RELACIONES
T1 x T3
A B C D
1 2 1 2
1 2 3 2
3 1 1 2
2 2 1 2
2 2 3 2
Select t1.a , t1.b, t3.c , t3.d from t1 , t3
DIFERENCIA
T1 - T2
A B
1 2
3 1
*En todas las relaciones intersección, producto cartesiano, diferencia se genera una nueva
relación.
NORMALIZACIÓN DE RELACIONES
Consiste en optimizar o reducir el espacio de almacenamiento, mediante la técnica de

separar relaciones, pero con identificadores comunes (llaves).
Nombre_producto Cantidad Precio Nro_RUC Razón_social Distrito Dirección

Varchar (35) Int(4) Double(5) Char(11) Varchar(35) Varchar(20) Varchar(35)

Leche 12 8 1008280889 La Alborada Lima Abancay
255
Cafecito 20 28 1008280889 La Alborada Lima Abancay
255
Atún 30 25 1008280889 La Alborada Lima Abancay
255
Leche 15 8 1008280887 El Trigal Comas Los Nogales
240
Cafecito 35 28 1008280887 El Trigal Comas Los Nogales
240
Leche 40 8 1008280886 Tupayachi La Victoria Aviación
530
Atún 40 25 1008280886 Tupayachi La Victoria Aviación
530
Cafecito 50 28 1008280888 El Carmen Rímac Las Flores
210
145*8=1 160
bytes
DEPENDENCIA FUNCIONAL
• Hay que llevar los campos dependientes a otra relación, dicha relación tendrá una
llave principal que servirá de nexo, a su vez, con la relación que queda, agregándole
la misma llave que en esta relación se llamará foránea y debe ser del mismo tipo, y
longitud.
• Cuando la relación tiene una descripción que amerita ponerle un identificador o llave
se procede a hacerlo.
Ejemplo:
Nro_RUC Razón_social
DNI  Nombres, apellidos, sexo
• Si existe por ejemplo nombre y apellido y no existe el DNI o código, debe agregarse
a la relación para luego descomponerla.
ID_producto  Nombre_producto, precio

Nro_RUC  Razón_social
ID_distrito  Distrito
ID_producto NOMBRE- Precio

(PK) PRODUCTO Double(5) 50*3=150
Char (10) Varchar(35) bytes
P001 Leche 8
P002 Cafecito 28
P003 Atún 25
ID_distrito (PK) distrito

Char (10) varchar(20) 120 bytes
D001 Lima
D002 Comas
D003 La Victoria
D004 Rímac
Nro_RUC (PK) Razón_social

Char (11) Varchar (35)
1008280889 La Alborada 184 bytes
1008280887 El Trigal
1008280886 Tupayachi
1008280888 El Carmen
TABLA OPTIMIZADA
ID_producto Nro_RUC ID_Distrito Cantidad Dirección

Varchar (10) Char(11) Char(10) Int(4) Varchar(35)
P001 1008280889 D001 12 Abancay

P002 1008280889 D001 20 Abancay
P003 1008280889 D001 30 Abancay
P001 1008280887 D002 15 Los Nogales
P002 1008280887 D002 35 Los Nogales
P001 1008280886 D003 40 Aviación
P003 1008280886 D003 40 Aviación
P002 1008280888 D004 50 Las Flores
8*70= 560
TÉCNICAS DE CONTEO
Concerniente a las técnicas para calcular posibilidades o maneras de realizar permutaciones
o combinaciones.
❖ Regla de la Suma
Cuando un suceso es independiente de otro y cada suceso tiene “n” maneras de realizarse
entonces la cantidad de posibilidades de “n” sucesos es igual a: 𝑛1 + 𝑛2 + ⋯ + 𝑛𝑘 𝑚𝑎𝑛𝑒𝑟𝑎𝑠.
Por ejemplo, si se tiene 4 candidatos demócratas y 3 republicanos ¿Cuántas posibilidades
hay de elegir un presidente de estos candidatos? Se observa que no hay ningún tipo de
dependencia, por ende la cantidad de posibilidades es: 4 + 3 = 7 𝑝𝑜𝑠𝑖𝑏𝑖𝑙𝑖𝑑𝑎𝑑𝑒𝑠
❖ Regla del Producto

Cuando se tiene sucesos en los cuales uno depende del otro entonces la cantidad de
posibilidades es: 𝑛1 ∗ 𝑛2 ∗ … ∗ 𝑛𝑘 𝑚𝑎𝑛𝑒𝑟𝑎𝑠. Por ejemplo, si se desea llegar de A a C ¿Cuántas
posibilidades hay?
A B C
Para ir de A a C hay: 3 ∗ 2 = 6 𝑝𝑜𝑠𝑖𝑏𝑖𝑙𝑖𝑑𝑎𝑑𝑒𝑠.
COMBINACIONES
Son aquellas en las que no interesa el orden.
𝑚!
𝐶𝑘𝑚 =
(𝑚 − 𝑘)! 𝑘!
PROPIEDADES
1) (𝑛1) = 𝑛
2) (𝑛𝑛) = 1
3) (𝑛0) = 1
4) (𝑛𝑘) = (𝑛−𝑘
𝑛
)
5) (𝑛𝑘) + (𝑘+1
𝑛
) = (𝑛+1
𝑘+1
)
Demostración:
𝑛! (𝑘 + 1) 𝑛! (𝑛 − 𝑘)
+
(𝑘 + 1)! (𝑛 − 𝑘)! (𝑛 − 𝑘)! (𝑘 + 1)!
𝑛! (𝑘 + 1 + 𝑛 − 𝑘) 𝑛! (𝑛 + 1) (𝑛 + 1)!
= = =
(𝑘 + 1)! (𝑛 − 𝑘)! (𝑘 + 1)! (𝑛 − 𝑘)! (𝑘 + 1)! (𝑛 − 𝑘)!
VARIACIONES
Ordinarias: Consiste en elegir de N elementos k elementos diferentes, interesa el orden. Su
fórmula es:
𝑛!
𝑉𝑛,𝑘 =
(𝑛 − 𝑘)!
Con repetición: Consiste en contabilizar de N elementos, sí interesa el orden y hay repetición,
su fórmula es: 𝑛𝑘 .
E1.
El Banco de la Nación dispone de 6 casillas para generar su clave web compuesta por
números ¿Cuántas posibilidades se dispone?
10 10 10 10 10 10
#𝑃𝑜𝑠𝑖𝑏𝑖𝑙𝑖𝑑𝑎𝑑𝑒𝑠 = 106 .
E2.
El Banco BBVA dispone de 4 casillas para la clave en el cajero automático, dispone de 10
números y 28 letras ¿Cuántas posibilidades hay de armar su clave si al menos hay un
número y una letra, si siempre debe existir aunque sea un número y una letra?
38 38 38 38 - 10 10 10 10 - 28 28 28 28
#𝑃𝑜𝑠𝑖𝑏𝑖𝑙𝑖𝑑𝑎𝑑𝑒𝑠 = 384 − 104 − 284 .
E3.
La SUNAT al generar la clave del contribuyente, dispone de 10 números, 28 letras y 4
caracteres especiales (@, ! , = , / ) ¿Cuántas posibilidades hay de armar la clave si siempre
debe haber un número especial?
4 38 38 38 38
#𝑃𝑜𝑠𝑖𝑏𝑖𝑙𝑖𝑑𝑎𝑑𝑒𝑠 = 4 ∗ 384 .
E4.
Para generar la clave de administrados de un servidor MS Windows Server 12. Se dispone
de 28 letras minúsculas y 28 letras mayúsculas, 10 números y 10 caracteres especiales si la
clave debe tener uno letra mayúscula y debe tener al menos un carácter especial , las demás
casillas se deben de completar con las letras minúsculas y números , la cantidad de
caracteres de la clave es de 6 elementos ¿cuántas posibilidades hay de armar la clave?
28 10 38 38 38 38
#𝑃𝑜𝑠𝑖𝑏𝑖𝑙𝑖𝑑𝑎𝑑𝑒𝑠 = 28 ∗ 10 ∗ 384 .
COMBINACIONES CON REPETICIÓN
Que vienen a ser muestras ordenadas de k elementos que pueden repetirse, no interesa el
orden, su fórmula es:
𝑛+𝑘−1
𝐶𝑅𝑛,𝑘 = ( )
𝑘
PERMUTACIONES CIRCULARES
Consiste en contabilizar la cantidad de intercambio teniendo un elemento estático en una
mesa circular.
𝑃𝑐 = (𝑛 − 1)!
El 1 es el elemento estático, el cual no puede ser rotado.

NÚMEROS DE STIRLING
Se utilizan para contabilizar las formas de repartir n elementos en k cajas diferentes sin que
haya ninguna vacía.
Si es en cajas distintas:
𝑘
𝑘
𝑆(𝑛,𝑘) 𝑘! = ∑(−1)𝑘−𝑖 ( ) 𝑖 𝑛
𝑖
𝑖=1
Si te interesa el orden y no hay repetición.
Ahora si se ubica en cajas iguales, las formas de repartir n elementos en k cajas iguales sin
que haya ninguna familia. Su fórmula es:
𝑘
1 𝑘
𝑆(𝑛,𝑘) = ∑(−1)𝑘−𝑖 ( ) 𝑖 𝑛
𝑘! 𝑖
𝑖=1
No hay repetición, no interesa el orden, también se puede usar las fórmulas:
𝑆(𝑛,𝑘) = 𝑆(𝑛−1,𝑘−1) + 𝑘 ∗ 𝑆(𝑛−1,𝑘)
Se satisface que 𝑆(𝑛,1) = 1 y 𝑆(𝑛,𝑛) = 1 para cajas iguales.
E1.
En una bodega hay 3 tipos diferentes de botellas ¿De cuántas formas se pueden elegir 2
botellas? Y ¿cuáles son esas combinaciones?
4∗3
𝐶23+2−1 = =6
1∗2
AB AC BC
AA BB CC
E2.
¿De cuántas formas se pueden sentar 3 parejas de casados alrededor de una mesa circular,
si no debe haber 2 mujeres juntas, ni 2 hombres juntos?
𝑛(𝑚𝑎𝑛𝑒𝑟𝑎𝑠) = 𝑃𝑐(4) ∗ 2! = (4 − 1)! ∗ 2! = 3! ∗ 2! = 12

E3.
¿Cuántos anagramas (ordenamientos) se pueden hacer con las de la palabra “enseñanza”,

si las letras E, S, E deben ir juntas en cualquier orden?
ESENÑANZA
7! 3!
𝑉= ∗
2! ∗ 2! 2!
E4.
¿Cuántos números de 5 cifras se pueden escribir con cuatro 2 y cuatro 5?
22225 22255 55522 55552
5! 5! 5! 5!
=5 = 10 = 10 =5
4! 3! 2! 3! 2! 4!
5 + 10 + 10 + 5 = 30 𝑛ú𝑚𝑒𝑟𝑜𝑠.
E5.
¿Cuántos ordenamientos existen de la palabra “MATEMATICO” en los cuales las dos “A” no
están juntos, ni las dos “M”, ni las dos “T”?
MATEMATICO
10! 9! 9! 9!
− − −
2! 2! 2! 2! 2! 2! 2! 2! 2!
A= {x/x es un ordenamiento con “a” juntas}
B= {x/x es un ordenamiento con “b” juntas}
C= {x/x es un ordenamiento con “c” juntas}
Entonces:
|𝐴 ∪ 𝐵 ∪ 𝐶| = |𝐴| + |𝐵| + |𝐶| − |𝐴𝐵| − |𝐵𝐶| − |𝐴𝐶| + |𝐴𝐵𝐶|
9! 9! 9! 8! 8! 8! 7!
= + + − − − +
2! 2! 2! 2! 2! 2! 2! 2! 2! 1
3 ∗ 9! 3 ∗ 8!
= − + 7!
2! 2! 2!
10! 3 ∗ 9! 3 ∗ 8!
|𝐴̅ ∩ 𝐵̅ ∩ 𝐶̅ | = 𝑈 − |𝐴 ∪ 𝐵 ∪ 𝐶| = − + − 7!
2! 2! 2! 2! 2! 2!
E6.
¿Cuántas permutaciones se pueden formar con los números 0, 1, 3, 5, 6,9 si el número 3

esta después de la segunda posición y el numero 6 debe ir en cualquier lugar que este
posterior al lugar del número 3?
1° _ _ 3 _ _ _ = 4*3*3*2=72
2° _ _ _ 3 _ _ =4*3*2*2=48
3° _ _ _ _ 3 6 =4*3*2*=24
72 + 48 + 24 = 144 𝑝𝑒𝑟𝑚𝑢𝑡𝑎𝑐𝑖𝑜𝑛𝑒𝑠.
Caso I: Permutaciones en las cuales el 3 está en la tercer posición _,_,3,_,_,_

Etapa I. Colocar el 3: hay una manera.
Etapa II. Colocar el 6: hay 3 maneras. (puede ir en 4°,5° o 6° posición)
Etapa III. Colocar el resto : hay 4! maneras. (quedan 4 lugares y 4 números)
Total: 1*3*4!=72
Caso II: Permutaciones en las cuales el 3 está en la cuarta posición: _,_,_,3,_,_
Etapa I. Colocar el 3: hay 1 manera.
Etapa II. Colocar el 6: hay 2 maneras.
Etapa III. Colocar el resto : 4! maneras.
Total: 1*2*4!=48
Caso III. Permutaciones en las que el 3 está en la quinta posición: _,_,_,_,3,_
Etapa I. Colocar el 3: hay 1 manera.
Etapa II. Colocar el 6: hay 1 manera.
Etapa III. Colocar el resto : 4! maneras.
Total: 1*1*4!=24
Respuesta: 72+48+24=144.
E7.
El programa tv Ganadores El Día Domingo eligió a 15 finalistas (7 son del área metropolitana)
de estos 5 serían los ganadores de un viaje a Cancún ¿De cuántas maneras se pueden
elegir los ganadores de manera que se seleccione al menos un finalista que no sea del área
metropolitana?
C(8,1)*C(7,4)+C(8,2)*C(7,3)+C(8,3)*C(7,2)+C(8,4)*C(7,1)+C(8,5)=2982
E8.
Tres atletas toman parte de una competencia ¿De qué maneras pueden llegar a la meta?
i) Si llegan juntos
ii) Si llegan 2 juntos
iii) Si llegan 3 juntos
𝐶33 + 𝐶23 + 𝐶13 = 10

E9.
Se traen 5 objetos de diferente color y se desea poner en 3 repositorios iguales. ¿Cuántas

posibilidades hay de asignar objetos a los repositorios si ninguna puede estar vacía? Y todos
los objetos son asignados.
𝑆(𝑛,𝑘) = 𝑆(𝑛−1,𝑘−1) + 𝑘 ∗ 𝑆(𝑛−1,𝑘)
Se satisface que 𝑆(𝑛,1) = 1 y 𝑆(𝑛,𝑛) = 1 para cajas iguales.
𝑆(5,3) = 𝑆(4,2) + 3 ∗ 𝑆(4,3)
𝑆(5,3) = 𝑆(3,1) + 2 ∗ 𝑆(3,2) + 3(𝑆(3,2) + 3 ∗ 𝑆(3,3) )
𝑆(5,3) = (1 + 2(𝑆(2,1) + 2 ∗ 𝑆(2,2) )) + 3(𝑆(2,1) + 2 ∗ 𝑆(2,2) + 3(1))
𝑆(5,3) = (1 + 2(1 + 2(1))) + 3(1 + 2(1) + 3)
𝑆(5,3) = 7 + 3(6) = 25
𝑆(𝑛,𝑘) = 𝑆(𝑛−1,𝑘−1) + 𝑘 ∗ 𝑆(𝑛−1,𝑘)
Se satisface que 𝑆(𝑛,1) = 1 y 𝑆(𝑛,𝑛) = 1 para cajas diferentes
Se multiplica el resultado por K!
Osea k!*S(n,k).
Problema: ¿De cuántas maneras se pueden distribuir 5 libros distintos de Matemática

Discreta entre Jorge , Karla y Anthony si cada uno le corresponde al menos un Libro?
CASO 1. A Jorge le corresponden 3 libros
Sub caso 1: Se selecciona 3 libros para Jorge :hay C(5,3)
Sub caso 2: Se selecciona 1 libros para Karla: C(2,1)
Sub caso 3. Se selecciona 1 libro para Anthony(hay una manera)
C(5,3)*C(2,1)*1
CASO 2:
A Jorge le corresponde 2 libros
Sub caso 1. Se selecciona 2 libros para Jorge : C(5,2)
Sub caso 2. Se distribuyen los 3 libros restantes entre Karla y Anthony
Variante 1: A Karla le corresponde 2 libros :C(3,2)
Variante 2: A Karla le corresponde 1 libro: C(3,1)
C(5,2)*(C(3,2)+C(3,1))
CASO 3:
A Jorge le corresponde 1 libro
Subcaso 1. Se selecciona 1 libro para Jorge : C(5,1)
Subcaso 2: Se distribuyen los 4 libros restantes entre Karla y Anthony
Variante 1. A Karla le corresponden 3 Libros:C(4,3)
Variante 2. A Karla le corresponden 2 libros: Hay C(4,2)
Variante 3: A Karla le corresponden 1 Libros: Hay C(4,1)
C(5,1)(C(4,3)+C(4,2)+C(4,1)
C(5,3)*C(2,1)+ C(5,2)*(C(3,2)+C(3,1))+ C(5,1)(C(4,3)+C(4,2)+C(4,1)

=150
X1+X2+X3+X4=16 , CUANTAS SOLUCIONES TIENE LA ECUACION SI Xi>=0
GRAFOS
Un grafo está compuesto de vértices y aristas. Simbológicamente se representa como:
G (V, E)
Donde:
E = Edges (Aristas)
V= Vértices
GRAFO SIMPLE NO DIRIGIDO
El que no está compuesto con lazos o aristas paralelos.
V1 V2 V3
*Es dirigido cuando tiene la orientación (flechita)
Grafo con aristas paralelas dirigido y lazos son de la forma
V1 V2 V3
lazo o bucle
El grado de un vértice en una gráfica no dirigida viene a ser las aristas incidentes en un
vértice determinado.
δ (V1) = 2
V
2
δ (V2) = 1
V
1 δ (V3) = 1
V
3
GRAFO DE SIMILITUD
Viene a ser un subconjunto de una gráfica que lo contiene
A D
B E
De la gráfica se puede extraer:
En una gráfica no dirigida cumple:
La sumatoria de todos los grafos de los vértices de una gráfica es igual al doble de la cantidad
de aristas que posee la gráfica (no debe haber puntos o vértices disco nexos de la gráfica)
Demostración:
Por inducción:
V1---V2
Se observa Sumando
δ (v1)=1 2 = 2x (1)
δ (v2)=1
Se cumple!
HIPÓTESIS INDUCTIVA:
Para n=k nodos
V1---V2------------------------------Vk-1---Vk
𝑘
∑ δ(Vi) = 2𝑒𝑟
𝑖=1
Para n=k+1 nodos
V1---V2------------------------------Vk-1---Vk---Vk+1
𝑘+1 𝑘
∑ δ(Vi) = ∑ δ(Vi) + δ(𝑉𝑘+1 ) = 2𝑒𝑟 + 2 = 2(𝑒𝑟 + 1) = 2𝑒𝑟+1

𝑖=1 𝑖=1
H.I
Por lo tanto:
𝑘
∑ δ(Vi) = 2𝑒𝑟
𝑖=1
Circuito y trayectoria de Euler (Grafica no dirigida)
Toda grafica cuyos vértices son de grado par posee circuitos de Euler.
V1
V2 V4
V3
Todos son de grado par | Hay circuito de Euler y trayectoria de Euler
δ(V1)=2 | M1: V1-V2-V3-V4-V1
δ(V2)=2 | M2: V1-V4-V3-V2-V1
δ(V3)=2
δ(V4)=2
C E
M1: A-B-C-D-E-B |
Es una trayectoria de Euler | No hay circuito de Euler
M2: A-B-E-D-C-B |
Es otra trayectoria de Euler |
La trayectoria de Euler consiste en barrer todas las aristas una sola vez, ahora cuando
partiendo del inicio barre todas las aristas llegando al inicio o punto de partida se dice que
hay circuito de Euler (no hay que pasar 2 veces por la misma arista).
La demostración de que todos los vértices de grado par hacen que la gráfica tenga circuito
de Euler, se demuestra por inducción.
Para 2 nodos:
V1 V2 δ(V1)=2
δ(V2)=2
Hay C.E
HIPÓTESIS INDUCTIVA
n=k nodos
V1---V2----------------Vk-1---Vk
Para n=k nodos; esto es agregamos un nodo de grado par a discreción conexo a la
gráfica.
V1---V2----------------Vk-1---Vk---Vk+1
H.I. hay C.E.
Sigue habiendo C.E.
Por lo tanto:
Si todos los vértices son de grado par entonces existe circuito de Euler.
Teorema:
En una gráfica la cantidad de nodos de grado impar es par.
δ(V2)=3 V
δ(V4)=3 1
V V
2 3
V V
5 4
δ(V1)=3 V V
δ(V2)=3 1 6
δ(V2)=3 V V
2 5
δ(V5)=3
V V
3 4
Demostración:
Dada la gráfica compuesta de n nodos se hace una partición con dos grafos de similitud, la
primera tendrá nodos de grado par y la segunda nodos de grado impar.
--------------------------------------------------G----------------------------------------------------
V
V V
V V 3
3 3
3 3
V
3
V
V V 3 V V
3 3 V
3 3
V V 3
3 3
V
3 V V
V 3 3
3
V
3
G1 (Grafos Par) G2 (Grafos Impar)
Partición:
G1 ∩ G2 = ∅
G1 ∪ G2 = G
Ahora por el teorema del “apretón de manos” o Handshaking.la sumatoria de todos los nodos
es 2 veces la cantidad de aristas
𝑛
∑ δ(Vi) = 2𝑒
𝑖=1
n r s
∑ δ(Vi) = ∑ δ𝑝 (V1) + ∑ δ𝐼 (Vi) =2𝑒

i=1 i=1 i=1
2𝑒𝑝 + ∑ δ𝐼 (Vi) =2𝑒

i=1
∑ δ𝐼 (Vi) =2𝑒 − 2𝑒𝑝 = 2(𝑒 − 𝑒𝑝 )

i=1
La cantidad de nodos es par.
Traza:
V2
V1 V3
Matriz de Incidencia:
a
e1 e2 e3 e4 e5
𝑒1 a 1 1 1 0 0
b 1 0 0 1 0
b 𝑒2 𝑒3 c 0 1 1 1 1
𝑒4
𝑒5
a b c d
Grados de
aristas 2 3 1 1 7
que entran
Grados de
aristas 1 1 3 2 7
que salen
B
A
C D
X
2
X ∑ δ(Vi) = 14 = 2(7)
1
X x1 x2 x3 x4
4 Int 2 3 1 3
Ext 3 3 2 1
X
∑ ρ(Vi) = 18 = 2(9)
3
RECORRIDOS
En una gráfica Si A es la matriz de adyacencia (con aristas múltiples y lazos permitidos)

entonces el número de trayectorias diferentes de longitud r de Vi a Vj es igual a la entrada i
– j ésima de la matriz exponencial Ar.
Su Matriz de adyacencia (vecino) consiste en poner 1 si el nodo es vecino con otro.
A B
D C
A B CD
MA = A 0111
B 1000
C 1001
D 1010
Longitud se refiere a la cantidad de veces que es recorrida la arista.

E1.
Hallar el número de trayectorias de longitud 4 entre los nodos B y D
0 1 1 1
𝑀𝐴 = [1 0 0 0] → 𝑀4 = 𝑀2 ∗ 𝑀2 =
𝐴 𝐴 𝐴
1 0 0 1
1 0 1 0
Trayectorias:
B-A-B-A-D
B-A-C-A-D
B-A-D-A-D
B-A-D-C-D
Con una gráfica dirigida
A B ¿Cuántas trayectorias de B a D hay de longitud 4?
C D
B-C-A-B-D
B-D-A-B-D
A B CD
A 0111 0111 1211

B 1000 MA * MA 2110 MA 2 * MA2 2232
C 1001 0100 2110
D 1010 1111 3332
B→D =2
Un grafo está compuesto de vértices y aristas, simbólicamente se representa como: G(V , E)

.
V :Vertices
E : Aristas
• Grafo simple no dirigido: No está compuesto con lazos ni con aristas paralelas.
*Es dirigido cuando tiene orientación (flechas).
• Grafos con aristas paralelas, dirigidas y con lazos son de la forma:
*El grado de un vértice vienen a ser las aristas incidentes en un vértice determinado.
• Grafo de similitud: Viene a ser un subconjunto de un grafica que lo contiene.
De la gráfica se puede extraer, una subgrafica seria:

En una gráfica no dirigida se cumple:
La sumatoria de grados de los n vértices es igual a dos veces la cantidad de aristas que
posee la gráfica (Teorema HANDSHAKING).
  (V ) = 2e
i =1
i
Demostración por inducción:
Se observa:
 (V1 ) = 1 
 2 = 2(1)
 (V2 ) = 1
Hipótesis inductiva: Para n=k
  (V ) = 2e
i =1
i k
Para n=k+1
k +1 k
  (V ) =   (V ) +  (V
i =1
i
i =1
i k +1 ) = 2ek + 2 = 2(ek + 1) = 2en +1
H .I .
n
   (Vi ) = 2e
i =1
CIRCUITO Y TRAYECTORIA DE EULER

Todo grafica cuyos vértices son de grado par posee circuito de Euler.
 (V1 ) = 2
 (V2 ) = 2
 (V3 ) = 2
 (V4 ) = 2
No hay circuito de Euler.
1 : A − B − C − D − E − B
2 : A − B − E − D − C − B
La trayectoria de Euler consiste en barrer todas las aristas una sola vez; ahora cuando
partiendo del inicio barro todas las aristas llegando al inicio o punto de partida se dice que
hay circuito de Euler (NO HAY QUE PASAR DOS VECES POR LA MISMA ARISTA).
• La demostración de que todos los vértices de grado par hacen que la gráfica tenga
circuito de Euler se realiza por inducción:
 (V1 ) = 2
 (V2 ) = 2 Hay C.E.
Hipótesis inductiva: n=k
Para n=k+1 nodos, agregamos un nodo de grado par a discreción conexo a la gráfica.
Sigue habiendo C.E.
 Si todos los vértices son de grado par entonces existe C.E.
Matriz de incidencia
a
e1
b e2
e3
e4
e5
E1 E2 E3 E4 E5
A 1 1 1 0 0
B 1 0 0 1 0
C 0 1 1 1 1
a b
c d
a b c d
Grados 2 3 1 1 7
internos
(aristas
que
entran)
Grados 1 1 3 2 7
externos
(aristas
que salen)
X1 X2
11
X3 X4
¿A cuántos grados equivale a la gráfica?
X1 X2 X3 X4
Int 2 3 1 3 =9
ext 3 3 2 1 =9
Recorridos
En una gráfica si A es la matriz de adyacencia con ( aristas múltiples y lazos permitidos)

entonces el número de trayectoria diferentes de longitud r de 𝑉𝑖 a 𝑉𝑗 es igual a la entrada i-
jésima de la matriz exponencial 𝐴𝑟
A B
D C
Su matriz de adyacencia consiste en poner si el nodo es vecino con otro
0 1 1 1
𝑀𝐴 = [1 0 0 0]
1 0 0 1
1 0 1 0
Longitud se refiere a la cantidad de veces que es recorrida una arista. Encontrar el número
de trayectorias de longitud 4 entre los nodos B y D
0 1 1 1 4
𝑀𝐴 = [1 0 0 0] = 𝑀 2 ∗ 𝑀 2
𝐴 𝐴
1 0 0 1
1 0 1 0
Algoritmo de Floy Warshall
Sirve para hallar el camino minimo entre los nodos de un grafo
for( k=1 to n)
for( i=1 to n)
for( j=1 to n)
if M[i][j]> M[i][k]+M[k][j]
M[i][j]= M[i][k]+M[k][j]
end if
fin for
fin for
// n es el número de nodos
M[i][j] es la matriz de distancias de i a j
2
5 7
1 3
15
Inicialmente la matriz es:
0 5 15
𝑀=[5 0 7]
15 7 0
Veamos al pasar por el algoritmo de Floy Warshall en qué iteración cambia, haciéndose de
1 a 3, 12 en lugar de 15
k=2, i=1, j=3
si(M[1][3]>M[1][2]+M[2][3])
(15>5+7)
M[1][3]=M[1][2]+M[2][3]
Fin si
Algoritmo de Warshall o cerradura transitiva para saber si existe camino entre un nodo y
otro en gràficas dirigidas
ALGORITMO DE CERRADURA O WARSHALL
Para ver si existe camino entre los nodos.
// n son los nodos
for k=1 to n
for i=1 to n
for j=1 to n
M[i][j]=M[i][j]||M[i][k]&&M[k][j]
Fin for
Fin for
Fin for
1 3
Inicialmente la matriz booleana (015 𝑦 115 )
0 1 0
𝑀 = [0 0 1]
1 0 0
Quiere decir que inicialmente se pone por ejemplo que no hay camino entre el nodo 1 y3,
pero luego de pasar por Warshall, la matriz resultante saldrá
1 1 1
𝑀 = [1 1 1]
1 1 1
Es decir, hay camino entre todos los nodos incluido consigo mismo
k=2, i=1, j=3
M[1][3]=M[1][3]||M[1][2]&&M[2][3]
0||1&&1
0||1
M[1][3]=1
1
3
6
4
If M[i][j]>M[i][k]+M[k][j]
M[i][j]=M[i][k]+M[k][j]
COLOREADO DE GRAFOS
Es una técnica para utilizar la cantidad mínima de “colores” para un problema de intercalar
ya sea en transporte o propiamente coloreado.
¿Cuántos colores como mínimo se requiere para distinguir el mapa?
RB
RP
RA RF
RC RE
E2.Siete especies de peces venenosos. Se quiere transportar si el pez i no puede estar

con i+1 e i+2. ¿Cuántos contenedores se necesitan? Hacer el grafo antes.
1 ≤i ≤5
B 2 A C
4 6
1 3 5 7 A
A B
C
3 contenedores
C
B A
A 1 3 5 7
2 4 6
C A B
3 contenedores
ALGORITMO DE DIJKSTRA
Funcionalidad:
1. Leer la matriz de distancias entre todos los nodos

2. Elegir un nodo y dicho nodo etiquetarlo e ingresarlo a un arreglo E={V1 … }
3. Calcular la distancia de dicho nodo a sus nodos adyacentes (para ello chequear la
matriz de adyacencia)
4. Elegir el nodo cuya distancia del nodo V1 elegido anteriormente es menor e ingresarlo
al Arreglo E= {V1 , V2 …}
5. Con dicho nodo V2 Calcular la distancia sus nodos adyacentes, luego elegir el nodo
que corresponde (distancia menor) incluyendo las distancias de a los nodos
anteriormente calculadas y que no fueron ingresadas al nodo E a esto se le llama
recálculo.
6. Repetir el paso 5 (for) hasta que E= { V 1 , V2 , … , Vn }
Es decir todos los nodos hallan sido calculados al final se tiene las distancias mínimas
entre todos los nodos.
Ejemplo:
9
6 5
14 6
2
1 6
3 4
9 11
10
7 15
Hallar la distancia mínima entre todos los nodos, elija el nodo 1 como nodo inicial y arme el
conjunto E
12 2
14 5
7 4
2 3 4
4
5 1
5
4 6 1 3 8
2
1 7 2 1
5 5 9
2
4 2 13 5
11 8
4 4
6 8
8 7 7
4 1
E = {1, 7, 6, 2, 8, 5, 3, 9, 4}
Hallar la distancia mínima entre todos los nodos, elija el nodo 2 como nodo inicial y arme el
conjunto E
5 2
2 5 7
2 7 5
3
2 5 2
4
5 7
1 3 4
1
4 4
3 2 2 2
2
2
2
2
4 6 8
8 6
6 4
4 3
E = {2, 3, 1, 4, 5, 6, 7, 8}
Definición de Árbol
Sea G= (V,E) un grafo (no dígrafo) o multígrafo G es un árbol si es conexo y no contiene

ciclos.
Teorema 1
Si a y b son 2 vértices distintos de un árbol T=(V,E) entonces existe un camino único que
conecta dichos vértices.
Demostración:
Por la definición de árbol no puede tener aristas paralelas y tampoco tiene bucles.
Por el absurdo si existe otro camino entre a y b entonces entraría en conflicto con la definición
porque sería o tendría arista paralela por ende solo hay un camino único entre a y b.
Teorema 2
Dado un árbol cualquiera T= (V,E) se verifica que:
|𝑉| = |𝐸| + 1
Demostración:
B 1
2
2=1+1
3=2+1 Cumple
A 2 3
2 V1 Cumple 2
V2
A B
|𝑉| = |𝑉1 | + |𝑉2 |

|𝑉| = 𝐸1 + 1 + 𝐸2 + 1 𝐸 = 𝐸1 + 𝐸2 + 1
|𝑉| = |𝐸| + 1
Definición:
Un árbol con raíz se dice que es un árbol m-ario, m>= o un m-árbol cuando todo vértice
interno tiene como máximo m hijos.
Un árbol con raíz se dice que es un árbol m-ario completo si todo vértice interno tiene
exactamente m hijos.
Definición:
Un m-árbol con raíz y de altura h se dice que está equilibrado cuando todas sus hijas están
situadas en el nivel h o en el h-1
Teorema 3
Un m-árbol completo con i vértices internos tiene en total
|𝑉| = 𝑚𝑖 + 1 Vértices
Cada vértice tiene m hijos
𝑖 Vértices → 𝑚𝑖 hijos
|𝑉| = 𝑚𝑖 + 1 ←Raíz
|𝑉| = |𝐸| + 1
Nivel 0
Nivel 1
Nivel 2
𝐸 = 𝐸1 + 𝐸2 + 1
También |𝑉| = |𝑖| + 𝑙 en general
Cantidad de vértices es igual a cantidad de nodos internos más cantidad de hojas

4=2+2
4 = Hijos + Hojas
Teorema 4
Dado una m-arbol completo si tiene:

𝑛(𝑚−1)+1
A) n vértices, entonces tendrá 𝒊 = (𝒏 − 𝟏)/𝒎 vértices internos y 𝑙 = hojas.
𝑚
|𝑉| = 𝑚𝑖 + 1 |𝑉| = |𝑖| + 𝑙

𝑛−1
𝑛 = 𝑚𝑖 + 1 𝑛= +𝑙
𝑚
𝑛−1 𝑛𝑚 − (𝑛 − 1)
=𝑖 =𝑙
𝑚 𝑚
𝑛𝑚 − 𝑛 + 1
=𝑙
𝑚
𝑛(𝑚 − 1) + 1
=𝑙
𝑚
B) i vértices internos tendrá 𝒏 = 𝒎𝒊 + 𝟏 vértices en total y 𝒍 = (𝒎 − 𝟏)𝒊 + 𝟏 hojas.

𝒍−𝟏
C) l hojas, entonces tendrá 𝒏 = (𝒎𝒍 − 𝟏)/(𝒎 − 𝟏) vértices en total e 𝒊 = 𝒎−𝟏 vértices
internos.
𝑛 = 𝑚𝑖 + 1
𝑛 =𝑙+𝑖
𝑙 = 𝑛 − 𝑖 = 𝑚𝑖 + 1 − 𝑖
𝑙 = (𝑚 − 1)𝑖 + 1
Teorema
En un árbol binario completo se cumple que:
|𝑉| = 2𝑛+1 − 1
Demostración:
Para h=0
𝑇(0) = 20+1 − 1 = 1
Para h=k
𝑇(𝑘) = 2𝑘+1 − 1 (H.I.)
Para h=k+1
𝑇(𝑘) = 2𝑘+2 − 1
𝑇(0) = 1
𝑇(1) = 3
𝑇(2) = 7
En el nivel siguiente aumenta en razón al nivel anterior por ende en el nivel k+1 aumentan
2 k+1
2𝑘+1 − 1 + 2𝑘+1 entonces se cumple

𝑇(𝑘 + 1) = 2𝑘+2 − 1 =2 k+1+1 -1 para el nivel k+1.
a)
𝑆𝑖 \ a b
𝑆0 𝑆1 , 𝑆3 𝑆2
𝑆1 𝑆1 , 𝑆2 𝑆3
𝑆2 𝑆2 𝑆3
𝑆3 ∅ ∅
𝑆𝑖 \ a b
{𝑆0 } {𝑆1 , 𝑆3 } {𝑆2 }

{𝑆1 } {𝑆1 , 𝑆2 } {𝑆3 }
{𝑆2 } {𝑆2 } {𝑆3 }
{𝑆3 } ∅ ∅
{𝑆1 , 𝑆3 } {𝑆1 , 𝑆2 } {𝑆3 }
{𝑆1 , 𝑆2 } {𝑆1 , 𝑆3 } {𝑆3 }
a
b
𝑆1
𝑆0 a
b
a
a
𝑆2
𝑆3
a
b
a
𝑆1 , 𝑆3 a
𝑆3
𝑆1 , 𝑆2 a
a
a
𝑆3 𝑆3 a
a
a
E2.Generar la gramática que reconozca un número complejo
𝐺 = (𝑆𝑇, 𝑆𝑁, 𝑛0 , 𝑅)
𝑆𝑇 = {0,1,2,3,4,5,6,7,8,9, . , −, +, 𝑖}
𝑛0 = 𝑖𝑚𝑎𝑔𝑖𝑛𝑎𝑟𝑖𝑜
𝑟1 : < 𝑖𝑚𝑎𝑔𝑖𝑛𝑎𝑟𝑖𝑜 >∷=< 𝑟𝑒𝑎𝑙 >< 𝑠𝑖𝑚𝑏𝑜𝑙𝑜 > | < 𝑒𝑛𝑡 >< 𝑠𝑖𝑚𝑏𝑜𝑙𝑜 > | < 𝑓𝑟𝑎𝑐 >< 𝑠𝑖𝑚𝑏𝑜𝑙𝑜 > |
< 𝑑𝑖𝑔 >< 𝑠𝑖𝑚𝑏𝑜𝑙𝑜 > | < 𝑟𝑒𝑎𝑙 >< 𝑠𝑖𝑚𝑏𝑜𝑙𝑜 >< 𝑠𝑖𝑔𝑛𝑜 >< 𝑟𝑒𝑎𝑙 > | < 𝑟𝑒𝑎𝑙 >
< 𝑠𝑖𝑔𝑛 >< 𝑟𝑒𝑎𝑙 >< 𝑠𝑖𝑚𝑏𝑜𝑙𝑜 >
𝑟2 : < 𝑓𝑟𝑎𝑐 >∷=< 𝑒𝑛𝑡 >
𝑟3 : < 𝑒𝑛𝑡 >∷=< 𝑑𝑖𝑔 > | < 𝑑𝑖𝑔 >< 𝑒𝑛𝑡 >
𝑟4 : < 𝑑𝑖𝑔 >∷= 0|1|2|3|4|5|6|7|8|9
𝑟5 : < 𝑠𝑖𝑔𝑛 >∷= +| −
𝑟6 : < 𝑠𝑖𝑚𝑏𝑜𝑙𝑜 >∷= 𝑖
E3.Realizar una máquina de Turing que reconozco la secuencia: //comentario en java
Solución:
< 𝑎0 , 𝐵 >→< 𝑎1 , 𝐵, 𝐷 >
< 𝑎1 ,/>→< 𝑎2 ,/, 𝐷 >

< 𝑎2 ,/>→< 𝑎3 ,/, 𝐷 >
< 𝑎3 , 𝑙 >→< 𝑎3 , 𝑙, 𝐷 >
< 𝑎3 , "\n" >→< 𝑎4 , "\𝑛", 𝐷 >
< 𝑎4 , 𝐵 >→< 𝑎4 , 𝐵, 𝐼 >
E4. Realizar un árbol gramatical que reconozca: int A[ ][ ]
𝑅1 : < 𝑣𝑎𝑟 >→< 𝑡𝑖𝑝𝑜 >< 𝑣𝑎𝑟𝑠 >< 𝑐𝑜𝑟𝑐ℎ𝑒𝑡𝑒 >
𝑅2 : < 𝑣𝑎𝑟𝑠 >→< 𝑢𝑛𝑎𝑉 >
𝑅3 : < 𝑢𝑛𝑎𝑣 >→ 𝐴
𝑅4 : < 𝑡𝑖𝑝𝑜 >→ 𝑖𝑛𝑡
𝑅5 : < 𝑐𝑜𝑟𝑐ℎ𝑒𝑡𝑒 >→< 𝑢𝑛 𝑐𝑜𝑟𝑐ℎ𝑒𝑡𝑒 >
𝑅6 : < 𝑐𝑜𝑟𝑐ℎ𝑒𝑡𝑒 >→< 𝑢𝑛 𝑐𝑜𝑟𝑐ℎ𝑒𝑡𝑒 >< 𝑐𝑜𝑟𝑐ℎ𝑒𝑡𝑒 >
𝑅7 : < 𝑢𝑛 𝑐𝑜𝑟𝑐ℎ𝑒𝑡𝑒 >→< 𝑐𝑜𝑟𝑐ℎ𝑒𝑡𝑒 𝑑 >
𝑅8 : < 𝑢𝑛 𝑐𝑜𝑟𝑐ℎ𝑒𝑡𝑒 >→< 𝑐𝑜𝑟𝑐ℎ𝑒𝑡𝑒 𝑖 >
𝑅9 : < 𝑐𝑜𝑟𝑐ℎ𝑒𝑡𝑒 𝑑 >→]
𝑅10 : < 𝑐𝑜𝑟𝑐ℎ𝑒𝑡𝑒 𝑖 >→ [
<var>
<tipo> <vars> <corchete> ;
int <unaV> <un corchete> <corchete>

corchetecorch
A <corchete i> <un corchete>

corchetecorch
[ <un corchete>
]
a) 𝐺 = {(𝑆, 𝐴, 𝐵, 𝐶), (𝑎, 𝑏, 𝑐), (𝑆), (𝑆 → 𝑎𝐴}), (𝐴 → (𝑎𝐴, 𝑎𝐵), 𝐵 → (𝑏𝐵, 𝑐𝐵, 𝐶), 𝐶 →
(𝑐𝐶, 𝑐)}
𝐿{𝑎𝑟 𝑏𝑚 𝑐 𝑛 ; 𝑚, 𝑛, 𝑟 ≥ 1}
𝑆 → 𝑎𝐴, 𝐵 → 𝑏𝐵, 𝑐 → 𝑐𝐶, 𝐶 → 𝑐
𝐴 → 𝑎𝐴, 𝐴 → 𝑏𝐵, 𝐵 → 𝑐𝐶, 𝐵 → 𝐶

b)
b c d
A B C
𝑛
𝑏 𝑚 𝑐 𝑟(𝑏𝑐) 𝑑
;𝑛 ≥ 1
𝐺 = {(𝑆, 𝐴, 𝐵, 𝐶), (𝑎, 𝑏, 𝑐), 𝑆, 𝑆 → 𝑎𝐴}
𝑆 → 𝑏𝐵, 𝐴 → 𝑎𝐴, 𝐴 → 𝑏𝐵, 𝐵 → 𝑏𝐵
𝐵 → 𝑐𝐶, 𝐵 → 𝐶, 𝐶 → 𝑐𝐶, 𝐶 → 𝑐
a b c
a b c c
S A B C Z
b b
CONVERSIONES POLACAS:
Tanembau , cairo, cormen
Entrefijos postfijo
A+B AB+
A+B-C AB+C-
(A+B)*(C-D) AB+CD-*
((A+B)*C-(D-E))$(F+G) AB+C*DE- -FG+$
A-B/(C*D)$E ABCDE$*/-
A$B*C-D+E/f/(G+H) AB$C*D-EF/GH+/+
Entrefijo Prefijo
A+B +AB
A+B-C -+ABC
(A+B)*(C-D) =+AB * -CD *+AB-CD
A$B*C-D+E/F/(G+H) +-*$ABCD//EF+GH
((A+B)+C-(D+E))$(F+G) $-*+ABC-DE+FG
A-B/(C*D)$E -A/B*C$DE
Entrefijo Postfijo
A+(B*C) ABC*+
(A+B)*C AB+C*
Algoritmo utilizando pilas
Supongamos se quiere llevar a postfijo A+B*C.
Se considera las columnas de símbolos, donde se almacena carácter a carácter la cadena

de entrada, la hilera de postfijo array, donde se arma la cadena de postfijo y OPSTK que es
la hilera o array que almacena los operadores.
A+B*C =A+(BC*)=ABC*+
Signo hilera posfijo OPSTK
1 A A
2 + A +
3 B AB +
4 * AB +*
5 C ABC +*
6 ABC* +
7 ABC*+
Ejercicios
Postfijo
(AB$)*C+D/(EH+)
(AB$C*)+(DEH+/)
AB$C*DEH+/+
PREFIJO
($AB)*C+D/(+EH)
(*$ABC)+(/D+EH)
+*ABC/D+E
¿Cuánto sale el valor si se lee la cadena posfija?
623*-382/+*2$3+?
2*3-6*3+8/2+23=12
((A+B)*(C-D))*E=AB+CD-*E*
Symb hilera de posfijo Opstk

1 ( (
2 ( ((
3 A A ((
4 + A ((+
5 B AB ((+
6 ) AB+ (
7 * AB+ (*
8 ( AB+ (*(
9 C AB+C (*(
10 - AB+C (*(-
11 D AB+CD (*(-
12 ) AB+CD- (*
13 ) AB+CD-*
14 * AB+CD-* *
15 E AB+CD-*E *
16 AB+CD-*E*
AB+CD-*E*
Pasar a posfijo (((A*B)*(C/D))/E)
SIMBOLO OPER CADENA
1 ( (
2 ( ((
3 ( (((
4 A ((( A
5 * (((* A
6 B (((* AB
7 ) (( AB*
8 * ((* AB*
9 ( ((*( AB*
10 C ((*( AB*C
11 / ((*(/ AB*C
12 D ((*(/ AB*CD
13 ) ((* AB*CD/
14 ) ( AB*CD/*
15 / (/ AB*CD/*
16 E (/ AB+CD/*E
17 ) AB+CD/*E/
Máquina de Mealy:
Es un detector construido en base a grafos.
Ejemplo:
Detectar la secuencia de 3 bits 101
X=1/s=0
X=1/s=0 X=0/s=0
X=0/s=0 X=0/s=0
I0 I1 I2
X=1/s=1
Rossen chequear ejemplos de máquina de Mealy

Separata Matemática Discreta

Cargado por

Copyright:

Formatos disponibles

Separata Matemática Discreta

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Separata Matemática Discreta

Cargado por

Copyright:

Formatos disponibles

matriz

Las premisas siempre son verdaderas.

E1. Demuestre que t ^ s se puede deducir de las premisas p → q, q→~t, p ν (t ^ s), r

▪ P2: q→~r (premisa)

▪ P3: p→~r (P1, P2, SH)

▪ P5: ~p (P3, P4, M. Tollens)

▪ P7: ~p ^ (p ν (t ^ s)) (P5, P6, combinación)

▪ P8: (t ^ s) (P7, Silogismo disyuntivo)

E2: Dadas las premisas

p ^ q, p→(r ^ q), r→(s ν t), ~s

Deducir t usando el cálculo proposicional

▪ P2: p→(r ^ q) (premisa)

▪ P3: ~p ν (r ^ q) (P2, condicional)

▪ P4: p ( P1, simplificación)

▪ P5: r ^ q (P3, P4, Silogismo Disyuntivo)

▪ P6: r (P5, simplificación)

▪ P8: s ν t (P6, P7, MP)

▪ P10: t (P8, P9, Silogismo Disyuntivo)

▪ ~q)→(r ^ s), r → t, ~t , deducir p

▪ P4: ~r ν ~s (P3, adición)

▪ P5: ~(r ^ s) (P4, Morgan)

▪ P6: (~p ν ~q) →(r ^ s) (premisa)

▪ P7: ~(~p ν ~q) (P5, P6, Modus Tollens)

▪ P8: p ^ q (P7, Morgan, doble negación)

▪ P9: p (P8, simplificación)

❖ Cuantificador existencial: (GE)

❖ Regla de especificación universal: (EU)

❖ Regla de especificación existencial: (EE)

❖ Regla de generalización universal (GU):

❖ Regla de generalización existencial (GE):

REGLAS DE INTERCAMBIO DE CUANTIFICADORES

▪ E1: ∃x(C(x)^B(x)), ∀x(B(x)→A(x)) (premisa) POR TANTO SE CUMPLE:

▪ P1: ∀x[ W(x)→C(x)]

▪ P5: W(r)^L(r)→Q(r) (P2, EU)

▪ P9: W(r) (P3, SC)

▪ P3: stgo(a)^~oceano(a) (P2, EE)

Consiste en reemplazar frases proposicionales por variables proposicionales para

Entonces el argumento (conjunto de proposiciones)

p: la banda pudo tocar

▪ P4: ~r (P2, P3, MT)

P(x): x es alguien del curso

▪ P3: P(a)^Q(a) (P1, EE)

• Si m es impar entonces 𝑚2 es impar.

Sea 𝑚 = 2𝑘 + 1; 𝑘 ∈ 𝑍 + y definición de 𝑚 impar entonces si elevamos 𝑚 al cuadrado

Por ejemplo demostrar

Si 𝑛2 es impar entonces 𝑛 es impar

es más fácil demostrar con la contra positiva es decir:

Si 𝑛 es par entonces 𝑛2 es par

Lo cual es cierto por ser 𝑛 par entonces 𝑛 = 2𝑘, 𝑘 ∈ 𝑍 + elevando al cuadrado 𝑛2 = 4𝑘 ⇒

Por equivalencia quedaría demostrado que si 𝑛2 es impar entonces 𝑛 es impar

• Método por el absurdo

Donde p y q son números primos entre si es decir su divisor común es 1

𝑞 2 = 2𝑘 2 → 𝑞 2 es par y tiene como divisor a 2

PROPIEDAD DEL BUEN ORDEN

Sean los números enteros positivos 1, 2, 3,…,𝑥1 , 𝑥2 ,…, 𝑥𝑛 ; si extraemos un subconjunto

Por lo tanto 𝑥1 es el mínimo de dicho subconjunto.

PRINCIPIO DE INDUCCIÓN MATEMÁTICA EN 𝐙 +

∴ 𝑃(𝑚) 𝑒𝑠 𝑣𝑒𝑟𝑑𝑎𝑑 𝑝𝑎𝑟𝑎 𝑐𝑢𝑎𝑙𝑒𝑠𝑞𝑢𝑖𝑒𝑟𝑎 𝑚, 𝑚 𝑝𝑒𝑟𝑡𝑒𝑛𝑒𝑐𝑒 𝑎 𝑍 +

𝑥1 − 1 ≠ 0 𝑦𝑎 𝑞𝑢𝑒 𝑃(0) Es verdadero, entonces 𝑥1 − 1 > 0