Dit is de samenvatting van het eerste hoofdstuk van het vak Discrete Wiskunde. In deze samenvatting werd zowel alle informatie uit de slides als bijkomende informatie uit eigen notities en de cursustekst opgenomen.
Hoofdstuk 1: Inleidende begrippen
Logica
Wiskunde is opgebouwd uit logische redeneringen. Wij gebruiken de taal en notatie van de
predicatenlogica om redeneringen neer te schrijven.
• Propositie: een bewering p die ofwel waar, ofwel onwaar is.
• Conjunctie: p ∧ q (”p en q”) en Disjunctie: p ∨ q (”p of q”)
• Implicatie: p ⇒ q (“Als p dan q”)
o Voorbeeld. “x is deelbaar door 10 ⇒ x is even”
• Equivalentie: p ⇔ q (“p is equivalent met q”) betekent (p ⇒ q) ∧ (q ⇒ p)
o Voorbeeld. “n2 even ⇔ n even”
• Negatie: ¬p
o Voorbeeld. “Het regent niet.”
Opmerking:
De negatie van de implicatie is niet hetzelfde als contrapositie!
• Negatie van de implicatie: ¬(p ⇒ q) is equivalent met p ∧ ¬q
• Contrapositie van de implicatie: p ⇒ q is equivalent met ¬q ⇒ ¬p
• Voorbeeld. Om te bewijzen dat “n 2 even ⇒ n even” is het gemakkelijker te bewijzen
dat “n oneven ⇒ n 2 oneven”.
Verzamelingen
Verzamelingen laten toe alle (wiskundige) objecten met dezelfde kenmerken te groeperen of
te verzamelen. Een object uit een gegeven verzameling heet een element.
Voorbeelden
• De verzameling priemgetallen groepeert alle positieve gehele getallen die juist twee
verschillende delers bezitten.
• N = {0, 1, 2, . . .}: de natuurlijke getallen
• Z = {. . . , −3, −2, −1, 0, 1, 2, . . .}: de gehele getallen
• Q = { a/b | a, b ∈ Z ∧ b 6= 0}: de rationale getallen
• R = de reële getallen
• C = {a + bi | a, b ∈ R}: de complexe getallen
N, Z, Q = discrete verzamelingen
R, C = continue verzamelingen
Kwantoren
Sommige uitspraken of eigenschappen zijn geldig voor alle objecten in een gegeven
verzameling. Om dit te noteren gebruiken we de kwantor “voor alle”: ∀.
Voorbeeld. ∀ x ∈ R : x 2 ≥ 0
Het dubbelpunt “:” betekent in een logische uitspraak “geldt”.
1
, Er is ook een kwantor “er bestaat” indien men wil zeggen dat een eigenschap geldt voor
minstens een element in een gegeven verzameling.
Voorbeeld. ∃ x ∈ R : x 2 = x.
Soms wil men benadrukken dat er slechts een element bestaat met de gegeven eigenschap.
Voorbeeld. ∃! 𝑥 ∈ ℝ+ 2
0 ∶ 𝑥 =𝑥
De volgorde van kwantoren heeft belang! Bijvoorbeeld
∀ 𝑥 ∈ ℝ ∶ ∃ 𝑦 ∈ ℝ+ : 𝑥 2 = 𝑦
is waar, terwijl
∃ 𝑦 ∈ ℝ+ ∶ ∀ 𝑥 ∈ ℝ ∶ 𝑥 2 = 𝑦
onwaar is.
Negaties van uitspraken zijn zeer belangrijk. Denk bijvoorbeeld aan het bewijs door
contrapositie.
De negatie van ∀ x ∈ X : p(x) is ∃ x ∈ X : ¬p(x) en de negatie van ∃ x ∈ X : p(x) is ∀ x ∈ X :
¬p(x).
Deelverzamelingen
Indien elk element van een verzameling A ook behoort tot een verzameling B, zeggen we dat
A een deelverzameling is van B of dat B de verzameling A omvat.
Symbolisch:
𝐴⊂𝐵⇔∀𝑎∈𝐴∶𝑎∈𝐵
Ook steeds
• 𝐵⊂𝐵
• 𝜙⊂𝐵
Alle andere deelverzamelingen van B noemen we echte deelverzamelingen van B.
Twee verzamelingen A en B zijn gelijk indien ze dezelfde elementen hebben.
Symbolisch:
(𝐴 ⊂ 𝐵) ∧ (𝐵 ⊂ 𝐴)
Gevolg:
𝐴 ≠ 𝐵 ⇔ (𝐴 ⊄ 𝐵) ∨ (𝐵 ⊄ 𝐴)
De verzameling van alle deelverzamelingen van een gegeven verzameling X noteren we
𝒫(𝑋).
Bewerkingen met verzamelingen
A ∩ B = {x ∈ A | x ∈ B} : Doorsnede
A ∪ B = {x | (x ∈ A) ∨ (x ∈ B)} : Unie
A \ B = {x | (x ∈ A) ∧ (x ∉ B)} : Verschil
2
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper lennyS. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €0,00. Je zit daarna nergens aan vast.
