Logica Proposicional, teoremas y demostraciones

1 o o u u u u a L´gica Proposicional, Teoremas y Demostraciones Manuel Maia 19 de marzo de 2012 Proposiciones Una proposici´n es una oraci´n declarativa o una expresi´n matem´tica que es verdadera o es falsa, pero no ambas. De esta manera, una proposici´n tiene un valor de verdad, que puede ser V, si es verdadera o puede ser F, si es falsa. Consideraremos exclusivamente proposiciones matem´ticas. Algunos ejemplos de proposiciones verdaderas son: • “4 es un n´mero entero par”. • “15 = 15”. • “La soluci´n de 2x – 3 = 1 es 2”. • “18 es m´ltiplo de 3”. Algunos ejemplos de proposiciones falsas son: • “144 es un n´mero entero impar”. • “2 = 17”. • “La soluci´n de 2x – 3 = 1 es 0”. • “16 es m´ltiplo de 5”. Algunos ejemplos de expresiones que no son proposiciones son: • “ 73”. • “2x – 1 = 3”. • “¿Cu´l es la soluci´n de 2x – 3 = 1?”. 1

2 u u u o u u u u o a i o a o o u u • “x es m´ltiplo de 3”. Generalmente, para referirnos a proposiciones espec´i?cas se usan letras may´sculas. Por ejemplo, P : 25 es un n´mero entero par. Q : 3 + 4 = 7. R : 2x + 3 es una ecuaci´n. Las proposiciones pueden contener variables. Por ejemplo, sea x un n´mero entero y consideremos P : 2x + 1 es un entero impar. Esta es una proposici´n que es verdadera no importa que n´mero entero sea la variable x. Entonces podemos denotarla por P (x) : 2x + 1 es un entero impar. Hay oraciones o expresiones matem´ticas que contienen variables y no son proposiciones. Por ejemplo, Q(x) : El n´mero entero x es m´ltiplo de 3. S´lo ser´ una proposici´n cuando le otorguemos un valor a x (y as´ podremos determinar si es verdadera o falsa). Por ejemplo, Q(13) es falsa y Q(21) es verdadera. Una expresi´n como Q(x), cuyo valor de verdad depende de una o m´s variables, es lo que se llama una expresi´n abierta. Conectivos L´gicos Podemos usar la palabra “y” para conectar dos proposiciones y crear una nueva proposici´n. Por ejemplo, podemos conectar las proposiciones P : El n´mero 4 es un entero par. Q : El n´mero 5 es un entero impar. para formar la nueva proposici´n 2

u u e i, e o u u i, R : El n´mero 4 es un entero par y el n´mero 5 es un entero impar. La proposici´n R a?rma que P y Q son ambas verdaderas. Como P y Q, en efecto son verdaderas, la proposici´n R tambi´n lo es. As´ dadas dos proposiciones cualesquiera P y Q, podemos combinarlas para formar una nueva proposici´n “P y Q”. Se usa el s´imbolo ? para indicar la palabra “y”. De esta manera, P ? Q signi?ca “P y Q”. La proposici´n P ? Q es verdadera si ambas proposiciones P y Q son verdaderas. En cualquier otro caso, es falsa. Esto se resume en la siguiente tabla de verdad. P V V F F Q V F V F P ? Q V F F F En cada ?la aparece una de las cuatro posibles combinaciones de valores de verdad para P y Q. Por ejemplo, si P es falsa y Q es verdadera, entonces P ? Q es falsa. Tambi´n podemos conectar dos proposiciones usando la palabra “o” para crear una nueva proposici´n. Dadas dos proposiciones cualesquiera P y Q, la a?rmaci´n “P o Q” signi?ca que una o ambas proposiciones son verdaderas. Esto di?ere del signi?cado usual que tiene “o” en el lenguaje cotidiano, donde signi?ca una alternativa o la otra, de manera excluyente, cuando hay dos alternativas. De esta manera, por ejemplo, la proposici´n “El n´mero entero 4 es par o el n´mero entero 3 es par” es verdadera. Se usa el s´imbolo ? para indicar la palabra “o”. As´ P ? Q signi?ca “P o Q”. La tabla de verdad para P ? Q es la siguiente. P V V F F Q V F V F P ? Q V V V F Otra manera de obtener nuevas proposiciones a partir de otras es usando la palabra “no”. Dada una proposici´n cualquiera P, podemos formar una nueva proposici´n “no es verdadero que P ”. Por ejemplo, si consideramos la proposici´n (verdadera) 3

