Demostración por contraposición

En lógica, la contraposición lógica es una ley que dice que, para cada sentencia condicional, hay una equivalencia lógica entre la misma y su contraposición. En la contraposición de una sentencia, el antecedente y consecuente son invertidos y negados: la contraposición de ${displaystyle P ightarrow Q}$ es, por lo tanto, ${displaystyle eg Q ightarrow eg P}$. Ambas expresiones son equivalentes. Formalizada en los silogismos por Aristóteles, se establece que la negación de un consecuente implica la negación de su antecedente. Es decir, si una primera premisa implica una segunda premisa, se puede concluir que la negación de la segunda premisa implica la negación de la primera premisa. En consecuencia, la implicación original y su contrarrecíproco son equivalentes.

Por ejemplo, la proposición "Todos los perros son mamiferos" puede ser reescrita en su forma condicional "Si es perro, es mamífero." La ley dice que esta sentencia es idéntica a su contraposición "Si no es mamífero, entonces no puede ser perro."

Note que si ${displaystyle P ightarrow Q}$ es verdadera y nos es informado de que Q es falsa, es decir ${displaystyle eg Q}$, se puede inferir lógicamente que P debe ser falso, es decir, ${displaystyle eg P}$. Esto es, normalmente llamado ley de contraposición, o regla de inferencia modus tollendo tollens

Dada una afirmación original, es posible obtener todas sus formas condicionales.

Considere el diagrama de Venn de la derecha. Está claro que, si algo está en A, también debe estar en B. Podemos reescribir "Todo A está en B", como

También está claro que cualquier cosa que no está en B, también no puede estar en A. Esa sentencia,

es la contrapositiva. Así, podemos decir que

En la práctica, esto puede facilitar bastante al intentar probar algo. Por ejemplo, si queremos demostrar que todas las chicas de Suecia (${displaystyle A}$) son rubias (${displaystyle B}$), podemos tratar de probar ${displaystyle (A o B)}$ revisando a cada una de las chicas de Suecia para ver si todas son rubias. O, alternativamente, podemos tratar de probar ${displaystyle ( eg B o eg A)}$, es decir, que todas las chicas no rubias están fuera de Suecia. Si encontramos al menos una chica no rubia en Suecia, hemos refutado ${displaystyle ( eg B o eg A)}$, y por equivalencia, hemos refutado también ${displaystyle (A o B)}$.

Esta ley lógica puede utilizarse como regla de derivación en la línea de premisas y puede definirse como la fórmula lógica:

${displaystyle (A ightarrow B)leftrightarrow (lnot B ightarrow lnot A)}$

Por ejemplo, la siguiente implicación

${displaystyle (A ightarrow B)}$ Está lloviendo, por lo tanto, te espero dentro del teatro.

es equivalente a su contrarrecíproco

${displaystyle (lnot B ightarrow lnot A)}$ No te espero dentro del teatro, por lo tanto, no está lloviendo.

El contrarrecíproco es una articulación alternativa del modus tollendo tollens de la lógica proposicional.

En síntesis, para cualquier juicio que A implica B, entonces no B siempre implica no A. Probar o refutar cualquiera de las dos sentencias automáticamente prueba o refuta la otra. Son completamente equivalentes. En efecto, si analizamos su tabla de valores de verdad:

Esta equivalencia queda clara, puesto que se obtiene una tautología.^{[cita requerida]}

La demostración de esta ley como regla del cálculo se realiza mediante la utilización de la regla "Introducción del negador", "Absurdo" o "Demostración indirecta" (diferentes nombres para una misma regla), de donde la regla "contrarrecíproco", también llamada de "contraposición" o "transposición" es derivada.

Aplicando las reglas del cálculo deducción natural:

Se expone aquí la fundamentación de una sola modalidad de las cuatro posibles, pues todas siguen los mismos pasos con iguales patrones, partiendo naturalmente del cambio de la premisa inicial.:^[1]​

${displaystyle A ightarrow lnot Bvdash B ightarrow lnot A}$

${displaystyle lnot A ightarrow Bvdash lnot B ightarrow A}$

${displaystyle lnot A ightarrow lnot Bvdash B ightarrow A}$

Una vez fundamentada la ley en todos los casos posibles podemos establecer, como fórmulas equivalentes una regla de reemplazo de la siguiente forma:

La proposición Q está implícita en la proposición P cuando la siguiente relación es verdadera:

En términos coloquiales, esto significa que "si P, entonces Q", o, "si Sócrates es hombre, entonces Sócrates es humano." En un condicional como ese, P es el antecedente, y Q es el consecuente. Una sentencia es contrapositiva de otra solamente cuando su antecedente es la negación del consecuente de la otra, y viceversa. La contrapositiva del ejemplo es

