함수의 개념 중에서 단사, 전사, 전단사 함수의 예를 들어 보고,  그 대응되는 두 집합의 크기를 비교하여 보시오.

여러 가지 Discrete한 구조들에 관한 여러 이론학습을 위하여 기본적인 function의 개념을 알아보고 computer 이론에서 많이 사용되는 function에 대하여 학습하도록 한다.

     여러 가지 함수 개념

여러 가지 Discrete한 구조들에 관한 여러 이론들 학습하기 앞서서 먼저 기본적인 function의 개념을 알아보고 computer 이론에서 많이 사용되는 function에 대하여 학습하도록 합시다.

그리고 다음의 강의 내용은 B. Kolman, R.C. Bussy & S. Ross의 저서인

Discrete Mathematical Structures,

Prentice Hall Inc., 1996.

의 5장의 내용을 참고하여 학습하기 바랍니다.

(1) Functions

◆Let A and B be nonempty sets. A function

f  from A to B which is denoted f : A → B  is a

relation from A to B such that for all

a∈Dom(f ) ,f(a) contains just one element of

B .  Functions are also called mappings,

transformations or correspondences.

◆f is 'onto' if  Ran(f ) = B ,

  f is 'everywhere defined'Dom(f ) = A

  f is 'one to one'  if f(a) ≠ f(a') for two

  distinct a' and a'

  f is an injection if   f is one to one;

  f is a surjection if   f is onto;

  f is a bijection if   f is one to one and onto.

◆  If f  is one to one, onto and everywhere defined, f  is called an one to one correspondence between A and B.

◆A function f : A → B  is invertible if its inverse relation  f^-1 is also a function.

 

Example 1.    f : Z → Z , where  Z  is the set of all integers.   Then f(x) = 2x + 1 is onto and one to one, f(x) = x2 is  not one to one.

 

Theorem 2. Let f : A → B  be any functions. Then    (a)  f-1 º f = 1A    (b) f º 1A = f

 

Theorem 4. Let A and B be two finite sets with the same number of elements and let f : A → B be an everywhere defined function.   (a) If f is one to one, then f  is onto;   (b) If f is onto, then f  is one to one.

(2)Functions for Computer Science

◆Characteristic function of a set A

◆Mod function

     when z = kn + r,

              z = r (mod n) 

◆Floor function

  f(g)  is the largest integer

less than or equal to

◆Ceiling function

c(g)  is the smallest integer

greater than or equal to

◆f(z)=2^z - base 2 exponential function

◆Hashing function

- when we store and later examine a large number of data records

- attempt to assign an item to one of the lists at random

- hashing function is used to compute a list number from a key

(3) Permutation Functions

◆A bijection from a set to itself is called a permutation of A

(example)  Let  A = {1, 2, 3}

◆Let  b₁ , b₂ , ... , b_r  be r district elements of the set  A = { a₁ , a₂ , ... , a_n}.

The permutation p : A → A defined by

p (b₁) = b₂

p (b₂) = b₃

...

p (b_r-1) = b_r

p (b_r) = b₁

p (b_x) = x , if  x ∈ A , x  {b₁ , b₂, ... , b_r }

is called a cyclic permutation of length  r  or simply a cycle of length   r denoted by (b₁ , b₂, ... , b_r )

(example)  Let A = { 1, 2, 3, 4, 5 } Then the cycle (1, 3, 5 ) denotes the permutation

◆Two cycles of a set A  are said to be disjoint if no element of A appears in both cycles.

 

Theorem 1. A permutation of a finite set that is not the identity or a cycle can be written as a product of disjoint cycles of  length ≥ 2.

 

Example.                   P=( 7。8 )( 2。4。5 )( 1。3。6 )

◆A cycle of length 2 is called a

  transposition (호환)

- Every cycle can be written as a product of  transpositions.

  (b₁,b₂,...,b_r) = (b_1,b_r)_。(b_1,b_r-1)_。(b_1,b_r-2)_。...°_。(b_1,b₃)_。(b_1,b₂)

 

(Example)  P =(7,8)。  (2,4,5)。 (1,3,6)  (1,3,6) = ( 1,6)。 (1,3),     (2,4,5)= (2,5)。 (2,4)     P =(7,8)。 (2,5)。 (2,4)。  ( 1,6)。 (1,3)

◆A permutation of a finite set is called even if it can be written as a product of an even number of transposition and it is called odd if it can be written as a product of an odd number of transpositions.

 

(Example) P=(3,5,6)。(1,2,4,7) P=(3,6)。 (3,5)。 (1,7)。 (1,4)。 (1,2) ∴P is an odd permutation

(4) Growth of Functions

◆ f is O(g) if there exist constants  c and k such that |f(n)|≤c ^. |g(n)| for all n≥k

◆ f  and g have the same order if f  is O(g) and g is O(f  )

- if f is O(g) but  g is not O(g) , is lower order than

- a relation   θis defined as follows

◆ f θg  iff  f and  g have the same order (f  = θ(g )or g = θ(f ))

 

Theorem 1. The relation θ is an equivalence relation

◆A simple function in the equivalence class is used to represent the order of all functions in that class

◆Rules for determining the θclass  of a function

1. (1) functions are constant and have zero growth, the slowest growth posible.

2. (lg(n)) is lower than (n^k ) if k > 0. This means that any logarithemic function

grows more slowly than any power function with positive exponent.

3. (n^a ) is lower than (n^b) if and only if a<b.

4. (aⁿ ) is lower than (bⁿ) if and only if a<b.

5. (n^k) is lower than (aⁿ) for any power nk and a>1. This means that any exponential function with base greater than 1 grows more rapidly than any power function.

6. If r is not zero, than (n^f ) = (f ) for any function f

7. If h is nonzero function and (f ) is lower than (or the same as) (g ). then (fh)is lower than (or the same as) (gh).

8. If  ( f) is lower than (g)than (f+g)= (g).

여러 가지 Discrete한 구조들에 관한 여러 이론학습을 위하여 기본적인 function의 개념을 알아보고 computer 이론에서 많이 사용되는 function에 대하여 학습하도록 한다.

 equivalence relation 이란 무엇인가 설명하고, 그 예를 들어 보시오.

 여러 가지 Discrete한 구조들에 관한 여러 이론들 중에서 relation과 digraph에 관하여 학습하도록 한다.

     Relations and Digraphs

여러 가지 Discrete한 구조들에 관한 여러 이론들 중에서 먼저

relation과 digraph에 관하여 학습하도록 합시다.

그리고 다음의 강의 내용은 B. Kolman, R.C. Bussy & S. Ross의 저서인

Discrete Mathematical Structures,

Prentice Hall Inc., 1996.

의 5장의 내용을 참고하여 학습하기 바랍니다.

(1) Product Sets and Partitions

◆Ordered pair (a,b) is a listing of objects a and b in a prescribed order

◆Product Set (Cartesian Product):

For two nonempty set A and B

A x B = { (a,b) | a∈A ,b∈B }

 

(Example)   Let  A = {1, 2, 3}, B = {r,s}; then A x B = {(1,r) , (1,s) , (2,r) , (2,s) , (3,r) ,(3,s)}

◆Generalization of Cartesian product

A₁ x A₂ x , ..., x A_m of the nonempty sets A₁,

A₂ , ..., A_m  is defined as

{(a₁, a₂ , ..., a_n) | a_i∈A_{i ,} i = 1, 2, ... ,m }

◆A Partition or quotient set of a nonempty set A is a collection P of nonempty subsets of A such that

1. Each element of A belongs to one of the sets in P

2. If A₁ and  A₂ are distinct element of  P then A₁ ∩ A₂ = Ø

- P⊆ P(A) , that is a partition of a set A  is a subset of the power set of A

(2) Relations and Digraphs

◆A relation R from A to  B is a subset of

   A x B

- If R ⊆A x B  and , (a,b)⊆R , 

  a is related to b by R and we write

          a R b

 

(Example) Let A = B = {1, 2, 3}. Define a relation R as follows a R b  iff   a < b Then R ={( 1, 2 )( 1, 3 )( 2, 3 )}

◆If R ⊆A x A  then R is said to be a relation

   on A

◆Let R ⊆A x B

- Domain of  R : the set of  elements in  A which are related to some elements in B

- Range of R : the set of elements in B which are related to some elements in A

-R-relative set of  x ,

  R(x) = { y∈B |x R y }

- if A₁ ⊆ A then R -relative set of A₁ ,

R(A₁)={y∈B | x R y for  some x in A₁}

 

(Example)  A = B = {a,b,c,d}  , R = {(a,b) (a,d) (b,c) (c,a)} Dom (R)={a,b,c}    Ran (R)={a,b,c,d} R(a)={b,d}             R{(b,c)} = {a,c}

◆The matrix of a Relation

- If  A = {a₁, a₂, ..., a_n}    B = {b₁, b₂, ..., b_n} and R ⊆ A x B

we can represent R by mxn matrix M_R=[m_ij]

 

(Example)  A = {a,b}  B={1,2,3}  R={(a,1)(b,2)(b,3)}  then

◆Let  R ⊆A x A

- Digraph of   

◆Let a∈ A then the indegree of a is the number of b∈ A such that (b,a) ∈R     

the outdegree of a is the numberof b∈ A  such that (b,a) ∈R  = |R(a)|

(3) Paths in Relations and Digraphs

◆Let R be a relation on a set A

A path of length n in R from a to b is a finite

sequence  π=a ,x₁, x₂ , ... , x_n-1 , b   

such that   a R x₁, x₁ R x₂ , ... , x_n-1 R b

A path that begins and ends at the same vertex is called a cycle.

◆Define Rⁿ as follows : x Rⁿ y  means that there is a path of length n from x to y in  R

- R^∞ is defined as follows :x R^∞ y means that there is a path from x to y in  called "connectivity relation"

 

Theorem 1. Let's define the Boolean product of A and B (A⊙B ) to be C=[cij] such that         cij = 1    if  aik =1 and bkj = 1 for some k               0   otherwise      Then    ( MR⊙MR = (MR)O2

 

Theorem2.

Proof :  By the induction, we can prove

Theorem 2.

◆

◆Reachability relation R^* of  R is defined as follows :

x R^*y means that x = y or x R^∞y

where I_n is the  n x n Identity matrix

(4) Properties of Relations

◆Reflexive and irreflexive relations

- A relation R on a set A is reflexive if (a,a) ∈ R  for all a ∈ A

- A relation R on a set A is irreflexive if (a,a)  R  for all a ∈ A

 

(Example) A = {1,2,3,4}    a R b   iff   a≤b → reflexive a R b   iff    a<b  → irreflexive

◆Symmetric, asymmetric and antisymmetric relations

- A relation R on a set A is symmetric

if whenever a R b   then  b R a  

- A relation on a set is asymmetric

if whenever a R b then ^~b R a  

- relation R on a set A is antisymmetric if whenever a R b  and b R a   then  a = b

 

 

(Example)  A = {1,2,3,4}     R = {(1,2)(2,2)(3,4)(4,1)}   R is not symmetric, not asymmetric   since (2,2)∈R, but antisymmetric

◆Properties of matrix

- The matrix M_R = [m_ij] of a symmetric relation satisfies the property that

if m_ij =1 then m_ji =1

Therefore so that M_R is a symmetric matrix

- The matrix M_R = [m_ij]  of an asymmetric relation R satisfies the property that if  m_ij =1  then m_ij =0

- The matrix M_R = [m_ij] of an antisymmetric relation R satisfies the property that if  i ≠ j then m_ij =0 or m_ji =0

◆  In the digraph of a symmetric relation R , if two vertices are connected by an edge they must always be connected in both direction.

  If we replace these two edges with one undirected edge the resulting diagram is called graph of the symmetric relation.

◆symmetric relation R on a set A will be called connected if there is a path from any element of A to any other element of A

◆Transitive relations

-A relation R on a set A is transitive if whenever aRb and  bRc  then aRc

 

(Example) A=Z      aRb  iff a<b  then R is transitive

 

Theorem 1. A relation R is transitive iff it satisfies the following property : If there is a path of length greater than 1 from a to b, then there is a path of length 1 from a to b.

(5) Equivalence Relations

◆A Relation R on a set A is called equivalence relation if it is reflexive. symmetric and transitive

Exampe.  Let A = and

          { (a,b) ∈ A x B |2 divides a-b }

We write aRb as a≡b (mod 2) read "a is congruent to b mod 2"

Show that R is an equivalence relation

Proof. First a≡a  (mod 2) since 2 divide a-a = 0 second if a≡b (mod 2) then b-a = 2(-k) hence a≡b (mod 2) . Finally, suppose that a≡b (mod 2) and b≡c (mod 2)  then a-b = 2k₁, and b-c = 2k₂ adding the two equations yields a-c = 2( k₁ + k₂ ) Hence (mod 2)

 

Theorem 1. Let P be a partition of a set A , and aRb iff a and b are members of the same block. Then R is an equivalence relation on A→R is called the equivalence relation determined by P

 

Lemma 1. Let R be an equivalence relation on A and let a∈A, b∈A then      aRb  iff  R(a) = R(b)

Proof. (i) Suppose R(a) = R(b), since R is reflexive b∈R(b),

therefore b∈R(a), so aRb

(ii) Suppose aRb , b∈R(a) and since R is symmetric a∈R(b), let x∈R(b) then since R is transitive and b∈R(a), x∈R(a) →R(b)⊆R(a)

let x∈R(a) , in the similar way x∈R(b)→R(a)⊆R(b).  Therefore we have

R(a) = R(b).

 

Theorem 2. Let  R be an equivalence relation on A and let P be the collection of all distinct relative sets R(a) ,a∈A then P is a partition of A and R is the equivalence relation determined by P.

Proof. We must show the following Properties.

(a) Every element of A belong to some relative set.

(b) It R(a) and R(b) are not identical then R(a) ∩ R(b) = 0

(a) is true since R(a) = 0 by reflexivity of  R

(b) is equivalent to "If R(a) ∩ R(b) ≠0 then R(a) = R(b)."

Assume that c∈ R(a) ∩ R(b) then aRc and bRc, since R is symmetric cRb.

By the transitivity aRb

Then R(a) = R(b) by Lemma 1.

(6) Computer representation of Relations and Digraphs

Refer the pp. 136-145 of the book :

B. Kolman, R.C. Bussy & S. Ross,

Discrete Mathematical Structures,

Prentice Hall Inc., 1996.

(7) Manipulation of Relations

◆Let R and S be relations from A to B then R, S ⊆A x B

- complement of is defined by if and only if a R b'

- R∩S : Intersection of R and S

- R∪S : Union of R and S

- inverse of R , R^-1 is defined by b R^-1a if and only if a R b

Dom(R^-1) = Ran(R) , Ran(R^-1) = Dom(R)

-M_R∩S = M_R∧ M_S

-M_R∪S = M_R ∨M_S

-M_R-1 = (M_R )^T

-

 

◆Closures

- The closure of  R with respect to a Property : the smallest relation R₁ that contains R and possesses the Property

◆Composition

- Let R ⊆A x B, S ⊆B x C

composition of R  and S is defined as follows.

a(R°° S)b  if a R b and b R c for some b∈B

- Let R and S be relations on A

then  M_{R°° S=} M_R⊙M_S

 

Theorem 1.   Let  R⊆A x B, S ⊆B x C,  T ⊆C x D.  Then    T°°( S°° R ) = (T°° S)°°  R

Proof. M_{T°°( S°° R ) =}M_{S°° R}⊙M_{T =}(M_R⊙ M_S)⊙M_T

M_{(T°° S°)°° R =}M_R⊙M_{T °S}⊙M_{T =}M_R⊙( M_S⊙M_T)

(8) Transitive Closure and      Warshall's Algorithm

 

Theorem 1. Let R be a relation on A then R∞ is the transitive closure of R.

Proof.R^∞ is transitive since if a R^∞ b and b R^∞ c then a R^∞ c

We must show that R^∞ is the smallest transitive relation containing R

Let S be any transitive relation on A and R⊆S 

Since S is transitive,

Since R⊆S , R^∞⊆S^{∞ ,} Therefore R^∞⊆S^∞ ⊆S

 

Theorem 2. Let  A be a set with |A| = n  and let R be a relation on A.  Then    R∞= R ∪R2 ∪... ∪R*.

Proof. The length of the shortest path from i to j cannot be more than n-1.

◆Warshall's Algorithm

- an efficient method for finding the transitive closure of a relation R on a set A

- let  R be a relation on a set A = {a₁ , a₂ , ... , a_n}

- let x₁ , x₂ , ... , x_m be a path in R then

 x₂ ,x₃ ,...,x_m-1 are interior vertices of the  path.

- we define a Boolean matrix W_k as follows ; W_k[ij] = 1 iff there is a path from a_i to a_j in R whose interior vertices come from the set {a₁ , a₂ , ... , a_n}

then

- suppose that W_k [t_ij] and W_k-1 [s_ij]

t_ij = 1  iff    (1) s_ij = 1  or  

                 (2)s_ik = 1 and s_kj = 1

The Algorithm of Warshall

        1. closure ← Mat

2. For K= 1 to N

3. For I = 1 to N

For J = 1 to  N

closure[I,J ] = closure[I,J]∨ ( closure[I,K]∧ closure[K,J] )

end of algorithm Warshall.

 여러 가지 Discrete한 구조들에 관한 여러 이론들 중에서 relation과 digraph에 관하여 학습하도록 한다.