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
Is (r → p) → (p → r) een tautologie, een contradictie of een contingentie? Klik op je antwoord.
(r → p) → (p → r)
1tautologie
2contradictie
3contingentie
2.Propositielogica & bewijzenMoeilijk
Welke uitspraak is equivalent met ¬∀x (F(x) → ∃y R(x, y)), met de ontkenning helemaal naar binnen geschoven? Klik erop.
¬∀x (F(x) → ∃y R(x, y))
1∀x (F(x) ∧ ∀y ¬R(x, y))
2∃x (F(x) → ∀y ¬R(x, y))
3∃x (¬F(x) ∧ ∃y R(x, y))
4∃x (F(x) ∧ ∀y ¬R(x, y))
3.Verzamelingen, relaties & functiesGemiddeld
Elk getal in het venndiagram is het aantal elementen in dat gebied. Bepaal |(C ∩ B) ∪ (B′ ∩ C′)|.
|U| = 50
|(C ∩ B) ∪ (B′ ∩ C′)| =
4.Verzamelingen, relaties & functiesMoeilijk
De functies f en g op {1, 2, 3, 4, 5} zijn gegeven door hun tabellen. Bepaal (f ∘ g)(5).
Een boom heeft 4 hoekpunten van graad 3, en al zijn andere hoekpunten zijn bladeren (graad 1). Hoeveel bladeren L heeft hij?
4 × deg 3
L =
6.GrafentheorieMoeilijk
Het algoritme van Kruskal bouwt een minimaal opspannende boom. Klik op de kant die het toevoegt als kant nummer 6; overgeslagen kanten tellen niet mee.
k = 6
1kant AB
2kant AC
3kant BC
4kant BD
5kant CE
6kant DE
7kant DF
8kant GB
9kant GC
10kant GD
11kant GE
7.Getaltheorie & modulair rekenenGemiddeld
Vind de inverse van 3 modulo 11: het getal x met 0 < x < 11 en 3·x ≡ 1 (mod 11).
a = 3n = 11
3−1 mod 11 =
8.Getaltheorie & modulair rekenenMoeilijk
Los 78x ≡ 12 (mod 84) op. Geef de kleinste positieve oplossing x.
78x ≡ 12 (mod 84)
x =
3Oplossingen
1.Propositielogica & bewijzen
Antwoord: contingentie
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).
Waarheidstabel rij voor rij
p = 1, r = 1: r → p = 1, p → r = 1, (r → p) → (p → r) = 1
p = 1, r = 0: r → p = 1, p → r = 0, (r → p) → (p → r) = 0
p = 0, r = 1: r → p = 0, p → r = 1, (r → p) → (p → r) = 1
p = 0, r = 0: r → p = 1, p → r = 1, (r → p) → (p → r) = 1
Classificeer
(r → p) → (p → r): 1, 0, 1, 1
1 in 3 van de 4 rijen, 0 in de andere: een contingentie.
Antwoord
contingentie
2.Propositielogica & bewijzen
Antwoord: ∃x (F(x) ∧ ∀y ¬R(x, y))
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 (F(x) → ∃y R(x, y)) ≡ ∃x (F(x) ∧ ∀y ¬R(x, y))
Antwoord
∃x (F(x) ∧ ∀y ¬R(x, y))
De andere opties laten een kwantor onveranderd, veranderen de volgorde van de kwantoren, of ontkennen de binnenste formule verkeerd.
3.Verzamelingen, relaties & functies
Antwoord: |(C ∩ B) ∪ (B′ ∩ C′)| = 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|.
Gebieden van de uitdrukking
A′ ∩ B′ ∩ C′: 11
A ∩ B′ ∩ C′: 6
A′ ∩ B ∩ C: 1
A ∩ B ∩ C: 2
Optellen
|(C ∩ B) ∪ (B′ ∩ C′)| = 11 + 6 + 1 + 2 = 20
Antwoord
|(C ∩ B) ∪ (B′ ∩ C′)| = 20
4.Verzamelingen, relaties & functies
Antwoord: (f ∘ g)(5) = 2
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.
Binnenste functie
g(5) = 1
Buitenste functie
f(1) = 2
(f ∘ g)(5) = 2
Antwoord
(f ∘ g)(5) = 2
5.Grafentheorie
Antwoord: L = 6
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 + 12 = 2(L + 4) − 2
L = 6
Antwoord
L = 6
Snelle methode: L = 2 + Σ (d − 2) over de hoekpunten met graad d ≥ 3.
6.Grafentheorie
Antwoord: kant DF
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
1. AC (3)
2. AB (4)
3. GC (5)
4. GD (6)
5. GE (10)
6. DF (18)
kantnummer 6
DF
Antwoord
kant DF
7.Getaltheorie & modulair rekenen
Antwoord: 3−1 mod 11 = 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·3 (mod 11).
r = 11, t = 0
r = 3, q = 3, t = 1
r = 2, q = 1, t = −3
r = 1, q = 2, t = 4
Inverse
1 ≡ 4·3 (mod 11)
x = 4
controle: 3·4 = 12 = 1·11 + 1
Antwoord
3−1 mod 11 = 4
8.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).