【Sponsored Link】

論理と集合の基本5|「逆,裏,対偶」と対偶の利用

前の記事「論理と集合の基本4|命題と集合の関係」の続きです.

この記事では,命題の「逆」,「裏」,「対偶」について説明します.「逆」と「裏」に関しては目新しい重要な定理はないのですが,「対偶」に関しては次の定理が成り立ちます.

命題「p\Rightarrow q」の真偽は,その対偶「\overline{q}\Rightarrow\overline{p}」の真偽に一致する.

この事実は非常に重要で,「背理法」の根拠にもなっています.

【Sponsored Link】

条件の否定

「逆」,「裏」,「対偶」の説明に入る前に,「条件の否定」ついて説明します.

まず,条件pxについての条件であるとします.なんでも構いませんが,たとえば「整数xは偶数である」や「整数xは1以上かつ5以下である」などをイメージしてください.

このとき,条件xは条件pを満たさない」「条件pの否定」といい,\overline{p}で表します.

これだけではよく分からないと思いますので,例を挙げます.

たとえば,条件p_1

p_1:整数xは偶数である

ならば,「条件p_1の否定\overline{p_1}」は

\overline{p_1}:整数xは奇数である

となります.また,

p_2:整数xは1以上かつ5以下である

ならば,「条件p_2の否定\overline{p_2}」は

\overline{p_2}:整数xは0以下または6以上である

となります.

なお,「条件pの否定\overline{p}の否定\overline{\overline{p}}」はもとの条件pに一致します.つまり,p\Leftrightarrow\overline{\overline{p}}となります.

逆,裏,対偶

まずは定義です.

命題「p\Rightarrow q」に対し,命題

  1. q\Rightarrow p
  2. \overline{p}\Rightarrow\overline{q}
  3. \overline{q}\Rightarrow\overline{p}

をそれぞれp\Rightarrow qの逆」p\Rightarrow qの裏」p\Rightarrow qの対偶」という.

命題の形を見ると,命題「p\Rightarrow q」のpqを入れ替えたものが「逆」,pqをともに否定にしたものが「裏」,pqを入れ替えてともに否定にしたものが「対偶」ということになりますね.

逆,裏,対偶の関係

命題「p\Rightarrow q」,「q\Rightarrow p」,「\overline{p}\Rightarrow\overline{q}」,「\overline{q}\Rightarrow\overline{p}」の関係は下図のようになっています.

論理と集合の基本pic10

たとえば,図では「\overline{p}\Rightarrow\overline{q}」の対偶は,「q\Rightarrow p」となっていますが,これを実際に確かめます.

\overline{p}\overline{q}を入れ替えて否定\overline{\overline{p}}\overline{\overline{q}}にすれば良いので,「\overline{\overline{q}}\Rightarrow\overline{\overline{p}}」となりますが,上で述べたように否定の否定はもとにもどりますから,これは結局「q\Rightarrow p」となることが分かります.

注意点

「逆」,「裏」に関しては次のことに注意してください.

もとの命題が真であっても,「逆」,「裏」は真であるとは限らない.

標語的に「逆(裏)は必ずしも真ならず」と言われることがよくあります.このことは,次の場合を考えれば簡単に分かります.

pxは4の倍数である
qxは偶数である

このとき,p\Rightarrow qは真ですが,逆q\Rightarrow pは偽です.

もちろん,逆q\Rightarrow pも真となることもありますが,このとき「pqは同値である」ということになります.これは前々回の記事「論理と集合の基本3|必要条件と十分条件」で説明した通りです.

「もとの命題」と「対偶」の関係

さて,冒頭でも書きましたが,「命題」とその「対偶」については次のように非常に強い[定理]があります.

[定理] 命題「p\Rightarrow q」の真偽は,その対偶「\overline{q}\Rightarrow\overline{p}」の真偽に一致する.

つまり,p\Rightarrow qが真なら\overline{q}\Rightarrow\overline{p}も真ですし,p\Rightarrow qが偽なら\overline{q}\Rightarrow\overline{p}も偽です.

逆に,\overline{q}\Rightarrow\overline{p}が真ならp\Rightarrow qも真ですし,\overline{q}\Rightarrow\overline{p}が偽ならp\Rightarrow qも偽です.

集合(ベン図)による説明

pqxに関する条件とし,pqの真理集合をそれぞれPQとします.

真理集合については,前回の記事「論理と集合の基本4|命題と集合の関係」を参照してください.

このとき,条件pの否定\overline{p}は「xpを満たさない」という条件なので,\overline{p}を表す集合は\overline{P}で,同様に,\overline{q}を表す集合は\overline{Q}である,ということに注意して下さい.

以下で,[1]「p\Rightarrow qが真である」とき「q\Rightarrow qが真である」と[2]「p\Rightarrow qが偽である」とき「q\Rightarrow qが偽である」を示します.

[1] 「p\Rightarrow qが真である」とします.

このとき,PQP\subset Qを満たします.これは前回の記事で説明しました.これをベン図で表すと以下のようになります.

論理と集合の基本pic7

