본문으로 건너뛰기

Ch. 1 The Foundations: Logic and Proofs

Discrete Mathematics and Its Applications · Kenneth H. Rosen · Ch. 1

Intuition

논리는 복잡한 일상 언어에서 모호함을 제거하여 참과 거짓을 가려내는 정교한 규칙 체계이며, 증명은 이러한 규칙을 이용해 지식의 확실성을 구축하는 과정이다.

One-liner​

명제와 술어의 정의로부터 시작하여 한정자와 추론 규칙을 학습하고, 이를 바탕으로 수학적 문장을 증명하는 다양한 방법론을 제시한다.

Prerequisites​

  • 기초 대수학 (변수, 함수, 부등식에 대한 이해)
  • 고교 수학 수준의 집합 표기 및 기초 명제 개념

Goals​

  • 명제 논리와 술어 논리의 차이를 이해하고 기호화할 수 있다.
  • 타당한 추론 규칙을 적용하여 논리적 결론을 도출할 수 있다.
  • 직접 증명, 대우 증명, 귀류법 등 적절한 증명 전략을 선택할 수 있다.
  • 존재 증명 및 유일성 증명의 개념을 파악한다.

Core Concepts​

1.1 Propositional Logic (명제 논리)​

Definition

Proposition (명제): 참(True) 또는 거짓(False) 중 하나로 판별되는 선언적 문장이다. (p.1)

  • Negation (부정, ¬p\neg p): 명제의 진리값을 반전시킨다. (p.3)
  • Connectives (연결사):
    • Conjunction (논리곱, p∧qp \wedge q): 둘 다 참일 때 참. (p.4)
    • Disjunction (논리합, p∨qp \vee q): 적어도 하나가 참일 때 참. (p.4)
    • Conditional Statement (조건문, p→qp \rightarrow q): pp가 참이고 qq가 거짓일 때만 거짓. (p.6)
    • Biconditional Statement (쌍조건문, p↔qp \leftrightarrow q): 진리값이 일치할 때만 참. (p.9)

1.2 Propositional Equivalences (명제 동치)​

Definition

Tautology (항진명제): 구성 명제의 진리값과 관계없이 항상 참인 명제이다. (p.21)

Definition

Contradiction (모순명제): 항상 거짓인 명제이다. (p.21)

Definition

Contingency (우연명제): 참일 수도 있고 거짓일 수도 있는 명제이다. (p.21)

  • Logical Equivalence (p≡qp \equiv q): p↔qp \leftrightarrow q가 항진명제인 경우 두 명제는 논리적으로 동치이다. (p.22)

1.3 Predicates and Quantifiers (술어와 한정자)​

  • Predicate (술어): 변수를 포함하여 대상의 성질을 서술하는 문장 성분이다. (p.31)
  • Universal Quantifier (전칭 한정자, ∀\forall): 도메인의 모든 xx에 대해 성립함을 뜻한다. (p.34)
  • Existential Quantifier (존재 한정자, ∃\exists): 조건을 만족하는 xx가 적어도 하나 존재함을 뜻한다. (p.36)

1.4 Nested Quantifiers (중첩 한정자)​

  • 한 문장 안에 여러 한정자가 중첩된 형태이다. (p.51)
  • Order Matters: ∀x∃yP(x,y)\forall x \exists y P(x, y)와 ∃y∀xP(x,y)\exists y \forall x P(x, y)는 의미가 다르다. 후자는 모든 xx에 공통으로 적용되는 단 하나의 yy가 존재해야 한다. (p.53)

1.5 Rules of Inference (추론 규칙)​

Definition

Valid Argument (타당한 논증): 모든 전제가 참일 때 결론이 반드시 참인 논리적 구조이다. (p.64)

  • Modus Ponens (긍정 논법): pp와 p→qp \rightarrow q로부터 qq를 도출한다. (p.65)
  • Modus Tollens (부정 논법): ¬q\neg q와 p→qp \rightarrow q로부터 ¬p\neg p를 도출한다. (p.66)
  • Hypothetical Syllogism (가언 삼단논법): p→qp \rightarrow q와 q→rq \rightarrow r로부터 p→rp \rightarrow r을 도출한다. (p.66)
  • Disjunctive Syllogism (선언 삼단논법): p∨qp \vee q와 ¬p\neg p로부터 qq를 도출한다. (p.66)
  • Resolution (해소법): p∨qp \vee q와 ¬p∨r\neg p \vee r로부터 q∨rq \vee r을 도출한다. (p.68)

1.6 Introduction to Proofs (증명 도입)​

  • Direct Proof (직접 증명): 가정 pp가 참임을 이용해 결론 qq를 연역적으로 도출한다. (p.76)
  • Proof by Contraposition (대우 증명): ¬q→¬p\neg q \rightarrow \neg p가 참임을 보여 본래 명제를 증명한다. (p.77)
  • Proof by Contradiction (귀류법): 명제의 부정을 가정했을 때 모순이 발생함을 보인다. (p.80)

1.7 Proof Methods and Strategy (증명법과 전략)​

  • Proof by Cases (경우 나누기 증명): 모든 가능한 경우를 전수 조사하여 각각의 타당성을 입증한다. (p.86)
  • Existence Proof (존재 증명): 구체적인 예시를 찾는 Constructive 방식과 존재성만 입증하는 Nonconstructive 방식이 있다. (p.91)
  • Uniqueness Proof (유일성 증명): 대상의 존재성과 함께, 다른 모든 대상은 해당 성질을 갖지 않음을 증명한다. (p.92)
  • Tilings: 체커보드 타일링 문제를 통해 증명 전략의 시각화와 불변량 개념을 학습한다. (p.97)

