タグ: 論理学

投稿日:

連立方程式の解法は…「文字を減らす」方針？その２

下の記事を見直してたらちょっと気になったので一言．「文字を減らす」という方針について以前の記事に追加です．

\[\begin{align*}
&\begin{cases}
f(s,~t)=0\\
s=g(x,y)\\
t=h(x,y)
\end{cases}
\Longleftrightarrow
\begin{cases}
f(g(x,y),~h(x,y))=0\\
s=g(x,y)\\
t=h(x,y)
\end{cases}
\end{align*}
\]

です．

（理由）
\(\Rightarrow\)は第１式の\(s\)と\(t\)に第２，３式により\(s=g(x,y),~t=h(x,y)\)をそれぞれ代入すれば得られます．
\(\Leftarrow\)はは第１式の\(g(x,y)\)と\(h(x,y)\)を第２，３式により\(g(x,y)=s,~h(x,y)=t\)とおき直せば得られます．（ちなみにこれは，もし第２，３式\(g(x,y)=s,~h(x,y)=t\)がなければ逆が成り立たない，すなわち
\[
\begin{cases}
f(s,~t)=0\\
s=g(x,y)\\
t=h(x,y)
\end{cases}
\Longrightarrow
f(g(x,y),~h(x,y))=0\\
\]
であることを意味します．）

…（同値性という観点から言えば）文字は別に減らしてなんかいないことに注意．

しかしもし，
\[
\exists s \exists t\begin{cases}
f(s,~t)=0\\
s=g(x,y)\\
t=h(x,y)
\end{cases}
\]
なら，存在記号を処理することで，

\[\exists s \exists t\begin{cases}
f(s,~t)=0\\
s=g(x,y)\\
t=h(x,y)
\end{cases}
\Longleftrightarrow
f(g(x,y),~h(x,y))=0
\]

となります．見た目通り，文字\(s,t\)は消えます．

投稿日:

「ならば」の否定

問題
\(a,~b\)を有理数とするとき，\(\sqrt{3}\)が無理数であることを用いて，「\(a+b\sqrt{3}=0\)ならば\(a=0\)かつ\(b=0\)」であることを証明せよ．

定番問題です。解答を見ると，次のように始まります。

\(b\neq 0\)とすると…

 

賢明な生徒であればここで「背理法かな？」気付くはず。それは正しいです。では，与えられた命題「\(a+b\sqrt{3}=0\)ならば\(a=0\)かつ\(b=0\)」の否定が「\(b\neq 0\)」ということでしょうか？…うーん明らかに違う気が。。

「\(a+b\sqrt{3}=0\)ならば\(a=0\)かつ\(b=0\)」の否定がどうなるかに注意しつつ，証明を作ってみます。与えられた命題は論理記号を用いて「\(a+b\sqrt{3}=0\Longrightarrow a=0\land b=0\)」と書けることに注意して，

証明（その１）

\[\overline{ a+b\sqrt{3}=0 \Longrightarrow a=0 \land b=0}\]と仮定する．
\begin{align}
&\overline{ a+b\sqrt{3}=0 \Longrightarrow a=0 \land b=0}\\
\Longleftrightarrow~ &\overline{\overline{a+b\sqrt{3}=0} \lor (a=0 \land b=0)}&(\Rightarrow \text{の定義})\\
\Longleftrightarrow~ &a+b\sqrt{3}=0 \land \overline{a=0 \land b=0}&(\text{ドモルガンの法則})\\
\Longleftrightarrow~ &a+b\sqrt{3}=0 \land (a \neq 0 \lor b \neq 0)&(\text{ドモルガンの法則})\\
\Longleftrightarrow~ &(a+b\sqrt{3}=0 \land a \neq 0 ) \lor (a+b\sqrt{3}=0 \land b \neq 0)&(\text{分配法則})\\
\Longleftrightarrow~ &\left(1+\frac{b}{a}\sqrt{3}=0 \land a \neq 0 \right) \lor \left(\frac{a}{b}+1\sqrt{3}=0 \land b \neq 0\right)\\
\Longleftrightarrow~ &\left(\frac{-3b}{a}=\sqrt{3} \land a \neq 0 \right) \lor \left(-\frac{a}{b}=\sqrt{3} \land b \neq 0\right)\\
\Longleftrightarrow~ &\bot \lor \bot\\
\Longleftrightarrow~ &\bot
\end{align}

