그림입니다.
원본 그림의 이름: CLP0000ec300017.bmp
원본 그림의 크기: 가로 468pixel, 세로 206pixel


Chapter 3  Functions, Sequences and Relations

                                                             그림입니다.
원본 그림의 이름: CLP0000ec300018.bmp
원본 그림의 크기: 가로 135pixel, 세로 203pixel

​(DM Ch. 1, Sets and Logic, Lecture Note)  http://matrix.skku.ac.kr/2018-DM/Ch-1/ 
 DM-Ch-1-Lab  http://math1.skku.ac.kr/home/pub/2651/   (Use Chrome browser, not IE)
    (DM Ch. 1, 동영상강의) 
Discrete Math 이산수학 Ch 0 Introduction 
https://youtu.be/9ahFnOFTWNQ 
Discrete Math 이산수학 Ch 1, 1.1, 1.2 Propositions 
https://youtu.be/QgdKqmCFW2Y 
Discrete Math 이산수학 Ch 1, 1.3, 1.4 Rules of Inference 
https://youtu.be/92siPfThf0M 
Discrete Math 이산수학 Ch 1, 1.5, 1.6 Nested Quantifiers 
https://youtu.be/7M7w9eX5D0Q


​(DM Ch. 2, Proofs, Lecture Note)  http://matrix.skku.ac.kr/2018-DM/Ch-2/
DM-Ch-2-Lab    http://math1.skku.ac.kr/home/pub/2652/
     (DM Ch. 2, 동영상강의) 
​DM Ch 2 Lecture 1 Sec 2.1, 2.2 2.2 More Methods of Proof Problem   
https://youtu.be/xEMkHb2AkYk
​DM Ch 2 Lecture 2 Sec 2.4, 2.5 Math Induction and Well-Ordering Property https://youtu.be/areatkjOjcg 

​(DM Ch. 3, Functions, Sequences, and Relations, Lecture Note)  
http://matrix.skku.ac.kr/2018-DM/Ch-3/
http://math1.skku.ac.kr/home/pub/2653/
     (DM Ch. 3, 동영상강의) 
​DM 이산수학 Ch 3, Functions, Sequences, and Relations 1  https://youtu.be/MhM_9ZuGAis 
​DM 이산수학 Ch 3, Functions, Sequences, and Relations 2  
https://youtu.be/ZjAtN9HkZwM
​DM 이산수학 Ch 3, Functions, Sequences, and Relations 3  https://youtu.be/Uuwsx2aiEPI

 

Ch 4, Algorithms, Lecture Notehttp://matrix.skku.ac.kr/2018-DM/Ch-4/
DM-Ch-4-Lab   http://math1.skku.ac.kr/home/pub/2654/
    (DM Ch. 4, 동영상강의) 
​DM 이산수학 Ch 4,
...


그림입니다.
원본 그림의 이름: CLP0000ec300017.bmp
원본 그림의 크기: 가로 468pixel, 세로 206pixel

 

그림입니다.
원본 그림의 이름: CLP0000ec300019.bmp
원본 그림의 크기: 가로 139pixel, 세로 32pixel  3.1. Functions

 

 Definition 1.1

 

  and are nonempty sets.

      is a function from to   = maps to

        is the domain (정의역) of and is the co-domain (공변역) of .

  is an assignment of exactly one element of to each element of .

 

    is the unique element of assigned by the function to the element of .

       is the image of and is a pre-image of .

The range (치역) or image of is the set of all images of elements of .


Functions are sometimes mappings or transformations.


그림입니다.

 maps to


is a function from to .

 is a subset of .

The range (치역) or image of under the function is the subset of that consists of the images of the elements of .

The range (치역) or image of by , so

.


(1.1)                                                   function

                                      travel miles per hour for hours

where is the times and is the distance traveled.        ■

 

 Example  1.2

 

 By

 The domain is the set of all .

 The co-domain is the set of all . (Assume the time is restricted to .)

 The range is the set of all .



 Example  1.3

 

 The set

   f = { (1, a), (2, b), (3, a) }  (ordered-pair notation)

 is a function from to .

, , .

 The domain of is .

 The codomain of is

 The range of is .

그림입니다.

Arrow diagram. There is exactly one arrow from each element in .

 


Domain and Range

 

Domain of .  Codomain of

 Range of

 A function assigns to each in a unique element in        .


 Example  1.4

But the following is not a function:

 The set

 (1.2)                              ordered-pair notation

 is not a function from to .

 The elements is not assigned to an element in .

 

그림입니다.

 


 Example  1.5

But the following is not a function:

 The set

  ordered-pair notation

 is not a function from to .

