importancia de la implicación frente a su tautología

Question

Soy autodidacta en lógica, empecé con la programación. Los textos destacan la importancia del operador de implicación, pero yo no veo la importancia del operador. Siempre fue intuitivamente claro que,

$$ p \rightarrow q \equiv \neg \ p \lor q $$

Teniendo esto en cuenta, mis preguntas son:

• ¿La implicación permite reglas de reescritura adicionales o una mayor comprensión de alguna forma?
• ¿Es la forma secuencial, con su fuerte uso de reglas de implicación, más "potente" que la lógica de enésimo orden con sintaxis proposicional? ¿Existen reglas de reescritura adicionales o significativamente más sencillas para alguna clase de enunciados?
• El operador en sí es contraintuitivo, YMMV. Tener la declaración verdadera en caso de que el primer operando no lo sea, no parece correcto o necesario en absoluto. ¿Qué me falta?

Espero que la pregunta en sí no sea demasiado vaga. Me he topado con estos bloqueos en la comprensión de la lógica y no he encontrado respuestas en mucho tiempo.

Answer 1

El operador parece contradictorio, pero capta correctamente lo que queremos decir con "si" en muchos casos. Por ejemplo, "Si nos quedamos sin leche, entonces iré a la tienda" no quiere decir que no vaya a ir a la tienda de todas formas si tenemos mucha leche: puede que nos quedemos sin huevos. Para un ejemplo más matemático, "si $p$ es un primo mayor que $2$ entonces $p$ no es par" no está haciendo ninguna afirmación sobre la paridad de los no-primos. Es cierto que hay muchos casos en los que no quieren esta interpretación; "si digo 'corre', corre" parece significar que no debes correr si yo no te lo digo. Pero el formalismo de la lógica proposicional no nos permite cambiar la interpretación de una conectiva por el contexto, así que tuvimos que elegir una. La que se eligió, por convención, es la primera interpretación.

En cuanto a por qué lo usamos: es cierto que no es necesario. Pero también, $\vee$ tampoco es necesario; por las leyes de DeMorgan podemos conformarnos con $\wedge$ y $\neg$ . Pero los símbolos adicionales como $\vee$ y $\to$ mejorar enormemente la claridad (el significado de $p \vee q$ por ejemplo, es mucho más fácil de entender que $\neg(\neg p \wedge \neg q)$ ). También nos permiten utilizar nuevas reglas de inferencia o equivalencias - las reglas que rigen $\vee$ y $\to$ son consecuencias de las normas para $\wedge$ y $\neg$ pero es mucho más fácil utilizar (por ejemplo) el modus ponens en lugar de una enorme cadena de reglas sobre negaciones y disyunciones.

Así que, para reiterar: $\to$ no es en absoluto necesario, pero mejora la claridad y hace que las pruebas sean mucho más cómodas.

Answer 2

Esta es una pregunta sorprendentemente interesante. Creo que parte de la razón de la confusión es que la lógica proposicional es una especie de bestia de dos cabezas:

• Por un lado, es un sistema de cálculo con los valores de verdad "sí" y "no", lógica digital, etc. En este uso es también el ejemplo prototípico de un Álgebra booleana (que debería ser una palabra familiar para alguien que viene del software).

• Por otro lado, la lógica proposicional es comúnmente enseñada en los textos de lógica matemática con el único propósito de ser una trampolín didáctico hacia un sistema de pruebas para lógica de predicados que es lo que interesa a los lógicos matemáticos para formalizar las pruebas en las matemáticas convencionales.

Resulta que en el primero de estos usos de la lógica proposicional, apenas se ve un $\to$ . A estos efectos, $\land$ y $\lor$ y $\neg$ (así como, en algunos casos, XOR, NAND, NOR ...) nos sirven bastante bien.

Donde sí se ve $\to$ es en los textos de lógica que se escriben con el motivo ulterior de introducir cuantificadores más adelante. Esto se debe a que $\to$ está diseñado básicamente para ser útil junto con un cuantificador : Podemos expresar, por ejemplo

