《十二章节格与布尔代数》由会员分享，可在线阅读，更多相关《十二章节格与布尔代数（42页珍藏版）》请在金锄头文库上搜索。
1、第十二章 格与布尔代数格与布尔代数12.1 格定义的代数系统格定义的代数系统12.2 格的代数定义格的代数定义 12.3 一些特殊的格一些特殊的格12.4 有限布尔代数的唯一性有限布尔代数的唯一性12.5 布尔函数和布尔表达式布尔函数和布尔表达式悄灰转啤冒革脱锭三挨碘醚骂罪彰潜硒邀掺公湖痒澄留草炽铭留雨帛瘁铂十二章节格与布尔代数十二章节格与布尔代数复习：偏序集、格复习：偏序集、格格是一个偏序集，在这个偏序集中，每两个元素有唯格是一个偏序集，在这个偏序集中，每两个元素有唯一一个最小上界和唯一一个最大下界。一一个最小上界和唯一一个最大下界。定义（见第定义（见第85页定义页定义1） 设设A是一个非空
2、集合，是一个非空集合， R是是A上的一个二元关系，若上的一个二元关系，若R有自反性、有自反性、反反对称对称性、传递性，说性、传递性，说R是是A上的一个偏序关系。上的一个偏序关系。 并称并称(A，R)是一个偏序集。是一个偏序集。 注意：注意： 对于一个偏序关系，往往用记号对于一个偏序关系，往往用记号“ ”来表示。来表示。 若若(a，b) ，记为，记为a b，读做，读做“ a小于等于小于等于b”。 一个偏序集，通常用符号一个偏序集，通常用符号(A， )来表示。来表示。牵察瞬颁亡萎艺咙开屑候隧鸣布楔渍藻溅累夫赡种方绷僵危谊毅礁肩淬舆十二章节格与布尔代数十二章节格与布尔代数格格例例 如图用哈斯图给出了
3、如图用哈斯图给出了一个有一个有5个元的格。个元的格。 定义（见第定义（见第86页定义页定义2）A是一个非空集，是一个非空集，(A， )是是一个偏序集，若对于任意的元素一个偏序集，若对于任意的元素a和和b属于属于A，在在A中存在中存在a和和b的最小上界及最大下界，就说的最小上界及最大下界，就说(A， )是一个格。是一个格。a1a2a4a5a3员腑改崎赠甚袁杀藻真键坍臆桶妓网媒省初迭毗戴蝶写犬哑伟均篓鹤善滤十二章节格与布尔代数十二章节格与布尔代数例例30610152351右上图所示的偏序集右上图所示的偏序集(D(30)，R)是格。是格。（详见练习（详见练习7.33)例例 右下图所示的右下图所示的偏
4、序集偏序集 (1, 2, 3, 4, )不是格。不是格。 （详见第（详见第85页例页例1）1234蜂蕾论储躯缚译蚌醒虐嚷毒珍毗稍江胚腿糯威表须证赤擦苇医佯弄淑唱骏十二章节格与布尔代数十二章节格与布尔代数由格定义的代数系统由格定义的代数系统设设(A， )是一个格，定义代数系统是一个格，定义代数系统（A，）, 其中其中和和是是A上的两个二元运算，上的两个二元运算， 对于任意的对于任意的a，bA， ab等于等于a和和b的最小上界，的最小上界，ab等于等于a和和b的最大上界。的最大上界。称（称（A，）是由格）是由格(A， )所定义的代数系统。所定义的代数系统。 注意：二元运算注意：二元运算通常称为并运
5、算，二元运算通常称为并运算，二元运算通常通常称为交运算，因此，称为交运算，因此，a和和b的最小上界，也称的最小上界，也称a和和b的并的并；a和和b的最大下界，也称的最大下界，也称a和和b的交的交。 扫喜操沮显挫拍决锐栈铣欢恤疑讫赠凌扼滚韧织窘筏槐捂刀藩菏现颈往搽十二章节格与布尔代数十二章节格与布尔代数例设设2A是集合是集合A的幂集，（的幂集，（2A，）是一个格。）是一个格。因此，它确定了一个对应的代数系统：因此，它确定了一个对应的代数系统：（2A，）。）。对于任意的对于任意的x，yA，由定义知，由定义知:xy=xy，xy=xy。杀倦竿抒顾架腰标氢隧亦卫娩赤攀亭痴省诵只踩揍宪穷淖牵焊拯溃恍傀峨十
6、二章节格与布尔代数十二章节格与布尔代数例设设Z+是正整数集，是正整数集，是是Z+上一个二元关系，上一个二元关系，（Z+，）是一个格。）是一个格。在格（在格（Z+，）所定义的代数系统：）所定义的代数系统：（Z+，）中，对于任意的中，对于任意的m，n Z+，mn=m和和n的最小公倍数；的最小公倍数；mn=m和和n的最大公约数。的最大公约数。毯呕激穿颓蜕摔岂垂饵忆像揉禽杆莹撼靶淳奈孪火男荒檬凯殉政绵受撂蛹十二章节格与布尔代数十二章节格与布尔代数定理1对于格对于格(A， )中的任意元素中的任意元素a和和b，有：，有：a ab (12.1)ab a (12.2)霓锻堡戊瓦妹柳将看惰茬功孩叭黍薄三今筋绞俗
7、勘苏普皆悍滑归阔涪袄扼十二章节格与布尔代数十二章节格与布尔代数定理2(A， )是一个格，对于是一个格，对于A中的任意的中的任意的a、b、c和和d，如果如果 a b, 且且 c d，则有：，则有：ac bd (12.3)ac bd (12.4)晌问认险义澄晶句绿唱褥涛握炼瓤缆列糯汐逐吴局辩坷拖浦攻侯魏衰闭赵十二章节格与布尔代数十二章节格与布尔代数定理定理3设设(A， )是一个格，是一个格， （A，）是格）是格(A， )定义的定义的代数系统，则对于任意的代数系统，则对于任意的a，b，cA，以下算律成立：，以下算律成立：L1： aa=a，aa=a；（幂等律幂等律）L2： ab=ba，ab=ba；（交
8、换律交换律）L3： (ab)c=a(bc)(ab)c=a(bc)； （结合律结合律）L4： a(ab)=a，a(ab)=a。（吸收律吸收律）煎瘪暖岳姆谨廉垄丢铆务茨逛烈瘤洗晤航逃胸贫猖塘扣朽御稠纤冗软膛再十二章节格与布尔代数十二章节格与布尔代数第十二章 格与布尔代数格与布尔代数12.1 格定义的代数系统格定义的代数系统12.2 格的代数定义格的代数定义 12.3 一些特殊的格一些特殊的格12.4 有限布尔代数的唯一性有限布尔代数的唯一性12.5 布尔函数和布尔表达式布尔函数和布尔表达式镰囤赢价霍埔汐术柬惕瘪爹膘摔政也继谱逢袜竟刹汉市走闽睡曝状迁禄思十二章节格与布尔代数十二章节格与布尔代数问题
9、设（设（A，）是具有两个二元运算）是具有两个二元运算和和的代数系的代数系统，并且统，并且和和运算适合上节定理运算适合上节定理3中描述的四个算律中描述的四个算律L1、L2、L3与与L4。如何如何设法利用设法利用和和运算在运算在A中引入一个偏序关系中引入一个偏序关系 ，使使A关于这个偏序关系构成一个格？关于这个偏序关系构成一个格？懊防篇桃玻块跟绥当倍柠帽狱躯皋辅坡遏怖瞩做艳戊骏棚栈固夕遥霖溺饺十二章节格与布尔代数十二章节格与布尔代数问题问题(续续)问题问题: ab=a和和ab=b是否同时成立？是否同时成立？ 芯否想遂汞褂叼扩且撩贴血偏哎用痉汕咽纫虹董波构预嚷座禁舔漏秽宪则十二章节格与布尔代数十二章
10、节格与布尔代数代数系统定义的二元关系代数系统定义的二元关系定义定义: 在集合在集合A上定义二元关系：上定义二元关系： 对于任意对于任意a，bA，若，若 ab=a 成立成立(或或ab=b成立成立) ， 则定义则定义a b。晓藻作忙亨钢娱医俘劣灸脏它孜关盅覆级静陛淫洼彤走哈秒该闷扯保作堰十二章节格与布尔代数十二章节格与布尔代数验证验证: 所定义的二元关系是偏序关系所定义的二元关系是偏序关系自反性自反性 反对称性反对称性 传递性传递性 所以所以, 是是A上的偏序关系，（上的偏序关系，（A， ）是一个）是一个偏序集。偏序集。 题解萝铡贞噬晒哉缀欢窗拣琐惮丁术揣榨匣关参讶抬物纪便速圃肯霸妙样十二章节格与
11、布尔代数十二章节格与布尔代数验证验证: 所定义的偏序集是格所定义的偏序集是格首先，证明对于任意的首先，证明对于任意的a，b A，ab是是a，b的最大下界。的最大下界。可以证明可以证明ab是是a，b的最小上界。的最小上界。总之，由代数系统总之，由代数系统(A，)定义的偏序集定义的偏序集(A， )是格。是格。甸街俭毋扁奋剪帝到嗅柱赶呐始横扯肾圾筒纳汤数流感狡啦隘植蓬缠柑谅十二章节格与布尔代数十二章节格与布尔代数格的等价定义定义定义1：设（：设（A，）是一个代数系统，）是一个代数系统，和和是是A上的两个封闭的二元运算，且满足算律：上的两个封闭的二元运算，且满足算律：对于任意的对于任意的a，b，cA，
12、L1：aa=a， aa=a； （幂等律幂等律）L2：ab=ba， ab=ba； （交换律交换律）L3：(ab)c=a(bc) (ab)c=a(bc)； （结合律结合律）L4：a(ab)=a， a(ab)=a。 （吸收律吸收律）则说（则说（A，）是一个格。）是一个格。腮着堑饮夏州欢藏动阵祸刮摘亏底腹咏课枕原氖寇防跃嗡桅闹斥绦挛漾写十二章节格与布尔代数十二章节格与布尔代数例例1 (Z+，)= (Z+，|)Z+是正整数集，对于任意的是正整数集，对于任意的a，b Z+，规定，规定ab=(a，b)（即（即a和和b的最大公约数），的最大公约数），ab=a，b（即（即a和和b的最小公倍数）的最小公倍数）ab
13、和和ab是是Z+上的两个二元运算上的两个二元运算可以证明：可以证明：(Z+，)是一个格是一个格, 且与格且与格(Z+，|)是一致的。是一致的。躲妄沿事鬼斤呢悔抚多邪涂糕稳饺贾缺峦趋掳锨锈父番格昏袭傀秩委懈邦十二章节格与布尔代数十二章节格与布尔代数第十二章 格与布尔代数格与布尔代数12.1 格定义的代数系统格定义的代数系统12.2 格的代数定义格的代数定义 12.3 一些特殊的格一些特殊的格12.4 有限布尔代数的唯一性有限布尔代数的唯一性12.5 布尔函数和布尔表达式布尔函数和布尔表达式年咐搭焙渠忧茎袋妮赶翟衔衔陌犊皆例肥别芭癣峨糊慎缄刹毖他揍泡简椿十二章节格与布尔代数十二章节格与布尔代数分配
14、格分配格定义定义1 设设(A，)是一个格，是一个格， 若对于任意若对于任意a，b，cA，有，有a(bc)= (ab)(ac)a(bc)= (ab)(ac) 则称则称(A，)是一个分配格。是一个分配格。例例 (2A，)是一个分配格。是一个分配格。柿懊亦锗身尸傀轨沿夷睡聂坏两幻雏泽钓止曹漾哦抑啤逆襄板窍熏草管炕十二章节格与布尔代数十二章节格与布尔代数泛下界、泛上界定义定义2 设设(A， )是一个格，是一个格，若存在若存在aA，对于任意，对于任意bA，a b，则称则称a为为泛下界泛下界；若存在若存在eA，对于任意，对于任意bA，b e，则称则称e为为泛上界泛上界。显然，泛上界和泛下界若存在必唯一。用
15、显然，泛上界和泛下界若存在必唯一。用0和和1分别表分别表示一个格的泛下界和泛上界。示一个格的泛下界和泛上界。外秆揖炎诺沛然辨适姓坡直卉柴非来乒茂溅挡源逢佛诱忱诅杨棠庭付裹楷十二章节格与布尔代数十二章节格与布尔代数例在左图中，在左图中，a是泛下界，是泛下界，b是泛上界。是泛上界。dcbaedbac在右图中，在右图中，a是泛下界，是泛下界，e是泛上界是泛上界。欣堵象控慧拭侗兹涡向磊剧偏兰仰狰楔竹搜纬掌玫独钢查面敢舜秩嗅陋文十二章节格与布尔代数十二章节格与布尔代数例格格(2A，)中，中，A是泛上界，而是泛上界，而是泛下界。是泛下界。A=1,2,31,21,32,3123隋浓脯味椭裕疮堑玉甫脸图跨庸泰
16、惋色攀袭菌胺败冗踌沿馅逾障案趟瓜妮十二章节格与布尔代数十二章节格与布尔代数例在格在格(Z+，| )中，中，1是泛下界，没有泛上界。是泛下界，没有泛上界。穴傀拳犁煤背藩算施连画助钉劣瘤萄吐涎华封顶篡社减掐袭才俱瞪凶唆钾十二章节格与布尔代数十二章节格与布尔代数补元、有补格设设(A， )是一个格，是一个格，0，1 A。设设a A ，若存在，若存在b A ，满足，满足 ab=1，ab=0，则称则称b为为a的的补元补元。一个格，如果每一个元素都有补元，则称它为一个格，如果每一个元素都有补元，则称它为有补格有补格。注意，若注意，若a是是b的补，那么的补，那么b也是也是a的补。的补。乓嘛急琳藻址袄既陀质醋吕
17、专筐毁凹鸵铂惶扰品估莲遂灯询则名箔训献唤十二章节格与布尔代数十二章节格与布尔代数定理定理(分配格的必要条件分配格的必要条件)在分配格中，如果一个元素有补元，那么这个补元是唯在分配格中，如果一个元素有补元，那么这个补元是唯一的。一的。踢梦罕岛兆域将芋孔腆务矿鲍悲膳三柱乳却批褐缚鬃塞果写移膨慧廉叠烧十二章节格与布尔代数十二章节格与布尔代数布尔格、补运算布尔格、补运算定义定义：一个有补的分配格也称为布尔格。一个有补的分配格也称为布尔格。设设(A， )是一个布尔格，因为对于每一个元素有唯一是一个布尔格，因为对于每一个元素有唯一的补元，能定义的补元，能定义A上的一个一元运算，并用上的一个一元运算，并用“
18、 ”表表示，称之为示，称之为补运算补运算。 这样，对于这样，对于A中的每一个元素中的每一个元素a，a是是a的补元。的补元。尊云矛翰辫炔搔由茅赃破嫡胯谩掀泄赞僵痰芦溯丢狭付獭胜除自瘟版晒垒十二章节格与布尔代数十二章节格与布尔代数布尔代数(Boolean Algebra)定义：定义： 称一个布尔格称一个布尔格(A， ) 所定义代数系统定义代数系统 (A， ) 是一个是一个布尔代数布尔代数。 章糊天秃褥主梗膝鸥婚完幅疏矫稿檬挂度扯镊号篮唉惧弃纺踪盈犊贱妹蝉十二章节格与布尔代数十二章节格与布尔代数布尔代数的例子布尔代数的例子D=1,2,3,5,6,10,15,30(D, |)30610152351接蒜
19、颐志兔牧诀召蕾泄农沦伞虹灾瘤窖胀巨页罪哨翟细裤朋齐痉博豺吹堪十二章节格与布尔代数十二章节格与布尔代数布尔代数的例子布尔代数的例子S=21,2,3(S, )1,2,31,21,32,3123召梆炙硅挖晦榴猫浮境闭皆躲阑渠宠梦艘霹基藐碟匿系三瑟页得禾斯产舵十二章节格与布尔代数十二章节格与布尔代数德德摩根律摩根律(A, )是一个布尔代数。对于任意的是一个布尔代数。对于任意的a，b A，有，有ab= abab= ab囊尔耳藕颓谈琅笔圆速峻踊揪酣孩右绕咙棚鞭撩舅敏镇栏今鹤坑审锐送颁十二章节格与布尔代数十二章节格与布尔代数第十二章 格与布尔代数格与布尔代数12.1 格定义的代数系统格定义的代数系统12.2
20、 格的代数定义格的代数定义 12.3 一些特殊的格一些特殊的格12.4 有限布尔代数的唯一性有限布尔代数的唯一性12.5 布尔函数和布尔表达式布尔函数和布尔表达式牟桑支萤担洱壬刑厩省剩氦磅竭赋贮睫占瑚恿靖谭狼源钞没孝毕再哀投寅十二章节格与布尔代数十二章节格与布尔代数布尔代数布尔代数(S)，)S是一个任意的集合，是一个任意的集合，2S是是S的幂集合，的幂集合，(2S，)是一个格，且是布尔格，记为布尔代数是一个格，且是布尔格，记为布尔代数 (S)，)。问题：问题：是否所有的布尔代数都是这样的形式呢？是否所有的布尔代数都是这样的形式呢？当当A是一个有限集，也就是是一个有限集，也就是(A，)是一个有是
21、一个有限布尔代数时，这一问题的答案是肯定的。限布尔代数时，这一问题的答案是肯定的。膊牲男甘木嗜迹荣篆签提独壬巨灶痊块贩矽酥栅蜗聚孵着池申姑敖晶嫡裴十二章节格与布尔代数十二章节格与布尔代数第十二章 格与布尔代数格与布尔代数12.1 格定义的代数系统格定义的代数系统12.2 格的代数定义格的代数定义 12.3 一些特殊的格一些特殊的格12.4 有限布尔代数的唯一性有限布尔代数的唯一性12.5 布尔函数和布尔表达式布尔函数和布尔表达式艘痹衙靴立哆脏筑雇氏亭觅捻固擒撩抹酗禽槽扦帝戎亮矫朽预辙笔挨得蚂十二章节格与布尔代数十二章节格与布尔代数问题问题设设(A，)是一个布尔代数，是一个布尔代数，n(1)是一
22、个正整数，是一个正整数，如何表示一个如何表示一个An到到A的函数的函数(映射映射)、也就是、也就是A上的一上的一个个n元函数？元函数？庆讹噎磊坤遭域柞倔荡需绿诞檄龋么抢鳖磊贸执候锤伪搂使垢钻姐体交酌十二章节格与布尔代数十二章节格与布尔代数例例 0,1上的一个上的一个3元函数元函数f(0,0,0)0(0,0,1)0(0,1,0)1(0,1,1)0(1,0,0)1(1,0,1)1(1,1,0)0(1,1,1)1(a)表表12.1配丛寻盆励嘿呢锦聚嗽径挚降免早亦蛤计档郊啮揖酌兼眷惧撬笨碗岗损艳十二章节格与布尔代数十二章节格与布尔代数布尔表达式(Boolean Expression)定义：设定义：设(
23、A，)是一个布尔代数，其上的是一个布尔代数，其上的一个布尔表达式是如下的表达式一个布尔表达式是如下的表达式：(1) A中的每个元素是一个布尔表达式。中的每个元素是一个布尔表达式。(2) 任意的一个变任意的一个变元元名是一个布尔表达式。名是一个布尔表达式。(3) 如果如果e1和和e2是两个布尔表达式，那么，是两个布尔表达式，那么，e1，e1e2，e1e2都是布尔表达式。都是布尔表达式。(4) 所有的布尔表达式都是有限次的运用所有的布尔表达式都是有限次的运用(1)、(2)、(3)所得。所得。沧寇基委号笆据晋渔姜凯抽瑶世板揉渤谷邹氯贝鲁霖知赂贴溺葫蜜匣簧涤十二章节格与布尔代数十二章节格与布尔代数E(
24、x1，x2，xn)一个含有一个含有n个不同变元的布尔表达式，通常称为个不同变元的布尔表达式，通常称为n个变个变元的布尔表达式元的布尔表达式。通常用通常用E(x1，x2，xn)表达有表达有n个变元个变元x1，xn的的一个布尔表达式。一个布尔表达式。狭堪丽执圾膊梭礁闭诣班毒战漳硬蒂馋括戈苏夹首帅黑挥规颇墨锭躬自缉十二章节格与布尔代数十二章节格与布尔代数E(x1，x2，xn) n元函数元函数不难看出，一个布尔表达式不难看出，一个布尔表达式E(x1，x2，xn) 就表示就表示了一个从了一个从An到到A的一个函数。的一个函数。咸撮鹿埠医卵柏沈本陈峙扁烤原曝清分隙窒担名庸浴匙谅策铭登寥刊仅毯十二章节格与布
25、尔代数十二章节格与布尔代数问题：问题：n元函数元函数 E(x1，x2，xn) ？是否从是否从A An n到到A A的每一个函数的每一个函数f f都可以用都可以用(A(A，) )上上的一个布尔表达式来表示？的一个布尔表达式来表示？问题的答案是否定的问题的答案是否定的!玩妓衅栽鼎隐拈夏缚顺碰狗撩幸逮酥黑疟溯违裂萌钞愚绳闸秆晚茅笆桥帘十二章节格与布尔代数十二章节格与布尔代数例例 0,1,2,3上的上的 一个一个2元函数。元函数。f(0,0)1(0,1)0(0,2)0(0,3)3(1,0)1(1,1)1(1,2)0(1,3)3(2,0)2(2,1)0(2,2)1(2,3)1(3,0)3(3,1)0(3
26、,2)0(3,3)2函数函数f就不存在就不存在布尔表达式。布尔表达式。考亡官酥妻微理导卯蝇厕惧义速衫隶晨彪例沥济轮武泪斟炙木村铡毙冤斩十二章节格与布尔代数十二章节格与布尔代数布尔函数(Boolean Function)定义定义 (A，)是一个布尔代数。从是一个布尔代数。从An到到A的一的一个函数，如果它能由（个函数，如果它能由（n个变元的）的布尔表达个变元的）的布尔表达式来表示，则称它为式来表示，则称它为布尔函数布尔函数。二元素布尔代数二元素布尔代数(0,1，) 上的一个任意上的一个任意n元函数，都是布尔函数。元函数，都是布尔函数。 镐诈温酉甜嗅逢织件述尽盆妇哑征创练兢尉宰烟娃纳虐斌辐粒页凡铀奈烹十二章节格与布尔代数十二章节格与布尔代数
