10 Rekursive funksjoner

Question 1

rekursiv funksjon

Answer 1

Hvis en mengde M er induktivt definert, kan vi definere en rekursiv funksjon (eng: recursive function) 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 (eng: base case) 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 (eng: recursion step).

Question 2

valuasjon (rekursiv funksjon)

Answer 2

La t vre en tilordning av sannhetsverdier til utsagnsvariabler, det vil si en funksjon fra mengden av utsagnsvariabler til {0,1}. En valuasjon (eng: valuation) kan nå defineres rekursivt som en funksjon v fra utsagnslogiske formler til {0, 1} på følgende måte:

Basissteget:
- v(P) = 1 hvis og bare hvis t(P) = 1, for alle utsagnsvariabler P.
Rekursjonssteget:
- 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