CH 2

BS102
Discrete Mathematics
Chapter 02
Basic Structures
Dr. Ahmed Hagag
Faculty of Computers and Artificial Intelligence
Benha University
Fall 2020
Chapter 2: Basic Structures
• Sets.
• Functions.
• Sequences, and Summations.
• Matrices.
@Ahmed Hagag BS102 Discrete Mathematics 2

Sets (1/24)
A set is an unordered collection of objects .
The objects in a set are called the elements, or

members, of the set. A set is said to contain its
elements.

Sets (2/24)
𝑆 = {𝑎, 𝑏, 𝑐, 𝑑}
We write 𝑎 ∈ 𝑆 to denote that 𝑎 is an element of

the set 𝑆. The notation 𝑒 ∉ 𝑆 denotes that 𝑒 is not
an element of the set 𝑆.

Sets (3/24)
The set 𝑂 of odd positive integers less than 10

can be expressed by 𝑂 = {1, 3, 5, 7, 9}.
The set of positive integers less than 100 can be

denoted by {1, 2, 3, … , 99}.
ellipses (…)

Sets (4/24)
Another way to describe a set is to use set

builder notation.
The set 𝑂 of odd positive integers less than 10

can be expressed by 𝑂 = {1, 3, 5, 7, 9}.

Sets (5/24)

Sets (6/24)
Interval Notation
Closed interval [𝑎, 𝑏]
Open interval (𝑎, 𝑏)
[𝑎, 𝑏] = {𝑥 | 𝑎 ≤ 𝑥 ≤ 𝑏}
[𝑎, 𝑏) = {𝑥 | 𝑎 ≤ 𝑥 < 𝑏}
(𝑎, 𝑏] = {𝑥 | 𝑎 < 𝑥 ≤ 𝑏}
(𝑎, 𝑏) = {𝑥 | 𝑎 < 𝑥 < 𝑏}

Sets (7/24)
If 𝐴 and 𝐵 are sets, then 𝐴 and 𝐵 are equal if and only if

∀𝑥(𝑥 ∈ 𝐴 ↔ 𝑥 ∈ 𝐵). We write 𝐴 = 𝐵, if 𝐴 and 𝐵 are
equal sets.
• The sets {1, 3 , 5} and {3, 5 , 1} are equal, because

they have the same elements.
• {1 , 3 , 3 , 5 , 5 , 5} is the same as the set

{1, 3 , 5} because they have the same elements.

Sets (8/24)
Empty Set
There is a special set that has no elements. This set is
called the empty set, or null set, and is denoted by ∅.
The empty set can also be denoted by { }

Sets (9/24)
Cardinality
The cardinality is the number of distinct elements in 𝑆.
The cardinality of 𝑆 is denoted by 𝑆 .

Sets (10/24)
Example1
𝑆 = {𝑎, 𝑏, 𝑐, 𝑑}
𝑆 =4
𝐴 = {1, 2, 3, 7, 9}
∅=

Sets (10/24)
Example1
𝑆 = {𝑎, 𝑏, 𝑐, 𝑑}
𝑆 =4
𝐴 = {1, 2, 3, 7, 9}
𝐴 =5
∅=
|∅| = 0

Sets (11/24)
Example2
𝑆 = 𝑎, 𝑏, 𝑐, 𝑑, 2
𝑆 =
𝐴 = {1, 2, 3, {2,3}, 9}
𝐴 =
{∅} = { }
∅ =

Sets (11/24)
Example2
𝑆 = 𝑎, 𝑏, 𝑐, 𝑑, 2
𝑆 =5
𝐴 = {1, 2, 3, {2,3}, 9}
𝐴 =5
{∅} = { }
∅ =1

Sets (12/24)
Infinite
A set is said to be infinite if it is not finite.
The set of positive integers is infinite.
𝑍 + = {1,2,3, … }

Sets (13/24)
Subset
The set 𝐴 is said to be a subset of 𝐵 if and only if
every element of 𝐴 is also an element of 𝐵 .
We use the notation 𝐴 ⊆ 𝐵 to indicate that

𝐴 is a subset of the se𝑡 𝐵 .
𝐴 ⊆ 𝐵 ↔ ∀𝑥(𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐵)

Sets (13/24)
Subset
The set 𝐴 is said to be a subset of 𝐵 if and only if
every element of 𝐴 is also an element of 𝐵 .
We use the notation 𝐴 ⊆ 𝐵 to indicate that

𝐴 is a subset of the se𝑡 𝐵 .
(𝑨 ⊆ 𝑩) ≡ (𝑩 ⊇ 𝑨)
𝐴 ⊆ 𝐵 ↔ ∀𝑥(𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐵)

Sets (13/24)
Subset
To show that two sets A and B are equal, show that

𝐴 ⊆ 𝐵 and 𝐵 ⊆ 𝐴.

