离散数学习题的答案解析

离散数学习题答案

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

（5）李辛与李末是兄弟

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

解：设p ：王强学过法语；q ：刘威学过法语；则命题符号化的结果是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，

()(110)1p q r ∧∧??∧∧??，

(())((11)0)(00)1p q r ?∨?→??∨?→?→?

*

()(())111p q r p q r ∴∧∧???∨?→???

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

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

20、求下列公式的成真赋值： （4）()p q q ?∨→

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

()10p q q ?∨???

???0

0p q ?????

所以公式的成真赋值有：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 ??∧∧∨∧∧37m m ?∨，此即公式的主析取范式， 所以成真赋值为011，111。

*6、求下列公式的主合取范式，并求成假赋值： |

（2）()()p q p r ∧∨?∨

解：原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?，此即公式的主合取范式， 所以成假赋值为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 ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ?∨∨∨∨，此即主析取范式。

)

主析取范式中没出现的极小项为0m ，2m ，4m ，所以主合取范式中含有三个极大项0M ，2M ，

4M ，故原式的主合取范式024M M M ?∧∧。

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

、

由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式1234567m m m m m m m ?∨∨∨∨∨∨

习题三及答案：（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 s

→?，r q

结论：p

?

证明：用归谬法

①p 结论的否定引入

②p q

→?前提引入

③q

?①②假言推理

④r q

?∨前提引入

⑤r

?③④析取三段论

⑥r s

∧?前提引入

⑦r ⑥化简

-

⑧r r ∧? ⑤⑦合取

由于0r r ∧??，所以推理正确。

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) 特定元素0a

-

=。

(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 ??→

解：解释是：(0)x y x y x y ??-

=→<，含义是：对于任意的实数x ，y ，若x-y=0则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)

():(3)4,(4)3

f x f f -

--

==

(c) (,):(3,3)(4,4)0,(3,4)(4,3)1F x y F F F F --

-

--

==== 试求下列公式在I 下的真值： (1)

(,)x yF x y ??

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

(,)((,3)(,4))x yF x y x F x F x ????∨

((3,3)(3,4))((4,3)(4,4))F F F F ?∨∧∨

(01)(10)?∨∧∨

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 -=为假。

举反例如下：{1,2},{1,3},A B ==则(){3}A B A B ?-=≠。

（8）

A B A C B C ?=??=

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

?一定成立，

但B C =不一定成立，例如：{

1,2}A =，{1}B =, {2}C =，则A B A C A ?=?=，

但B C ≠。

33、证明集合恒等式：

！

（1）()A B A B A ??=?

证明：()A B A ??

()()A B A A =???

()A B =???

A B =?B A

=?

习题七及答案：（P132-135）

26 设{}1,2,3,4,5,6A =，R 为A 上的关系，R 的关系图如图所示： （1）求23,R R 的集合表达式； （2）求r(R), s(R), t(R)的集合表达式。

