# 述語論理 ## 定義 述語論理(predicate logic)は、変数を含み変数への値の割り当てによって真偽が決まる文である述語(predicate)を、全称量化子 ∀(for all、常に真)と存在量化子 ∃(there exists、時々真)で修飾して主張を組み立てる体系である。量化子の変数が動く集合を論議領域(domain of discourse)と呼び、全変数が同一集合を動く場合は明示を省略する慣習がある。複数の量化子を含む主張では、量化子の順序を入れ替えると意味が一般に変わる(例: 「全員に共通の1つの夢がある」∃d∀a: H(a,d) と「各人がそれぞれの夢を持つ」∀a∃d: H(a,d) は別の主張)。否定を量化子の外側から内側へ移動させると量化子の種類が反転する(NOT(∀x: P(x)) は ∃x: NOT(P(x)) と同値、NOT(∃x: P(x)) は ∀x: NOT(P(x)) と同値)。述語論理式の妥当性は、論議領域・変数の値・述語の解釈のすべてに対して常に真になることと定義され、妥当でないことを示すには反例モデル(counter model)を1つ構成すれば十分である一方、妥当性そのものを示すには全解釈に対する論証が必要という非対称性がある。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 3 Logical Formulas]]) ## 横断的知見 （この concept は本 ingest が初出のため、複数ソースの突き合わせによる横断的知見はまだない。他章・他ソースが述語論理・量化子に触れた際にここへ追記する。） ## 未解決の問い - 述語論理の妥当性証明で使われる「反例モデル1個で非妥当性を示せるが、妥当性の肯定には全解釈への言及が必要」という非対称性は、他の証明技法(帰納法など、[[命題論理]]と同じ書籍の他章)とどう対応づけられるか。 - 量化子の順序入れ替えが意味を変える具体例(ゴールドバッハの予想の量化子順序を入れ替えると偽になる例)は、第3章では直感的な説明にとどまる。形式的な非妥当性の証明(反例モデルの構成)との関係を他ソースで補強できるか。 ## 関連 - 概念: [[命題論理]] / [[充足可能性問題(SAT)]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 3 Logical Formulas]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 3.