이산수학 논리∙명제에서 알고리즘까지 √ 원리를 알면 IT가 맛있다 ehanbit.net.

Presentation on theme: "이산수학 논리∙명제에서 알고리즘까지 √ 원리를 알면 IT가 맛있다 ehanbit.net."— Presentation transcript:

1 이산수학 논리∙명제에서 알고리즘까지 √ 원리를 알면 IT가 맛있다 ehanbit.net

2 Chapter 04. 관 계

3 학습목표 집합의 원소들 사이의 연관성을 나타내기 위한 구조인 관계의 개념 파악 화살도표, 좌표도표, 관계행렬을 통한 관계의 도식화 반사관계, 대칭관계, 추이관계를 통한 관계의 성질 이해 관계들을 결합하는 합성관계와 연산들 이해 반사폐포, 대칭폐포, 추이폐포를 통하여 새로운 관계를 만듦 하세도표 등을 이용하여 부분순서관계 이해

4 곱집합(Cartesian product)
기본 개념(계속) 곱집합(Cartesian product) A 와 B 는 집합 A, B 가 유한집합일 때 의 원소의 개수

5 이항관계(binary relation)
기본 개념(계속) [예제01] 두 집합 A={1, 2, 3}, B={a, b}에 대하여 를 구하여라. [풀이] 이항관계(binary relation) 두 개의 원소로 구성된 순서쌍(ordered pair)의 집합

6 기본 개념(계속) [정의1] a 는 b 에 대해 R 의 관계가 있음
두 집합 A, B 에 대하여 A 에서 B 로의 이항관계 (binary relation)가 의 부분집합일 때 a∈A 이고 b∈B 인 (a, b)∈R 로 나타내기도 함 (a, b)R 일 경우 또는 로 나타내기도 함 정의역(domain) 관계 R 의 순서쌍에서 모든 첫 번째 원소의 집합: dom(R) 치역(range) 모든 두 번째 원소의 집합: ran(R)

7 기본 개념(계속) [예제03] 두 집합 A={0, 1}, B={0, 1, 2}에 대한 이항관계 R 이
R={(a,b) ∈ A X B| a∈A, b∈B, a≥b} 일 때, (1) 관계 R 을 순서쌍으로 나타내어라. (2)0R0, 0R1, 0R2, 1R0, 1R1, 1R2이 각각 성립하는가? (3) 정의역과 치역을 구하여라.

8 기본 개념(계속) n 항 관계(n-ary relation) [정의2] 두 개 이상의 집합의 원소들 사이의 관계
데이터베이스를 표현하는 데 자주 사용 데이터베이스(database) 어느 한 조직의 여러 응용 시스템을 공유할 수 있도록 통합, 저장, 운영되는 데이터 집합 관계형 데이터베이스 모델(relational database model) 데이터베이스에서 n 항 관계의 개념을 기초로 하여 개발 된 것 [정의2] 집합 에 대한 n항 관계(n-ary relation) 의 부분집합

9 기본 개념(계속) [예제04] 두 집합 A={a, b}, B={1, 2}일 때 를 구하고, A 에서
[풀이] 의 모든 부분집합이 A 에서 B 로의 관계이므로 모든 관계의 수는 24=16

10 기본 개념(계속) [정의3] [예제05] 집합 A 에서 집합 B 로의 관계 R 에 대한 역관계(inverse relation)
R-1={(b, a)∈ | (a, b)∈R} [예제05] 두 집합 A={1, 2, 3}, B={3, 4, 5}에서 관계 R ={(1, 4), (2, 3), (2, 5), (3, 3)}일 때 관계 R 의 역관계 R-1 을 구하여라. [풀이]

