MAT1030 – Diskret matematikk Plenumsregning 8: Diverse ukeoppgaver fra kapittel 6 & 7,mm. Roger Antonsen

(1)

MAT1030 – Diskret matematikk

Plenumsregning 8: Diverse ukeoppgaver fra kapittel 6 & 7,mm.

Roger Antonsen

Matematisk Institutt, Universitetet i Oslo

27. mars 2008

(2)

Repetisjon

Funksjoner - Viktige begreper

Argumenter og verdier

Definisjonsomr˚adet til en funksjon Verdiomr˚adet til en funksjon Bildet til en funksjon Injektive funksjoner Surjektive funksjoner

Sammensetning av funksjoner Inverse funksjoner

MAT1030 – Diskret matematikk 27. mars 2008 2

(3)

Repetisjon

Funksjoner - Viktige begreper Argumenter og verdier

(4)

Repetisjon

Definisjonsomr˚adet til en funksjon

Verdiomr˚adet til en funksjon Bildet til en funksjon Injektive funksjoner Surjektive funksjoner

(5)

Repetisjon

Definisjonsomr˚adet til en funksjon Verdiomr˚adet til en funksjon

Bildet til en funksjon Injektive funksjoner Surjektive funksjoner

(6)

Repetisjon

Definisjonsomr˚adet til en funksjon Verdiomr˚adet til en funksjon Bildet til en funksjon

Injektive funksjoner Surjektive funksjoner

(7)

Repetisjon

Definisjonsomr˚adet til en funksjon Verdiomr˚adet til en funksjon Bildet til en funksjon Injektive funksjoner

Surjektive funksjoner

(8)

Repetisjon

(9)

Repetisjon

Sammensetning av funksjoner

Inverse funksjoner

(10)

Repetisjon

(11)

Repetisjon

Rekursjon og induksjon

Rekursive definisjoner Induksjonsbevis

Induksjonsstart & induksjonsskritt Rekurrenslikninger

Hvordan finne løsninger til rekurrenslikninger Den karakteristiske likningen til en rekurrenslikning Generell rekursjon og induksjon

Induktivt definerte mengder Rekursjon over slike

Alfabet, ord, formelle spr˚ak, formler Simultan rekursjon

(12)

Repetisjon

Rekursjon og induksjon Rekursive definisjoner

Induksjonsbevis

(13)

Repetisjon

Rekursjon og induksjon Rekursive definisjoner Induksjonsbevis

(14)

Repetisjon

Induksjonsstart & induksjonsskritt

Rekurrenslikninger

(15)

Repetisjon

(16)

Repetisjon

Hvordan finne løsninger til rekurrenslikninger

Den karakteristiske likningen til en rekurrenslikning Generell rekursjon og induksjon

(17)

Repetisjon

Hvordan finne løsninger til rekurrenslikninger Den karakteristiske likningen til en rekurrenslikning

Generell rekursjon og induksjon Induktivt definerte mengder Rekursjon over slike

(18)

Repetisjon

(19)

Repetisjon

Induktivt definerte mengder

Rekursjon over slike

(20)

Repetisjon

(21)

Repetisjon

Alfabet, ord, formelle spr˚ak, formler

Simultan rekursjon

(22)

Repetisjon

(23)

Oppgave (fra forelesningen 25/2 p˚a side 33)

a) Vis at hvis f :X →Y og g :Y →Z begge har inversef⁻¹ og g⁻¹, s˚a vil sammensetningen

h =g◦f ogs˚a ha en invers.

b) Under antagelsene i a), vis at h⁻¹ =f⁻¹◦g⁻¹.

(24)

a) Vis at hvisf :X →Y og g :Y →Z begge har inversef⁻¹ og g⁻¹, s˚a vil sammensetningen

(25)

a) Vis at hvisf :X →Y og g :Y →Z begge har inversef⁻¹ og g⁻¹, s˚a vil sammensetningen

(26)

Løsning (a)

Det g˚ar fint an ˚a vise dette direkte, men vi kan ogs˚a bruke det vi har lært om funksjoner.

