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
Soluzione