Sets (14/24)
Proper Subset
The set 𝐴 is a subset of the set 𝐵 but that 𝐴 ≠ 𝐵,
we write 𝐴 ⊂ 𝐵
and say that 𝐴 is a 𝐩𝐫𝐨𝐩𝐞𝐫 𝐬𝐮𝐛𝐬𝐞𝐭 of 𝐵.
𝐴 ⊂ 𝐵 ↔ ∀𝑥 𝑥 ∈ 𝐴 → 𝑥 ∈ 𝐵 ∧ ∃𝑥 𝑥 ∈ 𝐵 ∧ 𝑥 ∉ 𝐴

Sets (15/24)
Example
For each of the following sets,
determine whether 3 is an element of that set.
1,2,3,4
1, 2, 3, 4
1,2, 1,3

Sets (16/24)
Venn Diagram
𝐴 = 1,2,3,4,7
𝐵 = 0,3,5,7,9
𝐶 = 1,2

Sets (17/24)
Venn Diagram
𝐴 = 1,2,3,4,7
𝐵 = 0,3,5,7,9
𝐶 = 1,2 1, 2
3, 7 0, 5, 9
Universal Set

Sets (18/24)
Power Set
𝐓𝐡𝐞 𝐬𝐞𝐭 𝐨𝐟 𝐚𝐥𝐥 𝐬𝐮𝐛𝐬𝐞𝐭𝐬.
If the set is 𝑆. The power set of 𝑆 is denoted by 𝑃(𝑆).

The number of elements in the power set is 2 𝑆

Sets (18/24)
Power Set
𝐓𝐡𝐞 𝐬𝐞𝐭 𝐨𝐟 𝐚𝐥𝐥 𝐬𝐮𝐛𝐬𝐞𝐭𝐬.
If the set is 𝑆. The power set of 𝑆 is denoted by 𝑃(𝑆).

The number of elements in the power set is 2 𝑆
𝑆 = 1,2,3 𝑷 𝑺 = 𝟐𝟑 = 𝟖 𝐞𝐥𝐞𝐦𝐞𝐧𝐭𝐬
𝑃 𝑆 = 2𝑆
= ∅, 1 , 2 , 3 , 1,2 , 1,3 , 2,3 , 1,2,3
Sets (19/24)
Example1

Sets (19/24)
Example1

Sets (20/24)
Example2

Sets (20/24)
Example2

Sets (21/24)
The ordered 𝒏-tuple
The ordered 𝑛-tuple (𝑎1 , 𝑎2 , … , 𝑎𝑛 ) is the ordered

collection that has 𝑎1 as its first element, 𝑎2 as its
second element, … , and 𝑎𝑛 as its 𝑛th element.
In particular, ordered 2-tuples are called ordered

pairs (e.g., the ordered pairs (𝑎, 𝑏))

Sets (22/24)
Cartesian Products
Let 𝐴 and 𝐵 be sets.

The Cartesian product of 𝐴 and 𝐵, denoted by 𝐴 × 𝐵,
is the set of all ordered pairs (𝑎, 𝑏), where 𝑎 ∈ 𝐴 and
𝑏 ∈ 𝐵 . Hence, 𝐴 × 𝐵 = {(𝑎, 𝑏) | 𝑎 ∈ 𝐴 ∧ 𝑏 ∈ 𝐵}.

Sets (22/24)
Cartesian Products - Example
Let 𝐴 = 1,2 , and 𝐵 = 𝑎, 𝑏, 𝑐

𝐴×𝐵= 1, 𝑎 , 1, 𝑏 , 1, 𝑐 , 2, 𝑎 , 2, 𝑏 , 2, 𝑐 .
𝐴×𝐵 = 𝐴 ∗ 𝐵 =2∗3=6

Sets (22/24)
Cartesian Products - Example
Let 𝐴 = 1,2 , and 𝐵 = 𝑎, 𝑏, 𝑐

𝐴×𝐵= 1, 𝑎 , 1, 𝑏 , 1, 𝑐 , 2, 𝑎 , 2, 𝑏 , 2, 𝑐 .
𝐴×𝐵 = 𝐴 ∗ 𝐵 =2∗3=6
Find 𝐵 × 𝐴 ?

Sets (23/24)
The Cartesian product of more than two sets.
The Cartesian product of the sets 𝐴1 , 𝐴2 , … , 𝐴𝑛 ,

denoted by 𝐴1 × 𝐴2 × ⋯ × 𝐴𝑛 , is the set of ordered
𝑛-tuples (𝑎1 , 𝑎2 , … , 𝑎𝑛 ), where 𝑎𝑖 belongs to 𝐴𝑖 for
𝑖 = 1, 2, … , 𝑛. In other words,
𝐴1 × 𝐴2 × ⋯ × 𝐴𝑛 =
𝑎1 , 𝑎2 , … , 𝑎𝑛 𝑎𝑖 ∈ 𝐴𝑖 for 𝑖 = 1, 2, … , 𝑛 .

