Lógica proposicional

Ésta es la lógica de predicados de orden cero (LP0), y trabaja con conceptos sencillos que son ciertos o falsos (llueve, hace sol, etc.). En la de orden 1 ya aparecen variables (``el día $x$ llueve'', ``el día $x$ llueve en la comarca $y$'', etc.), y en la de orden 2 aparecen variables y predicados (``todo fenómeno meteorológico $f$ de los anteriormente mencionados tiene un día $x$ en el que ocurre'').

Como en LP0 no hay variables, tampoco hacen falta los cuantificadores. Su sintaxis es muy sencilla: [Sal98, p 3]

1. Todo átomo ($P$, $Q$, $R$, $S$, ...) es una fórmula bien formada.
2. Si $A$ es una fórmula bien formada, $\neg A$ también lo es.
3. Si $A$ y $B$ son fórmulas bien formadas, también lo son $(A\wedge B)$, $(A\vee B)$ y $(A\Rightarrow B)$.
4. No hay más fórmulas.

Además, permite hacer razonamientos de forma fácil, con la deducción natural (explicación en [Cle04]). Por ejemplo, aquí va la demostración de $\neg A\vee B\vdash A\Rightarrow B$, que es un caso no tan trivial (ni tan natural):

$$\begin{fitch} \par \neg A \vee B \ \par \fh A & H \ \par ... ... \par A \Rightarrow B & I$\Rightarrow$ 2,11 \par \end{fitch}$$

La deducción natural intenta reproducir la manera de razonar que tenemos los humanos. Incluye las operaciones lógicas más antiguas, como la reducción al absurdo, ya usada por Pitágoras 5 siglos aC. en la demostración de la irracionalidad de $\sqrt{2}$ (mucho antes que Aristóteles pensase su lógica de términos).

Aunque creada por los humanos desde hacía tiempo, fue formalizada en los años 1930. Jan Lukasiewicz ⁴ sugirió la idea en 1926, y Jaskowsky hizo un intento (sin mucho éxito) el 1929, usando diagramas. Fue el alemán Gerard Gentzen (1909-1945) que en 1935 y en Göttingen introdujo el primer modelo funcional. [WP]. Pero el modelo de Gentzen era un poco complicado, y -por suerte- Fitch inventó (en 1944) una notación más sencilla, que es la que aparece en el diagrama de arriba.

La mayoría de razonamientos de los que las personas discutimos habitualmente pueden ser escritos sin muchos problemas con lógica proposicional y ser demostrados con deducción natural. Refutar argumentos es más complicado: se puede hacer por resolución, pero como no se parece mucho a nuestro lenguaje natural ni forma de pensar, lo que hacemos habitualmente es usar el argumento a refutar como hipótesis, inventar alguna cosa que dependa de éste, e intentar llegar a una contradicción (por tanto, reductio ad absurdum).

El problema que podemos encontrar es que la lógica proposicional no es muy expresiva si queremos hablar de relaciones. Por ejemplo, se puede formalizar ``si Peano tiene razón pero Quine no, entonces Russell tampoco'' como $P\wedge\neg Q\Rightarrow\neg R$. Pero cuando queremos decir ``si Peano es amigo de Quine, y Quine de Russell, entonces Peano es amigo de Russell'' ya necesitamos la lógica de primer orden: $Apq\wedge Aqr\Rightarrow Apr$.