제 4 장 관 계.

Presentation on theme: "제 4 장 관 계."— Presentation transcript:

1 제 4 장 관 계

2 목차 4.1 관 계 4.2 관계의 표현 4.3 관계의 합성 4.4 동치 관계 4.5 관계의 폐쇄 성질 4.6 부분 순서와 속

3 4.1 관 계 정의 4-1 n-항 관계(n-ary relation) 순서쌍의 집합 곱 집합 A1×A2× …×An의 부분집합 R
4.1 관 계 순서쌍의 집합 관계를 표현하는 가장 기본적인 표기법 RØ ＝ 이면 R : 영 관계(empty relation), R＝A1×A2×…×An이면 R : 전체 관계(universal relation) 정의 n-항 관계(n-ary relation) 곱 집합 A1×A2× …×An의 부분집합 R : 집합 A1, A2, …, An 에서의 n-항 관계 R＝{(a1, a2, …, an) | ai∈Ai} (n - 투플의 집합)

4 4.1 관 계 정의 4-2 2-항 관계(binary relation)
4.1 관 계 정의 항 관계(binary relation) n = 2, R⊆A1×A2일 때, R : A1에서 A2로의 이항 관계(a, b) ∈ R이면 aRb , (a, b) ∈ R이면 aRb 정의역(domain): 순서쌍에서 모든 첫 번째 원소의 집합 치역(range): 순서쌍에서 모든 두 번째 원소의 집합 집합 A에 대한(on a set A) 관계 : A1＝A2＝A일 때 A에서 A로 가는 이항 관계

5 4.1 관 계 【예제 4.1】 두 집합 A＝{1, 2}, B＝{3, 4}일 때, A 에서 B 로의 모든 관계를 나타내어라.
4.1 관 계 【예제 4.1】 두 집합 A＝{1, 2}, B＝{3, 4}일 때, A 에서 B 로의 모든 관계를 나타내어라. [풀이] A×B＝{(1, 3), (1, 4), (2, 3), (2, 4)} ∴ 모든 관계의 개수 ː 24＝16 Ф {(1,3)} {(1,4)} {(2,3)} {(2,4)} {(1,3), (1,4)} {(2,3), (2,4)} {(1,3), (2,3)} {(1,4), (2,4)} {(1,3), (2,4)} {(1,4), (2,3)} {(1,3), (1,4), (2,3)} {(1,3), (1,4), (2,4)} {(1,3), (2,3), (2,4)} {(1,4), (2,3), (2,4)} {(1,3), (1,4), (2,3), (2,4)}

6 4.1 관 계 【예제 4.2】 집합 A＝{1, 2, 3, 4}에 대한 관계 R을 R＝{(a, b) ∈ A×A | b가 a로 나누어진다}라고 할 때, R의 모든 순서쌍을 나열하라. [풀이] R＝{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}

7 4.1 관 계 【예제 4.3】 정수 집합에 대한 관계들이 다음과 같을 때,
4.1 관 계 【예제 4.3】 정수 집합에 대한 관계들이 다음과 같을 때, R1＝{(a, b) | a < b} R2＝{(a, b) | a>b } R3＝{(a, b) | a＝b 또는 a＝－b} R4＝{(a, b) | a＝b} R5＝{(a, b) | a＝b＋1} R6＝{(a, b) | a＋b < 3} 각각의 순서쌍 (1, 1), (1, 2), (2, 1), (1, －1), (2, 2)를 포함하는 관계들을 모두 구하라. [풀이] (1, 1) : R1, R3, R4, R6 (1, 2) : R1, R6 (2, 1) : R2, R5, R6 (1, －1) : R2, R3, R6 (2, 2) : R1, R3, R4

8 4.1 관 계 정의 4-3 역관계(inverse relation) R-1＝{(b, a)|(a, b)∈R}
4.1 관 계 정의 역관계(inverse relation) R이 관계일 때 R의 역관계 : R-1 R-1＝{(b, a)|(a, b)∈R}

9 4.1 관 계 【예제 4.4】R＝{(1, 1), (1, 6), (5, 1), (5, 8), (7, 2)} 일 때, R－1를 구하라. [풀이] R－1＝{(1, 1), (6, 1), (1, 5), (8, 5), (2, 7)}

10 4.2 관계의 표현 (1) 화살표(arrow diagram)
4.2 관계의 표현 (1) 화살표(arrow diagram) 집합 A, B가 있을 때 a∈A와 b∈B가 aRb이면 이 관계를 a 에서 b로 가는 화살표로 표현

11 4.2 관계의 표현 【예제 4.5】 A＝{1, 2, 3, 4,} B＝{a, b, c, d}이고 관계 R＝{(1, c), (1, d), (2, b), (3, a), (3, c), (4, a)}일 때, R을 화살표를 사용해서 나타내어라.

12 4.2 관계의 표현 [풀이]

13 4.2 관계의 표현 (2) 관계 행렬(relation matrix)
4.2 관계의 표현 (2) 관계 행렬(relation matrix) R : A＝{a1, a2, …, am} 에서 B＝{b1, b2, …, bn} 로의 관계. 관계 R은 행렬 MR＝(mij) (단, 1≤i≤m, 1≤j≤n) 로 표현

14 4.2 관계의 표현 【예제 4.6】 집합 A＝{1, 2, 3}, B＝{1, 2}에 대하여, A에서 B로의 관계 R이 "a∈A, b∈B일 때 a>b이다"로 주어진 경우 R을 관계 행렬(relation matrix)로 표현하라. [풀이] R＝{(2, 1), (3, 1), (3, 2)}이므로, R의 관계 행렬은

15 4.2 관계의 표현 【예제 4.7】 A＝{a1, a2, a3}, B＝{b1, b2, b3, b4}이고, 관계 R에 대한 관계 행렬이 다음과 같이 표현될 때, R에 대한 순서쌍을 구하라

16 4.2 관계의 표현 [풀이] 관계 R은 mij＝1인 순서쌍(ai, bj)의 집합이므로
4.2 관계의 표현 [풀이] 관계 R은 mij＝1인 순서쌍(ai, bj)의 집합이므로 R＝{(a1, b2), (a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3)}

