Homepage  Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum


.dsy:it. .dsy:it. Archive > Didattica > Corsi G - M > Logica matematica
 
[help] Dimostrazione per Induzione
Clicca QUI per vedere il messaggio nel forum
Bemipefe
Salve !

Vorrei sapere se qualcuno sà in che modo si debba partire nella dimostrazione per induzione........

.....bisogna fare uso esclusivamente delle variabili n +1 , n+2 ........oppure è meglio utilizzare il risultato , cioè il valore numerico diretto.

Ad esempio se parto (per la dimostrazione) dal valore 0 , e poi partendo da questo valore n estendo la dimostrazione ad n+1........

.....ad n+1 devo usare il valore 1 = (0+1) oppure devo usare (n+1)

.......in questo caso però diventa un casino gia rappresentare 2 cioè n+2 = [(n+1) +1]..........se poi voglio andare avanti?


Non avreste un esempio pratico e semplice per capire la tecnica di dimostrazione?

GRAZIE Ciao! :-D

Polsy
allora, la dimostrazione x induzione funziona così: lavorando in un insieme ordinato in cui puoi stabilire un minimo (se no non si può fare) prima dimostri che la regola vale per l'elemento + piccolo, dopodichè dimostri che se la regola vale fino a un certo n allora vale anche per il successivo di n (nota: dico "il successivo" perchè non è detto che il successivo di n in un insieme sia n+1)
esempio:

"tutti i numeri naturali che finiscono con 0 sono multipli di 5, cioè della forma k*5 dove k è un naturale"

l'insieme dei numeri naturali che finiscono con zero è ordinato e il minimo è zero

primo passo: dimostro che 0 è multiplo di 5 (banale)

secondo passo: se un certo numero n che finisce con zero è multiplo di 5, allora devo dimostrare che anche il naturale che finisce con zero successivo a n (che ottengo facendo n+10) sarà divisibile per 5, cioè devo dimostrare che:
k*5 + 10 = h*5
cioè essendo n nella forma k*5 (lo assumo per ipotesi induttiva) dimostro che il suo successivo ( cioè n + 10 cioè k*5 + 10) rispetta anch'esso la regola (cioè è nella forma h*5)
per cui svolgo il 2° passo facendo
k*5 + 10 = k*5 + 2*5 = (k+2)*5
k+2 è un naturale e lo posso chiamare h, per cui ho k*5 + 10 = h*5

CVD

spero di non averti incasinato le idee :D

Bemipefe
Ok fin quì ci sono ........però il problema è che non sò quando la dimostrazione è finita e con quale prova si deve ritenere tale !?

Polsy
hai finito quando hai completato entrambi i passi
passo 1: dimostri che la proprietà vale sempre per il primo dell'insieme
passo 2: parti dall'ipotesi che la proprietà valga per tutti gli elementi fino a n, per cui ti scriverai per esteso la proprietà di uno di questi, ad esempio P(n) e la "modifichi" un po', nel senso la riscrivi in forme equivalenti, finchè non assume la forma P(n+1), cioè finchè non costituisce una prova della validità della proprietà per il successivo di n
ad esempio nella dimostrazione che ho fatto prima P(n) è "n è un multiplo di 5" o detto + formalmente n=k*5 mentre P(n+1) è "il successivo di n nell'insieme è un multiplo di 5" oppure n+10=h*5
nel momento in cui riesci a trasformare P(n) in P(n+1) (cioè nel nostro caso trasformare n=k*5 in n+10=h*5) hai finito la tua dimostrazione

Bemipefe
Ok vediamo se ho capito........ti faccio adesso un esempio io:

Si dimostri per induzione che ogni numero naturale "n" maggoire di 1 si scompone in un numero <= x di fattori primi dove x = log_2;

...io avrei fatto così

Caso base :
S(1) = x >1 = successivo di 1 = 2 = n
2 essendo numero primo può essere scomposto in 0 fattori primi
se la proprietà vale log_2(1) = x >= 0 (è così è infatti, poichè x=0)

Caso Induttivo:
S(n) = x > n = successivo di n = 3 = n+1
3 essendo numero primo è scomponibile in 0 fattori primi
se la prorpietà vale log_2(1) = x >= 0
(è così è infatti x = 1,6 circa e il numero di fattori primi è <= x)

