- 1、本文档共54页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第8章 格与布尔代数 8.1 格 8.2 布尔代数 定理8.1.13设?X,∨,∧,0,1?为有界分配格,如果对于a?X,a存在补元b,则b是a的惟一补元。 证明:因为b是a的补元,所以有 a∨b=1,a∧b=0 设c?X,c是a的另一个补元,同样也有a∨c=1,a∧c=0 从而有 a∨b= a∨c,a∧b= a∧c 由于?X,∨,∧,0,1?为分配格,根据定理8.1.10必有b=c,即a的补元惟一。 定义8.1.12设?X,∨,∧,0,1?为有界格,如果?a?X,在X中都有a的补元存在,则称?X,∨,∧,0,1?为有补格 例如,图8.8是三个有界格的哈斯图,由于每一个元素至少有一个补元,所以它们都是有补格。 返回章目录 8.2布尔代数 定义8.2.1 有补分配格称为布尔格。 在布尔格中每一个元素都有补元。因为有补格一定是有界格,所以布尔格一定是有界分配格,根据定理8.1.13,布尔格中的每一个元素的补元存在且惟一。于是可以将求补元的运算看作一元运算且把a的补元记为a′。 定义8.2.2 设?X,??是布尔格,?X,∨,∧,′?是格?X,??导出的代数系统。称代数系统?X,∨,∧, ′?为布尔代数。 在8.1节中证明了 ?P (A), R??是格,其中 A=?a,b?。 ?P (A),∪,∩?是?P (A), R??导出的代数系统,其中∪和∩是集合并运算和交运算。以后又进一步说明了?P (A),∪, ∩?是分配格和有界格,?是全下界、A是全上界。从而?P(A),∪,∩?是有界分配格。令A为全集,?T?P (A),T的补集~T=A–T?P (A),满足T∪~T= A和T∩~T=?,所以T的补元T′=~T。根据定义8.2.2,?P (A),∪,∩, ~?是布尔代数。 可以证明,当A为任意集合时,?P (A),∪,∩, ~?也是布尔代数。称为集合代数。集合代数是布尔代数的一个具体模型。 布尔代数一定是格。根据定理8.1.1,布尔代数中的两个二元运算满足交换律、结合律、幂等律和吸收律。此外,布尔代数还有下面的性质: 定理8.2.1 设?X,∨,∧, ′?为布尔代数,?a,b?X,必有 ⑴ (a′)′=a ⑵ (a∨b)′= a′∧b′ ⑶ (a∧b)′= a′∨b′ 证明:⑴ a′是a的补元,a也是a′的补元,由布尔代数中补元的惟一性有(a′)′=a ⑵(a∨b)∨(a′∧b′)=((a∨b)∨a′)∧((a∨b)∨b′) =(b∨(a∨a′))∧(a∨(b∨b′)) =(b∨1)∧(a∨1)=1∧1=1 (a∨b)∧(a′∧b′)=(a∧(a′∧b′))∨(b∧(a′∧b′)) =((a∧a′)∧b′)∨((b∧b′)∧a′) =(0∧b′)∨(0∧a′)=0∨0=0 所以 (a∨b)′= a′∧b′ ⑶ 同理可证 (a∧b)′= a′∨b′ 定理8.2.1中的⑴称为双重否定律,⑵和⑶称为德摩根律。布尔代数满足双重否定律和德摩根律。 定理8.2.2 设?X,*,°,′?是代数系统,其中*和°都是二元运算,′是一元运算。?X,*,°,′?是布尔代数的充分必要条件是:⑴*和°在X上封闭且满足交换律。 ⑵*和°满足分配律(满足*对°的分配律和°对*的分配律)。 ⑶X中存在运算*的幺元和运算°的幺元。设运算*的幺元为0,运算°的幺元为1。即?a?X,有a*0=a,a°1=a ⑷ ?a?X,?a′?X,使得a*a′=1,a°a′=0 由于篇幅的限制,证明从略。 定理8.2.2给出的四个条件可以作为布尔代数的等价定义。 布尔代数?X,*,°,′?也可以表示成为?X,*,°,′,0,1?,其中0是运算*的幺元,1是运算°的幺元。 【例8.9】设P是所有命题构成的集合,∨,∧和?分别是命题的析取、合取和否定联结词。证明代数系统?P,∨,∧, ??
文档评论(0)