大学数学

論理記号.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. 大学数学

    集合.6 共通集合と和集合(一般の場合)

    共通集合と和集合(一般の場合)添字集合と集合族の概念を使って、…

  2. 大学数学

    数の構成.1 自然数.1 ペアノシステムと自然数の構成

    数の構成~自然数から複素数へ~前回まで、一般的な集合や写像の性…

  3. 大学数学

    集合.10 直和(非交和、無縁和)

    直和(非交和、無縁和)◆Def.SetTop.2.…

  4. 大学数学

    集合.11 二項関係.1 順序

    二項関係今回からは二項関係というものを考えていきます。二項関係…

  5. 大学数学

    写像.3 写像の合成

    写像の合成高校数学で合成関数というものをやったかと思いますが、…

  6. 大学数学

    集合.14 商集合

    商集合前回の話で、同値類が集合の分割を与えるので、同値類をすべ…

コメント

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

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

アーカイブ

  1. 大学数学

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

    大学数学概説.3 大学3、4年生レベルの科目(代数)
  3. 大学数学

    写像.3 写像の合成
  4. 大学数学

    写像.8 単射の性質
  5. 大学数学

    論理記号.3 すべての、~が存在する
PAGE TOP
error: Content is protected !!