离散数学作业

华南理工大学网络教育学院 2014–2015学年度第一学期 《 离散数学 》作业 （解答必须手写体上传，否则酌情扣分）

1．设命题公式为  Q （P  Q）  P。 （1）求此命题公式的真值表； 答：解 （1） 真值表如下 P Q Q PQ  Q （P  Q） 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 （2）求此命题公式的析取范式；

答：（ Q （P  Q）） P Q（P  Q） P  QP Q P  P

1 1 0 0

 Q （P  Q）  P

1 1 1 1

 P Q Q P P 1 P P  P 11 （主析取范式） （PQ）（PQ）（PQ）（PQ）（3）判断该命题公式的类型。 答：该命题公式重言式

2．用直接证法证明

前提：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）），

。

1欢迎下载

精品文档

 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））。

证 (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>} 作哈斯图如右：

极小元和最小元为1； 12极大元和最大元为12

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

。 2欢迎下载

精品文档

1312

答：C（T）=1+2+3+1=7

7．给定权为1，9，4，7，3；构造一颗最优二叉树。 答： 1 3 4 7 9 4 4 7 9

24 8 7 9

15 9 15 24

8W（T）=4×1+4×3+3×4+2×7+1×9=51 9

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

24

W(T)=4×(2×3)+3×4+2×6+9=53 或 2 3 4 6 9 5 4 6 9 9 15 24

2415942536924942563159W(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

W(T)=4×1+4×2+3×4+2×9+2×5+2×6=64

。 3欢迎下载

27167312491156精品文档

10、设字母a,b,c,d,e,f在通讯中出现的频率为：a:30%,b:25%,c:20%，试给出传输这6个字母的最佳前缀码？问传输1000个字d:10%,e:10%,f:5%。

符需要多少位二进制位？

解 先求传输100个字符所需要的位数。A:30,b:25,c:20,d:10,e:10,f:5 是依照出现频率得出的个数。构造最优二叉树如下： 5 10 10 20 25 30

100 15 10 20 25 30

5545 25 20 25 30

11250110 25 45 30 10001202530 45 55 5101000000001 100

需要二进制位数为 10W(T)=10×{4×(5+10)+3×10+2×(20+25+30)}=2400

。 4欢迎下载

精品文档

欢迎您的下载， 资料仅供参考！

致力为企业和个人提供合同协议，策划案计划书，学习资料等等

打造全网一站式需求

。 5欢迎下载