数学における証明のポイント【随時更新】

命題論理に関する証明のポイント

1. 真理表（または評価）の計算$ $
   1.1 $\lor,\land,\Rightarrow,\neg$（および後述の $\Leftrightarrow$）の真偽は、
   以下の定義（真理表または評価規則）に還元して判断する。
   必要最小限の列を、定義に従って機械的に埋める（$\neg$、$\lor$、$\land$、$\Rightarrow$、$\Leftrightarrow$）。
   $$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline P & Q & \neg P & P \lor Q & P \land Q & P \Rightarrow Q & Q \Rightarrow P & P \Leftrightarrow Q \\ \hline T & T & F & T & T & T & T & T \\ \hline T & F & F & T & F & F & T & F \\ \hline F & T & T & T & F & T & F & F \\ \hline F & F & T & F & F & T & T & T \\ \hline \end{array} $$
   1.2 特に $\Leftrightarrow$ は基本記号として扱わず、
   $$ (A\Leftrightarrow B)\ \text{は}\ (A\Rightarrow B)\land(B\Rightarrow A)\ \text{の略記} $$
   として定義に接続して扱う。
   $ $
2. 定義への接続で結論する$ $
   2.1 トートロジーのときは「全ての評価 $v$ で $v(\cdot)=T$」を確認して結論する。
   2.2 矛盾式のときは「全ての評価 $v$ で $v(\cdot)=F$」を確認して結論する。
   2.3 同値を示したいときは、任意の評価 $v$ に対して
   $$ v(f\Leftrightarrow g)=T\ \Longleftrightarrow\ v(f)=v(g) $$
   が成り立つ（すなわち $\forall v$ で成り立つ）ことを用いて「全ての評価 $v$ で $v(f)=v(g)$」を結論する。
   同値の定義より、このとき $f\equiv g$ が従う。
   $ $
3. 命題 $P\Rightarrow Q$ を証明するパターン$ $
   3.1 $P$ を仮定し、そのとき必ず $Q$ が成り立つことを示す（直接法）。
   3.2 $\neg P$ を示し、含意 $P\Rightarrow Q$ は $Q$ の真偽に関わらず常に真となることを結論づける（空虚に真）。
   3.3 対偶 $\neg Q\Rightarrow \neg P$ を証明して結論する（$P\Rightarrow Q$ と同値である）。
   $ $
4. 命題 $P\Leftrightarrow Q$ を証明するパターン$ $
   4.1 同値変形（$\equiv$）の連鎖により、$P$ と $Q$ の真偽が常に一致することを示して結論する。
   4.2 次の定義に従い、$P\Rightarrow Q$ と $Q\Rightarrow P$ の両方を証明する。
   $$ (P \Rightarrow Q) \land (Q \Rightarrow P) $$
   $ $
5. 背理法（矛盾を導く事による証明）$ $
   5.1 ある結論 $C$ を示したいとき、$\neg C$ を仮定して矛盾を導き、よって $C$ が成り立つと結論する。
   $ $
6. 「必要性・十分性」による証明の進め方$ $
   6.1 必要性：主張 $P\Leftrightarrow Q$ を示したいとき、まず $P\Rightarrow Q$ を示す(「$P$ を仮定して $Q$ を導く」)。
   6.2 十分性：次に $Q\Rightarrow P$ を示す(「$Q$ を仮定して $P$ を導く」)。
   6.3 両方向が示せたら、定義より $P\Leftrightarrow Q$ が結論できる。
   $ $
7. 同値変形を用いる場面$ $
   7.1 （古典論理では）含意は次で置き換えられる。
   $$ A\Rightarrow B\ \equiv\ \neg A\lor B $$
   7.2 ド・モルガン則で連言と否定を変換する。
   $$ \neg(A\land B)\ \equiv\ \neg A\lor \neg B,\quad \neg(A\lor B)\ \equiv\ \neg A\land \neg B $$
   7.3 二重否定の除去
   $$ \neg\neg A\ \equiv\ A $$
   7.4 対偶
   $$ A\Rightarrow B\ \equiv\ \neg B\Rightarrow \neg A $$
   7.5 同値記号の分解と展開
   $$ A\Leftrightarrow B\ \equiv\ (A\Rightarrow B)\land(B\Rightarrow A) $$
   $$ A\Leftrightarrow B\ \equiv\ (A\land B)\lor(\neg A\land\neg B) $$
   7.6 可換則
   $$ A\lor B\ \equiv\ B\lor A,\qquad A\land B\ \equiv\ B\land A $$
   7.7 結合則
   $$ (A\lor B)\lor C\ \equiv\ A\lor(B\lor C),\qquad (A\land B)\land C\ \equiv\ A\land(B\land C) $$
   7.8 分配則
   $$ A\land(B\lor C)\ \equiv\ (A\land B)\lor(A\land C) $$
   $$ A\lor(B\land C)\ \equiv\ (A\lor B)\land(A\lor C) $$
   7.9 冪等則
   $$ A\lor A\ \equiv\ A,\qquad A\land A\ \equiv\ A $$
   7.10 吸収則
   $$ A\lor(A\land B)\ \equiv\ A,\qquad A\land(A\lor B)\ \equiv\ A $$
   7.11 恒真と恒偽との単位則と零則
   $$ A\land \top\ \equiv\ A,\qquad A\lor \bot\ \equiv\ A $$
   $$ A\lor \top\ \equiv\ \top,\qquad A\land \bot\ \equiv\ \bot $$
   7.12 排中律と矛盾律
   $$ A\lor\neg A\ \equiv\ T,\qquad A\land\neg A\ \equiv\ F $$
   7.13 含意の入れ子の同値
   $$ (A\land B)\Rightarrow C\ \equiv\ A\Rightarrow(B\Rightarrow C) $$
   $ $
8. その他の基本$ $
   8.1 含意の基本：$P\Rightarrow P$ は常に真である。
   8.2 選言の扱い：$P$ から $P\lor Q$ を得る（選言導入）。
   8.3 連言の扱い：$(P\land Q)$ を仮定したら、$P$ と $Q$ をそれぞれ取り出して用いる(連言除去)。
   $ $

述語論理に関する証明のポイント

1. 全称命題と存在命題の証明の基本$ $
   1.1 全称命題 $\forall x\in S,\ P(x)$ を示すときは、任意の $a\in S$ を任意に取り（以後固定して）$P(a)$ を導く。
   　　※ 証明の最後は「$x\in U$ は任意であったから」などにより、全称的な結論（$\forall x\in U$ の形）へ戻して締める。
   　　反例で否定するなら、ある $a\in S$ を $1$つ示して $\neg P(a)$ を導く。
   1.2 存在命題 $\exists x\in S\ \text{s.t.}\ P(x)$ を示すときは、具体的な $a\in S$（証人）を構成し、
   　　$P(a)$ が成り立つことを確認する。
   　　存在を否定するなら、任意の $x\in S$ に対して $\neg P(x)$ を示す（すなわち $\forall x\in S,\ \neg P(x)$ を示す）。
   1.3 特に $S=\varnothing$ では、$\forall x\in S,\ P(x)$ は空虚に真、$\exists x\in S\ \text{s.t.}\ P(x)$ は常に偽となる。
   $ $
2. 全称量化子・存在量化子と否定の関係$ $
   2.1 量化の否定規則により、量化子と否定を交換する。
   $$ \neg\forall x\,A(x)\ \equiv\ \exists x\,\neg A(x),\quad \neg\exists x\,A(x)\ \equiv\ \forall x\,\neg A(x) $$
   $ $
3. 集合 $S$ を定義域とした命題の取り扱い$ $
   3.1 $S$ が空集合となり得る文脈では、量化を含む命題の真偽が $S=\varnothing$ で変化しないかを必ず確認する。
   　　必要に応じて $S=\varnothing$ と $S\neq\varnothing$ の場合分けを行うか、仮定 $S\neq\varnothing$ を明示する。
   $ $
4. 唯一性の証明$ $
   4.1 次の $2$ 段構成で証明する。
   　　STEP1 候補を構成して存在を示す：$\exists a\in S\ \text{s.t.}\ P(a)$
   　　STEP2 任意に $2$ 点を取り等号を導いて唯一性を示す：$\forall b\in S,\ \forall c\in S,\ \bigl((P(b)\land P(c))\Rightarrow b=c\bigr)$
   $ $
5. 量化（$\forall\varepsilon>0$）を含む主張の扱い$ $
   5.1 「任意の $\varepsilon>0$ に対して…」を示すときは、
   　　任意の $\varepsilon>0$ を $1$つ取って固定し、その $\varepsilon$ について不等式を示す。
   5.2 「任意の $\varepsilon>0$ に対して…」から結論を導くときは、
   　　仮定を全ての $\varepsilon>0$ に対して使えるものとして扱い、
   　　矛盾を作りたい場合は $\varepsilon$ を都合よく具体的に選ぶ。
   　　(例：$|a-b|>0$ のとき $\varepsilon:=|a-b|/2$、$a-b>0$ のとき $\varepsilon:=a-b$ など。)
   $ $

集合に関する証明のポイント

1. 全体集合（議論領域）を固定して量化を明確にする$ $
   1.1 議論の対象となる全体集合$U$をあらかじめ固定し、以後の集合は基本的にその部分集合として扱う（例：$A\subseteq U$）。
   　　※「任意の$x$」「ある$x$」のような量化は、必ずどの集合の上で量化しているか（範囲）に注意して読む。
   　　特に、同じ条件式でも、全体集合$U$の取り方により定まる集合が変わることがある。
   　　（例：$x^2+1=0$ の解集合は $U=\mathbb R$ と $U=\mathbb C$ で異なる）。
   $ $
2. 集合$S$で制限された量化の略記$ $
   2.1 $\forall x\in S\ P(x)$ は $\forall x\ (x\in S\Rightarrow P(x))$ の略記
   2.2 $\exists x\in S\ P(x)$ は $\exists x\ (x\in S\land P(x))$ の略記
   $ $
3. 「集合の主張」を「論理式の主張」に帰着する$ $
   3.1 内包的表記 $\{x\in U\mid P(x)\}$ を、次の形に機械的に戻す。
   $$ x\in\{y\in U\mid P(y)\}\ \Leftrightarrow\ \bigl(x\in U\land P(x)\bigr) $$
   3.2 記号 $a\in A,\ a\notin A,\ A=\varnothing,\ A\subseteq U$ などは、必要に応じて定義へ戻して論理式で扱う。
   3.3 特に空集合の定義は次の同値な形を使い分ける。
   $$ \begin{align} A&=\varnothing\ :\Leftrightarrow\ \neg\bigl(\exists x\in U \ \text{s.t.}\ (x\in A)\bigr)\\ A&=\varnothing\ :\Leftrightarrow\ \forall x\in U (x\notin A) \end{align} $$
   3.4 特に、空集合の性質
   $$ \forall x\ (x\in\varnothing\ \text{は偽}) $$
   したがって、任意の $x$ について
   $$ x\in\varnothing\ \Leftrightarrow\ \bot $$
   が成り立つ（$\bot$ は常に偽である命題定数）。
   $ $
   3.5 量化子の否定は次で処理する（必要に応じて使用）
   $$ \forall x \in U,\ \neg P(x)\ \Leftrightarrow\ \neg\bigl(\exists x\in U\ \text{s.t.}\ P(x)\bigr) $$
   3.6 集合の等式・包含・演算は、まず「任意の $x\in U$」を取り、$x$ が属する条件を論理式に直して証明。
   3.7 今後頻出する変換規則（集合演算 $\leftrightarrow$ 論理演算）
   $$ \begin{align} x\in A\cap B\ \Leftrightarrow\ (x\in A\land x\in B)\\ x\in A\cup B\ \Leftrightarrow\ (x\in A\lor x\in B)\\ x\in A\setminus B\ \Leftrightarrow\ (x\in A\land x\notin B)\\ \end{align} $$
   3.7 論理式に直した後は、命題論理の同値変形（結合法則・分配法則・ド・モルガン則など）で整理し、
   　　必要なら再び $x\in(\text{集合式})$ に戻す。
   $ $
4. 部分集合の定義に戻して示す$ $
   4.1 $A\subseteq B$ の定義は
   $$ A\subseteq B\ :\Leftrightarrow\ \forall x\in U\ (x\in A\Rightarrow x\in B) $$
   である。よって、$A\subseteq B$を示す標準形は次である。
   　STEP1：任意の$x\in U$を取る。
   　STEP2：$x\in A$を仮定する。
   　STEP3：定義や既知の同値変形を用いて$x\in B$を導く。
   　STEP4：よって$A\subseteq B$。
   $ $
5. 集合の等号は「両方向の包含」で示す$ $
   5.1 集合の等号の定義は
   を示せばよい。
   $$ \begin{align} &A=B\ :\Leftrightarrow\ \forall x\in U\ (x\in A\Leftrightarrow x\in B)\\ &A=B\ :(x\in A\ \Rightarrow\ x\in B)\land(x\in B\ \Rightarrow\ x\in A)\\ &A=B\ \Leftrightarrow\ (A\subseteq B)\land(B\subseteq A)\\ \end{align} $$
   である(厳密には、後者は定義と部分集合の定義から導かれる定理)。よって、$A=B$を示す標準形は次である。
   　STEP1：任意の$x\in U$を取る。
   　STEP2：$x\in A$を仮定し、定義や既知の同値変形を用いて$x\in B$を導く。これにより$A\subseteq B$が従う。
   　STEP3：任意の$x\in U$を取る。
   　STEP4：$x\in B$を仮定し、同様にして$x\in A$を導く。これにより$B\subseteq A$が従う。
   　STEP5：以上より$A\subseteq B$かつ$B\subseteq A$であるから$A=B$が成り立つ。
   $ $