Monografías Plus      Agregar a favoritos      Ayuda      Português      Ingles     

Logica Proposicional, teoremas y demostraciones






Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
. 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

Monografias.com
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

Monografias.com
. 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

Monografias.com
. 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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Comentarios


Trabajos relacionados

  • Pitagoras y el pitagorismo

    Biografía de pitagoras. Armonía de los contrarios. La comunidad pitagorica. Nació hacia el año 578 ac. En samos (rival ...

  • Filósofos de la naturaleza

    Sócrates. La Política. Enseñanzas. El juicio. Tales de Mileto. Platón: Obra; Teoría de las ideas; Teoría del conocimien...

  • Eutanasia

    Definición del término eutanasia. Eutanasia: ¿Existe un derecho a morir?. Formas de aplicación de la eutanasia. La batal...

Ver mas trabajos de Filosofia

 
 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.


Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Iniciar sesión

Ingrese el e-mail y contraseña con el que está registrado en Monografias.com

   
 

Regístrese gratis

¿Olvidó su contraseña?

Ayuda