E.I.S.C

T´ ecnicas de demostraci´ on METODOS DE DEMOSTRACI´ ON

Definiciones b´ asicas Definici´ on 1. un Teorema es una sentencia que se puede verificar que es verdadera. (P1 ∧ P2 . . . ∧ Pn) → Q) es un teorema donde los P1 , P2 . . . Pn son los postulados o premisas y Q la conclusi´ on del teorema. Ejemplo 1. Sea el siguiente teorema si a y b son enteros positivos, a ≥ b, entonces a0 ≥ b0 premisas: P1 : a y b son enteros positivos. P2 : a ≥ b y la conclusi´ on Q es a0 ≥ b0 por lo tanto el teorema ser´ıa (P1 ∧ P2 ) → Q Definici´ on 2. Un lema es un teorema sencillo utilizado en la demostraci´ on de otros teoremas. Definici´ on 3. Un corolario es una proposici´ on que se puede establecer directamente a partir de un teorema que ya ha sido demostrado. 1. REGLAS DE INFERENCIA. Estas reglas justifican los pasos dados para demostrar que a partir de una serie de hip´ otesis se llega de forma l´ ogica a una conclusi´ on. Ejemplo 2. Una regla de inferencia b´ asica es la modus ponens

E.I.S.C

T´ ecnicas de demostraci´ on

p p→q ∴q Ejemplo 3. En que regla de inferencia se basa el siguiente argumento: Ahora estamos bajo cero. Por tanto estamos bajo cero o bien llueve ahora. p ∴p∨q Esta es la regla de inferencia de la Adici´ on y su tautolog´ıa ser´ıa p → (p ∨ q) Ejemplo 4. Cu´ al es la regla de inferencia de para el siguiente argumento: Estamos bajo cero y llueve. Por tanto, estamos bajo cero. p∧q ∴p Este argumento usa la regla de la simplificaci´ on y su tautolog´ıa ser´ıa (p ∧ q) → p.

E.I.S.C

T´ ecnicas de demostraci´ on

Ejemplo 5. Fue X o Y qui´ en cometi´ o el crimen. X estaba fuera del pueblo cuando el crimen fue cometido. Si X estaba fuera del pueblo, no pudo haber estado en la escena del crimen. Si X no estaba en la escena del crimen, no pudo haber cometido el crimen. Obtenga la conclusi´ on usando las reglas de inferencia. P1: X cometi´ o el crimen. P2: Y cometi´ o el crimen. Q: X estaba fuera del pueblo cuando fue cometido el crimen. R: X no estaba en la escena del crimen.

E.I.S.C

T´ ecnicas de demostraci´ on

El argumento en LP: 1) P 1 ∨ P 2 2) Q 3) Q → R 4) R →v P 1 5) R aplicando modus ponens a (2) y (3) 6) v P 1 aplicando modus ponens a (5) y (4) 7) ∴ P 2 aplicando el silogismo disyuntivo a (1) y (6) Por lo tanto se concluye que Y cometi´ o el crimen. Tambi´ en se puede demostrar la validez de un argumento derivando la conclusi´ on desde las premisas usando las REGLAS DE INFERENCIA. Ejemplo 6. Dado el siguiente argumento v´ alido: Si la banda no pudiera tocar rock o las bebidas no llegasen a tiempo, entonces la fiesta de A˜ no Nuevo tendr´ıa que cancelarse y Alicia se enojar´ıa. Si la fiesta se cancelara, habr´ıa que devolver el dinero. No se devolvio el dinero. Por lo tanto, la banda pudo tocar rock. Derive la consecuencia l´ ogica usando las reglas de inferencia. P : la banda pudo tocar rock. Q: las bebidas se entregaron a tiempo. R: la fiesta de A˜ no Nuevo se cancel´ o. S: Alicia estaba enojada. T : Hubo que devolver el dinero. El argumento v´ alido: Premisas: 1)(v P ∨ v Q) → (R ∧ S)

E.I.S.C

T´ ecnicas de demostraci´ on

2) R → T 3) v T ∴P Se debe inferir con las premisas 1,2 y 3 y llegar a derivar P. 1)R → T premisa 2) v T premisa 3) v R aplicando modus tollens a (1) y (2) 4) v R∨ v S aplicando ley de adici´ on con (3) 5) v (R ∧ S) aplicando ley de morgan a (4) 6) (v P ∨ v Q) → (R ∧ S) premisa 7) v (v P ∨ v Q) aplicando modus tollens a (5) y (6) 8) P ∧ Q aplicando ley de morgan y de la doble negaci´ on a (7) 9) ∴ P aplicando simplificaci´ on conjuntiva a (8) Ejemplo 6.1 aplique las reglas de inferencia para demostrar que q → p es una consecuencia l´ ogica de las premisas: u → r; (r ∧ s) → (p ∨ t); q → (u ∧ s); ∼ t 1) 2) 3) 4) 5) 6) 7) 8) 9)

(r ∧ s) → (p ∨ t) premisa v r∨ v s ∨ p ∨ t aplicaci´ on de la implicaci´ on a 1 u → r premisa v u ∨ r aplicaci´ on de la implicaci´ on a 3 v u∨ v s ∨ p ∨ t resoluci´ on 2 y 4 v (u ∧ s) ∨ p ∨ t aplicaci´ on de morgan a 5 (u ∧ s) → (p ∨ t) aplicaci´ on de implicaci´ on a 6 q → (u ∧ s) premisa q → (p ∨ t) silogismo hipot´ etico 8 y 7

E.I.S.C 10) 11) 12) 13)

T´ ecnicas de demostraci´ on

(v q ∨ p) ∨ t implicaci´ on y asociativa de 9 v t premisa v q ∨ p silogismo disyuntivo de 10 y 11 ∴ q → p implicaci´ on de 12