17 4.2 관계의 표현 【예제 4.8】 집합 A＝{1, 2, 3}일 때, 관계 R＝{(1, 1), (1, 3), (2, 3), (3, 2)}이고, S＝{(1, 1), (1, 3), (2, 1), (2, 2), (3, 3)}이다. 이 때 MRS와 MRS 를 각각 구하라.

18 4.2 관계의 표현 [풀이]

19 4.2 관계의 표현 (3) 방향 그래프(directed graph) 정의 4-4 방향 그래프
4.2 관계의 표현 (3) 방향 그래프(directed graph) 정의 방향 그래프 정점(vertex)들의 집합 V와, V의 각 원소들로 구성된 순서쌍인 간선(edge)의 집합 E로 구성

20 4.2 관계의 표현 【예제 4.9】 정점: a, b, c, d와 연결선: (a, b), (a, d), (b, b), (b, d), (c, a), (c, b), (d, b)로 구성된 방향 그래프는 ? [풀이]

21 4.2 관계의 표현 【예제 4.10】방향 그래프로 표시된 관계 R의 순서쌍 ? ◀ 책 그림 참조 ▶ [풀이]
4.2 관계의 표현 【예제 4.10】방향 그래프로 표시된 관계 R의 순서쌍 ? ◀ 책 그림 참조 ▶ [풀이] R＝{(1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (3, 1), (3, 3), (4, 1), (4, 3) }

22 4.2 관계의 표현 【예제 4.11】 집합 A＝{1, 2, 3, 4, 5, 6, } 관계 {R＝(m, n)∈A×A|mod(m, n)＝0, m≠ n, 단, mod 연산은 n/m의 나머지를 구하는 연산자} 관계 R에 대한 방향 그래프 ? [풀이]

23 4.3 관계의 합성 정의 4-5 합성 관계(composite relation) 집합 A, B, C,
4.3 관계의 합성 정의 합성 관계(composite relation) 집합 A, B, C, Rː A→B관계, S : B→C관계 합성 관계 R ◦ S 의 정의 R ◦ S＝{(a, c)∈A×C | (a, b)∈R이고 (b, c)∈S인, b∈B 가 존재한다}

24 4.3 관계의 합성 【예제 4.12】 A＝{2, 3, 8, 9}, B＝{4, 6, 18}, C＝{1, 4, 7, 9}이다. Rː A→B관계, S : B→C관계, R ◦ S를 구하라. R＝{(a, b) | a∈A, b∈B, mod(b, a)＝0} S＝{(b, c) | b∈B, c∈C, b≤c}

25 4.3 관계의 합성 [풀이] R＝{(2, 4), (2, 6), (2, 18), (3, 6), (3, 18), (9, 18)},
4.3 관계의 합성 [풀이] R＝{(2, 4), (2, 6), (2, 18), (3, 6), (3, 18), (9, 18)}, S＝{(4, 4), (4, 7), (4, 9), (6, 7), (6, 9)} ∴ R ◦ S＝{(2, 4), (2, 7), (2, 9), (3, 7), (3, 9)}

26 4.3 관계의 합성 【예제 4.13】 A＝{1, 2}, B＝{3, 4}, C＝{5, 6}이고, 관계 R＝{(1, 3), (1, 4)}, S＝{(3, 5), (4, 5)}이다. 이 때 R ◦ S을 구하라. [풀이] R ◦ S＝{(1, 5)}

27 4.3 관계의 합성 【예제 4.14】 합성 관계 R ◦ S를 구하여 관계 행렬로 표현하라.

28 4.3 관계의 합성 [풀이]

29 4.3 관계의 합성 ☞ 정리 4-1 집합 A, B, C, D, R⊆A×B, S⊆B×C, T⊆C×D 일때, R ◦ (S ◦ T)＝(R ◦ S) ◦ T 이다.

30 4.3 관계의 합성 [증명] R ◦ (S ◦ T)⊆(R ◦ S) ◦ T와 (R ◦ S) ◦ T⊆R ◦ (S ◦ T)를 동시에 만족함을 보인다. (1) R ◦ (S ◦ T)⊆(R ◦ S) ◦ T 증명 (x, y) ∈ R ◦ (S ◦ T)라 가정. (x, z) ∈ R, (z, y) ∈ S ◦ T, z ∈ B가 존재. (z, y)∈S ◦ T이므로, (z, w)∈S, (w, y)∈T, w∈C가 존재 (x, z)∈R, (z, w)∈S이므로 (x, w)∈R ◦ S (x, w)∈R ◦ S이고 (w, y)∈T이므로, (x, y)∈(R ◦ S) ◦ T ∴ R ◦ (S ◦ T)⊆(R ◦ S) ◦ T (2) (R ◦ S) ◦ T⊆R ◦ (S ◦ T)도 같은 방법으로 증명.

31 4.3 관계의 합성 ☞ 정리 4-2 A, B, C가 집합이고, R⊆A×B와 S⊆B×C일 때, (R ◦ S) －1＝S－1 ◦ R－1이다.

32 4.3 관계의 합성 [증명] (R ◦ S) －1⊆S－1 R－1와 S－1 R－1⊆(R ◦ S) －1를 동시에 만족함을 보인다.
4.3 관계의 합성 [증명] (R ◦ S) －1⊆S－1 R－1와 S－1 R－1⊆(R ◦ S) －1를 동시에 만족함을 보인다. (1) (R ◦ S)－1 ⊆S－1 R－1 증명 : (y, x)∈(R ◦ S) －1 가정, (x, y)∈R ◦ S이므로 (x, z)∈R, (z, y)∈S인 z∈B가 존재 (x, z)∈R이므로 (z, x)∈R－1, (z, y)∈S이므로 (y, z)∈S－1 (y, z)∈S－1, (z, x)∈R－1이므로, (y, x)∈S－1 R－1 ∴ (R ◦ S) －1⊆S－1 R－1 (2) S－1 R－1⊆(R ◦ S) －1 : 같은 방법으로 증명

33 4.3 관계의 합성 【예제 4.15】 집합 {1, 2, 3}에 대한 관계 R이 다음과 같을 때 R2을 관계 행렬과 방향 그래프로 표시하여라.

34 4.3 관계의 합성 [풀이] R2＝{(1, 1), (2, 2), (3, 1), (3, 2), (3, 3)}

35 4.3 관계의 합성 【예제 4.16】 R＝{(1, 1), (3, 1), (2, 3), (4, 2)}일 때, R2, R3, R4을 구하라. [풀이] R2＝R ◦ R＝{(1, 1), (2, 1), (4, 3), (3, 1)} R3＝R2 ◦ R＝{(1, 1), (3, 1), (2, 1), (4, 1)} R4＝R3 ◦ R＝{(1, 1), (3, 1), (2, 1), (4, 1)}

36 4.3 관계의 합성

37 4.3 관계의 합성 ☞ 정리 4-3 R이 A에 대한 관계이고, m, n이 자연수일 때 다음 식이 성립한다.
4.3 관계의 합성 ☞ 정리 4-3 R이 A에 대한 관계이고, m, n이 자연수일 때 다음 식이 성립한다. (1) Rm ◦ Rn＝R m＋n (2) Rm ◦ Rn＝Rn ◦ Rm (3) (Rm)n＝Rmn

38 4.4 동치 관계 4.4.1 관계의 성질 (1) 반사 관계(reflexive relation) 정의 4-6 반사 관계
4.4 동치 관계 관계의 성질 (1) 반사 관계(reflexive relation) 정의 반사 관계 A의 모든 원소 a가, (a, a)∈R이면, R은 반사적 또는 반사 관계 (R 은 집합 A에 대한 관계)

39 4.4 동치 관계 【예제 4.17】 집합 {1, 2, 3, 4}에 대한 다음의 방향 그래프로 표시된 관계들은 반사적인가?
4.4 동치 관계 【예제 4.17】 집합 {1, 2, 3, 4}에 대한 다음의 방향 그래프로 표시된 관계들은 반사적인가? [풀이] (1) 반사적, (2) 반사적이 아니다.

40 4.4 동치 관계 【예제 4.18】 다음의 관계들은 집합 {1, 2, 3, 4}에 대해 반사적인가?
4.4 동치 관계 【예제 4.18】 다음의 관계들은 집합 {1, 2, 3, 4}에 대해 반사적인가? R1＝{(1, 1), (1, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 1), (4, 4)} R2＝{(1, 1), (1, 4), (2, 2), (2, 4), (3, 3), (3, 4), (4, 4)} R3＝{(1, 2), (2, 1), (3, 4), (4, 3), (1, 1), (2, 2), (3, 3)} R4＝ ø R5＝{(1, 1), (2, 2), (3, 3), (4, 4)} R6＝{(3, 2), (4, 4), (2, 1), (1, 1), (4, 2), (3, 3), (3, 1), (2, 2)} [풀이] R2, R5, R6 : 반사적, R1, R3, R4 : 반사적이 아니다

41 4.4 동치 관계 【예제 4.19】 양의 정수들의 집합에서 관계 "나누기"는 반사적인가? [풀이] 반사적

42 4.4 동치 관계 (2) 대칭관계 정의 4-7 대칭 관계 R은 집합 A에 대한 관계,
4.4 동치 관계 (2) 대칭관계 정의 대칭 관계 R은 집합 A에 대한 관계, 모든 a, b∈A에 대해 (a, b)∈R일 때 반드시 (b, a)∈R인 관계가 존재하면, R은 대칭적 또는 대칭 관계

43 4.4 동치 관계 【예제 4.20】 [예제 4.18]의 관계는 집합 {1, 2, 3, 4} 에 대해 대칭적인가? [풀이]
4.4 동치 관계 【예제 4.20】 [예제 4.18]의 관계는 집합 {1, 2, 3, 4} 에 대해 대칭적인가? [풀이] R3, R4, R5 : 대칭적, R1, R2, R6 : 대칭이 아니다

44 4.4 동치 관계 【예제 4.21】 대칭 관계는 관계 행렬로 표현하면 쉽게 파악할 수 있다. 다음과 같이 관계 행렬로 표현된 관계는 대칭적인가? [풀이] (1), (2), (3) : 대칭적

45 4.4 동치 관계 【예제 4.22】 다음의 관계들은 대칭적인가? 단, Z는 정수의 집합이다.
4.4 동치 관계 【예제 4.22】 다음의 관계들은 대칭적인가? 단, Z는 정수의 집합이다. (1) R1＝{(m, n)∈Z×Z : m＝n} (2) R2＝{(m, n)∈Z×Z : m ≥ n} (3) R3＝{(m, n)∈Z×Z : m＝n 또는 m＝－n} (4) R4＝{(m, n)∈Z×Z : n＝m＋1} (5) R5＝{(m, n)∈Z×Z : m < n} (6) R6＝{(m, n)∈Z×Z : m＋n ≤ 0} [풀이] R1, R3, R6 : 대칭적 R2, R4, R5 : 대칭이 아니다.

46 4.4 동치 관계 (3) 반대칭 관계 (antisymmetruc relation) 정의 4-8 반대칭 관계
4.4 동치 관계 (3) 반대칭 관계 (antisymmetruc relation) 정의 반대칭 관계 R은 집합 A에 대한 관계, 모든 a, b∈A에 대해, 다음의 조건을 만족하면 반대칭적 또는 반대칭 관계 (a, b)∈R (b, a)∈R ⇒ a＝b

47 4.4 동치 관계 【예제 4.23】 다음 관계들은 반대칭적인가?

48 4.4 동치 관계 [풀이] (1) 반대칭적, (2) 대칭적, 반대칭적이 아니다.
4.4 동치 관계 [풀이] (1) 반대칭적, (2) 대칭적, 반대칭적이 아니다. (3) 영관계이므로 반대칭적, 대칭적이다. 반사적은 아니다

49 4.4 동치 관계 【예제 4.24】 다음의 관계들은 집합 1, 2, 3, 4에 대해 반대칭적인가?
4.4 동치 관계 【예제 4.24】 다음의 관계들은 집합 1, 2, 3, 4에 대해 반대칭적인가? R1＝{(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 3), (4, 4)} R2＝{(1, 1), (2, 2), (3, 3), (4, 4)} R3＝{(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)} R4＝{(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)} R5＝{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4),(3, 3), (3, 4), (4, 4)} R6＝{(3, 4)}