The elements is not assigned a unique element in (1 is assigned the values and ).



그림입니다.

 

 Example 1.7

 

Let  be the function defined by the rule

.

If  and the Codomain is the set of all non-negative real numbers, in ordered-pair notation, we would have

 Range (f) =     the set of all non-negative real numbers.


 

Graph of a function

http://matrix.skku.ac.kr/Cal-Book/part1/CS-Sec-1-3.htm


Let be a function from the set to the set . The graph of the function is the set of ordered pairs .


Definition 1.10

 

그림입니다.


 Example 1.11

 

그림입니다.



 Example 1.12

 

What day of the week will it be 365 days from Wednesday?

Solution

Since , days from Wednesday, it will be one day later, namely Thursday.

 

 Example  1.13

http://blog.naver.com/PostView.nhn?blogId=onlyyeom&logNo=100160308299&parentCategoryNo=37&categoryNo=51&viewDate=&isShowPopularPosts=false&from=postView

그림입니다.그림입니다.

 * 각 책은 하나씩 ISBN이 부여된다. ISBN은 다음과 같이 구성된다.

978                -    89 (한국) -       5460 -        326       3

(1)GS1 접두어    (2)국가·언어    (3)출판사    (4)항목     (5)확인숫자

        출판 국가 또는 언어 번호 출판사 번호, 영어(0), 프랑스어(2), 독일어(3), ...

 

        13자리 ISBN 이 abcdefghijklm일 때, a+3b+c+3d+e+3f+g+3h+i+3j+k+3l+m = 0 (mod 10)         ■

 

 

Definition  1.16

 

 In ,

  is the floor of . the greatest integer less than or equal to  .

 Symbolically, if is a real number and is an integer, then

      .     “rounds down.”

그림입니다.

 is the ceiling of . the least integer greater than or equal to  .

 Symbolically, if is a real number and is an integer, then

        “rounds up.”

그림입니다.

 

 Example  1.17

 

그림입니다.



 Example  1.18

 

 Shows the graphs of the floor and the ceiling functions.

  indicates that the point is to be included in the graph,

 indicates that the point is to be excluded from the graph.

 


그림입니다.      그림입니다.

Floor  Function               Ceiling Function


그림입니다.

 

Example  1.19

 

 In 2007, the U.S. first-class postage rate for retail flat mail up to ounces was cents for the first ounce or fraction thereof and cents for each additional ounce or  fraction thereof. The postage as a function of weight is

,   .

 The expressioncounts the number of additional ounces beyond , with a   fraction counting as one additional ounce. As examples

,

The graph of the function is

그림입니다.


The Quotient(Chinese)-Remainder Theorem, https://ko.wikipedia.org/중국인의 나머지정리

If and are integers, , there exist integers (quotient) and (remainder) satisfying

,   .

Dividing by , we obtain

      n/d  = q + r/d .

Since ,

   |n/d|  =  |q + r/d | = q

Compute the quotient as . Having computed the quotient , we computed the remainder as

.

The notation for the remainder.

 

 

One-to-One functions (Injective)


Definition  1.21

one-to-one (injective)  function

그림입니다.

         A function is said to be injective if it is one-to-one.

A function from to is one-to-one using quantifiers as


      is one-to-one      If      then    .                               ■

 


 Example  1.22

 

그림입니다.

 


 Example  1.23

 

그림입니다.



 Example  1.25

one-to-one function,      Not one-to-one function

그림입니다.


 Example  1.26

 

 Prove that the function

 from the set of positive integer to the set of positive integer is one-to-one.

Proof 

Show that       .

            .

Therefore is one-to-one.                                                      ■


 (In words, a function is not one-to-one if there exist and such that and .)

 Example  1.27

 

 Prove that the function

 from the set of positive integer to the set of positive integer is not one-to-one.

Proof 

[Show that f, such that .]

      

Therefore is not one-to-one.                                                  ■

 

 

Onto function (surjective function)

Definition 1.28

 

그림입니다.

Function from to is onto (surjection)      for every element        there is an element with .

                  A function is surjective if it is onto.


 Example  1.29

 

그림입니다.


 Example  1.30

 

그림입니다.


Bijection

Definition 1.34

(bijective function)

그림입니다.

,



 Example  1.35

  ( Example  1.29 )

그림입니다. 

 The function

 from to is a bijection.



Example  1.36

 

 If is a bijection from a finite set to a finite set , then , that is, the    sets have the same cardinality and are the same size. For example

 is a bijection from to . Both sets have four elements.

 In effect, counts the elements in : is the first element in ; is   the second element in ; and so on.


