対偶を利用する証明

命題「 $3$\displaystyle{p\Rightarrow q}$ 」が真であることの証明が困難な場合，対偶の性質

命題「 $3$\displaystyle{p\Rightarrow q}$ 」とその対偶「 $3$\displaystyle{\bar{q}\Rightarrow \bar{p}}$ 」の真偽は一致する．

より，対偶「 $3$\displaystyle{\bar{q}\Rightarrow \bar{p}}$ 」が真であることを証明すると，命題「 $3$\displaystyle{p\Rightarrow q}$ 」が真であることが証明できたことになる．

■事例

対偶を利用した証明でよく例に挙がっているのが

整数 $3$n$ において， $3$\displaystyle{ {n}^{2} }$ が偶数であるならば， $3$n$ は偶数である．

という命題が真であることの証明である．

上記の命題を，「 $3$\displaystyle{p\Rightarrow q}$ 」に対応させると

$3$p$ ： $3$\displaystyle{ {n}^{2} }$ は偶数である．

$3$q$ ： $3$n$ は偶数である．

「整数 $3$n$ において」は，命題が取り扱う要素の全体集合を指定している．

となる．

$3$n$ と $3${n}^{2}$ の関係を表で示す．

$3$n$	$3$- 2$	$3$- 1$	$3$0$	$3$1$	$3$2$	$3$3$	$3$4$	$3$5$	$3$6$
$3$\displaystyle{ {n}^{2} }$	$3$4$	$3$1$	$3$0$	$3$1$	$3$4$	$3$9$	$3$16$	$3$25$	$3$36$

表を見ると，命題は真でありそうである．

命題が真であることを証明するためには， $3$p$ の「 $3$\displaystyle{ {n}^{2} }$ が偶数である」を式で表わす必要がでてくる． $3$\displaystyle{ {n}^{2} }$ が偶数であるので

$3$\displaystyle{{n}^{2}=2\left({ \text{\hspace{5}}\text{\hspace{5}} }\right)}$

と， $3$\displaystyle{\left({\text{\hspace{5}}}\right)}$ の中に， $3$\displaystyle{ {n}^{2} }$ が， $3$4$ ， $3$1$ ， $3$4$ ， $3$9$ ， $3$16$ ， $3$36$ と変化するような整数 $3$k$ を含む式を入れなければならない．しかし，その式を見つけるのは容易でない．