AND と OR の推論規則｜記号論理学で連言と選言を扱う

連言（AND）と選言（OR）にも、それぞれ導入規則と除去規則があります。これらは含意の規則と比べて直感的で、使いやすいものが多いです。

連言導入（∧I）

連言導入は、p と q が両方成り立つときに p ∧ q を導く規則です。

$$\frac{pq}{p\wedge q}(\wedge I)$ 2つの命題を「かつ」で結んだ連言を作ります。p が証明でき、q も証明できるなら、p ∧ q も証明できるという当然の規則です。 <!-- outer_0 --> ## 連言除去（∧E） 連言除去は、p ∧ q から p を取り出す（または q を取り出す）規則です。 $\frac{p\wedge q}{p}(\wedge E_1)\frac{p\wedge q}{q}(\wedge E_2)$ 連言がわかっているなら、その各成分を自由に使えます。「AかつB」が成り立つなら「A」も成り立ち、「B」も成り立つという自然な推論です。 ## 選言導入（∨I） 選言導入は、p から p ∨ q を導く規則です。 $\frac{p}{p\vee q}(\vee I_1)\frac{q}{p\vee q}(\vee I_2)$ p が成り立つなら「p または q」も成り立ちます。片方が真なら、選言は真だからです。 この規則は「弱める」操作です。p という強い主張から、p ∨ q という弱い主張を導きます。q が何であっても構いません。 <!-- outer_1 --> ## 選言除去（∨E） 選言除去は少し複雑です。p ∨ q が成り立つとき、p から r が導け、q からも r が導けるなら、r が成り立つという規則です。 $\frac{p\vee q[p]⋮r[q]⋮r}{r}(\vee E)$$

これは場合分けに対応します。「p または q」が成り立つとき、p の場合を考えて r を導き、q の場合を考えても r を導けるなら、どちらにしても r が成り立つと結論できます。

連言と選言の規則の比較

連言と選言の規則には、興味深い対称性があります。

連言導入は2つ必要で、連言除去は1つで足りる。選言導入は1つで足りるが、選言除去は2つの場合分けが必要。このように、導入と除去で必要な情報量が逆転しています。

実例：分配法則の証明

p ∧ (q ∨ r) → (p ∧ q) ∨ (p ∧ r) を証明してみましょう。これは分配法則の一方向です。

まず p ∧ (q ∨ r) を仮定します。連言除去で p と q ∨ r を取り出します。

q ∨ r について場合分けします。q を仮定すると、p と q から p ∧ q を作り、選言導入で (p ∧ q) ∨ (p ∧ r) を得ます。r を仮定しても、同様に (p ∧ q) ∨ (p ∧ r) を得ます。

選言除去により、どちらの場合でも (p ∧ q) ∨ (p ∧ r) が導けるので、これを結論します。最後に含意導入で全体を閉じます。

次回は、否定の推論規則と背理法について学びます。