Inverse Function


A function is a one-to-one and onto from to .

is a one-to-one and onto from to . is inverse function of .

그림입니다.

The function is the inverse of function .


 Example  1.37

inverse function

 From the function

,

 we have

.

 

 Example  1.38

inverse function

 The arrow diagram for a bijection function from to .

 The arrow diagram for simply by reserving the direction of each arrow.

 

Definition 1.40

composition function

그림입니다.

 

 Example  1.31

   The composition function of and .

그림입니다.


그림입니다.

 

A binary operator on a set associates with each ordered pair of elements in one elements in .

 

Definition  1.45

binary operator

A function : is a binary operator on .

 


 Example  1.46

 

그림입니다.

 

Example  1.47

 

 If is a set of propositions, , , and are binary operator on .


A unary operator on a set associates with each single element in one element in .

 

 Definition  1.48

unary operator

 Function : is a unary operator on .

 

Example  1.49

 

 Let be a universal set.  If we define

 where , then is a unary operator on .

 


Example  1.50

 

 If is a set of proposition, is a unary operator on .

 


Exercises 1, 10, 16, 26, 35, 48, 51, 62, 68, 70, 90, 95, 98, 104

 

 

3.2   Sequences and Strings


A sequence is an ordered list.

 The domain consists of a set of consecutive integers.


The term denoted or . is the index of the sequence.


그림입니다.

그림입니다.


Infinite sequence : The domain of the sequence is infinite.

             : the initial index of an infinite sequence .

 


Finite sequence  :  The domain of the sequence is finite.

              : a finite sequence indexed from to



그림입니다.


For and are in the domain of the sequence.

,       sequence is increasing

,       sequence is decreasing

,       sequence is nondecreasing

,       sequence is nonincreasing



increasing is replaced by nondecreasing : “” is replaced by “

decreasing is replaced by nonincreasing : “” is replaced by “


 Example  2.7

 

 The sequence

,   ,   ,    ,   

 is increasing and nondecreasing.



 Example  2.8

 

 The sequence

,   

 is decreasing and nonincreasing.



 Example  2.9

 

그림입니다.


subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

 


Definition 2.11

 

Let be a sequence defined for .

Let , , be an increasing sequence whose values are in the set .

We call the sequence a subsequence of .


Example  2.13

 

 The sequence

(2.5)                             , , , , , ,

is a subsequence of the sequence

(2.6)                     , , , , , , , , , , .

Subsequence is obtained from sequence by choosing the first, second, fourth, eight, and so on, terms.

 

 Definition  2.14

 

If is a sequence, we define

read the summation from equals to of -sub-, is the sum of all the terms , , , .

 is the expanded form of the sum.

 is a sequence, we define

.

read the product from equals to of -sub-, is the product of all the terms , , , .

 is the expanded form of the product.


The formalism

(2.7)                                 

is the sum(or sigma) notation.

The formalism

(2.8)                                 

is the product notation.

In and , is the index, is the lower limit and is the upper limit.


 Example  2.15

 

그림입니다.



Example  2.16

 

그림입니다.

 


Example  2.17

 Changing the index and Limits in a Sum

 The sum

,

 replacing the index by , where .


 Example  2.18

 

 Find a formula for the sequence defined by

.


If is a finite set of integers and is a sequence,

denotes the sum of the elements .

If is a finite set of integers and is a sequence,

denotes the product of the elements .


 A string is a finite sequence of characters.


 Definition  2.20

 

 A string over is a finite sequence of element from , where is a finite set.


Example  2.21

 

 Let .  If we let

,   ,   ,   ,

we obtain a string over .  This string is written .

A string is a sequence, order is taken into account.

Repetitions in a string can be specified by superscripts.


The string with no elements is the null string. is null string.

 is the set of all strings over , including the .

 is the set of all nonnull strings over .



 Example  2.22

 

그림입니다.


 is the length of .

 is the number of elements in .


 Example  2.23

 

그림입니다. 


 and are two strings.

 is the concatenation of and .

              the string consisting of followed by


 Example  2.24

 

 If and , then

,     ,     ,     .


Example  2.25

 

 Let . If we define

,

where and are strings over , then is a binary operation on .




A substring of a string is obtained by selecting some or all consecutive elements of .

 Definition  2.26

 

A string is a substring of the string if there are strings and with .



Example  2.27

 

 The string is a substring of the string since if we take    and , we have . Note that is a substring of , is the part of that precedes (in ), and is the part of that follows (in ).




Exercises  40,45,67,69~73, 83~86, 94,111,117,120,129

 

 


