【お知らせ】プログラミング記事の投稿はQiitaに移行しました。

論理包含の定義に関する違和感について

論理包含という論理演算子があります。A → B は「AならばB」と読み、ブール代数的には !(A && !B)(または !A || B)と定義されます。(Trueは真、Falseは偽)

A B A → B !(A && !B)
T T T → T = T !(T && !T) = !(T && F) = !F = T
T F T → F = F !(T && !F) = !(T && T) = !T = F
F T F → T = T !(F && !T) = !(F && F) = !F = T
F F F → F = T !(F && !F) = !(F && T) = !F = T

後ろ2つ(Aが偽のとき)の定義に違和感があり、なぜこういう演算を考えたのか腑に落ちませんでした。現時点での理解を書いておきます。

  • 2019.10.23 モーダスポネンスにより再構成しました。
  • 2019.10.17 推移律により再構成しました。
  • 2018.03.08 対偶により再構成しました。

目次

概要

A → B は推移律や対偶などが成立するように組み立てられた論理演算です。

T → F(Aが真、Bが偽)を偽と決めて、それ以外は「間違っていなければ良い」と割り切って真とします。論理式で表せば !(A && !B) となり、ベン図で表現できます。

f:id:n7shi:20191017130703p:plain

不定

「AならばB」という命題は、「Aが真ならば必ずBは真となる」ことを表します。

※ 英語では "if A then B" または "A implies B" と読みます。

「AならばB」を A → B と表記します。Aを前件、Bを後件と呼びます。

AとBの両方が真であれば A → B も真となります。Aが真でもBが偽であれば A → B は偽となります。これらは直感に沿っているため、以下の2つに違和感はありません。

  • T → T = T
  • T → F = F

if A then Bプログラミング言語として考えたときと同じ挙動です。

問題はAが偽であるケースです。「AならばB」はAが真であることを前提としているため、Aが偽であるケースは想定外です。素直に考えれば「AならばB」は不定です。

if A then Bプログラミング言語として考えれば else が足りません。JavaScriptでは undefined となります。

> a=false,b=true
> if (a) b
undefined

不定(T/F)とする解釈は Non-Truth-Functional Interpretation と呼びます。

古典論理

すべての論理式を真偽の二値として扱う論理体系を古典論理と呼びます。

古典論理では、全ての論理式に真か偽の真理値 ( ${⊤ , ⊥}$ ) が割り当てられる。このときその真理値に対する直接的なエビデンスを持つか否かは問題にしない。これはどのような曖昧な命題においても「真か偽かが決定可能である」ということを意味する。

古典論理では F → TF → F不定とはできないため、真か偽のどちらかに決める必要があります。

※ 中間の状態(不定)を排除するということから排中律と呼びます。

モーダスポネンス

ここまでに決めた T → T = T から分かることを確認します。

命題 A → B が真だとします。

  • A → B = T

このときAが真だとします。

  • T → B = T

これが成り立つにはBが真である必要があります。

  • T → T = T

まとめると「A → B が真かつAが真ならば必ずBは真」となります。式で表します。

((A → B) ∧ A) → B

この式をモーダスポネンスと呼びます。

由来よりAとBがともに真であれば当然モーダスポネンスは真となります。

  • ((T → T) ∧ T) → T = (T ∧ T) → T = T → T = T

古典論理ではモーダスポネンスはAとBの真偽に依らず常に真であることを要請します。

