관계
- 두 집합 X와 Y에 대하여 곱집합 의 부분집합 R을 X에서 Y로의 관계라고 한다.
- 만약 x와 y가 각각 X와 Y의 원소이고 이면 로 표기하며, x는 y와 R의 관계가 있다고 한다.
- 만약 이면 로 표기하며, x는 y와 R의 관계가 없다고 한다.
- 예제) 집합 일 때, A에서 B로 가는 관계 R은 다음과 같을 때 물음에 답하라.
- 관계 R을 순서쌍으로 나타내시오
- 4R1은 성립하는가?
- 성립하지 않음
관계의 표현
화살표 도표
집합
- 이기 위한 필요충분조건은
부울행렬
- 관계를 행렬로 나타냈을 때 이점: 대수연산자를 이용하여 관계에 관련된 문제를 편리하게 계산 가능 에서의 관계 R이 다음과 같이 정의되었을 때 R을 부울행렬로 나타내시오
-
관계의 성질
반사적(reflexive)
- 집합 A에서의 관계 R에 대해 모든 에 대해 이면 R은 반사적이라고 한다.
- 집합 A에서의 관계 R이 반사적이 되려면 A의 모든 원소가 자기 자신과 관계를 가져야 한다.
- 예를 들어, 집합 에서의 관계 R이 반사적이려면 (1, 1), (2, 2), (3, 3)이 모두 R에 포함되어야 한다.
대칭적(symmetric)
- 집합 A에서의 관계 R에 대해 모든 에 대해 일 때 이면 R은 대칭적이라고 한다.
- 집합 A에서의 관계 R이 대칭적이 되려면, R에 포함된 모든 원소가 대칭되는 관계를 가져야 한다.
- 예를 들어, 집합 에서의 관계 R이 대칭적이려면 (1, 2)가 R에 포함되어 있다면 (2, 1)도 R에 포함되어야 한다.
추이적(transitive)
- 집합 A에서의 관계 R에 대해 모든 에 대해 이고 일 때, 이면 R은 추이적이라고 한다.
- 집합 A에서의 관계 R이 추이적이 되려면, R에 포함된 모든 원소들에 대해서 이고, 이면 이어야 한다.
- R 관계
- (1,1), (2,2), (3,3)모두 R에 포함되어 있으므로 반사적이다.
- (1,2)일 때 (2,1)은 포함되어 있지 않으므로 대칭적이지 않다.
- (1,3)이 관계에 포함되어 있고, (3,2)가 포함되어 있지만, (1,2)는 포함되어 있지 않으므로 추이적이지 않다.
- S 관계
- 반사적이다.
- (1,3)이 관계에 포함되어 있을 때 (3,1)도 포함되어 있으므로 대칭적이다.
- 추이적 조건에도 만족하지 못함
- T 관계
- (2,2)와 (3,3) 은 관계에 포함하지 않으므로 반사적이지 않다.
- (2,1)이 관계에 포함되어 있을 때 (1,2)는 포함되어 있지 않으므로 대칭적이지 않다.
- (2,1)과 (1,3)이 관계에 포함되어 있고, (2,3)도 포함되어 있으므로 추이적이다.
- 추이적 관계의 필요조건을 만족시키는 원소들이 존재하므로 추이적이다.
관계의 종류
주어진 관계를 이용하여 새로운 관계를 만들어 낼 수 있다.
역관계(inverse relation)
- 집합 X에서 집합 Y로의 관계 R이 있을 때, 관계를 구성하는 각 순서쌍의 원소 순서를 바꾸면 Y에서 X로의 관계가 되며, 이를 역관계라고 한다.
- 라고 표기함
합성관계(composition relation)
- 집합 A에서 집합 B로의 관계 R이 있고, 집합 B에서 집합 C로의 관계 S가 있을 때, 은 집합 A에서 집합 C로의 관계를 나타낸다.
- 집합 A에서 집합 B로의 관계가 R이고, 집합 B에서 C로의 관계가 S일 때, A에서 C로의 관계는 로 표기하는 것이 아니라 로 표기한다. 주의할 것
동치관계(equivalence relation)
- 집합 A에서의 관계 R이 반사적이고, 대칭적이고, 추이적이면 R은 동치관계라고 한다.
- 나머지함수: 하나의 식을 다른 값으로 나눈 뒤 나머지를 구하는 함수
- 8 mod 5 = 3이고 13 mod 5 = 3이다. 두 정수 m, n에 대해 양의 정수 d로 나머지 연산을 하였을 때 같은 값이 나오는 경우가 있는데 이때의 m과 n은 d에 관한 모듈로 합동이라 하고 로 표기한다.