10 Rekursive funksjoner Flashcards
1
Q
10.1 Rekursiv funksjon
A
Hvis en mengde M er induktivt definert, kan vi definere en rekursiv funksjon f med definisjonsområdet M på følgende måte:
- For hvert element x i basismengden til M, spesifiser en verdi for f(x). Dette kalles basissteget eller basistilfellet for funksjonen.
- 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.
2
Q
10.2 Valuasjon
A
La t være en tilordning av sannhetsverdier til utsagnsvariabler, det vil si en funksjon fra mengden av utsagnsvariabler til {0,1}. En valuasjon kan nå defineres rekursivt som en funksjon v fra utsagnslogiske formler til {0,1} på følgende måte:
- v(P) = 1 hvis og bare hvis t(P) = 1, for alle utsagnsvariabler P. Dette er basistilfellet i definisjonen.
- v(¬F) = 1 hvis og bare hvis v(F) = 0
- v(F ∧ G) = 1 hvis og bare hvis v(F) = 1 og v(G) = 1
- v(F ∨ G) = 1 hvis og bare hvis v(F) = 1 eller v(G) = 1
- v(F → G) = 1 hvis og bare hvis v(F) = 1 impliserer v(G) = 1.
Disse fire punktene utgjør rekursjonssteget i definisjonen.
