计算机问题求解-论题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，布尔代数和有界有补分配格是“等价”的
问题4： ·有界有补分配格一定有2n个元素 因为B1,B2,B3,..,Bn有2n个元素？ 其实，我们还可以这样来观察： 1,这样的格中，原子个数是n个 2,除0外，所有元素都可以表示为一个或者多个原子的 join,所有由一个或者多个原子的join的结果都是格中元素。 3,这样的元素有2n.1个
问题4： • 有界有补分配格一定有2 n个元素 因为B1，B2，B3，…,Bn有2 n个元素？ 其实，我们还可以这样来观察： 1，这样的格中，原子个数是n个 2,，除0外，所有元素都可以表示为一个或者多个原子的 join，所有由一个或者多个原子的join的结果都是格中元素。 3，这样的元素有2 n -1个
问题5：我们为什么要定义sum-of-products form?如何理解form是什么意思？ Fig.15-3 rectangle(universal set)into eight numbered sets which can be represented as follows: (1)A∩B∩C(3)ABc∩C(5)AnBc∩Ce(7)AcnBnC (2)A∩BnCe(4)Ac∩B∩C(6)Ac∩BnCe(8)Ac∩BenCc
问题5：我们为什么要定义sum-of-products form?如何理解form是什么意思？
问题6：任意的布尔代数运算表达式，是否都 可以表达为某个"sum-of-products form'"? E=(x+y')+(xyz'+x'y)'and E2=((xy'z'+y)'+x'z)
问题6：任意的布尔代数运算表达式，是否都 可以表达为某个”sum-of-products form”？
回到举重裁判的问题 fx.y.) 相应的布尔表达式： 0 0 0 0 (x'( v(XAVAE) 0 0 1 0 0 1 0 0 问题7：有没有科学 0 1 1 0 0 法，从任意的一个布尔 什么？ 11 0 1 逻辑表达式出发，得到 0 1 和它等价的最简表达式？ 小代数表达式是什么？ yZ+Xz+Xv
回到举重裁判的问题 x y z 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 f(x,y,z) 0 0 0 1 0 1 1 1 相应的布尔表达式: (x’yz) (xy’z) (xyz’) (xyz) 问题7:相应的布尔代数表达式是什么？ x’ yz+ xy’ z+ xyz’+ xyz 问题8:相应的最简布尔代数表达式是什么？ yz+xz+xy 问题7：有没有科学办 法，从任意的一个布尔 逻辑表达式出发，得到 和它等价的最简表达式？
复习几个概念： Literal？Fundamental product？Contained in? “惊艳”的吸收率： x'is not a literal of xy'z.Observe that if P is contained in P2,say P2 =P 2,then,by the absorption law, P1+P2=P1+P*Q=P1 Thus,for instance,x'+x'y=x
复习几个概念： Literal？Fundamental product？Contained in? “惊艳”的吸收率：