Matematik
well found induction
Hej
Kan nogle forklare mig hvordan man laver et WELL FOUND induktions bevis?
I mit eksempel skal jeg bevise at to sml-funktioner er ens, men hvis en kan forklare mig det generelle princip vil det være MINDST lige så fantastisk!
Her er alligevel lige mit sml eksempel:
datatype tree = Lf | Br of int*tree*tree:
fun size Lf =0 | size(Br(i,t1,t2)) = 1+size t1+ size t2;
fun sizeI Lf k=k | sizeI (Br(i,t1,t2)) k = size t1 (1+sizeI t2 k);
Bevis vha. WELL FOUND induktion at sizeI tr k = k+size tr gælder for alle trees tr og alle heltal k.
På forhånd tak for al tænkelig hjælp!
-Sarah
Svar #1
12. november 2010 af peter lind
Lad f(n) være en eller anden påstand som kan være sand eller falsk. Hvis du har at a) f(1) og og b) f(n) => f(n+1) så gælder f(n) for alle n >0
Argument f(1) er sandt Sætter du n = 1 i sætning b) får du at f(2) er sand. Derefter sætter du n=2 i sætning b) og får så f(3) er sand o.s.v.
Svar #2
12. november 2010 af Sa5 (Slettet)
Jo men det er bare et almindelig induktions bevis ikke? Det er WELL FOUND induktions beviser jeg ikke forstår... men tak ellers :)
Svar #3
12. november 2010 af peter lind
Jeg har aldrig hørt om well found induction. Jeg har søgt på et matematikleksikon. De giver en liste hvor man bruger induktion. Jeg har ikke orket at se dem alle igennem. Dem jeg har set er blot normal induktion. Min mistanke går så på om der egentlig eksisterer sådan en særlig induktion. Hvor er du stødt på det henne ?
Du kan søge videre på matematikleksikonet, his du har lyst. Her er adressen
http://mathworld.wolfram.com/search/?query=well+found+induction&x=0&y=0
Svar #4
12. november 2010 af Sa5 (Slettet)
Det eksisterer :) Det er et spørgsmål om at udnytte "well founded relations".
Svar #5
12. november 2010 af Sa5 (Slettet)
Note: jeg burde derfor også have skrevet "well-founded inducton" i stedet for "well found induction" :)
Svar #6
12. november 2010 af Andersen11 (Slettet)
#5
Ja, det er altid en god ide at formulere opgaven præcist. Jeg kan henvise til denne artikel på wiki:
http://en.wikipedia.org/wiki/Well-founded_relation
der beskriver maskineriet i well-founded induction.
Well-founded induction kaldes også undertiden for Noethersk induktion.
Skriv et svar til: well found induction
Du skal være logget ind, for at skrive et svar til dette spørgsmål. Klik her for at logge ind.
Har du ikke en bruger på Studieportalen.dk?
Klik her for at oprette en bruger.