抽象によるソフトウェア設計第3章論理系その6

今日は関係演算子の説明からです。

-> 矢印積 (直積)
- p -> q で p のタプルと q のタプルの全ての組み合わせを結合した関係を作る
- p, q のアリティが 2以上なら結果は多項関係になる
. ドット結合
- p . q で p, q は一般に少なくともどちらか一方は二項関係か多項関係。
- p が集合(アリティ1)で q が二項関係なら p の各要素について q の関係を関数として適用した結果( q のタプルの2つめのアトムをもつタプル)の集合
- p, q が二項関係なら関数合成みたいな感じ
[] ボックス結合
- ドット結合と意味は同じ。引数の順番と優先順位が違う
- p . q は q [p] と同じ
~ 転置
- タプルの順序を反転させた集合を返す。逆向きの関係を作る
- 二項関係が a -> b と b -> a のような逆向きのタプルを常に持つ時、対称的と言う。対称的な集合は転置で変化しない
- 対象閉包とは r を含む最小の対称的関係 : r + ~r
^ 推移閉包
- 二項関係が a -> b と b -> c を持つとき常に a -> c も持つなら、その関係を推移的と呼ぶ : r.r in r
- 二項関係 r を含む最小の推移的関係を ^r と書く : ^r = r + r.r + r.r.r + ...
* 反射推移閉包
- 二項関係 r が全てのアトム a について a -> a を含むとき、反射的であると呼ぶ : iden : r
- 二項関係 r を含む最小の反射的かつ推移的な関係を反射推移閉包と呼ぶ
- 反射推移閉包を *r と書ける : *r = ^r + iden
- iden は r が元々含んでいるアトム以外のものも含めてしまうけど、処理系の都合でこのほうがいいよって感じらしい。実用上はたいてい結合する時などに消えるので問題ない。または定義域の制限で明示的に除く

あとは値域の制限、定義域の制限が残っていますが今日はここまで。ひとつひとつ説明を読めばそんなに難しくないので安心しました。