.dsy:it. (http://www.dsy.it/forum/)
- Logica matematica (http://www.dsy.it/forum/forumdisplay.php?forumid=246)
-- [help] Dimostrazione per Induzione (http://www.dsy.it/forum/showthread.php?threadid=20708)

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?

__________________
_/\/\/\Bemipefe/\/\/\_

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

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?

__________________
_/\/\/\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.....

__________________
_/\/\/\Bemipefe/\/\/\_

congratulazioni!