Diskret Matematikk [lecture notes] [PDF]

Zitiervorschau

MAT-1005: DISKRET MATEMATIKK BORIS KRUGLIKOV

1. Matematisk logikk Utsagn er en setning som er enten sant eller usant men ikke begge deler. Sannhetsverdien til et utsagn P er T (true = 1) dersom P er sant og F (false = 0) dersom P er usant. Eksempel 1.1. P: ”Long live the queen!” – ikke utsagn. Q: ”Lengde av en sirkel med radius 1 er 2π” – utsagn (T ). R: π = 3 – utsagn (F ). S: ”Jeg st˚ ar ved tavla” – ikke utsagn (avhengig av tid-rom). U(x): x < 1 – ikke utsagn, men U(0) er utsagn (T). V(x): ”x2 + 1 er et positivt tall” – ikke utsagn, men V(x) er utsagn dersom x er et reelt tall (sannhetsverdie T ). La oss studere logiske operasjoner for ˚ a lage nye utsagn fra en eller flere gamle utsagnene P , Q osv. Definisjon 1.2. Negasjonen til P er utsagnet ”ikke P ” = ¬P . Definisjon 1.3. Konjunksjonen ”P og Q” = P ∧ Q er utsagnet som er sant n˚ ar b˚ ade P og Q er sanne, og usant ellers. Definisjon 1.4. Disjunksjonen ”P eller Q” = P ∨ Q er utsagnet som er sant n˚ ar P eller Q er sanne, og usant ellers. Definisjon 1.5. Eksklusiv-eller ”P xor Q” = P ⊕ Q er utsagnet som er sant n˚ ar nøyaktig ett av P og Q er sant. Definisjon 1.6. Implikasjonen P → Q er utsagnet som er usant n˚ ar P er sant og Q usant, ellers er P → Q sant. Definisjon 1.7. Ekvivalens P ↔ Q er utsagnet som er sant n˚ ar P og Q har identiske sannhensverdiene. Vi kan skrive dette med sannhetstabbel : P Q P ∧Q P ¬P T T T T F T F F F T F T F F F F

P Q P ∨Q T T T T F T F T T F F F

2

BORIS KRUGLIKOV

P Q P ⊕Q T T F T T F F T T F F F

P Q P →Q T T T F T F F T T F F T

P Q P ↔Q T T T F T F F T F F F T

Eksempel 1.8. ”Hvis 0 = 1 da er jeg en konge”, dvs. alt kan følge fra et falsk utsagn: P (F ), Q (?), P → Q (T ). Vi kan bruke sannhetstabeller for ˚ a sjeke om et komlisert utsagn er sant eller usant. Eksempel 1.9. La oss beregne sannhetstabell for utsagnet (¬P ∨Q) → (P ⊕ ¬Q). P Q ¬P ¬Q R = ¬P ∨ Q S = P ⊕ ¬Q R → S T T F F T T T T F F T F F T F T T F T F F F F T T T T T Definisjon 1.10. Et sammensatt utsagn som er alltid sant kalles for tautologi . Utsagnet som er alltid falsk kalles motsigelse. Eksempel 1.11. P ∨ ¬P er en tautologi og P ∧ ¬P er en motsigelse. Definisjon 1.12. Utsagnene P og Q er logisk ekvivalente hvis P ↔ Q er en tautologi. Dette skriver vi s˚ ann: P ⇔ Q (ogs˚ a P ≡ Q). Om implikasjonen P → Q er en tautologi, skriver vi P ⇒ Q. Eksempel 1.13. Sjekk at utsagnet P → Q er ekvivalent med utsagnet ¬Q → ¬P . P Q ¬P ¬Q R = P → Q S = ¬Q → ¬P R ↔ S T T F F T T T T F F T F F T F T T F T T T F F T T T T T Derfor har vi (P → Q) ⇔ (¬Q → ¬P ). P˚ a det samme m˚ ate f˚ ar vi: (P → Q) ⇔ (¬P ∨ Q). En bit er et tall som er enten 0 eller 1, og den brukes i informatikk istedenfor logiske variabler (med verdiene F og T ). Bitoperasjoner i en datamaskin tilsvarer de logiske operasjonene vi har ovenfor. En bitstreng er en sekvens av bit, f.eks. 0100011011. Vi kan utvide bitoperasjoner til bitstrenger.

NOTATER - DISKRET MAT. 2010

3

Eksempel 1.14. ¬0011 = 1100, 0011 ∧ 1001 = 0001, 0011 ∨ 1001 = 1011, 0011 ⊕ 1001 = 1010. NB: Aristotle-Boolean logikk diskutert ovenfor bruker bare veriene 0 og 1. Fuzzy-logikk bruker reelle tall mellom 0 og 1 som sannhetsveriene. For eksempel, det er vanskelig ˚ a svare med bare ”ja” (T = 1) eller ”nei” (F = 0) til spørsm˚ al P : ”Vil det reigne i morgen?”. Det er bedre ˚ a svare ”Sannsynligvys nei” eller ”Nei med sannsynlighet 80%” (=”Ja med sannsynlighet 20%”), dvs. blir 0.2 sannhetsverdien til P . Det finnes mer kompliserte fuzzy, kvantum og andre logikker idag. 2. Logisk ekvivalens og bevismetoder Det er tidkrevende ˚ a sjekke om et sammensatt utsagn er tautologi via sannhetstabeller. Vi bruker logiske ekvivalenser for ˚ a simplifisere et bevis. Ekvivalens Navn p˚ a loven P ∧ T ≡ P, P ∨ F ≡ P Indentitet P ∧ F ≡ F, P ∨ T ≡ T Dominasjon P ∧P ≡P ∨P ≡P Idempotens ¬(¬P ) ≡ P Dobbeltnektelse P ∧ Q ≡ Q ∧ P, P ∨ Q ≡ Q ∨ P Kommutativitet (P ∧ Q) ∧ R ≡ P ∧ (Q ∧ R), (P ∨ Q) ∨ R ≡ P ∨ (Q ∨ R) Assosiativitet (P ∧ Q) ∨ R ≡ (P ∨ R) ∧ (Q ∨ R), (P ∨ Q) ∧ R ≡ (P ∧ R) ∨ (Q ∧ R) Distributivitet ¬(P ∧ Q) ≡ ¬P ∨ ¬Q, ¬(P ∨ Q) ≡ ¬P ∧ ¬Q de Morgan Eksempel 2.1. La oss bevise ((P ∨ ¬Q) → (P ∧ Q)) ⇔ Q: (P ∨ ¬Q) → (P ∧ Q) ≡ ¬(P ∨ ¬Q) ∨ (P ∧ Q) ≡ ≡ (¬P ∧ Q) ∨ (P ∧ Q) ≡ (¬P ∨ P ) ∧ Q ≡ T ∧ Q ≡ Q Et matematisk bevis er en lignende rekkefølge av argumenter som begynner med aksyomene (en grunnsetning som aksepteres uten bevis – ”i god tro”). Det finnes slik matematiske utsagn: teorem = et ”stor” matematisk utsagn som er bevist ˚ a være riktig; korollar = et ”lite” teorem som følger umiddelbart fra et annet teorem; lemma = et resultat/hjelpesetning som oftest bevises foran et teorem for ˚ a gjøre beviset for det sistenevnte reddiggere og kortere; formodning = et matematisk utsagn som er ikke (enn˚ a) bevist, men som man tror/h˚ aper er riktig.

4

BORIS KRUGLIKOV

Ved bevis av et matematisk utasgn P → Q bruker vi inferensregler. Noen av disse er P → P ∨ Q (addisjon),

P ∧ Q → P (forenkling),

...

se Rosen s.66 for tabellen. Det eksisterer forskjellige typer av bevis: Direkte bevis. Klarer vi ˚ a vise at n˚ ar P har sannhetsverdi T , s˚ a har Q ogs˚ a sannhetsverdi T , da vil implikasjonen P → Q være sann. Eksempel 2.2. La oss bevise at hver reel interval I av lengde 2 inneholder et odde tall, dvs. et heltall n p˚ a formen n = 2k + 1 der k ogs˚ a er et heltall. Vi har I = [x − 1, x + 1] og la m = [x] være integer del av x. Hvis m ∈ I er odd f˚ ar vi tallet som trenges. Hvis m er par, da er m ± 1 odd og ett av tallene tilhører I. Indirekte bevis. Her beviser vi ekvivalent utsagnet ¬Q → ¬P . Det kalles ogs˚ a bevis ved motsigelse: vi vil bevise Q er T dersom P er T , og vi antar Q er F dvs. ¬Q er T ; s˚ a følger det at ¬P er T og P er F som kan ikke skje. Eksempel 2.3. La oss besøke igjen eksempelet med intervallet I = [x − 1, x + 1] av lengde 2. Anta at I inneholder ingen odd tall. Da finnes ogs˚ a ingen odd tall i de følgende intervallene: I + 2 = [x + 1, x + 3], I + 4 = [x + 3, x + 5], . . . I − 2 = [x − 3, x − 1], I − 4 = [x − 5, x − 3], . . . fordi hvis er 2k + 1 ∈ I + 2m, da f˚ ar vi 2(k − m) + 1 ∈ I. Siden alle reelle tall dekkes av union av intervallene I + 2m, finnes det ingen odde tall i det hele tatt. Men 1 er reel og odd. Motsigelse! 3. Mengdelære Definisjon 3.1. En mengde er en samling A med ”objekter” a, b, . . . , som kalles punkter/ellementer i mengden A. Vi skriver A = {a, b, . . . } (rekkefølgen er lykegyldig) eller a ∈ A, . . . Eksempel 3.2. 1) Z = {0, ±1, ±2, . . . } – heltallene. 2) Q = { pq | p, q ∈ Z, q 6= 0} – de rasjonale tall. 3) R – de reelle tall; R+ = {x ∈ R | x > 0} – de positive tall. 4) S = {0, 1, π} = {1, 0, π} = {π, 0, 1}. 5) ∅ = {} – den tomme mengden. Definisjon 3.3. Mengdene A og B er like, A = B, dersom de inneholder nøyaktig de samme elementene: x ∈ A ⇔ x ∈ B. A er en delmengde av B, A ⊆ B (av og til skrives dette A ⊂ B), dersom hvert element i A ogs˚ a tilhører B: x ∈ A ⇒ x ∈ B.

NOTATER - DISKRET MAT. 2010

5

Antall elementer i A kan være endelig eller uendelig. Dette tallet |A| kalles kardinaliteten til A. Dersom A har et endelig antall av elementer, har vi |A| ∈ Z≥0 (ikke-negative heltallene). For |A| = ∞ finnes det en avansert definisjon av kardinaliteten. Definisjon 3.4. Gitt en mengde A er samlingen av alle delmengder av A ogs˚ a en mengde P (A) = {B | B ⊆ A} – potensmengden til A. Kantors teorem krever at |P (A)| > |A| for alle A. Hvis |A| = n < ∞, er dette enkelt fordi |P (A)| = 2n (gyldig ogs˚ a for n = 0 dvs. A = ∅). Eksempel 3.5. Betrakt A = {1, 2, . . . , n}. Da kan vi spesifisere delmengde B ⊂ A gjennom bitstreng a1 a2 . . . an med ai = 0 dersom i ∈ /B og ai = 1 dersom i ∈ B. For eksempel for n = 2 kan vi identifisere P (A) = {00, 01, 10, 11}, s˚ a |P (A)| = 2n = 4. Definisjon 3.6. La A og B være to mengder. Samlingen av alle ordnede par av punkter fra disse (rekkefølgen teller!) er en ny mengde som kalles det kartesiske produkt A × B = {(a, b) | a ∈ A, b ∈ B}. Eksempel 3.7. R2 = R × R er det vanlige kartesiske planet. P˚ a det samme m˚ ate har vi n-dimensional euklidske rom Rn = R × · · · × R. Øving. Sjekk at |A × B| = |A| · |B| for endelig A og B. NB: Det er ikke nødvendig at |A × B| > max{|A|, |B|} for uendelig A og B. Betrakt to mengder A, B som er delmengder i en universal mengde V . Definisjon 3.8. Unionen av A og B er mengden A ∪ B = {x ∈ V | x ∈ A ∨ x ∈ B}. Snittet av A og B er mengden A ∩ B = {x ∈ V | x ∈ A ∧ x ∈ B}. Diffferenase av A og B er mengden A \ B = {x ∈ V | x ∈ A∧x∈ / B}. Mengden Ac = V \ A kalles for komplementet til A. Vi har de samme de Morgans regler for operasjonene med mengder: Regel Navn A ∩ V = A, A ∪ ∅ = A Indentitet A ∩ ∅ = ∅, A ∪ V = V Dominasjon A∩A=A∪A=A Idempotens c c (A ) = A Dobbeltkomplement A ∩ B = B ∩ A, A ∪ B = B ∪ A Kommutativitet (A ∩ B) ∩ C = A ∩ (B ∩ C), (A ∪ B) ∪ C = A ∪ (B ∪ C) Assosiativitet (A ∩ B) ∪ C = (A ∪ C) ∩ (B ∪ C), (A ∪ B) ∩ C = (A ∩ C) ∪ (B ∩ C) Distributivitet (A ∩ B)c = Ac ∪ B c , (A ∪ B)c = Ac ∩ B c de Morgan

6

BORIS KRUGLIKOV

