목차
명제와 진릿값
- 명제(Proposition): 객관적인 기준으로 진릿값을 구분할 수 있는 문장이나 수식: 영어 소문자 p, q, r …로 표현
- 진릿값(Truth Value): 참(true: T)이나 거짓(false: F)을 가리키는 값
논리연산자
- 부정(NOT): ~p 또는 ¬p
| p | ~p |
|---|---|
| T | F |
| F | T |
- 논리곱(AND): p ∧ q
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
- 논리합(OR): p ∨ q
| p | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
- 배차적 논리합(Exclusive OR: XOR): p ⊕ q ≡ (~p ∧ q) ∨ (p ∧ ~q)
| p | q | p ⊕ q |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
합성명제
합성명제(Compound Proposition): 하나 이상의 명제들이 논리연산자에 의해 결합된 명제
- 항진명제(Tautology): T
- 합성명제를 구성하는 단일명제의 진리값에 상관없이 합성명제의 진릿값이 항상 참(T)인 명제
- 모순명제(Contradiction): F
- 합성명제를 구성하는 단일명제의 진리값에 상관없이 합성명제의 진릿값이 항상 거짓(F)인 명제
- 사건명제(Contigency)
- 항진명제도 모순명제도 아닌 합성명제
조건명제
- 조건명제(Conditional Proposition) / 함축(Implication): p → q ≡ ~p ∨ q
| p | q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
- 쌍방조건명제(Biconditional Proposition): p ↔ q ≡ (p → q) ∧ (q → p) ≡ ~(p ⊕ q)
| p | q | p ↔ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
- 역(Converse), 이(Inverse), 대우(Contraposition)
| p | q | p → q 조건명제 | q → p 역 | ~p → ~q 이 | ~q → ~p ≡ p → q 대우 |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | F | T | T | F |
| F | T | F | F | F | T |
| F | F | T | T | T | T |
논리연산자의 우선순위
| 우선순위 | 연산자 |
|---|---|
| 1 | () |
| 2 | ~ |
| 3 | ∧ |
| 4 | ∨ |
| 5 | ⊕ |
| 6 | → |
| 7 | ↔ |
논리적 동치
논리적 동치(Logically Equivalence): P ≡ Q
- 두 개의 합성명제 P와 Q의 진릿값이 서로 같은 경우
| 법칙 | 논리적 동치 | |
|---|---|---|
| 항등법칙(Identity Law) | p ∧ T ≡ p | p ∨ F ≡ p |
| 지배법칙(Domination Law) | p ∨ T ≡ T | p ∧ F ≡ F |
| 부정법칙(Negation Law) | p ∧ ~p ≡ F | p ∨ ~p ≡ T |
| 이중 부정법칙(Double Negation Law) | ~(~p) ≡ p | |
| 멱등법칙(Idempotent Law) | p ∧ p ≡ p | p ∨ p ≡ p |
| 교환법칙(Commutative Law) | p ∧ q ≡ 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) ∨ (p ∧ r) |
| 드모르간의 법칙(De Morgan's Law) | ~(p ∧ q) ≡ ~p ∨ ~q | ~(p ∨ q) ≡ ~p ∧ ~q |
| 흡수법칙(Absorption Law) | p ∧ (p ∨ q) ≡ p | p ∨ (p ∧ q) ≡ p |
| 함축법칙(Implication Law) | p → q ≡ ~p ∨ q | |
명제함수
- 명제함수(Propositional Function): P(x)
- 논의영역이 주어진 변수 x를 포함하여 진릿값을 판별할 수 있는 문장이나 수식
- 논의영역(Domain of Discourse): D
- 명제함수에 포함된 변수 x의 범위이나 값
한정자
- 전체/전칭한정자(Universal Quantifier): ∀
- 논의영역의 모든 값 ex) 논의영역 D에 속하는 모든 x에 대한 명제 P(x): ∀xP(x)
- 존재한정자(Existential Quantifier): ∃
- 논의영역 중 어떤 값 ex) 논의영역 D에 속하는 원소 중 어떤 x에 대한 명제 P(x): ∃xP(x)
한정자와 논리 연산자
| ∀ | ∃ |
|---|---|
| ∀x(P(x) ∧ Q(x)) ≡ ∀xP(x) ∧ ∀xQ(x) | ∃x(P(x) ∧ Q(x)) ≡ ∃xP(x) ∧ ∃xQ(x) |
| ∀x(P(x) ∨ Q(x)) ≡ ∀xP(x) ∨ ∀xQ(x) | ∃x(P(x) ∨ Q(x)) ≡ ∃xP(x) ∨ ∃xQ(x) |
| ~(∀xP(x)) ≡ ∃x(~P(x)) | ~(∃xP(x)) ≡ ∀x(~P(x)) |
추론
- 추론(Inference)/논증(Argument)
- 참(T)인 명제를 근거로 하여 다른 명제가 참(T)임을 유도하는 방식
- 가정/전제(Hypothesis), 결론(Conclusion)
- 가정/전제: 결론의 근거가 되는 최종 결론을 제외한 명제, 진릿값이 참(T)으로 간주되는 명제
- 결론: 주어진 전제에 의해 유도된 명제
유효추론과 허위추론
- 유효(정당한)추론
- 주어진 전제를 이용해 유도된 결론이 정확한 추론, 전제가 참(T)일 때 결론이 모두 참(T)인 추론
- 허위(부당한)추론
- 주어진 전제를 이용해 유도된 결론이 틀린 추론, 전제가 참(T)인 경우, 결론이 거짓(F)인 경우가 하나라도 있는 추론
- 유효추론 예: 전제가 모두 참(T)인 경우에 결론인 q의 진릿값 역시 참(T)이므로 이 추론은 유효추론이다.
| 전제 | 결론 | 전제 |
|---|---|---|
| p | q | p → q |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
- 허위추론 예: 전제가 모두 참(T)인 경우에 결론인 p의 진리값 중 거짓(F)이 존재하므로 이 추론은 허위추론이다.
| 결론 | 전제 | 전제 |
|---|---|---|
| p | q | p → q |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
논리적 추론법칙
| 법칙 이름 | 추론법칙 | 항진명제 |
|---|---|---|
| 논리곱 (Conjunction) | p q ∴ p ∧ q | None |
| 선언적 부가 (Disjunctive Addition) | p ∴ p ∨ q | p → (p ∨ q) |
| 단순화 (Simplication) | p ∧ q ∴ p(or q) | (p ∧ q) → p(or q) |
| 긍정논법 (Modus Ponens) | p p → q ∴ q | {p ∧ (p → q)} → q |
| 부정논법 (Modus Tollens) | ~p p → q ∴ p ∨ q | {~p ∧ (p → q)} → ~p |
| 선언적 삼단논법 / 소거 (Disjunctive Syllogism) | p ∨ q ~q ∴ p | {(p ∨ q) ∧ ~q} → p |
| 가설적 삼단논법 / 추이 (Hypothetical Syllogism) | p → q q → r ∴ p → r | {(p → q) ∧ (q → r)} → (p → r) |