[이산수학] KOCW 가천대학교 김철연 교수님 강의 3주차 정리

Terminology

1. Theorem (정리) : 참이라는 것을 보일 수 있는 진술, 증명의 대상
2. Axiom (공리) : 우리가 진실이라고 가정하는 진술, 증명의 대상이 아님
3. Lemma (보조정리) : 참이라는 것을 보일 수 있는 진술 중 중요도가 낮은 것, theorem 증명 간소화하기 위해 중간에 미리 정리
4. Corollary : 참이라는 것을 보일 수 있는 진술 중 증명이 필요 없는 것, theroem을 보면 자동적으로 알 수 있는 것
5. Conjecture : 아직 증명되지 않은 것 중 참이라고 가정하는 진술

→ Axiom - Theorem(중요), Lemma, Corollary - Conjecture

Methods of Proving Theorems

1. Direct Proof (직접 증명법) : 조건 명제 만듦, 가정 명제를 ‘참’이라 가정, 결론이 참이 나와서 증명
2. Proof by contraposition (대우증명법) : 조건명제와 대우는 동치
3. Proof by contradiction (귀류법) : 조건명제가 아닐 경우 not p가 어떤 경우에도 거짓임을 밝혀내면 됨, 명제의 부정이 참임을 가정하여 증명

ch.2 Basic Structures

Set (집합)

• set은 unordered, 순서X, 중복X (Bag은 중복O)
• N (natural number, 자연수)
• Z (모든 정수)
• Z+ (양의 정수)
• Q (유리수) : 분수로 표현 가능(무리수는 분수로 표현X)
• R (real number, 실수)

Equality

• 두 집합이 같은 원소를 가진다
• 원소나열법, 조건제시법

Subset (부분집합)

• A의 모든 원소가 B의 원소라면 A는 B의 부분집합이다.
• A (subset 부분집합) B (superset 초집합)
• A는 A의 부분집합이다. (자기자신을 빼면 진부분집합 proper subset)
• 공집합(empty set)은 모든 집합의 부분집합이다.

Finite and Infinite

• n개의 원소가 있다면 유한집합(finite set)
• cardinality |A| = 원소의 개수가 몇개인지
• 무한집합(infinite set)

Power Set(멱집합)

• P(S) : S의 모든 부분집합

Cartesian Products (곱집합)

• Ordered n-tuple : 집합 n개로부터 가져온 원소를 나열한 것
• 집합 n개에 대한 cartesian products는 A1 x A2 x A3 … x An = 모든 가능한 조합(각각의 집합에서 원소 하나씩)

각종 집합

• union (합집합)
• intersection (교집합)
• disjoint (서로소집합)
• difference (차집합)
• complement (여집합 → 전체집합 언급 universal set)

Function (함수)

• f: A→ B A(domain 정의역) B(codomain 공역)
• f(a)=b a(preimage) b(image)
• 하나의 x 값에 대해 하나의 y 값이 존재해야 함, A의 모든 원소는 B의 원소 중 하나와 짝을 이루어야 함, B 집합은 상관 없음
• one-to-one function : 일대일대응(b에 중복 X)
• onto function : 정의역과 공역이 동일
• bijection function(=one-to-one correspondence) : one-to-one이면서 onto, A과 B의 수가 같고 각각이 연결되어야 함
• Inverse function : 역함수
• composition of functions (합성함수) : (f.g)(a)=f(g(a))