50 4.4 동치 관계 [풀이] R4, R5, R6 : 반대칭적 R2 : 반대칭적, 동시에 대칭적
4.4 동치 관계 [풀이] R4, R5, R6 : 반대칭적 R2 : 반대칭적, 동시에 대칭적 ( 대칭적과 반대칭적은 서로 반대가 아님) R1, R3 : 반대칭적이 아니다

51 4.4 동치 관계 (4) 이행 관계(transitive relation) 정의 4-9 이행 관계 R은 집합 A에 대한 관계,
4.4 동치 관계 (4) 이행 관계(transitive relation) 정의 이행 관계 R은 집합 A에 대한 관계, 모든 a, b, c∈A, (a, b)∈R이고, (b, c)∈R이면 (a, c)∈R일 때, R을 이행적 또는 이행 관계

52 4.4 동치 관계 【예제 4.25】 다음의 방향 그래프로 표시된 관계들은 이행적인가?
4.4 동치 관계 【예제 4.25】 다음의 방향 그래프로 표시된 관계들은 이행적인가? [풀이] (1) 이행적 (2) 이행적이 아니다

53 4.4 동치 관계 【예제 4.26】 다음의 관계들은 이행적인가? [풀이] R1, R5, R7 : 이행적
4.4 동치 관계 【예제 4.26】 다음의 관계들은 이행적인가? R1＝{(1, 2), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)} R2＝{(1, 1), (1, 3), (1, 4), (2, 2), (3, 1), (3, 3), (4, 1), (4, 4)} R3＝{(1, 1), (1, 3), (2, 2), (3, 1), (3, 4), (4, 1), (4, 4)} R4＝{(1, 1), (1, 3), (2, 2), (3, 1), (3, 3), (3, 4), (4, 1), (4, 4)} R5＝{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4)} R6＝{(1, 1), (1, 3), (3, 1), (3, 4)} R7＝{(1, 2)} [풀이] R1, R5, R7 : 이행적 R2, R3, R4, R6 : 이행적이지 않다

