2006-05-22

第12章ブール代数駆け足で読む『離散数学〜コンピュータサイエンスの基礎数学』

本駆け足シリーズの全体の目次はこちら

集合と命題は同じ性質を持つ。同じ法則を満たす。この法則を代数としたものがブール代数 boolean algebra という。
ブール代数は分配かつ相補的な束
ブール代数の基本性質
- 交換律 $a+b=b+a$ $a*b=b*a$
- 分配律 $a+(b*c)=(a+b)*(a+c)$ $a*(b+c)=(a*b)+(a*c)$
- 同一律(零元 0 と単位元 1 の存在) $a+0=a$ $a*1=a$
- 補元律(補元a') $a+a’=1$ $a*a’=0$
ブール代数のその他の性質(基本性質から導かれる)
- べき等律 $a+a=a$ $a*a=a$
- 有界律 $a+1=1$ $a*0=0$
- 吸収律 $a+(a*b)=a$ $a*(a+b)=a$
- 結合律 $(a+b)+c=a+(b+c)$ $(a*b)*c=a*(b*c)$
- 補元の一意性 $a+x=1$ かつ $a*x=0$ ならば、 $x=a’$
- 対合律 $(a’)’=a$
- 0'=1, 1=0;
- ド・モルガンの法則 $(a+b)’=a’*b’$ $(a*b)’=a’+b’$
ブール代数の演算子 $+,*,’$ はそれぞれ、和、積、補と呼ばれる。
部分代数
- ブール代数Bの部分集合Cがブール演算子 $+,*,’$ について閉じているとき、CはBの部分代数であるという。
- ２つのブール代数には同形関係が存在する。２つのブール代数に１対１対応が存在する場合である。
双対性
- ブール代数の命題の $+,*$ を交換し、0,1を交換したものを双対という。
ブール代数の用語
- リテラル literal とは、ブール代数の変数とその補変数のことである。
- 基本積 fundamental product とは、リテラルそのもの、または、複数のリテラルの積のことである。ただし、複数のリテラルというとき、同じリテラルはその補変数も含めて、１回だけしか含まない。
- 基本積の含む・含まれるの関係。ある基本積 $P_1$ の構成リテラルのすべてが、別の基本積 $P_2$ のリテラルになっているとき、 $P_1$ は $P_2$ に含まれるという。リテラル書式で含まれる基本積は含む基本積より小さいが、ベン図では、含まれる基本積が含む基本積を包含する。
- 積和形式 sum of products (加法標準形 disjunctive normal form, dnf) とは、ブール式を互いに他を含まない基本積を項とする和で表した形式のことである。このように表現できるのは、有限な長さを持つ束(すべての線形部分集合が有限である束)がirredundantな結び既約の結びと表すことができることに相当する(たぶん)
  - ブール式が積和形式で表され、すべての変数が含まれるとき、完全加法標準形(dull disjuctive normal form) という。すべての積和形式(加法標準形)のブール式は、完全加法標準形に変換できる。
- 主項 prime implicant と合意 consensus。
  - ２つの基本積 $P_1,P_2$ が、あるただ１つの変数について片方が変数をもう片方が補変数をもっているとき、その変数を除いた $P_1,P_2$ の積を合意という。合意Qについて $P_1+P_2=P_1+P_2+Q$ が成り立つ。
  - 合意に着目して、ブール式を変換する(consensus method)ことにより、ブール式は主項と呼ばれる項の和として表すことができる。ブール式Eの主項Pとは、 $P+E=E$ が成り立ち、Pに含まれる基本積(集合としては大きい基本積)Xでは $X+E ￥not = E$ であるよう項をいう。ブール式は主項のみの和として表すことができる。
- ブール式の最簡形 minimal
  - 複数の表し方をもつブール式であるが、ブール式で用いているリテラルの数と積和の数の２指標に着目する。２つのブール式について、片方のリテラル数と積和の数が、もう片方のそれ以下で、リテラル数か積和の数のすくなくとも片方がより小さいとき、前者のブール式は後者より簡単 simpler であるという。最簡形とは、より簡単な表現を持たないブール式のことである。
- 余分のない superfluous 主項の和として表したとき、それは最簡形となっている。ただし、余分のない、とは、除くことの出来ない、という意味である。
プログラミング問題
- 第11章までのソースより、推敲状態が甘いので、より注意すること。
- 積和形式(BoolSumOfProd クラス)の命題Eの完全加法標準形を出力する->FullDistinctNormal
- 全主項の和として表示->PrimesBool
- 最簡表示->MinimumBool



public class BoolSumOfProd {

	String[] var;

	String[] cvar;

	int[][][] elem;

	//int[][] comp;

	

	/*

	 * XY'Z + X'Z' is expressed as

	 * var ={"X","Y","Z"}

	 * cvar={"X'","Y'","Z'"}

	 * elem={{{0,0},{1,1},{2,0}},{{0,1},{2,1}}}

	 */

	public static void main(String[] args) {

		String[] var = {"x","y","z","t"};

		//String[] var = {"x","y","z"};

		//int[][][] elem= {{{0,0},{1,1}},{{0,0},{1,0},{2,1}},{{0,1},{1,0},{2,1}}};

		

		int[][][] elem={{{0,0},{1,0}},{{1,1},{3,0}},{{0,1},{1,0},{2,1}},{{0,0},{1,1},{2,0},{3,1}}};

		

		//int[][][] elem= {{{0,0},{1,0},{2,0}},{{0,1},{2,1}},{{0,0},{1,0},{2,1}},{{0,1},{1,1},{2,1}},{{0,1},{1,0},{2,1}}};

		//int[][][] elem= {{{0,0},{1,0},{2,0}},{{0,0},{1,0},{2,1}},{{0,0},{1,1},{2,0}},{{0,1},{1,0},{2,0}},{{0,1},{1,1},{2,0}}};

		//int[][][] elem = {{{0,0},{1,1}},{{0,0},{1,0},{2,0}},{{0,1},{1,1},{2,1}},{{0,1},{1,0},{2,0},{3,1}}};

		//int[][][] elem = {{{0,0},{1,0},{2,0}},{{0,1},{2,1}},{{0,0},{1,0},{2,1}},{{0,1},{1,1},{2,1}},{{0,1},{1,0},{2,1}}};

		//int[][][] elem= {{{0,0}},{{0,1},{1,0},{2,0}},{{0,0},{1,1},{2,1}}};

		//int[][] comp = {{0,1},{0,0,1},{1,0,1}};

		//BoolSumOfProd b = new BoolSumOfProd(var,elem,comp);

		BoolSumOfProd b = new BoolSumOfProd(var,elem);

		System.out.println("