2. METODOS PARA DEMOSTRAR TEOREMAS. 2.1 Demostraci´ on Directa. Se basa en la implicaci´ on p → q se puede demostrar que si p es verdadero q tambi´ en lo es. p: es la hip´ otesis (lo que se supone como verdadero) q: es la Tesis (lo que se va ha demostrar) Definici´ on 1. El entero n es par si existe un entero k tal que n = 2k y es impar si existe un entero k tal que n = 2k + 1 Ejemplo 7. Demostrar que si n es un entero impar, entonces n2 es un entero impar. p: n es impar. (hip´ otesis) 2 q: n es impar. (tesis) Se demuestra p → q, se parte de que p verdadero y se termina demostrando que q es verdadero. Si n es impar entonces, n = 2k + 1, donde k es un entero. Se sigue que n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2 (k2 + k) +1 | {z } t∈Z

Por tanto como n2 es de la forma 2t + 1 entones

E.I.S.C

T´ ecnicas de demostraci´ on

n2 es impar. Definici´ on 2. El n´ umero real r es racional si existen dos enteros p y q, q 6= 0, tales que r = p/q. Un n´ umero real que no es racional es irracional. Ejemplo 8. Demuestre que la suma de dos racionales es un racional. p: Sean r y s racionales, si r es racional entonces r = p/q para q 6= 0 y si s es racional entonces s = t/u para u 6= 0. (hip´ otesis) q: Hay que demostrar que r + s es racional. (tesis) sumamos r + s = pq + ut = pu+qt , donde qu 6= 0 qu por que q 6= 0 y u 6= 0 por tanto hemos expresado r + s como la raz´ on de dos enteros pu + qt y qu POR TANTO r + s es racional. 2.2 Demostraci´ on indirecta. Como la implicaci´ on p → q es equivalente a su contrarec´ıproca v q →v p la implicaci´ on se puede demostrar viendo que su contrarec´ıproca es verdadera. Ejemplo 9. Demostrar que si 3n + 2 es impar, entonces n es impar. p: 3n + 2 es impar. q: n es impar. Suponemos la v q es decir que n es par, entonces n = 2k para alg´ un entero k y demostramos v p es decir que 3n + 2 es par.

E.I.S.C

T´ ecnicas de demostraci´ on

ahora se sigue que 3n + 2 = 3(2k) + 2 = 2(3k) + 2 = 2 (3k + 1) y 3n + 2 es de la forma 2l | {z } l∈Z

Por tanto 3n + 2 es par, es decir v p Ejemplo 10. Demuestre que la suma de dos impares es par. p: r y s son impares. q: r + s es par. Suponemos que r +s es impar y se debe demostrar que r o s son pares no de manera simult´ anea. Sea r + s impar entonces r + s = 2k + 1, k ∈ Z Vemos que pasa cuando s es par y cuando s es impar s es PAR, suponemos que s = 2t, t ∈ Z, entonces r = 2k + 1 − 2t = 2 (k − t) +1 por tanto r es IM| {z } Z

PAR. Cuando s es par r es impar. s es IMPAR, s = 2t + 1, t ∈ Z, entonces r = 2k + 1 − 2t − 1 = 2k − 2t = 2 (k − t) | {z } Z

Por tanto r es PAR. Cuando s es impar r es par. De ninguna forma bajo la premisa v q, r y s son o pares o impares por tanto se garantiza v p 2.3 Contraejemplo. Se busca un ejemplo para refutar el cu´ al la implicaci´ on o doble implicaci´ on sea falsa.

E.I.S.C

T´ ecnicas de demostraci´ on

Ejemplo 11. Demuestre o refute la proposici´ on que expresa que si x y y son n´ umeros reales, (x2 = y 2 ) ↔ (x = y) Buscamos un ejemplo que contradiga la afirmaci´ on, sean x = −3 y y = 3 entonces (−3)2 = (3)2 , pero −3 6= 3, el resultado es falso. Este es el CONTRAEJEMPLO. 2.4 Demostraci´ on por contradicci´ on o reducci´ on al absurdo. Dado p, supongamos que se puede encontrar una contradicci´ on q tal que v p → q sea verdadera, esto es, v p → F es verdadera. Entonces la preposici´ on v p tiene que ser FALSA. por tanto p DEBE SER VERDADERA. Por ejemplo una contradicci´ on q puede ser r∧ v r entonces podemos mostrar que v p → (r∧ v r) sea VERDADERA. √ Ejemplo 12. Demuestre√que 2 es irracional. Sea p: la proposici´ on 2 es irracional √ y supongamos que v p es verdadera. Entonces 2 es racional. Mostraremos que √ esto conduce a una contradicci´ on. Sea que 2 es racional por tanto: Existen dos enteros a y b de tal forma que √ 2 = a/b, donde a y b no tiene FACTORES COMUNES (es decir que no hay una fracci´ on equivalente a a/b m´ as peque˜ na).

E.I.S.C

T´ ecnicas de demostraci´ on √

Como 2 = a/b entonces 2 = a2 /b2 y por tanto 2b2 = a2 Esto significa que a2 es PAR, entonces a es PAR, y a es de la forma a = 2c para alg´ un c∈Z Bien entonces 2b2 = 4c2 por lo que b2 = 2c2 esto significa que b2 es PAR, por tanto b es PAR. Se ha mostrado que ambos a y b son PARES y por tanto tienen factor com´ un 2. Esto es una CONTRADICCION a la suposici´ on de que en √ 2 = a/b, a y b no tiene FACTORES COMUNES Entonces se ve que v p implica tanto r como v r donde r es la sentencia a y b son enteros sin FACTORES COMUNES. Por tanto √ v p es falsa y p es verdadera, entonces 2 es IRRACIONAL. para que v p → F sea verdadera v p debe ser FALSA y por tanto p es VERDADERA. Ejemplo 13. Demuestre por el absurdo que si 3n+2 es impar, entonces n es impar. Suponemos que n es PAR sabiendo que 3n + 2 ´ es IMPAR y llegamos a una CONTRADICCION. Sea n par, tambi´ en suponemos que 3n+2 es impar

