Archivo de la etiqueta: demostración

Álgebra Superior I: Demostraciones directas e indirectas

Por Guillermo Oswaldo Cota Martínez

Deja un comentario

Esta entrada es parte de una serie de notas introductorias sobre técnicas de demostración. Cada una es independiente de la otra, y para su explicación, se usa el siguiente diagrama de un mundo imaginario llamado el mundo de los Blorgs. Para leer más sobre ello, haz click aquí.

Introducción

Hasta ahora hemos introducido algunos conceptos introductorios de lo que es una demostración matemática, pero apenas estamos por iniciar este recorrido hacia lo que son estas. Ahora, empezaremos por ver dos formas de pensar al demostrar que son las demostraciones directas e indirectas.

La demostración directa

Ahora vamos a explorar un poco más esto de las demostraciones, qué son y cómo nos ayudan. ¿Recuerdas nuestro ejemplo de que todos los blorgs amarillos comían peces? Este es un ejemplo de una demostración directa. Este nombre viene del hecho de que partimos de una secuencia de proposiciones válidas y vamos conectando las proposiciones una tras una hasta que tenemos la conclusión deseada. En general este tipo de demostraciones van a ser cadenas de puras implicaciones. Por ejemplo

$P_0 \Rightarrow P_1, P1\Rightarrow P_2, P_2 \Rightarrow \dots, P_{n-1} \Rightarrow P_{n} $

De donde concluímos que $P_0 \Rightarrow P_{n}$. Esto en términos sencillos quiere decir: Las demostraciones directas van a ser aquellas que podemos dar «el paso claro» por ejemplo si sabemos que con madera podemos construir las patas y el asiento, y con patas y el asiento podemos construir una silla, entonces ya sabríamos que con madera podemos construir una silla, pues decimos: «Primero con la madera construimos las patas y el asiento, y después con las patas y el asiento construimos la silla». Cuando veamos otros tipos de demostraciones, verás más fácilmente porqué tienen este nombre. Mientras tanto veamos otro ejemplo.

Proposición. Un blorg que vive en las montañas come los lunes.

Demostración. Recordemos cómo empezamos la demostración de la entrada pasada, empezamos con un blorg que vive en las montañas y veremos poco a poco que come los lunes. Para empezar, nota que con las siguientes proposiciones:

$P(x) = x \text{ vive en las montañas} $

$Q(x) = x \text{ es un blerg},$

se cumple que:

$$P(x) \Rightarrow Q(x).$$

Además, sabemos que todos los blergs comen los lunes, es decir, suponiendo que $R(x) = x \text{ come los lunes}$ entonces:

$$Q(x) \Rightarrow R(x).$$

Y la siguiente regla de inferencia es válida:

\begin{array}{rl}
& P \Rightarrow Q \\
& Q \Rightarrow R \\
\hline
\therefore & P \Rightarrow R
\end{array}.

Entonces podemos aplicar esta regla de inferencia a nuestro problema, dando como resultado que

$$P(x) \Rightarrow R(x) $$

Ahora recuerda que en las demostraciones nuestro objetivo va a ser «generalizar». No basta con que un blorg en las montañas coma los lunes, si no quisieramos que siempre que veamos a un blorg en las montañas, sepamos que come los lunes.

Para esto, empezaremos con un blorg a quien le llamaremos $x$ y lo único que sabemos de este blorg es que vive en las montañas, es decir $P(x)$. Ahora, aplicando las reglas de inferencia, sabemos que si $P(x)$ entonces también $R(x)$. Esto quiere decir que sabiendo que un blorg vive en las montañas, ya sabemos que también come los lunes. Recuerda que para hacer este paso aplicamos las reglas de inferencia. De esta manera, $x$ come los lunes.

Por lo tanto, los blorgs que viven en las montañas comen los lunes.


$\square$

Demostraciones indirectas

Otra estrategia para demostrar cosas va a ser mediante lo que se conoce como la demostración indirecta. Y esta forma de demostrar proposiciones va a usar la siguiente regla de inferencia:

\begin{array}{rl}
& P \Rightarrow Q \\
\hline
\therefore &(\neg Q) \Rightarrow (\neg P)
\end{array}.

¿Recuerdas que la premisa es equivalente a la conclusión? Pues el que sea equivalente es suficiente para que sea una regla de inferencia válida. Hay ocasiones en la que no es tan sencillo hacer la demostración directa, pues al hacer la demostración indirecta, no probamos que una proposición $P$ implique $Q$, sino que en vez de eso, probamos que $\neg Q$ implica $\neg P$. Esta herramienta nos va a ser útil, pues resultará que en ocasiones es mejor trabajar con las negaciones que con las proposiciones sin negar, veamos un ejemplo.

