Metateoria: introduzione

Riepilogo

Questa lezione apre la quarta e ultima unità di contenuto del corso, dedicata alla metateoria. Ne presenta le tre lezioni e il filo che le unisce: le due unità precedenti hanno costruito, sullo stesso linguaggio, due nozioni di ciò che segue da premesse date, la deduzione $\Gamma \vdash \varphi$ e la conseguenza semantica $\Gamma \models \varphi$ , e questa unità dimostra che coincidono, prima per un numero finito di premesse (correttezza, lemma di Kalmár e completezza), poi per premesse qualsiasi (teorema di compattezza e completezza forte), e infine offre una terza via per decidere la conseguenza, il metodo di risoluzione, di cui dimostra anche che è corretto e completo. Spiega perché la compattezza si dimostra prima della completezza forte e non al contrario; mostra con due esempi le domande a cui né la ricerca di deduzioni né la tavola di verità sanno rispondere da sole; stabilisce che cosa si riprende dalle tre unità precedenti e dà consigli per il suo studio.

Obiettivi di apprendimento

Descrivere la successione delle tre lezioni dell’unità, spiegare quali risultati di ciascuna usa la successiva e giustificare che la compattezza si dimostri, con un argomento semantico, prima della completezza forte.
Distinguere i due lati del corso, la deducibilità $\Gamma \vdash \varphi$ , esistenziale e finita, e la conseguenza semantica $\Gamma \models \varphi$ , universale su infinite assegnazioni, ed enunciare la correttezza e la completezza nei loro tre gradi.
Spiegare perché la coincidenza delle due relazioni non si stabilisce caso per caso ma con metateoremi, e riconoscere quali strumenti delle unità precedenti (induzioni, dimostrazione per casi, teoremi di deduzione, lemma di coincidenza, forme congiuntive) userà ogni dimostrazione.
Leggere deduzioni sulle deduzioni e argomenti semantici dell’unità distinguendo a ogni passo di quale relazione si parla, e pianificare lo studio a partire dalla valutazione d’ingresso.

Valutazione d’ingresso

