ベン図と集合と論理と Haskell

ベン図の集合と論理

素朴集合の直観的なモデルとしてベン図があるが、ベン図上で集合と論理がどのように表現されるかを考えてみた。

まず、考察の対象とする個体の集合を領域(D, domain) と呼ぶことにする。ベン図では全体集合と呼ばれている。領域 D の要素は個体であり、集合は含まれていない。

この領域 D の部分集合を集合(Set)と定義する。今考えているのは領域 D が有限集合なので、その部分集合である集合は必ず存在する。

領域 D のべき集合を Pow(D) とすると、Pow(D) の要素は領域 D における集合を網羅している。

述語 P(x) は領域 D から二値集合 {True, False} への関数である。また領域 D の要素と述語 P(x) のペア (a, P) を命題という。P(a) は a の P(x) による値で True, または False だが、これを表記に注目してP(a)という命題とみなしてもいい。

領域 D のすべての要素に述語 P(x) を適用することを領域 D に述語 P(x) をマッピングすると呼ぶことにする。また、領域 D の要素 a と 命題 P(a) の値のペア、(a, P(a)) を述語 D のマップと呼ぶことにする。ただし、いずれも正規の用語ではない。説明の利便のための造語だ。

述語 P(x) のマップでは、領域 D のそれぞれの要素に真理値 {True, False} のいずれかの値が割り振られている。このとき、述語 P(x) を True にする領域 D の要素を集めるとそれは集合になる。この集合を述語 P(x) の真理集合と呼ぶ。述語 P(x) は無限に考えることができるが、領域 D の個体全てに P(a) が True であるか False であるかを割り当てることが述語 P(x) の条件である。P(a)が真であるか偽であるか確定できないラッセルの集合のようなものの述語は排除される。

述語 P(x) の真理集合は必ず領域 D の部分集合であり、領域 D の部分集合の全ては Pow(D) の要素である。したがって、述語Pが無限にあってもそのなかには真理集合が同じ述語どうしがある。真理集合が同じ述語どうしは論理的に同値である。無限の述語があっても、それは真理集合によって同値類に分けられる。

このような条件のもとにあっては、集合は述語による内包的定義で定義することができる。すなわち、

{x | P(x) == True}

である。

このモデルでは論理演算は2値集合 {True, False} における2項演算である。これは単に命題の値に関する演算規則でしかない。たとえば P(a) ∧ Q(b) の真理値は P(a) の真理値と Q(b) の真理値のみから計算される。命題 P(a) と Q(b) の内部的な論理関係は問題にされない。このような定義では含意は単なる2項演算であり A -> B = ¬A ⋁ B である。

このような条件下で、集合演算と論理の関係を考えてみる。集合 A を内包的に定義する述語を A(x) とし、集合 B を内包的に定義する述語を B(x) とする。このとき、述語 A(x) のマップは (x, A(x)) で述語 B のマップは (x, B(x)) である。領域 D の上にマップ A と マップ B を重ね合わせると、領域 D の要素 a で A(a) と B(a) が共に True の場合、A(a) と B(a) が異なる場合、A(a) と B(a) が共に False の場合がある。

このとき、集合 A と集合 B の両方に属する D の要素を a とすると、A(a) は True で B(a) も True である。したがって、A(a) ∧ B(a) も True である。a が集合 A と 集合 B の共通部分であるとき命題 A(a) ∧ B(a) は常に真となる。

逆に、A(a) ∧ B(a) が True のときは、A(a) と B(a) は共に True だから、要素 a は A と B の共通部分に含まれる。したがって A(x) ∧ B(x) は集合 A ⋂ B を内包的に定義する述語である。

ただし、この集合演算と論理演算の対応関係は、述語の論理演算に関してしか成立しない。つまり、A(x) と B(x) は同じ個体 x を主語としていなければならない。たとえば、領域 D で命題 A(a) と命題 B(b) の真理値が True の場合、A(a) ∧ B(b) の値も True だが、これが集合 A と 集合 B の共通部分の存在を表しているというわけではない。集合と論理の関係は全般的なものではなく、命題論理の起こり得る可能性のうちの部分的なものだ。