さて,ここで\overline{P}P(青丸)の外側で,\overline{Q}Q(黒丸)の外側です.ですから,図を見れば明らかなように,\overline{Q}\subset\overline{P}が成り立ちます.

\overline{p}\overline{q}を表す集合が\overline{P}\overline{Q}でしたから,結局「q\Rightarrow qが真である」となり,もとの命題が真なら対偶も真であることが分かりました.

[2] 「p\Rightarrow qが偽である」とします.

このとき,PQP\not\subset Qを満たします.これも前回の記事で説明しました.これをベン図で表すと以下どちらかのようになります.

論理と集合の基本pic8論理と集合の基本pic9

図を見れば明らかなように,どちらの場合も\overline{Q}\not\subset\overline{P}ですから,\overline{q}\Rightarrow\overline{p}は偽と分かります.

したがって,「q\Rightarrow qが偽である」となり,もとの命題が偽なら対偶も偽であることが分かりました.

以上の[1],[2]から,「もとの命題の真偽」と「対偶の真偽」が一致することが分かりました.

証明問題への応用

この[定理]は次のような証明問題で有効です.

[問] 実数xyx+y>0をみたすなら,x>0またはy>0であることを示せ.

xyの条件pq

p:実数xyx+y>0をみたす
q:実数xyx>0またはy>0をみたす

と定めると,[問]は「p\Rightarrow qを示せ」ということになります.

しかし,これを直接示すのは少し面倒ですが,[定理]を使えばすぐに示すことができます.

[定理]から,「『もとの命題の真偽』と『対偶の真偽』は一致する」ので,対偶「\overline{q}\Rightarrow\overline{p}」が真であることを示すことができれば,もとの命題「p\Rightarrow q」も真であることが分かるというわけですね.

さて,\overline{p}\overline{q}はそれぞれ

\overline{p}:実数xyx+y\leqq0をみたす
\overline{q}:実数xyx\leqq0かつy\leqq0をみたす

で(qにおいて,「または」の否定が「かつ」になることに注意.),\overline{q}\Rightarrow\overline{p}を示します.つまり,

実数xyx\leqq0かつy\leqq0をみたすなら,x+y\leqq0をみたす

ことを示します.これは簡単に示すことができます.解答は以下のようになります.

[解答]

問の対偶「実数xyx\leqq0かつy\leqq0をみたすなら,x+y\leqq0をみたす」が真であることを示せば,問も真であることが分かるので,以下対偶を示す.

実数xyx\leqq0かつy\leqq0をみたすとする.このとき,両辺足してx+y\leqq0となるから,対偶が成り立つことが分かった.

以上で題意が示された.

[解答終]

このように,直接証明することが面倒であっても,対偶を使うことで簡単に証明できることがあります.対偶を使うことの威力を感じていただけたでしょうか?

「背理法」との関係

この節は分からなければとばしても問題ありません.

背理法とは「命題が偽であると仮定すると矛盾が起こることを示し,命題が真であることを示す証明法」のことをいいます.

参考記事:背理法1|背理法の仕組みと例背理法2|背理法が有効な証明の2つのタイプと例

言い換えれば,「背理法」とは

  1. pかつ\overline{q}となることがある」……(*)と仮定する.
  2. 矛盾が生じる.
  3. 矛盾が起きたのは正しいと分かってもいないのに(*)と仮定したのが実は誤りだったからだ.
  4. よって,pかつ\overline{q}とはなり得ない.
  5. すなわち,pが成り立っているなら,qが成り立たなければならない.
  6. したがって,p\Rightarrow qが真

という流れの証明なわけです.

詳しくは説明しませんが,実は「対偶による証明」と「背理法による証明」は論理的には同じことをしています.そのことを感じてもらうために,上の問題を背理法を使って解いてみます.

[問(再掲)] 実数xyx+y>0をみたすなら,x>0またはy>0であることを示せ.

[解答]

背理法により示す.

つまり,ある実数xyx+y>0をみたすが「x\leqq0かつy\leqq0である」……(*)と仮定する.

このとき,x\leqq0y\leqq0の両辺を加えるとx+y\leqq0となり,これはx+y>0に矛盾する.

よって,仮定(*)が誤りで,x<0またはy<0であることが分かった.

[解答終]

さて,どうでしょうか?「対偶による証明」も「背理法による証明」も,結局はx\leqq0y\leqq0からx+y\leqq0を導きました.

集合の言葉で言い換えると,「対偶による証明」は\overline{Q}\Rightarrow\overline{P}を示しているわけですが,これは結局P\cap \overline{Q}=\emptysetであることと同じです.

また,「背理法による証明」はP\cap\overline{Q}\neq\emptysetと仮定して,矛盾を導くことで「実はP\cap\overline{Q}=\emptysetでした!」という論法なわけです.

論理と集合の基本pic7

したがって,「対偶による証明」も「背理法による証明」もどちらもP\cap \overline{Q}=\emptysetを示していることに他ならず,結局同じことをしているのです.

同じとは言っても,問題によっては「一方では証明しやすいけど,他方では証明しにくい」といったこともありますから,どちらを使って証明するべきかはその都度考える必要はあります.

【Sponsored Link】

SNSでもご購読できます。