目次
予備知識とゴール
予備知識
数学の予備知識はいらないです。 具体例もすべて日常的なものを使っています。
論理については、この辺りの記号を知っていた方が良いです👇
| 記号 | 名前 | 読み方 |
|---|---|---|
| $\top$ | 恒真命題 | トートロジー |
| $\bot$ | 恒偽命題 | 矛盾 |
| $\lnot P$ | 否定命題 | $P$ でない |
| $P \land Q$ | 連言命題 | $P$ かつ $Q$ |
| $P \lor Q$ | 選言命題 | $P$ または $Q$ |
| $P \to Q$ | 含意命題 | $P$ ならば $Q$ |
| $P \leftrightarrow Q$ | 同値命題 | $P$ のときのみ $Q$ |
| $\forall \ x P(x)$ | 全称命題 | すべての $x$ について $P(x)$ |
| $\exists x \ P(x)$ | 存在命題 | ある $x$ について $P(x)$ |
不安な方は、お先に命題とは？述語とは？数学に必要な論理の基礎①をどうぞ。
ゴール
論理は全ての数学の基礎です。 論理というのは大雑把に言うと命題＋推論です。
この記事では推論の方を解説します。 具体的には「ゆえに」と「すなわち」という2つの推論の言葉を正しく理解することがゴールです。
推論とは？
含意命題 $P{\to}Q$ が恒真命題のとき、これを前提 $P$ 、結論 $Q$ の妥当な推論といい、
\begin{align} P{\Rightarrow}Q \end{align}
と書いて「$P$ ゆえに $Q$」と読みます。
※ $P \Rightarrow Q$ を $P$ $\therefore$ $Q$ とも書き、
「$P$ よって $Q$」や「$P$ より $Q$」や「$P$ は $Q$ を導く」とよも読みます。
※ $P \Rightarrow Q$ を $Q$ $\Leftarrow$ $P$ や $Q$ $\because$ $P$ とも書き、
「$Q$ なぜなら $P$」や「$Q$ は $P$ に従う」とも読みます。
※ $\to$ と $\Rightarrow$ は機能が違います。
$\to$ は命題同士をつなげて新しい命題を作る記号ですが、$\Rightarrow$ は命題同士の関係を表す記号です。
推論が正しいかどうか（妥当かどうか）と、前提や結論の命題が正しいかどうか（真か偽か）とは関係ありません。 推論が正しくても前提が正しくなければ結論が正しくない場合もありますし、 前提が正しくなければ推論が正しくても結論が正しくない場合もあります。 正しい結論を得るには、前提と推論がどちらも正しい必要があります。
たとえば、これは前提も推論もどちらも正しいパターンです👇
人間は動物である。
そして、私は人間である。
よって、私は動物である。
これは、推論は正しいけど前提が正しくないパターンです👇
トマトなら植物である。
そして、私はトマトである。
よって、私は植物である。
これは、前提は正しいけど推論が正しくないパターンです👇
ネコは動物である。
そして、私は動物である。
よって、私はネコである。
正しい結論を得るためには、前提の命題も推論もどちらも正しくないといけません。 つまり、真の命題は、真の命題と妥当な推論から導かれる、ということです。
同値とは？
同値命題 $P \leftrightarrow Q$ が恒真命題のとき、これを $P$ と $Q$ の同値変形といい、
\begin{align} P \Leftrightarrow Q \end{align}
と書いて「$P$ すなわち $Q$」と読みます。
※ $P \Leftrightarrow Q$ を「$P$ つまり $Q$」とも読みます。
※ $\leftrightarrow$ と $\Leftrightarrow$ は機能が違います。
$\leftrightarrow$ は命題同士をつなげて新しい命題を作る記号ですが、$\Leftrightarrow$ は命題同士の関係を表す記号です。
同値変形 $P \Leftrightarrow Q$ というのは、命題 $P$ から命題 $Q$ が導け、さらに $Q$ からも $P$ が導けるということです。
同値命題 $P{\leftrightarrow}Q$ が真になるのは $P$ と $Q$ の真理値が一致するときだけなので、 真理表を書いて $P$ と $Q$ の真理値がすべてのパターンで一致していれば、$P$ から $Q$ へ同値変形できるということになります。
証明とは？
真だと分かっている $n$ 個の命題 $P_1, P_2, \cdots ,P_n$ から、推論や同値変形を重ねて未知の命題 $Q$ を導くことを、$Q$ の証明といいます：
\begin{align} P_1 \land P_2 \land \cdots \land P_n \Rightarrow \cdots \Rightarrow Q \end{align}
たとえばこんな感じの証明をよく見ると思います👇
$P_1$、$P_2$ である。
ゆえに $L_1$ である。
すなわち $L_2$ である。
また、$P_3$ 、 $P_4$ 、 $P_5$ である。
ゆえに $L_3$ である。
$L_2$、$L_3$ ゆえに $Q$ である。
これを記号で書くとこうなります👇
$P_1 \land P_2 \Rightarrow L_1$
$L_1 \Leftrightarrow L_2$
$P_3 \land P_4 \land P_5 \Rightarrow L_3$
$L_2 \land L_3 \Rightarrow Q$
これを省略しないでちゃんと書くとこんな推論をしてることになります👇
\begin{align} P_1 \land P_2 \land P_3 \land P_4 \land P_5 & \Rightarrow L_1 \land P_3 \land P_4 \land P_5 \br & \Leftrightarrow L_2 \land P_3 \land P_4 \land P_5 \br & \Rightarrow L_2 \land L_3 \br & \Rightarrow Q \end{align}
よく見ると、ちゃんと $Q$ の証明の形：
\begin{align} P_1 \land P_2 \land P_3 \land P_4 \land P_5 \Rightarrow \cdots \Rightarrow Q \end{align}
になってることが分かります。
基本の同値変形
基本的な同値変形を10個みてみましょう。
排中律
命題 $P$ について次の同値変形が成り立ちます：
\begin{align} P \lor \lnot P \Leftrightarrow \top \end{align}
排中律が成り立つことは、真理表を書けばすぐに確認できます。
| $P$ | $\lnot P$ | $P \lor \lnot P$ | $\top$ | $P \lor \lnot P \leftrightarrow \top$ |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
排中律は、命題の真理値は必ず真か偽のどちらかを取るということを意味しています。
たとえば「彼はネコが好き」という命題と「彼はネコが好きでない」という命題はどちらかが必ず真になります。
論理の世界には「好きでも嫌いでもない」という中間の状態はありません。
矛盾律
命題 $P$ について次の同値変形が成り立ちます：
\begin{align} P \land \lnot P \Leftrightarrow \bot \end{align}
矛盾律も、真理表を書けばすぐに確認できます。
| $P$ | $\lnot P$ | $P \land \lnot P$ | $\bot$ | $P \land \lnot P \leftrightarrow \bot$ |
|---|---|---|---|---|
| 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
矛盾律は、ある命題とその否定命題がどちらも真になることはないということを意味しています。
吸収律
命題 $P$ について次の同値変形が成り立ちます：
\begin{align} P \lor \top \Leftrightarrow \top \end{align}
吸収律も真理表で確認できます。
| $P$ | $\top$ | $P \lor \top$ | $P \lor \top \leftrightarrow \top$ |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 |
命題 $P$ について次の同値変形が成り立ちます：
\begin{align} P \land \bot \Leftrightarrow \bot \end{align}
| $P$ | $\bot$ | $P \land \bot$ | $P \land \bot \leftrightarrow \bot$ |
|---|---|---|---|
| 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 |
消去律
命題 $P$ について次の同値変形が成り立ちます：
\begin{align} P \land \top \Leftrightarrow P \end{align}
消去律も真理表で確認できます。
| $P$ | $\top$ | $P \land \top$ | $P \land \top \leftrightarrow P$ |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 |
命題 $P$ について次の同値変形が成り立ちます：
\begin{align} P \lor \bot \Leftrightarrow P \end{align}
| $P$ | $\bot$ | $P \lor \bot$ | $P \lor \bot \leftrightarrow P$ |
|---|---|---|---|
| 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 |
べき等律
命題 $P$ について次の同値変形が成り立ちます：
\begin{align} P \land P \Leftrightarrow P \end{align}
べき等律も真理表で確認できます。
| $P$ | $P \land P$ | $P \land P \leftrightarrow P$ |
|---|---|---|
| 1 | 1 | 1 |
| 0 | 0 | 1 |
命題 $P$ について次の同値変形が成り立ちます：
\begin{align} P \lor P \Leftrightarrow P \end{align}
| $P$ | $P \lor P$ | $P \lor P \leftrightarrow P$ |
|---|---|---|
| 1 | 1 | 1 |
| 0 | 0 | 1 |
交換律
命題 $P$ と $Q$ について次の同値変形が成り立ちます：
\begin{align} P \lor Q \Leftrightarrow Q \lor P \end{align}
交換律も真理表で確認できます。
| $P$ | $Q$ | $P \lor Q$ | $Q \lor P$ | $P \lor Q \leftrightarrow Q \lor P$ |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 1 |
命題 $P$ と $Q$ について次の同値変形が成り立ちます：
\begin{align} P \land Q \Leftrightarrow Q \land P \end{align}
| $P$ | $Q$ | $P \land Q$ | $Q \land P$ | $P \land Q \leftrightarrow Q \land P$ |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 0 | 0 | 0 | 1 |
結合律
命題 $P$ と $Q$ と $R$ について次の同値変形が成り立ちます：
\begin{align} P \lor (Q \lor R) \Leftrightarrow (P \lor Q) \lor R \end{align}
結合律も真理表で確認できます。
| $P$ | $Q$ | $R$ | $(P \lor Q) \lor R$ | $P \lor (Q \lor R)$ |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 0 | 0 |
命題 $P$ と $Q$ と $R$ について次の同値変形が成り立ちます：
\begin{align} P \land (Q \land R) \Leftrightarrow (P \land Q) \land R \end{align}
| $P$ | $Q$ | $R$ | $(P \land Q) \land R$ | $P \land (Q \land R)$ |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
結合律があるおけげで、たとえば $P{\lor}(Q{\lor}R)$ や $(P{\lor}Q){\lor}R$ を $P{\lor}Q{\lor}R$ のようにカッコを省略して書けます。
ただし、次に見るように $\land$ と $\lor$ の間に成り立つのは結合律ではなく分配律なので、 カッコを省略できるのは $\land$ と $\lor$ が混ざっていないときだけです。
分配律
命題 $P$ と $Q$ と $R$ について次の同値変形が成り立ちます：
\begin{align} P \land (Q \lor R) \Leftrightarrow (P \land Q) \lor (P \land R) \end{align}
分配律も真理表で確認できます。
| $P$ | $Q$ | $R$ | $P{\land}(Q{\lor}R)$ | $(P{\land}Q){\lor}(P{\land}R)$ |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
命題 $P$ と $Q$ と $R$ について次の同値変形が成り立ちます：
\begin{align} P \lor (Q \land R) \Leftrightarrow (P \lor Q) \land (P \lor R) \end{align}
2つめも確認しておきましょう。
| $P$ | $Q$ | $R$ | $P{\lor}(Q{\land}R)$ | $(P{\lor}Q){\land}(P{\lor}R)$ |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
対偶律
命題 $P$ と $Q$ について次の同値変形が成り立ちます：
\begin{align} P \to Q \Leftrightarrow \lnot Q \to \lnot P \end{align}
対偶律も真理表で確認できます👇
| $P$ | $Q$ | ${\lnot}P$ | ${\lnot}Q$ | $P{\to}Q$ | ${\lnot}Q{\to}{\lnot}P$ |
|---|---|---|---|---|---|
| 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 | 1 |
対偶律は、これまでに出てきた同値変形を繰り返すことでも確認できます👇
\begin{align}P \to Q & \Leftrightarrow \lnot P \lor Q \br & \Leftrightarrow Q \lor \lnot P \br & \Leftrightarrow \lnot \lnot Q \lor \lnot P \br & \Leftrightarrow \lnot Q \to \lnot P \end{align}
このように、真理表を書くよりも同値変形を繰り返す方が簡単に確認できる場合もあります。
同値命題の同値変形
命題 $P$ と命題 $Q$ の同値命題は次のように同値変形して書き換えることができます。
\begin{align} P \leftrightarrow Q \Leftrightarrow ( P \land Q ) \lor ( \lnot P \land \lnot Q) \end{align}
これが正しいことは、次のように確認できます。
\begin{align} P \leftrightarrow Q & \Leftrightarrow ( P \to Q ) \land ( Q \to P ) \br & \Leftrightarrow ( \lnot P \lor Q) \land ( \lnot Q \lor P ) \br & \Leftrightarrow ( \lnot P \land \lnot Q ) \lor ( Q \land \lnot Q ) \lor ( \lnot P \land P ) \lor ( Q \land P ) \br & \Leftrightarrow ( \lnot P \land \lnot Q ) \lor \bot \lor \bot \lor ( P \land Q ) \br & \Leftrightarrow ( P \land Q ) \lor ( \lnot P \land \lnot Q) \end{align}
量化子の交換律
全称命題 $\forall x \ \forall y \ P(x, y)$ について次の同値変形が成り立ちます：
\begin{align} \forall x \ \forall y \ P(x, y) \Leftrightarrow \forall y \ \forall x \ P(x, y) \end{align}
これは次のように確認。
\begin{align} \forall x \ \forall y \ P(x, y) & \Leftrightarrow \forall x \ ( P(x, y_1) \land \cdots \land P(x, y_n) ) \br & \Leftrightarrow ( P(x_1, y_1) \land \cdots \land P(x_1, y_n) ) \land \cdots \land ( P(x_m, y_1) \land \cdots \land P(x_m, y_n) ) \br & \Leftrightarrow ( P(x_1, y_1) \land \cdots \land P(x_m, y_1) ) \land \cdots \land ( P(x_1, y_n) \land \cdots \land P(x_m, y_n) ) \br & \Leftrightarrow \forall y \ ( P(x_1, y) \land \cdots \land P(x_m, y) ) \br & \Leftrightarrow \forall y \ \forall x \ P(x, y) \end{align}
$\exists$ も交換することができます。
存在命題 $\exists x \ \exists y \ P(x, y)$ について次の同値変形が成り立ちます：
\begin{align} \exists x \ \exists y \ P(x, y) \Leftrightarrow \exists y \ \exists x \ P(x, y) \end{align}
これは次のように確認できます。
\begin{align} \exists x \ \exists y \ P(x, y) & \Leftrightarrow \exists x \ ( P(x, y_1) \lor \cdots \lor P(x, y_n) ) \br & \Leftrightarrow ( P(x_1, y_1) \lor \cdots \lor P(x_1, y_n) ) \lor \cdots \lor ( P(x_m, y_1) \lor \cdots \lor P(x_m, y_n) ) \br & \Leftrightarrow ( P(x_1, y_1) \lor \cdots \lor P(x_m, y_1) ) \lor \cdots \lor ( P(x_1, y_n) \lor \cdots \lor P(x_m, y_n) ) \br & \Leftrightarrow \exists y \ ( P(x_1, y) \lor \cdots \lor P(x_m, y) ) \br & \Leftrightarrow \exists y \ \exists x \ P(x, y) \end{align}
否定の同値変形
あとで出てきますが、背理法という証明法で証明するときに否定命題を作る必要がでてくるので、否定命題に同値変形する方法をまとめておきます。
否定命題の否定
否定命題 $\lnot P$ の否定命題について次の同値変形が成り立ちます：
\begin{align} \lnot \lnot P \Leftrightarrow P \end{align}
| $P$ | $\lnot P$ | $\lnot \lnot P$ |
|---|---|---|
| 1 | 0 | 1 |
| 0 | 1 | 0 |
連言命題の否定（ド・モルガンの法則）
連言命題 $P \land Q$ の否定命題について次の同値変形が成り立ちます：
\begin{align} \lnot (P \land Q) \Leftrightarrow \lnot P \lor \lnot Q \end{align}
| $P$ | $Q$ | $\lnot (P \land Q)$ | $\lnot P \lor \lnot P$ |
|---|---|---|---|
| 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 |
選言命題の否定（ド・モルガンの法則）
命題 $P \lor Q$ の否定命題について次の同値変形が成り立ちます：
\begin{align} \lnot (P \lor Q) \Leftrightarrow \lnot P \land \lnot Q \end{align}
| $P$ | $Q$ | $\lnot (P \lor Q)$ | $\lnot P \land \lnot P$ |
|---|---|---|---|
| 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 |
含意命題の否定
含意命題 $P \to Q$ の否定命題について次の同値変形が成り立ちます：
\begin{align} \lnot (P \to Q) \Leftrightarrow P \land \lnot Q \end{align}
\begin{align} \lnot ( P \to Q ) & \Leftrightarrow \lnot ( \lnot P \lor Q ) \br & \Leftrightarrow P \land \lnot Q \end{align}
同値命題の否定
同値命題 $P \leftrightarrow Q$ の否定命題について次の同値変形が成り立ちます：
\begin{align} \lnot (P \leftrightarrow Q) \Leftrightarrow (P \lor Q) \land (\lnot P \lor \lnot Q) \end{align}
全称命題の否定（ド・モルガンの法則）
全称命題 $\forall x \ P(x)$ の否定命題について次の同値変形が成り立ちます：
\begin{align} \lnot (\forall x \ P(x)) \Leftrightarrow \exists x \ \lnot P(x) \end{align}
$x$の変域を$x_1$、$x_2$、$\cdots$、$x_n$とすると，
\begin{align} \lnot ( \forall x \ P(x) ) & \Leftrightarrow \lnot ( P(x_1) \land P(x_2) \land \cdots \land P(x_n) ) \br & \Leftrightarrow \lnot P(x_1) \lor \lnot P(x_2) \lor \cdots \lnot P(x_n) \br & \Leftrightarrow \exists x \ ( \lnot P(x) ) \end{align}
ただし、1行目から2行目への変形で、ド・モルガンの法則を繰り返し使いました。
\begin{align} \lnot \forall x \ ( P(x) \to Q(x) ) \Leftrightarrow \exists x \ ( P(x) \land \lnot Q(x) ) \end{align}
\begin{align} \lnot \forall x \ ( P(x) \to Q(x) ) & \Leftrightarrow \exists x \ \lnot ( \lnot P(x) \lor Q(x) ) \br & \Leftrightarrow \exists x \ ( P(x) \land \lnot Q(x) ) \end{align}
存在命題の否定（ド・モルガンの法則）
存在命題 $\exists x \ P(x)$ の否定命題について次の同値変形が成り立ちます：
\begin{align} \lnot (\exists x \ P(x)) \Leftrightarrow \forall x \ \lnot P(x) \end{align}
$x$の変域を$x_1$，$x_2$，$\cdots$，$x_n$とすると，
\begin{align} \lnot ( \exists x \ P(x) ) & \Leftrightarrow \lnot ( P(x_1) \lor P(x_2) \lor \cdots \lor P(x_n) ) \br & \Leftrightarrow \lnot P(x_1) \land \lnot P(x_2) \land \cdots \lnot P(x_n) \br & \Leftrightarrow \forall x \ ( \lnot P(x) ) \end{align}
ただし、1行目から2行目への変形で、ド・モルガンの法則を繰り返し使いました。
\begin{align} \lnot \exists x \ ( P(x) \land Q(x) ) \Leftrightarrow \forall x \ ( P(x) \to \lnot Q(x) ) \end{align}
\begin{align} \lnot \exists x \ ( P(x) \land Q(x) ) & \Leftrightarrow \forall x \ \lnot ( P(x) \land Q(x) ) \br & \Leftrightarrow \forall x \ ( \lnot P(x) \lor \lnot Q(x) ) \br & \Leftrightarrow \forall x \ ( P(x) \to \lnot Q(x) ) \end{align}
恒真命題の否定
恒真命題 $\top$ の否定命題について次の同値変形が成り立ちます：
\begin{align} \lnot \top \Leftrightarrow \bot \end{align}
\begin{align} \lnot \top & \Leftrightarrow \lnot ( P \lor \lnot P ) \br & \Leftrightarrow \lnot P \land P \br & \Leftrightarrow \bot \end{align}
恒偽命題の否定
恒偽命題 $\top$ の否定命題について次の同値変形が成り立ちます：
\begin{align} \lnot \bot \Leftrightarrow \top \end{align}
\begin{align} \lnot \bot & \Leftrightarrow \lnot ( P \land \lnot P ) \br & \Leftrightarrow \lnot P \lor P \br & \Leftrightarrow \top \end{align}
基本の推論規則
連言除去
$P \land Q$ が真なら $P$ は真になります：
\begin{align} P \land Q \Rightarrow P \end{align}
| $P$ | $Q$ | $P{\land}Q$ | $P{\land}Q \to P$ |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 0 | 0 | 1 |
これは、たとえばこんな推論が妥当だということを言ってます👇
私はネコとイヌが好きだ。
ゆえに、私はネコが好きだ。
選言導入
$P$ が真ならから $P \lor Q$ が導けます：
\begin{align} P \Rightarrow P \lor Q \end{align}
| $P$ | $Q$ | $P{\lor}Q$ | $P \to P{\lor}Q$ |
|---|---|---|---|
| 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 0 | 0 | 0 | 1 |
これは、たとえばこんな推論が妥当だということを言ってます👇
私はネコが好きだ。
ゆえに、私はネコかイヌが好きだ。
全称除去（普遍例化）
これは公式に具体例をあてはめることがOKな理由です。
$x$ の変域を $x_1, x_2, \cdots$ とすると、$\forall \ x P(x)$ から $P(x_i)$ が導けます：
\begin{align} \forall \ x P(x) \Rightarrow P(x_i) \end{align}
ただし $x_i$ は $x$ の変域の任意の値です。
\begin{align} \forall \ x \ P(x) & \Leftrightarrow P(x_1) \land P(x_2) \land \cdots \land P(x_n) \br & \Rightarrow P(x_i) \end{align}
これは、たとえばこんな推論が妥当だということを言ってます👇
私はすべての動物が好きだ。
ゆえに、私はネコが好きだ。
存在導入（存在汎化）
$x$ の変域を $x_1, x_2, \cdots$ とすると、$P(x_i)$ から $\exists x \ P(x)$ が導けます：
\begin{align} P(x_i) \Rightarrow \exists x \ P(x) \end{align}
\begin{align} P(x_i) & \Rightarrow P(x_1) \lor P(x_2) \lor \cdots \lor P(x_n) \br & \Leftrightarrow \exists x \ P(x) \end{align}
これは選言導入を一般化したものです。たとえばこんな推論が妥当だということを言ってます👇
私はネコが好きだ。
ゆえに、私はある動物が好きだ。
直接法
$A{\to}B$ という形の命題を証明するのに、 $A$ を仮定して $B$ を導くということをします。
この証明方法は直接法と呼ばれていて、中学校でも習います。
この証明方法の基礎は次の同値変形です。
命題 $P$、$Q$、$R$ について次の同値変形が成り立ちます：
\begin{align} P \to (Q \to R) \Leftrightarrow (P \land Q) \to R \end{align}
なぜなら、
\begin{align} P \to ( Q \to R ) & \Leftrightarrow \lnot P \lor ( \lnot Q \lor R ) \br & \Leftrightarrow ( \lnot P \lor \lnot Q ) \lor R \br & \Leftrightarrow \lnot ( P \land Q ) \lor R \br & \Leftrightarrow ( P \land Q ) \to R \end{align}
だからです。
ほとんどの命題は $A{\to}B$ という形をしています。
本来これを証明するには、真である $n$ 個の命題 $P_1, P2, \cdots P_n$から $A{\to}B$ を推論することになります。
つまり、
\begin{align} P_1 \land P_2 \land \cdots \land P_n \Rightarrow A \to B \end{align}
という形の推論をしないといけません。
でもこのように含意命題を直接導くことは結構難しかったりします。
そこでこの同値関係を使って、
\begin{align} P_1 \land P_2 \land \cdots \land P_n \land A \Rightarrow B \end{align}
の形の推論に直して証明します。
命題 $A{\to}B$ を証明するのに、
\begin{align} P \Rightarrow A \to B \end{align}
という形の推論で証明する代わりに、
\begin{align} P \land A \Rightarrow B \end{align}
という形の推論で証明することがあります。 このとき、前件から前提に移った命題 $A$ のことを仮定といいます。
三段論法
$A \land B \Rightarrow C$ という形の推論規則を三段論法といいます。 有名な三段論法を4つ紹介します。
前件肯定
まずは前件肯定という、一番シンプルな三段論法です。
この推論規則は含意除去やモーダスポネンスとも呼ばれています。
$P{\to}Q$ と $P$ から $Q$ を導けます：
\begin{align} (P \to Q) \land P \Rightarrow Q \end{align}
なぜなら、
\begin{align} (P \to Q) \land P & \Leftrightarrow ( \lnot P \lor Q ) \land P \br & \Leftrightarrow ( \lnot P \land P ) \lor ( Q \land P ) \br & \Leftrightarrow \bot \lor ( Q \land P ) \br & \Leftrightarrow Q \land P \br & \Rightarrow Q \end{align}
だからです。
前件肯定を使った推論はたとえばこんな感じです👇
ネコを飼ってるならネコ好きだ。
そして、私はネコを飼ってる。
ゆえに、私はネコ好きだ。
後件否定
次は後件否定という推論規則です。
これもシンプルな三段論法のひとつで、モーダストレンスとも呼ばれています。
$P{\to}Q$ と $\lnot Q$ から $\lnot P$ を導けます：
\begin{align} (P \to Q) \land \lnot Q \Rightarrow \lnot P \end{align}
なぜなら、
\begin{align} (P \to Q) \land \lnot Q & \Leftrightarrow ( \lnot P \lor Q ) \land \lnot Q \br & \Leftrightarrow ( \lnot P \land \lnot Q ) \lor ( Q \land \lnot Q ) \br & \Leftrightarrow ( \lnot P \land \lnot Q ) \lor \bot \br & \Leftrightarrow \lnot P \land \lnot Q \br & \Rightarrow \lnot P \end{align}
だからです。
後件否定を使った推論はたとえばこんな感じです👇
ネコを飼ってるならネコ好きだ。
そして、私はネコ好きでない。
ゆえに、私はネコを飼ってない。
選言三段論法
次は選言三段論法という推論規則です。
$P \lor Q$ と $\lnot P$ から $Q$ を導けます：
\begin{align} (P \lor Q) \land \lnot P \Rightarrow Q \end{align}
なぜなら、
\begin{align} (P \lor Q) \land \lnot P & \Leftrightarrow ( P \land \lnot P ) \lor ( Q \land \lnot P ) \br & \Leftrightarrow \bot \lor ( Q \land \lnot P ) \br & \Leftrightarrow Q \land \lnot P \br & \Rightarrow Q \end{align}
だからです。
選言三段論法を使った推論はたとえばこんな感じです👇
私はネコかイヌが好きだ。
そして、私はネコ好きでない。
ゆえに、私はイヌが好きだ。
仮言三段論法
次は仮言三段論法という推論規則です。 単に三段論法とよばれることも多いです。
$P{\to}Q$ と $Q{\to}R$ から $P{\to}R$ を導けます：
\begin{align} (P \to Q) \land (Q \to R) \Rightarrow P \to R \end{align}
なぜなら、
\begin{align} (P \to Q) \land (Q \to R) & \Leftrightarrow ( \lnot P \lnot Q ) \land ( \lnot Q \lor R ) \br & \Leftrightarrow ( \lnot P \land \lnot Q ) \lor ( Q \land \lnot Q) \lor ( \lnot P \land R ) \lor ( Q \land R ) \br & \Rightarrow \lnot P \lor \bot \lor R \lor R \br & \Leftrightarrow \lnot P \lor R \br & \Leftrightarrow P \to R \end{align}
だからです。
仮言三段論法を使った推論は例えばこんな感じです👇
ネコが好きならペットを飼っている。
そして、ペットを飼っているなら一軒家に住んでいる。
ゆえに、ネコが好きなら一軒家に住んでいる。
両刀論法
$A{\land}B{\land}(C{\lor}D){\Rightarrow}E$ という形の推論を両刀論法といいます。ジレンマともいいます。
選言除去
まずは選言除去という推論規則です。単にジレンマとよばれることも多いです。 この推論規則のおかげで、場合分けの証明が妥当になります。
\begin{align} (P \to R) \land (Q \to R) \land (P \lor Q) \Rightarrow R \end{align}
選言除去を使った推論は例えばこんな感じです👇
ネコを飼ってるなら動物好き。
イヌを飼ってるなら動物好き。
私はネコかイヌを飼っている。
ゆえに、私は動物好き。
構成的ジレンマ
\begin{align} (P \to Q) \land (R \to S) \land (P \lor R) \Rightarrow Q \lor S \end{align}
破壊的ジレンマ
\begin{align} (P \to Q) \land (R \to S) \land (\lnot Q \lor \lnot S) \Rightarrow \lnot P \lor \lnot R \end{align}
背理法（否定導入）
否定導入は、背理法という証明方法の基礎になっている推論規則です。
$P$ を仮定して矛盾が導かれるならば $\lnot P$ が導かれます：
\begin{align} P \to \bot \Rightarrow \lnot P \end{align}
なぜなら、
\begin{align} P \to \bot & \Leftrightarrow \lnot P \lor ( P \land \lnot P ) \br & \Leftrightarrow ( \lnot P \lor P ) \land ( \lnot P \lor \lnot P ) \br & \Leftrightarrow \top \land \lnot P \br & \Leftrightarrow \lnot P \end{align}
だからです。この推論規則で $P$ に $\lnot P$ を代入すれば、
\begin{align} \lnot P \to \bot \Rightarrow P \end{align}
となります。 実際にはこっちをよく使います。 $P$ を証明したいけど直接証明するのが難しいとき、$\lnot P$ から矛盾を導くことで、間接的に $P$ を証明することができます。
たとえば「彼はネコが好き」を証明したいけれど、これを直接証明するのが難しいとします。 そんなとき、「彼はネコが好きでない」と仮定して何かしらの矛盾を導ければ、間接的に「彼はネコが好き」を証明することができます。
矛盾
最後は爆発律とも呼ばれる推論規則で、矛盾からはどんな命題も導き出せてしまうという規則です。
矛盾からはどんな命題も導けます：
\begin{align} \bot \Rightarrow P \end{align}
数学で矛盾が嫌われる理由がここにあります。 理論のどこかにひとつでも矛盾があれば、そこからどんな命題でも導けてしまうからです。