ベン図ではまた、量化子のある命題も説明できる。∀xA(x) は述語 A(x) がすべての個体について True となる場合に真であるから、次のように単純命題を ∧ 記号で結合した命題論理の複合命題になる。ただし、a0, ..., an は領域 D の全ての要素を列記しているものとする。

∀x P(x) = P(a0) ∧ P(a1) ∧ ... ∧ P(an)

主語と述語からなる単純命題は P(a) であるが、全証命題 ∀x P(x) は領域 D について述語 P(x) の命題すべての論理積である。同様に存在命題 ∃x P(x) は述語 P(x) の全ての単純命題の論理和である。

∃x P(x) は P(a0) ∨ P(a1) ∨ ... ∨ P(an)

このように、全称命題も存在命題も有限個の単純命題の複合命題だから、全称命題の否定 ¬ ∀x P(x) はド・モルガンの法則から次のように計算できる。

¬ ∀x P(x) = ¬P(a0) ⋁ ¬P(a1) ⋁ ... ⋁ ¬P(an)
= ∃x ¬P(x)

このようにベン図をモデルとして集合と論理を考えた場合、領域 D の(部分)集合については、一階述語論理のうち、主語が同じ述語の複合述語の性質で完全に記述できる。また、一階述語論理の論理関係のうち集合としては論じることができないものがあることも分かる。

一階述語論理が命題論理のどのような拡張であるか曖昧な印象があるが、有限集合の領域 D については、一階述語論理の命題も命題論理の命題に展開して論じることができる。また、論理と集合の関係も明確に述べることができる。

しかし、実際には、一階述語論理には主語の違う命題を扱っている様に見えるものがある。たとえば、イプシロン・デルタ論法のばあい次のような命題になる。

 ∀ε>0, ∃δ>0 s.t. ∀x∈R, 0<|x-a|<δ ⇒ |f(x)-b|<ε

命題の含意の前件と後件では主語が異なっているように見えるので上の議論は使えない。 しかし、この述語は、εとδとxの直積を領域 D ととれば、上に述べた議論を行うことができるが、ここでは詳しくは述べない。

ベン図とHaskell

このように領域が有限集合のベン図は、集合と論理の機械的な取扱ができるので、これを Haskell で記述してみた。Data.List モジュールの集合演算を利用するので Data.List をインポートする。

Prelude> import Data.List

まず領域 D の要素をアルファベット1文字の a,b,c,d,e,f とする。

Prelude Data.List> domain = "abcdef"

領域 D のべき集合を計算する関数 pow を定義する。

Prelude Data.List> pow [] = [[]]; pow (x:xs) = map (x:) (pow xs) ++ pow xs
Prelude Data.List> pow domain
["abcdef","abcde","abcdf","abcd","abcef","abce","abcf","abc","abdef","abde","abdf",
"abd","abef","abe","abf","ab","acdef","acde","acdf","acd","acef","ace","acf","ac",
"adef","ade","adf","ad","aef","ae","af","a","bcdef","bcde","bcdf","bcd","bcef","bce",
"bcf","bc","bdef","bde","bdf","bd","bef","be","bf","b","cdef","cde","cdf","cd","cef",
"ce","cf","c","def","de","df","d","ef","e","f",""]

領域の要素数より、集合の方が格段に多いことが分かる。

Prelude Data.List> length domain
6
Prelude Data.List> length $ pow domain
64

要素が集合に属しているかどうかは、Prelude の elem 関数で調べることができる。

Prelude Data.List> elem 'a' "abc"
True
Prelude Data.List> elem 'd' "abc"
False

領域 D の要素を主語とする述語の真理値は要素が主語に含まれているかどうかで判別できるから次のように定義できる。

Prelude Data.List> p1 x = elem x "abd"
Prelude Data.List> p2 x = elem x "bcd"
Prelude Data.List> p1 'a'
True

これらの述語は domain の要素について排中律を満たしている。

Prelude Data.List> map (p1) domain
[True,True,False,True,False,False]

Haskell の内包表記を使うと、これらの述語で集合を内包的に定義できる。

Prelude Data.List> [x| x <- domain, p1 x]
"abd"
Prelude Data.List> [x| x <- domain, p2 x]
"bcd"

Data.List モジュールには集合演算 union と intersect が定義してある。

Prelude Data.List> "abd" `union` "bcd"
"abdc"
Prelude Data.List> "abd" `intersect` "bcd"
"bd"