Dette viser at mengdelære er ekvivalent (isomorf) til formal logikkteori (og ogs˚ a til tallteori!), dvs at de er samtydig ikke-selvmotsigende og komplett. NB. Definisjon av mengde vi har diskutert er naiv og fører til mange paradokser. For eksempel samlingen av alle mengder er ikke sjøl en mengde, dvs. det eksisterer ingen universal mengde V , ellers blir Russels paradoks mulig, se Rosen s.121 (i praksis tar vi noen mengde V som ”universal” fordi det er nok ˚ a betrakte delmengder A ⊂ V ). P˚ a det samme m˚ ate er ikke alle setninger et utsagn. For eksempel (vi vil bruke kvantorer ∀ = ”for alle” og ∃ = ”det eksisterer”) P : ”∃A ⊂ R : |Z| < |A| < |R|” er ikke et utsagn i Aristotle-Boolean logikk (kontinuumhypotesen). 4. Funksjoner La A og B være to mengder. En funksjon f : A → B er en regel som til hvert element a ∈ A tilornder ett element b = f (a) ∈ B (b er bildet til a). A kalles for definisjonsomr˚ ade, B kalles for co-omr˚ ade og f (A) = {b = f (a) | a ∈ A} ⊆ B kalles for bildet til f . Det er viktig ˚ a spesifisere b˚ ade omr˚ adene A og B for ˚ a jobbe med funksjoner i datamaskiner. Definisjon 4.1. Funksjonen f er injektiv hvis f (x) = f (y) ⇒ x = y, dvs. to forskjellige elementer i A havner p˚ a to forskjellige elementfer i B. Funksjonen f er surjektiv hvis f (A) = B, dvs. ∀b ∈ B∃a ∈ A : f (a) = b. Funksjonen f er bijektiv dersom f er b˚ ade injektiv og surjektiv. Dersom f : A → B er bijektiv, definerer vi inversfunksjonen f −1 : B → A via f −1 (b) = a for b = f (a). Hver mengde A gir opphav til en identitetsfunksjon idA : A → A, idA (a) = a. For to funksjoner f : A → B, g : B → C definerer vi sammensetningen g ◦ f : A → C via (g ◦ f )(a) = g(f (a)). For en bijeksjon f : A → B har vi f −1 ◦ f = idA og f ◦ f −1 = idB . Eksempel 4.2. La f (x) = x2 . Hvis A = B = R+ , da er f bijeksjon og √ f −1 (x) = x. Om A = B = R, blir f hverken injektiv eller surjektiv. NB. N˚ a kan vi definere likhet for kardinaler (forskjellige ∞). Vi skriver |A| ≤ |B| dersom det finnes en injektiv funksjon f : A → B. Om f er bijektiv, skriver vi |A| = |B|. Bernsteins teorem krever at |A| ≤ |B| og |B| ≤ |A| impliserer |A| = |B|. For eksempel har vi: |Z| < |R| = |P (Z)|.

NOTATER - DISKRET MAT. 2010

7

I tilleg til vannlige funksjoner f (x) = xn , g(x) = ax , h(x) = log x osv. vil vi trenge noen andre funksjoner. Definisjon 4.3. For x ∈ R la bxc være det største heltall ≤ x. b c : R → Z kalles for gulvfunksjonen. La dxe være det minste heltall ≥ x. d e : R → Z kalles for takfunksjonen. Eksempel 4.4. 1) For n ∈ Z har vi bnc = dne = n. 2) bπc = 3 og dπe = 4, fordi π = 3.14159... 3) b−ec = −3 og d−ee = −2, fordi e = 2.71828... En annen viktig funksjon Z+ → Z+ er faktorial f (n) = n! = 1·2 · · · n. Vi har 0! = 1, 1! = 1, 2! = 2, 3! = 6, 4! = 24, . . . , 10! = 3 628 800, . . . La oss endelig betrakte funksjoner Z+ → R. Dette kaller vi for rekkefølger: ai = f (i), slik at vi kan skrive a1 , a2 , . . . i stedet for f . Eksempel 4.5. an = α + nβ kalles for en aritmetisk følge. bn = α β n kalles for en geometrisk følger. P Hvis mengden A er endelig og best˚ ar ev reelle tall, skriver vi A a for summen av alle elementer i A. For rekkefølger har vi en spesial tegnesystem: n X ai = am + am+1 + · · · + an . i=m n P

Eksempel 4.6. 1) 2)

n P

i = 1 + 2 + ··· + n =

i=1 i

2

r = 1 + r + r + · · · + rn =

i=0

rn+1 −1 r−1

n(n+1) . 2

for r 6= 1 (og n + 1 for r = 1).

Til slutt la oss diskutere hvordan vokser funksjoner. For eksempel, e vokser raskere enn xk for alle α, k > 0. Dette betyr at eαx /xk blir større enn hverken som helst tall C > 0 hvis vi la x være stor nok. Vi skriver f (x) = O(g(x)) dersom f vokser ikke mye raskere enn g, dvs. f (x)/g(x) ≤ C for noen C > 0 og alle x (vannligvis er x > 0). αx

Eksempel 4.7. 1) bxc = O(x) og dxe = O(x). n n n P P P 2) i = O(n2 ), i2 = O(n3 ) og 2i = O(2n ). i=1

i=1

3) n! = O((αn)n ) for α >

1 e

i=1

= 0.367...

5. Algoritmer Definisjon 5.1. En algoritme er en sekvens av istruksjoner som kan utføres presist skritt for skritt. Hvert skritt er en veldefinert og enkelt matematisk operasjon. Antall skritt m˚ a være endelig uavhengig av

8

BORIS KRUGLIKOV

data som kommer som input i algoritmen og den sistenevnte m˚ a løse problemet som vi har foran oss og m˚ a gi korrekt output data. Bruksanvisninger og kokebokoppskrifter er eksempler p˚ a algoritmer. Her er algoritmer som er viktig for b˚ ade matematikk og informatikk. Eksempel 5.2. Gitt n heltall a1 , . . . , an finn det største tallet M blant dem og bestem indeks m til det maksimalle elementet. Her er algoritmen som løser dette problemet: 1) Sett M = a1 , m = 1. 2) Sammenlign M og a2 . Dersom M < a2 sett M ˚ a være nytt maksimum: M = a2 , m = 2. Ellers bytt ingenting. 3) Fortsett og sammenlign M med a3 osv. til vi har vært gjennom an . 4) Da har M verdien max{a1 , . . . , an } og m blir det (minste) nummer i slik at ai = M . En matematisk formel kan betraktes som en kortfattet m˚ ate ˚ a uttrykke noe som vi ogs˚ a kunne ha sagt p˚ a et vannlig spr˚ ak. En datamaskin m˚ a ha sine instruksjoner p˚ a et bestemt programmeringsspr˚ ak. Det finnes mange slik spr˚ ak, for eksempel Pascal, C++, Java osv. Det finnes ogs˚ a en mellomting som heter pseudokode. Den er lett ˚ a forst˚ a og kan oversettes til forskjellige programmeringsspr˚ ak. Eksempel 5.3. La oss skrive algoritmen for eksempelet ovenfor med pseudokoden. procedure max (a1 , . . . , an : integers) M := a1 , m := 1 for i = 2 to n do if M < ai then M := ai , m := i end do (M is the maximum element with the index m) Det er klart at antall skritt, dvs. kompleksitet til algoritmen, er O(n). Eksempel 5.4. La a1 , . . . , an være n forskellige heltall. Gitt et heltall x, bestem om x = am for ett m og i s˚ a fall finn indeksen m. Lineær søkealgoritme. Vi begynner med ˚ a sammenligne x og a1 , etterp˚ a x med a2 osv. procedure lin_search (x: integer; a1 , . . . , an : integers) i := 1 while (i ≤ n and x 6= ai ) do i := i + 1 end do if i ≤ n then m := i else m := 0 (m is the index corresponding to x, or 0 if x is not found)

NOTATER - DISKRET MAT. 2010

9

Kompleksitet til algoritmen er igjen O(n). Eksempel 5.5. La a1 , . . . , an være n forskellige heltall, som vi n˚ a antar ordnet i oppadstigende rekkefølge, nemlig a1 < · · · < an . Problemstillingen er som ovenfor. Binær søkealgoritme. Vi deler listen p˚ a midten og ser om x tilhører den venstre halvdelen eller den høyre. S˚ a tar vi den utvalgte delen og fortsetter. procedure binary_search (x: integer; a1 , . . . , an : increasing integers) i := 1, j := n while i < j do k := b i+j c 2 if x > ak then i := k + 1 else j := k end do if x = ai then m := i else m := 0 (m is the index corresponding to x, or 0 if x is not found) Kompleksitet til algoritmen er O(log n) som er mye bedre enn O(n) (log n ¿ c · n for hvert c > 0 n˚ ar n → +∞). Eksempel 5.6. Gitt forskjellige heltall a1 , . . . , an (n ≥ 2) trenges det ˚ a ordne dem i oppadstigende rekkefølge (slik problemet kan oppst˚ a n˚ ar man søker databaser med forskjellige karakteregenskap – navn, alder, telefonnumber osv). Boblesort algoritme. Vi begynner med ˚ a sammenligne a1 og a2 . Dersom a1 > a2 s˚ a bytter vi dem (dvs. vi bytter indeksene). Ellers blir a1 , a2 st˚ aende. N˚ a sammenligner vi a2 og a3 og gjør som foran. Vi fortsetter til an og f˚ ar den ˚ a bli maksimalt i mengden. S˚ a begynner vi igjen med a1 , . . . , an−1 og bytter som tidligere osv. procedure boblesort (a1 , . . . , an : reelle tall) for i = 1 to n − 1 do for j = 1 to n − i do if aj > aj+1 then x := aj , aj := aj+1 , aj+1 := x end do end do (a1 , . . . , an are in increasing order) Kompleksitet til algoritmen er O(n2 ). Stopproblemet. Finnes det en algoritme som kan avgjøre om et vilk˚ arlig dataprogram og input avslutter eller ikke? Ifølge et teorem av A.Turing det eksisterer ingen slik algoritme. Dete impliserer at en datamaskin ikke kan skrive programmer (av større kompleksitet enn maskinen sjøl) og m˚ a vi, mennesker, passe p˚ a algoritmer.

10

BORIS KRUGLIKOV

6. Heltall og divisjon Definisjon 6.1. La a, b ∈ Z, b 6= 0. Vi sier at a deler b (dvs. a er en divisor/faktor av b) dersom ∃c ∈ Z: b = ac. Vi skriver a|b. For eksempel 2|3, 2|0 og −1|1, men 36 | 4. Ogs˚ a ∀n ∈ Z+ : 1|n, n|n. a g˚ ar a|c. Teorem 6.2. (1) Dersom a|b og b|c, s˚ (2) Dersom a|b og a|c, s˚ a g˚ ar a|(mb + nc) ∀ m, n ∈ Z. Bevis.(1) b = aβ, c = bγ ⇒ c = a(βγ) dvs. a|c. (2) b = aβ, c = aγ ⇒ (mb + nc) = maβ + naγ = a(mβ + nγ) dvs. a|(mb + nc).

¤

Definisjon 6.3. Et heltall p ≥ 2 kalles for primtall dersom de eneste positive faktorene til p er 1 og p selv. Et heltall n ≥ 2, som ikke er et primtall, sies ˚ a være sammensatt. Eksempel 6.4. 2, 3, 5, 7, 11, 13, 17 er primtall og 4, 6, 8, 9, 10, 12, 14, 15, 16 er sammensatte. Teorem 6.5 (Entydig faktorisering av heltall). La n ≥ 2 være et heltall. Da kan n skrives entydig som et produkt av primtall: n = q1 · · · qt = pk11 · · · pks s

(q1 ≤ · · · ≤ qt prime) eller ekvivalent (p1 < · · · < ps prime, k1 , . . . , ks ∈ Z+ )

Beviset kommer senere. Eksempel 6.6. 100 = 2 · 2 · 5 · 5 = 22 52 , 625 = 54 , 5! = 23 · 3 · 5, 257 = 257, 9999 = 32 · 11 · 101. √ Teorem 6.7. Sammensatt heltallet n ≥ 2 har en primdivisor p ≤ n. √ Bevis. La n = ab med 1 < a ≤ b < n. √ Da har vi a ≤ n og hver primdivisor p til a tilfredstiller p ≤ a ≤ n. ¤ Dette gir algoritmen for ˚ a sjekke om tallet n er prim: Sjekk om 2|n, hvis ja – ferdig; ellers sjekk √ om 3|n, hvis ja – ferdig, etterp˚ a 5, 7, 11√osv. til det største primtallet ≤ n. Kompleksitet til algoritmen = O( n). Teorem 6.8. Det finnes uendelig mange primtall i Z. Bevis. Anta at det finnes bare endelige mange primtall p1 , . . . , pk . La n = p1 · · · pk + 1. Siden n > pi er tallet sammensatt og det har en primdivisor p|n. Siden p er blant pi , deler det p1 · · · pk . Da deler p ogs˚ a 1 = n − p1 · · · pk . Motsiegelse! ¤ Teorem 6.9 (Divisjonsalgoritmen). ∀ a ∈ Z, d ∈ Z+ ∃! q, r ∈ Z, 0 ≤ r < d: a = dq + r. Vi skriver r = a mod d.

NOTATER - DISKRET MAT. 2010

11

Bevis. Eksistens. Vi har q = b ad c, r = a − dq. Entydighet. Dersom a = dq1 + r1 = aq2 + r2 er to slik løsninger, da har vi d(q1 − q2 ) = r2 − r1 . Siden |r2 − r1 | < d og d|(r2 − r1 ) har vi r2 = r1 og derfor q1 = q2 . ¤ Definisjon 6.10. La a, b ∈ Z. Det største heltall d slik at d|a og d|b kalles for den største felles divisor til a, b [greatest common divisor]. Vi skriver d = gcd(a, b). Vi definerer gcd(0, 0) = 0. Dersom gcd(a, b) = 1, s˚ a sier vi at a og b er innbyrdes prime. Eksempel 6.11. gcd(3, 5) = 1, gcd(3, 15) = 3, gcd(21, 12) = 3, gcd(4!, 24 ) = 8, gcd(135, 0) = 135. Definisjon 6.12. La a, b ∈ Z. Det minste positive heltall g slik at a|g og b|g kalles for det minste felles multiplum til a, b [least common multiple]. Vi skriver g = lcm(a, b). Vi definerer lcm(0, n) = 0 ∀n ∈ Z. Med hensyn til entydigfaktoriseringsteoremet la oss ha (pi prime, ki , lj ∈ Z≥0 ): a = pk11 · · · pks s , b = pl11 · · · plss . Da har vi: min(k1 ,l1 )

gcd(a, b) = p1

max(k1 ,l1 )