u u i, 3 o u u u o e e a ´ i, “El n´mero entero 3 es impar”, podemos formar la nueva proposici´n “No es verdadero que el n´mero entero 3 es impar”, la cual evidentemente es falsa. Se usa el s´imbolo ¬ para indicar la frase “no es verdadero que”. As´ ¬P signi?ca “no es verdadero que P ”. La tabla de verdad para ¬P es la siguiente. P V F ¬P F V Otras maneras de expresar la negaci´n de “El n´mero entero 3 es impar”, son: • “Es falso que el n´mero entero 3 es impar”, • “El n´mero entero 3 no es impar”. Proposiciones Condicionales Otra manera de conectar dos proposiciones es mediante el uso de condicionales. Dadas dos proposiciones cualesquiera P y Q, podemos formar la nueva proposici´n “Si P, entonces Q.” Esta proposici´n se escribe de manera simb´lica como P ? Q, la cual tambi´n se lee “P implica Q”. Que la proposici´n P ? Q es verdadera signi?ca que si P es verdadera entonces Q tambi´n debe ser verdadera (P verdadera obliga a que Q sea verdadera). Una proposici´n de la forma P ? Q se conoce como proposici´n condicional (Q ser´ verdadera bajo la condici´n de que P sea verdadera). El signi?cado de P ? Q nos dice que la unica manera en que la proposici´n P ? Q es falsa es cuando P es verdadera y Q falsa. As´ la tabla de verdad para P ? Q es la siguiente. P V V F F Q V F V F 4 P ? Q V F V V

4 ´ a u u u u u u u u u u u u a e u Las expresiones m´s comunes que signi?can P ? Q son las siguientes: • Si P, entonces Q. • Q, si P. • Q, siempre que P. • P es una condici´n su?ciente para Q. • Q es una condici´n necesaria para P. • P, solo si Q. Por ejemplo, la proposici´n (verdadera) “Si el n´mero entero a es par, entonces es el n´mero entero a es m´ltiplo de 2”, se puede escribir como cualquiera de las siguientes expresiones: • “El n´mero entero a es m´ltiplo de 2, si el n´mero entero a es par ”. • “El n´mero entero a es m´ltiplo de 2, siempre que el n´mero entero a sea par ”. • “El n´mero entero a es par, solo si el n´mero entero a es m´ltiplo de 2”. La rec´iproca de una proposici´n condicional P ? Q es la proposici´n Q ? P. La contrarrec´iproca (o contrapositiva) de P ? Q es la proposici´n ¬Q ? ¬P. Proposiciones Bicondicionales Dadas dos proposiciones cualesquiera P y Q, podemos considerar tanto P ? Q como su rec´iproca Q ? P. En primer lugar, P ? Q no es lo mismo que Q ? P, pues tienen distinto signi?cado, y en consecuencia, pueden tener valores de verdad diferentes. Consideremos ahora la proposici´n m´s compleja (note el uso de los par´ntesis) (P ? Q) ? (Q ? P ) . Esta a?rma que tanto P ? Q como Q ? P son verdaderas. Se usa el s´imbolo ? para expresar este signi?cado. Ahora, Q ? P se lee “P si Q” y P ? Q se lee “P, solo si Q”. En consecuencia, leemos P ? Q como “P, si y solo si, Q”. Una proposici´n de la forma P ? Q se conoce como proposici´n bicondicional. Por ejemplo, sea a un n´mero entero ?jo y consideremos: P : a es par, 5

u u u i, u o a P Q 5 o o l´ l´ o P Q : a es m´ltiplo de 2. Entonces: P ? Q : Si a es par, entonces a es m´ltiplo de 2, Q ? P : Si a es m´ltiplo de 2, entonces a es par. As´ tenemos la proposici´n (que es verdadera) P ? Q : a es par, si y solo si, a es m´ltiplo de 2. El conocimiento que tenemos de las tablas para ? y ?, y un an´lisis cuidadoso de la siguiente tabla (n´tese que las columnas intermedias corresponden a las proposiciones m´s simples que conforman (P ? Q) ? (Q ? P )), P ? Q Q ? P (P ? Q) ? (Q ? P ) V V F F V F V F V F V V V V F V V F F V revela que la tabla de verdad para P ? Q es la siguiente. P V V F F Q V F V F P ? Q V F F V Equivalencia L´gica Dos proposiciones l´gicamente equivalentes son dos proposiciones cuyos valores de verdad coinciden inea por inea en una tabla de verdad, y de esta manera tienen el mismo signi?cado. Por ejemplo, las proposiciones P ? Q y (P ? Q) ? (¬P ? ¬Q) son l´gicamente equivalentes, como podemos ver en la siguiente tabla de verdad. Q ¬P ¬Q (P ? Q) (¬P ? ¬Q) P ? Q (P ? Q) ? (¬P ? ¬Q) V V F F V F V F F F V V F V F V V F F F F F F V V F F V V F F V 6