Todos los perros son mamíferos

simbólicamente como $$ \forall x(\mathit{dog}(x) \to \mathit{mammal}(x)) $$

En este contexto particular, el $\to$ tiene más sentido; junto con $\forall$ forma parte de un equipo que expresa que si estamos ante un perro, entonces implícitamente también estamos ante un mamífero.

Es técnicamente conveniente dividir el "todo A es B" en una parte -- la $\forall$ -- que se trata de hacer afirmaciones universales en general y una parte la $\to$ -- que ayuda a formular esto particular tipo de reivindicación universal.

Una vez que tenemos $\forall x$ que nos permita expresar afirmaciones sobre más de una cosa (quizás una infinidad de cosas) a la vez, lo que necesitamos para llegar hasta "todos los perros son mamíferos" es expresar: No importa lo que estés mirando, será o un perro y un mamífero, o un mamífero que no es un perro, o algo que no es ni un perro ni un mamífero. Si y sólo si es cierto para todo en el mundo que entra en una de esas tres clases, entonces es cierto en general que todos los perros son mamíferos.

La tabla de verdad para $\to$ es entonces lo que recoge este potencial-propiedad-de-todo en un único reclamo uniforme para cada $x$ que podemos aplicar nuestro $\forall$ a.

El desventaja de esta división es sólo que hace irresistible para los autores de libros de texto presentar una avalancha de reglas y ejercicios para este nuevo y bonito conectivo antes de introducen el $\forall$ -- pero antes tenemos $\forall$ no hay una motivación realmente buena de cómo $\to$ y los intentos de explicarlo suelen acabar en humo y espejos lingüísticos, en el mejor de los casos, o en argumentos descarados de autoridad, en el peor.

En resumen: Una vez que se pone el $\to$ por debajo de un $\forall$ tiene mucho sentido. Si usted no tienen una $\forall$ alrededor del $\to$ El significado a menudo acaba siendo contraintuitivo y sólo puede entenderse si se acepta que ésta es la tabla de verdad que queremos.

Considere, por ejemplo, el paradoja del bebedor :

$$ \exists x( p(x)\to\forall x(p(x)) $$

que es lógicamente válido según las reglas de prueba y la semántica oficial de la lógica de predicados, pero no tiene mucho sentido intuitivo porque el $\to$ ha sido escrito bajo un $\exists$ en lugar de bajo un $\forall$ .

---

Para completar, debo mencionar que hay algunas aplicaciones de la lógica proposicional a posteriori que no entran en ninguna de las dos grandes categorías anteriores. Un ejemplo destacado es la Correspondencia Curry-Howard entre los sistemas de prueba para el cálculo proposicional (en particular para lógica intuicionista ) y sistemas de tipo para los lenguajes de programación funcional. Aquí el $\to$ La conectiva adquiere una importancia fundamental -aunque los cuantificadores rara vez están presentes- es lo que resulta corresponder a tipos de funciones en el lado del sistema de tipos.

Answer 3

Es interesante que diga que le resulta "intuitivamente claro" que:

$p \rightarrow q \equiv \neg p \lor q$

pero también dices que "tener la declaración verdadera cuando el primer operando no lo es no parece correcto

desde $\neg p \lor q$ es verdadera siempre que $p$ no lo es.

De todos modos, aquí hay más reglas de equivalencia para el condicional:

$\neg (p \rightarrow q) \equiv p \land \neg q$ (Implicación de la negación)

$p \rightarrow q \equiv \neg q \rightarrow \neg p$ (Contraposición)

$p \rightarrow (q \rightarrow r) \equiv (p \land q) \rightarrow r$ (Exportación)

$p \rightarrow (q \land r) \equiv (p \rightarrow q) \land (p \rightarrow r)$ (izquierda Distribución $\rightarrow$ en $\land$ )

$(p \lor q) \rightarrow r \equiv (p \rightarrow r) \land (q \rightarrow r)$ (correcta "distribución" ... Pero no realmente ya que el $\lor$ se convierte en $\land$ )