数学の論理                              戻る

 数学の問題を解くとき、「正攻法でやると多少めんどうになりそうだな〜」と感じるときがある。
そんなとき、問題を同値な、そして考えやすい別な問題にすり替えることは、問題解決の常套
手段である。このページでは、その基本的な方策について、まとめてみたい。

 いくつかの予備知識を確認しながら、話を進める。

命題について

 客観的に、真偽が判定できるような数式・文章を命題という。

(例) 1+1=2 ・・・ 命題で、真
   日本の人口は、1億である ・・・ 命題で、偽
   あなたは、数学が好きですか? ・・・ 真偽判定不能で、命題とならない

 いくつかの命題から、別な命題を作ることを、命題の合成という。

次の、3つのタイプが基本的である。命題 P、Q に対して、

 (離接) P または Q  記号では、P∨Q と書く。
 (合接) P かつ Q   記号では、P∧Q と書く。
 (否定) P でない    記号では、¬P または、 〜P または、  と書く。

(例) 2つの命題 P: X<2 、Q: X>0 に対して、

   P∨Q : Xは、全ての実数 、P∧Q : 0<X<2 、¬P : X≧2


命題の真理表について

 命題 P、Q の真偽によって、合成命題 P∨Q、P∧Q、¬P の真偽が次の表に従って定め
られる。表において、真は 「1」、偽は 「0」で表される。

P∨Q P∧Q ¬P
  左の表によって定められた真理表は、日常

 の感覚と大体同じなので、違和感なく覚えられ

 ることと思う。ただ、「または」は、日常使ってい

 る感覚(排他的)と異なるので、注意を要する。

 日常で、「ハンバーガーまたはジュースを頼む」と言われたら、どちらか一方を頼むのが普
通だが、数学では、両方頼むことも有りとなる。


#「∨」は、ラテン語の vel (どちらか少なくとも一方)からとられたらしい。日常使っている排
 他的な「または」としては、別な単語 aut を使うようだ。

(参考文献:足立恒夫 著 数 体系と歴史 (朝倉書店))


(例) ¬P∨Q の真理表を作れ。

¬P ¬P∨Q


 真理値が全て、0(偽)である命題を、矛盾命題といい、真理値が全て、1(真)である命題
トートロジーという。

 また、2つの命題の真理表が全く同一のとき、これらの命題は、論理的に同値であるとい
い、等号を用いて表される。


(論理的に同値な命題の例)

1.(2重否定)  ¬(¬P)=P  (Pでないことはないは、Pそのものということ)

2.(ド・モルガンの法則)

 ¬(P∨Q)=(¬P)∧(¬Q)  (またはの否定は、かつ)

 ¬(P∧Q)=(¬P)∨(¬Q)  (かつの否定は、または)

3.(分配の法則)

 P∧(Q∨R)=(P∧Q)∨(P∧R) 、P∨(Q∧R)=(P∨Q)∧(P∨R)


条件命題について

 数学では、「P ならば Q である」という形式の命題が多い。記号で、P → Q と書く。この
命題も、合成命題の一つであり、次のように、真理表が定められる。

P → Q
  この真理表と、先の(例)における ¬P∨Q の真理
  表を比較して分かるように、両者は、論理的に同値で
  ある。すなわち、

   P → Q = ¬P∨Q が成り立つ。

(覚え方としては、「PかつQでない、ことはない」の方がいいかもしれない。私自身は、そう
覚えている。)


(参考) 両者が論理的に同値であることに違和感を抱く人は多い。次のように考えてはどう
    だろうか。

 「P ならば Q である」の否定が、「P であるのに Q でない」と理解できれば、それは、暗

黙のうちに、¬(P → Q) = P∧¬Q すなわち、P → Q = ¬P∨Q ということを認めざ

るをえないということである。(参考文献:足立恒夫 著 数 体系と歴史 (朝倉書店))


 この命題で大切なポイントは、仮定Pが偽ならば、結論Qの真偽に関わらず、P → Q が
