Logica 13-14
Lezioni 17-18 Lunedì 18 Nov
Annuncio
• E' possibile che dovrò rinviare delle lezioni della prossima settimana.
• Tenete d'occhio gli annunci sui cambi di orario e anche la mia pagina docente
• Consegnare compito 3
• NB: come già indicato nella scorsa lezione,
c'erano due parentesi mancanti nella conclusione dell'argomentazione dell'esercizio 3.2.2 . La
versione corretta è questa
P →(R & S), Q →(R & T) ⱶ (P v Q) → R
• Ma va bene ugualmente, se qualcuno ha interpretato la formula così
P →(R & S), Q →(R & T) ⱶ P v (Q → R)
• Venerdì prossimo: compito in classe
Che cosa vi sarà richiesto nel compito?
• esercizi di traduzione analoghi a quelli fatti in classe
• un esercizio con tavole di verità
• un paio di argomentazioni da dimostrare con alberi di refutazioni
• un paio di argomentazioni molto semplici da dimostrare con deduzione naturale (senza introduzione della negazione e senza
dimostrazioni ipotetiche incassate dentro altre dimostrazioni ipotetiche)
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)
Esercizio risolto 4.23
• (P & Q) |– P Q
• Strategia:
• dimostriamo per assurdo e quindi ipotizziamo;
• (1) (P Q)
• Per ottenere una contraddizione cerchiamo di dimostrare l'opposto della nostra premessa, ossia P & Q
• Dobbiamo quindi dimostrare una congiunzione.
• Per farlo, dobbiamo dimostrare entrambi i congiunti: P, Q
• Ma come? Per assurdo, ossia prima ipotizzando P , poi Q
• In entrambi i casi , grazie alla regola I ottengo una contraddizione
Esercizio risolto 4.23
Dimostrare:
(P & Q) |– P Q
Soluzione
Strategie dimostrative
• (1) Per dimostrare una formula atomica: in
mancanza di altre strategie, ipotizzare la negazione della conclusione per ottenere la sua doppia
negazione tramite I, quindi applicare E.∼ ∼
• (2) Per dimostrare una negazione: assumere per ipotesi la conclusione senza il segno di negazione per ottenere un assurdo, quindi applicare I.∼
• (3) Per dimostrare una congiunzione: dimostrare ciascuno dei congiunti separatamente e poi
congiungerli mediante &I.
Strategie dimostrative (ii)
• (4) Per dimostrare una disgiunzione: provare a derivare uno dei disgiunti per applicare I; se questa strategia ∨ fallisce, comportarsi come nel caso delle fbf atomiche, cioè assumere la negazione della conclusione e poi
applicare I e E.∼ ∼
• (5) Per dimostrare una condizionale: ipotizzare
l’antecedente e derivare il conseguente, poi applicare
→I.
• (6) Per dimostrare una bicondizionale: usare →I due volte per dimostrare i condizionali necessari a ottenere la conclusione per ↔I.
Strategie dimostrative (iii)
• Aggiungerei:
• se tra le premesse è disponibile una
disgiunzione P v Q e bisogna dimostrare C,
provare a dimostrare sia P -> C che Q -> C e poi applicare vE
Sommario delle 10 regole di base
• Guardare insieme la tabella riassuntiva 4.2 a p.
118
Esempio per sostituzione
• Un esempio per sostituzione di una fbf o di una forma argomentativa è il risultato della
sostituzione di zero o più lettere enunciative
con fbf qualsiasi, anche complesse, purché ogni occorrenza della stessa lettera venga sostituita dalla stessa fbf (diciamo zero o più’ per
permettere a ogni forma di valere come esempio per sostituzione di se stessa).
• Esempio ...
• P → Q, ∼Q |– ∼P
• Sostituzioni:
• P = (P N) ∨
• Q = S∼
• (P N) ∨ → S∼ , ∼ S ∼ |– ∼(P N)∨
Regole derivate
• Se è valida una certa forma argomentativa P1, ..., Pn |– C, sarà valido qualsiasi esempio per
sostituzione P1*, ..., Pn* |– C* di quella forma
• Perché potrei ripetere gli stessi passi dimostrativi che mi hanno condotto a C da P1, ... Pn, questa volta per ottenere C* da P1*, ..., Pn*
• Quindi la dimostrazione di una forma
argomentativa genera una corrispondente regola DERIVATA
Esempio:
• abbiamo dimostrato (es. 4.18) che questa forma è valida:
• P → Q, ∼Q |– ∼P
• Allo stesso modo potremmo dimostrare la validità di qualsiasi esempio per sostituzione di tale forma. Quindi posso assumere questa regola derivata:
• Da fbf della forma φ → ψ e ∼ψ, (è lecito) inferire ∼φ.
regole derivate notevoli
• Alcune regole derivate sono particolarmente utili e intuitive. Gli è stato quindi assegnato un nome ed è utile conoscerle e imparare a usarle per
abbreviare le dimostrazioni.
• Quella che abbiamo appena visto viene chiamata Modus tollens (MT):
• MT Modus tollens: Da fbf della forma φ → ψ e
∼ψ, (è lecito) inferire ∼φ.
• v. tabella 4.3 p. 118
Esercizio risolto 4.25
Dimostrare:
(P N) → S |– S → (P N)
Soluzione
Per apprezzare l’utilità pratica delle regole derivate è sufficiente confrontare questa
dimostrazione con quella riportata qui sotto, in cui si fa a meno del richiamo a MT e si riproduce invece per intero la derivazione del corrispondente esempio per sostituzione:
Regole ASS e DC
• ASS (assimilazione, assorbimento): v. 4.26, p.
110
• DC (dilemma costruttivo): v. prossima diap.
Esercizio risolto 4.27
Dimostrare la regola derivata DC, cioè:
P Q, P → R, Q → S |– R S