离散数学习题答案（耿素云屈婉玲）

本文格式为Word版，下载可任意编辑——离散数学习题答案（耿素云屈婉玲）离散数学习题答案

习题二及答案：（P38）

5、求以下公式的主析取范式，并求成真赋值：（2）(?p?q)?(q?r)解：原式?(p?q)?q?r

?q?r?(?p?p)?q?r

?(?p?q?r)?(p?q?r)?m3?m7，此即公式的主析取范式，

所以成真赋值为011，111。

6、求以下公式的主合取范式，并求成假赋值：（2）(p?q)?(?p?r)

解：原式?(p??p?r)?(?p?q?r)所以成假赋值为100。

7、求以下公式的主析取范式，再用主析取范式求主合取范式：（1）(p?q)?r解：原式?

?(?p?q?r)?M4，此即公式的主合取范式，

p?q?(?r?r)?((?p?p)?(?q?q)?r)

?(p?q??r)?(p?q?r)?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r)?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q??r)?(p?q?r)

?m1?m3?m5?m6?m7，此即主析取范式。

主析取范式中没出现的微小项为m0，m2，m4，所以主合取范式中含有三个极大项M0，M2，M4，故原式的主合取范式?M0

9、用真值表法求下面公式的主析取范式：（1）(p?q)?(?p?r)解：公式的真值表如下：?M2?M4。

p00q00r01?p11p?q00?p?r01(p?q)?(?p?r)01001111

110011010101110000111111010000111111由真值表可以看出成真赋值的状况有7种，此7种成真赋值所对应的微小项的析取即为主析取范式，故主析取范式

?m1?m2?m3?m4?m5?m6?m7

习题三及答案：（P52-54）

11、填充下面推理证明中没有写出的推理规则。前提：?p?q,?q?r,r结论：s证明：

①p前提引入②④

?s,p

?p?q前提引入?q?r前提引入

③q①②析取三段论⑤r③④析取三段论⑥

15、在自然推理系统P中用附加前提法证明下面推理：（2）前提：(p?q)?(r?s),(s?t)?u结论：

r?s前提引入

⑦s⑤⑥假言推理

p?u

证明：用附加前提证明法。①p附加前提引入②③④⑥⑦

p?q①附加

(p?q)?(r?s)前提引入

r?s②③假言推理

⑤s④化简

s?t⑤附加

(s?t)?u前提引入

⑧u⑥⑦假言推理故推理正确。

16、在自然推理系统P中用归谬法证明下面推理：

p??q，?r?q，r??s结论：?p

（1）前提：

证明：用归谬法

①p结论的否定引入②③④⑤⑥

p??q前提引入?q①②假言推理?r?q前提引入

?r③④析取三段论r??s前提引入

⑦r⑥化简⑧r??r⑤⑦合取由于r??r?0，所以推理正确。

17、在自然推理系统P中构造下面推理的证明：

只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间。假使A在11点以前离开，看门人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。

解：设p：A到过受害者房间，q：A在11点以前离开，r：A是谋杀嫌犯，s：看门人看见过A。则前提：(p??q)?r，结论：r证明：①②③④⑤⑥⑦

习题五及答案：（P80-81）

15、在自然推理系统N?中，构造下面推理的证明：（3）前提：?x(F(x)?G(x))，??xG(x)结论：?xF(x)证明：①②③④

p，q?s，?s

q?s前提引入

?s前提引入

?q①②拒取式

p前提引入

p??q③④合取引入

(p??q)?r前提引入

r⑤⑥假言推理

??xG(x)前提引入?x?G(x)①置换?G(c)②UI规则?x(F(x)?G(x))前提引入

⑤⑥⑦

F(c)?G(c)④UI规则F(c)③⑤析取三段论

?xF(x)⑥EG规则

22、在自然推理系统N?中，构造下面推理的证明：

