8布尔代数习题答案

练习8.11．证明在布尔代数中a∨(a’∧b)=a∨b,a∧(a’∨b)=a∧b证明：a∨(a’∧b)=(a∨a’)∧(a∨b)分配律=1∧(a∨b)布尔代数的定义=a∨b布尔代数的定义第二个式子是第一个式子的对偶式，对第一个式子用对偶原理即可得到。2．证明：(1)(a∨b)∧(c∨d)=(a∧c)∨(b∧c)∨(a∧d)∨(b∧d)(2)(a∧b)∨(c∧d)=(a∨c)∧(b∨c)∧(a∨d)∧(b∨d)并推广到一般情况。证明：只需证明第一式，用对偶原理即得第二式。(a∨b)∧(c∨d)=((a∨b)∧c)∨((a∨b)∧d)分配律=((a∧c)∨(b∧c))∨((a∧d)∨(b∧d))分配律=(a∧c)∨(b∧c)∨(a∧d)∨(b∧d)结合律推广到一般情况：(1)(a1∨a2∨…∨an)∧(b1∨b2∨…∨bn)=(a1∧b1)∨(a1∧b2)∨…∨(a1∧bn)∨(a2∧b1)∨(a2∧b2)∨…∨(a2∧bn)∨…∨(an∧b1)∨(an∧b2)∨…∨(an∧bn)∨(2)(a1∧a2∧…∧an)∨(b1∧b2∧…∧bn)=(a1∨b1)∧(a1∨b2)∧…∧(a1∨bn)∧(a2∨b1)∧(a2∨b2)∧…∧(a2∨bn)∧…∧(an∨b1)∧(an∨b2)∧…∧(an∨bn)3.证明：(1)(a’∧c’)∨(b∧c)∨(a∧b’)=(a’∧b)∨(a∧c)∨(b’∧c’)证明：左式=(a’∧c’)∨(b∧c)∨(a∧b’)=(((a’∧c’)∨b)∧((a’∧c’)∨c))∨(a∧b’)分配律=((a’∨b)∧(c’∨b)∧(a’∨c)∧(c’∨c))∨(a∧b’)分配律=((a’∨b)∧(c’∨b)∧(a’∨c))∨(a∧b’)分配律=((a’∨b)∧(c’∨b)∧(a’∨c))∨(a∧b’)分配律=(((a’∨b)∧(c’∨b)∧(a’∨c))∨a)∧(((a’∨b)∧(c’∨b)∧(a’∨c))∨b’)分配律=((a’∨b∨a)∧(c’∨b∨a)∧(a’∨c∨a))∧((a’∨b∨b’)∧(c’∨b∨b’)∧(a’∨c∨b’))分配律=(c’∨b∨a)∧(a’∨c∨b’)布尔代数的定义右式=(a’∧b)∨(a∧c)∨(b’∧c’)=(((a’∧b)∨a)∧((a’∧b)∨c)))∨(b’∧c’)分配律=(((a’∨a)∧(b∨a))∧((a’∨c)∧(b∨c)))∨(b’∧c’)分配律=((b∨a)∧(a’∨c)∧(b∨c))∨(b’∧c’)分配律=(((b∨a)∧(a’∨c)∧(b∨c))∨b’)∧(((b∨a)∧(a’∨c)∧(b∨c))∨c’))分配律=(((b∨a∨b’)∧(a’∨c∨b’)∧(b∨c∨b’)))∧(((b∨a∨c’)∧(a’∨c∨c’)∧(b∨c∨c’))))分配律=(a’∨c∨b’)∧(b∨a∨c’)布尔代数的定义所以，左式=右式，即原式成立。(2)(a∧b)∨(b∧c)∨(c∧a)=(a∨b)∧(b∨c)∧(c∨a)证明：(a∧b)∨(b∧c)∨(c∧a)=(((a∧b)∨b)∧((a∧b)∨c))∨(c∧a)分配律=(b∧((a∧b)∨c))∨(c∧a)吸收律=(b∧((a∨c)∧(b∨c)))∨(c∧a)分配律=(b∧(a∨c))∨(c∧a)交换律、吸收律=((b∧(a∨c))∨c)∧((b∧(a∨c))∨a)分配律=(((b∧a)∨(b∧c))∨c)∧(((b∧a)∨(b∧c))∨a)分配律=((b∧a)∨c)∧((b∧c)∨a)吸收律=((b∧a)∨c)∧((b∧c)∨a)吸收律=((b∨c)∧(a∨c))∧((b∨a)∧(c∨a))分配律=(a∨b)∧(b∨c)∧(c∨a)幂等律、交换律4.证明：如果a∧b=a∧c且a∨b=a∨c，则b=c.证明：b=b∨(a∧b)吸收律=b∨(a∧c)题目条件=(b∨a)∧(b∨c)分配律=(a∨c)∧(b∨c)题目条件=(a∧b)∨c分配律=(a∧c)∨c题目条件=c吸收律练习8.21．构造命题布尔代数{0,1},∨,∧,﹁,0,1上的下列布尔函数的真值表(1)f(x,y,z)=x∧(y∨z)xyz(y∨z)x∧(y∨z)0000000110010100111010000101111101111111(2)f(x,y,z)=x∨(y∧z)xyzy∧zx∨(y∧z)0000000100010000111110001101011100111111(3)f(w,x,y,z)=w∧y∧(x∨z)w,x,y,z0000000100100011010001010110011110001001101010111100110111101111x∨z0101111101011111w∧y0000000000110011w∧y∧(x∨z)0000000000010011(4)f(w,x,y,z)=w∨(y∧(x∨z))w,x,y,z0000000100100011010001010110011110001001101010111100110111101111x∨z0101111101011111(y∧(x∨z))0001001100010011w∨(y∧(x∨z))00010011111111112.构造一个三元函数f(x,y,z)，使得当且仅当x,y,z中恰有一个取值1时，f的值为0。解：据题意可知，函数f须满足以下表格：f0,0,010,0,100,1,000,1,111,0,001,0,111,1,011,1,11假设f(x,y,z)的主析取范式为f=(a∧x∧y∧z)∨(b∧x∧y∧z’)∨(c∧x∧y’∧z)∨(d∧x∧y’∧z’)∨(e∧x’∧y∧z)∨(f∧x’∧y∧z’)∨(g∧x’∧y’∧z)∨(h∧x’∧y’∧z’)把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=(x∧y∧z)∨(x∧y∧z’)∨(x∧y’∧z)∨(x’∧y∧z)∨(x’∧y’∧z’)或者用类似方法得到主合取范式f=(x∨y∨z’)∧(x∨y’∨z)∧(x’∨y∨z)3．已知{0,1,a,b},∨,∧,’,0,1为布尔代数，其上有布尔函数：f(x1,x2,x3)=(a∧x1∧x2’)∨(x1∧(x3∨b))(1)求f(b,1,a)的值；(2)求f(x1,x2,x3)的主析取范式和主合取范式。解：(1)f(b,1,a)=b(2)首先在此布尔代数中a=b’，所以a∨b=1.方法一f(x1,x2,x3)=(a∧x1∧x2’)∨(x1∧(x3∨b))=(a∧x1∧x2’)∨(x1∧x3)∨(x1∧b)=(a∧x1∧x2’∧(x3∨x3’))∨(x1∧(x2∨x2’)∧x3)∨(b∧x1∧(x2∨x2’)∧(x3∨x3’))=(a∧x1∧x2’∧x3)∨(a∧x1∧x2’∧x3’)∨(x1∧x2∧x3)∨(x1∧x2’∧x3)∨(b∧x1∧x2∧x3)∨(b∧x1∧x2∧x3’)∨(b∧x1∧x2’∧x3)∨(b∧x1∧x2’∧x3’)=(x1∧x2’∧x3’)∨(x1∧x2∧x3)∨(x1∧x2’∧x3)∨(b∧x1∧x2∧x3’)主析取范式f(x1,x2,x3)=(a∧x1∧x2’)∨(x1∧(x3∨b))=((a∧x1∧x2’)∨x1)∧((a∧x1∧x2’)∨(x3∨b))=(x1)∧(a∨x3∨b)∧(x1∨x3∨b)∧(x2’∨x3∨b)=(x1)∧(b∨x2’∨x3)=(x1∨(x2∧x2’)∨(x3∧x3’))∧(b∨(x1∧x1’)∨x2’∨x3)=(x1∨x2∨x3)∧(x1∨x2∨x3’)∧(x1∨x2’∨x3)∧(x1∨x2’∨x3’)∧(b∨x1∨x2’∨x3)∧(b∨x1’∨x2’∨x3)=(x1∨x2∨x3)∧(x1∨x2∨x3’)∧(x1∨x2’∨x3)∧(x1∨x2’∨x3’)∧(b∨x1∨x2’∨x3)∧(b∨x1’∨x2’∨x3)主合取范式==(x1∨x2∨x3)∧(x1∨x2∨x3’)∧(x1∨x2’∨x3)∧(x1∨x2’∨x3’)∧(b∨x1’∨x2’∨x3)主合取范式方法二假设f(x1,x2,x3)的主析取范式为f=(a0∧x1∧x2∧x3)∨(a1∧x1∧x2∧x3’)∨(a2∧x1∧x2’∧x3)∨(a3∧x1∧x2’∧x3’)∨(a4∧x1’∧x2∧x3)∨(a5∧x1’∧x2∧x3’)∨(a6∧x1’∧x2’∧x3)∨(a7∧x1’∧x2’∧x3’)则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)=(a∧x1∧x2’)∨(x1∧(x3∨b))得到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=(x1∧x2∧x3)∨(b∧x1∧x2∧x3’)∨(x1∧x2’∧x3)∨(x1∧x2’∧x3’)类似方法可以得到主合取范式(x1∨x2∨x3)∧(x1∨x2∨x3’)∧(x1∨x2’∨x3)∧(x1∨x2’∨x3’)∧(b∨x1’∨x2’∨x3)4．对于表11.1中的函数f，分别写出其主析取范式和主合取范式。表11.1f0,0,010,0,100,1,010,1,101,0,001,0,111,1,001,1,11解：假设f(x1,x2,x3)的主析取范式为f=(a∧x1∧x2∧x3)∨(b∧x1∧x2∧x3’)∨(c∧x1∧x2’∧x3)∨(d∧x1∧x2’∧x3’)∨(e∧x1’∧x2∧x3)∨(f∧x1’∧x2∧x3’)∨(g∧x1’∧x2’∧x3)∨(h∧x1’∧x2’∧x3’)把f(0,0,0)=f(0,1,0)=f(1,0,1)=f(1,1,1)=1和f(0,0,1)=f(0,1,1)=f(1,0,0)=f(1,1,0)=0代入上式可以得到a=1,b=0,c=1,d=0,e=0,f=1,g=0,h=1.代入f可以得到主析取范式(x1∧x2∧x3)∨(x1∧x2’∧x3)∨(x1’∧x2∧x3’)∨(x1’∧x2’∧x3’)类似方法可得到主合取范式。(x1∨x2∨x3’)∧(x1∨x2’∨x3’)∧(x1’∨x2∨x3)∧(x1’∨x2’∨x3)