이산 수학 - 10 관계

<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    tex2jax: {
      inlineMath: [ ['$','$'], ["\\(","\\)"] ],
      processEscapes: true
    }
  });
</script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.2/MathJax.js?config=TeX-MML-AM_CHTML"></script>

 

집합 A, B가 주어질 때

- A, B의 곱 집합 : A x B = {(a, b) | a $\in$ A, b $\in$ B}

- A에서 B로으의 관계 R은 A x B의 한 부분잡합을 의미

=> (a, b) $\in$ R이면, aRb로 표기 / (a, b) $\notin$ R 이면 a$\bar{R}$b로 표기

 

ex) 철수는 1반, 영희는 2반, 영진은 1반 일때 학생에서 반으로의 관계 R로 표시하면

- R = {(철수, 1반), (영희, 2반), (영진, 1반)} $\subset$ A x B

- 철수R1반, 영희R2반, 영진 R1반, 영진$\bar{R}$2반

 

 

집합 A, B가 주어질때

- B = A이면 A에서 A로의 관계 R을 'A에서의 관계'라고도 함

 

A = {철수, 영희, 짱구}에 대하여

- 철수와 영희는 친구, 출수와 짱구는 친구, 영희와 짱구는 친구라는 관계를 R로 표기하면

- R = {(철수, 영희), (철수, 짱구), (영희, 짱구)}

 

 

A = {1, 2, 3, 4}, R = {(a, b) $\in$ A x A | a < b }로 주어지면

- R = {(1, 2), (1,3), (1,4), (2, 3), (2,4), (3, 4)}

- 1R4, 3$\bar{R}$2

 

 

 

A에서 B로의 관계 R이 주어질 때

- A = R의 정의역(domain)

- B = R의 공역(Codomain)

- R의 치역(Range) = {b $\in$ B | (a, b) $\in$ R인 a $\in$ A가 존재}

- R의 치역 $\subset$ R의 공역 = B

 

 

예시

- 집합 A = {철수, 영희, 영진}, 집합 B = {1반, 2반, 3반}와 철수는 1반, 영희는 2반, 영진은 1반을 나타내는 관계 R에 대하여

- R의 정의역 = {철수, 영희, 영진} = A

- R의 공역 = {1반, 2반, 3반} = B

- R의 치역 = 1반, 2반

 

 

관계의 표현 방법

1. 순서쌍을 이용한 표현

- 관계의 모든 원소를 순서쌍으로 표현

- 집합 A = {1, 2, 3, 4}, 집합 B = {2, 3, 4, 5}, R = {(a, b) $\in$ A x B | a + b는 짝수}

-> R = {(1, 3), (1, 5), (2, 2), (2,4), (3, 3), (3, 5), (4, 2), (4, 4)}

 

2. 화살표 도표를 이용한 표현

- A에서 B로의 관계 R이 주어졌을 때, 만약 (a, b) $\in$ R이면 a와 b를 화살표로 연결해서 관계를 표현

ex) 집합 A = (1, 2, 3, 4}, B ={2, 3, 4, 5}, R = {(a, b) $\in$ A x B | a + b는 소수}

 

 

3. 좌표를 이용한 표현

- A에서 B로의 관계 R이 주어졌을때 A의 원소는 x축, B의 우너소는 y축에 표시

- (a, b) $\in$ R이면 a를 가리키는 축과 b를 가리키는 축이 만나는 점을 좌표에 표시

ex) 집합 A = (1, 2, 3, 4}, B ={2, 3, 4, 5}, R = {(a, b) $\in$ A x B | a + b는 짝수}

- x축에 A의 원소, y축에는 b의 원소

 

4. 관계 행렬을 이용한 표현

- A, B로 관계 R이 주어질 때 A의 각 원소가 행을 나타내는 것으로, B의 각 원소는 열을 나타내는 것으로 가정

- (a, b) $\in$ R이면 a를 가리키는 행과 b를 가리키는 열이 만나는 원소는 1

- (a, b) $\notin$ R이면 a를 가리키는 행과 b를 가리ㅣ는 열이 만나는 원소는 0

ex) 집합 A = (1, 2, 3, 4}, B ={2, 3, 4, 5}, R = {(a, b) $\in$ A x B | a + b는 짝수}

 

 

5. 방향 그래프를 이용한 표현

- 그래프 : 점들과 점 사이를 연결한 선으로 구성된 수학적 개념

- 방향 그래프 : 점 사이를 연결한 선이 화살표인 그래프

 

 

 