これらの集合演算は述語の論理演算の真理集合と一致している。

Prelude Data.List> [x| x <- domain, (p1 x) || (p2 x)]
"abcd"
Prelude Data.List> [x| x <- domain, (p1 x) && (p2 x)]
"bd"

このように、領域 D が有限集合の場合、ベン図の様々な概念を Haskell でプログラムすることができる。

ベン図と含意

命題論理の含意は Haskell では次のように定義できる。

Prelude Data.List> imply x y = not x || y
Prelude Data.List> imply False True
True
Prelude Data.List> imply True True
True

そこで領域 D が "abcdef" のときこの命題論理の含意がどのような働きをするかを見てみる。

Prelude Data.List> domain = "abcdef"

まず、集合 "abc" と集合 "abcde" を内包的に定義する述語 p(x) と q(x) を作る。

Prelude Data.List> p x = elem x "abc"
Prelude Data.List> q x = elem x "abcde"
Prelude Data.List> [x | x <- domain, p x]
"abc"
Prelude Data.List> [x | x <- domain, q x]
"abcde"

q(x) の真理集合は p(x) の真理集合を包含している。すなわち P ⊂ Q である。

そこで、p(x) -> q(x) という述語の真理集合はどのようになるかを見てみる。

Prelude Data.List> [x | x <- domain, p x `imply` q x]
"abcdef"

これは真理集合が domain と一致している。すなわち真理集合 Q が真理集合 P を包含しているとき、領域 D の全ての要素について、p(x) -> q(x) は真となる。すなわち、∀x p(x) -> q(x) は真である。このように量化子 ∀x がついた述語の真理集合は領域そのものと等しいことが分かる。

それでは P を包含しない R の述語を次のように定義して、p(x) -> r(x) の真理集合がどのようになるかを見てみる。

Prelude Data.List> r x = elem x "bcd"
Prelude Data.List> [x | x <- domain, p x `imply` r x]
"bcdef"

この真理集合は Domain とは一致しない。要素 a が欠けている。a は p(x) -> r(x) の反例である。実際、要素

'a' は p(a) を真にするが、r(a) は偽なので、p(a) -> r(a) は偽である。

Prelude Data.List> p 'a'
True
Prelude Data.List> r 'a'
False
Prelude Data.List> p 'a' `imply` r 'a'
False

これらのことから、∀x p(x) -> q(x) という量化子のある命題が常に真の場合、量化子を除いた命題 p(x) -> q(x) の真理集合が領域と一致しなくてはならないことが分かる。また、それは述語 p(x) と q(x) の真理集合が包含関係にあることを意味している。この場合、p(x) -> q(x) という述語は、p(x) や q(x) の真理集合に含まれる要素以外の要素についても常に真となるのが、直感的な予測と異なって面白い。さらに、命題の真理値の演算である含意が、どういう風に真理集合の包含関係に関連しているのかが理解できる。

このように、ベン図モデルに Haskell を適用することにより、なんとなく掴みづらい量化子のある命題の意味をイメージ化することができる。

ベン図と量化子

領域 D = {a,b,c,d,e,f} において真理集合が {a,b,c} である2述語 P(x) と領域 D の要素 a からなる命題 P(a) の真理値は a ∈ {a,b,c} で求めることができる。Haskell で記述すると次のようになる。

Prelude> import Data.List
Prelude Data.List> domain = "abcdef"
Prelude Data.List> p x = elem x "abc"
Prelude Data.List> p('a')
True

それでは量化子のある命題 ∀x P(x) の真理値はどのようにして求めるのだろうか。それは P(a) ∧ P(b) ∧ ... ∧ P(f) で計算される。領域 D は有限離散集合なのでこのような考え方ができる。これを Haskell で記述すると次のようになる。

Prelude Data.List> and $ map p domain
False
Prelude Data.List> and $ map (\x->elem x domain) domain
True

同様に、∃x P(x) は P(a) ∨ P(b) ∨ ... ∨ P(f) で計算できる。Haskell では次のようになる。

Prelude Data.List> or $ map p domain
True

領域 D が離散集合の場合、量化子を伴う命題の場合も真理値を機械的に計算できる。この場合、量化子を伴う命題であっても、単なる複合命題の一つと考えることができる。

推論と Haskell

