고교 과정과 안겹치는 내용 위주로 이산수학을 정리해보도록 하겠습니다.
성균관대학교 2021 여름학기 GEDB007_42 수업을 바탕으로 작성되었습니다.
Functions
고교 과정과 똑같다. 다음의 용어만 알고가자.
•
onto (전사) : 공역 = 치역
•
one-to-one (일대일 함수) : ㅇㅇ
•
bijection (일대일 대응) : ㅇㅇ
Sequence
고교 과정과 똑같다. 다음의 용어만 알고가자.
•
Finite Sequence : 유한 수열
•
Infinite Sequence : 무한 수열
String
의 문자열은 에 속하는 원소들의 유한 수열을 말한다.
는 Null String이라 한다.
는 를 포함한 의 문자열의 집합을 말한다.
문자열의 연산
•
Length : 문자열의 길이
•
Concatenation : 이어 붙이는거
•
Substring : 부분 문자열
•
Reverse : 뒤집는거, 윗첨자 R로 씀
Relation
에서 로의 이항 관계 은 의 부분 집합이다.
, is Related to 라고 한다.
함수는 하나에 하나만이 존재하는 특수한 관계로 정의할 수 있음
Relation의 특성
•
Reflexive (반사 관계) : 모든 에 대해 일때 Reflexive 하다고 한다.
•
Symmetric (대칭 관계) : , 일때 Symmetric 하다고 한다.
•
Antisymmetric (반대칭 관계) : , 일때, 이면 Antisymmetric 하다고 한다.
* Symmetric 하면서 동시에 Antisymmetric 할 수도 있다!! 뭔가 이름만 보면 안될 것 같은데...
•
Transitive (추이 관계) : 이고, 일때, 이면 Transitive하다고 한다. 로도 나타낼 수 있겠지?
•
Partial Order : 이 Reflexive, Antisymmetric and Transitive 하다고 하면 Partial Order가 있다고 한다.
•
Equivalance Relation (동치 관계) : 이 Reflexive, Symmetric and Transitive 하다고 하면 Partial Order가 있다고 한다.
◦
한 Partition내의 두 원소 의 관계 은 Reflexive, Symmetric, Transitive하다.