방향 그래프를 이용한 표현

- A에서의 관계 R이 주어질 때 A의 각 원소를 점으로 표시하고 (a, b) $\in$ R이면, a를 나타내는 점에서 b를 나타내는 점으로 화살표를 그려서 관계를 표현

ex) 집합 A = {1, 2, 3, 4}, R = {(a, b) $\in$ A x A | a - b $\geq$ 0}

 

관계의 성질

- 반사성

- 대칭성

- 추이성

 

 

 

반사성의 정의

- 집합 A에서 관계 R이 주어질때, 모든 a $\in$ A에 대해서 (a, a) $\in$ R이면 R이 반사성을 가진다고 하거나 R을 반사 관계라고 함.

ex) A = {1, 2, 3, 4} , R = {(a, b) $\in$ A x A | a - b $\geq$ 0}

- R ={(1, 1), (2, 1), (2, 2), (3, 1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3), (4, 4)}

 -> R은 반사 관계

ex) A = {1, 2, 3, 4}, R = {(a, b) $\in$ A x A | a - b $\gt$ 0}

- R = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}

 -> R은 반사 관계가 아님( (1,1) $\notin$ R)

 

 

반사 관계의 특징

- R이 반사 관계이면 R의 관계 행렬의 대각 원소는 모두 1

- R이 반사 관계이면 R의 방향 그래프 표현에서 모든점은 루프를 가짐

ex) A = {1, 2, 3, 4}, R = {(a, b) $\in$ A x A | a - b $\geq$ 0}

 

비반사성

- 집합 A에서 관계 R가 주어질때, 모든 a $\in$ A에 대하여 (a, a) $\notin$ R이면, R이 비반사성을 가진다거나 R을 비반사 관계라고 한다.

ex) A = {1, 2, 3, 4}, R = {(a, b) $\in$ A x A | a- b $\gt$ 0}

- 관계 행렬의 대각 원소가 0, 방향 그래프에서 모든 점은 루프를 가지지 않음 -> 비반사 관계

- R = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}, 비반사 관계

 

반사 관계와 비반사 관계의 관계

- 반사 관계가 아니면 비반사 관계이다? -> 거짓

- 다음 관계는 반사 관계도 비반사 관계도 아님

 

 

 

대칭성

- 집합 A에서 관계 R이 주어질때 , (a, b) $\in$ R이면 항상 (b, a) $\in$ R을 만족시키면 R이 대칭성을 가진다 하며, R을 대칭 관계라고 함.

ex) A = {1, 2, 3, 4}, R = {(a, b) $\in$ A x A | a + b는 홀수}

- R = {(1, 2), (1, 4), (2, 1), (2, 3), (3, 2), (3, 4), (4, 1), (4, 3)}

 -> R은 대칭 관계

ex) A = {1, 2, 3, 4}, R = {(a, b) $\in$ A x A | a - b $\get$ 0}

- R = {(1, 1), (2,1), (2, 2), (3, 1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3), (4, 4)}

 -> (2, 1) $\in$ R, (1, 2) $\notin$ R => R은 대칭 관계가 아님

 

 

대칭 관계의 특징

- R의 관계 행렬은 대칭 행렬

- R의 방향 그래프 표현에서 어떤 점 x에서 다른점 y로 가는 연결선이 존재하면 y에서 x로 가는 연결선도 반드시 존재

ex) A = {1, 2, 3, 4}, R = {(a, b) $\in$ A x A | a + b는 홀수}

 

 

추이성

- 집합 A에서 관계 R이 주어질때, (a, b) $\in$ R이고, (b, c) $\in$ R이면 항상 (a, c) $\in$ R을 만족 시키면, R은 추이성을 가진다 하고, R을 추이 관계라고 한다

ex) A = {1, 2, 3, 4}, R = {(a, b) $\in$ A x A | a - b $\get$ 0} -> R은 추이관계

- (a, b) $\in$ R -> a - b $\get$ 0

- (b, c) $\in$ R - > b - c $\get$ 0

 => (a, b) $\in$ R, (b, c) $\in$ R -> a - b $\get$ 0, b - c $\get$ 0 -> a -c $\get$ 0 -> (a, c) $\in$ R

ex) A = {1, 2, 3, 4}, R = {(a, b) $\in$ A x A | a + b는 홀수} -> R은 추이 관계가 아님

 - (1, 2) $\in$ R이고, (2, 3) $\in$ R이지만 (1, 3) $\notin$ R