Bitstreng-bevis

[logikeren02]

Oppgaven er som følger: Første quote er oppgaveteksten, andre er hvordan svaret skal formuleres i svaret.

 

La f være en funksjon på bitstrenger definert rekursivt på følgende måte:

- f(0) = 1 og f(1) = 0 /// f(bo) = f(b)1, hvor b er en bitstreng./// f(b1) = f(b)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 1____ holder for b = 0, og b = 1.

Ved å sette inn 0 for b, får vi f(f(0)) = 0.

 

Følgende utregning viser at dette er sant.

f(f(0)) = f(1) ved punkt (1) i definisjonen av f
= 0 ved punkt (1) i definisjonen av f

Ved å sette inn 1 for b, får vi f(f(1)) = 1. Følgende utregning viser at dette er sant.

f(f(1)) = f(0) ved punkt (1) i definisjonen av f
= 1 ved punkt (1) i definisjonen av f

 

2______steget:

 

Anta at påstanden holder for en bitstreng b, det vil si at f(f(b)) = b.

Dette er 3___________, og vi må fra denne vise at 4____________ holder for en bitstreng bx, det vil si at f(f(bx)) = 5_____, hvor x enten er 0 eller 1.

Vi får to tilfeller, ett for x = 0 og ett for x = 1.

 

Hvis x = 0, får vi følgende.

f(f(b0)) = f(f(b)1) ved 6________ i definisjonen av f
= f(f(b))0 ved punkt (3) i definisjonen av f
= b0 ved induksjonshypotesen

 

Hvis x = 1, får vi følgende.

f(f(b1)) = f(7_______) ved 8________ i definisjonen av f
= f(f(b))1 ved punkt (2) i definisjonen av f
= b1 ved induksjonshypotesen

Ved 9_______ følger det at 10________ for alle bitstrenger b.

 

 

Beklager at det ser rotete ut. Håper på litt god hjelp her, da jeg rett og slett ikke vet hva jeg skal skrive på de 10 tomme feltene...