代数系としての論理式

命題論理の論理式の集合は、論理演算について閉じているから、代数系だ。特に論理和 ∨ については、次の演算規則を満たすので可換モノイドである。

結合法則： (a ∨ b) ∨ c = a ∨ (b ∨ c)
単位元則： a ∨ ⊥ = ⊥ ∨ a = a
交換法則： a ∨ b = b ∨ a

さらに次の性質から、論理式の簡約が可能だ。

a ∨ a = a

この性質から、論理和については、原子命題の組み合わせを論理和で結合したものにすべての論理式は簡約できる。この場合簡約後の論理式は、

A1 ⋁ A2 ⋁ ... ⋁ An, A2 ⋁ A3 ⋁ ... ⋁ Am, ...

などの形をしたものに限られる。

要素命題と ⋁ 演算子のみからなる論理式の集合は、⋁ 演算について可換モノイドである。また、領域 D の冪集合は ∪ 演算子について可換モノイドであるので両者の間にはモノイド準同型写像を考えることができる。また、簡約された論理式の集合と冪集合の濃度は等しい。したがって論理式と冪集合の要素(真理集合)との同型写像が存在する。このとき ⋁ 演算子は ∪ 演算子に写される。

論理式の要素に ∨ 演算子以外に ¬ 演算子が加わるとそう簡単にはいかない。¬ (A ∨ B) を展開する方法がないからだ。また ¬ 演算子と ∨ 演算子だけでは分配法則が作れない。∧ 演算子を導入して、∨ 演算子と ∧ 演算子の分配法則、および ¬ (A ∨ B) = ¬ A ∧ ¬ B というド・モルガン法則を導入すれば ∨ 演算子と ∧ 演算子のみが出現する標準形にすることができるが、複雑になる。

⋁ 演算子のみの論理式では、簡約によって、出現する命題は要素命題 A1, A2, ..., An からなる複合命題に限られる。そこで ￢ A1 = A2 ⋁ A3 ⋁ ... ⋁ An と定義する。また、A1 ⋁ A2 ⋁ ... ⋁ An = T とし、T - A を T から命題 A に含まれる要素命題を取り除いたものとすると、任意の命題 A について A ∨ ￢ A = T、¬ (A ∨ B) = T - (A ∨ B) となる。このとき、

A ∧ B = ¬ ((T - A) ∨ (T - B))

と定義すると、

A ∧¬ A = ¬ ((T - A) ∨ A) = ¬ T = ⊥

これは、

A ∧ ¬ A = ⊥

であることを示している。すなわち、導入した ¬ 演算子は、

A ∨ ¬ A = T
A ∧ ¬ A = ⊥

という否定演算子の演算規則をみたす。したがって、要素命題が有限のとき、以上のようなやり方で ¬ 演算子を導入できる。このとき、論理演算は論理式の集合について閉じており、論理式の演算規則は真理表による演算規則と同じものになる。T = A1 ∨ A2 ∨ ... ∨ An は真理表上のトートロジーではないが、トートロジーと同じ扱いをする。

T = A1 ∨ A2 ∨ .... ∨ An をトートロジーと考えるというのは確かに腑に落ちないが、A -> A のような真理表上のトートロジーも、

A -> A = ¬ A ∨ A = A1 ∨ A2 ∨ ... ∨ An = T

となって、T と同値な命題であることを示すことができる。すなわち、上に述べたような ¬ 演算子の定義のもとで、T 以外のすべてのトートロジーは、T と同値な論理式になる。

命題論理は論理式の定義と論理演算の演算法則からなる構文論的な定義しかされていない。これに ¬ A = T - A を付け加えるのは、命題論理の解釈の問題だ。要素命題の集合が有限集合の場合、この解釈を付け加えても、すべての論理演算の演算規則は成立する。この解釈のもとでは、命題論理の論理式と領域 D の冪集合との間に同型写像が定義されるので、論理式の真理集合をその写像によって領域 D の冪集合の要素に対応させることができる。

