MAT1030 – Diskret matematikk Plenumsregning 9: Diverse ukeoppgaver Roger Antonsen

(1)

MAT1030 – Diskret matematikk

Plenumsregning 9: Diverse ukeoppgaver

Roger Antonsen

Matematisk Institutt, Universitetet i Oslo

10. april 2008

(2)

Oppgaver fra forelesningene

Oppgave (fra forelesningen 10/3)

a) Ved ˚a bruke den rekursive definisjonen av PL, vis hvordan vi skritt for skritt kan finne verdiene av

PL(e,d) PL(a,d) PL(ab,d) PL(aba,d)

Husk at variablene a ogb kan st˚a for hvilken som helst avbokstavene a,b og d.

b) Vis, ved ˚a bruke definisjonen av R og egenskapen tilPL, at R(abac) =caba.

(3)

Oppgaver fra forelesningene

Husk at variablene aog b kan st˚a for hvilken som helst avbokstavene a,b og d.

(4)

Oppgaver fra forelesningene

(5)

Oppgaver fra forelesningene

PL(e,d)

PL(a,d) PL(ab,d) PL(aba,d)

(6)

Oppgaver fra forelesningene

PL(e,d) PL(a,d)

PL(ab,d) PL(aba,d)

(7)

Oppgaver fra forelesningene

PL(e,d) PL(a,d) PL(ab,d)

PL(aba,d)

(8)

Oppgaver fra forelesningene

(9)

Oppgaver fra forelesningene

(10)

Oppgaver fra forelesningene

(11)

Definisjonene av PL og R

Definisjon

PL(e,a) =a

PL(wb,a) =PL(w,a)b

PL(w,a) blir ordet aw, for alle ord w. Vi viser det induksjon etterp˚a, som en øvelse.

Definisjon

R(e) =e

R(wb) =PL(R(w),b)

R(w) blir speilvendingen av ordetw.

(12)

Definisjonene av PL og R

Definisjon PL(e,a) =a

PL(wb,a) =PL(w,a)b

Definisjon

R(e) =e

R(wb) =PL(R(w),b)

(13)

Definisjonene av PL og R

PL(wb,a) =PL(w,a)b

Definisjon

R(e) =e

R(wb) =PL(R(w),b)

(14)

Definisjonene av PL og R

PL(wb,a) =PL(w,a)b

PL(w,a) blir ordet aw, for alle ord w.

Vi viser det induksjon etterp˚a, som en øvelse.

Definisjon

R(e) =e

R(wb) =PL(R(w),b)

(15)

Definisjonene av PL og R

PL(wb,a) =PL(w,a)b

Definisjon

R(e) =e

R(wb) =PL(R(w),b)

(16)

Definisjonene av PL og R

PL(wb,a) =PL(w,a)b

Definisjon

R(e) =e

R(wb) =PL(R(w),b)

(17)

Definisjonene av PL og R

PL(wb,a) =PL(w,a)b

Definisjon R(e) =e

R(wb) =PL(R(w),b)

(18)

Definisjonene av PL og R

PL(wb,a) =PL(w,a)b

Definisjon R(e) =e

R(wb) =PL(R(w),b)

(19)

Definisjonene av PL og R

PL(wb,a) =PL(w,a)b

Definisjon R(e) =e

R(wb) =PL(R(w),b)

(20)

Løsning

a) PL(e,d)

=d

PL(a,d) =PL(ea,d) =PL(e,d)a=da PL(ad,d) =PL(a,d)d=dad

PL(aba,d) =PL(ab,d)a=PL(a,d)ba=PL(e,d)aba=daba b)

R(abac) =PL(R(aba),c)

=cR(aba) =cPL(R(ab),a)

=caR(ab) =caPL(R(a),b)

=cabR(a) =cabPL(R(e),a)

=cabaR(e) =caba

(21)

Løsning

a) PL(e,d) =d

=cabaR(e) =caba

(22)

Løsning

a) PL(e,d) =d PL(a,d)

=PL(ea,d) =PL(e,d)a=da PL(ad,d) =PL(a,d)d=dad

=cabaR(e) =caba

