Unit 2 – Corso di Logica e Teoria dell’Argomentazione

Calcolo proposizionale

Unit 2 – Corso di Logica e Teoria dell’Argomentazione

Sommario

• Proprietà del calcolo proposizionale• Regole di inferenza ipotetiche e non• Regole derivate• Teoremi• Equivalenze

Natura formale

• Finora: logica proposizionale e la nozione di validità sono state trattate in modo statico, attraverso la loro semantica (tavole di verità, interpretazioni)

• Ma le inferenze logiche sono dinamiche: come rendiamo conto della logica come motore inferenziale?

• Il calcolo proposizionale è una costruzione formale a sé stante, in cui l’interpretazione è secondaria (interviene solo successivamente e come aggiunta esterna)

Un altro metodo: le derivazioni

• Le nozioni semantiche non sembrano necessarie. Esistono altri metodi usando solo la struttura linguistica proposizionale?

• Nuovo metodo (introdotto da G. Gentzen): per dimostrare se una forma argomentativa è deduttivamente valida costruiamo una successione di passaggi inferenziali a partire dalle premesse fino alla conclusione, senza alcun riferimento al significato di ogni formula usata

Regole e calcolo

Calcolo proposizionale (o calcolo della

deduzione naturale)

Insieme di Regole di inferenza derivazione

(dimostrazione,deduzione):

sequenza di fbf, ciascuna ottenuta applicando una

regola d’inferenza

di cui esistono diverse versioni…

Dagli assiomi alla conclusione

• Le premesse sono assunte come vere, e prendono il nome di assiomi– Non vi è alcuna limitazione al numero di assiomi

• La conclusione viene ottenuta con una successione di passaggi inferenziali– Non vi sono limitazioni al numero di passaggi

inferenziali– Una derivazione può avere sotto-derivazioni

all’interno, cioè “nidificate” (che portano a dimostrare fbf intermedie)

– Le derivazioni non sono meccaniche (come le tavole di verità): occorre una discreta dose di creatività

Regole ipotetiche e non

• Regole non ipotetiche: le inferenze si basano su premesse sempre vere

• Regole ipotetiche: le inferenze passano attraverso un’ipotesi considerata momentaneamente vera (ma che può essere vera o falsa), con lo scopo di derivare cosa ciò che essa implicherebbe

Regola →E

• Regola →E (eliminazione del condizionale): da un condizionale e dal suo antecedente possiamo inferire il conseguente

f→y,f ⊢ y

• questa regola è ovvia (è il modus ponens). La sua validità è giustificata dalla tavola di verità del condizionale: se condizionale e antecedenti sono veri, è vero anche il conseguente.

f→yf:. y

Esempio

• P→Q,Q→R,P⊢R

1 P→Q A2 Q→R A3 P A4 Q 1,3 →E5 R 2,4 →E

NB: Omettiamo i tre puntini a sinistra citando righe e regola usata a giustificazione del passaggio, in tal modo indicando implicitamente che si tratta di conclusioni

Esempio

• P→(~Q→R),P,~Q⊢R

1 P→(~Q→R) A2 P A3 ~Q A4 ~Q→R 1,2 →E5 R 3,4 →E

Regola ~E

• Regola ~E (eliminazione della negazione): da un fbf della forma ~~fpossiamo inferire f

~~f ⊢ f

• La validità di questa regola è giustificata dalla tavola di verità della negazione: il valore di verità della negazione della negazione di un enunciato è lo stesso dell’enunciato stesso

~~f:. f

Esempio

• ~P→Q,~~~P⊢Q

1 ~P→Q A2 ~~~P A3 ~P 2 ~E4 Q 1,3 →E

Esempio

• P→~~Q,~~P⊢Q

1 P→~~Q A2 ~~P A3 P 2 ~E4 ~~Q 1,3 →E5 Q 4 ~E

Regola &E

• Regola &E (eliminazione della congiunzione): da una congiunzione possiamo inferire uno qualunque dei due congiunti

f&y ⊢ ff&y ⊢ y

• La validità di questa regola è giustificata dalla tavola di verità della congiunzione: se la congiunzione è vera allora, necessariamente, ogni congiunto è vero

f&y:. f

f&y:. y

Esempio

• P→(Q&R),P⊢R

1 P→(Q&R) A2 P A3 Q&R 1,2 →E4 R 3 &E

Esempio

• P→(Q&R),~~P&S⊢Q

1 P→(Q&R) A2 ~~P&S A3 ~~P 2 &E4 P 3 ~E5 (Q&R) 1,4 →E6 Q 5 &E

