Esercizi sulla ricorsività
Salve a tutti,
fino ad ora ho ben capito che gli esercizi di ricorsività vanno a braccetto con le dimostrazioni per induzione, ma voglio ben capire se ho ben a mente il procedimento.
Su una "classica" dimostrazione per induzione ti dice di dimostrare che un predicato $p(n)$ che ne so $AA n > 0$.
Allora tu ti calcoli il basso base ovvero ti calcoli $P(1)$, se è verificato passi al passo induttivo.
Il passo induttivo altro non è che dire "Supponiamo che sia vera $P(n)$ per una n arbitraria che sia $>0$, verifichiamo se è vera $P(n+1)$.
Il tutto si riconduce quindi a dimostrare vera $P(n+1)$ mediante $P(n)$ che abbiamo suposto vero nel passo induttivo, più diciamo "altri teoremi elementari della matematica" (ovvero qualcosa di Elementare che è palese sia così, e che quindi non dimostriamo a sua volta).
Diciamo che già qui un pochino mi perdo nella scomposizione, sarà che devo fare calcoli su calcoli per aquisire manualità. Passiamo però ora agli esercizi sulla ricorsione.
L'esercizio che ho fatto è il seguente:
$\{(a_0=2),(a_n = a_(n-1) +(n+1)*2^(n+1) AA n >= 1):}$
verificare: $a_n=n*2^(n+2)+2$ $AAn >=0$
Quindi qui abbiamo una formula da verificare per induzione, e ci viene anche incontro la definizione ricorsiva $an$ per dimostrare che quella formula è vera.
Quindi ho proseguito inanzi tutto individuandomi il passo base, ovvero:
$a_0 = 0*2^2= 2$ ed il passo base è verificato perchè, nella formula ricorsiva $a_0$ è proprio uguale a $2$
Poi procediamo con il passo induttivo, ovvero:
Supponiamo vera la formula da ferificare, cioè $a_n=n*2^(n+2)+2$ $AAn >=0$, verifichiamo $a_(n+1)=(n+1)*2^(n+3)+2$ $AAn >=0$
Devo dire che ho riutilizzato meccanicamente un'altro esercizio pre-svolto, ma vediamo se il mio ragionamento è giusto.
Con la formula di prima stiamo dicendo $P(n) -> P(n+1)$ quindi se ci trovaimo vera $P(n+1)$ lo sarà per forza di cose anche $P(n)$ perchè "Vero non implica mai falso".
Inoltre, secondo il principio di induzione potremmo anche dire che questa formula è vera $AA n >= 0$ in quanto abbiamo preso un $n$ generico, e abbiamo dimostrato che la formula è vera pero il suo successivo. Quindi vuol dire che qualsiasi $n >= 0$ la formula sarà vera per il suo successivo.
Detto ciò per dimostrare $a_(n+1)$ ci viene incontro la formula ricorsiva della traccia, che ci dice come "costruirci" qualsiasi elemento della successione.
Quindi diciamo che $a_(n+1) = a_n + (n+1) * 2^(n+2)$
Per il passo induttivo, $P(n)$ che abbiamo supposto vero ci andiamo a sostituire $a_n$ ed abbiamo
$ =n*2^(n+2)+2 + (n+1) * 2^(n+2)$
E svolgendoci i calcoli troviamo proprio che è tutto uguale a:
$2^(n+3)*(n+1)+2$ che è proprio la formula che volevamo verificare.
Ovvero prendendoci la definizione ricorsiva di $an$, sfruttando il passo induttivo $P(n)$ abbiamo ottenuto proprio $p(n+1)$
Secondo voi è giusto come procedimento? a me sembra effettivamente che "non fili moltissimo", però sulla ricorsività ci sono stati dimostrati 2 esercizi contati, sul libro appena l'accenna, e questo è tutto quello che sono riuscito a produrre.
fino ad ora ho ben capito che gli esercizi di ricorsività vanno a braccetto con le dimostrazioni per induzione, ma voglio ben capire se ho ben a mente il procedimento.
Su una "classica" dimostrazione per induzione ti dice di dimostrare che un predicato $p(n)$ che ne so $AA n > 0$.
Allora tu ti calcoli il basso base ovvero ti calcoli $P(1)$, se è verificato passi al passo induttivo.
Il passo induttivo altro non è che dire "Supponiamo che sia vera $P(n)$ per una n arbitraria che sia $>0$, verifichiamo se è vera $P(n+1)$.
Il tutto si riconduce quindi a dimostrare vera $P(n+1)$ mediante $P(n)$ che abbiamo suposto vero nel passo induttivo, più diciamo "altri teoremi elementari della matematica" (ovvero qualcosa di Elementare che è palese sia così, e che quindi non dimostriamo a sua volta).
Diciamo che già qui un pochino mi perdo nella scomposizione, sarà che devo fare calcoli su calcoli per aquisire manualità. Passiamo però ora agli esercizi sulla ricorsione.
L'esercizio che ho fatto è il seguente:
$\{(a_0=2),(a_n = a_(n-1) +(n+1)*2^(n+1) AA n >= 1):}$
verificare: $a_n=n*2^(n+2)+2$ $AAn >=0$
Quindi qui abbiamo una formula da verificare per induzione, e ci viene anche incontro la definizione ricorsiva $an$ per dimostrare che quella formula è vera.
Quindi ho proseguito inanzi tutto individuandomi il passo base, ovvero:
$a_0 = 0*2^2= 2$ ed il passo base è verificato perchè, nella formula ricorsiva $a_0$ è proprio uguale a $2$
Poi procediamo con il passo induttivo, ovvero:
Supponiamo vera la formula da ferificare, cioè $a_n=n*2^(n+2)+2$ $AAn >=0$, verifichiamo $a_(n+1)=(n+1)*2^(n+3)+2$ $AAn >=0$
Devo dire che ho riutilizzato meccanicamente un'altro esercizio pre-svolto, ma vediamo se il mio ragionamento è giusto.
Con la formula di prima stiamo dicendo $P(n) -> P(n+1)$ quindi se ci trovaimo vera $P(n+1)$ lo sarà per forza di cose anche $P(n)$ perchè "Vero non implica mai falso".
Inoltre, secondo il principio di induzione potremmo anche dire che questa formula è vera $AA n >= 0$ in quanto abbiamo preso un $n$ generico, e abbiamo dimostrato che la formula è vera pero il suo successivo. Quindi vuol dire che qualsiasi $n >= 0$ la formula sarà vera per il suo successivo.
Detto ciò per dimostrare $a_(n+1)$ ci viene incontro la formula ricorsiva della traccia, che ci dice come "costruirci" qualsiasi elemento della successione.
Quindi diciamo che $a_(n+1) = a_n + (n+1) * 2^(n+2)$
Per il passo induttivo, $P(n)$ che abbiamo supposto vero ci andiamo a sostituire $a_n$ ed abbiamo
$ =n*2^(n+2)+2 + (n+1) * 2^(n+2)$
E svolgendoci i calcoli troviamo proprio che è tutto uguale a:
$2^(n+3)*(n+1)+2$ che è proprio la formula che volevamo verificare.
Ovvero prendendoci la definizione ricorsiva di $an$, sfruttando il passo induttivo $P(n)$ abbiamo ottenuto proprio $p(n+1)$
Secondo voi è giusto come procedimento? a me sembra effettivamente che "non fili moltissimo", però sulla ricorsività ci sono stati dimostrati 2 esercizi contati, sul libro appena l'accenna, e questo è tutto quello che sono riuscito a produrre.
Risposte
"Neptune":
Devo dire che ho riutilizzato meccanicamente un'altro esercizio pre-svolto, ma vediamo se il mio ragionamento è giusto.
Con la formula di prima stiamo dicendo $P(n) -> P(n+1)$ quindi se ci trovaimo vera $P(n+1)$ lo sarà per forza di cose anche $P(n)$ perchè "Vero non implica mai falso".
Inoltre, secondo il principio di induzione potremmo anche dire che questa formula è vera $AA n >= 0$ in quanto abbiamo preso un $n$ generico, e abbiamo dimostrato che la formula è vera pero il suo successivo. Quindi vuol dire che qualsiasi $n >= 0$ la formula sarà vera per il suo successivo.
La dimostrazione di per sé va bene, quello che non va bene è questa parte qua.
Il principio di induzione è uno degli assiomi di Peano per la presentazione assiomatica di [tex]\mathbb{N}[/tex]; precisamente questro assioma dice che se [tex]S \subseteq \mathbb{N}[/tex], se [tex]0 \in S[/tex] e se è vera [tex]n \in S \implies n+1 \in S[/tex], allora [tex]S=\mathbb{N}[/tex]. L'implicazione [tex]n \in S \implies n+1 \in S[/tex] può essere vera in due modi: o quando è falso [tex]n \in S[/tex] o quando sono simultanemante vere [tex]n \in S[/tex] e [tex]n+1 \in S[/tex]: ovviamente se è falso [tex]n\in S[/tex] l'implicazione è vera ma [tex]S\neq\mathbb{N}[/tex], quindi non ci facciamo niente con questa implicazione in questo caso, dacché dobbiamo usare l'implicazione in questione con [tex]n \in S[/tex] vera (e conseguentemente [tex]n+1[/tex] vera).
Il principio di induzione si applica alla dimostrazione delle proprietà su [tex]\mathbb{N}[/tex]: sia [tex]\mathcal{P}(n)[/tex] una proprietà su [tex]\mathbb{N}[/tex], se [tex]\mathcal{P}(0)[/tex] è vera ed è vera l'implicazione [tex]\mathcal{P}(n)\implies\mathcal{P}(n+1)[/tex] allora la proprietà in oggetto è vera [tex]\forall n \in \mathbb{N}[/tex]. Questa cosa può essere dimostrata: sia [tex]S:=\{n \in \mathbb{N}: \mathcal{P}(n) \text{ è vera }\}[/tex], si applica ad [tex]S[/tex] il principio di induzione e si ottiene [tex]S=\mathbb{N}[/tex].
A questo punto per quanto detto nel paragrafo in cui parlo del principio di induzione supponiamo vera [tex]\mathcal{P}(n)[/tex] e proviamo essere vera [tex]\mathcal{P}(n+1)[/tex]: quindi non stiamo dicendo che è vera [tex]\mathcal{P}(n) \implies \mathcal{P}(n+1)[/tex] e dimostrando che è vera [tex]\mathcal{P}(n+1)[/tex] ci ritroviamo che è vera [tex]\mathcal{P}(n)[/tex], ma stiamo dicendo che è vera [tex]\mathcal{P}(n)[/tex], e stiamo provando che è vera l'implicazione [tex]\mathcal{P}(n)\implies\mathcal{P}(n+1)[/tex] per potere dire che è vera [tex]\mathcal{P}(n+1)[/tex], secondo, tra l'altro, lo schema di ragionamento del modus ponens: [tex]A \land (A \implies B)[/tex] permette di dedurre [tex]B[/tex].
"WiZaRd":
[quote="Neptune"]
Devo dire che ho riutilizzato meccanicamente un'altro esercizio pre-svolto, ma vediamo se il mio ragionamento è giusto.
Con la formula di prima stiamo dicendo $P(n) -> P(n+1)$ quindi se ci trovaimo vera $P(n+1)$ lo sarà per forza di cose anche $P(n)$ perchè "Vero non implica mai falso".
Inoltre, secondo il principio di induzione potremmo anche dire che questa formula è vera $AA n >= 0$ in quanto abbiamo preso un $n$ generico, e abbiamo dimostrato che la formula è vera pero il suo successivo. Quindi vuol dire che qualsiasi $n >= 0$ la formula sarà vera per il suo successivo.
La dimostrazione di per sé va bene, quello che non va bene è questa parte qua.
Il principio di induzione è uno degli assiomi di Peano per la presentazione assiomatica di [tex]\mathbb{N}[/tex]; precisamente questro assioma dice che se [tex]S \subseteq \mathbb{N}[/tex], se [tex]0 \in S[/tex] e se è vera [tex]n \in S \implies n+1 \in S[/tex], allora [tex]S=\mathbb{N}[/tex]. L'implicazione [tex]n \in S \implies n+1 \in S[/tex] può essere vera in due modi: o quando è falso [tex]n \in S[/tex] o quando sono simultanemante vere [tex]n \in S[/tex] e [tex]n+1 \in S[/tex]: ovviamente se è falso [tex]n\in S[/tex] l'implicazione è vera ma [tex]S\neq\mathbb{N}[/tex], quindi non ci facciamo niente con questa implicazione in questo caso, dacché dobbiamo usare l'implicazione in questione con [tex]n \in S[/tex] vera (e conseguentemente [tex]n+1[/tex] vera).
Il principio di induzione si applica alla dimostrazione delle proprietà su [tex]\mathbb{N}[/tex]: sia [tex]\mathcal{P}(n)[/tex] una proprietà su [tex]\mathbb{N}[/tex], se [tex]\mathcal{P}(0)[/tex] è vera ed è vera l'implicazione [tex]\mathcal{P}(n)\implies\mathcal{P}(n+1)[/tex] allora la proprietà in oggetto è vera [tex]\forall n \in \mathbb{N}[/tex]. Questa cosa può essere dimostrata: sia [tex]S:=\{n \in \mathbb{N}: \mathcal{P}(n) \text{ è vera }\}[/tex], si applica ad [tex]S[/tex] il principio di induzione e si ottiene [tex]S=\mathbb{N}[/tex].
A questo punto per quanto detto nel paragrafo in cui parlo del principio di induzione supponiamo vera [tex]\mathcal{P}(n)[/tex] e proviamo essere vera [tex]\mathcal{P}(n+1)[/tex]: quindi non stiamo dicendo che è vera [tex]\mathcal{P}(n) \implies \mathcal{P}(n+1)[/tex] e dimostrando che è vera [tex]\mathcal{P}(n+1)[/tex] ci ritroviamo che è vera [tex]\mathcal{P}(n)[/tex], ma stiamo dicendo che è vera [tex]\mathcal{P}(n)[/tex], e stiamo provando che è vera l'implicazione [tex]\mathcal{P}(n)\implies\mathcal{P}(n+1)[/tex] per potere dire che è vera [tex]\mathcal{P}(n+1)[/tex], secondo, tra l'altro, lo schema di ragionamento del modus ponens: [tex]A \land (A \implies B)[/tex] permette di dedurre [tex]B[/tex].[/quote]
Quindi la dimostrazione per induzione ci fornisce la seguente implicazione logica:
$P(n) in S => P(n+1) in S$ dove S sarà la nostra succesione di numeri $in NN$
E come dici tu per il modun ponens se $P(n) in S$ è vera e $P(n) in S => P(n+1) in S$ è vera allora sarà vera anche $P(n+1) in S$
Quello che mi sfugge è "Come fai a dire che $p(n) in S$ è vera? Noi la supponiamo solamente.
Come dici tu "Supponiamo vera $p(n)$ e verifichiamoche sia vera l'implicazione logica $p(n) => p(n+1)$ quindi tutta la formula è vera per qualsiasi valore n".
Ma alla fine dei calcoli quello che noi facciamo è vedere se $p(n+1)$ trovato rispecchia le regole della sequenza, sfruttando si $p(n)$. Ma non ci verifichiamo $p(n)$. Oppure per l'implicazione logica di prima se $p(n)$ fosse falsa lo sarebbe anche $p(n+1)$ e quindi dimostrato $p(n+1)$ abbiamo verificato anche $p(n)$ ?
Ciao,
io ho sempre questa cosa che non capisco come mai il principio di induzione sia così poco compreso: a me sembra così naturale!
Io provo a dirtelo così: supponi di dover dimostrare che $P(10)$ è vera, di sapere che $P(1)$ è vera e di sapere che
(*) "se $P(n)$ è vera allora $P(n+1)$ è vera", per ogni $n$.
$P(1)$ è vera, quindi $P(1+1)=P(2)$ è vera (per (*)), quindi $P(2+1)=P(3)$ è vera (per (*)), quindi $P(3+1)=P(4)$ è vera (per (*)), quindi $P(4+1)=P(5)$ è vera (per (*)), quindi $P(5+1)=P(6)$ è vera (per (*)), quindi $P(6+1)=P(7)$ è vera (per (*)), quindi $P(7+1)=P(8)$ è vera (per (*)), quindi $P(8+1)=P(9)$ è vera (per (*)), quindi $P(9+1)=P(10)$ è vera (per (*)). Quindi $P(10)$ è vera.
In altre parole
$P(1) => P(2) => P(3) => P(4) => P(5) => P(6) => P(7) => P(8) => P(9) => P(10)$
Più in generale
$P(1) => P(2) => P(3) => ... => P(n)$.
Ne segue che se sai che $P(1)$ è vera, per mostrare che $P(n)$ è vera per ogni $n$ basta dimostrare (*).
-----
Te l'ho detto così perché non so se ti sia chiaro il meccanismo di ricorsione, se tutto quello che volevi era una giustificazione logica del principio di induzione allora mi scuso, è meglio che dimentichi quello che ho scritto e aspetti la risposta di Wizard.
io ho sempre questa cosa che non capisco come mai il principio di induzione sia così poco compreso: a me sembra così naturale!
Io provo a dirtelo così: supponi di dover dimostrare che $P(10)$ è vera, di sapere che $P(1)$ è vera e di sapere che
(*) "se $P(n)$ è vera allora $P(n+1)$ è vera", per ogni $n$.
$P(1)$ è vera, quindi $P(1+1)=P(2)$ è vera (per (*)), quindi $P(2+1)=P(3)$ è vera (per (*)), quindi $P(3+1)=P(4)$ è vera (per (*)), quindi $P(4+1)=P(5)$ è vera (per (*)), quindi $P(5+1)=P(6)$ è vera (per (*)), quindi $P(6+1)=P(7)$ è vera (per (*)), quindi $P(7+1)=P(8)$ è vera (per (*)), quindi $P(8+1)=P(9)$ è vera (per (*)), quindi $P(9+1)=P(10)$ è vera (per (*)). Quindi $P(10)$ è vera.
In altre parole
$P(1) => P(2) => P(3) => P(4) => P(5) => P(6) => P(7) => P(8) => P(9) => P(10)$
Più in generale
$P(1) => P(2) => P(3) => ... => P(n)$.
Ne segue che se sai che $P(1)$ è vera, per mostrare che $P(n)$ è vera per ogni $n$ basta dimostrare (*).
-----
Te l'ho detto così perché non so se ti sia chiaro il meccanismo di ricorsione, se tutto quello che volevi era una giustificazione logica del principio di induzione allora mi scuso, è meglio che dimentichi quello che ho scritto e aspetti la risposta di Wizard.
"Martino":
Ciao,
io ho sempre questa cosa che non capisco come mai il principio di induzione sia così poco compreso: a me sembra così naturale!
Io provo a dirtelo così: supponi di dover dimostrare che $P(10)$ è vera, di sapere che $P(1)$ è vera e di sapere che
(*) "se $P(n)$ è vera allora $P(n+1)$ è vera", per ogni $n$.
$P(1)$ è vera, quindi $P(1+1)=P(2)$ è vera (per (*)), quindi $P(2+1)=P(3)$ è vera (per (*)), quindi $P(3+1)=P(4)$ è vera (per (*)), quindi $P(4+1)=P(5)$ è vera (per (*)), quindi $P(5+1)=P(6)$ è vera (per (*)), quindi $P(6+1)=P(7)$ è vera (per (*)), quindi $P(7+1)=P(8)$ è vera (per (*)), quindi $P(8+1)=P(9)$ è vera (per (*)), quindi $P(9+1)=P(10)$ è vera (per (*)). Quindi $P(10)$ è vera.
In altre parole
$P(1) => P(2) => P(3) => P(4) => P(5) => P(6) => P(7) => P(8) => P(9) => P(10)$
Più in generale
$P(1) => P(2) => P(3) => ... => P(n)$.
Ne segue che se sai che $P(1)$ è vera, per mostrare che $P(n)$ è vera per ogni $n$ basta dimostrare (*).
-----
Te l'ho detto così perché non so se ti sia chiaro il meccanismo di ricorsione, se tutto quello che volevi era una giustificazione logica del principio di induzione allora mi scuso, è meglio che dimentichi quello che ho scritto e aspetti la risposta di Wizard.
Ma noi quindi dimostrarimo $p(1)$ che è il passo base;
Poi supponiamo vera una qualsiasi $p(n)$ della successione, se il supporre vera $p(n)$ implica anche $p(n+1)$ vera, allora da li possiamo dire che è verà per ogni numero naturale maggiore o uguale di 1 ?
Ma quindi tu dici:
(*) "se $P(n)$ è vera allora $P(n+1)$ è vera", per ogni $n$.
Tu dimostri verà $p(1)$ che è il passo base, la p(n) la supponi vera, e ti provi vera $p(n+1)$ sfruttando $p(n)$.
A me è proprio quel suppore vero il nocciolo del mio dubbio.
Ovvero, se suppongo vera $p(n)$ e trovo vera $p(n+1)$ allora è vera per $AA n >= 1$, il che significa che essere vera $p(n+1)$ deve esserlo a forza $p(n)$? Ovvero noi diciamo facciamo finta che sia vera per $n$ e aggiungiamoli $1$, se la troviamo ancora vera rispetto all'ipotesi iniziale allora è vera anche $p(n)$ ?
P.S: Grazie comunque per avermi risposto, ma a me quello che manca è proprio "tale giustificazione logica" ovvero, se capissi bene logicamente come funziona poi mi filerebbe molto più liscio il discorso che pensare a priori che sia vero.
"Neptune":No.
noi diciamo facciamo finta che sia vera per $n$ e aggiungiamoli $1$, se la troviamo ancora vera rispetto all'ipotesi iniziale allora è vera anche $p(n)$ ?
Noi dimostriamo l'implicazione $P(n) => P(n+1)$.
Quando dimostri un'implicazione $A => B$ non ti interessi dei valori di verità effettivi dei due argomenti $A$ e $B$, dimostri solo che supponendo che $A$ sia vera si deduce che $B$ è vera.
Dimostrare $A => B$ non c'entra niente con dimostrare $A$,
è tutta un'altra cosa.
Poi, supponi di dover dimostrare $P(m)$. In base all'implicazione $P(n) => P(n+1)$, ti basta dimostrare $P(m-1)$ (siccome l'implicazione $P(n) => P(n+1)$ vale per ogni $n$, vale anche per $n=m-1$, quindi $P(m-1) => P(m)$). Ci sei?
Ora per dimostrare $P(m-1)$ ti basta dimostrare $P(m-2)$, ci sei? Sto usando $P(n) => P(n+1)$ con $n=m-2$.
Ora per dimostrare $P(m-2)$ ti basta dimostrare $P(m-3)$, ci sei? Sto usando $P(n) => P(n+1)$ con $n=m-3$.
E avanti così scendendo finché non arrivi a $1$.
In questo modo deduci che se $P(1)$ è vera allora anche $P(m)$ è vera (in base alla catena di implicazioni $P(1) => P(2) => P(3) => ... => P(m)$). E quindi ti sei ridotto a dimostrare che (1) $P(1)$ è vera e (2) $P(n) => P(n+1)$ per ogni $n$.
Mi dispiace ma non riesco ad essere più chiaro di così.
Ciao
Mi unisco "empaticamente" a Martino per il suo modo di vedere la cosa.
Sottolineo anch'io che la dimostrazione di $p(n)\Rightarrow p(n+1)$ non ha nulla a che vedere con la verita' di $p(n)$ o di $p(n+1)$. Per esempio la proposizione
$(2n" dispari" ) \to (2n+1" pari")" " \forall n\in NN$
E' VERA
Sottolineo anch'io che la dimostrazione di $p(n)\Rightarrow p(n+1)$ non ha nulla a che vedere con la verita' di $p(n)$ o di $p(n+1)$. Per esempio la proposizione
$(2n" dispari" ) \to (2n+1" pari")" " \forall n\in NN$
E' VERA
"Martino":No.
[quote="Neptune"]noi diciamo facciamo finta che sia vera per $n$ e aggiungiamoli $1$, se la troviamo ancora vera rispetto all'ipotesi iniziale allora è vera anche $p(n)$ ?
Noi dimostriamo l'implicazione $P(n) => P(n+1)$.
Quando dimostri un'implicazione $A => B$ non ti interessi dei valori di verità effettivi dei due argomenti $A$ e $B$, dimostri solo che supponendo che $A$ sia vera si deduce che $B$ è vera.
Dimostrare $A => B$ non c'entra niente con dimostrare $A$,
è tutta un'altra cosa.
Poi, supponi di dover dimostrare $P(m)$. In base all'implicazione $P(n) => P(n+1)$, ti basta dimostrare $P(m-1)$ (siccome l'implicazione $P(n) => P(n+1)$ vale per ogni $n$, vale anche per $n=m-1$, quindi $P(m-1) => P(m)$). Ci sei?
Ora per dimostrare $P(m-1)$ ti basta dimostrare $P(m-2)$, ci sei? Sto usando $P(n) => P(n+1)$ con $n=m-2$.
Ora per dimostrare $P(m-2)$ ti basta dimostrare $P(m-3)$, ci sei? Sto usando $P(n) => P(n+1)$ con $n=m-3$.
E avanti così scendendo finché non arrivi a $1$.
In questo modo deduci che se $P(1)$ è vera allora anche $P(m)$ è vera (in base alla catena di implicazioni $P(1) => P(2) => P(3) => ... => P(m)$). E quindi ti sei ridotto a dimostrare che (1) $P(1)$ è vera e (2) $P(n) => P(n+1)$ per ogni $n$.
Mi dispiace ma non riesco ad essere più chiaro di così.
Ciao[/quote]
Quindi ricapitolando, quello che dimostri per induzione è che un numero generico $n$ implica il suo successivo, ovvero per induzione non fai altro che dimostrare un implicazione.
Praticamente dici supponiamo che $n in S$ dove $S sube NN$, se $n =>n+1$ allora $n+1 in S$
Nei vari esercizi $S$ sarà una sequenza di numeri, ed ogni numero $in NN$
Un esercizio tipo di dimostrazione per induzione non fa altro che darti una formula per calcolarti l'elemento n-esimo e ti dice anche che regole deve rispecchiare tale elemento. Aggiungendo ovviamente qual'è la base di questa sequenza di numeri.
Ad esempio ti dice che l'n-esimo multiplo di $8$ si può calcolare con una certa formula.
come agisci? supponi che quella formula sia vera per $n$, e quindi devi verificare che $p(n) => p(n+1)$ per dimostrare che quella formula data dall'esercizio valga per ogni $n$, e non solo per alcune (esempio banale è la formula per calcolarsi la successione dei numeri primi, che poi si è scoperto che funziona solo fino ad un certo numero).
Quindi ora il punto è verificare $p(n) => p(n+1)$.
Come posso farlo? dimostro $p(n+1)$ mediante $p(n)$ che suppongo vera e trovo che ho comunque un multiplo di 8. No?
Cioè quello che mi state dicendo è che "non dimostriamo il valore di verità", semplicemente prendiamo "la possibilità in cui sia vero" (per questo supponiamo vero) perchè nel caso in cui sia falso non dimostreremmo ciò che ci serve.
Ovvero se l'implicazione è vera, ed il valore di verità è anch'esso vero, allora abbiamo la nostra bella sequenza;
Il valore di verità falso signficherebbe dire che $n notin S$, e quindi non ci servirebbe al fine della nostra dimostrazione perchè non dimostrerebbe nulla. Giusto?
Semplificando drasticamente, in logica matematica si dice che una proposizione [tex]q[/tex] è conseguenza logica di un sistema di proposizioni [tex]p_{1}, p_{2}, p_{3}, \ldots, p_{n}[/tex] se non si da mai il caso che il sistema di presesse sia vero e la [tex]q[/tex] sia falsa. Un metodo di deduzione è corretto quando permette di dedurre da un sistema di premesse una conclusione nel senso sopra esposto: una regola inferenziale è allora una "semplice" regola formale che permette dai passare da un sistema di proposizioni dette premesse ad un sistema di preposizioni dette conclusioni di modo che che queste siano conseguenza logica delle premsse, che porta ad un valore di verità vero partendo da valori di verità vero, ma che non consente di stabile la verità di una proposizione in assoluto.
La regola di inferenza più utilizzata è il modus ponens: semplificando, se [tex]\phi,\chi[/tex] sono formule di modo che [tex]\phi \land (\phi \implies \chi)[/tex] sia vera, allora anche [tex]\chi[/tex] è vera.
Quando si ha da provare un teorema si ha da provare che da un sistema di ipotesi (vere) si deduce la tesi (da dimostrarsi vera). Solitamente il teorema di schematizza in una struttura implicativa [tex]\text{Ipotesi} \implies \text{Tesi}[/tex] e si scrivono tante belle catene di implicazioni partendo dalle ipotesi arrivando alla tesi: in realtà sarebbe più corretto (da un punto di vista logico-formale) scrivere una sequenza di implicazioni di modo che tramitte la transitività dell'implicazione si possa infine scrivere l'implicazione [tex]\text{Ipotesi} \implies \text{Tesi}[/tex] ed essendo vera l'ipotesi si possa inferire la verità della tesi.
Ti renderai conto che questa differenza tra implicazione ed inferenza, molto importante nei sistemi logici formali, è quesi irrilevante per gli scopi matematici, quindi si è soliti confondere la dimostrazione della verità dell'implicazione con la dimostrazione della verità della conclusione.
Ciò premesso, qual è l'importanza del passo [tex]\mathcal{P}(n) \implies \mathcal{P}(n+1)[/tex]? La risposta risiede nel modus ponens: se dimostriamo essere vera questa implicazione allora, supponendo vera [tex]\mathcal{P}(n)[/tex], possiamo inferire che è vera [tex]\mathcal{P}(n+1)[/tex]. A questo punto se abbiamo provato che è vera [tex]\mathcal{P}(0)[/tex] potremo inferire [tex]\mathcal{P}(1)[/tex], quindi da [tex]\mathcal{P}(1)[/tex] potremo inferire [tex]\mathcal{P}(2)[/tex] e via continuando.
Spero di essere stato sufficientemente chiaro: purtroppo le mie conoscenze di logica sono limitate e non saprei cos'altro aggiungere per rendere l'idea del perché e del come funzionano le dimostrazioni per induzioni.
La regola di inferenza più utilizzata è il modus ponens: semplificando, se [tex]\phi,\chi[/tex] sono formule di modo che [tex]\phi \land (\phi \implies \chi)[/tex] sia vera, allora anche [tex]\chi[/tex] è vera.
Quando si ha da provare un teorema si ha da provare che da un sistema di ipotesi (vere) si deduce la tesi (da dimostrarsi vera). Solitamente il teorema di schematizza in una struttura implicativa [tex]\text{Ipotesi} \implies \text{Tesi}[/tex] e si scrivono tante belle catene di implicazioni partendo dalle ipotesi arrivando alla tesi: in realtà sarebbe più corretto (da un punto di vista logico-formale) scrivere una sequenza di implicazioni di modo che tramitte la transitività dell'implicazione si possa infine scrivere l'implicazione [tex]\text{Ipotesi} \implies \text{Tesi}[/tex] ed essendo vera l'ipotesi si possa inferire la verità della tesi.
Ti renderai conto che questa differenza tra implicazione ed inferenza, molto importante nei sistemi logici formali, è quesi irrilevante per gli scopi matematici, quindi si è soliti confondere la dimostrazione della verità dell'implicazione con la dimostrazione della verità della conclusione.
Ciò premesso, qual è l'importanza del passo [tex]\mathcal{P}(n) \implies \mathcal{P}(n+1)[/tex]? La risposta risiede nel modus ponens: se dimostriamo essere vera questa implicazione allora, supponendo vera [tex]\mathcal{P}(n)[/tex], possiamo inferire che è vera [tex]\mathcal{P}(n+1)[/tex]. A questo punto se abbiamo provato che è vera [tex]\mathcal{P}(0)[/tex] potremo inferire [tex]\mathcal{P}(1)[/tex], quindi da [tex]\mathcal{P}(1)[/tex] potremo inferire [tex]\mathcal{P}(2)[/tex] e via continuando.
Spero di essere stato sufficientemente chiaro: purtroppo le mie conoscenze di logica sono limitate e non saprei cos'altro aggiungere per rendere l'idea del perché e del come funzionano le dimostrazioni per induzioni.
"WiZaRd":
Semplificando drasticamente, in logica matematica si dice che una proposizione [tex]q[/tex] è conseguenza logica di un sistema di proposizioni [tex]p_{1}, p_{2}, p_{3}, \ldots, p_{n}[/tex] se non si da mai il caso che il sistema di presesse sia vero e la [tex]q[/tex] sia falsa. Un metodo di deduzione è corretto quando permette di dedurre da un sistema di premesse una conclusione nel senso sopra esposto: una regola inferenziale è allora una "semplice" regola formale che permette dai passare da un sistema di proposizioni dette premesse ad un sistema di preposizioni dette conclusioni di modo che che queste siano conseguenza logica delle premsse, che porta ad un valore di verità vero partendo da valori di verità vero, ma che non consente di stabile la verità di una proposizione in assoluto.
La regola di inferenza più utilizzata è il modus ponens: semplificando, se [tex]\phi,\chi[/tex] sono formule di modo che [tex]\phi \land (\phi \implies \chi)[/tex] sia vera, allora anche [tex]\chi[/tex] è vera.
Quando si ha da provare un teorema si ha da provare che da un sistema di ipotesi (vere) si deduce la tesi (da dimostrarsi vera). Solitamente il teorema di schematizza in una struttura implicativa [tex]\text{Ipotesi} \implies \text{Tesi}[/tex] e si scrivono tante belle catene di implicazioni partendo dalle ipotesi arrivando alla tesi: in realtà sarebbe più corretto (da un punto di vista logico-formale) scrivere una sequenza di implicazioni di modo che tramitte la transitività dell'implicazione si possa infine scrivere l'implicazione [tex]\text{Ipotesi} \implies \text{Tesi}[/tex] ed essendo vera l'ipotesi si possa inferire la verità della tesi.
Ti renderai conto che questa differenza tra implicazione ed inferenza, molto importante nei sistemi logici formali, è quesi irrilevante per gli scopi matematici, quindi si è soliti confondere la dimostrazione della verità dell'implicazione con la dimostrazione della verità della conclusione.
Ciò premesso, qual è l'importanza del passo [tex]\mathcal{P}(n) \implies \mathcal{P}(n+1)[/tex]? La risposta risiede nel modus ponens: se dimostriamo essere vera questa implicazione allora, supponendo vera [tex]\mathcal{P}(n)[/tex], possiamo inferire che è vera [tex]\mathcal{P}(n+1)[/tex]. A questo punto se abbiamo provato che è vera [tex]\mathcal{P}(0)[/tex] potremo inferire [tex]\mathcal{P}(1)[/tex], quindi da [tex]\mathcal{P}(1)[/tex] potremo inferire [tex]\mathcal{P}(2)[/tex] e via continuando.
Spero di essere stato sufficientemente chiaro: purtroppo le mie conoscenze di logica sono limitate e non saprei cos'altro aggiungere per rendere l'idea del perché e del come funzionano le dimostrazioni per induzioni.
Sei stato più che chiaro, sei riuscito a dirmi in maneira semplice ma concerta "ciò che mi mancava".
A sentirsi sempre dire "verifichiamo $p(n+1)$, mi è sembrato logico chiedermi "ma verifichiamo cosa?" tant'è che ti viene da pensare che verifichi il valore di verità di $p(n+1)$. In realtà, come siamo arrivati a dire in questo thread, noi verifichiamo che sia vera l'implicazione logica, che poi sia vera $p(n+1)$ dipende tutto dal valore di verità di $p(n)$. Ecco che acquisisce anche di senso dire "supponiamo vera $p(n)$, la supponiamo verà perchè potrebbe anche non esserlo, noi stiamo verificando l'implicazione e come tutti sappiamo preposizione falsa può implicare tutto, non avrebbe senso dimostrarla.
Vi ringrazio molto per questo aiuto.
Ma quindi, tornando infine alla ricorsività, è vero dire, come ho sviluppato quell'esercizio, che avendo la formula ricorsivà del termine "ennesimo" la sfruttiamo ai fini della dimostrazione? è quello che facciamo, o almeno che ho fatto in quell'esercizio, detto per sommi capi.
Non vorrei approfittare della vostra estrema gentilezza, ma sapreste linkarmi qualche esercizio sulla ricorsività? perchè sulle dimostrazioni per induzione un pò ne ho, ma che comprendano la ricorsività ho poca roba.
Beh, ovviamente la formula ricorsiva è utilizzata per provare che è vera [tex]\mathcal{P}(n) \implies \mathcal{P}(n+1)[/tex].
"WiZaRd":
Beh, ovviamente la formula ricorsiva è utilizzata per provare che è vera [tex]\mathcal{P}(n) \implies \mathcal{P}(n+1)[/tex].
Ovvero abbiamo un asserzione, ovvero una premessa, in più per provare l'implicazione logica, giusto?
Quindi quando invece mi dicono di calcolarmi una formula ricorsiva non faccio altro che: fare delle deduzioni matematiche (provando a far variare il nostro numero per un tot di valori) e poi dimostrare sempre per induzione che quella deduzione che ho fatto vale "per tutta la succesione" e non solo per quel numero finito di prove che ho sviluppato, giusto?
Ovvero se mi dicono di dare una definizione ricorsiva di ${a_n=4n-1}$ $AA >= 0$
Allora provo a variare un pò di $n$ a partire da $0$, e cerco di faccio un ipotesi sul variare di $n$, sapendo invece con certezza qual'è l'inizio della sequenza perchè basta provare per $0$
Dopo aver fatto un ipotesi sulla formula ricorsiva non faccio altro che dimostrarmela per induzione. Ad esempio, se hai tempo, mi svolgeresti questo esercizio che ti ho citato? (giusto per vedere tu come lo svolgeresti, se non ti è di disturbo, ovviamente).
Ad ogni modo, scusate l'off-topic, ma forse non sarò un genio della matematica, molto spesso scrivo cavolate per sbadataggine più che per reale negligenza, però non mi si può dire che non studio la matematica, ci sono miei post in piena notte, e adesso pure al mattino presto. Dite che se faccio notare questa cosa in sede di esame gli faccio compassione?
Innazitutto scusami se ho impiegato tanto tempo per rispondere alle tue ultime domande ma onestamente mi ero dimenticato del topic.
Tornando in tema, non ho capito quello che chiedi.
Una definizione ricorsiva non è altro che una applicazione del principio di induzione, al pari delle dimostrazioni per induzione. Non ho però capito in cosa consista il tuo dubbio circa le definizioni ricorsive.
Tornando in tema, non ho capito quello che chiedi.
Una definizione ricorsiva non è altro che una applicazione del principio di induzione, al pari delle dimostrazioni per induzione. Non ho però capito in cosa consista il tuo dubbio circa le definizioni ricorsive.
Il punto è quando ho un esercizio sulla ricorsione dove mi dicono "questa è la formula chiusa", "calcolati la formula ricorsiva".
Tu per calcolarti la formula ricorsiva come fai? provi a fare delle supposizioni vedendo un pò come funziona "questa formula chiusa". Però alla fine hai fatto solo delle supposizioni, supposizioni che devi, in conclusione, verificare tramite il principio di induzione o sbaglio?
Ovvero se ti chiedono di calcolarti la formula ricorsiva di questa formula chiusa ${a_n=4n-1} AA n>=0$
Tu come lo svolgeresti questo esercizio?
Tu per calcolarti la formula ricorsiva come fai? provi a fare delle supposizioni vedendo un pò come funziona "questa formula chiusa". Però alla fine hai fatto solo delle supposizioni, supposizioni che devi, in conclusione, verificare tramite il principio di induzione o sbaglio?
Ovvero se ti chiedono di calcolarti la formula ricorsiva di questa formula chiusa ${a_n=4n-1} AA n>=0$
Tu come lo svolgeresti questo esercizio?
"Neptune":
se ti chiedono di calcolarti la formula ricorsiva di questa formula chiusa ${a_n=4n-1} AA n>=0$, tu come lo svolgeresti questo esercizio?
Beh, io lo farei in due passi: 1) calcolo di [tex]a_0[/tex] e 2) determinazione della relazione ricorrente.
Per 1) non ci vuole tanta inventiva; in questo caso è [tex]a_0=-1[/tex].
Per 2) ci vuole abbastanza fortuna in generale... Ma in questo caso hai:
[tex]a_{n+1}=4(n+1)-1=(4n-1)+4=a_n+4[/tex],
ed ecco la tua bella ricorrenza.
Quindi:
[tex]\forall n\in \mathbb{N}, a_n=4n-1 \Leftrightarrow \begin{cases} a_0=-1\\ a_{n+1}=a_n+4 \; ,\text{ per } n\in \mathbb{N}\end{cases}[/tex].
P.S.: Non smetterò mai di dirlo: "qual è" si scrive senza apostrofo, perchè non c'è elisione.
Capisco.
Onestamente non ne ho mai fatti tanti e i pochi che ho fatto non li ho mai risolti in modo sistematico: diciamo che li ho sempre fatti in modo molto intuitivo.
Data la formula chiusa [tex]a_{n}=4n-1[/tex] basta notare che i numeri che si ottengono sono i multipli di [tex]4[/tex] diminuiti dell'unità, quindi
[tex]&a_{0}=-1\\ &a_{n}=a_{n-1}+4[/tex].
Onestamente non ne ho mai fatti tanti e i pochi che ho fatto non li ho mai risolti in modo sistematico: diciamo che li ho sempre fatti in modo molto intuitivo.
Data la formula chiusa [tex]a_{n}=4n-1[/tex] basta notare che i numeri che si ottengono sono i multipli di [tex]4[/tex] diminuiti dell'unità, quindi
[tex]&a_{0}=-1\\ &a_{n}=a_{n-1}+4[/tex].
Fregato sul tempo dal mio conterraneo! Accidenti! Tutta colpa del fatto che non capivo come allineare le equazioni: alla fine ci ho rinunciato.
WiZ, potresti usare l'ambiente cases (così esce fuori anche una parentesi graffa carina)... Gli altri ambienti di allineamento (tipo align e simili) non so se funzionano.
P.S.: Ma non ti fai vedere mai a MSA?
P.S.: Ma non ti fai vedere mai a MSA?
Lo so ma volevo evitare proprio le parentesi graffe.
P.S.
È che sono un fantasma sfuggente!
P.S.
È che sono un fantasma sfuggente!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo