离散数学习题答案.pdf

《离散数学习题答案.pdf》由会员分享，可在线阅读，更多相关《离散数学习题答案.pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.离散数学习题答案离散数学习题答案习题一及答案：习题一及答案：P14-15P14-151414、将以下命题符号化：、将以下命题符号化：5 5李辛与李末是兄弟李辛与李末是兄弟解：设解：设 p p：李辛与李末是兄弟，那么命题符号化的结果是：李辛与李末是兄弟，那么命题符号化的结果是 p p6 6王强与王强与 X X 威都学过法语威都学过法语解：设解：设 p p：王强学过法语；：王强学过法语；q q：X X 威学过法语；那么命题符号化的结果是威学过法语；那么命题符号化的结果是pq9 9只有天下大雨，他才乘班车上班只有天下大雨，他才乘班车上班解：设解：设 p p：天下大雨；：天下大雨；q q：他乘班车上

2、班；那么命题符号化的结果是：他乘班车上班；那么命题符号化的结果是q p1111下雪路滑，他迟到了下雪路滑，他迟到了解：设解：设 p p：下雪；：下雪；q q：路滑；：路滑；r r：他迟到了；那么命题符号化的结果是：他迟到了；那么命题符号化的结果是(pq)r1515、设、设 p p：2+3=5.2+3=5.q q：大熊猫产在中国：大熊猫产在中国.r r：太阳从西方升起：太阳从西方升起.求以下复合命题的真值：求以下复合命题的真值：4 4(pqr)(pq)r)解：解：p=1p=1，q=1q=1，r=0r=0，(pqr)(110)1，(pq)r)(11)0)(0 0)1(pqr)(pq)r)11119

3、19、用真值表判断以下公式的类型：、用真值表判断以下公式的类型：2 2(p p)q解：列出公式的真值表，如下所示：解：列出公式的真值表，如下所示：-优选.pqpq(p p)(p p)q0 00 01 11 11 11 10 01 11 10 01 10 01 10 00 01 10 01 11 11 10 00 00 01 1由真值表可以看出公式有由真值表可以看出公式有 3 3 个成真赋值，故公式是非重言式的可满足式。个成真赋值，故公式是非重言式的可满足式。2020、求以下公式的成真赋值：、求以下公式的成真赋值：4 4(p q)q解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的

4、条件是：解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：(pq)1p 00q q 0所以公式的所以公式的成真赋值有：成真赋值有：0101，1010，1111。习题二及答案：习题二及答案：P38P385 5、求以下公式的主析取范式，并求成真赋值：、求以下公式的主析取范式，并求成真赋值：2 2(p q)(qr)解：原式解：原式(pq)qr qr(p p)qr(pqr)(pqr)m3 m7，此即公式的主析取范式，此即公式的主析取范式，所以成真赋值为所以成真赋值为 011011，111111。*6*6、求以下公式的主合取范式，并求成假赋值：、求以下公式的主合取范式，并求成假赋值

5、：2 2(pq)(pr)-优选.解：原式解：原式(ppr)(pqr)(pqr)M4，此即公式的主合取范式，此即公式的主合取范式，所以成假赋值为所以成假赋值为 100100。7 7、求以下公式的主析取范式，再用主析取范式求主合取范式：、求以下公式的主析取范式，再用主析取范式求主合取范式：1 1(pq)r解：原式解：原式 pq(r r)(p p)(qq)r)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m1 m3 m5 m6 m7，此即主析取范式。，此即主析取范式。主析取范式中没出现的极小项为主析取范式中没出现的极小项为m0，m2，m

6、4，所以主合取范式中含有三个极大项所以主合取范式中含有三个极大项M0，M2，M4，故原式的主合取范式，故原式的主合取范式 M0 M2 M4。9 9、用真值表法求下面公式的主析取范式：、用真值表法求下面公式的主析取范式：1 1(pq)(pr)解：公式的真值表如下：解：公式的真值表如下：p0 00 00 00 01 1q0 00 01 11 10 0rp1 11 11 11 10 0pq0 00 01 11 11 1pr0 01 10 01 10 0(pq)(pr)0 01 10 01 10 00 01 11 11 11 1-优选.1 11 11 10 01 11 11 10 01 10 00 0

7、0 01 11 11 10 00 00 01 11 11 1由真值表可以看出成真赋值的情况有由真值表可以看出成真赋值的情况有 7 7 种，此种，此 7 7 种成真赋值所对应的极小项的析取即为主析种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式取范式，故主析取范式 m1 m2 m3 m4 m5 m6 m7习题三及答案：习题三及答案：P52-54P52-541111、填充下面推理证明中没有写出的推理规那么。、填充下面推理证明中没有写出的推理规那么。前提：前提：pq,qr,r s,p结论：结论：s s证明：证明：p p前提引入前提引入pq前提引入前提引入 q q析取三段论析取三段论qr前提

8、引入前提引入 r r析取三段论析取三段论r s前提引入前提引入 s s 假言推理假言推理1515、在自然推理系统、在自然推理系统 P P 中用附加前提法证明下面推理：中用附加前提法证明下面推理：-优选.2 2前提：前提：(pq)(r s),(st)u结论：结论：p u证明：用附加前提证明法。证明：用附加前提证明法。p p附加前提引入附加前提引入pq附加附加(pq)(r s)前提引入前提引入r s假言推理假言推理s s化简化简st附加附加(st)u前提引入前提引入 u u假言推理假言推理故推理正确。故推理正确。1616、在自然推理系统、在自然推理系统 P P 中用归谬法证明下面推理：中用归谬法证

9、明下面推理：1 1前提：前提：p q，rq，r s结论：结论：p证明：用归谬法证明：用归谬法 p p结论的否认引入结论的否认引入p q前提引入前提引入q假言推理假言推理rq前提引入前提引入r析取三段论析取三段论r s前提引入前提引入-优选.r r化简化简r r合取合取由于由于r r 0，所以推理正确。，所以推理正确。1717、在自然推理系统、在自然推理系统 P P 中构造下面推理的证明：中构造下面推理的证明：只要只要 A A 曾到过受害者房间并且曾到过受害者房间并且 1111 点以前没离开，点以前没离开，A A 就是谋杀嫌犯。就是谋杀嫌犯。A A 曾到过受害者房间。曾到过受害者房间。如如果果

10、A A 在在 1111 点以前离开，看门人会看见他。看门人没有看见他。所以，点以前离开，看门人会看见他。看门人没有看见他。所以，A A 是谋杀嫌犯。是谋杀嫌犯。解：设解：设 p p：A A 到过受害者房间，到过受害者房间，q q：A A 在在 1111 点以前离开，点以前离开，r r：A A 是谋杀嫌犯，是谋杀嫌犯，s s：看门人看见过：看门人看见过A A。那么前提：那么前提：(pq)r，p，q s，s结论：结论：r证明：证明：q s前提引入前提引入s前提引入前提引入q拒取式拒取式p前提引入前提引入pq合取引入合取引入(pq)r前提引入前提引入r假言推理假言推理习题四及答案：习题四及答案：P6

