計算理論の基礎(関数と関係)

[計算理論]計算理論の導入3(関数と関係について)

計算理論を学ぶ為に関数と関係についてまとめる。

語句

・関数(function)：入力と出力の関係を決める。
・写像(mapping)：関数と同意。f(a) = bは「fはaをbに写す」と言う。
・定義域(domain)：入力となりえるものの集合
・値域(range)；出力を含む集合
・上への(onto)関数：値域のすべての要素が関数の出力である関数
・mの法をとる：mで割った余りを考える
・引数(argument)：関数への入力組
・k項関数(k-ary function)：k個の引数をもつ関数
・項数：引数の個数
・単項関数(unary function)：引数が一つの関数
・二項関数(binary function)：引数が二つの関数
・前置記法(prefix notation)：二つの引数の前に関数シンボルがある記法
Example: add(a,b)
・中置記法(infix notation)：二つの引数の間に関数シンボルがある記法
Example: a+b
・述語(predicate),特性(property)：値域が{TRUE, FALSE}である関数
・関係(relation)：k個組の集合、A × A ... ×Aが定義域である特性
・二項関係(binary relation)：二項の関係
Example: a < b, a > b, a = b... 「aRb = TRUE」と記載する場合がある
・同値関係(equivalence relation)：二つのものの間のある種の等しさを議論する概念
　１. Rは反射律(reflexive)をみたす。すなわち、すべてのxについて、xRx。
　２. Rは対称律(symmetric)をみたす。すなわち、すべてのxとyについて、xRyならばyRx。
　３. Rは推移律(transitive)をみたす。すなわち、すべてのx, y, zについて、xRyかつyRzならばxRz。