Volum 1: Logikk & Mengder

Fundamentet for diskret matematikk

🧠 Logikk

Proposisjoner (Utsagn)

En proposisjon er et utsagn som er enten sant (T) eller usant (F), men ikke begge deler.

Eksempler på proposisjoner:

"Oslo er hovedstaden i Norge" - SANT
"2 + 2 = 5" - USANT
"Alle primtall er odde" - USANT (2 er et primtall)

IKKE proposisjoner:

"Hva heter du?" - Spørsmål
"Lukk døren!" - Kommando
"x + 2 = 5" - Avhenger av x (kan være sant eller usant)

Logiske operatorer

NOT (¬): Negasjon
AND (∧): Konjunksjon (sant bare hvis begge er sanne)
OR (∨): Disjunksjon (sant hvis minst én er sann)
XOR (⊕): Eksklusiv OR (sant hvis nøyaktig én er sann)
→ : Implikasjon (hvis p, så q)
↔ : Biimplikasjon (p hvis og bare hvis q)

💡 Sannhetstabell for implikasjon (p → q)

En implikasjon er bare usann når p er sann og q er usann!
• T → T = T
• T → F = F
• F → T = T
• F → F = T

"Hvis det regner, tar jeg paraply" er bare usann hvis det regner OG jeg ikke tar paraply.

Logiske ekvivalenser (Viktige lover)

