1
프로그래머 수학
8주차 강의
관계(1)
2
1. 기본 개념
곱집합(Cartesian product)
A 와 B 는 집합
A , B 가 유한집합일 때 의 원소의 개수
표현
B A
|
|
|
|
|
| A B A B A B
B
A
A
2A
A
3
2. 이항 관계 (Binary Relations)
이항관계 : 두 집합 A, B 에 대하여 A 로부터 B 로의 이항 관계 R 은 두 집합의 곱집합 A B 의 부분 집합이다.
A B 의 원소인 순서쌍
(a, b)가 주어졌을 때, a R b 는 (a, b) R 의 필요충분조건
a R b (a, b) R a b (a, b) R
정의역 (domain) : Dom(R) = { a | ( a,b) R} A 치역 (range) : Ran(R) = { b | (a,b) R} B
R
4
역관계(Inverse of a Relation)
역관계(inverse relation) R
-1
R 이 A 에서 B 로의 관계라 하자.
B 에서 A 로의 역관계 R
－1은 다음과 같이 정의된다:
R
－1= { ( y , x ) ∈ B × A | ( x , y ) ∈ R }
5
3. 관계의 표현
이항관계의 표현 방법
화살표 도표
좌표 도표
방향 그래프
관계 행렬
6
화살도표(arrow diagram)
두 집합 A, B 가 있을 때 집합 A의 원소 a와 집합 B의 원소 b사이에 관계가 성립하는 경우 그 관계를 화살표로 그려서 나타내는 방법
3-1. 화살표 도표
예제 :
집합 A={1,2,3,4}, 집합 B={a,b,c}라 하고, A와 B 사이의 관계 R={(1,a), (1,b), (2,b), (2,c), (3,c), (4,b)}라 할 때 관계 R과 역관계 R-1을 화살도표를 이용하여 나타내어라.<풀이>
7
좌표도표(coordinate diagram)
두 집합 A, B 가 있을 때 집합 A 의 원소 a 를 x 축 위의 점으로 표시하고, 집합 B 의 원소 b 를 y 축 위의 점으로 표시하여 두 점이 좌표상에서 만나는 점을 나타내는 방법
3-2. 좌표 도표
예제 :
두 집합 A={1,2,3,4}, 집합 B={2,3,4}이고 집합 A에서 B로의 관계 R={(1,3), (2,1), (2,4), (3,2), (4,3)}일 때 관계 R을 좌표도표를 이용하여 타나내어라.<풀이> 관계 R을 좌표도표를 이용하여 나타내면 다음과 같다.
8
방향그래프(directed graph)
하나의 집합에 대한 관계를 나타냄
집합 A의 관계에 대한 방향그래프를 그리고자 할 때 먼저 A의 원소들을 나타내는 정점(vertex)을 그리고, 원소 (a, b)가 관계에 속하면 a에서 b로 화살표 모양의 에지(edge)를 그림
루프(loop): (a, a)가 관계일 때 a 에서 a 로 그리게 되는 에지
3-3. 방향 그래프
예제: 집합 A={1,2,3,4,5}이고, 관계 R= {(a,b)| a>b, a,bA}
이라 할 때, 관계 R에 대한 방향 그래프를 그려라.
<풀이>
2
1
5
4 3
9
관계행렬(relation matrix)
두 집합 A, B 에 대한 관계를 행렬로 표현한 방법
A 의 원소들을 행에 배치하고 B 의 원소들을 열에 배치한 후 A 의 원소와 B 의 원소 사이에 관계가 있으면 1로, 관계가 없으면 0으로 행렬의 원소를 나타냄
행렬 안의 모든 원소들이 0 또는 1인 행렬을 부울행렬(boolean matrix)이라고 함
3-4. 관계 행렬
예제: 두 집합 A={1,2,3}, B={1,2,3,4}에 대해서 관계 R={(1,1), (1,3), (2,3), (3,2), (3,4)}일 때 이를 관계 행렬로 나타내어라.
<풀이> 관계행렬 MR은 다음과 같다.
10
4. 관계의 성질
반사 관계(reflexive relation)
집합 A에 있는 모든 원소 a에 대해, (a,b)R 인 관계
비반사 관계 (irreflexive relation)
집합 A에 있는 모든 원소 a에 대해, (a,a) R 인 관계
대칭관계 (symmetric relation)
집합 A에 있는 원소 a, b에 대해, (a,b) R일 때 (b,a) R인 관계
반대칭 관계 (antisymmetric relation)
집합 A에 있는 모든 원소 a, b에 대해, (a,b) R이고 (b,a) R이라면, a = b 인 관계
추이관계(transitive relation)
집합 A에 있는 원소 a, b, c에 대해, (a,b) R이고 (b,c) R 이면, (a,c) R 를 만족하면 관계
11
4-1. 반사 관계
반사관계(reflexive relation)
집합 A에 있는 모든 원소 a에 대해, (a,b)R 인 관계
예제 :
다음 방향그래프는 반사관계가 성립하는가?12
비반사 관계 (irreflexive relation)
집합 A에 있는 모든 원소 a에 대해, (a,a) R 인 관계
예제 :
다음 방향그래프는 대칭관계가 성립하는가?4-2. 비반사 관계
예제
: x, y가 자연수의 집합 N의 원소일 때 다음의 관계는 대칭 관계인지 아닌지를 구별하여라.R = {(x, y) | x N, y N, x + y = 10}
13
대칭관계 (symmetric relation)
집합 A에 있는 원소 a, b에 대해, (a,b) R일 때 (b,a) R인 관계
예제 :
다음은 대칭관계가 성립하는가 ? 예제 :
x, y가 자연수의 집합 N의 원소일 때 다음의 관계는 대칭 관계인지 아닌지를 구별하여라.R = {(x, y) | x N, y N, x + y = 10}
4-3. 대칭 관계
14
반대칭관계 (symmetric relation)
집합 A 에 있는 모든 원소 a , b 에 대해, ( a,b) R 이고 (b,a) R 이라면, a = b 인 관계
즉, 모든 원소 x, y (x y )에 대해 (x, y) R이면 (y, x) R인 관계를 만족하면, 관계R을 반대칭 관계라고 한다.
예제 :
다음의 관계들이 반대칭 관계인지 아닌지를 구별하여라.(1) R1 = {(1,2), (2,2), (2,3), (3,1), (3,4), (4,4)}
(2) R2 = {(a, b) | a N, b N, a b}
4-4. 반대칭 관계
15
4-5. 추이 관계
추이관계(transitive relation)
집합 A에 있는 원소 a, b, c에 대해, (a,b) R이고 (b,c) R 이면, (a,c) R 를 만족하면 관계
예제 :
다음 방향그래프는 추이관계가 성립하는가?16
예제 :
집합 A={1,2,3}에 대하여 다음의 관계가 추이관계인지 판별하고, 각각 관계행렬로 나타내어라.(1) R1={(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1)}
(2) R2={(2,2), (3,3)}
(3) R3={(1,3)}
(4) R4={(1,3), (2,2), (3,1)}
<풀이>
(1) (3,1)∈R이고 (1,2)∈R일 때 (3,2)∈R이므로 추이관계가 성립하지 않는다.
(2) 추이관계이다 (3) 추이 관계이다 (4) 추이 관계 아니다.
관계의 성질: 예제
17
예제 :
다음 관계행렬을 보고 반사관계, 대칭관계, 반대칭관계, 추이관계 중에서 어떤 관계가 성립하는지 판별하라.<풀이>
(1) 반사관계, 대칭관계, 반대칭관계, 추이관계가 모두 성립한다.
(2) 반사관계와 반대칭관계가 성립한다.
관계의 성질: 예제
18
예제 :
집합 A = {1,2,3,4}일 때 다음의 관계들에 대하여 그 관계가 반사, 대칭, 반대칭, 추이 관계인지를 구별하여라.(1) R1 = {(1, 1), (1, 2), (2, 1), (2, 4), (4, 2), (4, 4)}
(2) R2 = {(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2), (3, 3), (4, 4)}
(3) (4) R4
1 2 3 4 1 1 1 0 0 M = 2 1 1 0 0 3 0 0 1 1 4 0 0 1 1
관계의 성질: 예제
19
참고문헌
본 강의 자료에서 예제 등의 출처는 다음과 같은 참고 문헌이다.
1) PLD: Programming Logic and Design using Flowchart, 주형석 저(IT미디어)
2) 이산수학: 논리,명제에서 알고리즘까지, 홍영진 저(한빛미디어) 3) 이산수학 및 응용, 임은기 번역(한티미디어)
4) 전산수학, 김대수 (생능)