s ,ls ) · · · pmin(k , lcm(a, b) = p1 s

s ,ls ) · · · pmax(k . s

Dette impliserer Teorem 6.13. For a, b ∈ Z har vi: ab = gcd(a, b) lcm(a, b). 7. Kongruensregning og Kriptografi I kongruensregning er vi bare interessert i restleddene til heltall etter ˚ a ha delt med et bestemt heltall m ≥ 2. Definisjon 7.1. Heltallene a, b er kongruent modulo m hvis m|(b − a), dvs. a mod m = b mod m. Vi skriver a ≡ b mod m. Eksempel 7.2. 21 ≡ 27 ≡ 0 mod 3. −4 ≡ 20 ≡ 2 mod 6. Teorem 7.3. Dersom a ≡ b mod m og c ≡ d mod m, da har vi a + c ≡ b + d mod m,

ac ≡ bd mod m.

Definisjon 7.4. Hashingfunksjon p˚ a mengde S er en (surjektiv) funksjon h : S → {0, 1, . . . , m − 1}. Man ofte bruker den følgende hashingfunksjonen (m ∈ Z, m > 1) h : Z+ → {0, . . . , m − 1},

h(x) = x mod m.

12

BORIS KRUGLIKOV

Eksempel 7.5. Funksjonen menneske i Norge7→ personnummer er en kodifikasjon (ikke hashingfunksjon). Den er injektiv med co-omr˚ ade {0, 1, . . . , m − 1} og m = 100 000 000 000. Funksjonen personnummer 7→ de fem siste sifrene er hashingfunksjon av type h(x) = x mod 100 000, og brukes ved arkivering av data. Man ogs˚ a bruker h(x) = (ax + b) mod m (a ∈ Z+ , b ∈ Z) som hashingfunksjon. Den kan brukes for ˚ a generere pseudotilfeldige tall . Vi velger noen x0 og definerer xn rekursivt ved ˚ a sette xn+1 = h(xn ). Eksempel 7.6. La m = 12, a = 7, b = −1, x0 = 2. Vi beregner: x1 = 1, x2 = 6, x3 = 5, x4 = 10, x5 = 9, x6 = 2, x7 = 1, x8 = 6, . . . NB: Funksjonen ovenfor, kalt lineær kongruens generator , er for enkel for ˚ a nærme seg til virkelige tilfeldige tall. Det finnes mer komplisert generatorer for sekvenser av pseudotilfeldige tall. Eksempel 7.7. Er det mulig ˚ a bruke funksjonen h(x) = 2x+b mod 30 for b = 2 eller b = 3 som generator for pseudotilfeldige tall? Nei, den er ikke injektiv. Ved b = 2 best˚ ar bildet til h av partall, og ved b = 3 best˚ ar det av oddetall (sekvensen xn blir klart ikke tilfeldig). Kriptografi best˚ ar av ˚ a kunne gjøre en tekst uleselig for uvedkommende. Vi tar en klartekst, krypterer den og f˚ ar en kryptotekst. Den kan vi dekryptere og f˚ a tilbake klarteksten. a norsk med m = 30 symEksempel 7.8. La oss kryptere teksten p˚ boler, hvor vi først krypterer bokstaver med tall fra 1 til 29 a b c d e f g h i j k l m n o p q 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 r s t u v w x y z æ ø ˚ a 18 19 20 21 22 23 24 25 26 27 28 29 (Caesar kode) og bruker 0 for mellomrom (dersom trenger vi andre skilletegn m˚ a m øke), og etterp˚ a bruker hashingfunksjonen h(x) = x+5 mod 30. For ˚ a dekryptere bruker vi inversfunksjonen h−1 (x) = x − 5 mod 30 og bytter nummere til bukstavene. norsk spr˚ ak likner p˚ a dansk 7→ 14.15.18.19.11.0.19.16.18.29.11.0.12.9.11.14.5.18.0.16.29.0.4.1.14.19.11 7→ 19.20.23.24.16.5.24.21.23.4.16.5.17.14.16.19.10.23.5.21.4.5.9.6.19.24.16 Den siste linja er krypterte teksten. Vi kan ogs˚ a ha output som sekvens av bokstaver: ... 7→ stwxpexuwdpeqnpsjweudeifsxp

NOTATER - DISKRET MAT. 2010

13

8. Tallteoretiske algoritmer La oss skrive n ∈ Z+ i det desimale tallsystemet (0 ≤ ai ≤ 9): n = ak ak−1 . . . a1 a0 = ak 10k + ak−1 10k−1 + · · · + a1 10 + a0 . Eksempel 8.1. 4321 = 4 · 103 + 3 · 102 + 2 · 10 + 1. Det brukes ogs˚ a andre tallsystemer, for exempel binære med grunntall b = 2 eller heksadesimale med grunntall b = 16. Teorem 8.2. La b > 1 være et heltall. Hvert n ∈ Z+ kan skrives entydig som n = (ak ak−1 . . . a1 a0 )b = ak bk + ak−1 bk−1 + · · · + a1 b + a0 , hvor k ≥ 0, 0 ≤ ai < b og ak 6= 0. Bevis. Divisjonsalgoritmen gir n = q0 b + a0 , 0 ≤ a0 < b, hvor q0 = bn/bc, a0 = n mod b. Vi fortsetter med q0 : q0 = q1 b + a1 , 0 ≤ a1 < b. Etterp˚ a tar vi q1 osv. til vi kommer til qk = 0. ¤ Eksempel 8.3. La b = 2. Ta n = 19. Vi bruker algoritmen ovenfor: 19 = 9 · 2 + 1, 9 = 4 · 2 + 1, 4=2·2 , 2=1·2 , 1 = 0 · 2 + 1,

q0 q1 q2 q3 q4

= 9, = 4, = 2, = 1, = 0,

a0 a1 a2 a3 a4

= 1. = 1. = 0. = 0. = 1.

Vi f˚ ar: 19 = 1 · 24 + 0 · 23 + 0 · 22 + 1 · 21 + 1 = (10011)2 . Vi vet fra skole hvordan ˚ a beregne a + b i desimale notasjoner. Addisjonsalgoritmen for andre tallsystemer er helt analog. Eksempel 8.4. ·· 7 = (111)2 +3 = (11)2 10 = (1010)2 Tilsvarende gjelder ogs˚ a multiplikasjon. Eksempel 8.5. 7 = ×5 =

(111)2 (101)2 111 + 111 35 = (100011)2

14

BORIS KRUGLIKOV

Neste studerer vi eksponensiering bn = b| ·{z · · }b . For ˚ a beregne dette n ganger

direkt m˚ a vi bruke n − 1 = O(n) multiplikasjoner. Vi beskriver n˚ a binære algoritmen, som er mye bedre i kompleksitet. Skriv n binært som (ak ak−1 . . . a1 a0 )2 . Vi f˚ ar: k +a k−1 +···+a 2+a 1 0 k−1 2

bn = b(ak ak−1 ...a1 a0 )2 = bak 2

k

k−1

= (b2 )ak (b2

)ak−1 · · · (b2 )a1 (b)a0 =

Y

i

b2 .

ai =1 k

k−1

S˚ a vi regner ut b, b2 , b4 = (b2 )2 , b8 = (b4 )2 , . . . , b2 = (b2 )2 og multipliserer de av dem som tilsvarer ai = 1 (ellers f˚ ar vi ai = 0 og 2i ai (b ) = 1). S˚ a blir det noe mellom k og 2k operasjoner, og siden k = blog2 nc er kompleksitetet lik O(log n). Denne algoritmen brukes veldig mye i kommersielle nettjenester for ˚ a beregne raskt bn mod m. N˚ a kommer vi til ˚ a finne gcd(a, b), den største felles divisor, uten ˚ a faktorisere tallene a, b. Teorem 8.6 (den euklidske algoritme). La a, b ∈ Z+ . Anta a ≥ b. Sett r0 = a, r1 = b. Gjenta anvendelser av divisjonsalgoritmen for ˚ a f˚ a sekvens ri fra ri−2 = qi−1 ri−1 + ri , i ≥ 2. Dermed er gcd(a, b) den siste rest rk som er positiv. Bevis. Sekvens av heltall {ri }i>0 er nedstigende (r1 > r2 > . . . ) og ikke negativ, derfor finnes det rk+1 = 0. S˚ a stopper algoritmen. Om a = qb + r har vi at d = gcd(a, b) = gcd(b, r). Dette er fordi d|a og d|b impliserer d|r = (a − qb). Og dersom d|b og d|r s˚ a m˚ a d|a ogs˚ a. N˚ a slutter vi at d = gcd(a, b) = gcd(r0 , r1 ) = gcd(r1 , r2 ) = · · · = gcd(rk , rk+1 ) = gcd(rk , 0) = rk . ¤ Definisjon 8.7. La a, b, n ∈ Z. Vi sier at n er en lineær kombinasjon av a og b dersom ∃ s, t ∈ Z slik at n = sa + tb. Som følger fra den euklidske algoritme kan gcd(a, b) skrives som en lineær kombinasjon av a og b. Den finnes ved˚ a bruke tilbake ligningener for ri . ar r0 = 231 og Eksempel 8.8. La a = 231, b = 120. Vi f˚ 231 120 111 9

= = = =

1 · 120 + 111, 1 · 111 + 9, 12 · 9 + 3, 3 · 3,

r1 r2 r3 r4

= 120, r2 = 111, = 111, r3 = 9, = 9, r4 = 3, = 3, r5 = 0.

NOTATER - DISKRET MAT. 2010

15

Derfor er gcd(231, 120) = 3 (legg merke til at vi slapp ˚ a faktorisere 3 231 = 3 · 7 · 11 og 120 = 2 · 3 · 5). For ˚ a skrive dette som en lineær kombinasjon av a og b, beregner vi fra ligningene ovenfor: r2 = 111 = a − b, r3 = 9 = b − r2 = b − (a − b) = 2b − a, r4 = 3 = r2 − 12r3 = (a − b) − 12(2b − a) = 13a − 25b. S˚ a slutter vi at 3 = 13 · 231 − 25 · 120 eller gcd(a, b) = 13a − 25b. Teorem 8.9. La a, b, c ∈ Z+ og gcd(a, b) = 1. (i) Hvis a|bc, da m˚ a a|c. (ii) Hvis a|c og b|c, da m˚ a ab|c. Bevis. (i) Siden gcd(a, b) = 1 f˚ ar vi: ∃ s, t ∈ Z slik at sa+tb = 1. Gang med c og f˚ a sac + tbc = c. N˚ a a|sac og a|tbc ⇒ a|c. (ii) Lignende. ¤ Korollar 8.10. Anta at p er et primtall og p|a1 a2 · · · an . Da m˚ a p|ai for noen i. For eksempel (p−1)! = 1·2 · · · (p−1) har ingen faktor p, s˚ a p 6 |(p−1)! og gcd(p, (p − 1)!) = 1. Dette f˚ ar vi bruk for senere. Definisjon 8.11. La a, b, m ∈ Z, a > 0, m > 1. En lineær kongruens er ligningen ax ≡ b mod m, hvor x ∈ Zm = Z mod m er ukjent. Definisjon 8.12. La m ∈ Z, m > 1. Et heltall a ¯ sies ˚ a være invers til tallet a ∈ Z modulo m dersom a¯ a ≡ 1 mod m. ¯ modulo m hvis og bare hvis Teorem 8.13. Heltallet a har invers a gcd(a, m) = 1, og i s˚ a fall er a ¯ entydig i Zm (dvs. om det finnes en annen løsning a ¯0 m˚ a vi ha a ¯0 ≡ a ¯ mod m). Bevis. Eksistens. Anta at a har en invers a ¯, a¯ a ≡ 1 mod m. Da har vi: m|(a¯ a −1), dvs. a¯ a −1 = cm. Om d|a og d|m f˚ ar vi at d|1 = a¯ a −cm. Da er d = ±1, dvs. gcd(a, m) = 1. Anta n˚ a at gcd(a, m) = 1. Da ∃ s, t ∈ Z slik at sa + tm = 1. Da er sa ≡ 1 mod m, dvs. a ¯ = s mod m er en invers til a. Entydighet. Anta a¯ a ≡ 1 mod m, a¯ a0 ≡ 1 mod m. Derfor er a¯ a− a¯ a0 ≡ 0 mod m, dvs. m|a(¯ a−a ¯0 ). Fra Teorem 8.9 f˚ ar vi m|(¯ a−a ¯0 ), 0 dvs. a ¯≡a ¯ mod m. ¤ Eksempel 8.14. Fra Eksempel 8.8 finner vi med deling med 3 at gcd(77, 40) = 1. Den euklidske algoritmen der gir oss lineær kombinasjon 13 · 77 − 25 · 40 = 1. S˚ a er 77−1 ≡ 13 mod 40 eller (siden 77 ≡ 37 mod 40) har vi 37−1 ≡ 13 mod 40. P˚ a lignende m˚ ate er 40−1 ≡ −25 ≡ 52 mod 77.

16

BORIS KRUGLIKOV

Teorem 8.13 impliserer at den lineære kongruensen ax ≡ b mod m (med gcd(a, b) = 1) har løsningen x ≡ a ¯b mod m. Eksempel 8.15. Siden 45 ≡ 1 mod 11 er 9−1 ≡ 5 mod 11. Derfor har kongruensen 9x ≡ 3 mod 11 løsningen x = 5 · 3 mod 11 = 4. Vi kan ha flere lineære kongruenser. Teorem 8.16 (kinesisk restteorem). La m1 , . . . , mk være parvis innbyrdes prime heltall ≥ 2. Systemet x ≡ a1 mod m1 .. . x ≡ ak mod mk har en entydig løsning modulo m = m1 · · · mk . Bevis. Eksistens. La Mi = m/mi = m1 · · · mi−1 m ˇ i mi+1 · · · mk (m ˇi betyr fravær av mi ). Siden gcd(mi , Mi ) = 1 finnes det inversen Mi yi ≡ 1 mod mi . La oss sjekke at x=

k X

as Ms ys

s=1

er en løsning. Regn modulo mi : x ≡ a1 M1 y1 + · · · + ai Mi yi + · · · + ak Mk yk ≡ a1 0y1 + · · · + ai Mi yi + · · · + ak 0yk ≡ ai Mi yi ≡ ai mod mi . Entydighet. Dersom x0 er en annen løsning, s˚ a er (x − x0 ) ≡ 0 mod mi , 0 0 dvs. mi |(x − x ) og derfor m1 · · · mk |(x − x ), dvs. x ≡ x0 mod m. ¤ Eksempel 8.17. La oss løse systemet av lineære kongruenser x ≡ 2 mod 3,

x ≡ 3 mod 5,

x ≡ 5 mod 7.

Vi har: m1 = 3, m2 = 5, m3 = 7, m = 3 · 5 · 7 = 105 og M1 = 35, M2 = 21, M3 = 15, y1 = 2, y2 = 1, y3 = 1. Dermed er x = 2 · 35 · 2 + 3 · 21 · 1 + 5 · 15 · 1 = 278 ≡ 68 mod 105. Eksempel 8.18. Systemet x ≡ 1 mod 2,

x ≡ 6 mod 10

har ingen løsning fordi den første lingningen betyr at x er odd, mens den annen betyr at x har 6 som det siste siffer i det desimale tallsystemet. Grunnen til feil er at 2 og 10 ikke er innbyrdes prime: gcd(2, 10) = 2.

NOTATER - DISKRET MAT. 2010

17

NB: Det kinesiske restteorem sier at dersom m = m1 · · · mk (med mi parvis inbyrdes prime), da kan alle a, 0 ≤ a < m, representeres entydig ved (a mod m1 , . . . , a mod mk ) og vi kan regne med slike sekvenser av mindre heltall istenenfor a, f.eks. ¡ ¢ a · b = (a mod m1 ) · (b mod m1 ), . . . , (a mod mk ) · (b mod mk ) forutsatt at 0 ≤ ab < m. Dette reduserer kompleksitet. Teorem 8.19 (Fermats lille teorem). La p være et primtall. Hvis p 6 |a, s˚ a er ap−1 ≡ 1 mod p. For alle a ∈ Z gjelder ap ≡ a mod p. Bevis. La oss anta først at p 6 |a. Mengden {a, 2a, . . . , (p − 1)a} best˚ ar av parvis ikke-kongruent elementer modulo p, fordi sa ≡ ta mod p, 1 ≤ s < t < p impliserer p|a(t − s) og dette gir p|(t − s) som er umulig. Derfor restklasser av elementene fra mengden {a, 2a, . . . , (p − 1)a} i Zp = Z mod p er lik elementene {1, 2, . . . , p − 1}. S˚ a f˚ ar vi a · 2a · · · (p − 1)a = (p − 1)!ap−1 ≡ (p − 1)! mod p, dvs. p|(ap−1 −1)(p−1)!. Siden gcd(p, (p−1)!) = 1 f˚ ar vi at p|(ap−1 −1), dvs. ap−1 ≡ 1 mod p. Ganger vi dette med a, s˚ a f˚ ar vi ap ≡ a mod p, noe som gjelder for alle heltall a. ¤ Eksempel 8.20. 34 = 81 ≡ 1 mod 5 fordi p = 5 er prim. Eksempel 8.21. 25 = 32 ≡ 2 mod 6 som ikke er 1 og p = 6 = 2 · 3 er sammensatt. Eksempel 8.22. 2340 ≡ 1 mod 341 til og med p = 341 = 11 · 31 er sammensatt. Definisjon 8.23. Heltallet n ≥ 2 er pseudoprim med hensyn til grunntallet a dersom an−1 ≡ 1 mod n. 9. Offentlig nøkkel og RSA kryptografi Vi bruker kredittkort for ˚ a handle i nettbutikk. Uvedkommende kan lytte p˚ a tr˚ aden og stjele data vi sender. Men de kan ikke snappe kredittkortnummer fordi det er kriptert. Hvordan gjøres dette? I tradisjonelle krypteringsmetoder m˚ a sender og mottaker ha en felles hemmelig nøkkel. Da kan de kryptere of sende informasjon, og dekryptere den ved mottagelse. Begge to har den samme private nøkklen og dette kalles for symmeriske kryptosystem. Ved handling p˚ a internet er slik scenario ikke mulig. Vi m˚ a ha en m˚ ate til ˚ a sende b˚ ade informasjon og nøkkelen i en melding som uvedkommende ikke kan lese. Dette gjøres ved hjelp av den (asymmetriske)

18

BORIS KRUGLIKOV

offentlige nøkkelen som best˚ ar av en generell og ˚ apen regel, som alle vet, og en hemmelig nøkkel, som er kjent bare til mottaker. S˚ a først sender mottakeren en del av data til senderen, som krypterer og sender informasjon tilbake. Den er umulig ˚ a dekriptere uten ˚ a vite hele data, slik at bare mottakeren kan lese meldingen. Den hemmelige nøkkelen kan regnes ut hvis man vet faktoriseringen, som er en del av hemmelige data. En av mest utbredte slike algoritmer er RSA (= Rivest-Adleman-Shamir) kryptosystemet. Velg to store forskjellige primtall p og q. La n = p q. Velg et positivt heltall e slik at gcd(e, (p − 1)(q − 1)) = 1. Da eksisterer en invers d til e modulo (p − 1)(q − 1), dvs. de = 1 + k(p − 1)(q − 1) for et k ∈ Z. La 0 < M < n være et heltall slik at p 6 |M , q 6 |M . Lemma 9.1. M de ≡ M mod n. Bevis. Fermats lille teorem impliserer M p−1 ≡ 1 mod p, M q−1 ≡ 1 mod q. Dette gir oss M de = M 1+k(p−1)(q−1) = M (M p−1 )k(q−1) ≡ M mod p M de = M 1+k(p−1)(q−1) = M (M q−1 )k(p−1) ≡ M mod q. Kinesisk restteorem impliserer n˚ a M de ≡ M mod n. ¤ RSA-kryptosystemet fungerer som følger (vi tenker om ˚ a sende en sekvens av heltall; informasjon kan kodifiseres med f.eks. Caesar kode). Velg to primtall p, q med ca. 200 sifrer (dvs. ∼ 10200 ). Da har n ca. 400 sifrer. La n = p q og velg e, d som tidligere. Mottaker sender ˚ apent bare n og e og beholder p, q og d hemmelig. N˚ a senderen kan kryptere M med tallet C = M e mod n. Dette kan dekrypteres ved ˚ a beregne M = C d mod n. Uvedkommende kan ikke lese M fra C fordi de trenger ˚ a faktorisere n (for ˚ a finne d) og dette er en veldig tidkrevende operasjon – det tar mange millioner ˚ ar for ˚ a regne ut p, q. Dette gir sikkerkhet for informasjon. 10. Matematisk induksjon Matematisk induksjon virker som følger. Betrakt en p˚ astand P (n), hvor n ∈ N er et naturlig tall (her er N mengden {1, 2, 3, . . . } eller {0, 1, 2, . . . }). Anta at utsagnene P (1) og P (n) ⇒ P (n + 1) er sanne. Da er utsagnet P (n) ∀n ∈ N sant. For ˚ a bevise dette la S = {n ∈ N | P (n)}. Vi har at 1 ∈ S og n ∈ S ⇒ n + 1 ∈ S. Dersom S 6= N, finnes det det minimale naturlige tall k 6∈ S. Vi har k 6= 1, s˚ a er n = k − 1 ∈ N og n ∈ S siden k var minimal. Men da er k = n + 1 ∈ S. Motsiegelse!

NOTATER - DISKRET MAT. 2010

19

Eksempel 10.1. La oss bevise n X

i = 1 + 2 + ··· + n =

i=1

n(n + 1) . 2

Kall p˚ astanden for P (n). P (1): 1 = 1·2 = 1. Ok. 2 Pn+1 Pn Anta P (n). Vi har: i = 1 + 2 + · · · + n + (n + 1) = i=1 i=1 i + n(n+1) (n+1)(n+2) (n + 1) = 2 + (n + 1) = . Dette er P (n + 1). Ferdig! 2 P Eksempel 10.2. La oss finne formelen for ni=1 i2 = 1+4+9+· · ·+n2 . Vi h˚ aper at resultat er en kubisk polynom av n, dvs. an3 +bn2 +cn+d. Vi kan gjette koeffisienter a, b, c, d: n=1: n=2: n=3: n=4:

1 = a + b + c + d, 5 = 1 + 4 = 8a + 4b + 2c + d, 14 = 1 + 4 + 9 = 27a + 9b + 3c + d, 30 = 1 + 4 + 9 + 16 = 64a + 16b + 4c + d.

Ved ˚ a løse dette finner vi a = 13 , b = 12 , c = 61 , d = 0. N˚ a er gjetting s˚ ann: n X n3 n2 n n(n + 1)(2n + 1) i2 = + + = . 3 2 6 6 i=1 For ˚ a bevise dette kall p˚ astanden for P (n). P (1): 1 = 1·2·3 = 1. Ok. 6 Pn+1 2 Pn 2 n(n+1)(2n+1) 2 Anta P (n). Vi har: + i=1 i = i=1 i + (n + 1) = 6 (n+1)(n+2)(2n+3) 2 . Dette er P (n + 1). Ferdig! (n + 1) = 6 Eksempel 10.3. La oss beregne summen av de første positive odde heltall. 1=1 1+3=4 1+3+5=9 1 + 3 + 5 + 7 = 16 1 + 3 + 5 + 7 + 9 = 25. Ut fra dette er det rimelig ˚ a gjette at n X (2i − 1) = 1 + 3 + 5 + · · · + (2n − 1) = n2 . i=1

For ˚ a bevise dette kall p˚ astanden for P (n).

20

BORIS KRUGLIKOV

P (1): 2 · 1 − 1 = 1 = 12 . Ok. N˚ a anta P (n). Vi har: n+1 n X X (2i − 1) = (2i − 1) + (2(n + 1) − 1) = n2 + 2n + 1 = (n + 1)2 . i=1

i=1

Dette er P (n + 1). Ferdig! Bemerkning 10.4. La p˚ astanden Q(n) være at summen i eksempel 10.3 er lik n2 + π. Da viser den siste regning at Q(n) ⇒ Q(n + 1). Dette er F → F sant utsagn. Men vi kan ikke slutte at Q(n)∀n ∈ N (det er galt: heltall = uheltall). Grunnen er at utsagnet Q(1) er usant. Eksempel 10.5. La oss bevise P (n): 2n > n2 . P˚ astanden er sant for n = 0, 1, men usant for n = 2, 3, 4. La oss begynne da med n = 5. P (5): 25 = 32 > 52 = 25. Ok. Anta P (n) for n ≥ 5. Da har vi: 2n+1 = 2 · 2n > 2n2 > n2 + 2n + 1 = (n + 1)2 fordi n > 3 > 2 + n1 (⇔ n2 > 2n + 1) for n ≥ 5, dvs. vi fikk P (n + 1). S˚ a slutter vi P (n)∀n ≥ 5. 11. Prinsipper av telling Kombinatorikk behandler problemmer knyttet til ˚ a telle, arangere eller kombinere ting. Vi skal studere noen regler av telling som brukes i kombinatorikk. Produktregel. La oss utføre en sekvens av r oppgaver. Anta at det finnes n1 m˚ ater for ˚ a utføre oppgave 1, n2 m˚ ater for ˚ a utføre oppgave 2, . . . , nr m˚ ater for ˚ a utføre oppgave r. Da er det akkurat n1 n2 · · · nr m˚ ater for utføre hele sekvens av oppgaver. Med notasjoner fra mengdelære skriver vi dette s˚ ann: |A1 × · · · × Ar | = |A1 | · |A2 | · · · |Ar |. Eksempel 11.1. Beregn antall av passord med lengde 3 og type BT X, hvor B er en norsk bokstav, T et heltall mellom 0 og 9, og X er enten en bokstav eller et slik tall. Det finnes 29 m˚ ater ˚ a velge B, 10 m˚ ater ˚ a velge T og 29 + 10 = 39 m˚ ater ˚ a velge X. Derfor er antall av passord lik 29 · 10 · 39 = 11 310. Eksempel 11.2. La A være en endelig mengde med kardinalitet n = |A|. Vi skal bevise at potensmengde (mengde av alle delmengder) har kardinalitet |P (A)| = 2n . La oss skrive A som en sekvens {a1 , a2 , . . . , an }. En delmengde B ⊂ A best˚ ar av noen elementer ai . For a1 er det 2 muligheter – enten a1 ∈ B eller a1 6∈ B. Likes˚ a finnes det 2 muligheter for a2 osv. Antall muligheter for a1 , a2 , . . . , an er 2 · 2 · · · 2 = 2n .

NOTATER - DISKRET MAT. 2010

21

Eksempel 11.3. La A, B være to endelig mengder med |A| = n og |B| = m. Beregn antall N av funksjoner f : A → B. Dersom A = {a1 , a2 , . . . , an } finnnes det m muligheter for f (a1 ) ∈ B, n m muligheter for f (a2 ) ∈ B osv. Antall er N = m | · m{z· · · m} = m . n ganger

Vi kan bruke produktregelen for mer komplisert eksempler. Eksempel 11.4. Beregn antall N av injektive funksjoner f : A → B. Dersom n > m, s˚ a er N = 0 fordi det finnes ingen injektiv funksjon (se eksempel 13.2 litt senere). For n ≤ m kan a1 havne p˚ a ett av de m elementene i B, a2 p˚ a ett av de (m − 1) elementene B \ {f (a1 )}, a3 p˚ a ett av de (m − 2) elementene B \ {f (a1 ), f (a2 )} osv. Antall av injektive funksjoner er dermed N = m · (m − 1) · · · (m − n + 1). Dette er lik P (m, n) =

m! m · (m − 1) · · · (m − n + 1)(m − n) · · · 1 = (m − n)! (m − n) · (m − n − 1) · · · 1 = m · (m − 1) · · · (m − n + 1).

Eksempel 11.5. Antall N av surjektive funksjoner er enda mer komplisert. Klart vi har N = 0 for n < m. Ellers (n ≥ m) f˚ ar vi N = 1 for m = 1, N = 2n − 2 for m = 2, n n N = 3 − 3 · 2 + 3 for m = 3 og generelt µ ¶ m X k m (m − k)n (−1) N= k k=0 = mn − m · (m − 1)n + m(m−1) (m − 2)n − m(m−1)(m−2) (m − 3)n + . . . , 2 6 ¡ ¢ hvor m = k!1 P (m, k) er binomiale koeffisienter (kommer snart). k 12. Inklusjon-eksklusjonprinsippet Sumregel. Anta at oppgaven kan gjøres i n1 m˚ ater eller i n2 m˚ ater og at ingen m˚ ate fra den første gruppe hører til den annen gruppe. Da finnes det akkurat n1 + n2 m˚ ater for ˚ a gjøre oppgaven. Om det finnes n1 , . . . , nr m˚ ater, er totalt antall lik n1 + · · · + nr . Med notasjoner fra mengdelære skriver vi dette s˚ ann: |A1 ∪ · · · ∪ Ar | = |A1 | + |A2 | + · · · + |Ar |,

dersom Ai ∩ Aj = ∅ ∀i 6= j.

Eksempel 12.1. Medlem av instituttstyre kan være en ansatt, en postdoktor eller en student. Det finnes 20 ansatter, 5 postdoktorer og 25 studenter ved instituttet. Derfor finnes det 20 + 5 + 25 = 50 kandidater til instituttstyre.

22

BORIS KRUGLIKOV

En bedre teknikk for ˚ a løse telleproblemmer er inklusjon-eksklusjon som vi først beskriver for r = 2 mengder: |A1 ∪ A2 | = |A1 | + |A2 | − |A1 ∩ A2 |. Eksempel 12.2. Anta at det er 80 studenter p˚ a kurset MAT-1001 (mengde A1 ), 50 studenter p˚ a kurset MAT-1005 (A2 ) og at 30 tar begge kursene. Antall studenter som tar enten MAT-1001 eller MAT-1005 er |A1 ∪ A2 | = |A1 | + |A2 | − |A1 ∩ A2 | = 80 + 50 − 30 = 100. Eksempel 12.3. Beregn antall N av bitstrenger av lengde 6 som enten ikke begynner med 0 eller slutter med 00. La A1 være mengden av bitstrenger som ikke begynner med 0 ⇔ begynner med 1. Vi har |A1 | = 25 fordi uspesifiserte elementene i slike bitstrenger 1xxxxx form en bitstreng av lengde 5. La A2 = {xxxx00} være mengden av bitstrenger som slutter med 00. Vi har |A2 | = 24 . A1 ∩ A2 best˚ ar av bitstrenger som begynner med 1 og slutter med 00. Det finnes 3 uspesifisert bit, derfor er |A1 ∩ A2 | = 23 . S˚ a slutter vi: N = 25 + 24 − 23 = 32 + 16 − 8 = 40. Det generelle inklusjon-eksklusjonprinsippet er det følgende X X |A1 ∪ A2 ∪ · · · ∪ Ar | = |Ai | − |Ai ∩ Aj | +

X

1≤i≤r

1≤i 2000 ansatte (bortsett fra administrasjon) e = 334 ansatte. og 6 fakulteter. Derfor m˚ a minst ´en fakultet ha ≥ d 2000 6 Eksempel 13.5. En butikk selger blomster av m forskjellige typer. Hvor mange blomster m˚ a det være totalt, slik at det finnes sikkert k blomster som har like typen? n Dette tallet er n = (k − 1)m + 1 fordi d m e = dk − 1 + m1 e = k og dette n kan ikke reduseres: n − 1 = (k − 1)m blomster kan være en samling av (k − 1) like blomster for hver av m typer. Eksempel 13.6. Hvor mange bokstaver m˚ a man lese i en (uspesifisiert) norske tekst for ˚ a sikre at ´en av dem gjentas minst 11 ganger? Som i eksempel 13.5 har vi m = 29, k = 11, s˚ a er det minimalle tallet lik n = (11 − 1) · 29 + 1 = 291. 14. Permutasjoner og kombinasjoner Definisjon 14.1. La S være en endelig mengde. En permutasjon av S er en bijeksjon av S med seg selv. La oss nummerere S = {a1 , . . . , an }; vi kan ogs˚ a skrive i istedet for ai . Da er permutasjon ¡ 1 2 ... σn :¢ S → S lik en funksjon i 7→ σ(i) som vi skriver s˚ ann: σ(1)σ(2) . ... σ(n)

24

BORIS KRUGLIKOV

¡123¢ Eksempel 14.2. Permutasjonen ¡123¢ 213 er transposisjon 1 ↔ 2 (3 er urørelig) og permutasjonen 231 er syklus 1 → 2 → 3 → 1. Det finnes n muligheter for σ(1), (n − 1) muligheter for σ(2) (alle bortsett fra σ(1)), (n−2) muligheter for σ(3) (alle bortsett fra σ(1), σ(2)) osv. Antall permutasjoner er derfor lik n · (n − 1) · (n − 2) · · · 2 · 1 = n! Definisjon 14.3. r-permutasjonen er et ordnet utvalg ev r ≤ n elementer fra mengde S med |S| = n. Vi kan anse r-permutasjon som en injektiv funksjon σ : {1, . . . , r} → S. Det finnes n muligheter for σ(1), (n − 1) muligheter for σ(2), . . . , (n − r + 1) muligheter for σ(r). Antall r-permutasjoner er derfor lik n! P (n, r) = n · (n − 1) · (n − 2) · · · (n − r + 1) = . (n − r)! Eksempel 14.4. Beregn antall av alle mulige (3 første) medaljeliste i MidnatSol Maraton med 500 deltakere. Dette er ˚ a beregne 3-permutasjoner med 1=gull, 2=sølv, 3=bronse. Antall er P (500, 3) = 500 · 499 · 488 = 124 251 000. Definisjon 14.5. r-kombinasjonen er et uordnet utvalg ev r ≤ n elementer fra mengde S med |S| = n. Med andre ord er r-kombinasjonen en delmengde i S av kardinalitet r. Siden det eksisterer presis r! m˚ ater ˚ a nummerere en delmengde i S er antall av r-kombinasjoner lik P (n, r) n · (n − 1) · · · (n − r + 1) n! C(n, r) = = = . r! r · (r − 1) · · · 1 r!(n − r)! Eksempel 14.6. Beregn antall av mulige (uordnete) par fra en mengde med n elementer. Dette er lik n! n(n − 1) C(n, 2) = = . 2!(n − 2)! 2 Eksempel 14.7. Beregn antall muligheter ˚ a velge 6 kort fra kortstokk med 36 spillekort. Detter er lik 36! 36 · 35 · 34 · 33 · 32 · 31 = 6!30! 6·5·4·3·2·1 6 6 · 6· 6 5 · 7· 6 2 · 17· 6 3 · 11· 6 4 · 8 · 31 = 6 · 7 · 17 · 11 · 8 · 31 = 6 6· 6 5· 6 4· 6 3· 6 2 · 1 = 24 · 3 · 7 · 11 · 17 · 31 = 1 947 792.

P (36, 6) =

NOTATER - DISKRET MAT. 2010

25

Teorem 14.8. C(n, r) = C(n, n − r). Analytisk bevis. Vi har: C(n, r) =

n! n! = = C(n, n − r). r!(n − r)! (n − r)!r!

Kombinatorisk bevis. Utvalg av delmengde A ⊂ S med kardinaliteten |A| = r er ekvivalent til utvalg av komplementet Ac ⊂ S med kardinaliteten |Ac | = n − r. ¤ NB: Husk at 0! = 1 slik at C(n, 0) = C(n, n) = 1, som er klart ogs˚ a fra kombinatoriske betydning som kombinasjoner.

15. Binomialformelen I binomiale formlene er binomialkoeffisientene skrives s˚ ann: µ ¶ n n! . = C(n, r) = r!(n − r)! r ¡ ¢ Vi definerer ogs˚ a nr = 0 dersom r < 0 eller r > n. Teorem 15.1 (Pascals identitet). La n ≥ k > 0. Da gjelder: ¶ ¶ µ ¶ µ µ n+1 n n . = + k k k−1 Bevis. µ ¶ µ ¶ n n n! n! + = + k−1 k (k − 1)!(n − k + 1)! k!(n − k)! n! n! + (k − 1)! (n − k)! (n − k + 1) (k − 1)! k (n − k)! n!(n + 1) n! (k + (n − k + 1))) = = (k − 1)! k (n − k)! (n − k + 1) k!(n − k + 1)! µ ¶ (n + 1)! n+1 = = . k k!(n + 1 − k)!

