代数学 #1 論理

命題

Def

命題とは YES,NO がはっきりと定まる主張のこと。

Ex

$「1+1=2」 ・・・①$　真 (命題)
$「1+1=3」 ・・・②$　偽　（命題）
$「100は大きい数」 ・・・③$　（命題ではない）

② は一見式が誤っていて命題でないのでは？と言うふうに見えるが、「誤りである」とはっきり主張ができるため命題である。

100 が大きい数かどうかは主観的であり客観的に YES,NO を断定できないため命題とは言わない。

含意命題

Def

$$命題「P⇒Q」 (P:仮定, Q:結果)$$

日本語的に言うと以下のような感じ。

「P じゃ無いなら Q の真偽はどうでも良い。」⇔「P なら Q に収まっとけ！！」

真理値表を具体的に以下に示す。

P	Q	P=>Q
0	0	1
0	1	1
1	0	0
1	1	1

この真理値は$¬P∨Q$と同値であり、真理値表を比較すると明らかである。

P	Q	¬P	¬P∨Q
0	0	1	1
0	1	1	1
1	0	0	0
1	1	0	1

Ex

$a,b∈Z$
$「a,bが偶数⇒a+bが偶数」・・・真$
$「a+bが偶数⇒a,bが偶数」・・・偽$

$1+1=2$だが「１」は奇数のため二つ目の命題は偽である。（反例）

必要条件と十分条件

Def

$P⇒Q$が真であるとする。

この時、

• P は Q であるための十分条件
• Q は P であるための必要条件

と言う。

また$P⇒Q$及び$Q⇒P$が共に真の時$P⇔Q$と書き P と Q は同値であると言う。

またの時、

• P は Q であるための必要十分条件
• Q は P であるための必要十分条件

と言う。

Ex

$△ABC が「正三角形(P) ⇒ 二等辺三角形(Q)」$

• 正三角形は二等辺三角形であるための十分条件(十分すぎる条件)
• 二等辺三角形は正三角形であるための必要条件（最低ラインとして必要な条件）

つまり、抽象度の高いものが必要条件で、具体度がより高いものが十分条件と言えるでしょう。

対偶

Def

$$「P⇒Q」と「¬Q⇒¬P」の真偽は一致する$$

「P であるなら Q に収まっててね！！」と言う事と「Q に入らないなら P にも入ってきちゃだめ！！」は日本語的イメージしても同値である。

また、P⇒Q が偽の時のイメージは以下である。

このように P なのに Q に収まっていない部分を反例と言い、反例を一つでも証明すれば偽を主張できる。

証明技法

(1)背理法

$$「Pが真である」⇔「¬Pが真であると仮定して矛盾が生じる」$$

(2)対偶証明法

$$「P⇒Qが真」⇔「¬Q⇒¬Pが真」$$

Ex

$a,b∈Z, 「a,bの少なくとも一方が偶数⇒abは偶数」$

普通に証明すると

$aが偶数とすると$
$a=2m, b=n$
$ab=2mn$
$∴abは偶数である$

これは b が偶数としても同じ結果を得ることができる。

背理法での証明

背理法は $P⇒Q$を否定して矛盾が生じることを示せば良いのでまずは$¬(P⇒Q)$を表したい。

ここで含意命題の以下の性質を思い出したい。

$$(P⇒Q)⇔（¬P∨Q）$$

これを含意の除去と言う。

$¬（¬P∨Q）⇔P∧¬Q$なので、「P でかつ Q じゃない」を審査して矛盾を示せば良い。

すなわち審査する命題は以下となる。

$「a,bの少なくとも一方が偶数」かつ「abは奇数である」$

• （偶数）*(偶数) = (偶数)
• （偶数）*(奇数) = (偶数)
• （奇数）*(奇数) = (奇数)

よって、a,b の少なくとも一方が偶数だと ab は奇数になり得ないので矛盾している。

$∴ 「a,bの少なくとも一方が偶数⇒abは偶数」は真である$

対偶証明法での証明

対偶のセクションで示した通り

$$「P⇒Q」と「¬Q⇒¬P」の真偽は一致する$$

なので、

$「abは奇数=>a,b共に奇数」$が真であることを示せば良い。