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.

Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa

Svar
Sofie

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.
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Er det noe her som gikk tapt da du copy/paste'a oppgaven? Enkelte deler ser litt uforventet ut.
alfabetet {(,)}
∧ ∈ B
Bilde
Sofie

Takk for svar! Det er faktisk nøyaktig det som står i oppgaven...
Aleks855
Rasch
Rasch
Innlegg: 6855
Registrert: 19/03-2011 15:19
Sted: Trondheim
Kontakt:

Da er det bare jeg som har glemt notasjonen for formelle språk. :)
Bilde
DennisChristensen
Grothendieck
Grothendieck
Innlegg: 826
Registrert: 09/02-2015 23:28
Sted: Oslo

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.
Gjest3092

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

Stemmer at tegnet er Lambda, ja!:-)
HJELPPLS

Noen som kan hjelpe med oppgave b, sitter veldig veldig fast :(((
Svar