#2: 命題論理
執筆中
この記事は書きかけです…命題記号
定義 2.1 古典論理
- 真または偽という性質をどちらか片方のみを持つ条件 $P$ を 命題 (proposition) という.
- 命題 $P$ の 否定 (negation) $\lnot P$ はまた命題である.
- 命題 $P, Q$ の 論理和 (logical disjunction) $P\lor Q$ はまた命題である.
- 命題 $P, Q$ の 論理積 (logical implication) $P\land Q$ はまた命題である.
このとき, $\lnot P,\,P\lor Q,\,P\land Q$ の真偽を次に定める (以降, 真を $T$, 偽を $F$ で表す).
| $P$ | $\lnot P$ |
|---|---|
| $T$ | $F$ |
| $F$ | $T$ |
| $P$ | $Q$ | $P\lor Q$ | $P\land Q$ |
|---|---|---|---|
| $T$ | $T$ | $T$ | $T$ |
| $T$ | $F$ | $T$ | $F$ |
| $F$ | $T$ | $T$ | $F$ |
| $F$ | $F$ | $F$ | $F$ |
論理包含・同値
定義 2.2 論理包含
- 命題 $P, Q$ において, $(\lnot P)\lor Q$ を 包含, 含意, あるいは 内含, (logical conjunction) といい, $P\Longrightarrow Q$, または $Q\Longleftarrow P$ で表す.
- このとき, $P$ は $Q$ の 十分条件 (sufficient condition), $Q$ は $P$ の 必要条件 (necessary condition) という.
- $P\Longrightarrow Q$ かつ $Q\Longleftarrow P$ のとき, $P$ と $Q$ は 同値 (equivalent), あるいは $P$ は $Q$ の 必要十分条件 (necessary and sufficient condition) であるといい, $P\Longleftrightarrow Q$, あるいは $P=Q$ で表す.
$P\Longrightarrow Q,\,P=Q$ の真偽をまとめると以下の通りである.
| $P$ | $Q$ | $P\Longrightarrow Q$ | $P=Q$ |
|---|---|---|---|
| $T$ | $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ | $F$ |
| $F$ | $T$ | $T$ | $F$ |
| $F$ | $F$ | $T$ | $T$ |
演算の優先順位
複数の演算子による命題の場合, 演算の優先順によって解釈が異なる場合は原則括弧で囲む. ただし, 文脈によって $\Longrightarrow, \Longleftarrow, \Longleftrightarrow$ は $\lnot, \lor, \land$ よりも暗黙的に優先順位が高いことも多い.定理2.3 論理命題の諸性質1
以下は常に真である.- $\lnot\lnot P = P.$ (二重否定)
- $A\lor P = P,\,P\land P = P.$ (べき等律)
- $P\lor (\lnot P)= T.$ (排中律)
- $P\land (\lnot P)= F.$ (矛盾律)
- $A\lor B = B\lor A,\,A\land B = B\land A$ (交換律)
- $(A\lor B)\lor C = A\lor (B\lor C),\,(A\land B)\land C = A\land (B\land C).$ (結合率)
- $(A\land B)\lor C = (A\lor C)\land (B\lor C),\,(A\lor B)\land C = (A\land C)\lor (B\land C).$ (分配律)
- $\lnot(A\lor B) = (\lnot A)\land(\lnot B),\,\lnot(A\land B) = (\lnot A)\lor(\lnot B).$ (De Morgan の法則)
証明
真偽値表を用いて確かめよ (以降の命題・定理も同様).■
定理2.4 論理命題の諸性質2
以下は常に真である.- $P\Longrightarrow P.$ (トートロジー)
- $(P\Longrightarrow Q) \Longrightarrow (\lnot Q\Longrightarrow\lnot P).$ (対偶)
- $((P\Longrightarrow Q) \land (Q\Longrightarrow R))\Longrightarrow (P\Longrightarrow R).$ (三段論法)
- $(P\land (P\Longrightarrow Q)) \Longrightarrow Q.$ (モーダス・ポネンス)
- $(P=F)\land (P\Longrightarrow Q).$ (空虚な真)
命題について
命題のみが書かれた場合は文脈上, 常に真であることを主張しているか, あるいはそうであると仮定していることがほとんどである.今後も特に断りがない場合, 単に命題を書いた場合は常にそれが常に真であることを主張する.
例2.5 演繹法
- 「ソクラテスは人間である」
- 「人間はいつか死ぬ」
を真とすれば, 三段論法より「ソクラテスはいつか死ぬ」は真である.
(命題 $P$ を 「$x$ はソクラテスである」, 命題 $Q$ を 「$x$ は人間である」, 命題 $R$ を 「$x$ はいつか死ぬ」 のように解釈している)
例2.6 包含関係
集合の包含関係 $A\subset B$ は命題論理を用いて以下のように表せられる. $$x\in A \Longrightarrow x\in B.$$特に, $\emptyset\subset A$ は空虚な真 (あるいは対偶) を考えれば, 任意の集合 $A$ で真である.