l´ l´ ´ o a o o 6 o o o u e a o a u u u u ´ Esto se evidencia en la coincidencia inea por inea de las dos ultimas columnas. La equiva- lencia l´gica de P ? Q y (P ? Q) ? (¬P ? ¬Q) la expresamos de la siguiente manera (P ? Q) = (P ? Q) ? (¬P ? ¬Q) Un ejemplo importante (como veremos m´s adelante) de equivalencia l´gica es el si- guiente. (P ? Q) = (¬Q) ? (¬P ). Que son l´gicamente equivalentes, podemos verlo en la tabla siguiente. P Q ¬P ¬Q P ? Q (¬Q) ? (¬P ) V V F F V F V F F F V V F V F V V F V V V F V V Otras dos equivalencias l´gicas importantes son las conocidas como Leyes de Morgan: 1. ¬(P ? Q) = (¬P ) ? (¬Q). 2. ¬(P ? Q) = (¬P ) ? (¬Q). Veri?que estas dos equivalencias como un ejercicio. De?niciones, Teoremas, Proposiciones y Demostra- ciones Una de?nici´n es una explicaci´n exacta y sin ambig¨edad del signi?cado de un t´rmino o frase matem´tica. Daremos, como ejemplo, algunas de?niciones que nos ser´n de utilidad en esta secci´n. No podemos de?nir todo, de manera que asumimos que el lector est´ de alguna manera familiarizado con los n´meros naturales, 1, 2, 3, 4, 5 . . . , los n´meros enteros, . . . , -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5 . . . , los n´meros racionales, los n´meros reales, las operaciones de suma y producto con ellos, y algo de algebra elemental. 7

o u o u u a o e u ia u u o o u o u o u ´ u De?nici´n: Un n´mero entero n es par si existe un entero k, tal que n = 2k. Por ejemplo, 4, -28, 0 son pares, pues 4 = 2 · 2 -28 = 2 · (-14) 0 = 2 · 0 (k = 2), (k = -14), (k = 0). De?nici´n: Un n´mero entero n es impar si existe un entero k, tal que n = 2k + 1. Por ejemplo, 3, -15, 1 son impares, pues 3 = 2 · 1+1 -15 = 2 · (-8) + 1 1 = 2 · 0+1 (k = 1), (k = -8), (k = 0). Claramente, un n´mero entero cualquiera es par o es impar, pero no ambos a la vez. Hay que hacer una observaci´n. Las de?niciones usualmente se expresan como proposi- ciones condicionales, aunque lo m´s adecuado ser´ia expresarlas como proposiciones bicondi- cionales. Por ejemplo, la de?nici´n t´cnica y precisa de n´mero entero par deber´ ser “Un n´mero entero n es par si y solo si existe un entero k, tal que n = 2k,” pero se conviene en escribirla en forma de proposici´n condicional. Es decir, a´n cuando una de?nici´n est´ escrita en forma condicional, se interpreta como bicondicional. Esto es una convenci´n. De?nici´n: Dados dos enteros a y b, si b = ac, para alg´n entero c, decimos que a divide a b, y escribimos a | b. En esta situaci´n, a es un divisor de b, y b es m´ltiplo de a. Por ejemplo, 4 divide a 28 pues 28 = 4 · 7. Escribimos esto como 4 | 28. Sin embargo, 5 no divide a 12, pues no existe un entero c tal que 12 = 5c. Escribimos esto como 5 12, que puede leerse como “5 no divide a 12”. De?nici´n: Decimos que un n´mero natural p es primo si sus unicos divisores positivos son 1 y p. Los primeros diez n´meros primos son: 2, 3, 5, 7, 11, 13, 17, 19, 23 y 29. 8

