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 ¬(p ∧ q)? Klik erop.
¬(p ∧ q)
1¬p ∨ ¬q
2¬p ∧ ¬q
3¬p ∧ q
4¬p ∨ q
2.Propositielogica & bewijzenMoeilijk
In hoeveel van de 16 rijen van de waarheidstabel is ((¬q ↔ p) ∧ q) ↔ ((r ↔ p) ∨ s) waar? Noem dit aantal N.
((¬q ↔ p) ∧ q) ↔ ((r ↔ p) ∨ s)
N =
3.Verzamelingen, relaties & functiesGemiddeld
R = {(1, 1), (2, 1), (2, 3), (3, 1), (3, 2)} is een relatie op {1, 2, 3}. Wat is het kleinste aantal k geordende paren dat aan R moet worden toegevoegd om haar transitief te maken (de grootte van de transitieve afsluiting min |R|)?
R = {(1, 1), (2, 1), (2, 3), (3, 1), (3, 2)}
k =
4.Verzamelingen, relaties & functiesMoeilijk
Een equivalentierelatie R op {1, …, 9} heeft de klassen {2, 7, 8, 9}, {3, 4, 5, 6}, {1}. Hoeveel geordende paren bevat R? Noem het aantal |R|.
{2, 7, 8, 9}{3, 4, 5, 6}{1}
|R| =
5.GrafentheorieGemiddeld
Hoeveel verschillende Hamiltoncircuits H heeft de volledige graaf K4? Circuits die alleen verschillen in het beginpunt of de richting tellen als hetzelfde.
K4
H =
6.GrafentheorieMoeilijk
Hoeveel gesloten wandelingen van lengte 2 beginnen en eindigen bij E? Een wandeling mag hoekpunten en kanten herhalen. Noem het aantal N.
M = adjacentiematrixL = 2
N =
7.Getaltheorie & modulair rekenenGemiddeld
Vind de inverse van 5 modulo 67: het getal x met 0 < x < 67 en 5·x ≡ 1 (mod 67).
a = 5n = 67
5−1 mod 67 =
8.Getaltheorie & modulair rekenenMoeilijk
97 is een priemgetal. Gebruik de kleine stelling van Fermat om 1736991 mod 97 te vinden.
p = 97k = 36991
1736991 mod 97 =
3Oplossingen
1.Propositielogica & bewijzen
Antwoord: ¬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).
De wet
De Morgan: ¬(a ∧ b) ≡ ¬a ∨ ¬b. De ∧ wordt een ∨ en beide delen worden ontkend.
¬(p ∧ q) ≡ ¬p ∨ ¬q
Controleer met de waarheidstabel
p = 1, q = 1: 0 | 0 0 0 1
p = 1, q = 0: 1 | 1 0 0 0
p = 0, q = 1: 1 | 1 0 1 1
p = 0, q = 0: 1 | 1 1 0 1
Antwoord
¬p ∨ ¬q
De kolommen na de streep zijn de opties in de getoonde volgorde.
2.Propositielogica & bewijzen
Antwoord: N = 6
Waarheidstabellen: een formule met n verschillende variabelen heeft 2ⁿ rijen, één voor elke combinatie van waarheidswaarden (1 = waar, 0 = onwaar). Werk van binnen naar buiten en geef elke deelformule een eigen kolom. ¬a draait de waarde om; a ∧ b is alleen 1 als beide 1 zijn; a ∨ b is alleen 0 als beide 0 zijn; a → b is alleen 0 als a = 1 en b = 0; a ↔ b is 1 als beide kanten gelijk zijn.
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.
Toe te voegen paren
{(2, 2), (3, 3)}
Tellen
k = 2
Antwoord
k = 2
4.Verzamelingen, relaties & functies
Antwoord: |R| = 33
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.
Paren per klasse
|R| = 4² + 4² + 1² = 33
Antwoord
|R| = 33
5.Grafentheorie
Antwoord: H = 3
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.
Tellen
H = (4 − 1)!/2 = 6/2 = 3
Antwoord
H = 3
6.Grafentheorie
Antwoord: N = 3
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 1 0 0
B: 1 0 1 1 1
C: 1 1 0 0 1
D: 0 1 0 0 1
E: 0 1 1 1 0
Gemeenschappelijke buren
(M²)EE = 0·0 + 1·1 + 1·1 + 1·1 + 0·0 = 3
Antwoord
N = 3
7.Getaltheorie & modulair rekenen
Antwoord: 5−1 mod 67 = 27
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·5 (mod 67).
r = 67, t = 0
r = 5, q = 13, t = 1
r = 2, q = 2, t = −13
r = 1, q = 2, t = 27
Inverse
1 ≡ 27·5 (mod 67)
x = 27
controle: 5·27 = 135 = 2·67 + 1
Antwoord
5−1 mod 67 = 27
8.Getaltheorie & modulair rekenen
Antwoord: 1736991 mod 97 = 15
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.