Sets (24/24)
Example:

Set Operations (1/7)
Union
Let 𝐴 and 𝐵 be sets. The union of the sets A and B ,
denoted by 𝐴 ∪ 𝐵, is the set that contains those
elements that are either in 𝐴 or in 𝐵 , or in both.

Union

Union
The union of the sets {1, 3, 5} and {1, 2, 3}

is the set {1, 2, 3, 5}

Intersection
Let 𝐴 and 𝐵 be sets. The intersection of the sets A and
B , denoted by 𝐴 ∩ 𝐵, is the set that contains those
elements that are in both 𝐴 and 𝐵.

Intersection

Intersection
The intersection of the sets {1, 3, 5} and {1, 2, 3}

is the set {1, 3}

Disjoint
Two sets are called disjoint if their intersection is the

empty set.
𝐴∩𝐵 =∅

Difference
Let 𝐴 and 𝐵 be sets. The difference of 𝐴 and 𝐵 ,

denoted by 𝐴 − 𝐵 , is the set containing those
elements that are in 𝐴 but not in 𝐵.

Difference
Let 𝐴 and 𝐵 be sets. The difference of 𝐴 and 𝐵 ,

denoted by 𝐴 − 𝐵 , is the set containing those
elements that are in 𝐴 but not in 𝐵.
𝐴 = 1,3,5 , 𝐵 = 1,2,3
𝐴−𝐵= 5

Difference

Complement
Let 𝑈 be the universal set.

The complement of the set 𝐴 , denoted by 𝐴ҧ
An element 𝑥 belongs to 𝑈 if and only if 𝑥 ∉ 𝐴.

Complement
Let 𝑈 be the universal set.

The complement of the set 𝐴 , denoted by 𝐴ҧ
An element 𝑥 belongs to 𝑈 if and only if 𝑥 ∉ 𝐴.
𝑈 = 1,2,3,4,5 , 𝐴 = 1,3
𝐴ҧ = 2,4,5

Complement

Generalized Unions

Generalized Unions

Generalized Intersections

Generalized Intersections

Set Identities (1/8)


Example1

Example1 – Answer



Example2

Example2 – Answer

Functions (1/21)
Function
Let 𝐴 and 𝐵 be nonempty sets. A function 𝑓 from 𝐴 to
𝐵 is an assignment of exactly one element of 𝐵 to
each element of 𝐴.
We write 𝑓(𝑎) = 𝑏 if 𝑏 is the unique element of 𝐵

assigned by the function 𝑓 to the element 𝑎 of 𝐴.
If 𝑓 is a function from 𝐴 to 𝐵, we write 𝑓: 𝐴 → 𝐵.

Functions (2/21)
Function

Functions (3/21)
The Function 𝒇: 𝑨 → 𝑩

Functions (3/21)
Domain: 𝐴
Co-Domain: 𝐵
𝑓 𝑎 =𝑏
𝑏 is the image of 𝑎
𝑎 is a preimage of 𝑏
The range, or image, of 𝑓

is the set of all images of
elements of 𝐴.

Functions (4/21)
1 Domain = 𝑎, 𝑏, 𝑐, 𝑑, 𝑒
𝑎 2
𝑏 3 Co-Domain = 1,2,3,4,5,6,7
𝑐 4 Range = {1,3,4,5,7}
𝑑 5
𝑒 6
7
𝑨 → 𝑩

Functions (5/21)
Definition
Let 𝑓1 and 𝑓2 be functions from 𝐴 to R. Then 𝑓1 + 𝑓2 and 𝑓1 𝑓2 are also
functions from 𝐴 to R defined for all 𝑥 ∈ 𝐴 by
𝑓1 + 𝑓2 (𝑥) = 𝑓1 (𝑥) + 𝑓2 (𝑥),
(𝑓1 𝑓2 )(𝑥) = 𝑓1 𝑥 𝑓2 (𝑥).

Functions (6/21)
Example
Let 𝑓1 and 𝑓2 be functions from R to R such that 𝑓1 (𝑥) = 𝑥 2 and
𝑓2 (𝑥) = 𝑥 − 𝑥 2. What are the functions 𝑓1 + 𝑓2 and 𝑓1 𝑓2 ?
𝑓1 + 𝑓2 𝑥 = 𝑓1 𝑥 + 𝑓2 𝑥 = 𝑥 2 + 𝑥 − 𝑥 2 = 𝑥,
𝑓1 𝑓2 𝑥 = 𝑓1 𝑥 𝑓2 𝑥 = 𝑥 2 𝑥 − 𝑥 2 = 𝑥 3 − 𝑥 4.