E.I.S.C

T´ ecnicas de demostraci´ on

por tanto 3n + 2 = 2q + 1 = 3n = 2q + 1 − 2 =, n = 2q−1 para q ∈ Z por tanto es una CON3 ´ por que n es UN ENTERO PAR. TRADICCION Esta es una aplicaci´ on de la tautolog´ıa ((p → q) ∧ (v q) → (v p)) modus tollens dado que el argumento es una implicaci´ on p → q. Ahora como ((p → q) ∧ (v q) → (v p)) es v´ alida p → q debe ser verdadera y p y q deben ser verdaderas y asu vez v q y v p son falsas entonces ((p → q) ∧ (v q) → (v p)) ≡ ((V ∧ F ) → F ) ≡ V | {z } | {z } | {z } V

F

F

2.5 Demostraci´ on por casos. Se demuestra la implicaci´ on: (p1 ∨ p2 . . . ∨ pn) → q y resolvemos (p1 ∨ p2 . . . ∨ pn) → q =v (p1 ∨ p2 . . . ∨ pn) ∨ q (p1 ∨ p2 . . . ∨ pn) → q = (v p1 ∧ v p2 . . . ∧ v pn) ∨ q (p1 ∨ p2 . . . ∨ pn) → q = q ∨ (v p1 ∧ v p2 . . . ∧ v pn) (p1 ∨ p2 . . . ∨ pn) → q = (q∨ v p1 ) ∧ (q∨ v p2 ) . . . ∧ (q∨ v pn) (p1 ∨ p2 . . . ∨ pn) → q = (v p1 ∨ q) ∧ (v p2 ∨ q) . . . ∧ (v pn ∨ q) (p1 ∨p2 . . .∨pn) → q = (p1 → q)∧(p2 → q) . . .∧(pn → q) Por tanto podemos decir que: [(p1 ∨ p2 . . . ∨ pn) → q] ↔ [(p1 → q) ∧ (p2 → q) . . . ∧ (pn → q)] Ejemplo 14. Demuestre por casos que | xy |=| x || y |, donde x y y son reales.

E.I.S.C

T´ ecnicas de demostraci´ on

Definici´ on valor absoluto:   x si x ≥ 0 | x |=  −x si x ≤ 0 Por casos entonces: p: x e y son reales q: | xy |=| x || y | p es equivalente a p1 ∨ p2 ∨ p3 ∨ p4 p1 es x ≥ 0 y y ≥ 0 p2 es x ≥ 0 y y < 0 p3 es x < 0 y y ≥ 0 p4 es x < 0 y y < 0 Por tanto podemos demostrar: (p1 → q) ∧ (p2 → q) ∧ (p3 → q) ∧ (p4 → q) (p1 → q) entonces xy ≥ 0 por que x ≥ 0 y y ≥ 0, y por tanto | xy |= xy =| x || y | (p2 → q) si x ≥ 0 y y < 0, entonces xy ≤ 0, por tanto | xy |= −xy = x(−y) =| x || y | (aqu´ı como y < 0, tenemos que | y |= −y) (p3 → q) si x < 0 y y ≥ 0, entonces xy ≤ 0, por tanto | xy |= −xy = (−x)y =| x || y | (aqu´ı como x < 0, tenemos que | x |= −x)

E.I.S.C

T´ ecnicas de demostraci´ on

(p4 → q) si x < 0 y y < 0, entonces xy > 0, por tanto | xy |= xy == (−x)(−y) =| x || y | (aqu´ı como y < 0, tenemos que | y |= −y y x < 0, tenemos que | x |= −x) 2.6 Demostraci´ on por equivalencia Se puede demostrar un teorema que viene dado por un bicondicional, esto es: p ↔ q ≡ (p → q) ∧ (q → p) Ejemplo 15. Demostrar el teorema: El entero n es impar si, y s´ olo si, n2 es impar. p:El entero n es impar. q:El entero n2 es impar. 1)p → q, Hay que demostrar que si n es impar, entonces n2 es impar. (m´ etodo directo). sea n impar es de la forma n = 2k + 1 donde k ∈ Z ahora vemos que pasa con n2 = (2k + 1)2 = 4k2 + 4k + 1 = 2 (2k2 + 2k) +1 por tanto n2 es | {z } Z

IMPAR. (queda demostrada p → q) 2)q → p, Hay que demostrar que si n2 es impar, entonces n es impar. (Contradicci´ on). supongo que n es par, por tanto es de la forma n = 2k tomando como premisa que n2 es impar y llego a una contradicci´ on. ahora vemos que pasa con n2 = (2k)2 = 4k2 = al es una CON2 (2k2 ) por tanto n2 es PAR lo cu´ | {z } Z

´ TRADICCION por que estamos suponiendo que

E.I.S.C

T´ ecnicas de demostraci´ on