Proposición. Si un blorg es amigo de los delfines, entonces es amarillo.

Demostración. Como estamos dando un ejemplo de la demostración indirecta, entonces pensémosle como tal. Primero tomemos nuestras proposiciones.

$P(x) = x \text{ es amigo de los delfines}$

$Q(x) = x \text{ es amarillo}.$

Y tenemos la proposición $P(x) \Rightarrow Q(x)$. Lo que nos dice la regla de inferencia es que habremos demostrado esta proposición si demostramos que $\neg Q \Rightarrow \neg P$. Ahora notemos que

$\neg Q(x) = x \text{ no es amarillo} = x \text{ es azul o rojo}$
$\neg P(x) = x \text{ no es amigo de los delfines}.$

Nota que si un blorg no es amarillo, entonces solo puede ser azul o rojo (pues los blorgs solo pueden ser de tres colores). De esta manera, en vez de demostrar que $P(x) \Rightarrow Q(x)$ demostraremos que $\neg Q \Rightarrow \neg P$. Para ello, es suficiente tomar a un blorg $x$ que sea azul o rojo. A continuación vamos a dividir esta demostración en casos. Como tenemos dos colores posibles para los blorgs, vamos a ver primero qué pasa si nuestro blorg es rojo y después qué pasa si es azul. Veamos cómo se ve esto.

Caso 1. $x$ es rojo.

Como nuestro blorg es rojo, entonces es un blerg, y sabemos que los blergs solo son amigos de los blurgs. Entonces no es amigo de los delfines.

¿Notas cómo probamos la conclusión? Ahora ya sabemos que la proposición es cierta siempre que nuestra $x$ sea rojo entonces no será amigo de los delfines. Con esto solo nos queda un caso.

Caso 2. $x$ es azul.

El caso que falta es que el blorg sea azul, es decir que sea un blurg. Pero aún así se cumple que $x$ no sea amigo de delfines, pues es amigo de los blargs y blergs.

Entonces lo que acabamos de hacer fue demostrar que en cualquier caso, el blorg $x$ no es amigo de los delfines. Así que podemos concluir que $\neg Q \Rightarrow \neg P$

$\square$

Sobre la demostración

Vamos a hacer algujnas observaciones sobre la forma en que demostramos nuestras proposiciones.

  1. Hasta ahora tenemos dos formas de demostrar: la directa y la indirecta. En pocas palabras la directa usa sucesiones de proposiciones que ya sabemos para llegar a una conclusión, mientras que la indirecta no empieza por lo que quiere demostrar, sino que nota que si la conclusión no es cierta, entonces la premisa no lo es.
  2. En nuestra segunda demostración dividimos nuestro problema en casos, esto es, notamos que si nuestro blorg no era amarillo, solo podía ser azul o rojo. Entonces lo que hicimos en ese punto fue irnos por los dos caminos: el camino en donde el blorg es rojo y el camino en donde es azul. Y notamos que en cualquiera de los caminos, no se cumplía la premisa. Habrá ocasiones en las que notes que para demostrar una proposición deberás considerar todos los casos, entonces tendrás que dividir tu problema en los distintos casos para hacer la demostración.
  3. Algo más que mencionar de nuestra última demostración es que no siempre vamos a dividir una demostración indirecta en casos, pues fue una coincidencia que en nuestra demostración necesitásemos del uso de los distintos casos. Entonces una demostración indirecta no siempre va a usar casos, pero hay ocasiones en las que serán necesarios.

Tarea moral

A continuación hay algunos ejercicios para que practiques los conceptos vistos en esta entrada. Te será de mucha utilidad intentarlos para entender más la teoría vista.

  1. Demuestra directamente que los blorgs rojos comen frutas.
  2. Demuestra directamente que los blorgs rojos comen frutas los lunes.
  3. Demuestra indirectamente que si un blorg no come peces, entonces es un blerg.

Más adelante…

Continuando con nuestras estrategias, la siguiente consistirá en la contradicción. En pocas palabras para demostrar que una proposición es verdadera, supondremos que no lo es. Y en una serie de pasos lógicos, veremos que habrá proposiciones que son falsas y verdaderas a la vez (esto no puede pasar), llamándose esto una contradicción.

Entradas relacionadas

Álgebra Superior I: Problemas de condicionales y cuantificadores

Por Guillermo Oswaldo Cota Martínez

