Deduzione: introduzione · Topos Uranos

Riepilogo

Questa lezione apre la seconda unità del corso, dedicata alla deduzione. Presenta le sue cinque lezioni e il filo che le unisce, dalla definizione di un sistema deduttivo formale fino alle leggi di De Morgan e alle leggi distributive; colloca l’unità nel cammino del corso, tra il linguaggio, già costruito, e la semantica e la metateoria, che verranno, e anticipa ciò che queste diranno di essa; giustifica la scelta di un sistema assiomatico, che si costruisce in due tappe (il sistema di Łukasiewicz, con tre schemi di assiomi e il modus ponens, e il sistema del corso, che gli aggiunge la regola della sostituzione della doppia negazione), e spiega perché serve questa seconda regola e perché la si postula invece di dimostrarla; mostra con una deduzione breve quanto lavoro nasconde un ragionamento elementare; precisa ciò che si prende dall’unità precedente, cioè la leggibilità unica, l’induzione (quella forte sui naturali e quella strutturale) e lo sviluppo delle abbreviazioni, e dà consigli per studiarla.

Obiettivi di apprendimento

Descrivere la sequenza delle cinque lezioni dell’unità e spiegare quali risultati di ciascuna usa la successiva.
Collocare la deduzione nel percorso del corso, distinguere la deducibilità $\Gamma \vdash \varphi$ dalla conseguenza semantica $\Gamma \models \varphi$ e spiegare che cosa affermeranno la correttezza e la completezza.
Spiegare perché il sistema del corso aggiunge a quello di Łukasiewicz una seconda regola primitiva, la sostituzione della doppia negazione, a partire da ciò che i tre schemi possono e non possono vedere in una negazione congiunta.
Leggere una deduzione breve per righe numerate, distinguere la deduzione di formule dalla deduzione sulle deduzioni, riconoscere ciò che l’unità prende dalla precedente e organizzarne lo studio a partire dalla valutazione d’ingresso.

Valutazione d’ingresso

Prima di percorrere l’unità conviene misurare il punto di partenza. Questa valutazione è un’autovalutazione: non ha voto, e il suo unico scopo è orientare lo studio. Le sue tredici domande sono di due tipi. Le prime tre toccano ciò che l’unità dà per noto dalla precedente: la leggibilità unica, l’induzione forte e lo sviluppo delle abbreviazioni; chi ne sbaglia una deve ripassare, prima di proseguire, la lezione che la domanda nomina. Le dieci restanti toccano, in ordine, le cinque lezioni di questa unità: tre la prima, tre la seconda, due la terza, una la quarta e una la quinta. Chi non ha mai studiato un sistema deduttivo non deve aspettarsi di rispondere correttamente, e non importa: ogni risposta, giusta o no, spiega il punto e nomina la lezione che lo tratta. Le stesse abilità si misurano di nuovo alla fine, nella lezione di sintesi.

Valutazione d’ingresso

Prima di iniziare l’unità, misura il tuo punto di partenza. È un’autovalutazione breve: non riceve voto e il risultato resta solo nel tuo browser.