Esto es, "Si no Q, entonces no P", o más precisamente "Si Q no es el caso, entonces P no es el caso." Usando nuestro ejemplo, "Si Sócrates no es humano, entonces Sócrates no es un hombre." Esta sentencia se dice que es contrapuesta con relación a la original y las dos son lógicamente equivalentes. Debido a la equivalencia lógica, afirmar una afirma automáticamente la otra: cuando una es verdadero, la otra también. Lo mismo ocurre para la falsedad.

Rigurosamente, la oposición solo puede existir en dos condicionales simples. Sin embargo, la oposición también puede existir en dos condicionales complejos, si los mismos son semejantes. Por lo tanto, ${displaystyle forall {x}(P{x} o Q{x})}$, o "Todos los Ps son Qs," tiene como contrapositiva ${displaystyle forall {x}( eg Q{x} o eg P{x})}$, o "Todo no Q es no P."

En lógica, la contraposición de una declaración condicional se forma negando ambos términos e invirtiendo la dirección de la inferencia. Explícitamente, la contraposición de la declaración «si A, entonces B» es «si no es B, entonces no A». Una declaración y su contrapositiva son lógicamente equivalentes: si la afirmación es cierta, entonces su contrapositivo es cierto, y viceversa.^[3]​

Si tenemos que demostrar que una proposición p implica una proposición q (es decir, si se da p, se tiene que dar q), a veces es más sencillo demostrar que si no se da q, entonces no puede cumplirse p. Esto se conoce como demostración por contrarrecíproco o contraposición. Nótese que "p implica q" y "no q implica no p" son proposiciones equivalentes.

En matemáticas, la demostración por contraposición es una regla de inferencia utilizada en demostraciones. Esta regla se infiere una sentencia condicional a partir de su contraposición.^[4]​ En otras palabras, la conclusión «si A, entonces B» se extrae de la premisa simple «si no B, entonces no A».

Cualquier demostración por contraposición también puede formularse trivialmente en términos de una demostración por contradicción: Para demostrar la proposición ${displaystyle PRightarrow Q}$, consideramos lo contrario, ${displaystyle lnot (PRightarrow Q)equiv lnot (lnot Pvee Q)equiv Pwedge lnot Q}$. Puesto que tenemos una prueba de que ${displaystyle lnot QRightarrow lnot P}$, tenemos ${displaystyle Pwedge lnot QRightarrow Pwedge lnot Pequiv ot }$ lo que llega a la contradicción que se pretende. Así que demostración por contraposición es en cierto sentido "al menos tan difícil de formular" como demostración por contradicción.

Un ejemplo sencillo: "Demuéstrese que todos los números primos mayores que 2 son impares". Aquí,

${displaystyle p}$: "n es un número primo mayor que 2" ${displaystyle q}$: "n es un número impar".

Demostrar

${displaystyle pRightarrow q}$: "si un número primo es mayor que 2, entonces es impar "

es lo mismo que demostrar que

${displaystyle lnot qRightarrow lnot p}$: "si un número entero es par (i.e. no impar), entonces no es un número primo o es menor o igual que 2."

La ventaja es que esto es más fácil de demostrar, ya que todo número par se puede escribir como n = 2 × k, donde k es entero. Si k es menor o igual que 1 entonces n es menor o igual que 2 (segunda parte de ${displaystyle lnot p}$), así que podemos suponer que k es mayor que 1. En este supuesto n es mayor que 2, pero no es primo ya que tiene algún factor que no es ni 1 ni él mismo, concretamente k. Así que 2 es el único número primo par, por lo que se ha demostrado que todos los números primos mayores que 2 son impares.

Sea x un número entero.

A pesar de que se puede dar una demostración directa, optamos por probar esta afirmación por contraposición. La contraposición de la declaración anterior es:

Esta última afirmación se puede demostrar de la siguiente manera. Supongamos que x no es par. Entonces x es impar. El producto de dos números impares es impar, por lo tanto, x² = x · x es impar. Por lo tanto x² no es par.

Después de haber probado la contraposición, inferimos la declaración original.^[5]​

En la lógica de primer orden, una sentencia condicional es definida como:

Se tiene:

Sea:

Es como si A es verdad, entonces B es verdad, y también se da que B es falso. Entonces podemos, entonces, mostrar que A no debe ser verdad, por contradicción. Por ejemplo, si A fuese verdadero, entonces B también tendría que ser verdadero (dado). Sin embargo, se nos da que B no es verdadero, entonces tenemos una contradicción. Luego, A no es verdad (suponiendo que estamos tratando con declaraciones concretas que solo pueden ser verdaderas o falsas (ley del tercero excluido)):

Podemos aplicar el mismo proceso en sentido contrario:

También sabemos que B o es verdadero o falso. Si B es falso, entonces A es también. Sin embargo, se da que A es verdad. Así, la suposición de que B es falso nos lleva a una contradicción, por lo tanto, debe ser falsa. Por lo tanto, B debe ser verdadero:

Combinando los dos argumentos, llegamos a la equivalencia:

La equivalencia lógica entre dos proposiciones significa que ambas son simultáneamente verdaderas o simultáneamente falsa. Para probar que una sentencia y su contrapositiva son lógicamente equivalentes, se tiene que entender cuando una implicación es verdadera o falsa.

Esta sentencia es falsa solo cuando P es verdadero y Q es falso. Así, podemos reducir esta proposición a la sentencia "Falso cuando P y no Q" (es decir, "Verdadero cuando P no es el caso y no Q"):

Los elementos de una conjunción lógica pueden ser revertidos sin cambiar el significado de la frase (por conmutatividad):

Se define ${displaystyle R}$ como igual a "${displaystyle eg Q}$", y ${displaystyle S}$ como igual a ${displaystyle eg P}$, (también, ${displaystyle eg S}$ es igual a ${displaystyle P}$ solamente):

Esta frase se lee como "No es cierto que (R es verdadero y S es falso)", que es la definición de un condicional. Entonces podemos realizar la siguiente sustitución:

Cuando se intercambia las definiciones de R y S, se llega a:

Aunque el valor-verdad de las sentencias puede diferir, el valor-verdad de expresiones equivalentes siempre es el mismo.

Considere la sentencia «Todo objeto rojo tiene color». La misma puede ser expresada de manera equivalente como «Si un objeto es de color rojo entonces tiene color».

En otras palabras, la contrapositiva es lógicamente equivalente a un determinado condicional, aunque no es válida para bicondicionales ('si y sólo si').

Del mismo modo, considere la sentencia "Todo cuadrilátero tiene cuatro lados", o, expresado de forma equivalente: "Si un polígono es un cuadrilátero, entonces el mismo tiene cuatro lados."

Como la sentencia y su recíproco son ambas verdaderas, esta afirmación se llama bicondicional, y puede expresarse como "Un polígono es un cuadrilátero si y solamente si tiene cuatro lados." (La frase si y solamente si puede ser abreviada como IFF.) Esto es, tener cuatro lados para ser es un cuadrilátero y también suficiente para que un polígono sea cuadrilátero.

Como la contrapositiva de una sentencia siempre tiene el mismo valor de verdad (verdadero o falso) que la sentencia, puede ser una herramienta bastante útil para demostrar teoremas matemáticos. Una prueba por contradicción es una prueba directa de la contrapositiva de una declaración.^[6]​

Sin embargo, los métodos indirectos también se pueden utilizar con contraposición, como por ejemplo la prueba por contradicción, por ejemplo, en la prueba de irracionalidad de la raíz cuadrada de 2. Por la definición de un número racional, podemos decir que "Si ${displaystyle {sqrt {2}}}$ es racional, entonces el mismo se puede expresar por una fracción irreducible." Esta frase es verdadera, pues una manera de volver a reescribir la definición (verdadera). La contrapositiva de esta sentencia es "Si ${displaystyle {sqrt {2}}}$ no puede ser expresado a través de una fracción irreeducible, entonces no es racional." Esta contrapositiva, así como la sentencia original, también es verdadera. Por lo tanto, se puede demostrar que ${displaystyle {sqrt {2}}}$ no puede ser expresada como una fracción irreducible, entonces debe ser cierto que ${displaystyle {sqrt {2}}}$ no es un número racional. Este último puede ser probado por la contradicción.

El ejemplo anterior utiliza la contrapositiva de una definición para demostrar un teorema. También se puede probar un teorema que demuestra la contrapositiva de la declaración del teorema. Para probar que, si un entero positivo N es un número no cuadrado, a su vez, su raíz cuadrada es irracional, que no puede demostrar su equivalente positivo frente que si un entero positivo N tiene una raíz cuadrada, que es racional, entonces N es un número cuadrado. Esto se puede demostrar mediante la creación de √N igual a la expresión racional a/b con a y b siendo números enteros positivos sin ningún factor primo en común, y en cuadratura para obtener N = a²/b² y notar que una vez que N sea un número entero positivo b=1 de modo que N = a², un número cuadrado.

---