よくわかる離散数学

• 自分向けのメモも兼ねて、UECのJ科およびI科で開講されている「離散数学」で扱われている事項について書いていこうと思います。

論理

命題とその真偽

命題

• 命題とは、それが本当か本当でないかがはっきりしているような文のことである。

 素数は無限に存在する……この文は誰の目から見ても正しいとわかる。よって命題である。
 その人は男性である……男性であるか男性でないかははっきりと分かるので、命題である。
 この部屋は大きい……大きいか大きくないかというのは主観によるので命題ではない。

• 命題は必ず本当か本当でないかがはっきりする。
  • その命題が本当であることを、「真」という。
  • その命題が本当でないことを、「偽」という。
• つまり命題はすべて真偽が決定する。
  • 真偽が決定しないものは命題ではない。

条件付き命題

• 命題の中には、状況によって真偽が変化するものがある。

 xは素数である……xに何が入るかによって真偽がかわる

• xを命題変数と呼ぶ。

• 命題変数を含む命題を条件付き命題と呼ぶ。

命題関数

• 条件付き命題は、変数によって真か偽の結果が決まる。
• つまり、条件付き変数は変数によって真か偽という値が得られる関数とみなすことができる。

• 命題を関数として考えるとき、それを命題関数という。

• 普通の関数にf(x)のように記号をつけることがあるように、命題関数にもP(x)のような記号をつけることがある。

 P(x) : xは命題である

• 上の例はP(x)という命題関数は「xは素数である」という命題であることを示している。

真理値表

• 命題を命題関数として扱い、P(x)などの記号に変えることによって、命題の内容には関係なく単純に命題の真偽だけを考察の対象にできる。
• 命題関数の変数とその真偽を表にしたものを真理値表という。
• 「P(x) : xは素数である」を例に、真理値表を作ってみる。

• 表にあるTとはtrueすなわち真のことである。Fとはfalseすなわち偽のことである。

論理演算

• 「真偽」という概念を対象に行う演算のことである。
• 一般的な足し算や引き算は数を対象に行う。論理演算は「真偽」を対象に行う。
• 命題関数に対して論理演算を行うことで、命題の内容を考えることなく、複雑な命題な組み合わせの真偽について考えることができる。

論理和

• 論理和とは2つの命題関数のどちらかが真であれば結果が真となるような演算である。
• P(x)とQ(x)の論理和をP(x)∨Q(x)とかく。
• 真理値表を示す。

論理積

• 論理和とは2つの命題関数の両方が真であれば結果が真となるような演算である。
• P(x)とQ(x)の論理和をP(x)∧Q(x)とかく。
• 真理値表を示す。

否定

• 否定とは命題関数が真であれば結果が偽となり、偽であれば結果が真となるような演算である。
• P(x)の否定を¬P(x)とかく。
• 真理値表を示す。

PならばQ

• PならばQとは命題関数P(x)が真で、命題関数Q(x)が偽であるときのみ結果が偽になるような演算である。
• PならばQをP(x)⇒Q(x)とかく
• 真理値表を示す。

同値

• PとQが同値とは、P⇒QとQ⇒Pが同時に成り立っているとき真になるような演算である。
• 言い換えればPとQの真偽が一致している状態を指す。
• PとQが同値であることをP(x)⇔Q(x)とかく。
• 真理値表を示す。