jueves, 29 de junio de 2017

1.6.Demostraciones

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

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
de aqui que
 5n + 3 = 2(5k + 4), k
y como si k es entero, 5k + 4 tambien lo es (lo llamaremos m), tendremos que 
5n + 3 = 2m, m
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 ,
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.


No hay comentarios.:

Publicar un comentario