离散数学习题答案

习题一及答案：（P14-15） 14、将下列命题符号化：

（5）李辛与李末是兄弟

解：设p：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语

解：设p：王强学过法语；q：刘威学过法语；则命题符号化的结果是（9）只有天下大雨，他才乘班车上班

解：设p：天下大雨；q：他乘班车上班；则命题符号化的结果是qp （11）下雪路滑，他迟到了

解：设p：下雪；q：路滑；r：他迟到了；则命题符号化的结果是(pq)r

15、设p：2+3=5.

q：大熊猫产在中国. r：太阳从西方升起. 求下列复合命题的真值：

（4）(pqr)((pq)r) 解：p=1，q=1，r=0，

pq

(pqr)(110)1，

((pq)r)((11)0)(00)1 (pqr)((pq)r)111

19、用真值表判断下列公式的类型： （2）(pp)q

解：列出公式的真值表，如下所示：

p q p q (pp) (pp)q 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。 20、求下列公式的成真赋值：

（4）(pq)q

解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：

(pq)1p0 q0q0所以公式的成真赋值有：01，10，11。

习题二及答案：（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)(pqr)M4，此即公式的主合取范式， 所以成假赋值为100。

7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）(pq)r

解：原式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M2M4。

9、用真值表法求下面公式的主析取范式：

（1）(pq)(pr) 解：公式的真值表如下： p q r p pq pr (pq)(pr) 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式m1m2m3m4m5m6m7

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

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

① p 前提引入 ② pq 前提引入 ③ q ①②析取三段论 ④ qr 前提引入

⑤ r ③④析取三段论 ⑥ rs 前提引入

⑦ s ⑤⑥假言推理

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

证明：用附加前提证明法。

① p 附加前提引入

② pq ①附加 ③ (pq)(rs) 前提引入 ④ rs ②③假言推理 ⑤ s ④化简 ⑥ st ⑤附加 ⑦ (st)u 前提引入

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

16、在自然推理系统P中用归谬法证明下面推理： （1）前提：pq，rq，rs 结论：p

证明：用归谬法

① 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，p，qs，s 结论：r 证明：

① qs 前提引入 ② s 前提引入 ③ q ①②拒取式 ④ p 前提引入

⑤ pq ③④合取引入 ⑥ (pq)r 前提引入 ⑦ r ⑤⑥假言推理

习题四及答案：（P65-67）

5、在一阶逻辑中将下列命题符号化： （2）有的火车比有的汽车快。

解：设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；则命题符号化的结果是：

xy(F(x)G(y)H(x,y))

（3）不存在比所有火车都快的汽车。 解：方法一：

设F(x)：x是汽车，G(y)：y是火车，H(x,y)：x比y快；则命题符号化的结果是：

x(F(x)y(G(y)H(x,y)))或x(F(x)y(G(y)H(x,y)))

方法二：

设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；则命题符号化的结果是：

x(G(x)y(F(y)H(x,y)))或xy(G(x)(F(y)H(x,y)))

9、给定解释I如下：

(a) 个体域为实数集合R。 (b) 特定元素a0。

(c) 函数

f(x,y)xy,x,yR。

(d) 谓词F(x,y):xy,G(x,y):xy,x,yR。

给出以下公式在I下的解释，并指出它们的真值：

（2）xy(F(f(x,y),a)G(x,y))

y0xy)，含义是：对于任意的实数x，y，若x-y=0则x解：解释是：xy(x该公式在I解释下的真值为假。

14、证明下面公式既不是永真式也不是矛盾式： （1）x(F(x)y(G(y)H(x,y)))

解：取解释I如下：个体域为全总个体域，

F(x)：x是兔子，G(y)：y是乌龟，H(x,y)：x比y跑得快，则该公式在解释I下真值是1；

取解释I如下：H(x,y)：x比y跑得慢，其它同上，则该公式在解释I下真值是0；

''故公式（1）既不是永真式也不是矛盾式。

此题答案不唯一，只要证明公式既不是永真式也不是矛盾式的每个解释合理即可。

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

5、给定解释I如下： (a) 个体域D={3,4}

(b)

f(x):f(3)4,f(4)3

(c) F(x,y):F(3,3)F(4,4)0,F(3,4)F(4,3)1 试求下列公式在I下的真值： (1)

xyF(x,y)

xyF(x,y)x(F(x,3)F(x,4))

解：方法一：先消去存在量词

(F(3,3)F(3,4))(F(4,3)F(4,4))

(01)(10)

1

15、在自然推理系统N中，构造下面推理的证明： （3）前提：x(F(x)G(x))，xG(x) 结论：xF(x) 证明：

① 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)：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) ⑦⑨假言推理

习题六及答案（P99-100）

28、化简下述集合公式：

（3）((AB)C)((AB)C)((AB)C)((AB)C) 解：((AB)C)((AB)C)((AB)C)((AB)C)

(AB)(AB)

A

