이산수학 논리 정리

1. 명제와 진릿값

명제(Proposition): 객관적인 기준으로 진릿값을 구분할 수 있는 문장이나 수식: 영어 소문자 p, q, r …로 표현
진릿값(Truth Value): 참(true: T)이나 거짓(false: F)을 가리키는 값

2. 논리연산자

부정(NOT): ~p 또는 ¬p

p ~p

T F

F T

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

3. 합성명제

합성명제(Compound Proposition): 하나 이상의 명제들이 논리연산자에 의해 결합된 명제

항진명제(Tautology), T: 합성명제를 구성하는 단일명제의 진리값에 상관없이 합성명제의 진릿값이 항상 참(T)인 명제
모순명제(Contradiction), F: 합성명제를 구성하는 단일명제의 진리값에 상관없이 합성명제의 진릿값이 항상 거짓(F)인 명제
사건명제(Contigency): 항진명제도 모순명제도 아닌 합성명제

4. 조건명제

조건명제(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

5. 논리연산자의 우선순위

우선순위	연산자
1	()
2	~
3	∧
4	∨
5	⊕
6	→
7	↔

6. 논리적 동치

논리적 동치(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

7. 명제함수

명제함수(Propositional Function), P(x): 논의영역이 주어진 변수 x를 포함하여 진릿값을 판별할 수 있는 문장이나 수식
논의영역(Domain of Discourse), D: 명제함수에 포함된 변수 x의 범위이나 값

8. 한정자

전체/전칭한정자(Universal Quantifier), ∀: 논의영역의 모든 값
- 논의영역 D에 속하는 모든 x에 대한 명제 P(x): ∀xP(x)
존재한정자(Existential Quantifier), ∃: 논의영역 중 어떤 값
- 논의영역 D에 속하는 원소 중 어떤 x에 대한 명제 P(x): ∃xP(x)

9. 한정자와 논리 연산자

∀	∃
∀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))

10. 추론

추론(Inference)/논증(Argument): 참(T)인 명제를 근거로 하여 다른 명제가 참(T)임을 유도하는 방식
가정/전제(Hypothesis), 결론(Conclusion)
- 가정/전제: 결론의 근거가 되는 최종 결론을 제외한 명제, 진릿값이 참(T)으로 간주되는 명제
- 결론: 주어진 전제에 의해 유도된 명제

11. 유효추론과 허위추론

유효(정당한)추론
- 주어진 전제를 이용해 유도된 결론이 정확한 추론
- 전제가 참(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

12. 논리적 추론법칙

법칙 이름	추론법칙	항진명제
논리곱 (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)

DISCRETE MATHEMATICS

[DISCRETE MATHEMATICS] 이산수학 논리