¤

S˚ a n˚ a kan vi beregne binomialkoeffisientene fra Pascals triangelen, hvor hvert element er summen av de to som stor oppover (vi tenker at tall utenfor triangelen er 0, men vi skriver ikke nuller).

26

BORIS KRUGLIKOV

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 . ... ... ... ... ... ... . Teorem 15.2 (Binomialteorem). n µ ¶ X n n−k k n x y (x + y) = k k=0 n(n − 1) n−2 2 n(n − 1) 2 n−2 x y +· · ·+ x y +n x y n−1 +y n . 2 2 P Bevis. Vi har (x+y)n = dk xn−k y k , hvor koeffisienten dk er lik antall muligheter for utvalg av n − k x’er fra liste av n elementer (mengde av gjentatt parantesser (x + y)). Dette betyr at µ ¶ n . ¤ dk = C(n, n − k) = C(n, k) = k ¡ ¢ P Korollar 15.3. For n ≥ 0 er nk=0 nk = 2n . = xn +n xn−1 y+

Bevis. Sett x = y = 1 i binomialteoremet. ¡ ¢ P Korollar 15.4. For n ≥ 0 er nk=0 (−1)k nk = 0.

¤

Bevis. Sett x = 1, y = −1 i binomialteoremet.

¤

Vi kan skriver binomialformlene fra Pascals trianglelen s˚ ann (x + y)2 = x + 2 x y + y 2 (x + y)3 = x3 + 3 x2 y + 3 x y 2 + y 3 (x + y)4 = x4 + 4 x3 y + 6 x2 y 2 + 4 x y 3 + y 4 (x + y)5 = x5 + 5 x4 y + 10 x3 y 2 + 10 x2 y 3 + 5 x y 4 + y 5 .