Regola &I

• Regola &I (introduzione della congiunzione): da due fbf Φ e Ψqualsiasi possiamo inferire Φ&Ψ

Φ,Ψ ⊢ Φ&Ψ

• La validità di questa regola è giustificata dalla tavola di verità della congiunzione: se due proposizioni sono vere la loro congiunzione è vera

Φy:. Φ&Ψ

Φy:. Ψ&Φ

Esempio

• P,Q,(P&Q)→R⊢R

1 P A2 Q A3 (P&Q)→R A4 P&Q 1,2 &I5 R 3,4 →E

Esempio

• P→Q,~R,P,(Q&~R)→(S&T)⊢S

1 P→Q A2 ~R A3 P A4 (Q&~R)→(S&T) A5 Q 1,3 →E6 Q&~R 2,5 &I7 (S&T) 4,6 →E8 S 7 &E

Regola vI

• Regola vI: (introduzione della disgiunzione): da una fbf Φ possiamo inferire la disgiunzione ΦvΨ di Φ con una fbf Ψ qualsiasi

Φ ⊢ ΦvΨ

• La validità di questa regola è giustificata dalla tavola di verità della disgiunzione: se almeno una proposizione è vera allora la loro disgiunzione è vera

Φ:. ΦvΨΦ

:. ΨvΦ

Esempio

• P→Q,P&R⊢QvS

1 P→Q A2 P&R A3 P 2 &E4 Q 1,3 →E 5 QvS 4 vI

Esempio

• P→Q,P,(Qv~R)→S⊢SvT

1 P→Q A2 P A3 (Qv~R)→S A4 Q 1,2 →E5 Qv~R 4 vI6 S 3,5 →E7 SvT 6 vI

Regola vE

• Regola vE (eliminazione della disgiunzione): dalle fbf fvy, f→c e y→cpossiamo inferire c

fvy,f→c,y→c ⊢ c

• La validità è giustificata dal fatto che, per via delle due implicazioni, il conseguente è vero se uno qualsiasi degli antecedenti è vero, dunque se la loro disgiunzione è vera

fvyf→cy→c:. c

Esempio

• PvQ,P→R,Q→R⊢RvS

1 PvQ A2 P→R A3 Q→R A4 R 1,2,3 vE5 RvS 4 vI

Esempio

• P→(Q&S),Pv~R,~R→(Q&S)⊢S

1 P→(Q&S) A2 Pv~R A3 ~R→(Q&S) A4 Q&S 1,2,3 vE5 S 4 &E

Regola ⟷E

• Regola ⟷E (eliminazione del bicondizionale): da una fbf della forma f⟷y possiamo inferire f→y o y→f

f⟷y ⊢ f→yf⟷y ⊢ y→f

• La validità di questa regola è ovvia vista l’equivalenza tra il bicondizionale e la congiunzione dei due condizionali

f⟷y:. f→y

f⟷y:. y→f

Esempio

• P⟷Q,P,Q→R⊢R

1 P⟷Q A2 P A3 Q→R A4 P→Q 1 ⟷E5 Q 2,4 →E6 R 3,5 →E

Esempio

• (P&S)⟷Q,Q,S→~R⊢~RvT

1 (P&S)⟷Q A2 Q A3 S→~R A4 Q→(P&S) 1 ⟷E 5 P&S 2,4 →E6 S 5 &E7 ~R 3,6 →E8 ~RvT 7 vI

Regola ⟷I

• Regola ⟷I (introduzione del bicondizionale): da due fbf della forma f→y e y→f possiamo inferire f⟷y

f→y,y→f ⊢ f⟷y

• La validità di questa regola è ovvia vista l’equivalenza tra il bicondizionale e la congiunzione dei due condizionali

f→yy→f:. f⟷y

f→yy→f:. y⟷f

Esempio

• P⟷Q⊢Q⟷P

1 P⟷Q A2 P→Q 1 ⟷E3 Q→P 1 ⟷E4 Q⟷P 2,3 ⟷I

Regole ipotetiche

• Regole valide che utilizzano premesse ipotetiche, cioè assunzioni temporanee (con lo scopo di capire cosa succederebbe in tal caso)

• L’ipotesi (H) assunta non è vera, la si dà momentaneamente per vera e si dà corso allo sviluppo inferenziale per capire cosa succederebbe in tal caso, cioè a quale conclusione (C) si giungerebbe

• Al termine, l’ipotesi si scarica (cioè non viene più considerata come premessa da cui dipende la conclusione)

