命題論理
Contents
命題論理
命題論理 (英：propositional logic) とは、命題を一つの記号に置き換えて単純化し、推論形式を用いて結論を問う論理体系のこと。
命題とは
命題 (英：proposition) とは、真が偽かを問える平叙文。真を $\top$ 、偽を $\bot$ で表す。命題は分解でき、それ以上分解できない命題を原始命題 (英：atomic proposition) と呼ぶ。また原始命題を組み合わせて構成される命題を複合命題 (英：compound proposition) と呼ぶ。命題論理では、原始命題を形式的に命題変項 (英：propositional variable) で表す。
- 原始命題の例：
「本日は晴天である」 - 複合命題の例：
「本日は晴天か曇りである」
命題変項の記号：
命題変項は慣習的にアルファベットで表される。
- 原始命題：
$p,q,r,\ldots$ - 複合命題および命題一般：
$P,Q,R,\ldots$
論理式
論理式 (英：logical formula) とは、定められた形式に従って論理式と論理結合子 (英：logical connective) を組み合わせたもの。整式 (英：well-formed formula) とも呼ばれる。論理結合子とは、論理式の定義に沿って、論理式と結合する記号のこと。命題論理では、$\lnot \land \lor \rArr \lrArr$ を用いる。
論理式の定義：
命題論理では次の定義によって再帰的に論理式と論理結合子が定められる。
- 命題変項は論理式である。
- $P$ が論理式であるとき、$\lnot P$ は論理式である。
- $P, Q$ が論理式であるとき、$P\land Q, ~P\lor Q, ~P\rArr Q, ~P\lrArr Q$ は論理式である。
- 以上のものだけが論理式である。
補助記号：
補助記号 (英：auxiliary symbol) とは、読解を容易にするために補助的に用いる記号。命題論理では $, . ()$ を用いる。例えば $P\lor (Q\land R)$ のように使用される。
論理結合子の結合の強さ：
補助記号を用いて論理式の読解が容易になる一方、論理式の構成が複雑になると、かえって読解が困難になる。そのため論理結合子には結合の強さが定義されている。
\[ \def\arraystretch{1.5} \begin{array}{ccc} \text{強} & \lrarr & \text{弱} \\ \hline \lnot & \land & \lArr \\ & \lor & \lrArr \\ \end{array} \]
論理結合子の結合の強さによって、例えば次のように論理式は簡略化される。
\[ \begin{gathered} (P\land (Q\lor R))\lrArr ((P\land Q)\lor (P\land R)) \cr \downarrow \cr P\land (Q\lor R)\lrArr (P\land Q)\lor (P\land R) \end{gathered} \]
形式的定義
論理体系の形式化は複数あるが、ここではウカシェヴィチ (波：Jan Łukasiewicz) の形式化を記す。この形式化では論理結合子は $\rArr \lnot$ のみ使用する。$\land \lor \lrArr$ はこの形式化の定義から導かれる。
公理系：
\[ \begin{aligned} (A1) &: P\rArr(Q\rArr P)\cr (A2) &: (P\rArr(Q\rArr R))\rArr((P\rArr Q)\rArr (P\rArr R)) \cr (A3) &: (\lnot P\rArr\lnot Q)\rArr(Q\rArr P) \end{aligned} \]
推論規則：
\[ \cfrac{\begin{matrix} P & P\rArr Q \end{matrix}}{\begin{matrix} Q \end{matrix}}\text{Modus Ponens}~(\text{MP}) \]
$\boldsymbol{\land\lor\lrArr}$ の定義：
ウカシェヴィチの形式化では $\land\lor\lrArr$ は公理化されていない。当形式化の文脈では $\land\lor\lrArr$ は省略記号であり、次式のように導かれる。なお、$\lrArr$ と区別するために $\equiv$ を同値記号として用いる。
\[ \begin{aligned} P\lor Q &\equiv \lnot P\rArr Q \cr P\land Q &\equiv \lnot(\lnot P\lor \lnot Q) \cr P\lrArr Q &\equiv (P\rArr Q)\land (Q\rArr P) \end{aligned} \]
論理式の意味
論理式の形式だけでは論理式は意味を持たない。命題論理では各論理式に次の意味を持たせている。
否定：
否定 (英：negation) の命題「命題 $P$ でない」は $\lnot P$ とで表される。
\[ \def\arraystretch{1.5} \begin{array}{c:c} P & \lnot P \\ \hline \top & \bot \\ \bot & \top \end{array} \]
連言：
連言 (英：conjunction) の命題、「命題 $P$ かつ命題 $Q$」は、$P\land Q$ で表される。
\[ \def\arraystretch{1.5} \begin{array}{cc:c} P & Q & P\land Q \\ \hline \top & \top & \top \\ \top & \bot & \bot \\ \bot & \top & \bot \\ \bot & \bot & \bot \end{array} \]
選言：
選言 (英：disjunction) の命題、「命題 $P$ または命題 $Q$」は、$P\lor Q$ で表される。
\[ \def\arraystretch{1.5} \begin{array}{cc:c} P & Q & P\lor Q \\ \hline \top & \top & \top \\ \top & \bot & \top \\ \bot & \top & \top \\ \bot & \bot & \bot \end{array} \]
含意：
含意 (英：implication) の命題、「命題 $P$ (が真) ならば命題 $Q$ (が真)」は、$P\rArr Q$ で表される。
\[ \def\arraystretch{1.5} \begin{array}{cc:c} P & Q & P\rArr Q \\ \hline \top & \top & \top \\ \top & \bot & \bot \\ \bot & \top & \top \\ \bot & \bot & \top \end{array} \]
同値：
同値 (英：equivalence) の命題、「命題 $p$ (が真)、かつそのときに限り命題 $q$ (が真)」は、$p\lrArr q$ で表される。
\[ \def\arraystretch{1.5} \begin{array}{cc:c} P & Q & P\lrArr Q \\ \hline \top & \top & \top \\ \top & \bot & \bot \\ \bot & \top & \bot \\ \bot & \bot & \top \end{array} \]
論理式の性質
同一律：
\[ \begin{aligned} & P\lor P\lor\cdots\lor P \equiv P \cr & P\land P\land\cdots\land P \equiv P \cr & P\lrArr P \end{aligned} \]
交換律：
\[ \begin{aligned} & P\lor Q \equiv Q\lor P \cr & P\land Q \equiv Q\land P \cr \end{aligned} \]
結合律：
\[ \begin{aligned} (P\lor Q) \lor R &\equiv P\lor (Q\lor R) \cr (P\land Q) \land R &\equiv P\land (Q\land R) \end{aligned} \]
分配律：
\[ \begin{aligned} & P\lor (Q\land R) \equiv (P\lor Q)\land (P\lor R) \cr & P\land (Q\lor R) \equiv (P\land Q)\lor (P\land Q) \end{aligned} \]
ド・モルガンの定理：
\[ \begin{aligned} & \lnot (P\land Q) \equiv \lnot P\lor \lnot Q \cr & \lnot (P\lor Q) \equiv \lnot P\land \lnot Q \end{aligned} \]
吸収律：
\[ \begin{aligned} & P\land (P\lor Q) \equiv P \cr & P\lor (P\land Q) \equiv P \end{aligned} \]
二重否定：
\[ \lnot\lnot P \equiv P \]
排中律：
\[ P\lor \lnot P \equiv \top \]
矛盾律：
\[ P\land \lnot P \equiv \bot \]
真偽の性質：
\[ \begin{aligned} \top\land P &\equiv P \cr \top\lor P &\equiv \top \cr \bot\land P &\equiv \bot \cr \bot\lor P &\equiv P \cr \end{aligned} \]
含意の除去：
\[ \begin{aligned} (P\rArr Q) &\lrArr \lnot P\lor Q \cr &\lrArr \lnot(P\land\lnot Q) \end{aligned} \]
同値の除去：
\[ \begin{aligned} P\lrArr Q &\equiv (P\rArr Q)\land (Q\rArr P) \cr &\equiv (P\land Q)\lor (\lnot P\land\lnot Q) \end{aligned} \]
推移律：
\[ \begin{aligned} (P\rArr Q)\land (Q\rArr R) &\rArr (P\rArr R) \cr (P\lrArr Q)\land (Q\lrArr R) &\rArr (P\lrArr R) \end{aligned} \]
背理法：
\[ (P\rArr \lnot P) \equiv \lnot P \]
同値の性質：
\[ \begin{aligned} (P\lrArr Q) &\equiv (\lnot P\lrArr\lnot Q) \cr \lnot(P\lrArr Q) &\equiv (P\lrArr\lnot Q) \end{aligned} \]
含意の性質：
\[ \begin{aligned} (\top\rArr P) &\equiv P \cr (\bot\rArr P) &\equiv \top \cr (P\rArr\top) &\equiv \top \cr (P\rArr\bot) &\equiv \lnot P \end{aligned} \]
論理式の分類
恒真式：
恒真式 (英：toutology) とは、常に真となる論理式のこと。恒真式である場合、その論理式は証明可能である。論理式 $P$ が証明可能であるとき $\vDash P$ と表される。
矛盾式：
矛盾式 (英：inconsistent formula) とは、常に偽となる論理式のこと。
充足可能式：
充足可能式 (英：satisfiable formula) とは、矛盾式でない論理式のこと。充足可能式を真にする真理値の割り当てをモデル (英：model) といい、モデルを求める問題を充足問題と呼ぶ。また充足可能式であるかどうかを判定する問題を決定問題 (英：decision problem) と呼ぶ。