内容发布更新时间 : 2024/6/24 20:11:48星期一 下面是文章的全部内容请认真阅读。

华南理工大学网络教育学院 2014–2015学年度第一学期 《 离散数学 》作业 （解答必须手写体上传，否则酌情扣分）

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 1 0 1 0 1 1 0 1 0 1 1 0 1

0 0 0

1 1 0 0

1 1 1 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）（主析取范式） （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

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

(5)P (3)(4) (6) P ? R P

(7)R (5)(6) (8) ?S? R （1）（7） 即SVR得证

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

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

(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={<1,2>,<1,3>,<1,4>,<1,6>,<1,12>,<2,4>,<2,6>,<2,12>,<3,6>,<3,12>, <4,12>,<6,12>}UIA

COV A={<1,2>,<1,3>,<2,4>,<2,6>,<3,6>,<4,12>,<6,12>} 作哈斯图如右： 极小元和最小元为：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

《 离散数学作业 》 第 3 页 （共 5 页）