54 4.4 동치 관계 【예제 4.27】 다음의 방향 그래프(directed graph)로 주어진 관계가 반사적, 대칭적, 반대칭적, 이행적인지를 판별하고, 관계 행렬(relation matrix)로 나타내어라.

55 4.4 동치 관계

56 4.4 동치 관계 [풀이] (1) 반사적, 대칭적, 이행적이다. (2) 반사, 반대칭적, 이행적이다.
4.4 동치 관계 [풀이] (1) 반사적, 대칭적, 이행적이다. (2) 반사, 반대칭적, 이행적이다. (3) 대칭적, 반대칭적, 이행적이다. (4) 반사적, 대칭적이다.

57 4.4 동치 관계 ☞정리 4-4 R을 집합 A에 대한 관계라 할 때 (1) R은 반사 관계 ⇔ IA⊆R
4.4 동치 관계 ☞정리 4-4 R을 집합 A에 대한 관계라 할 때 (1) R은 반사 관계 ⇔ IA⊆R (2) R은 이행 관계 ⇔ R ◦ R⊆R (3) R은 반사 관계이고, 이행 관계 IA⊆R＝R ◦ R (4) R이 이행 관계라면 자연수 n에 대해 Rn⊆R이 된다. 단, IA는 항등 관계로서 {(a, a) | a∈A} 이다.

58 4.4 동치 관계 정의 4-10 동치 관계(equivalence relation)
4.4 동치 관계 정의 동치 관계(equivalence relation) 집합 A에 대한 관계가 반사적, 대칭적, 이행적 이면 이를 동치 관계라 한다.

59 4.4 동치 관계 【예제 4.28】 Z가 정수의 집합이고 R＝{(m, n)∈Z×Z | m＝n 또는 m＝－n}일 때,
4.4 동치 관계 【예제 4.28】 Z가 정수의 집합이고 R＝{(m, n)∈Z×Z | m＝n 또는 m＝－n}일 때, R이 Z에 대한 동치 관계임을 보여라. [풀이] (1) n∈Z라면, (m, n)∈R인 m＝n이 존재：반사적 (2) (m, n)∈R라면, m＝n일 때 n＝m이고, m＝－n일 때, n＝－m이므로 (n, m)∈R : 대칭적

60 4.4 동치 관계 (3) (m, n)∈R이고 (n, p)∈R이면, 네 가지 경우 m＝n, n＝p인 경우 m＝p
4.4 동치 관계 (3) (m, n)∈R이고 (n, p)∈R이면, 네 가지 경우 m＝n, n＝p인 경우 m＝p m＝n, n＝－p인 경우 m＝－p m＝－n, n＝p인 경우 m＝－p m＝－n, n＝－p인 경우 m＝p 모든 경우에서, (m, p)∈R이므로 : 이행적 ∴ 관계 R은 동치 관계

61 4.4 동치 관계 【예제 4.29】 R이 실수 집합이고 R＝{(a,b)∈R×R | a－b는 정수}일 때, R은 동치 관계인가?
4.4 동치 관계 【예제 4.29】 R이 실수 집합이고 R＝{(a,b)∈R×R | a－b는 정수}일 때, R은 동치 관계인가? [풀이] (1) 모든 실수 a에 대해 a-a = 0은 정수, aRa를 만족 : 반사적

62 4.4 동치 관계 (2) aRb가 존재할 때 a－b가 정수이면 b－a 또한 정수 bRa가 존재 : 대칭적
4.4 동치 관계 (2) aRb가 존재할 때 a－b가 정수이면 b－a 또한 정수 bRa가 존재 : 대칭적 (3) aRb, bRc가 존재할 때 a－b와 b－c는 정수, a－c＝(a－b)＋(b－c)는 정수로 aRc 만족 : 이행적 ∴ R은 동치 관계