A cosa si giunge?

• Siano H l’ipotesi inferenziale e C la conclusione della derivazione ipotetica, ci sono due possibilità– si giunge ad una conclusione ammissibile,

allora possiamo inferire che H→C (per cui se H fosse vera, sarebbe vera C)

– si giunge ad una conclusione contraddittoria, allora possiamo inferire ~H (in tal modo si elimina la contraddizione generata da H). E’ nota come dimostrazione per assurdo

• Espediente grafico: linea verticale per tutta l’argomentazione ipotetica

Regola →I

• Regola →I (introduzione del condizionale): da una derivazione di una fbf y (ammissibile) con l’aiuto di una ipotesi f possiamo scaricare l’ipotesi e inferire f→y

• La validità di questa regola deriva dal fatto che supponendo una fbf vera abbiamo derivato la verità di un’altra fbf, ma poiché la prima fbf non è necessariamente vera, possiamo dedurne solo la loro implicazione

| f| …| yf→y

Esempio

• P→Q,Q→R⊢P→R

1 P→Q A2 Q→R A3 | P H (→I)4 | Q 1,3 →E5 | R 2,4 →E6 P→R 3-5 →I

Esempio

• P⊢R→R

1 P A2 | R H (→I)3 R→R 2 →I

Esempio

• P→Q,(QvR)→P⊢P⟷(QvR)

1 P→Q A2 (QvR)→P A3 | P H (→I)4 | Q 1,3 →E 5 | QvR 4 vI6 P→(QvR) 3-5 →I7 P⟷(QvR) 2,6 ⟷I

Esempio

• ~P→Q,R→S⊢(~P→(QvS))&(R→(QvS))

1 ~P→Q A2 R→S A3 | ~P H (→I)4 | Q 1,3 →E 5 | QvS 4 vI6 ~P→(QvS) 3-5 →I7 | R H (→I)8 | S 2,7 →E9 | QvS 8 vI10 R→(QvS) 7-9 →I11 (~P→(QvS))&(R→(QvS)) 6,10 &I

Esempio

• P→S,(Q&S)→R⊢P→(Q→R)

1 P→S A2 (Q&S)→R A3 | P H (→I)4 | S 1,3 →E5 | | Q H (→I)6 | | Q&S 4,5 &I7 | | R 2,6 →E8 | Q→R 5-7 →I9 P→(Q→R) 3-8 →I

Regola ~I

• Regola ~I (introduzione della negazione): se da un’ipotesi f si deriva un assurdo (una contraddizione) del tipo y&~y allora possiamo inferire ~f

• La validità di questa regola (dimostrazione per assurdo) deriva dal fatto che una contraddizione è necessariamente falsa, per cui nel processo inferenziale deve esserci (almeno) una premessa falsa: ma le altre premesse sono certe, dunque la premessa falsa è proprio l’ipotesi

| f| …| y&~y~f

Esempio

• P→Q,~Q⊢~P

1 P→Q A2 ~Q A3 | P H (~I)4 | Q 1,3 →E5 | Q&~Q 2,4 &I6 ~P 3-5 ~I

Esempio

• P→~Q⊢~(P&Q)

1 P→~Q A2 | P&Q H (~I)3 | P 2 &E4 | Q 2 &E5 | ~Q 1,3 →E6 | Q&~Q 4,5 &I7 ~(P&Q) 2-6 ~I

Esempio

• ~P→P⊢P

1 ~P→P A2 | ~P H (~I)3 | P 1,2 →E4 | P&~P 2,3 &I5 ~~P 2-4 ~I6 P 5 ~E

Osservazioni

• Ogni ipotesi assunta dà inizio ad una nuova linea ipotetica (graficamente con una linea verticale)

• Nessuna formula derivata da un’ipotesi può essere usata all’esterno della linea ipotetica

• Quando si assumono più ipotesi, l’ordine di scaricamento è inverso rispetto a quello di assunzione (se P si assume prima di Q, allora Q si deve scaricare prima di P)

• Fino a che non si siano scaricate tutte le ipotesi la dimostrazione non è completa

1 ~Pv~Q A2 | ~P H (→I)3 | | P&Q H (~I)4 | | P 3 &E5 | | P&~P 2,4 &I6 | ~(P&Q) 3-5 ~I7 ~P→~(P&Q) 2-6 →I8 |~Q H (→I)9 | | P&Q H (~I)10 | | Q 9 &E11 | | Q&~Q 8,10 &I12 | ~(P&Q) 9-11 ~I13 ~Q→~(P&Q) 8-12 →I14 ~(P&Q) 1,7,13 vE