Haskell で命題論理の含意を定義するのは次のようにする。

Prelude> imply x y = not x || y

これを使って命題 A と B が真のとき A -> B の真理値を求めるのは簡単だ。

Prelude> imply True True
True

しかし、命題 A が真で、命題 A -> B が真のとき命題 B の真理値を求めるのは複雑な手続きが必要になる。命題 A -> B の真理値が True であったとしても、その時の命題 A と B の真理値の組み合わせは複数になるからだ。

そこで、まず、命題 A -> B の真理表を次のようにして作る。

Prelude> implytbl = [(imply x y, (x, y)) | x <- [True,False], y <- [True,False]]
Prelude> implytbl
[(True,(True,True)),(False,(True,False)),(True,(False,True)),(True,(False,False))]

この真理表には A -> B が True の場合も False の場合も含まれているので、A -> B の真理値が True のものだけを集めた真理表を作る。

Prelude> implytrue = filter fst implytbl
Prelude> implytrue
[(True,(True,True)),(True,(False,True)),(True,(False,False))]

A -> B の真理値が True のものだけを取り出したので、A と B の真理値の組み合わせのリストを取り出す。

Prelude> ab = [snd x | x <- implytrue]
Prelude> ab
[(True,True),(False,True),(False,False)]

この中から A が True のときの B の真理値(のリスト)を取り出すと次のようになる。

Prelude> [snd x | x <- ab, fst x]
[True]

確かに A -> B が True のとき A が True ならば B も True である。

このように、推論は単なる真理値の時とくらべ手続きが複雑になる。A, A -> B ならば B という modus ponens はこのような複雑な手続きを経て証明されたものだ。論理学がわかりにくいのは、推論の手続きが単純ではないにもかかわらず、その興味は推論に集中しているからだ。

ベン図とマッピング

領域 D = {a,b,c,d,e,f} の要素は述語 P(x) と組み合わせると P(a),P(b),..,P(f) という命題ができる。更にこの命題は必ず True か False の値を持つ。このときの命題の真理値を領域 D の要素に割り当てたものを、述語 P(x) のマッピングと呼ぶことにする。もちろんマッピングという正式の用語はなく、説明の利便のため使うだけだ。

ここで、領域 D の部分集合 {b,c,e} が真理集合となるような述語 P(x) を考える。Haskell で記述すると次のようになる。

Prelude> import Data.List
Prelude Data.List> domain = "abcdef"
Prelude Data.List> p x = elem x "bce"
Prelude Data.List> map_of_p = map p domain
Prelude Data.List> mpa_of_p
Prelude Data.List> map_of_p
[False,True,True,False,True,False]

map_of_p が述語 P(x) を領域 D のそれぞれの要素にそれを主語とし述語 P(x) を組み合わせてできる命題の真理値を割り当てたマッピングだ。このマッピングからは容易に P(x) の真理集合や、その補集合を取り出すことができる。

Prelude Data.List> [fst x | x <- zip domain map_of_p, snd x]
"bce"
Prelude Data.List> [fst x | x <- zip domain map_of_p, not $ snd x]
"adf"

これらの領域 D と真理集合とその補集合はそれぞれ、ベン図の全体集合、集合を表す円、全体集合の中の集合の円の外側の部分を表している。ベン図と異なるのは、全体集合の中に要素が散在していて円で囲うことのできない集合も表すことができるところである。したがって、上のマッピングは領域 D の全ての部分集合に対応させることができる。

さて、今度は {c,e,f} を真理集合とする述語 Q(x) を定義して、そのマッピングを作ってみる。

Prelude Data.List> q x = elem x "cef"
Prelude Data.List> map_of_q = map q domain
Prelude Data.List> map_of_q
[False,False,True,False,True,True]

このマッピングの True の部分だけを集めると述語 Q(x) の真理集合が得られるがいちいち内包表記で求めるのが面倒なので map_to_set という関数を定義する。

Prelude Data.List> map_to_set m = [fst x | x <- zip domain m, snd x]
Prelude Data.List> map_to_set map_of_q
"cef"

map_of_p と map_of_q の同じ位置の真理値は同じ主語に対応しているので、これらのマッピングは重ね合わせることができる。ただし、ただ重ね合わせることはできないので、それぞれの真理値を論理演算子で結合する。すると、論理演算子で結合した新しいマッピングが得られる。例えば ∧ 演算子で2つのマップを重ね合わせると次のようになる。

