14.2 分配格、有补格与布尔代数
本章目录 · 1 节
本章导读
【14.2 分配格、有补格与布尔代数】依次区分“满足分配律”“存在全局上下界”“每个元素有补元”,三者不能彼此替代。
【定义14.2.1 分配格】格中任意a,b,c均满足两条分配律时称分配格:
在格公理下,只要第一条对所有元素成立,就能推出第二条,反向也成立。例如用第一条展开(a∨b)∧(a∨c):先得到a∨((a∨b)∧c),再展开括号并吸收a∧c,得a∨(b∧c)。注意这是全称恒等式的相互推出,并非只检查某一个三元组。
【例14.2.1】以下L₁为三元链,L₂为四元菱形,均分配;L₃为钻石格M₃,L₄为五角格N₅,均不分配。
M₃中b∧(c∨d)=b,而(b∧c)∨(b∧d)=a。N₅中c∨(b∧d)=c,而(c∨b)∧(c∨d)=d,且c≠d。四元菱形是两个二元链的积,并不是五元钻石格;不要只根据“像菱形”判断是否分配。(例完)
【定理14.2.1】格分配,当且仅当不含与M₃或N₅同构的子格。这里必须是保留原格交、并运算的子格,只找五个点的轮廓不够。必要性可由分配律对封闭子集的继承及上述反例看出;充分性是格论的结构定理,此处与原书一样给出结论供判别使用。
【推论14.2.1】少于五个元素的格都是分配格;每条非空链在min、max下也为分配格,有限和无限链均可。
【例14.2.2】下列三图均不分配。
L₁的最大元为f,e之上还有f;取出a,b,c,d,e时,其中的交、并没有改变,所以仍为子格。L₃中b虽位于a< b<d<f的长链上,去掉d后,a,b,c,e,f仍对原交、并封闭。(例完)
【定义14.2.2—14.2.3 有界格】若存在0≤x≤1对所有x∈L成立,称L有界,记(L,∧,∨,0,1)。0、1分别为全下界、全上界,由反对称性唯一。它们是抽象名称,不必等于整数0、1。允许单元素退化格,此时0=1;若要求非退化,须另加0≠1。
非空有限格必有界:全体元素的有限交为0,有限并为1。无限格未必有界,例如(Z,min,max);无限幂集格P(S)却有界,0=∅,1=S。
在有界格中a∧0=0、a∨0=a、a∧1=a、a∨1=1。对偶时除交并、序方向之外还要同时交换0和1。
【定义14.2.4 补元】在有界格中,若a∧b=0且a∨b=1,就称a、b互为补元。两个等式缺一不可。0、1总互补,其他元素可能无补元、一个补元或多个补元。
【例14.2.3】图14.2.1中:(1)L₁仅a、c互补,b无补元。(2)L₂中a与d、b与c互补。(3)M₃中a与e互补,b的补元为c、d,c的为b、d,d的为b、c。(4)N₅中a与e互补,b的补元为c、d,c、d的补元都仅b。补元不唯一的例子说明一般有补格中不能直接指定一个具有全部布尔性质的“取反”运算。(例完)
【定理14.2.2】有界分配格中,一个元素若有补元,则补元唯一。若b、c均补a,则
同理c=b∧c,故b=c。使用了分配律,不能把结论无条件用于M₃、N₅。
【定义14.2.5 有补格】有界且每个元素都有至少一个补元,称有补格。图14.2.1中L₂、M₃、N₅均有补,L₁没有;图14.2.2中L₂、L₃有补,而L₁中b,c,d,e没有补元,因为与任何元素的并都无法在交为a的同时达到f。
【定义14.2.6 布尔代数】有补分配格称布尔格或布尔代数,记(B,∧,∨,′,0,1)。由分配性,补元唯一,故a↦a′才定义为确定的一元运算。有补不推出分配,分配也不推出有补。
【例14.2.4】(1)110=2·5·11,S₁₁₀={1,2,5,10,11,22,55,110}在gcd、lcm下构成布尔代数。每个d的补元为110/d,因为110无重复素因子,gcd(d,110/d)=1、lcm(d,110/d)=110。若n含重复素因子,照此公式一般不成立,例如S₄中的2无补元。
(2)任意集合S的幂集在∩、∪、相对于S的补集下构成布尔代数,0=∅、1=S;补集必须有固定全集。
(3)命题公式按逻辑等值取等价类,以合取、析取、否定为运算,形成命题布尔代数;未取等价类的不同字符串不是直接相等的元素。(4)数字电路中的二值逻辑代数为最基本的二元布尔代数;多输入的布尔函数也可逐点组成布尔代数。(例完)
【定理14.2.3】布尔代数满足双重否定和德摩根律:
第一式因a为a′的补元且补元唯一。第二式可检查(a∧b)∧(a′∨b′)=0,以及(a∧b)∨(a′∨b′)=1,故a′∨b′正是a∧b的唯一补元;另一式对偶可得。有限多个元素的版本用归纳法,不必把“有限”未经说明扩大到任意无限交并。
【定义14.2.7 等价公理描述】非空系统(B,*,○)的两运算若各自交换,互相分配,存在1、0使a*1=a、a○0=a,而且每个a有a′使a*a′=0、a○a′=1,则它是布尔代数,其中*为∧,○为∨。这套公理中的1是*的单位元,0是○的单位元。
先从这些公理推出a○1=1、a*0=0。例如a○1=(a○1)*1=(a○1)*(a○a′)=a○(1*a′)=a○a′=1。再由(a○a)*(a○a′)=a○(a*a′)=a得a○a=a,*的幂等律对偶;吸收可由a○(a*b)=(a*1)○(a*b)=a*(1○b)=a得到。结合律同样是这套公理的推论,最终恢复前面的有补分配格定义;不能在未说明时把交换性本身当成结合性。
【定义14.2.8 原子】有全下界0的格中,a≠0且没有0<b<a时,称a为原子,即a覆盖0。原书定义写0∈L时须同时理解为全下界,不是任意指定一个名叫0的元素。
正因子格Sₙ中的原子恰为n的不同素因子;P(S)中的原子为单元素子集。单元素布尔代数无原子,不应将0算作原子。
【定理14.2.4 有限布尔代数表示定理】有限布尔代数B,设A为其原子集合,则B同构于P(A)。具体同构为Φ(x)={p∈A:p≤x}。
证明要点:每个非零x下方都能在有限集合中选到极小非零元,故有原子。不同原子交为0。令u为x下方所有原子的并;若u<x,则x∧u′非零,又有原子p≤x∧u′,与u已包括全部p≤x矛盾。因此x由其下方原子唯一表示为并。分配律保证Φ(x∧y)=Φ(x)∩Φ(y)、Φ(x∨y)=Φ(x)∪Φ(y),补元对应相对补集;任取A的子集,其原子之并给出逆映射,含空并0。这也说明为什么这里需要有限性。
【推论14.2.2—14.2.3】若有n个原子,则|B|=2ⁿ,n≥0;任意等势的有限布尔代数同构。反向只有基数为2ⁿ并不足以断定任意一个给定格是布尔代数,仍须检验运算公理。
