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