Un metodo analitico per i tableau

Il metodo per i tableau descritto in questo articolo è stato teorizzato dal gruppo di lavoro di Raymond Smullyan dell’Indiana University.
Si tratta di un metodo analitico che il gruppo di Smullyan applica alla logica proposizionale.

I simboli utilizzati

Se non hai familiarità con i simboli della logica, gli unici simboli qui utilizzati sono:
\(\wedge\) che rappresenta l’AND logico, in altre parole la congiunzione.
\(\vee\) che rappresenta l’OR logico, cioè la disgiunzione.
\(\supset\) che significa “implica”.
\(\neg\) rappresenta la negazione.

Le regole di inferenza

Il metodo di Smullyan si basa su un insieme di otto regole, che vengono poi applicate nella risoluzione del tableaux.

  1. a. Se \(\neg X\) è vero, X è falso (principio di non contraddizione)
    b. Se \(\neg X\) è falso, X è vero (idem)
  2. a. Se una congiunzione \(X \wedge Y\) è vera,  lo sono anche X e Y
    b. Se una congiunzione \(X \wedge Y\) è falsa, o X è falso o Y è falso
  3. a. Se una disgiunzione \(X \vee Y\) è vera, o X è vero o Y è vero
    b. Se una disgiunzione \(X \vee Y\) è falsa, X è falso e Y è falso
  4. a. Se \(X \supset Y\) è vera,  o X è falso o Y è vero
    b. Se \(X \supset Y\) è falsa,  X  è vero  e Y è falso

Un esempio per comprendere il punto 4:
a. Per andare sul Cervino (X) devo essere allenato (Y) ( \(X \supset Y\)),
se il mio andare sul Cervino implica che devo essere allenato, o sono allenato (quindi Y è vero) oppure non vado sul Cervino (quindi X è falso)
b. Se è falso che per andare sul Cervino  (X) devo essere allenato , allora per andare sul Cervino (X è vero) non mi devo allenare (Y è falso)

Formule con Segno: a questo punto vengono introdotti da Smullyan i simboli T e F (true e false) e viene definita una formula TX o FX (dotate di segno) alla variabile X, priva di segno.

Esempio di tableaux

Supponiamo di voler provare la formula \([p \vee (q \wedge r) ]\supset [(p \vee q) \wedge (p\vee r)]\)

Quello seguente è il tableau che, applicando le regole di inferenza, fornisce la dimostrazione:

Tableau metodo analitico

Spiegazione

Poniamo come falso l’enunciato da dimostrare (dimostrazione per assurdo): (1) \(F[p \vee (q \wedge r) ]\supset [(p \vee q) \wedge (p\vee r)]\) e vediamo se ne ricaviamo una contraddizione. La nostra prima linea sarà quindi costituita dall’enunciato preceduto da una F.
Ora, una formula della forma \(X \supset Y\) può essere falsa solo se X è vero e Y è falso. Ad esempio se andare in montagna (X) implica l’essere allenato (Y), se X è vera e Y è falsa  l’enunciato \(X \supset Y\)  risulterà falso.
Quindi, TX e FX sono conseguenze dirette della formula \(F(X \supset Y)\). In (2) scriveremo quindi  \(Tp \vee (q \wedge r) \) e in (3)  \(F (p \vee q) \wedge (p\vee r)\) come dirette conseguenze di (1).
Ora, osservando (2) notiamo che è enunciato nella formula \(T(X \vee Y)\)  (dove \(X=p\) e \(Y=(q  \wedge r)\)).
Non possiamo a questo punto concludere in maniera diretta sul valore di verità di X o Y. Possiamo solo inferire che o TX o TY sono vere.
Quindi il tableau dirama in due colonne (4) e (5): una per ogni possibilità.
A questo punto da 5 (\(T(q \vee r)\)) si traggono le dirette conseguenze (6) e (7): \(Tq\) e \(Tr\).
Ora, se osserviamo 3 notiamo che è nella forma \(F(X \vee Y)\), che significa che o FX o FY. Sappiamo anche che o (4) o (5) si conserva.
Quindi, sia per (4) che per (5) diramiamo in FX e FY, Il ramo quattro dirama in (8) e (9), il ramo 5 in (10) e (11).
(8) avrà come conseguenze dirette \(Fp\) (12) e (\(Fq\) (13)
(9) avrà come conseguenze dirette \(Fp\) (14) e (\(Fr\) (15)
(10) avrà come conseguenze dirette \(Fp\) (16) e (\(Fq\) (17)
(11) avrà come conseguenze dirette \(Fp\) (18) e (\(Fr\) (19)
Ora, osservando il tableau, notiamo che (4) è in contraddizione con (12), quindi escludiamo la diramazione con una X sulla base della regola di inferenza 1.
Rileviamo anche che (4) è in contraddizione con (14) e sempre in base al principio di non contraddizione escludiamo la diramazione ponendovi una X al termine.
(6) è in contraddizione con (17) e (7) è in contraddizione con (19), quindi escludiamo con una X anche queste ultime due diramazioni.
Ne consegue che \(F[p \vee (q \wedge r) ]\supset [(p \vee q) \wedge (p\vee r)]\) è insostenibile, quindi \([p \vee (q \wedge r) ]\supset [(p \vee q) \wedge (p\vee r)]\) non può essere falsa in alcuna situazione.
Avendo dimostrato che non può essere falsa, allora deve essere vera.

Bibliografia

Raymond Smullyan, First Order Logic, Dover Publications, disponibile solo in inglese.

Nota
Il professor Smullyan è autore di molti libri interessanti.
Anni fa avevo allestito un libretto con un suo dialogo molto bello e divertente intitolato “Dio è taoista?”. Puoi scaricare il libretto facendo click qui.
Il dialogo si trova nell’antologia di Hofstadter-Dennett intitolata l’Io della Mente (Adelphi), grande libro!

W Raymond Smullyan su Wikipedia Italiana

Raymond Smullyan
Raymond Smullyan (New York, 25 Maggio 1919)