(1) Vi har tidligere i kurset vist at en funksjon har en invers hvis og bare hvis den er injektiv og surjektiv. Det er derfor tilstrekkelig ˚a vise ath er b˚ade injektiv og surjektiv.

Ved (1), sidenf og g begge har inverser, s˚a m˚a f og g være b˚ade injektive og surjektive.

(2) Vi har tidligere vist at hvisf og g er injektive, s˚a erg ◦f injektiv. (3) Vi har tidligere vist at hvisf og g er surjektive, s˚a erg ◦f surjektiv.

Ved (2) og (3) er h b˚ade injektiv og surjektiv. Ved (1) har h en invers.

(27)

Løsning (a)

(28)

Løsning (a)

(29)

Løsning (a)

(30)

Løsning (a)

(2) Vi har tidligere vist at hvisf og g er injektive, s˚a erg ◦f injektiv.

(3) Vi har tidligere vist at hvisf og g er surjektive, s˚a erg ◦f surjektiv. Ved (2) og (3) er h b˚ade injektiv og surjektiv.

Ved (1) har h en invers.

(31)

Løsning (a)

(3) Vi har tidligere vist at hvisf og g er surjektive, s˚a erg ◦f surjektiv.

(32)

Løsning (a)

Ved (2) og (3) er h b˚ade injektiv og surjektiv.

(33)

Løsning (a)

Ved (2) og (3) er h b˚ade injektiv og surjektiv.

(34)

Løsning (b)

For ˚a vise atf⁻¹◦g⁻¹ er inversen til h, m˚a vi vise at

h((f⁻¹◦g⁻¹)(z)) =z for alle z ∈Z og at (f⁻¹◦g⁻¹)(h(x)) =x for alle x∈X.

For ˚a gjøre det m˚a vi bruke atf⁻¹ er inversen til f og atg⁻¹ er inversen til g.

h((f⁻¹◦g⁻¹)(z)) =h(f⁻¹(g⁻¹(z))) = (g ◦f)(f⁻¹(g⁻¹(z))) = g(f(f⁻¹(g⁻¹(z)))) =g(g⁻¹(z)) =z

(f⁻¹◦g⁻¹)(h(x)) =f⁻¹(g⁻¹(h(x))) =f⁻¹(g⁻¹((g◦f)(x))) = f⁻¹(g⁻¹(g(f(x)))) =f⁻¹(f(x)) =x

(35)

Løsning (b)

For ˚a vise atf⁻¹◦g⁻¹ er inversen til h, m˚a vi vise at h((f⁻¹◦g⁻¹)(z)) =z for allez ∈Z

og at (f⁻¹◦g⁻¹)(h(x)) =x for alle x∈X.

(36)

Løsning (b)

h((f⁻¹◦g⁻¹)(z)) =z for allez ∈Z og at (f⁻¹◦g⁻¹)(h(x)) =x for alle x∈X.

(37)

Løsning (b)

(38)

Løsning (b)

h((f⁻¹◦g⁻¹)(z))

=h(f⁻¹(g⁻¹(z))) = (g ◦f)(f⁻¹(g⁻¹(z))) = g(f(f⁻¹(g⁻¹(z)))) =g(g⁻¹(z)) =z

(39)

Løsning (b)

h((f⁻¹◦g⁻¹)(z)) =h(f⁻¹(g⁻¹(z)))

= (g ◦f)(f⁻¹(g⁻¹(z))) = g(f(f⁻¹(g⁻¹(z)))) =g(g⁻¹(z)) =z

(40)

Løsning (b)

h((f⁻¹◦g⁻¹)(z)) =h(f⁻¹(g⁻¹(z))) = (g ◦f)(f⁻¹(g⁻¹(z)))

= g(f(f⁻¹(g⁻¹(z)))) =g(g⁻¹(z)) =z

(41)

Løsning (b)

h((f⁻¹◦g⁻¹)(z)) =h(f⁻¹(g⁻¹(z))) = (g ◦f)(f⁻¹(g⁻¹(z))) = g(f(f⁻¹(g⁻¹(z))))

=g(g⁻¹(z)) =z

(42)

Løsning (b)