~Pv~Q⊢~(P&Q)Cerchiamo di dimostrare che ~P e ~Q portano alla stessa conclusione

~Pv~Q| ~P…| ~(P&Q)~P→~(P&Q)…| ~Q…| ~(P&Q)~Q→~(P&Q)~(P&Q)

1 ~(P&Q) A2 | ~(~Pv~Q) H (~I)3 | | ~P H (~I)4 | | ~Pv~Q 3 vI5 | | ~Pv~Q&~(~Pv~Q) 2,4 &I6 | ~~P 3-5 ~I7 | P 6 ~E8 | | ~Q H (~I)9 | | ~Pv~Q 8 vI10 | | ~Pv~Q&~(~Pv~Q) 2,8 &I11 | ~~Q 8-10 ~I12 | Q 11 ~E13 | P&Q 7,12 &I14 | (P&Q)&(~(P&Q)) 1,13 &I15 ~~(~Pv~Q) 2-14 ~I16 ~Pv~Q 15 ~E

~(P&Q)⊢~Pv~Q Cerchiamo di dimostrare che la negazione della conclusione è un assurdo

~(P&Q)| ~(~Pv~Q)……| assurdo~~(~Pv~Q) ~Pv~Q

Osservazioni

• In generale non esiste un solo modo di dimostrare una forma argomentativa

• Considerate l’operatore principale della formula conclusiva, generalmente esso permette di individuare una strategia vincente, in quanto si tratta dell’ultimo operatore da inserire. Poi a ritroso considerate il penultimo. E così via…

Strategie dimostrative

• Spesso funzionano le seguenti strategie– per una negazione, dimostrare per via ipotetica

che la sua affermazione è assurda (~I)– per una congiunzione, dimostrare ciascun

congiunto e poi congiungerli (&I)– per una disgiunzione, dimostrare un disgiunto

oppure dimostrare per via ipotetica l’assurdità della negazione di un disgiunto (e poi vI)

– per un condizionale, dimostrare dall’ipotesi dell’antecedente il conseguente (→I)

– per un bicondizionale usare →I due volte

Richieste sistemiche

P→Q,Q→R,P

R

siano date alcune fbf

Posso determinare se una fbf data

segue validamente?(decidibilità)

Posso trovare tutte le fbf che seguono validamente?

(completezza)

Posso dimostrare anche una fbf che non segue

validamente?(correttezza)

Proprietà sistemiche

• Abbiamo già parlato della decidibilità: il sistema proposizionale è decidibile (data una qualunque forma argomentativa nel linguaggio è possibile stabilire meccanicamente se è valida o no)

• Il calcolo proposizionale è completo: tutte le forme valide possono essere dedotte (dimostrate) attraverso il calcolo proposizionale (ogni argomentazione valida può essere dedotta)

• Il calcolo proposizionale è corretto: in esso non è possibile generare fbf che non seguano validamente (non si possono produrre forme argomentative invalide)

Correttezza e completezza

• Abbiamo detto che il sistema proposizionale è completo e corretto

• Le dieci regole d’inferenza (vE, &E, ⟷E, ~E, →E, vI, &I, ⟷I, →I, ~I) formano un sistema– completo: con esse possiamo derivare tutte le

forme valide della logica proposizionale – corretto: con esse possiamo derivare solo le

forme valide della logica proposizionale

Non decidibilità di CP

• Le dieci regole d’inferenza (vE, &E, ⟷E, ~E, →E, vI, &I, ⟷I, →I, ~I) formano un sistema– Non decidibile: con esse possiamo

dimostrare tutte le forme valide, ma non possiamo dimostrare l’invalidità di una formula

– Se provassimo a dimostrare una forma invalida saremmo impegnati all’infinito senza successo: l’invalidità non è dimostrabile

• Attenzione, però: la decidibilità del sistema proposizionale è assicurata dalla procedura meccanica delle tavole di verità!

Esempi per sostituzione

• Una volta dimostrata una forma valida, essa rimane tale se alle proposizioni semplici sostituiamo altre proposizioni semplici o complesse (la dimostrazione seguirebbe la stessa sequenza inferenziale)– Dalla validità (dimostrata) di P→~Q⊢~(P&Q)

segue la validità di– R→~S⊢~(R&S)

(con R al posto di P e S al posto di Q)– (RvT)→S⊢~((RvT)&~S)

(con RvT al posto di P e ~S al posto di Q)

Regole Derivate

• Non aumentano le possibilità dimostrative delle regole di base (è già al massimo)

• Consistono in scorciatoie che possono abbreviare le dimostrazioni

• In virtù della sostituibilità, ogni forma dimostrata genera una corrispondente nuova regola d’inferenza detta regola derivata

• Ad alcune di loro (quelle più utili) viene dato un nome per citarle all’occorrenza

Teorema

• I teoremi (o leggi del calcolo delle proposizioni) sono fbf che non hanno bisogno di alcuna premessa per essere dimostrate

• Semanticamente corrispondono alle tautologie, cioè alle fbf che valgono in ogni situazione logicamente possibile

• Per indicare che una fbf è un teorema si antepone il simbolo ‘⊢’ alla fbf– Esempio: ⊢P→P

Esempi

• Dimostrare che P→P è un teorema⊢P→P

• Dimostrare che ~(P&~P) è un teorema⊢~(P&~P)

1 | P H (→I)2 P→P 1-1 →I

1 | P&~P H (~I)2 ~(P&~P) 1-1 ~I

Esempi

• Dimostrare il teorema⊢P→(PvQ)

• Dimostrare il teorema⊢(P&Q)→P

1 | P H (→I)2 | PvQ 1 vI3 P→(PvQ) 1-2 →I

1 | P&Q H (→I)2 | P 1 &E3 P&Q→P 1-2 →I

Esempio

• Dimostrare il teorema⊢P⟷~~P

1 | P H (→I)2 | | ~P H (~I)3 | | P&~P 1,2 &I4 | ~~P 2-3 ~I5 P→~~P 1-4 →I6 | ~~P H (→I)7 | P 6 ~E8 ~~P→P 6-7 →I9 P⟷~~P 5,8 ⟷I

Equivalenze

• I teoremi in forma bicondizionale (cioè del tipo (⊢Φ⟷Ψ) si dicono equivalenze, e Φ e Ψ si dicono equivalenti (o interderivabili)– Esempio: ⊢P⟷~~P

• Sostituibilità: se una fbf è ottenuta da un’altra fbf sostituendo una sottoformula con una fbf equivalente, allora la seconda fbf si può ottenere dalla prima fbf usando le dieci regole di inferenza– Esempio: poiché ⊢P⟷~~P siamo certi che P&Q e

~~P&Q sono interderivabili

Esempi notevoli equivalenze

Doppia negazione DNDM Legge di De MorganDM Legge di De MorganCOM CommutazioneCOM CommutazioneASSOC AssociazioneASSOC AssociazioneDIST DistribuzioneDIST DistribuzioneTRAS Trasposizione

⊢P⟷~~P⊢~(PvQ)⟷~P&~Q⊢~(P&Q)⟷~Pv~Q⊢(PvQ)⟷(QvP)⊢(P&Q)⟷(Q&P)⊢(Pv(QvS))⟷((PvQ)vS)⊢(P&(Q&S))⟷((P&Q)&S)⊢(Pv(Q&S))⟷((PvQ)&(PvS)) ⊢(P&(QvS))⟷((P&Q)v(P&S))⊢(P→Q)⟷(~Q→~P)

Esempi notevoli equivalenze

IM Implicazione materialeIM Implicazione materialeESP EsportazioneTAUT TautologiaTAUT Tautologia

⊢(P→Q)⟷(~PvQ)⊢(P→Q)⟷~(P&~Q)⊢((P&Q)→R)⟷(P→(Q→R))⊢P⟷(P&P)⊢P⟷(PvP)

Quale vantaggio?

• Il calcolo proposizionale non sembra aver apportato molti vantaggi– Le derivazioni non hanno un carattere

meccanico (a differenza delle tavole di verità)– Ogni forma valida era già dimostrabile con le

tavole di verità– Non possiamo dimostrare l’invalidità (a

differenza delle tavole di verità)• Dunque nessun vantaggio nella risoluzione

di esempi. E allora?

Tuttavia…

• Le regole del calcolo proposizionale caratterizzano completamente tutto l’insieme delle regole logiche deduttive: dato un qualsiasi insieme di premesse le regole sono sufficienti a dimostrare tutte le possibili conseguenze logiche che ne derivano

• In altri termini, le regole d’inferenza sono i costituenti di base su cui si appoggia tutta la nostra logica deduttiva (a livello proposizionale)

Unit 2 – Corso di Logica e Teoria dell’Argomentazione

Documents

Transcript of Unit 2 – Corso di Logica e Teoria dell’Argomentazione