Teken een venndiagram en bepaal gebied voor gebied wat bij de verzamelingsuitdrukking hoort.
Vul bij telproblemen de gebieden van binnen naar buiten in: eerst alle verzamelingen, dan de paren, dan de losse verzamelingen en tot slot de buitenkant.
Gebruik inclusie–exclusie als controle: |A ∪ B| = |A| + |B| − |A ∩ B|.
Test bij een relatie elke eigenschap op elk paar en geef één tegenvoorbeeld als ze niet geldt.
Tel bij een functie de pijlen die aankomen bij elk element van B: hoogstens één betekent injectief, minstens één surjectief.
Grafentheorie
Handenschudlemma
Σ deg(v) = 2|E|
Volledige grafen
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Reguliere graaf
|E| = n·k/2
Boom en bos
|E| = n − 1, |E| = n − c
Bladeren van een boom
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
circuit: alle graden even; pad: precies 2 oneven graden
Hamiltoncircuits in Kn
(n − 1)!/2
Dijkstra-update
d(v) = min(d(v), d(u) + w(u, v))
Wandelingen van lengte L
(Mᴸ)ij
Methode
Schrijf de graad van elk hoekpunt op; de graden zijn samen twee keer het aantal kanten.
Controleer bij Eulervragen of de graaf samenhangend is en tel de hoekpunten met oneven graad.
Gebruik bij bomen n − 1 kanten en het handenschudlemma.
Houd bij Dijkstra een tabel met voorlopige afstanden bij en leg elke ronde het onafgehandelde hoekpunt met de kleinste afstand vast.
Sorteer voor een minimaal opspannende boom de kanten op gewicht en sla elke kant over die een cykel sluit (Kruskal), of laat één boom groeien vanuit een beginpunt (Prim).
Getaltheorie & modulair rekenen
Deling met rest
a = q·n + r, 0 ≤ r < n
Euclides
gcd(a, b) = gcd(b, a mod b)
Kleinste gemene veelvoud
lcm(a, b) = a·b/gcd(a, b)
Inverse
a·a⁻¹ ≡ 1 (mod n), gcd(a, n) = 1
Lineaire congruentie
a·x ≡ b → x ≡ a⁻¹·b (mod n)
Eulers φ-functie
φ(n) = n·∏(1 − 1/p), φ(pᵏ) = pᵏ − pᵏ⁻¹
Fermat
aᵖ⁻¹ ≡ 1 (mod p)
RSA
n = pq, φ = (p − 1)(q − 1), d = e⁻¹ mod φ, c = mᵉ mod n, m = cᵈ mod n
Methode
Reduceer eerst elk getal modulo n; resten liggen tussen 0 en n − 1.
Deel voor een ggd herhaaldelijk met het algoritme van Euclides; de laatste rest ongelijk aan nul is de ggd.
Laat voor een inverse het uitgebreide algoritme lopen en houd de coëfficiënt van a; tel n erbij op als die negatief is.
Los a·x ≡ b op door met a⁻¹ te vermenigvuldigen; combineer twee congruenties door x = r₁ + m₁k te schrijven.
Schrijf bij machten de exponent binair en kwadrateer herhaaldelijk; in RSA is d = e⁻¹ mod φ(n) met φ(n) = (p − 1)(q − 1).
2Oefenopgaven
1.Propositielogica & bewijzenGemiddeld
Je wilt (r ∨ p) → q bewijzen uit het ongerijmde. Welke uitspraak neem je aan het begin aan? Klik erop.
(r ∨ p) → q
1¬(r ∨ p) ∧ q
2¬(r ∨ p) ∧ ¬q
3(r ∨ p) ∧ ¬q
4¬(r ∨ p) → ¬q
2.Propositielogica & bewijzenMoeilijk
Welke uitspraak is equivalent met ¬∀x (A(x) → B(x)), met de ontkenning helemaal naar binnen geschoven? Klik erop.
¬∀x (A(x) → B(x))
1∃x (¬A(x) ∧ B(x))
2∃x (A(x) ∧ ¬B(x))
3∃x (A(x) → ¬B(x))
4∀x (A(x) ∧ ¬B(x))
3.Verzamelingen, relaties & functiesGemiddeld
Precies één gebied van het venndiagram is de verzameling (C ∩ B′) ∩ (A − B). Klik op zijn nummer.
(C ∩ B′) ∩ (A − B)
1gebied 1
2gebied 2
3gebied 3
4gebied 4
5gebied 5
6gebied 6
7gebied 7
8gebied 8
4.Verzamelingen, relaties & functiesMoeilijk
Hoeveel antisymmetrische relaties zijn er op een verzameling met 2 elementen? Noem het aantal N.
|X| = 2
N =
5.GrafentheorieGemiddeld
Een boom heeft 4 hoekpunten van graad 3, 3 hoekpunten van graad 4, 2 hoekpunten van graad 5, 3 hoekpunten van graad 2, en al zijn andere hoekpunten zijn bladeren (graad 1). Hoeveel bladeren L heeft hij?
4 × deg 33 × deg 42 × deg 53 × deg 2
L =
6.GrafentheorieMoeilijk
Hoeveel wandelingen van lengte 2 gaan van C naar A? Een wandeling mag hoekpunten en kanten herhalen. Noem het aantal N.
M = adjacentiematrixL = 2
N =
7.Getaltheorie & modulair rekenenGemiddeld
Vind de inverse van 13 modulo 17: het getal x met 0 < x < 17 en 13·x ≡ 1 (mod 17).
a = 13n = 17
13−1 mod 17 =
8.Getaltheorie & modulair rekenenMoeilijk
Een RSA-sleutel gebruikt de priemgetallen p = 23 en q = 47 en de publieke exponent e = 17. Bepaal de privé-exponent d (0 < d < φ(n)).
p = 23q = 47e = 17
d =
3Oplossingen
1.Propositielogica & bewijzen
Antwoord: (r ∨ p) ∧ ¬q
Logische equivalentie: twee formules zijn equivalent (≡) als ze in elke rij van de waarheidstabel dezelfde waarde hebben. Een tautologie is in elke rij 1, een contradictie in elke rij 0, en een contingentie is geen van beide. Nuttige wetten: De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b en ¬(a ∨ b) ≡ ¬a ∧ ¬b; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contrapositie); ¬(a → b) ≡ a ∧ ¬b; en de distributieve wetten, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Delen van de implicatie
a = r ∨ p, b = q
Ontkenning van de implicatie
¬(a → b) ≡ a ∧ ¬b = (r ∨ p) ∧ ¬q
Antwoord
(r ∨ p) ∧ ¬q
Als de aanname tot een tegenspraak leidt, moet de implicatie waar zijn.
2.Propositielogica & bewijzen
Antwoord: ∃x (A(x) ∧ ¬B(x))
Kwantoren en redeneringen: ¬∀x P(x) ≡ ∃x ¬P(x) en ¬∃x P(x) ≡ ∀x ¬P(x). Schuif een ontkenning naar binnen, verwissel elke kwantor die ze passeert en ontken de binnenste formule met de propositiewetten, zoals ¬(a → b) ≡ a ∧ ¬b. Een redenering is geldig als de conclusie 1 is in elke rij waarin alle premissen 1 zijn. Eén rij met ware premissen en een onware conclusie is een tegenvoorbeeld en toont aan dat de redenering ongeldig is.
Schuif de ontkenning naar binnen
¬∀x (A(x) → B(x)) ≡ ∃x (A(x) ∧ ¬B(x))
Antwoord
∃x (A(x) ∧ ¬B(x))
De andere opties laten een kwantor onveranderd, veranderen de volgorde van de kwantoren, of ontkennen de binnenste formule verkeerd.
3.Verzamelingen, relaties & functies
Antwoord: gebied 1
Verzamelingen en venndiagrammen: A ∪ B bevat de elementen in A of B (of beide), A ∩ B de elementen in beide, A − B de elementen van A die niet in B zitten, en het complement A′ alles in U dat niet in A zit. In een venndiagram is elke verzamelingsuitdrukking een vereniging van gebieden, dus tel gebied voor gebied. Inclusie–exclusie: |A ∪ B| = |A| + |B| − |A ∩ B|, en |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|.
Binnen of buiten elke verzameling
A ∩ B′ ∩ C
Het gebied
gebied 1
Antwoord
gebied 1
4.Verzamelingen, relaties & functies
Antwoord: N = 12
Relaties: een relatie R op een verzameling X is een verzameling geordende paren (x, y). R is reflexief als (x, x) ∈ R voor elke x in X; symmetrisch als (x, y) ∈ R altijd samengaat met (y, x) ∈ R; antisymmetrisch als (x, y) en (y, x) alleen beide in R zitten als x = y; en transitief als (x, y) en (y, z) in R (x, z) ∈ R afdwingen. Een equivalentierelatie is reflexief, symmetrisch en transitief, en verdeelt X in disjuncte klassen.
Tel de vrije keuzes
N = 22·31 = 12
Antwoord
N = 12
5.Grafentheorie
Antwoord: L = 18
Euler, Hamilton en bomen: een samenhangende graaf heeft een Eulercircuit (elke kant één keer, terug naar het begin) als elk hoekpunt even graad heeft, en een Eulerpad dat geen circuit is als precies twee hoekpunten oneven graad hebben; het pad loopt dan van het ene oneven hoekpunt naar het andere. Een Hamiltoncircuit bezoekt elk hoekpunt één keer; Kn heeft er (n − 1)!/2. Een boom op n hoekpunten heeft n − 1 kanten, en een samenhangende graaf met m kanten houdt een opspannende boom over na het verwijderen van m − n + 1 kanten.
Handenschudlemma voor een boom
L + 40 = 2(L + 12) − 2
L = 18
Antwoord
L = 18
Snelle methode: L = 2 + Σ (d − 2) over de hoekpunten met graad d ≥ 3.
6.Grafentheorie
Antwoord: N = 1
Graden: de graad van een hoekpunt is het aantal kanten dat erin samenkomt. Elke kant heeft twee uiteinden, dus de graden tellen op tot twee keer het aantal kanten: Σ deg(v) = 2|E| (het handenschudlemma). Het aantal hoekpunten met oneven graad is daarom even. Kn heeft n(n − 1)/2 kanten, een k-reguliere graaf op n hoekpunten heeft nk/2, en een boom op n hoekpunten heeft n − 1 kanten.
Adjacentiematrix
A: 0 1 0 0 0
B: 1 0 1 1 1
C: 0 1 0 0 1
D: 0 1 0 0 1
E: 0 1 1 1 0
Gemeenschappelijke buren
(M²)CA = 0·0 + 1·1 + 0·0 + 0·0 + 1·0 = 1
Antwoord
N = 1
7.Getaltheorie & modulair rekenen
Antwoord: 13−1 mod 17 = 4
Inversen en congruenties: a heeft een inverse modulo n precies als ggd(a, n) = 1. Het uitgebreide algoritme van Euclides schrijft 1 = s·n + t·a, en dan is a⁻¹ ≡ t (mod n). Een congruentie a·x ≡ b (mod n) met ggd(a, n) = 1 heeft de oplossing x ≡ a⁻¹·b. Twee congruenties x ≡ r₁ (mod m₁) en x ≡ r₂ (mod m₂) met onderling ondeelbare moduli hebben één oplossing modulo m₁·m₂ (Chinese reststelling). Eulers φ(n) telt de getallen van 1 tot n die onderling ondeelbaar zijn met n: φ(n) = n·∏(1 − 1/p).
Uitgebreid algoritme van Euclides
Elke rest r wordt geschreven als r ≡ t·13 (mod 17).
r = 17, t = 0
r = 13, q = 1, t = 1
r = 4, q = 3, t = −1
r = 1, q = 4, t = 4
Inverse
1 ≡ 4·13 (mod 17)
x = 4
controle: 13·4 = 52 = 3·17 + 1
Antwoord
13−1 mod 17 = 4
8.Getaltheorie & modulair rekenen
Antwoord: d = 893
Modulaire machten en RSA: bereken aᵏ mod n door herhaald kwadrateren: schrijf k binair, kwadrateer, reduceer na elke stap en vermenigvuldig de machten waarvan de bit 1 is. Fermat: aᵖ⁻¹ ≡ 1 (mod p) voor een priemgetal p dat a niet deelt, dus de exponent kan modulo p − 1 gereduceerd worden. RSA: kies priemgetallen p en q, n = p·q en φ(n) = (p − 1)(q − 1); de publieke exponent e is onderling ondeelbaar met φ(n), en de privé-exponent is d = e⁻¹ mod φ(n). Versleutel met c = mᵉ mod n en ontsleutel met m = cᵈ mod n.