h((f⁻¹◦g⁻¹)(z)) =h(f⁻¹(g⁻¹(z))) = (g ◦f)(f⁻¹(g⁻¹(z))) = g(f(f⁻¹(g⁻¹(z)))) =g(g⁻¹(z))

=z

(43)

Løsning (b)

(44)

Løsning (b)

(f⁻¹◦g⁻¹)(h(x))

=f⁻¹(g⁻¹(h(x))) =f⁻¹(g⁻¹((g◦f)(x))) = f⁻¹(g⁻¹(g(f(x)))) =f⁻¹(f(x)) =x

(45)

Løsning (b)

(f⁻¹◦g⁻¹)(h(x)) =f⁻¹(g⁻¹(h(x)))

=f⁻¹(g⁻¹((g◦f)(x))) = f⁻¹(g⁻¹(g(f(x)))) =f⁻¹(f(x)) =x

(46)

Løsning (b)

(f⁻¹◦g⁻¹)(h(x)) =f⁻¹(g⁻¹(h(x))) =f⁻¹(g⁻¹((g◦f)(x)))

= f⁻¹(g⁻¹(g(f(x)))) =f⁻¹(f(x)) =x

(47)

Løsning (b)

(f⁻¹◦g⁻¹)(h(x)) =f⁻¹(g⁻¹(h(x))) =f⁻¹(g⁻¹((g◦f)(x))) = f⁻¹(g⁻¹(g(f(x))))

=f⁻¹(f(x)) =x

(48)

Løsning (b)

(f⁻¹◦g⁻¹)(h(x)) =f⁻¹(g⁻¹(h(x))) =f⁻¹(g⁻¹((g◦f)(x))) = f⁻¹(g⁻¹(g(f(x)))) =f⁻¹(f(x))

=x

(49)

Løsning (b)

(50)

Vi vet at vi kan dele planet opp i to felter ved hjelp av en sirkel. Vi vet at to sirkler kan skjære hverandre i to punkter

Vi vet at 2n punkter vil dele en sirkel opp i 2n buestykker.

Bruk dette til ˚a definere funksjonenG(n) ved rekursjon, hvor G(n) er antall omr˚ader vi kan dele planet opp i ved hjelp av n sirkler.

Foresl˚a en formel forG(n) og se om du kan vise den ved induksjon.

(51)

Vi vet at vi kan dele planet opp i to felter ved hjelp av en sirkel.

Vi vet at to sirkler kan skjære hverandre i to punkter Vi vet at 2n punkter vil dele en sirkel opp i 2n buestykker.

(52)

Vi vet at to sirkler kan skjære hverandre i to punkter

Vi vet at 2n punkter vil dele en sirkel opp i 2n buestykker.

(53)

(54)

(55)

(56)

Løsning

G(1) = 2, siden ´en sirkel gir to omr˚ader.

Hvis n sirkler deler planet opp iG(n) omr˚ader, m˚a vi se p˚a hva som skjer n˚ar vi legger til en ny sirkel.

Siden den nye sirkelen vil skjære hver av de andren sirklene høyst 2 steder, s˚a f˚ar vi høyst 2n nye skjæringspunkter.

Disse skjæringspunktene deler den nye sirkelen inn i 2n buestykker, og hvert av disse buestykkene kan dele et av de gamle omr˚adene inn i to. Vi kan alts˚a f˚a 2n nye omr˚ader n˚ar vi legger til sirkel nummern+ 1. Det betyr at G(n+ 1) =G(n) + 2n

(57)

Løsning

(58)

Løsning

(59)

Løsning

(60)

Løsning

Disse skjæringspunktene deler den nye sirkelen inn i 2n buestykker, og hvert av disse buestykkene kan dele et av de gamle omr˚adene inn i to.

Vi kan alts˚a f˚a 2n nye omr˚ader n˚ar vi legger til sirkel nummern+ 1. Det betyr at G(n+ 1) =G(n) + 2n

(61)

Løsning

Vi kan alts˚a f˚a 2n nye omr˚ader n˚ar vi legger til sirkel nummern+ 1.

Det betyr at G(n+ 1) =G(n) + 2n

(62)

Løsning

