The University of Jordan –Aqaba Branch

Ahmed Alsarairah Discrete Mathematics

--------------------------------------------------------------------------------------------------------------------------------------------
2.1 :Basic structure ( sets, Functions ,sequences sums and matrices )
Definition 1: A set is an unordered collection of objects called elements or members of the set.
we can write a  A denote that a is an element of the set A and a  A denote that a is not an
element of the set .

For instance :

1. The set V of all vowels .

2. The set B of all even numbers between 2 and 10

 General sets :

1. N = 1, 2,........ ,natural numbers

2. Z = 0, 1, 2,..... ,Integer numbers

3. Z + = 1, 2,..... ,positive Integer numbers

4. R ,real numbers

5. R + ,positive real numbers

p 
6. Q =  :where p and q belong to Z  , rational numbers
q 

7. , complex numbers.

 we can write the sets by two ways

1. The general form or Roster form

a, b, c,.....


 

2. set builder notation  x : p (x ) 
element discription 
 

 we can write the intervals by the set form

a, b  = x : a  x  b 
( a , b ) = x : a  x  b 
 a , b ) = x : a  x  b 

1
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Definition 2: The sets are equal  they have the same elements
iff

i.e.: A=B  x ( x  A and x  B )

Example 1: which of the following sets are equal

1. A = 2,3,5 , B = 3, 2,5, 2,3, 2

2. A = N , B = Z +  0

Definition 3: The empty set ( Null set ) has no elements and denoted by   ,  .

Venn Diagram : we can use this method to represent the set graphically.

For Example :
1 3 5
1. A = 2,3,5, 7, 6,9 →
7 6 9

Note : By Venn diagram ,the universal set denoted by U

Examples 2: Display the following sets by Venn Diagram

1. A = x : x is the vowels letters 

2. A = x : x is the odd numbers between 0 and 13

2
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
 Subsets and proper subsets

Definition 4 : The set A is a subset of set B  every element of A is also an element of B

A B  x ( x  A and x B )

Definition 5: The set A is a proper subset of set B  every element of A is also an

element of B and A  B .

Example 3: Decide whether  or  could be placed in each blank

1. a, b , c , d  d , c , b , a, f , s 

2. 6,8,3 8, 6,3

Theorem 1: For every set S always
1. S  S 2.   S

Definition 6: The size of a set or the cardinality of a set is denoted by S or n (S) .

Example 4: Find the size of the following sets

1. 2, 4,3, 7 2.   3.   4. 0

Power sets :

Definition 7: Let S be a set ,then the power set of S is the set of all subsets of a set S ,and it is
denoted by p (S) .

Example 5 : Find the power set of the following

1. A = 3, 7

2. B =  
3. C =  

Rule : The size of a power set is 2n , n is the number of elements of S .  n ( P (S ) ) = 2n 

3
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Cartesian Product :

Definition 8 : Let A and B be sets .The Cartesian product of A and B are denoted
by A  B is the set of all order pairs ( a , b ) ,where a  A and b  B .

A  B = ( a , b ) : a  A and b B

Notes :
1. A  B = B  A IF A = B  or A =  or B =  
2. A  B = A . B
3. P (A  B ) = 2 A . B

Example 6 : If A = 2, 4,3 , B = 2, 4 , c = 2, 7 , find

1. A  B =

2. A 2 =

3. A  B c =

Example 7 : If A = 2, 4,3 , B = a,v , d , s  , How many elements are there in

P (A  B )

Example 8 : Explain ,why A  B  c  ( A  B )  c

4
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Truth sets and Quantifiers
The truth set of P (x) is denoted by x  Domain : P (x)
Example : Find the truth set of each predicates when the domain is the set of
integers
1. P (x) : x 3  1 2. q(x) : x3  x

3. P (x) : x 2  3 4. P (x) : x 2  x

5. P (x) : 2x + 1 = 0

Example : List the member of these sets

1. x : x is an integer such that x 2

=2

2. x : x is a real number such that x 2 = 1

5
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Example : Determine in which set 5 is an element
1. 5 , 5 2. 5 , 5 ,5, 5, 5

Example : Determine in which set 5 is an element

1. 5 , 5 2. 5 , 5 ,5, 5, 5

Example : Determine whether each of these statement is true or false

1. 0  2.   0 3. 0  

4.   0 5. 0  0 6. 0  0

Example : what is the cardinality

1. 5 , 5 2. 5 , 5 ,5, 5, 5 3. 5

Example : How many elements in the following

1. p (a, a , b ) 2. p ( p ( ))

6
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Example : Translate each of these quantification into English and determine the
truth set

1. x  R , x 2 = −1

2. x  Z , x 2 = 2

3. x  Z , x 2  0

Question : Determine whether each of these statement is true or false

