En matemáticas, una demostración o bien
una prueba es un argumento deductivo para asegurar la
verdad de una proposición matemática. Las demostraciones son ejemplos
de razonamiento deductivo y se distinguen de
argumentos inductivos o empíricos; una demostración debe
demostrar que una afirmación es siempre verdadera (ocasionalmente al listar
todos los casos posibles y mostrar que es válida en cada uno), más que enumerar
muchos casos confirmatorios. Una afirmación no probada que se cree verdadera se
conoce como conjetura.
Las demostraciones emplean lógica pero normalmente incluyen
una buena parte de lenguaje natural, el cual usualmente admite alguna
ambigüedad. De hecho, la gran mayoría de las demostraciones en las matemáticas
escritas puede ser considerada como aplicaciones de lógica rigurosa. La
distinción entre demostraciones formales e informales ha llevado a
examinar la lógica matemática histórica y actual,
el cuasi-empirismo matemático y el formalismo matemático.
El hecho de no conocer ninguna demostración de un teorema no implica su
no veracidad; sólo la demostración de la negación de este resultado implica que
es falso.
Observese que, de acuerdo con estas definiciones, un teorema es
verdadero si, y solo si la proposicion condicional
P → Q
es una tautologia o tambien si
P ⇒ Q
o tambien si
P ∴ Q
Dicho de otra forma un teorema es verdadero si, y solo si el
razonamiento
P → Q
es valido.
Ejemplo 1
Determinar cuales de los razonamientos siguientes son validos. Construir
demostraciones para los razonamientos que lo sean y para los que no lo sean,
explicar por qu´e la conclusion no se sigue de la hipotesis.
(a) p ∧ q
(b) p ∨ q
(c) p → q
p → r
p→ r
p → r
_____
_____
_____
∴ r ∧ q
∴ r ∨ q
∴ r → q
Solucion
(a) En efecto
(p ∧ q) ∧ (p → r) ⇐⇒ (q ∧ p) ∧ (p → r)
{Conmutatividad de ∧}
⇐⇒ q ∧ [p ∧ (p −→ r)] {Asociatividad de ∧}
⇒ q ∧ r
{Modus ponens}
⇒ r ∧ q
{Conmutatividad de ∧}
El razonamiento es valido.
(b) En efecto
(p ∨ q) ∧ (p → r) ⇒ (¬q → p) ∧ (p −→ r) {Implicacion}
⇒ ¬q → r
{Silogismo hipotetico}
⇒ ¬¬q ∨ r
{Implicacion}
⇐⇒ q ∨ r
{Doble negacion}
⇐⇒ r ∨ q
{Conmutatividad de ∨}
El razonamiento, por tanto, es valido.
(c) Veamos si el razonamiento es valido, es decir, si [(p → q) ∧ (p → r)] ⇒ (r → q).
Si (p → q)∧(p → r) es verdad, entonces p → q y p →
r, ambas, han de ser verdad. Analizamos las distintas opciones segun los
valores de verdad de p.
− Si p es verdad, entonces q y r han de ser verdad, luego r → q es
verdad.
− Si p es falsa, entonces q y r pueden ser las dos verdad, las dos falsas
o una falsa y la otra verdad. En uno de los casos (r verdadera y q falsa)
la conclusion, r → q es falsa.
Por lo tanto de la veracidad de la hipotesis no se sigue la veracidad de
la conclusion y, consecuentemente, el razonamiento no es valido.
Ejemplo2
Formular simbolicamente los siguientes razonamientos y determinar cuales
son validos. Tomar:
p: Estudio mucho.
q: Obtengo C como calificacion.
r: Me hago rico.
(a) Si estudio mucho, entonces obtengo C como calificacion.
Estudio mucho.
_________________________________________
∴ Obtengo C como
calificacion.
(b) Si estudio mucho, entonces obtengo C como calificacion.
Si no me hago rico, entonces no obtengo C como
calificacion.
___________________________________________
∴ Me hago rico.
(c) Estudio mucho si y solo si me hago rico.
Me hago rico.
_____________________________
∴ Estudio mucho.
(d) Si estudio mucho o me hago rico, entonces obtengo C como
calificacion.
Obtengo C como calificacion.
___________________________________________________
∴ Si no estudio
mucho, entonces me hago rico.
(e) Si estudio mucho, entonces obtengo C como calificacion o me hago
rico.
No obtengo C como calificacion y no me hago
rico.
___________________________________________________
∴ No estudio mucho.
Solucion
(a) La regla de inferencia en notacion simbolica es:
p → q
p
_____
∴ q
conocida con el nombre de Modus ponens, luego el razonamiento es
valido.
(b) La regla de inferencia en notacion simbolica es
p → q
¬r → ¬q
______
∴ r
Observemos lo siguiente:
(p → q) ∧ (¬r → ¬q) ⇐⇒ (p → q) ∧ (q → r)
{Contrarreciproca}
⇒ p → r
{Silogismo Hipotetico}
Por tanto, la conclusion es:
Estudio mucho o me hago rico
es decir, el razonamiento no es valido.
(c) La regla de inferencia en notacion simbolica es
p ←→ r
r
______
∴ p
Veamos si [(p ←→ r) ∧ r] ⇒ p. En efecto, si (p ←→ r) ∧ r es verdad,
entonces p ←→ r y r han de ser, ambas, verdad, luego p tambien sera verdad y,
consecuentemente, el razonamiento es valido.
(d) La regla de inferencia en notacion simbolica es:
(p ∨ r) → q
q
________
∴ ¬p → r
Si ¬p --→ r es falsa, entonces ¬p es verdad y r falsa, es decir p y r
son, las dos, falsas, luego (p ∨ r) → q es verdad
independientemente del valor de verdad que tenga q, de aqui que el valor de
verdad de [(p ∨ r) → q] ∧ q dependa del de q,
es decir, podr´a ser verdadera o falsa y, consecuentemente, el razonamiento no
sea valido.
(e) La regla de inferencia en notacion simbolica es:
p → (q ∨ r)
¬q
∧ ¬r
_________
∴ ¬p
Observemos lo siguiente:
[p → (q ∨ r)] ∧ (¬q ∧ ¬r) ⇐⇒ [p → (q ∨ r)] ∧ [¬(q ∨ r)] {De Morgan}
⇒ ¬p
{Modus Tollens}
Por tanto, el razonamiento es valido.
Ejemplo 3
Expresar verbalmente los razonamientos dados y establecer la validez de
los mismos. Tomar:
p : 1Gb es mejor que nada.
q : Compraremos mayor capacidad de memoria.
r : Compraremos un ordenador nuevo.
(a) p →
r
p → q
________
∴ p → (r ∧ q)
(b) p → (r ∨ q)
r → ¬q
_________
∴ p → r
(c) p → r
r → q
______
∴ q
(d) ¬r →
¬p
r
_______
∴ p
(e) p → r
r → q
p
______
∴ q
Solucion
(a) La forma verbal del razonamiento seria:
Si 1Gb es mejor que nada, entonces compraremos un
ordenador nuevo.
Si 1Gb es mejor que nada, entonces compraremos mayor
capacidad de memoria.
_____________________________________________________________
∴ Si 1GB es mejor que nada,
entonces compraremos un ordenador nuevo y mayor capacidad
de memoria.
Entonces
(p → r) ∧ (p → q) ⇐⇒ (¬p ∨ r) ∧ (¬p ∨ q)
{Implicacion}
⇐⇒ ¬p ∨ (r ∧ q)
{Distributividad de ∨ respecto de ∧}
⇐⇒ p −→ (r ∧ q)
{Implicacion}
Por lo tanto, el razonamiento es valido.
(b) En forma verbal, el razonamiento es
Si 1Gb es mejor que nada, entonces compraremos un
ordenador nuevo o mayor capacidad de memoria.
Si compramos un ordenador nuevo, entonces no compraremos
mayor capacidad de
memoria.
______________________________________________________________
∴ Si 1Gb es mejor que nada,
entonces compraremos un ordenador nuevo.
Pues bien, si p → r es falso, entonces p es verdad y r es falso, luego r
→ ¬q es verdad independientemente del valor de verdad de q y el valor de verdad
de [p → (r ∨ q)]∧(r → ¬q) dependera
del de p → (r ∨ q) que, a su vez, depende del que
tenga q.
− Si q es verdad, entonces p → (r ∨ q) es verdad y, por
lo tanto, [p → (r ∨ q)] ∧ (r → ¬q) es
verdad.
− Si q es falso, entonces p → (r ∨ q) es verdad y, por
lo tanto, [p → (r ∨ q)] ∧ (r → ¬q) es
falso.
Consecuentemente, el razonamiento no es valido.
(c) El razonamiento seria:
Si 1Gb es mejor que nada, entonces compraremos un ordenador
nuevo.
Si compramos un ordenador nuevo, entonces compraremos mayor
capacidad de memoria.
______________________________________________________________
∴ Compraremos mayor capacidad de
memoria.
Estudiemos la validez del razonamiento. Por el silogismo
hipotetico,
[(p → r) ∧ (r → q)] ⇒ (p −→ q)
pero p → q no implica logicamente q. En efecto, si p → q es verdad,
entonces pueden ocurrir dos cosas:
si p es verdad, q ha de ser tambien verdad.
si p es falso, q puede ser verdad o falso.
Consecuentemente, el razonamiento no es valido.
(d) La forma verbal del razonamiento seria:
Si no compramos un ordenador nuevo, entonces 1GB no es
mejor que nada.
Compraremos un ordenador nuevo.
____________________________________________________
∴ 1Gb es mejor que nada.
Estudiemos su validez.
Si [(¬r → ¬p) ∧ r] es verdad, entonces ¬r → ¬p y r han
de ser, ambas, verdad, de aqui que ¬r sea falsa y ¬p y, por lo tanto, p pueda
ser verdad o falsa.
Asi pues, de la veracidad de [(¬r −→ ¬p) ∧ r] no se sigue la veracidad de p, luego la primera proposicion no
implica logicamente la segunda y, consecuentemente, el razonamiento no es
valido.
(e) El razonamiento en forma verbal es
Si 1Gb es mejor que nada, entonces compraremos un
ordenador nuevo.
Si compramos un ordenador nuevo, entonces compraremos
mayor capacidad de memoria.
1Gb es mejor que nada.
_____________________________________________________________
∴ Compraremos mayor capacidad de
memoria.
Veamos el razonamiento:
(p → r) ∧ (r −→ q) ∧ q ⇒ (p −→ q) ∧ p {Silogismo Hipotetico}
⇒ q
{Modus Ponens}
Por lo tanto es valido.
Metodos de Demostracion
Hemos visto con anterioridad que una demostracion era un razonamiento
que establece la veracidad de un teorema, es decir demostrar un teorema
equivale a probar que la proposicion condicional P → Q es una tautologia o lo
que es igual probar que P ⇒ Q.
Veremos algunas de las tecnicas utilizadas para probar implicaciones. Debido a que dichas tecnicas son bastante comunes nos referiremos a ellas por sus nombres.
Demostracion Vacia
Una demostracion de
este tipo se construye estableciendo que el valor verdadero de la hip´otesis P
es falso.
En efecto, si podemos
establecer la falsedad de P, entonces el condicional P → Q siempre es verdad
independientemente del valor de verdad de la conclusion Q. luego P → Q es una
tautologia y, consecuentemente, P ⇒ Q.
Aunque parece que
tiene poco valor, este metodo de demostracion es importante para establecer
limitaciones o estudiar casos especiales.
Demostracion
Trivial
Se construye una
demostracion de este tipo, probando que el valor verdadero de la conclusion es
verdad.
Si es posible
establecer la veracidad de la conclusion Q, entonces el condicional P→ Q sera
una tautologia independientemente del valor de verdad que tenga la hipotesis,
luego P ⇒ Q, la demostracion es correcta y el
teorema cierto.
Al igual que la
demostracion vacia, la demostracion trivial tiene una aplicacion limitada y aun
asi es bastante importante. Se utiliza frecuentemente para establecer casos
especiales de afirmaciones.
Demostracion
Directa
Una demostracion de
este tipo muestra que la verdad de la conclusion Q, se sigue logicamente
de la verdad de la hipotesis P. La demostracion empieza asumiendo que P es
verdad para despues, utilizando cualquier informacion disponible, asi como
teoremas probados con anterioridad, probar que Q es verdad.
Ejemplo 4
Demostrar que el
cuadrado de un numero entero par tambien es par.
Demostracion
El teorema a
demostrar escrito en forma de condicional, seria
“Para cualquier
entero n, si n es par, entonces n 2 es par”
que se corresponde
con el esquema
∀n p(n) −→ p(n 2 )
donde p(n) : n es
par.
y el universo del
discurso son todos los numeros enteros.
Pues bien, sea n un
numero entero cualquiera.
Si n es par, entonces
por la definicion que vimos en el ejemplo 4 existira un numero entero k tal
que
n = 2k
de aqui que elevando
al cuadrado, obtengamos
n 2 = 4k 2 = 2(2k 2
)
y como el cuadrado de
un numero entero tambien es entero, 2k 2 sera entero (lo llamaremos m).
Asi pues, hemos
encontrado un entero m tal que
n 2 = 2m.
Por lo tanto, y
utilizando de nuevo la definicion, concluimos que
n 2 es par.
Aunque este ejemplo
es bastante sencillo, el desarrollo l´ogico de la demostracion es identico al
de otros teoremas de contenidos mas complicados. Observemos, una vez mas, el
camino seguido a traves de implicaciones.
Sea n cualquier
numero entero. Entonces,
n es
par ⇒ ∃k : n = 2k
{Ejemplo 4}
⇒ n 2 = 4k 2
{Elevando al cuadrado}
⇒ ∃m : n 2 = 2m
{Tomando m = 2k 2}
⇒ n 2 es par
{Ejemplo 4}
Demostracion por la
Contrarreciproca
La demostracion de un
teorema se dice que es por la contrarreciproca cuando suponiendo que la
conclusion, Q, es falsa y utilizando la hipotesis P y otros teoremas y
equivalencias logicas establecidas previamente, se concluye que P es
falso.
Esta basada en la
equivalencia logica entre una proposicion condicional y su
contrarreciproca,
P → Q ⇐⇒ ¬Q → ¬P
Por lo tanto, si
probamos que ¬Q → ¬P es una tautolog´ıa, habremos probado que P → Q tambien lo
es, luego P ⇒ Q.
Ejemplo 5 Demostrar, para cada
entero n, que si 5n + 3 es par, entonces n es impar.
Demostracion
Utilizaremos el
metodo de demostracion por la contrarreciproca.
Si
p(n) : n es par
q(n) : n es
impar
el esquema del
teorema propuesto sera
∀n [p(5n + 3) → q(n)]
en el universo de los
numeros enteros. El esquema de la contrarreciproca seria
∀n [¬q(n) −→ ¬p(5n + 3)]
es decir,
“Para cada entero n,
si n no es impar, entonces 5n + 3 no es par”
Pues bien, sea n
cualquier numero entero.
Si n no es impar,
entonces,
n = 2k +
1
para cualquier entero
k y, por lo tanto,
5n + 3 = 5(2k + 1) +
3, ∀k ∈ Z
de aqui que
5n + 3 = 2(5k +
4), ∀k ∈ Z
y como si k es
entero, 5k + 4 tambien lo es (lo llamaremos m), tendremos que
5n + 3 = 2m, ∀m ∈ Z
Consecuentemente, y
de acuerdo con la definicion dada en el ejemplo 5, 5n + 3 no es par y la
demostracion concluye.
Veamos la
demostracion a traves de implicaciones. Sea n un n´umero entero cualquiera.
Entonces,
n no es impar ⇒ n 6= 2k + 1, ∀k ∈ Z
{Nota 3.3}
⇒ 5n + 3 = 5(2k
+ 1) + 3
= 10k + 8 {Haciendo
operaciones}
= 2(5k + 4)
⇒ 5n + 3 6= 2m, ∀m ∈ Z {Tomando m = 5k
+ 4}
⇒ 5n + 3 no es par
{Ejemplo 4}
Demostracion por
Contradiccion
La demostracion de un
teorema diremos que es por contradiccion cuando suponiendo que la conclusion,
Q, es falsa y utilizando la hipotesis P, y otros teoremas y equivalencias
logicas establecidas previamente, se llega a una contradiccion.
Esta basada en la
equivalencia logica conocida como reduccion al absurdo, es por ello que este
metodo de demostracion es conocido, tambien, como demostracion por reduccion al
absurdo.
P → Q ⇐⇒ (P ∧ ¬Q) → C
donde C es una
contradiccion. Por lo tanto, si probamos que (P ∧ ¬Q) → C es una
tautologia tendremos que P → Q tambien lo es y, consecuentemente, P ⇒ Q.
Ejemplo 6 Demostrar que
si el cuadrado de un numero entero es impar, entonces el numero es impar.
Demostracion
El teorema a
demostrar es
“Para cada entero n,
si n 2 es impar, entonces n es impar”
Si
p(n) : n es impar
entonces el esquema
del teorema en notacion simbolica sera
∀n p(n 2 ) −→ p(n)
en el universo de los
numeros enteros. Lo demostraremos por contradiccion o reduccion al absurdo. El
esquema seria
∀n p(n 2 ) ∧ ¬p(n) → C
donde C es una
contradiccion.
Pues bien, sea n
cualquier numero entero.
Supongamos que n 2 es
impar y que, sin embargo, n no es impar. Entonces, tendremos que
n 2 es impar y n es
par
tenemos que existen
dos numeros enteros k y l tales que
n 2 = 2k + 1 y
n = 2l
luego,
n 2 = 2k + 1 y n 2 =
4l 2
por lo tanto,
2k + 1 = 4l
2
de donde se sigue
que
1 = 4l 2 − 2k = 2(2l
2 − k)
y como si l y k son
enteros, 2l 2 − k tambien lo es (lo llamaremos m), tendremos que hemos
encontrado un n´umero entero m tal que
1 = 2m
es decir, el 1 es
par, lo cual, obviamente, es una contradiccion.
Lo que nos ha llevado
a la contradiccion es la suposicion de que n no era impar, por lo tanto esta es
falsa siendo cierta la contraria, es decir, n es impar.
Veamos la
demostracion a traves de implicaciones.
n2 impar y n no es
impar ⇒ n2 impar y n es par
⇒ ∃k : n2 = 2k + 1 y ∃l : n = 2l {Definicion de impar y
par}
⇒ ∃k : n2 = 2k + 1 y ∃l : n 2 = 4l 2 {Elevando l al cuadrado}
⇒ ∃k y ∃l : 2k + 1 = 4l 2
{Igualando}
⇒ ∃k y ∃l : 1 = 2(2l 2 − k) {Haciendo
operaciones}
⇒ ∃m : 1 = 2m
{Tomando m = 2l 2 − k}
⇒ 1 es par
{Definicion de numero par}
⇒ Contradiccion
Busqueda de
Contraejemplos
Este tipo de
demostracion, intimamente relacionada con el cuantificador universal, aparece
cuando se quiere probar que una proposicion del tipo ∀x, p(x) es falsa. Normalmente diremos que se refuta la proposici´on ∀x, p(x).
En efecto, ∀x, p(x) sera falsa cuando exista, al menos, un elemento a en el universo
del discurso para el cual p(a) sea una proposicion falsa. Hemos encontrado,
pues, un ejemplo que contradice el que ∀x, p(x) sea verdad
por lo cual le llamaremos contraejemplo.
En el caso de un
teorema el planteamiento seria como sigue: ∀x [p(x) → q(x)] es
falso si existe un elemento a en el universo para el cual la proposicion
condicional p(a) → q(a) sea falsa, es decir
tal que p(a) sea verdad y, sin embargo, q(a) sea falsa.
Ejemplo 7 En el universo de los
numeros enteros positivos, demostrar o refutar la siguiente
proposicion: “la suma de dos cuadrados perfectos es tambien un cuadrado
perfecto.”
Solucion
Recordemos que un
entero positivo x es un cuadrado perfecto si puede encontrarse otro entero
positivo y tal que x = y2 .
La proposicion a
demostrar escrita en forma de condicional seria:
“Si m y n son enteros
positivos y cuadrados perfectos, entonces m + n es un cuadrado perfecto.”
Pues bien, si
p(m, n) : m + n es un
cuadrado perfecto,
entonces la
proposicion escrita en forma simbolica es:
∀m, ∀n [(p(m, 0) ∧ p(n, 0)) → p(m, n)]
y un
contraejemplo,
∃a, ∃b : [p(a, 0) ∧ p(b, 0) ∧ ¬p(a, b)]
es decir,
“pueden encontrarse
dos enteros positivos a y b tales que sean cuadrados perfectos y que, sin
embargo, su suma no lo sea.”
Pues bien, elijamos
dos cuadrados perfectos arbitrariamente, por ejemplo el 25 y el 36.
Entonces,
25 + 36 = 61 6= y 2 ,
∀y
por lo tanto, y de
acuerdo con la definicion de cuadrado perfecto dada, 61 no es un cuadrado
perfecto. Asi pues, ya tenemos el contraejemplo
“25 y 36 son, ambos,
cuadrados perfectos y, sin embargo, su suma, 25 + 36, no lo es.”
Consecuentemente, la
proposicion propuesta es falsa.
NOTA Segun hemos
visto podemos demostrar un teorema de forma directa o indirecta
(contrarreciproca y contradiccion). Si podemos demostrarlo de forma directa,
resultara, en general, mas facil que utilizar metodos indirectos. Podemos
empezar intentando un metodo directo y si no resulta, buscar un contraejemplo
que refute el teorema. Si la busqueda del contraejemplo tambien falla, entonces
intentarIamos la demostracion a traves de metodos indirectos.