3.3   Relations   (Skipped section: 2.3)


그림입니다.


Definition  3.1

 

  and 

 

그림입니다.

 

       

 say that is related to .

 say that is not related to .


If , we call a (binary) relation on .

: A function from to is a binary operator on .


A (binary) relation from a set to a set      


 Example  3.3

 

 그림입니다.

그림입니다.


Example  3.4

 

 Let be the relation on defined by if , .

 Then

.

그림입니다.

Figure 3.1 The digraph of the relation of Example 3.4.


A digraph is represented by two letters

An informative ways to picture a relation on a set is to draw its digraph.


We first draw vertices(dots) to represent the elements of       To draw the diagraph of a relation on a set .

If the element is in relation, we draw an arrow (directed edge) from to .

                                        

An element of the form in a relation corresponds to a directed edge from to . Such an edge is a loop.


 Example  3.5

 

그림입니다.

그림입니다.



Definition  3.6

reflexive relation

,       A relation on a set is reflexive.

,       The relation on a set is reflexive.


Example  3.7

 

The relation on defined by if , .

Then

.

This relation is reflexive.

Because for each element , ;

, , ,

 The digraph of a reflexive relation has a loop at every vertex.

 The digraph of this relation has a loop at every vertex.



By the generalized De Morgan’s laws for logic,

,       A relation on is not reflexive.



 Example  3.8

 

 Relation

 on is not reflexive. (Because some vertex has no loop.) 


For example, , but .

             , but .

Vertices (and ) do not have a loop.      The relation is not reflexive.



Definition  3.9

 

 A relation on is symmetric  if  (, if , then ).



 Example  3.10

 

 Relation

 on is symmetric

  ,       .

 For example, and .


Example  3.11

 

Relation on defined by if , .

 Then

.

  is not symmetric.

For example, , but .

The digraph of this relation has a directed edge from to .

The digraph of this relation has no directed edge from to .



Definition  3.12

 

그림입니다.

, and     : A relation on a set is antisymmetric




Example  3.13

 

 A relation on defined by if , .

 This is antisymmetric

    , and       .


Example  3.15

 

그림입니다.


그림입니다.

Figure 3.3 The digraph of the relation of Example 3.15.



 Example  3.16

 

 Relation

 on is not anti symmetric because both and .

 In the digraph of this relation there are two directed edges between and .



Definition  3.17

 

그림입니다.

and       : A relation on a set is transitive



Example  3.18

 

The relation on defined by if , .

 Then

.

, and       .

Pairs of Form 순서쌍의 짝

     

Pairs of Form 순서쌍의 짝

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

  그림입니다.



 Example  3.19

 

 The relation

 on is not transitive.

   and       .

                                         No directed edge from to .

 


 Definition  3.20

 

그림입니다.

그림입니다.

 

Example  3.21

 

 Since the relation defined on the positive integers by

    if divides

 is reflexive, antisymmetric and transitive, is a partial order.

그림입니다.


그림입니다.



Definition  3.23

 

 Let be a relation from to . The inverse of , denoted , is the relation  from to defined by

.

 

 Example  3.24

 

그림입니다.

그림입니다.         그림입니다.


Definition  3.25

 

 Let be a relation from to .

Let  be a relation from to .

Let  be a subset of . is a subset of .

Then        is the composition of and .

And    is the relation from to .

                      = { (x, y) : (x, y) in R_1 and (y, z) in R_2 for some y in Y }.

 

                  (not    . )



 Example  3.26

 

그림입니다.

그림입니다.


Exercises   12, 13, 21, 23, 24, 32, 37, 48

 

 


3.4   Equivalence Relations


A set have balls.

The balls color are red, blue and green.

Let be a partition of .

그림입니다.


The next theorem shows that some relation is always reflexive, symmetric and transitive.


 Theorem  4.1

 

Let  be a partition of a set . Define to mean that for some set in , both and belong to . Then is reflexive, symmetric and transitive.

 

Proof 

Let .

By the definition of partition, belongs to some numbers of .

Thus and is reflexive.

   Suppose that .

Then both and belong to some set .

Since both and belong to , and is symmetric.

    Finally suppose that and .

Then both and belong to some set and both and belong to some set .

Since belong to exactly one member of , .

Therefore, both and belong to and .

We have shown that is transitive.                                          ■




Example  4.2

 

 The partition

 of .

 The relation on given by Theorem 4.1 contains the ordered pair ,      and because is in .

 The complete relation is

.


Definition  4.3

equivalence relation

 A relation on is caled an equivalence relation if is reflexive, symmetric, and transitive.

      Three properties:

 (1) , .    (reflexive)

 (2)        . (symmetric)

 (3) and        . (transitive)

 