63 4.4 동치 관계 정의 4-11 동치류(equivalence class) R은 집합 A에 대한 동치 관계
4.4 동치 관계 정의 동치류(equivalence class) R은 집합 A에 대한 동치 관계 R에 대한 a의 동치류 : [a]로 표기 [a]＝{x (a, x)∈R}

64 4.4 동치 관계 【예제 4.30】 집합 A＝{1, 2, 3, 4}에 대한 관계 R이 다음과 같이 주어졌을 때 동치류를 구하라. R＝{(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (3, 4), (4, 3), (4, 4)} [풀이] [1]＝[2]＝{1, 2}, [3]＝[4]＝{3, 4}

65 4.4 동치 관계 【예제 4.31】 [예제 4.28]에서 정의한 R에 대한 동치류를 구하라. [풀이]
4.4 동치 관계 【예제 4.31】 [예제 4.28]에서 정의한 R에 대한 동치류를 구하라. [풀이] [a]＝{－a, a}, 각각 두 개의 원소 (a＝0 제외)

66 4.4 동치 관계 ☞ 정리 4-5 R을 집합 A에 대한 동치 관계라 할 때, 다음 문장들은 동치이다. (1) aRb
4.4 동치 관계 ☞ 정리 4-5 R을 집합 A에 대한 동치 관계라 할 때, 다음 문장들은 동치이다. (1) aRb (2) [a]＝[b] (3) [a]∩[b] ≠ ø

67 4.4 동치 관계 [증명] <1> (1) ⇒ (2)
4.4 동치 관계 [증명] <1> (1) ⇒ (2) aRb라 가정, [a]＝[b] : [a]⊆[b]와 [b]⊆[a]임을 보임 c∈[a] → aRc R : 대칭적, aRb → bRa R : 이행적, bRa , aRc → bRc ∴ c∈[b] → [a]⊆[b] * [b]⊆[a]도 같은 방법으로 증명

68 4.4 동치 관계 <2> (2) ⇒ (3) [a]＝[b]가정, R : 반사적 → a∈[a], [a] ≠ ø
4.4 동치 관계 <2> (2) ⇒ (3) [a]＝[b]가정, R : 반사적 → a∈[a], [a] ≠ ø ∴ [a]∩[b]＝[a]∩[a]＝[a] ≠ ø <3> (3) ⇒ (1) [a]∩[b] ≠ ø 가정, c∈[a], c∈[b]가 존재 → aRc , bRc R은 대칭적 → cRb ∴ 이행적 성질에 의해 aRc, cRb → aRb

69 4.4 동치 관계 정의 4-12 분할(partition)
4.4 동치 관계 정의 분할(partition) 집합 A의 분할은 다음의 조건을 만족하는 A의 부분 집합 A1, A2, …, An의 모임이다. 이 때, Ai를 A의 분할 원소라 한다.

70 4.4 동치 관계 【예제 4.32】 A＝{1, 2, 3, 4, 5, 6}이라 할 때 A1＝{1, 2}, A2＝{3, 4, 6}, A3＝{5}는 A의 분할인가? [풀이] 분할이다

71 4.4 동치 관계 ☞ 정리 4-6 R이 A에 대한 동치 관계일 때 동치류의 모임은 A의 분할이다. [증명]
4.4 동치 관계 ☞ 정리 4-6 R이 A에 대한 동치 관계일 때 동치류의 모임은 A의 분할이다. [증명] A의 모든 원소 a에 대해 a∈[a] 즉, ∪[a]＝A a∈A [a] ≠ [b] 이면 [a]∩[b]＝ ø (정리 4-5) ∴{[a] | a∈A} : A의 분할

72 4.4 동치 관계 ☞ 정리 4-7 집합 A의 분할이 {A1, A2, …, Ak}일 때 A에 대한 동치 관계 R이 존재하고, R에 대한 각 동치류는 A의 분할 원소 Ai이다. [증명] A에 대한 관계 R 정의 : aRb ( a, b∈Ai ) R이 동치 관계임을 보인다. (1) aRa는 명백, R : 반사적

73 4.4 동치 관계 (2) aRb → bRa (∵a, b가 같은 분할 원소 Ai에 속함) R : 대칭적
4.4 동치 관계 (2) aRb → bRa (∵a, b가 같은 분할 원소 Ai에 속함) R : 대칭적 (3) aRb, bRc → a, b∈Ai 이고, b, c∈Aj b∈Ai∩Aj, 분할의 정의에 의해 Ai＝Aj 즉, a와 c는 같은 분할 원소에 속해 있고 aRc 이다 R : 이행적 ∴ 반사적, 대칭적, 이행적이므로 R은 동치 관계이다.

74 4.5 관계의 폐쇄 성질 P : 관계가 갖는 성질(반사적·대칭적·이행적 성질)
4.5 관계의 폐쇄 성질 P : 관계가 갖는 성질(반사적·대칭적·이행적 성질) R : 집합 A에 대한 관계(R은 P를 만족 또는 만족하지 않음) S : P에 관한 R의 폐쇄(closure) : R을 포함하면서 성질 P를 갖는 최소 관계

75 4.5 관계의 폐쇄 성질 【예제 4.33】 집합 A＝{1, 2, 3, 4}이고 R＝{(1, 2), (2, 1), (2, 2), (3, 2)}일 때, R의 반사 폐쇄를 구하라. [풀이] S＝{(1, 1), (1, 2), (2, 1), (2, 2), (3, 2), (3, 3), (4, 4)}

76 4.5 관계의 폐쇄 성질 ☞ 정리 4-8 R이 집합 A에 대한 관계이면 R의 반사 폐쇄는 R∪{(a, a) | a∈A}이다.

77 4.5 관계의 폐쇄 성질 【예제 4.34】 집합 A＝{1, 2, 3}이고 R＝{(1, 2), (2, 1), (2, 2), (3, 2)}일 때, R의 대칭 폐쇄를 구하라. [풀이] S＝{(1, 2), (2, 1), (2, 2), (2, 3), (3, 2)}

78 4.5 관계의 폐쇄 성질 【예제 4.35】 양의 정수의 집합에 대한 관계
4.5 관계의 폐쇄 성질 【예제 4.35】 양의 정수의 집합에 대한 관계 R＝{(a, b) a>b}의 대칭 폐쇄를 구하라. [풀이] R∪R－1 ＝{(a, b) | a>b} ∪{ (b, a) | a>b} ＝{(a, b) | a ≠ b}

79 4.5 관계의 폐쇄 성질 ☞ 정리 4-9 R이 집합 A에 대한 관계이면 R의 대칭 폐쇄는 R∪{(b, a)∈A×A | (a, b)∈R}＝R∪R－1이다.

80 4.5 관계의 폐쇄 성질 정의 4-13 경로(path) 방향 그래프 G의 a에서 b로의 경로는 G에서
4.5 관계의 폐쇄 성질 정의 경로(path) 방향 그래프 G의 a에서 b로의 경로는 G에서 한 개 이상 간선 (x0, x1), (x1, x2), …, (x n－1, xn) 으로 구성(단, x0＝a, xn＝b)된 순서를 갖는다. 길이가 n인 경로에서 시작점과 끝점이 같은 경우를 사이클(순환; cycle)이라 한다.

81 4.5 관계의 폐쇄 성질 【예제 4.36】 다음의 방향 그래프에서 <a, b, e, d>, <a, e, c, d, b>, <b, a, c, b, a, a, b>, <d, c>는 경로가 존재하는가? 또한 경로의 길이와 경로의 순회 여부를 결정하라. ◀ 책 그림 참조 ▶

82 4.5 관계의 폐쇄 성질 [풀이] <a, b, e, d> : 길이 3인 경로 존재
4.5 관계의 폐쇄 성질 [풀이] <a, b, e, d> : 길이 3인 경로 존재 <a, e, c, d, b> : 경로가 존재하지 않는다. <b, a, c, b, a, a, b> : 길이는 6인 경로, 순환 <d, c> : 길이가 1인 경로 존재

83 4.5 관계의 폐쇄 성질 ☞ 정리 4-10 집합 A에 대한 관계 R은 a에서 b로의 길이가 n인 경로가 존재하면 (a, b)∈Rn이다.

84 4.5 관계의 폐쇄 성질 정의 4-14 접속 관계(connectivity relation)
4.5 관계의 폐쇄 성질 정의 접속 관계(connectivity relation) 집합 A에 대한 관계 R의 접속 관계 R* R*＝{(a, b) | a에서 b로의 경로가 존재}

85 4.5 관계의 폐쇄 성질 【예제 4.37】 집합 A＝{1, 2, 3, 4, 5}, 관계 R＝{(1, 1), (1, 2), (2, 3), (3, 4), (3, 5), (4, 5)}라 할 때 다음을 구하라. (1) R (2) R* (1) R2 ={(1,1),(1,2),(1,3),(2,4),(2,5),(3,5)} (2) R* ={(1,1),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4), (2,5),(3,4),(3,5),(4,5)}

