Discrete Mathematics
Eng. Abdimahad M. (Huruuse)
Course Topics
Mathematical
Sets Logic
1 3
Probability
5
6
Graph Theory
2 4
and Trees.
Relations and Counting Theory
Functions
Introduction
Discrete Mathematics
➢ is a branch of mathematics that deals with objects and
values that are distinct, separate, and countable. Unlike
continuous mathematics, discrete mathematics focuses on
elements that do not change smoothly but exist as
individual units.
Introduction
Data can be Descriptive (like "high" or "fast") or Numerical
(numbers).
And Numerical Data can be Discrete or Continuous:
Discrete data is counted,
Continuous data is measured
Introduction
Why study Discrete math?
Applications of Discrete Mathematics
1. Computer Science
❖ Graph Theory: Models networks (internet, communication, social networks).
❖ Boolean Algebra: Basis of digital logic and computer hardware.
❖ Cryptography: Uses prime numbers to secure data (e.g., RSA).
Introduction
Biology
• Genetic Sequencing: Discrete mathematics helps
in mapping genomes by understanding sequences
of DNA and RNA using combinatorial analysis.
• Population Dynamics: Models of population growth
and interaction between species can be analyzed
using differential equations and graph theory.
• Neural Networks: Modeled using graphs, where
neurons are nodes and synapses are edges, helping
in understanding brain structure and function.
Introduction
3. Physics
• Quantum Mechanics: The state space of quantum
systems is discrete; quantum computing
fundamentally relies on discrete mathematics for
its logic.
• Statistical Mechanics: Discrete math is used to
calculate the possible states in systems at
thermodynamic equilibrium.
Introduction
Engineering
• Control Systems: Discrete mathematics is used in designing systems
that manage, command, direct, or regulate the behavior of other
devices or systems.
• Signal Processing: Deals with the analysis and manipulation of
signals that are discretized in time and amplitude.
Introduction
Computer Graphics
• Image Processing: Pixels can be represented as
matrices; operations on these matrices can
modify images and perform tasks such as
enhancing image data or extracting useful
information.
• These examples highlight the wide-reaching
applications of discrete mathematics in solving
practical problems across various scientific and
engineering disciplines.
Introduction to Set Theory
A set is defined as a collection of distinct objects
of the same type or class of objects. The objects
of a set are called elements or members of the
set.
An object can be numbers, alphabets, names,
etc.
Examples of sets are:
A set of rivers of Somalia.
A set of vowels
.
Introduction to Set Theory
We broadly denote a set by the capital letter A, B,
C, etc. while the fundamentals of the set by small
letter a, b, x, y, etc.
If A is a set, and a is one of the elements of A,
then we denote it as a ∈ A. Here the symbol ∈
means -"Element of."
Set Representation
Set Representation
Sets are represented in two forms:-
a) Roster or tabular form: In this form of representation we list all the
elements of the set within braces { } and separate them by commas.
Example: If A= set of all odd numbers less then 10 then in the roster from
it can be expressed as A={ 1,3,5,7,9}.
b) Builder form: In this form of representation we list the properties
fulfilled by all the elements of the set. We note as {x: x satisfies
propertieSet s P}. and read as 'the set of those entire x such that each x has
properties P.'
Example: If B= {2, 4, 8, 16, 32}, then the set builder representation will
be: B={x: x=2n, where n ∈ N and 1≤ n ≥5}
Set Of Numbers
Sets can be classified into many Types of Sets
categories. Some of which are
finite, infinite, subset, universal,
proper, power, singleton set, etc.
2. Infinite Sets:
1. Finite Sets: A set is said to be
finite if it contains exactly n
distinct element where n is a non- A set which is not
negative integer. Here, n is said to finite is called as
be "cardinality of sets." The
cardinality of sets is denoted by
Infinite Sets.
|A|, # A, card (A) or n (A).
3. Subsets: If every element in a set A is
also an element of a set B, then A is called
a subset of B. It can be denoted as A ⊆ B.
Here B is called Superset of A.
Example: If A= {1, 2} and B= {4, 2, 1}
the A is the subset of B or A ⊆ B.
Properties of Subsets:
➢ Every set is a subset of itself.
➢ The Null Set i.e.∅ is a subset of every set.
➢ If A is a subset of B and B is a subset of C, then A will
be the subset of C. If A⊂B and B⊂ C ⟹ A ⊂ C
➢ A finite set having n elements has 2n subsets.
4. Proper Subset: If A is a subset of B and A ≠ B then A
is said to be a proper subset of B. If A is a proper subset of B
then B is not a subset of A, i.e., there is at least one element
in B which is not in A.
Example:
(ii) The null ∅ is a proper subset of
(i) Let A = {2, 3, 4}
every set.
B = {2, 3, 4, 5} 5. Improper Subset: If A is a subset of B and A
= B, then A is said to be an improper subset of B.
A is a proper subset of B.
Example
(i) A = {2, 3, 4}, B = {2, 3, 4}
A is an improper subset of B.
(ii) Every set is an improper subset of itself.
6. Universal Set: If all the sets under investigations are
subsets of a fixed set U, then the set U is called Universal Set.
Example: In the human population studies the universal set
consists of all the people in the world.
7. Null Set or Empty Set: A set having no elements is called
a Null set or void set. It is denoted by∅.
8. Singleton Set: It contains only one element. It is denoted
by {s}. Example: S= {x|x∈N, 7<x<9} = {8}