Calcolo della deduzione naturale
Innanzitutto buona serata!
Devo dimostrare i seguenti teoremi del linguaggio logico proposizionale mediante le regole del calcolo della deduzione naturale di Prawitz:
1)[tex]\vdash ((\neg P \rightarrow R) \wedge (Q \rightarrow R)) \rightarrow ((P \rightarrow Q) \rightarrow R)[/tex]
2)[tex]\vdash \neg (A \rightarrow \neg B) \rightarrow ( A \wedge B)[/tex]
1) Per la prima avrei ipotizzato questa risoluzione(il tutto assumendo il teorema del terzo escluso([tex]\neg A \vee A[/tex])):
2)Per la seconda in classe il professore ha dato questa dimostrazione che per il secondo ramo(o meglio la deduzione di [tex]\neg B[/tex] apparentemente dal nulla) mi lascia abbastanza perplesso:
Da notare che una formula barrata equivale a formula scaricata in seguito ad un'introduzione della negazione su una formula assunta in precedenza o di una formula precedentemente negata.
Vi chiedo se cortesemente potete darmi una dritta su come affrontare tali esercizi di dimostrazione; per alcuni, quale il secondo da me inserito, non trovo nessun metodo di dimostrazione valido e rimango bloccato sul nascere della dimostrazione.
Vi è qualche metodo particolare di cui sono allo scuro?
Grazie e ancora buona serata!!
Devo dimostrare i seguenti teoremi del linguaggio logico proposizionale mediante le regole del calcolo della deduzione naturale di Prawitz:
1)[tex]\vdash ((\neg P \rightarrow R) \wedge (Q \rightarrow R)) \rightarrow ((P \rightarrow Q) \rightarrow R)[/tex]
2)[tex]\vdash \neg (A \rightarrow \neg B) \rightarrow ( A \wedge B)[/tex]
1) Per la prima avrei ipotizzato questa risoluzione(il tutto assumendo il teorema del terzo escluso([tex]\neg A \vee A[/tex])):
2)Per la seconda in classe il professore ha dato questa dimostrazione che per il secondo ramo(o meglio la deduzione di [tex]\neg B[/tex] apparentemente dal nulla) mi lascia abbastanza perplesso:
Da notare che una formula barrata equivale a formula scaricata in seguito ad un'introduzione della negazione su una formula assunta in precedenza o di una formula precedentemente negata.
Vi chiedo se cortesemente potete darmi una dritta su come affrontare tali esercizi di dimostrazione; per alcuni, quale il secondo da me inserito, non trovo nessun metodo di dimostrazione valido e rimango bloccato sul nascere della dimostrazione.
Vi è qualche metodo particolare di cui sono allo scuro?
Grazie e ancora buona serata!!
Risposte
Per quel poco che so, mi sembrano corrette entrambe le deduzioni.
Ex Falso Quodlibet (dal falso $\bot$ segue ogni cosa, quindi anche $not B$ ). In generale si dovrebbe cercare di non usare questa regola perchè è molto controintuitiva, sarebbe meglio tenerla come ultima risorsa quando proprio non si riesce a risolvere in altro modo.
Non lo so, cmq hai provato a sfogliare queste note http://www.danielclemente.com/logica/dn.en.pdf mi sembrano fatte molto bene.
Ciao.
"Howard_Wolowitz":
la deduzione di $¬B$ apparentemente dal nulla
Ex Falso Quodlibet (dal falso $\bot$ segue ogni cosa, quindi anche $not B$ ). In generale si dovrebbe cercare di non usare questa regola perchè è molto controintuitiva, sarebbe meglio tenerla come ultima risorsa quando proprio non si riesce a risolvere in altro modo.
"Howard_Wolowitz":
Vi è qualche metodo particolare di cui sono allo scuro?
Non lo so, cmq hai provato a sfogliare queste note http://www.danielclemente.com/logica/dn.en.pdf mi sembrano fatte molto bene.
Ciao.
L'esercizio fatto da te mi sembra sbagliato. L'ipotesi p non è scaricata quindi la proposizione finale è dedotta da p, non si tratta di un teorema. (Le dispense da cui studio io definiscono teorema una derivazione senza ipotesi, non so se ci sono altri termini).
Sto cercando di farlo anche io ma p non sono ancora riuscito a trovare una deduzione che scarichi p.
Sto cercando di farlo anche io ma p non sono ancora riuscito a trovare una deduzione che scarichi p.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo