証明のやり方

(数学の分野としての)論理を学ぶには、事前に、他分野(解析とかトポロジーとか)を学ぶ場合と同等な論理的能力が要求される。「箱を開ける鍵は箱のなか」状態となり、ラチが明かない。証明のやり方(How to Prove)ということなら、「みんなが使っているルールを俺も憶える」と割り切ったほうが早い。$`\newcommand{\Imp}{\Rightarrow}`$

  1. $`A\land B`$ を証明したいなら : $`A`$ を証明し、$`B`$ も証明する。
  2. $`A\lor B`$ を証明したいなら : どちらか一方を証明すればOK。両方証明すれば、それは $`A\land B`$ の証明になる。
  3. $`A\Imp B`$ を証明したいなら : $`A`$ を仮定して $`B`$ を証明する。
  4. $`\lnot A`$ を証明したいなら : $`A`$ を仮定して矛盾を導く。矛盾とは、$`C \land \lnot C`$ の形の命題、$`C`$ は何でもいい。例:「$`\sqrt{2}`$ は有理数ではない」の証明は、「$`\sqrt{2}`$ は有理数である」を仮定して矛盾を導く。
  5. $`\forall x\in X. A(x)`$ を証明したいなら : $`(x: X)`$ という自由変数の宣言のもとで、自由変数 $`x`$ を含む命題 $`A(x)`$ を証明する。変数名はリネームしたほうが分かりやすい($`x`$ を $`a`$ にリネームとか)。
  6. $`\exists x\in X. A(x)`$ を証明したいなら : $`A(x)`$ を満たす $`x`$ の具体例を作る。

その他:

  1. $`A`$ と $`A\Imp B`$ から $`B`$ を導いてもよい(モダスポネンス)。
  2. $`A \equiv \lnot (\lnot A)`$ だから、$`\lnot A`$ を仮定して矛盾を導けば $`A`$ の証明になる(背理法)。
  3. $`A\lor B`$ を仮定し $`C`$ を証明したいとき、$`A`$ から $`C`$ と $`B`$ から $`C`$ に分けて証明する(場合分け)。
  4. $`\exists x\in X. A(x)`$ を仮定し $`C`$ を証明したいとき、$`(x: X)`$ という宣言と $`A(x)`$ という条件が付いた条件付き変数を導入して $`C`$ を証明する。変数名はリネームしたほうが分かりやすい($`x`$ を $`a`$ にリネームとか)。

$`\lnot (\lnot A) \equiv A`$ (二重否定の法則)のような、よく知られた同値性の法則がある。

  1. ド・モルガンの法則 $`\lnot (A \land B) \equiv (\lnot A)\lor (\lnot B)`$
  2. ド・モルガンの法則 $`\lnot (A \lor B) \equiv (\lnot A)\land (\lnot B)`$
  3. ド・モルガンの法則 $`(\lnot \forall x\in X. A(x) )\equiv (\exists x\in X. \lnot A(x))`$
  4. ド・モルガンの法則 $`(\lnot \exists x\in X. A(x) )\equiv (\forall x\in X. \lnot A(x) )`$
  5. 含意の書き換え $`(A \Imp B )\equiv (\lnot A \lor B)`$
  6. 対偶の法則 $`(A \Imp B) \equiv (\lnot B \Imp \lnot A)`$

ウダウダ言ってないで、憶えて使う、使って憶える