読者です 読者をやめる 読者になる 読者になる

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

計算理論

[計算理論]計算理論の導入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):二つのものの間のある種の等しさを議論する概念
 1. Rは反射律(reflexive)をみたす。すなわち、すべてのxについて、xRx。
 2. Rは対称律(symmetric)をみたす。すなわち、すべてのxとyについて、xRyならばyRx。
 3. Rは推移律(transitive)をみたす。すなわち、すべてのx, y, zについて、xRyかつyRzならばxRz。