（2）凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。解：设F(x)：x为大学生，G(x)：想是勤奋的，c：王晓山则前提：?x(F(x)?G(x))，?G(c)结论：?F(c)证明：①②③④

?x(F(x)?G(x))前提引入F(c)?G(c)①UI规则?G(c)前提引入?F(c)②③拒取式

25、在自然推理系统N?中，构造下面推理的证明：

每个科学工都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工，并且是聪明的。所以，王大海在他的事业中将获得成功。（个体域为人类集合）

解：设F(x)：x是科学工，G(x)：x是刻苦钻研的，H(x)：x是聪明的，I(x)：x在他的事业中获得成功，c：王大海则前提：?x(F(x)?G(x))，?x(G(x)?H(x)?I(x))，F(c)?H(c)结论：I(c)证明：①②③④⑤⑥

F(c)?H(c)前提引入F(c)①化简

H(c)①化简?x(F(x)?G(x))前提引入F(c)?G(c)④UI规则G(c)②⑤假言推理

⑦⑧⑨⑩

G(c)?H(c)③⑥合取引入?x(G(x)?H(x)?I(x))前提引入G(c)?H(c)?I(c)⑧UI规则I(c)⑦⑨假言推理

习题七及答案：（P132-135）22、给定

A??1,2,3,4?，A上的关系R??1,3,1,4,2,3,2,4,3,4?，试

（1）画出R的关系图；（2）说明R的性质。解：（1）

●●

1●●234（2）R的关系图中每个顶点都没有自环，所以R是反自反的，不是自反的；

R的关系图中任意两个顶点假使有边的都是单向边，故R是反对称的，不是对称的；

R的关系图中没有发生顶点x到顶点y有边、顶点y到顶点z有边，但顶点x到顶点z没有边的状况，故R是

传递的。26设

A??1,2,3,4,5,6?，R为A上的关系，R的关系图如图7.13所示：

2（1）求R,R3的集合表达式；

??1,5,2,5,3,1,3,3,4,5（2）求r(R),s(R),t(R)的集合表达式。解：（1）由R的关系图可得R所以R可得R2?

?，

?R?R??3,1,3,3,3,5?，R3?R2?R??3,1,3,3,3,5n??3,1,3,3,3,5?,当n>=2；

??1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6（2）r(R)=R?IA?，

s(R)?R?R?1??1,5,5,1,2,5,5,2,3,1,1,3,3,3,4,5,5,4?

t(R)?R?R2?R3?...?R?R2??1,5,2,5,3,1,3,3,4,5,3,546、分别画出以下各偏序集（1）R??

A,R?的哈斯图，并找出A的极大元、微小元、最大元和最小元。

??a,d,a,c,a,b,a,e,b,e,c,e,d,e??IA

解：哈斯图如下：

ebcda

A的极大元为e、微小元为a；A的最大元为e、最小元为a。48、设

A,R和B,S为偏序集，在集合A?B上定义关系T如下：

?a1,b1,a2,b2?A?B,a1,b1Ta2,b2?a1Ra2?b1Sb2证明T为A?B上的偏序关系。证明：（1）自反性：

任取a1,b1?A?B，则：?R为偏序关系，具有自反性，?a1Ra1?S为偏序关系，具有自反性，?b1Sb1?a1Ra1?b1Sb1又a1,b1Ta2,b2?a1Ra2?b1Sb2，?a1,b1Ta1,b1，故T满足自反性（2）反对称性：

任取a1,b1,a2,b2?A?B，若a1,b1Ta2,b2且a2,b2Ta1,b1，则有：a1Ra2?b1Sb2a2Ra1?b2Sb1（1）（2）

?a1Ra2?a2Ra1，又R为偏序关系，具有反对称性，所以a1?a2?b1Sb2?b2Sb1，又S为偏序关系，具有反对称性，所以b1?b2?a1,b1?a2,b2，故T满足反对称性（3）传递性：