1. y   y  2.  y    y  3.  y    y 

4. x   x  5. x   x 

Question :Find the power set of the following

1. A = a , 4,5

2. B = 0

3. C =  

7
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
2.2 : Set Operations

we can combine two or more sets in many different ways.

So, we will use the following operations .
❶ The union of the sets A and B denoted by A B ,is the set contains these
elements that are either in A or B or in both . A B = x : x  A  x  B 
❷ The intersection of the sets A and B denoted by A B ,is the set
containing these elements in both . A B = x : x  A  x  B 
❸ The complement of the set A denoted by A c , A is the set of elements
exist out of the set . A c = x : x  A  x  A 
❹ The difference of A and B is also called the complement of B with respect
to A . A − B = A / B = B c = A B c = x : x  A  x  B 
Note : Two sets are disjoint  their intersection is empty .

Example : Let U = 1, 2,,......,10 , A = 2,5,8 , B = even numbers  , C = odd numbers 

,Find
1. A B =

2. ( A B ) C =

3. B c =

8
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Set Identities :

Now, We will prove several identities by many ways .

 For Example :
1. Separately, A  B and B  A
2. Venn Diagram
3. Set builder Notation
4. Member ship table
5. Set identities

 Note : preposition forms

1. x  A   ( x  A )

2. ( x  A )  ( x  B )   ( x  A  x  B )
9
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Example : Prove the following

1. A B = A B

10
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
2. A = A

3. A ( B C ) = ( A B ) ( A C )

4. A A = 

11
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
5. A A = U

6. A  = 

7. A ( B C ) = ( A B ) C

12
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Definition : The intersection and union of a collection of sets are given by
n
A1 A2 ..... An = Ai
i =1
n
A1 A2 ..... An = Ai
i =1
n n
Example : Find Ai , A i for every positive integer i ,if
i =1 i =1

1. A i = 0, i  2. A i = 1, 2,3,...., i 

Definition : (Bit string )

A set of consecutive binary digits representing data in coded form .

Computer Representation of sets
There are many ways to represent sets using a computer one method is :
❶ specify arbitrary ordering of elements of U .
❷ Represent a subset A of U with bit string of length n ,where the ith bit in this
string is 1 and 0 if does not belong to A.

Example : suppose that the universal set is U = 1, 2,3, 4,5, 6, 7,8 ,express each of
the following set with bit strings
1. 1, 2, 7 2. 5

Example : Use the previous example to find the actual set that satisfy the following
0,1, 0, 0, 0, 0,1,1

13
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
2.3 : Functions

Definition : Let A and B be nonempty sets then f (x ) is a function from A to B

 for each element in A exists one image in B .

Note : If f : A → B , then A is a domain and B is a co-domain .

So, for each a  A and f (a) = b ,then f (a) is called range.

Note : f (a) = b  image , a  preimage

Example : Use the following map to find

1. Domain
a
1
2. Range b
2
c
3
d
3. Co-domain

Example : If f : Z → Z and f (x ) = x 2 ,find

1. Domain

2. Range

3. Co-domain

14
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
One to One and Onto functions

Definition : A function f (x ) is 1-1 or injection  f (a) = f (b) implies that

a = b for all a and b .

Definition : A function f (x ) from A to B is called onto or surjection  for

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

Definition : If f (x ) is 1-1 and onto ,the f (x ) is called bijection .

Example : Classify the following to function or not

a 1 1 a 1 a

b 2 2 b 2 b

c 3 3 c 3 c

Example : Classify ,which of the following is 1-1 or onto or both.

a 1 1 a 1 a

b 2 2 b 2 b

c 3 3 c 3 c

15
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Example: Let f (x ) be a function from 1, 2, 7 to a, b, c defined by f (1) = c ,
f (2) = a , f (7) = c , f (1) = b . show that f (x ) is 1-1 and onto.

Example: Let f : Z → Z and f (x ) = x 2 .show that why f (x ) not 1-1 and not
onto.

Example : Display ,why f (x ) is not function ,where f : R → R

1
1. f (x ) = 2. f (x ) = x
x

16
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Inverse Function
−1
If f (a) = b  a = f (b) .

Note : If f (x ) is 1-1 ,then we can find an inverse function

Composition Functions :

Definition : Let f be a function from B to C and g from A to B the