Vi kan alts˚a f˚a 2n nye omr˚ader n˚ar vi legger til sirkel nummern+ 1.

Det betyr at G(n+ 1) =G(n) + 2n

(63)

Løsning

Hvis vi skal tippe p˚a en formel direkte, s˚a ser vi atG(n) ligger ganske nærme n².

n G(n) n²

G(n)−n²

1 2 1 1

2 4 4 0

3 8 9 −1

4 14 16 −2

5 22 25 −3

6 32 36 −4

Vi ser at differansen mellomG(n) og n² er −n+ 2. Vi tipper derfor p˚a formelenG(n) =n²−n+ 2. Vi viser at G(n) =n²−n+ 2 ved induksjon.

(64)

Løsning

n G(n) n²

G(n)−n²

1 2 1 1

2 4 4 0

3 8 9 −1

4 14 16 −2

5 22 25 −3

6 32 36 −4

(65)

Løsning

n G(n) n²

G(n)−n²

1 2 1 1

2 4 4 0

3 8 9 −1

4 14 16 −2

5 22 25 −3

6 32 36 −4

(66)

Løsning

n G(n) n²

G(n)−n²

1 2 1

1

2 4 4 0

3 8 9 −1

4 14 16 −2

5 22 25 −3

6 32 36 −4

(67)

Løsning

n G(n) n²

G(n)−n²

1 2 1

1

2 4 4

0

3 8 9 −1

4 14 16 −2

5 22 25 −3

6 32 36 −4

(68)

Løsning

n G(n) n²

G(n)−n²

1 2 1

1

2 4 4

0

3 8 9

−1

4 14 16 −2

5 22 25 −3

6 32 36 −4

(69)

Løsning

n G(n) n²

G(n)−n²

1 2 1

1

2 4 4

0

3 8 9

−1

4 14 16

−2

5 22 25 −3

6 32 36 −4

(70)

Løsning

n G(n) n²

G(n)−n²

1 2 1

1

2 4 4

0

3 8 9

−1

4 14 16

−2

5 22 25

−3

6 32 36 −4

(71)

Løsning

n G(n) n²

G(n)−n²

1 2 1

1

2 4 4

0

3 8 9

−1

4 14 16

−2

5 22 25

−3

6 32 36

−4 Vi ser at differansen mellomG(n) og n² er −n+ 2. Vi tipper derfor p˚a formelenG(n) =n²−n+ 2. Vi viser at G(n) =n²−n+ 2 ved induksjon.

(72)

Løsning

n G(n) n² G(n)−n²

1 2 1

1

2 4 4

0

3 8 9

−1

4 14 16

−2

5 22 25

−3

6 32 36

(73)

Løsning

1 2 1 1

2 4 4

0

3 8 9

−1

4 14 16

−2

5 22 25

−3

6 32 36

(74)

Løsning

1 2 1 1

2 4 4 0

3 8 9

−1

4 14 16

−2

5 22 25

−3

6 32 36

(75)

Løsning

1 2 1 1

2 4 4 0

3 8 9 −1

4 14 16

−2

5 22 25

−3

6 32 36

(76)

Løsning

1 2 1 1

2 4 4 0

3 8 9 −1

4 14 16 −2

5 22 25

−3

6 32 36

(77)

Løsning

1 2 1 1

2 4 4 0

3 8 9 −1

4 14 16 −2

5 22 25 −3

6 32 36

(78)

Løsning

1 2 1 1

2 4 4 0

3 8 9 −1

4 14 16 −2

5 22 25 −3

6 32 36 −4

(79)

Løsning

1 2 1 1

2 4 4 0

3 8 9 −1

4 14 16 −2

5 22 25 −3

6 32 36 −4

Vi ser at differansen mellomG(n) og n² er −n+ 2.

Vi tipper derfor p˚a formelenG(n) =n²−n+ 2. Vi viser at G(n) =n²−n+ 2 ved induksjon.

(80)

Løsning

1 2 1 1

2 4 4 0

3 8 9 −1

4 14 16 −2

5 22 25 −3

6 32 36 −4

Vi tipper derfor p˚a formelenG(n) =n²−n+ 2.

Vi viser at G(n) =n²−n+ 2 ved induksjon.

