8 布尔代数 习题答案.doc

练习8.11证明在布尔代数中a(ab)=ab, a(a b)=ab证明：a(ab)= (aa)(ab) 分配律=1(ab) 布尔代数的定义=ab 布尔代数的定义第二个式子是第一个式子的对偶式，对第一个式子用对偶原理即可得到。2证明：(1) (ab)(cd)=(ac)(bc)(ad)(bd)(2) (ab)(cd)=(ac)(bc) (ad)(bd)并推广到一般情况。证明：只需证明第一式，用对偶原理即得第二式。(ab)(cd)=( (ab)c)(ab)d) 分配律=( (ac)(bc)(ad)(bd) 分配律= (ac)(bc) (ad)(bd) 结合律推广到一般情况：(1) (a1a2an)(b1b2bn)=(a1b1)(a1b2)(a1bn) (a2b1)(a2b2)(a2bn) (anb1)(anb2)(anbn) (2) (a1a2an) (b1b2bn)=(a1b1) (a1b2) (a1bn)(a2b1) (a2b2) (a2bn)(anb1) (anb2) (anbn) 3. 证明：(1) (a c) (bc) (ab)=(a b) (ac) (b c)证明：左式=(a c) (bc) (ab)=(a c) b) (a c) c) )(ab) 分配律=(a b)(c b) (a c)(c c)(ab) 分配律=(a b)(c b) (a c)(ab) 分配律= (a b)(c b) (a c)(ab) 分配律=(a b)(c b) (a c) a) (a b)(c b) (a c) b) 分配律= (a ba)(c ba) (a ca)(a bb)(c bb) (a cb) 分配律= (c ba)(a cb) 布尔代数的定义右式=(a b) (ac) (b c)=(a b) a)(a b) c)(b c) 分配律=(a a)(ba)(a c)(b c)(b c) 分配律=(ba)(a c)(b c)(b c) 分配律=(ba)(a c)(b c)b) (ba)(a c)(b c) c) 分配律=(bab)(a cb)(b cb) (bac)(a cc)(b cc) 分配律=(a cb) (bac) 布尔代数的定义所以，左式=右式，即原式成立。(2) (ab) (bc) (ca)=(ab) (bc) (ca)证明：(ab) (bc) (ca)=(ab) b)(ab) c)(ca) 分配律=(b(ab) c)(ca) 吸收律=(b(ac)(bc)(ca) 分配律=( b(ac)(ca) 交换律、吸收律=( b(ac)c)(b(ac)a) 分配律=( ba)(bc)c)(ba)(bc)a) 分配律=( ba)c)( (bc)a) 吸收律=( ba)c)( (bc)a) 吸收律=( bc)(ac)( (ba)(ca) 分配律=(ab) (bc) (ca) 幂等律、交换律4. 证明：如果ab=ac 且ab=ac，则b=c.证明：b=b(ab) 吸收律= b(ac) 题目条件= (ba)(bc) 分配律= (ac) (bc) 题目条件= (ab) c 分配律=(ac) c 题目条件=c 吸收律练习8.21构造命题布尔代数上的下列布尔函数的真值表(1) f(x,y,z)=x(yz)xyz(yz)x(yz)0000000110010100111010000101111101111111(2) f(x,y,z)=x(yz)xyzyzx(yz)0000000100010000111110001101011100111111(3) f(w,x,y,z)=wy(xz)w,x, y,z00 0000 0100 1000 1101 0001 0101 1001 1110 0010 0110 1010 1111 0011 0111 1011 11xz0101111101011111wy0000000000110011wy(xz)0000000000010011(4) f(w,x,y,z)=w(y(xz)w,x, y,z00 0000 0100 1000 1101 0001 0101 1001 1110 0010 0110 1010 1111 0011 0111 1011 11xz0101111101011111(y(xz)0001001100010011w(y(xz)00010011111111112. 构造一个三元函数f(x,y,z)，使得当且仅当x,y,z中恰有一个取值1时，f的值为0。解：据题意可知，函数f须满足以下表格：f10010111假设f(x,y,z)的主析取范式为f=(axyz) (bxyz) (cxyz) (dxyz) (exyz) (fxyz) (gxyz) (hxyz)把f(0,0,0)=f(0,1,1)=f(1,0,1)=f(1,1,0)=f(1,1,1)=1和f(0,0,1)=f(0,1,0)=f(1,0,0)=0代入上式可以得到a=1,b=1,c=1,d=0,e=1,f=0,g=0,h=1.代入f可以得到f=(xyz) (xyz) (xyz)(xyz)(xyz)或者用类似方法得到主合取范式f=(xyz)(xyz)(xyz)3已知为布尔代数，其上有布尔函数：f(x1,x2,x3)= (ax1x2) (x1(x3b)(1) 求f(b,1,a)的值；(2) 求f(x1,x2,x3)的主析取范式和主合取范式。解：(1) f(b,1,a)=b(2) 首先在此布尔代数中a=b，所以ab=1.方法一f(x1,x2,x3)= (ax1x2) (x1(x3b)=(ax1x2) (x1x3) (x1b)=(ax1x2 (x3 x3) (x1(x2 x2)x3) (b x1(x2 x2) (x3 x3)=(ax1x2 x3 ) (ax1x2 x3) (x1x2x3) (x1x2x3) (b x1x2x3) (b x1x2x3)(b x1x2x3) (b x1x2x3)=(x1x2x3) (x1x2x3) (x1x2x3) (bx1x2x3) 主析取范式f(x1,x2,x3)= (ax1x2) (x1(x3b)= (ax1x2) x1) (ax1x2) (x3b)= (x1)(ax3b) (x1x3b) (x2x3b)= (x1) (bx2x3)= (x1(x2 x2)(x3x3) (b(x1x1)x2x3)=(x1x2x3) (x1x2x3) (x1x2x3) (x1x2 x3)(bx1x2x3) (bx1x2x3)=(x1x2x3) (x1x2x3) (x1x2x3) (x1x2 x3)(bx1x2x3) (bx1x2x3) 主合取范式=(x1x2x3) (x1x2x3) (x1x2x3) (x1x2 x3)(bx1x2x3) 主合取范式方法二假设f(x1,x2,x3)的主析取范式为f=(a0x1x2x3) (a1x1x2x3) (a2x1x2x3) (a3x1x2x3) (a4x1x2x3) (a5x1x2x3) (a6x1x2x3) (a7x1x2x3)则f(0,0,0)= a7，f(0,0,1)= a6，f(0,1,0)= a5，f(0,1,1)= a4，f(1,0,0)=a3， f(1,0,1)=a2，f(1,1,0)=a1，f(1,1,1)=a0。再由f(x1,x2,x3)= (ax1x2) (x1(x3b)得到f(0,0,0)=0，f(0,0,1)=0，f(0,1,0)=0 ，f(0,1,1)=0，f(1,0,0)=1， f(1,0,1)=1，f(1,1,0)=b，f(1,1,1)=1。从而a0=1,a1=b,a2=1,a3=1,a4=0,a5=0,a6=0,a7=0.带入假设得到主析取范式为f=(x1x2x3) (bx1x2x3) (x1x2x3) (x1x2x3)类似方法可以得到主合取范式(x1x2x3) (x1x2x3) (x1x2x3) (x1x2 x3)(bx1x2x3) 4对于表11.1 中的函数f，分别写出其主析取范式和主合取范式。表11.1f10100101解：假设f(x1,x2,x3)的主析取范式为f=(ax1x2x3) (bx1x2x3) (cx1x2x3) (dx1x2x3) (ex1x2x3) (fx1x2x3) (gx1x2x3) (hx1x2x3)把f(0,0,0)=f(0,1,0)=f(1,0,1)=