Deja un comentario

Introducción

En esta entrada resolveremos problemas de temas vistos en entradas anteriores. Haremos algunos ejemplos relacionados con los conectores condicionales que vimos en una entrada anterior: la implicación y la doble implicación. También veremos algunos de cuantificadores lógicos.

Problemas resueltos

Problema. Si $P$ y $R$ son verdaderas y $Q$ es falsa, di si la siguiente proposición es verdadera o falsa: $$(P \lor R) \Rightarrow \neg(Q \land R).$$

Solución. Haremos una tabla de verdad pero únicamente con los valores que nos dan, es decir, no vamos a hacer la tabla para todos los casos, sino únicamente los que nos interesan en este momento:

$P$$Q$$R$$P \lor R$ $Q \land R$$\neg (Q \land R)$$(P \lor R) \Rightarrow \neg(Q \land R)$
$1$$0$$1$  $1$ $0$  $1$   $1$

Por lo tanto la proposición es verdadera para los valores de verdad dados.

$\square$

Problema. Di si las siguientes proposiciones sobre los números enteros son verdaderas o no:

  1. $(3+1=4) \Rightarrow (0<10)$
  2. $(4=5) \Leftrightarrow (9+1=10)$
  3. $((6<7) \lor (3^2=10)) \Rightarrow (12<12^2)$
  4. $((-1<1) \land (1<-1)) \Leftrightarrow ((13-1=12-1+1)\Rightarrow (1+1<2))$

Solución.

Vamos a hacer algunas verificaciones sobre cada una de las proposiciones para encontrar su valor de verdad:

  • $(3+1=4) \Rightarrow (0<10)$

Como $3+1=4$ es verdadera y $0<10$ es verdadera también, entonces la proposición es verdadera.

  • $(4=5) \Leftrightarrow (9+1=10)$

Recordemos que la doble condicional es verdadera si ambas proposiciones tienen el mismo valor de verdad. Por un lado no es cierto que $4=5$ mientras que sí es verdad que $9+1=10$. Por lo tanto la proposición es falsa.

  • $((6<7) \lor (3^2=10)) \Rightarrow (12<12^2)$

Vamos a ver la proposición por partes. Primero veamos que $((6<7) \lor (3^2=10))$ es una disyunción verdadera pues una de las proposiciones que la componen, $6<7$, lo es. Como $12<12^2$ es verdad, entonces la implicación tiene antecedente y subsecuente verdaderos y por lo tanto es verdadera.

  • $((-1<1) \land (1<-1)) \Leftrightarrow ((13-1=12-1+1)\Rightarrow (1+1<2))$

De nuevo vamos a dividir la proposición en sus partes, $(-1<1) \land (1<-1)$ y $(13-1=12-1+1)\Rightarrow (1+1<2)$. Primero notemos que $(-1<1) \land (1<-1)$ es falsa, pues no es cierto que $1<-1$.

Ahora, veamos cómo es $(13-1=12-1+1)\Rightarrow (1+1<2)$. Nota que $12=13-1$ y $12=12-1+1$, entonces $13-1=12-1+1$. Entonces esta primera parte es verdad, mientras que $1+1=2$ pero no es cierto que $2<2$. Así que es falso que $1+1<2$. Entonces $(13-1=12-1+1)\Rightarrow (1+1<2)$ es falso.

Como $(-1<1) \land (1<-1)$, $(13-1=12-1+1)\Rightarrow (1+1<2)$ son ambas falsas, entonces $((-1<1) \land (1<-1)) \Leftrightarrow ((13-1=12-1+1)\Rightarrow (1+1<2))$ es verdadero.

Nota: En este tipo de ejercicios, ¿viste cómo se dieron las argumentaciones de las proposiciones en cada caso? El secreto aquí fue «desarmar» las proposiciones en partes más pequeñas. Esto lo hacemos pues recuerda que los conectores son binarios, esto significa que su valor de verdad depende del valor de verdad de las dos proposiciones que conectan.

Así, para ver cuál es el valor de verdad de $((6<7) \lor (3^2=10)) \Rightarrow (12<12^2)$, lo que hicimos fue deshacerlo en sus partes. Una parte $A$ fue $(6<7) \lor (3^2=10)$ y la otra parte $B$ fue $12<12^2$. Entonces bastaba con verificar cuáles eran los valores de verdad de $A$ y $B$. Para ello, volvimos a «desarmar» a $A$ en sus partes «atómicas». Es decir, desarmamos $(6<7) \lor (3^2=10)$ en $6<7$ y $3^2=10$ y estudiamos el valor de verdad de cada uno de ellos. Usualmente este tipo de pensamiento de «desarmar un problema en sus partes» te ayudará a verificar o demostrar cosas más adelante.

