大学数学

論理記号.5 論理演算

論理演算

前回までで一通りよく使う論理記号については押さえましたが、今回からは論理演算を取り扱います。

p,q,r を命題とします。また、常に真である命題を 1、常に偽である命題を 0 で表すことにします。

次の計算法則が成り立ちます。(多いですが、一つ一つはそこまで難しくないので慣れていきましょう)


Prop.SetTop.1.5.1. (よく使う計算法則一覧)

べき等則
(p \land p) \Leftrightarrow p
(p \lor p) \Leftrightarrow p

交換則
(p \land q) \Leftrightarrow (q \land p)
(p \lor q) \Leftrightarrow (q \lor p)

結合則
((p \land q) \land r )\Leftrightarrow (p \land (q \land r))
((p \lor q) \lor r )\Leftrightarrow (p \lor (q \lor r))

分配則
((p \land q) \lor r )\Leftrightarrow ( (p \lor r) \land (q \lor r))
((p \lor q) \land r )\Leftrightarrow ( (p \land r) \lor (q \land r))
(p \land (q \lor r) )\Leftrightarrow ( (p \land q) \lor (p \land r))
(p \lor (q \land r) )\Leftrightarrow ( (p \lor q) \land (p \lor r))

ド・モルガンの法則
\lnot (p \land q) \Leftrightarrow ( (\lnot p) \lor (\lnot q) )
\lnot (p \lor q) \Leftrightarrow ( (\lnot p) \land (\lnot q) )

○二重否定=肯定
\lnot (\lnot p) \Leftrightarrow p

01 に関わる演算
(p \land 0) \Leftrightarrow 0
(p \lor 0) \Leftrightarrow p
(p \land 1) \Leftrightarrow p
(p \lor 1) \Leftrightarrow 1
(p \land (\lnot p)) \Leftrightarrow 0
(p \lor (\lnot p)) \Leftrightarrow 1


では、順番に解説していきましょう。

べき等則

(p \land p) \Leftrightarrow p
(p \lor p) \Leftrightarrow p

これは日本語で言ってしまうと極めて単純明快で、「p または p」も「p かつ p」も結局 p だということです。p^2 (べき)が p に等しいような見た目なので、べき等則と言っています。

交換則

(p \land q) \Leftrightarrow (q \land p)
(p \lor q) \Leftrightarrow (q \lor p)

これも簡単なことで、かつとまたはで挟んでいるだけなので順序を交換したところで意味は変わらないと言っているだけです。

分配則

((p \land q) \lor r )\Leftrightarrow ( (p \lor r) \land (q \lor r))
((p \lor q) \land r )\Leftrightarrow ( (p \land r) \lor (q \land r))
(p \land (q \lor r) )\Leftrightarrow ( (p \land q) \lor (p \land r))
(p \lor (q \land r) )\Leftrightarrow ( (p \lor q) \land (p \lor r))

これについては、実数の分配則

(p+q) \times r=p \times r+q \times r
p \times (q+r) =p \times q+p \times r

を念頭に置いておくと理解しやすいでしょう。(もちろん実数の分配則では、p,q,r は実数としています)

ド・モルガンの法則

\lnot (p \land q) \Leftrightarrow ( (\lnot p) \lor (\lnot q) )
\lnot (p \lor q) \Leftrightarrow ( (\lnot p) \land (\lnot q) )

高校数学の集合の単元で出てきたド・モルガンの法則の論理バージョンです。「かつ」や「または」を否定すると、「かつ」が「または」に、「または」が「かつ」にひっくり返ります。これと同じようにして、一般の命題の否定を作っていくことができます。詳しくは次の記事(否定の作り方)でお話しします。

二重否定=肯定

\lnot (\lnot p) \Leftrightarrow p

これはそのままの意味なので、特に混乱することはないでしょう。こちらも否定の作り方で計算例を出します。

01 に関わる演算

(p \land 0) \Leftrightarrow 0
(p \lor 0) \Leftrightarrow p
(p \land 1) \Leftrightarrow p
(p \lor 1) \Leftrightarrow 1
(p \land (\lnot p)) \Leftrightarrow 0
(p \lor (\lnot p)) \Leftrightarrow 1

一つずつ意味を解説していきましょう。

(p \land 0) \Leftrightarrow 0

常に偽である命題 0p が同時に成り立つことはないので、左辺は 0 と同値になります。

(p \lor 0) \Leftrightarrow p

左辺は常に偽である命題 0 または p が成り立つと言っているのですが、0 が成り立つことはないので、pと同値になります。

(p \land 1) \Leftrightarrow p

常に真である命題 1p が同時に成り立つとき、p さえ成り立てばいつでも 1 は成り立つので、左辺は p と同値になります。

(p \lor 1) \Leftrightarrow 1

常に真である命題 1 または p が成り立つとき、1 は常に成り立つので、左辺は 1 と同値になります。

(p \land (\lnot p)) \Leftrightarrow 0

pp でないが同時に成り立つことはあり得ないので、左辺は常に偽です。したがって 0 と同値です。

(p \lor (\lnot p)) \Leftrightarrow 1

すべての命題は真偽が決定できるものであることが、命題の定義です。定義から、p であるか p でないかのいずれかは必ず成り立っているので、左辺は常に真です。したがって 1 と同値です。

計算例

では、いくつか計算例を示していきましょう。新しい概念に出会ったときは使って慣れることが大切です。