o o . o . o o o n u a a Un teorema es una proposici´n matem´tica que es verdadera, y puede ser (y ha sido) veri?cada como verdadera. Los teoremas usualmente son proposiciones condicionales del tipo P ? Q (esto es, “si P , entonces Q”), aunque el enunciado del teorema o proposici´n a veces oculta este hecho. N´tese el enunciado de la siguiente proposici´n. Proposici´n Las soluciones de la ecuaci´n ax2 + bx + c son x = v -b ± b2 – 4ac 2a Con este enunciado, la proposici´n no parece ser una proposici´n condicional, sin embargo podemos expresar esta proposici´n como una proposici´n condicional escribiendo: Proposici´n Si x es una soluci´n de la ecuaci´n ax2 + bx + c, entonces x = v -b ± b2 – 4ac 2a Cuando un teorema se expresa como una proposici´n condicional P ? Q, la proposici´n P se llama hip´tesis y la proposici´n Q se llama tesis. Por ejemplo, en la proposici´n anterior la hip´tesis es “x es una soluci´n de la ecuaci´n ax2 + bx + c” y la tesis es “x = v -b ± b2 – 4ac 2a ”. Cabe se˜alar que no todo teorema es una proposici´n condicional. Algunos tienen la forma bicondicional P ? Q (que puede expresarse como dos proposiciones condicionales). Otros teoremas son simplemente proposiciones P. Por ejemplo, Teorema Existe una in?nidad de n´meros primos. Hay teoremas que tienen otras formas menos comunes, por ejemplo, las tres siguientes: (P ? Q) ? R, P ? (Q ? R), P ? (Q ? R). Hay varias palabras que signi?can esencial- mente lo mismo que la palabra “teorema”. En general “teorema” se reserva para proposi- ciones signi?cativas o importantes (por ejemplo, el Teorema de Pit´goras). Una proposici´n matem´tica verdadera, pero no signi?cativa, se llama simplemente proposici´n, un lema es una proposici´n que ayuda a demostrar un teorema. Un corolario es una proposici´n relativamente sencilla que es consecuencia inmediata de un teorema o proposici´n m´s rele- vante. 9

o o o o o a o ´ o a . . i, o o o o u o Una demostraci´n de un teorema es una veri?caci´n escrita que muestra que el teorema es verdadero. Informalmente, desde el punto de vista de la l´gica, una demostraci´n de un teorema es un argumento l´gico que establece la verdad del teorema. Consiste de una sucesi´n de a?rmaciones (1), (2), . . . , (n), tales que cada a?rmaci´n tiene una o m´s razones que justi?can su validez, que pueden ser hip´tesis, de?niciones, a?rmaciones anteriores en la misma demostraci´n o proposiciones matem´ticas ya demostradas y adem´s la ultima a?rmaci´n, (n), es la tesis que queremos demostrar. 6.1 Demostraci´n Directa La forma m´s natural de demostraci´n de un teorema o proposici´n que es una proposici´n condicional es la demostraci´n directa. Analizando la tabla de verdad para P ? Q, vemos que si queremos demostrar el teorema o proposici´n P ? Q, es su?ciente demostrar que Q es verdadera siempre que P lo sea (pues P ? Q es verdadera cuando P es falsa). P V V F F Q V F V F P ? Q V F V V As´ en una demostraci´n directa de P ? Q asumimos que la hip´tesis, P, es verdadera y demostramos usando argumentos l´gicos que la tesis, Q, es verdadera. Una demostraci´n directa sigue el siguiente esquema. Esquema para una demostraci´n directa Proposici´n Si P, entonces Q. Demostraci´n: Supongamos P. . . En consecuencia Q. Los puntos suspensivos . indican la sucesi´n de razonamientos l´gicos que inician con P verdadero y ?nalizan con Q verdadero. El inicio de la demostraci´n se indica con De- mostraci´n: y se ?naliza con el s´imbolo o alg´n otro parecido. Como ejemplo, demostraremos que la expresi´n abierta 10

6.2 u u e a u u o u u o “Si x es un n´mero entero impar, entonces x2 es un n´mero entero impar” es en realidad una proposici´n verdadera, esto es, no importa qu´ entero sea x, siempre ser´ una proposici´n verdadera. Proposici´n Si x es un n´mero entero impar, entonces x2 es un n´mero entero impar. Demostraci´n: Supongamos que x es impar. Entonces, por de?nici´n de n´mero entero impar, existe un n´mero entero a, tal que x = 2a + 1. Ahora x2 = (2a + 1)2 = (2a + 1) · (2a + 1) = 4a2 + 4a + 1 = 2(2a2 + 2a) + 1 = 2k + 1 (k = 2a2 + 2a). En consecuencia, x2 es impar. Demostraci´n por Contrarrec´iproca La demostraci´n por contrarrec´iproca se usa para demostrar, al igual que la demostraci´n directa, teoremas y proposiciones que tienen la forma condicional P ? Q. Esta forma de demostraci´n se basa en el hecho de que P ? Q es l´gicamente equivalente a (¬Q) ? (¬P ), como muestra la siguiente tabla. P Q ¬P ¬Q P ? Q (¬Q) ? (¬P ) V V F F V F V F F F V V F V F V V F V V V F V V De esta manera, si queremos demostrar P ? Q por contrarrec´iproca, basta demostrar (¬Q) ? (¬P ) usando una demostraci´n directa. Esto es, asumimos que ¬Q es verdadera y demostramos que ¬P es verdadera. Una demostraci´n por contrarrec´iproca sigue el siguiente esquema. 11

