Roberto Zunino, 2015
Diamo qui sotto una piccola lista di consigli per l'esame scritto. In particolare, elenchiamo alcuni errori da evitare.
Se \(f\) è monotona, il fatto che \(f(X)\subseteq f(Y)\) non implica che \(X \subseteq Y\). Un controesempio banale è la funzione \(f(Z) = \emptyset\) per ogni \(Z\). Come esercizio, potete cercare controesempi meno banali, ad esempio estendendo \( f(\{1,2\}) = \{3\} \subseteq f(\{2,3\}) = \{3,4\} \) a una funzione monotona su tutto \(\powset(\N)\).
Si noti che il principio di induzione associato ad un insieme di regole parla sempre di un proprietà (o insieme o relazione) \(p\) da dimostrare. Volendo fare un esempio concreto, prendiamo le regole per i numeri naturali \(\N\).
\[ \dfrac{}{0} \qquad \dfrac{x}{x+1} \]
[Errore 1] Il principio di induzione associato a queste regole NON è \(\Regh(\N) \subseteq \N\), che espanso diventa
\[ \begin{array}{l} 1)\ 0\in\N \\ 2)\ \forall x.\ x \in \N \implies x+1\in \N \end{array} \]
Questo dice solo che \(\N\) è chiuso rispetto allo zero e al successore, così come lo sono anche gli altri insiemi numerici \(\Z,\R\,\ldots\). L'affermazione di sopra è vera, ma NON è il principio di induzione sui naturali.
[Errore 2] Il principio di induzione NON è nemmeno il seguente: se \(p\) è un predicato sui naturali, allora vale che
\[ \begin{array}{l} 1)\ p(0) \\ 2)\ \forall x.\ p(x) \implies p(x+1) \end{array} \]
Qui compare correttamente un predicato \(p\) sui naturali da dimostrare, cosa che non si faceva prima. Però, scorrettamente, si afferma che un \(p\) arbitrario deve soddisfare 1) e 2). Questo non può valere per ogni \(p\): per esempio \(p(n): n\neq 0\) banalmente viola 1). Quindi, non solo NON è il principio di induzione, ma non è nemmeno vero!
[Risposta corretta] Il principio di induzione sui numeri naturali invece dice che (come sappiamo), se \(p\) è un predicato sui naturali, per dimostrare \(\forall n\in \N.\ p(n)\) è sufficiente dimostrare che
\[ \begin{array}{l} 1)\ p(0) \\ 2)\ \forall x.\ p(x) \implies p(x+1) \end{array} \]
Si noti come si parla sempre di un predicato \(p\), come prima, ma 1) e 2) ora sono le ipotesi del principio di induzione, non la tesi! Questo, in formule, corrisponde a \(\Regh(p)\subseteq p \implies \N\subseteq p\), che è il principio di induzione associato a \(\N\).
Per fare un altro esempio, se \(T\) è l'insieme degli alberi binari di naturali, definito induttivamente dalle regole
\[ \dfrac{}{n}(n\in\N) \qquad \dfrac{s\quad d}{(s,d)} \]
[Errore 1] il principio di induzione associato NON è
\[ \begin{array}{l} 1)\ \forall n\in\N. n \in T \\ 2)\ \forall s,d.\ s\in T \land d\in T \implies (s,d)\in T \end{array} \]
[Errore 2] NON è nemmeno: se \(p\) è un predicato sugli alberi, allora vale \[ \begin{array}{l} 1)\ \forall n\in\N. p(n) \\ 2)\ \forall s,d.\ p(s) \land p(d) \implies p(s,d) \end{array} \]
[Risposta corretta] Invece è: se \(p\) è un predicato sugli alberi, per dimostrare che per ogni albero \(t\in T\) vale \(p(t)\), è sufficiente dimostrare che \[ \begin{array}{l} 1)\ \forall n\in\N. p(n) \\ 2)\ \forall s,d.\ p(s) \land p(d) \implies p(s,d) \end{array} \]
dove in \(p(n)\) il simbolo \(n\) denota l'albero che contiene solo il naturale \(n\). Si noti, ancora una volta, che si parla di una proprietà \(p\) da dimostrare sugli alberi in \(T\).
Ancora un esempio: sia \(R\in\mathcal P(T\times \mathbb N)\) una relazione binaria tra alberi di naturali e naturali, definita induttivamente dalle regole di inferenza \[ \dfrac{}{R(n,n)} \qquad \dfrac{R(s,n)\quad R(d,m)}{R((s,d),n+m)} \]
[Errore 1] Il principio di induzione su \(R\) NON è \[ \begin{array}{l} 1) \forall n.\ R(n,n) \\ 2) \forall s,d,n,m.\ R(s,n) \land R(d,m) \implies R((s,d), n+m) \end{array} \]
[Errore 2] NON è nemmeno: se \(p(-,-)\) è un predicato su alberi e naturali, allora vale \[ \begin{array}{l} 1) \forall n.\ p(n,n) \\ 2) \forall s,d,n,m.\ p(s,n) \land p(d,m) \implies p((s,d), n+m) \end{array} \]
[Errore 3] NON è nemmeno: se \(p(-,-)\) è un predicato su alberi e naturali, per dimostrare che per ogni albero \(t\in T\) e naturale \(n\in\mathbb N\) vale \(p(t,n)\), è sufficiente dimostrare che \[ \begin{array}{l} 1) \forall n.\ p(n,n) \\ 2) \forall s,d,n,m.\ p(s,n) \land p(d,m) \implies p((s,d), n+m) \end{array} \]
[Risposta corretta] Invece è: se \(p(-,-)\) è un predicato su alberi e naturali, per dimostrare che per ogni albero \(t\in T\) e naturale \(n\in\mathbb N\) tale che \(R(t,n)\) vale \(p(t,n)\), è sufficiente dimostrare che \[ \begin{array}{l} 1) \forall n.\ p(n,n) \\ 2) \forall s,d,n,m.\ p(s,n) \land p(d,m) \implies p((s,d), n+m) \end{array} \]
Si consiglia inoltre di leggere le soluzioni degli scritti passati e notare quali principi di induzione sono stati generati dalle regole. In particolare, in tali soluzioni sono anche mostrati principi di induzione tratti da insiemi di regole che definiscono induttivamente sia insiemi che relazioni.
Nel caso generale, ricordiamo qui sotto alcune caratteristiche del principio di induzione, che si possono applicare in pratica quando lo si genera dalle regole:
Si raccomanda sempre di verificare quanto sopra quando si genera il principio di induzione dalle regole. Negli esercizi, questo è un passo importante. Infatti, spesso dopo averlo generato bisogna usarlo per dimostrare una \(p\) data. Se si sbaglia a generarlo, la dimostrazione di \(p\) sarà di conseguenza scorretta, in quanto viziata dall'errore a monte.
Si consiglia di definire sempre il predicato/insieme/relazione \(p(\ldots)\) che si vuole dimostare per induzione. A volte viene dato dal testo dell'esercizio, altre va ricavato con qualche manipolazione di formule dalla tesi (in genere suggerita nel testo). Su tale \(p\) viene poi applicato un principio di induzione (in genere si suggerisce quale usare) e quindi si verificano i vari casi risultanti.
Anche se non vi si chiedono i passaggi formali per dimostrare le formule che appaiono durante la soluzione degli esercizi, è fondamentale che tali formule siano gestite correttamente.
Per esempio, se per ipotesi avete un OR tra due formule, non potete assumere che valgano entrambe.
Allo stesso modo, un'ipotesi della forma \(p(x)\) è diversa da un'ipotesi \(\forall x.\ p(x)\). A volte il quantificatore \(\forall\) viene omesso e considerato implicitamente, ma in tal caso bisogna stare molto attenti a come viene usato, specialmente se ci sono altre variabili che incidentalmente chiamiamo \(x\).
Concretamente, se abbiamo una proprietà definita come \(q(x):\ \forall y\in\N.\ y + 1\neq x\) e vogliamo istanziare questa proprietà come \(q(y)\), dobbiamo prestare attenzione a non scrivere \(\forall y\in\N.\ y + 1\neq y \) che è una banale verità, ma a rinominare correttamente la variabile quantificata e scrivere invece \(\forall \bar y\in\N.\ \bar y + 1\neq y \) che è equivalente sui naturali a dire \(y = 0\). Nel dubbio, conviene sempre essere espliciti nei quantificatori, e rinominare le variabili quantificate non appena ne "compare" un'altra con lo stesso nome.
Un altro errore è il seguente. Se devo dimostrare \(\forall x.\ p(x) \implies q(x)\) devo prima introdurre il quantificatore \(\forall\) e poi il connettivo \(\implies\). Di solito, si fanno entrambi i passi contemporaneamente. Un errore abbastanza frequente qui è quello di introdurre il connettivo \(\implies\) senza curarsi del \(\forall\), prendendo come ipotesi \(\forall x. p(x)\) e nuova tesi \(q(x)\).
Questo è errato: è come se, per dimostrare che "per ogni x, se \(x \geq 10\) allora \(x \geq 5\)", partissimo supponendo per ipotesi che "per ogni x, \(x \geq 10\)". Non solo le regole logiche non ci consentono di assumere tale ipotesi. Questo errore ci fa mettere a ipotesi una formula falsa, dalla quale ricaviamo un assurdo prendendo per esempio \(x = 7\), che consente di dimostrare qualunque tesi! In poche parole, un errore simile ci consentirebbe di dimostrare pure enunciati falsi come "per ogni x, se \(x \geq 10\) allora \(x \geq 42\)".
Se dovete dimostrare \(R(a,b,c)\) come tesi, dove \(R\) è definita tramite regole, allora dovete esibire/costruire una derivazione per tale tesi. Se avete invece un'ipotesi \(R(a,b,c)\) allora potete invertirla per esaminare quali regole potrebbero averla causata (o in generale in quali modi potrebbe finire una derivazione per quella ipotesi). Notate che la tesi non si inverte mai!
Nell'annotare i programmi con le opportune asserzioni, vanno seguite le regole delle triple di Hoare, e non "andare ad intuito". L'intuizione gioca comunque un ruolo fondamentale per capire come procedere, ma la soluzione deve rispettare le regole formali e "meccaniche" delle triple. Per esempio, questo è scorretto: \[ \begin{array}{l} \hoareA{n \mbox{ pari}} \\ n := n+1 \\ \hoareA{n \mbox{ dispari}} \end{array} \] mentre questo è corretto: \[ \begin{array}{l} \hoareA{n \mbox{ pari}} \\ \hoareA{(n+1) \mbox{ dispari}} \\ n := n+1 \\ \hoareA{n \mbox{ dispari}} \end{array} \] Qui sopra le asserzioni attorno all'assegnamento correttamente seguono la regola \(\hoare{P\{e/x\}}{x:=e}{P}\) delle triple: sopra l'assegnamento vi è la stessa asserzione di sotto dove \(x\) viene rimpiazzato con \(e\). Sopra poi si usa una PrePost per riscrivere \((n+1)\) dispari come \(n\) pari.
L'osservazione di sopra può apparire una pignoleria, ma non lo è: nella soluzione scorretta durante la correzione dello scritto non si capisce se lo studente ha compreso la regola, la ha applicata e poi ha direttamente semplificato facendo due passaggi in uno, o se invece non ha capito la regola e sta solo procedendo ad intuito. L'errore viene valutato in base a quanto dista dalla versione corretta: per esempio, nell'esempio sopra, l'errore non è sicuramente grave visto che è plausibile che uno possa avere semplificato mentalmente. Micro-semplificazioni come ad es. scrivere \(n\) al posto del formalmente corretto \((n+1)-1\) oppure \(n\leq 5\) al posto di \(\lnot(n\gt 5)\) non vengono considerate errori.
In sintesi, il criterio fondamentale è: la soluzione proposta mostra una comprensione delle regole per le triple di Hoare da parte dello studente?
Si consiglia di controllare quanto segue nella soluzione ad un esercizio:
Alcune domande che mi sono state poste in passato:
Home - Teaching - Informatica
Roberto Zunino, 2015