Note di Logica Matematica n.3

Claudia Malvenuto e Roberto Maieli^{∗} (canale E-O - a.a. 2002-2003)

5 dicembre 2002

Indice

1 La concezione classica delle dimostrazioni 1

2 La dualità tra dimostrazione e refutazione 2

3 Regole per i principali connettivi della logica classica 3 3.1 Regole della congiunzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.2 Regole della disgiunzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.3 Regole dell’implicazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

4 Esercizi 7

1 La concezione classica delle dimostrazioni

La logica classica stabilisce cosa si deve intendere per dimostrazione (o prova) di una proposizione e cosa si deve intendere per refutazione (o controprova) di una proposizione. Nella logica classica:

• una dimostrazione di una proposizione A è un processo che ci permette di concludere (o conoscere) che la proposizione A è vera;

• una refutazione di una proposizione A è un processo che ci permette di concludere (o conoscere) che la propoizione A è falsa;

Una dimostrazione D di una proposizione A (detta conclusione o tesi) da una proposizione B (detta premessa o ipotesi)

B (ipotesi) ; ⋮ ; A (tesi)

è un processo che permette di :

• trasformare ogni dimostrazione di B in una dimostrazione di A;

• trasformare ogni refutazione di A in una refutazione di B.

Una dimostrazione di una proposizione A (conclusione) da una proposizione B (premessa) è qualcosa che permette di

• passare dalla verità della ipotesi B alla verità della conclusione B,

∗Dipartimento di Informatica, Università di Roma “La Sapienza”, Via Salaria, 113. E-mail: claudia, maieli@dsi.uniroma1.it.

• passare dalla falsità della conclusione A alla falsità dell’ipotesi B.

È in questo senso che si usa dire che in logica classica una dimostrazione di una proposizione A (conclusione, tesi) da una proposizione B (premessa, ipotesi)

• dall’alto (ipotesi) verso il basso (conclusione) preserva la verità (dunque, se B è vera allora anche A deve essere vera);

• dal basso (conclusione) verso l’alto (ipotesi) preserva la falsità (se assumiamo che la conclusione è falsa allora anche l’ipotesi B deve essere falsa).

Si osservi che data una dimostrazione D di A da B allora:

• se abbiamo una refutazione di B (ossia, se sappiamo che la premessa B è falsa) allora la dimostrazione data non ci permette di avere alcuna informazione sul valore (vero/falso) della conclusione A;

• se, invece, abbiamo una dimostrazione di A (ossia se sappiamo che la conclusione è vera) allora la dimostrazione data non ci permette di avere alcuna informazione sul valore dell’ipotesi B.

2 La dualità tra dimostrazione e refutazione

La logica classica esige che per ogni proposizione A :

• esista una proposizione chiamata negazione di A, ed indicata con ¬A;

• la negazione della negazione di A sia A stessa (quindi, ¬¬A = A).

La negazione classica permette di stabilire una dualità tra la dimostrazione e la refutazione di una proposizione. Questa dualità ci permette di fare a meno delle dimostrazioni o delle refutazioni. Infatti per qualunque proposizione A

• ogni refutazione di A è un processo che permette di stabilire che il valore di A è il falso, e quindi permette di stabilire che il valore di ¬A è vero, e quindi è una dimostrazione di ¬A;

• una dimostrazione di ¬A è un processo che ci permette di stabilire che il valore di verità di ¬A è V, e quindi il valore di verità di A è F ed è quindi una refutazione di A.

Analogamente, per qualunque proposizione A:

• ogni dimostrazione di A è una refutazione di ¬A;

• ogni refutazione di ¬A è una dimostrazione di A.

Dunque possiamo solo usare uno dei due concetti, quello di dimostrazione o quello di refutazione. Potremmo, ad esempio, usare solo il concetto di dimostrazione e fare a meno del concetto di refutazione, poichè la refutazione di una proposizione A equivale ad una dimostrazione di ¬A. Viceversa, potremmo solo usare il concetto di refutazione e fare a meno del concetto di dimostrazione, poichè ogni dimostrazione di A equivale ad una refutazione di ¬A. Il metodo (“semantico”) dei tableaux sfrutta questo secondo approccio allo studio della dimostrabilità in logica classica.