また、T は真理表ではトートロジーではないが、命題論理の解釈として領域 D の冪集合をとるときはトートロジーである。

なぜなら、述語論理では述語 A(x) と個体 a の組み合わせが命題になる。すなわち、A(a) が真であるとは、個体 a が述語 A(x) を充足するときであり、そうでない場合は A(a) は偽となる。命題論理と領域 D の冪集合のモノイド準同型では、要素命題 A１の像はシングルトン集合 {a1} である。要素命題 A に対応する述語 A(x) は領域 D の要素 a1 だけが充足し、領域 D の他の要素は充足しない。

このとき T(x) = A1(x) ∨ A2(x) ∨ ... ∨ An(x) は領域 D のどの要素に対しても真となるので、偽となることはない、すなわちトートロジーなのだ。

論理式の真理集合を求める。

否定記号と選言記号のみで記述された命題論理の真理集合は簡単に計算できる。次のプログラムは、要素命題 A, B, ..., E と否定記号 ¬ と選言記号 ∨ で記述された論理式から真理集合を計算するプログラムだ。

-- file name: truthset.hs

import Data.List

data Prop = A | B | C | D | E | Not Prop | Or Prop Prop deriving Show

evalP A = ["a"]
evalP B = ["b"]
evalP C = ["c"]
evalP D = ["d"]
evalP E = ["e"]
evalP (Not x) = ["a","b","c","d","e"] \\ evalP x
evalP (Or x y) = evalP x `union` evalP y

a = Or A B
b = Not (Or (Not (Or A B)) (Not (Or A C)))
c = Or (Not (Or A B)) (Or A C)

データ型 Prop は要素命題 A, B, C, ..., E と ¬ および ∨ 記号から生成される論理式を表している。さらに、この論理式を評価してその論理式に対応する領域 D = {a, b, c, d, e} の部分集合（真理集合）を求める関数 evalP を記述している。

論理式 A の真理集合は {a} のシングルトン集合だ。領域 D の個体に命題 A を適用したとき A(a) は真で、他の個体に適用した A(x) は偽となる。¬ A は A の真理集合の領域 D における補集合に対応する。また、任意の論理式 P について ¬ P の真理集合は P の真理集合の補集合である。また、A ∨ B の真理集合は A の真理集合と B の真理集合の和集合である。

命題論理の論理式からその真理集合を計算するプログラムはこれだけだ。

最後に例題として３つの論理式を定義している。すなわち、

a = A ∨ B
b = (A ∨ B) ∧ (A ∨ C)
c = (A ∨ B) -> (A ∨ C)

である。これを ghci で取り込んで a, b, c のそれぞれの論理式を evalP で評価してみる。

Prelude> :l truthset.hs
[1 of 1] Compiling Main ( truthset.hs, interpreted )
Ok, one module loaded.
*Main> evalP a
["a","b"]
*Main> evalP b
["a"]
*Main> evalP c
["c","d","e","a"]

a = A ∨ B の真理集合は {a, b} だ A ∨ B は領域 D の要素 a と b に適用されたときだけ真になる。

b = (A ∨ B) ∧ (A ∨ C) の真理集合は、A ∨ B の真理集合 {a, b} と A ∨ C の真理集合 {a, c} の共通部分の {a} だ。a のときだけ両者の論理式が真となるからだ。

c = (A ∨ B) -> (A ∨ C) の真理集合は {c, d, e, a} だこの評価は難しいが次の真理表を見れば正しいことがわかる。

* | A ∨ B | A ∨ C | (A ∨ B) -> (A ∨ C) |
a | T | T | T
b | T | F | F
c | F | T | T
d | F | F | T
e | F | F | T

このように、命題論理の論理式から、真理集合は機械的に求めることができるのが分かる。

