命題と論理

論理はやっぱ大切。 なので、復習がてらまとめる。

命題(Proposition)の定義

論理的に正しいか正しくないか(間違い)を判定可能な叙述のこと。

正しいか正しくないかの表現方法

命題論理における正しさと間違いの表現方法。

-正誤
論理学True/T/真False/F/偽
ブール代数単位元1零元0

アリストテレスの思考の3法則

思考(論理)の公理的な法則1としては次の3つの法則がある。

原則説明論理式
同一律 (identity)「何であれ、ある事物Aは同じ事物Aである」ことFor all A, A = A.
無矛盾律 (non-contradiction)「ある事物について同じ観点でかつ同時に、それを肯定しつつ否定することはできない」こと。2¬(A∧¬A) = T.
排中律 (excluded middle)「命題は成立するか成立しないかのどちらか以外は起こらない」こと。¬¬(A∨¬A) = T.

論理演算の5つの演算子

命題論理とブール代数は代数的構造が同じになる。3

演算子命題論理ブール代数集合
否定¬x̅全体集合の補集合
または+∨和集合
かつ・∧積集合
ならば⇒⇒部分集合
同値⇔=全単射

命題論理における真理値表

それらの命題論理の演算子を使ったの計算結果の例。

PQ¬P¬¬PP ∧ QP ∨ QP ⇒ QQ ⇒ PP ⇔ Q
TTFTTTTTT
TFFTFTFTF
FTTFFTTFF
FFTFFFTTT

ブール代数の性質

