수학의신이상엽/ 명제와 논리

명제와 증명

명제와 연결사

  • 명제: 참, 거짓이 분명히 판단되는 문장
    • 단순 명제: p, q, r
    • 합성 명제: 몇 개의 단순 명제들이 연결사에 의해 결합된 명제
  • 연결사: 두 명제 p와 q에 대해
    • 부정
      • \sim p
      • not p
    • 논리곱
      • p \wedge q
      • p and q
    • 논리합
      • p \vee q
      • p or q
    • 조건
      • p \to q
      • if p then q
    • 쌍조건
      • p \leftrightarrow q
      • p if and only if q
      • 줄여서 iff 라고도 함

진리표

  • 진리표란 명제의 진리값을 표로 나타낸 것
p q

\sim p

p \wedge q

p \vee q

p \to q

p \leftrightarrow q

T T F T T T T
T F F F T F F
F T T F T T F
F F T F F T T
  • 진리집합
    • 해당 명제가 참이 되도록 하는 모든 원소들의 집합
    • 집합이므로 대문자로 표기
  • 명제 P가 거짓이라는 것은 진리집합에 해당 하는 원소들이 없다는 의미이고, P는 공집합이라는 의미가 된다.
  • p \to q 는 p가 q의 부분집합인지를 묻는 것과 같다. 만일 p가 거짓이면 p가 공집합이 되는 것이므로, p가 거짓일 때는 q와 관계 없이 참이 된다.
  • 진리표에 의해 다음 명제들은 참이다.
    • p \to q \equiv \sim p \vee q
    • \sim (p \wedge q) \equiv \sim p \vee \sim q (드모르간의 법칙)
    • p \to q \equiv \sim q \to \sim p (대우 법칙)
    • (p \vee q) \vee r \equiv p \vee (q \vee r) (결합 법칙)
    • p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r) (분배 법칙)
    • 위 명제들의 and를 or로, or를 and로 동시에 바꾸면 결과는 같다.

연역적 추론

  • 연역적 추론이란 이미 알고 있는 판단을 근거로 새로운 판단을 유도하는 것

명제 함수

명제함수와 한정기호

  • 명제함수: 변수 x가 결정되어야만 참, 거짓이 판단되는 문장
    • p(x), q(x)...
  • 한정기호: 전칭기호와 존재기호
    • \forall : for every
    • \exists : for some

명제의 부정

  • 두 명제 p와 q에 대해, x의 모집단은 건드리지 않도록 하며 다음의 4가지 원리를 모두 적용한다.
    • \forall \rightleftharpoons \exists
    • \wedge \rightleftharpoons \vee
    • p \rightleftharpoons \sim p
    • < \rightleftharpoons \geq

함의와 동치

항진명제와 모순명제

  • 항진명제: 모든 논리적 가능성의 진리값들이 참인 명제. t
  • 모순명제: 모든 논리적 가능성의 진리값들이 거짓인 명제. c
  • 항진명제와 모순명제의 성질
    • 임의의 명제 p에 대하여
      • p \vee \sim p \equiv t
      • p \wedge \sim p \equiv c
      • t \vee p \equiv t
      • c \vee p \equiv p
      • t \wedge p \equiv p
      • c \wedge p \equiv c
  • 항진명제, 모순명제의 정의에 따라 아래 명제는 참이다.
    • \sim p \to c \equiv p
    • (p \to q) \wedge (q \to r) \to (p \to r) \equiv t
      • p이면 q이고, q이면 r이면, p이면 r이다.

함의와 동치

  • 함의: 항진인 조건문 p \to p 를 논리적 함의라 하고, p \Rightarrow p 로 나타내며, p는 q의 충분조건, q는 p의 필요조건이라 한다.
  • 동치: 항진인 쌍조건문 p \leftrightarrow p 를 동치라 하고, p \Leftrightarrow p 로 나타내며 p와 q는 서로의 필요충분조건이라 한다.
[ssba]

The author

지성을 추구하는 사람/ suyeongpark@abyne.com

댓글 남기기

This site uses Akismet to reduce spam. Learn how your comment data is processed.