Discrete Wiskunde
Inhoud
Introductie ........................................................................................................................................................ 6
Gebruikte Notatie (algemeen) ..................................................................................................................... 6
Vergelijkingen en ongelijkheden .............................................................................................................. 6
Bewerkingen en rekenen ......................................................................................................................... 7
Verzamelingen.......................................................................................................................................... 8
Bekende getallen en verzamelingen ........................................................................................................ 9
Gebruikte Notatie (discrete wiskunde) ........................................................................................................ 9
Getallen .......................................................................................................................................................... 10
Getallenstelsels .......................................................................................................................................... 10
Decimaal ................................................................................................................................................. 10
Binair ...................................................................................................................................................... 10
Octaal ..................................................................................................................................................... 10
Hexadecimaal ......................................................................................................................................... 11
Omrekenen tussen getallenstelsels ........................................................................................................... 12
Decimaal naar binair .............................................................................................................................. 12
Binair terugrekenen naar decimaal........................................................................................................ 12
Binair naar octaal ................................................................................................................................... 13
Binair naar hexadecimaal ....................................................................................................................... 13
Bewerkingen op getallen ........................................................................................................................... 15
Geslotenheid .......................................................................................................................................... 15
Commutativiteit ..................................................................................................................................... 15
associativiteit ......................................................................................................................................... 15
Rationale getallen (ℚ) ................................................................................................................................ 15
Afronden .................................................................................................................................................... 16
Floor ....................................................................................................................................................... 16
Ceiling ..................................................................................................................................................... 16
Div en Mod (modulo) ................................................................................................................................. 16
Div........................................................................................................................................................... 16
Mod ........................................................................................................................................................ 16
Getaltheorie ............................................................................................................................................... 17
Verschil tussen delers en echte delers ................................................................................................... 17
, Priemgetallen ......................................................................................................................................... 17
Proposities ...................................................................................................................................................... 18
Propositie ................................................................................................................................................... 18
Voorbeelden van propositie: ................................................................................................................. 18
Operatoren ................................................................................................................................................. 19
Andere operatoren................................................................................................................................. 19
Negatie ¬p .............................................................................................................................................. 19
Conjunctie (en), p ∧ q............................................................................................................................. 19
Disjunctie (of), p ∨ q ............................................................................................................................... 19
Equivalentie p ⟷ q ................................................................................................................................ 20
Implicatie p q ..................................................................................................................................... 20
Conjunctie, disjunctie, implicatie, equivalentie samen ............................................................................. 21
Waarheidstabellen ..................................................................................................................................... 22
Aantal rijen bepalen ............................................................................................................................... 22
Tautologie / Contradictie / Contingentie: .................................................................................................. 23
Absurditeit .............................................................................................................................................. 23
Herschrijfregels .......................................................................................................................................... 24
Bit operatoren ............................................................................................................................................ 26
Bitwise & (and) ....................................................................................................................................... 26
Bitwise | (or) .......................................................................................................................................... 26
Predikaten ...................................................................................................................................................... 27
Notatie predikaat: ...................................................................................................................................... 27
Domein van variabelen .......................................................................................................................... 27
Van predicaat naar propositie (binden) ..................................................................................................... 29
Toekennen van een waarde ................................................................................................................... 29
Binding met behulp van een kwantor .................................................................................................... 29
Universele Kwantor (geldt het voor alle) ....................................................................................... 30
Existentiële kwantor (bestaat er in ieder geval 1 waarvoor het geldt) ......................................... 30
Gebonden en vrije variabelen ................................................................................................................ 31
Predikaat met meerdere variabelen ...................................................................................................... 31
Opdracht ................................................................................................................................................ 33
Ontkenningen ......................................................................................................................................... 33
Leren lezen van predikaat in tekst ......................................................................................................... 34
Verzamelingen................................................................................................................................................ 36
Speciale verzamelingen: ......................................................................................................................... 36
Specificatie ................................................................................................................................................. 37
Expliciete specificatie ............................................................................................................................. 37
, Impliciete specificatie............................................................................................................................. 37
Venn diagrammen .................................................................................................................................. 38
Gelijkheid.................................................................................................................................................... 38
Deelverzamelingen..................................................................................................................................... 39
deelverzameling ().............................................................................................................................. 39
Superset () .......................................................................................................................................... 39
Strikte (echte) deelverzameling ()...................................................................................................... 39
Belangrijke deelverzamelingrelatie ........................................................................................................ 40
Lege verzameling.................................................................................................................................... 40
Voorbeeld opgave: ................................................................................................................................. 40
Machtsverzameling ( 𝒫 ) ............................................................................................................................ 42
Eigenschappen machtsverzameling ....................................................................................................... 43
Voorbeeldopdracht ................................................................................................................................ 43
Operatoren ................................................................................................................................................. 44
Vereniging .............................................................................................................................................. 44
Doorsnede .............................................................................................................................................. 44
Verschil ................................................................................................................................................... 44
Complement ........................................................................................................................................... 44
Disjunct................................................................................................................................................... 44
Bags (multisets) .......................................................................................................................................... 45
Multipliciteit ........................................................................................................................................... 45
Basisverzameling (distinct) ..................................................................................................................... 45
Verzamelingsnotaties ............................................................................................................................. 45
Kardinaliteit ............................................................................................................................................ 45
Subbag .................................................................................................................................................... 45
Vereniging en doorsnede (BAGS!!) ........................................................................................................ 46
Som ......................................................................................................................................................... 46
Verschil ................................................................................................................................................... 46
Relaties ........................................................................................................................................................... 47
Notatie........................................................................................................................................................ 47
Tupel ........................................................................................................................................................... 48
Volgorde van belang: (a, b, c) (a, c, b) ................................................................................................ 48
Tripel, paar ............................................................................................................................................. 48
Cartesisch product .................................................................................................................................. 49
R A² ..................................................................................................................................................... 49
Binaire relaties ........................................................................................................................................... 49
, Grafen......................................................................................................................................................... 50
Begrippen ............................................................................................................................................... 50
Cykel ....................................................................................................................................................... 50
(sterk) Samenhangend / onsamenhangend........................................................................................... 50
Eigenschappen graaf .................................................................................................................................. 51
Reflexief.................................................................................................................................................. 51
Symmetrisch ........................................................................................................................................... 52
Transitief ................................................................................................................................................ 52
Functies .......................................................................................................................................................... 53
Notatie: ...................................................................................................................................................... 53
Eigenschappen van functies; ...................................................................................................................... 53
Terminologie (Domein, codomein en beeld) ............................................................................................. 54
Domein (definitiegebied) ................................................................................................................. 54
Codomein (doelverzameling)........................................................................................................... 54
Beeld....................................................................................................................................................... 54
Eigenschappen van functies ....................................................................................................................... 55
Injectieve functie .................................................................................................................................... 55
Niet injectief ........................................................................................................................................... 55
Surjectieve functies ................................................................................................................................ 55
Bijectie .................................................................................................................................................... 55
Formele taaltheorie ....................................................................................................................................... 56
Talen ........................................................................................................................................................... 56
Syntax vs. Semantiek .............................................................................................................................. 56
Compilerstappen .................................................................................................................................... 57
Alfabet ..................................................................................................................................................... 58
Verzameling woorden ............................................................................................................................ 58
Alfabet , Taal L * ............................................................................................................................ 58
Operatoren ................................................................................................................................................. 59
Concatenatie .......................................................................................................................................... 59
Repetitie en vereniging .......................................................................................................................... 59
Grammatica ................................................................................................................................................ 61
Grammatica G = (H, T, P, Z) .................................................................................................................... 61
Grammatica G genereert taal L(G) ......................................................................................................... 62
Afleidingen ............................................................................................................................................. 62
Contextgevoelig / Contextvrij: ................................................................................................................... 62
Contextgevoelig: .................................................................................................................................... 62
Contextvrij: ............................................................................................................................................. 62
Inhoud
Introductie ........................................................................................................................................................ 6
Gebruikte Notatie (algemeen) ..................................................................................................................... 6
Vergelijkingen en ongelijkheden .............................................................................................................. 6
Bewerkingen en rekenen ......................................................................................................................... 7
Verzamelingen.......................................................................................................................................... 8
Bekende getallen en verzamelingen ........................................................................................................ 9
Gebruikte Notatie (discrete wiskunde) ........................................................................................................ 9
Getallen .......................................................................................................................................................... 10
Getallenstelsels .......................................................................................................................................... 10
Decimaal ................................................................................................................................................. 10
Binair ...................................................................................................................................................... 10
Octaal ..................................................................................................................................................... 10
Hexadecimaal ......................................................................................................................................... 11
Omrekenen tussen getallenstelsels ........................................................................................................... 12
Decimaal naar binair .............................................................................................................................. 12
Binair terugrekenen naar decimaal........................................................................................................ 12
Binair naar octaal ................................................................................................................................... 13
Binair naar hexadecimaal ....................................................................................................................... 13
Bewerkingen op getallen ........................................................................................................................... 15
Geslotenheid .......................................................................................................................................... 15
Commutativiteit ..................................................................................................................................... 15
associativiteit ......................................................................................................................................... 15
Rationale getallen (ℚ) ................................................................................................................................ 15
Afronden .................................................................................................................................................... 16
Floor ....................................................................................................................................................... 16
Ceiling ..................................................................................................................................................... 16
Div en Mod (modulo) ................................................................................................................................. 16
Div........................................................................................................................................................... 16
Mod ........................................................................................................................................................ 16
Getaltheorie ............................................................................................................................................... 17
Verschil tussen delers en echte delers ................................................................................................... 17
, Priemgetallen ......................................................................................................................................... 17
Proposities ...................................................................................................................................................... 18
Propositie ................................................................................................................................................... 18
Voorbeelden van propositie: ................................................................................................................. 18
Operatoren ................................................................................................................................................. 19
Andere operatoren................................................................................................................................. 19
Negatie ¬p .............................................................................................................................................. 19
Conjunctie (en), p ∧ q............................................................................................................................. 19
Disjunctie (of), p ∨ q ............................................................................................................................... 19
Equivalentie p ⟷ q ................................................................................................................................ 20
Implicatie p q ..................................................................................................................................... 20
Conjunctie, disjunctie, implicatie, equivalentie samen ............................................................................. 21
Waarheidstabellen ..................................................................................................................................... 22
Aantal rijen bepalen ............................................................................................................................... 22
Tautologie / Contradictie / Contingentie: .................................................................................................. 23
Absurditeit .............................................................................................................................................. 23
Herschrijfregels .......................................................................................................................................... 24
Bit operatoren ............................................................................................................................................ 26
Bitwise & (and) ....................................................................................................................................... 26
Bitwise | (or) .......................................................................................................................................... 26
Predikaten ...................................................................................................................................................... 27
Notatie predikaat: ...................................................................................................................................... 27
Domein van variabelen .......................................................................................................................... 27
Van predicaat naar propositie (binden) ..................................................................................................... 29
Toekennen van een waarde ................................................................................................................... 29
Binding met behulp van een kwantor .................................................................................................... 29
Universele Kwantor (geldt het voor alle) ....................................................................................... 30
Existentiële kwantor (bestaat er in ieder geval 1 waarvoor het geldt) ......................................... 30
Gebonden en vrije variabelen ................................................................................................................ 31
Predikaat met meerdere variabelen ...................................................................................................... 31
Opdracht ................................................................................................................................................ 33
Ontkenningen ......................................................................................................................................... 33
Leren lezen van predikaat in tekst ......................................................................................................... 34
Verzamelingen................................................................................................................................................ 36
Speciale verzamelingen: ......................................................................................................................... 36
Specificatie ................................................................................................................................................. 37
Expliciete specificatie ............................................................................................................................. 37
, Impliciete specificatie............................................................................................................................. 37
Venn diagrammen .................................................................................................................................. 38
Gelijkheid.................................................................................................................................................... 38
Deelverzamelingen..................................................................................................................................... 39
deelverzameling ().............................................................................................................................. 39
Superset () .......................................................................................................................................... 39
Strikte (echte) deelverzameling ()...................................................................................................... 39
Belangrijke deelverzamelingrelatie ........................................................................................................ 40
Lege verzameling.................................................................................................................................... 40
Voorbeeld opgave: ................................................................................................................................. 40
Machtsverzameling ( 𝒫 ) ............................................................................................................................ 42
Eigenschappen machtsverzameling ....................................................................................................... 43
Voorbeeldopdracht ................................................................................................................................ 43
Operatoren ................................................................................................................................................. 44
Vereniging .............................................................................................................................................. 44
Doorsnede .............................................................................................................................................. 44
Verschil ................................................................................................................................................... 44
Complement ........................................................................................................................................... 44
Disjunct................................................................................................................................................... 44
Bags (multisets) .......................................................................................................................................... 45
Multipliciteit ........................................................................................................................................... 45
Basisverzameling (distinct) ..................................................................................................................... 45
Verzamelingsnotaties ............................................................................................................................. 45
Kardinaliteit ............................................................................................................................................ 45
Subbag .................................................................................................................................................... 45
Vereniging en doorsnede (BAGS!!) ........................................................................................................ 46
Som ......................................................................................................................................................... 46
Verschil ................................................................................................................................................... 46
Relaties ........................................................................................................................................................... 47
Notatie........................................................................................................................................................ 47
Tupel ........................................................................................................................................................... 48
Volgorde van belang: (a, b, c) (a, c, b) ................................................................................................ 48
Tripel, paar ............................................................................................................................................. 48
Cartesisch product .................................................................................................................................. 49
R A² ..................................................................................................................................................... 49
Binaire relaties ........................................................................................................................................... 49
, Grafen......................................................................................................................................................... 50
Begrippen ............................................................................................................................................... 50
Cykel ....................................................................................................................................................... 50
(sterk) Samenhangend / onsamenhangend........................................................................................... 50
Eigenschappen graaf .................................................................................................................................. 51
Reflexief.................................................................................................................................................. 51
Symmetrisch ........................................................................................................................................... 52
Transitief ................................................................................................................................................ 52
Functies .......................................................................................................................................................... 53
Notatie: ...................................................................................................................................................... 53
Eigenschappen van functies; ...................................................................................................................... 53
Terminologie (Domein, codomein en beeld) ............................................................................................. 54
Domein (definitiegebied) ................................................................................................................. 54
Codomein (doelverzameling)........................................................................................................... 54
Beeld....................................................................................................................................................... 54
Eigenschappen van functies ....................................................................................................................... 55
Injectieve functie .................................................................................................................................... 55
Niet injectief ........................................................................................................................................... 55
Surjectieve functies ................................................................................................................................ 55
Bijectie .................................................................................................................................................... 55
Formele taaltheorie ....................................................................................................................................... 56
Talen ........................................................................................................................................................... 56
Syntax vs. Semantiek .............................................................................................................................. 56
Compilerstappen .................................................................................................................................... 57
Alfabet ..................................................................................................................................................... 58
Verzameling woorden ............................................................................................................................ 58
Alfabet , Taal L * ............................................................................................................................ 58
Operatoren ................................................................................................................................................. 59
Concatenatie .......................................................................................................................................... 59
Repetitie en vereniging .......................................................................................................................... 59
Grammatica ................................................................................................................................................ 61
Grammatica G = (H, T, P, Z) .................................................................................................................... 61
Grammatica G genereert taal L(G) ......................................................................................................... 62
Afleidingen ............................................................................................................................................. 62
Contextgevoelig / Contextvrij: ................................................................................................................... 62
Contextgevoelig: .................................................................................................................................... 62
Contextvrij: ............................................................................................................................................. 62
