술어논리

개념

• 전칭
  • ∀p(x), q(x)
  • 모든 p(x)에 대하여 q(x)를 만족하면 참
  • Ex) 모든 자연수는 0이상이다 : ∀ x는 자연수, x ≥ 0
• 특칭
  • ∃p(x), q(x)
  • 어떤 p(x)에 대하여 q(x)를 만족하면 참
  • ∃ 다음에 !를 붙이면 (∃!) 참인 것이 단 1개만 존재한다는 의미
• 쌍대원리
  • ∀ ↔ ∃
• 괴델의 완전성 정리
  • 술어논리의 법칙들은 증명이 가능하다
• 논리는 수학에 언어를 제공한다.
  • ∃k₀ ∈ A, ∀a ∈ A, k₀ ≤ a : k₀는 a의 최소값
  • ∃p ∈ ℕ, ∀a, b ∈ ℕ, p = ab ⇒ a=1 ∨ b=1 : p는 1이거나 소수이다.
  • ∀a, b ∈ A, a = b : a는 한 원소로 된 집합이다. (또는 공집합)
  • ∀ε > 0, ∃N ∈ ℕ, n ≥ N ⇒ | a_n – a | < ε : lim_n→∞ a_n = a

논리식

• ¬∀p(x), q(x) ≡ ∃p(x), ¬q(x)
  • ¬∃p(x), q(x) ≡ ∀p(x), ¬q(x)
• ∀p(x), q(x) ≡ ∀x, p(x) → q(x)
  • ∃p(x), q(x) ≡ ∃x, p(x) ∧ q(x)
• ∀p(x), q(x) ∧ ∀p(x), r(x) ≡ ∀p(x), q(x) ∧ r(x)
• ∀x, p(x) ∧ ∀x, q(x) ≡ ∀x, p(x) ∧ q(x)
  • ∃x, p(x) ∨ ∃x, q(x) ≡ ∃x, p(x) ∨ q(x)
• ∀x, ∀y, p(x, y) ≡ ∀y, ∀x, p(x, y)
  • ∃x, ∃y, p(x, y) ≡ ∃y, ∃x, p(x, y)