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

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

　（1） 従業員の集合　A ＝ ｛x₁, x₂, x₃ ｝
　（2） 部門　 の集合　B ＝ ｛y₁, y₂｝

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

　
　さて、集合 A と集合 B の直積集合 （A × B） は、以下の組から構成されます。
　　　A × B ＝ ｛ (x₁, y₁), (x₂, y₁), (x₃, y₁), (x₁, y₂), (x₂, y₂), (x₃, y₂) ｝

　直積 （A × B） のなかで、「真」 ならしめる順序対の集合を以下とします。
　　　α ＝ ｛ (x₁, y₂), (x₂, y₂) ｝.

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

　
　2つの集合 （Ω₁と Ω₂） と、その直積 （Ω₁ × Ω₂） を例にします。
　（1） Ω₁の任意の エレメント を x とする。
　（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) を関数として扱うなら、「従業員の データ 集合のなかに部門 コード を挿入する」 ことは正当ですが、ただ、べつの大きな問題点が起こります--これについては、後日、説明します。]

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