DISCRETE WISKUNDE
INHOUD
Hoofdstuk 1: basisbegrippen ...................................................................................................................................... 1
Hoofdstuk 2: Verzamelingen, relaties en functies ....................................................................................................... 1
Hoofdstuk 3: modulorekenen ..................................................................................................................................... 2
Rekenen in ℤn.................................................................................................................................................................. 2
Elementaire vergelijkingen bij modulorekenen .............................................................................................................. 3
Lineaire Diofantische vergelijkingen ............................................................................................................................... 3
Chinese reststelling ......................................................................................................................................................... 3
Residugetalsysteem (grote getallen) .............................................................................................................................. 4
Hoofdstuk 4: eindige velden ....................................................................................................................................... 5
Toepassingen in cryptografie .......................................................................................................................................... 5
Hoofdstuk 5: logica ..................................................................................................................................................... 6
Propositionele logica ...................................................................................................................................................... 6
Predikatenlogica ............................................................................................................................................................. 6
Bewijsstrategieën ........................................................................................................................................................... 7
Rechtstreeks bewijs .................................................................................................................................................... 7
Bewijs door gevallenonderzoek .................................................................................................................................. 7
Bewijs door contrapositie ........................................................................................................................................... 7
Bewijs uit het ongerijmde ........................................................................................................................................... 7
Bewijs door wiskundige inductie ................................................................................................................................ 7
Handige dingen/bevindingen uit werkcollege ............................................................................................................ 8
Theorie uit oefeningen ............................................................................................................................................... 9
, DiWi 2020-2021
DISCRETE WISKUNDE
HOOFDSTUK 1: BASISBEGRIPPEN
Groep, ring & veld. Verzameling G met binaire operator ◊. Verzameling R met 2 binaire operatoren ◊ en ●.
Groep: gesloten onder ◊, ◊ is associatief, ∃ eenheidselement voor ◊,elk element heeft invers voor ◊
Commutatieve (= abelse) groep: groep waarvoor ook geldt dat ◊ commutatief is.
Ring: zoals abelse groep + minstens 2 elementen, gesloten onder ●, ● associa ef en ● distribu ef t.o.v. ◊.
Commutatieve ring: ring waarvoor geldt: ● is commutatief
Ring met eenheidselement: ring waarvoor geldt: ∃ uniek eenheidselement voor ●
Veld: commutatieve ring met eenheidselement + elk element (≠ 0) heeft een invers voor ●
Galoisveld GF(q): veld van orde q met q priemmacht (q=priemn) bv. GF(5)={0,1,2,3,4} (= een eindig veld)
Eindige groep/ring/veld: waarbij G of R eindig is. Grootte = orde = |G| = #G
Bv. ℤ is een ring en geen veld: er bestaat maar 1 operator waarvoor a ◊ b = 1 = b ◊ a
ℕ={0,1,2,3,…} Natuurlijke getallen gesloten + *, natuurlijke ordening
ℤ={…,-2,-1,0,1,2,…} Gehele getallen gesloten + * - , ring
ℚ={a/b | a ∈ ℤ, b ∈ ℤ, b ≠ 0} Rationale getallen gesloten + * - / , veld, geen discrete ordening
ℂ={a+bi | a,b ∈ ℝ, i² = -1} Complexe getallen gesloten + * - / , veld, voorstellen in vlak
ℤn = {0,1,2,…,n-1}, n ∈ ℕ, n ≥ 2
HOOFDSTUK 2: VERZAMELINGEN, RELATIES EN FUNCTIES
Verzameling is bepaald door zijn (unieke) elementen. Ongeordend. A=B indien zelfde elementen. Cardinaliteit = #A.
Onechte deelverzameling: lege verzameling deelverzameling van A en A deelverzameling van zichzelf.
Echte deelverzameling: alle andere verzamelingen. ⊆ is zowel echt als onecht, ⊂ is echt.
Machtsverzameling = delenverzameling = power set P(A) = {X: X ⊂ A }. Er geldt dat #P(A) = 2#A
Partitie: strikte opsplitsing van A in verschillende verzamelingen
Bv. A = {1,2,3,4,5,6} een mogelijke P = {{2},{1,5},{3,4,6}}
Doorsnede ∩, unie ∪, verschil \ , complement Ac = Ā Wetten van De Morgan van toepassing bij ∩ & ∪
Cartesisch product: A x B = {(a,b) | a ∈ A ∧ b ∈ B} ( koppels van 2), A x B x C x… kan ook
Koppel heeft wel volgorde: (a,b) != (b,a). A x B x C leidt tot triples, met 4 = quadruples, …
Relatie R tussen A en B: R ⊂ A x B aka R: A B.
Domein van R = verzameling van alle punten waaruit pijl vertrekt.
Bereik/codomein van R = verzameling van alle punten waarin een pijl toekomt.
Verzamelingen A en B bevatten evenveel elementen ⇔ er bestaat een bijectie van A naar B of omgekeerd.
Eindig aftelbare verzameling: iedere eindige verzameling is aftelbaar
Oneindig aftelbare verzameling: er bestaat een bijectie met ℕ. <-> overaftelbare verzameling: geen bijectie met ℕ.
R is een partiële orderelatie in V ⇔
R is een totale orderelatie in V als ook voldaan is aan ∀x,y ∈ V: (x,y) ∈ R of (y,x) ∈ R
Als V geordend wordt m.b.v. een totale orderelatie: lineair geordende relatie of ketting.
Strikte orderelatie bekomt men door reflexieve pijlen te verwijderen (-> antireflexief). Bv. > is strikt, ≥ niet
1
INHOUD
Hoofdstuk 1: basisbegrippen ...................................................................................................................................... 1
Hoofdstuk 2: Verzamelingen, relaties en functies ....................................................................................................... 1
Hoofdstuk 3: modulorekenen ..................................................................................................................................... 2
Rekenen in ℤn.................................................................................................................................................................. 2
Elementaire vergelijkingen bij modulorekenen .............................................................................................................. 3
Lineaire Diofantische vergelijkingen ............................................................................................................................... 3
Chinese reststelling ......................................................................................................................................................... 3
Residugetalsysteem (grote getallen) .............................................................................................................................. 4
Hoofdstuk 4: eindige velden ....................................................................................................................................... 5
Toepassingen in cryptografie .......................................................................................................................................... 5
Hoofdstuk 5: logica ..................................................................................................................................................... 6
Propositionele logica ...................................................................................................................................................... 6
Predikatenlogica ............................................................................................................................................................. 6
Bewijsstrategieën ........................................................................................................................................................... 7
Rechtstreeks bewijs .................................................................................................................................................... 7
Bewijs door gevallenonderzoek .................................................................................................................................. 7
Bewijs door contrapositie ........................................................................................................................................... 7
Bewijs uit het ongerijmde ........................................................................................................................................... 7
Bewijs door wiskundige inductie ................................................................................................................................ 7
Handige dingen/bevindingen uit werkcollege ............................................................................................................ 8
Theorie uit oefeningen ............................................................................................................................................... 9
, DiWi 2020-2021
DISCRETE WISKUNDE
HOOFDSTUK 1: BASISBEGRIPPEN
Groep, ring & veld. Verzameling G met binaire operator ◊. Verzameling R met 2 binaire operatoren ◊ en ●.
Groep: gesloten onder ◊, ◊ is associatief, ∃ eenheidselement voor ◊,elk element heeft invers voor ◊
Commutatieve (= abelse) groep: groep waarvoor ook geldt dat ◊ commutatief is.
Ring: zoals abelse groep + minstens 2 elementen, gesloten onder ●, ● associa ef en ● distribu ef t.o.v. ◊.
Commutatieve ring: ring waarvoor geldt: ● is commutatief
Ring met eenheidselement: ring waarvoor geldt: ∃ uniek eenheidselement voor ●
Veld: commutatieve ring met eenheidselement + elk element (≠ 0) heeft een invers voor ●
Galoisveld GF(q): veld van orde q met q priemmacht (q=priemn) bv. GF(5)={0,1,2,3,4} (= een eindig veld)
Eindige groep/ring/veld: waarbij G of R eindig is. Grootte = orde = |G| = #G
Bv. ℤ is een ring en geen veld: er bestaat maar 1 operator waarvoor a ◊ b = 1 = b ◊ a
ℕ={0,1,2,3,…} Natuurlijke getallen gesloten + *, natuurlijke ordening
ℤ={…,-2,-1,0,1,2,…} Gehele getallen gesloten + * - , ring
ℚ={a/b | a ∈ ℤ, b ∈ ℤ, b ≠ 0} Rationale getallen gesloten + * - / , veld, geen discrete ordening
ℂ={a+bi | a,b ∈ ℝ, i² = -1} Complexe getallen gesloten + * - / , veld, voorstellen in vlak
ℤn = {0,1,2,…,n-1}, n ∈ ℕ, n ≥ 2
HOOFDSTUK 2: VERZAMELINGEN, RELATIES EN FUNCTIES
Verzameling is bepaald door zijn (unieke) elementen. Ongeordend. A=B indien zelfde elementen. Cardinaliteit = #A.
Onechte deelverzameling: lege verzameling deelverzameling van A en A deelverzameling van zichzelf.
Echte deelverzameling: alle andere verzamelingen. ⊆ is zowel echt als onecht, ⊂ is echt.
Machtsverzameling = delenverzameling = power set P(A) = {X: X ⊂ A }. Er geldt dat #P(A) = 2#A
Partitie: strikte opsplitsing van A in verschillende verzamelingen
Bv. A = {1,2,3,4,5,6} een mogelijke P = {{2},{1,5},{3,4,6}}
Doorsnede ∩, unie ∪, verschil \ , complement Ac = Ā Wetten van De Morgan van toepassing bij ∩ & ∪
Cartesisch product: A x B = {(a,b) | a ∈ A ∧ b ∈ B} ( koppels van 2), A x B x C x… kan ook
Koppel heeft wel volgorde: (a,b) != (b,a). A x B x C leidt tot triples, met 4 = quadruples, …
Relatie R tussen A en B: R ⊂ A x B aka R: A B.
Domein van R = verzameling van alle punten waaruit pijl vertrekt.
Bereik/codomein van R = verzameling van alle punten waarin een pijl toekomt.
Verzamelingen A en B bevatten evenveel elementen ⇔ er bestaat een bijectie van A naar B of omgekeerd.
Eindig aftelbare verzameling: iedere eindige verzameling is aftelbaar
Oneindig aftelbare verzameling: er bestaat een bijectie met ℕ. <-> overaftelbare verzameling: geen bijectie met ℕ.
R is een partiële orderelatie in V ⇔
R is een totale orderelatie in V als ook voldaan is aan ∀x,y ∈ V: (x,y) ∈ R of (y,x) ∈ R
Als V geordend wordt m.b.v. een totale orderelatie: lineair geordende relatie of ketting.
Strikte orderelatie bekomt men door reflexieve pijlen te verwijderen (-> antireflexief). Bv. > is strikt, ≥ niet
1