Problema. Sean $P(x)$, $Q(x)$ y $R(x)$ los siguientes predicados:

  • $P(x): x \leq 4$
  • $Q(x): x +1$ es par.
  • $R(x): x> 0$

Si nuestro universo de discurso son los números enteros, ¿cuáles son los valores de verdad de las siguientes proposiciones?

  1. $P(1)$
  2. $P(1) \Rightarrow Q(1)$
  3. $P(0) \Rightarrow (R(5) \Rightarrow Q(0))$
  4. $R(-1) \lor P(2)$
  5. $\neg R(-2) \lor P(-2)$

Solución.

1.$P(1)$

Es verdadera, pues $1 \leq 4$.

2. $P(1) \Rightarrow Q(1)$

Como $P(1)$ es verdadera y además $1+1=2$ es par, entonces la proposición es verdadera.

3. $P(0) \Rightarrow (R(5) \Rightarrow Q(0))$

Vamos a dividir la proposición en partes. Primero notemos que $P(0)$ es verdad. Mientras que $R(5) \Rightarrow Q(0)$ es falsa, ya que es cierto que $5>0$ pero es falso que $0+1$ sea par. Entonces la proposición es falsa.

4. $R(-1) \lor P(2)$

Como $R(-1)$ es falsa pero $P(2)$ es verdad, entonces la proposición es verdadera.

5. $\neg R(-2) \lor P(-2)$

Como $-2<0$ es verdad, entonces $\neg R(-2)$ es falso, mientras que $-2<4$ es verdad. De esta manera la proposición es verdadera.

Problema. Considera los siguientes predicados:

  • $P(x): 2x>0$
  • $Q(x):x>0$
  • $R(x): x=20$
  • $T(x):x<0$

Determina la verdad o falsedad de las siguientes proposiciones, considerando que nuestro universo de discurso son los números enteros. Si la proposición no es verdadera, da un contraejemplo o explicación de ello.

  1. $\forall x(P(x) \Rightarrow Q(x))$
  2. $\exists x (Q(x) \land T(x))$
  3. $\forall x(R(x) \Rightarrow(Q(x))$
  4. $\exists ! x(R(x))$
  5. $ \nexists x (Q(x) \land P(x))$

Solución.

  • $\forall x(P(x) \Rightarrow Q(x))$

Nota que siempre que se cumple $2x>0$ entonces $x>0$ (más adelante demostrarás esto con toda formalidad, pero de momento lo daremos por cierto). Por lo tanto la proposición es verdadera.

  • $\exists x (Q(x) \land T(x))$

Para que esto sucediera, necesitaríamos la existencia de al menos un elemento $x$ que cumpla $0<x$ y $x>0$, es decir necesitaríamos un elemento que sea positivo y negativo a la vez, pero esto no es posible. Por lo tanto la proposición es falsa.

  • $\forall x(R(x) \Rightarrow(Q(x))$

Lo que nos dice esta proposición es «Para todo número entero $x$ que cumpla $x=20$ entonces $x>0$» o dicho de otra manera: «Si un número entero es igual a 20, entonces será positivo.» Lo cuál es correcto, pues si el número es distinto a 20, la implicación será correcta (recuerda la tabla de verdad de la implicación), mientras que el único caso en donde la hipótesis se cumple es cuando $x=20$ y claramente es un número que cumple $x>0$. Entonces la proposición es verdadera.

  • $\exists ! x(R(x))$

Esto nos quiere decir que existe un único número entero que sea igual a 20, e inmediatamente podemos saber que es verdadera, pero ¿A qué nos referiremos que un número sea igual a 20? Primero tendríamos que ponernos de acuerdo de qué significa la igualdad. Aunque ahora no lo haremos, piensa el cómo nos aseguraríamos de que es el único número entero que cumple esa propiedad ¿Qué pasaría si no fuera cierto?

  • $ \nexists x (Q(x) \land P(x))$

Lo que dice la proposición es que ningún número $x$ va a cumplir a la vez $x>0$ y $2x>0$, pero esto no es cierto, pues pensemos en $x=1$. Cumple $Q(x)$ ya que $1>0$ y cumple $P(x)$ porque $2*1=2>0$. Entonces podemos decir que es falso pues dimos un contraejemplo que contradijo la proposición.

Entradas relacionadas