......dopo ciò tu cosa avresti fatto ? tu dici di far valere la proprietà fino ad un "n " "generico"......ma come faccio a dimostrare che la proprietà vale per un "n" generico ? (Ad esempio come faccio a sapere che log_2(n) = x con x>= al numero di fattori primi di n, se non assegno ad "n" stesso un valore ?)

CIAO!

Bemipefe
Nel testo dell'esercizio c'è log_2(n) e non log_2

....una svista Scusa

CIAO!

Polsy
no allora, non devi sostituire i numeri uno per uno, se no vai avanti all'infinito :P
tu fai il caso base dove dimostri che la proprietà vale per 2 (il primo dell'insieme)
dopo fai il caso induttivo in cui per ipotesi vale fino a n (un generico n, non devi sostituirci un numero), e partendo da quello devi dimostrare che vale anche per n+1
a questo punto ti chiederai, ma come faccio a convincermi che con questo metodo vale sempre, sia per 2 che per 3 che per 376438796?
il caso induttivo ti dice che SE hai dimostrato la proprietà fino a un certo numero ALLORA vale anche per il successivo. tu nel caso base l'hai dimostrata fino a 2
vale fino a 2 => allora vale anche per 3
vale fino a 3 => allora vale anche per 4
vale per 4 ...
e così all'infinito, solo che se ti metti a fare 2,3,4,5... come casi distinti non ti passa più, col metodo induttivo sottintendi questa catena di inferenze, ecco perchè usi un n generico, perchè così può valere come 2, come 3 o come 7684760

per quanto riguarda la specifica dimostrazione dei fattori primi ora non mi viene in mente come fare il caso induttivo, ci penso un po' e se i cricetini nella testa si svegliano la posto qua :)

Polsy
cricetini attivi :) nella dimostrazione ho usato per comodità n-1 e n al posto di n e n+1 ma è la stessa cosa

caso base: S(2) --> la proprietà vale per 2? si! perchè 2 è primo quindi x=1 (cioè il 2 si scompone in 1 solo fattore primo, che è il 2 stesso) e in effetti x<=log_2(2) che è appunto 1

caso induttivo: assumendo che valga la proprietà per i primi n-1 numeri, dimostro che vale anche per n (ASSOLUTAMENTE non sostituire un numero a n, dev'essere un caso generico)
n può essere primo (in tal caso la proprietà è banalmente vera) o non primo, in tal caso avrà un certo numero di divisori, questi divisori non possono essere + grandi di n/2 ciascuno, e visto che siamo pessimisti prendiamo il caso in cui uno dei divisori sia proprio n/2. per ipotesi induttiva abbiamo che la proprietà vale per tutti gli interi fino a n-1, per cui vale anche per n/2, per cui n/2 verrà scomposto in log_2(n/2) fattori primi nel caso peggiore.
a questo punto, in quanti fattori verrà scomposto n? n lo si ottiene facendo n/2 * 2 quindi ha come fattori primi il 2 + tutti i fattori primi di n/2, che abbiamo appena detto essere log_2(n/2)
allora il famoso x sarà al massimo log_2(n/2) + 1 e applicando un po' di proprietà dei logaritmi abbiamo che:
log_2(n/2) + 1 = log_2(n/2) + log_2(2) = log_2( (n/2)*2 ) = log_2(n)
CVD

Bemipefe
Grazie Polsy !
Adesso penso di avere acquisito il metodo di dimostrazione per induzione! .........una delle cose di logica che mi mancavano.........oltra al Sistema Deduttivo di Hilbert .....che a quanto pare studiamo solo noi della facoltà SMFN di Roma.....

....speriamo di no, altrimenti a chi chiedo spiegazioni?

Polsy
prego! mi fa piacere che ti sia stato utile :)
purtroppo hilbert non l'ho fatto e non ne so nulla...:? se proprio sei in crisi magari vai a ricevimento dal tuo prof di logica e fattelo un po' spiegare da lui ;)

Bemipefe
.....si grazie, avevo già preso in considerazione il fatto di andare dal Professore........solo che devo farmi 1 ora e mezzo di viaggio all'andata e al ritorno e poi dovrei arrivare a piedi al Dipartimento di Informatica, e con questo caldo non ne ho voglia .......però alla fine credo che sia l'unica soluzione ......CIAO!

Bemipefe
Allora .......ancora Induzione..... vediamo se ho imparato.

Una cosa semplice........ dimostrare che perogni N (escluso 0) vale 0/n = 0