n2 es IMPAR por tanto si n2 es impar, entonces n es impar (queda demostrada p → q) 2.7 Demostraci´ on por unicidad. Mostrar que existe un ´ unico elemento x tal que P (x) es lo mismo que demostrar la sentencia: ∃x(P (x) ∧ ∀y(y 6= x →v P (y))) Entonces demostramos: 1) Existencia. mostramos que existe un elemento x con la propiedad deseada. 2) Unicidad. Mostramos que si y 6= x, entonces y no tiene la propiedad deseada. Ejemplo 15.1 Demuestre que todo entero tiene un unico inverso respecto a la suma. ´ Esto es si p es un entero, entonces existe un unico entero q tal que p + q = 0 ´ Existencia: Si p ∈ Z, encontramos que p+q = 0 cuando q = −p como q tambi´ e es entero, por consiguiente, existe un entero q tal que p+q =0 Unicidad: se muestra que dado el entero p, el entero q tal que p + q = 0 es UNICO. supongamos que existe r ∈ Z tal que r 6= q y p + r = 0 entonces p + q = p + r por tanto q = r lo que contradice la suposici´ on de que r 6= q.

E.I.S.C

T´ ecnicas de demostraci´ on

Por lo tanto hay un UNICO entero q tal que p+q =0 Ejercicios Resueltos 1. Sean m y n enteros. Demuestre que n2 = m2 si y s´ olo si m = n o m = −n Como es un teorema de si y s´ olo si p ↔ (q ∨ r) = (p → (q ∨ r)) ∧ ((q ∨ r) → p) 1)p → (q ∨ r) Entonces p : n2 = m2 y q :m = n o r:m = −n Sea n2 = m2 , n2 − m2 = 0, (n − m)(n + m) = 0 entonces (n − m) = 0 y (n + m) = 0 por tanto m = n o m = −n. 2) (q ∨ r) → p Sea m = n o m = −n, n − m = 0 y n + m = 0, (n − m)(n + m) = 0, n2 − m2 = 0, por tanto n2 = m2 2. Demuestre que la suma de un irracional y un racional es un irracional. Por contradicci´ on suponemos que la suma de un irracional y un racional es racional bajo la suposici´ on de que i es irracional y r es el racional y llegamos a contradicci´ on llegando a establecer que cualquiera de los dos no cumple con la condici´ on de ser racional o irracional.

E.I.S.C

T´ ecnicas de demostraci´ on

Sea i un irracional y r un racional entonces suponemos que i + r es un racional, es decir i + r = s donde s es racional. Si despejamos i nos queda que i = s − r es un RACIONAL lo cual es una contradicci´ on por que i es un irracional.

3. Demuestre que la suma de dos racionales es ´ un n´ umero racional (CONTRADICCION) Sean r y s racionales, entonces suponemos que r + s es irracional, es decir r + s = i, despejamos r = i−s pero como se demostr´ o que la suma de un irracional y un racional es un racional, entonces podemos deducir que r es un irracional Por tanto es una contradicci´ on por que r es racional.

4. Demuestre que el producto de dos racionales es racional. Por el m´ etodo directo es muy f´ acil se suponen que r y s son racionales y se debe demostrar que el producto es racional. sean r = pq , p, q ∈ Z para q 6= 0 y s = kt k, t ∈ Z

E.I.S.C

T´ ecnicas de demostraci´ on

para t 6= 0 y continuamos realizando el prodonde qt 6= 0 y pk ∈ Z y ducto r · s = pq · kt = pk qt por tanto demostramos que r·s es un racional. 5. Demuestre que si x es irracional, 1/x tambi´ en lo es.(sea p : x es irracional y q : 1/x es irracional p → q Por el m´ etodo indirecto (se demuestra v q →v p) Entonces suponemos que 1/x es racional y demostramos que x es racional. Sea 1/x un racional entonces 1x = pq donde p, q ∈ Z, q 6= 0 Ahora pq debe ser diferente de cero por que 1 6= x · 0 por tanto p 6= 0. Despejamos x, x = pq donde ambos son enteros y p 6= 0 por lo tanto x es un RACIONAL.

6. Demuestre que si x e y son n´ umeros reales, entonces max(x, y) + min(x, y) = x + y Por casos; primero se demuestra para x ≤ y y segundo para x ≥ y. 1) Sea x ≤ y entonces max(x, y) + min(x, y) = y +x como y +x = x+y por tanto max(x, y)+ min(x, y) = x + y

E.I.S.C

T´ ecnicas de demostraci´ on

2) Sea x ≥ y entonces max(x, y) + min(x, y) = x+y 3. SUCESIONES, SUMATORIAS Y PRODUCTORIAS. Sucesi´ on. Es una lista de objetos dispuestos en orden. un primer elemento, segundo elemento, un tercer elemento y as´ı sucesivamente. esta es una sucesi´ on FINITA. Ejemplo 16. Si la lista empieza por un primer elemento y sigue hasta n pasos, n ∈ N es una sucesi´ on INFINITA. Ejemplo 17. La sucesi´ on 1,0,0,1,0,1,0,0,1,1,1 es una sucesi´ on finita de elementos repetidos. Ejemplo 18. La lista 3,8,13,18,23,... es una sucesi´ on infinita. Ejemplo 19. Otra sucesi´ on infinita de los cuadrados de todos los enteros positivos. 1,4,9,16,25,...., 3.1 F´ ormula recursiva o recurrente Ejemplo 20. Sea la sucesi´ on infinita 3,8,13,18,23,...la podemos expresar como una f´ ormula recurrente as´ı: an = an−1 + 5 para a1 = 3 para 2 ≤ n < ∞ Ejemplo 21. Sea la sucesi´ on infinita 5,10,20,40,80,160 la podemos expresar como una f´ ormula recurrente as´ı: tn = 2tn−1 para t1 = 5 para 2 ≤ n ≤ 6

E.I.S.C

T´ ecnicas de demostraci´ on

