Discrete wiskunde: oefenopgaven en tentamenvragen

De wiskunde van de informatica en van elk bewijs: propositielogica en kwantoren, verzamelingen, relaties en functies, grafen met kortste paden en opspannende bomen, en getaltheorie tot en met RSA. Tentamenvragen vragen om exacte antwoorden, dus een zorgvuldige tabel of tekening telt zwaarder dan een rekenmachine.

Oefen dit vak gratisDit vak oefenenMaak een proeftentamenElke dag 5 gratis opgaven. Geen creditcard nodig.

Samenvattingspakket (pdf)Formuleoverzichten, methodestappen en oefenopgaven met volledige oplossingen, klaar om af te drukken.

Onderwerpen in dit vak

  1. Propositielogica & bewijzenwaarheidstabellen · equivalenties en bewijsmethoden · kwantoren en redeneringenrekenopgaven
  2. Verzamelingen, relaties & functiesvenndiagrammen en deelverzamelingen · inclusie–exclusie en relaties · functies en tellenrekenopgaven
  3. Grafentheoriegraden en kanten · Eulerpaden en bomen · kortste paden en opspannende bomenrekenopgaven
  4. Getaltheorie & modulair rekenenggd en resten · inversen en congruenties · modulaire machten en RSArekenopgaven

Tentamentips voor Discrete wiskunde

  • Schrijf de waarheidstabel of het venndiagram helemaal uit: de meeste fouten komen van een overgeslagen rij of gebied.
  • Om een bewering te weerleggen is één tegenvoorbeeld genoeg; om haar te bewijzen controleer je alle gevallen of geef je een algemeen argument.
  • Reduceer in modulair rekenen na elke stap en houd de resten tussen 0 en n − 1.

Uitgewerkte voorbeelden

Propositielogica & bewijzenMakkelijk
pq¬(p ∨ q) → q11100100

Precies één rij van de waarheidstabel maakt ¬(p ∨ q) → q onwaar. Klik op die rij.

¬(p ∨ q) → q
  1. 1p = 1, q = 1
  2. 2p = 1, q = 0
  3. 3p = 0, q = 1
  4. 4p = 0, q = 0
Hints tonen
  1. a → b is alleen 0 als a = 1 en b = 0. ¬a draait de waarde om. a ∨ b is alleen 0 als beide 0 zijn.
  2. Bepaal eerst het hoofdvoegwoord: wat moeten de twee kanten zijn om de hele formule 0 te maken?
  3. Geef elk deel een eigen kolom: p ∨ q; ¬(p ∨ q); ¬(p ∨ q) → q.
Toon het antwoord en de uitleg

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.

Waarheidstabel rij voor rij

p = 1, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 1, q = 0: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 0, q = 1: p ∨ q = 1, ¬(p ∨ q) = 0, ¬(p ∨ q) → q = 1
p = 0, q = 0: p ∨ q = 0, ¬(p ∨ q) = 1, ¬(p ∨ q) → q = 0

De rij

p = 0, q = 0 → ¬(p ∨ q) → q = 0

Antwoord

p = 0, q = 0
Verzamelingen, relaties & functiesGemiddeld
UMPC

Van 53 eerstejaarsstudenten slaagden er 35 voor Wiskunde (M), 28 voor Natuurkunde (P) en 29 voor Scheikunde (C). 20 slaagden voor M en P, 18 voor M en C, 10 voor P en C, en 6 voor alle drie. Hoeveel zitten in geen van de drie verzamelingen?

|U| = 53

Gevraagd: |(M ∪ P ∪ C)′|

Hints tonen
  1. Vul het venndiagram van het midden naar buiten in: eerst alle drie, dan de paren, dan de losse verzamelingen.
  2. Alleen M en P (niet C): 20 − 6 = 14. Alleen M: 35 − 14 − 12 − 6 = 3.
  3. Minstens één verzameling: 35 + 28 + 29 − 20 − 18 − 10 + 6 = 50.
Toon het antwoord en de stapsgewijze oplossing

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

M ∩ P ∩ C: 6
M ∩ P alleen: 20 − 6 = 14
M ∩ C alleen: 18 − 6 = 12
P ∩ C alleen: 10 − 6 = 4

Losse verzamelingen

M alleen: 35 − 14 − 12 − 6 = 3
P alleen: 28 − 14 − 4 − 6 = 4
C alleen: 29 − 12 − 4 − 6 = 7

Antwoord

|M ∪ P ∪ C| = 50
|(M ∪ P ∪ C)′| = 53 − 50 = 3

Antwoord

|(M ∪ P ∪ C)′| = 3

Zo werkt het oefenen

  • “Dit vak oefenen” mengt opgaven uit al zijn onderwerpen, net als een echt tentamen.
  • Elke opgave heeft nieuwe waarden, zodat je de methode leert in plaats van een antwoord.
  • Kom je vast te zitten? Open eerst een kleine hint en de volledige uitleg pas als je die nodig hebt.
  • Proeftentamens zijn getimed en hebben geen hints, en aan het eind krijg je je score en een volledige bespreking.

Gerelateerde vakken

Basis informaticaDatastructuren en algoritmenCalculus 1Inleiding statistiekWiskunde voor ingenieursStatistiek 2: Inferentiële statistiekDifferentiaalvergelijkingenTechnische wiskunde 2
Oefen dit vak gratisDit vak oefenenMaak een proeftentamenElke dag 5 gratis opgaven. Geen creditcard nodig.