(x + y)6 = x6 + 6 x5 y + 15 x4 y + 20 x3 y 3 + 15 x2 y 4 + 6 x y 5 + y 6 ... ... ... ... ... ... ... ... ...

.

NOTATER - DISKRET MAT. 2010

27

16. Sannsynlighet Vi kan utføre et forsøk og se p˚ a utfallet. Mengden av alle mulige utfall kalles for utfallsrommet. En hendelse er en delmengde av utfallsrommet. Eksempel 16.1. Vi kaster en terning. Dette er et forsøk. Tallet som kommer fram p˚ a terningen er utfallet. S = {1, 2, 3, 4, 5, 6} er utfallsrommet. En delmengde E av S er en hendelse, f.eks. vi kan ta E = {1, 3, 5} ˚ a best˚ a av oddetall. Definisjon 16.2. Dersom S er en endelig utfallsrommet med like forventninger for alle utfall, er sannsynligheten for en henvendelse E ⊆ S |E| lik P (E) = . Slik disribusjon kalles for uniform sannsynlighet. |S| Eksempel 16.3. Vi kaster et (rettferdig:-) terning. Utfallet 1 har sannsynlighet lik 1/6 og det samme gjelder 2, 3, 4, 5 og 6. Sannsynligheten for at det kommer fram et oddetall er P (E) = 3/6 = 1/2. Eksempel 16.4. En person spiller lotteri (f.eks. Tipping) med 2 utfall: vinne eller tape (|S| = 2). Er det sant at sannsynlighet for ˚ a vinne er 1 1/2 (= 2 · 100 = 50%)? Nei, fordi sannsynligheten er ikke uniform. Eksempel 16.5. Vi kaster 2 terninger. Hva er sannsynlighet for hendelsen Ei at summen blir i, hvor i = 1, 2, 3 eller 7? Først finner vi utfallsrommet. Det første kast gir 6 muligheter, likes˚ a det neste. Dermed best˚ ar utfallsrommet S av 36 ordnete par (a, b) med 1 ≤ a, b ≤ 6. Hendelsen er Ei = {(a, b) | a + b = i}. i = 1. Det finnes ingen par som gir summen 1, dvs. E1 = ∅, s˚ a er P (E1 ) = 0. i = 2. Det finnes akkurat ett par (1, 1) som gir summen 2, s˚ a er P (E2 ) = 1/36. i = 3. Det finnes 2 par med summen 3, E3 = {(1, 2), (2, 1)}, s˚ a sannsynligheten er P (E3 ) = 2/36 = 1/18. i = 7. Endelig 6 par har summen 7: (1, 6), (2, 5), (3, 4), (4, 3), (5, 3) og (6, 1) og disse utgjør hendelsen E7 , s˚ a er P (E7 ) = 6/36 = 1/6. Eksempel 16.6. Vi trekker 3 kuler fra en krukke med 10 kuler nummerert fra 0 til 9. Hva er sannsynlighet for ˚ a trekke kombinasjonen N (rekkefølgen teller), hvor N er lik 111, 504? Utfallsrommet er S = {n1 n2 n3 | 0 ≤ ni ≤ 9, ni 6= nj for i 6= j}. Det finnes |S| = 10 · 9 · 8 = 720 elementer i utfallsrommet, derfor er

28

BORIS KRUGLIKOV

sannsynligheten for hendelser lik P (N = 111) = 0

fordi 111 6∈ S,

P (N = 504) = 1/720

fordi 504 ∈ S.

