《离散数学作业题版》由会员分享，可在线阅读，更多相关《离散数学作业题版（7页珍藏版）》请在金锄头文库上搜索。
1、（ 密 封 线 内 不 答 题 ）教学中心： 专业层次： 姓名： 学号： 座号： 华南理工大学网络教育学院教学中心： 专业层次： 姓名： 学号： 座号： 20142015学年度第一学期 离散数学 作业（解答必须手写体上传，否则酌情扣分）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 1110 1 0 1011 1 0 1 0001 1 1 0 1001 （2）? Q
2、?（P ? Q）?P?(? Q ?(?P? Q) ? ? P?( Q? ? (?P? Q) ? ? P ? ( ?P? Q) ? (Q?P) ?1（析取范式）?(?P? Q) ? (?P? Q) ? (P? Q) ?（P? Q）（主析取范式）（3）该公式为重言式2用直接证法证明 前提：P ? Q，P ? R，Q ? S结论：S ? R解：（1）?S P (2)Q ?S P (3) ? Q (1)(2) (4)P? Q P (5)P (3)(4) (6) P ? R P (7)R (5)(6) (8) ?S? R （1）（7）即SVR得证3在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢
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 ?F (x) p (2) ?H (x) ES(1) (3) ?x (G (x) ?H (x) P (4)G (c) vH (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
4、)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
5、, 6, 12上的整除关系。(1) 给出关系R；（2） 给出COV A（3） 画出关系R的哈斯图；（4） 给出关系R的极大、极小元、最大、最小元。 解：R=,UIACOV A=,作哈斯图如右：极小元和最小元为：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=518给定权为2，6，3，9，4；构造一颗最优二叉树。解：2 3 4 6 9 5 4 6 9 9 15 24W(T)
6、=3*(2+3)+2*4+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 27 W(T)=4*1+4*2+3*4+2*9+2*5+2*6=6410、设字母在通讯中出现的频率为：，。试给出传输这6个字母的最佳前缀码？问传输1000个字符需要多少位二进制位？解 先求传输100个字符所需要的位数。，是依照出现频率得出的个数。构造最优二叉树如下：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
