[이산수학]명제 논리(Propositional Logic) - 2

부당한 논증(1)

전제가 모두 참일 때, 결론이 참이 아닌 경우가 존재한다.

부당한 논증(2)

Invalid argument(fallacy)
전제가 모두 참일 때, 결론이 참이 아닌 경우가 존재한다.

대표적인 부당한 논증의 유형

•전건 부정의 오류(the fallacy of denying the antecedent)
𝐴 → 𝐵, ¬𝐴 ⊭¬𝐵

•후건 긍정의 오류(the fallacy of affirming the consequent)
𝐴 → 𝐵, 𝐵 ⊭ 𝐴

•논리합 긍정의 오류(the fallacy of affirming a disjunction)
𝐴 ∨ 𝐵, 𝐴 ⊭ ¬𝐵

증명(Proof)

진리표의 문제점
• 단순 명제가 n개 이면, 진리표의 행은 2^n 개로 지수적으로 증가된다.

자연 연역법(Natural Deduction)

증명 기법 중의 하나
공리는 사용하지 않고, 추론 규칙(10 inference rules) 사용

가정을 쓰는 규칙
• $➝_{I}$
• $¬_{I}$
• $⋁_{E}$



가정을 안 쓰는 규칙
• $∧_{I}$
• $∧_{E}$
• $⋁_{I}$
• $➝_{E}$
• $↔︎_{I}$
• $↔︎_{E}$
• $¬_{E}$



추론 규칙의 표현 및 의미
선을 중심으로 위에는 전제, 아래는 결론은 표시
$\frac{A➝B, A} {B}$

의미로는 타당한 논증이다.

즉, $A➝B, A ⊨ B$

가정을 안 쓰는 규칙

논리곱 도입($∧_{I}$)

$\frac{A,\ B} {A\ ∧\ B}$ 또는 $\frac{A,\ B} {B\ ∧\ A}$



논리곱 제거($∧_{E}$)

$\frac{A\ ∧\ B} {A}$ 또는 $\frac{A\ ∧\ B} {B}$



논리합 도입($⋁_{I}$)

$\frac{A} {A\ ⋁\ B}$ 또는 $\frac{B} {A\ ⋁\ B}$



조건 제거($➝_{E}$)
$\frac{A,\ A ➝ B} {B}$



쌍 조건 도입($↔︎_{I}$)

$\frac{A ➝ B,\ B ➝ A} {A\ ↔︎ \ B}$

쌍 조건 제거($↔︎_{E}$)

$\frac{A\ ↔︎ \ B} {A\ ➝\ B}$ 또는 $\frac{A\ ↔︎ \ B} {B\ ➝\ A}$



부정 제거($¬_{E}$)

$\frac{¬¬A} {A}$

가정을 쓰는 규칙

조건 연산자 도입($➝_{I}$)

$\frac{A\ ⊨\ B} {A\ ➝\ B}$

▶︎ 여기서 $A$는 가정이다.

부정 연산자 도입($¬_{I}$)

$\frac{A\ ⊨\ B,\ A\ ⊨\ ¬B} {¬A}$

▶︎ 여기서 $A$는 가정이다.

모순에 의한 증명(proof by contradiction)
• 결론을 부정한 후에 모순을 유도하기 때문이다.

논리합 기호 제거($⋁_{E}$)
proof by cases라고도 불림

$\frac{A\ ⋁\ B,\ A'\ ⊢\ C,\ B'\ ⊨\ C} {C}$

▶︎ 여기서 $A',\ B'$는 가정이다.

논리적 동치 증명

논리적 동치
• $A\ ≡\ B$ iff $\ ⊨A\ ↔︎\ B$

논리적 동치 증명은 양 방향을 모두 증명해야 한다.
• $\ ⊨A\ ↔︎\ B$ $\ ≡\ \ ⊨(A➝B)∧(B➝A)$

증명 시 주의 사항

전제의 모순 여부를 확인

Inconsistent set of premises
• 전제가 모순이면 어떤 것도 증명할 수 있다.
• 따라서, 증명 전에는 전제의 일관성을 먼저 체크 해야 한다.