大学数学

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

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

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

  2. 大学数学

    論理記号.6 否定の作り方

    否定の作り方~一定のルールに則って否定を作ろう~数学において、…

  3. 大学数学

    写像.6 標準的な写像の例

    標準的な写像の例今回はいくつかの標準的な写像について例を挙げて…

  4. 大学数学

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

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

  5. 大学数学

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

    多様体現代幾何学の中心的な対象である多様体について学びます。…

  6. 大学数学

    集合.15 集合の演算

    集合の演算ここまで、べき集合、和集合、補集合、差集合、共通集合…

コメント

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

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

アーカイブ

  1. 大学数学

    集合.6 共通集合と和集合(一般の場合)
  2. 大学数学

    集合.3 補集合、差集合
  3. 大学数学

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

    集合.4 共通集合と和集合(n個の場合)
  5. 大学数学

    集合.13 同値類と集合の分割
PAGE TOP
error: Content is protected !!