. e o u i, i, u Esquema para una demostraci´n por contrarrec´iproca Proposici´n Si P, entonces Q. Demostraci´n: (por contrarrec´iproca) Supongamos ¬Q. . . En consecuencia ¬P. Como ejemplo, demostraremos una misma proposici´n usando los dos m´todos vistos hasta ahora. Proposici´n Si 3x – 1 es par, entonces x es impar. Demostraci´n: (directa) Supongamos que 3x – 1 es par. Entonces, por de?nici´n, existe un n´mero entero a, tal que 3x – 1 = 2a. As´ restando 2x a ambos lados, obtenemos 3x – 1 – 2x = 2a – 2x x – 1 = 2(a – x) x = 2(a – x) + 1 x = 2k + 1 (k = a – x). En consecuencia, x es impar. Proposici´n Si 3x – 1 es par, entonces x es impar. Demostraci´n: (por contrarrec´iproca) Supongamos que x no es impar. Entonces x es par. As´ existe un n´mero entero a, tal que x = 2a. Ahora, 3x – 1 = 3(2a) – 1 = 6a – 1 – 1 + 1 = 6a – 2 + 1 = 2(3a – 1) + 1 = 2k + 1 (k = 3a – 1). 12

6.3 a a o a i i, u o o En consecuencia, 3x – 1 es impar. Vale la pena mencionar que en ocasiones una demostraci´n por contrarrec´iproco es mucho m´s f´cil que una demostraci´n directa. Por ejemplo, consideremos la expresi´n abierta (que en realidad es una proposici´n) “Si x2 es par, entonces x es par”. Una demostraci´n directa no es f´cil, sin embargo, una demostraci´n por contrarrec´iproca s´ lo es: Proposici´n Si x2 es par, entonces x es par. Demostraci´n: (por contrarrec´iproca) Supongamos que x no es par. Entonces x es impar. As´ existe un n´mero entero a, tal que x = 2a + 1. Ahora, x2 = (2a + 1)2 = (2a + 1) · (2a + 1) = 4a2 + 4a + 1 = 2(2a2 + 2a) + 1 = 2k + 1 (k = 2a2 + 2a). Es decir, x2 es impar. En consecuencia x es par. Habr´ notado, de hecho, que es la misma demostraci´n directa de “si x es impar, entonces x2 es impar ”. Esto es porque “Si x2 es par, entonces x es par” es l´gicamente equivalente a “si x es impar, entonces x2 es impar”. Demostraci´n por Contradicci´n Supongamos que queremos demostrar que una proposici´n P es verdadera. Una demostraci´n por contradicci´n comienza suponiendo que P es falsa, esto es, que ¬P es verdadera y ?naliza deduciendo que para una cierta proposici´n C, se tiene que C ? ¬C es verdadera. Esto es una contradicci´n, pues una proposici´n y su negaci´n no pueden tener el mismo valor de verdad (recordemos la tabla de verdad para ¬). Esto es equivalente a demostrar que P es verdadera, como muestra la siguiente tabla de verdad, 13

. i, i, e e o o e u u u u u u v v u o a o P V C V ¬P F ¬C F C ? ¬C F (¬P ) ? (C ? ¬C) V V F F F V F F V V V F V F F F V F F , donde se ve que P = (¬P ) ? (C ? ¬C). As´ para demostrar P por contradicci´n, basta demostrar (¬P ) ? (C ? ¬C) mediante una demostraci´n directa. As´ una demostraci´n por contradicci´n sigue el siguiente esquema. Esquema para una demostraci´n por contradicci´n de una proposici´n Proposici´n P. Demostraci´n: (Por contradicci´n) Supongamos ¬P. . . En consecuencia C ? ¬C. Algo que no es claro en este m´todo es qu´ proposici´n es la proposici´n C. En cualquier caso, se inicia la demostraci´n asumiendo que ¬P es verdadera y deduciendo l´gicamente nuevas proposiciones se llegar´ a alguna proposici´n C y su negaci´n, ¬C. Daremos un ejemplo, pero antes necesitamos recordar qu´ es un n´mero racional. a Un n´mero racional es un n´mero real de la forma , donde a y b son n´meros enteros b y b = 0. Un n´mero irracional es un n´mero real que no es racional. v Proposici´n El n´mero 2 es irracional. Demostraci´n: (por contradicci´n) Supongamos que 2 no es irracional. Entonces 2 es racional y por tanto existen enteros a y b (b = 0), tales que v a 2= . b (1) a Supongamos que la fracci´n est´ completamente simpli?cada. Esto es, a y b no tienen b factores comunes. En particular, esto signi?ca que a y b no son ambos pares. Ahora, elevando ambos lados de la ecuaci´n (1) al cuadrado, obtenemos 2= a2 b2 , (2) 14

