离散数学第五章格与布尔代数.ppt
离散数学=((x??y?)?(y?(x?)?))?=((x??y?)?(y?x))?(反身律)=((x?y)?(x??y?))?(交换律)=(x??y?)?(x?y)(deMorgan律及反身律)=(x?y)?(x??y?)(交换律)=x+y(定理7(3))(9)x?0=x?1?(1?=0)=x+1(由本定理(6))=(x\1)?(1\x)=(x?1?)?x?(定理6(1))=(x?0)?x?(1?=0)*第30页,共86页,星期日,2025年,2月5日离散数学=0?x?(因0?x及定理5(1))=x?(因0?x?及定理5(1))有限集合代数是有限布尔代数(例4);有限布尔代数是否是有限集合代数呢?下面的斯笃(stone)定理回答了这个问题,答案是肯定的;这就为我们利用熟悉、简单的有限集合代数来研究、简化有限布尔代数奠定了理论基础。定义3.原子(atom)设(B,?,?,?,?,0,1)是布尔代数。a是B的一个原子?a?B?a?0?(?x?B)(a?x=0?a?x=a)?a?B?a?0?(?x?B)(x?0?a?x=0?a?x)。*第31页,共86页,星期日,2025年,2月5日离散数学注:?令S={a:a?B?a是原子}称S为B的原子集;?定义中a?0说明原子a不能是最小元;?定义中后一等价式说明:任一非零元(x?0),要么与原子不可比较(a?x=0),要么比原子大(a?x)。例7.a0a6a2a7a4a5a3a1图3图2图1a0a1a2a3a0a1*第32页,共86页,星期日,2025年,2月5日离散数学在图1中,a0是最小元,a1是原子,a1是最大元;在图2中,a0是最小元,a2,a3是原子,a1是最大元;在图3中,a0是最小元,a2,a3,a4是原子,a1是最大元;定理9.设(B,?,?,?,?,0,1)是布尔代数,并且a?B。a是B的一个原子?a是0的一个直接后继;即a是B的一个原子?0?a?a?0?(?x?B)(0?x?x?a?x=0?x=a)。[证].先证?):①已知a?0(原子的定义);②显然0?a(0是B的最小元及a?B);③(?x?B)(0?x?x?a?x=0?x=a)*第33页,共86页,星期日,2025年,2月5日离散数学对于任何元素x?B,0?x?x?a?a?x=x(本节定理5(1)及x?a)?x=0?x=a(a是原子,故a?x=0?a?x=a)由①②③可知,a是0的直接后继;次证?):①已知a?B;②已知a?0(a是0的直接后继);③(?x?B)(a?x=0?a?x=a)(采用二分法);对于任何元素x?B,分情况论证如下:(甲)x与a可比较:(Ⅰ)x=0,则有a?x=0(本节定理5(1)及0?a)*第34页,共86页,星期日,2025年,2月5日离散数学(Ⅱ)x?0(a)x?a?0?x?x?a(0是B的最小元及x?0)?x=a(a是0的直接后继)?a?x=a(幂等律)(b)a?x,则有a?