华南理工大学网络教育学院-2019–2020学年度第一学期《离散数学》作业

华南理工大学网络教育学院 2019–2020学年度第一学期 《 离散数学 》作业

1、 用推理规则证明 Q，?P ? R， P ? S，? S? Q ?R 证 （1）?Q ?R P （2）? R P （3）? Q （1）（2）析取三段论 （4）?（P? ?Q） P

（5）?P ? Q （4）等价转换 （6）? P （3）（5）析取三段论

2、用推理规则证明 ?（P? ?Q），?Q ?R，? R??P 证 （1）?Q ?R P （2）? R P （3）? Q （1）（2）析取三段论 （4）?（P? ?Q） P

（5）?P ? Q （4）等价转换 （6）? P （3）（5）析取三段论

3．设命题公式为 ? Q ?（P ? Q）? ? P。 （1）求此命题公式的真值表； 解真值表如下

P Q ?Q P?Q 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1

（2）求此命题公式的析取范式；

? Q ?（P ? Q）? ? P??（? Q ?（?P? Q））?? P ?（ Q? ?（?P? Q））?? P??（?P? Q）?（ Q? ? P）?1（析取范式） ?（?P??Q）?（?P?Q）?（P??Q）?（P?Q）（主析取范式）

《 离散数学作业 》 第 1 页 （共 6 页）

? Q ?（P ? Q） 1 0 0 0 ? P 1 1 0 0 ? Q ?（P ? Q）? ? P 1 1 1 1

（3）判断该命题公式的类型。 答：该公式为重言式

4．在一阶逻辑中构造下面推理的证明

每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。

令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)

5．用直接证法证明：

前提：（?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

《 离散数学作业 》 第 2 页 （共 6 页）

(8)Q（c） T(2)I

(9)Q（c）∧R（c） T(7,8)I (10) （?x）（Q（x）∧R（x）） EG(9)

6．设R是集合A = {1, 2, 3, 4, 5, 6, 7, 8, 9}上的整除关系。

（1） 给出关系R；（2）画出关系R的哈斯图；

答：

解 R={<1,2>,<1,3>,<1,4>,<1,5>,<1,6>，<1,7>,<1,8>,<1,9>,<2,4>,<2,6>，<2,8>，<3,6>，<3,9>，<4,8>}∪IA

COV A={<1,2>,<1,3>,<1,5>,<1,7>,<2,4>,<2,6>，<3,6>，<3,9>，<4,8>} 作哈斯图如右：

（2） 指出关系R的最大、最小元，极大、极小元。 答：

极小元和最小元为1；

极大元为5,6,7,8,9, 无最大元

7．设R是集合A = {1, 2, 3, 4, 6, 12}上的整除关系。

(1) 给出关系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

（2） 给出COV A 《 离散数学作业 》 第 3 页 （共 6 页）

869423517

答：COV A={<1,2>,<1,3>,<2,4>,<2,6>，<3,6>，<4,12>，<6,12>}

（3） 画出关系R的哈斯图； 答：作哈斯图如右：

（4） 给出关系R的极大、极小元、最大、最小元。 答：极小元和最小元为1； 极大元和最大元为12

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

1242163

答：

解 C?T??1?2?3??1 7

1312

9．给定权为1，9，4，7，3；构造一颗最优二叉树。 答：

解 1 3 4 7 9 4 4 7 9 8 7 9 15 9 24

24158349741《 离散数学作业 》 第 4 页 （共 6 页）