便利な (?) 論理演算 - ノリの悪い日記

自分だけそう思っているにすぎないかも知れないけれど, 便利だと思っている論理演算について書いてみる. なお, ここでは恒真命題は $I$ , 恒偽命題は $O$ で表わすことにする.

まず, 単項命題 $A$ , $\overline{A}$ の書き換えとして,

$A \\ \iff O \vee A \\ \iff \overline{I} \vee A \\ \iff I \Rightarrow A$

これは, $A$ が前提を必要とせず, 成り立つことを示している.

$\overline{A} \\ \iff \overline{A} \vee O \\ \iff A \Rightarrow O$

これは, A が正しいと仮定すると矛盾することを示している.

便利だと思っているのは, 含意命題の前件で連言になっている命題を否定して, 後件に移動して選言として加えても, また, その逆の操作を行なっても同値だというものである. つまり,

$A \wedge C \Rightarrow B \\ \iff A \Rightarrow B \vee \overline{C}$

$A \Rightarrow B \vee D \\ \iff A \wedge \overline{D} \Rightarrow B$

以上二つをまとめて, 公式化しておくと,

$A \wedge C \Rightarrow B \vee D \\ \iff A \wedge \overline{D} \Rightarrow B \vee \overline{C}$

となる. 一応, 証明しておくと,

$A \wedge C \Rightarrow B \vee D \\ \iff( \overline{A \wedge C} )\vee (B \vee D) \\ \iff( \overline{A} \vee \overline{C} )\vee (B \vee D) \\ \iff( \overline{A} \vee D )\vee (B \vee \overline{C}) \\ \iff( \overline{A \wedge \overline{D} } )\vee (B \vee \overline{C}) \\ \iff A \wedge \overline{D} \Rightarrow B \vee \overline{C}$

これを使うと, たとえば, $P \Rightarrow Q$ の間接証明には次のやり方があることがわかる.

$P \Rightarrow Q \\ \iff I \wedge P \Rightarrow O \vee Q \\ \iff I \wedge \overline {Q} \Rightarrow O \vee \overline{P} \\ \iff \overline {Q} \Rightarrow \overline {P}$

これは対偶による証明である. 他にも,

$P \Rightarrow Q \\ \iff P \wedge P \Rightarrow O \vee Q \\ \iff P \wedge \overline {Q} \Rightarrow \overline{P}$

$P \Rightarrow Q \\ \iff P \Rightarrow Q \vee Q \\ \iff P \wedge \overline {Q} \Rightarrow Q$

$P \Rightarrow Q \\ \iff P \Rightarrow O \vee Q \\ \iff P \wedge \overline {Q} \Rightarrow O$

が考えられる. 背理法とは, 上の $3$ つ全部を指すのか, 最後のものだけを指すのかわからないが, $3$ つとも背理法とまとめる方が普通のような気がする. 実際,

$P \wedge \overline {Q} \Rightarrow P$
$P \wedge \overline {Q} \Rightarrow \overline{Q}$

は自明なので, $3$ 番目の形に帰着できる. 同様なので, 最初のものだけ示せば,

$(P \wedge \overline {Q} \Rightarrow \overline{P}) \wedge (P \wedge \overline {Q} \Rightarrow P) \\ \iff P \wedge \overline {Q} \Rightarrow P \wedge \overline{P} \\ \iff P \wedge \overline {Q} \Rightarrow O \\ \iff P \Rightarrow Q$

である.

単項命題の背理法は,

$P \\ \iff I \Rightarrow P \\ \iff I \Rightarrow P \vee P \\ \iff \overline{P} \Rightarrow P$

$P \\ \iff I \Rightarrow P \\ \iff I \Rightarrow O \vee P \\ \iff \overline{P} \Rightarrow O \\ \iff \overline{\overline{P}}$

である.

他にも次のような公式は, ほぼ自明である.

$P \wedge Q \Rightarrow R \\ \iff P \Rightarrow \overline{Q} \vee R \\ \iff P \Rightarrow (Q \Rightarrow R)$

また,

$P \wedge Q \Rightarrow R \\ \iff Q \Rightarrow \overline{P} \vee R \\ \iff Q \Rightarrow ( P \Rightarrow R)$