Functions (7/21)
Definition
Let 𝑓 be a function from 𝐴 to 𝐵 and let 𝑆 be a subset of 𝐴.
The image of 𝑆 under the function 𝑓 is the subset of 𝐵 that consists of
the images of the elements of 𝑆.
We denote the image of 𝑆 by 𝑓(𝑆), so
𝑓 𝑆 = 𝑡 ∃𝑠 ∈ 𝑆 𝑡 = 𝑓 𝑠 .
or shortly {𝑓 𝑠 | 𝑠 ∈ 𝑆}.

Functions (8/21)
Example
Let 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒} and 𝐵 = {1, 2, 3, 4} with 𝑓(𝑎) = 2, 𝑓(𝑏) = 1,
𝑓(𝑐) = 4, 𝑓(𝑑) = 1, and 𝑓(𝑒) = 1.
𝑆 = 𝑏, 𝑐, 𝑑 ⊆ 𝐴
The image of the subset 𝑆 = {𝑏, 𝑐, 𝑑} is the set 𝑓(𝑆) = {1, 4}

Functions (9/21)
One-to-One function (injective)
A function f is said to be one-to-one, or injective,

if and only if f(a) = f(b) implies that a = b for all a and b in the domain
of f.

Functions (9/21)
One-to-One function (injective)
1 𝑓 𝑎 =1
𝑎 2
𝑏 3 𝑓 𝑏 =3
𝑐 4 𝑓 𝑐 =7
𝑑 5
𝑒 6 𝑓 𝑑 =4
7 𝑓 𝑒 =5
𝑨 → 𝑩

Functions (9/21)
NOT One-to-One function (Not injective)
1 𝑓 𝑎 =1
𝑎 2
𝑏 3 𝑓 𝑏 =1
𝑐 4 𝑓 𝑐 =7
𝑑 5
𝑒 6 𝑓 𝑑 =4
7 𝑓 𝑒 =5
𝑨 → 𝑩

Functions (10/21)
onto function (surjective)
A function f from A to B is called onto, or surjective, if and only if for

every element b ∈ B there is an element a ∈ A with f(a) = b.

Functions (10/21)
onto function (surjective)
𝑓 𝑎 =1
𝑎
1
𝑏 𝑓 𝑏 =1
2
𝑐
3 𝑓 𝑐 =4
𝑑
4
𝑒 𝑓 𝑑 =2
Co-Domain = 1,2,3,4
𝑓 𝑒 =3
𝑨 → 𝑩 Range = {1,2,3,4}

Functions (10/21)
NOT onto function (Not surjective)
𝑓 𝑎 =1
𝑎
1
𝑏 𝑓 𝑏 =1
2
𝑐
3 𝑓 𝑐 =4
𝑑
4
𝑒 𝑓 𝑑 =1
Co-Domain = 1,2,3,4
𝑓 𝑒 =3
𝑨 → 𝑩 Range = {1,3,4}

Functions (11/21)
One-to-one correspondence (bijection)
The function f is a one-to-one correspondence, or a bijection, if it is

both one-to-one and onto.

Functions (11/21)
One-to-one correspondence (bijection)

|A| = |B|
𝑓 𝑎 =1
𝑎 1
𝑏 2 𝑓 𝑏 =3
𝑐 3
𝑓 𝑐 =5
𝑑 4
𝑒 5 𝑓 𝑑 =2
Co-Domain = 1,2,3,4,5
𝑓 𝑒 =4
𝑨 → 𝑩 Range = {1,2,3,4,5}

Functions (11/21)
NOT One-to-one correspondence (Not bijection)
𝑓 𝑎 =1
𝑎 1
𝑏 2 𝑓 𝑏 =3 NOT one-to-one
𝑐 3 NOT onto
𝑓 𝑐 =5
𝑑 4
𝑒 5 𝑓 𝑑 =1
Co-Domain = 1,2,3,4,5
𝑓 𝑒 =4
𝑨 → 𝑩 Range = {1,3,4,5}

Functions (11/21)
𝑓 𝑎 =1
𝑎 1
𝑏 2 𝑓 𝑏 =2 Onto
𝑐 3
𝑓 𝑐 =3 NOT one-to-one
𝑑 4
𝑒 𝑓 𝑑 =1
Co-Domain = 1,2,3,4
𝑓 𝑒 =4
𝑨 → 𝑩 Range = {1,2,3,4}

Functions (11/21)
𝑓 𝑎 =1
𝑎 1
𝑏 2 𝑓 𝑏 =3 One-to-one
𝑐 3 NOT onto
𝑓 𝑐 =5
𝑑 4
5 𝑓 𝑑 =2
Co-Domain = 1,2,3,4,5
𝑨 → 𝑩 Range = {1,2,3,5}

Functions (12/21)
Examples
𝑨 → 𝑩

Functions (12/21)
Examples
One-to-one
NOT onto
𝑨 → 𝑩

Functions (12/21)
Examples
𝑨 → 𝑩

Functions (12/21)
Examples
NOT One-to-one
Onto
𝑨 → 𝑩

Functions (12/21)
Examples
𝑨 → 𝑩

