离散数学作业.doc

密 封 线 内 不 答 题 ）

教学中心： 专业层次： 姓名： 学号： 座号：

华南理工大学网络教育学院

教学中心： 专业层次： 姓名： 学号： 座号：

2014–2015学年度第一学期
《 离散数学 》作业
（解答必须手写体上传，否则酌情扣分）

1．设命题公式为 Ø Q Ù（P ® Q）® Ø P。　
（1）求此命题公式的真值表；
答：解 （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 QÚPÙØ QÚØ P
PÚ QÙØ QÚØ P P Ú1ÚØ P P ÚØ P Ú11
（Ø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）），
$ 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

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

答：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
W（T）=4×1+4×3+3×4+2×7+1×9=51
8．给定权为2，6，3，9，4；构造一颗最优二叉树。　
解 2 3 4 6 9
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
W(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
10、设字母在通讯中出现的频率为：，。试给出传输这6个字母的最佳前缀码？问传输1000个字符需要多少位二进制位？
解 先求传输100个字符所需要的位数。A:30,b:25,c:20,d:10,e:10,f:5
是依照出现频率得出的个数。构造最优二叉树如下：
5 10 10 20 25 30
15 10 20 25 30
25 20 25 30
25 45 30
45 55
100
需要二进制位数为 10W(T)=10×{4×(5+10)+3×10+2×(20+25+30)}=2400