MA265 - ROP - Elementos Extremos - Cotas[Libro]

Matemática Discreta • Inducción matemática • Invariantes Unidad 1: Teoría de Conjuntos, Lógica proposicional y Relaciones Logro de la sesión Al finalizar la sesión, estarás preparado para: Determinar si un ciclo de programación es invariante y demostrar su validez usando el principio de inducción matemática. Bibliografía • Profesores UPC – Libro digital – Inducción Matemática • Profesores UPC – Libro digital – Invariantes • Forero A. (2009). Matemática Estructural . Departamento de Matemáticas Universidad de los Andes Bogotá, D.C-Colombia. Revisar páginas desde 67 hasta 76. • Epp S. (2012). Matemáticas discretas con aplicaciones . México, D.F. Cengage Learning. Revisar páginas desde 244 hasta 268. Bibliografía Multimedia Bibliografía textos de consulta. Supongamos que tuviste una mala experiencia con cuatro carpinteros que contrataste en distintas fechas. ¿Se puede afirmar que “todos los carpinteros son incumplidos”? Razonamiento inductivo Determine el valor de verdad de las siguientes proposiciones: 1. ∀ 𝑛 ∈ ℕ, 𝑛 2 − 3𝑛 − 1 < 0 2. ∀ 𝑛 ∈ ℕ, 𝑛 2 + 𝑛 + 41 es primo Inducción matemática Si, para una afirmación 𝑃(𝑛) podemos demostrar que: 1. La afirmación 𝑃 𝑛 es verdadera para 𝑛 = 𝑛 0 , 2. La afirmación 𝑃 𝑛 es verdadera para 𝑛 = 𝑘 + 1, suponiendo que 𝑃(𝑛) es verdadera para 𝑛 = 𝑘 . Es decir, 𝑃 𝑘 + 1 se cumple a partir de que 𝑃 𝑘 se haya cumplido. Base de la Inducción Paso de Inducción Entonces se tiene que 𝑃(𝑛) es verdadera para todo natural 𝑛 ≥ 𝑛 0 Demuestre que para todo 𝑛 ∈ ℕ , se cumple 𝑃 𝑛 : 1 + 3 + 5 + ⋯ + (2𝑛 − 1) = 𝑛 2 Ejemplo de inducción matemática Solución. ▪ Veamos que 𝑃(1) es verdadero: 𝑃 1 : 2 ∗ 1 − 1 = 1 2 ▪ Asumimos que 𝑃(𝑛) es verdadero para 𝑛 = 𝑘 , es decir: 𝑃 𝑘 : 1 + 3 + 5 + ⋯ + (2𝑘 − 1) = 𝑘 2 • Debemos demostrar que 𝑃(𝑛) es verdadero para 𝑛 = 𝑘 + 1 , es decir: 𝑃 𝑘 + 1 : 1 + 3 + 5 + ⋯ (2𝑘 − 1) + (2(𝑘 + 1) − 1) = (𝑘 + 1) 2 Por lo tanto, se puede afirmar que 𝑃(𝑛) cumple para todo número natural 𝑛 . Comenzamos la prueba: 1 + 3 + 5 + ⋯ 2𝑘 − 1 + 2 𝑘 + 1 − 1 = + 2 𝑘 + 1 − 1 = 𝑘 2 +2𝑘 + 1 = (𝑘 + 1) 2 𝑘 2 Ejemplo de inducción matemática Solución. Ejercicio Demuestre que: ∀ 𝑛 ∈ ℕ, 𝑛 3 + 2𝑛 es divisible por 3 La invariante es una condición que se sigue cumpliendo después de la ejecución de determinadas iteraciones. Las invariantes se pueden utilizar para demostrar el buen funcionamiento de algoritmos y cumplen con un papel importante en el diseño. Invariante de un algoritmo Subrutina Comp ( X , Y ; Z ) Ciclo de la Subrutina Programa Invariante de un algoritmo 1. Z ← X 2. W ← Y 3. While ( W >0) a. Z ← Z + Y b. W ← W -1 4. RETURN Fin de Subrutina. Ejemplo Para el siguiente algoritmo: 𝑆𝑈𝐵𝑅𝑈𝑇𝐼𝑁𝐴 𝑆𝑈𝑀𝐴 𝑋, 𝑌 1. 𝑍 ← 𝑋/𝑌 2. 𝑊 ← 𝑌 𝑊𝐻𝐼𝐿𝐸 (𝑊 > 0) 𝑎. 𝑍 ← 𝑍 + 𝑋 𝑏. 𝑊 ← 𝑊 − 1 3. 𝑅𝐸𝑇𝑈𝑅𝑁𝐼𝑁 𝐷𝐸 𝐿𝐴 𝑆𝑈𝐵𝑅𝑈𝑇𝐼 a) Determine el invariante. b) Pruebe la validez de la invariante mediante inducción matemática. Solución (a): Hallando Invariante 𝑍 𝑛 = 𝑌 − 𝑊 𝑛 + 1 𝑋 Así, el invariante es: 𝒁 𝒏 + 𝑾 𝒏 𝑿 = 𝒀𝑿 + 𝑿 𝑊 0 = 𝑌 𝑍 𝑘+1 = 𝑍 𝑘 + 𝑋 𝑊 𝑘+1 = 𝑊 𝑘 − 1 Cálculo de la invariante Antes del ciclo Durante del ciclo: 𝑛 𝑍 𝑛 𝑊 𝑛 𝑍 1 = 𝑍 0 + 𝑋 1 = 𝑋 + 𝑋 = 2𝑋 𝑍 2 = 𝑍 1 + 𝑋 = (2𝑋) + 𝑋 = 3𝑋 𝑍 3 = 𝑍 2 + 𝑋 = (3𝑋) + 𝑋 = 4𝑋 2 3 𝒁 𝒏 = (𝒏 + 𝟏)𝑿 𝑍 𝑛 = 𝑍 𝑛−1 + 𝑋; 𝑛 𝑊 1 = 𝑊 0 − 1 = 𝑌 − 1 𝑊 2 = 𝑊 1 − 1 = 𝑌 − 2 𝑊 3 = 𝑊 2 − 1 = 𝑌 − 3 𝑾 𝒏 = 𝒀 − 𝒏 𝑊 𝑛 = 𝑊 𝑛−1 − 1; Despejando, 𝑛 = 𝑌 − 𝑊 𝑛 , reemplazamos en 𝑍 𝑛 : : 𝑍 0 = 𝑋 , 𝑊 0 = 𝑌 (𝑍 ← 𝑍 + 𝑋) (𝑊 ← 𝑊 − 1) = 𝑌𝑋 + 𝑋 − 𝑊 𝑛 𝑋 Ejemplo Solución (b): Probando la validez del invariante 𝑷 𝒏 : 𝒁 𝒏 + 𝑾 𝒏 𝑿 = 𝒀𝑿 + 𝑿 , ∀𝒏 ≥ 𝟎. • Recordemos que 𝑍 0 = 𝑋, 𝑊 0 = 𝑌 , luego Recordemos que 𝑍 𝑘+1 = 𝑍 𝑘 + 𝑋 y 𝑊 𝑘+1 = 𝑊 𝑘 − 1 , 𝑍 𝑘+1 − 𝑋 + (𝑊 𝑘+1 +1)𝑋 = 𝑌𝑋 + 𝑋 • Supongamos que 𝑃 𝑛 es verdadero, para 𝑛 = 𝑘 : Por tanto, 𝑃 𝑘 + 1 es verdadero; finalmente, se ha demostrado que 𝑷 𝒏 : 𝒁 𝒏 + 𝑾 𝒏 𝑿 = 𝒀𝑿 + 𝑿…