11 Section 02. 관계의 표현 화살도표(arrow diagram) [예제07]
두 집합 A, B 가 있을 때 집합 A 의 원소 a 와 집합 B 의 원소 b 사이에 관계가 성립하는 경우 그 관계를 화살표로 그려서 나타내는 방법 [예제07] 집합 A={1, 2, 3, 4}, 집합 B={a, b, c}라 하고 A 와 B 사이 의 관계 R={(1, a), (1, b), (2, b), (2, c), (3, c), (4, b)}라 할 때 관계 R 과 역관계 R-1을 화살도표를 이용하여 나타내어라. [풀이]

12 좌표도표(coordinate diagram)
관계의 표현(계속) 좌표도표(coordinate diagram) 두 집합 A, B 가 있을 때 집합 A 의 원소 a 를 x 축 위의 점으로 표시하고, 집합 B 의 원소 b 를 y 축 위의 점으로 표시하여 두 점이 좌표상에서 만나는 점을 나타내는 방법 [예제08] 두 집합 A={1, 2, 3, 4}, B={2, 3, 4}고 집합 A 에서 B 로의 관계 R={(1, 3), (2, 1), (2, 4), (3, 2), (4, 3)}일 때 관계 R 을 좌표도표를 이용하여 나타내어라. [풀이]

13 관계행렬(relation matrix)
관계의 표현(계속) 관계행렬(relation matrix) 두 집합 A, B 에 대한 관계를 행렬로 표현한 방법 A 의 원소들을 행에 배치하고 B 의 원소들을 열에 배치한 후 A 의 원소와 B 의 원소 사이에 관계가 있으면 1로, 관계가 없으면 0으로 행렬의 원소를 나타냄 행렬 안의 모든 원소들이 0 또는 1인 행렬을 부울행렬(boolean matrix)이라고 함 [예제09] 두 집합 A={1, 2, 3}, B={1, 2, 3, 4}에 대해 관계 R={(1, 1), (1, 3), (2, 3), (3, 2), (3, 4)}일 때 이를 관계행렬로 나타내어 라.

14 방향그래프(directed graph)
관계의 표현(계속) 방향그래프(directed graph) 하나의 집합에 대한 관계를 나타냄 집합 A의 관계에 대한 방향그래프를 그리고자 할 때 먼저 A의 원소들을 나타내는 정점(vertex)을 그리고, 원소 (a, b)가 관계에 속하면 a에서 b로 화살표 모양의 에지(edge)를 그림 루프(loop) (a, a)가 관계일 때 a 에서 a 로 그리게 되는 에지