Functions (12/21)
Examples
One-to-one
Onto
∴ bijection
𝑨 → 𝑩

Functions (12/21)
Examples
𝑨 → 𝑩

Functions (12/21)
Examples
NOT One-to-one
NOT Onto
𝑨 → 𝑩

Functions (12/21)
Examples
𝑨 → 𝑩

Functions (12/21)
Examples
NOT a function
from 𝑨 to 𝑩
𝑨 → 𝑩

Functions (13/21)
Examples
Determine whether the function 𝑓 𝑥 = 𝑥 + 1 from the set of integers

to the set of integers is one-to-one.

Functions (13/21)
Examples (Answer)
Determine whether the function 𝑓 𝑥 = 𝑥 + 1 from the set of integers
to the set of integers is one-to-one.
𝑓 𝑎 = 𝑎 + 1 and 𝑓 𝑏 = 𝑏 + 1
𝑓 𝑥 is one−to−one (if 𝑓 𝑎 = 𝑓 𝑏 and a equal b then).

𝑎+1=𝑏+1
𝑎=𝑏
∴ 𝑓 𝑥 is one−to−one

Functions (14/21)
Examples
Determine whether the function 𝑓(𝑥) = 𝑥 2 from the set of integers to
the set of integers is one-to-one.

Functions (14/21)
Examples (Answer)
Determine whether the function 𝑓(𝑥) = 𝑥 2 from the set of integers to
the set of integers is one-to-one.
𝑓 𝑎 = 𝑎2 and 𝑓 𝑏 = 𝑏2
𝑓 𝑥 is one−to−one (if 𝑓 𝑎 = 𝑓 𝑏 and a equal b then).
𝑎2 = 𝑏2
±𝑎 = ±𝑏
𝑎 may be not equal 𝑏
∴ 𝑓 𝑥 is NOT one−to−one

Functions (15/21)
Inverse Functions
Let f be a one-to-one correspondence from the set A to the set B. The
inverse function of f is the function that assigns to an element b
belonging to B the unique element a in A such that 𝑓(𝑎) = 𝑏. The
inverse function of f is denoted by 𝒇−𝟏. Hence, 𝑓 −1 𝑏 = 𝑎 when
𝑓(𝑎) = 𝑏.

Functions (15/21)
Inverse Functions

Functions (16/21)
Invertible
A one-to-one correspondence is called invertible because we can
define an inverse of this function. A function is not invertible if it is
not a one-to-one correspondence, because the inverse of such a
function does not exist.

Functions (17/21)
Invertible – Example
Let f be the function from 𝑎, 𝑏, 𝑐 to { 1 , 2, 3} such that 𝑓(𝑎) = 2,
𝑓(𝑏) = 3, and 𝑓(𝑐) = 1. Is 𝑓 invertible, and if it is, what is its
inverse?

Functions (17/21)
Invertible – Example
Let f be the function from 𝑎, 𝑏, 𝑐 to {1, 2, 3} such that 𝑓(𝑎) = 2,
𝑓(𝑏) = 3, and 𝑓(𝑐) = 1. Is 𝑓 invertible, and if it is, what is its
inverse?
Answer:
The function 𝑓 is invertible because it is a one-to-one correspondence.
The inverse function 𝑓 −1 reverses the correspondence given by 𝑓, so
𝑓 −1 (1) = 𝑐, 𝑓 −1 (2) = 𝑎, and 𝑓 −1 (3) = 𝑏.

Functions (18/21)
Composition of the Functions f and g

Let g be a function from the set 𝐴 to the set 𝐵 and let f be a function
from the set 𝐵 to the set 𝐶. The composition of the functions f and g,
denoted by 𝑓 ∘ g, is defined by 𝑓 ∘ g 𝑎 = 𝑓 g 𝑎 .

Functions (18/21)
Composition of the Functions f and g

Let g be a function from the set 𝐴 to the set 𝐵 and let f be a function
from the set 𝐵 to the set 𝐶. The composition of the functions f and g,
denoted by 𝑓 ∘ g, is defined by 𝑓 ∘ g 𝑎 = 𝑓 g 𝑎 .
Note that the composition f ∘ g cannot be defined unless the range of g is

a subset of the domain of f .

Functions (19/21)
Composition Example 1
Let g be the function from the set {𝑎 , 𝑏, 𝑐} to itself such that g(a) = b,
g(b) = c, and g(c) = a. Let f be the function from the set {𝑎 , 𝑏 , 𝑐} to
the set { 1 , 2 , 3 } such that f(a) = 3 , f(b) = 2 , and f(c) = 1. What is the
composition of f and g, and what is the composition of g and f ?