Notation​

기호의미
p≡qp \equiv q두 명제 p,qp, q가 논리적으로 동치임
∃!xP(x)\exists! x P(x)P(x)P(x)를 만족하는 xx가 유일하게 존재함
WLOGWLOG일반성을 잃지 않고 (Without Loss of Generality)
∴\therefore그러므로

Key Theorems & Formulas​

De Morgan's Laws (Propositional)

조건: p,qp, q는 임의의 명제

결론:

\neg(p \wedge q) \equiv \neg p \vee \neg q \\ \neg(p \vee q) \equiv \neg p \wedge \neg q $$ (p.22)
De Morgan's Laws for Quantifiers

결론:

\neg \forall x P(x) \equiv \exists x \neg P(x) \\ \neg \exists x P(x) \equiv \forall x \neg P(x) $$ (p.41)

Intuitions​

  • Resolution (해소법)의 직관: pp이거나 qq인데, pp가 아니라면(¬p\neg p) 반드시 rr이어야 하는 상황에서 결국 qq 또는 rr 중 하나는 참일 수밖에 없다. (p.68)
  • Existence Proof (Nonconstructive): 산길에 발자국이 있다면, 누구인지는 몰라도 누군가 지나갔음은 확실한 것과 같다. 대상을 특정하지 않고도 존재를 확신할 수 있다. (p.91)

Worked Examples​

Example 1: 대우 증명 (p.78)​

문제: 정수 nn에 대하여 3n+23n+2가 홀수이면 nn은 홀수임을 증명하라.

핵심 단계:

  1. 대우 명제 설정: "nn이 짝수이면 3n+23n+2는 짝수이다."
  2. n=2kn = 2k 대입: 3(2k)+2=6k+2=2(3k+1)3(2k)+2 = 6k+2 = 2(3k+1).
  3. 결론: 결과가 2×(정수)2 \times (\text{정수}) 형식이므로 짝수이다.

요점: 결론의 부정이 다루기 쉬운 형태(n=2kn=2k)일 때 대우 증명이 효과적이다.

Example 2: 비구성적 존재 증명 (p.91)​

문제: xyx^y가 유리수가 되는 무리수 x,yx, y가 존재함을 보여라.

핵심 단계:

  1. x=2,y=2x = \sqrt{2}, y = \sqrt{2}를 고려한다. 무리수임은 이미 알려져 있다.
  2. 만약 22\sqrt{2}^{\sqrt{2}}가 유리수라면 증명 종료.
  3. 만약 무리수라면, x=22,y=2x = \sqrt{2}^{\sqrt{2}}, y = \sqrt{2}로 둔다.
  4. xy=(22)2=22=2x^y = (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^2 = 2 (유리수).

요점: 두 케이스 중 어느 것이 정답인지 몰라도, 결과적으로 성질을 만족하는 쌍이 '있음'은 확실하다.

Common Pitfalls​

Pitfall

Affirming the Conclusion (결론 긍정의 오류): p→qp \rightarrow q와 qq가 참이라고 해서 pp가 참이라고 결론짓는 것은 논리적 오류이다. "천재는 악필이다"와 "내가 악필이다"로부터 "나는 천재다"를 유도할 수 없는 것과 같다. (p.69)

Pitfall

Denying the Hypothesis (가정 부정의 오류): p→qp \rightarrow q와 ¬p\neg p가 참일 때 ¬q\neg q를 도출하는 행위이다. (p.69)

Connections​

  • 선행 개념: 고교 수학의 집합과 명제.
  • 후속 개념: Ch. 4 수학적 귀납법, Ch. 11 부울 대수.
  • 응용 분야: 시스템 명세의 일관성 검토, 자동 정리 증명(Automated Theorem Proving), Prolog 언어.

Critical Notes​

교재가 강조하는 것

  • 논리 연산자를 이용한 영어 문장의 엄밀한 기호화. (p.11)
  • 추론 규칙의 타당성을 진리표와 항진명제로 연결하는 기초 체력. (p.64)

실제로 중요한 것

  • 중첩 한정자의 순서 해석 능력은 이후 미적분학의 극한(ϵ−δ\epsilon-\delta)이나 함수의 연속성을 이해할 때 결정적이다. (p.55)
  • 다양한 증명법 중 어떤 것이 문제 해결에 가장 효율적인지 판단하는 전략적 사고. (p.93)

교재가 생략하거나 얼버무리는 것

  • 증명 과정에서 사용되는 수많은 산술적 성질들(교환법칙, 분배법칙 등)을 공리(Axiom) 수준에서 하나하나 나열하기보다 직관적으로 사용하며 넘어가는 경향이 있다. (p.75)

Open Questions​

이해하지 못한 것

  • Nonconstructive Proof: 대상을 보여주지 않고도 존재를 증명한다는 것이 논리적으로는 완벽하지만 직관적으로는 여전히 낯설게 느껴질 수 있음. (p.91)

더 알고 싶은 것

  • Gödel's Incompleteness Theorem: 본 장에서 다룬 추론 체계로 증명할 수 없는 참인 명제가 존재할 수 있는지에 대한 철학적·수학적 한계. (p.14)
  • Satisfiability (SAT): 주어진 논리식을 참으로 만드는 변수 할당을 찾는 문제의 계산 복잡도와 P vs NP 문제. (p.27)