Download presentation
Presentation is loading. Please wait.
1
관계 기본 개념 관계의 표현 관계의 성질 관계의 연산 관계의 폐포 동치 관계 부분순서 관계
2
집합의 원소들 사이의 연관성을 나타내기 위한 구조인 관계의 개념을 파악한다.
화살도표, 좌표도표, 관계행렬을 통하여 관계를 도식화한다. 반사관계, 대칭관계, 추이관계로부터 관계의 성질을 이해한다. 관계들을 결합하는 합성관계와 연산들을 이해한다. 반사폐포, 대칭폐포, 추이폐포를 통하여 새로운 관계를 만든다. 하세도표 등을 이용하여 부분순서관계를 이해한다.
3
곱집합(Cartesian product)
A 와 B 는 집합 A, B 가 유한집합일 때 의 원소의 개수 표현
4
이항관계(binary relation)
두 개의 원소로 구성된 순서쌍(ordered pair)의 집합
5
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)
8
n 항 관계(n-ary relation) 두 개 이상의 집합의 원소들 사이의 관계 데이터베이스를 표현하는 데 자주 사용
데이터베이스(database) 어느 한 조직의 여러 응용 시스템을 공유하도록 통합, 저장, 운영되는 데이터 집합 관계형 데이터베이스 모델(relational database model) 데이터베이스에서 n 항 관계의 개념을 기초로 하여 개발된 것 집합 에 대한 n항 관계(n-ary relation) 의 부분집합
10
관계 R의 정의역은 R-1의 치역이 되고, 관계 R의 치역은 R-1에서의 정의역이 됨
11
화살도표(arrow diagram) 두 집합 A, B 가 있을 때 집합 A 의 원소 a 와 집합 B 의 원소 b 사이에 관계가 성립하는 경우 그 관계를 화살표로 그려서 나타내는 방법
12
좌표도표(coordinate diagram)
두 집합 A, B 가 있을 때 집합 A 의 원소 a 를 x 축 위의 점으로 표시하고, 집합 B 의 원소 b 를 y 축 위의 점으로 표시하여 두 점이 좌표상에서 만나는 점을 나타내는 방법
13
관계행렬(relation matrix)
두 집합 A, B 에 대한 관계를 행렬로 표현한 방법 A 의 원소들을 행에 배치하고 B 의 원소들을 열에 배치한 후 A 의 원소와 B 의 원소 사이에 관계가 있으면 1로, 관계가 없으면 0으로 행렬의 원소를 나타냄 행렬 안의 모든 원소들이 0 또는 1인 행렬을 부울행렬(boolean matrix)이라고 함
14
방향그래프(directed graph)
하나의 집합에 대한 관계를 나타냄 집합 A의 관계에 대한 방향그래프를 그리고자 할 때 먼저 A의 원소들을 나타내는 정점(vertex)을 그리고, 원소 (a, b)가 관계에 속하면 a에서 b로 화살표 모양의 에지(edge)를 그림 루프(loop) (a, a)가 관계일 때 a 에서 a 로 그리게 되는 에지
16
집합 A 에 대한 관계 R 반사관계(reflexive relation) 대칭관계(symmetric relation)
모든 a∈A 에 대하여 aRa 일 때의 R 대칭관계(symmetric relation) 모든 a, b∈A 에 대하여 aRb 이면 bRa 일 때의 R 추이관계(transitive relation) 모든 a, b, c∈A에 대하여 aRb 이고 bRc 이면 aRc 일 때의 R
17
집합 A 에 대한 관계 R 비반사관계(irreflexive relation)
모든 a∈A 에 대하여 일 때의 R 반대칭관계(antisymmetric relation) 모든 a, b∈A 에 대하여 aRb 이고 bRa 이면 a=b 일 때의 R
28
R 과 S 의 합성관계(composition relation)
a∈A 이고 c∈C 일 때 aRb이고 bSc인 b∈B가 존재하는 순서쌍 (a, c)로 구성되는 관계 S◦R로 나타냄
30
관계행렬을 이용한 합성관계
32
하나의 관계 R 에 대한 합성관계 n이 양의 정수일 때
38
반사폐포(reflexive closure)
관계 R 을 포함하고 반사적이며, R 이 포함된 모든 반사관계 안에 포함됨 R 이 집합 A 에 대한 관계일 때 R 의 반사폐포
39
대칭폐포(symmetric closure)
관계 R 을 포함하고 대칭적이며, R 이 포함된 모든 대칭관계 안에 포함됨 R 이 집합 A 에 대한 관계일 때 R 의 대칭폐포
40
추이폐포(transitive closure)
반사폐포나 대칭폐포를 만드는 것에 비해 매우 복잡 새로운 순서쌍을 추가할 필요가 없을 때까지 반복적으로 순서쌍 추가 방향그래프 G 에서 a 에서 b 로의 경로(path) x0=a, xn=b라고 할 때 한 개 이상의 에지 (x0, x1), (x1, x2), ···, (xn-1, xn)로 구성 길이 n인 경로 x0, x1, x2, ···, xn-1, xn으로 나타냄
41
연결관계(connectivity relation) R *
관계 R 에 적어도 길이 1이면서 a 에서 b 로의 경로가 있는 쌍 (a, b)로 R n 은 길이 n 이면서 a 에서 b 로의 경로가 있는 쌍 (a, b)로 구성 R * 는 R n 의 합집합:
45
동치관계(equivalence relation)
46
R 에 대한 a 의 동치류(equivalence classes)
집합 A 의 각 원소 a 에 대하여 [a] [a]={x| (a, x)∈R}
48
부분순서관계(partial order relation)
집합 A 에 대한 관계 R 이 반사관계, 반대칭관계, 추이관계가 성립할 때의 관계 R 이 때 A 는 부분순서집합(partially ordered set, poset) (A, R)로 나타냄
49
집합 A 에 대한 관계 R 이 부분순서관계일 때 (a, b)∈R 을 나타내기 위해 ‘ ’를 사용하여 라고 나타냄
부분순서관계는 관계 ≤를 일반화하는 것 집합 A 에 대한 관계 R 이 부분순서관계일 때 (a, b)∈R 을 나타내기 위해 ‘ ’를 사용하여 라고 나타냄 이고 이면 라고 나타냄 ‘a가 b보다 우선한다(a precedes b)’라는 의미
Similar presentations