De Morgans lover:
- ¬(p ∧ q) ≡ ¬p ∨ ¬q
- ¬(p ∨ q) ≡ ¬p ∧ ¬q
Kommutative lover:
- p ∧ q ≡ q ∧ p
- p ∨ q ≡ q ∨ p
Assosiative lover:
- (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
- (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
Distributive lover:
- p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
- p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

📦 Mengdelære

Hva er en mengde?

En mengde er en samling av distinkte objekter (elementer). Rekkefølgen spiller ingen rolle, og duplikater ignoreres.

Notasjon:
A = {1, 2, 3, 4, 5}
B = {2, 4, 6, 8}
x ∈ A betyr "x er element i A"
x ∉ A betyr "x er ikke element i A"

Spesielle mengder

Tomme mengden: ∅ eller { } (inneholder ingen elementer)
Univers: U (mengden av alle elementer under betraktning)
ℕ: Naturlige tall {0, 1, 2, 3, ...}
ℤ: Hele tall {..., -2, -1, 0, 1, 2, ...}
ℚ: Rasjonale tall (brøker)
ℝ: Reelle tall

Mengdeoperasjoner

Union (A ∪ B): Alle elementer som er i A ELLER B
Snitt (A ∩ B): Elementer som er i BÅDE A OG B
Differanse (A \ B eller A - B): Elementer i A som IKKE er i B
Komplement (A'): Alle elementer i U som IKKE er i A
Symmetrisk differanse (A ⊕ B): (A ∪ B) \ (A ∩ B)

Eksempel:
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}

A ∪ B = {1, 2, 3, 4, 5, 6}
A ∩ B = {3, 4}
A \ B = {1, 2}
A ⊕ B = {1, 2, 5, 6}

Kartesisk produkt

A × B er mengden av alle ordnede par (a, b) der a ∈ A og b ∈ B.

A = {1, 2}, B = {x, y}
A × B = {(1,x), (1,y), (2,x), (2,y)}

💡 Kardinalitet

|A| er antall elementer i mengden A.
Inklusjons-eksklusjonsprinsippet:
|A ∪ B| = |A| + |B| - |A ∩ B|

↔️ Relasjoner

Hva er en relasjon?

En binær relasjon R fra A til B er en delmengde av A × B.
Vi skriver aRb eller (a,b) ∈ R for å si at a er relatert til b.

Eksempel:
A = {1, 2, 3}, B = {x, y}
R = {(1,x), (2,x), (2,y), (3,y)}
Da er: 1Rx, 2Rx, 2Ry, 3Ry

Egenskaper ved relasjoner (på A × A)

Refleksiv: ∀a ∈ A: aRa (alle elementer er relatert til seg selv)
Symmetrisk: ∀a,b: aRb → bRa
Antisymmetrisk: ∀a,b: (aRb ∧ bRa) → a = b
Transitiv: ∀a,b,c: (aRb ∧ bRc) → aRc

            ⚠️ Viktig for eksamen:

            • Ekvivalensrelasjon: Refleksiv + Symmetrisk + Transitiv

            • Partiell orden: Refleksiv + Antisymmetrisk + Transitiv

            • Total orden: Partiell orden + alle par er sammenlignbare

➡️ Funksjoner

Definisjon

En funksjon f: A → B er en spesiell relasjon der hvert element i A er relatert til nøyaktig ett element i B.

Typer funksjoner

Injektiv (én-til-én): Ulike elementer i A går til ulike elementer i B
- ∀a₁,a₂ ∈ A: f(a₁) = f(a₂) → a₁ = a₂
Surjektiv (onto): Hvert element i B har minst én urverdi i A
- ∀b ∈ B, ∃a ∈ A: f(a) = b
Bijektiv: Både injektiv og surjektiv (perfekt én-til-én korrespondanse)

Eksempel:
f: ℤ → ℤ, f(x) = 2x
• Injektiv? JA (hvis 2x₁ = 2x₂, så x₁ = x₂)
• Surjektiv? NEI (3 har ingen urverdi siden 3/2 ∉ ℤ)
• Bijektiv? NEI

💡 Inversfunksjoner

En funksjon f har en invers f⁻¹ hvis og bare hvis f er bijektiv.
(f⁻¹ ∘ f)(x) = x og (f ∘ f⁻¹)(y) = y

Volum 2: Tallteori

Tallsystemer, delelighet og modulær aritmetikk

🔢 Delelighet

Definisjon

Vi sier at a deler b (skrevet a | b) hvis det eksisterer et heltall k slik at b = ka.
Eksempel: 3 | 12 fordi 12 = 3 · 4

Divisjonsalgoritmen

For alle heltall a og positive heltall d eksisterer unike heltall q og r slik at:
a = dq + r der 0 ≤ r < d

q = kvotient (quotient)
r = rest (remainder)

Eksempel: 25 = 7 · 3 + 4
Her er: a = 25, d = 7, q = 3, r = 4

Største felles divisor (GCD)

gcd(a, b) er det største positive heltallet som deler både a og b.

💡 Euklids algoritme

For å finne gcd(a, b):
1. Hvis b = 0, returner a
2. Ellers, returner gcd(b, a mod b)

Eksempel: gcd(48, 18)
= gcd(18, 48 mod 18) = gcd(18, 12)
= gcd(12, 18 mod 12) = gcd(12, 6)
= gcd(6, 12 mod 6) = gcd(6, 0)
= 6

Primtall

Et primtall er et naturlig tall større enn 1 som bare er delelig med 1 og seg selv.

De første primtallene: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
2 er det eneste partall som er et primtall
Aritmetikkens fundamentalteorem: Hvert heltall > 1 kan faktoriseres unikt som produkt av primtall

Primfaktorisering:
60 = 2² · 3 · 5
100 = 2² · 5²

⚙️ Modulær aritmetikk

Kongruens

a ≡ b (mod m) betyr at m | (a - b)
Ekvivalent: a og b har samme rest ved divisjon med m

Eksempel:
23 ≡ 8 (mod 5) fordi 23 - 8 = 15, og 5 | 15
Eller: 23 = 5 · 4 + 3 og 8 = 5 · 1 + 3 (samme rest 3)

Regneregler for kongruenser

Hvis a ≡ b (mod m) og c ≡ d (mod m), da:

a + c ≡ b + d (mod m)
a - c ≡ b - d (mod m)
a · c ≡ b · d (mod m)
aⁿ ≡ bⁿ (mod m) for n ≥ 0

            ⚠️ OBS for divisjon:

            Du kan IKKE dele begge sider med et tall generelt!

            6 ≡ 2 (mod 4), men 3 ≢ 1 (mod 4)

            (Kan dele hvis tallet er relativt primisk med modulusen)

Modulær invers

a⁻¹ (mod m) er et tall x slik at a · x ≡ 1 (mod m).
Inversen eksisterer hvis og bare hvis gcd(a, m) = 1.

Finn 7⁻¹ (mod 11):
Vi søker x slik at 7x ≡ 1 (mod 11)
Prøv: 7 · 8 = 56 = 11 · 5 + 1 ≡ 1 (mod 11)
Svar: 7⁻¹ ≡ 8 (mod 11)

Viktige teoremer

💡 Fermats lille teorem

Hvis p er primtall og gcd(a, p) = 1, da:
aᵖ⁻¹ ≡ 1 (mod p)

Konsekvens: aᵖ ≡ a (mod p) for alle a

💡 Eulers teorem

Hvis gcd(a, n) = 1, da:
aᵠ⁽ⁿ⁾ ≡ 1 (mod n)
der φ(n) = Eulers phi-funksjon (antall tall < n som er relativt primiske med n)

🧮 Kinesisk restteorem (CRT)

Teoremet

Hvis m₁, m₂, ..., mₖ er parvis relativt primiske (gcd(mᵢ, mⱼ) = 1 for i ≠ j), da har systemet:

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₖ (mod mₖ)

en unik løsning modulo M = m₁ · m₂ · ... · mₖ

Eksempel: Løs systemet:
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

Løsning: x ≡ 23 (mod 105)

Volum 3: Kombinatorikk

Telling, permutasjoner og kombinasjoner

🎲 Grunnleggende telleprins ipper

Produktregelen (Multiplication Principle)

Hvis en hendelse kan inntreffe på n₁ måter, og en annen uavhengig hendelse på n₂ måter, kan begge sammen inntreffe på n₁ · n₂ måter.

Eksempel: Hvor mange måter kan du velge en forrett (3 valg) og en hovedrett (5 valg)?
Svar: 3 · 5 = 15 måter

Sumregelen (Addition Principle)

Hvis to hendelser er gjensidig utelukkende, og den første kan inntreffe på n₁ måter og den andre på n₂ måter, kan enten den ene eller den andre inntreffe på n₁ + n₂ måter.

🔄 Permutasjoner

Permutasjoner uten repetisjon

Antall måter å ordne n distinkte objekter:
P(n) = n!

Antall måter å velge og ordne r objekter fra n:
P(n, r) = n!/(n-r)!

Eksempel: På hvor mange måter kan 5 personer sitte i en rad?
Svar: 5! = 120

På hvor mange måter kan vi velge president og visepresident fra 10 kandidater?
Svar: P(10, 2) = 10!/8! = 10 · 9 = 90

Permutasjoner med repetisjon

Hvis vi har n objekter der n₁ er like, n₂ er like, osv.:
n! / (n₁! · n₂! · ... · nₖ!)

Eksempel: Hvor mange anagrammer har ordet "MISSISSIPPI"?
11 bokstaver: 1M, 4I, 4S, 2P
Svar: 11! / (1! · 4! · 4! · 2!) = 34,650

Sirkulære permutasjoner

Antall måter å ordne n objekter i en sirkel:
(n-1)!

🎯 Kombinasjoner

Kombinasjoner uten repetisjon

Antall måter å velge r objekter fra n der rekkefølge ikke spiller rolle:

C(n, r) = (n choose r) = n! / (r!(n-r)!)

Eksempel: På hvor mange måter kan vi velge 3 personer fra en gruppe på 10?
Svar: C(10, 3) = 10!/(3!·7!) = 120

Kombinasjoner med repetisjon

Antall måter å velge r objekter fra n typer (repetisjon tillatt):
C(n+r-1, r) = (n+r-1)! / (r!(n-1)!)

            ⚠️ Huskeregel:

            • Rekkefølge viktig? → Permutasjon

            • Rekkefølge uviktig? → Kombinasjon

            • Repetisjon tillatt? → Bruk formel med repetisjon

📊 Binomialteoremet

(x + y)ⁿ = Σ C(n,k) · xⁿ⁻ᵏ · yᵏ for k = 0 til n

Eksempel: (x + y)³
= C(3,0)x³y⁰ + C(3,1)x²y¹ + C(3,2)x¹y² + C(3,3)x⁰y³
= x³ + 3x²y + 3xy² + y³

Pascals triangel

            1
           1 1
          1 2 1
         1 3 3 1
        1 4 6 4 1
       1 5 10 10 5 1

Hvert tall er summen av de to tallene over: C(n,k) = C(n-1,k-1) + C(n-1,k)

🔁 Rekursjon

Rekursive relasjoner

En rekursiv relasjon definerer et ledd i en sekvens ved hjelp av tidligere ledd.

Fibonacci-tall:
F₀ = 0, F₁ = 1
Fₙ = Fₙ₋₁ + Fₙ₋₂ for n ≥ 2
Sekvens: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Løsning av lineære rekursjoner

For aₙ = c₁aₙ₋₁ + c₂aₙ₋₂, finn karakteristisk likning:

r² - c₁r - c₂ = 0

Hvis røttene er r₁ og r₂, da: aₙ = α₁r₁ⁿ + α₂r₂ⁿ

Grafteori

Noder, kanter og veier

🌐 Grunnleggende begreper

Hva er en graf?

En graf G = (V, E) består av:

V: Mengde av noder (vertices)
E: Mengde av kanter (edges) som forbinder nodene

Typer grafer

Urettet graf: Kanter har ingen retning
Rettet graf (digraf): Kanter har retning (fra en node til en annen)
Vektet graf: Hver kant har en vekt (tall)
Simpel graf: Ingen løkker eller parallelle kanter
Komplett graf Kₙ: Alle par av noder er forbundet

Grad av en node

deg(v) = antall kanter som møtes i node v

💡 Håndtrykkingsteoremet

Summen av alle grader = 2 · antall kanter
Σ deg(v) = 2|E|

Antall noder med odde grad må være partall

🚶 Veier og sykler

Definisjoner

Vei (path): Sekvens av kanter uten gjentatte kanter
Enkel vei: Vei uten gjentatte noder
Sykel (cycle): Vei som starter og slutter i samme node
Sammenhengende graf: Det finnes en vei mellom alle par av noder

Euler-veier og sykler

Euler-vei: Vei som bruker hver kant nøyaktig én gang
Euler-sykel: Sykel som bruker hver kant nøyaktig én gang

💡 Eulers teorem

En sammenhengende graf har:
• Euler-sykel ⟺ alle noder har partall grad
• Euler-vei ⟺ nøyaktig 2 noder har odde grad

Hamilton-veier og sykler

Hamilton-vei: Vei som besøker hver node nøyaktig én gang
Hamilton-sykel: Sykel som besøker hver node nøyaktig én gang

            ⚠️ Viktig forskjell:

            • Euler: Hver KANT én gang

            • Hamilton: Hver NODE én gang

            (Det finnes ingen enkel algoritme for Hamilton-problemer - NP-komplett!)

🌳 Trær

Definisjon

Et tre er en sammenhengende graf uten sykler.

Egenskaper ved trær

Et tre med n noder har nøyaktig n - 1 kanter
Det finnes nøyaktig én enkel vei mellom to noder
Å fjerne en kant gjør grafen usammenhengende
Å legge til en kant skaper en sykel

Binære trær

Et binært tre er et rotert tre der hver node har høyst 2 barn (venstre og høyre).

Fullt binært tre: Alle indre noder har nøyaktig 2 barn
Komplett binært tre: Alle nivåer er fulle, unntatt muligens det siste
Høyde: Lengste vei fra rot til blad

Et binært tre med høyde h har høyst 2ʰ⁺¹ - 1 noder

📏 Korteste vei-algoritmer

Dijkstras algoritme

Finner korteste vei fra en startnode til alle andre noder i en vektet graf (ikke-negative vekter).

💡 Dijkstras algoritme - Pseudokode

1. Sett dist[start] = 0, dist[alle andre] = ∞
2. Sett alle noder som ubesøkt
3. Mens det finnes ubesøkte noder:
   a. Velg ubesøkt node u med minst dist[u]
   b. Merk u som besøkt
   c. For hver nabo v til u:
      hvis dist[u] + vekt(u,v) < dist[v]:
          dist[v] = dist[u] + vekt(u,v)

Bellman-Ford algoritme

Finner korteste vei selv med negative vekter (men ingen negative sykler). Tregere enn Dijkstra, men mer generell.

Kryptografi & RSA

Moderne kryptering basert på tallteori

🔐 Grunnleggende kryptografi

Typer kryptering

Symmetrisk kryptering: Samme nøkkel for kryptering og dekryptering (f.eks. AES)
Asymmetrisk kryptering: Offentlig nøkkel for kryptering, privat nøkkel for dekryptering (f.eks. RSA)

Caesar-chiffer (historisk)

Hver bokstav flyttes k posisjoner i alfabetet.
Eksempel med k=3: A→D, B→E, C→F, ..., X→A, Y→B, Z→C

Klartekst: HELLO
Chiffertekst (k=3): KHOOR

🔑 RSA-kryptering

RSA-algoritmen

RSA er et asymmetrisk krypteringssystem basert på vanskeligheten av å faktorisere store tall.

💡 RSA nøkkelgenerering

Velg to store primtall p og q
Beregn n = p · q
Beregn φ(n) = (p-1)(q-1)
Velg e slik at 1 < e < φ(n) og gcd(e, φ(n)) = 1
Finn d slik at e · d ≡ 1 (mod φ(n))

Offentlig nøkkel: (n, e)
Privat nøkkel: (n, d)

Kryptering og dekryptering

Kryptering: C = Mᵉ (mod n)
Dekryptering: M = Cᵈ (mod n)

Komplett RSA-eksempel:

1. Velg p = 3, q = 11
2. n = 3 · 11 = 33
3. φ(33) = 2 · 10 = 20
4. Velg e = 3 (gcd(3, 20) = 1)
5. Finn d: 3d ≡ 1 (mod 20) → d = 7

Offentlig nøkkel: (33, 3)
Privat nøkkel: (33, 7)

Krypter melding M = 2:
C = 2³ mod 33 = 8

Dekrypter C = 8:
M = 8⁷ mod 33 = 2 ✓

Hvorfor er RSA sikker?

Lett å finne store primtall
Lett å multiplisere p · q = n
Vanskelig å faktorisere n tilbake til p og q (hvis n er stor nok)
Uten p og q kan man ikke beregne φ(n) eller d

            ⚠️ Eksamensfavoritt:

            Husk hele RSA-prosessen! Du må kunne:

            • Generere nøkler

            • Kryptere en melding

            • Dekryptere en melding

            • Forklare hvorfor det er sikkert

📝 Digitale signaturer

Hvordan fungerer det?

Digitale signaturer bruker RSA "baklengs":

Signering: S = Mᵈ (mod n) (bruker privat nøkkel)
Verifisering: M = Sᵉ (mod n) (bruker offentlig nøkkel)

Dette beviser at meldingen kom fra eieren av den private nøkkelen!

💡 Kryptering vs Signering

Kryptering (hemmelighold):
• Bruker mottakerens offentlige nøkkel
• Bare mottakeren kan dekryptere

Signering (autentisitet):
• Bruker avsenderens private nøkkel
• Alle kan verifisere signaturens
• Beviser at avsender har sendt meldingen

Oppsummering & Eksamenstips

Alt du trenger å huske før eksamen

📋 Viktigste formler og konsepter

Logikk

De Morgans lover: ¬(p ∧ q) ≡ ¬p ∨ ¬q og ¬(p ∨ q) ≡ ¬p ∧ ¬q
Implikasjon: p → q er bare usann når p er sann og q er usann

Mengdelære

Inklusjons-eksklusjon: |A ∪ B| = |A| + |B| - |A ∩ B|
Potens-mengde: |P(A)| = 2^|A|

Tallteori

Euklids algoritme for gcd
Fermats lille teorem: a^(p-1) ≡ 1 (mod p) hvis p er primtall
Eulers teorem: a^φ(n) ≡ 1 (mod n) hvis gcd(a,n) = 1

Kombinatorikk

Permutasjoner: P(n,r) = n!/(n-r)!
Kombinasjoner: C(n,r) = n!/(r!(n-r)!)
Binomialteorem: (x+y)^n = Σ C(n,k) x^(n-k) y^k

Grafteori

Håndtrykkingsteoremet: Σ deg(v) = 2|E|
Euler-sykel: Alle noder har partall grad
Tre med n noder har n-1 kanter

RSA

n = p · q, φ(n) = (p-1)(q-1)
e · d ≡ 1 (mod φ(n))
Kryptering: C = M^e (mod n)
Dekryptering: M = C^d (mod n)

✅ Eksamen-sjekkliste

Kan du...

☐ Sette opp og løse sannhetstabeller?
☐ Bevise logiske ekvivalenser med De Morgans lover?
☐ Utføre mengdeoperasjoner (union, snitt, differanse)?
☐ Bruke Euklids algoritme til å finne gcd?
☐ Løse kongruenslikninger?
☐ Finne modulær invers?
☐ Beregne permutasjoner og kombinasjoner?
☐ Løse problemer med binomialteoremet?
☐ Identifisere Euler-veier og sykler?
☐ Bruke Dijkstras algoritme?
☐ Generere RSA-nøkler?
☐ Kryptere og dekryptere med RSA?

💡 Studietips

Slik lærer du diskret matematikk effektivt:

Øv, øv, øv! Matematikk læres best ved å løse oppgaver
Forstå bevisene: Ikke bare pugge formler, forstå hvorfor de gjelder
Lag egne eksempler: Test konseptene på små, enkle eksempler
Tegn grafer: Visualisering hjelper enormt i grafteori
Skriv ned prosessen: RSA og Euklid krever steg-for-steg-løsninger
Bruk øvingsoppgavene: Gå gjennom alle 10 øvingssettene

            ⚠️ Vanlige feil å unngå:
            Glemme at implikasjon p → q er sann når p er usann
Forveksle permutasjoner og kombinasjoner
Glemme at gcd(a,n) = 1 er nødvendig for modulær invers
Blande Euler-veier (kanter) med Hamilton-veier (noder)
Ikke sjekke at e og φ(n) er relativt primiske i RSA

        

🎯 Siste forberedelser

💪 Uken før eksamen

Dag 7-5: Gjennomgå alt pensum systematisk
Dag 4-3: Løs gamle eksamensoppgaver
Dag 2: Gjenta vanskelige temaer
Dag 1: Lett repetisjon, god søvn!

🎓 På eksamensdagen

Les oppgavene nøye - svar på det som spørres om
Start med oppgaver du er trygg på
Vis mellomregninger - delpoeng er viktig!
Sjekk svarene dine hvis tid
Ikke panikk hvis noe er vanskelig - alle sliter med noen oppgaver

🌟 Du klarer dette! 🌟

Diskret matematikk er utfordrende, men med grundig forberedelse og øving
vil du mestre det. Lykke til på eksamen!

📐 🎓 ✨