base dell'induzione:

Passo 1 - 0/1 = 0

Passo 2 - 0/2 = 0

.....

Principio Induttivo:

Ammettendo che la proprietà valga per un generico (n-1) , cioè:

Passo (n-1) - 0/(n-1) = 0

allora deve valere anche per s[(n-1)] (successivo di n-1), e sapendo che s[(n-1)] = (n-1)+1 si avrà:

Passo (n-1)+1 - 0/(n-1)+1 = Passo n - 0/n = 0


Così può andare?

Polsy
Originally posted by Bemipefe
Allora .......ancora Induzione..... vediamo se ho imparato.

Una cosa semplice........ dimostrare che perogni N (escluso 0) vale 0/n = 0

base dell'induzione:

Passo 1 - 0/1 = 0

Passo 2 - 0/2 = 0

.....


per il passo base basta solo il passo 1


Principio Induttivo:

Ammettendo che la proprietà valga per un generico (n-1) , cioè:

Passo (n-1) - 0/(n-1) = 0

allora deve valere anche per s[(n-1)] (successivo di n-1), e sapendo che s[(n-1)] = (n-1)+1 si avrà:

Passo (n-1)+1 - 0/(n-1)+1 = Passo n - 0/n = 0


Così può andare?


il passo induttivo dice che DEVI DIMOSTRARE che se vale per i precedenti di n allora vale anche per n, cioè quell'inferenza non ce l'hai come ipotesi, tu hai come ipotesi la premessa e devi dimostrare la conseguenza

nello svolgimento del passo induttivo tu parti dal presupposto che la proprietà valga anche per s[n+1], ma in realtà è ciò che devi dimostrare! per cui tu non sai ancora che 0/(n-1+1)=0, ci devi arrivare facendo dei passaggi logici dall'equazione 0/(n-1)=0, che per ora è l'unica certezza che hai

Bemipefe
...ci devi arrivare facendo dei passaggi logici dall'equazione....


Il problema è che questi passaggi logici cambiano da dimostrazione a dimostrazione, e non riesco mai a capire quali sono

Nello specifico di questo esercizio, cosa intendi per passaggi logici?

Io ...spremendo un pò le meningi , ho trovato che....

se 0/n-1+1 non fosse 0 ma un generico x, cioè:

0/n-1+1 = x

allora dall'espressione bisognerebbe ricavare 0 = x*(n-1+1)

e ciò altro non porta al fatto che x = 0 cioè che 0/n-1+1 = 0

...così come va?

Polsy
Originally posted by Bemipefe
Il problema è che questi passaggi logici cambiano da dimostrazione a dimostrazione, e non riesco mai a capire quali sono

infatti è questa la vera difficoltà della dimostrazione :P


Nello specifico di questo esercizio, cosa intendi per passaggi logici?

Io ...spremendo un pò le meningi , ho trovato che....

se 0/n-1+1 non fosse 0 ma un generico x, cioè:

0/n-1+1 = x

allora dall'espressione bisognerebbe ricavare 0 = x*(n-1+1)

e ciò altro non porta al fatto che x = 0 cioè che 0/n-1+1 = 0

...così come va?

questo ragionamento effettivamente dimostra che 0/n = 0 per ogni n, solo che è una dimostrazione per assurdo, non per induzione

nel senso, potevi dire già da subito che se questo x fosse diverso da zero avremmo x*n (che è sicuramente diverso da zero) = 0, il che è un assurdo
questo senza dividere in caso base e induttivo

il fatto è che esistono diversi metodi di dimostrazione proprio perchè in alcuni casi conviene usarne uno e in altri casi conviene usarne un altro, nel caso 0/n = 0 la dimostrazione migliore è quella per assurdo, sinceramente nemmeno io saprei come dimostrarlo induttivamente

Bemipefe
Forse ci sono ..... vediamo se riesco a fare questa:



Allora ....
Ti spiego un attimo..... in pratica A_n è l'insieme che contiene tutti gli insiemi A che rispettano quella proprietà , e poi mi chiede se la cardinalità di A_n = 2^n-1


Base Induttiva
n = 1
A è sottoinzieme di {1}

Quindi A_n = { {1} } e |A_n| = 2^n-1 = 2^0 = 1
Vera