Ejemplo 22. Encontrar una f´ ormula recursiva para la sucesi´ on 3,7,11,15,19,23,.... 3.2 F´ ormula Expl´ ıcita. Ejemplo 23. Sea la sucesi´ on 1,4,9,16,25,...., la f´ ormu2 la expl´ıcita es bn = n tal que n ≥ 1 Ejemplo 24. Sea la sucesi´ on -4,16,-64,256,.... n sn = −(4) para n ≥ 1 Ejemplo 25. Encontrar una f´ ormula expl´ıcita para la sucesi´ on finita: 87,82,77,72,67. 3.3 Progresi´ on geom´ etrica. Es una sucesi´ on de la forma: a, ar, ar 2 , . . . , arn donde el t´ ermino inicial a y la raz´ on r de la progresi´ on son reales. Ejemplo 26. La sucesi´ on {bn}, bn = (−1)n para n ≥ 1 es una progresi´ on geom´ etrica donde el termino inicial a = −1 y la raz´ on r = −1 b1 , b2 , b3 , b4 , . . . comienza por −1, 1, −1, 1, .... Ejemplo 27. Sea cn = 2 · 5n para n ≥ 1 es una progresi´ on geom´ etrica con t´ ermino inicial a = 10 y raz´ on r = 5 donde c1 , c2 , c3 , c4 , . . . comienza por 10, 50, 250, 1,250, . . . , Ejemplo 28. Dada la siguiente progresi´ on geom´ etrica dn = 6 · (1/3)n para n ≥ 1 encontrar el t´ ermino inicial y la raz´ on.

E.I.S.C

T´ ecnicas de demostraci´ on

3.4 Progresi´ on aritm´ etica. Una progresi´ on aritm´ etica es una sucesi´ on de la forma: a, a + d, a + 2d, a + 3d, . . . , a + nd donde el t´ ermino inicial a y la diferencia d son n´ umeros reales. Ejemplo 29. La sucesi´ on sn = −1 + 4n para n ≥ 0 es una progresi´ on aritm´ etica con t´ ermino inicial a = −1 y diferencia d = 4, la progresi´ on comienza c0 , c1 , c2 , c3 , . . . comienza por −1, 3, 7, 11, . . . Ejemplo 30. La sucesi´ on tn = 7 − 3n para n ≥ 0 es una progresi´ on aritm´ etica con t´ ermino inicial a = 7 y diferencia d = −3, la progresi´ on comienza t0 , t1 , t2 , t3 , . . . comienza por 7, 4, 1, −2, . . . 3.5 Sumatorias. Usamos la notaci´ on de la sumatoria para expresar la suma de los t´ erminos. am , am+1 , · · · , an de la sucesi´ on {an}. Usamos la notaci´ on n X

aj

j=m

Para representar am + am+1 + · · · + an j es el ´ındice de la sumatoria, n l´ımite superior y m l´ımite inferior. Ejemplo 31. Exprese la suma de los cien primeros

E.I.S.C

T´ ecnicas de demostraci´ on

t´ erminos de la sucesi´ on {an}, donde an = 1/n para n = 1, 2, 3, . . . 100 X 1 j=1

j

Ejemplo 32. Cu´ al es el valor de

P5

P5

j=1 j

2

= 12 + 22 + 32 + 42 + 52 = 1 + 4 + 9 + 16 + 25 = 55 j=1 j

2

Ejemplo 33. supongamos que tenemos la suma: 5 X

2

j=1

y queremos que el ´ındice var´ıe entre 0 y 4 en lugar de 1 y 5 para conseguir esto hacemos k = j − 1 por tanto el t´ ermino j 2 se convierte en (k + 1)2 , as´ı: 4 X

(k + 1)2

k=0

Es f´ acil ver que ambas suman 55. Ejemplo 34. Supongamos que tenemos: 4 X 3 X i=1 j=1

ij

E.I.S.C

T´ ecnicas de demostraci´ on

Primero se desarrolla la sumatoria interna: 4 X 3 X i=1 j=1

ij =

4 X

(i+2i+3i) =

i=1

4 X

6i = 6+12+18+24 = 60

i=1

Pn

Pn

i=1 can = Pn Pcn i=1 anPn + i=1 bi i=1 Pn(ai + bi) = i=1 ai P n (a + b ) = na + i i=1 P i=1 bi n i = n(n+1) i=1 2 Pn 2 n(n+1)(2n+1) i=1 i = 6 P n n2 (n+1)2 3 i = 4 Pn Pn+pi=1 Pn−p f (k) = f (k − p) = k=iP k=i+p k=i−p f (k + p) n opica j=1 (aj − aj−1 ) = an − a0 telesc´ Pn k = ar n+1 −a , r 6= 1 ar k=0 r−1

Teorema 1. Si a y r son reales y r 6= 0, entonces:  arn+1−a n X si r 6= 1 r−1 ar j = (n + 1)a si r = 1 j=0

Ejemplo 35.0 Use la f´ ormula para la suma de los t´ erminos de una progresi´ on geom´ etrica para evaluar la suma de la progresi´ on Cn = 2 · 3n, para 5 ≥ n ≥ 0: La sucesi´ on Cn tiene como elementos 2, 2 · 3, 2 · 32 , 2 · 33 , 2 · 34 , 2 · 35 Entonces podemos calcular la suma de estos elementos: 5 X j=0

2 · 3j = 2 + 2 · 3 + 2 · 32 + 2 · 33 + 2 · 34 + 2 · 35

E.I.S.C

T´ ecnicas de demostraci´ on

Usando el teorema 1. donde a = 2 y r = 3 tenemos: 5 X

2 · 35+1 − 2 2(36 − 1) 2·3 = = = 36 − 1 = 728 3−1 2 j=0 j

Ejemplo 35. Obtener 100 X

k2

k=50

Soluci´ on:

P100

P49

P100

P100

2 = k=1 k jamos: 2 k=50 k =

2 k=1 k +

2 k=1 k −

seg´ un la tabla

P100

k=50 k

2

=

P100

k=50 k

P49

k=1 k

Pn

2 k=1 k =

2

entonces despe-

2