La negazione classica permette altresì di esprimere la dualità esistente tra dimostrazioni e refutazioni da ipotesi nel modo seguente:

• ogni dimostrazione di una proposizione A da una proposizione B è una dimostrazione della proposizione ¬B dalla proposizione ¬A (o equivalentemente una refutazione di B ottenuta da una refutazione di A)^{1}; • ogni dimostrazione di una proposizione ¬B da una proposizione ¬A è una dimostrazione di A da

1Una dimostrazione di A da B, letta dal basso verso l’alto, fa passare dalla falsità di A (refutazione di A) alla falsità di B (refutazione di B); letta dall’alto verso il basso fa passare dalla verità di B alla verità di A.

B (o equivalentemente, una refutazione di ¬A ottenuta da una refutazione di ¬B)^{2}

A_{1}, ..., A_{n}

3 Regole per i principali connettivi della logica classica

La logica, secondo l’interpretazione vero-funzionale, stabilisce quando, date due proposizioni A e B, il nuovo composto A∘B ottenuto mettendo assieme in una qualche maniera A e B, è una proposizione. Una volta appurato che il composto A ∘ B è una proposizione possiamo porci le seguenti questioni naturali:

1. quando posso dimostare (stabilire la verità di) A ∘ B ?

2. quando posso confutare (stabilire la falsità di) di A ∘ B (o equivalentemente, stabilire la verità di¬(A ∘ B)) ?

3. cosa posso concludere da una dimostrazione di A ∘ B (o equivalentemente, da una confutazione di A ∘ B) ?

Le risposte a queste domande conducono alle regole logiche. Queste possono essere, grosso modo, classificate in regole di introduzione di un connettivo (risposte al punto 1 e 2) e in regole di eliminazione di un connettivo (risposta al punto 3).

3.1 Regole della congiunzione

Definiamo le regole della congiunzione ∧. Ricordiamo per comodità che secondo l’interpretazione booleana (o vero-funzionale) la congiunzione di due formule A∧B ha valore Vero solo quando entrambi i componenti A, B hanno valore Vero. Data una dimostrazione di A ed una dimostrazione di B possiamo concludere la verità della conclusione A ∧ B:

A ∧ B^{D_{1} ; ⋮ ; A D_{2} ; ⋮ ; B}

Queste regola è corretta; essa, letta dall’alto (le foglie dell’albero) verso il basso (la radice) infatti preserva la verità dalle premesse alla conclusione, nel senso che non si dà mai il caso che le premesse siano vere e la conclusione sia falsa. Viceversa, letta dal basso verso l’alto tale regola preserva la falsità nel senso che tutte le volte che si ha una refutazione della conclusione (o equivalentemente una dimostrazione di ¬(A∧B)) si ottiene pure una renfutazione di almeno una delle due premesse (quindi ¬A oppure ¬B deve essere vera):

D ; ⋮ ; ¬(A ∧ B) ; \begin{aligned}¬A \\ & ¬B \end{aligned}

2Una dimostrazione di ¬B da ¬A, letta dal basso verso l’alto fa passare dalla falsità (refutazione) di ¬B alla falsità (refutazione) di ¬A, letta dall’alto verso il basso fa passare dalla verità di ¬A alla verità di ¬B.

Si osservi che nel primo caso, nella lettura dall’alto verso il basso i due rami dell’albero sono “legati da una congiunzione”, il che vuol dire che entrambe le premesse devono essere vere, mentre nel caso della lettura rovesciata dell’albero, i due rami verso il basso sono legati da una disgiunzione, ed è sufficiente assumere uno dei due rami vero. Viceversa, per stabilire o dimostrare la verità di ¬(A ∧ B) è sufficiente avere una dimostrazione di ¬A o una dimostrazione di ¬B :

¬(A ∧ B) D_{1} ; ⋮ ; ¬A  ¬(A ∧ B) D_{2} ; ⋮ ; ¬B

Entrambe le regole sono corrette: esse infatti, lette dall’alto verso il basso, preservano la verità, mentre lette dal basso verso l’alto, ciascuna delle due regole appena enunciate preserva la falsità nel senso che se ho una refutazione di ¬(A ∧ B) (o equivalentemente ho una dimostrazione di A ∧ B) allora posso concludere con una refutazione di ¬A e ¬B, o equivalentemente con una dimostrazione di A e B :