11、5-67P65-675 5、在一阶逻辑中将以下命题符号化：、在一阶逻辑中将以下命题符号化：-优选.2 2有的火车比有的汽车快。有的火车比有的汽车快。解：解：设设 F(x)F(x)：x x 是火车，是火车，G(y)G(y)：y y 是汽车，是汽车，H(x,y)H(x,y)：x x 比比 y y 快；那么命题符号化的结果是：快；那么命题符号化的结果是：xy(F(x)G(y)H(x,y)3 3不存在比所有火车都快的汽车。不存在比所有火车都快的汽车。解：方法一：解：方法一：设设 F(x)F(x)：x x 是汽车，是汽车，G(y)G(y)：y y 是火车，是火车，H(x,y)H(x,y)：x x 比比

12、y y 快；那么命题符号化的结果是：快；那么命题符号化的结果是：x(F(x)y(G(y)H(x,y)或或x(F(x)y(G(y)H(x,y)方法二：方法二：设设 F(x)F(x)：x x 是火车，是火车，G(y)G(y)：y y 是汽车，是汽车，H(x,y)H(x,y)：x x 比比 y y 快；那么命题符号化的结果是：快；那么命题符号化的结果是：x(G(x)y(F(y)H(x,y)或或xy(G(x)(F(y)H(x,y)9 9、给定解释、给定解释 I I 如下：如下：(a)(a)个体域为实数集合个体域为实数集合 R R。(b)(b)特定元素特定元素a0。(c)(c)函数函数f(x,y)xy,

13、x,yR。(d)(d)谓词谓词F(x,y):xy,G(x,y):xy,x,yR。给出以下公式在给出以下公式在 I I 下的解释，并指出它们的真值：下的解释，并指出它们的真值：2 2xy(F(f(x,y),a)G(x,y)y 0 x y)，含义是：对于任意的实数，含义是：对于任意的实数 x x，y y，假设，假设 x-y=0 x-y=0 那么那么 xyx=2；2 2r(R)=RIA1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6，R11,5,5,1,2,5,5,2,3,1,1,3,3,3,4,5,5,4R2R3.RR21,5,2,5,3,1,3,3,3,5,4,5s

14、(R)Rt(R)R4141、设设 A=1A=1，2 2，3 3，44，R R 为为A A上 的 二 元 关 系，a,b,c,d A A，a,b R c,d ab cd1证明 R 为等价关系；2求 R 导出的划分。1 1只需证明只需证明 R R 具有自反性、对称性和传递性即可，证明过程如下：具有自反性、对称性和传递性即可，证明过程如下：-优选.a任取 a,b A A，有ab ab，a,b R a,b，所以 R 具有自反性；b任取 a,b,c,d A A，假设 a,b R c,d，那么有ab cd，cd ab，c,d R a,b，所以 R 具有对称性；c任取 a,b,c,d,e,f A A，假设

15、a,b R c,d 且 c,d R e,f，那么有ab cd且cd e f，ab e f，a,b R e,f，所以 R 具有传递性，综合a b c可知：R 为集合A A上的等价关系；2先求出集合A A的结果：A A 1,1,1,2,1,3,1,4,2,1,2,2,2,3,2,4,3,1,3,2,3,3,3,4,4,1,4,2,4,3,4,4 再分别求集合A A各元素的等价类，结果如下：1,1R1,1,1,2 R 2,1R1,2,2,1,1,3 R 2,2 R 3,1R1,3,2,2,3,1,1,4 R 2,3 R 3,2 R 4,1R1,4,2,3,3,2,4,1,2,4 R 3,3 R 4,

16、2 R 2,4,3,3,4,2,3,4 R 4,3 R 3,4,4,3,4,4 R 4,4。等价关系 R 导出的划分就是集合 A 关于 R 的商集A/R，而集合 A 关于 R 的商集A/R是由 R 的所有等价类作为元素构成的集合，所以等价关系R 导出的划分是：1,1,1,2,2,1,1,3,2,2,3,1,1,4,2,3,3,2,4,1,2,4,3,3,4,2,3,4,4,3,4,4 4646、分别画出以下各偏序集分别画出以下各偏序集A,R的哈斯图，的哈斯图，并找出并找出 A A 的极大元、的极大元、极小元、极小元、最大元和最小元。最大元和最小元。1 1Ra,d,a,c,a,b,a,e,b,e

17、,c,e,d,e解：哈斯图如下：解：哈斯图如下：IA-优选.ebcdafA A 的极大元为的极大元为 e e、f f，极小元为，极小元为 a a、f f；A A 的最大元和最小元都不存在。的最大元和最小元都不存在。*22*22、给定、给定A1,2,3,4，A A 上的关系上的关系R 1,3,1,4,2,3,2,4,3,4，试，试1 1画出画出 R R 的关系图；的关系图；2 2说明说明 R R 的性质。的性质。解：解：1 112342 2R R 的关系图中每个顶点都没有自环，所以的关系图中每个顶点都没有自环，所以 R R 是反自反的，不是自反的；是反自反的，不是自反的；R R 的关系图中任意两

18、个顶点如果有边的都是单向边，的关系图中任意两个顶点如果有边的都是单向边，故故 R R 是反对称的，是反对称的，不是对称不是对称的；的；R R 的关系图中没有发生顶点的关系图中没有发生顶点 x x 到顶点到顶点 y y 有边、顶点有边、顶点 y y 到顶点到顶点 z z 有边，但顶点有边，但顶点 x x 到到顶点顶点 z z 没有边的情况，故没有边的情况，故 R R 是传递的。是传递的。-优选.*48*48、设设A,R 和 B,S为偏序集，在集合为偏序集，在集合AB上定义关系上定义关系 T T 如下：如下：a1,b1,a2,b2AB,a1,b1T a2,b2 a1Ra2b1Sb2证明证明 T T

19、 为为AB上的偏序关系。上的偏序关系。证明：证明：1 1自反性：自反性：任取 a1,b1AB，则：R为偏序关系，具有自反性，a1Ra1S为偏序关系，具有自反性，b1Sb1a1Ra1 b1Sb1又 a1,b1T a2,b2 a1Ra2b1Sb2，a1,b1T a1,b1，故T具有自反性2 2反对称性：反对称性：任取 a1,b1,a2,b2AB，若 a1,b1T a2,b2且 a2,b2T a1,b1，则有：a1Ra2b1Sb2a2Ra1b2Sb1（1）（2）a1Ra2 a2Ra1，又R为偏序关系，具有反对称性，所以a1 a2b1Sb2b2Sb1，又S为偏序关系，具有反对称性，所以b1 b2 a1

20、,b1 a2,b2，故T具有反对称性3 3传递性：传递性：任取 a1,b1,a2,b2，a3,b3AB，若 a1,b1T a2,b2且 a2,b2T a3,b3，则有：a1,b1T a2,b2 a1Ra2b1Sb2a2,b2T a3,b3 a2Ra3b2Sb3a1Ra2 a2Ra3,又R为偏序关系，具有传递性，所以a1Ra3b1Sb2b2Sb3,又S为偏序关系，具有传递性，所以b1Sb3a1Ra3 b1Sb3 a1,b1T a3,b3，故T具有传递性。综合综合1 1 2 2 3 3知知 T T 具有自反性、反对称性和传递性，故具有自反性、反对称性和传递性，故 T T 为为AB上的偏序关系。上的

21、偏序关系。-优选.习题九及答案：习题九及答案：P179-180P179-1808 8、S=Q Q,Q 为有理数集，为S上的二元运算，a,b,x,y S有a,b x,y ax,ay+b1 1运算在S上是否可交换、可结合？是否为幂等的？2 2运算是否有单位元、零元？如果有，请指出，并求出S中所有可逆元素的逆元。解：解：1 1x,y a,b xa,xb+y ax,bx+y a,b x,y运算不具有交换律x,y a,b c,d ax,bx+y c,d acx,adx+bx+y而 x,y a,b c,d x,y*ac,ad+b xac,xad+xb+y acx,adx+bx+yx,y a,b c,d运算

22、有结合律任取 a,b s，则有：a,b a,b a2,abb a,b运算无幂等律-优选.2 2令 a,b*x,y a,b 对 a,b s均成立则有：ax,ay+b a,b 对 a,b s均成立ax 1 0ax a对a,b成立ayb bay 0 x 1 0 x 1必定有y 0y 0运算的右单位元为 1，0，可验证 1，0 也为运算的左单位元，运算的单位元为 1，0令 a,b*x,y x,y，若存在 x,y 使得对 a,b s上述等式均成立，则存在零元，否则不存在零元。由 a,b*x,y x,y ax,ay+b x,ya 1x 0ax xayb ya 1y+b 0由于a 1y+b 0不可能对 a,

23、b s均成立，故 a,b*x,y x,y 不可能对 a,b s均成立，故不存在零元；设元素 a,b 的逆元为 x,y，则令 a,b*x,y e 1，01x ax 1a（当a 0）ayb 0by a当a 0时，a,b 的逆元不存在；当a 0时，a,b 的逆元是1b,aa1111、设S1，2，.,10，问下面的运算能否与S构成代数系统 S，?如果能构成代数系统则说明运算是否满足交换律、结合律，并求运算的单位元和零元。3 3xy=大于等于x和y的最小整数；-优选.解：解：3 3由由*运算的定义可知：运算的定义可知：xy=max(x,y)，x,yS,有xyS，故运算在S上满足封闭性，所以运算与非空集合

24、S能构成代数系统；任取x,yS,有xy=max(x,y)=max(y,x)=yx,所以运算满足交换律；任取x,y,zS,有(xy)z=max(max(x,y),z)=max(x,y,z)=max(x,max(y,z)=x(yz),所以运算满足结合律；任取xS，有x1=max(x,1)=x=max(1,x)=1x,所以运算的单位元是1；任取xS，有x10=max(x,10)=10=max(10,x)=10 x,所以运算的零元是10；1616、设V11,2,3,1,其中xy表示取x和y之中较大的数。V25,6,6，其中x y表示取x和y之中较小的数。求出V1和V2的所有的子代数。指出哪些是平凡的子

25、代数，哪些是真子代数。解：（1）V1中运算的单位元是1，V1的所有的子代数是：1,2,3,1,1,1,1,2,1,1,3,1；V1的平凡的子代数是：1,2,3,1,1,1；V1的真子代数是：1,1,1,2,1,1,3,1；（2）V2中运算的单位元是6，V2的所有的子代数是：5,6,6，6,6；V2的平凡的子代数是：5,6,6，6,6；V2的真子代数是：6,6。习题十一及答案：习题十一及答案：P218-219P218-2191 1、图、图 11.1111.11 给出了给出了 6 6 个偏序集的哈斯图。判断其中哪些是格。如果不是格，说明理由个偏序集的哈斯图。判断其中哪些是格。如果不是格，说明理由-

26、优选.解：解：a a、c c、f f是格；因为任意两个元素构成的集合都有最小上界和最大下界；是格；因为任意两个元素构成的集合都有最小上界和最大下界；b b不是格，因为不是格，因为d,ed,e的最大下界不存在；的最大下界不存在；d d不是格，因为不是格，因为b,cb,c的最小上界不存在；的最小上界不存在；e e不是格，因为不是格，因为a,ba,b的最大下界不存在。的最大下界不存在。2 2、以下各集合低于整除关系都构成偏序集，判断哪些偏序集是格。、以下各集合低于整除关系都构成偏序集，判断哪些偏序集是格。1 1L=1L=1，2 2，3 3，4 4，55；2 2L=1L=1，2 2，3 3，6 6，1

27、212；解：画出哈斯图即可判断出：解：画出哈斯图即可判断出：1 1不是格，不是格，2 2是格。是格。4 4、设、设 L L 是格，求以下公式的对偶式：是格，求以下公式的对偶式：2 2a(bc)(ab)(ac)解：对偶式为：解：对偶式为：a(bc)(ab)(ac)，参见，参见 P208P208 页定义页定义 11.211.2。6 6、设、设 L L 为格，为格，a,b,cL，且a b c，证明ab bc。证明：a b,ab b,b c,bc b,ab bc9 9、针对图、针对图 11.1111.11 中的每个格，如果格中的元素存在补元，那么求出这些补元。中的每个格，如果格中的元素存在补元，那么求

28、出这些补元。解：解：a a图：图：a,da,d 互为补元，其中互为补元，其中 a a 为全下界，为全下界，d d 为全上界，为全上界，b b 和和 c c 都没有补元；都没有补元；c c图：图：a,fa,f 互为补元，其中互为补元，其中a a 为全下界，为全下界，f f 为全上界，为全上界，c c 和和 d d 的补元都是的补元都是 b b 和和 e e，b b 和和 e e 的补元都是的补元都是 c c 和和 d d；f f图：图：a,fa,f 互为补元，其中互为补元，其中 a a 为全下界，为全下界，f f 为全上界，为全上界，b b 和和 e e 互为补元，互为补元，c c 和和 d d

29、 都没有补元。都没有补元。1010、说明图、说明图 11.1111.11 中每个格是否为分配格、有补格和布尔格，并说明理由。中每个格是否为分配格、有补格和布尔格，并说明理由。解：解：a a图：是一条链，所以是分配格，图：是一条链，所以是分配格，b b 和和 c c 都没有补元，所以不是有补格，所以不是布尔格；都没有补元，所以不是有补格，所以不是布尔格；c c图：图：a,fa,f 互为补元，互为补元，c c 和和 d d 的补元都是的补元都是 b b 和和 e e，b b 和和 e e 的补元都是的补元都是 c c 和和 d d，所以任何元素皆有补元，是有，所以任何元素皆有补元，是有补格；补格；

30、c(bd)ca c,(cb)(cd)f d d c(bd)(cb)(cd)，所以所以对对运算不满足分配律，所以不是分配格，所以不是布尔格；运算不满足分配律，所以不是分配格，所以不是布尔格；f f图：经过分析知图图：经过分析知图f f对应的格只有对应的格只有 2 2 个五元子格：个五元子格：L1=a,c,d,e,f,L1=a,c,d,e,f,L2=a,b,c,d,fL2=a,b,c,d,f。画出。画出 L1L1 和和 L2L2 的的哈斯图可知哈斯图可知 L1L1 和和 L2L2 均不同构于钻石格和五角格，根据分配格的充分必要条件见均不同构于钻石格和五角格，根据分配格的充分必要条件见 P213P213 页的定理页的定理 11.511.5得图得图f f对应的格是分配格；对应的格是分配格；c c 和和 d d 都没有补元，所以不是有补格，所以不是布尔格。都没有补元，所以不是有补格，所以不是布尔格。-优选