Eksempel 16.7. Fortsett med Eksempel 16.6. La oss legge kuler tilbake etter hver trekning. Da er S = {n1 n2 n3 | 0 ≤ ni ≤ 9} med kardinalitet lik |S| = 10 · 10 · 10 = 1000. N˚ a er alle kombinasjoner mulige og har like forventinger. S˚ a har vi: P (N = 111) = P (N = 504) = 1/1000. P˚ astand 16.8. Dersom hendelser E1 og E2 er uavhengig, s˚ a har vi: P (E1 ∩ E2 ) = P (E1 ) · P (E2 ). ¤ Eksempel 16.9. Dersom vi legger kuler tilbake i krukken, er trekninger p˚ a alle skritt uavhengige. Derfor sannsynlighet for utfall 5 p˚ a skritt nr.1 er lik sannsynlighet for utfall 0 p˚ a skritt nr.2 og er lik sannsynlighet for utfall 4 p˚ a skritt nr.3. Dette impliserer 1 1 1 1 P (N = 504) = P (n1 = 5)P (n2 = 0)P (n3 = 4) = · · = , 10 10 10 1000 som vi beregnet i Eksempel 16.7. Eksempel 16.10. Vi trekker 3 kuler fra en krukke med 30 kuler som best˚ ar av 3 kuler med nummer 0 p˚ a, 3 kuler med nummer 1 p˚ a, . . . , 3 kuler med nummer 9 p˚ a (vi legger ikke kuler tilbake). Hva er sannsynlighet for ˚ a trekke kombinasjonen N , hvor N er lik 111, 504? Vi begynner med N = 111. Det finnes 3 kuler med nummer 1 p˚ a ute av 30, hvorfra P (n1 = 1) = 3/30. Dersom vi fikk 1 ved trekning 1, er det 2 kuler med nummer 1 p˚ a ute av 29, hvorfra1 P (n2 = 1 | n1 = 1) = 2/29. Etterp˚ a finnes det bare ´en kule med 1 p˚ a ute av 28, hvorfra P (n3 = 1 | n1 = 1, n2 = 1) = 1/28. Vi slutter at 3 2 1 1 · · = ≈ 0.00025. 30 29 28 4060 N˚ a fortsetter vi med N = 504. Det finnes 3 kuler med nummer 5 p˚ a ute av 30, hvorfra P (n1 = 5) = 3/30. Dersom vi fikk 5 ved trekning 1, er det 3 kuler med nummer 0 p˚ a ute av 29, hvorfra P (n2 = 5 | n1 = 0) = 3/29. Etterp˚ a finnes det 3 kuler med 4 p˚ a ute av 28, hvorfra P (n3 = 4 | n1 = 5, n2 = 0) = 3/28. Vi slutter at P (N = 111) =

P (N = 504) = 1Vi

9 3 3 3 · · = ≈ 0.0011. 30 29 28 8120

skriver P (hendelsen | betingelsen) for betinget sannsynlighet.

NOTATER - DISKRET MAT. 2010

29

P˚ astand 16.11. La E være en hendelse. Sannsynlighet for den kom¯ = 1 − P (E). plementærhendelsen E¯ = S \ E er P (E) ¤ Eksempel 16.12. Vi genererer en sekvens av n bit tilfeldig. Hva er sannsynligheten for at minst 2 bit er 0? Betegn henvendelsen med E. Da er E¯ henvendelsen at det finnes ingen eller bare ´en bit 0. Det betyr at bitsstreng er en av de følgende (n + 1) sekvenser: 111 . . . 11, 011 . . . 11, 101 . . . 11, 110 . . . 11, . . . , 111 . . . 10. Siden utfallsrommet best˚ ar av 2n elementer, er sannsynligheten lik n+1 ¯ P (E) = 1 − P (E) = 1 − 2n . P˚ astand 16.13. La E1 og E2 være to henvendelser i S. Da er P (E1 ∪ E2 ) = P (E1 ) + P (E2 ) − P (E1 ∩ E2 ). Bevis. Inklusjon-eksklusjonsprinsippet.

¤

Eksempel 16.14. Hva er sannsynlighet for at et tilfeldig heltall mellom 1 og 1000 er delige med 2, 3 eller 5? I eksempel 12.4 anvendet vi inklusjon-eksklusjonsprinsippet og fant at kardinaliteten for henvendelsen i oppgaven er |E| = 734. Vi slutter 734 at P (E) = 1000 = 0.734. 17. Rekurrens Definisjon 17.1. Rekurrensrelasjon av orden k er en ligning av type an = Fn (an−1 , . . . , an−k ), n ≥ k. Sekvens {an }n≥0 som oppfyller likningen kalles for en løsning til rekurrensrelasjonen. Eksempel 17.2. Rekurrensrelasjonen an = 2an−1 − an−2 har en løsnig an = 1. Sekvensen an = 5n er ogs˚ a en løsning: 5n = 2 · 5(n − 1) − 5(n − 2). Men sekvenser an = n2 og an = 2n er ikke løsninger fordi n2 6= 2(n − 1)2 − (n − 2)2 = n2 − 2,

2n 6= 2 · 2n−1 − 2n−2 = 2n − 2n−2 .

Definisjon 17.3. Initialbetingelsene er verdiene til de første k ledd a0 , . . . , ak−1 . De tillater ˚ a beregne ak , etterp˚ a ak+1 , etterp˚ a ak+2 osv. P˚ astand 17.4. Initialbetingelsene bestemmer løsningen til rekurrensrelasjonen entydig. ¤

30

BORIS KRUGLIKOV

Eksempel 17.5. Fibonacci-tall er gitt med rekurrensrelasjonen Fn = Fn−1 + Fn−2 og initialbetingelsene F1 = 1, F2 = 1. Vi beregner: F3 = 2, F4 = 3, F5 = 5, F6 = 8, F7 = 13, F8 = 21, F9 = 34, . . . Fibonacci-tallene er kjent i mange omr˚ ader. Her er eksempel av tesselering av planet med kvadrater, som har linjestykkene lik Fn : p

p

13 21 2

3

1 1

5 p

8 p

a en sparekonto til 10% rente, Eksempel 17.6. Vi setter 40 000 kr. p˚ som legges til ˚ arlig. Hvor mye har vi p˚ a konto etter 35 ˚ ar? La Pn være saldoen etter n ˚ ar. Vi har Pn = Pn−1 + 0.1 Pn−1 = 1.1 Pn−1 . Dette gir Pn = 1.1n P0 . Med P0 = 40 000 f˚ ar vi P35 = 1.135 40 000 ≈ 1 160 000 kr. Eksempel 17.7 (T˚ arn i Hanoi). Vi har 3 stolper og n sirkelskiver med forskjellig diameter stablet opp p˚ a hverandre p˚ a en stolpe ordnet etter størrelsen (den største nederst). Vi ønsker ˚ a flytte stabelen en skive ad gangen til en annen stolpe slik at skivene ogs˚ a er ordnet der og uten noen gang ˚ a ha en større skive p˚ a toppen av en mindre. Vi f˚ ar lov ˚ a bruke alle 3 stolpene. Vi beskriver en rekursiv algoritme for ˚ a løse dette som følger: Begynn med n skiver p˚ a den første stolpen. Flytt de (n − 1) øverste skivene til den tredje stolpen (rekurrens). S˚ a flytter vi den største som er blitt igjen p˚ a den første stolpen til stolpe nr.2. S˚ a flytter vi de (n−1) skivene fra stolpe nr.3 til stolpe nr.2 (igjen rekurrens). La Hn være antall flyttinger som kreves for n skiver. Vi har vist at Hn = 2Hn−1 + 1. Siden H1 = 1 beregner vi: H2 = 2 · 1 + 1 = 3, H3 = 2 · 3 + 1 = 7, osv. Generelt (induksjon) er Hn = 2n − 2.

NOTATER - DISKRET MAT. 2010

31

Eksempel 17.8. La an betegne antallet av bitstrenger av lengde n uten to p˚ afølgende 0-ere. Slike kan deles i to disjunkte mengder, nemlig de som slutter med 1 og de som slutter med 0. Den første delen tilsvarer bitstrengene av lengde (n − 1) uten to p˚ afølgende 0-ere, med 1 føyd til p˚ a slutten. Antallet av disse er an−1 . Den annen delen best˚ ar av dem som slutter med 0, og derfor m˚ a de ha 1 som (n − 1)-ste bit. De tilsvarer bitstrengene av lengde (n − 2) uten to p˚ afølgende 0-ere, med 10 føyd til p˚ a slutten. Antallet av disse er an−2 . Dermed f˚ ar vi rekurrensrelasjonen an = an−1 + an−2 . Siden a1 = 2 = F3 , a2 = 3 = F4 , s˚ a er sekvensen lik Fibonacci-tallene an = Fn+2 . Definisjon 17.9. En lineær homogen rekurrensrelasjon med konstante koeffisienter er gitt med likningen an = c1 an−1 + c2 an−2 + · · · + ck an−k

(†)

