対偶を利用する証明

　さて、難しいことを書く前に、馴染みやすいところから数理論理学に入っていこう。

一般に、真偽を問うことのできる形式 (文や式) を命題という。

　ある命題が正しいとき、その命題は真であるといい、正しくないとき、その命題は偽であるという。たとえば、次の命題(A)は真、(B)は偽である。

「奇数と奇数の和は偶数である」‥‥ (A)

「√2＋√3＝√5」‥‥ (B)

　ここで、少しの違和感を顧みず、(A) を

「奇数と奇数の和である ならば 偶数である」

と書き換えてみよう。さらに、ならばの記号 "→" を使えば、(A) は次のようになる。

「奇数と奇数の和である → 偶数である」

この場合、"奇数と奇数の和である" を仮定、"偶数である" を結論という。

　しかし、命題について言及するたびに長い文や式を書くのは非効率である。よって、"ならば" を "→" と置いたように、仮定や結論もｐやｑといった文字で置き換えてしまうと簡潔である。

　仮定 "奇数と奇数の和である" をｐ、結論 "偶数である" をｑと置くと、最終的に (A) は次のように表わされる。

「ｐ → ｑ」

　さて、このような形式の命題「ｐ→ｑ」には、それぞれ逆・裏・対偶が存在する。逆は仮定と結論を "→" の前後で逆にした命題であり、裏は仮定と結論の内容をそれぞれ否定したものを "→" で結んだ命題であり、対偶は仮定と結論の内容をそれぞれ否定したものを "→" の前後で逆にした命題 (つまり、"裏" の "逆" ) である。

　否定の記号 "￢" を使えば、(A) における逆・裏・対偶とそれぞれの意味は、次のようにまとめられる。

命題「　ｐ →　 ｑ」‥‥ 奇数と奇数の和である ならば 偶数である

逆　「　ｑ → 　ｐ」‥‥ 偶数である ならば 奇数と奇数の和である

裏　「￢ｐ → ￢ｑ」‥‥ 奇数と奇数の和でない ならば 奇数である

対偶「￢ｑ → ￢ｐ」‥‥ 奇数である ならば 奇数と奇数の和でない

　証明は後にするが、命題とその対偶の真偽は一致する。また、命題が真であってもその逆や裏が真であるとは限らない、つまり逆と裏はもとの命題の真偽によらない。

　さあ、この対偶の性質を利用して、次の命題を証明してみよう。

命題「n² が偶数ならば，n は偶数である」

この命題はそのまま証明するよりも、対偶を使った方が簡単である。

【証明】

この命題の対偶は，次の命題である。

n が奇数ならば，n² は奇数である

ここで，奇数 n は，ある整数 z を用いて n=2z+1 と表され

n²＝(2z+1)²=4z²+4z+1＝2(2z²+2z)+1

である。2z²+2z² は整数であるから，n² は奇数である。

よって，対偶が真であるから，もとの命題も真である。

　逆に、(A) のような命題はそのまま証明した方が簡単である。

(A)「奇数と奇数の和である ならば 偶数である」

冒頭で真であると断言した (A) を、ここで証明してみよう。

【証明】

2つの奇数 n,m は，ある整数 z,k を用いて n=2z+1,m=2k+1 と表され

n+m=(2z+1)+(2k+1)=2{(z+k)+1}

である。z+k は整数であるから，n+m は偶数である。

よって，(A) は真である。

　　｜次へ