第３章 関数 駆け足で読む『離散数学〜コンピュータサイエンスの基礎数学』
本駆け足シリーズの全体の目次はこちら
- 関数 function
写像 mapping・変換 transform、とも。集合Aと集合Bとがあって、Aの各要素にBの唯一の要素を割り当てるときに、その割り当て全体を、AからBへの関数と呼ぶ。集合Aは定義域 domain, Bは値域 codomainと呼ばれる。この関数fをと書き、fはAをBへ移すと読む。また、
で
であるとき、bはfのもとでのaの像 image またはaに対するfの値 valueと呼ばれ、aのfはb a of f equals b, と読む
Aの要素をそれ自身に割り当てる関数は恒等関数 identity function と呼ばれる
１対１の関数 ならば
のような関数f
AからBの上への関数 function onto B. fの像が値域全体であるときfを上への関数と呼ぶ
可逆 invertivle の逆の関係
が関数であるとき、fは可逆であると言う。fが可逆であるのは、１対１ "one to one" かつ上への関数であるときである。
１対１対応の関数 one to one correspondence は、Aの各要素がBの唯一の要素に対応し、またその逆にBの各要素がAの各要素に対応しているような関係のことである。
１対１関数を単車 ingective,上への関数を全射 surjective, １対１対応を全単射 bijective とも呼ぶ
- 添数関数と添数付き集合族 indexing set, collection with indix
関数fがある集合の要素とある集合族S(ある集合の部分集合の集合)の要素(部分集合)とを関係付けるものとする。fが１対１で上への関数ならば、SはIを添数集合とする集合族と呼ばれる。集合族に対して、１対１対応の添数 index をつける(ID付け)ことができた、ということ
計算機での取り扱いは、原則として、添数つきで行うので、それへの導入の意味もある
- 基数 cardinary
集合で言えば要素数のこと。n以下の正の整数の集合の基数と１対１対応の関係にある集合の基数はnとなる。このようなnが存在するときにこの集合は有限 finite であるという。正の整数全体は無限 infinite 集合であるが、可算無限 denumerable, coutably infinite であるとして、非可算集合と区別する。加算無限な正の整数の集合の基数は、可算であるので、値が定められており、それをアレフゼロ"\bf{\aleph_0}"と書く
- プログラミング問題
- fが関数であるか否かを決定するプログラム->IsFunction
- fは関係であって、そのうち、Aの要素に対して、唯一のBの要素が対応している場合であるから、その判断を下す
- Im(f) (値域)、
を書き出すプログラム->第２章のStringRange, CompositRelationを参照
- これらは、関係でもあるfについて、関係としての値域、合成関数の作成と同じであるので第２章で作成したものが用いられる
- fが１対１であるか否かの判定をするプログラム->Is1to1
- fが関数であって、fが可逆であるから、fの逆関係を作成し、それが関数か否かを判定する->Inverse, IsFunction
- fが関数であるか否かを決定するプログラム->IsFunction
public class Function {public static void main(String[] args) {
int[][] sample1 = {{1,3},{4,3},{2,4},{6,3},{3,6},{5,6}};
int[][] sample2 = {{1,3},{2,4},{6,3},{4,4},{2,2},{5,3}};
int[][] sample3 = {{1,4},{4,3},{2,3},{6,5},{3,4},{5,6}};
int[][] sample4 = {{1,5},{2,3},{6,4},{4,1},{3,2},{5,1}};
int f1 = IsFunction(sample1);
int f2 = IsFunction(sample2);
System.out.println("sample1 isFunction? " + f1);
System.out.println("sample2 isFunction? " + f2);
String sep = "\t";
PrintImageF(sample3,sep);
PrintImageF(sample4,sep);
System.out.println("Im(f3)" +Relation.StringRange(sample3,sep));
System.out.println("Im(f4)" +Relation.StringRange(sample4,sep));
int[][] sample3sq = Relation.CompositRelation(sample3,sample3);
System.out.println("s3^2");
Relation.PrintR(sample3sq,"\t","\n");
int[][] sample4sq = Relation.CompositRelation(sample4,sample4);
System.out.println("s4^2");
Relation.PrintR(sample4sq,"\t","\n");
int s3Is1to1 = Is1to1(sample3);
System.out.println("sample3 is 1to1 "+ s3Is1to1);
int s4Is1to1 = Is1to1(sample4);
System.out.println("sample4 is 1to1 "+ s4Is1to1);
}
/*
* Return 1 if relation f is a function, otherwise return -1
*
*/
public static int IsFunction(int[][] r){
int ret=1;
for(int i=0;i<r.length;i++){
for(int j=0;j<r.length;j++){
if(r[i][0]==r[j][0]){
if(r[i][1]!=r[j][1]){
ret = -1;
return ret;
}
}
}
}
return ret;
}
public static int Is1to1(int[][] r){
int ret=1;
int rIsF = IsFunction(r);
if(rIsF==-1){
ret =-1;
return ret;
}else{
int[][] inv = Inverse(r);
int invIsF = IsFunction(inv);
if(invIsF==-1){
ret=-1;
}
return ret;
}
}
/*
* Print out f(a)
*
*/
public static void PrintImageF(int[][] f,String sep){
String ret = StringImageF(f,sep);
System.out.println(ret);
}
public static String StringImageF(int[][] f, String sep){
String ret = "";
int[] im = ImageF(f);
for(int i=0;i<im.length;i++){
ret+=im[i] + sep;
}
return ret;
}
public static int[] ImageF(int[][] f){
int[] tmpret = new int[f.length];
int counter = 0;
for(int i=0;i<tmpret.length;i++){
boolean flag = true;
for(int j=0;j<counter;j++){
if(f[i][1]==tmpret[j]){
flag = false;
break;
}
}
if(flag){
tmpret[counter]=f[i][1];
counter++;
}
}
int[] ret = new int[counter];
for(int i=0;i<counter;i++){
ret[i]=tmpret[i];
}
return ret;
}
/*
* Return Inverse
*
*/
public static int[][] Inverse(int[][] r){
int[][] ret = new int[r.length][2];
for(int i=0;i<r.length;i++){
ret[i][0]=r[i][1];
ret[i][1]=r[i][0];
}
return ret;
}
}
第３章終了
