関係と論理
・$n$項関係と$n$項論理について学びます。
・関係データベースの基本について学びます。
・写像と関係の関連を学びます。
・同値関係や順序関係について学びます。
・演算を保存する同値関係について学びます。
１．関係：要素の組の集合
集合$A_1,A_2,\dots,A_n$の直積
$A_1\times A_2\times\cdots\times A_n:=\{(x_1,x_2,\cdots,x_n)|x_1\in A_1,x_2\in A_2,\cdots,x_n\in A_n\}$
$A_1,A_2,\dots,A_n$上のn項関係 $R$$\subseteq A_1\times A_2\times\cdots\times A_n$
外延的表記：$R=\{(a_1,a_2,\dots,a_n),(b_1,b_2,\dots,b_n),\dots,(c_1,c_2,\dots,c_n)\}$
内包的表記：$R=\{(x_1,x_2,\cdots,x_n)|P_R(x_1,x_2,\cdots,x_n)\}$（$n$変数述語）
| 番号 | 名前 | 住所 |
| 1 | 相川 | 小平市 |
| 5 | 田中 | 国立市 |
| 9 | 松田 | 小平市 |
$=\{$(1,相川,小平市),(5,田中,国立市),(9,松田,小平市)$\}$
$=\{(x_1,x_2,\cdots,x_n)|$学生の番号$x_1$と名前$x_2$と住所$x_3\}$
$\subseteq$番号$\times$名前$\times$住所
例．$\lt=\{(x,y)|x\lt y\}=\{(1,2),(1,3),(2,3),(1,4),\dots\}\subseteq$自然数$\times$自然数
２．関係の演算：射影と選択
$R\subseteq A_1\times A_2\times\cdots\times A_n$とする。１．射影：$\pi(R;A_{i_1},A_{i_2},\dots,A_{i_k}):=\{(x_{i_1},x_{i_2},\dots,x_{i_k})|(x_1,x_2,\dots,x_n)\in R\}$
必要な項目だけ表示する
２．選択：$\sigma(R;P(A_1,A_2,\dots,A_n)):=R\cap\{(x_1,x_2,\dots,x_n)|P(x_1,x_2,\dots,x_n)\}$
条件Pを満たす組を取り出す
| 番号 | 名前 | 住所 |
| 1 | 相川 | 小平市 |
| 5 | 田中 | 国立市 |
| 9 | 松田 | 小平市 |
① $π$(学生;番号,名前)$=\{$(1,相川),(5,田中),(9,松田)$\}$
② $σ$(学生;住所="小平市")$=\{$(1,相川,小平市),(9,松田,小平市)$\}$
| 番号 | 名前 |
| 1 | 相川 |
| 5 | 田中 |
| 9 | 松田 |
| 番号 | 名前 | 住所 |
| 1 | 相川 | 小平市 |
| 9 | 松田 | 小平市 |
３．関係の演算：直積と結合
$R\subseteq A_1\times A_2\times\cdots\times A_n,\ S\subseteq B_1\times B_2\times\cdots\times B_m$とする。３．直積：$R\times S:=\{(x_1,\dots,x_n,y_1,\dots,y_m)|(x_1,\dots,x_n)\in R,\ (y_1,\dots,y_m)\in S\}$
４．結合：直積から$A_i=B_j$の組を取りだし項目$B_j$を消す
$\theta(R,S;A_i,B_j):=\pi(\sigma(R\times S,A_i=B_j);A_1,\dots,A_n,B_1\dots,B_{j-1},B_{j+1},\dots,B_m)$
| 番号 | 名前 | 住所 |
| 1 | 相川 | 小平市 |
| 5 | 田中 | 国立市 |
| 番号 | 科目 | 点数 |
| 1 | 数学 | 80 |
| 5 | 数学 | 50 |
| 5 | 英語 | 70 |
| 学生.番号 | 名前 | 住所 | 成績.番号 | 科目 | 点数 |
| 1 | 相川 | 小平市 | 1 | 数学 | 80 |
| 1 | 相川 | 小平市 | 5 | 数学 | 50 |
| 1 | 相川 | 小平市 | 5 | 英語 | 70 |
| 5 | 田中 | 国立市 | 1 | 数学 | 80 |
| 5 | 田中 | 国立市 | 5 | 数学 | 50 |
| 5 | 田中 | 国立市 | 5 | 英語 | 70 |
| 学生.番号 | 名前 | 住所 | 科目 | 点数 |
| 1 | 相川 | 小平市 | 数学 | 80 |
| 5 | 田中 | 国立市 | 数学 | 50 |
| 5 | 田中 | 国立市 | 英語 | 70 |
直積は、組のすべての組合せ
結合は、直積で生じる無駄な組を省く
４．SQL：関係データベースの問合せ言語
コッドにより考案された関係モデルに基づく問合せ言語
基本形（$R_1\times R_2\times\cdots\times R_j\subseteq A_1\times A_2\times\cdots\times A_n$とする）
|
SELECT $A_{i_1},A_{i_2},\dots,A_{i_k}$ FROM $R_1,R_2,\dots,R_j$ WHERE $P(A_1,A_2,\dots,A_n)$ |
関係$R_1,R_2,\dots,R_j$の直積から 条件$P(A_1,A_2,\dots,A_n)$を満たす組を取り出し、 項目$A_{i_1},A_{i_2},\dots,A_{i_k}$を表示する |
５．「愛する」関係から「三角関係」を導く
三角関係：異なる二人が同じ人を愛する関係| $人_1$ | $人_2$ |
| 太郎 | 花子 |
| 花子 | 太郎 |
| 和夫 | 花子 |
| 良子 | 和夫 |
| $人_1$ | $人_2$ | $人_3$ | $人_4$ |
| 太郎 | 花子 | 太郎 | 花子 |
| 太郎 | 花子 | 和夫 | 花子 |
| 花子 | 太郎 | 花子 | 太郎 |
| 和夫 | 花子 | 太郎 | 花子 |
| 和夫 | 花子 | 和夫 | 花子 |
| 良子 | 和夫 | 良子 | 和夫 |
| $人_1$ | $人_2$ | $人_3$ | $人_4$ |
| 太郎 | 花子 | 和夫 | 花子 |
| 和夫 | 花子 | 太郎 | 花子 |
| $人_1$ | $人_2$ | $人_3$ |
| 太郎 | 花子 | 和夫 |
| 和夫 | 花子 | 太郎 |
SELECT $人_1,人_2,人_3$
FROM 愛,愛
WHERE $人_2=人_4\wedge 人_1\ne 人_3$
データベースのパズル
| 番号 | 名前 | 住所 |
| 1 | 相川 | 小平市 |
| 5 | 田中 | 国立市 |
| 9 | 山崎 | 小平市 |
| 番号 | 科目 | 点数 |
| 1 | 数学 | 80 |
| 5 | 数学 | 50 |
| 5 | 英語 | 70 |
| 9 | 英語 | 50 |
パズル
① 二つの表(関係)を結合するSQLとその結果の表(関係)を示せ。
② 小平市の学生の名前を求めるSQLとその結果の表を示せ。
③ 小平市の学生の名前と科目と点数を求めるSQLのその結果の表を示せ。
６．二項関係
$R\subseteq A\times B,\ S\subseteq B\times C$に対し$R^{-1}$$:=\{(y,x)|(x,y)\in R\}\subseteq B\times A$ 逆関係
$R\cdot S$$:=\{(x,z)|(x,y)\in R,(y,z)\in S\}\subseteq A\times C$ 関係の合成
$R\subseteq A\times B,\ x\in A,\ X\subseteq A$に対し
$R(x)$$:=\{y|(x,y)\in R\}$, $R(X)$$:=\{y|\exists x\in X\ \ (x,y)\in R\}$ 像
写像(関数)：$|f(x)|=1$（像が必ず1つある関係）$f:A\to B$と書く
写像が単射：$x=y \iff f(x)=f(y)$ 異なる要素の像は異なる
写像が全射：$f(A)=B$ 値域$B=$像$f(A)$
$f:A\to B$が全単射なら、逆関数$f^{-1}:B\to A$が定まり
$A$と$B$の要素の間に1対1対応ができる
７．関係から導かれる写像
関係$R\subseteq A\times B$は$R(x)=\{y|(x,y)\in R\}$を考えると 写像$R：A\to 2^B$と見なせ、
$R(X):=\{y|\exists x\in X\ \ (x,y)\in R\}$を考えると 写像$R：2^A\to 2^B$と見なせる
パズル：すべての写像$f：2^A\to 2^B$が関係からこのように導かれるわけではない。
$f：2^A\to 2^B$が、ある関係$\subseteq A\times B$から導かれたものであるための条件を求めよ。
８．順序関係と同値関係
関係$R\subseteq A\times A$に対し、次の操作を考える$R^{-1}$$:=\{(y,x)|(x,y)\in R\}$（逆関係）
$R^2$$:=R･R=\{(x,z)|(x,y)∈R,(y,z)\in R\}$（合成）
$R^3:=R\cdot R\cdot R,\ R^4:=R\cdot R\cdot R\cdot R, \dots$
$R^0$$:=\{(x,x)|x\in A\}$ 恒等関係
$R^+$$:=R^1\cup R^2\cup R^3\cup\cdots$ 推移的閉包
$R^*$$:=R^0\cup R^+$ 反射的推移的閉包
$R$が同値関係$\iff R=R^*=R^{-1}$ 反射的∧推移的∧対称的
同値関係はある意味で「同じ」とみなせる関係。
例．三角形の合同、相似
$R$が順序関係$\iff R=R^*\wedge R\cap R^{-1}=R^0$ 反射的∧推移的∧反対称的
順序関係はある意味で以下、以上などとみなせる関係。
例．≦、≧、辞書式順序。
９．同値関係による分割
同値関係$\subseteq A\times A$は、$A$の要素の間で「同じ」であることを意味する関係なので、元の集合$A$を同じもの同士に分割し、次が成立つ。$(x,y)\in R\iff R(x)=R(y)$
$x$と$y$が「同じ」なら$x$と同じものの集合と$y$と同じものの集合は等しい。
$(x,y)\not\in R\iff R(x)\wedge R(y)=\emptyset$
$x$と$y$が「同じ」でなければ$x$と$y$の両方と同じものはない。
この分割を$R$による$A$の商集合 $A/R=\{R(x)|x\in A\}$ という。
パズル．分割の例をあげよ。
１０．演算を保存する同値関係
同値関係$R\subseteq A\times A$が$A$上の演算(写像)$f:A\times A\to A$を保存するというのは$(x_1,y_1),(x_2,y_2)\in R \implies (f(x_1,x_2),f(y_1,y_2))\in R$
が成立つことを言う。（同じものの演算結果は同じということ）
$R$が演算$f$を保存するとき、商集合$A/R$上にも自然に演算
$f(R(x),R(y))=R(f(x,y))$
が導入できる。
１１．nを法とする演算
例．非負整数の集合$\mathbb{N}=\{0,1,2,\dots\}$上に同値関係$R_n=\{(x,y)|xとyはnで割った余りが等しい\}$
を考える。この同値関係は加算と乗算を保存する。
| ＋ | 0 | 1 | 2 | 3 | 4 | 5 |
| 0 | 0 | 1 | 2 | 3 | 4 | 5 |
| 1 | 1 | 2 | 3 | 4 | 5 | 0 |
| 2 | 2 | 3 | 4 | 5 | 0 | 1 |
| 3 | 3 | 4 | 5 | 0 | 1 | 2 |
| 4 | 4 | 5 | 0 | 1 | 2 | 3 |
| 5 | 5 | 0 | 1 | 2 | 3 | 4 |
| × | 0 | 1 | 2 | 3 | 4 | 5 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| 2 | 0 | 2 | 4 | 0 | 2 | 4 |
| 3 | 0 | 3 | 0 | 3 | 0 | 3 |
| 4 | 0 | 4 | 2 | 0 | 4 | 2 |
| 5 | 0 | 5 | 4 | 3 | 2 | 1 |
| × | 0 | 1 | 2 | 3 | 4 |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 |
| 2 | 0 | 2 | 4 | 1 | 3 |
| 3 | 0 | 3 | 1 | 4 | 2 |
| 4 | 0 | 4 | 3 | 2 | 1 |
注．表では$R_n(k)$を単に$k$で表す。
例えば $R_6(2)\times R_6(5)=R_6(4)$
パズル：上の演算表から、逆演算(減算や除算)が定義できるか、判定せよ。