※ こうすれば実用上便利な論理体系が構成できるということです。このように常に真となる論理式を恒真式と呼びます。(後述

すべての組み合わせを調べます。途中で不明な部分が ? ∧ F として現れますが、これは ? の真偽に依らず常に偽となります。

A B ((A → B) ∧ A) → B = T
T T ((T → T) ∧ T) → T = (T ∧ T) → T = T → T = T
T F ((T → F) ∧ T) → F = (F ∧ T) → F = F → F = T
F T ((F → T) ∧ F) → T = (? ∧ F) → T = F → T = T
F F ((F → F) ∧ F) → F = (? ∧ F) → F = F → F = T

以上より前件が偽であるときの論理包含の値が決まりました。

  • F → T = T
  • F → F = T

モーダスポネンスは A → B やAやBが必ずしも真でなくても成り立つように拡張されたため「A → B においてAであれば、Bとなる」と読み替えられます。

※ プログラミングでアロー関数に引数を適用するのに似ています。

> (a => 'b')('a')  // (A → B) ∧ A
'b'                //    → B

性質

A → B に対して !B → !A対偶と呼びます。T → TF → F は対偶の関係でともに真で等しく、T → FF → T は対偶が元に戻ることから、対偶は真偽が等しいことが分かります。これを対偶律と呼びます。

(A→B)→(¬B→¬A)

A → B に対して B → Aと呼びます。T → TF → F は逆が元に戻るため真偽は等しいですが、T → FF → T は逆の関係で真偽が異なることから、逆の真偽は必ずしも等しくないことが分かります。

A → B に対して !A → !Bと呼びます。逆と裏は対偶の関係にあるため真偽は等しいです。

解釈

記号論理学の作法として、例えば「a ⇒ b」は「a ならば b」であると解釈されるが、こう書いたからといって a が真であることを主張はしていない。あくまで「もしも a が真ならば b も真である。a が偽ならば b は真でも偽でもよい」と述べているだけである。

A → B が偽となるのは T → F(Aが真、Bが偽)だけで、それ以外はすべて真です。定式化すれば (A && !B) == F となり、書き換えれば !(A && !B) が得られます。

A -> B と「ならば」との関係は、「A であるのに B でないことはない」と考えるのだと読んだことがあります。これを論理式にすると、¬(A ∧ (¬B)) です。

日常的なたとえ話でも「偽となるのは T → F だけ」で、「偽でなければ(消極的に)真だと認める」という論法を使っています。

ある人が「この仕事が失敗したら辞表を出す」と言ったとしよう。この言葉が嘘となるのは、仕事が失敗したにもかかわらず辞表を出さなかった場合のみである。仕事が失敗して辞表を出したならば約束を守ったのであるし、仕事が成功して(失敗せず)かつ辞表を出さなかったならば、やはりその人は嘘を言わなかったことになる。仕事が成功したにもかかわらず(何か他の理由で)辞表を出した場合も、やはり嘘を言ったとはみなされないであろう。すなわち、先の宣言では仕事が成功した場合のことは何も言っていないのであるから、辞表を出そうが出すまいが本人の自由である。

ここから「偽となるのは T → F だけ」は読み取れますが、「何も言っていない」グレーゾーンが「偽でなければ真」だとされることには違和感が残るかもしれません。

反例

命題が偽となるケースは反例として扱われます。前述のたとえ話で「嘘」と言っているのは反例に相当します。もし反例が1つでもあれば命題は不成立となるため、偽の判定には慎重を要します。

!(A && !B) のベン図を再掲します。

f:id:n7shi:20191017130703p:plain

白い部分はAがBからはみ出している部分です。これは命題 A → B が偽となる反例で T → F に相当します。(Aが真、Bが偽)

※ はみ出した部分がなければ完全な包含関係となり、命題は満たされます。

もし仮に F → B を偽とすれば反例として扱われることになります。反例が1つでもあれば命題は不成立となってしまうため、不定である F → B は反例から除外する必要があります。そのため F → B を消極的に真として扱うと考えられそうです。

つまり「間違っていなければ良い」と割り切ると解釈できるでしょう。

別の考え方

納得できるポイントは人によって違うでしょう。いくつか別の考え方を紹介します。

包含関係

$A→B$ は「Aが真ならば必ずBは真となる」です。これを真となる元の集合と読み替えれば「Aの元ならば必ずBの元となる」となり、これは $A⊂B$ に対応します。

f:id:n7shi:20191022200039p:plain

このように包含関係が認められることが「論理包含」や「意」という名前の由来になっています。

ところで補集合は包含関係が逆になります。

(A⊂B)→(B^c⊂A^c)

補集合を否定に読み替えれば対偶律が得られます。

(A→B)→(¬B→¬A)

逆の包含関係 $A⊃B$ も同時に満たされるのは集合が一致するとき $A=B$ だけで、必ずしも一致しないことも読み取れます。もしAがBからはみ出していれば、そのはみ出した部分が反例となります。

対偶と逆

先ほどは論理包含の値を決めてから対偶と逆の性質を見ましたが、反対にそこから始めて論路包含の値を決めることもできます。

対偶律を要請すれば、T → T の対偶 F → F は真となります。

  • F → F = T

T → F の対偶は T → F で元に戻るため、残る F → T を決めるには別の要請が必要です。

逆の真偽が必ずしも等しくないことを要請すれば、T → F とその逆 F → T とは真偽が異なることになります。

  • F → T = T

既に T → TF → F は真であると決まっているため、残りの T → FF → T の真偽を異ならせれば、逆の真偽は必ずしも等しくなくなります。

まず、A -> B の満たすべき性質として、「逆また真ならず」という推論の性質がある。つまり、A -> B が真であるからと言って必ずしも B -> A が真ではないということだ。

対偶と後件

対偶律に加えて、後件が真のときに命題も真とすることを要請します。

つまり A → T がAに依らず真となることを要請すれば、その対偶として F → B はBに依らず真となります。

(a) $q$ が無条件に正しければ,$p$ の正否にかかわらず $p⇒q$ は正しい;
(b) $p$ が正しくないならば,$q$ の正否にかからわず $p⇒q$ は正しい;

※ (a)の対偶が(b)です。

まとめると次のように解釈できます。

論理における「P ならば Q」は、「P でない、と Q である、の少なくとも一方が正しい」の短い言い換えなのである。

含意とは、前件が偽、または後件が真のときに真となるように規約された論理的二項関係

これは真となる F → F, F → T, T → T に注目した解釈で、定式化すれば定義としてよく紹介される !P || Q となります。ド・モルガンの法則により !(P && !Q) と同値となり、こちらは前述のように偽となる T → F に注目しています。

推移律

推移律 ((A → B) ∧ (B → C)) → (A → C) がA,B,Cの真偽に依らず常に成り立つ、つまり恒真式であることを要請すれば F → TF → F の値が決まります。

A -> B かつ B -> C が真であれば A -> C も真であるという含意の推移律が成立するためには必要な条件なのだ。

※ 個人的には、推移律はA,B,Cがすべて真のときは直観的にも明らかなため、そのケースしか考えていませんでした。「A,B,Cの真偽に依らず常に成り立つ」という発想がありませんでした。

Aが真であるケースを調べます。途中で不明な部分が F ∧ ? として現れますが、これは ? の真偽に依らず常に偽となります。

A B C ((A→B) ∧ (B→C)) → (A→C) = T
T T T ((T→T) ∧ (T→T)) → (T→T) = (T ∧ T) → T = T → T = T
T T F ((T→T) ∧ (T→F)) → (T→F) = (T ∧ F) → F = F → F = T
T F T ((T→F) ∧ (F→T)) → (T→T) = (F ∧ ?) → T = F → T = T
T F F ((T→F) ∧ (F→F)) → (T→F) = (F ∧ ?) → F = F → F = T

以上の結果より、Aが偽であるケースもすべて成り立つことが確認できます。

A B C ((A→B) ∧ (B→C)) → (A→C) = T
F T T ((F→T) ∧ (T→T)) → (F→T) = (T ∧ T) → T = T → T = T
F T F ((F→T) ∧ (T→F)) → (F→F) = (T ∧ F) → T = F → T = T
F F T ((F→F) ∧ (F→T)) → (F→T) = (T ∧ T) → T = T → T = T
F F F ((F→F) ∧ (F→F)) → (F→F) = (T ∧ T) → T = T → T = T

なお、推移律でAが真であるケースはモーダスポネンスと等しいです。

\begin{aligned} &( (⊤ → B) ∧ (B → C) ) → (⊤ → C) \\ &⇔\ (B ∧ (B → C)) → C \\ &⇔\ ((B → C) ∧ B) → C \end{aligned}

記号について

$A→B$ を $A⊃B$ と表記する本があります。この場合の $⊃$ は集合とは関係のない記号だとされます。前述のように集合との対応は $A⊂B$ のため、集合をイメージしてしまうと記号が逆になるので混乱します。

また、$A⊃B$ を "A implies B"(AはBを包含する)と読むことがあり、集合とは無関係だと意識していてもやはり混乱します。

こじつけ

無用な混乱を避けるためには $A⊃B$ ではなく $A→B$ と書いて「AならばB」と読みたい所ですが、そういう流儀の本ばかりではありません。

※ 以下、個人的な対処法を書きます。属人的な内容のため無視しても構いません。

論理式で $⊃$ を見掛けたときは、真ん中に線を引いて $∋$ をイメージしてから、先を尖らせて矢印 $→$ に読み替えるという方法で対処しています。

また、$(A∧B)→A$ となることから、これを命題の集合だと思って $\{A,B\}⊃\{A\}$ にこじつけたりもしています。

恒真式

私が論理包含について初めて意識したのはデータベースの本がきっかけです。

恒真式について説明されています。

パラメータとなる命題の値にかかわらず、結果が常に真となる論理式を、トートロジーあるいは恒真式と呼びます。

次に、命題論理でよく使われる定理=トートロジーを紹介します。読者のみなさんの中には、すでにこのような論理式に親しみのある方も少なくないのではないかと思います。これらの定理がトートロジーになっていることを、ぜひ真理値表を書いて確かめてみてください。

  • 同一律 ... $P ⊃ P$
  • 排中律 ... $P ∨ ¬ P$
  • 二重否定律 ... $¬ ¬ P ≡ P$
  • 矛盾律 ... $¬ ( P ∧ ¬ P )$
  • Principle of explosion ... $( P ∧ ¬ P ) ⊃ Q$
  • 対偶律 ... $( P ⊃ Q ) ⊃ ( ¬ Q ⊃ ¬ P )$
  • 推移律 ... $( ( P ⊃ Q ) ∧ ( Q ⊃ R ) ) ⊃ ( P ⊃ R )$
  • 分配律 ... $P ∧ ( Q ∨ R ) ≡ ( P ∧ Q ) ∨ ( P ∧ R )$ あるいは $P ∨ ( Q ∧ R ) ≡ ( P ∨ Q ) ∧( P ∨ R )$
  • ド・モルガン ... $¬ ( P ∨ Q ) ≡ ¬ P ∧ ¬ Q$ あるいは $¬ ( P ∧ Q ) ≡ ¬ P ∨ ¬ Q$
  • 前件肯定式 ... $( ( P ⊃ Q ) ∧ P ) ⊃ Q$
  • 後件否定式 ... $( ( P ⊃ Q ) ∧ ¬ Q ) ⊃ ¬ P$
  • 選言的三段論法 ... $( ( P ∨ Q ) ∧ ¬ P ) ⊃ Q$

※ 前件肯定式はモーダスポネンスです。

この本では 「ならば」に $⊃$ を使っていますが、当時は集合に引きずられてとても混乱しました。そのときの試行錯誤がこの記事を書く動機になっています。

結合の変更

論理包含には結合則は成り立ちませんが、それに相当する書き換えがあります。

\begin{aligned} &(A∧B)→C \\ &⇔\ ¬(A∧B)∨C \\ &⇔\ (¬A∨¬B)∨C \\ &⇔\ ¬A∨(¬B∨C) \\ &⇔\ ¬A∨(B→C) \\ &⇔\ A→(B→C) \end{aligned}

※ 最初 $(A∧B)→C$ と最後 $A→(B→C)$ の式は、どちらも $C$ が成立するために $A$ と $B$ が仮定されていると解釈できるため、直観的に結び付きます。

この書き換えによってモーダスポネンスが同一律に帰着することが分かります。

\begin{aligned} &((P → Q) ∧ P) → Q \\ &⇔\ (P → Q) → (P → Q) \end{aligned}

同様に後件否定式は対偶律に帰着します。

\begin{aligned} &((P → Q) ∧ ¬Q) → ¬P \\ &⇔\ (P → Q) → (¬Q → ¬P) \end{aligned}

選言的三段論法は論理包含の定義と二重否定律によって同一律に帰着します。

\begin{aligned} &((P ∨ Q) ∧ ¬P) → Q \\ &⇔\ (P ∨ Q) → (¬P → Q) \\ &⇔\ (P ∨ Q) → (¬¬P ∨ Q) \\ &⇔\ (P ∨ Q) → (P ∨ Q) \end{aligned}

直観主義論理

古典論理の節直観主義論理の記事を引用しました。ついでに簡単に紹介します。

直観主義論理はここまで見て来た古典論理とは別の論理体系です。定理証明支援系の Coq が採用しています。

証明論的な視点から見ると、直観主義論理は古典論理の制限であって排中律や二重否定除去が公理として許容されないものである。

多くの古典論理の恒真式は直観主義的には証明できない。排中律 $p∨¬p$ だけでなくパースの法則 $((p→q)→p)→p$ や二重否定除去 $¬¬p→p$ などがその例である。古典論理において二重否定導入 $p→¬¬p$ と二重否定除去 はともに定理である。直観主義論理においては前者のみが定理である。すなわち二重否定を導入することはできるが、除去することはできない。

公理を追加することで古典論理が再現できます。

古典論理の体系は次のどれかを公理に追加することによって得られる:

  • $ϕ∨¬ϕ$ (排中律。これは $(ϕ→χ)→((¬ϕ→χ)→χ)$ とも定式化できる。)
  • $¬¬ϕ→ϕ$ (二重否定除去)
  • $((ϕ→χ)→ϕ)→ϕ$ (パースの法則)

参考

不定とするモデルが議論されていたというコメントを見掛けました。

真偽値なしや特殊な値(不定など)と考える人もいました。 ですから、真偽値なしや不定と考えることは、 それほど不自然なことではないと言えます。

3値論理にはいくつか種類がありますが、不定とするモデル (Non-Truth-Functional Interpretation) は採用されていません。

未読ですが、関連する書籍があるようです。

戸田山先生の「論理学をつくる」に、条件文の真理表がこうあるべき事情が書かれています。

今、『論理学をつくる』戸田山和久著を読んでいる。分厚い本だが、教科書に書いてないことがたくさん説明してあって、なるほどそういうことだったのか目からウロコの内容が多い。その中で含意の真理値表がどうしてあのようになるのかの説明があってよくわかった。

直接は関係ありませんが、論理を真偽値ではなく確率として扱う確率論理というのがあります。

原論文では論理包含から議論を始めています。論理演算が確率の加法・乗法に変換されるのが興味深いです。似た話題は前掲のスタンフォードのテキストでも取り上げられています。