真になるところである。

 「雨が降れば、傘を差す」という行為について、雨が降っているのに傘を差さないのは、変
であるが、雨が降らなければ、傘を差しても差さなくても変ではない。お天気なのに、傘を差
していることを咎められたら、「これは、日傘です。」とでも言っておけばよい。

 同様に、「明日天気がよければ外出しよう」と約束したら、天気が悪いときは、外出しても、
しなくても自由で、約束を破ったことにはならない。天気がよいのに外出しなかったら、それ
は、約束を破ったことになる。

 この場合の応用例として、次の問題は有名である。

(例) 空集合は、すべての集合の部分集合である。

  B⊂A であるとき、BはAの部分集合である。ところで、B⊂A とは、「X∈B ならば、
X∈A」が成り立つことをいう。いま、Bが空集合のとき、X∈Bは偽なので、命題「X∈B なら
ば、X∈A」は真である。よって、空集合Bは、任意の集合Aの部分集合である。


 このように、仮定が偽のとき、命題 P → Q は、無内容的に成り立つという。

(参考) 「偽」の命題からは、どんな命題も導けるといった、ラッセルの講演の話が知られ
    ている。

 例えば、「2=1」の命題から、「私は、日本の総理大臣」という命題は、次のように証明さ
れる。

 「2≠1」は、「真」の命題なので、「2≠1」∨「私は、日本の総理大臣」は、「真」の命題

ところで、「2=1」の命題が成り立つと仮定するということは、「2=1」が「真」の命題、すなわ

ち、「2≠1」は、「偽」の命題と仮定するということである。

「2≠1」∨「私は、日本の総理大臣」は、「真」の命題であったので、「私は、日本の総理大

臣」が「真」の命題ということになる。したがって、「2=1」ならば、「私は、日本の総理大臣」

である。(参考文献:足立恒夫 著 数 体系と歴史 (朝倉書店))


(例) 三段論法がトートロジーであることを示せ。

P → Q Q → R P → R (P→Q)∧(Q→R) (P→Q)∧(Q→R)→(P→R)

 このことから、三段論法(P ならば、Q で Q ならば、R のとき、P ならば R)による推論
は、常に有効である。


(例) アリバイの原理がトートロジーであることを示せ。

P → Q ¬P ¬Q (P → Q)(¬Q) (P → Q)(¬Q) → (¬P)

 このことから、「P ならば Q だが、Q でなければ、P でない」という推論は常に有効である。


 よおすけさんからのコメントです。(令和5年7月23日付け)

 命題((P→Q)∧(Q→R))→(P→R) がトートロジーであることの別証明です。

(証明) 命題((P→Q)∧(Q→R))→(P→R) が偽となるのは、

 P→Q が真、Q→R が真、P→R が偽の場合だけである。

 ところで、P→R が偽となるのは、Pが真で、Rが偽の場合だけである。

 Pが真で、P→Q が真より、Qが真となり、Q→R が真より、Rが真となるが、Rが偽であるこ

とに矛盾する。

 したがって、この命題が偽となることは無く、トートロジーである。  (証終)


必要条件と十分条件

 命題 P → Q が常に真であるとき、記号 P ⇒ Q で表す。

 このとき、Pは、Qであるための十分条件といい、Qは、Pであるための必要条件であると
いう。

(例) X=1 ⇒ X2=1 において、

「X=1」は、「X2=1」であるための十分条件
  ・・・X2=1であるためには、X=1であれば十分!

「X2=1」は、「X=1」であるための必要条件
  ・・・X=1であるためには、とりあえず X2=1であることが必要!


逆・裏・対偶

 命題 P → Q に対して、次の命題を、それぞれ、もとの命題の対偶という。

 逆 : Q → P
 裏 : ¬P → ¬Q
対偶 : ¬Q → ¬P


(例) もとの命題とその対偶は、論理的に同値であることを示せ。