このことは命題論理という言語が解釈によって領域 D の冪集合を記述する言語になるということだ。これは論理の普遍性を表していると同時に、論理を冪集合の性質として捉えることができることも示している。ある理論を領域 D の冪集合としてモデル化できる場合、その理論は論理と同時に、集合でも表現できるということだ。

領域 D とラッセルのパラドックス

論理式と領域 D の冪集合の間には、モノイド準同型が存在する。これは論理的な推論が、冪集合の集合演算として捉えることができることを示している。

たとえば、領域 D が整数のとき、述語 x^2 = 1 の真理集合は、{1, -1} である。また、述語 x > 0 の真理集合は {1, 2, 3, ... } である。したがってこれらの述語の論理結合である x ^ 2 = 1 ∧ x > 0 の真理集合は、両者の真理集合の共通部分の {1} である。このように、論理式の論理演算は、真理集合の集合演算として解釈することができる。

これは、領域 D の冪集合は、領域 D のすべての部分集合を含み、論理演算に対応する集合演算で閉じているからだ。論理式で記述されたことは、すべて真理集合の集合演算に反映させることができる。これは、論理式はすべて、物の集まりとしての集合に反映させることができることを示している。この場合、物の集まりとしての集合にはなんの矛盾も発生しない。

しかし、集合を物の集まりとして定義すると、ラッセルのパラドックスを生じる。上の議論では、物の集まりとしての集合になんら問題はなさそうなのだが、ラッセルのパラドックスぱどうして発生するのだろうか。

ここで領域 D として集合の集合をとる。領域 D の部分集合は、物の集まりだからこれも領域 D の要素のはずだ。その場合、その部分集合には、その部分集合と対応する要素がふくまれる場合と、その部分集合の外にその部分集合を表す D の要素がある場合に分かれる。前者が、自分自身を要素として含む集合であり、後者は自分自身を要素として含まない集合だ。領域 D の中には確かに、これらの２種類の要素が存在する。

しかし、この代表例で切り取った推論では論理の全体像がみえてこない。領域 D の冪集合 P(D) を考えると、これは領域 D のすべての部分集合の集合になる。したがって、領域 D の要素との全単射が存在するはずだ。だが、領域 D の濃度はその冪集合 P(D) の濃度より小さい。領域 D から冪集合 P(D) への全射はない。領域 D の要素では、そのすべての部分集合を表すには、要素の数が足りないのだ。

このように、領域 D の要素でその部分集合を表そうとしても、表せる部分集合と、表せない部分集合がある。領域 D の要素で表せる領域 D の部分集合は集合と呼ばれ、領域 D の要素で表せない領域 D の部分集合はクラスになる。なにが集合で、なにがクラスであるかは恣意的なものである。しかし、どうしても領域 D の要素で表せない部分集合がある。それが、「自分自身を要素として含まない集合の集合」である。

前述のように領域 D の要素は自分自身を要素として含む集合と、自分自身を要素として含まない集合がある。この場合、自分自身を要素として含まない集合（D の要素）を集めるとこれは D の部分集合である。しかし、この部分集合 R に対応する領域 D の要素はない。なぜなら、そのような要素を a とすると、a が R に含まれてしまうと a は自分自身を要素として含む集合であり、a が R に含まれていないと、それは自分自身を要素として含まないにも関わらず R の要素ではないからだ。

このような場合でも R に対する要素は、領域 D の外に求めることができる。すなわち領域 D の冪集合 P(D) の中に求めることができる。これは領域 D の濃度と冪集合 P(D) の濃度の差を考えると当たり前のことだ。

領域 D の部分集合すべてを領域 D の要素に対応させることは不可能だ。しかし、ラッセルのパラドックスはこの不可能が可能であると仮定することによって物の集まりという集合の定義に矛盾が存在するかのように見せかけているのだ。不可能を可能だと仮定したら矛盾するのは当たり前だ。

集合をものの集まりと定義することに矛盾は存在しない。矛盾は領域 D と冪集合 P(D) の間に全単射があると仮定することによって発生するのだ。