发布时间 : 星期三 文章华南理工大学网络教育学院-2019–2020学年度第一学期《离散数学》作业更新完毕开始阅读20586b20ba4ae45c3b3567ec102de2bd9605dece
华南理工大学网络教育学院 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