华工离散数学作业题

2014–2015学年度第一学期 《 离散数学 》作业 1．设命题公式为 ? Q ?（P ? Q）? ? P。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （3）判断该命题公式的类型。

解 （1） 真值表如下 P Q ?Q P?Q ? Q ?（P ? Q） ? P ? Q ?（P ? Q）? ? P 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 （2） ? Q ?（P ? Q）? ? P??（? Q ?（?P? Q））?? P

）?? P??（?P? Q）?（ Q? ? P）?1（析取范式） ?（ Q? ?（?P? Q）

（主析取范式） ?（?P??Q）?（?P?Q）?（P??Q）?（P?Q）（3）该公式为重言式

2．用直接证法5．给定权为2，6，3，9，4；构造一最优二叉树。 解 2 3 4 6 9

5 4 6 9 9 6 9 15 9

24

颗

24159425369W?T??4?(2?3)?3?4?2?6?9?53 或 2 3 4 6 9 5 4 6 9 9 15 24

24942563159W?T??3?(2?3)?2?4?2?(6?9)?53

6．给定权为1，9，4，7，3；构造一颗最优二叉树。 24 解 1 3 4 7 9 4 4 7 9 8 7 9 15 9 24

W?T??4?1?4?3?3?4?2?7?1?9?51

411583497《 离散数学作业 》 第 1 页 （共 4 页）

3．给定权为2，6，5，9，4，1；构造一颗最优二叉树。 解 1 2 4 5 6 9 3 4 5 6 9 7 5 6 9 7 11 9 11 16 27

27119561673124W?T??4?1?4?2?3?4?2?9?2?5?2?6?64证明 前提：P ? Q，P ? R，Q ? S 结论：S ? R

证 (1)P ? Q P (2) ?P ? Q T(1)E

(3) Q ? S P (4) ?P ? S T(2,3)I (5) ? S ? P T(4)E

(6) P ?R P (7) ? S ?R T(5,6)I (8) S?R T(7)E

3．在一阶逻辑中构造下面推理的证明

每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。

令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。 解 前提：?x（F（x）?? G（x）），?x（G（x）?H（x）），

? x? H（x）。 结论：? x ?F（x）。

证 (1)? x ?H（x） P (2)?H（c） ES (1)

(3)?x（G（x）?H（x）） P (4) G（c）?H（c） US(3) (5) G（c） T(2，4)I

(6)?x（F（x）?? G（x）） P (7) F（c）?? G（c） US(6) (8) ? F（c） T(5,7)I

(9)（?x）? F（x） EG(8) 4．用直接证法证明：

前提：（?x）（C（x）→ W（x）∧R（x）），（?x）（C（x）∧Q（x）） 结论：（?x）（Q（x）∧R（x））。

《 离散数学作业 》 第 2 页 （共 4 页）

证 (1)（?x）（C（x）∧Q（x）） P

(2)C（c）∧Q（c） ES (1)

(3)（?x）（C（x）→ W（x）∧R（x）） P (4) C（c）→ W（c）∧R（c） US(3) (5) C（c） T(2)I

(6)W（c）∧R（c） T(4,5)I (7)R（c） T(6)I (8)Q（c） T(2)I

(9)Q（c）∧R（c） T(7,8)I (10) （?x）（Q（x）∧R（x）） EG(9) 5．设R是集合A = {1, 2, 3, 4, 6, 12}上的整除关系。

(1) 给出关系R； （2） 给出COV A

（3） 画出关系R的哈斯图；

（4） 给出关系R的极大、极小元、最大、最小元。

解 R={<1,2>,<1,3>,<1,4>,<1,6>，<1,12>,<2,4>,<2,6>，<2,12>，<3,6>，<3,12>，<4,12>,<6,12>}∪IA

COV A={<1,2>,<1,3>,<2,4>,<2,6>，<3,6>，<4,12>，<6,12>}

12作哈斯图如右：

极小元和最小元为1；

64极大元和最大元为12

236．求带权图G的最小生成树，并计算它的权值。

11312

解

C?T??1?2?3?1?7

7．给定权为1，9，4，7，3；构造一颗最优二叉树。 解 1 3 4 7 9 4 4 7 9 8 7 9 15 9 24

24411583497W?T??4?1?4?3?3?4?2?7?1?9?51

《 离散数学作业 》 第 3 页 （共 4 页）

8．给定权为2，6，3，9，4；构造一颗最优二叉树。 解 2 3 4 6 9 5 4 6 9 9 6 9 15 9

24

24159425369W?T??4?(2?3)?3?4?2?6?9?53 或 2 3 4 6 9 5 4 6 9 9 15 24

24942563159W?T??3?(2?3)?2?4?2?(6?9)?53

9、给定权为2，6，5，9，4，1；构造一颗最优二叉树。 解 1 2 4 5 6 9 3 4 5 6 9 7 5 6 9 7 11 9 11 16 27

27119561673124W?T??4?1?4?2?3?4?2?9?2?5?2?6?64

10、设字母a,b,c,d,e,f在通讯中出现的频率为：a:30%,b:25%,c:20%，

d:10%,e:10%,f:5%。试给出传输这6个字母的最佳前缀码？问传输1000个字

符需要多少位二进制位？

a:30,b:25,c:20,d:10,e:10,f:5是依照解 先求传输100个字符所需要的位数。

出现频率得出的个数。构造最优二叉树如下： 5 10 10 20 25 30 15 10 20 25 30 25 20 25 30 25 45 30 45 55 100

100452501105530110000000110001202551010需要二进制位数为10W?T??10??4??5?10??3?10?2??20?25?30???2400

《 离散数学作业 》 第 4 页 （共 4 页）