Dimostrazione con implicazione
Ricordando che
PROP
principio di induzione
sottoformule
funzione valutazione
lemma da dimostrare
ho dei problemi con la dimostrazione di una proprietà. Se dico che una certa proprietà \(A\) vale per \(\varphi \in PROP\) intendo dire che \(A(\varphi)\) è vera. Se la proprietà contiene una implicazione, del tipo
\[
\begin{split}
A(\varphi):=
\forall p_{i}\in sub(\varphi)(v(p_{i})=v'(p_{i}))
&\Rightarrow v(\varphi)=v'(\varphi) \\
A_{1}
&\Rightarrow A_{2}
\end{split}
\]
(vale a dire: Se due funzioni valutazione danno lo stesso risultato per per le proposizioni atomiche, a meno dell'absurdum, che ricorrono in una proposizione, allora le valutazioni danno lo stesso risultato per la proposizione. Per quanto ho visto è il lemma che legittima l'uso delle tavole di verità nella verifica delle tautologie)
mi trovo in difficoltà quando devo usare la verità della proprietà, ovvero dell'implicazione. Procedo adesso al primo punto della dimostrazione per induzione.
\(1.\) La proprietà è vera per le proposizioni atomiche. Se \(\varphi=p_{i}\) allora \(sub(p_{i})=\{p_{i}\}\) e per \(A_{1}\) vale \(v(p_{i})=v'(p_{i})\) quindi \(v(\varphi)=v'(\varphi)\). Se \(\varphi=\perp\) allora \(sub(\perp)=\{\perp\}\) ma non esiste \(p_{i}\in \{\perp\}\) allora penso si possa parlare di vacuous truth.
Sapendo la tavola di verità dell'implicazione, schematicamente nel caso dell'absurdum ci troviamo nella situazione \(0X\rightarrow 1\) in quanto \(01,00\rightarrow 1\) ovvero basta che la prima proposizione sia falsa perché l'implicazione sia vera. Chiarito questo ritorno alla dimostrazione nel caso di \(\varphi=p_{i}\). Cosa significa rigorosamente mostrare che l'implicazione è vera per \(p_{i}\) (in riferimento alla tavola di verità)? A me sembra di avere usato \(11\rightarrow 1\).
A questo punto non so più come devo usare le condizioni del dominio (\(00,01,11\)) quando suppongo vera una implicazione. Basta che ne prenda una a scelta? Perché? Il lemma lo saprei dimostrare completando anche i punti \(2\) e \(3\) del principio di induzione usando la proprietà in modo naiv, a meno del vacuous truth, solamente vorrei capire bene come funziona perché ho paura di essere troppo arbitrario.
PROP
principio di induzione
sottoformule
funzione valutazione
lemma da dimostrare
ho dei problemi con la dimostrazione di una proprietà. Se dico che una certa proprietà \(A\) vale per \(\varphi \in PROP\) intendo dire che \(A(\varphi)\) è vera. Se la proprietà contiene una implicazione, del tipo
\[
\begin{split}
A(\varphi):=
\forall p_{i}\in sub(\varphi)(v(p_{i})=v'(p_{i}))
&\Rightarrow v(\varphi)=v'(\varphi) \\
A_{1}
&\Rightarrow A_{2}
\end{split}
\]
(vale a dire: Se due funzioni valutazione danno lo stesso risultato per per le proposizioni atomiche, a meno dell'absurdum, che ricorrono in una proposizione, allora le valutazioni danno lo stesso risultato per la proposizione. Per quanto ho visto è il lemma che legittima l'uso delle tavole di verità nella verifica delle tautologie)
mi trovo in difficoltà quando devo usare la verità della proprietà, ovvero dell'implicazione. Procedo adesso al primo punto della dimostrazione per induzione.
\(1.\) La proprietà è vera per le proposizioni atomiche. Se \(\varphi=p_{i}\) allora \(sub(p_{i})=\{p_{i}\}\) e per \(A_{1}\) vale \(v(p_{i})=v'(p_{i})\) quindi \(v(\varphi)=v'(\varphi)\). Se \(\varphi=\perp\) allora \(sub(\perp)=\{\perp\}\) ma non esiste \(p_{i}\in \{\perp\}\) allora penso si possa parlare di vacuous truth.
Sapendo la tavola di verità dell'implicazione, schematicamente nel caso dell'absurdum ci troviamo nella situazione \(0X\rightarrow 1\) in quanto \(01,00\rightarrow 1\) ovvero basta che la prima proposizione sia falsa perché l'implicazione sia vera. Chiarito questo ritorno alla dimostrazione nel caso di \(\varphi=p_{i}\). Cosa significa rigorosamente mostrare che l'implicazione è vera per \(p_{i}\) (in riferimento alla tavola di verità)? A me sembra di avere usato \(11\rightarrow 1\).
A questo punto non so più come devo usare le condizioni del dominio (\(00,01,11\)) quando suppongo vera una implicazione. Basta che ne prenda una a scelta? Perché? Il lemma lo saprei dimostrare completando anche i punti \(2\) e \(3\) del principio di induzione usando la proprietà in modo naiv, a meno del vacuous truth, solamente vorrei capire bene come funziona perché ho paura di essere troppo arbitrario.
Risposte
Detto altrimenti: consideriamo una proprietà \(A:=A_{0}\Rightarrow A_{1}\) dell'insieme delle proposizioni. Devo mostrare \((ii)\) la seconda proprietà del principio di induzione quindi devo iniziare supponendo \(A(\varphi)\) vera per una qualche proposizione. Mi servono però anche informazioni su \(A_{0}(\varphi),A_{1}(\varphi)\) per potere dimostrare \((ii)\). \(A(\varphi)\) può essere vera in diversi modi. Attraverso
\(1.\) la falsità di \(A_{0}(\varphi)\) e la falsità \(A_{1}(\varphi)\)
\(2.\) la falsità di \(A_{0}(\varphi)\) e la verità \(A_{1}(\varphi)\)
\(3.\) la verità di \(A_{0}(\varphi)\) e la verità \(A_{1}(\varphi)\)
Quindi io devo mostrare la seconda proprietà in tutti e tre i casi, se non sono esclusi a priori in qualche modo?
\(1.\) la falsità di \(A_{0}(\varphi)\) e la falsità \(A_{1}(\varphi)\)
\(2.\) la falsità di \(A_{0}(\varphi)\) e la verità \(A_{1}(\varphi)\)
\(3.\) la verità di \(A_{0}(\varphi)\) e la verità \(A_{1}(\varphi)\)
Quindi io devo mostrare la seconda proprietà in tutti e tre i casi, se non sono esclusi a priori in qualche modo?
Ciao, ho letto quello che hai scritto ma non ho capito cosa c'entra con quello che devi fare. Infatti secondo me devi fare questo:
Considerata la proprietà $A(\phi) := (v(\phi) = v'(\phi))$, le ipotesi del lemma 1.2.3 forniscono la base di induzione ovvero ti dicono che $A(p_i)$ è vero per ogni atomo $p_i \in s ub (\phi)$ ed inoltre $A(\bot)$ è vero semplicemente per la definizione di funzione di valutazione infatti $v(\bot) = 0 = v'(\bot)$. Quindi procediamo per casi, indagando la struttura di $\phi$
Se $\phi := \psi ^^ \chi$ allora per l'ipotesi di induzione hai che $A(\psi)$ è vera e $A(\chi)$ è vera quindi facciamo il passo induttivo: $v(\phi) = v(\psi ^^ \chi) = min (v(\psi), v(\chi)) = min (v'(\psi), v'(\chi)) = v'(\psi ^^ \chi)= v'(\phi)$
Se $\phi := \psi vv \chi$ allora per l'ipotesi di induzione hai che $A(\psi)$ è vera e $A(\chi)$ è vera quindi facciamo il passo induttivo: $v(\phi) = v(\psi vv \chi) = max (v(\psi), v(\chi)) = max (v'(\psi), v'(\chi)) = v'(\psi vv \chi)= v'(\phi)$
etc etc per gli altri connettivi, ed infine per la negazione
Se $\phi := not \psi$ allora per l'ipotesi di induzione hai che $A(\psi)$ è vera e quindi $v(\phi) = v(not \psi) = 1 - v(\psi) = 1 - v'(\psi) = v'(not \psi) = v'(\phi)$
Fine
Considerata la proprietà $A(\phi) := (v(\phi) = v'(\phi))$, le ipotesi del lemma 1.2.3 forniscono la base di induzione ovvero ti dicono che $A(p_i)$ è vero per ogni atomo $p_i \in s ub (\phi)$ ed inoltre $A(\bot)$ è vero semplicemente per la definizione di funzione di valutazione infatti $v(\bot) = 0 = v'(\bot)$. Quindi procediamo per casi, indagando la struttura di $\phi$
Se $\phi := \psi ^^ \chi$ allora per l'ipotesi di induzione hai che $A(\psi)$ è vera e $A(\chi)$ è vera quindi facciamo il passo induttivo: $v(\phi) = v(\psi ^^ \chi) = min (v(\psi), v(\chi)) = min (v'(\psi), v'(\chi)) = v'(\psi ^^ \chi)= v'(\phi)$
Se $\phi := \psi vv \chi$ allora per l'ipotesi di induzione hai che $A(\psi)$ è vera e $A(\chi)$ è vera quindi facciamo il passo induttivo: $v(\phi) = v(\psi vv \chi) = max (v(\psi), v(\chi)) = max (v'(\psi), v'(\chi)) = v'(\psi vv \chi)= v'(\phi)$
etc etc per gli altri connettivi, ed infine per la negazione
Se $\phi := not \psi$ allora per l'ipotesi di induzione hai che $A(\psi)$ è vera e quindi $v(\phi) = v(not \psi) = 1 - v(\psi) = 1 - v'(\psi) = v'(not \psi) = v'(\phi)$
Fine
Grazie per la risposta. I lemma 1.2.3 è quello che devo dimostrare. Mi dice che se considero la subformula di un predicato \(\varphi\) e due funzioni di valutazione danno lo stesso risultato sui predicati atomici (escluso \(\perp\)) della subformula di \(\varphi\), allora le funzioni danno lo stesso risultato per il predicato.
Sapresti mostrarmi il lemma 1.2.3 al secondo punto del principio di induzione? Non ho capito perché hai scritto la proprietà in quel modo. Da quanto ho capito dell'enunciato la proprietà è quella in OP. No?
Sapresti mostrarmi il lemma 1.2.3 al secondo punto del principio di induzione? Non ho capito perché hai scritto la proprietà in quel modo. Da quanto ho capito dell'enunciato la proprietà è quella in OP. No?
"5mrkv":
Sapresti mostrarmi il lemma 1.2.3
L'ho appena fatto, quella che ho scritto è la dimostrazione del lemma 1.2.3 !
Forse ti ho confuso quando ho detto "utilizzando le ipotesi..." però vedi ogni teorema ha delle ipotesi ed una tesi e bisogna utilizzare le ipotesi per mostrare la tesi... xD Vabbè cmq vedo che hai risposto alle 3 di notte, magari ti rileggi tutto con calma di giorno e poi mi dici..."5mrkv":
Non ho capito perché hai scritto la proprietà in quel modo. Da quanto ho capito dell'enunciato la proprietà è quella in OP. No?
No, nel tuo primo post tu hai preso tutto l'enunciato del teorema e l'hai ficcato nella proprietà $A$. Secondo me ti fai ingannare dalla forma dell'enunciato. Pensala così: sapendo che $v(p_i)= v'(p_i)$ per un certo insieme di atomi ${p_1, ... , p_n }$ mostrare che risulta $v(\phi) = v'(\phi)$ per tutte le formule $\phi$ che contengono soltanto gli atomi $p_1, ... , p_n$. Ti piace di più in questa forma? Lo schema è esattamente quello del principio di induzione di cui tu hai linkato la definizione, ma la base di induzione è ristretta ad un sottoinsieme dell'insieme di tutti gli atomi e quindi la verità della proprietà $A$ è limitata alle sole proposizioni che contengono quegli atomi (anzichè a tutto PROP cone nella tua def. ).
P.S. Che testo è quello ? van Dalen ?
"perplesso":
L'ho appena fatto, quella che ho scritto è la dimostrazione del lemma 1.2.3 !
Ho immaginato che volessi mostrarlo ma non ero sicuro in quanto non riesco a capire come mai la proprietà possa essere scritta in quel modo.
xD Vabbè cmq vedo che hai risposto alle 3 di notte, magari ti rileggi tutto con calma di giorno e poi mi dici...
Mi sono svegliato presto
"perplesso":
No, nel tuo primo post tu hai preso tutto l'enunciato del teorema e l'hai ficcato nella proprietà $A$. Secondo me ti fai ingannare dalla forma dell'enunciato. Pensala così: sapendo che $v(p_i)= v'(p_i)$ per un certo insieme di atomi ${p_1, ... , p_n }$ mostrare che risulta $v(\phi) = v'(\phi)$ per tutte le formule $\phi$ che contengono soltanto gli atomi $p_1, ... , p_n$. Ti piace di più in questa forma? Lo schema è esattamente quello del principio di induzione di cui tu hai linkato la definizione, ma la base di induzione è ristretta ad un sottoinsieme dell'insieme di tutti gli atomi e quindi la verità della proprietà $A$ è limitata alle sole proposizioni che contengono quegli atomi (anzichè a tutto PROP cone nella tua def. ).
Io vorrei mostrarla come è posta nel libro ma proprio non capisco allora come costruire questa proprietà! Se tu mi dici che la proprietà è \(A(\varphi)=(v(\varphi)=v'(\varphi))\) allora questa proprietà non può valere per tutto \(PROP\)! Vale per tutto \(PROP\) solo se aggiungo che la funzione di valutazione concorda sugli elementi \(p_{i}\) della subformula* (che è quello bisogna dimostrare). Nella definizione di induzione su \(PROP\) però è usata solamente una generica proprietà \(A(\varphi)\) senza condizioni esterne. Segue che la condizione
P.S. Che testo è quello ? van Dalen ?
Esatto.
"5mrkv":
Nella definizione di induzione su PROP però è usata solamente una generica proprietà A(φ) senza condizioni esterne. Segue che la condizionedeve appartenere alla proprietà stessa.
Ok scusa non avevo capito che l'induzione la puoi applicare solo in quel modo lì, cmq dal punto di vista della dimostrazione non dovrebbe cambiare molto. Mettiamo $A$ come l'hai definita nel primo post, la base di induzione l'hai già fatta, ora nel passo successivo devi analizzare la struttura di $\phi$, per esempio
se $\phi = \psi ^^ \chi$ e per ipotesi di induzione sai che $A(\psi)$ e $A(\chi)$ sono vere allora supponiamo che risulti $v(p_i) = v'(p_i)$ per ogni atomo $p_i$ che occorre in $\phi$ e partendo da questa supposizione dobbiamo provare che $v(\phi)=v'(\phi)$. Prima di tutto notiamo che da $v(p_i) = v'(p_i) \forall p_i \in s ub (\phi)$ segue a maggior ragione
$v(p_i) = v'(p_i) \forall p_i \in s ub (\psi)$
e
$v(p_i) = v'(p_i) \forall p_i \in s ub (\chi)$
e quindi usando le implicazioni $A(\psi)$ e $A(\chi)$, che sappiamo essere vere per ipotesi induttiva, ricaviamo che $v(\psi)=v'(\psi)$ e $v(\chi)= v'(\chi)$ e con un facile calcolo
$v(\phi)= v( \psi ^^ \chi ) = min (v(\psi), v(\chi)) = min (v'(\psi), v'(\chi)) = v' ( \psi ^^ \chi ) = v'(\phi)$
e con questo abbiamo provato la correttezza dell'implicazione
$(v(p_i) = v'(p_i) \forall p_i \in s ub (\phi) ) => v(\phi) = v'(\phi)$
cioè la verità di $A(\phi)$. Analogamente per gli altri casi.
Io invece volevo operare in un altro modo, cioè restringendo l'alfabeto del linguaggio. Prendiamo in esame un insieme finito di atomi $S = {p_1,...,p_n}$. definiamo l'insieme delle formule che usano questi atomi
Definizione $PROP_S$ è il più piccolo insieme tale che
(i) $p_1, ... , p_n, \bot \in PROP_S$
(ii) se $\psi, \chi \in PROP_S$ allora $\psi ^^ \chi \in PROP_S$ (analogamente per $vv$, $->$ etc etc)
(iii) se $\psi \in PROP_S$ allora $(not \psi) \in PROP_S$
Notare che $PROP_S \subset PROP$
Quindi enunciavo il principio di induzione su $PROP_S$
Principio di induzione
Se una proprietà $A$ definita su $PROP_S$ è tale che
(i) $A(p_i)$ è vera per ogni $p_i \in S \cup {\bot}$
(ii) se $A(\psi)$ e $A(\phi)$ con $\phi, \psi \in PROP_S$ sono vere allora $A(\psi ^^ \phi)$ è vera
(e analogamente per gli altri connettivi)
allora $A(\phi)$ è vera per ogni $\phi \in PROP_S$
e poi usavo questo principio per stendere la dimostrazione come nel mio primo post... Emh... pensandoci forse è meglio seguire l'impostazione di van Dalen... xD
Ok perplesso grazie mille per la disponibilità 
Leggerò con calma.
Leggerò con calma.
Ok ho ricollegato la dimostrazione di induzione con implicazione al caso intuitivo. Nel caso di una proprietà \(A=(A_{0}\Box A_{1})\) nel passo base devo mostrare che non ci sono casi in cui al variare della verità di \(A_{0},A_{1}\) risulti falsa \(A\).
Nel passo induttivo devo considerare invece tutti i casi per cui \(A_{0},A_{1}\) rendono \(A\) vero. Per noi \(\Box = \rightarrow \) e \(A_{1}\) dipende da \(A_{0}\) per cui basta verificare \(A_{0}=0,1\). Quando \(A_{0}=0\) sappiamo già che l'implicazione è vera quindi possiamo fare a meno di fare calcoli. Ora basta porre \(A_{0}=1\) e verificare che \(A_{1}=1\).
Sostanzialmente ritorniamo al ragionamento per cui supposto \(A_{0}\) si verifica che vale \(A_{1}\) e quando \(A_{0}=0\) prendiamo la proprietà per vera parlando di vacuous truth.
Nel passo induttivo devo considerare invece tutti i casi per cui \(A_{0},A_{1}\) rendono \(A\) vero. Per noi \(\Box = \rightarrow \) e \(A_{1}\) dipende da \(A_{0}\) per cui basta verificare \(A_{0}=0,1\). Quando \(A_{0}=0\) sappiamo già che l'implicazione è vera quindi possiamo fare a meno di fare calcoli. Ora basta porre \(A_{0}=1\) e verificare che \(A_{1}=1\).
Sostanzialmente ritorniamo al ragionamento per cui supposto \(A_{0}\) si verifica che vale \(A_{1}\) e quando \(A_{0}=0\) prendiamo la proprietà per vera parlando di vacuous truth.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo