Logica 13-14

Logica 13-14

Lezione 17

15 Nov 2013

Ancora alberi di refutazione

• Guardiamo insieme la soluzione all'es. 3.4

(10), p. 92 fornita da Varzi et al. nel file con le soluzioni agli esercizi supplementari (una

studentessa non era convinta su un punto)

Ancora alberi di refutazione (ii)

• Riguardiamo insieme il metodo applicato al caso di una singola fbf. Dice Varzi:

• si può cominciare con una lista costituita da un’unica formula. Se il risultato è un albero terminato che non contiene nessun

cammino aperto, allora la formula è contraddittoria;

• se invece il risultato è un albero che contiene uno o più cammini aperti, allora la formula è tautologica oppure vero-

funzionalmente contingente.

• D’altra parte, è evidente che una fbf è tautologica se e solo se la sua negazione è vero-funzionalmente inconsistente, visto che il connettivo di negazione inverte tutti i valori della formula negata.

• Quindi la tecnica degli alberi di refutazione ci consente anche di decidere se una fbf è

tautologica ovvero contingente: basta

costruire un albero per la sua negazione. In

breve:

• (1) Una formula  è inconsistente se e solo se tutti i cammini di un albero terminato per  sono chiusi.

• (2) Una formula  è tautologica se e solo se tutti i cammini di un albero terminato per  sono chiusi.

• (3) Una formula  è vero-funzionalmente contingente se e solo se  non è né tautologica né inconsistente.

• QUI VARZI CONFONDE UN PO' LE IDEE, PERCHE' CI AVEVA APPENA SUGGERITO DI PRENDERE IN

CONSIDERAZIONE LA NEGAZIONE DELLA FORMULA DA

VALUTARE.

• Quindi meglio dire:

• Per scoprire lo statuto di una formula , costruire un albero per  e procedere così:

• (a) se tutti i cammini di un albero terminato per  sono chiusi, considerare  tautologica.

• (b) Se non è venuto fuori che  è tautologica, costruire un albero per  e decidere così:

• (b1) se tutti i cammini si chiudono,  è inconsistente

• (b2) se qualche cammino rimane aperto,  è contigente.

Esempio di tautologia

• P v P

• (P v P)

• P

•  P

• x

Esempio di contraddizione

• (P v P)

•  (P v P)

• (P v P)

• P P

• Abbiamo scoperto che (P v P) non è una tautologia. ora vediamo cos'è:

• (P v P)

• P

•  P

• x Contraddizione!

Esempio di contingenza

• P v Q

• (P v Q)

•  P

•  Q

A questo punto abbiamo scoperto che non è una tautologia.

Adesso consideriamo P v Q è scopriamo che è contingente:

P v Q

P Q

Introduzione della negazione (dimostrazione per assurdo)

• guardare esempi pp. 19-106:

• 4.18, 4.19, 4.20

Esempio 4.21 p. 106

• Questo esempio, oltre a mostrare l'uso della regola di intro della negazione, illustra una strategia:

• se abbiamo a disposizione una disgiunzione, tipicamente è utile cercare di dimostrare che entrambi i disgiunti implicano la conclusione desiderata.

• In questo caso, cerchiamo di ottenere questa

conclusione con la regola di intro della neg.