composition function , f and g denoted for all a  A by ( f  g ) (a) = f ( g (a)

g f
A B C

Note : we can use the composition function to find the inverse function .

( f  f ) (x) = x
−1
and (f  f ) (x) = x
−1

Example : Let f : Z → Z and g : Z → Z such that

f (x ) = 3x + 2 , g (x ) = x + 1 . Find ( f  g ) (x)

17
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
The floor (   ) and ceiling (   ) functions or the greatest integer function

Properties : If x  R and n  Z , then

1.  x  = n , n  x  n + 1 , x −1  n  x

2.  x  = n , n  x  n +1 , x  n  x +1

3. x − 1   x    x   x + 1

4.  − x  = −  x  and −  x  =  − x 

5.  x + n  =  x  + n

Example : Find

1. 3 = 2. 3 = 3.  2.7  =

4.  2.7  = 5.  −1.2  = 6.  −1.2  =

 1   5   5  
Example : Find    +     
 2   2   3  

18
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Example : Determine whether each of these functions from Z → Z is 1-1 and
onto (bijection ).

1. f (n ) = n + 1 2. f (n ) = n
2

Example : Determine whether f : Z Z → Z is onto

1. f (n , m ) = m + n 2. f (n , m ) = m 2 + n 4

3. f (n , m ) = m − n

19
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Example : Let S = −1, 0,1 ,find f (S) if
x 
1. f (x) = 3 2. f (x) =  
2

Example : Let g(x) =  x  , find

1. g (0)
−1

2. g (−1, 0,1)
−1

3. g (0  x  1)
−1

20
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
2.4 : Sequences and summation

Definition : A sequence is a function from a subset of the set of integers to a set of S

Note : 1. we use the notation an to denote the image of the integer n .

2. an is called the general term or last term or general formula .

3. The notation of sequence is an  .

Definition : A sequence has two branches

1. Arithmetic seq. 2. Geometric seq.

an = a1 + (n −1)d an = a1.r n −1 , n = 1, 2,...

Where where

a1  The first term or initial term a1  The first term or initial term

d = an +1 − an common difference an +1
d = common ratio
an

Definition : ( recurrence relations)

A recurrence relation for the seq. an  is an equation that expresses an in terms of
one or more previous terms .

Examples : Let an  be a seq. such that an = an −1 + 5 , n = 1, 2,.... and suppose that
ao = 3 ,find a1 = 3 , a2 = 3

21
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Definition :(Fibonacci Seq.)

The Fibonacci seq. f  , f 1 ,.... is defined by the initial condition f  = 0 , f 1 = 1 and

the recurrence relation f n = f n −1 + f n −2 , n = 2,3,... .

Example : Classify the following to Arithmetic or Geometric ,then find the general
form

1- 3, 6,12,.....

1 1 1
2- , , , .....
3 9 27

3- 3, 6, 9,.....

Example : Find the first five terms of the following

an = n an −1 + n 2 an − 2 , a = 1 , a1 = 2

22
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Example : Determine ,if the following seq. an = 3n is a solution of
an = 2an −1 − an −2 , n = 2,3,...

Example : Show that if the seq. an = −n + 2 is a solution of the recurrence relation

an = an −1 + 2an −2 + 2n − 9

Question : Find these terms of the following seq.

1. an = ( −1) + 2
n n
, a3 , a5
n  n 
2. an =   +   , a1 , a6
2 2
23
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Summation :

The summation depends on the type of sequence.

for illustrative :
n
1. The sum of Arithmetic seq. S n = ( 2a + (n − 1)d ) , where
2
n in the number of terms , d is the common difference , a is the first term
2. The sum of geometric seq.
 a.r n +1 − a   a.r n − a 
n
 , r 1 n
 , r 1 
 a1r j =S n =  r − 1  or  a1r j =  r − 1 
j =0 (n + 1)a , r = 1 j =1 (n + 1)a , r = 1
   

3. The sum of special sequences

n
n (n + 1) n
n (n + 1)(2 n + 1)

k =1
k =
2
k 2 =
k =1 6

 n (n + 1)  
n 2
1

k =1
k =

3

2  x
k =0
k
=
1− x
, x 1


1
k x k −1 = , x 1
(1 − x )
2
k =1

Example: Find the sum of the following

4

1. i
i =1
=

2. ii =1
2
=

24
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
15

3. i
i =7
2
=

4 3

4.  (i + j ) =
i =1 j =1

 ( 2.3 )
20

5.
j
+ 2j =
i =0

Example : Let X be a real number , x  1 , find x

n =0
n

 ( 3 + (−1) ) =
20
j
Question : Find
i =0

25
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Logic ( Preposition Logic )
Definition: A statement or preposition is declarative sentence that is either true or
false but not both.
Examples of preposition
1. 2 + 4 = 6 . 2. 3 + 4 =9
3. The sun will come tomorrow. 3. Amman is the capital of Jordan.

Example : which of the following are statement

1. 2 + 4 =y 2. 5+ 6 3. What is your name?

4. Just do it 5. The sum of two prime numbers are even

 Boolean Operators

1. Negation ( Not ) , (  )
Example : Give the negation of the following
1. P : 3+5 > 7 2. Q : it is cold

2. Conjunction ( and ) , (  ) 3. Disjunction ( or ) , (  )

p q Pq pq
T T T T
T F F T
F T F T
F F F F

4. Exclusive – Or operator ( XOR ) , (  )

p q pq
T T F
T F T
F T T
F F F

Example : Let p and q be the prepositions

P : I will earn an A in this course q : I will drop this course
Find P  q :

26
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
5. Implication ( implies ) ( → ) p→q
p q p→q Hypothesis Conclusion
T T T
T F F
F T T
F F T
Example : choose the correct answer of the following
1. If Sunday is a day of the week, then 1+3=5 . ( T ,F )
2. If you went to school, then September is a month . ( T , F )

6. Inverse , convers , contra positive

p → q q→ p q → p
7. Biconditional operator ( iff ) , (  )
p q pq
T T T Note :
T F F
 is the oppiste of 
F T F
F F T
Example : Let p and q be the preposition
P : I bought a lottery ticket this week q : I won the million dollar
Express each of these preposition
1. p :

2. p  q :

3. p  q :

4. p  q :

5. p → q :

6. p  q :

7. p  ( p  q) :

27
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Note : we will use the following form in the solution of combinatorial circuits

Example : Determine whether these statements are true or false

1. 2 + 2 = 4 iff 1 + 1 = 2 . ( )

2. If 1 + 1 = 3 ,then 2 + 2 = 4 . ( )

3. If 1 + 1 =2 ,then the cat can fly. ( )

Example : Construct a truth table for ( p  q)  ( p  q)

Example : Find the output of the combinatorial circuits

28
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Example : show that if the following statements are equivalent by truth table
p → (q → r ) and q → ( p  r)

29
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Exercises :

1. Construct a truth table for

b. ( p  r  q) a. ( p → q)  (p → q)

2. show that if the following statements are equivalent by truth table

( p  q)  ( p  q)  (p  q)

3. Let p and q be the propositions “The election is decided” and “The votes
have been counted, "respectively.
Express each of these compound propositions as an English sentence.
a) ￢p b) p ∨ q c) ￢p ∧ q
d) q → p e) ￢q →￢p f) p↔q
g) ￢q ∨ (￢p ∧ q)