任取a1,b1,a2,b2，a3,b3?A?B，若a1,b1Ta2,b2且a2,b2Ta3,b3，则有：a1,b1Ta2,b2?a1Ra2?b1Sb2a2,b2Ta3,b3?a2Ra3?b2Sb3?a1Ra2?a2Ra3,又R为偏序关系，具有传递性，所以a1Ra3?b1Sb2?b2Sb3,又S为偏序关系，具有传递性，所以b1Sb3?a1Ra3?b1Sb3?a1,b1Ta3,b3，故T满足传递性。综合（1）（2）（3）知T满足自反性、反对称性和传递性，故T为A?B上的偏序关系。

习题九及答案：（P179-180）8、

S=Q?Q,Q为有理数集，为?S上的二元运算，?a,b,x,y?S有a,b?x,y?ax,ay+b（1）?运算在S上是否可交换、可结合？是否为幂等的？

（2）?运算是否有单位元、零元？假使有，请指出，并求出S中所有可逆元素的逆元。解：（1）

x,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+y??x,y?a,b??c,d??运算有结合律

?

任取a,b?s，则有：a,b?a,b?a2,ad?b?a,b??运算无幂等律（2）

令a,b*x,y?a,b对?a,b?s均成立则有：ax,ay+b?a,b对?a,b?s均成立??a?x?1??0?ax?a????对??a,b?成立ay?b?bay?0????x?1?0?x?1?必定有????y?0?y?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,y???ax?x??a?1?x?0???ay?b?y??a?1?y+b?0???由于?a?1?y+b?0不可能对?a,b?s均成立，故a,b*x,y?x,y不可能对?a,b?s均成立，故不存在零元；

设元素a,b的逆元为x,y，则令a,b*x,y?e?1，01?x???ax?1?a????（当a?0）ay?b?0b??y???a??当a?0时，a,b的逆元不存在；当a?0时，a,b的逆元是11

1b,?aa、

设S??1，2，...,10?，问下面的运算能否与S构成代数系统S，??假使能构成代数系统则说明?运算是否满足交换律、结合律，并求?运算的单位元和零元。（3）x?y=大于等于x和y的最小整数；解：（3）由*运算的定义可知：x?y=max(x,y)，

x,y?S,有x?y?S，故?运算在S上满足封闭性，所以?运算与非空集合S能构成代数系统；任取x,y?S,有x?y=max(x,y)=max(y,x)=y?x,所以?运算满足交换律；任取x,y,z?S,有(x?y)?z=max(max(x,y),z)=max(x,y,z)=max(x,max(y,z))=x?(y?z),所以?运算满足结合律；任取x?S，有x?1=max(x,1)=x=max(1,x)=1?x,所以?运算的单位元是1；任取x?S，有x?10=max(x,10)=10=max(10,x)=10?x,所以?运算的零元是10；16、

设V1??1,2,3?,?,1,其中x?y表示取x和y之中较大的数。V2??5,6?,?,6，其中x?y表示取x和y之中较小的数。求出V1和V2的所有的子代数。指出哪些是平凡的子代数，哪些是真子代数。

解：（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的所有的子代数是：?5,6?,?,6，?6?,?,6；V2的平凡的子代数是：?5,6?,?,6，?6?,?,6；V2的真子代数是：?6?,?,6。

习题十一及答案：（P218-219）

1、图11.11给出了6个偏序集的哈斯图。判断其中哪些是格。假使不是格，说明理由解：（a）、（c）、（f）是格；由于任意两个元素构成的集合都有最小上界和最大下界；（b）不是格，由于{d,e}的最大下界不存在；（d）不是格，由于{b,c}的最小上界不存在；（e）不是格，由于{a,b}的最大下界不存在。

2、以下各集合低于整除关系都构成偏序集，判断哪些偏序集是格。（1）L={1，2，3，4，5}；（2）L={1，2，3，6，1