Domanda 1Dalle unità precedentiLa stringa $\sigI\sigI\sigO\sigI\sigO\sigO\sigI\sigO\sigI$ è una formula composta, della forma $\sigI\varphi\psi$ . Quali sono le sue componenti $\varphi$ e $\psi$ ?
$\varphi = \sigI\sigO\sigI\sigO\sigO\sigI$ e $\psi = \sigO\sigI$ .
$\varphi = \sigI\sigO\sigI$ e $\psi = \sigO\sigO\sigI\sigO\sigI$ .
Ammette due scomposizioni, secondo dove si taglia la stringa dopo il disco iniziale.
$\varphi$ è tutta la stringa che segue il disco iniziale, e $\psi$ è la stringa vuota.
Domanda 2Dalle unità precedentiIn una dimostrazione per induzione forte che ogni naturale $n$ soddisfa una proprietà $P(n)$ , che cosa si può supporre nel dimostrare $P(n)$ ?
Che $P(m)$ vale per ogni naturale $m$ minore di $n$ .
Solo che vale $P(n - 1)$ .
Che $P(m)$ vale per ogni naturale $m$ minore o uguale a $n$ .
Niente, finché non si sono dimostrati separatamente $P(1)$ e $P(2)$ .
Domanda 3Dalle unità precedentiCon le abbreviazioni ufficiali del corso, quale formula designa $(\varphi \rightarrow \psi)$ , scritta con la negazione congiunta e la negazione?
$\neg(\neg\varphi \downarrow \psi)$ .
$(\neg\varphi \downarrow \psi)$ .
$\neg(\varphi \downarrow \neg\psi)$ .
Nessuna in particolare: dipende da come si decide di leggerla.
Domanda 4Lo schema A1 è $(\varphi \rightarrow (\psi \rightarrow \varphi))$ . La formula $(v_{1} \rightarrow (v_{2} \rightarrow v_{3}))$ è un’istanza di A1?
No: al posto della prima e dell’ultima occorrenza di $\varphi$ dovrebbe andare la stessa formula, e qui ci sono $v_{1}$ e $v_{3}$ .
Sì, con $\varphi := v_{1}$ e $\psi := v_{2}$ .
Sì, perché ogni implicazione il cui conseguente è un’altra implicazione è un’istanza di A1.
No, perché le istanze di uno schema non possono contenere variabili.
Domanda 5In una deduzione compaiono già le righe $\psi$ e $(\varphi \rightarrow \psi)$ , dove $\varphi$ e $\psi$ sono formule distinte. Quale formula permette di scrivere il modus ponens applicato a quelle due righe?
Nessuna: il modus ponens esige l’antecedente $\varphi$ , e ciò che si ha è il conseguente.
$\varphi$ .
$(\psi \rightarrow \varphi)$ .
$\neg\varphi$ .
Domanda 6Si sa che $\{\varphi\} \vdash \psi$ , cioè che c’è una deduzione di $\psi$ la cui unica premessa è $\varphi$ . Che cosa afferma allora il teorema di deduzione?
Che $\vdash (\varphi \rightarrow \psi)$ : l’implicazione è un teorema.
Che $\vdash \psi$ : la premessa si può sopprimere senz’altro.
Che $\vdash (\psi \rightarrow \varphi)$ .
Che $\{\psi\} \vdash \varphi$ .
Domanda 7Che cosa si deduce, senza altre premesse, dall’insieme $\{(\varphi \rightarrow \psi), (\psi \rightarrow \chi)\}$ ?
$(\varphi \rightarrow \chi)$ .
$\chi$ , applicando due volte il modus ponens.
$(\chi \rightarrow \varphi)$ .
$(\varphi \wedge \chi)$ .
Domanda 8La regola della sostituzione della doppia negazione (SDN) cambia, in una riga, una sola occorrenza di una sottoformula, e agisce sulla stringa della lingua di base. Quante occorrenze della sottoformula $\neg v_{1}$ contiene la stringa che $(v_{1} \rightarrow v_{2})$ designa?
Due.
Una, quella che corrisponde all’antecedente.
Nessuna: la formula non contiene negazioni.
Quattro.
Domanda 9Quale formula si ottiene da $(\neg\varphi \rightarrow \psi)$ per contrapposizione, senza aggiungere doppie negazioni?
$(\neg\psi \rightarrow \varphi)$ .
$(\psi \rightarrow \neg\varphi)$ .
$(\varphi \rightarrow \neg\psi)$ .
$(\neg\psi \rightarrow \neg\varphi)$ .
Domanda 10 $(\varphi \vee \psi)$ e $(\neg\varphi \rightarrow \psi)$ designano la stessa formula?
No: la prima è $\neg(\varphi \downarrow \psi)$ e la seconda, $\neg(\neg\neg\varphi \downarrow \psi)$ ; sono formule distinte, equivalenti per deduzione.
Sì, per la definizione dell’implicazione.
Sì, perché entrambe si leggono « $\varphi$ o $\psi$ ».
No, e nemmeno l’una si deduce dall’altra.
Domanda 11Si sa che $\varphi \dashv\vdash \varphi'$ , cioè che ciascuna si deduce dall’altra. Che cosa giustifica che anche $\neg\varphi \dashv\vdash \neg\varphi'$ ?
Un teorema, la sostituzione di equivalenti, che si dimostra con il teorema di deduzione e la contrapposizione.
Nessuna giustificazione speciale: basta «negare entrambi i lati» dell’equivalenza.
La definizione della negazione, perché $\neg\varphi$ è $(\varphi \downarrow \varphi)$ .
Nulla, perché non è vero: la negazione può separare formule equivalenti.
Domanda 12Dall’insieme di premesse $\Gamma \cup \{\neg\varphi\}$ si deducono una formula $\chi$ e la sua negazione $\neg\chi$ . Che cosa si può concludere?
Che $\Gamma \vdash \varphi$ .
Che $\Gamma \vdash \neg\varphi$ .
Che da $\Gamma$ si deduce qualsiasi formula.
Nulla: una deduzione che arriva a una contraddizione non prova nulla.
Domanda 13A quale formula è equivalente la negazione di un’implicazione, $\neg(\varphi \rightarrow \psi)$ ?
A $(\varphi \wedge \neg\psi)$ .
A $(\neg\varphi \rightarrow \neg\psi)$ .
A $(\varphi \rightarrow \neg\psi)$ .
A $(\neg\varphi \wedge \psi)$ .