2002年 4月14日 作成 反射性・対称性・移行性 >> 目次 (テーマごと)
2007年 6月16日 補遺  


 
 さて、今回は、「反射性・対称性・移行性」 の量化を扱ってみましょう。

 まず、「真理集合」 という考えかたを理解してください。
 以下を例にして 「真理集合」 を説明します。

 (1) 従業員の集合 A = {x1, x2, x3
 (2) 部門  の集合 B = {y1, y2

 そして、命題関数 [ 関係の論理 ] として、R (x, y) を考えてみます。
 R (x, y) を 「x は y に配属されている」 という関係とします。

 
 さて、集合 A と集合 B の直積集合 (A × B) は、以下の組から構成されます。
   A × B = { (x1, y1), (x2, y1), (x3, y1), (x1, y2), (x2, y2), (x3, y2) }

 直積 (A × B) のなかで、「真」 ならしめる順序対の集合を以下とします。
   α = { (x1, y2), (x2, y2) }.

 この集合 α のことを R (x, y) の 「真理集合 (true set)」 あるいは 「解 (solution)」 といいます。

 
 2つの集合 (Ω1と Ω2) と、その直積 (Ω1 × Ω2) を例にします。
 (1) Ω1の任意の エレメント を x とする。
 (2) Ω2の任意の エレメント を y とする。
 (3) 直積の任意の エレメント は (x, y) となる。

 直積の任意の エレメント (x, y) について、以下の 2つの 「関係」 を考えてみます。
 (1) R (x, y)
 (2) S (x, y)

 R (x, y) と S (x, y) のそれぞれの真理集合を α と β とすれば、「関係の論理法則」 として以下が成立します。
 (ただし、α の補集合は αcとする。)
 (1) α ∩ β ≡ ∀x ∀y [ R (x, y) ∧ S (x, y) ].
 (2) α ∪ β ≡ ∀x ∀y [ R (x, y) ∨ S (x, y) ].
 (3) αc ≡ ∀x ∀y [ ¬R (x, y)].
 (4) αc ∪ β ≡ ∀x ∀y [ ¬R (x, y) ∨ S (x, y) ] ≡ ∀x ∀y [ R (x, y) ⇒ S (x, y) ].
   (¬p ∨ q ≡ p ⇒ q を思い出してください。)

 もう、以上の記号列を読むことができるでしょう (記号列を観ても、拒否反応は起こらないでしょう)。
 集合と述語論理と グラフ は、以上に記述したように 「相互乗り入れ (翻訳)」することができます。
 2つの関係 (関係 R と関係 S) のうち少なくとも 1つが成立することを記述しているのが (2) ですし、2つの関係の間に共通集合を生成することを記述しているのが (1) です。なお、(3) のなかで (補集合として扱った) 「関係の否定」 は以下のように (「'」 を使って) 記述することもあります。
  ¬R (x, y) ≡ R' (x, y).

 さて、関係の論理を扱うときに、以下の関係を覚えておけばよいでしょう。
 (1) 汎関係と零関係
 (2) 逆関係
 (3) 連鎖
 (4) 遺伝的
 (5) 反射性・対称性・移行性

 汎関係・零関係・逆関係・連鎖・遺伝的は、次回、解説します。
 反射性・対称性・移行性は、以下のように記述されます。
 (1) 反射性 ∀x R (x, x).
 (2) 対称性 ∀x ∀y [ R (x, y) ⇒ R (y, x) ].
 (3) 移行性 ∀x ∀y ∀z { [ R (x, y) ∧ R (y, z) ] ⇒ R (x, z) }.

 反射性は R (x, x) ですから、2項 (x, y) として考えれば、x = y のことです。
 対称性は (x, y) = (y, x) のことです。対称性を述語論理的に言えば、「x は y の兄弟であれば、y は x の兄弟である」 ということです。
 移行性は三段論法の推論の典型例でしょう。

 さて、反射性・対称性・移行性の論理否定を作ってみましょう
 (1) 非反射性 ∀x ¬R (x, x).
 (2) 非対称性 ∀x ∀y [ R (x, y) ⇒ ¬R (y, x) ].
 (3) 非移行性 ∀x ∀y ∀z { [ R (x, y) ∧ R (y, z) ] ⇒ ¬R (x, z) }.

 ここで注意しなければならない点は、「¬」 記号の位置です。
 非対称性と 「対称性の論理的否定」 はちがう、という点に注意してください。
「対称性の論理的否定」 は、(対称性の全体に対して ¬ 記号を附与した) ¬{ ∀x ∀y [ R (x, y) ⇒ R (y, x) ] } ですから、非対称性とはちがう、という点に注意してください。つまり、(前回まで習得してきた 「全称の存在化」 を思い出せば) 「対称性の論理的否定」 は、以下のようになるでしょう。

  ¬{ ∀x ∀y [ R (x, y) ⇒ R (y, x) ] } ≡ ∃x ∃y ¬[ ¬R (x, y) ∨ R (y, x) ] ≡ ∃x ∃y [ R (x, y) ∧ ¬R (y, x) ].

 さて、「順序対」 は、どのような関係として記述できるでしょうか。「順序対」 というのは、以下の 2つの関係を両立している関係です--具体的に (1, 2) という順序対を想像して考えてみてください。
 (1) 非対称性
 (2) 移行性

 ちなみに、直積集合を使って データ 構造を扱おうとした セット・アット・ア・タイム (RDB が実現している データ 演算) は、移行性を厳密には導入できなかったので、( RDB の生みの親である)コッド 博士 (Codd E.F.) は、-- R (x, y) のなかの R は Relation ですが-- R を Relation (関数、あるいは関係の論理) として厳密に扱わないで、Relationship と言ってよい、としました。

 ところが、「Relation ≒ Relationship」 という扱いが、後々、世間では、大混乱を起こす原因になったのです。というのは、「RDB の テーブル 構造を ER図 (Entity-Relationship 図) を使って表現すれば、visibility を実現した図式になる」 というふうな間違いが起こってしまったのです。そのために、ER図として、「従業員の データ 集合のなかに部門 コード を挿入する」 という間違いが罷り通るようになってしまいました-- ER という概念では、従業員の entity のなかに部門 コード を挿入してはいけない [ ただし、R (x, y) を関数として扱うなら、「従業員の データ 集合のなかに部門 コード を挿入する」 ことは正当ですが、ただ、べつの大きな問題点が起こります--これについては、後日、説明します。]

 次回は、汎関係・零関係・逆関係・連鎖・遺伝的を説明します。 □

 



[ 補遺 ] (2007年 6月16日)

 この エッセー で確認したかった点は、以下の 2点です。

 (1) Relation (関係) と Relationship (関連)
 (2) 関係の対称性・非対称性

 「関係の論理 (aRb)」 は、シュレーダー や ド・モルガン や パース が研究してきて、現代では、述語論理のなかに組み入れられています。「aRb」 は 「a は、b に対して、関係 R にある」 と読み、数学では、R (a, b) として考えて、関数 f (x, y) と同値です。つまり、「関係」 は、関数として考えるということです。言い換えれば、個体 a も個体 b も変項として、関係 R を一次的とみなす関係主義の考えかたです。いっぽう、「関連」 は、個体を一次的として、関係は二次的とする実体主義の考えかたで、どちらかといえば、日常言語の用語です。そして、ふだんの生活のなかでは、まず、個体を 「認知 (直知)」 するほうが自然でしょうね。しかし、いざ、個体を定義しようとすれば、なかなか、難しい。たとえば、「時計」 を例にすれば、「時計」 を ひとつの個体として認知するのか、それとも、「時計」 は最終組立物であって、文字盤や針などを個体として認知するのか、さらに、文字盤や針などは加工品であって、(それらの材料たる) 鉄・真鍮を個体として考えるのかは、文脈次第でしょうね。言い換えれば、「物は高次の構成物」 であって、定義できないので、「無定義語 (変項)」 として扱い、それらの変項を一義に定立できる関数があるとするのが数学的な考えかたです。

 関係を関数として扱えば、変項のあいだで、「並び」 が問われます。言い換えれば、変項を並べるために関数を使いますが、関係には、「並び」 が問われない事態--すなわち、対称性--も起こります。たとえば、2項関係 R (a, b) として、以下の 2つの関係を考えてみて下さい。

 (1) 父親である
 (2) 恋人である

 (1) では、もし、「父親である (a, b) -- a は、b に対して、父親である」 を 「真」 とすれば、R (b, a) -- b は、a に対して、父親である--は 「偽」 となります。たとえば、「佐藤正美は佐藤敦の父親である」 が 「真」 であれば、「佐藤敦は佐藤正美の父親である」 は 「偽」 です。この関係の性質が非対称性 [ R (a, b) ≠ R (b, a) ] です。
 いっぽう、(2) では、「恋人である (a, b)-- a は、b に対して、恋人である」 を 「真」 とすれば、R (b, a) -- b は、a に対して、恋人である」 も 「真」 となります。たとえば、「佐藤正美は山崎恵美子の恋人である」 が 「真」 であれば、「山崎恵美子は佐藤正美の恋人である」 も 「真」 です。この関係の性質が対称性 [ R (a, b) = R (b, a) ] です。




  << もどる ベーシックス すすむ >>
  数学基礎論