In previous years many lecturers played a role in the development of the COS1501
(previously COS101S) study material. Our sincere thanks go to Willem Labuschagne,
Martha Pistorius, Biffie Viljoen, Ruth de Villiers and Louise Leenen – some of whom
are no longer lecturers in the School of Computing. We also thank Jeanetta du Preez
for creating the mind map in study unit 1, the diagram for the worked example in
section 1.2.2, and figures 5.1, 5.2 and 5.3 in study unit 5.
This study guide for COS1501 was reviewed and approved by the following team:
ROLE NAME
Director, School of Computing Sheryl Buckley
Educational advice Hentie Wilson
Chair of Committee Hentie Wilson
Academic field specialists Sihem Belabbes
Biffie Viljoen (study units 9 and 10)
Layout format Hentie Wilson
Page layout School of Computing
Printed and published by the University of South Africa, Muckleneuk, Pretoria
ii
,Introduction COS1501/1
CONTENTS
Introduction v
1. What is Discrete Mathematics? v
2. The purpose of the module vi
3. Outcomes of the module vi
4. Syllabus vi
5. How to study this module vii
6. Acknowledgements xiv
Glossary of symbols xv
Study unit 1 The development of numbers systems: Z+, Z≥ and Z 1
1.1 Introduction to the study unit 1
1.2 Positive integers: Z+ 3
1.2.1 Commutative property 4
1.2.2 Associative property 5
1.2.3 Distributive property 6
1.2.4 Multiplicative identity 7
1.3 Non-negative integers: Z≥ 7
1.3.1 The existence of an additive identity 10
1.3.2 Multiplication by zero 10
1.4 Integers: Z 11
1.5 The additive inverse, absolute values and prime numbers 15
1.6 The nine laws for Z≥ 19
1.7 In summary of the study unit 20
Study unit 2 Rational and real numbers: Q and R 21
2.1 Introduction to this study unit 21
2.2 The rational numbers: Q 22
2.3 The 11th law of Q 25
2.4 The real numbers: R 25
2.5 In summary of the study unit 31
Study unit 3 Sets 33
3.1 Introduction to this study unit 33
3.2 Why do set theory? 34
3.3 How do we talk about sets? 34
3.4 How to build new sets from old ones 39
3.5 In summary of the study unit 46
Study unit 4 Proofs involving sets 47
4.1 Venn diagrams 48
4.2 Proofs 53
4.3 Working with (X ∩ Y)ʹand (X ∪ Y)ʹ 57
4.4 The Inclusion-exclusion principle 63
4.5 Proofs on specific sets 67
4.6 In summary of the study unit 68
iii
, Introduction COS1501/1
Study unit 5 Relations 69
5.1 Ordered pairs 70
5.2 Relations 71
5.3 Properties of relations 75
5.4 In summary of the study unit 82
Study unit 6 Special kinds of relation 83
6.1 Order relations 84
6.2 Some comments on proof strategies 89
6.3 Equivalence relations 90
6.4 n-ary relations 96
6.5 Functions 98
6.6 In summary of the study unit 102
Study unit 7 More about functions 103
7.1 Surjective functions 104
7.2 Injective functions 106
7.3 The composition of relations / functions 108
7.4 Bijective functions and inverses 112
7.5 In summary of the study unit 114
Study unit 8 Operations 115
8.1 Binary operations 116
8.2 The properties of binary operations. 119
8.3 Operations on vectors 122
8.4 Operations on matrices 125
8.5 In summary of the study unit 133
Study unit 9 Logic: Truth tables 135
9.1 Statements and connectives 136
9.2 Relationships between statements 145
9.3 In summary of the study unit 149
Study unit 10 Logic: quantifiers, predicates, and proof strategies 151
10.1 Quantifiers and predicates 152
10.2 Proof strategies 159
10.2.1 Direct proof 159
10.2.2 Proof by contradiction (reductio ad absurdum) 160
10.2.3 Proof by contrapositive 160
10.2.4 Proofs involving quantifiers 162
10.2.5 Vacuous proof 164
10.3 In summary of the study unit 165
Appendix A: Index
Appendix B: Bibliography
iv
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through EFT, credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying this summary from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller PotatoArmor. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy this summary for R65,00. You're not tied to anything after your purchase.