D ; ⋮ ; A ∧ B ; A, B

3.2 Regole della disgiunzione

Ricordiamo per comodità che secondo l’interpretazione vero-funzionale, la disgiunzione di due formule A ∨ B ha valore Falso solo nel caso in cui entrambi i componenti A e B hanno valore Falso; in tutti gli altri casi la disgiunzione di due formule ha valore Vero. Tutte le volte che si ha una dimostrazione di A o una dimostrazione di B si può derivare A ∨ B

D ; ⋮ ; A ; A ∨ B  D ; ⋮ ; B ; A ∨ B

La regola è corretta; tutte le volte che A (rispettivamente B) è vera allora anche A ∨ B sarà vera. Letta dal basso verso l’alto tale regola preserva la falsità, nel senso che tutte le volte che ho una refutazione di A ∨ B (quindi una dimostrazione di ¬(A ∨ B)) avrò anche una refutazione di A e B (quindi una dimostrazione di ¬A e ¬B):

D ; ⋮ ; ¬(A ∨ B) ; ¬A, ¬B

Viceversa, se ho una dimostrazione di ¬A e una dimostrazione di ¬B posso concludere con una dimostrazione di ¬(A ∨ B):

¬(A ∨ B))^{D_{1} ; ⋮ ; ¬A D_{2} ; ⋮ ; ¬B}

La regola è corretta: infatti non si dà il caso che entrambe le premesse siano vere e la conclusione falsa. Letta dal basso (conclusione ¬(A ∨ B)) verso l’alto (premesse ¬A, ¬B) la regola preserva la falsità, nel senso che tutte le volte che ho una refutazione di ¬(A ∨ B) (e quindi una dimostrazione di A ∨ B) allora avrò anche una refutazione di almeno una delle due premesse, e quindi A oppure B sarà vera:

D ; ⋮ ; A ∨ B ; \begin{aligned}A \\ & B \end{aligned}

Inoltre tutte le volte che ho una dimostrazione di A ∨ B e una dimostrazione di ¬A (rispettivamente una dimostrazione di ¬B) avrò anche una dimostrazione di B:

B^{D_{1} ; ⋮ ; ¬A D_{2} ; ⋮ ; A ∨ B}  A^{D_{1} ; ⋮ ; ¬B D_{2} ; ⋮ ; A ∨ B}

3.3 Regole dell’implicazione

Secondo l’interpretazione vero-funzionale del connettivo →, l’implicazione A → B assume valore Falso solo nel caso in cui l’antecedente A assuma valore Vero e il conseguente B assuma valore Falso. In tutti gli altri casi l’implicazione ha valore falso. Tutte le volte che ho una dimostrazione di ¬A o una dimostrazione di B oppure una dimostrazione di B a partire da A, allora posso concludere che A → B è vera (dimostrabile):

D ; ⋮ ; ¬A ; A → B  D ; ⋮ ; B ; A → B  A ; ⋮ ; B ; A → B

Le regole sono corrette e, lette dall’alto verso il basso, preservano la verità dalle premesse alla conclusione, nel senso che non si dà il caso che le premesse siano corrette e la conclusione falsa. Lette dal basso verso l’alto le regole preservano la falsità, nel senso che tutte le volte che abbiamo una refutazione di A → B (o equivalentemente una dimostrazione di ¬(A → B)) abbiamo anche una refutazione contemporaneamente di ¬A (quindi una dimostrazione di A) e di B (quindi una dimostrazione di A e ¬B):

D ; ⋮ ; ¬(A → B) ; A, ¬B

Viceversa posso dimostrare la negazione di una implicazione ¬(A → B) tutte le volte che ho una dimostrazione di A ed una dimostrazione di ¬B:

¬(A → B)^{D_{1} ; ⋮ ; A D_{2} ; ⋮ ; ¬B}

La regola è corretta, infatti dall’alto in basso preserva la verità dalle premesse alla conclusione, quindi non si dà il caso che le premesse siano entrambe vere e la conclusione falsa. Viceversa dal basso verso l’alto preserva la falsità, nel senso che se la conclusione è falsa, e quindi se ho una refutazione di ¬(A → B) (cioè una dimostrazione di A → B) allora alemno una delle due premesse A oppure ¬B sarà falsa (quindi ¬A oppure B sarà vera):