(23)

Løsning

a) PL(e,d) =d

PL(a,d) =PL(ea,d)

=PL(e,d)a=da PL(ad,d) =PL(a,d)d=dad

=cabaR(e) =caba

(24)

Løsning

a) PL(e,d) =d

PL(a,d) =PL(ea,d) =PL(e,d)a

=da PL(ad,d) =PL(a,d)d=dad

=cabaR(e) =caba

(25)

Løsning

a) PL(e,d) =d

PL(a,d) =PL(ea,d) =PL(e,d)a=da

PL(ad,d) =PL(a,d)d=dad

=cabaR(e) =caba

(26)

Løsning

a) PL(e,d) =d

PL(a,d) =PL(ea,d) =PL(e,d)a=da PL(ad,d)

=PL(a,d)d=dad

=cabaR(e) =caba

(27)

Løsning

a) PL(e,d) =d

PL(a,d) =PL(ea,d) =PL(e,d)a=da PL(ad,d) =PL(a,d)d

=dad

=cabaR(e) =caba

(28)

Løsning

a) PL(e,d) =d

=cabaR(e) =caba

(29)

Løsning

a) PL(e,d) =d

PL(aba,d)

=PL(ab,d)a=PL(a,d)ba=PL(e,d)aba=daba b)

=cabaR(e) =caba

(30)

Løsning

a) PL(e,d) =d

PL(aba,d) =PL(ab,d)a

=PL(a,d)ba=PL(e,d)aba=daba b)

=cabaR(e) =caba

(31)

Løsning

a) PL(e,d) =d

PL(aba,d) =PL(ab,d)a=PL(a,d)ba

=PL(e,d)aba=daba b)

=cabaR(e) =caba

(32)

Løsning

a) PL(e,d) =d

PL(aba,d) =PL(ab,d)a=PL(a,d)ba=PL(e,d)aba

=daba b)

=cabaR(e) =caba

(33)

Løsning

a) PL(e,d) =d

PL(aba,d) =PL(ab,d)a=PL(a,d)ba=PL(e,d)aba=daba

b)

=cabaR(e) =caba

(34)

Løsning

a) PL(e,d) =d

R(abac)

=PL(R(aba),c)

=cabaR(e) =caba

(35)

Løsning

a) PL(e,d) =d

=cabaR(e) =caba

(36)

Løsning

a) PL(e,d) =d

=cR(aba)

=cPL(R(ab),a)

=cabaR(e) =caba

(37)

Løsning

a) PL(e,d) =d

=cabaR(e) =caba

(38)

Løsning

a) PL(e,d) =d

=caR(ab)

=caPL(R(a),b)

=cabaR(e) =caba

(39)

Løsning

a) PL(e,d) =d

=cabaR(e) =caba

(40)

Løsning

a) PL(e,d) =d

=cabR(a)

=cabPL(R(e),a)

=cabaR(e) =caba

(41)

Løsning

a) PL(e,d) =d

=cabaR(e) =caba

(42)

Løsning

a) PL(e,d) =d

=cabaR(e)

=caba

(43)

Løsning

a) PL(e,d) =d

=cabaR(e) =caba

(44)

Oppgave (Øvelse i indukssjonsbevis)

Vis ved induksjon p˚a lengden av ord atPL(w,a) =aw. Løsning

Induksjonsstarten er at p˚astanden holder n˚ar w =e.

Da erPL(w,a) =PL(e,a) =a=aw.

Induksjonsskrittet:

Anta at p˚astanden holder for ord w av lengden. Det er v˚ar induksjonshypotese.

Anta at vi har et ordwbav lengden+ 1, hvorb er en bokstav. Vi m˚a vise at:PL(wb,a) =awb

Vi harPL(wb,a) =PL(w,a)bved definisjonen avPL. Ved induksjonshypotesen har viPL(w,a) =aw. Da har viPL(wb,a) =PL(w,a)b=awb.

(45)

Vis ved induksjon p˚a lengden av ord atPL(w,a) =aw.

Løsning

Induksjonsskrittet:

Anta at p˚astanden holder for ord w av lengden. Det er v˚ar induksjonshypotese.