hvor ci ∈ R, ck 6= 0. Vi skriver LHHR for en slik. Eksempel 17.10. (1) Fn = Fn−1 + Fn−2 er en LHRR. (2) an = an−3 er en LHRR. (3) an = an−1 + a2n−2 er ikke lineær. (4) Hn = 2Hn−1 + 1 er ikke homogen. (5) Bn = n Bn−1 har ikke konstante koeffisienter. La oss prøve ˚ a finne en enkelt løsning til LHRR, f.eks. an = λn . Ved ˚ a sette dette inn i (†)n=k f˚ ar vi den karakteristiske ligningen λk = c1 λk−1 + c2 λk−2 + · · · + ck−1 λ + ck . Teorem 17.11. Anta at den karakteristiske ligningen har k forskjellige reelle røtter λ1 , . . . , λk . Da er den generlle løsningen til LHRR (†) slik an = z1 λn1 + z2 λn2 + · · · + zn λnn , der zi er reelle konstanter. Bevis. Vi ser bare p˚ a det enkle tilfelle k = 2. Det generelle tilfelle er lignende. La an = z1 λn1 + z2 λn2 . Dette er en løsning fordi ) −c2 λ1n−2 )+z2 (λn2 −c1 λ2n−1 −c2 λn−2 an −c1 an−1 −c2 an−2 = z1 (λn1 −c1 λn−1 2 1 = z1 λn−2 (λ21 − c1 λ1 − c2 ) + z2 λn−2 (λ22 − c1 λ2 − c2 ) = 0 + 0 = 0. 1 2 Vi skal tilfredstille n˚ a initialbetingelser som tilsvarer n = 0, 1: ½ z1 + z2 = a0 z1 λ1 + z2 λ2 = a1 .

32

BORIS KRUGLIKOV

Disse ligniner har de følgende løsninger (λ1 6= λ2 ): a1 − λ2 a0 Eq.2 − λ2 · Eq.1 : z1 = , λ1 − λ2 a1 − λ1 a0 Eq.2 − λ1 · Eq.1 : z2 = . λ2 − λ1 Siden initialbetingelsene a0 , a1 er vilk˚ arlige, er an den generelle løsningen, se P˚ astand 17.4. ¤ Eksempel 17.12. Finn løsningen til den LHRR an = an−1 + 2an−2 med initialbetingelsene a0 = 2, a1 = 7. Den karakteristiske ligningen er λ2 − λ − 2 = 0 og den har røtter λ1 = 2, λ2 = −1. Dermed er an = z1 2n + z2 (−1)n . Initialbetingelsene gir ½ z1 + z2 = 2 2z1 − z2 = 7. med (entydig) løsningen z1 = 3, z2 = −1. Til slutt, an = 3 · 2n − (−1)n . Eksempel 17.13. La oss finne lukket form for Fibonacci-tall Fn = Fn−1 + Fn−2 . Den karakteristiske ligningen er λ2 − λ − 1 = 0 √

og den har røtter λ1 = ϕ = 1+2 5 , λ2 = −1/ϕ = Fn = z1 ϕn + z2 (−1/ϕ)n . Initialbetingelsene er ½ z1 + z2 = F0 = 0 z1 ϕ − z2 /ϕ = F1 = 1.

√ 1− 5 . 2

Dermed er

√ med (entydig) løsningen z1 = −z2 = 1/(ϕ − 1/ϕ) = 1/ 5. Til slutt, √

√

( 1+2 5 )n − ( 1−2 5 )n √ Fn = . 5 La oss merke at siden |ϕ| > 1 og |1/ϕ| < 1 har vi Fn lim =ϕ n→∞ Fn−1 dvs. at forholdet mellom to p˚ afølgende Fibonacci-tall nærmer seg det gylne snitt tallet 1 ϕ=1+ ≈ 1.618. 1 1+ 1 1+ 1 1+ ...

NOTATER - DISKRET MAT. 2010

33

18. Relasjoner §8.1, 8.3, 8.5 fra boka. 19. Grafer - generell teori §9.1-9.4 fra boka. 20. Euler og Hamilton grafer §9.5-9.6 fra boka. 21. Planar grafer og farge tegning §9.8 med noen definisjoner og fakta fra §9.7. 22. Innføring til trær §10.1 og noe fra §10.2

For stoffet i seksjoner 18-22 se boka og notater av Loren Olson og Hugues Verdure.

23. Trær og anvendelser Definisjon 23.1. En urettet sammenhengende graf Γ = (V, E) uten sykler kalles for et tre (V er noder, E er kanter). Det er lett ˚ a sjekke at Γ er et tre hvis og bare hvis det finnes en entydig enkel veg mellom to gitt noder. En bestemt node r ∈ V kalles for rota. Den har niv˚ a (= minus høyde) 0. De nodene som har kant til r er sagt ˚ a være barn til r, og vi forstetter. Niv˚ aet k best˚ ar av alle noder som har forbindelse gjennom en kant med en node p˚ a niv˚ a k − 1, og som ikke tilhører niv˚ a k − 2. Hvis e = (xy) er en kant med noder x p˚ a niv˚ a k − 1 og y p˚ a niv˚ a k, s˚ a sier vi at y er et barn av x og x er forelderen til y. Høyden til Γ er den maksimale niv˚ aet blant alle nodene. En node uten barn kalles for et blad . Den ligger nederste i grenen fra rota r. Det finnes entydig forelder for alle noder bortsett fra rota. S˚ ann f˚ ar vi et rotfestet tre med rota r.

34

BORIS KRUGLIKOV

Teorem 23.2. Det gjelder for et tre Γ: |V | = |E| + 1. Bevis. Funksjon (kant mellom forelder og barn) 7→ (barn) er en bijeksjon mellom E og V \{r}. Derfor har mengdene lik antall elementer. ¤ For et rotfestet tre kan vi ordne nodene slik. Rota r f˚ ar adresse 0, og vi fortsetter med induksjon. Anta at vi har nummerert niv˚ a k − 1. Velg en node v p˚ a niv˚ a k − 1 med adresse a, og la oss nummere barn v1 , . . . , vi av v (de ligger p˚ a niv˚ a k). De f˚ ar adressene a.1, . . . , a.i. Dette er universelle adressesystem. Binær søketrær. Omvendt, gitt en ordnete mengde V med ordnete forskjellige elementer vi kan tegne dem som noder i et binær tre Γ (vi tenker at kanter fra en node kan g˚ a venstre og høyre). Det første elementet v1 ∈ V tas som rota r, og vi fortsetter med induksjon. For ˚ a plassere element vi , vi sammenlign den med r. Dersom vi < r g˚ ar vi via venstre kant, og dersom vi > r g˚ ar vi via høyre kant. Etterp˚ a sammenligner vi vi med det neste elementet x og fortsetter venstre eller høyre. Dersom vi kommer til et tomt plass, s˚ a plasserer vi vi der. Eksempel 23.3. Binær graf som tilsvarer sifre streng 527983461 er lik: ©© © 2n ¢¢

1n

AA

5n

HH H n 7

3n AA

4n

¢¢

6n

AA

9n

¢¢

8n

Avgjørelsetrær. Høyden h til Γ er den maksimale lengden fra rota til et blad. Dersom vi kan representere en avgjørelseprosess ved et rotfestet tre av høyde h, s˚ a vil vi alltid kunne treffe en avgjørelse etter h skritt. Eksempel 23.4. Anta gitt 8 mynter som ser identiske ut, men ´en av dem er falsk og er lettere enn de andre. Gitt en sk˚ alvekt, finn falskmynten. Betegn myntene 1, 2, . . . , 8. N˚ ar vi bruker sk˚ alvekt har vi enten like vekt p˚ a begge sider (da er ingen av myntene falske), eller ´en side er

NOTATER - DISKRET MAT. 2010

35

lettest (da er falskmynten der). Her er binært avgjørelsetre: 1234 ∨ 5678 » tXXX < > 56 ∨ 78 12 ∨ 34t» »»» X Xt

1 ∨ 2 t¡ 3 ∨ @ 4 t 5 ∨ 6 t¡ 7 ∨ @ 8 t ¢A ¢A ¢A ¢A A A A A ¢ Ai i ¢ A i ¢i A i ¢i Ai 1i 2 3 4 5 6 7 8

Med trenær avgjørelsetre kan vi ha avgjørelse i bare h = 2 skritt: 123 ∨ 678 » tXXX » » XXX > » » A A A ¢ A ¢¢ A ¢ 1i 2i 3i 4i 5i 6i 7i 8i

Prefikskoder. Anta at vi ønsker ˚ a overføre teksten til bitstrenger. En mulighet er ˚ a bruke Caeser chifferkode. Siden 25 > 29, bitstrenger av lengde 5 er nok til ˚ a kode alle norske bokstaver. Men bokstavene opptrer med forskjellige hyppighet, for eksampel ”e” og ”o” opptrer oftere enn ”c” og ”z”. Det blir lurt ˚ a representere de mest hyppige bokstavene med kortere sekvenser, fordi dette følger til de korteste signaler. Definisjon 23.5. En prefikskode er en endelig mengde med bitstrenger der ingen streng inng˚ ar som den første delen av en annen streng. Prefikskoder er bijektiv med blader av binært rotfestet trær, hvor hver venstre kant fra en node tilsvarer 0 og høyre kant tilsvarer 1 (vi skriver sekvens av 0- og 1-er for veien fra rota til bladet for koden). Her er eksempel: t ¡@ 1 @@t t¡¡ ¡ @ @ 1 0 1 ¡ @ @@t t¡ @t 01 0 ¡@ 1 0 ¡ ¡ @@t ¡ ¡ t ¡ t 000 001 110 0

Treet gir oss en algoritme for ˚ a dekode en overføring av signalene. For eksempel, la 01 = a, 000 = b, 001 = m, 110 = n. Bitstreng 0000111001110 kan deles entydig til tillate koder: 000|01|110|01|110 som betyr ”banan”.

36

BORIS KRUGLIKOV

Anta at hyppigheter til bokstaver er 0 < w1 ≤ w2 ≤ · · · ≤ wn (vi antar wi = pi · c hvor a finne bokstaven nummer Ppi er sannsynlighet for ˚ i i teksten og c = wi er totalvekten). La li være niv˚ aet til bladet som tilsvarer bokstaven nummer i. Vekten til koden (eller tilsvarende P treet) er W = wi li /c. Problemet: finn binært tre med n blad og en tilordning av vektene wi for noder, slik at vekten W til treet er minimal. Huffmans algoritme for ˚ a finne et optimalt tre. Anta at vi kan lage et omtimalt tre for n − 1 vekter. Gitt n vekter w1 ≤ · · · ≤ wn lag et optimalt tre T 0 for vekter w1 + w2 , w3 , . . . , wn og bytt noden for w1 + w2 med treet

w1©© t

t ©HH © H ©

HHw2 t

Det nye treet T er optimalt.

Eksempel 23.6. Betrakt vekter w1 = 1, w2 = 2, w3 = 4, w4 = 5, w5 = 6. Huffmans algoritmen fungerer slik. 1 At

2 Bt

t3 ¡@

4 Ct

5 Dt

6 Et

4 Ct

5 Dt

6 Et

@@t ¡ t¡ C ¡@ @@t t¡ A¡ B

5 Dt

6 Et

¡ t A¡

@ @t B

Skritt 0

Skritt 1

t7 ¡@

t7 ¡@

@ t t¡ ¡ @ C ¡@ @@t t¡ ¡ A B

t11 ¡@ ¡ @ t t ¡ @ D E

Skritt 2

Skritt 3

NOTATER - DISKRET MAT. 2010

t18 ©©HH

© t©© ¡@ @@t ¡ t¡ C ¡@ ¡ @ ¡ t @t A B

37

HH

Ht ¡@

t¡ D¡

@ t @ E

Skritt 4

Vi har de følgende optimale koder: A = 000, B = 001, C = 01, D = 10, E = 11. Vekten til koden er W = (3 · 1 + 3 · 2 + 2 · 4 + 2 · 5 + 2 · 6)/18 = 13/6. 24. Utspenningstrær Definisjon 24.1. La Γ = (V, E) være en enkel graf. Et utspenningstre T for Γ er en undergraf som er et tre og som inneholder samtlige noder V til Γ (i s˚ a fall er kanter til T en delmengde i E). Teorem 24.2. En enkel graf er sammenhengede hvis og bare hvis den har et utspenningstre. Bevis. Hvis T er et utspenningstre, da for arbitrære noder x, y ∈ V finnes det veien γ som forbindes dem i T , og s˚ a ogs˚ a i Γ. La Γ være sammenhengede og ikke et tre. Da finnes det en sykel ϑ. ˜ med de samme Ta ut en kant e = (xy) fra sykelen. Vi f˚ ar grafen Γ noder og antall kanter lik |E| − 1. Den er ogs˚ a sammenhengende fordi vi fjerner bare kanten mellom nodene x og y, som er forbinded gjennom ˜ er ikke et tre fortsett med algoritmen. sykelen ϑ likevel. Hvis Γ ¤ Det finnes to algoritmer for ˚ a finne et utspenningstre. Viddesøk. Ta en node – rota r. Tilsett alle kanter som g˚ ar ut fra den s˚ a lenge undergrafen T ⊂ Γ vi f˚ ar er et tre. Hvis samtlige noder fra Γ er ikke enn˚ a med i T , fortsett med neste noden x 6= r fra T , osv. Dybdesøk. Ta en node – rota r. Tilsett en kant (rx), etterp˚ a kant (xy) osv s˚ a lenge veien vi f˚ ar er ikke en sykel. Hvis det er umulig ˚ a tilsette kanter til veien, g˚ a noen skritt tilbake og tilsett veien til noden uten ˚ a forme en sykkel. Fortsett med dette. Eksempel 24.3. La oss anvende algoritmer for grafen t

t

ti @ @

¡ ¡

t

@ ¡ ¡ ¡ ¡ @ @¡ t¡ t

¡ ¡

t

t

38

BORIS KRUGLIKOV

Vi begynner med rota som er tegnet med dobbelt sirkel. Resultater av algoritmer er nedenfor: t

t

Dybdesøk ti t ¡ ¡ ¡ ¡ t¡ t

t

t

t

Viddesøk t t t i @ ¡ @ ¡ @ ¡ @ ¡ t t t @¡

t

Dybdesøk algoritmen kan ogs˚ a brukes for backtrack anvendelser, dvs. n˚ ar man løser problemet vilk˚ arlig og følger spor tilbake. Eksempel 24.4. La oss tegne grafen nedenfor med 3 farger (siden grafen har 3-noder sykel, er 2 farger ikke nok): r=rød, b=bl˚ a, g=grønn. 2 t ¡@

1t @

3 t

¡

¡

@

@ @

@

¡ @

t¡ 6

@

@t 4

@t 5

Tegneorden er 1-2-3-4-5-6. Vi begynner med 1=r, 2=b, 3=r, 4=g, 5=? Ikke nok farger. S˚ a vi trekker tilbake: 1=r, 2=b, 3=g, 4=r, 5=g, 6=g. Her er resultatet: r t @

b t ¡@

¡

¡

@

@ @

@

¡ @

t¡ g

g t

@t g

@

@t r

Minimalt utspenningstre. Anta at en enkel sammenhengende graf Γ = (V, E) har vektfunksjon P w : E → R+ . Vi vil finne et utspenningstre T slik at vekten w(T ) = e∈T w(e) er minimal. Prims algoritme. Velg en node v1 ∈ V og sett P = {v1 }, Q = ∅. Dersom etter noen skritt P = {v1 , . . . , vk }, Q = {e1 , . . . , ek−1 }, s˚ a ser vi p˚ a alle kanter som forbinder x ∈ P med y ∈ V −P . Blant disse velger vi en med minimal vekt og kaller den for ek+1 ; den er lik (vi vk+1 ) for noen i ≤ k. Sett P := P ∪ {vk+1 }, Q := Q ∪ {ek }. Dersom |P | < n = |V | fortsetter vi. Ellers er T = (V, Q) et minimalt utspenningstre. Legg merke til at p˚ a hvert skritt av algoritmen er (P, Q) et tre. Kruskals algoritme. Velg en kant e1 ∈ E med minimal vekt w(e1 ). Sett Q = {e1 }. Dersom etter noen skritt Q = {e1 , . . . , ek−1 }, s˚ a ser vi p˚ a alle kanter ek ∈ E − Q slik at e1 , . . . , ek danner en undergraf uten

NOTATER - DISKRET MAT. 2010

39

sykler (dvs. skog). Blant disse velger vi en med minimal vekt og setter Q := Q ∪ {ek }. Dersom k < n − 1 = |E| fortsetter vi. Ellers er T = (V, Q) et minimalt utspenningstre. Eksempel 24.5. Finn et minimalt utspenningstre for vektet grafen 4 t ©t ©H © © HH1 1© 2 4© © © HHt 2 © tH t© 4 H HH HH ©© © 4 H 3 H © 5 Ht H© t 5

Anta at vi bruker mest top og etterp˚ a venstre valg dersom vi har flere muligheter. Dette gir det følgende resultatet for b˚ ade Prims og Kruskals algoritmer. 4 t H ©t HH1 1©© 2 H t © t t H © HH HH 4HH 3HH Ht Ht

Vekten til minimalt utspenningstre er w(T ) = 15.

25. Boolsk algebra ar av en mengde Definisjon 25.1. Boolsk algebra (A, 0, 1,¯, +, ·) best˚ A, to spesielle elementer 0 og 1, en mono-operasjon ¯ og to binære operasjoner +, · med grunnsetninger: Boolske identiteter x + 0 = x, x · 1 = x x + x¯ = 1, x · x¯ = 0 x + y = y + x, x · y = y · x x + (y + z) = (x + y) + z, x · (y · z) = (x · y) · z (x + y) · z = (x · y) + (x · z), (x · y) + z = (x + z) · (y + z)

Navn p˚ a loven Indentitet Kompliment Kommutativitet Assosiativitet Distri-butivitet

Disse grunnlegende egenskaper impliserer de følgende:

40

BORIS KRUGLIKOV

Boolske identiteter Navn p˚ a loven x + x = x, x · x = x Idempotens x + 1 = 1, x · 0 = 0 Dominasjon x¯ = x Dobbeltnektelse (x + y) = x¯ · y¯, (x · y) = x¯ + y¯ de Morgan B˚ ade matematisk logikk (P = {utsagner}, F , T , ¬, ∨, ∧) og mengdelære (E, ∅, E, c , ∪, ∩) er boolske algebrær. Mest vannlig eksempel er B = {0, 1} med operasjoner ¯0 = 1, ¯1 = 0 og + 0 1 0 0 1 1 1 1

· 0 1 0 0 0 1 0 1

Rom av alle boolske funksjoner Fn = {f : B n → B} er ogs˚ a Boolsk algebra. Her B n = B × · · · × B = {(x , . . . , x ) : x = 0, 1}. 0 og 1 er 1 n i | {z } n

identiske konstanter, dvs. funksjoner som er uavhengige av argumenter (x1 , . . . , xn ). Algebraiske operasjoner er definert med f¯(x1 , . . . , xn ) = f (x1 , . . . , xn ), (f + g)(x1 , . . . , xn ) = f (x1 , . . . , xn ) + g(x1 , . . . , xn ), (f · g)(x1 , . . . , xn ) = f (x1 , . . . , xn ) · g(x1 , . . . , xn ). n

Siden |B n | = |B|n = 2n , s˚ a har vi |Fn | = 22 . Boolsk formlene Bn er definert rekursivt: 0, 1, x1 , . . . , xn ∈ Bn , og hvis F , G ∈ Bn s˚ a er ogs˚ a F¯ , F + G, F · G ∈ Bn . Hver formelen F ∈ Bn gir en funksjon f ∈ Fn . La F ∼ G hvis tilsvarende funksjoner er lik f = g. Dette er ekvivalens relasjon p˚ a Bn og vi betrakter mengden av samtlige ekvivalensklasser (Bn /∼). Teorem 25.2. (Bn /∼) = Fn . I tilleg to formlene er ekvivalent F ∼ G hvis og bare hvis uttrykket F kommer fra G via Boolske identiteter. Bevis. Det er klar at ∼ identifiserer forskjellige uttrykker som gir de samme funksjoner, og s˚ a (Bn /∼) best˚ ar av Boolske funksjoner. Vi m˚ a vise at hver slik funksjon f ∈ Fn kan skrives som en formel. La a =½(a1 , . . . , an ) ∈ B n . Betegn med δa ∈ Fn Kronecker funksjonen 1 x=a δa (x) = . Dette kan skrives som uttrykk y1 · · · yn , hvor 0 x 6= a yi = xi dersom ai = 1 og yi = x¯i dersom ai = 0 for alle 1 ≤ i ≤ n. [For eksempel, δ010 (x1 , x2 , x3 ) = x1 · x2 · x3 i B 3 ]

NOTATER - DISKRET MAT. 2010

41

P˚ astanden følger fra dette fordi hver funksjon f ∈ Fn kan skrives P som δai for noen ai ∈ B n (summen kan være tom). ¤ S˚ a hver funksjon kan representeres via 0, 1,¯, +, · . Kan vi bruke mindre antall operasjoner? Ja, fordi de Morgans loven forbinder binære operasjoner: x + y = x¯ · y¯,

x · y = x¯ + y¯.

Vi kan til og med bruke bare ´en binær operasjon | 0 1 0 1 1 1 1 0 for ˚ a f˚ a alle de andre Boolske operasjoner x¯ = x|x,

x + y = (x|x)|(y|y),

x · y = (x|y)|(x|y),

og ogs˚ a konstanter: 1 = x|(x|x),

0 = (x|x)|((x|x)|(x|x)).

26. Logiske kretser Boolske algebrær brukes i strømkretser og andre elektroniske enheter (f.eks. datamaskiner). De basiske logiske operasjoner tilsvarer elektroniske kretser: x -HH © ©

x ¯-

x

-

y

-

x +y

x

-

y

-

» x y¼

Vi kan ogs˚ a bruke addisjon og multiplikasjon med flere argumenter (finn betegnelse). Øvelse: (i) Skriv kretsen (circuit) for Boolsk formelen (x + y)¯ z + x¯. (ii) Finn krets-versjon for de Morgans identitet x y = x¯ + y¯. Adderere. Anta at vi vil finne summen a + b av to binære heltall, hvor a = am am−1 . . . a1 a0 og b = bn bn−1 . . . b1 b0 . Vi beginner med halvadderer (x, y) 7→ x + y mod 2: x ⊕ y = (x + y)(xy). Det finnes forskjell mellom addisjon mod 2 (halv-adderer), vannlig addisjon (adderer) (x, y) 7→ x + y og addisjon ”with carry” dvs. (x, y) 7→ x +s y = x + y + s, s = 0, 1 (merk at +0 ≡ +):

42

BORIS KRUGLIKOV

⊕ 0 1 + 0 1 +1 0 1 0 0 1 0 0 1 0 1 10 1 1 0 1 1 10 1 10 11 Det første siffer i k1 k0 = x + y er gitt med k1 = x y (og k0 = x ⊕ y). For ˚ a beregne k1 k0 = x +s y har vi formelen: k0 = x ⊕ y ⊕ s = x y s + x y¯ s¯ + x¯ y s¯ + x¯ y¯ s, k1 = S(x, y, s) = x y s + x¯ y s + x y¯ s + x y s¯. N˚ a kan vi addere: c = a + b er gitt med c0 = a0 ⊕ b0 , s1 = a0 b0 ; c1 = a1 ⊕b1 ⊕s1 , s2 = S(a1 , b1 , s1 ); c2 = a2 ⊕b2 ⊕s2 , s3 = S(a2 , b2 , s2 ) . . . For ˚ a minimisere elektroniske tilbehør som brukes i enheter m˚ a vi minimisere komleksitet for Boolske formlene av Boolske funksjoner. Dette kan gjøres ved hjelp av Karnaugh algoritmen. Den fungerer bra for funksjoner med n ≤ 6 argumenter (og det finnes mer generelle algoritmer, f.eks. Quine-McCluskey’s, som vi vil ikke diskutere). K-kart (Karnaugh map). Betrakt en funksjon med n ≤ 4 argumenter. Vi tegner den som rektangelen R av størrelse 2 × 2 for n = 2, 2 × 4 for n = 3 og 4 × 4 for n = 4. Vi skriver funksjonsverdiene 1 i celler av rektangelen (som tilsvarer delmengde A) og lar celler fra R \ A st˚ a tomme (verdien 0). Vi merker del-rektangeler (blokker) av størrelser 2i × 2j som best˚ ar av bare 1’er og de P tilsvarer enklere uttrykk i summen av produkter formelen f (x) = a∈A δa (x). Vi trenger bare ˚ a bruke primære blokker (som er ikke dekket med større blokker), og vi kan forsømme de som ikke er vesentlig (dvs. er dekket med andre primære blokker). Eksempel 26.1. Betrakt funksjonen gitt med tabellen x y f 0 0 1 0 1 0 1 0 1 1 1 1 Dette gir f (x, y) = δ00 + δ10 + δ11 = x¯ y¯ + x y¯ + x y, som vi tegner s˚ ann: y

y¯

® ®© x ­ 1 1ª

x ¯

1ª ­

Ovalene som merker primære blokker gir enklere uttrykk f (x, y) = x + y¯.

NOTATER - DISKRET MAT. 2010

43

Eksempel 26.2. For funksjoner f (x, y, z) = xyz + xy¯ z + x¯ y z¯ + x¯ y z + x¯yz + x¯y¯ z g(x, y, z) = xyz + x¯ y z + x¯yz + x¯y¯ z har vi de følgende K-kart yz y¯ z y¯z¯ y¯z

$© ' ® x ­ 1 1 1 1ª

x ¯ 1

1

&%

yz y¯ z y¯z¯ y¯z

®© x 1ª ® © x ¯ ­ 1 ª1 ª

® 1 ­

som simplifiserer funksjoner s˚ ann f (x, y, z) = x + z,

g(x, y, z) = xz + x¯y.

27. Spr˚ ak og (frasestruktur-)grammatikk Definisjon 27.1. Alfabet V er en endelig ikke-tom mengde. Strenger av symboler fra V kalles for ord, og den tomme strengen λ er ogs˚ a et ord. Et spr˚ ak er en delmengde i mengden V ∗ = V + ∪ {λ} av alle ord (V + er mengden av ikke-tomme ord). Definisjon 27.2. Grammatikk G = (V, T, I, P ) best˚ ar av et alfabet V , en mengde T ⊂ V av terminale elementer, initialsymbolen I ∈ V \ T og produksjonsreglene P ⊂ V + × V + slik at for hvert par (x, y) ∈ P (vi skriver x → y) inneholder strengen x et ikke-terminal element θ ∈ V \T . For ˚ a skape ord bruker vi produksjonsreglene x → y for del-strenger: ∗ lxr ⇒ lyr. Sammensatt flere slike implikasjoner betegnes med w ⇒ z. Definisjon 27.3. Spr˚ aket for grammatikken G best˚ ar av alle ord med symboler fra T som skapes fra produksjonsreglene med utgangspunkt I: ∗ L(G) = {w ∈ T ∗ | I ⇒ w}. Eksempel 27.4. G = (V, T, I, P ) hvor V = {I, A, B, a, b, n}, T = {a, b, n}, P = {I → bA, A → λ, A → anB, B → λ, B → an}. Her spr˚ aket for G er L(G) = {b, ban, banan}. Eksempel 27.5. V = {I, 0, 1}, T = {0, 1}, P = {I → 1I, I → 0}. Spr˚ aket er L(G) = {1n 0 | n ≥ 0} = {0, 10, 110, 1110, 11110, . . . }. Eksempel 27.6. V = {I, 0, 1}, T = {0, 1}, P = {I → 0I1, I → λ}. Spr˚ aket er L(G) = {0n 1n | n ≥ 0} = {λ, 01, 0011, 000111, 00001111, . . . }. Eksempel 27.7. V = {I, 0, 1}, T = {0, 1}, P = {I → λ, I → 0I, I → I1}. Spr˚ aket er L(G) = {0m 1n | m, n ≥ 0} = {λ, 0, 1, 00, 01, 11, 000, 001, 011, 111, . . . }.

44

BORIS KRUGLIKOV

Definisjon 27.8. Grammatikken G = (V, T, I, P ) kalles regulær dersom alle produksjonsreglene i P har formen A → λ, A → a eller A → aB for noen terminal a og ikke-terminal symboler A, B. Dersom G er regulær, kaller vi ogs˚ a L(G) regulær. Eksempel 27.5 viser et regulært spr˚ ak. Gramatikken i eksempel 27.7 er ikke regulær, men spr˚ aket er regulært likevel fordi vi kan bytte gramatikken G til en regulær grammatikk G0 = (V 0 , T, I, P 0 ) med V 0 = {I, A, 0, 1}, T = {0, 1} og P 0 = {I → λ, I → 0I, I → 1A, A → 1A, A → λ}, slik at L(G0 ) = L(G). Vi skal se senere at spr˚ aket L(G) er ikke regulært for grammatikken i eksempel 27.6. 28. Endelig-tilstand automata og spr˚ ak gjenkjennelse La A, B ⊂ V ∗ være noen mengder av ord i alfabet V . Sammenkjeding av A og B er A B = {x y | x ∈ A, y ∈ B}. Vi definerer potensmengder rekursivt A0 = {λ}, A1 = A, A2 = A A, n + ∞ n ∗ . . . , An+1 = A An , . . . Vi setter A∗ = ∪∞ n=0 A , A = ∪n=1 A = A A . Definisjon 28.1. En endelig-tilstand automaton M = (S, T, f, s0 , F ) best˚ ar av en endelig mengde S av tilstander, et endelig input alfabet T , en overgangsfunksjon f : S × T → S, initialstand s0 ∈ S og en delmengde F ⊂ S av terminalstander. Vi kan utvide overgangsfunksjon gjennom transitivitet til funksjonen f : S × T ∗ → S gitt rekursivt med f (s, λ) = s,

f (s, x a) = f (f (s, x), a),

hvor s ∈ S, x ∈ T ∗ , a ∈ T . Derfor er automaton M deterministisk (for hver s ∈ S og x ∈ T ∗ er f (s, x) entydig definert). aket gjenkjent av automaton M = (S, T, f, s0 , F ) Definisjon 28.2. Spr˚ best˚ ar av alle ord som tar initialstand til en av terminalstander: L(M ) = {x ∈ T ∗ | f (s0 , x) ∈ F }. To automata M, M 0 er ekvivalent dersom de gjenkjenner det samme spr˚ ak L(M ) = L(M 0 ).

NOTATER - DISKRET MAT. 2010

45

Eksempel 28.3. Finn spr˚ aket for automaton M (terminalstander er i en dobbel sirkel): ' 1 ¶

$ ³ ? ?0,1 start 0 - sk 1 - sn 1 - sn - sn n 0 1 2 39 § ¦ 6 0 0

Her er L(M ) = 0(10)∗ = {0, 010, 01010, 0101010, . . . }. Øvelse: G˚ a gjennom eksempler i §12.3 i boka uten ˚ a lese teori. NB: Det eksisterer ogs˚ a ikke-deterministiske automata, slik at for noen tilstander s og symboler (bokstaver) a ∈ T finnes det flere muligheter for f (s, a), dvs. at det finnes flere piler fra s med det samme (input) tegn p˚ a. Men de er ekvivalent til deterministiske automata. Definisjon 28.4. Regulære uttrykk over alfabetet T er definert rekursivt med ∅, λ, a er regulære ∀a ∈ T, A, B er regulære ⇒ A B, A ∪ B, A∗ er regulære. Hvert regulæret uttrykk r definerer entydig et spr˚ ak R(r) ⊂ T ∗ . Eksempel 28.5. Her er noen regulære uttrykk og tilsvarende spr˚ ak: ∗ 1 ∪ 01 = {0, 1, 01, 011, 0111, 01111, . . . }. λ ∪ 1(01)∗ = {λ, 1, 101, 10101, 1010101, . . . }. 0(0∗ 1)+ = {alle bitstrenger som begynner med 0 og slutter med 1}. Teorem 28.6. Et spr˚ ak R(r) er regulært hvis og bare hvis uttrykket r er regulært. Eksempel 28.7. Spr˚ aket fra eksempel 27.4 er regulært fordi det er gitt med regulært utrykk b ∪ ban ∪ banan. Spr˚ aket fra eksempel 27.5 er gitt ∗ med regulært utrykk 1 0 og er derfor regulært. Spr˚ aket fra eksempel 27.7 er gitt med regulært utrykk 0∗ 1∗ og er ogs˚ a regulært. Teorem 28.8 (Kleene’s teorem). Spr˚ aket R ⊂ T ∗ er regulært hvis og bare hvis det er gjenkjent av en endelig-tilstand automaton, dvs. R = L(M ). aket R best˚ aenEksempel 28.9. Finn automaton som gjenkjenner spr˚ de av ord som begynner og slutter med 0 og har ingen etterfølgende 0’er. Her R er gitt med regulært uttrykk 0(1+ 0)∗ og er gjenkjent av

46

BORIS KRUGLIKOV

automaton n XXX 1X : sk » y 1 XXXXX 0 »»» » XXX XXX »» » z n1 » start 0 XXX - sn 0 s2 9 0 X XXX 1 XXX ? 0,1 X z sn X 9 3

Det finnes ogs˚ a ikke-regulære spr˚ ak. Eksempel 28.10. La oss se igjen p˚ a spr˚ aket R = {0n 1n | n ≥ 0} fra eksempel 27.6. Anta at det eksisterer en deterministisk automaton M som gjenkjenner R. La N = |S|. Ordet ω = 0N 1N er gjenkjent av M . La s0 s1 . . . s2N være sekvensen av tilstander som tilsvarer ω som input (s2N er en terminalstand). Ifølge dueslagprinsippet finnes det to lik tilstander gjennom s0 , . . . , sN . Betegn dem si , sj , i < j. Derfor har vi en løkke σ = si . . . sj i (multipseudo- rettet) grafen tilsvarende M med 0’er p˚ a kanter. Betegn lengde av løkken med t = j − i. La oss skrive ω som sammenkjeding ω = α σ ν, hvor α = s0 . . . si og ν = sj . . . s2N . Da er ogs˚ a ω 0 = α σσ ν et ord som er gjenkjent av M (vi g˚ ar to ganger p˚ a løkken). Men ω 0 = 0N +t 1N 6∈ R. Motsiegelse! Dette viser at R ikke er et regulært spr˚ ak. Mer komplisert automata eksisterer, som kan gjenkjenne kontekstfornuftig spr˚ ak, f.eks. lineær begrenset automata eller en Turing maskin, som er prototypen av moderne datamaskiner.