したがってもとの命題は正しい．

証明終

\(\bot\)は矛盾命題を表します。

…では，模範解答の「\(b\neq 0\)とすると～」は一体何をしているのでしょうか？これはおそらく以下のようだと思われます：

証明（その２）

\[
\begin{align}
&a+b\sqrt{3}=0 \Rightarrow b=0 \\
\overset{(\ast)}\Longleftrightarrow~&a+b\sqrt{3}=0 \Rightarrow a+b\sqrt{3}=0 \land b=0 \\
\Longleftrightarrow~ &a+b\sqrt{3}=0 \Rightarrow a=0 \land b=0
\end{align}
\]
であるから，\[a+b\sqrt{3}=0 \Rightarrow b=0\]を示せばよい．この命題を否定すると\[a+b\sqrt{3}=0 \land b\neq 0\]であるが，
\[a+b\sqrt{3}=0 \land b\neq 0\Longleftrightarrow\sqrt{3}=-\frac{a}{b} \land b\neq 0\]これは矛盾である．

証明終

上の証明における\((\ast)\)は，（直観的にはまあ明らか，ではありますが）\[(P\Rightarrow Q) \Longleftrightarrow (P\Rightarrow P \land Q)\]という論理式によります。いずれにしても，ならば（含意）の否定というものを学んでいない以上，上のような証明は作りようがない。いきなり「\(b \neq 0\)とする」なんて言われても納得しようがないし，安易に納得してはいけない。ちなみにこの解答の脚注にはこんな一言が載っています。「結論が\(p\)かつ\(q\)という命題を背理法を用いて証明するときは\(\overline{p}\)または\(\overline{q}\)のみを仮定して矛盾を導けばよい」…でもそうすべき理由とその方針が正しい理由は？

まあ，ある程度はブラックボックス化するのはやむを得ないとはいえ，ここは端折るところではないのでは…と思います。さもなければそもそも\(P\Rightarrow Q \land R\)なんて命題の証明なんて取り扱わないで欲しい。生徒に説明するとき誤魔化すハメになりほんと迷惑極まりない。

 

投稿日:

否定をとることの難しさと論理式の有用性

背理法で示す方針の場合，与えられた命題を否定する必要がありますが，これが意外と難しいケースがあります．

\(xy\)平面内の相異なる４点\(P_1,~P_2,~P_3,~P_4\)とベクトル\(\overrightarrow{v}\)に対し，\(k\neq m\)のとき\(\overrightarrow{P_kP_m}\cdot \overrightarrow{v}\neq 0\)が成り立っているとする．このとき，\(k\)と異なるすべての\(m\)に対し\[\overrightarrow{P_kP_m}\cdot\overrightarrow{v}<0\]が成り立つような点\(P_k\)が存在することを示せ．（京都大・文）

この問題の場合，与えられた命題は

「\(k\neq m\)のとき\(\overrightarrow{P_kP_m}\cdot \overrightarrow{v}\neq 0\)が成り立っているとする．このとき，\(k\)と異なるすべての\(m\)に対し\(\overrightarrow{P_kP_m}\cdot\overrightarrow{v}<0\)が成り立つような点\(P_k\)が存在する」

です．この否定をとればいいわけですが，どこからどう手をつければいいのかいまいちわからない，できたとしてもなんだか不安…．そこで，ここでは論理記号を用いて捉えてみます．与えられた命題を次の４つの部分に分けて翻訳していきます．

      1. \(k\neq m\)のとき\(\overrightarrow{P_kP_m}\cdot \overrightarrow{v}\neq 0\)が成り立っているとする．
      2. このとき，
      3. \(k\)と異なるすべての\(m\)に対し\(\overrightarrow{P_kP_m}\cdot\overrightarrow{v}<0\)が成り立つ
      4. ような点\(P_k\)が存在する