(46)

Induksjonsskrittet:

Anta at p˚astanden holder for ordw av lengden. Det er v˚ar induksjonshypotese.

(47)

Da erPL(w,a) =PL(e,a) =a=aw. Induksjonsskrittet:

(48)

Induksjonsstarten er at p˚astanden holder n˚ar w =e. Da erPL(w,a) =PL(e,a) =a=aw.

Induksjonsskrittet:

(49)

Induksjonsskrittet:

(50)

Induksjonsskrittet:

Anta at p˚astanden holder for ordw av lengden.

Det er v˚ar induksjonshypotese.

(51)

Induksjonsskrittet:

(52)

Induksjonsskrittet:

Anta at vi har et ordwbav lengden+ 1, hvorber en bokstav.

Vi m˚a vise at:PL(wb,a) =awb

(53)

Induksjonsskrittet:

(54)

Induksjonsskrittet:

Vi harPL(wb,a) =PL(w,a)bved definisjonen avPL.

Ved induksjonshypotesen har viPL(w,a) =aw. Da har viPL(wb,a) =PL(w,a)b=awb.

(55)

Induksjonsskrittet:

Ved induksjonshypotesen har viPL(w,a) =aw.

Da har viPL(wb,a) =PL(w,a)b=awb.

(56)

Induksjonsskrittet:

Ved induksjonshypotesen har viPL(w,a) =aw.

(57)

Oppgaver fra forelesningene

Oppgave fra forelesningen 12/3

LaHF og f være definert som i eksemplet over, og laS :HF →HF være definert ved

S(X) =X ∪ {X}. a) Vis at X ∈HF ⇒S(X)∈HF.

b) LaX,Y ∈HF.

Vis at X ∈Y ⇒f(X)<f(Y).

c) Forklar hvorfor det ikke finnes noen X ∈HF slik atX ∈X

d) LaN ⊆HF være den minste mengden slik at ∅ ∈N og slik at hvis X ∈N s˚a vilS(X)∈N.

Drøft sammenhengen mellomN ogN0.

(58)

Oppgaver fra forelesningene

b) LaX,Y ∈HF.

(59)

Oppgaver fra forelesningene

b) LaX,Y ∈HF.

(60)

Oppgaver fra forelesningene

S(X) =X ∪ {X}.

a) Vis at X ∈HF ⇒S(X)∈HF. b) LaX,Y ∈HF.

(61)

Oppgaver fra forelesningene

S(X) =X ∪ {X}.

a) Vis at X ∈HF ⇒S(X)∈HF.

b) LaX,Y ∈HF.

(62)

Oppgaver fra forelesningene

S(X) =X ∪ {X}.

(63)

Oppgaver fra forelesningene

S(X) =X ∪ {X}.

(64)

Oppgaver fra forelesningene

S(X) =X ∪ {X}.

(65)

Oppgaver fra forelesningene

S(X) =X ∪ {X}.

d) LaN ⊆HF være den minste mengden slik at∅ ∈N og slik at hvis X ∈N s˚a vilS(X)∈N.

(66)

Oppgaver fra forelesningene

S(X) =X ∪ {X}.

d) LaN ⊆HF være den minste mengden slik at∅ ∈N og slik at hvis

(67)

Definisjonen av HF (fra forelesningen)

Vi definerer de hereditært endelige mengdeneHF som den minste mengden slik at

∅ ∈HF

HvisX ={a1, . . . ,an}er en endelig delmengde avHF, s˚a erX ∈HF.

Vi definerer f :HF →N0 ved rekursjon overHF ved

f(∅) = 0

