习题14

数学学习 · 爱知数学讲义

18
本章目录 · 1 节

本章导读

【习题14】共19组。格图向上为较大元素;补元按该格自己的全下界、全上界计算,不能将任意两个不可比元素都称为互补。

【14.1】原题六张哈斯图如下,交叉但未标点的位置不是元素。

abcd
题14.1(a) 四元链
abcdef
题14.1(b) 不是格
abcdef
题14.1(c) 六元格
abcdefg
题14.1(d) 不是格
abcdef
题14.1(e) 不是格
abcdef
题14.1(f) 六元格

(a)是格,交、并为较小、较大元素。(b)不是,b、c没有共同下界,且d、e都是它们的极小上界而无最小者。(c)是格,两条链a<b<e<f与a<c<d<f的内部元素,跨链交为a、并为f,同链取min、max。(d)不是,b、c的上界有d、e、f、g,但无最小上界。(e)不是,a、b无共同下界。(f)是格;除同链外,b∧c=a、b∨c=d,b∧e=a、b∨e=f,d∧e=c、d∨e=f。不能因(c)的两条线相交,就把交点当作新节点而改变答案。

【14.2】按整除偏序。(1){1,2,3,4,5}不是格,2、3没有共同上界。(2){1,2,3,6,12}是格,各对的gcd、lcm都在底集;注意4不在集合,但也不是2、3的确界。(3){1,2,3,4,6,9,12,18,36}是36的全体正因子格,交为gcd、并为lcm。(4){1,2,2²,…}是一条无限链,任意两个2的幂的交、并为较小、较大者,所以是格,虽无全上界。

【14.3】(1)Z₁₆加法群全部子群组成链:⟨0⟩⊂⟨8⟩⊂⟨4⟩⊂⟨2⟩⊂Z₁₆,阶分别1、2、4、8、16。

<0><8><4><2>Z16
题14.3(1) Z₁₆的子群格

(2)S₃的全部子群为{id}、⟨(12)⟩、⟨(13)⟩、⟨(23)⟩、A₃={id,(123),(132)}和S₃。四个非平凡真子群互不包含,两两交均{id}、并运算均生成整个S₃;图中<12>简记⟨(12)⟩,其余类同。

{id}<12><13><23>A3S3
题14.3(2) S₃的完整子群格

【14.4】同时交换∧、∨及≤、≥,不取逻辑否定。(1)a∨(a∧b)≥a。(2)a∧(b∨c)≥(a∧b)∨(a∧c)。(3)b∧(c∨a)≥(b∧c)∨a。第三个原式本身并非所有格的定理,例如二元布尔代数中b=1、a=c=0时原式1≤0为假;本题仅要求写出对偶式,不是要证明三个原式都成立。

【14.5】设n≥1,m=a₁∧…∧aₙ=a₁∨…∨aₙ。每个i都满足m≤aᵢ≤m,反对称性得全部aᵢ=m。不能仅凭各自幂等就推出结论。

【14.6】a≤b≤c,则a∨b=b且b∧c=b,故两者相等。链条件允许等号,a=b或b=c均成立。

【14.7】图14.2.1的L₂底集{a,b,c,d},a为底、d为顶,b、c不可比。非空子格共12个:四个单元集;五个可比二元集{a,b}、{a,c}、{a,d}、{b,d}、{c,d};两个三元链{a,b,d}、{a,c,d};以及整个{a,b,c,d}。{b,c}必须补入其交a与并d,因此不是子格;三元集{a,b,c}与{b,c,d}也不封闭。

【14.8】主理想S={x∈L:x≤a}含a,故非空。若x,y≤a,则x∨y≤a;又x∧y≤x≤a,所以对原格两运算封闭,是子格。这里是≤a,若误写成<a,在某些格中并可能等于a而不封闭。

【14.9】只讨论14.1中确为格的(a)(c)(f)。(a)底a、顶d,仅a与d互补,b、c无补元。(c)底a、顶f:a↔f;b的补元c、d;e的补元c、d;c的补元b、e;d的补元b、e。即两条长链的内部元素跨链互补,同链不互补。(f)底a、顶f:a↔f、b↔e,c和d无补元。补元关系对称,但不一定唯一。

【14.10】(a)是分配格,非有补格、非布尔格,因为链有两个内部元素无补元。(c)有补但不分配,因此非布尔格:e∧(b∨c)=e,而(e∧b)∨(e∧c)=b,且b≠e。(f)同构于三元链×二元链,故分配;c、d无补元,所以非有补格、非布尔格。(b)(d)(e)本身不是格,不适用后面三种格的分类。

【14.11】有界格中0≤a≤1。由确界定义或14.1.3立即得a∧0=0、a∨0=a、a∧1=a、a∨1=1。0、1是各自格的界,不必是数值0、1。