Ex.SetTop.1.5.2.

論理記号.2の記事で、

p \Rightarrow q( \lnot p) \lor q と同値であることを定理として述べましたが、改めてこれを示しましょう。

p \Rightarrow q がいつ真になるかを考えると、「p が成りたっていてかつ q が成り立つ」ときか、「そもそも p が成り立っていない」とき、またそのときに限り真となります。

言い換えると、p \Rightarrow q は「p かつ q」または「p でない」と同値です。このことを論理記号で書くと、

(p \Rightarrow q) \Leftrightarrow ( (p \land q ) \lor ( \lnot  p))

となります。ここから式変形していきましょう。

まず、分配則を用いて、

( (p \land q ) \lor ( \lnot  p)) \Leftrightarrow ((p \lor ( \lnot p )) \land ( q \lor ( \lnot p )))

次に、(p \lor (\lnot p)) \Leftrightarrow 1 と交換則を q \lor ( \lnot p ) に適用して、

 ((p \lor ( \lnot p )) \land ( q \lor ( \lnot p ))) \Leftrightarrow (1 \land ( ( \lnot p ) \lor q))

それから、再び交換則を用いて、

 (1 \land ( ( \lnot p ) \lor q) ) \Leftrightarrow (( ( \lnot p ) \lor q) \land  1)

さらに、(p \land 1) \Leftrightarrow p を、p  ( \lnot p ) \lor q  として適用すると、

 (( ( \lnot p ) \lor q) \land  1) \Leftrightarrow ( ( \lnot p ) \lor q)

以上から、

(p \Rightarrow q) \Leftrightarrow (( \lnot p) \lor q)

よって示されました。



Ex.SetTop.1.5.3.

p \Rightarrow q と q \Rightarrow r が同時に成り立つとき、p \Rightarrow r が成り立ちます。これを仮言三段論法と言います。

全体を論理式で表すと、

((p \Rightarrow q) \land  (q \Rightarrow r)) \Rightarrow (p \Rightarrow r)

が成り立ちます。この命題が真であることを示してみましょう。

示すためには、上の式全体が 1 と同値であることを示せばよいです。( 1 は常に真であることを表すので、1 と同値であるというのは、命題が真であるということです)

まず、Ex.SetTop.1.5.2.の結果を使って式の全体を書き換えます。

((p \Rightarrow q) \land  (q \Rightarrow r)) \Rightarrow (p \Rightarrow r)
\Leftrightarrow
(((\lnot p) \lor q ) \land ((\lnot q) \lor r )) \Rightarrow ((\lnot p) \lor r )
\Leftrightarrow
\lnot(((\lnot p) \lor q ) \land ((\lnot q) \lor r )) \lor ((\lnot p) \lor r )

以下、次のように変形していきます。(どの計算法則を使っているのか自分で考えてみて下さい)

\lnot(((\lnot p) \lor q ) \land ((\lnot q) \lor r )) \lor ((\lnot p) \lor r )
\Leftrightarrow
(\lnot((\lnot p) \lor q )) \lor (\lnot((\lnot q) \lor r )) \lor ((\lnot p) \lor r )
\Leftrightarrow
(p \land (\lnot q) ) \lor (q \land (\lnot r) ) \lor (\lnot p) \lor r
\Leftrightarrow
((p \land (\lnot q) ) \lor (\lnot p)) \lor ((q \land (\lnot r) ) \lor r)
\Leftrightarrow
((p \lor (\lnot p) ) \land ((\lnot q) \lor (\lnot p))) \lor ((q \lor r ) \land ( (\lnot r) \lor r))
\Leftrightarrow
((\lnot q) \lor (\lnot p)) \lor (q \lor r )
\Leftrightarrow
((\lnot q) \lor q) \lor ((\lnot p) \lor r )
\Leftrightarrow
1 \lor (\lnot p) \lor r
\Leftrightarrow
1

よって、示されました。


 

論理記号.6へ>

<論理記号.4へ

記事一覧(大学数学.1)に戻る

関連記事

  1. 大学数学

    集合.16 集合の濃度.1 濃度の定義と比較方法

    有限集合と無限集合、濃度直観的に意味がわかると思うのでここまで…

  2. 大学数学

    集合.5 添字集合と集合族

    添字集合と集合族より一般の場合の共通集合や和集合を考えるために…

  3. 大学数学

    集合.17 集合の濃度.2 可算集合

    どこまでが高々可算集合なのか?自然数全体の集合 \( \mat…

  4. 大学数学

    集合.3 補集合、差集合

    補集合集合 \( A \) は全体集合 \( X \) の部分…

  5. 大学数学

    集合.18 集合の濃度.3 連続体濃度を持つ集合

    非可算集合可算濃度 \( \aleph_0 \) よりも濃度が…

  6. 大学数学

    集合.20 選択公理

    選択公理実は今までも暗に使っていたのですが、次のことは公理とみ…

コメント

  1. この記事へのコメントはありません。

  1. この記事へのトラックバックはありません。

アーカイブ

  1. 大学数学

    写像.4 逆写像
  2. 数学コラム

    虚数iは本当に存在しないのか?~iを作ってみた~
  3. 大学数学

    集合.21 上界、下界、上限、下限、最大元、最小元、極大元、極小元
  4. 大学数学

    写像.13 集合の準同型定理、引き起こされる写像
  5. 大学数学

    集合.15 集合の演算
PAGE TOP
error: Content is protected !!