(Relations and Its Properties) 이산수학 (Discrete Mathematics) 7.1 관계와 그 특성 (Relations and Its Properties) 2006년 봄학기 문양세 강원대학교 컴퓨터과학과

We will cover … in Chapter 7. 7.1 Relations & Its Properties $7.1 Relations and Its Properties (관계, 그리고 그 특성) $7.3 Representing Relations (관계의 표현) $7.5 Equivalence Relations (동치 관계)

Binary Relations (이진 관계) 7.1 Relations & Its Properties 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에 관계된다”고 말한다.)

Complementary Relations (보수 관계) 7.1 Relations & Its Properties 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)} = ≥

Complementary Relation Example 7.1 Relations & Its Properties 예제 3: 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라 할 수 있다.

Inverse Relations (역 관계) 7.1 Relations & Its Properties 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  a eats b, then: b R−1 a  b is eaten by a. (Passive voice.) (R−1 will be “is eaten by.”)

Relations on a Set 7.1 Relations & Its Properties 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 IA on a set A is the set {(a,a)|aA}. (집합 A에 대한 항등 관계 IA는 집합 {(a,a)|aA}를 의미한다.)

Examples of Relations on a Set (1/2) 7.1 Relations & Its Properties 예제 4: 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)}이다.

Examples of Relations on a Set (2/2) 7.1 Relations & Its Properties 예제 6: n개의 원소를 갖는 집합에는 몇 개의 관계가 있는가? 정의에 의해, 집합 A에 대한 관계는 A x A의 부분집합이다. A x A의 원소 개수는 n2이다. 또한, m개의 원소를 가지는 집합의 부분집합 개수는 2m개 이다. 그러므로, A x A의 부분집합 개수는 이 된다. 결국, n개 원소를 갖는 집합에 대한 가능한 관계의 수는 이다.

A relation R on A is reflexive if aA, aRa. Reflexivity (반사성) 7.1 Relations & Its Properties 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. Note: “likes” between people is not reflexive, but not irreflexive either. (Not everyone likes themselves, but not everyone dislikes themselves either.)

예제 9: 양의 정수 집합에 대해 “나누다” 관계는 반사적인가? Reflexivity Example 7.1 Relations & Its Properties 예제 9: 양의 정수 집합에 대해 “나누다” 관계는 반사적인가? 임의의 양의 정수 a에 대해 a|a가 성립한다. 즉, 양의 정수 a는 자기 자신 a로 나누어 떨어진다. 따라서, “나누다”는 양의 정수 집합에 대해 반사적이다.

Symmetry & Antisymmetry (대칭성) 7.1 Relations & Its Properties 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, “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.

Symmetry & Antisymmetry Example 7.1 Relations & Its Properties 예제 12: 양의 정수 집합에 대한 “나누다” 관계는 대칭인가? 반대칭인가? 반례(counterexample)를 들어 반대칭임을 보인다. 즉, 1|2 이지만 2|1이므로, 반대칭이다.

A relation is intransitive if it is not transitive. Transitivity (전이성) 7.1 Relations & Its Properties 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.

예제 15: 양의 정수 집합에 대한 “나누다” 관계가 전이적인가? Transitivity Example 7.1 Relations & Its Properties 예제 15: 양의 정수 집합에 대한 “나누다” 관계가 전이적인가? 양의 정수 a, b, c에 대해서, a가 b를 나누고, b가 c를 나눈다고 하자. 즉, a|b, b|c가 성립한다고 가정하자. 그러면, b = ak, c = bl인 양의 정수 k와 l이 있다. 따라서, c = a(kl)이 성립하므로, a는 c를 나눌 수 있다. 즉, a|c가 성립하므로, “나누다”는 전이적이다.

Composite Relations (관계 합성/결합) 7.1 Relations & Its Properties 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 nth power Rn of a relation R on a set A can be defined recursively by: R0 :≡ IA ; Rn+1 :≡ RnR for all n≥0.

Examples of Composite Relations (1/2) 7.1 Relations & Its Properties 예제 20: {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)}이 된다.

Examples of Composite Relations (2/2) 7.1 Relations & Its Properties 예제 22: R = {(1,1), (2,1), (3,2), (4,3)}이라 하자. n = 2, 3, 4, … 일 때, 거듭 제곱 Rn을 구하라. R2 = RR = {(1,1), (2,1), (3,1), (4,2)} R3 = R2R = {(1,1), (2,1), (3,1), (4,1)} R4 = R3R = {(1,1), (2,1), (3,1), (4,1)} … Rn = Rn-1R = {(1,1), (2,1), (3,1), (4,1)} You can get Rn using “induction.” (교재의 R3와 R4는 잘못 구해진 것으로 보임…)