Functions (19/21)
Let g be the function from the set {𝑎 , 𝑏, 𝑐} to itself such that g(a) = b,
g(b) = c, and g(c) = a. Let f be the function from the set {𝑎 , 𝑏 , 𝑐} to
the set { 1 , 2 , 3 } such that f(a) = 3 , f(b) = 2 , and f(c) = 1.
Answer:
1) The composition of f and g (i.e., (f ∘ g))
(f ∘g)(a) = 2, (f ∘g)(b) = 1, (f ∘g)(c) = 3
2) The composition of g and f (i.e., (g ∘ f)) cannot be defined
because the range of f is NOT a subset of the domain of g .

Functions (20/21)
Let f and g be the functions from the set of integers to the set of
integers defined by f(x) = 2x + 3 and g(x) = 3x + 2. What is the
composition of f and g? What is the composition of g and f ?

Functions (20/21)
Let f and g be the functions from the set of integers to the set of
integers defined by f(x) = 2x + 3 and g(x) = 3x + 2.
Answer:
1) The composition of f and g (i.e., (f ∘g))
(f ∘g)(x) = 𝑓 𝑔 𝑥 = 2 3𝑥 + 2 + 3 = 6𝑥 + 7
2) The composition of g and f (i.e., (g ∘f))

(g ∘f)(x) = 𝑔 𝑓 𝑥 = 3 2𝑥 + 3 + 2 = 6𝑥 + 11

Functions (21/21)
The Graphs of Functions
Let 𝑓 be a function from 𝐴 to

𝐵. The graph of the function
𝑓 is the set of ordered pairs
{(𝑎, 𝑏)| 𝑎 ∈ 𝐴 and 𝑏 ∈ 𝐵}.

Some Important Functions (1/4)
Floor function 𝒚 = 𝒙

Ceiling function 𝒚 = 𝒙

Useful Properties

Examples
0.5 =
0.5 =
3 =
−0.5 =
−1.2 =
1.1 =
0.3 + 2 =
1.1 + 0.5 =

Examples-Answer
0.5 = 0
0.5 = 1
3 =3
−0.5 = − 0.5 = −1
−1.2 = −1
1.1 = 1
0.3 + 2 = 2
1.1 + 0.5 = 3

Sequences (1/13)
Definition
• A sequence is a set of things (usually numbers) that
are in order.
➢ For example, 1 , 2, 3, 5, 8 is a sequence with five terms and
1, 3, 9, 27, 81, . . . , 30, . . . is an infinite sequence.
• We use the notation 𝑎𝑛 to denote the image of the

integer 𝑛. We call 𝑎𝑛 a term of the sequence.
• We use the notation {𝑎𝑛 } to describe the sequence.

{𝑎𝑛 } = 𝑎1 , 𝑎2 , 𝑎3 , …

Sequences (2/13)
Example
• Consider the sequence {𝑎𝑛 } , where
1
𝑎𝑛 =
𝑛
The list of the terms of this sequence, beginning with 𝑎1 ,
namely,
𝑎1 , 𝑎2 , 𝑎3 , 𝑎4 , … ,
Starts with
1 1 1
1, , , , …
2 3 4
Sequences (3/13)
Geometric
2, 10, 50, 250, …

Sequences (4/13)
Geometric – Example1
𝑎𝑟 𝑛 , 𝑛 = 0,1,2, …
𝑎=1
𝑟 = −1

Sequences (5/13)
𝑎𝑟 𝑛 , 𝑛 = 0,1,2, …
𝑎=2
𝑟=5

Sequences (6/13)
𝑎𝑟 𝑛 , 𝑛 = 0,1,2, …
𝑎=6
𝑟 = 1/3

Sequences (7/13)
Find 𝒂, 𝒓? 𝟑 ∗ 𝟒𝒏 , 𝒏 = 𝟎, 𝟏, 𝟐, …
𝑎𝑟 𝑛 , 𝑛 = 0,1,2, …
𝑎=3
𝑟=4

Sequences (8/13)
Find 𝒂, 𝒓? 𝟑 ∗ 𝟒𝒏 , 𝒏 = 𝟏, 𝟐, 𝟑, …
𝑎 = 12
𝑟=4

Sequences (9/13)
Arithmetic

Sequences (10/13)
Arithmetic – Example1
𝑎 + 𝑛𝑑 , 𝑛 = 0,1,2, …
𝑎 = −1
𝑑=4

Sequences (11/13)
Arithmetic – Example2
𝑎 + 𝑛𝑑 , 𝑛 = 0,1,2, …
𝑎=7
𝑑 = −3

Sequences (12/13)
Notes:
• Are terms obtained from previous terms by adding the
same amount or an amount that depends on the
position in the sequence?
• Are terms obtained from previous terms by
multiplying by a particular amount?
• Are terms obtained by combining previous terms in a
certain way?
• Are there cycles among the terms?

Sequences (13/13)
Fibonacci Sequence
0, 1, 1, 2, 3, 5, 8, …

Summations (1/8)

Summations (1/8)
Here, the index of summation runs through all integers

starting with its lower limit m and ending with its upper
limit n. A large uppercase Greek letter sigma, ∑, is used
to denote summation.