15 관계의 표현 – 방향그래프(계속) [예제10] 집합 A={1, 2, 3, 4}이고 관계 R={(a, b)| a∈A, b∈A, a≤b} 이라 할 때 관계 R 에 대한 방향그래프를 그려라. [풀이] R ={(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}이므로 방향그래프는 다음과 같다.

16 [예제11]그림과 같은 방향그래프로 표현된 관계 R을 관계행렬로 나타내시오.
관계의 표현 – 방향그래프(계속) [예제11]그림과 같은 방향그래프로 표현된 관계 R을 관계행렬로 나타내시오. a X Y b c

17 Section 03. 관계의 성질 [정의4] 집합 A 에 대한 관계 R 반사관계(reflexive relation)
: 모든 a∈A 에 대하여 aRa 일 때의 R 대칭관계(symmetric relation) : 모든 a, b∈A 에 대하여 aRb 이면 bRa 일 때의 R 추이관계(transitive relation) : 모든 a, b, c∈A에 대하여 aRb 이고 bRc 이면 aRc 일 때의 R

18 관계의 성질(계속) [정의5] 집합 A 에 대한 관계 R 비반사관계(irreflexive relation)
: 모든 a∈A 에 대하여 일 때의 R 반대칭관계(antisymmetric relation) : 모든 a, b∈A 에 대하여 aRb 이고 bRa 이면 a =b 일 때의 R

19 관계의 성질 – 반사관계, 비반사관계 [예제12] 다음 방향그래프는 반사관계가 성립하는가? (1) (2) [풀이]
(1) (2) [풀이] (1)각 원소들이 자기 자신으로의 관계를 가지므로 반사관계성립 (2)원소 3이 자기 자신으로의 관계를 가지지 못하므로 반사관계 성립하지 않음

20 관계의 성질 – 반사관계, 비반사관계(계속) [예제14]
집합 A={a, b, c, d }에 대한 다음 관계가 반사관계인지 비반 사관계인지 구분하고, 각각 관계행렬로 나타내어라. R1={(a, a), (a, b), (b, c), (c, d)} (2) R2={(a, a), (b, a), (b, b), (c, c), (d, d)} (3) R3={(a, b), (b, c), (c, d), (d, a)}

21 관계의 성질 – 대칭관계, 반대칭관계 [예제15] 다음 방향그래프는 대칭관계가 성립하는가? (1) (2) [풀이]
(1) (2) [풀이] (1) 대칭관계 성립 (2) (1, 3)∈R, (1, 4)∈R, (4, 3)∈R 이지만 (3, 1)R, (4, 1)R, (3, 4)R 이므로 대칭관계 성립하지 않음

22 관계의 성질 – 대칭관계, 반대칭관계(계속) [예제17] 집합 A={x, y, z}에 대한 다음 관계가 대칭관계인지 반대칭관
계인지 구분하고, 각각 관계행렬로 나타내어라. (1) R1={(x, z)} (2) R2={(y, z), (z, y)} (3) R3={(x, x), (y, y), (z, z)} (4) R4={(x, y), (x, z), (y, x), (z, z)} [풀이] (1) 반대칭관계

23 관계의 성질 – 대칭관계, 반대칭관계(계속) (2) 대칭관계 (3) 대칭관계며, 반대칭관계도 성립
(4) 대칭관계도 반대칭관계도 아님

24 [예제18] 관계의 성질 – 대칭관계, 반대칭관계(계속)
집합 A={1,2,3,4,5,6}일 때 라면 (x,y)∈R로 정의되는 관계 R이 반사관계, 비반사관계, 대칭관계, 반대칭관계 중에서 어떤 관계가 성립되는지 판별하라.

25 관계의 성질 - 추이관계 [예제19] 다음 방향그래프는 추이관계가 성립하는가? (1) (2) [풀이]
(1) (2) [풀이] (b, a)∈R 이고 (a, c)∈R 일 때 (b, c)R 이므로 추이관계 성립하지 않음 (2) (1, 4)∈R 이고 (4, 3)∈R 일 때 (1, 3)∈R 이므로 추이관계 성립

26 관계의 성질 – 추이관계(계속) [예제20] 집합 A={1, 2, 3}에 대하여 다음의 관계가 추이관계인지 판
별하고, 각각 관계행렬로 나타내어라. (1) R1={(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1) } (2) R2={(2, 2), (3, 3)} (3) R3={(1, 3)} (4) R4={(1, 3), (2, 2), (3, 1)} [풀이] (1) 추이관계성립하지 않음

27 관계의 성질 – 추이관계(계속) (2) 추이관계 (3) 추이관계 (4) 추이관계 성립하지 않음

28 관계의 성질 – 추이관계(계속) [예제21] 다음 관계행렬이 반사관계, 대칭관계, 반대칭관계, 추이관계
중에서 어떤 관계가 성립하는지 판별하여라. (2) [풀이] (1) 반사관계, 대칭관계, 반대칭관계, 추이관계 성립 (2) 반사관계, 반대칭관계 성립

29 Section 04. 관계의 연산 - 합성관계 [정의6] 집합 A 에서 B 로의 관계를 R 이라 하고, 집합 B 에서 C 로
R 과 S 의 합성관계(composition relation) a∈A 이고 c∈C 일 때 aRb이고 bSc인 b∈B 가 존재 하는 순서쌍 (a, c)로 구성되는 관계 S ◦R로 나타냄

30 관계의 연산 – 합성관계(계속) [예제23] 집합 A={1, 2, 3}, B={a, b, c, d, e}, C={4, 5, 6, 7}일 때 A 에서 B로의 관계 R={(1, a), (1, e), (2, b), (3, c)}이고, B 에 서 C로의 관계 S={(a, 4), (b, 4), (c, 7), (d, 5)}이다. 합성관 계 S ◦R 을 구하여라. [풀이] S ◦R ={(1, 4), (2, 4), (3, 7)}

31 관계의 연산 – 합성관계(계속) 관계행렬을 이용한 합성관계

32 관계의 연산 – 합성관계(계속) [예제24]관계 R과 S에 대한 관계행렬 MR 과 MS 는 다음과 같다. R과 S의 합성관계 S ◦R 를 관계행렬로 나타내어라. [정리01] 집합 A, B, C, D 에 대하여 집합 A 에서 B 로의 관계를 R, 집합 B 에서 C 로의 관계를 S, 집합 C 에서 D 로의 관계를 T 라고 할 때 이다.

33 관계의 연산 – 합성관계(계속) [정의7] 하나의 관계 R 에 대한 합성관계
집합 A 에 대한 관계 R 에 대하여 n=1, 2, 3, …일 때 거듭제곱 R n 하나의 관계 R 에 대한 합성관계 n이 양의 정수일 때

34 관계의 연산 – 합성관계(계속) [예제25] 집합 A={1, 2, 3}에서의 관계 R={(1, 2), (2, 2), (3, 1), (3, 3)}이다. 이 때 관계행렬을 사용하여 R 2, R 3 를 구하여라. [풀이]

35 관계의 연산 – 합성관계(계속)

36 관계의 연산 – 합성관계(계속) [정리02] 집합 A 에 대한 관계 R 이 추이관계일 때 모든 양의 정수 n 에 대하여 이다.
대하여 이다. [증명]

37 관계의 연산 – 여러 가지 연산 [예제28] 집합 {1, 2, 3}에 대한 두 관계 R1={(1, 1), (1, 2), (2, 3)}, R2={(1, 1), (1, 3), (2, 2), (2, 3), (3, 3)}일 때 과 를 관계행렬을 사용하여 구하여라. [풀이]

38 관계의 연산 – 여러 가지 연산(계속)

39 반사폐포(reflexive closure)
Section 05. 관계의 폐포 - 반사폐포 반사폐포(reflexive closure) 관계 R 을 포함하고 반사적이며, R 이 포함된 모든 반사관계 안에 포함됨 R 이 집합 A 에 대한 관계일 때 R 의 반사폐포 [예제29] 집합 A={a, b, c, d}에 대한 관계 R={(a, b), (a, c), (c, b), (d, a), (d, d)}의 반사폐포를 구하여라. [풀이] {(a, b), (a, c), (c, b), (d, a), (d, d)}∪{(a, a), (b, b), (c, c)} ={(a, a), (a, b), (a, c), (b, b), (c, b), (c, c), (d, a), (d, d)}

40 대칭폐포(symmetric closure)
관계의 폐포 - 대칭폐포 대칭폐포(symmetric closure) 관계 R 을 포함하고 대칭적이며, R 이 포함된 모든 대칭관계 안에 포함됨 R 이 집합 A 에 대한 관계일 때 R 의 대칭폐포 [예제31] 집합 A={0, 1, 2, 3}에 대한 관계 R={(0, 1), (1, 2), (2, 2), (2, 3), (3, 2)}의 대칭폐포를 구하여라. [풀이] {(0, 1), (1, 2), (2, 2), (2, 3), (3, 2)}∪{(1, 0), (2, 1)} ={(0, 1), (1, 0), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2)}