4. Write these propositions using p and q and logical connectives (including

negations).
a) It is below freezing and snowing.
b) It is below freezing but not snowing.
c) It is not below freezing and it is not snowing.
d) It is either snowing or below freezing (or both).
e) If it is below freezing, it is also snowing.
f ) Either it is below freezing or it is snowing, but it is not snowing if it is
below freezing.

30
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
2.6 Matrices
Definition : A matrix is a rectangular array of number with m-rows and n-
columns .
 a11 a12 . . a1n 
a a 22 . . a 2 n 
 21
The general form of any matrix is  . .  where a ij is element or
 
 . . 
a m1 . . . a mn 
entry .
Note :

1. The size of matrix = ( # of rows ) x ( # of columns ) = m x n

2. The matrix is called square iff m = n .

3. The matrices are equal iff the corresponding entries in every position are
equal .

Matrices Addition ( Subtraction ) : Matrices Product :

If A and B are two matrices then If A and B are two matrices then we can
A  B = aij  bij   product A and B iff the number of
columns in A = the number of rows in B .

1 4 3 5 2 1
Example : If A = 6 0 3 , B=  ,find
  4 1 8
1. The size of A and B .

2. a 23 = a 21 =

3. A+B=

31
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
 2
1 4 3
Example : If A = 6 0 3 , B = 3 ,find A . B
  1

Transposes and power Matrices

Definition : The identity matrix of order n ,is the n x n matrix I n =  ij  ,

where  ij = 1 if i= j and  ij = 0 if i  j.

1 0 0
 
For example : I 3 = 0 1 0
0 0 1

Note : The power of square matrices can be defined by the following

A0 = I n , Ar = 
A 
A ....
 A
r −times

Definition: The transpose of matrix is defined by At  AT and we can find the

transpose by interchanging the rows and columns.

Note : A square matrix is called symmetric  A = AT

32
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
7 1 3
Example : If A =   ,find
6 2 5

1. AT 2. Explain ,if a matrix A is symmetric .

Zero – one Matrices

A matrix all of whose entries are either 0 or 1 is called a zero –one.

Boolean Operations
1. The join of any two sets A and B are denoted by A  B .

2. The meet of any two sets A and B are denoted by A  B .

3. The Boolean product is denoted by AB , where

AB = cij = (a i1  b1 j )  (a i 2  b2 j )  ........  (a ik  bkj )

Note : The rth Boolean product of a matrix A is denoted by Ar 

1 0
1 1 1
Example : If A = 0 0 1 , B = 1 1 ,find
  0 0

1. AB

2. A2

33
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Inverse Matrix

We can find the inverse matrix for any Square matrix ( A) if the determinant of a
matrix not equal zero ( A  0 ) .

a c
−1 1 d − c
1. If A =    A = A .− b , where A = a.d − b.c
 b d   a 
T
 e f d f d e 
 − 
a b c  h i g i g h 
1  b b
A = d f 
c a c a
 A −1 = .− −
h 
2. If e
A  h i g i g
 g h i 
 b c a c a b 
 e −
 f d f d e 

Example : Find the inverse of the following matrices

 3 1
1. A =  
4 5

2 5 6
2. A = 4 0 2
1 1 3

34
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

1 1 1 1
Practice 1: If A =   , B=  ,find
0 1 1 0

1. AB 2. A2 3. A  B 4. A  B

Practice 2 : Find the inverse of the following matrices

− 2 5 1 
3 4
1. A=  2. A =  4 4 2
− 2 − 3
 1 1 0

35
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

Chapter 4 : Number Theory

Definition : If a , b are integers ,then ,if there exist an integer a divides b
number c such that b = a.c .
i.e.: a , b  Z , a  0 ,then a \ b  a divides b , c  Z : b = a.c

Note : If b = a.c then a  divisor  Factor , b  multiple  dividend

Properties of divisibility
1. a \ 0
2. (a \ b)  (a \ c)  a \ (b + c)
3. a \ b  a \ (b.c)
4. (a \ b)  (b \ c)  a \ c
Proof :

36
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

Theorem : (Division Algorithms )

Let a be an integer and d a positive integer ,then there are unique integers
q and r , 0  r  d such that a = d .q + r .
Note : a  dividend , q  quotient , d  divisor , r  remainder
q  a div d , r  a mod d
a div d = a / d  , a mod d = a − d a / d 
Example : Find the quotient and remainder when
1) 27 is divided by 10 2) -15 is divided by 4