n(n+1)(2n+1) 6

100·101·201 49·50·99 − 6 6

=338.350 -40.425=297.925

Ejemplo 36. Aplique la propiedad telesc´ opica para calcular: n X (2k − 1) k=1

Sea 2k − 1 = k2 − (k − 1)2 entonces obtenemos

Pn

k=1 (k

2

− (k − 1)2 ) = n2

E.I.S.C

T´ ecnicas de demostraci´ on

3.6 Productorias. El producto de am, am+1 , · · · , an se representa por: n Y

aj

j=m

Ejemplo 37. Cu´ al es el valor de estos productos Q10 i=0 Qi=0 8 i=5 i = 5 · 6 · 7 · 8 = 1680 Ejemplo 38. Cu´ al es el valor de estos productos Q4 i=0 j! = 1 · 2 · 6 · 24 = 288 4. INDUCCION MATEMATICA. Es una t´ ecnica de demostraci´ on que se utiliza para demostrar muchos teoremas que afirman que P (n) es verdadera para todos los enteros positivos n. La inducci´ on matem´ atica se usa para demostrar proposiciones de la forma ∀nP (n), donde el dominio es el conjunto de los enteros positivos. Una demostraci´ on por inducci´ on de que P (n) es verdadera para todo n ∈ Z+ consiste en dos pasos: PASO BASE: Se muestra que la proposici´ on P(1) es verdadera. PASO INDUCTIVO: se muestra que la implicaci´ on P (k) → P (k + 1) es verdadera para todo entero positivo k. La sentencia P (k) para un entero positivo fijo k se denomina la hip´ otesis de inducci´ on.

E.I.S.C

T´ ecnicas de demostraci´ on

La inducci´ on matem´ atica expresada como regla de inferencia: [P (1) ∧ ∀k(P (k) → P (k + 1))] → ∀nP (n) En pocas palabras s´ olo se muestra que si se supone que P (k) es verdadera, entonces P (k + 1) es tambi´ en verdadera. Ejemplo 39. Demostrar por inducci´ on que la suma de los n primeros enteros positivos para n ≥ 1 es n(n+1) es decir: 2 1 + 2 + 3 + ··· + n =

n(n+1) 2

Sea P (n) : el predicado 1 + 2 + 3 + · · · + n = para n ≥ 1

n(n+1) 2

PASO BASE: Se muestra que P (1) es verdadera. entonces lo cu´ al es verdadera. P (1): 1 = 1(1+1) 2 PASO INDUCTIVO: Se debe demostrar que si P (k) es verdadera entonces P (k + 1) para k ≥ 1 Sea P (k) : (hip´ otesis de inducci´ on) k(k + 1) 2 Ahora hay que demostrar la verdad de P (k + 1) : (tesis de inducci´ on) 1 + 2 + 3 + ··· + k =

1 + 2 + 3 + · · · + (k + 1) =

(k + 1)(k + 2) 2

E.I.S.C

T´ ecnicas de demostraci´ on

Entonces comienza la demostraci´ on tomando la hip´ otesis: k(k + 1) 2 se suma (k + 1) en ambos miembros: 1 + 2 + 3 + ··· + k =

1 + 2 + 3 + · · · + k + (k + 1) =

k(k + 1) + (k + 1) 2

k(k + 1) + 2(k + 1) 2 factorizando (k + 1) nos queda:

1 + 2 + 3 + · · · + k + (k + 1) =

(k + 1)(k + 2) 2 Por tanto como se demostr´ o la tesis de inducci´ on, entonces P (n) es verdadero para todos los valores n ≥ 1. 1 + 2 + 3 + · · · + k + (k + 1) =

Ejemplo 40. Demostrar por inducci´ on para n ≥ 1 que: 1 + 3 + 5 + · · · + (2n − 1) = n2 PASO B´ ASICO: sea P (1) 1 = 12 PASO INDUCTIVO: Se debe demostrar que si P (k) es verdadera entonces P (k + 1) para k ≥ 1 Sea P (k) : (hip´ otesis de inducci´ on) 1 + 2 + 3 + · · · + (2k − 1) = k2

E.I.S.C

T´ ecnicas de demostraci´ on

Ahora hay que demostrar la verdad de P (k + 1) : (tesis de inducci´ on) 1 + 2 + 3 + · · · + (2k − 1) + (2k + 1) = (k + 1)2 Entonces comienza la demostraci´ on tomando la hip´ otesis: 1 + 2 + 3 + · · · + (2k − 1) = k2 se suma (k + 1) en ambos miembros: 1 + 2 + 3 + · · · + (2k − 1) + (2k + 1) = k2 + (2k + 1) 1 + 2 + 3 + · · · + (2k − 1) + (2k + 1) = k2 + 2k + 1 1 + 2 + 3 + · · · + (2k − 1) + (2k + 1) = (k + 1)2 Entonces queda demostrada la tesis de inducci´ on, por tanto para n ≥ 1 P (n) es verdadera. Ejemplo 41. Demostrar por inducci´ on la desigualdad: n n < 2 para n ≥ 1 Sea P (n) : es la proposici´ on n < 2n ´ SICO: P (1) es verdadera, dado que 1) PASO BA 1 < 21 = 2 2) PASO INDUCTIVO: Suponemos que P (k) es verdadero y demostramos que P (k + 1) tambi´ en lo es. P (k): k < 2k para k ≥ 1 P (k + 1): k + 1 < 2k+1 para n ≥ 1 k < 2k

E.I.S.C

T´ ecnicas de demostraci´ on

