第１章 集合論 駆け足で読む『離散数学〜コンピュータサイエンスの基礎数学』
本駆け足シリーズの全体の目次はこちら
- 集合 set、要素 element、外延 extention、抽象 abstraction、空集合 empty set、AはBに含まれる(A is contaitned by B)(
)、BはAを含む(B contains A)(
)、真部分集合 proper subset (
)
- 集合演算 和 union、共通部分 intersection、互いに素 disjoint nonintersecting、BのAに対する補集合 B's relative complement to A はAとBとの差 difference (
、固定された普遍集合に対しては、絶対補集合 absolute complement
- 集合代数、べき等律 Idempotent Law、結合律 Associative Law、交換律 Commutative Law、分配律 Distibutive Law、同一律 Identity Law、対合律 Involution Law、補元率 Complement Law、ド・モルガンの法則 DeMorgan's Law
- 集合の類、べき集合、集合の集合は類 class、または集合族 collection、与えられた集合の類のいくつかの集合を部分類 subclass、または部分集合族 subcollectionという、与えられた集合Aのすべての部分集合からなる類はAのべき集合 power set
、べき集合の要素の数は
、Aのべき集合は
と表すこともある
- 帰納法 induction(Pを正の整数の集合
で定義された命題であるとし、
- プログラミング問題
- ２つの集合A、Bについて、
,
,
を書き出すプログラムの作成->Blong
- 数値の集合Aについて、ある数値XがAの要素であるかを判定するプログラムの作成
- 上記プログラムを呼び出すプログラムで、数値集合Aが数値集合Bの部分集合であるか否かを判定するプログラムの作成->Subset
- さらにAとBとが等しいか否かを判定するプログラムの作成(AがBの部分集合であり、かつ、BがAの部分集合であることを確認する)->Equal
- ２つの集合A、Bについて、
public class Set {public static void main(String[] args) {
int[] a ={2,3,4,5};
int[] b ={2,3,4};
int subset = Subset(a,b);
int equal = Equal(a,b);
System.out.println("a is subset of b? " + subset);
System.out.println("a is b ? " + equal);
}
/*
* If x in a, return 1. If not return -1
*/
public static int Blong(int x,int[] a){
int ret = -1;
for(int i=0;i<a.length;i++){
if(x==a[i]){
ret = 1;
break;
}
}
return ret;
}
/*
* if a is subset of b, return 1. If not return -1.
*/
public static int Subset(int[] a, int[] b){
int ret = 1;
int cnt=0;
if(a.length>b.length){
ret = -1;
return ret;
}
for(int i=0;i<a.length;i++){
int eleminb = Blong(a[i],b);
if(eleminb==-1){
ret = -1;
break;
}
}
return ret;
}
/*
* if a equals b, return 1. If not, return -1.
*/
public static int Equal(int[] a,int[] b){
int ret =-1;
if(a.length != b.length){
return ret;
}
int ainb = Subset(a,b);
int bina = Subset(b,a);
if(ainb+bina==2){
ret=1;
}
return ret;
}
}
- 第１章終了
