이산수학
수학적 모델링
문제를 해결하기 위해 수학적 구조에 매핑시켜 체계적으로 해결하는 방법론
1. 주어진 문제의 상황과 배경 파악
2. 문제와 수학적 구조와의 매핑
3. 수학적 기초 개념을 이용한 문제 해결
논리와 명제
명제 논리(prpositional logic): 주어와 술어를 구분하지 않고 전체를 하나의 식으로 처리.
술어 논리(predicate logic): 주어와 술어로 구분하여 참 또는 거짓에 관한 법칙을 다룬다.
명제(proposition): 참이나 거짓을 객관적이고 명확하게 구분할 수 있는 문장이나 수학적 식. 통상 영문 소문자 p, q, r 등으로 표기.
진리값(truth value): 명제가 참 또는 거짓을 가질 때 그 값, T, F
단순 명제(simple proposition): 하나의 문장이나 식으로 구성되어 있는 명제
합성명제(composition proposition): 여러개의 단순 명제들이 논리 연산자들로 연결되어 만들어진 명제
진리표(truth table): 단계적으로 단순 명제들이 가질 수 있는경우의 진리 값을 표시한 뒤 복합 명제들을 연산한다.
n개의 단순 명제가 있을 때 진리값의 경우의 수는
논리 연산자(logical operators)
| 이름 | 기호 | 의미 |
|---|---|---|
| 부정(negation) | ~ | NOT |
| 논리곱(conjunction) | ∧ | AND |
| 논리합(disjunction) | ∨ | OR |
| 배타적 논리합(exclusive or) | ⊕ | Exclusive OR |
| 조건(implication) | → | If ... then |
| 쌍방 조건(Biconditional Proposition) | ↔ | If and only if |
함축(implication)
조건 이라고도 한다. 임의의 명제 p, q에 대하여, 'p이면 q이다.'
- p가 참이고 q가 거짓일 때만 F 이다.
필요 조건이 참이면 그냥 참. 필요 조건이 거짓일 때 충분 조건이 거짓이라면 상관 없다. 하지만 참이라면 논리적 오류가 생겨 거짓.
쌍방 조건
모두 참이거나 거짓일 때 참이다.
- p이면 q이고, q이면 p이다.
- p if and only if q
- p는 q의 필요 충분 조건이다.
- p is necessary and sufficient for q
논리 연산자 우선순위
~ ∧ ∨ → ↔
명제 p→q에 대한 역, 이, 대우
q→p 역(converse)
~p→~q 이(inverse)
~q→~p 대우(contrapositive)
| p | q | ~p | ~q | p→q | q→P | ~p→~q | ~q→~p |
|---|---|---|---|---|---|---|---|
| T | T | F | F | T | T | T | T |
| T | F | F | T | F | T | T | F |
| F | T | T | F | T | F | F | T |
| F | F | T | T | T | T | T | T |
항진명제(Tautology): 합성 명제에서 그 명제를 구성하는 단순 명제들의 진리값에 상관 없이 항상 참의 값을 가질 때 항진 명제라 한다.
모순명제(Contradiction): 명제를 구성하는 단순 명제들의 진리값에 관계 없이 항상 거짓(F)의 값을 가지는 명제
논리적 동치(logical equivalence): 두 개의 명제 p,q의 쌍방조건 p↔q가 항진 명제이면 두 명제 p,q는 논리적 동치라 하고 p⇔q , p≡q 로 표시한다. 즉 명제 p와 q는 같은 논리 값을 가진다는 의미.
논리적 동치 관계의 기본 법칙
멱등 법칙(idempotent law)
- p∨p ⇔ p
- p∧p⇔p
항등 법칙(identity law)
- p∨T⇔T
- p∨F⇔p
- p∧T⇔p
- p∧F⇔f
부정 법칙(negation law)
- ~T⇔F
- ~F⇔T
- p∨~p⇔ T
- p∧~p⇔ F
이중 부정 법칙(double negation law)
- ~(~p)⇔p
교환 법칙(commutative law)
- p∨q⇔q∨p
- p∧p⇔q∧p
- p↔q⇔q↔p
결합 법칙(associative law)
- (p∨q)∨r⇔p∨(q∨r)
- (p∧q)∧r⇔ p∧(q∧r)
분배 법칙(distributive law)
- p∨(q∧r)⇔(p∨q)∧(p∨r)
- p∧(q∨r)⇔(p∧q)v(p∧r)
흡수 법칙(absorption law)
- p∨(p∧q)⇔p
- p∧(p∨q)⇔P
드 모르간 법칙(De Morgan's law)
- ~(p∨q)⇔~p∧~q
- ~(p∧q)⇔~p∨~q
조건 법칙
- p→q⇔~p∨q
대우 법칙
- p→q⇔~q→~p
추론(argument): 주어진 명제가 참인 것을 바탕으로 새로운 명제가 참이 되는 것을 유도해내는 방법
전제(premise): 추론에 주어진 명제들. p1,p2,...,pn
결론(conclusion): 새로이 유도된 명제
유효 추론(valid argument): 전제가 참이고 결론도 참인 추론
허위 추론(fallacious argument): 전제가 참이고 결론이 거짓인 추론
추론 법칙
긍정 법칙(modus ponens)
- p, p→q ∴q
부정 법칙(modus tollens)
- ~q, p→q ∴~p
조건 삼단 법칙(hypothetical)
- p→q, q→r ∴p→r
선언 삼단 법칙(disjunctive dilemma)
- p∨q, ~p ∴q
양도 법칙(constructive dilemma)
- (p→q)∧(r→s), p∨r ∴q∨s
대전제)네가 만일 정직하면 세인이 증오할 것이고, 만일 부정직하면 신이 증오할 것이다.
(소전제)너는 정직하든가 또는 부정직하다.
(결론)그러므로 너는 세인의 증오를 받든지 신의 증오를 받는다.
파괴적 법칙(destructive dilemma)
- (p→q)∧(r→s), ~q∨~s ∴~p∨~r
선접 법칙(disjunctive addition)
- p ∴p∨q
분리 법칙(simplication)
- p∧q ∴p
연접 법칙(conjunction)
- p, q ∴p∧q
명제 술어(propositional predicate): 변수에 따라 달라지는 명제 P(x)
술어 논리(predicate logic): 명제 술어에 대한 논리
술어 한정자(predicate quantifier): 변수의 범위를 한정 시키는 것
∀: 모든 것에 대하여(for all)
∃: 존재한다.(there exist)
전체 한정자(universal quantifier)
-
모든 x에 대하여 P(x)는 참이다.
-
P(x)에 대한 전체 한정자는 로 나타낸다.
-
가 참이 되기 위한 필요충분조건
- x의 전체집합 U에 대하여 성립해야한다.
-
부정: P(x)가 성립하지 않는 x가 존재한다. ~⇔~
존재 한정자(existential quantifier)
- 어떤 x에 대하여 P(x)가 참인 x가 존재한다.
- P(x)에 대한 존재 한정자.
- 가 참이 되기 위한 필요충분조건
- 전체집합 U안에 P(x)를 만족시키는 x가 적어도 한 개 존재해야 한다.
- 부정: '모든 x는 P(x)가 성립하지 않는다.'
~⇔~
