Discrete Wiskunde & Logica
Discrete Mathematics and It’s
Applications
Inhoudsopgave
1 College 1 2
1.1 Proposities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Connectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Tautology, Contradictie en Contigency . . . . . . . . . . . . . 5
1.4 Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Satisfiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 College 2 8
2.1 Propositionele functies . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Validity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Satisfiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 De scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.6 Nested Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . 10
3 College 3 11
3.1 Argumenten . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Rules of inference . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Bewijzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.4 Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.5 Conditional statements . . . . . . . . . . . . . . . . . . . . . . 16
3.6 Bewijs strategie . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4 College 4 19
4.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 Set operations . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3 Set identities . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5 College 5 23
5.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.2 Cardinality of Sets . . . . . . . . . . . . . . . . . . . . . . . . 24
Pagina 1 van 27
,6 College 6 26
6.1 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . 26
1 College 1
1.1 Proposities
Een propositie is een verklarende of mededelende zin die False of True is.
De variabele die we gebruiken voor het opstellen van een propositie zijn p, g, r
en s. Een ware propositie noteren we met T en een onware propositie noteren
we met F .
Samengestelde proposities
Samengestelde proposities zijn proposities die bestaan uit proposities en
connectives. We kunnen voor een samengestelde propositie een waarheidsta-
bel opstellen. Zo’n tabel bestaan uit de mogelijke waarden voor de proposities
in de samengestelde propositie en geeft de uiteindelijk mogelijke waarden van
de samengestelde propositie.
1.2 Connectives
Negation
Negation is de ontkenning van een propositie en noteren we met ¬.
Propositie p: de aarde is rond
Propositie ¬p: de aarde is niet rond
p ¬p
T F
F T
() Pagina 2 van 27
,Conjunction
Conjunction is de samenstelling van twee proposities waar het de één en de
ander is. We noteren conjuncion met ∧.
Propositie p: ik ben thuis
Propositie q: het regent
Propositie p ∧ q: ik ben thuis en het regent
p q p∧q
T T T
T F F
F T F
F F F
Disjunction
Disjunction is de samenstelling van twee proposities waarbij het de één of de
ander is. We noteren disjunction met ∨.
Propositie p: ik ben thuis
Propositie q: het regent
Propositie p ∨ q: ik ben thuis of het regent
p q p∨q
T T T
T F T
F T T
F F F
Exclusive or
Bij disjunctie betekent de ’of’ dat minstens één van de twee condities waar
moet zijn, wil de disjunctie waar zijn. Beiden condities mogen echter ook
waar zijn. Bij de exlusive or mag er echter slechts één van de condities waar
zijn wil de Xor waar zijn. We noteren de exclusive or met ⊕.
() Pagina 3 van 27
, p q p⊕q
T T F
T F T
F T T
F F F
Implication
Implication is de samenstelling van twee proposities waar de proposities af-
hankelijk van elkaar zijn. We noteren implication met →.
Propositie p: ik ben thuis
Propositie q: het regent
Propositie p → q: Als ik thuis ben, dan regent het
p q p→q
T T T
T F F
F T T
F F T
Van een implicatie propositie kunnen we weer nieuwe implicatie/voorwaar-
delijke proposities maken:
Propositie p → q: als ik niet naar de stad ga, dan regent het
De converse van p → q:
q → p: als het regent, dan ga ik niet naar de stad
De inverse van p → q:
¬p → ¬q: als ik naar de stad ga, dan regent het niet
De contrapositive van p → q:
¬q → ¬p: als het niet regent, dan ga ik naar de stad
Biconditional
Biconditional is de samenstelling van twee proposities waarbij de ene nood-
zakelijk en voldoende is voor de ander. We noteren biconditional met ↔.
Propositie p: ik ben thuis
Propositie q: het regent
() Pagina 4 van 27
Discrete Mathematics and It’s
Applications
Inhoudsopgave
1 College 1 2
1.1 Proposities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Connectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Tautology, Contradictie en Contigency . . . . . . . . . . . . . 5
1.4 Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Satisfiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 College 2 8
2.1 Propositionele functies . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Equivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.3 Validity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.4 Satisfiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 De scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.6 Nested Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . 10
3 College 3 11
3.1 Argumenten . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Rules of inference . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.3 Bewijzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.4 Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.5 Conditional statements . . . . . . . . . . . . . . . . . . . . . . 16
3.6 Bewijs strategie . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4 College 4 19
4.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 Set operations . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3 Set identities . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5 College 5 23
5.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5.2 Cardinality of Sets . . . . . . . . . . . . . . . . . . . . . . . . 24
Pagina 1 van 27
,6 College 6 26
6.1 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . 26
1 College 1
1.1 Proposities
Een propositie is een verklarende of mededelende zin die False of True is.
De variabele die we gebruiken voor het opstellen van een propositie zijn p, g, r
en s. Een ware propositie noteren we met T en een onware propositie noteren
we met F .
Samengestelde proposities
Samengestelde proposities zijn proposities die bestaan uit proposities en
connectives. We kunnen voor een samengestelde propositie een waarheidsta-
bel opstellen. Zo’n tabel bestaan uit de mogelijke waarden voor de proposities
in de samengestelde propositie en geeft de uiteindelijk mogelijke waarden van
de samengestelde propositie.
1.2 Connectives
Negation
Negation is de ontkenning van een propositie en noteren we met ¬.
Propositie p: de aarde is rond
Propositie ¬p: de aarde is niet rond
p ¬p
T F
F T
() Pagina 2 van 27
,Conjunction
Conjunction is de samenstelling van twee proposities waar het de één en de
ander is. We noteren conjuncion met ∧.
Propositie p: ik ben thuis
Propositie q: het regent
Propositie p ∧ q: ik ben thuis en het regent
p q p∧q
T T T
T F F
F T F
F F F
Disjunction
Disjunction is de samenstelling van twee proposities waarbij het de één of de
ander is. We noteren disjunction met ∨.
Propositie p: ik ben thuis
Propositie q: het regent
Propositie p ∨ q: ik ben thuis of het regent
p q p∨q
T T T
T F T
F T T
F F F
Exclusive or
Bij disjunctie betekent de ’of’ dat minstens één van de twee condities waar
moet zijn, wil de disjunctie waar zijn. Beiden condities mogen echter ook
waar zijn. Bij de exlusive or mag er echter slechts één van de condities waar
zijn wil de Xor waar zijn. We noteren de exclusive or met ⊕.
() Pagina 3 van 27
, p q p⊕q
T T F
T F T
F T T
F F F
Implication
Implication is de samenstelling van twee proposities waar de proposities af-
hankelijk van elkaar zijn. We noteren implication met →.
Propositie p: ik ben thuis
Propositie q: het regent
Propositie p → q: Als ik thuis ben, dan regent het
p q p→q
T T T
T F F
F T T
F F T
Van een implicatie propositie kunnen we weer nieuwe implicatie/voorwaar-
delijke proposities maken:
Propositie p → q: als ik niet naar de stad ga, dan regent het
De converse van p → q:
q → p: als het regent, dan ga ik niet naar de stad
De inverse van p → q:
¬p → ¬q: als ik naar de stad ga, dan regent het niet
De contrapositive van p → q:
¬q → ¬p: als het niet regent, dan ga ik naar de stad
Biconditional
Biconditional is de samenstelling van twee proposities waarbij de ene nood-
zakelijk en voldoende is voor de ander. We noteren biconditional met ↔.
Propositie p: ik ben thuis
Propositie q: het regent
() Pagina 4 van 27