解：（1）由R 的关系图可得{}1,5,2,5,3,1,,4,5R = 所以{}23,1,3,3,R R R =?=，{323,1,3,3,3,5R R R =?=，

*

可得{}3,1,3,3,3,5,n>=2n R =当； （2）{}A r(R)=R

I 1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6=， {}1()R 1,5,5,1,2,5,,3,1,1,3,3,3,4,5,5,4s R R -== {}2

3

2()R

R ...R

1,5,2,5,3,1,3,3,3,5,4,5t R R R ===

41、设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 ?的结果：

{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 ?=<><><><><><><><><><><><><><><><>

再分别求集合A A ?各元素的等价类，结果如下：

[1,1]{1,1},R <>=<>

[1,2][2,1]{1,2,2,1},R R <>=<>=<><>

[1,3][2,2][3,1]{1,3,2,2,3,1},R R R <>=<>=<>=<><><>

·

[1,4][2,3][3,2][4,1]{1,4,2,3,3,2,4,1},R R R R <>=<>=<>=<>=<><><><> [2,4][3,3][4,2]{2,4,3,3,4,2},R R R <>=<>=<>=<><><> [3,4][4,3]{3,4,4,3},R R <>=<>=<><> [4,4]{4,4}R <>=<>。

等价关系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）{A ,,,,,,,,,,,,,I R a d a c a b a e b e c e d e ≤=

解：哈斯图如下：

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

*22、给定{}1,2,3,4A =，A 上的关系{}1,3,1,4,2,3,2,4,3,4R =，试

#

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

● ●

（2）R 是反自反的，不是自反的；

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

称的；

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

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

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

112211221212

,,,A B,,,a b a b a b T a b a Ra b Sb ?∈??∧

证明T 为A B ?上的偏序关系。 证明：（1）自反性： <

1111111111

112212121111,A B R R S b Sb R b Sb ,,,,T a b a a a a a b T a b a Ra b Sb a b T a b ∈?∴∴∴∧?∧∴任取，则：

为偏序关系，具有自反性，为偏序关系，具有自反性，又，，故具有自反性

（2）反对称性：

11221122221112122121

1221121221121122,,,A B ,,,,R S b b ,,T a b a b a b T a b a b T a b a Ra b Sb a Ra b Sb a Ra a Ra a a b Sb b Sb a b a b ∈?∧∧∴∧=∴∧=∴=任取，若且，则有：（1）（2）

，又为偏序关系，具有反对称性，所以，又为偏序关系，具有反对称性，所以，故具有反对称性

（3）传递性：

112233112222331122121222332323

12231312231313131133,,,,A B ,,,,,,,,,R ,S b Sb b Sb ,,T a b a b a b a b T a b a b T a b a b T a b a Ra b Sb a b T a b a Ra b Sb a Ra a Ra a Ra b Sb b Sb a Ra a b T a b ∈??∧?∧∴∧∴∧∴∧?任取，，若且又为偏序关系，具有传递性，所以又为偏序关系，具有传递性，所以，故具有传递性。

综合（1）（2）（3）知T具有自反性、反对称性和传递性，故T为A B

上的偏序关系。@

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

8、

S=Q Q,Q S a,b ,x,y a,b x,y ax,ay+b

S ?*?∈*=为有理数集，为上的二元运算，有

（1）S *运算在上是否可交换、可结合？是否为幂等的？

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

,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 ,a,b c,d ,*ac,ad+b

xac,xad+xb+y acx,adx+bx+y ,a,b c,d x y x y x y x y **=*=**====**∴*而运算有结合律

￥

2a,b s a,b a,b a ,a,b ab b ∈*=+≠∴*任取，则有：运算无幂等律

（2）

()()a,b *,a,b a,b s ax,ay+b a,b a,b s ax a a x 10a,b ay b b ay 0x 10x 1

y 0y 0

101010

x y =?∈=?∈?=?-=?∴????+==???-==??∴???

==??∴**∴*令对均成立则有：对均成立

对成立必定有运算的右单位元为，，可验证，也为运算的左单位元，运算的单位元为，

()()()a,b *,,,a,b s a,b *,,ax,ay+b ,a 1x 0ax x a 1y+b 0ay b y a 1y+b 0a,b s a,b *,,a,b s x y x y x y x y x y x y

x y x y =?∈=?=?-=?=??

???

-=+=????

-=?∈=?∈令，若存在使得对上述等式均成立，则存在零元，否则不存在零元。由由于不可能对均成立，

故不可能对均成立，故不存在零元；

a,b ,a,b *,e 101x ax 1a

a ay

b 0b y a a 0a,b 1b a a,b ,a a

x y x y ==?

=?=????≠??+=??=-

??

∴=≠-设元素的逆元为，则令，（当0）

当时，的逆元不存在；

当0时，的逆元是

11、

{}S 12S S ?

=***设，，...,10，问下面的运算能否与构成代数系统，如果能构成代数系统则说明运算是否满足交换律、结合律，并求运算的单位元和零元。 （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)=1x,∈***任取，有所以运算的单位元是1； x S x 10=max(x,10)=10=max(10,x)=10x,∈***任取，有所以运算的零元是10；

16、

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

{}{}{}}}}

}}{}1111V 1 V 1,2,3,,1,1,,1,1,2,,1,1,3,,1 V 1,2,3,,1,1,,1 V 1,,1,1,2,,1,1,3,,1??????????解：（1）中运算的单位元是，

的所有的子代数是：；

的平凡的子代数是：；的真子代数是：；

}{}{}{}{}2222V 6V 5,6,,66,,6 V 5,6,,66,,6 V 6,,6******（2）中运算的单位元是，

的所有的子代数是：，；

的平凡的子代数是：，；的真子代数是：。

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

1、图给出了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页定义。 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、针对图中的每个格，如果格中的元素存在补元，则求出这些补元。 解：

（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、说明图中每个格是否为分配格、有补格和布尔格，并说明理由。 解：

（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页的定理）得图（f ）对应的格是分配格；c 和d 都没有补元，所以不是有补格，所以不是布尔格。