１．「\(k\neq m\)のとき\(\overrightarrow{P_kP_m}\cdot \overrightarrow{v}\neq 0\)が成り立っているとする」は
\[k\neq m \Longrightarrow \overrightarrow{P_kP_m}\cdot \overrightarrow{v}\neq 0\]

２．「このとき」は\[\Longrightarrow\]

３．「\(k\)と異なるすべての\(m\)に対し\(\overrightarrow{P_kP_m}\cdot\overrightarrow{v}<0\)が成り立つ」は\[\forall m \big[m\neq k \Longrightarrow \overrightarrow{P_kP_m}\cdot\overrightarrow{v}<0\big]\]

４．「ような点\(P_k\)が存在する」は
\[\exists P_k\]

ですから，以上を繋げると，
\[\big(k\neq m \Longrightarrow \overrightarrow{P_kP_m}\cdot \overrightarrow{v}\neq 0\big)\Longrightarrow\exists P_k\forall m \big[m\neq k \Longrightarrow \overrightarrow{P_kP_m}\cdot\overrightarrow{v}<0\big]\]
となります．これの否定を考えます．
\[\overline{\big(k\neq m \Longrightarrow \overrightarrow{P_kP_m}\cdot \overrightarrow{v}\neq 0\big)\Longrightarrow\exists P_k\forall m \big[m\neq k \Longrightarrow \overrightarrow{P_kP_m}\cdot\overrightarrow{v}<0\big]}\]

ここで，一般に
\[
\begin{align*}
&(A\rightarrow B)\Longleftrightarrow \overline{A}\lor B
\end{align*}
\]
ですから，
\[\overline{A\rightarrow B}\Longleftrightarrow \overline{\overline{A} \lor B}\Longleftrightarrow A \land \overline{B}\]
です．したがって，
\[
\begin{align*}
&\overline{\big(k\neq m \Longrightarrow \overrightarrow{P_kP_m}\cdot \overrightarrow{v}\neq 0\big)\Longrightarrow\exists P_k\forall m \big[m\neq k \Longrightarrow \overrightarrow{P_kP_m}\cdot\overrightarrow{v}<0\big]}\\
\Longleftrightarrow~&\big(k\neq m \Longrightarrow \overrightarrow{P_kP_m}\cdot \overrightarrow{v}\neq 0\big)\land \overline{\exists P_k\forall m \big[m\neq k \Longrightarrow \overrightarrow{P_kP_m}\cdot\overrightarrow{v}<0\big]}\\
\Longleftrightarrow~&\big(k\neq m \Longrightarrow \overrightarrow{P_kP_m}\cdot \overrightarrow{v}\neq 0\big)\land \forall P_k\exists m \big[\overline{m\neq k \Longrightarrow \overrightarrow{P_kP_m}\cdot\overrightarrow{v}<0}\big]\\
\Longleftrightarrow~&\big(k\neq m \Longrightarrow \overrightarrow{P_kP_m}\cdot \overrightarrow{v}\neq 0\big)\land \forall P_k\exists m \big[m\neq k \land \overline{\overrightarrow{P_kP_m}\cdot\overrightarrow{v}<0}\big]\\ \Longleftrightarrow~&\big(k\neq m \Longrightarrow \overrightarrow{P_kP_m}\cdot \overrightarrow{v}\neq 0\big)\land \forall P_k\exists m \big[m\neq k \land \overrightarrow{P_kP_m}\cdot\overrightarrow{v}\geq0\big]\\ \Longleftrightarrow~&\big(k\neq m \Longrightarrow \overrightarrow{P_kP_m}\cdot \overrightarrow{v}\neq 0\big)\land \forall P_k\exists m \big[(m\neq k \land \overrightarrow{P_kP_m}\cdot\overrightarrow{v}>0)\lor(m\neq k \land\overrightarrow{P_kP_m}\cdot\overrightarrow{v}=0)\big]\\
\Longleftrightarrow~&\big(k\neq m \Longrightarrow \overrightarrow{P_kP_m}\cdot \overrightarrow{v}\neq 0\big)\land \forall P_k\big[\exists m(m\neq k \land \overrightarrow{P_kP_m}\cdot\overrightarrow{v}>0)\lor\exists m(m\neq k \land\overrightarrow{P_kP_m}\cdot\overrightarrow{v}=0)\big]\\
\Longleftrightarrow~&\big(k\neq m \Longrightarrow \overrightarrow{P_kP_m}\cdot \overrightarrow{v}\neq 0\big)\land \forall P_k\exists m(m\neq k \land \overrightarrow{P_kP_m}\cdot\overrightarrow{v}>0)
\end{align*}
\]
となります．