Prima di percorrere l’unità conviene stabilire il punto di partenza. Questa valutazione è un’autovalutazione: non ha voto, e il suo unico scopo è orientare l’apprendimento. Le sue quindici domande sono di due tipi. Le prime sei riguardano ciò che l’unità dà per noto dalle precedenti: la definizione di conseguenza semantica e la sua riduzione all’insoddisfacibilità, il valore della negazione congiunta, il lemma di coincidenza, la finitezza della deduzione e la dimostrazione per casi; chi ne sbaglia qualcuna farà bene a ripassare, prima di proseguire, la lezione che la domanda indica. Le nove restanti percorrono in ordine le tre lezioni di questa unità, tre per ciascuna. Chi non ha mai studiato la metateoria di un sistema logico non deve aspettarsi di risponderle bene, e non importa: ogni risposta, corretta o no, spiega il punto e indica 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à precedentiChe cosa significa $\Gamma \models \varphi$ ?
Che ogni assegnazione che soddisfa tutte le formule di $\Gamma$ soddisfa anche $\varphi$ .
Che esiste una deduzione di $\varphi$ a partire da $\Gamma$ .
Che qualche assegnazione soddisfa insieme $\Gamma$ e $\varphi$ .
Che $\varphi$ segue da una sola formula di $\Gamma$ .
Domanda 2Dalle unità precedentiQuale dei seguenti enunciati è equivalente a $\Gamma \models \varphi$ ?
Che $\Gamma \cup \{\neg\varphi\}$ è insoddisfacibile.
Che $\Gamma \cup \{\varphi\}$ è soddisfacibile.
Che $\Gamma \cup \{\neg\varphi\}$ è soddisfacibile.
Che $\neg\varphi$ è insoddisfacibile.
Domanda 3Dalle unità precedentiSe un’assegnazione $v$ dà alla formula $\alpha$ il valore $1$ , quale valore dà a $(\alpha \downarrow \beta)$ ?
$0$ , qualunque sia il valore di $\beta$ .
Dipende da $\beta$ : vale $1$ se $\beta$ vale $0$ .
$1 - v(\beta)$ .
$1$ , perché una delle componenti è vera.
Domanda 4Dalle unità precedentiLe variabili di $\varphi$ sono $v_{2}$ e $v_{7}$ . Due assegnazioni $v$ e $w$ danno gli stessi valori a $v_{2}$ e a $v_{7}$ , e valori opposti a tutte le altre variabili. Se $v(\varphi) = 1$ , che cosa si può dire di $w(\varphi)$ ?
Che $w(\varphi) = 1$ .
Niente, perché $v$ e $w$ differiscono su infinite variabili.
Che $w(\varphi) = 0$ , perché $w$ inverte quasi tutti i valori di $v$ .
Che $w(\varphi) = 1$ solo se $v$ e $w$ coincidono anche su $v_{1}, \ldots, v_{6}$ .
Domanda 5Dalle unità precedentiSia $\Gamma$ un insieme infinito di formule con $\Gamma \vdash \varphi$ . Che cosa si può affermare?
Che qualche sottoinsieme finito di $\Gamma$ deduce $\varphi$ .
Che $\varphi$ è un teorema.
Che la deduzione usa tutte le formule di $\Gamma$ .
Niente senza il teorema di compattezza, perché $\Gamma$ è infinito.
Domanda 6Dalle unità precedentiSi sa che $\Gamma \cup \{p\} \vdash \chi$ e che $\Gamma \cup \{\neg p\} \vdash \chi$ . Che cosa permette di concludere la dimostrazione per casi?
Che $\Gamma \vdash \chi$ .
Niente, finché non si sa se $\Gamma$ deduce $p$ o deduce $\neg p$ .
Che $\Gamma \vdash (p \leftrightarrow \chi)$ .
Solo che $\Gamma \cup \{p, \neg p\} \vdash \chi$ .
Domanda 7Il sistema del corso è corretto. Che cosa afferma questa proprietà?
Che per ogni insieme $\Gamma$ , se $\Gamma \vdash \varphi$ allora $\Gamma \models \varphi$ .
Che se $\Gamma \models \varphi$ allora $\Gamma \vdash \varphi$ .
Che non esiste una formula $\varphi$ con $\vdash \varphi$ e $\vdash \neg\varphi$ .
Che ogni formula vera è un teorema.
Domanda 8Sia $v$ l’assegnazione che dà il valore $1$ a $p$ e il valore $0$ a $q$ . Che cosa afferma il lemma di Kalmár, con le variabili $p$ e $q$ , per la formula $(p \leftrightarrow q)$ ?
Che $\{p, \neg q\} \vdash \neg(p \leftrightarrow q)$ .
Che $\{p, \neg q\} \vdash (p \leftrightarrow q)$ .
Che $\{p, q\} \vdash \neg(p \leftrightarrow q)$ .
Che $\vdash \neg(p \leftrightarrow q)$ .
Domanda 9Può un sistema deduttivo essere corretto senza essere completo?
Sì: il sistema di Łukasiewicz senza la regola SDN è corretto e non deduce la tautologia $((v_{1} \downarrow v_{2}) \rightarrow \neg v_{1})$ .
No: correttezza e completezza si implicano a vicenda.
No: un sistema i cui assiomi sono tautologie deduce tutte le tautologie.
Sì, ma solo se il sistema è incoerente.
Domanda 10Che cosa afferma il teorema di compattezza?
Che un insieme di formule è soddisfacibile se e solo se ogni suo sottoinsieme finito è soddisfacibile.
Che un insieme di formule è soddisfacibile se e solo se ogni sua formula è soddisfacibile.
Che ogni insieme infinito di formule è soddisfacibile.
Che un insieme è soddisfacibile se lo è qualcuno dei suoi sottoinsiemi finiti.
Domanda 11Sia $\Gamma$ un insieme infinito di formule con $\Gamma \models \varphi$ . Che cosa assicura la compattezza?
Che $\Gamma_{0} \models \varphi$ per qualche sottoinsieme finito $\Gamma_{0}$ di $\Gamma$ .
Che $\varphi$ segue da una sola formula di $\Gamma$ .
Che $\varphi$ segue da ogni sottoinsieme finito di $\Gamma$ .
Che $\varphi$ è valida.
Domanda 12La prima lezione dimostra la completezza per insiemi finiti di premesse. Perché la finitezza della deduzione non basta a estenderla a un insieme infinito $\Gamma$ ?
Perché la finitezza parla di $\Gamma \vdash \varphi$ , e ciò che si ha è $\Gamma \models \varphi$ : occorre che la conseguenza, non la deduzione, si riduca a una parte finita, e questa è la compattezza.
Basta invece: se $\Gamma \models \varphi$ , la finitezza fornisce un $\Gamma_{0}$ finito con $\Gamma_{0} \models \varphi$ .
Perché il lemma di Kalmár non vale per formule con infinite variabili.
Perché la completezza per insiemi infiniti di premesse è falsa.
Domanda 13Qual è il risolvente delle clausole $\{p, \neg q, r\}$ e $\{q, s\}$ ?
$\{p, r, s\}$ .
$\{p, \neg q, r, q, s\}$ .
$\{p, r\}$ .
Non hanno risolvente, perché non condividono alcun letterale.
Domanda 14Per decidere per risoluzione se $\{(p \vee q), \neg p\} \models q$ , quale insieme di clausole si cerca di refutare?
$\{\{p, q\}, \{\neg p\}, \{\neg q\}\}$ .
$\{\{p, q\}, \{\neg p\}, \{q\}\}$ .
$\{\{p, q\}, \{\neg p\}\}$ .
$\{\{\neg p, \neg q\}, \{p\}, \{\neg q\}\}$ .
Domanda 15Si può derivare per risoluzione la clausola vuota $\Box$ dall’insieme $\{\{p, q\}, \{\neg p, \neg q\}\}$ ?
No: l’insieme è soddisfacibile e la risoluzione è corretta.
Sì, in un solo passo, eliminando insieme le due coppie complementari.
Sì, in due passi: prima su $p$ e poi su $q$ .
No, perché nessuna delle due clausole è unitaria.