Example  4.4

equivalence relation

 Relation is

.

 Relation is an equivalence relation on .

  is reflexive, symmetric and transitive.

  

Figure 4.2 The graph of the relation of Example 4.2


 is reflexive ( a loop at every vertex)

 is symmetric ( for every directed edge from to , there is a directed edge from to )

 is transitive (there is a directed edge from to and a directed edge from to , there is a directed edge from to ).


Example  4.5

equivalence relation

 Consider the relation

 on       is reflexive.

 ,       is symmetric

 , are       is transitive

 is reflexive, symmetric and transitive.

  is an equivalence relation on .



  Example  4.6

  Not an equivalence relation

 The relation on defined by if , is Not an equivalence relation  because

  is not symmetric (      ).

 But this relation is reflexive and transitive.

 

(See . )

 



Example  4.7

Not an equivalence relation

 The relation

 on is Not an equivalence relation

   is neither reflexive nor transitive.

        is not reflexive

 ,             is not transitive



Theorem  4.8

equivalence relation, partition

그림입니다.


Definition  4.9

equivalence class

그림입니다.



 Example  4.10

equivalence class

그림입니다.

그림입니다.

 

 

Example  4.13

 

 Relation

 on is reflexive, symmetric and transitive.

 Thus, is an equivalence relation.

Solution

The equivalence class containing consists of all such that .

Therefore,     .

The equivalence class containing consists of all such that .

Therefore,     .

The equivalence class containing consists of all such that .

Therefore,     .

The equivalence classes are

,     ,     .               ■


Example  4.14

equivalence relation

 Let . Define to mean that divides .

 Then is reflexive, symmetric and transitive. is an equivalence relation on .

Solution

그림입니다.

The equivalence classes consists of all with .

.

The equivalence classes consists of all with .

.

The equivalence classes consists of all with .

.

그림입니다.These three sets partition .

,   ,   .



 Theorem  4.16

 

그림입니다.

그림입니다.

 







Exercises  4, 15, 22, 29, 64



3.5  Matrices of Relations


A matrix is a relation from to .

We label the rows with the elements of (in some arbitrary order).

We label the columns with the elements of (in some arbitrary order).

If then set the entry in row and column to .

Otherwise,

This matrix is the matrix of the relation (relative to the orderings of and ).



 Example  5.1

 

그림입니다.



 Example  5.2

 

그림입니다.



 Example  5.3

 

그림입니다.


The matrix of a relation on a set (from to ), we use the same ordering for the rows as we do for the columns.

 

The matrix of a relation on a set is a square matrix.

A relation on the set is reflexive by examining the matrix of .

  The relation is reflexive       has ’s on the main diagonal.

  The relation is reflexive       for all .

A relation on the set is called symmetric by examining the matrix of .

  The relation is symmetric       for all and , the entry of is equal to the entry of .

  The relation is symmetric       , for all .

 



 Example  5.4

 

 Matrix of the relation

 on the set = relative to the ordering , , , is


  The above relation on the set is not symmetric.

  The above relation is not reflexive since   (2, 2) is not 1 on the main diagonal.

 


Example  5.5

 

 Let be a relation from to defined by

.

 Let be a relation from to defined by

.

Solution

The matrix of relative to the orderings , , and , is

.

The matrix of   relative to the orderings , and , , is

.

The product of these matrices

.

Let us interpret .

...

 is “almost” the matrix of the relation .


To obtain the matrix of the relation , we need only change all nonzero entries in to .               ( 2 -> 1)


Thus the matrix of the relation , relative to previously chosen ordering , , and , , is



 Theorem  5.6

 

 Let be a relation from to   and be a relation from to .

 Choose orderings of , and .

  is the matrix of . is the matrix of with respect to the orderings selected.

The matrix of the relation with respect to the ordering selected is obtained by   replacing each nonzero term in the matrix product by .


Example  5.7

 

 Matrix of the relation

 on , relative to the ordering , , , is

.      .

 

 Whenever is nonzero, then is nonzero.                           그림입니다.

 Thus, is transitive.

 Example  5.8

 

 Matrix of the relation

 on , relative to the ordering , , , , is

 .

 The entry in row , column of is nonzero, but the corresponding entry in is   zero. Therefore, is not transitive.


 

      Exercises  1, 4, 8, 11, 14, 16, 19, 25        [End of Ch. 3]

 

Copyright by SGLee, SKKU  sglee@skku.edu

http://matrix.skku.ac.kr/sglee/vita/LeeSG.htm