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 ¬c → (b ∨ a) bewijzen met de contrapositie. Welke implicatie bewijs je in plaats daarvan? Klik erop.
¬c → (b ∨ a)
1(b ∨ a) → ¬c
2¬(b ∨ a) → ¬¬c
3¬c ∧ ¬(b ∨ a)
4¬¬c → ¬(b ∨ a)
2.Propositielogica & bewijzenMoeilijk
Welke uitspraak is equivalent met ¬∃x (F(x) → G(x)), met de ontkenning helemaal naar binnen geschoven? Klik erop.
¬∃x (F(x) → G(x))
1∀x (F(x) ∧ ¬G(x))
2∀x (¬F(x) → ¬G(x))
3∃x (F(x) ∧ ¬G(x))
4∀x (F(x) → ¬G(x))
3.Verzamelingen, relaties & functiesGemiddeld
Van 29 eerstejaarsstudenten slaagden er 7 voor Wiskunde (M), 16 voor Natuurkunde (P) en 4 voor beide. Hoeveel zitten in minstens één van de twee verzamelingen?
|U| = 29|M| = 7|P| = 16|M ∩ P| = 4
|M ∪ P| =
4.Verzamelingen, relaties & functiesMoeilijk
Het pijlendiagram toont een functie f: A → B met A = {1, 2} en B = {a, b, c, d, e}. Klik op de beschrijving die bij f past.
f = {(1, a), (2, c)}
1injectief, niet surjectief
2surjectief, niet injectief
3bijectief
4geen van beide
5.GrafentheorieGemiddeld
Hoeveel verschillende Hamiltoncircuits H heeft de volledige graaf K6? Circuits die alleen verschillen in het beginpunt of de richting tellen als hetzelfde.
K6
H =
6.GrafentheorieMoeilijk
Hoeveel gesloten wandelingen van lengte 2 beginnen en eindigen bij C? Een wandeling mag hoekpunten en kanten herhalen. Noem het aantal N.
M = adjacentiematrixL = 2
N =
7.Getaltheorie & modulair rekenenGemiddeld
Bepaal Eulers φ φ(63), het aantal gehele getallen van 1 tot 63 die onderling ondeelbaar zijn met 63.
n = 63 = 32·7
φ(63) =
8.Getaltheorie & modulair rekenenMoeilijk
Los 14x ≡ 22 (mod 30) op. Geef de kleinste positieve oplossing x.
14x ≡ 22 (mod 30)
x =
3Oplossingen
1.Propositielogica & bewijzen
Antwoord: ¬(b ∨ a) → ¬¬c
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 = ¬c, b = b ∨ a
Contrapositie
¬b → ¬a = ¬(b ∨ a) → ¬¬c
Antwoord
¬(b ∨ a) → ¬¬c
De contrapositie is equivalent met de oorspronkelijke uitspraak, dus door haar te bewijzen bewijs je de uitspraak.
2.Propositielogica & bewijzen
Antwoord: ∀x (F(x) ∧ ¬G(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 (F(x) → G(x)) ≡ ∀x (F(x) ∧ ¬G(x))
Antwoord
∀x (F(x) ∧ ¬G(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: |M ∪ P| = 19
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
M ∩ P: 4
M − P: 7 − 4 = 3
P − M: 16 − 4 = 12
(M ∪ P)′: 29 − (3 + 12 + 4) = 10
Antwoord
|M ∪ P| = 19
Antwoord
|M ∪ P| = 19
4.Verzamelingen, relaties & functies
Antwoord: injectief, niet surjectief
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.
Injectief?
elk element van B wordt hoogstens één keer geraakt → injectief
Surjectief?
b, d, e ontvangen geen pijl → niet surjectief
Antwoord
injectief, niet surjectief
Antwoord
injectief, niet surjectief
5.Grafentheorie
Antwoord: H = 60
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 = (6 − 1)!/2 = 120/2 = 60
Antwoord
H = 60
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²)CC = 1·1 + 1·1 + 0·0 + 0·0 + 1·1 = 3
Antwoord
N = 3
7.Getaltheorie & modulair rekenen
Antwoord: φ(63) = 36
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).
Priemfactoren
63 = 32·7
φ-waarde
φ(63) = φ(7)·φ(9) = 6·6 = 36
Antwoord
φ(63) = 36
8.Getaltheorie & modulair rekenen
Antwoord: x = 8
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).