86 4.5 관계의 폐쇄 성질 정의 4-15 이행 폐쇄(transitive closure) R을 집합 A에 대한 관계라면, R*는
4.5 관계의 폐쇄 성질 정의 이행 폐쇄(transitive closure) R을 집합 A에 대한 관계라면, R*는 R의 이행 폐쇄이다.

87 4.5 관계의 폐쇄 성질 【예제 4.38】 집합 A＝{1, 2, 3, 4}이고, 관계 R이 다음의 방향 그래프로 구성될 때 R의 이행 폐쇄 R*를 구하라.

88 4.5 관계의 폐쇄 성질 [풀이] R*＝{(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 4) }

89 4.5 관계의 폐쇄 성질 【예제 4.39】 집합 {1, 2, 3, 4}에서 관계 R이 다음과 같은 관계 행렬로 주어졌을 때 방향 그래프, 반사 폐쇄, 대칭 폐쇄, 이행 폐쇄를 구하라.

90 4.5 관계의 폐쇄 성질 [풀이] (1) 방향 그래프는 다음과 같이 구성된다.

91 4.5 관계의 폐쇄 성질 (2) 반사 폐쇄 : 순서쌍 (1, 1), (4, 4) 추가
4.5 관계의 폐쇄 성질 (2) 반사 폐쇄 : 순서쌍 (1, 1), (4, 4) 추가 (3) 대칭 폐쇄 : 순서쌍 (3, 1) 추가 (4) 이행 폐쇄 (R*) : 경로에 존재하는 모든 순서쌍을 구한다 R*＝{(1, 1), (1, 3), (1, 4), (2, 2), (3, 3), (4, 1), (4, 3), (4, 4)}

92 4.6 부분 순서와 속 정의 4-16 부분 순서 관계 집합 A에 대한 관계 R이 반사적, 반대칭적,
4.6 부분 순서와 속 정의 부분 순서 관계 집합 A에 대한 관계 R이 반사적, 반대칭적, 이행적이면 이를 부분 순서 관계라 하며, (A, R) 을 부분 순서 집합(partially ordered set ; poset) 이라 한다.

93 4.6 부분 순서와 속 【예제 4.40】 정수(Z)의 집합에 대한 관계 ≥ 가 부분 순서 관계임을 보여라. [풀이]
4.6 부분 순서와 속 【예제 4.40】 정수(Z)의 집합에 대한 관계 ≥ 가 부분 순서 관계임을 보여라. [풀이] 모든 정수 a에 대해, a ≥ a만족 : 반사 관계 a ≥ b, b ≥ a이면 a=b : 반대칭 관계 a ≥ b, b ≥ c 이면 a ≥ c : 이행 관계 ∴ 정수(Z)의 집합에서 관계 ≥ 가 부분 순서 관계임

94 4.6 부분 순서와 속 【예제 4.41】 다음의 방향 그래프(directed graph)가 부분 순서 관계인지를 판별하라.
4.6 부분 순서와 속 【예제 4.41】 다음의 방향 그래프(directed graph)가 부분 순서 관계인지를 판별하라. [풀이] (1), (2), (3) ː 부분 순서 관계