41 추이폐포(transitive closure)
관계의 폐포 - 추이폐포 추이폐포(transitive closure) 반사폐포나 대칭폐포를 만드는 것에 비해 매우 복잡 새로운 순서쌍을 더 추가할 필요가 없을 때까지 반복적으로 순서쌍을 추가 [정의8] 방향그래프 G 에서 a 에서 b 로의 경로(path) x0=a, xn=b라고 할 때 한 개 이상의 에지 (x0, x1), (x1, x2), ···, (xn-1, xn)로 구성 길이 n인 경로 x0, x1, x2, ···, xn-1, xn으로 나타냄

42 관계의 폐포 – 추이폐포(계속) [정의9] 집합 A 에 대한 관계 R 이 있을 때
연결관계(connectivity relation) R * 관계 R 에 적어도 길이 1이면서 a 에서 b 로의 경로가 있는 쌍 (a, b)로 R n 은 길이 n 이면서 a 에서 b 로의 경로가 있는 쌍 (a, b)로 구성 R * 는 R n 의 합집합:

43 관계의 폐포 – 추이폐포(계속) [예제 33] 집합 A={1,2,3} 에 대한 관계 R ={(1,2),(2,3),(3,1)}의 연결관계 R*를 구하라.

44 관계의 폐포 – 추이폐포(계속) [정리03] 연결관계 R * 는 관계 R 의 추이폐포다. [증명]

