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
Welke formule is logisch equivalent met ¬(q ↔ p)? Klik erop.
¬(q ↔ p)
1q ↔ ¬p
2q ∧ ¬p
3¬q ∨ ¬p
4¬q ↔ ¬p
2.Propositielogica & bewijzenMoeilijk
De premissen r → p; r zijn gegeven. Welke conclusie volgt eruit? Klik erop.
r → pr
1¬p
2r ∧ ¬p
3¬r
4p
3.Verzamelingen, relaties & functiesGemiddeld
Uit een enquête onder 37 mensen blijkt dat 20 een laptop (L) hebben, 12 een tablet (T) en 13 een smartwatch (W). 5 hebben L en T, 8 hebben L en W, 4 hebben T en W, en 3 hebben alle drie. Hoeveel zitten in precies één van de drie verzamelingen? Noem het aantal n.
|U| = 37
n =
4.Verzamelingen, relaties & functiesMoeilijk
Hoeveel injectieve (één-op-één) functies f: A → B zijn er als |A| = 2 en |B| = 4? Noem het aantal N.
|A| = 2|B| = 4
N =
5.GrafentheorieGemiddeld
Heeft de samenhangende graaf een Eulercircuit, een Eulerpad dat geen circuit is, of geen van beide? Klik op je antwoord.
|V| = 5|E| = 6
1Eulercircuit
2Eulerpad, geen circuit
3geen van beide
6.GrafentheorieMoeilijk
Bepaal het totale gewicht W van een minimaal opspannende boom van de gewogen graaf.
|V| = 6|E| = 9
W =
7.Getaltheorie & modulair rekenenGemiddeld
Los 52x ≡ 21 (mod 67) op. Geef de oplossing x met 0 < x < 67.
52x ≡ 21 (mod 67)
x =
8.Getaltheorie & modulair rekenenMoeilijk
Een RSA-sleutel gebruikt de priemgetallen p = 17 en q = 31 en de publieke exponent e = 23. Bepaal de privé-exponent d (0 < d < φ(n)).
p = 17q = 31e = 23
d =
3Oplossingen
1.Propositielogica & bewijzen
Antwoord: q ↔ ¬p
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).
De wet
¬(a ↔ b) is precies 1 als a en b verschillen, wat a ↔ ¬b is.
¬(q ↔ p) ≡ q ↔ ¬p
Controleer met de waarheidstabel
p = 1, q = 1: 0 | 0 0 0 1
p = 1, q = 0: 1 | 1 0 1 0
p = 0, q = 1: 1 | 1 1 1 0
p = 0, q = 0: 0 | 0 0 1 1
Antwoord
q ↔ ¬p
De kolommen na de streep zijn de opties in de getoonde volgorde.
2.Propositielogica & bewijzen
Antwoord: p
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.
Rijen met alle premissen waar
p = 1, r = 1: ¬p = 0, r ∧ ¬p = 0, ¬r = 0, p = 1
Conclusie
p (modus ponens)
Antwoord
p
3.Verzamelingen, relaties & functies
Antwoord: n = 20
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|.
Midden en paren
L ∩ T ∩ W: 3
L ∩ T alleen: 5 − 3 = 2
L ∩ W alleen: 8 − 3 = 5
T ∩ W alleen: 4 − 3 = 1
Losse verzamelingen
L alleen: 20 − 2 − 5 − 3 = 10
T alleen: 12 − 2 − 1 − 3 = 6
W alleen: 13 − 5 − 1 − 3 = 4
Antwoord
10 + 6 + 4 = 20
Antwoord
n = 20
4.Verzamelingen, relaties & functies
Antwoord: N = 12
Functies en tellen: een functie f: A → B geeft elk element van A precies één beeld in B. f is injectief (één-op-één) als verschillende elementen verschillende beelden hebben, surjectief (op) als elk element van B een beeld is, en bijectief als beide gelden. Met |A| = m en |B| = n zijn er nᵐ functies, n!/(n − m)! injectieve (m ≤ n), en met inclusie–exclusie Σ (−1)ᵏ·C(n, k)·(n − k)ᵐ surjectieve. |𝒫(A)| = 2ᵐ en |A × B| = m·n.
Tellen
N = 4!/(4 − 2)! = 12
Antwoord
N = 12
5.Grafentheorie
Antwoord: Eulerpad, geen circuit
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.
Het Eulerpad begint bij het ene oneven hoekpunt en eindigt bij het andere.
6.Grafentheorie
Antwoord: W = 29
Kortste paden en opspannende bomen: het algoritme van Dijkstra legt per ronde één hoekpunt vast: het onafgehandelde hoekpunt met de kleinste voorlopige afstand. Zijn afstand is dan definitief, en elke buur v krijgt d(v) = min(d(v), d(u) + w(u, v)). Het algoritme van Kruskal bouwt een minimaal opspannende boom door de kanten van licht naar zwaar te nemen en elke kant over te slaan die een cykel zou sluiten; het algoritme van Prim laat één boom groeien vanuit een beginpunt door steeds de lichtste kant toe te voegen die eruit vertrekt. Een opspannende boom van n hoekpunten heeft n − 1 kanten.
Het algoritme van Kruskal
AB (2): nemen
BC (3): nemen
BE (5): nemen
DE (6): nemen
AC (8): overslaan, sluit een cykel
CE (9): overslaan, sluit een cykel
DF (13): nemen
Totaal gewicht
W = 2 + 3 + 5 + 6 + 13 = 29
Antwoord
W = 29
7.Getaltheorie & modulair rekenen
Antwoord: x = 12
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).
Inverse van 52
r = 67, t = 0
r = 52, q = 1, t = 1
r = 15, q = 3, t = −1
r = 7, q = 2, t = 4
r = 1, q = 7, t = −9
52−1 ≡ 58 (mod 67)
Oplossen
x ≡ 58·21 = 1218 ≡ 12 (mod 67)
controle: 52·12 = 624 ≡ 21 (mod 67)
Antwoord
x = 12
8.Getaltheorie & modulair rekenen
Antwoord: d = 167
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.