. o i y en consecuencia a2 = 2b2 . (3) Esto nos dice que a2 es par. Pero hemos demostrado anteriormente que si a2 es par, entonces a es par. Como sabemos que a y b no son ambos pares, se concluye que b es impar. Ahora, como a es par, existe un entero c tal que a = 2c. Sustituyendo en la ecuaci´n (3), obtenemos (2c)2 = 2b2 , y as´ 4c2 = 2b2 . Por lo tanto b2 = 2c2 . En consecuencia b2 es par, y por lo tanto, b es par. De esta manera, b es impar y b es par (una contradicci´n). Supongamos que queremos demostrar una proposici´n condicional P ? Q usando una demostraci´n por contradicci´n. Comenzamos suponiendo que P ? Q es falsa. Esto ocurre precisamente cuando Q es falsa y P verdadera (vea la tabla de verdad para P ? Q). De esta manera, comenzamos suponiendo que Q es falsa y P es verdadera, y ?nalizamos deduciendo que para cierta proposici´n C se tiene que C ? ¬C es verdadera, esto es, llegando a una contradicci´n. En consecuencia, por lo visto antes, P ? Q es verdadera. Esquema para una demostraci´n por contradicci´n de una proposici´n condicional Proposici´n P ? Q. Demostraci´n: (Por contradicci´n) Supongamos P y ¬Q. . . En consecuencia C ? ¬C. Como ejemplo, demostraremos una proposici´n condicional ya demostrada, pero esta vez por contradicci´n. Proposici´n Si x2 es par, entonces x es par. Demostraci´n: (por contradicci´n) Supongamos que x2 es par y que x no es par. Esto es, x es impar, y por lo tanto existe un entero a, tal que x = 2a + 1. 15

6.4 o Ahora, x2 = (2a + 1)2 = (2a + 1) · (2a + 1) = 4a2 + 4a + 1 = 2(2a2 + 2a) + 1 = 2k + 1 (k = 2a2 + 2a). En consecuencia, x2 es impar. Hemos llegado a una contradicci´n, x2 es par y x2 es impar. Demostraci´n de Bicondicionales Sabemos que una proposici´n bicondicional P si y solo si Q es l´gicamente equivalente a la proposici´n (si P, entonces Q) y (si Q, entonces P ). De esta manera, para demostrar una proposici´n de la forma “P si y solo si Q” debemos demostrar dos proposiciones condicionales: la proposici´n “si P, entonces Q” y la proposici´n “si Q, entonces P ”. Una demostraci´n de una proposici´n bicondicional tiene el siguiente esquema. Esquema para una demostraci´n de una proposici´n bicondicional Proposici´n P si y solo si Q. Demostraci´n: (Demuestre P ? Q usando una demostraci´n directa, por contrarrec´iproco o por contradicci´n). (Demuestre Q ? P usando una demostraci´n directa, por contrarrec´iproco o por contradicci´n). 16

o i, o Veamos un ejemplo. Proposici´n El entero x es impar si y solo si x2 es impar. Demostraci´n: Primero demostraremos que si x es impar, entonces x2 es impar. Supongamos que x es impar. Entonces, por de?nici´n, existe un entero a, tal que x = 2a + 1. Ahora, x2 = (2a + 1)2 = (2a + 1) · (2a + 1) = 4a2 + 4a + 1 = 2(2a2 + 2a) + 1. En consecuencia, x2 es impar. Rec´iprocamente, supongamos que x2 es impar y veamos que x es impar. Para demostrar esto usaremos una demostraci´n por contrarrec´iproco. Supongamos que x no es impar. Entonces x es par, y por lo tanto existe un entero a tal que x = 2a. As´ x2 = (2a)2 = 4a2 = 2(2a2 ). En consecuencia, x2 es par. Esto demuestra que si x2 es impar, entonces x es impar 6.5 Otras Demostraciones Hay otros tipos de demostraciones menos comunes. Algunas son las siguientes (s´lo las describiremos). Demostraci´n por Casos. Supongamos que queremos demostrar P ? Q ? R. Como (P ? Q ? R) = (P ? R) ? (Q ? R), (verif´iquelo) debemos considerar y demostrar dos casos, P ? R y Q ? R. 17

