Semantica: introduzione · Topos Uranos

Riepilogo

Questa lezione apre la terza unità del corso, dedicata alla semantica. Presenta le sue sei lezioni e il filo che le unisce, dall’estensione di un’assegnazione a tutte le formule fino all’algoritmo delle forme normali e ai circuiti di interruttori; colloca l’unità nel cammino del corso, dopo la deduzione, che ha ottenuto formule da altre senza badare al loro significato, e prima della metateoria, che metterà in relazione la deducibilità $\Gamma \vdash \varphi$ con la conseguenza semantica $\Gamma \models \varphi$ ; spiega perché una sola clausola, quella del connettivo primitivo, basta a dare significato a tutto il linguaggio, e perché i valori di verità si calcolano con polinomi; mostra con una tavola di quattro righe ciò che la semantica decide senza cercare deduzioni né inventare marcature; precisa ciò che si prende dalle unità precedenti e dà consigli per studiarla.

Obiettivi di apprendimento

Descrivere la sequenza delle sei lezioni dell’unità e spiegare quali risultati di ciascuna usa la successiva.
Collocare la semantica nel percorso del corso, distinguere la conseguenza semantica $\Gamma \models \varphi$ dalla deducibilità $\Gamma \vdash \varphi$ e spiegare che cosa affermeranno la correttezza e la completezza.
Spiegare perché la bivalenza e la vero-funzionalità permettono di dare significato a tutte le formule con una sola clausola, e decidere con una tavola di verità se uno schema di ragionamento è valido.
Riconoscere ciò che l’unità prende dalle precedenti, distinguere i simboli $=$ , $\eqsem$ , $\dashv\vdash$ , $\leftrightarrow$ e $\Leftrightarrow$ , e organizzare 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 quindici domande sono di due tipi. Le prime quattro toccano ciò che l’unità dà per noto dalla prima: la definizione per ricorsione e la leggibilità unica, le abbreviazioni ufficiali, i casi di un’induzione sulla complessità e la sostituzione di una sottoformula; chi ne sbaglia una deve ripassare, prima di proseguire, la lezione che la domanda nomina. Le undici restanti toccano, in ordine, le sei lezioni di questa unità: due la prima, due la seconda, una la terza e due ciascuna delle ultime tre. Chi non ha mai studiato la semantica di un linguaggio formale 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à precedentiUna funzione sulle formule si definisce dando il suo valore in ogni variabile e una regola che calcola il valore di $\sigI\varphi\psi$ a partire da $\varphi$ , da $\psi$ e dai valori di entrambe. Che cosa garantisce che così resti definita esattamente una funzione?
La leggibilità unica: ogni formula composta si scompone in un solo modo nel suo disco iniziale e nelle sue due componenti.
Che la regola restituisca sempre $0$ o $1$ .
Niente: bisognerebbe verificare il valore formula per formula, e siccome sono infinite, non si può fare.
Che anche le abbreviazioni $\neg$ , $\vee$ e $\wedge$ abbiano leggibilità unica.
Domanda 2Dalle unità precedentiCon le abbreviazioni ufficiali del corso, quale formula è $(\varphi \vee \varphi)$ ?
La stessa stringa di $\neg\neg\varphi$ .
La stessa $\varphi$ , per l’idempotenza.
$(\varphi \downarrow \varphi)$ .
Nessuna: una disgiunzione esige due formule distinte.
Domanda 3Dalle unità precedentiPer dimostrare per induzione sulla complessità che tutte le formule hanno una certa proprietà, quali casi bisogna trattare?
Le variabili e l’unica regola di formazione, $\sigI\varphi\psi$ , cioè $(\varphi \downarrow \psi)$ .
Le variabili, la negazione, la congiunzione e la disgiunzione.
Solo la regola $(\varphi \downarrow \psi)$ : le variabili sono un caso particolare.
Le variabili e i sei connettivi $\neg$ , $\vee$ , $\wedge$ , $\rightarrow$ , $\leftrightarrow$ e $\veebar$ .
Domanda 4Dalle unità precedentiSostituendo la formula $\alpha$ con la formula $\beta$ in $\varphi$ , secondo la definizione della lezione sull’induzione, quali occorrenze di $\alpha$ si cambiano?
Tutte le sue occorrenze come sottoformula, contemporaneamente.
Solo la prima, leggendo la stringa da sinistra a destra.
Solo quelle che si vedono nella scrittura abbreviata.
Quelle di $\alpha$ e, dopo, quelle che compaiono nelle copie di $\beta$ .
Domanda 5Un’assegnazione dà a $p$ il valore $0$ e a $q$ il valore $1$ . Se $(\varphi \downarrow \psi)$ vale $1$ esattamente quando $\varphi$ e $\psi$ valgono $0$ , quale valore assume la formula $(p \downarrow (q \downarrow p))$ ?
$1$ .
$0$ , perché $q$ vale $1$ .
Non si può calcolare senza conoscere i valori delle altre variabili.
Dipende da come si raggruppano le componenti.
Domanda 6Che cosa significa $\not\models \varphi$ ?
Che qualche assegnazione dà a $\varphi$ il valore $0$ : $\varphi$ non è valida.
Che $\varphi$ è una contraddizione.
Che nessuna assegnazione soddisfa $\varphi$ .
Che $\varphi$ non si deduce nel sistema del corso.
Domanda 7Si sa che $\Gamma \cup \{\varphi\} \models \psi$ : ogni assegnazione che soddisfa $\Gamma$ e $\varphi$ soddisfa $\psi$ . Che cosa ne segue?
$\Gamma \models (\varphi \rightarrow \psi)$ .
$\Gamma \models \psi$ .
$\Gamma \models (\psi \rightarrow \varphi)$ .
$\models (\varphi \rightarrow \psi)$ .
Domanda 8La formula $(v_{1} \vee \neg v_{1})$ è valida. Quale delle formule seguenti è valida per il teorema di sostituzione uniforme?
$(\neg v_{2} \vee \neg\neg v_{2})$ .
$(v_{1} \vee \neg v_{2})$ .
$(\neg v_{2} \vee \neg v_{3})$ .
Nessuna: la sostituzione uniforme permette solo di cambiare alcune variabili con altre.
Domanda 9Secondo la convenzione del corso, quale formula designa l’espressione $v_{1} \wedge v_{2} \wedge v_{3}$ , scritta senza parentesi?
$((v_{1} \wedge v_{2}) \wedge v_{3})$ .
$(v_{1} \wedge (v_{2} \wedge v_{3}))$ .
I due raggruppamenti, perché sono la stessa stringa.
Nessuna: senza parentesi l’espressione non designa nulla.
Domanda 10Una funzione di verità di due argomenti assegna un valore, $0$ o $1$ , a ciascuna delle quattro righe $(1, 1)$ , $(1, 0)$ , $(0, 1)$ e $(0, 0)$ . Quante funzioni di verità di due argomenti ci sono?
Domanda 11Può una formula scritta solo con $\wedge$ e $\vee$ a partire dalle variabili valere $0$ nell’assegnazione che dà $1$ a tutte le variabili?
No: ogni formula scritta solo con $\wedge$ e $\vee$ vale $1$ in quell’assegnazione.
Sì, se si annidano abbastanza congiunzioni e disgiunzioni.
Sì: siccome la negazione congiunta basta da sola, bastano anche la congiunzione e la disgiunzione.
Non si può sapere senza scrivere la tavola di ogni formula.
Domanda 12Un letterale è una variabile o la negazione di una variabile. Quale delle formule seguenti è un letterale?
$\neg v_{2}$ .
$\neg\neg v_{1}$ .
$(v_{1} \wedge v_{2})$ .
$\top$ .
Domanda 13È valida la forma normale congiuntiva $(\neg v_{1} \vee v_{2} \vee v_{1}) \wedge (v_{3} \vee \neg v_{2})$ ?
No: la seconda clausola non contiene nessuna coppia complementare, e l’assegnazione che dà $0$ a $v_{3}$ e $1$ a $v_{2}$ la refuta.
Sì: la prima clausola contiene una coppia complementare, e ne basta una.
Sì, perché è soddisfacibile.
Non si può decidere senza una tavola di otto righe.
Domanda 14Per portare una formula in forma normale disgiuntiva si distribuisce la congiunzione sulla disgiunzione. Qual è la regola giusta?
$(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee (\varphi \wedge \chi))$ .
$(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee (\varphi \vee \chi))$ .
$(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \vee \psi) \wedge (\varphi \vee \chi))$ .
$(\varphi \wedge (\psi \vee \chi)) \longmapsto ((\varphi \wedge \psi) \vee \chi)$ .
Domanda 15Un circuito ha due interruttori diretti, delle leve $p$ e $q$ , collegati in serie, e quel blocco è in parallelo con un interruttore diretto della leva $r$ . Quale formula dice quando conduce?
$((p \wedge q) \vee r)$ .
$((p \vee q) \wedge r)$ .
$((p \wedge q) \wedge r)$ .
$((p \vee q) \vee r)$ .