计算机问题求解-论题1-13 -布尔代数 2015年12-31
计算机问题求解--论题1-13 --布尔代数 2015年12-31
问题1：这个是布尔代数的定义，你有没有一种熟悉的感 觉？它和另一个定义有什么异同之处？你能想到什么？ Let B be a nonempty set with two binary operations and *a unary operation,and two distinct elements 0 and 1.Then B is called a Boolean algebra if the following axioms hold where a.b.c are any elements in B: B Commutative laws: (la)a+b=b+a (Ib)a*b=b*a [B2] Distributive laws: (2a)a+(b*c)=(a+b)*(a+c) (2b)a*(b+c)=(a米b)+(a*c) [B3] Identity laws: (3a)a+0=a (3b)a*1=a [Ba] Complement laws: (4a)a+a'=1 (4b)a*a=0 Axioms Defining a Lattice Let L be a nonempty set closed under two binary operations called meer and join.denoted respectively by A and V.Then L is called lattice if the following axioms hold where a,b,c are elements in L: [L1】Commutative law: (1a)aAb=b入d (Ib)avb=bva [L2]Associative law: (2a)(4八b)Ac=aA(bAc) (2b)(avb)vc=av(bvc) [L3]Absorption law: (34)4A(aVb)=a (3b)aV(a入b)=4 We will sometimes denote the lattice by (L.A,V)when we want to show which operations are involved
问题1：这个是布尔代数的定义，你有没有一种熟悉的感 觉?它和另一个定义有什么异同之处？你能想到什么？
“这个”代数和格 Theorem 15.2:Let a,b,c be any elements in a Boolean algebra B. (i)Idempotent laws: (5a)a+a=a (5b) a米a=a (i） Boundedness laws: 6a)4+1=1 (6b) a*0=0 Gii) Absorption laws: @0+0*b三a (7b)a*(a+b)=a (iv) Associative laws: (8a)(a++c三a+(b+c) (8b)(a*b)*c=a*(b*c) 问题2：显然，这个代数一定是个格！那么：多出来的那些特性 (由公理描述)，有什么用呢？
“这个”代数和格 问题2：显然，这个代数一定是个格！那么：多出来的那些特性 （由公理描述），有什么用呢？
我们可以很容易的验证B3是布尔代数 (b)Let Bn=B x B x...x B (n factors)where the operations of+,*and'are defined componentwise using Fig.15-1.For notational convenience,we write the elements of B as n-bit sequences without commas.e.g.. x =110011 and y 111000 belong to B".Hence x+y=111011,x*y=110000,x′=001100 111 Then B"is a Boolean algebra.Here 0=000...0 is the zero element,and 1 =111...I is the unit element. 110 101 011 问题3：从这个B3中，我们能否设计一个“类似”的格？ 元素有哪些？偏序关系是什么？ 010 meet和join分别是什么？ 100 001 000 B3
我们可以很容易的验证B3是布尔代数 001 111 110 101 011 010 100 000 B3 问题3：从这个B3中，我们能否设计一个“类似”的格？ 元素有哪些？偏序关系是什么？ meet和join分别是什么？
其实，布尔代数是一类特别的格： ·1,我们可以从布尔代数和偏序集两个角度共同定义一个“系统” ·2,布尔代数和有界有补分配格是“等价”的 Theorem 15.5:The following are equivalent in a Boolean algebra: (1)a+b=b,(2)a*b=a,(3)a'+b=1,(4)a*b=0 Thus in a Boolean alegbra we can write a b whenever any of the above four conditions is known to be true
其实，布尔代数是一类特别的格： • 1，我们可以从布尔代数和偏序集两个角度共同定义一个“系统” • 2，布尔代数和有界有补分配格是“等价”的