Module #2: Basic Proof Methods

1. Predicate Logic

P(x) : x is greater than 3

• 명제함수(propositional function) P에서의 x의 값
  주어 : x
  술어(predicate) : is greater than 3

• 규칙

  • 함수는 대문자, 변수는 소문자
  • 함수 그 자체(P)는 명제가 아님. 변수가 들어가야 명제 (P(3), P(x))
  • 변수는 1개 이상 가능 P(x, y, z)

• Universes of Discourse : 정의역

---

한정기호

전칭 한정기호(∀) : 정의역에 속하는 모든 x값에 대하여 P(x)이다.

• P(x)가 거짓이 되는 원소를 ∀xP(x)의 반례라고 부른다

존재 한정기호(∃) : 정의역에 속하는 적어도 하나의 값 x에 대하여 P(x)이다.

유일 한정기호(∃!) : 유일하게 한 개만 존재할 때 사용한다.

문장	T	F
∀xP(x)	모든 x에 대하여 P(x)가 참이다.	P(x)가 거짓이 되는 x가 존재한다.
∃xP(x)	P(x)가 참이 되는 x가 존재한다.	모든 x에 대하여 P(x)가 거짓이다.

• 한정 기호의 순서에 따라 뜻이 달라진다

표현	의미
∀x∀yP(x,y)	모든 x, y의 쌍에 대하여 P(x, y)가 참이다.
∀x∃yP(x,y)	모든 x에 대하여 P(x, y)가 참이 되는 y가 있다.
∃x∀yP(x,y)	어떤 x에 대하여 모든 y에 대해 P(x, y)가 참이다.
∃x∃yP(x,y)	P(x, y)가 참이 되는 x, y의 쌍이 있다.

• 한정기호는 모든 논리 연산자보다 상위의 우선순위를 갖는다

  ∃xQ(x) ∨ P(x) = (∃xQ(x)) ∨ P(x)

한정 기호에 대한 드 모르간 법칙

~∀xP(x) = ∃x~P(x)
~∃xP(x) = ∀x~P(x)

---

구속 변수와 자유 변수

구속 변수 : 한정 기호가 적용된 변수

자유 변수 : 한정 기호가 적용되어 있지 않거나, 값이 할당되어 있지 않은 변수

ex) ∀xP(x,y)에서 x는 구속 변수, y는 자유 변수이다.

---

2. Proof

Proof Terminology

• Theroem(정리) : 참이라고 증명된 하나의 진술
• Axiom(공리), hypotheses(가설), premises(전제) : 우리가 추론하는 구조를 정의하는 가정들
• Rules of inference(추론 규칙) : 가설에서 결론을 도출하는 논리적으로 타당한 추론 패턴
• Lemma(보조정리) : 주요 정리를 증명하기 위한 중간 단계로 사용되는 작은 정리
• Corollary(따름정리) : 증명된 정리로부터 직접적으로 귀결될 수 있는 정리
• Conjecture(가설) : 어떤 부분적 증거에 근거해 참이라고 주장되는 문장.
• Theory(이론) : 주어진 공리 집합에서 증명할 수 있는 모든 정리들의 모음

Inference Rules 추론 규칙

• 전제가 모두 참이면 결론도 참이다.

Rule of Addtion (∨ 도입)
1. p
__
2. p ∨ q

Rule of Simplification (∧ 제거)
1. p ∧ q
__
2. p

Rule of Conjunction (∧ 도입)
1. p
2. q
__
3. p ∧ q

Rule of modus ponens (the mode of affirming, → 제거)
1. p
2. p → q
__
3. q

Rule of modus tollens (the mode of denying, 후건 부정)
1. ~q
2. p → q
__
3. ~p

Rule of hypothetical syllogism (가설적 삼단논법)
1. p → q
2. q → r
__
3. p → r

Rule of disjunctive syllogism (선언적 삼단논법, ∨ 제거)
1. p ∨ q
2. ~p
__
3. q

Inference Rules for Quantifiers 양화사의 추론규칙

Universal instantiation (∀ 제거)
1. ∀x P(x)
__
2. P(o) // 임의의 o 가정

Universal generalization (∀ 도입)
1. P(g) // 임의의 g 가정
__
2. ∀x P(x)

Existential instantiation (∃ 제거)
1. ∃x P(x)
__
2. P(c) // 임의의 c 가정

Existential generalization (∃ 도입)
1. P(o) // 임의의 존재하는 o 가정
__
2. ∃x P(x)

증명의 오류들

• Affirming the conclusion : 결론 긍정의 오류. 결론이 참일지라도 전제가 거짓일 수 있다.
• Denying the hypothesiss : 가설 부정의 오류. p → q 일때, p가 거짓이라고해서 q가 거짓인 것은 아니다.
• Circular Reasoning : 순환 논증. 결론을 뒷받침하기 위해 결론을 다시 사용하는 오류

증명의 방법들 (p → q)

• Direct Proof 직접 증명 : p가 참일 때, q가 참임을 증명
• Indirect Proof 간접 증명(대우에 의한 증명) : ~q를 가정하고, ~p임을 증명
• Vacuous Proof 공허한 증명 : ~p를 증명
• Trivial Proof 자명한 증명 : q를 증명
• Proof by Contradiction 모순에 의한 증명
  • ~p → (q ∧ ~q) 이 참임을 보여 p가 참임을 증명
• Proving Existential
  • Existence Proof 존재 증명 : ∃x P(x)일 때, P를 만족하는 원소를 구함. → 생산적 증명
  • 비생산적 증명 : 존재 정량화의 부정을 모순법을 사용해 증명
• Proof by cases 경우에 의한 증명 : 모든 경우의 수를 고려해 증명