Summations (2/8)
Example 1

Summations (3/8)
Example 1
Answer
100
෍ 1/𝑛
𝑛=1

Summations (4/8)
Example 2

Summations (4/8)
Example 2
Answer

Summations (5/8)
Example 3

Summations (5/8)
Example 3

Summations (6/8)
Example 4

Summations (7/8)
Double Summation
Find

Summations (8/8)
Double Summation
Find

Matrices (1/14)
Definition:
A matrix is a rectangular array of numbers. A matrix
with 𝑚 rows and 𝑛 columns is called an 𝑚 × 𝑛 matrix. A
matrix with the same number of rows as columns is
called square.
1 2

Matrices (1/14)
Definition:
A matrix is a rectangular array of numbers. A matrix
with 𝑚 rows and 𝑛 columns is called an 𝑚 × 𝑛 matrix. A
matrix with the same number of rows as columns is
called square.

Matrices (2/14)
𝒎 × 𝒏 matrix

Matrices (3/14)
𝒎 × 𝒏 matrix
The (2, 1)th element or entry of A is the element 𝒂𝟐𝟏 ,

means 2nd row and 1st column of A.

Matrices (4/14)
Matrix Arithmetic (Sum.)

Let A = [𝑎𝑖𝑗 ] and B = [𝑏𝑖𝑗 ] be 𝑚 × 𝑛 matrices.
The sum of A and B, denoted by A + B, is the 𝑚 × 𝑛
matrix that has 𝑎𝑖𝑗 + 𝑏𝑖𝑗 as its (i, j)th element. In other
words, A + B = [𝑎𝑖𝑗 + 𝑏𝑖𝑗 ].
A B A+B
Matrices (4/14)
Note: matrices of different sizes

Matrix Arithmetic (Sum.) can not be added.
Let A = [𝑎𝑖𝑗 ] and B = [𝑏𝑖𝑗 ] be 𝑚 × 𝑛 matrices.

The sum of A and B, denoted by A + B, is the 𝑚 × 𝑛
matrix that has 𝑎𝑖𝑗 + 𝑏𝑖𝑗 as its (i, j)th element. In other
words, A + B = [𝑎𝑖𝑗 + 𝑏𝑖𝑗 ].
A B A+B
Matrices (5/14)
Matrix Arithmetic (Product/Multiplication)
𝐀 𝒎𝒌 𝐁𝒌𝒏 𝐀𝐁 = 𝐂𝒎𝒏

Matrices (5/14)
Matrix Arithmetic (Product/Multiplication)
𝐀 𝒎𝒌 𝐁𝒌𝒏 𝐀𝐁 = 𝐂𝒎𝒏

Matrices (6/14)
Example1 (1/2)
1 1 2 1 2
𝐀3×3 = 1 2 3 𝐌3×2 = 3 −1
1 3 −1 3×3 1 1 3×2
𝐀3×3 × 𝐌3×2 = 𝐁3×2
1 2
1
1 1 2 1 2 1 2
2 1 2 3 × 3 −1 = 3 −1
3 1 3 −1 1 1 1 1

Matrices (6/14)
Example1 (2/2)
1 1 2 1 2
𝐀3×3 = 1 2 3 𝐌3×2 = 3 −1
1 3 −1 3×3 1 1 3×2
𝐀3×3 × 𝐌3×2 = 𝐁3×2

𝒂𝟏𝟏 = 𝟔
= 𝟏×𝟏+𝟏×𝟑+𝟐×𝟏
1 2
1
1 1 2 1 2 6 3
2 1 2 3 × 3 −1 = 10 3
3 1 3 −1 1 1 9 −2

Matrices (6/14)
Example1 (2/2)
1 1 2 1 2
𝐀3×3 = 1 2 3 𝐌3×2 = 3 −1
1 3 −1 3×3 1 1 3×2
𝐀3×3 × 𝐌3×2 = 𝐁3×2

𝒂𝟑𝟏 = 𝟗
= 𝟏 × 𝟏 + 𝟑 × 𝟑 + (−𝟏) × 𝟏
1 2
1
1 1 2 1 2 6 3
2 1 2 3 × 3 −1 = 10 3
3 1 3 −1 1 1 9 −2

Matrices (7/14)
Example2 (1/2)

Matrices (7/14)
Example2 (2/2)

Matrices (8/14)
Identity matrix (𝐈𝒏 )

The identity matrix of order 𝑛 is the 𝑛 × 𝑛 matrix
𝐈𝑛 = [𝛿𝑖𝑗 ], where 𝛿𝑖𝑗 = 1 if 𝑖 = 𝑗 and 𝛿𝑖𝑗 = 0 if 𝑖 ≠ 𝑗.
1 0 0
𝐈3 = 0 1 0
0 0 1 3×3

Matrices (9/14)
Powers of square matrices (𝐀𝒓 )

