🤣

[Discrete Mathematics] 3. Functions, Sequences, Relations

고교 과정과 안겹치는 내용 위주로 이산수학을 정리해보도록 하겠습니다.
성균관대학교 2021 여름학기 GEDB007_42 수업을 바탕으로 작성되었습니다.

Functions

고교 과정과 똑같다. 다음의 용어만 알고가자.
•
onto (전사) : 공역 = 치역
•
one-to-one (일대일 함수) : ㅇㅇ
•
bijection (일대일 대응) : ㅇㅇ

Sequence

고교 과정과 똑같다. 다음의 용어만 알고가자.
•
Finite Sequence : 유한 수열
•
Infinite Sequence : 무한 수열

String

XX의 문자열은 XX에 속하는 원소들의 유한 수열을 말한다.
λ\lambda는 Null String이라 한다.
X∗X^*는 λ\lambda를 포함한 XX의 문자열의 집합을 말한다.

문자열의 연산

•
Length : 문자열의 길이
•
Concatenation : 이어 붙이는거
•
Substring : 부분 문자열
•
Reverse : 뒤집는거, αR\alpha^R 윗첨자 R로 씀

Relation

XX에서 YY로의 이항 관계 RR은 X×YX \times Y의 부분 집합이다.
(x,y)∈R=:xRy(x,y) \in R =: xRy , xx is Related to yy 라고 한다.
함수는 xx 하나에 yy 하나만이 존재하는 특수한 관계로 정의할 수 있음

Relation의 특성

•
Reflexive (반사 관계) : 모든 xx에 대해 (x,x)∈R(x,x) \in R 일때 Reflexive 하다고 한다.
•
Symmetric (대칭 관계) : (x,y)∈R(x,y) \in R, (y,x)∈R(y,x) \in R 일때 Symmetric 하다고 한다.
•
Antisymmetric (반대칭 관계) : (x,y)∈R(x,y) \in R, (y,x)∈R(y,x) \in R 일때, x=yx=y 이면 Antisymmetric 하다고 한다.
* Symmetric 하면서 동시에 Antisymmetric 할 수도 있다!! 뭔가 이름만 보면 안될 것 같은데...
•
Transitive (추이 관계) : (x,y)∈R(x,y) \in R 이고, (y,z)∈R(y,z) \in R 일때, (x,z)∈R(x,z) \in R 이면 Transitive하다고 한다. ∀x∀y∀z,[(x,y)∈R∧(y,z)∈R]→[(x,z)∈R]\forall x \forall y \forall z , [(x,y) \in R \wedge (y,z) \in R] \rightarrow [(x,z) \in R] 로도 나타낼 수 있겠지?
•
Partial Order : RR이 Reflexive, Antisymmetric and Transitive 하다고 하면 Partial Order가 있다고 한다.
•
Equivalance Relation (동치 관계) : RR이 Reflexive, Symmetric and Transitive 하다고 하면 Partial Order가 있다고 한다.
◦
한 Partition내의 두 원소 x,yx, y 의 관계 RR은 Reflexive, Symmetric, Transitive하다.