Prelude Data.List> map_of_and = zipWith (&&) map_of_p map_of_q
Prelude Data.List> map_of_and
[False,False,True,False,True,False]
Prelude Data.List> map_to_set map_of_and
"ce"

このマッピングから得られる真理集合は次のように {b,c,e} と {c,e,f} の共通部分になる。

Prelude Data.List> "bce" `intersect` "cef"
"ce"

つまり述語 P(x) と 述語 Q(x) を論理演算子で結合した複合述語 P(x) ∧ Q(x) の真理集合は、P(x) の真理集合と Q(x) の真理集合の共通部分であることが分かる。このように、ベン図を用いると論理演算と集合の関係をマッピングを介して明確に表すことができる。

論理演算子はあくまでも真理値の2項演算でしかないが、それをマッピング全体に適用することによって集合の関係に置き換えることができるのだ。

ところで、論理学では含意が重要になるので含意の演算子を定義する。

Prelude Data.List> imply x y = not x || y

これを利用すると P(x) -> Q(x) の真理集合を求めることができる。

Prelude Data.List> map_of_imply = zipWith imply map_of_p map_of_q
Prelude Data.List> map_to_set map_of_imply
"acdef"

この集合にどういう意味が有るのかはわかりづらいが、その補集合を考えてみる。

Prelude Data.List> map_to_set $ map not map_of_imply
"b"

'b' は次のように P(x) -> Q(x) の反例である。

Prelude Data.List> (p 'b') `imply` (q 'b')
False

そこで P(x) の真理集合の部分集合が真理集合であるような述語 R(x) を考えてみる。

Prelude Data.List> r x = elem x "bc"
Prelude Data.List> map_of_r = map r domain
Prelude Data.List> map_of_r
[False,True,True,False,False,False]

この R(x) を使って次のような複合述語 R(x) -> P(x) の真理集合を求めてみる。

Prelude Data.List> map_of_imply = zipWith imply map_of_r map_of_p
Prelude Data.List> map_of_imply
[True,True,True,True,True,True]
Prelude Data.List> map_to_set map_of_imply
"abcdef"

R(x) -> P(x) の真理集合は領域 D と一致してしまう。この場合、マッピングの全真理値の and をとると True になるから、

Prelude Data.List> and map_of_imply
True

これは ∀x R(x) -> P(x) という量化子のある命題が真であるということを意味している。

このようにベン図のマッピングを利用すると、集合と論理の関係や、量化子のある一階述語論理の命題をわかりやすく記述することができる。マッピングにはベン図のような図形として表現する集合の制限がないので、領域 D の全ての集合について記述できる。また、集合と論理の間の関係を明確にすることができる。領域 D のマッピングは項変数が1つだけの一階述語論理のモデルである。

ベン図と三段論法

人間は死ぬ。ソクラテスは人間である。故にソクラテスは死ぬ。という三段論法は命題論理では記述できない。これは1階述語論理で推論が行われる。領域に地球上の存在物、人間であるという述語を H(x)、死すべきものであるという述語を M(x) とすると、上の議論は次のように記号化できる。  

∀x H(x) -> M(x), H(s) ならば M(s)

これをベン図で記述するためにはどうすればいいだろうか。領域 D が有限離散集合の場合は、∀x H(x) -> M(x) は次の様に展開できる。

(H(a) -> M(a)) ∧ (H(b) -> M(b)) ∧ ... ∧ (M(an) -> H(an))

これらのうち、どれかの主語に対しても H(x) -> M(x) が False となる場合、上の論理式は False になってしまうので、領域 D の要素のうち任意の要素について H(x) -> M(x) の x に要素を代入して得られる命題の真理値はつねに True になる。したがって、s がソクラテスを表す要素である場合も、

H(s) -> M(s)

は True である。したがって、最初の推論から次の推論が演繹できる。

H(s) -> M(s), H(s) ならば M(s)

これは、1階述語論理ではなく、命題論理の論理式であるから modus ponens から M(s) が True であると推論できる。すなわち、人間は死ぬから、人間であるソクラテスは死ぬと結論付けられる。 Haskell でこの問題を扱ってみる。領域 D = {a,b,c,d,e,f} について P(x) = {b,c}、Q(x) = {b,c,d,e} とおくと、∀x P(x) -> Q(x) は True であるから、Q(c) は True になる。