Matrices (10/14)
Transpose of 𝐀 (𝐀𝒕 )
Interchanging the rows and columns of 𝐀
𝐀 𝒕
𝐀

Matrices (10/14)
Transpose of 𝐀 (𝐀𝒕 )
Interchanging the rows and columns of 𝐀
𝐀 𝒕
𝐀

Matrices (11/14)
Symmetric
A square matrix 𝐀 is called symmetric if 𝐀 = 𝐀𝒕
𝐀 𝐀𝒕

Matrices (11/14)
Symmetric
A square matrix 𝐀 is called symmetric if 𝐀 = 𝐀𝒕

Matrices (12/14)
Zero–One Matrices
A matrix all of whose entries are either 𝟎 or 𝟏

Matrices (13/14)
join and meet (Zero–One Matrices)
meet
join

Matrices (14/14)
Example (1/3)

Matrices (14/14)
Example (2/3)

Matrices (14/14)
Example (3/3)

Dr. Ahmed Hagag
ahagag@fci.bu.edu.eg

CH 2

Uploaded by

Document Informationclick to expand document information

Document Informationclick to expand document information

Copyright:

Available Formats

CH 2

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CH 2

Uploaded by

Copyright:

Available Formats

BS102

@Ahmed Hagag BS102 Discrete Mathematics 2

A set is an unordered collection of objects .

The objects in a set are called the elements, or

@Ahmed Hagag BS102 Discrete Mathematics 3

We write 𝑎 ∈ 𝑆 to denote that 𝑎 is an element of

@Ahmed Hagag BS102 Discrete Mathematics 4

The set 𝑂 of odd positive integers less than 10

The set of positive integers less than 100 can be

@Ahmed Hagag BS102 Discrete Mathematics 5

Another way to describe a set is to use set

The set 𝑂 of odd positive integers less than 10

@Ahmed Hagag BS102 Discrete Mathematics 6

@Ahmed Hagag BS102 Discrete Mathematics 7

@Ahmed Hagag BS102 Discrete Mathematics 8

If 𝐴 and 𝐵 are sets, then 𝐴 and 𝐵 are equal if and only if

• The sets {1, 3 , 5} and {3, 5 , 1} are equal, because

• {1 , 3 , 3 , 5 , 5 , 5} is the same as the set

@Ahmed Hagag BS102 Discrete Mathematics 9

@Ahmed Hagag BS102 Discrete Mathematics 10

@Ahmed Hagag BS102 Discrete Mathematics 11

@Ahmed Hagag BS102 Discrete Mathematics 12

@Ahmed Hagag BS102 Discrete Mathematics 13

@Ahmed Hagag BS102 Discrete Mathematics 14

@Ahmed Hagag BS102 Discrete Mathematics 15

@Ahmed Hagag BS102 Discrete Mathematics 16

We use the notation 𝐴 ⊆ 𝐵 to indicate that

@Ahmed Hagag BS102 Discrete Mathematics 17

We use the notation 𝐴 ⊆ 𝐵 to indicate that

@Ahmed Hagag BS102 Discrete Mathematics 18

To show that two sets A and B are equal, show that

@Ahmed Hagag BS102 Discrete Mathematics 19

@Ahmed Hagag BS102 Discrete Mathematics 20

@Ahmed Hagag BS102 Discrete Mathematics 21

@Ahmed Hagag BS102 Discrete Mathematics 22

@Ahmed Hagag BS102 Discrete Mathematics 23

If the set is 𝑆. The power set of 𝑆 is denoted by 𝑃(𝑆).

@Ahmed Hagag BS102 Discrete Mathematics 24

If the set is 𝑆. The power set of 𝑆 is denoted by 𝑃(𝑆).

@Ahmed Hagag BS102 Discrete Mathematics 26

@Ahmed Hagag BS102 Discrete Mathematics 27

@Ahmed Hagag BS102 Discrete Mathematics 28

@Ahmed Hagag BS102 Discrete Mathematics 29

The ordered 𝒏-tuple

The ordered 𝑛-tuple (𝑎1 , 𝑎2 , … , 𝑎𝑛 ) is the ordered

In particular, ordered 2-tuples are called ordered

@Ahmed Hagag BS102 Discrete Mathematics 30

Let 𝐴 and 𝐵 be sets.

@Ahmed Hagag BS102 Discrete Mathematics 31

Cartesian Products - Example

Let 𝐴 = 1,2 , and 𝐵 = 𝑎, 𝑏, 𝑐

@Ahmed Hagag BS102 Discrete Mathematics 32

Cartesian Products - Example

Let 𝐴 = 1,2 , and 𝐵 = 𝑎, 𝑏, 𝑐

@Ahmed Hagag BS102 Discrete Mathematics 33

The Cartesian product of more than two sets.

The Cartesian product of the sets 𝐴1 , 𝐴2 , … , 𝐴𝑛 ,