もとの問題の解説では他の解法があったのですが，別解としての上記のように否定をとり矛盾を示す方針が載っていました．が，その「否定をとる」という作業の時点で既に難しく，ならば論理式で記述したらどうなるかなと思い考えてみました．見た目こそ厳ついものの，論理式の扱いに慣れさえすればとても分かりやすく明解です．

投稿日:

命題（条件）の分配法則

命題や条件は，分配することができます．すなわち，
\[(p\lor q)\land r \Longleftrightarrow (p \land r)\lor (q \land r)\]や\[(p\land q)\lor r \Longleftrightarrow (p \lor r)\land (q \lor r)\]などが成り立ちます．

証明

真理表で確認します．
まず，\(p,~q,~r\)の真偽は\(2^3=8\)通りあることに注意して，

と書けます．見やすさのためにFを赤色にしました．
次に\(p\lor q\)を書き，その列を埋めましょう．\(p\)の列と\(q\)の列に着目して，\(\lor\)の定義に従うと，

と書けます．次に\((p\lor q)\land r\)を書き，その列を埋めます．\(p\lor q\)と\(r\)の列に着目して，\(\land\)の定義に従うと，

と書けます．
今度は\( (p \land r)\lor (q \land r)\)について調べます．そのためにはまず\((p \land r)\)と\((q \land r)\)を調べなくてはなりません．なのでまず，\(p\lor r\)と\(q \land r\)を書き，それぞれの列を埋めましょう．\(p\)の列と\(r\)の列，そして\(q\)の列と\(r\)の列に着目して\(\land\)の定義に従うと，

と書けます．さて，準備ができたので\( (p \land r)\lor (q \land r)\)を書いてその列を埋めていきましょう．先ほど書いた\( (p \land r)\)と\((q \land r)\)の列に着目して\(\lor\)の定義に従うと，

と書けます．

さて，ここで\((p\lor q)\land r\)と\((p \land r)\lor (q \land r)\)の列に着目しましょう．すると，真理値が同じですね．同値\(\leftrightarrow\)の定義より，\((p\lor q)\land r\)と\((p \land r)\lor (q \land r)\)が同値であることが分かります．

これで，\((p\lor q)\land r \Longleftrightarrow (p \land r)\lor (q \land r)\)であることが証明できました．同様にして，\((p\land q)\lor r \Longleftrightarrow (p \lor r)\land (q \lor r)\)が証明できます．

投稿日:

「すべて」「存在する」の否定

以下，\(x\in \{x_1,~x_2,~x_3,\cdots ,x_n\}\)とする．

\(\overline{\forall x~p(x)} \Longleftrightarrow \exists x~\overline{p(x)}\)

証明

\[
\begin{align*}
&\overline{\forall x~p(x)}\\
\Longleftrightarrow~&\overline{p(x_1)\land p(x_2)\land p(x_2)\land \cdots \land p(x_n)}\\
\Longleftrightarrow~&\overline{p(x_1)}\lor \overline{p(x_2)}\lor \overline{p(x_2)}\lor \cdots \lor\overline{p(x_n)}\\
\Longleftrightarrow~&\exists x~\overline{p(x)}&\textbf{（証明終）}
\end{align*}
\]

\(\overline{\exists x~p(x)} \Longleftrightarrow \forall x~\overline{p(x)}\)

証明

\[
\begin{align*}
&\overline{\exists x~p(x)}\\
\Longleftrightarrow~&\overline{p(x_1)\lor p(x_2)\lor p(x_2)\lor \cdots \lor p(x_n)}\\
\Longleftrightarrow~&\overline{p(x_1)}\land \overline{p(x_2)}\land \overline{p(x_2)}\land \cdots \land\overline{p(x_n)}\\
\Longleftrightarrow~&\forall x~\overline{p(x)}&\textbf{（証明終）}
\end{align*}
\]