45 관계의 폐포 – 추이폐포(계속) [예제34] 집합 {1, 2, 3, 4}에서의 관계 R={(1, 2), (2, 1), (2, 3), (3, 4), (4, 1)}이다. 추이폐포 R * 를 구하여라. [풀이]

46 관계의 폐포 – 추이폐포(계속) 추이폐포 R *={(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4)}

47 Section 06. 동치관계 [정의10] [예제35] 동치관계(equivalence relation)
하여라. (1) R1={(1, 1), (1, 4), (2, 2), (2, 3), (3, 2),(3, 3), (4, 1), (4, 4)} (2) R2={(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)} [풀이] (1) 동치관계 (2) 동치관계 아님

48 동치관계(계속) [정의11] 집합 A 에 대한 관계 R 이 동치관계일 때
R 에 대한 a 의 동치류(equivalence classes) 집합 A 의 각 원소 a 에 대하여 [a] [a]={x| (a, x)∈R}

49 동치관계(계속) [예제37] 관계 R1, R2가 동치관계인지 판별하고, 동치관계일 경우 동 치류를 구하여라.
(1, 5), (2, 2), (3, 1), (3, 3), (3, 5), (4, 4), (5, 1), (5, 3), (5, 5)} [풀이] (1) 동치관계 동치류: [1]=[3]={1, 3}, [2]=[4]={2, 4} (2) 동치관계 동치류: [1]=[3]=[5]={1, 3, 5}, [2]={2}, [4]={4}

50 [예제40]집합 X 의 부분집합 간의 포함관계 ⊆는 부분순서관계인가?
Section 07. 부분순서관계 [정의12] 부분순서관계(partial order relation) 집합 A 에 대한 관계 R 이 반사관계, 반대칭관계, 추이 관계가 성립할 때의 관계 R 이 때 A 는 부분순서집합(partially ordered set, poset) Note> (A,R ) [예제40]집합 X 의 부분집합 간의 포함관계 ⊆는 부분순서관계인가? [풀이] 임의의 부분집합 A 에 대하여 A⊆A이므로 반사관계가 성립 하고, 부분집합 A, B 에 대하여 A⊆B 이고 B⊆A 이면 A=B 이므로 반대칭관계도 성립한다. 또한 부분집합 A, B, C 에 대하여 A⊆B 이고 B⊆C 이면 A⊆C 이므로 추이관계도 성 립한다. 따라서 부분순서관계다.

51 부분순서관계(계속) 부분순서관계는 관계 ≤를 일반화하는 것
집합 A 에 대한 관계 R 이 부분순서관계일 때 (a, b)∈R 을 나타내기 위해서 ‘ ’를 사용하여 라고 나타냄 이고 이면 라고 나타냄 ‘a가 b보다 우선한다(a precedes b)’라는 의미 관계가 집합 A에 속하는 원소들에 대한 순서화라는것 을 의미함

