离散数学作业.doc

（ 密 封 线 内 不 答 题 ） 教学中心： 专业层次： 姓名： 学号： 座号： 华南理工大学网络教育学院 教学中心： 专业层次： 姓名： 学号： 座号： 20142015学年度第一学期 离散数学 作业（解答必须手写体上传，否则酌情扣分）1设命题公式为 Q （P Q） P。 （1）求此命题公式的真值表；答：解 （1） 真值表如下PQQPQ Q （P Q） P Q （P Q） P0011111010101110100011101001（2）求此命题公式的析取范式；答：（ Q （P Q） P Q（P Q） P QP Q P P Q Q P P 1 P P P 11（PQ）（PQ）（PQ）（PQ）（主析取范式）（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) SR T(7)E3在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。令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=,，,，,IACOV A=,，作哈斯图如右：极小元和最小元为1；极大元和最大元为12 6求带权图G的最小生成树，并计算它的权值。 答：C（T）=1+2+3+1=77给定权为1，9，4，7，3；构造一颗最优二叉树。 答： 1 3 4 7 9 4 4 7 9 8 7 9 15 9 24W（T）=41+43+34+27+19=518给定权为2，6，3，9，4；构造一颗最优二叉树。解 2 3 4 6 9 5 4 6 9 9 6 9 15 924W(T)=4(23)+34+26+9=53或 2 3 4 6 9 5 4 6 9 9 15 24W(T)=3(2+3)+24+2(6+9)=539、给定权为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 27W(T)=41+42+34+29+25+26=6410、设字母在通讯中出现的频率为：，。试给出传输这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)=104(5+10)+310+2(20+25+30)=2400