\(\forall\)（すべての）を否定すると\(\exists\)（存在する）となり，\(\exists\)（存在する）を否定すると\(\forall\)（すべての）となります．

投稿日:

\(\exists x \forall y\)と\(\forall y \exists x\)の違い

並びが違うだけのように見えますが意味は全く異なります．\(p(x,~y)\)を条件とします．

\(\exists x \forall y~p(x,~y)\)は「\(x\)が存在して，任意の\(y\)に対して\(p(x,~y)\)が成り立つ」となります．最初に「存在して」と言っているあたりが慣れないと気持ち悪いと思います．なので言い換えると，「任意の\(y\)に対して\(p(x,~y)\)が成り立つような\(x\)が，\(y\)とは無関係に存在する」となります．

ポイントは，\(x\)は\(y\)に依存していないということです．

他方，\(\forall y \exists x ~p(x,~y)\)は「どんな\(y\)に対しても，それに対応して\(x\)が存在して，\(p(x,~y)\)が成り立つ」ということです．やはり「存在して」が先に来ると違和感がある人は「\(p(x,~y)\)が成り立つような\(x\)が，\(y\)に応じて存在する」と言い換えればよいと思います．

こちらは\(x\)は\(y\)に依存しているということがポイントです．

【具体例】

条件\(p(x,~y)\)を「\(x\)は\(y\)の親である」という条件とします（\(x,y\in \text{人類}\)）．このとき，

\(\exists x \forall y~p(x,~y)\)は，
\[\exists x \forall y~[~\text{\(x\)は\(y\)の親である}~]\]
となります．これを翻訳すると「人間\(x\)が存在して，その人間\(x\)はすべての人間\(y\)の親である」，あるいは「どんな人間\(y\)にとっても親となる人間\(x\)が（その人間\(y\)が誰であるかとは無関係に）存在する」となります．

・・・この命題は常識的に考えれば真とは言いづらいですね＾＾；宗教のようなある種の信仰を持っている人にとってはこの命題も真と言えるのかもしれませんが．

他方，\(\forall y \exists x ~p(x,~y)\)は，

\[\forall y \exists x ~[~\text{\(x\)は\(y\)の親である}~]\]

これを翻訳すると「どんな人間\(y\)に対しても，その人間\(y\)に対応して\(x\)という人間が存在し，\(x\)と\(y\)との間に親子関係が成り立つ」あるいは「どんな人間\(y\)に対しても，その人間に応じて親\(x\)が存在する」となります．

・・・この命題は明らかに真でしょう．（クローン人間など特殊な例を考えない限り）物理的に人間から生まれなかった人間はいませんから．

以上，\(\exists x \forall y\)と\(\forall y \exists x\)の違い，それは\(x\)と\(y\)の間に関係（対応）があるかないか，ということです！

投稿日:

「かつ」「または」の分配法則

\(p,~q,~r,~s\)を命題とする．このとき，
\[p\land (q \lor r) \Longleftrightarrow (p\land q) \lor (p\land r)\]
が成り立ちます．高校数学的にはベン図で証明（というか説明？）しますが，論理学的には真理値表で証明します．

他にも，\[p\lor (q \land r) \Longleftrightarrow (p\lor q) \land (p\lor r)\]や\[(p\lor q) \land (r \lor s) \Longleftrightarrow (p\land r) \lor (q\land r) \lor (p \land s) \lor (q \land s)\]や
\[(p\land q) \lor (r \land s) \Longleftrightarrow (p\lor r) \land (q\lor r) \land (p \lor s) \land (q \lor s)\]なども同様に成り立ちます．数や文字の分配法則にそっくりですね．証明はこちら．

投稿日:

存在記号は分配できるか？

できます（かつ（\(\land\)）に関して）．なぜなら，

\[\forall x[p(x)\land q(x)]~\Longleftrightarrow \forall x p(x)\land \forall x q(x)\]であるから，この命題の待遇を考えると，

\[\lnot(\forall x[p(x)\land q(x)])~\Longleftrightarrow \lnot(\forall x p(x)\land \forall x q(x))\]

すなわち