6.6 ´ a u u u u u u o ´ ia o ´ Demostraci´n de Proposiciones “y”. Supongamos que queremos demostrar la proposici´n P ? (Q ? R). Como (P ? (Q ? R)) = (P ? Q) ? (P ? R), (verif´iquelo) debemos demostrar P ? Q y P ? R. Demostraci´n de Proposiciones “o”. Para demostrar la proposici´n P ? (Q ? R) pro- cedemos por contradicci´n. Esto es, suponemos P y ¬(Q ? R) y debemos llegar a una contradicci´n. Es util recordar que ¬(Q ? R) = ¬Q ? ¬R (leyes de Morgan). Conjeturas y Contraejemplos Hay tres grandes categor´ias de proposiciones matem´ticas: 1. Teoremas y Proposiciones. Estas son proposiciones verdaderas. Por ejemplo, • El Teorema de Pit´goras. • El cuadrado de un n´mero impar es impar. 2. Conjeturas. Estas son proposiciones cuya verdad o falsedad a´n no ha sido de- mostrada, pero hay indicios de que son verdaderas. Por ejemplo, • Cualquier n´mero entero par mayor que 2 es la suma de dos n´meros primos (Conjetura de Goldbach). • Hay una in?nidad de n´meros primos de la forma 2n – 1, donde n es un entero positivo. 3. Proposiciones Falsas. Por ejemplo, • Todos los n´meros primos son impares. • La ecuaci´n ax2 + bx + c = 0 tiene tres soluciones. La ultima categor´ nos lleva a la pregunta ¿c´mo demostrar que una proposici´n es falsa? Discutiremos brevemente algunos casos. Supongamos que queremos demostrar que una proposici´n P es falsa. La manera de hacerlo es demostrando que ¬P es verdadera, y esto lo podemos hacer, en teor´ia, mediante una demostraci´n directa, por contrarrec´iproco o por contradicci´n. Ahora supongamos que queremos demostrar que una proposici´n condicional P ? Q es falsa. Como P ? Q es falsa unicamente cuando P es verdadera y Q falsa (vea la tabla de 18

u u ia a i, u verdad para P ? Q), debemos hallar un ejemplo en el cual P es verdadera y Q falsa. La existencia de tal ejemplo demuestra que P ? Q es falsa. Un ejemplo de este tipo es lo que se llama un contraejemplo. Por ejemplo, consideremos la siguiente conjetura (pues no sabemos si es verdadera o es falsa). Conjetura Si n es un entero, entonces n2 – n + 11 es un n´mero primo. Hallemos el valor de n2 – n + 11 para algunos valores de n : n -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 n2 – n + 1 23 17 13 11 11 13 17 23 31 41 53 67 83 101 La conjetura parece ser verdadera, pues todos los n´meros obtenidos en cada caso son pri- mos. Esto no basta para concluir que la conjetura es verdadera. Habr´ que hacer una demostraci´n. Antes de intentar una demostraci´n, probemos un valor m´s para n. Observe que 112 – 11 + 11 = 112 no es primo. En consecuencia, la conjetura es falsa, pues n = 11 es un contraejemplo. As´ podemos escribir la siguiente demostraci´n de que es falsa: Demostraci´n (de que la conjetura es falsa): La proposici´n Si n es un entero, entonces n2 – n + 11 es un n´mero primo es falsa. Para un contraejemplo, tomemos n = 11, y el entero 112 – 11 + 11 = 121 = 11 · 11 no es primo. 19

7 o u u 4 9 25 . . . n2 . . . . . l´ u e e u ´ e u o Inducci´n Matem´tica Considere la siguiente proposici´n. Conjetura La suma de los n primeros n´meros naturales impares es igual a n2 . Esta conjetura dice lo siguiente: n suma de los n primeros n´meros naturales impares es igual a n2 1 1= 2 1+3= 3 1+3+5= 4 1+3+5+7= 5 1+3+5+7+9= 1 16 . . . . . . n 1 + 3 + 5 + 7 + · · · + (2n – 1) = . . . . . . Observe que en las 5 primeras ineas de la tabla, la suma de n primeros n´meros naturales impares es efectivamente igual a n2 . Observe tambi´n que el n-´simo n´mero natural impar (el ultimo en cada suma) es 2n – 1. Esta tabla lleva a la siguiente pregunta, ¿es verdad que para cada n, se tiene que 1 + 3 + 5 + 7 + · · · + (2n – 1) = n2 ? Es decir, ¿la conjetura es verdadera? Podemos plantear esto en t´rminos de proposiciones como sigue. Para cada n´mero natural n tenemos una proposici´n P (n) como sigue: P (1) : 1 = 12 , P (2) : 1 + 3 = 22 , P (3) : 1 + 3 + 5 = 32 , P (4) : 1 + 3 + 5 + 7 = 42 , . . P (n) : 1 + 3 + 5 + 7 + · · · + (2n – 1) = n2 , . . ¿Son verdaderas todas estas proposiciones?, ¿c´mo demostrar, por ejemplo, que P (723452137234875623895647802020218237584298376342375629484474764157234968721450) 20