D ; ⋮ ; A → B ; \begin{aligned}¬A \\ & B \end{aligned}

Infine consideriamo due regole molto importanti in logica e alla base di molte dimostrazioni in logica e matematica:

• la regola del modus ponens: data una dimostrazione di A → B ed una dimostrazione di A allora posso concludere che B è vera:

B^{D_{1} ; ⋮ ; A → B D_{2} ; ⋮ ; A}

Si verifica facilmente che la regola è corretta.

• La regola del modus tollens permette di confutare A, e quindi di dimostrare ¬A a partire da una dimostrazione di A → B e da una dimostrazione di ¬B:

¬A^{D_{1} ; ⋮ ; A → B D_{2} ; ⋮ ; ¬B}

La regola è corretta, essa preserva la verità dalle premesse alla conclusione.

Un insieme di regole logiche forma in generale un sistema di dimostrazione (o di refutazione). Grosso modo un sistema di dimostrazione che usa regole di introduzione è detto sistema di deduzione^{3}. Viceversa un sistema che usi solo regole di eliminazione è spesso detto sistema di refutazione^{4}

3In generale un sistema deduttivo può presentare sia regole di introduzione che regole di eliminazione per un connettivo.

Ad esempio il Calcolo dei Sequenti di Gentzen (a due parti) (1936) presenta sia regole di eliminazione che regole di introduzione. In realtà si mostra facilmente che ci si può limitare ad usare un calcolo equivalente che faccia uso solo di regole di introduzione. Per un approfondimento di queste questioni il lettore può consulatare il testo di Szabo, “Collected papers of Gherard Gentzen”, North Holland.

4Il metodo dei tableaux (anni ’70) è un esempio di sistema di refutazione (per i dettagli il lettore può consultare il testo di Ben-Ari, “Mathematical Logic for Computer Science”, Prentice Hall).

4 Esercizi

Stabilire quali tra le seguenti regole sono corrette e quali no^{5} ? Si ricordi che una regola R con premesse P_{1}, ..., P_{n} e conclusione P è corretta se e solo se {P_{1}, ..., P_{n}} ⊧ P, che equivale a dire, per la definizione di validità e l’equivalenza logica, ⊧ (P_{1} ∧P_{2} ∧...∧P_{n}) → P, se e solo se, per il teorema di validità, ¬((P_{1} ∧P_{2} ∧...∧P_{n}) → P) è insoddisfacibile, se e solo se, per la completezza e correttezza del metodo dei tableaux, esiste un tableau chiuso per ¬((P_{1} ∧ P_{2} ∧ ... ∧ P_{n}) → P), il che equivale a dire che tutti i rami del tableau la cui radice è etichettata con {P_{1}, P_{2}, ..., P_{n}, ¬P } chiudono.

1. :

\begin{matrix}A \\ A ⊕ B \end{matrix}

2. :

\begin{aligned}A → B & A → ¬B \\ & ¬A \end{aligned}

3. :

\begin{matrix}A → B \\ ¬(A ∧ ¬B) \end{matrix}  {¬(A ∧ ¬B) \atop A → B}

4. :

\begin{matrix}A → B \\ ¬A ∨ B \end{matrix}  {¬A ∨ B \atop A → B}

5. :

\begin{matrix}A ∧ B \\ ¬(A → ¬B) \end{matrix}  {¬(A → ¬B) \atop A ∧ B}

6. :

\begin{matrix}A ∨ B \\ ¬A → B \end{matrix}  {¬A → B \atop A ∨ B}

7. :

\begin{matrix}A → (B → C) & A → B \\ A → C \end{matrix}

8. :

\begin{matrix}A → C & B → C \\ (¬A → B) → C \end{matrix}

9. :

\begin{aligned}A ∨ B & C → ¬B \\ & C → A \end{aligned}

accettata) :

\begin{aligned}P_{1} & ... & P_{n} \\ & P \end{aligned}

5Per semplicità, una regola con premesse P_{1}, ⋯, P_{n} e conclusione P sarà espressa nella seguente forma compatta, usata per la prima volta da Gentzen per indicare le regole del calcolo dei sequenti (oggi è considerata la notazione standard