\[\exists x[\lnot p(x)\lor \lnot q(x)]~\Longleftrightarrow \exists x \lnot p(x)\lor \exists x \lnot q(x)\]

となります．\(\lnot\)は否定を表す記号です．ですから，

\[\exists x[\overline{p(x)}\lor \overline{q(x)}]~\Longleftrightarrow \exists x \overline{ p(x)}\lor \exists x \overline{q(x)}\]

とも書けますね．見やすさのために\(\overline{p(x)}\)を\(p(x)\)に，\(\overline{q(x)}\)を\(q(x)\)に改めて書き換えれば，
\[\exists x[p(x) \lor q(x)]~\Longleftrightarrow \exists x p(x)\lor \exists x q(x)\]
となります．

注意：ただし，存在記号はかつ（\(\land\)）に関しては分配できません！すなわち，\[\exists x[p(x) \land q(x)] \Longrightarrow \exists x p(x) \land \exists xq(x)\]であって，この逆は成り立ちません．これは具体例を考えれば分かりやすい．仮に全体集合をあるクラスだとして，\(p(x)\)を「\(x\)は勉強が得意」\(q(x)\)を「\(x\)はスポーツが得意」だとします．すると，\(\exists x[p(x) \land q(x)]\)は「勉強もスポーツも両方得意な生徒がいる」となり，\(\exists x p(x) \land \exists xq(x)\)は「勉強が得意な生徒がいて，かつ，スポーツが得意な生徒もいる」となります．\(\Longrightarrow\)が成り立つのは当たり前でしょう．\(\Longleftarrow\)について考えます．「（そのクラスに）勉強が得意な生徒がいて，スポーツが得意な生徒もいるのなら，勉強もスポーツも両方得意な生徒がいる」となりますが，これは正しいでしょうか．少し考えればわかるように明らかに正しくないですね．反例．仮定を満たすクラスとして，「勉強は超得意だけどスポーツはダメダメな秀才君がいて，スポーツは超得意だけど勉強はからっきしの脳筋君がいる．そしてクラスの他の生徒たちは勉強もスポーツもとくに得意とは言えない，いたってフツーの生徒，そんなクラスが例えば考えられます．このクラスには明らかに「勉強もスポーツも両方得意な生徒」はいることにはなりませんね．

投稿日:

任意記号は分配できるか？

\(p(x),~q(x)\)を条件とする．\(\forall\)は「任意記号（または全称記号）」と呼び，「任意の（Any），すべての(for All)」という意味です．Aをひっくり返して\(\forall\)．このとき，

\[\forall x[p(x)\land q(x)]~\Longleftrightarrow \forall x p(x)\land \forall x q(x)\quad \cdots (\ast)\]

が成り立ちます．例えば，\(p(x)\)を「\(x\)は勉強が得意」という条件，\(q(x)\)を「\(x\)はスポーツが得意」という条件だとしましょう．このとき，\(\forall x[p(x)\land q(x)]\)は

\[\text{全員，勉強とスポーツ両方得意}\]

という意味になります．イメージし易さのため，\(x\in \text{（とあるクラス）}\)とすると，

\[\text{このクラスの全員が，勉強とスポーツ両方得意}\]

となります．いわば，スーパーマンみたいな奴だけで構成されたクラスですね，そんなクラスをイメージしてください．

他方，\(\forall x p(x)\land \forall x q(x)\)は\[\text{このクラスの全員が勉強が得意で，かつ，このクラスの全員がスポーツが得意}\]という意味になります．

これらの「翻訳」に従って，上の\((\ast)\)を記述し直してみると，

\begin{align*}
&\text{このクラスの全員が，勉強とスポーツ両方得意}\\
\Longleftrightarrow~&\text{このクラスの全員が勉強が得意で，かつ，このクラスの全員がスポーツが得意}
\end{align*}

ということになります．このようにイメージすると，\((\ast)\)の\(\Longleftarrow\)も\(\Longrightarrow\)もどちらも成り立つこと，すなわち同値であることが容易に納得できます．

注意：ただし，任意記号はまたは（\(\lor\)）に関しては分配できません！

© 2024 佐々木数学塾, All rights reserved.