（ 密 封 线 内 不 答 题 ） 教学中心： 专业层次： 姓名： 学号： 座号： 华南理工大学网络教育学院 教学中心： 专业层次： 姓名： 学号： 座号： 20202021学年度第一学期 离散数学 作业1、用推理规则证明 P Q，(Q R） R，（PS） S证 （1）(Q R） R 前提引入 （2）Q R （1）等价转换 （3） Q （2）化简 （4）P Q P （5）P （3）（4）拒取式 （6）（PS） P （7）P S （6）等价转换 （8）S （5）（7）析取三段论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 设R是集合A = 1, 6, 9,12,18,24,36上的整除关系。(1) 给出关系R；（2）画出关系R的哈斯图；（3）给出关系R的极大、极小元、最大、最小元。 解：(1) R=,(2) COVA= ,8求带权图G的最小生成树，并计算它的权值。 解：最小生成树如图所示权值为 4+7+8+9=289求带权图G的最小生成树，并计算它的权值。 解：C(T)=2+2+3+5+6+100=11810、求带权为1，2，3，4，5，6，7，8的最优二元树T，并给出T对应的二元前缀码集合。解：（B=000,001,01000,01001,0101,011,10,11,W(T)=102） 离散数学作业 第 2 页 （共 2 页）