52 부분순서관계(계속) [정의13] 집합 A 에 대한 관계 R 이 부분순서관계고 a, b∈A 일 때
또는 이면 a 와 b는 비교가능(comparable) 또는 이면 a 와 b는 비교불가능(noncomparable) 완전순서관계(total order relation) 또는 선형순서관계(linear order relation) 집합 A 에 속하는 원소들의 모든 쌍이 비교가능할 때의 R 완전순서집합(totally ordered set) 또는 선형순서집합(linearly ordered set) 집합 A

53 부분순서관계(계속) [예제42] 집합 A={1, 2, 3, 6, 9, 18}에 대한 관계 R 이 a 가 b 로 나누
[풀이] 18|3이 될 수 있으므로 비교가능

54 부분순서관계(계속) [정의14] [예제43] 두 부분순서집합 과 가 있을 때
두 부분순서집합 과 가 있을 때 곱집합 에 대한 사전식 순서(lexicographic order) 인 경우 또는 이고 인 경우에 정해짐 [예제43] 부분순서집합 에서 다음에 대한 사전식 순서를 정하여라. (1) (2, 4, 3), (3, 2, 2) (2) (3, 4, 6), (3, 4, 8) [풀이] (1) (2, 4, 3) (3, 2, 2) (2) (3, 4, 6) (3, 4, 8)

55 부분순서관계(계속) [예제44] 집합 A={1,2,3,6,8,12}에 대한 관계 R이 a가 b로 나누어 떨어지는 관계 (a|b)일 때 하세도표를 그려라. [풀이] 12 1 3 6 8 2

56 부분순서관계(계속) [예제46] 집합 {a, b, c}에 대한 멱집합(power set)을 A 라고 할 때 부
분순서집합 에 대한 하세도표를 그려라. [풀이]

57 부분순서관계(계속) [정의15] 부분순서집합 가 있을 때 극대원소(maximal element)
부분순서집합 가 있을 때 극대원소(maximal element) A 의 원소 a 에 대하여 인 원소 b 가 A 에 존재하 지 않을 때 원소 a 극소원소(minimal element) 인 원소 b 가 A 에 존재하지 않을 때 원소 a

58 부분순서관계(계속) [정의16] 최대원소(greatest element)
부분순서집합 A 의 모든 원소 b 에 대하여 인 A 의 원소 a 최소원소(least element) 인 A 의 원소 a

59 부분순서관계(계속) [예제48] 다음의 하세도표에서 극대원소, 극소원소, 최대원소, 최소원 소를 찾아라. (2) (3)

60 부분순서관계(계속) [정리04] 공집합이 아니고 유한한 모든 부분순서집합 는 극소 원소를 갖는다. [증명]

61 부분순서관계(계속) [정의17] 과 가 집합 A 에 대한 부분순서관계라고 하자.
이 때 A 의 모든 원소 a 와 b 에 대하여 이면 를 만족할 때 는 와 양립(compatible)한다고 함 가 와 양립할 수 있는 완전순서관계면 는 에 대한 위상정렬(topological sorting)이라고 함

62 부분순서관계(계속) [예제49] 부분순서집합 ({2, 3, 4, 6, 18, 24}, |)의 원소들을 위상정렬
하여라. 여기서 |는 a가 b로 나누어 떨어지는 관계(a|b)다. [풀이] A={2, 3, 4, 6, 18, 24}라고 하고, 하세도표로 나타내면 다 음과 같다.

63 부분순서관계(계속) 이 부분순서집합에서 극소원소는 2와 3이다. 이 중에서 3을 선택하면 완전순서의 시작은 3이 되고, 부분
순서집합은 A-{3}이 된다. 이제 극소원소는 2가 되며, 2를 선택하면 완전순서는 가 되고 부분순서집합은 A-{3, 2}가 된다. 이 때 극소원소는 4와 6이 되며, 이 중에서 6을 선택하면 완 전순서는 이 된다. 즉, 이와 같은 과정을 반복하게 되 면 다음과 같이 부분순서집합의 원소들을 정렬할 수 있다.

64 Thank you