30、设A,B,C代表任意集合，试判断下面命题的真假。如果为真，给出证明；如果为假，给出反例。 （6）(AB)AB

(AB)ABA，如果BA，则

解：该命题为假，

BAB，否则

BAB，故BAB为假。

举反例如下：（8）

A{1,2},B{1,3},则(AB)A{3}B。

ABACBC

ABAC一定成立，

解：该命题为假，举反例如下：如果B，C都是A的子集，则

1,2}，B但BC不一定成立，例如：A{但BC。

{1}, C{2}，则ABACA，

33、证明集合恒等式： （1）A(BA)BA 证明：A(BA)

(AB)(AA)

(AB)

ABBA习题七及答案：（P132-135）

26 设A1,2,3,4,5,6，R为A上的关系，R的关系图如图7.13所示： （1）求R2,R3的集合表达式； （2）求r(R), s(R), t(R)的集合表达式。

解：（1）由R的关系图可得R1,5,2,5,3,1,3,3,4,5 所以R2RR3,1,3,3,3,5，R3R2R3,1,3,3,3,5， 可得Rn3,1,3,3,3,5,当n>=2； （2）r(R)=RIA1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6， R11,5,5,1,2,5,5,2,3,1,1,3,3,3,4,5,5,4 R2R3...RR21,5,2,5,3,1,3,3,3,5,4,5

s(R)Rt(R)R41、设A={1，2，3，4}，R为AA上的二元关系，a,b,c,dAA，

a,bRc,dabcd

（1）证明R为等价关系； （2）求R导出的划分。

（1）只需证明R具有自反性、对称性和传递性即可，证明过程如下：

（a）任取a,bAA，有abab，a,bRa,b，所以R具有自反性； （b）任取a,b,c,dAA，若a,bRc,d，

则有abcd，cdab，c,dRa,b，所以R具有对称性；

（c）任取a,b,c,d,e,fAA，若a,bRc,d且c,dRe,f， 则有abcd且cdef，ab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,1]R{1,1},

[1,2]R[2,1]R{1,2,2,1},

[1,3]R[2,2]R[3,1]R{1,3,2,2,3,1},

[1,4]R[2,3]R[3,2]R[4,1]R{1,4,2,3,3,2,4,1}, [2,4]R[3,3]R[4,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}}

46、分别画出下列各偏序集A,R的哈斯图，并找出A的极大元、极小元、最大元和最小元。 （1）Ra,d,a,c,a,b,a,e,b,e,c,e,d,e解：哈斯图如下：

e IA

b c d a f

A的极大元为e、f，极小元为a、f； A的最大元和最小元都不存在。

*22、给定A1,2,3,4，A上的关系R1,3,1,4,2,3,2,4,3,4，试

（1）画出R的关系图； （2）说明R的性质。 解：（1） 1 2 ● ● ● ● 3 4 （2）R的关系图中每个顶点都没有自环，所以R是反自反的，不是自反的；

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

称的；

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

到顶点z没有边的情况，故R是传递的。

*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为偏序关系，具有自反性，a1Ra1S为偏序关系，具有自反性，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,ab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a1x0axx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0yba当a0时，a,b的逆元不存在；当a0时，a,b的逆元是1b,aa

11、

设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， 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-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，12}； 解：画出哈斯图即可判断出：（1）不是格，（2）是格。 4、设L是格，求以下公式的对偶式： （2）a(bc)(ab)(ac)

解：对偶式为：a(bc)(ab)(ac)，参见P208页定义11.2。 6、设L为格，a,b,cL，且abc，证明abbc。 证明：

ab,abb,

bc,bcb,

abbc

9、针对图11.11中的每个格，如果格中的元素存在补元，则求出这些补元。 解：

（a）图：a,d互为补元，其中a为全下界，d为全上界，b和c都没有补元；

（c）图：a,f互为补元，其中a为全下界，f为全上界，c和d的补元都是b和e，b和e的补元都是c和d；

（f）图：a,f互为补元，其中a为全下界，f为全上界，b和e互为补元，c和d都没有补元。 10、说明图11.11中每个格是否为分配格、有补格和布尔格，并说明理由。 解：

（a）图：是一条链，所以是分配格，b和c都没有补元，所以不是有补格，所以不是布尔格；

（c）图：a,f互为补元，c和d的补元都是b和e，b和e的补元都是c和d，所以任何元素皆有补元，是有补格；

c(bd)cac, (cb)(cd)fddc(bd)(cb)(cd)，所以

对运算不满足分配律，所以不是分配格，所以不是布尔格；

（f）图：经过分析知图（f）对应的格只有2个五元子格：L1={a,c,d,e,f}, L2={a,b,c,d,f}。画出L1和L2的哈斯图可知L1和L2均不同构于钻石格和五角格，根据分配格的充分必要条件（见P213页的定理11.5）得图（f）对应的格是分配格；c和d都没有补元，所以不是有补格，所以不是布尔格。