帰納法による証明：ド・モルガンの法則と分配法則の一般化
要約
この授業では、数学および命題論理における帰納法による証明のテーマを扱います。存在する2種類の証明、すなわち論理の規則に基づく内部的または演繹的証明と、論理そのものに関わる命題を証明するために必要な外部的またはメタ数学的証明が説明されます。数学的帰納法は、ある命題がすべての自然数に対して成り立つことを示すための証明手法として導入されます。具体的な証明の例が提示され、命題論理におけるド・モルガンの法則および分配法則の一般形が紹介され、それぞれ帰納法によって証明されます。この授業は、数学と論理の基礎を理解し、それをさまざまな知識分野に応用するために非常に重要です。
学習目標：
この授業を終えた学生は次のことができるようになります：
- 区別する：内部的または演繹的証明と外部的またはメタ数学的証明の2種類の証明を認識する。
- 適用する：数学的帰納法を用いて自然数や命題論理に関する証明を行う。
- 使用する：命題論理の表現において、連言および選言の記法を用いる。
- 理解する：ド・モルガンの法則および命題論理における分配法則の一般形。
- 理解する：帰納法の仮定の概念と、帰納的証明におけるその役割。
目次
内部的証明と外部的証明
数学的帰納法による証明
命題論理における帰納法による証明
ド・モルガンの法則の一般形
分配法則の一般形
内部的証明と外部的証明
区別すべき2種類の証明が存在します。これまで多くの形式的証明の例を見てきました。これらの証明は、論理の規則に従って導かれるものです。このような証明は「論理の内部」で行われると言われ、「内部的証明」または「演繹的証明」とも呼ばれます。この種の形式的証明は、論理の言語で記述できる命題のみを証明するための限定的な方法です。しかし、論理そのものに関することを証明したい場合もあります。例えば、命題論理のすべての命題がある性質を満たすことを証明したい場合などです。このように、論理そのものに関わる命題は、論理の内部では証明も確立もできません。こうした命題を証明するには外部的証明を用います。外部的証明は「メタ数学的証明」とも呼ばれます。そして我々はすでにこの種の内容に出会っており、例えば（メタ）帰結定理を見たときがそうでした。ここで帰納的証明が文脈の中に位置づけられます。
数学的帰納法による証明
数学的帰納法とは、すべての自然数に対してある命題が成り立つことを証明するための方法です。
例：
11^n - 4^n という形のすべての数（ただし n は任意の自然数）について、常に 7 で割り切れることが証明できます。
証明： n=1 の場合を見てみると、
11^1 - 4^1 = 7
これは明らかに 7 で割り切れます。
次に、11^n - 4^n が n=k に対して割り切れると仮定します。この仮定から、n=k+1 に対しても同様に成り立つことを証明します。その手順は次のとおりです：
したがって、11^k - 4^k が 7 で割り切れるならば、11 ( 11^{k} - 4^{k} ) + 7\cdot 4^{k} も割り切れます。これはすなわち、11^{k+1} - 4^{k+1} も 7 で割り切れるということです。この結果、k=1 に対して割り切れるなら、k=2, k=3, k=4,\cdots と続いて、すべての n\in\mathbb{N} に対して割り切れることになります。このような場合、帰納法が完了したといいます。■
命題論理における帰納法による証明
これから行う帰納法による証明のために、まず次の記法上の約束を導入する必要があります。
記法： F_1,\cdots, F_n を命題論理における任意の有限個の式とする。このとき、それらの連言（AND）と選言（OR）は次のように記述されます：
\displaystyle \bigwedge_{i=1}^n F_i := F_1\wedge \cdots \wedge F_n
\displaystyle \bigvee_{i=1}^n F_i := F_1\vee \cdots \vee F_n
これにより、次に示す2つの一般化された形式を扱うことが可能となります。
ド・モルガンの法則の一般形
命題論理における有限個の式の集合が与えられたとき、 F_1,\cdots, F_n, 常に次の2つの性質が成り立ちます：
\displaystyle\neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right)
\displaystyle\neg\left(\bigvee_{i=1}^n F_i \right) \equiv \left( \bigwedge_{i=1}^n \neg F_i \right)
証明： 最初に、n に関する帰納法を用いて \neg\left(\bigwedge_{i=1}^n F_i \right) \equiv \left( \bigvee_{i=1}^n \neg F_i \right) を証明します。
まず初期の場合 n=1 を確認しましょう。この場合、次が明らかに成り立ちます： \neg F_1 \equiv \neg\left(\bigwedge_{i=1}^1F_i\right)\equiv \left(\bigvee_{i=1}^n \neg F_i \right) \equiv\neg F_1
次に、ある n=k に対してこの性質が成り立つと仮定します。つまり、有限個の式 F_1, F_2, \cdots, F_k に対して次が成り立つとします：
\displaystyle \neg\left(\bigwedge_{i=1}^k F_i\right) \equiv \left(\bigvee_{i=1}^k \neg F_i\right)
このとき、次のことが成り立つことを証明します：
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) \equiv \left(\bigvee_{i=1}^{k+1} \neg F_i\right)
連言の定義を用いると、次のようになります：
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right) := \neg\left[\left(\bigwedge_{i=1}^{k} F_i\right) \wedge F_{k+1}\right]
この式に対して、通常の2項に対するド・モルガンの法則を適用すると：
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[\neg\left(\bigwedge_{i=1}^{k} F_i\right) \vee \neg F_{k+1}\right]
ここで、帰納法の仮定を適用すれば：
\displaystyle \neg\left(\bigwedge_{i=1}^{k+1} F_i\right)\equiv \left[ \left(\bigvee_{i=1}^k \neg F_i\right) \vee \neg F_{k+1}\right] := \left(\bigvee_{i=1}^{k+1}\neg F_i \right)
したがって、この帰納法は完了しており、この性質はすべての n に対して成り立つことになります。2つ目の関係式についても、完全に同様な方法で証明できるので、これは読者への練習問題として残しておきます。ムハハハ！
分配法則の一般形
ド・モルガンの法則と同様に、 分配法則も次のように一般化することができます。\{F_1, \cdots, F_n\} および \{G_1,\cdots, G_m\} を任意の有限集合の命題論理式とすると、次の等価関係が成り立ちます：
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]
\displaystyle \left[ \left(\bigvee_{i=1}^n F_i \right) \wedge \left(\bigvee_{j=1}^m G_j \right) \right] \equiv \left[\bigvee_{i=1}^n\left(\bigvee_{j=1}^m(F_i\wedge G_j) \right) \right]
証明： この証明を構成するには、n と m に関する二重の帰納法を用いる必要があります。ここではまず n に関して、その後 m に関して帰納法を行います。対象となる等式は以下です：
\left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^m G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^m(F_i\vee G_j) \right) \right]
まず m=1 の場合を考えます。このとき上式は次のように書き換えられます：
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^1 G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^1(F_i\vee G_j) \right) \right].
これは次のように言い換えることができます：
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^n\left( F_i\vee G_1 \right) \right].
ここで、この等式を n に関する帰納法で証明していきます。
まず n=1 の場合を考えると、式は次のように単純化されます：
F_1 \vee G_1 \equiv F_1 \vee G_1.
これは明らかに正しいです。次に、ある n=k に対して命題が成り立つと仮定します。つまり、帰納法の仮定は次のようになります：
\displaystyle \left[ \left(\bigwedge_{i=1}^k F_i \right) \vee G_1 \right] \equiv \left[\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right].
ここから n=k+1 に対してもこの関係が成り立つことを示します。
連言の定義から次のように書けます：
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] := \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\wedge F_{k+1} \right) \vee G_1 \right]
ここで、\vee に関する分配法則を用いると、次のようになります：
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\left(\bigwedge_{i=1}^{k}F_i \right)\vee G_{1} \right) \wedge \left(F_{k+1} \vee G_1 \right) \right]
ちょうどこの時点で、帰納法の仮定を用いることができます：
\displaystyle \left[\left(\bigwedge_{i=1}^{k+1}F_i \right) \vee G_1 \right] \equiv \left[\left(\bigwedge_{i=1}^k\left( F_i\vee G_1 \right) \right) \wedge \left(F_{k+1} \vee G_1 \right) \right] := \left[\bigwedge_{i=1}^{k+1}(F_{i}\vee G_1 \right]
したがって、すべての n\in\mathbb{N} に対して次が成り立つことが帰納法により証明されました：
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right)\vee G_1\right] \equiv \left[\bigwedge_{i=1}^n(F_i\vee G_1)\right]
これにより n に関する帰納法が完了し、m=1 の初期ケースも確認されました。次に m に関する帰納法を完成させます。そのために、m=l において命題が成り立つと仮定します：
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^l G_j \right) \right] \equiv \left[\bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \right]
この仮定から、m=l+1 に対しても命題が成り立つことを示します。
いつものように、連言の定義から始めると次のようになります：
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] := \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\left(\bigwedge_{j=1}^{l} G_j \right) \wedge G_{l+1}\right) \right]
ここで、\vee に関する分配法則を使うと：
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \left( \left(\bigwedge_{i=1}^n F_i \right) \vee \left( \bigwedge_{j=1}^l G_j \right) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1} \right) \right]
したがって、帰納法の仮定を用いることで次のように書くことができます：
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \left( \bigwedge_{i=1}^n F_i \right)\vee G_{l+1} \right) \right]
そして、n に関する帰納法の結果を用いれば：
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^l(F_i\vee G_j) \right) \wedge \left( \bigwedge_{i=1}^n (F_i \vee G_{l+1} )\right) \right]
この最後の式は、連言の定義から次のように書けます：
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{l+1} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{l+1}(F_i\vee G_j) \right) \right]
したがって、m に関する帰納法も完了し、次の等式が成り立つことが示されました：
\displaystyle \left[ \left(\bigwedge_{i=1}^n F_i \right) \vee \left(\bigwedge_{j=1}^{m} G_j \right) \right] \equiv \left[ \bigwedge_{i=1}^n\left(\bigwedge_{j=1}^{m}(F_i\vee G_j) \right) \right]
これはすべての n,m\in\mathbb{N} に対して有効です。
この帰納法による証明の探究を通じて、厳密な数学的証明技法が自然数の領域だけでなく、命題論理の領域にも適用可能であることを示しました。帰納法を用いることで、ド・モルガンの法則および分配法則の一般形の妥当性を確立し、数学のさまざまな分野に存在する論理的基盤への理解を強化しました。このアプローチは、抽象的な推論能力の発展にとって不可欠であるだけでなく、数学およびそれを超えた複雑な問題に取り組むための強力な道具ともなります。