이산수학 관계

1. 관계의 종류
1) 반사적 관계: 관계 R을 구성하는 집합 A에 대해서 a ∈ A에 대해 (a,a) ∈ R이라면 관계 R은 반사적 관계가 된다.
    예) A = {a, b, c}
    R은 (a,a), (b,b), (c,c)의 원소를 모두 포함해야지 반사적 관계가 성립된다.
2) 비반사적 관계: R을 집합 X에서의 어떤 이항 관계라고 하자. 만일 모든 x ∈ X에 대해 (x,x) !∈ R이면 R은 비반사적이라고 한다.
3) 대칭적 관계: 관계 R을 구성하는 집합 A에 대해서 a, b ∈ A에 대해 (a,b) ∈ R이고 (b,a) ∈ R 이라면 관계 R은 대칭적 관계가 된다.
    예) A = {a, b, c}
    R에 (a,b)의 원소를 포함하고 있다면 (b,a)의 원소를 가지고 있어야 대칭적 관계가 성립된다.
4) 반대칭적 관계: 관계 R을 구성하는 집합 A에 대해서 a, b ∈ A에 대해 (a,b) ∈ R, (b,a) ∈ R이고 a와 b가 같지 않은 쌍이 한개이상 존재 하지 않을 경우
    예) A = {a, b, c}
    R1 = { (a,b), (b,a) } 반대칭 관계가 아니다.
    R2 = { (a,b), (c,a) } 반대칭 관계이다.
5) 추이적 관계: 관계 R을 구성하는 집합 A에 대해서 a, b, c ∈ A에 대해 (a,b) ∈ R 그리고 (b,c) ∈ R 일때 (a,c) ∈ R 이라면 관계 R은 추이적 관계가 된다.
    예) A = {a, b, c}
    R에 (a,b), (b,c)가 있다면 (a,c)가 R에 존재해야 추이적 관계가 된다.
6) 동치 관계: 반사적, 대칭적, 추이적인 이항 관계를 뜻한다. 즉, 어떤 집합 X과 관계 ~이 있을 때, 임의의 원소 a, b, c에 대해
반사관계: a ~ a
대칭관계: a ~ b => b ~ a
추이관계: a ~ b, b ~ c => a ~ c가 성립한다는 것을 의미한다.

2. 하세도표(hasse diagram): 부분순서집합의 원소들을 표현하기 위해 고안된 표기법으로, 각 원소의 순서 관계를 그래프로 표현한다.
1) 극대원소 : 하세 도표의 맨 위에 위치하는 원소
2) 극소원소 : 하세 도표의 맨 아래에 위치하는 원소
3) 최대원소 : 하세 도표에서 모든 원소의 맨 위에 있는 것
4) 최소원소 : 하세 도표에서 모든 원소의 맨 아래에 있는 것