Modular Congruence

Definition : If a , b  Z , m  Z + then a is congruent to b modulo m ,if m divides (a-b) .

i.e.: a  b (mod m)  m \ (a − b) or (a − b) mod m = 0

Theorem : Let a , b  Z , m  Z + , then a  b (mod m)  a mod m = b mod m .

Example : Determine whether 16  6 (mod 4) and 25  5 (mod 7)

Theorem : Let a , b  Z , m  Z + and a , b are congruent modulo m

 k  Z such that a = b + k m .

37
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Theorem : Let m  Z + , if a  (mod m) and c  d (mod m) ,then
1. a + c  (b + d )(mod m) 2. a.c  (b.d )(mod m)

Arithmetic Modulo m

We can defined the arithmetic operations on Z m by

1. a + m b  (a + b)(mod m) 2. a. m b  (a.b)(mod m)

Example : find the following

1. 9 + 4 5 2. 9 . 4 5

Practice 1 : If a = 75 , m = 30 ,then a div m = ............ , a mod m = ...............

Practice 2 : Find the following : (170 mod 30 + 100 mod 30) mod 30
Practice 3 : Decide whether each of these integers is congruent to (5 mod 17)

1. 80
2. -29
Practice 4 : Find the modulo 5
Practice 5 : Suppose that a , b  Z , a  4(mod 13) , b  9(mod 13) ,find the
integer c with 0  c  12 .
1. c  9a (mod 13) 2. c  (a + b) (mod 13)

38
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

39
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Prime Numbers

Any integer number p  1 is prime  it is not the product of any two integers
greater than 1.

Corollary : 1. The factors of any prime number is 1 and itself.

2. The nonprime is called composite

Mersenne Primes : Any prime number that can be written as 2 p − 1 is called

mersenne.
For instance : 3 = 2 2 − 1
Theorem 1 : Every positive integer number greater than 1 can be uniquely written by
one or more prime numbers .
Note : There are infinitely prime numbers.

*** Finding the prime factors of an integer number

1. Find n
2. List all prime numbers  n
3. Find all factors

Example : Find the prime factors of the following

1. 7007 2. 88

Example : show that 100 is composite

40
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

Greatest Common Divisor ( gcd )

d = gcd(a, b) = max(d : d \ a  d \ b)  d \ a  d \ b and c  Z (e \ a  e \ b) , d  e

Note : a , b  Z are called coprime ( Relatively prime )  g.c.d (a , b) = 1
Example : Find the following
1. gcd(24 , 36) 2. gcd(7 , 13)

Least Common Multiple ( L.C.M )

L.c.m (a , b) of positive integers a , b is the smallest positive integer number

that multiple both of a , b .
m = Lcm(a, b) = min (m : a \ m  b \ m)  a \ m  b \ m and n  Z (a \ n  b \ n) , m  n

Example : Find the following

