5. 이산수학

관계의 성질 - 

추이관계 : (a,b) ∈ R이고 (b,c) ∈ R이면 (a,c) ∈ R이 성립하는 경우

(a,b)(b,c) → (a,c) O

(a,b) 다음에 (b,(아무 값)) 이 존재하지 않을 때는 추이관계가 성립한다.

R2 = {(1,2),(2,3),(1,3),(2,1),(1,1)}

(1,2)(2,1) → (1,1) O

(1,2)(2,3) → (1,3) O

(2,3) → X O

(1,3) → X O

(2,1)(1,2) → (2,2) 가 존재하지 않으므로 X

(2,1)(1,3) → (2,3) O

(2,1)(1,1) → (2,1) O

(1,1)(1,2) → (1,2) O

(1,1)(1,3) → (1,3) O

2. 관계의 표현

[그림]

3. 관계의 성질

동치관계 : 반사관계, 대칭관계, 추이관계가 성립될 때

부분순서(반순서)관계 : 반사관계, 반대칭관계, 추이관계가 성립될 때

합성관계 : 주어진 두 관계로부터 새로운 관계를 이끌어내는것

[그림]

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

S={(4,2),(2,5),(3,1),(1,3)}

1. R*S = {(1,5),(3,2),(2,5)}

2. S*R = {(4,2),(3,2),(1,4)}

3. R*(S*R) = {(3,2)}

4. (R*S)*R = {(3,5)}

4. 함수

집합 A를 함수 f의 정의역

[그림]

집합 B를  함수 f의 공변혁

[그림]

f(A)를 함수 f의 치역

[그림]

함수의 조건

[그림]

[그림]

함수의 종류

1. 단사함수

서로다른 원소에 대응되는 함수

2. 전사함수

치역과 공변혁이 일치하는 함수(공변혁에 남는게 존재해서는 안된다)

3. 전단사 함수

일대일 대응, 전사이면서 단사함수인것

4. 상수 함수

정의역의 모든 원소가 공변역의 원소 하나만 가리킬때 (n:1)

5. 항등 함수

자기가 자기 자신에게 연결될 때