sumamos 1 a ambos lados: k + 1 < 2k + 1 k + 1 < 2k + 1 ≤ 2k + 2k = 2 · 2k = 2k+1 Por tanto k + 1 < 2k+1 Ejemplo 42. (Ejercicio propuesto) Demostrar por inducci´ on que: 1 + 2 + 22 + · · · + 2n = 2n+1 − 1 para n ≥ 0 4.1 Invariante de ciclo Es una t´ ecnica para demostrar que los ciclos y programas hacen lo que se afirma que hacen. Hacen parte de la teor´ıa de la verificaci´ on de algoritmos. Es una relaci´ on entre variables que persiste a trav´ es de todas las iteraciones del ciclo.

E.I.S.C

T´ ecnicas de demostraci´ on

Ejemplo 43. Consideremos el siguiente c´ odigo: FUNCTION CUAD (A) 1. C ← 0 2. D ← 0 3. WHILE (D 6= A) a. C ← C + A b. D ← D + 1 4. RETURN(C) Este ciclo calcula el cuadrado del n´ umero A es de2 cir C = A Pasos: 1. Encontramos la invariante de ciclo que relacione algunas de las variables, para ello se debe realizar la prueba de escritorio. 2. La invariante nada tiene que ver con la salida. 3. Demostramos por inducci´ on matem´ atica la invariante de ciclo encontrada. La invariante de ciclo ser´ a la proposici` on P (n) Hay s´ olo tres variables de las cuales A se comporta como constante, C y D como variables a trav´ es de la prueba de escritorio. La invariante de ciclo es la proposici´ on P (n) : Cn = A × Dn para n ≥ 0 Ahora la demostramos por inducci´ on: ´ SICO: Sea P (0) entonces C0 = A × D0 , PASO BA

E.I.S.C

T´ ecnicas de demostraci´ on

0 = A × 0 por tanto se cumple. PASO INDUCTIVO: P (k) : Ck = A × Dk (Hip´ otesis) P (k + 1) : Ck+1 = A × Dk+1 (Tesis) Ck+1 = = = =

(1) (2)

Ck + A A × Dk + A usando (1) para reemplazar en Ck A × (Dk + 1) Factorizando A × Dk+1 segundo miembro de P(k+1)

y por tanto queda demostrado que P (n) : Cn = A × Dn para n ≥ 0 Ejemplo 44. Para la siguiente rutina, encontrar la invariante de ciclo y demostrarla por inducci´ on. RUTINA exp(N,M:R) 1. R ← 1 2. K ← 2M 3. WHILE (k > 0) a. R ← R × N b. K ← K − 1 4. RETURN CALCULA: R = N 2M La invariante de ciclo es la proposici´ on k 2M n P (n) : Rn × N = N ´ SICO: P (0) : R0 ×N k0 = N 2M , 1×N 2M = PASO BA N 2M entonces N 2M = N 2M por tanto se cumple P (0)

E.I.S.C

T´ ecnicas de demostraci´ on

PASO INDUCTIVO: P (s) : Rs × N ks = N 2M (Hip´ otesis) P (s + 1) : Rs+1 × N ks+1 = N 2M (Tesis) Rs+1 × N ks+1

= = = = = =

Rs × N × N ks+1 reemplazando 3.a Rs × N × N ks −1 reemplazando 3.b Rs × N × N ks × N −1 usando ´ algebra ks −1 agrupando Rs × N × N × N Rs × N ks N 2M usando la hip´ otesis

Por tanto queda demostrado que Rs+1 × N ks+1 = N 2M 5. DEFINICIONES RECURSIVAS. A veces es d´ıficil definir objetos de forma expl´ıcita y sin embargo, puede resultar sencillo definirlos en t´ erminos de ellos mismos, este proceso se llama recursi´ on. Podemos utilizar la recursi´ on para definir sucesiones, funciones y conjuntos. Podemos demostrar resultados sobre conjuntos definidos recursivamente empleando el m´ etodo de inducci´ on estructural. Utilizamos dos pasos para definir una funci´ on recursivamente bajo el dominio de los enteros no negativos.

E.I.S.C

T´ ecnicas de demostraci´ on

1. PASO BASE: Se especifica el valor de la funci´ on en cero. 2. PASO RECURSIVO: Se proporciona una regla para obtener su valor en un entero a partir de sus valores en enteros m´ as peque˜ nos. Ejemplo 45. Supongamos que f se define recursivamente como sigue: f (0) = 3 f (n + 1) = 2f (n) + 3 Entonces: f (1) = 2f (0) + 3 = 2,3 + 3 = 9 f (2) = 2f (1) + 3 = 2,9 + 3 = 21 f (3) = 2f (2) + 3 = 2,21 + 3 = 45 f (4) = 2f (3) + 3 = 2,45 + 3 = 93 Ejemplo 46. Una definici´ on recursiva de la funci´ on factorial f (n) = n! Primero se especifica un valor para f (0) y encontramos una regla para calcular f (n + 1) en funci´ on de f (n). f (0) = 1 f (n + 1) = (n + 1)f (n) Calculemos f (4) f (4) = 4 · f (3) = 4 · 3f (2) = 4 · 3 · 2 · f (1) = 4 · 3 · 2 · 1 · f (0) = 4 · 3 · 2 · 1 · 1 = 24 podemos tami´ en obtener un c´ odigo simple para la funci´ on factorial:

E.I.S.C

T´ ecnicas de demostraci´ on

Funci´ on factorial (n:entero positivo) If n=1 then Factorial(n):=1 Else Factorial(n):= n*factorial(n-1) End funci´ on. Factorial (3)=3*factorial(2)=3*2*factorial(1)=3*2*1=6 Ejemplo 47. Una definici´ on recursiva de: n X

ak

k=0 0 X

ak

= a0

k=0 n+1 X

ak = (

k=0

n X

ak ) + an+1

k=0

Definici´ on 1. Los n´ umeros de Fibonnacci, f0 , f1 , . . . , se definen a partir de las ecuaciones f0 = 0, f1 = 1 y fn = fn−1 + fn−2 para n = 2, 3, 4, . . . Ejemplo 48. Los n´ umeros de fibonacci, f0,f1,f2 son definidos para n=2,3,4 son: f2=f1+f0=1+0=1

E.I.S.C

T´ ecnicas de demostraci´ on

f3=f2+f1=1+1=2, f4=f3+f2=2+1=3, f5=f4+f3=3+2=5, f6=f5+f4=5+3=8, funci´ on fibonacci (n:entero positivo) if n=0 then fibonacci(0):=0 else if n=1 then fibonnaci(1):=1 else fibonacci(n):=fibonacci(n-1)+ fibonacci (n-2) end fibonacci Ejemplo 49. Un algoritmo recursivo para calcular el m´ aximo com´ un divisor de dos enteros no negativos a y b, donde a < b. procedure mcd(a,b) si a=0 entonces mcd(a,b)=b else mcd(a,b):=mcd(b mod a,a) end mcd Ejemplo 50. (Funci´ on de Ackermann)  2n   0 A(m, n) =   2 A(m − 1, A(m, n − 1))

si si si si

m=0 m≥1 y n=0 m≥1 y n=1 m≥1 y n≥2

E.I.S.C

T´ ecnicas de demostraci´ on

1. Obtener A(1, 0), como m = 1 y n = 0 entonces A(1, 0) = 0 se aplica el segundo criterio de la funci´ on. 2. Obtener A(1, 1), como m = 1 y n = 1 entonces A(1, 1) = 2 se aplica el tercer criterio de la funci´ on. 3. Obtener A(0, 1), como m = 0 y n = 1 entonces A(0, 1) = 2(1) = 2 se aplica el primer criterio de la funci´ on. 4. Obtener A(2, 2). Aplicando el cuarto criterio nos queda otra recursividad A(1, A(2, 1)), ahora A(2, 1) = 2 por tercer criterio, por tanto tenemos que calcular A(1, 2). Por el cuarto criterio A(0, A(1, 1)), donde A(1, 1) = 2 reemplazando nos queda A(0, 2) por el primer criterio A(0, 2) = 4 por tanto A(2, 2) = 4 5. Obtener A(2, 3). Usamos el cuarto criterio A(2, 3) = A(1, A(2, 2)) ahora A(2, 2) = 4 es decir que tenemos que calcular A(1, 4) por que A(2, 3) = A(1, 4) lo podemos hacer de dos formas: a) Aplicando la siguiente f´ ormula A(1, n) = n 2 si n ≥ 1, entonces A(1, 4) = 24 = 16 por tanto A(2, 3) = 16 b) Ahora sin usar f´ ormulas, s´ olo con recursividad. A(1, 4) aplicamos el cuarto criterio A(1, 4) = A(0, A(1, 3)) ahora calculamos A(1, 3) = A(0, A(1, 2))

E.I.S.C

T´ ecnicas de demostraci´ on

ahora calculamos A(1, 2) = A(0, A(1, 1)) como A(1, 1) = 2 aplicando el tercer criterio. A(1, 2) = A(0, 2) = 4 por el primer criterio, entonces A(1, 2) = 4 ahora reemplazamos A(1, 3) = A(0, A(1, 2)) = A(0, 4) = 8 aplicando el primer criterio, entonces A(1, 3) = 8 retomamos A(1, 4) = A(0, A(1, 3)) = A(0, 8) = 16 por el primer criterio. POR TANTO A(2, 3) = 16 5.1 Conjuntos y estructuras bien definidas. Las definiciones recursivas de un conjunto tienen dos partes: 1. Paso base. Colecci´ on inicial de elementos. 2. Paso recursivo. Reglas para la formaci´ on de nuevos elementos del conjunto a partir de los que ya se conocen.

Definici´ on 2. El conjunto Σ∗ de cadenas sobre el alfabeto Σ se puede definir recursivamente por: Paso base. λ ∈ Σ∗ , donde λ es la cadena vac´ıa, aquella que no tiene s´ımbolos. Paso recursivo. Si w ∈ Σ∗ y x ∈ Σ∗ , entonces wx ∈ Σ∗

E.I.S.C

T´ ecnicas de demostraci´ on

Ejemplo 51. Sea Σ = {0, 1} las cadenas del conjunto Σ∗ , el conjunto de todas las cadenas de bits. Paso base. lo constituye la cadena vac´ıa λ Paso recursivo. 0 y 1 cadenas que se forman recursivamente por primera vez, 00, 01, 10 y 11 cadenas que se forman al aplicar el paso recursivo por segunda vez. Definici´ on 3. Dos cadenas se pueden combinar mediante la operaci´ on de la concatenaci´ on. Sea ∗ Σ un conjunto de s´ımbolos y Σ el conjunto de las cadenas formadas a partir de s´ımbolos de Σ. Podemos definir recursivamente la concatenaci´ on de dos cadenas, denotada con el s´ımbolo · como sigue: Paso base. Si w ∈ Σ∗ , entonces w · λ = w, donde λ es la cadena vac´ıa. Paso recursivo. Si w1 ∈ Σ∗ , w2 ∈ Σ∗ y x ∈ Σ, entonces w1 · (w2 x) = (w1 · w2 )x Ejemplo 52. F´ ormulas bien formadas en l´ ogica proposicional. Podemos definir el onjunto de f´ ormulas bien formadas con variables proposicionales y operadores l´ ogicos, adem´ as de los valores V y F. Paso base.{V, F} y p, donde p es una variable proposicional. Paso recursivo. Si E y F son f´ ormulas bien formadas, entonces (v E), (E ∧ F ), (E ∨ F ), (E → F ), (E ↔ F ) son f´ ormulas bien formadas.