1. Lcm(24 , 6) 2. Lcm(4 , 10)

3. gcd(15 , 30 , 105)

41
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

Example : Determine whether the integers in each of these sets are relatively
prime
1. 21 , 23 , 55 2. 14 , 12 , 32

Theorem : If a, b  Z + , then a.b = gcd(a, b) . Lcm(a, b) .

Greatest Common Divisor by Euclidean Algorithm

Example : Find
1. gcd(91 , 287) 2. gcd(111 , 201)

Greatest Common Divisor as linear Combination

Example : Express gcd(91 , 287) as a linear Combination

Question 1 : Use the Euclidean Algorithm to find gcd(12 , 18)

Question 2 : Express gcd(36 , 48) as a linear Combination

42
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

Mathematical Induction

We use this method to prove many of statements .

Now ,we will discuss the induction steps
1. p(1) is true
2. If p(k ) is true ,then p(k + 1) also is true for all k  1 .

Example : By mathematical induction show that

n(n + 1)
1 + 2 + 3 + ... + n = , n  1
2

n −1
Example : By mathematical induction show that n! 2 , n 1

43
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

Example : Let A1, A2 ,....An be a sets . By mathematical induction show that

n n
 Ai =  Ai
i =1 i =1

Question 1 : By mathematical induction show that

an −1
1 + a + a 2 + ... + a n −1 =
a −1
Question 2 : By mathematical induction show that n  2
n

44
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Relations :

Partitions : A partitions of a set A is a collection of P ( non empty set ) such that

1. Each element of A belong to one of P .
2. A1 A2 = 

Example : If A = a , b , c , d , e , f , g , h  , A1 = a , b , c  , A 2 = f , g , h 
A 3 = d , e , f , g , h  , A 4 = b , f  , A5 = d, c  , A 6 = f , g , h 
Describe which of the following is a partition of A .
1. A1 , A 2  2. A1 , A 5 , A 6  3. A 3 , A 4 

Definition : A binary relation from A to B is a subset of A  B

Note : If (a, b )  R ,then a is related to b
Definition : A relation on a set A is a relation from A to A .

Example : If A = a , b , c , B = 1, 2, 3 ,explain which of the following

represents a relation from A to B
R1 = (a, a) (a,1) (b, 3)
R 2 = (c,1) (b, 2) (a,1)

+
Example : Let A  Z , R is the relation defined by
aRb  2a  b + 1 , which of the following is a relation
A1 = (1, 4) (2, 5) (3, 7)
A 2 = (2, 2) (1, 5) (3,8)

45
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Example : List all order pairs in the following relation
R = (a, b) : a divides b on the set 1, 2,3, 4,5

Properties of relations
1. A relation R on a set A is called reflexive if (a, a)  R , a  A
2. A relation R on a set A is called symmetric if (b , a)  R ,whenever
(a, b )  R , a, b  A

3. A relation R on a set A is called antisymmetric if (a,b )  R and

(b , a)  R , a, b  A then a = b Or a  b  (a,b )  R , (b , a)  R

4. A relation R on a set A is called transitive if (a,b ) R and (b , c ) R then (a,c ) R

Example : Consider the following relations on A = 1, 2,3, 4

R1 = (1,1) (1, 2) (2,1) (2, 2) (3, 4) (4,1) (4, 4)

R 2 = (1,1) (1, 2) (2,1) 

R 3 = (1,1) (1, 2) (1, 4) (2,1) (2, 2) (3, 3) (4, 4) (4,1)

R 4 = (2,1) (3,1) (3, 2) (4,1) (4, 2) (4, 3) 

R 5 =  (2, 3) 

R 6 = (1,1) (1, 2) (1, 4) (1, 3) (2, 2) (2, 3) (2, 4) (3, 3)(3, 4)(4, 4)

46
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Representing Relaion:
1. Matrix of relations
A relation between finite sets can be represenred using a zero – one matrix.
1 , (ai , b j )  R

MR =
 m ij 
 m ij = 
and
1 , (ai , b j )  R

Example : Let A = 1, 2, 3 , B = a , b  ,explain if
,then represent R by matrix [Link] a relation R = (2, a) (3, b) (1, a)(1, b)

Example : Let A = a , b , c  , B = d , e , f  ,use the following matrix to write

the set of relation .
1 1 0
MR =
0 1 1


0 0 1


 We can apply the properties of the relation on a matrix form by the following steps:
1. Reflexive  The main diagonal of M R is 1 .
2. Symmetric  m ij = 1 whenever m ji = 1. ( m ij = m ji )
or
Symmetric  M R = M R T
3. Antisymmetric  m ij = 1 , m ji = 0 when i  j .
or
Antisymmetric  m ij = m ji = 0 when i  j

Theorem : A relation R is called equivalence relation  R is reflexive ,symmetric

