# 命題論理 ## 定義 命題論理(propositional logic)は、真(T)または偽(F)のいずれか一方の値を取る文である命題(proposition)を、NOT・AND・OR・XOR・IMPLIES・IFF といった論理結合子(logical connective)で組み合わせ、その真偽を真理値表(truth table)によって厳密に定める体系である。日常英語の「または」「ならば」が持つ曖昧さを排除する目的で導入され、OR は両方が真でも真になる包含的論理和として定義される点や、IMPLIES は仮説(if 部)が偽であれば結論の真偽によらず全体が真になる点が、日常語の直観とは異なる特徴として強調される。任意の命題論理式は真理値表からの機械的な読み取りによって、あるいは交換律・結合律・冪等律・De Morgan の法則などの同値公理による代数的変換によって、選言標準形(disjunctive normal form, DNF)・連言標準形(conjunctive normal form, CNF)のいずれにも変換できる。妥当性(validity、変数の値によらず常に真)と充足可能性(satisfiability、ある割り当てで真にできる)は、F が妥当 iff NOT(F) が充足不能、という関係で相互に還元できる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 3 Logical Formulas]]) ## 横断的知見 （この concept は本 ingest が初出のため、複数ソースの突き合わせによる横断的知見はまだない。他章・他ソースが命題論理に触れた際にここへ追記する。） ## 未解決の問い - 命題論理の同値公理群(Theorem 3.4.4)による DNF/CNF 変換と、真理値表による変換は、一般にどちらがどの程度効率的か。第3章の記述では「真理値表法と同程度の手間がかかりうる」とされるが、具体的な計算量の比較は書かれていない。 - 命題論理の同値公理の完全性(Theorem 3.4.5)は、述語論理に拡張したときにどのような形の完全性定理として現れるか([[述語論理]]の妥当性の議論との接続)。 ## 関連 - 概念: [[述語論理]] / [[充足可能性問題(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.