f({a₁, . . . ,a_n}) = 2^f^(a¹⁾+· · ·+ 2^f^(aⁿ⁾.

Her m˚a vi anta at mengden er beskrevet uten gjentagelse, det vil si at alle a_i’ene er forskjellige.

Eksempel

∅ ∈HF,{∅} ∈HF,{∅,{∅}} ∈HF,{{∅}} ∈HF, . . .

(68)

Definisjonen av HF (fra forelesningen)

∅ ∈HF

HvisX ={a1, . . . ,an}er en endelig delmengde avHF, s˚a erX ∈HF. Vi definerer f :HF →N0 ved rekursjon overHF ved

f(∅) = 0

f({a₁, . . . ,a_n}) = 2^f^(a¹⁾+· · ·+ 2^f^(aⁿ⁾.

Eksempel

∅ ∈HF,{∅} ∈HF,{∅,{∅}} ∈HF,{{∅}} ∈HF, . . .

(69)

Definisjonen av HF (fra forelesningen)

∅ ∈HF

HvisX ={a1, . . . ,an}er en endelig delmengde avHF, s˚a erX ∈HF. Vi definerer f :HF →N0 ved rekursjon overHF ved

f(∅) = 0

f({a₁, . . . ,a_n}) = 2^f^(a¹⁾+· · ·+ 2^f^(aⁿ⁾.

Eksempel

∅ ∈HF,{∅} ∈HF,{∅,{∅}} ∈HF,{{∅}} ∈HF, . . .

(70)

Definisjonen av HF (fra forelesningen)

∅ ∈HF

HvisX ={a1, . . . ,an} er en endelig delmengde avHF, s˚a erX ∈HF.

Vi definerer f :HF →N0 ved rekursjon overHF ved

f(∅) = 0

f({a₁, . . . ,a_n}) = 2^f^(a¹⁾+· · ·+ 2^f^(aⁿ⁾.

Eksempel

∅ ∈HF,{∅} ∈HF,{∅,{∅}} ∈HF,{{∅}} ∈HF, . . .

(71)

Definisjonen av HF (fra forelesningen)

∅ ∈HF

HvisX ={a1, . . . ,an} er en endelig delmengde avHF, s˚a erX ∈HF. Vi definererf :HF →N0 ved rekursjon overHF ved

f(∅) = 0

f({a₁, . . . ,a_n}) = 2^f^(a¹⁾+· · ·+ 2^f^(aⁿ⁾.

Eksempel

∅ ∈HF,{∅} ∈HF,{∅,{∅}} ∈HF,{{∅}} ∈HF, . . .

(72)

Definisjonen av HF (fra forelesningen)

∅ ∈HF

f(∅) = 0

f({a₁, . . . ,a_n}) = 2^f^(a¹⁾+· · ·+ 2^f^(aⁿ⁾.

Eksempel

∅ ∈HF,{∅} ∈HF,{∅,{∅}} ∈HF,{{∅}} ∈HF, . . .

(73)

Definisjonen av HF (fra forelesningen)

∅ ∈HF

f(∅) = 0

f({a₁, . . . ,a_n}) = 2^f^(a¹⁾+· · ·+ 2^f^(aⁿ⁾.

Eksempel

∅ ∈HF,{∅} ∈HF,{∅,{∅}} ∈HF,{{∅}} ∈HF, . . .

(74)

Definisjonen av HF (fra forelesningen)

∅ ∈HF

f(∅) = 0

f({a₁, . . . ,a_n}) = 2^f^(a¹⁾+· · ·+ 2^f^(aⁿ⁾.

Eksempel

∅ ∈HF,{∅} ∈HF,{∅,{∅}} ∈HF,{{∅}} ∈HF, . . .

(75)

Definisjonen av HF (fra forelesningen)

∅ ∈HF

f(∅) = 0

f({a₁, . . . ,a_n}) = 2^f^(a¹⁾+· · ·+ 2^f^(aⁿ⁾.

Eksempel

∅ ∈HF,{∅} ∈HF,{∅,{∅}} ∈HF,{{∅}} ∈HF, . . .

(76)

Definisjonen av HF (fra forelesningen)

∅ ∈HF

f(∅) = 0

f({a₁, . . . ,a_n}) = 2^f^(a¹⁾+· · ·+ 2^f^(aⁿ⁾.

Eksempel

,{∅} ∈HF,{∅,{∅}} ∈HF,{{∅}} ∈HF, . . .

(77)

Definisjonen av HF (fra forelesningen)

∅ ∈HF

f(∅) = 0

f({a₁, . . . ,a_n}) = 2^f^(a¹⁾+· · ·+ 2^f^(aⁿ⁾.

Eksempel

∅ ∈HF,{∅} ∈HF

,{∅,{∅}} ∈HF,{{∅}} ∈HF, . . .

(78)

Definisjonen av HF (fra forelesningen)

∅ ∈HF

f(∅) = 0

f({a₁, . . . ,a_n}) = 2^f^(a¹⁾+· · ·+ 2^f^(aⁿ⁾.

Eksempel

,{{∅}} ∈HF, . . .

(79)

Definisjonen av HF (fra forelesningen)

∅ ∈HF

f(∅) = 0

f({a₁, . . . ,a_n}) = 2^f^(a¹⁾+· · ·+ 2^f^(aⁿ⁾.

Eksempel

∅ ∈HF,{∅} ∈HF,{∅,{∅}} ∈HF,{{∅}} ∈HF, . . .

(80)

Husk atS :HF →HF er definert vedS(X) =X ∪ {X}.

Løsning (a)

Vis at X ∈HF ⇒S(X)∈HF.

Anta at X ∈HF.

Da m˚a X ={a₁, . . . ,an} være en endelig delmengde avHF

(fordiHF er definert som denminste mengden som oppfyller de to kravene).

Da er S(X)

=X ∪ {X}={a₁, . . . ,an,X}, som ogs˚a er en endelig delmengde av HF.

Da m˚a S(X)∈HF.

(81)

Løsning (a)

Vis at X ∈HF ⇒S(X)∈HF.

Anta at X ∈HF.

Da m˚aX ={a₁, . . . ,an} være en endelig delmengde avHF

(fordi HF er definert som denminstemengden som oppfyller de to kravene).

Da er S(X)

Da m˚a S(X)∈HF.

(82)

Løsning (a)

Vis at X ∈HF ⇒S(X)∈HF. Anta at X ∈HF.

(fordi HF er definert som denminstemengden som oppfyller de to kravene).

Da er S(X)

Da m˚a S(X)∈HF.

(83)

Løsning (a)

(fordi HF er definert som denminstemengden som oppfyller de to kravene). Da er S(X)

Da m˚a S(X)∈HF.

(84)

Løsning (a)

Da m˚aX ={a₁, . . . ,an} være en endelig delmengde avHF (fordi HF er definert som denminstemengden som oppfyller de to kravene).

Da er S(X)

Da m˚a S(X)∈HF.

(85)

Løsning (a)

Da er S(X)

=X ∪ {X}={a₁, . . . ,a_n,X}, som ogs˚a er en endelig delmengde av HF.

Da m˚a S(X)∈HF.

(86)

Løsning (a)

Da er S(X) =X ∪ {X}

={a₁, . . . ,a_n,X}, som ogs˚a er en endelig delmengde av HF.

Da m˚a S(X)∈HF.

(87)

Løsning (a)

Da er S(X) =X ∪ {X}={a₁, . . . ,a_n,X}

, som ogs˚a er en endelig delmengde av HF.

Da m˚a S(X)∈HF.

(88)

Løsning (a)

Da er S(X) =X ∪ {X}={a₁, . . . ,a_n,X}, som ogs˚a er en endelig delmengde av HF.

Da m˚a S(X)∈HF.

(89)

Løsning (a)

Da er S(X) =X ∪ {X}={a₁, . . . ,a_n,X}, som ogs˚a er en endelig delmengde av HF.

Da m˚a S(X)∈HF.

(90)

Husk atf(∅) = 0 og f({a₁, . . . ,an}) = 2^f^(a¹⁾+· · ·+ 2^f^(aⁿ⁾.

Løsning (b)

La X,Y ∈HF. Vis at X ∈Y ⇒f(X)<f(Y).

Anta at Y ={a₁, . . . ,a_n,X}. Da vil f(Y)

=f({a₁, . . . ,an,X}) = 2^f^(a¹⁾+· · ·+ 2^f^(aⁿ⁾+ 2^f^(X⁾

Siden f(X)<2^f^(X⁾≤f(Y), har vif(X)<f(Y).