P → Q ¬Q ¬P ¬Q → ¬P

 このことから、ある命題を証明するかわりに、その対偶を証明してもよいことになる。しか
も、問題によっては、対偶を証明する方が、非常に楽な場合がある。これは、経験的に、確
かな真実である。


(例) 3つの数 X、Y、Z について、X+Y+Z>3 ならば、少なくとも一つは、1 より大きい。

 この命題の対偶は、「3つの数 X、Y、Z について、どれも1以下ならば、X+Y+Z≦3」

明らかに、X≦1、Y≦1、Z≦1 ならば、X+Y+Z≦1+1+1=3 なので、対偶命題は真。

よって、もとの命題も真である。


命題関数

 集合 U 上で定義された命題 P(X) を考える。命題 P(X) が真となるような集合 Uの要素 X
の集合を、命題関数 P(X) の真理集合といい、Pで表す。

 それぞれの命題関数の真理集合は次のようになる。

 P(X)∨Q(X) ・・・ P∪Q (PとQの結び(和集合))
 P(X)∧Q(X) ・・・ P∩Q (PとQの共通部分)
  ¬P(X)    ・・・  Pc 
 (Pの補集合)
 P(X) → Q(X) ・・・ ∪Q

 この真理集合の考えを用いると、P ⇒ Q の証明は視覚的に行うことができる。すなわち、

 P(X) ⇒ Q(X) を証明するには、P⊂Q であることを確かめればよい。

 実際に、P(X) → Q(X) の真理集合は、P∪Q であり、命題がトートロジーであることから

∪Q=U に等しい。このとき、

 P=P∩U=P∩(P∪Q)=(P∩P)∪(P∩Q)=P∩Q⊂Q から、P⊂Q

逆に、P⊂Q とすると、U=P∪P⊂P∪Q⊂U から、 P∪Q=U

よって、命題 P(X) → Q(X) は、トートロジーである。


(例) |X|+|Y|<1 ならば、X2+Y2<1 であることを証明せよ。

 この問題は、真理集合を調べることにより、簡単に示される。

  左図より、正方形の内部:|X|+|Y|<1 は、

 円の内部:X2+Y2<1 に含まれるので、

 命題は成り立つ。



反例の作り方

 命題 P(X) → Q(X) が偽であることを示すには、反例をあげるのが手っ取り早い方法であ
る。P⊂Q が成り立たないことから、P(X)であるが、Q(X)でないようなXを一つ探せばよい。


(例) 命題「X2=1 ならば X=1」は偽である。なぜなら、X=−1という反例があるから。


全称命題と存在命題

 数学において、「すべての〜」とか「〜であるものが存在する」という形式の命題は数多い。

「すべてのXに対して、P(X)である」という命題を全称命題といい、記号で、∀X:P(X) と
書く。

全称命題の真理集合は、全体集合Uである。(∀:全称記号(universal quantifier))

「あるXに対して、P(X)である」という命題を存在命題といい、記号で、∃X:P(X) と書く。

存在命題の真理集合は、空でない集合である。(∃:存在記号(existential quantifier))


(例) すべての実数Xに対して、X2≧0
   ある実数Xに対して、2X−4=0
   a≦b は、存在命題 ∃X≧0 : a+X=b で表される。

全称命題と存在命題について、次の関係式は基本的である。

 ¬(∀X:P(X))=∃X:¬P(X)    (「すべて」の否定は「ある」)

 ¬(∃X:P(X))=∀X:¬P(X)    (「ある」の否定は「すべて」)


 複雑な命題を考えるとき、文章で与えられたままでは頭が混乱するので、記号化して考え
た方がよい。単純作業で、いろいろな命題に変換できる。


(例) 命題「すべての実数Xについて、X2>1 ならば、X>1 である。」の否定命題を作り、
   その真偽を判定せよ。
  
 ¬(∀X:(X2>1→X>1))
=∃X:¬(X2>1→X>1)
=∃X:¬(¬(X2>1)∨(X>1))

