| Definere mengde induktivt | Bygger dei opp innan/nedanfrå
Fordelar:
- god kontroll på kva element som er i mengda
- enklare å bevise |
| Lukka Mengde | Ei mengde er lukka under ein gikk operasjon innebære at når operasjonen utførast foreligger det garanti på at resultatet fins i same mengde |
| Induktivt definerte mengder | En induktivt definer mengde er den minste mengden som inneholder en gitt mengde – kalt en basismengde – og som er lukket under gitte operasjoner. En mengde definers induktivt I følgende tre steg:
Basissteget: å spesifisere en basismengde
Induksjonssteget: å spesifisere operasjonene
Tillukningen: å ta den minste mengden som inneholder basismengden og som er lukket under operasjonene
La oss induktivt definere partall:
Basismengde {0}
Operasjonene: en som tar x som argument og som gir x +2 som verdi, og en som tar x som argument og som gir x -2 som Verdi
Element i basismengden: 0
Steg 1: 2, -2
Steg 2: 4, -4
Steg 3: 6, -6 |
| Rekursive funksjonar | Rekursjon tar utgangspunkt I induktivt definerte mengder, og bygger videre på disse
Plassholder: kan være x, y [], input. Eksepel f(x) = 2x + 1 (x er plassholder). Husk: vi kan ikke bruke reserverte symboler som plassholdere ( feks + og - )
Rekursiv funksjon: “hvis en mengde M er induktivt definert, kan vi definer en reukrsiv funksjon f med definisjonsområdet M på følgende mate:
For hvert element x I basismengden til M, spesifiser en Verdi for f(x). Dette kalles basissteget eller basistilfellet for en funksjon
For hvert element x I M som fremkommer I et induksjonssteg, definer verdien til f(x) ved å bruke de tidligere definerte verdiene for f. Dette kalles rekursjonssteget. |