e o o e o o a o o o a i, o o u o i, es verdadera? La t´cnica de demostraci´n por Inducci´n Matem´tica (o simplemente Inducci´n) se usa cuando tenemos una colecci´n, P (1), P (2), P (3), . . . , P (n), . . . de proposiciones y queremos demostrar que todas son verdaderas. La validez de este m´todo se demostrar´ despu´s. Por lo pronto s´lo presentaremos el esquema para una demostraci´n por inducci´n y, us´ndolo demostraremos que la conjetura es verdadera. Esquema para una demostraci´n por Inducci´n Matem´tica Proposici´n Las proposiciones P (1), P (2), P (3), . . . , P (n), . . . son todas verdaderas. Demostraci´n: (por Inducci´n) (1) Se demuestra que P (1) es verdadera. (2) Dado k = 1, se demuestra que P (k) ? P (k + 1) es verdadera. Se sigue por inducci´n matem´tica que cada P (n) es verdadera. El primer paso, (1), se llama paso inicial. Generalmente, P (1) es muy f´cil de demostrar. El paso (2) se llama paso inductivo. Aqu´ generalmente se hace una demostraci´n directa de P (k) ? P (k + 1). La hip´tesis de que P (k) es verdadera se llama hip´tesis inductiva. Veamos que la conjetura 1 + 3 + 5 + 7 + · · · + (2n – 1) = n2 , para n ? N, es verdadera. Proposici´n Si n es un n´mero natural, entonces 1 + 3 + 5 + 7 + · · · + (2n – 1) = n2 . Demostraci´n: (por Inducci´n) Aqu´ P (n) : 1 + 3 + 5 + 7 + · · · + (2n – 1) = n2 . 21

i, o u u (1) Si n = 1, la proposici´n es 2 · 1 – 1 = 12 , que obviamente es verdadera. (2) Debemos demostrar que P (k) ? P (k + 1), donde P (k) : 1 + 3 + 5 + 7 + · · · + (2k – 1) = k2 . y P (k + 1) : 1 + 3 + 5 + 7 + · · · + (2(k + 1) – 1) = (k + 1)2 . Usaremos una demostraci´n directa. Supongamos que P (k) : 1 + 3 + 5 + 7 + · · · + (2k – 1) = k2 es verdadera. Entonces 1 + 3 + 5 + 7 + · · · + (2(k + 1) – 1) = 1 + 3 + 5 + 7 + · · · + (2k – 1) + (2(k + 1) – 1) = [1 + 3 + 5 + 7 + · · · + (2k – 1)] + (2(k + 1) – 1) = k2 + (2(k + 1) – 1) = k2 + 2k + 1 = (k + 1)2 . As´ 1 + 3 + 5 + 7 + · · · + (2(k + 1) – 1) = (k + 1)2 . Esto demuestra que P (k) ? P (k + 1). Se sigue por Inducci´n Matem´tica que si n es un n´mero natural, entonces 1 + 3 + 5 + 7 + · · · + (2n – 1) = n2 . 8 Ejercicios 1. En los siguientes ejercicios a, b, c y n son n´meros enteros. Demuestre: (a) Si n es impar, entonces n3 es impar. (b) Si a es impar, entonces a2 + 3a + 5 es impar. 22

u u ´ u u u o u . u . u (c) Si a, b son pares, entonces ab es par. (d) Si a, b son impares, entonces ab es impar. (e) Si a | b y a | c, entonces a | (b + c). (f) Si a | b, entonces a | (3b3 – b2 + 5b). (g) Si n es un n´mero entero, entonces n2 + 3n + 4 es par. (h) Si n2 es impar, entonces n es impar. (i) Si n es impar, entonces n2 es impar. (j) Si a no divide a bc, entonces a no divide a b. (k) Si 4 no divide a a2 , entonces a es impar. (l) Si n es impar, entonces 8 | (n2 – 1). (m) Si n es un n´mero entero, entonces 4 (n2 + 2). (n) Si n es un entero, entonces 4 | n2 o 4 | (n2 – 1). (o) Si a | b y a | (b2 – c), entonces a | c. 2. En los siguientes ejercicios demuestre que la proposici´n es falsa: (a) Si n es un n´mero natural, entonces 2n2 – 4n + 31 es primo. (b) Si n es un n´mero natural, entonces n2 + 17n + 17 es primo. (c) Si n2 – n es par, entonces n es par. (d) Si a es un n´mero entero, entonces 4 | (a2 – 3). 3. Demuestre por Inducci´n Matem´tica: (a) Si n es un n´mero natural, entonces 1 + 2 + 3 + 4 + ··· + n = (b) Si n es un n´mero natural, entonces n2 + n 2 12 + 22 + 33 + 42 + · · · + n2 = n(n + 1)(2n + 1) 6 (c) Si n es un n´mero natural, entonces 21 + 22 + 23 + 24 + · · · + 2n = 2n+1 – 2. 23