=∃X:(X2>1)∧(X≦1)

 
これを、翻訳すれば、「X2>1 かつ X≦1 となる実数Xがある。」となる。

 たとえば、X=−2 が該当するので、この命題は、真である。
 (よって、もとの命題は偽ということになる。)


(例) 命題「P ならば、QまたはR」は、命題「Pかつ(Qでない) ならば、R」と論理的
   に同値である。

    
 実際に、P → Q∨R =(¬P)∨(Q∨R)=((¬P)∨Q)∨R

 =((¬P)∨(¬(¬Q)))∨R=(¬(P∧(¬Q))∨R=P∧(¬Q) → R

これを、「XY=0 ならば、X=0 または Y=0 」に適用してみると、

 「XY=0 かつ X≠0 ならば Y=0 」という形になり、納得されやすい表現になる。


 この(例)における言い換えは、大学入試でよく用いられる技法で、知っている者だけが
非常に有利になる魔法の論理である。


(参考文献:茂木 勇 著 集合と論証(科学新興社)
        秋山 仁 著 真理表(数学ライブラリー))


 平成27年度入試 東京大学前期文系で真偽を問う問題が出題された。

問題 以下の命題A、Bそれぞれに対し、その真偽を述べよ。また、真ならば証明を与え、偽
   ならば反例を与えよ。

命題A nが正の整数ならば、n3/26+100≧n2が成り立つ。

命題B 整数n、m、p が5n+5m+3p=1を満たすならば、10nm+3mp+3np<0が成
    り立つ。


 グラフ描画ソフトにお助けいただくと、F(x)=x3/26+100−x2 のグラフは下図の通り。

15<x<20 の周辺が微妙で、ズームして見ると、

     

   グラフから、x=17 が怪しい!!






(確かめ) F(17)=4913/26+100−289=−0.0384616・・・

 から、ほんの一瞬、x3/26+100<x2 となるので、命題Aは偽となる。反例は、n=17。


(コメント) グラフ描画ソフトを活用して「偽」を示したが、実際の試験場では微分のお世話に
      なるしかないだろう。


(命題Aの解) F(x)=x3/26+100−x2 とおくと、F(x)は微分可能な3次関数である。

ここで、 F’(x)=3x2/26−2x=0 とおくと、 x=52/3=17.333・・・で極小かつ最小

F(17)=173/26+100−172=4913/26+100−289=−0.0384616・・・<0

よって、x=17 のとき負で、正の整数nに対して、いつも n3/26+100≧n2 が成り立

つとは限らない。したがって、命題Aは偽で、反例は、n=17。  (終)


 およそ受験でともに「偽」となることはないだろうと高をくくれれば命題Bは「真」だろうと予想
がつく。

実際に、整数n、m、p が5n+5m+3p=1を満たすならば、10nm+3mp+3np<0が
成り立つ。

(証明)

10nm+3mp+3np=10nm+3p(m+n)
=10nm+(1−5(n+m))(m+n)=10nm+m+n−5(n+m)2
=m+n−5n2−5m2

ここで、 m−5m2=−5(m−1/10)2+1/20 で、

 m=0 のとき、 m−5m2=0 、m=1 のとき、 m−5m2=−4

同様に、 n−5n2=−5(n−1/10)2+1/20 で、

 n=0 のとき、 n−5n2=0 、n=1 のとき、 n−5n2=−4

 m=0 かつ n=0 とすると、 3p=1 で、この式を満たす整数pは存在しない。

 よって、m、nが同時に0になることはなく、 m+n−5n2−5m2<0 が成り立つ。

 以上から、命題Bは真である。  (証終)


(追記) 令和5年7月20日付け

 全国的に明日から夏休み!気分的に久しぶりに論理の問題を考えてみたくなった。

問題  命題 P、Q に対して、その合成命題 P*Q を次の真理表で定義する。

P * Q









 このとき、否定 ¬P 、離接 P∨Q 、合接 P∧Q は、「*」を用いてどのように表される
だろうか? 

(解)
¬P
1
P * P
 から、 ¬P=P * P

また、

P∨Q ¬P ¬Q (¬P)*(¬Q)

から、 P∨Q(¬P)*(¬Q)

よって、 P∨Q(P * P)*(Q * Q)

さらに

P∧Q ¬P∧Q









から、 ¬P∧Q=P * Q なので、 P∧Q=¬P * Q

よって、 P∧Q=P * Q*P * Q)  (終)


 こういう論理の問題は、数学の授業ではあまり詳しく言及されることはなく、大学の一般教
