이산수학 - 정수론, 나눗셈, 베주의 항등식, 유클리드 호제법, 나머지 연산, 소수와 소인수 분해, RSA 암호
1. 나눗셈 a는 정수이고 b는 양의 정수라 할 때, 다음을 만족하는 유일한 정수 q, r이 존재한다. \[ a = bq + r \quad \text{단,} \quad 0 \leq r 이 정리는 어떤 정수 \( a \)를 양의 정수 \( b \)로 나누면, 몫 \( q \)와 나머지 \( r \)가 존재하며, 나머지 \( r \)는 0 이상 \( b \) 미만의 범위에 속한다는 것을 의미한다. 예를 들어, \( a = 17 \)이고 \( b = 5 \)인 경우를 생각해보자. \( a \)를 \( b \)로 나누면 다음과 같이 나타낼 수 있다.\[17 = 5 \cdot 3 + 2\]여기서 몫 \( q = 3 \)이고 나머지 \( r = 2 \)이다. 또한, 나머지 \( r \)는 0 이상 5 미만의 ..
2024. 5. 15.
이산수학 - 그래프, 트레일, 경로, 이분 그래프, 완전 이분 그래프, 정규 그래프, 오일러 투어, 해밀턴 경로
1. 기본사항 다음 그림처럼 점과 두 점을 서로 연결하는 선으로 이루어진 도형을 그래프라 한다. 2. 주요 용어 그래프 \( G \)는 꼭지점(vertex)들과 변(edge)들로 구성된다. 이를 수식으로 나타내면 \( G = (V, E) \)이다. 여기서 \( V = \{ v | v \text{는 꼭지점} \} \)이고, \( E = \{ e | e \text{는 변} \} \)이다.변은 두 꼭지점을 연결한다. 즉, 변에 의해 발생(incident)된다고 한다.연결된 두 꼭지점은 서로 인접(adjacent)한다고 한다.병렬 변(parallel edge)은 두 꼭지점을 연결하는 변이 복수개 있을 때를 의미한다.루프(loop)는 동일한 꼭지점을 연결하는 변을 뜻한다.고립된 꼭지점(isolated ..
2024. 5. 15.
이산수학 - 함수, 함수의 상등, 전사함수, 단사함수, 합성함수, 계승함수, 바닥함수, 천장함수, 나머지 함수
1. 기본사항 집합 \(X\)와 \(Y\)가 주어졌을 때, \(X\)에서 \(Y\)로의 함수 \(f\)는 다음 조건을 만족하는 관계이다.모든 \(x \in X\)에 대해, 오직 하나의 \(y \in Y\)가 존재하여 \((x, y) \in f\)를 만족한다. 이를 수식으로 표현하면 다음과 같다.\[ \forall x \in X, \exists ! y \in Y \quad \text{such that} \quad (x, y) \in f \]즉, \(X\)의 임의의 원소 \(x\)에 대해, \((x, y) \in f\)를 만족하는 \(y\)가 \(Y\)에 오직 하나만 존재한다.이를 함수 \(f\)로 표현하면 다음과 같이 쓸 수 있다.\[ f : X \to Y \]그리고, \(f(x) = y\)라는 관계를 만..
2024. 5. 15.
이산수학 - 관계, 관계의 표현, 관계의 성질, 관계의 종류, 반사적, 대칭적, 추이적, 동치관계
1. 기본사항관계란 객체들 간의 연관성을 포현하는 구조이다. 이산수학에서 관계는 주로 두 집합에 속하는 서로 다른 두 원소 사이의 연관성을 표현하는 데 사용된다. 두 집합 X와 Y에 대하여 곱집합 X x Y의 부분집합 R을 X에서 Y로의 관계라고 말한다. 집합 \(A\)와 \(B\)의 곱집합(Cartesian Product) \(A \times B\)는 \(A\)의 원소와 \(B\)의 원소의 모든 순서쌍(ordered pair)들의 집합을 의미합니다. 즉,\[ A \times B = \{ (a, b) \mid a \in A, b \in B \} \] 집합 \( X \)에서 집합 \( Y \)로의 (이항)관계 \( R \)은 \( X \times Y \)의 부분집합이다.- 이항관계 \( R \)에 대..
2024. 5. 15.
