logic
数学
論理演算
記号
集合

ろんりについてまとめる

はじめに

この記事は「ろんりと集合」という中内伸光さんの本を参考に記述しています.
この本で勉強をしていて、大事なことをまとめようとしています.
この本の引用を多少用いています.
この本の本質的なことはこの記事からは確認できません.

$ \lnot (完成) \lor \lnot \lnot (未完成) $

ろんり

文の構造を記号化すると、文の構造を把握しやすくなる

  • 思考の節約

記号論理学

  • 命題論理学
    • 「〜である.」
  • 述語論理学
    • 「すべての〜、ある〜」

論理について

  • 「対象としての『論理』」
  • 「『論理』を議論するための『論理』」(メタ論理)

命題

  • 「客観的に正しいか正しくないかが判断できる主張」
    • 誰が見ても「正しい」と判断できる主張
    • 誰が見ても「正しくない」と判断できる主張

真理値

  • 「正しい」ことを「真(1)である」
  • 「正しくない」ことを「偽(0)である」

真理値表

NOT

$ \lnot p $

$p$ $ \lnot p $
1 0
0 1

AND

$ p \land q $

$p$ $q$ $ p \land q $
1 1 1
1 0 0
0 1 0
0 0 0

OR

$ p \lor q $

$p$ $q$ $ p \lor q $
1 1 1
1 0 1
0 1 1
0 0 0

同値

同じものではないけれど、同じと見なしたい動機がある

$ p \equiv q$

反射法則

二重否定は元の命題と同値

$ \lnot \lnot p \equiv p $

結合法則

どこから計算しても同じ

p q r $ p \land q $ $ (p \land q) \land r $ $ q \land r $ $ p \land (q \land r) $
1 1 1 1 1 1 1
1 1 0 1 0 0 0
1 0 1 0 0 0 0
1 0 0 0 0 0 0
0 1 1 0 0 1 0
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 0 0 0 0

ANDだけでなく、ORについても結合法則が成り立つ.
* $ (p \land q) \land r \equiv p \land (q \land r) $
* $ (p \lor q) \lor r \equiv p \lor (q \lor r) $

記号論理では、ある法則が成り立つとき、
「その法則の$\land$を$\lor$に、そして、$\lor$を$\land$に置き換えた法則が成り立つ」
原理、これが双対性.(2つのことがら・概念が互いに鏡で映し合っている対称性がある状況)

命題論理の7つの法則

1. 反射法則

二重否定は元の命題と同値

$ \lnot \lnot p \equiv p $

2. ベキ等法則

AND、ORを何回繰り返しても同値

  1. $ p \land p \equiv p $
  2. $ p \lor p \equiv p $

3. 交換法則

ひっくり返しても同値

  1. $ p \land q \equiv q \land p $
  2. $ p \lor q \equiv q \lor p $

交換法則が成り立つ場合の方が少数
* 爪を切って、爪を研ぐ.
* 爪を研いで、爪を切る.

4. 結合法則

どこから計算しても同値

$ (p \land q) \land r \equiv p \land (q \land r) $
$ (p \lor q) \lor r \equiv p \lor (q \lor r) $

5. 分配法則

分配しても同値

  1. $ p \land (q \lor r) \equiv (p \land q) \lor (p \land r) $
  2. $ p \lor (q \land r) \equiv (p \lor q) \land (p \lor r) $

左からも右からも分配できる.
$ (p \lor q) \land r $

6. 吸収法則

同値変形の小道具

  1. $ p \land (p \lor q) \equiv p $
  2. $ p \lor (p \land q) \equiv p $
p q $ p \lor q $ $ p \land (p \lor q) $ $ p \land q $ $ p \lor (p \land q) $
1 1 1 1 1 1
1 0 1 1 0 1
0 1 1 0 0 0
0 0 0 0 0 0

吸収法則を用いいなければ、簡単な式にできないものもある.
(分配法則、ベキ当法則)
$ p \land (p \lor q) \equiv (p \land p) \lor (p \land q) \equiv p \lor (p \land q) $
じつはこれはPと同値ですけどね.

7. ド・モルガンの法則

「否定の必須道具」

  1. $ \lnot(p \land q) \equiv \lnot p \lor \lnot q $
  2. $ \lnot(p \lor q) \equiv \lnot p \land \lnot q $

同値変形

  • 恒真命題 : $I$
    • 真理値を1しか取らない命題
  • 恒偽命題 : $O$
    • 真理値を0しか取らない命題

$\lnot I = O$
$\lnot O = I$

恒真命題の性質

  1. $ p \land I \equiv p $
  2. $ p \lor I \equiv I $

恒偽命題の性質

  1. $ p \land O \equiv O $
  2. $ p \lor O \equiv p $

恒真命題と恒偽命題は双対的

矛盾法則

$ p \land \lnot p \equiv O $

拝中法則

$ p \lor \lnot p \equiv I $

継続中ですー.

参考資料さん

「ろんりと集合」 著:中内伸光