5/23/24, 12:00 PM SST 102 Discrete Mathematic
KENYATTA UNIVERSITY
DIGITAL SCHOOL OF VIRTUAL AND OPEN LEARNING
IN COLLABORATION WITH
SCHOOL OF PURE AND APPLIED SCIENCES
DEPARTMENT OF MATHEMATICS AND ACTUARIAL SCIENCE,
SST102 DISCRETE MATHEMATICS
WRITTEN BY: Dr. Titus Kibua
VETTED BY:Dr. Lydia Njuguna
INTRODUCTION
Welcome to this module. Here you will learn basic concepts of mathematical structures
that are countable or otherwise distinct and are separable. In contrast to real numbers that
have the property of varying smoothly the objects studied in discrete mathematics such as
integers, graphs and statements in logic do not vary smoothly in this way but have
distinct separated values. Discrete mathematics therefore excludes topics in continuous
mathematics such as calculus and analysis. Concepts and notations from discrete
mathematics are useful in studying and describing objects and problems in branches of
computer algorithms, programming languages, cryptography, automated theorem proving
and software development.
DISCRETE MATHEMATICS FLOW CHART
WEEK LESSON
WEEK 0 INTRODUCTION (YOUR CONTEXT, YOUR GOALS, THOUGHTS ABOUT MATHEMATICS)
WEEK 1 THE NOTION OF A SET
WEEK 2 SET OPERATIONS
WEEK 3 RELATIONS
WEEK 4 PARTIAL ORDERINGS
WEEK 5 LATTICES
WEEK 6 BASIC DEFINITIONS AND CONCEPTS OF GROUPS, RINGS AND FIELDS
WEEK 7 BOOLEAN ALGEBRA
WEEK 8 DUALITY
WEEK 9 TRUTH VALUES AND TRUTH TABLES
WEEK 10 TAUTOLOGY
WEEK 11 GRAPHS
WEEK 12 ADJACENCY MATRICES
WEEK 13 & 14 EXAMINATION
OVERVIEW OF THE MODULE
about:blank 1/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
Introduction (Your Context, Your Goals)
This lesson is intended to help you acclimatize learning and create a community of
learners who will motivate each other during the course. You will be required to introduce
yourself to your lecturer and colleagues either physically during a face to face session or
even online before other academic interaction start. This will be at the discretion of
individual universities and lecturers. It will be important to also state your context and
goals as well as what you think about Mathematics. You can also share any experience
that you may have regarding Mathematics.
LESSON ONE introduces the basic language and notation of sets.
LESSON TWO explores the standard set operations including union of sets, intersection
of sets, difference between sets and Venn diagrams.
LESSON THREE considers the relations between objects of the same set or between
objects of two or more sets.
LESSON FOUR introduces partially ordered sets. The use of relations to order some or
all elements of sets.
LESSON FIVE considers partially ordered sets in which every pair of elements has both
a least upper bound and a greatest lower bound.
LESSON SIX touches on basic concepts of groups, rings and fields; algebraic systems
whose structure imitates that of inters
LESSON SEVEN introduces the operations and the rules for working with the set {0, 1} .
LESSON EIGHT explores the interchanging of Boolean sums and products and the
interchanging of 0s and 1s.
LESSON NINE introduces the basic building blocks of logic.
LESSON TEN explores the proposition that is always true.
LESSON ELEVEN introduces graphs; a collection of points and lines between the
points.
LESSON TWELVE explores how adjacency matrices are used in graph theory.
EXAMINATION will bring together the work you have been doing to an end.
Troubleshooting
about:blank 2/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
If you have problems accessing or logging into the system (LMS):
1. Go to the Student Help Desk – https://support.ku.ac.ke/
2. Chat with us at http://chat.ku.ac.ke/
3. Call the Digital school offices at (See our Contacts here)-
http://www.ku.ac.ke/dsvol/contact-us
4. Guides about how to use moodle are available at hhtp://www.ku.ac.ke/dsvol/students
– resources
5. Also use our social media huddles:
Twitter:@KUDigitalSchool
Facebook:@KUDSVOL
MODULE LEARNING OUTCOMES
By the end of this module you will be able to:
1. Use mathematical reasoning.
2. Count or enumerate objects.
3. Work with discrete structures.
4. Use algorithmic thinking.
5. Apply discrete mathematics to almost every conceivable area of study.
COURSE DESCRIPTION
Set Theory: Set algebra, recursive definition of sets, orderings relations. Partially ordered
sets, lattices. The idea of a group, a ring and field. Boolean Algebra. Axiomatic definition
of Boolean algebra, duality and propositional functions, truth values and truth tables and
tautology. Logic: predicate logic, propositional logic, logical reasoning. Networks:
directed and undirected graphs, sub graphs, circuits, paths, cycles, connectivity,
adjacency and incidence matrices. Elements of transport networks.
COURSE REQUIREMENTS
about:blank 3/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
This is a blended learning course that will utilize the flex model. This means that learning
materials and instructions will be given online and the lessons will be self-guided with
the lecturer being available briefly for face to face sessions and support and also on-site
(online) most of the time. Your lecturer will be meeting you face to face to introduce a
lesson and put it into perspective and you will actively participate in your search for
knowledge by undertaking several online activities. This means that some of the 39
instructional hours of the course will be delivered face to face while other lessons will be
taught online through various learner and lecturer activities. It is important for you to
note that one instructional hour is equivalent to two online hours. Three instructional
hours will be needed per week. Out of these, one will be used for face to face contact
with your lecturer (also referred as e-moderator in the online activities) while the other
two instructional hours (translating to four online hours) will be used for online activities
otherwise referred to as e-tivities in the lessons. This will add up to the 5 hours
requirement per lesson earlier mentioned. There are 27 online activities each taking at
least two hours and totaling to 54 online hours. You are advised to follow the topic flow-
chart given so that you cover at least a lesson every week.
You will be required to participate and interact online with your peers and the e-
moderator who in this case is your lecturer. Guidelines for the online activities (which we
shall keep referring to as e-tivities) will be provided whenever there is an e-tivity. Please
note that since the online e-tivities are part of the learning process, they may be graded at
the discretion of your e-moderator. Such grading will however be communicated in the e-
tivity guidelines and feedback given as soon as possible after the e-tivity. The e-tivities
will include but will not be limited to online assessment quizzes, assignments and
discussions. There are also assessment questions that you can attempt at the end of every
lesson to test your understanding of the lesson. The answers are also provided. All the
resources that have been used in this module in form of books and videos are available
under the E – references section after the answers to the questions.
ASSESSMENT
about:blank 4/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
It is important to note that the module has embedded certain learner formative assessment
feedback tools that will enable you gauge your own learning progress. The tools include
online collaborative discussions forums that focus on team learning and personal mastery
and will therefore provide you with peer feedback, lecturer assessment and self-
reflection. You will also be required to do continuous assessment tests that are meant to
assess the application of the skills and knowledge gained during the course. The
continuous assessment tests score in combination with scores for e-tivities (where
graded) will account for 30% of your final examination score with the remaining 70%
coming from a face to face sit-in final written examination that will be guided by the
university examination policy and procedures.
TABLE OF CONTENTS
LESSON 1: THE NOTION OF A SET 8
1.1 Introduction 8
1.2 Lesson Learning Outcomes 8
1.3 Set notation and relations E – tivity 9
1.4 Assessment 10
1.5 Expected Answers 10
1.6 E – references 10
LESSON 2: SET OPERATIONS 11
2.1 Introduction 11
2.2 Lesson Learning Outcomes 11
2.3 Set operations E - tivity 11
2.4 Assessment 12
2.5 Expected Answers 12
2.6 E – references 13
LESSON 3: RELATIONS 14
3.1 Introduction 14
3.2 Lesson Learning Outcomes 14
about:blank 5/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
3.3 Relations E - tivity 14
3.4 Assessment 15
3.5 Expected Answers 16
3.6 E – references 16
LESSON 4: PARTIAL ORDERINGS 16
4.1 Introduction 16
4.2 Lesson Learning Outcomes 16
4.3 Partial orderings E - tivity 17
4.4 Assessment 18
4.5 Expected Answers 18
4.6 E – references 18
LESSON 5: LATTICES 19
5.1 Introduction 19
5.2 Lesson Learning Outcomes 19
5.3 Lattices E - tivity 19
5.4 Assessment 20
5.5 Expected Answers 20
5.6 E – references 21
LESSON 6: BASIC DEFINITIONS AND CONCEPTS OF GROUPS, RINGS AND
FIELDS 21
6.1 Introduction 21
6.2 Lesson Learning Outcomes 21
6.3 Basic definitions and concepts of groups, rings and fields E – tivity 21
6.4 Assessment 23
6.5 Expected Answers 23
6.6 E – references 23
LESSON 7: BOOLEAN ALGEBRA 23
7.1 Introduction 23
7.2 Lesson Learning Outcomes 24
7.3 Boolean algebra E - tivity 24
about:blank 6/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
7.4 Assessment 25
7.5 Expected Answers 26
7.6 E – references 26
LESSON 8: DUALITY 26
8.1 Introduction 26
8.2 Lesson Learning Outcomes 26
8.3 Duality E – tivity 27
8.4 Assessment 28
8.5 Expected Answers 28
8.6 E – references 28
LESSON 9: TRUTH VALUES AND TRUTH TABLES 28
9.1 Introduction 28
9.2 Lesson Learning Outcomes 28
9.3 Truth values and truth tables E – tivity 29
9.4 Assessment 30
9.5 Expected Answers 30
9.6 E – references 30
LESSON 10: TAUTOLOGY 31
10.1 Introduction 31
10.2 Lesson Learning Outcomes 31
10.3 Tautology E - tivity 31
10.4 Assessment 32
10.5 Expected Answers 32
10.6 E – references 33
LESSON 11: GRAPHS 33
11.1 Introduction 33
11.2 Lesson Learning Outcomes 33
11.3 Graphs E - tivity 35
11.4 Assessment 36
11.5 Expected Answers 36
about:blank 7/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
11.6 E – references 36
LESSON 12: ADJACENCY MATRICES 37
12.1 Introduction 37
12.2 Lesson Learning Outcomes 37
12.3 Adjacency matrices E – tivity 38
12.4 Assessment 39
12.5 Expected Answers 40
12.6 E – references 40
LESSON 1
THE NOTION OF A SET
1.1 Introduction
In this lesson you will study the mathematical theory of well determined collections
called sets of objects that are called members or elements of the set.
1.2 Lesson Learning Outcomes
By the end of this lesson, you will be able to;
1.2.1 Define a set.
1.3 SET NOTATION AND RELATIONS
The term set is intuitively understood by most people to mean a collection of objects that
are called the elements of the set. This concept is the starting point on which we will
build more complex ideas. We write a A to denote that a is an element of the set A .
The notation a Adenotes that a is not an element of the set A . The notation a, b, ,c d
represents the set with four elements a, b, c and d . The set V of odd integers less than 10
can be expressed as V 1, 3, 5, 7, 9. Set builder notation: V { x| x is an odd positive
integer less than 10}.Sets can have other sets as members. Let Z 2, 1, 0, 1, 2, ... be
the set of integers, Z 1, 2, 3, ...be the set of positive integers. Then P Z, Z is a
set containing two elements each of which is a set. Two sets are equal if and only if they
have the same elements. A 1, 3, 5and B 3, 5, 1 are equal. Also
C 1, 3, 3, 3, 5, 5, 5 and d 1, 3, 5 are equal. It does not matter how many times an
element is repeated. A is a subset of B notation A B . If A {a , b} then the subsets of
, a, b, a, b . If A a, b then | A | 2 or cardinality of A 2 .
A are
about:blank 8/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
Since has no element, | |0 . You will find more details of set notation and relations
in e-tivity 1.3.
E – tivity 1.3. Set notation and relations
Numbering, pacing and sequencing 1.3
Title Set notation and relations.
Purpose The purpose of the task is to enable you define a set.
Brief summary of overall task Read the book chapter 1(pages 1 – 4) and watch the video in order to be
able to:
1. Define a set.
Spark
Individual task
1. After reading the book pages 1 – 4 and wathing the video:
(a) Define a set.
(b) If A 1, 2and B a, b, c identify the elements of the set
C A B
(c) Determine whether each of these statements is true or false.
(i) 0 (ii) {0}
2. Post your answer in discussion forum 1.3a.
Interaction begins 1. Read at least two posts from your colleagues contribution and putting
netiquette into consideration, positively critique your colleagues answers
with a view to improve them.
2. Taking into consideration the feedback from your colleagues, post in
discussion forum 1.3 your enhanced answers.
about:blank 9/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
E-moderator interventions 1. Ensure that learners are focused on the contents of the discussion.
2. Stimulate further learning and generation of new ideas.
3. Provide feedback on the learning progress.
4. Closing the discussion forum.
Shedule and time This activity should take 3 hours
Next Set operations
1.4 Assessment
1. Define a finite set.
2. For each of the following sets, determine whether 2 is an element of that set.
(a){ x R| x is an integer greater than 1} (b) {{2}, {{2}}}
3. List the members of these sets.
(a) { x| x is a real number such that x 2 1} (b) { x| x is a positive integer less than 12}
1.5 Expected Answers
1. Let S be a set. If there are exactlyn elements in S where n a positive integer is then S is
a finite set.
2. (a) Yes (b) No
3. (a) {1, 1} (b) {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
1.6 E – references
1. Al Doerr and Ken Levasseur (2019). Applied discrete structures. 3rd Edition. Retrieved
from :http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
2. Kenneth H. Rosen. Discrete Mathematics and its applications. 8th Edition. Retrieved
from:http://dl.booktolearn.com/ebooks2/science/mathematics/9781259676512_Discrete_
Mathematics_and_Its_Applications_8th_Edition_6a1e.pdf
3. Video on [Discrete Mathematics] Subsets and power sets: Retrieved on 25th July, 2020
from https://www.youtube.com/watch?v=H5D6EAezsXQ
LESSON 2
SET OPERATIONS
2.1 Introduction
10
about:blank 10/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 11/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 12/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 13/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 14/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 15/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 16/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 17/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 18/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 19/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 20/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 21/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 22/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 23/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 24/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 25/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 26/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 27/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 28/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 29/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 30/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 31/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 32/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 33/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 34/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 35/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 36/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 37/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 38/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 39/40
5/23/24, 12:00 PM SST 102 Discrete Mathematic
about:blank 40/40
