Kapitteltest – Kapittel 12
Oppgave
(Denne oppgaven er omtrent lik oppgave 12.1 i boken.)
La $f$ være en funksjon på bitstrenger definert rekursivt på følgende måte:
- $f(\str{0})=\str{1}$ og $f(\str{1})=\str{0}$
- $f(b\str{0})=f(b)\str{1}$, hvor $b$ er en bitstreng.
- $f(b\str{1})=f(b)\str{0}$, hvor $b$ er en bitstreng.
Følgende er et induksjonsbevis for at $f(f(b))=b$ for alle bitstrenger $b$. Finn ut hva som skal stå i boksene.
Basissteget: Det er at holder for $b=\str{0}$ og $b=\str{1}$.
Ved å sette inn $\str{0}$ for $b$, får vi $f(f(\str{0}))=\str{0}$. Følgende utregning viser at dette er sant.
- $f(f(\str{0}))=f(\str{1})$ (ved punkt 1 i definisjonen av $f$)
- $=\str{0}$ (ved punkt 1 i definisjonen av $f$)
Ved å sette inn $\str{1}$ for $b$, får vi $f(f(\str{1}))=\str{1}$. Følgende utregning viser at dette er sant.
- $f(f(\str{1}))=f(\str{0})$ (ved punkt 1 i definisjonen av $f$)
- $=\str{1}$ (ved punkt 1 i definisjonen av $f$)
steget: Anta at påstanden holder for en bitstreng $b$, det vil si at $f(f(b))=b$. Dette er , og vi må fra denne vise at holder for en bitstreng $bx$, det vil si at $f(f(bx))=$, hvor $x$ enten er $\str{0}$ eller $\str{1}$. Vi får to tilfeller, ett for $x=\str{0}$ og ett for $x=\str{1}$.
Hvis $x=0$, får vi følgende.
- $f(f(b\str{0})) = f(f(b)\str{1})$ (ved punkt i definisjonen av $f$)
- $=f(f(b))\str{0}$ (ved punkt 3 i definisjonen av $f$)
- $=b\str{0}$ (ved induksjonshypotesen)
Hvis $x=\str{1}$, får vi følgende.
- $f(f(b\str{1})) = f$ () (ved punkt i definisjonen av $f$)
- $=f(f(b))\str{1}$ (ved punkt 2 i definisjonen av $f$)
- $=b\str{1}$ (ved induksjonshypotesen)
Ved følger det at $f(f(b))=$ for alle bitstrenger $b$.