관계의 개념, 표현, 성실, 합성관계, 동치관계와 부분순서관계
관계의 개념
- 원소들 간 관계 정의는 매우 중요함!
Relation & Binary Relation
- 곱집합으로!
Domain : dom(R)
정의역
Codomain : codom(R)
공번역
Range : ran(R)
치역
n-ary Relation
n항 관계
- 관계가 이루어지는 집합이 셋 이상일 때
Inverse Relation :
역관계
- 관계 R에서 정의역이 역관계에서는 공번역이고, R의 공번역은 역관계에서 정의역임.
관계의 표현
Arrow Diagram
Coordinate Diagram
좌표도표
Relation Matrix
- 1과 0으로만 표시.
예시) 
Directed Graph
방향그래프
- 루프: 원소에서 시작해서 그 원소로 끝나는 화살표
관계의 성질 (5개)
Reflexive Relation
반사관계
- 모든 원소가 자기자신이랑 대응 있을 때 성립
- 반사 관계에 대한 관계 행렬은 대각원소들이 모두 1임.
- 방향 그래프로 나타내면 모든 원소에 대해 루프 존재
Irreflexive Relation
비반사관계
- (a,a)가 하나도 존재하지 않으면 비반사 (반사랑 비반사는 동시에 불가함!)
- 관계행렬에서 대각원소는 모두 0
- 방향 그래프는 루프 존재 X
Symmetric Relation
대칭관계
- 관계행렬에서 대각원소 기준으로 마주보는 원소가 같음
- 방향그래프는 반드시 양방향으로 화살표
Asymmetric Relation
반대칭관계
- 관계행렬 : 대각원소 기준 1이면 마주보는 원소 0. 0,0 도 가능
- 방향그래프 : 두 원소 사이에 단방향. 루프 가능.
--> 대칭과 반대칭은 둘다 가능하거나 둘다 아닐 수도 있음.
Transitive Relation
추이관계
예제
합성관계
- DB의 join 연산
Composition Relation: S º R
- 두 개 이상의 관계를 합성해 새로운 관계 생성
합성관계는 교환법칙 성립하지 않는다!!
합성관계와 관계행렬
관계행렬을 이용해 합성관계 구하기 가능.
합성관계의 거듭제곱
- 3제곱에서 자기자신이 나오면 추이관계다!
추이관계와 거듭제곱의 관계
동치관계와 부분순서관계
Equivalence Relation
- 반,대,추
- 동치관계는 집합의 원소들이 같다는 것 의미
Equivalence Class [a]
동치와 분할
동치류 집합의 측징
- 공집합 안됨
- 서로소여야 함. 겹치는거 안됨.
example
Partial Order Relation
- 반,반,추
- 관계 R에 반대칭관계 성립하면 그 관계는 순서관계를 가짐. -> 순서관계 가지려면 서로다른 원소 a,b 에 대해 (a,b)가 존재하면 (b,a)는 존재안함.
example
Comparable, Noncomparable
Total Order
하세도표
- 방향그래프와 부분순서관계 성질 이용해서 표기
example
Maximal Element
- 여러개 존재 가능
- 하세도표에서 가장 상위에 위치(우선순위 가장 높음)한 하나 이상의 원소들
- 극대원소들 간 우선순위는 같음.
Minimal Element
- 여러개 존재 가능
- 하세도표 상 가장 하위.
- 우선순위 가장 낮은 원소들
Greatest Element
- 하세도표 상 가장 상위 단 하나 원소
- 가장 우선순위 높은 원소
Least Element
- 하세도표 가장 하위에 있는 단 하나 원소
- 가장 우선순위 낮은 원소
example
roundy