(81)

Løsning

1 2 1 1

2 4 4 0

3 8 9 −1

4 14 16 −2

5 22 25 −3

6 32 36 −4

Vi tipper derfor p˚a formelenG(n) =n²−n+ 2.

Vi viser at G(n) =n²−n+ 2 ved induksjon.

(82)

Løsning

Basissteget er ˚a vise at formelen G(n) =n²−n+ 2 holder forn= 1:

G(1) = 1²−1 + 2 = 2, som stemmer.

Vi antar s˚a at G(n) =n²−n+ 2. Det er induksjonshypotesen. Induksjonsstegetg˚ar ut p˚a ˚a vise atG(n+ 1) = (n+ 1)²−(n+ 1) + 2. Vi regner p˚a følgende m˚ate:

G(n+ 1) = G(n) + 2n (ved antakelse)

= (n²−n+ 2) + 2n (ved induksjonshypotese)

= n²+n+ 2

= (n²+ 2n+ 1)−n+ 1

= (n+ 1)²−n+ 1

= (n+ 1)²−(n+ 1) + 2

(83)

Løsning

G(1)

= 1²−1 + 2 = 2, som stemmer.

= n²+n+ 2

= (n²+ 2n+ 1)−n+ 1

= (n+ 1)²−n+ 1

= (n+ 1)²−(n+ 1) + 2

(84)

Løsning

G(1) = 1²−1 + 2

= 2, som stemmer.

= n²+n+ 2

= (n²+ 2n+ 1)−n+ 1

= (n+ 1)²−n+ 1

= (n+ 1)²−(n+ 1) + 2

(85)

Løsning

G(1) = 1²−1 + 2 = 2

, som stemmer.

= n²+n+ 2

= (n²+ 2n+ 1)−n+ 1

= (n+ 1)²−n+ 1

= (n+ 1)²−(n+ 1) + 2

(86)

Løsning

G(1) = 1²−1 + 2 = 2, som stemmer.

= n²+n+ 2

= (n²+ 2n+ 1)−n+ 1

= (n+ 1)²−n+ 1

= (n+ 1)²−(n+ 1) + 2

(87)

Løsning

G(1) = 1²−1 + 2 = 2, som stemmer.

Vi antar s˚a at G(n) =n²−n+ 2.

Det er induksjonshypotesen. Induksjonsstegetg˚ar ut p˚a ˚a vise atG(n+ 1) = (n+ 1)²−(n+ 1) + 2. Vi regner p˚a følgende m˚ate:

= n²+n+ 2

= (n²+ 2n+ 1)−n+ 1

= (n+ 1)²−n+ 1

= (n+ 1)²−(n+ 1) + 2

(88)

Løsning

G(1) = 1²−1 + 2 = 2, som stemmer.

Vi antar s˚a at G(n) =n²−n+ 2. Det er induksjonshypotesen.

Induksjonsstegetg˚ar ut p˚a ˚a vise atG(n+ 1) = (n+ 1)²−(n+ 1) + 2. Vi regner p˚a følgende m˚ate:

= n²+n+ 2

= (n²+ 2n+ 1)−n+ 1

= (n+ 1)²−n+ 1

= (n+ 1)²−(n+ 1) + 2

(89)

Løsning

G(1) = 1²−1 + 2 = 2, som stemmer.

Induksjonsstegetg˚ar ut p˚a ˚a vise atG(n+ 1) = (n+ 1)²−(n+ 1) + 2.

Vi regner p˚a følgende m˚ate:

= n²+n+ 2

= (n²+ 2n+ 1)−n+ 1

= (n+ 1)²−n+ 1

= (n+ 1)²−(n+ 1) + 2

(90)

Løsning

G(1) = 1²−1 + 2 = 2, som stemmer.

Induksjonsstegetg˚ar ut p˚a ˚a vise atG(n+ 1) = (n+ 1)²−(n+ 1) + 2.

Vi regner p˚a følgende m˚ate:

= n²+n+ 2

= (n²+ 2n+ 1)−n+ 1

= (n+ 1)²−n+ 1

= (n+ 1)²−(n+ 1) + 2