公式例
可換則A · B = B · A
A + B = B + A
結合則A · (B · A) = (A · B) · C
A + (B + C) = (A + B) + C
吸収則A · (A + B) = A
A + (A · B) = A
分配則A · (A + B) = A · B + A · C
A + (B · C) = (A + B) · (A + C)
相補則A · A' = 0
A + A' = 1
1' = 0
0' = 1
同一則A + 0 = A
A + 1 = 1
A * 1 = A
A * 0 = 0
べき等則A · A = A
A + A = A
二重否定則(A')' = A
ド・モルガンの法則(A + B)' = A' · B'
(A · B)' = A' + B'

3つの推論方法

推論とは，いくつかの命題を根拠にして，1 つの命題を導き出すこと。代表的に次の3つが使われる。

式説明
否定式P ⇒ Q という事実と ～Q という事実から，～P という事実を導き出す推論方
肯定式P ⇒ Q という事実と P という事実から，Q という事実を導き出す推論方法
三段論法P ⇒ Q という事実と Q ⇒ R という事実から，P ⇒ R という事実を導き出す推論方法

命題論理 vs. 述語論理

論理意味例
命題論理リテラルのみを使用する論理のことnが偶数 => n+2は偶数
述語論理量子化や述語(関数)を使用する論理のこと∀n∈ℕ: even(n) ⇒ even(n+2)

2つの量子化

演算子使い方意味確率主張
全称量化子(∀x) P(x)すべてのxに対してPである100%ある
特称量化子(∃x) P(x)あるxに対してPであるnot 0%少なくとも一つはある

間違えやすいモノ

論理包含の同値は対偶

  • ある命題論理「東京に住んでいるならば日本に住んでいる」の同値は、
  • 「日本に住んでいないならば東京に住んでいない」になる。
PQ¬Q ⇒ ¬P住所の例
TTT日本に住んでいない => 東京に住んでいない
TFF日本に住んでいる => 東京に住んでいない
FTT (vacuous truth)　日本に住んでいない => 東京に住んでいる
FFT (vacuous truth)日本に住んでいる => 東京に住んでいる

論理包含の否定は論理積を使う

  • よくある勘違いが論理包含の否定パターン。
  • 「AならばB」の否定を「AでないならばB」、あるいは「AならばBでない」と考えてしまうのは正しくない。
  • 「AならばB」の否定は、「AではあるがBではない」、つまり「AかつBでない」。
  • 例で言えば、「東京に住んでいるかつ日本に住んでいない」となる。
  • 前提条件を満たしているが結論を満たしていないということが、「AならばB」の否定となるといこと。
PQP ∧ ¬Q住所の例
TTF東京に住んでいる ∧ 日本に住んでいない
TFT東京に住んでいる ∧ 日本に住んでいる
FTF東京に住んでいない ∧ 日本に住んでいない
FFF東京に住んでいない ∧ 日本に住んでいる

論理包含のvacuous truth

  • 論理包含では、前件がFalseの場合は命題論理は意味をなさない。
    • 例: 「東京に住んでいない => 日本に住んでいる」は意味が通じない
  • なぜその場合にTrueになる(vacuous truth)かというと、計算上都合がいいから。
  • なぜなら、論理積による否定のさらに否定(~(P ∧ ¬Q))が論理包含と同値になるため
PQP ⇒ Q住所の例
TTT東京に住んでいる => 日本に住んでいる
TFF東京に住んでいる => 日本に住んでいない
FTT (vacuous truth)東京に住んでいない => 日本に住んでいる
FFT (vacuous truth)東京に住んでいない => 日本に住んでいない

トートロジーと同値の違い

  • 一般的に使われる言語のトートロジーはBoys will be boysみたいな反復または言い換え。4
  • だが、論理学のトートロジーは常にTrueになることなので注意。
用語意味
Tautology常にTrueの式のこと5
例: (P ⇔ Q) ∨ (Q ⇔ P)
Equivalent2つの式が同じ値であること

トートロジーの例

PQP ⇒ QQ ⇒ P(P ⇔ Q) ∨ (Q ⇔ P)
TTTTT
TFFTT
FTTFT
FFTTT

推論の2つのパターン

パターン|説明| ---|---|--- 演繹(deduction)|一般的かつ普遍的な事実を前提とし、そこから結論を導きだす方法|((A ⇒ B) ∧ A) => B 帰納(induction)|さまざまな事実や事例から導き出される傾向をまとめあげ、結論につなげる方法|枚挙的帰納法、アナロジー(類推)、アブダクション(仮説形成)

充足可能性問題(SAT問題)

  • 「一つの命題論理式が与えられたとき、それに含まれる変数の値を偽(False)あるいは真(True)にうまく定めることによって全体の値を'真'にできるか？」という問題
  • 例: (x ∨ y) ∧ (x ∨ ¬y) ∧ (x ∨ ¬y)
    • x=T, y=Fで全体としてTにできるので、Yes
  • この問題はNP完全問題として知られている。

ちなみに、ある問題XがNP完全問題であることは一般に次のように求める6。

  1. 問題XがNPに属することを示す。
  2. NP完全であることが既知の問題Aを、多項式時間で問題Xに変換可能であることを示す。
  3. 以上より、XはAと同等かそれより難しい。しかし、NP完全問題はNPの中で一番難しい問題なので、XはAと同じくNP完全問題である。

普遍的な論理表現の例

日常生活で役に立つ普遍的な命題論理。

  • 自分ができること ∧ 他人が求めていること = 提供できる価値
  • 因果関係がある ⇒ 相関関係がある

19の誤謬のパターン

オンラインブック7がわかりやすい。

1

Law of thought https://en.wikipedia.org/wiki/Law_of_thought 5: Truth Tables, Tautologies, and Logical Equivalences https://sites.millersville.edu/bikenaga/math-proof/truth-tables/truth-tables.html 4: Tautology (language) https://en.wikipedia.org/wiki/Tautology_(language) 2: 無矛盾律 https://ja.wikipedia.org/wiki/%E7%84%A1%E7%9F%9B%E7%9B%BE%E5%BE%8B 3: 記号論理学 https://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/math/logic/logic.htm 7: Bad Arguments https://bookofbadarguments.com/jp/ 8: Bad Arguments https://bookofbadarguments.com/jp/ 6: 大人になってからの再学習 http://zellij.hatenablog.com/entry/20131019/p1