이산수학 () 관계와그특성 (Relations and Its Properties) 2011년봄학기 강원대학교컴퓨터과학전공문양세
Binary Relations ( 이진관계 ) Let A, B be any two sets. A binary relation R from A to B, written R:A B, is a subset of A B. (A 에서 B 로의이진관계 R 은 R:A B 로표기하며 A B 의부분집합이다.) E.g., let < : N N : {(n,m) n < m} The notation a R b or arb means (a,b) R. E.g.,, a < b means (a,b) < If arb, we may say a is related to b (by relation R). (arb 이면, a 는 ( 관계 R 에의해서 ) b 에관계된다 고말한다.) Page 2
Complementary Relations ( 보수관계 ) Let R:A B be any binary relation. Then, R:A B, the complement of R, is the binary relation defined by R : {(a,b) (a,b) R} = (A B) R Note the complement of R is R. Example: < = {(a,b) (a,b) <} = {(a,b) (a<b)} = Page 3
Complementary Relation Example 예제 : A = {0, 1, 2}, B = {a, b} 라하면, {(0,a), (0b) (0,b), (1a) (1,a), (2b)} (2,b)} 는 A 에서 B 로 의관계 R 로표현할수있다. 이때, (0,a) R 이므로, 0Ra 라할수있다. 그러나, (1,b) R 이므로, 1Rb 라할수있다. Page 4
Inverse Relations ( 역관계 ) Any binary relation R:A B has an inverse relation R 1 :B A, defined d by R 1 : {(b,a) (a,b) R}. E.g., < 1 = {(b,a) a<b} = {(b,a) b>a} = >. E.g., if R:People Foods is defined by arb a eats b, then: br 1 a b is eaten by a. (Passive voice.) (R 1 will be is eaten by. ) Page 5
Relations on a Set A (binary) relation from a set A to itself is called a relation on the set A. ( 집합 A 에서 A 로의관계를집합 A 상의관계라한다.) E.g., the < relation from earlier was defined as a relation on the set N of natural numbers. ( < < 은정수집합 N 에대한관계이다.) The identity relation I A on a set A is the set {(a,a) a A}. ( 집합 A 에대한항등관계 I A 는집합 {(a,a) a A} 를의미한다.) Page 6
Examples of Relations on a Set (1/2) 예제 : A = {1, 2, 3, 4} 라할때, 관계 R = {(a,b) a divides b} 에속하는순서쌍은? A x A 의원소인 (a,b) 에있어서 b 를 a 로나눌수있는순서쌍을구한다. 즉, R = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4)} 이다. Page 7
Examples of Relations on a Set (2/2) 예제 : n 개의원소를갖는집합에는몇개의관계가있는가? 정의에의해, 집합 A 에대한관계는 A x A 의부분집합이다. A x A 의원소개수는 n 2 이다. 또한, m 개의원소를가지는집합의부분집합개수는 2 m 개이다. 2 그러므로, A x A의부분집합개수는 2 n 이된다. 2 결국, n개원소를갖는집합에대한가능한관계의수는 2 n2 이다. Page 8
Reflexivity ( 반사성 ) A relation R on A is reflexive if a A, ara. E.g., the relation : {(a,b) a b} is reflexive. 즉, (a,a) 를원소로가지면반사적 (reflexive) 이라고이야기한다. A relation is irreflexive iff its complementary relation is reflexive. Example: < is irreflexive. Page 9
Reflexivity Example 예제 : 양의정수집합에대해 나누다 관계는반사적인가? 임의의양의정수 a 에대해 a a 가성립한다. 즉, 양의정수 a 는자기자신 a 로나누어떨어진다. 따라서, 나누다 는양의정수집합에대해반사적이다. Page 10
Symmetry & Antisymmetry ( 대칭성 ) A binary relation R on A is symmetric iff R = R 1, that is, if (a,b) R R (b,a) R. R E.g., = (equality) is symmetric. < is not. is married to is symmetric, but likes is not. 즉, (a,b) 가 R 의원소일때, 반드시 (b,a) 도원소이면대칭적이라한다. A binary relation R is antisymmetric if (a,b) R (b,a) R. < is antisymmetric, likes is also antisymmetric. Page 11
Symmetry & Antisymmetry Example 예제 : 양의정수집합에대한 나누다 관계는대칭인가? 반대칭인가? 반례 (counterexample) 를들어반대칭임을보인다. 즉, 1 2 이지만 2 1 이므로, 반대칭이다. Page 12
Transitivity ( 전이성 ) A relation R is transitive iff (for all a,b,c) (a,b) R R (b,c) R R (a,c) R. R A relation is intransitive if it is not transitive. Examples: is an ancestor of is transitive. likes is intransitive. Page 13
Transitivity Example 예제 : 양의정수집합에대한 나누다 관계가전이적인가? 양의정수 a, b, c 에대해서, a 가 b 를나누고, b 가 c 를나눈다고하자. 즉, a b, b c 가성립한다고가정하자. 그러면, b = ak, c = bl 인양의정수 k 와 l 이있다. 따라서, c = a(kl) 이성립하므로, a 는 c 를나눌수있다. 즉, a c 가성립하므로, 나누다 는전이적이다. Page 14
Composite Relations ( 관계합성 / 결합 ) Let R:A B, and S:B C. Then the composite S R of R and S is defined d as: S R = {(a,c) b: arb bsc} ((a,b) R 이고 (b,c) S 이면, S R 은 (a,c) 을원소로하는관계이다.) Note function composition f g is an example. The n th power R n of a relation R on a set A can be defined recursively by: R 0 : I n+1 : n A ; R R RR for all n 0. Page 15
Examples of Composite Relations (1/2) 예제 : {1, 2, 3} 에서 {1, 2, 3, 4} 로의관계 R = {(1,1), 1) (1,4), (2,3), (3,1), (3,4)} 과, {1, 2, 3, 4} 에서 {0, 1, 2} 로의관계 S = {(1,0), (2,0), (3,1), (3,2), (4,1)} 가있을때, R 과 S 의합성 S R 은? S R 의구성을위해서는, R 에속한순서쌍의두번째원소와 S 에속한 순서쌍의첫번째원소가같은것을찾으면된다. 예를들어, R 의 (2,3) 과 S 의 (3,1) 을바탕으로 S R 의순서쌍 (2,1) 을만 든다. 결국, S R = {(1,0), (1,1), (2,1), (2,2), (3,0), (3,1)} 이된다. Page 16
Examples of Composite Relations (2/2) 예제 : R = {(1,1), 1) (2,1), (3,2), (4,3)} 이라하자. n = 2, 3, 4, 일때, 거듭제곱 R n 을구하라. R 2 = R R = {(1,1), (2,1), (3,1), (4,2)} R 3 = R 2 R = {(1,1), (2,1), (3,1), (4,1)} R 4 = R 3 R = {(1,1), (2,1), (3,1), (4,1)} R n = R n-1 R = {(1,1), (2,1), (3,1), (4,1)} You can get R n using induction. ( 교재의 R 3 와 R 4 는잘못구해진것으로보임 ) Page 17