論理と証明

論理と証明

数学の議論に意味があるのは正しい論理が用いられたときのみである.

目次

  1. 命題論理
  2. 述語論理
  3. 証明法

1.命題論理

論理 について考えてみる.論理学では式や文章で (内容が正しい)であるか(内容が誤っている)であるかが定まっているものを 命題という.数学の記述においては,「命題」は真である命題を意味する.真の命題に 1 を,偽の命題に 0 を対応させて,命題の真理値 ということにする.

いくつかの命題が与えられたとき,それらを組み合わせて複合命題をつくることができる.2つの命題 P, Q の基本的な複合命題を見てみよう.

(i)P かつ Q 」という命題(論理積)を P ∧ Q で表す.この命題は P と Q がともに真のときにのみ真である命題である.したがって,P, Q それぞれの真理値に対応する P ∧ Q の真理値は次のようになる.

PQP ∧ Q
111
100
010
000

一般に,このような表を真理表 とよんでいる.

(ii)P または Q 」という命題(論理和)を P ∨ Q で表す.日常語と違って,P ∨ Q は P, Q のどちらかが一方が真,あるいは P, Q 両方が真のとき,真である命題である.

(iii)P ならば Q」という命題(含意)を P ⇒ Q で表す.その真理値は,P が真のときには,Q が真であれば真であり,P が偽のときには,Q の真偽とは無関係に真であると定める.

(iv)P でない 」という否定命題を ¬P で表す.

(v)P と Q は同値である 」という命題を P ⇔ Q で表す.

命題 P, Q, R,... の複合命題は P, Q, R 等を {0, 1} をとる変数として,真理値を対応させる関数と考えることができる.このような関数を論理関数という.

論理関数に関する等式を挙げておく.等式は両辺の真理値が等しい,すなわち論理関数として両辺が等しいという意味である.真理表が等しいことを確認すればよい.

補題 次が成立する.

  1. 交換法則
    1. P∨ Q = Q∨ P
    2. P∧ Q = Q∧ P
  2. 結合法則
    1. P∨ (Q∨ R) = (P∨ Q)∨ R
    2. P∧ (Q∧ R) = (P∧ Q)∧ R

このように,結合法則が成立しているので,P1∨ P2∨...∨ Pr あるいは P1∧ P2∧ ... ∧ Pr という表現を用いても混乱を生じない.

補題 次の分配法則が成立する.

    1. P∨ (Q∧ R) = (P∨ Q)∧ (P∨ R)
    2. P∧ (Q∨ R) = (P∧ Q)∨ (P∧ R)
    1. P∨ (P∧ Q) = P
    2. P∧ (P∨ Q) = P

定理 論理関数に関するド・モルガンの法則が成立する.

命題(証明の論理) 次の等式が成立する.

(P ⇒ Q) = (¬Q ⇒ ¬P) = ¬P ∨ Q

2.述語論理

数学には変数 を含む命題}も登場する.変数 x を含む命題を P(x) で表す.ただし,変数 x の定義されている集合(定義域あるいは対象領域)は定まっているとする.変数を含む命題では,変数 x の個々の値について(x に特定の元を代入すると)真偽が確定する.数学の記述で必要になるのは次のような命題である.

全称命題を論理記号では (∀x) P(x) で 表し,存在命題を (∃x) P(x) で表す.いま,変数 x の定義域を A とし,B = { x ∈ A | P(x) は真} と定めると,(∀ x) P(x) は B = A ということであり,(∃ x) P(x) は B が空集合ではないということにほかならない.

補題 否定については次の関係が成立する.

¬((∀x) P(x)) = (∃x)(¬P(x))

¬((∃x) P(x)) = (∀x)(¬P(x))

実数の数列 {an} が極限 a に収束するとはどういうことか述語論理の立場で考えてみよう.コーシーによる次の数学的定義は微分積分学の基礎になっている.

定義 数列 {an} が a に収束するとは,

任意の正数 ε に対して,自然数 N が存在して,n ≧ N のとき,|an-a| < ε が成立することをいう.

記号では,limn → ∞an = a で表す. 論理記号を用いることにより,数列の極限の定義は次のように表される.

(∀ε)(∃N)(∀ n)(n ≧ N ⇒ |an-a| < ε)

いま,

P(n,N) = (n ≧ N), Q(n,ε) = (|an-a|<ε)

とおくと,否定は次のようになる.

¬((∀ε)(∃ N)(∀ n)(P(n,N) ⇒ Q(n,ε))) = (∃ε)(∀ N)(∃ n)(P(n,N) ∧¬Q(n,ε))

このことを言葉で表現すると,

ある正数 ε が存在して,どんな自然数 N に対しても,n ≧ N かつ |an-a| ≧ ε となる n が存在する

のようになる.

3.証明法

典型的な直接証明 は次のように行われる.

  1. 命題 P は真である.
  2. 命題 P ⇒ Q は真である.
  3. したがって,命題 Q は真である.

確かに,P の真理値が 1 のとき,P ⇒ Q の真理値が 1 になるためには Q の真理値は 1 でなければならない.

間接証明が有効な場合もある.命題 P ⇒ Q が正しいことを証明する代わりに,対偶 (¬Q) ⇒ (¬P) が正しいことを証明してもよいのである.命題 Q ⇒ P を逆の命題 という.逆の命題の真偽はもとの命題の真偽とは一致しない.

例題 n2 が偶数のとき,n は偶数であることを示せ.

解答 もし,n が奇数であれば,n2 は奇数である.したがって,n は偶数である.

背理法も間接証明である.命題 P を証明する場合,否定命題 ¬P を仮定すると矛盾が生じることを示して,P を証明するという方法である.これは,P と ¬P の真理値が反対であることを根拠にしている.

例題(無理数の証明) √2 が無理数であることを示せ.

解答 √2 が有理数 a/b に等しいとする.このとき,a, b は互いに素であると仮定してよい.等式 2b2=a2 が成立する.よって,a2 は偶数である.したがって,a も偶数であり,a=2a' とおくと,b2=2a'2 となり,b も偶数になる.このことは a, b が互いに素であったことに矛盾するので,背理法により,\sqrt{2} が無理数であることが結論される.

次も背理法の一種である.

補題 命題 P ⇒ Q を証明するには,命題 P∧¬Q が偽であることを示せばよい.

ある命題が偽であることを示すには,反例 を示せばよい.命題 P ⇒ Q が真のとき,Q を P の必要条件 ,P を Q の十分条件 という.


トップへ
酒井文雄記(2000年4月)