Lògica proposicional

Aquesta és la lògica de predicats d'ordre zero (LP0), i treballa amb conceptes senzills que són certs o falsos (plou, fa sol, etc.). A la d'ordre 1 ja hi apareixen variables (``el dia $x$ hi plou'', ``el dia $x$ plou a la comarca $y$'', etc.), i a la d'ordre 2 hi apareixen variables i predicats (``tot fenomen meteorològic $f$ dels anteriorment esmentats té un dia $x$ a on ocorre'').

Com que a LP0 no hi ha variables, tampoc fan falta els quantificadors. La seva sintaxi és molt senzilla: [Sal98, p 3]

1. Tot àtom ($P$, $Q$, $R$, $S$, ...) és una fórmula ben formada.
2. Si $A$ és una fórmula ben formada, $\neg A$ també ho és.
3. Si $A$ i $B$ són fórmules ben formades, també ho són $(A\wedge B)$, $(A\vee B)$ i $(A\Rightarrow B)$.
4. No hi ha més fórmules.

A més, permet fer raonaments de forma fàcil, amb la deducció natural (explicació a [Cle04]). Per exemple, aquí ve la demostració de $\neg A\vee B\vdash A\Rightarrow B$, que és un cas 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ó natural intenta reproduir la manera de raonar que tenim els humans. Inclou les operacions lògiques més antigues, com la reducció a l'absurd, ja usada per Pitàgores 5 segles aC. a la demostració de la irracionalitat de $\sqrt{2}$ (molt abans que Aristòtil pensés la seva lògica de termes).

Encara que feta pels humans des de fa temps, va ser formalitzada als anys 1930. Jan Lukasiewicz ⁴ va suggerir la idea al 1926, i Jaskowsky va fer un intent (sense molt èxit) al 1929, usant diagrames. Va ser l'alemany Gerard Gentzen (1909-1945) qui al 1935 i a Göttingen va introduir el primer model funcional. [WP]. Però el model de Gentzen era una mica complex, i -per sort- Fitch va inventar (al 1944) una notació més senzilla, que és la que apareix al diagrama de dalt.

La majoria de raonaments dels quals les persones discutim habitualment poden ser escrits sense molts problemes amb lògica proposicional i ser demostrats amb deducció natural. Refutar arguments és més complicat: es pot fer per resolució, però com que no s'assembla molt al nostre llenguatge natural ni forma de pensar, el que fem habitualment és utilitzar l'argument a refutar com a hipòtesi, inventar alguna cosa que depengui d'aquest, i intentar arribar a una contradicció (per tant, reductio ad absurdum).

El problema que podem trobar és que la lògica proposicional no és molt expressiva si volem parlar de relacions. Per exemple, es pot formalitzar ``si Peano té raó però Quine no, llavors Russell tampoc'' com $P\wedge\neg Q\Rightarrow\neg R$. Però quan volem dir ``si Peano és amic de Quine, i Quine de Russell, llavors Peano és amic de Russell'' ja necessitem la lògica de primer ordre: $Apq\wedge Aqr\Rightarrow Apr$.