順序同型じゅんじょどうけいorder isomorphismとブール代数だいすうBoolean algebra 基本きほん演習えんしゅう

1対応たいおうする講義こうぎlecture

2問題もんだい1：順序保存写像じゅんじょほぞんしゃぞうorder-preserving mapを確認かくにんする

$$P=\{1,2,3\}$$P=\{1,2,3\}、$$Q=\{2,4,6\}$$Q=\{2,4,6\} を通常つうじょうの大小だいしょうで順序じゅんじょづける。$$f:P\to Q$$f:P\to Q を $$f\left(x\right)=2x$$f(x)=2x とする。$$f$$f は順序保存写像じゅんじょほぞんしゃぞうorder-preserving mapか。

2.1解答かいとう

$$x\text{[PARSE ERROR: Undefined("Command("le")")]}y$$x\le y なら $$2x\text{[PARSE ERROR: Undefined("Command("le")")]}2y$$2x\le 2y である。したがって $$f\left(x\right)\text{[PARSE ERROR: Undefined("Command("le")")]}f\left(y\right)$$f(x)\le f(y) であり、$$f$$f は順序保存写像じゅんじょほぞんしゃぞうorder-preserving mapである。

2.2解説かいせつ

順序保存写像じゅんじょほぞんしゃぞうorder-preserving mapでは、大小だいしょうの向むきが保たもたれるかを見みる。値あたいの差さが保存ほぞんされる必要ひつようはない。

順序保存写像じゅんじょほぞんしゃぞうorder-preserving mapでは、差さや比ひが保存ほぞんされるかではなく、$$x\text{[PARSE ERROR: Undefined("Command("le")")]}y$$x\le y から $$f\left(x\right)\text{[PARSE ERROR: Undefined("Command("le")")]}f\left(y\right)$$f(x)\le f(y) が必かならず従したがうかを確認かくにんする。

3問題もんだい2：鎖くさりchainと反鎖はんくさりantichainを判定はんていする

$$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}P\left(\right\{1,2,3\left\}\right)$$\mathcal P(\{1,2,3\}) を包含ほうがんinclusionで順序じゅんじょづける。次つぎの集合族しゅうごうぞくは鎖くさりchainか、反鎖はんくさりantichainか。

3.1解答かいとう

最初さいしょの集合族しゅうごうぞくでは

なので鎖くさりchainである。

二ふたつ目めの集合族しゅうごうぞくでは、異ことなる 1 元げん集合しゅうごうどうしは互たがいに包含ほうがんしない。したがって反鎖はんくさりantichainである。

3.2解説かいせつ

包含順序ほうがんじゅんじょinclusion orderでは、要素数ようそすうの大小だいしょうだけでなく、実際じっさいに含ふくまれている元げんelementを比較ひかくする必要ひつようがある。

鎖くさりchainかどうかは任意にんいの 2 元げんが比較ひかくできるかで判定はんていし、反鎖はんくさりantichainかどうかは異ことなる 2 元げんが比較不能ひかくふのうかで判定はんていする。要素数ようそすうだけではなく、実際じっさいの包含ほうがんを見みる。

4問題もんだい3：ド・モルガンの法則De Morgan's lawsを使つかう

全体集合ぜんたいしゅうごうを $$U=\{1,2,3,4,5\}$$U=\{1,2,3,4,5\}、$$A=\{1,2,3\}$$A=\{1,2,3\}、$$B=\{3,4\}$$B=\{3,4\} とする。$$U\setminus (A\cap B)$$U\setminus(A\cap B) と $$(U\setminus A)\cup (U\setminus B)$$(U\setminus A)\cup(U\setminus B) を求もとめ、一致いっちを確認かくにんせよ。

4.1解答かいとう

$$A\cap B=\left\{3\right\}$$A\cap B=\{3\} なので、

である。また

なので、

である。両者りょうしゃは一致いっちする。

4.2解説かいせつ

ド・モルガンの法則De Morgan's lawsは、補集合ほしゅうごうcomplementが共通部分きょうつうぶぶんintersectionを和集合わしゅうごうunionへ変かえることを表あらわす。全体集合ぜんたいしゅうごう $$U$$U を固定こていしないと補集合ほしゅうごうcomplementは定さだまらない。

5証明しょうめい演習えんしゅう：補元ほげんcomplementの一意性いちいせいuniqueness

5.1問題もんだい

ブール代数だいすうBoolean algebraで、ある元げん $$x$$x の補元ほげんcomplementが一意いちいであることを証明しょうめいせよ。

5.2解答かいとう

$$y,z$$y,z がどちらも $$x$$x の補元ほげんcomplementだとする。すると $$x\wedge y=0$$x\wedge y=0、$$x\vee y=1$$x\vee y=1、$$x\wedge z=0$$x\wedge z=0、$$x\vee z=1$$x\vee z=1 である。

同おなじ議論ぎろんで $$z\text{[PARSE ERROR: Undefined("Command("le")")]}y$$z\le y である。よって反対称性はんたいしょうせいantisymmetryより $$y=z$$y=z である。

5.3解説かいせつ

補元ほげんcomplementの一意性いちいせいuniquenessは、ド・モルガンの法則De Morgan's lawsを証明しょうめいするときの土台どだいになる。