（ 密 封 线 内 不 答 题 ） 教学中心： 专业层次： 姓名： 学号： 座号： 华南理工大学网络教育学院 教学中心： 专业层次： 姓名： 学号： 座号： 20202021学年度第一学期 离散数学 作业1、用推理规则证明 （P Q），Q R， RP证 （1）r 前提引入 （2）（Q R） 前提引入 （3） QVR （2）等价置换 （4） Q （1）（3）析取三段式 （5）P VQ 前提引入 （6）P （4）（5）析取三段式2、用推理规则证明 P Q，R S （P R）（Q S）证 （1）P R 附加前提引入 （2）R （1）化简 （3）P （1）化简 （4）P Q P （5）Q （3）（4）假言推理 （6）R S P （7）S （2）（6）假言推理 （8）Q S （5）（7）合取3求公式的主析取范式与主合取范式，并写出相应的成真赋值与成假赋值。解 主析取范式，成真赋值10，11主合取范式成假赋值是00,014在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。5用推理规则证明 x（P（x） Q（x），x P（x）x Q（x）证 （1）x B（x） 前提引入 （2）B（c） （1） US （3）x（A（x） B（x） 前提引入 （4）A（c） B（c） （3） US （5）A（c） （2）（4）I （6）$x A（x） （5）EG6设R是集合A = 1, 2, 3, 4, 6, 8, 12, 24上的整除关系。 （1） 给出关系R；（2） 画出关系R的哈斯图；（3）指出关系R的最大、最小元，极大、极小元。 解：（1）R=, ,(2)哈斯图如下所示（3）最大元24 最小元1 极大元12 极小元17求带权图G的最小生成树，并计算它的权值。 解：C（T）=1+2+3+5+7=18 8. 求带权图G的最小生成树，并计算它的权值。 解：C(T)=2+2+3+5+6+100=1189、 求带权为2，3，5，7，8的最优二元树T，并给出T对应的二元前缀码集合。解：（B=00，010，011，10，11），W（T）=2532+33+27+28=55）10、 求带权为1，2，3，4，5，6，7，8的最优二元树T，并给出T对应的二元前缀码集合。解：（B=000,001,01000,01001,0101,011,10,11,W(T)=102） 离散数学作业 第 2 页 （共 2 页）