정의, 진리표, 논리적 동치, 손 계산 문제
이산수학 (DM)
명제논리와 증명에서 출발해 집합·함수·관계, 귀납과 점화식, 경우의 수, 정수론, 그래프와 트리, 이산확률까지 다룹니다.
증명에 쓰는 논리와 셀 수 있는 대상을 다룹니다. 컴퓨터 과학과 선형대수, 확률의 바탕이 되는 언어를 정의에서 시작해 손으로 계산할 수 있는 데까지 익힙니다.
- 각 단원 끝의 확인 문제를 모두 맞히면 단원이 완료됩니다. 잠금은 없으므로 어느 단원부터 읽어도 됩니다.
- 위젯은 먼저 결과를 예측하고 확인하는 방식이 기본입니다. 위젯 위의 단추로 자유 조작으로 바꿀 수 있습니다.
- 증명과 서술형 문제는 풀이를 연 뒤 스스로 채점합니다.
| 부 | 단원 | 수 | 진도 |
|---|---|---|---|
| 1부. 논리와 증명 | DM.1–DM.3 | 3 | |
| 2부. 집합, 함수, 귀납 | DM.4–DM.6 | 3 | |
| 3부. 세기 | DM.7–DM.9 | 3 | |
| 4부. 정수와 그래프 | DM.10–DM.12 | 3 | |
| 5부. 확률 | DM.13 | 1 |
1부. 논리와 증명
- DM.1
- DM.2
- 술어, 전칭·존재 한정기호, 한정기호의 부정과 순서, 영역에 따른 진릿값
- DM.3
- 직접 증명, 대우 증명, 귀류법, 경우 나누기, 존재 증명과 반례, 필요충분조건
2부. 집합, 함수, 귀납
- DM.4
- 원소와 부분집합, 합집합·교집합·여집합·차집합, 집합의 항등식, 멱집합, 곱집합, 원소의 개수
- DM.5
- 함수, 단사·전사·전단사, 합성과 역함수, 관계와 그 성질, 동치관계와 분할, 부분순서
- DM.6
- 귀납법의 구조, 합 공식과 부등식의 증명, 강한 귀납법, 재귀적 정의, 정렬 원리
3부. 세기
- DM.7
- 합의 법칙과 곱의 법칙, 순열과 조합, 중복 허용, 이항정리와 파스칼 삼각형, 별과 막대
- DM.8
- 비둘기집 원리와 일반화, 포함배제 원리, 교란순열, 전사함수의 수
- DM.9
- 점화식으로 세기, 선형 동차 점화식과 특성방정식, 중근, 비동차 점화식, 분할정복 점화식
4부. 정수와 그래프
- DM.10
- 나눗셈 정리, 최대공약수와 유클리드 호제법, 베주 항등식, 합동, 모듈러 역원, 페르마 소정리, RSA의 원리
- DM.11
- 그래프의 정의, 차수와 악수 정리, 경로와 연결성, 오일러 회로, 이분 그래프, 인접행렬과 경로의 수, 평면 그래프
- DM.12
- 트리의 동치 조건, 뿌리 트리와 이진 트리, 신장 트리와 최소 신장 트리(크루스칼), 케일리 공식
5부. 확률
- DM.13
- 표본공간과 사건, 같은 가능성의 확률, 조건부확률과 독립, 베이즈 정리, 확률변수와 기댓값, 기댓값의 선형성, 분산