養の哲学の講義で詳しい話を聞いたような気がする。

問題  Q∧R が偽のとき、(Q → PR → P) はトートロジーであることを示せ。

 トートロジーを示すには、真理表を作って、真理値が全て、1(真)であることを示せばよい
わけであるが、次のように示してもよい。

(解) (Q → PR → P)=(¬Q∨P¬R∨P)=¬Q∧R∨P

よって、Q∧R が偽のとき、¬Q∧R)は真となり、Pの真偽に関わらず、¬Q∧R∨P

は真となるので、(Q → PR → P) はトートロジーである。  (終)


(コメント) Q∧R が偽のとき、QまたはRは偽で、そのとき、Q → P または R → P
      無内容的に成り立つから真。だから、トートロジーであることは自明かな。


問題  次の命題はトートロジーであることを示せ。

(1) (¬P∨P
(2) (P∧QR∨P

(3) (¬P∧Q))∨P

(4) (P∧¬Q))((¬P

(解)(1) (¬P∨P の真理集合は全体集合Uなので、トートロジーである。

(2) (P∧QR∨P)=(¬P¬QR∨P)=(¬P∨P∨¬Q

 このとき、真理集合は全体集合Uなので、トートロジーである。

(3) (¬P∧Q))∨P=((¬P¬Q))∨P=(¬P∨P∨¬Q

 このとき、真理集合は全体集合Uなので、トートロジーである。

(4) (P∧¬Q))((¬P → Q)=((¬P∨Q)=(¬P∨P∨

 このとき、真理集合は全体集合Uなので、トートロジーである。  (終)


(追記) 令和5年9月19日付け

問題  x、y は有理数とする。

 x+y と xy がともに整数ならば、x、y は整数であることを示せ。

(解) x+y=m、xy=n とおくと、m、nは整数で、x、y は、2次方程式 t2−mt+n=0 の

解である。解 t は有理数なので、 t=q/p (p、qは互いに素な整数) と書ける。

方程式に代入して、 q2/p2−mq/p+n=0 すなわち、 q2−mpq+np2=0 より、

 q2=p(mq−np) となるので、q2 すなわち、q は p で割り切れる。

しかるに、p、qは互いに素な整数なので、p=±1 となる。

 よって、解 t は整数となり、すなわち、x、y は整数である。  (終)


(コメント) この問題を背理法で示すには、どうすればいいのだろう?

 「x、y は整数である」の否定は、「x、y の少なくとも一つは整数でない」で、上記の(解)か
ら、これは矛盾としていいのかな?


問題  ある仕事を、A、B、C の3人で行っても1時間以上かかるという。この仕事を、1人
    が単独で行うとき、2時間以上かかるものが少なくとも2人いることを示せ。

(解) 「2時間以上かかるものが少なくとも2人いる」の否定は、

 「2時間以上かかるものが1人以下」

すなわち、「2時間未満で終わらせるものが少なくとも2人いる」

すなわち、単独で、1時間あたり仕事全体の半分以上が終わるものが少なくとも2人いる

すなわち、この2人で、1時間より短い時間で仕事が終わることになる。

これは、「A、B、C の3人で行っても1時間以上かかる」ことに矛盾する。

したがって、2時間以上かかるものが少なくとも2人いる。  (終)



  以下、工事中!