95 4.6 부분 순서와 속 정의 4-17 선형 순서 관계(linear order relation)
4.6 부분 순서와 속 정의 선형 순서 관계(linear order relation) 부분 순서 집합 (A, )에서 A의 원소 a, b가 a b 또는 b a이면 a와 b를 비교 가능 (comparable)하다고 하고, A의 모든 두 원소들이 비교 가능하면 A를 선형 순서 집합이라 하며, 관계 를 선형 순서 관계라고 한다.

96 4.6 부분 순서와 속 【예제 4.42】 부분 순서 집합 (Z, |)에서 정수 3과
4.6 부분 순서와 속 【예제 4.42】 부분 순서 집합 (Z, |)에서 정수 3과 9가 비교 가능한가? 또한 5와 7은 비교 가능한가? 단, 관계 | 는 mod(a, b)＝0을 의미한다. [풀이] 9 | 3 : 9와 3은 비교 가능, 5 | 7, 7 | 5 : 비교 가능하지 않다. ∴ | 는 선형 순서 관계가 아니다.

97 4.6 부분 순서와 속 【예제 4.43】 부분 순서 집합 (Z, ≤ )는 비교 가능한가? [풀이]
4.6 부분 순서와 속 【예제 4.43】 부분 순서 집합 (Z, ≤ )는 비교 가능한가? [풀이] a, b가 정수, a ≤ b 또는 b ≤ a 만족, 선형 순서 관계

98 4.6 부분 순서와 속 ■ 유사 순서(quasi-order) ：반사적이 아니고 이행적인 관계 “a b이고 b c이면 a c”
4.6 부분 순서와 속 ■ 유사 순서(quasi-order) ：반사적이 아니고 이행적인 관계 “a b이고 b c이면 a c” ( 는 반대칭이고 이행적이다： a b이고 a ≠ b이면, a b)

99 4.6 부분 순서와 속 : 부분 순서 집합 (A, )의 방향 그래프
4.6 부분 순서와 속 : 부분 순서 집합 (A, )의 방향 그래프 : A의 원소인 정점과 b가 a를 커버할 때 a에서 b로의 간선으로 구성됨 원소 b는 원소 a를 커버(cover) : a b이고 A 내에 a c b인 c가 존재하지 않을 때

100 4.6 부분 순서와 속 【예제 4.44】 A = { 1, 2, 3, 4, 5, 6}이고, n | m은 mod(m, n) = 0 이라 하자. 부분 순서 집합 (A, |)를 하세 도표를 작성하라. 단, mod(m, n) = 0 은 m이 n으로 나누어 나머지가 0임을 뜻한다.

101 4.6 부분 순서와 속 [풀이] 하세 도표를 작성하면 다음과 같다.

102 4.6 부분 순서와 속 【예제 4.45】 P({a, b, c})를 멱집합이라고 할 때, 부분 순서 집합 (P, ⊆)를 하세 도표로 작성하라. [풀이] 하세 도표로 작성하면 다음 그림과 같다.

103 4.6 부분 순서와 속 【예제 4.46】 다음 도표가 하세 도표인지를 판별하라.

104 4.6 부분 순서와 속 [풀이] (1) : 하세 도표가 아니다. (2) : 하세 도표 (3) : 하세 도표가 아니다.

105 4.6 부분 순서와 속 ☞ 정리 4-11 모든 유한 부분 순서 집합은 하나의 하세 도표로 표시할 수 있다.

106 4.6 부분 순서와 속 정의 4-18 극대 원소(maximal) 와 극소 원소(minimal)
4.6 부분 순서와 속 정의 극대 원소(maximal) 와 극소 원소(minimal) (P, )를 부분 순서 집합이라 하자. P 내의 원소 x에 대하여 x y인 y가 존재하지 않을 때 원소 x를 P의 극대 원소라 하고, y x인 y가 존재하지 않을 때 원소 x를 P의 극소 원소라고 한다.

107 4.6 부분 순서와 속 ■ 부부분 순서 집합(subposet)
4.6 부분 순서와 속 ■ 부부분 순서 집합(subposet) 부분 순서 집합 P의 부분 집합 S는 P의 부분 순서를 계승받고, 그 자체가 부분 순서 집합이 된다. 왜냐하면 반사적 · 반대칭적 · 이행적 특성은 P의 모든 원소에 적용되기 때문이다.

108 4.6 부분 순서와 속 【예제 4.47】 [예제 4.44]의 부분 순서 집합 {1, 2, 3, 4, 5, 6}의 부부분 순서 집합인 (1) {2, 3, 4, 5, 6}과 (2) {1, 2, 3, 6}을 하세 도표로 작성하라. [풀이]

109 4.6 부분 순서와 속 【예제 4.48】 집합 {a, b, c}의 공집합을 제외한 모든 진부분 집합은 부분 순서 ⊆ 를 갖는 멱집합 P({a, b, c})의 부부분 순서 집합이다. 이를 하세 도표로 작성하라.

110 4.6 부분 순서와 속 [풀이]

111 4.6 부분 순서와 속 정의 4-19 최대 원소(largest element;maximum)
4.6 부분 순서와 속 정의 최대 원소(largest element;maximum) 와 최소 원소(smallest element;minimum) S : 부분 순서 집합 (P, )의 부부분 순서 집합, 최대 원소 : ∀s∈S, s M인 원소 M이 S 내에 존재 M = max(S) 최소 원소 : ∀s∈S, m s인 원소 m이 S 내에 존재 m = min(S)

112 4.6 부분 순서와 속 [예제 4.44] 최대 원소 : 존재하지 않는다 (극대 원소간의 의 관계가 없기 때문)
4.6 부분 순서와 속 [예제 4.44] 최대 원소 : 존재하지 않는다 (극대 원소간의 의 관계가 없기 때문) 최소 원소 : 1 [예제 4.45] 최대 원소 : {a, b, c}, 최소 원소 : { }

113 4.6 부분 순서와 속 정의4-20 상한(upper bound)과 최소 상한
4.6 부분 순서와 속 정의4-20 상한(upper bound)과 최소 상한 (least upper bound), 하한(lower bound)과 최대 하한(greatest lower bound) S : 부분 순서 집합 (P, )의 부부분 순서 집합 (1) ∀s∈S, s x인 ∃x∈P, x : P 내에서 S에 대한 상한