Prelude Data.List> domain = "abcdef"
Prelude Data.List> p x = elem x "bc"
Prelude Data.List> q x = elem x "bcde"
Prelude Data.List> imply x y = not x || y
Prelude Data.List> p_imply_q x = (p x) `imply` (q x)
Prelude Data.List> map p_imply_q domain
[True,True,True,True,True,True]
Prelude Data.List> p 'b'
True
Prelude Data.List> q 'b'
True

三段論法の推論については、注意すべき点がいくつか有る。まず、論理演算子は真理値しか扱わないので、単純命題にしか適用できないということだ。∀x P(x) -> Q(x) のような全称命題は複数の命題を扱っているので、そのままでは、論理演算を伴う論理的な推論を構築することはできない。しかし、ベン図モデルでは、領域の全ての要素について述語 P(x) と組み合わせてできる命題を考えることができるから、全称命題の真理値を個々の命題すべての論理積と考えることができる。この性質を利用して ∀x P(x) -> Q(x) から複合命題 P(s) -> Q(s) を導き出すことができ、含意の論理演算による推論が可能になる。

このようにベン図モデルでは、述語論理から命題論理への関連が明確となる。この性質は、また、集合と述語の論理演算を整合的に論じることのできる基礎を提供している。

まとめ

これまで述べてきたように、論理と集合の関係、命題論理と1階述語論理との関係は、領域が有限集合のベン図モデルによって、明快に記述することができる。そのため、容易にベン図モデルの振る舞いを Haskell で調べることができる。

たとえば、領域 D が有限集合の場合、領域 D のすべての要素について述語 P(x) による命題を作ることができる。すなわち、P(a0), P(a1),..., P(an) である。このため領域 D における全称命題 ∀x P(x) は次のように単純命題を ∧ 記号で結合した命題論理の複合命題になる。

∀x P(x) = P(a0) ∧ P(a1) ∧ ... ∧ P(an)

従って、∀x P(x) の否定である ¬ ∀x P(x) は命題論理のド・モルガンの法則から次のように展開できる。

¬ ∀x P(x) = ¬P(a0) ⋁ ¬P(a1) ⋁ ... ⋁ ¬P(an)
= ∃x ¬P(x)

領域 D が有限集合のベン図ではこのように1階述語論理と命題論理との移行が単純にできる。

それだけではなく、領域 D では集合と論理の相互関係を定義できる。

領域 D では述語と要素からなる命題 P(a) は必ず真または偽の値をとる。このため集合の内包的定義 {x | P(x)} は必ず領域 D の部分集合を定める。これはまた、述語 P(x) の真理集合でもある。

また、述語 P(x) と Q(x) を論理記号でつないだ複合述語 P(x) ∧ Q(x) の真理集合は内包的定義 {x | P(x) ∧ Q(x)} で定義できるが、これは真理集合 P と Q の共通部分と等しい。述語の論理演算は、集合の集合演算に対応している。

このように領域 D が有限離散集合であれば、そこで論理と集合が矛盾なく記述できる。領域 D のベン図に論理と素朴集合を展開するときには何の矛盾も発生しない。

ベン図は論理学の初心者にとっては、論理と集合を学ぶための分かりやすく安心できるモデルとなる。ここにはラッセルのパラドックスは発生せず、集合とクラスの区別も発生しない。このモデルを拡張して領域 D が無限集合の場合に議論を広げれば、おそらく、ほとんどの数学的対象がベン図で記述できるのではないだろうか。

ただ、このモデルでは自己言及が取り扱えない。自己言及はラッセルのパラドックスを引き起こすし、自己言及する述語の振る舞いは奇怪なものになるが、ベン図では記述不可能なシステムの記述をすることができる。目的によっては自己言及する述語は決して悪者ではない。

とはいえ、本来の素朴集合の考え方はベン図の考え方ではないのだろうか。ベン図のモデルでは帰属関係モデルにくらべると表現の制限が見られるが、矛盾は起こさない。したがって、数学的対象を論理と集合で記述する目的のためにはベン図モデルのほうがふさわしい気がする。