※ 含意の括弧は省略できない.
$\displaystyle{ (P \Rightarrow Q) \Rightarrow R \\ \iff (\overline{P} \vee Q) \Rightarrow R \\\iff \left\{ \begin{array}{l} \overline{P} \Rightarrow R \\ Q \Rightarrow R \\ \end{array} \right.}$
//

このような論理演算を知っておくと, 直接証明とは違う別証明を考えるときに役立つことがある. たとえば, 中学生のとき, 「中点連結定理」というのを習ったが, その逆である,

$(AM = MB) \wedge (MN \parallel BC) \\ \quad \Rightarrow AN = NC$

が真であることを証明するのに,

$(AM = MB) \wedge (AN \neq NC) \\ \quad \Rightarrow MN \nparallel BC$

を証明してもよい. 仮定によって $N$ は中点ではないのだから, 中点 $N'$ を別に取ることができる. そうすると「中点連結定理」により, $MN' \parallel BC$ である. $M$ を通って $BC$ に平行な線は平行線の公理によりただひとつであるから, $MN \nparallel BC$ である.

※ 背理法を使う簡単な受験問題をひとつだけやっておく.

【問】
$a, \ b$ は有理数のとき,

$a+b\sqrt{2}=0$ ならば $a=b=0$

であることを証明せよ. ただし, $\sqrt{2}$ は無理数である．

【解】
この問題を取り上げたのは, 証明すべき含意命題が,

$(a+b\sqrt{2}=0) \Rightarrow (a=0) \wedge (b = 0)$

となっていて, 結論が $\wedge$ で結ばれているからである. 一般に推論 (sequent) で,

$P_1,P_2, \cdots, P_m \Rightarrow Q_1, Q_2, \cdots, Q_n$

とカンマ ‘,’ で区切ってあったら, 前件 (仮定) の方は $\wedge$ , 後件 (結論) は $\vee$ として解釈するのが古典的である.

つまり, もし前件に $\vee$ , 後件に $\wedge$ が含まれていたら,

$(p \vee q) \Rightarrow r \iff (p \Rightarrow r) \wedge (q \Rightarrow r)$

または,

$p \Rightarrow (q \wedge r) \iff (p \Rightarrow q) \wedge (p \Rightarrow r)$

を使って命題を分解して複数命題として考えるということである.

※ 他には, 次のようなものが考えられる.

$\displaystyle{(p \wedge (a \Rightarrow b)) \Rightarrow q \\ \iff p \wedge (\overline{a} \vee b) \Rightarrow q \\ \iff (p \wedge \overline{a} ) \vee (p \wedge b) \Rightarrow q \\ \iff \left\{ \begin{array}{l} p \wedge \overline {a} \Rightarrow q\\ p \wedge b \Rightarrow q \\ \end {array} \right. \\ \\ \iff \left\{ \begin{array}{l} p \Rightarrow q \vee a\\ p \wedge b \Rightarrow q \\ \end {array} \right. }$
//

したがって, この場合も,

$\displaystyle{ \left\{ \begin{array}{l} a+b\sqrt{2}=0 \Rightarrow a=0\\ a+b\sqrt{2}=0 \Rightarrow b=0\\ \end{array} \right.}$

として考えればよい. ところが, この場合, 下の命題と $a+b\sqrt{2}=0$ を仮定すると, $b = 0$ が出て, そこから $a =0$ が出てくるので, $a+b\sqrt{2}=0 \Rightarrow a=0$ である. したがって, (下の命題 ) $\Rightarrow$ (上の命題) である. このことから,

$\displaystyle{ \left\{ \begin{array}{l} a+b\sqrt{2}=0 \Rightarrow a=0\\ a+b\sqrt{2}=0 \Rightarrow b=0\\ \end{array} \right.} \\ \iff a+b\sqrt{2}=0 \Rightarrow b=0$

となり, 結局最後の命題だけを証明すればよい ( $p \Rightarrow q$ が真のとき, $p \wedge q \iff p$ というのは, この場合だけでなくよく使う).

更に,

$a+b\sqrt{2}=0 \Rightarrow b=0 \\ \iff (a+b\sqrt{2}=0) \wedge (b \neq 0) \Rightarrow O$

なので,

$a + b\sqrt{2}=0$ かつ $b \neq 0$ を仮定すると,

$\sqrt{2}=-\dfrac{a}{b}$

となって, $\sqrt{2}$ が有理数で表わせない実数 (無理数) であることと矛盾する. したがって証明された. //

以上, 証明すべき含意命題は, 前件 (仮定) の方は $\wedge$ , 後件 (結論) は $\vee$ である複数の命題に分割でき, それぞれの命題は,

$A \wedge C \Rightarrow B \vee D \\ \iff A \wedge \overline{D} \Rightarrow B \vee \overline{C}$

を使って同値変形できることを述べた.