and transitive .

Example : Which of the following matrices are reflexive , symmetric ,antisymmetric

47
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
1 1 1
1. M R =
1 1 1


1 0 1


0 1 0
2. M R =
0 1 0


0 1 0


1 0 1
3. M R =
0 1 0


1 0 1

Example : list the oreder pairs for the previous example .

2. Digraph of relations

48
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
To display the relation by digraph
- Draw a small circle for each element in A
- Use the order pairs to connect between the elements.
Note : Circles = Vertices , Lines = Edges

Example : Display the following relations by digraph

1. A = 1, 2,3, 4 , R = (1,1) (1, 2) (1,3) (2,3) (3, 4) (4,1)

1 1 0
2. A = 1, 2, 3 , MR =
0 1 1


0 1 1


Example : Draw the matrix form of the following relation `

Combining Relations

49
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Example : Let A = 1, 2,3 , B = 1, 2,3, 4 be sets ,and
R1 = (1,1) (1, 2) (1, 4) , R 2 = (1,1) (2, 2)  find
1. R1 R2 =

2. R1 R2 =

3. R1 − R 2 =

4. R1  R 2 =

The composite of two relations

If R is a relation from A to B and S is a relation from B to C then the coposite of
R and S ( S R ) is the relation consisting of order pairs (a,c) , a  A , c  C.

Example : Let
R1 = (1,1) (1, 3) (2, 3)(2, 4)(3,1) , R 2 = (2,1) (3,1)(3, 2)(4, 2) 
find ( S R )

50
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Question : Consider the following relations on A = 1, 2,3, 4
R1 = (2, 2) (2, 3) (2, 4) (3, 2) (3, 3) (3, 4)
R 2 = (1,1) (1, 2) (2,1) (2, 2) (3, 3) (4, 4)
R 3 = (2, 4) (4, 2) 
R 4 = (1, 2) (2, 3) (3, 4) 
R 5 =  (1,1)(2, 2)(3, 3)(4, 4) 
R 6 = (1, 3) (1, 4) (2, 3) (2, 4) (3,1) (3, 4) 

Question Display the following relation by digraph

0 1 0 1 
1 1 1 0 
A = 1, 2, 3, 4 , MR = 
0 0 1 1 
 
1 0 1 0 

Question Which of the following relations are maps from A = {1, 2, 3, 4} to A?

1. {(1, 3),(2, 4),(3, 1),(4, 2)}
2. {(1, 3)(2, 4)}
3. {(1, 1),(2, 2),(3, 3),(4, 4),(1, 3),(2, 4),(3, 1),(4, 2)}
4. {(1, 1),(2, 2),(3, 3),(4, 4)}.

51
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Path in Digraph

A path from a to b in the directed graph G is a sequence of edges

( xo , x1 ) ( x1 , x2 ).........( xn−1 , xn ) in G , n is a nonnegative integer.

Note : 1. If the path from a to a then the length is zero

2. If the path begins and ends at the same vertex then is called circuit or cycle .

Example : which of the following are paths ,then find the length of ach path and determine
which one is called cycle
1. a, b, c, e
2. b, e, c, b, e
3. a, a, b, e, d , e
4. b, c, e, d , a, a, b
5. b, c, c, b, e, d , e, d
6. a, a, b, b, c, c, b, e, d ,

52
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Graph
In this section ,we will explain the different types of graphs with its suitable example .
1. Undirected graph : In this case the direction of edge does not obtain(exist).(without
direction )

2. Directed graph : the direction between both vertices exist .

3. Mixed graph : is the combination of both directed and undirected graph.

4. Null graph : The graph with no vertices and no edges

5. A graph with only vertices and no edges is known as an edgeless graph.

6. Self loop graph :the edge from v1 to v1 .(From the vertex to itself )

7. Simple graph : A graph in which there is no self loop graph and parallel edges .

8. Multiple graph : is a graph with multiple edges between the same vertices and loops are
allowed

9. Finite ( countable ) and infinite (uncountable )

53
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
The Degree of vertices in an undirected graph :
Definition : The degree of vertex in an undirected graph is the number of edges that

connect between the vertex with another vertex .( deg(v) )

Definition : Two vertices u and v in an undirected graph are called adjacent or
neighbors .( N(v) )
Example : Find the number of vertices ,the number of edges, the neighbors and the
degree of each vertex

Theorem : Let G(v,e) be an undirected graph with m edges then 2m =  deg(v)

vV

Example : How many edges are there in a graph with 10 vertices each of degree 6 ?

54
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

Definition : In a graph with directed edges ,the in-degree of a vertex v denoted by

deg − (v ) [ Terminal Vertex ], and the out-degree of v denoted by deg + (v )
[ initial vertex ].
Example : Find the in-degree and out-degree of each vertex in the following graph .

55
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

Example :determine whether the graph shown has directed or undirected edges,
whether it has multiple edges, and whether it has one or more loops.

56
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

Adjacency Matrices :
1 , if {v ,v }is an edge of G
if its adjacency matrix is A = aij  , then aij =  i j

0 , otherwise

Example : Draw a graph with the adjacency matrix of the following graph

57
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

Question :determine whether the graph shown has directed or undirected edges,
whether it has multiple edges, and whether it has one or more loops.

58
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

Example :determine whether the graph shown has directed or undirected

edges, whether it has multiple edges, and whether it has one or
more loops.

The graph has undirected edges, multiple edges, and no loops.

The graph has undirected edges, multiple edges, and no loops.

This graph has directed edges, multiple edges, and two loops.

59
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

Trees
Introduction to trees
Definition : A tree is a connected undirected graph with no simple circuit .
(without multiple edges or loops )

For instance :

Definition : A rooted tree is a tree in which one vertex has been designated as the
root and every edge is directed away from the root.

Notes : Let T be a rooted tree

1. The ancestors of a vertex other tan the root are the vertices in the path from
the root to this vertex .(including the root )
2. The descendants of a vertex v are these vertices that have v as an ancestor .
3. A vertex of a rooted tree is called leaf ,if it has no children .
4. Vertices that have children is called internal vertices .
5. Vertices with the same parent are called siblings.

60
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

Example : In the rooted tree T , Find

1. The parent of c . ( )
2. The children g . ( )
3. The sibling of h. ( )
4. All ancestors of e. ( )
5. The descendants of b. ( )
6. The internal vertices . ( )
7. The leaves . ( )
8. The sub-tree rooted at g.

Example : Use the following graph to answer

a) Which vertex is the root?

b) Which vertices are internal?

c) Which vertices are leaves?

d) Which vertices are children of j?

e) Which vertex is the parent of h?

f ) Which vertices are siblings of o?

g) Which vertices are ancestors of m?

h) Which vertices are descendants of b?

61
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Definition : A rooted tree is called an m-ary tree if every internal vertex has no more than
m children. The tree is called a full m-ary tree if every internal vertex has
exactly m children. An m-ary tree with m = 2 is called a binary tree.

Example : Classify the following trees to full m-ary or not

Ordered Rooted tree

Left child right child

Left sub tree right sub tree

62
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Example : Use the following graph to answer

1. The left child of d

2. The right child of d

3. The left sub tree of c

Properties of trees

Theorem : A tree with n vertices has n − 1 edges.

Theorem : A full m-ary tree with i internal vertices contains n = mi + 1 vertices.
Theorem : A full m-ary tree with
n −1 (m − 1) n + 1
1. n vertices has i = internal vertices and L = leaves,
m m
2. I internal vertices has n = m i + 1 vertices and L = (m −1) i + 1 leaves,
m L −1 L −1
3. L leaves has n = vertices and i = internal vertices.
m −1 m −1
Example : How many edges does a tree with 400 vertices have?

Example : How many vertices does a full 5-ary tree with 100 internal vertices have?

Example : How many edges does a full binary tree with 1000 internal vertices have?

Example : How many leaves does a full 3-ary tree with 100 vertices have?

63
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Note : The height of a rooted tree is the maximum of the levels of vertices

Note : A rooted tree with many m-ary of height h is balanced ,if all leaves are at level h
or h-1 .

Example : 1. Find the level of each vertex in the rooted trees .

2. What is the height of these trees?
3. Explain ,if the tree is balanced

64
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------
Example : Construct the tree of the following expression

1. (7 + (6 − 2)) − ( x − ( y − 3))

2. ((3 + x) − (3 − x)) − ( x + 3)

3. (3 − (2 − (11 − (9 − 4))))  (2 + (3 + (4 + 7)))

65
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

Traversal Algorithms
Procedures for systematically visiting every vertex of an ordered rooted tree.
1. Preorder Traversal
Visit the root search the left subtree search the right subtree

2. Inorder Traversal
Visit the left subtree Visit the root Visit the right subtree

3. postorder Traversal
Visit the left subtree Visit the right subtree Visit the root

Example : In which order are the vertices of the ordered rooted tree visited using

1. A preorder traversal

2. An inorder traversal

3. A post order traversal

Example : In which order are the vertices of the ordered rooted tree visited using

1. A preorder traversal

2. An inorder traversal

3. A post order traversal

66
 The University of Jordan –Aqaba Branch
Ahmed Alsarairah Discrete Mathematics
--------------------------------------------------------------------------------------------------------------------------------------------

Example : In which order are the vertices of the ordered rooted tree visited using

1. A preorder traversal

2. An inorder traversal

3. A post order traversal

67