Strukturell induksjon

Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk på høyskolenivå. Alle som har kunnskapen er velkommen med et svar. Men, ikke forvent at admin i matematikk.net er spesielt aktive her.

Strukturell induksjon

Innlegg Sofie » 14/03-2019 21:02

Hei! Jeg sliter med å skjønne hvordan jeg skal løse disse oppgavene. Har ikke helt forstått meg på induksjon enda, så sliter spesielt med det... Håper noen snille kan hjelpe meg på veien :D

Oppgave 1:
La B være språket over alfabetet {(,)} som er induktivt definert slik:

∧ ∈ B
Hvis X ∈ B og Y ∈ B, så XY ∈ B.
Hvis X ∈ B, så (X) ∈ B.

a) Forklar med egne ord hvordan elementene i mengden B ser ut.
b) Bevis ved strukturell induksjon at for alle X ∈ B, er det slik at antall tegn I X er et partall.
c) Definer to funksjoner, v og h, rekursivt slik at for alle X ∈ B, er v(X) antall venstreparenteser I X og h(X) antall høyreparenteser i X.

Oppgave 2:
Definer en rekursiv funksjon SUM på lister over tall som summerer alle tallene i listen. For eksempel vil SUM((2, 3)) = 5 og SUM((2, 3, 4)) = 9. Bevis ved strukturell induksjon at SUM(L + M) = SUM(L) + SUM(M) for alle lister L og M.
Sofie offline

Re: Strukturell induksjon

Innlegg Aleks855 » 14/03-2019 21:06

Er det noe her som gikk tapt da du copy/paste'a oppgaven? Enkelte deler ser litt uforventet ut.

alfabetet {(,)}


∧ ∈ B
Bilde
Aleks855 offline
Rasch
Rasch
Innlegg: 5706
Registrert: 19/03-2011 15:19
Bosted: Trondheim

Re: Strukturell induksjon

Innlegg Sofie » 14/03-2019 23:15

Takk for svar! Det er faktisk nøyaktig det som står i oppgaven...
Sofie offline

Re: Strukturell induksjon

Innlegg Aleks855 » 15/03-2019 08:01

Da er det bare jeg som har glemt notasjonen for formelle språk. :)
Bilde
Aleks855 offline
Rasch
Rasch
Innlegg: 5706
Registrert: 19/03-2011 15:19
Bosted: Trondheim

Re: Strukturell induksjon

Innlegg DennisChristensen » 15/03-2019 10:01

Noe er feil. Vi er gitt at $\wedge\in B$, men dette ordet består av kun ett tegn, altså lar ikke oppgave (b) seg løse.
DennisChristensen offline
Fermat
Fermat
Innlegg: 743
Registrert: 09/02-2015 23:28
Bosted: Oslo

Re: Strukturell induksjon

Innlegg Gjest3092 » 15/03-2019 15:53

Tegnet i oppgaven er ikke konjunkt, men Lambda. Lambda konjunkt XY = XY.
Gjest3092 offline

Re: Strukturell induksjon

Innlegg Gjest » 15/03-2019 19:58

Stemmer at tegnet er Lambda, ja!:-)
Gjest offline

Hvem er i forumet

Brukere som leser i dette forumet: Ingen registrerte brukere og 12 gjester