강좌 소개
- kocw 가천대학교 김철연 교수님 2014-1 이산수학
- 이산 : 떨어져 있는, discrete(↔continuous)
- 0과 1 사이의 실수는 무한개, 정수는 없음 → 이산수학은 마치 정수(0,1) 같이 서로 끊어지는 개념
- 소프트웨어는 수학에 근간을 두고 있음
- discrete math는 출발점이자 도착점임. (c언어, 컴퓨터구조)
- 고등학생 때 배운 집합과 명제가 기초지식(50% 이상은 고등학생 때 배운 내용을 영어로 다시 배우는 것 뿐)
- 가장 중요한 것은 로직
ch.1 Foundation part 1
Proposition(명제)
- proposition = declarative sentence (선언적 문장)
- True or false, but not both (참 또는 거짓)
- natural language를 simple하게 바꿈 → propositional variable (명제 변수, p,q,r,s,… 하나가 하나의 명제를 의미함)
Logical operator (논리연산자)
- operand (피연산자) → p, q, r…
- unary operator(피연산자 1개) / binary operator(피연산자 2개)
- Negation : ㄱp
- Conjunction(And) : p^q (p and q)
- Disjunction(or) : pvq
- Exclusive(배타적) : p x q
- Truth table(진리표)
p q p ^ q p v q p x q
| T |
T |
T |
T |
F |
| T |
F |
F |
T |
T |
| F |
T |
F |
T |
T |
| F |
F |
F |
F |
F |
Conditional Satements
- If p, then q (p → q)
- p = hypothesis 가정 (antecedent)
- q = conclusion 결론 (consequence)
- converse (역) = q → p
- inverse(이) = ㄱp→ㄱq
- contrapositive(대우) = ㄱq→ㄱp (truth table이 p→q와 같음!! equivalent 동치)
- hypothesis가 false 이면 결론이 뭐든간에 true임!!
p q p → q ㄱp v q
| T |
T |
T |
T |
| T |
F |
F |
F |
| F |
T |
T |
T |
| F |
F |
T |
T |
- Logical equivalence(동치) p → q = ㄱq→ㄱp = ㄱp v q
Biconditional Statement
- p if and only if p (p↔q, p iff q)
p q p ↔ q
Logical equivalence(동치)
- compound proposition 2개 이상의 변수가 연산자에 의해 엮여 있는 것
- 동치 : 어떤 상황에서도 값이 동일해야 함
- 작대기 3개로 표현( =)
- p → q = ㄱq→ㄱp = ㄱp v q
- pv(p^q)=p, p^(pvq)=p
Consistence of Rules
- 최소한 어느 한 경우에는 동시에 T가 되는 경우
p q pvq p^q p→q (pvq)^ㄱp^(p→q) (p^q)^ㄱp^(p→q)
| T |
T |
T |
T |
T |
F |
F |
| T |
F |
T |
F |
F |
F |
F |
| F |
T |
T |
F |
T |
T |
F |
| F |
F |
F |
F |
T |
F |
F |
Tautology and Contradiction
- Tautology : 항상 참 pVㄱp
- Contradiction : 항상 거짓 p^ㄱ
- Contingency : 항상 참이거나 거짓이지 않은 평범
Predicates(술어논리)
- 서술어 부분만, T F는 주어나 목적어 자리가 채워졌을 때 결정됨
- P(x) ← x에 들어가는 건 proposition