Principio Induttivo
Si può notare che l'insieme A_n è un sottoinsieme dell'insieme P({1...n}) , cioè è sottoinsieme all'insieme delle parti di {1...n}.
Infatti in A_n ci sono tutti i sottoinsiemi di {1....n} meno alcuni inziemi.
Gli insiemi che mancano sono quelli che contengono gli elementi isolati da 2 a n ossia gli elementi del tipo {2}, {3} .....fino a {n}, che non rispettano 1 appartiene ad A
Se da 1 a n ci sono n elementi da 2 a n si possono costruire (n-1) sottoinsiemi contenenti i singoli elementi da 2 a n.
In più l'insieme A_n rispetto a P({1-n}) non contiene l'insieme vuoto quindi l'insieme A_n contiene [(n-1)+1] elementi (+1 riguarda il vuoto) , rispetto a P({1...n}).
Visto che la cardinalità di P({1...n}) è 2^n la cardinalità di A_n è:
2^n - [(n-1)+1] = 2^n - n
Ma effettivamente 2^n -n = 2^(n-1)


Tranne l'impostazione credo che il principio attivo (ragionamento logico) sia efficace. Tu che dici?

Polsy
Originally posted by Bemipefe
Forse ci sono ..... vediamo se riesco a fare questa:



Allora ....
Ti spiego un attimo..... in pratica A_n è l'insieme che contiene tutti gli insiemi A che rispettano quella proprietà , e poi mi chiede se la cardinalità di A_n = 2^n-1


Base Induttiva
n = 1
A è sottoinzieme di {1}

Quindi A_n = { {1} } e |A_n| = 2^n-1 = 2^0 = 1
Vera

fin qui perfetto

Principio Induttivo
Si può notare che l'insieme A_n è un sottoinsieme dell'insieme P({1...n}) , cioè è sottoinsieme all'insieme delle parti di {1...n}.
Infatti in A_n ci sono tutti i sottoinsiemi di {1....n} meno alcuni inziemi.
Gli insiemi che mancano sono quelli che contengono gli elementi isolati da 2 a n ossia gli elementi del tipo {2}, {3} .....fino a {n}, che non rispettano 1 appartiene ad A
Se da 1 a n ci sono n elementi da 2 a n si possono costruire (n-1) sottoinsiemi contenenti i singoli elementi da 2 a n.
In più l'insieme A_n rispetto a P({1-n}) non contiene l'insieme vuoto quindi l'insieme A_n contiene [(n-1)+1] elementi (+1 riguarda il vuoto) , rispetto a P({1...n}).
Visto che la cardinalità di P({1...n}) è 2^n la cardinalità di A_n è:
2^n - [(n-1)+1] = 2^n - n
Ma effettivamente 2^n -n = 2^(n-1)


Tranne l'impostazione credo che il principio attivo (ragionamento logico) sia efficace. Tu che dici?

qua hai fatto un po' della fantamatematica :P
ci sono 2 errori matematici e uno di forma

quelli matematici sono che prima di tutto 2^(n-1) non è uguale a 2^n -n, se vuoi scomporlo in modo da evidenziare il 2^n dovresti scrivere (2^n) / 2
inoltre gli insiemi per cui A_n differisce da P({1...n}) non sono solo quelli unitari da 2 a n, ma anche insiemi del tipo {2,5} o {3,n-7,n} etc.

l'errore di forma è che anche ammettendo la correttezza delle formule questa non è una dimostrazione "per induzione", per esserlo devo partire dal caso n-1
fai così:
- ammettendo che la proprietà sia vera per n-1 (ipotesi induttiva) quale sarà la cardinalità di A_(n-1) ?
- per ottenere A_n quali (e quindi quanti) insiemi devi aggiungere a quelli che hai in A_(n-1) (di cui conosco la cardinalità)?
- il risultato che ti viene fuori è 2^n-1? se si congratulazioni :D se no riguarda i conti :P

Bemipefe




Bemipefe
Per Polsy

Guarda un pò qua: http://twiki.dsi.uniroma1.it/pub/Lo...ltati060222.txt

è anche merito tuo GRAZIE!

Bemipefe
Ah scusami........ io sono quello che ha preso 18.....

Polsy
:D congratulazioni!

Powered by: vbHome (lite) v4.1 and vBulletin v2.3.1 - Copyright ©2000 - 2002, Jelsoft Enterprises Limited
Mantained by dsy crew (email) | Collabora con noi | Segnalaci un bug | Archive | Regolamento |Licenze | Thanks | Syndacate