[이산수학]부분순서관계란? (비교가능/비교불가능/완전순서)

[이산수학]부분순서관계란? (비교가능/비교불가능/완전순서)_예제포함

 

관계는 순서쌍으로 표현합니다. 순서쌍은 원소 나열에 의미가 있음을 말합니다. (a, b)와 (b, a) 같이 a와 b의 나열에 따라 서로 다른 원소가 됩니다. 관계 중에는 그 성질이 무엇이냐에 따라 모든 원소가 부분적인 순서관계를 갖는 경우가 있습니다. 

 

■ 부분순서관계(Partial Order)

부분순서관계가 되려면 반사관계, 반대칭관계, 추이관계가 성립해야 합니다. 이때 부분순서관계는 꼭 반대칭관계가 성립해야 합니다. 반대칭관계는 (a, b) ∈ R이고, a ≠ b 일 때는  (b, a) ∉ R 이어야 성립합니다. 그래서 원소 a와 원소 b사이의 순서관계가 확실할 수밖에 없습니다.

 

 

■ 비교가능(Comparable)/비교불가능(Noncomparable)

부분순서관계가 성립하는 관계의 순서쌍을 구성하는 원소들에 대해 우선 순위를 판별할 수 있는지 없는지를 '비교가능' 또는 '비교불가능'으로 표현합니다.

 

집합 A에 대한 관계 R이 부분순서관계고, a, b ∈ A일 때,  a < b 또는 b < a면 a와 b는 비교가능이라고 하고, a ≮ b 또는  b ≮ a면 a와 b는 비교불가능이라고 합니다.

 

■ 완전순서(Total Order)

집합 A에 대한 부분순서관계 R에서 집합 A의 모든 원소의 순서쌍을 비교할 수 있으면 관계 R을 완전순서관계(total order relation)라 하고, 이때 집합 A를 완전순서집합이라고 합니다.

 

 

수학으로 이해하는 디지털 논리 이산수학 244p 참고

 

-----------------------------------

이산수학 총정리

목록 보러가기 

-----------------------------------