이산수학 () 관계와그특성 (Relations and Its Properties) 2010년봄학기강원대학교컴퓨터과학전공문양세 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 1
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), (0,b), (1,a), (2,b)} 는 A에서 B로의관계R로표현할수있다. 이때, (0,a) R 이므로, 0Ra라할수있다. 그러나, (1,b) R 이므로, 1Rb라할수있다. Page 4 2
Inverse Relations ( 역관계 ) Any binary relation R:A B has an inverse relation R 1 :B A, defined 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 aeatsb, then: 1 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 3
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 개이다. 그러므로, A x A 의부분집합개수는이된다. 결국, n 개원소를갖는집합에대한가능한관계의수는이다. 2 2 n 2 2 n Page 8 4
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 5
Symmetry & Antisymmetry ( 대칭성 ) A binary relation R on A is symmetric iff R = R 1, that is, if (a,b) R (b,a) 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 6
Transitivity ( 전이성 ) A relation R is transitive iff (for all a,b,c) (a,b) R (b,c) R (a,c) 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 7
Composite Relations ( 관계합성 / 결합 ) Let R:A B, and S:B C. Then the composite S R of R and S is defined 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 A ; R n+1 : R n R for all n 0. Page 15 Examples of Composite Relations (1/2) {1, 2, 3} 에서 {1, 2, 3, 4} 로의관계 R = {(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 8
Examples of Composite Relations (2/2) R = {(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 9