【14.12】必须按指定运算的个数及含义分类,不能为凑分类擅自添加运算。

(1)S₁={1,1/2,2,1/3,3,1/4,4}不对普通乘法封闭,例如4·4=16不在其中,故不是该运算下的代数系统,更不是半群、群。

(2)n≥2的左投影aᵢ*aⱼ=aᵢ封闭、结合,故是半群;无双侧单位元,非独异点、群。

(3){0,1}普通乘法为交换独异点,单位元1,0不可逆,非群。题设只有这一种运算,未定义环或格;可另行扩充运算形成其他系统,但不是当前给定的签名。

(4){1,2,3,6}在gcd与lcm下是布尔代数,抽象0为整数1、抽象1为整数6,补元1↔6、2↔3;所以同时是格。每个单独运算都构成交换独异点,但都不是群。不能将gcd充当环的加法,因为它幂等且无法形成非平凡加法群。

(5){0,1}模2加法、模2乘法为二元域F₂,因此是环和整环;加法为二阶阿贝尔群,乘法为独异点,但含0的乘法系统不是群。这两个原运算不是布尔格的交、并:模2加法1+1=0不满足并的幂等律。它是布尔环;若另定义x∨y=x+y+xy、x∧y=xy、x′=1+x,才得到对应的二元布尔代数。

【14.13】p=(a∧b)∨(a∧b∧c)∨(b∧c)。由吸收律,中间项被a∧b吸收,故p=(a∧b)∨(b∧c)=b∧(a∨c)。对偶式为p*=(a∨b)∧(a∨b∨c)∧(b∨c),化简得p*=b∨(a∧c)。对偶不对元素加撇,也不是取补表达式。

【14.14】(1)a≤b⇒a∧b′≤b∧b′=0,所以(2)a∧b′=0。由德摩根及0′=1,(2)等价于(3)a′∨b=1。反向若(2)成立,则a=a∧(b∨b′)=(a∧b)∨(a∧b′)=a∧b,故a≤b。这里的第二式含b′,漏掉撇号会改变整个命题。

【14.15】同构意义下,1、2、3、4、5元格的数量分别1、1、1、2、5。

1元:唯一的0=1格,分配、有补、布尔。2元:唯一的二元链,分配、有补、布尔。3元:唯一三元链,分配,非有补、非布尔,见图14.2.1 L₁。

4元:四元链与四元菱形。前者分配,非有补、非布尔;后者分配、有补、布尔,见图14.2.1 L₂。

0ab1
题14.15 四元链

5元恰为五元链、四元菱形下再加一个最小元、四元菱形上再加一个最大元、M₃、N₅。前三者分配但不有补,不是布尔格;M₃、N₅有补但不分配,也非布尔格。后两者见图14.2.1 L₃、L₄。

0abc1
题14.15 五元链
0uab1
题14.15 在四元菱形下增添最小元
0abu1
题14.15 在四元菱形上增添最大元

完整性可按有限格的最小、最大元分类:4元时只有两个内部点,二者可比或不可比;5元时三个内部点的可比类型恰为三元链、二元链加孤立点、一个点在另两者之下、一个点在另两者之上、三点反链,分别得到上述五种。

【14.16】定义x⊕y=(x∧y′)∨(x′∧y),即布尔异或,封闭、交换,单位元0,x⊕x=0,每个元素都是自身的逆。结合律可将三元式展开成“恰有一个为真或三个都为真”的四个交项,左右括号相同;故(B,⊕)是阿贝尔群,也是独异点、半群。若再配原来的∧作乘法,会得到布尔环,但原题只指定⊕时不将未给的第二运算强加进去。

【14.17】a≤c则a∧c=a。由分配律,(a∨b)∧c=(a∧c)∨(b∧c)=a∨(b∧c),即模律。证明实际上对任意分配格成立,不必额外用补元;删去a≤c则一般不成立。

【14.18】n≥1,对n归纳。(1)二元德摩根为起点;将前n项的并看作一个元素,再与第n+1项用二元式,并代入归纳假设,即得(a₁∨…∨aₙ)′=a₁′∧…∧aₙ′。(2)同理或由对偶得(a₁∧…∧aₙ)′=a₁′∨…∨aₙ′。若采用空并0、空交1约定,n=0也成立,因为0′=1、1′=0。

【14.19】若f:B₁→B₂、g:B₂→B₃为布尔代数同构,则通常函数记法下g∘f是B₁到B₃的双射,并逐一保持交、并、补、0、1,所以B₁≅B₃;若使用全书先左后右的复合符号,则写f○g,含义仍是先f后g。保持运算可直接验算(g(f(x∧y)))=g(f(x)∧f(y))=g(f(x))∧g(f(y)),其余类同。