114 4.6 부분 순서와 속 (2) x : P 내에서 S에 대한 상한 y : P 내에 있는 S에 대한 모든 상한에 대하여,
4.6 부분 순서와 속 (2) x : P 내에서 S에 대한 상한 y : P 내에 있는 S에 대한 모든 상한에 대하여, x y일 때 x를 P 내에 있는 S의 최소 상한 x = lub(S) (3) ∀s∈S, z s인 ∃z∈P, z : P 내에서 S에 대한 하한 (4) z : P 내에서 S에 대한 하한 w : P 내에 있는 S에 대한 모든 하한에 대하여, w z일 때 z를 P 내에 있는 S의 최대 하한 z = glb(S)

115 4.6 부분 순서와 속 【예제 4.49】 [예제 4.44]와 같이 부분 순서 집합({1, 2, 3, 4, 5, 6}, |)이 있을 때, 다음과 같은 부부분 순서 집합에 대하여 상한, 최소 상한, 하한, 최대 하한을 각각 구하라. (1) {2, 3} (2) {4, 6} (3) {3, 6}

116 4.6 부분 순서와 속 [풀이] (1) 상한: 6, 최소 상한: 6, 하한: 1, 최대 하한: 1
4.6 부분 순서와 속 [풀이] (1) 상한: 6, 최소 상한: 6, 하한: 1, 최대 하한: 1 (2) 상한: 없음, 하한 : 2, 1, glb({4, 6}) = 2 (3) 상한: 6, lub({3, 6}) = 6 하한 : 3, 1, glb({3, 6 }) = 3

117 4.6 부분 순서와 속 【예제 4.50】 다음 하세 도표에 해당하는 부분 순서 집합 P에 대하여, 다음과 같은 부부분 순서 집합이 있을 때, 상한, 최소 상한, 하한, 최대 하한을 각각 구하라. (1) {b, c} (2) {d, f} (3) {d, e, f} (4) {b, d, e, f}

118 4.6 부분 순서와 속

119 4.6 부분 순서와 속 [풀이] (1) 상한: d, e, g, h. 최소 상한 : 없음. 하한 : 없음
4.6 부분 순서와 속 [풀이] (1) 상한: d, e, g, h. 최소 상한 : 없음. 하한 : 없음 (2) 상한: h. lub({d, f})＝h. 하한: a, c, 최대 하한: 없음 (3) 상한, 최소 상한: h, 하한: a, c, 최대 하한 : 없음 (4) 상한, 최소 상한: h, 하한, 최대 하한 : a

120 4.6 부분 순서와 속 정의 4-21 속(lattice) 부분 순서 집합 (P, )에서 P의 임의의 원소
4.6 부분 순서와 속 정의 속(lattice) 부분 순서 집합 (P, )에서 P의 임의의 원소 x, y에 대하여 {x, y}의 glb와 lub가 각각 하나씩 존재한다고 하면, (P, )을 속이라고 한다. 이 때, lub({x, y}) x∨y, glb({x, y})＝x∧y로 나타내며, (∨또는 : 합 연산자, ∧ 또는 *: 곱 연산자)

121 4.6 부분 순서와 속 【예제 4.51】 P({a, b, c})를 멱집합이라 할 때, 부분 순서 집합 (P, ⊆)이 속인지 판별하라. [풀이] [예제 4.45]의 하세 도표를 참고하면, lub({{a}, {c}})＝{a}∨{c}＝{a, c} lub({{a, b}, {a, c}})＝{a, b}∨{a, c}＝{a, b, c} glb({{a, b}, {c}})＝{a, b}∧{c}＝ ø glb({{a, b}, {b, c}})＝{a, b}∧{b, c}＝{b} 결국, 부분 순서 집합 (P, ⊆)은 속이다.

122 4.6 부분 순서와 속 ■ 일반적으로 임의의 집합 S에 대하여 (P(S), ⊆)： 속
4.6 부분 순서와 속 ■ 일반적으로 임의의 집합 S에 대하여 (P(S), ⊆)： 속 lub({A, B, …, Z})＝A∪B…∪Z glb({A, B, …, Z})＝A∩B…∩Z

123 4.6 부분 순서와 속 【예제 4.52】 A＝{1, 2, 3, 4, 5, 6}이고, n | m은 mod(m, n)＝0이라 하자. 부분 순서 집합 (A, |)이 속인지 판별하라. 단, mod(m, n)＝0은 m이 n으로 나누어짐을 말한다. [풀이] {3, 4}는 상한이 존재하지 않으므로 속이 아니다.

124 4.6 부분 순서와 속 【예제 4.53】 P를 양의 정수라 하고 n | m은 mod(m, n)＝0이라 할 때, 부분 순서 집합 (P, |)이 속인지 판별하라. [풀이] lub({m, n}) : m, n의 최소 공배수 glb({m, n}) : m, n의 최대 공약수 (예), lub({12, 10})＝60, glb({12, 10})＝2 ∴ ( P, | ) : 속

125 4.7 n-항 관계의 응용 정의 4-25 도메인, 카티션 프로덕트, 릴레이션
도메인(domain) : D1, D2, … , Dn 으로 표기하며 값들의 집합 카티션 프로덕트(Cartesian product) : D1 x D2 x … x Dn 으로 표기하며 n-튜플의 집합 릴레이션(relation) : R로 표기, R ⊆ D1xD2x … xDn P171 – p177 참조

126 4.7 n-항 관계의 응용 [예] 학번, 성명, 전공, 평균점수 : 도메인 * 카티션 프로덕트(4-튜플)

127 4.7 n-항 관계의 응용 [예] 학생 릴레이션

128 4.7 n-항 관계의 응용 [예] 학생 릴레이션 : 학생 테이블
릴레이션 스킴(내포) : 학번, 성명, 전공, 평균평점(애트리뷰트) * 테이블의 논리적 구조를 기술한 것으로 정적 릴레이션 인스턴스(외포) : 1, 이영호, CS, 3.83 (n-튜플들의 집합) * 현실세계의 어느 한 시점에서의 릴레이션의 내용 기술, 동적