四、判断说明题（判断下列各题，并说明理由．） 1．命题公式?(Q?P)?P为永假式．
2．命题公式┐P∧（P→┐Q）∨P为永真式．
3．下面的推理是否正确，试予以说明．
(1) （?x）F（x）→G（x） 前提引入
(2) F（y）→G（y） US（1）．
五．计算题
1．（1）求命题公式?(P?Q)?(P??Q)的主析取范式、主合取范式； （2）求该命题公式的成假赋值．
2．求公式(P?Q)?R的析取、合取、主析取、主合取范式． 3．求P?Q?R的析取范式，合取范式、主析取范式，主合取范式． 4．试求出（P∨Q）→R的析取范式，合取范式，主合取范式． 5．求（P∨Q）→（R∨Q）的合取范式．
6．设谓词公式?x(P(x,y)??zQ(y,x,z))??yR(y,z)?F(y)．试 （1）写出量词的辖域；
（2）指出该公式的自由变元和约束变元．
六、证明题
1．试证明命题公式 (P?(Q??R))??P?Q与?（P??Q）等价．
2．试证明（?x）（P（x）∧R（x））? （?x）P（x）∧（?x）R（x）．
参考解答
一、单项选择题
1．B 2．D 3．C 4．B 5．A 6．D 7．D 8．C 9．B
二、填空题
1．T （或1）
2． (P?Q)?R
3． (P?Q?R)? (P?Q??R)
4． (?x)(F(x)? G(x))
5． (A(1)? A(2))? (B(1)? B(2))
6．A (a) ∧A (b)∧A（c）
11
7．A (a)∧A (b))∧(B（a）∨B（b）
8．A(1)?A(2) 9．x
10．R(x，y )中的y
三、公式翻译题
1．解：设P：今天是天晴；
则 ? P．
2．解：设P：今天下雨，
则 ? P．
3．解：设 P：今天有人来， 则 ? P．
4．解：设P：他去学校，
则 ? P．
5．解：设P：他接受了这个任务，Q：他完成好了这个任务， 则 P?? Q．
6．解：设P：小王去旅游，Q：小李去旅游，
则 P?Q．
7．解：设 P：他去旅游，Q：他有时间，
则 P ?Q．
8．解：设 P：我去书店，Q：天不下雨，
则 P ?Q．
9．解：设P：所有人今天都去参加活动，Q：明天的会议取消，
则 P? Q． 10．解：设P：你去，Q：他去，
则 P??Q．
11．解：设P(x)：x是人，Q(x)：x去工作，
则 (?x)(P(x) ?┐Q(x))．
12．解：设P(x)：x是人，Q(x)：x去上课，
则 (?x)(P(x) ?Q(x))．
13．解：设P(x)：x是人，Q(x)：x努力工作． 则 (?x)(P(x)? Q(x))．
14．解：设P(x)：x是人，Q(x)：x去工作， 则 (?x)(P(x)?Q(x))．
15．解：设P(x)：x是人，Q(x)：x学习努力，
12
则 （?x）(P(x)?Q(x))．
四、判断说明题（判断下列各题，并说明理由．） 1．解：正确 因为，由真值表
P Q Q?P ?( Q?P) 0 0 1 0 0 1 0 1 1 0 1 0 1 1 1 0 可知，该命题公式为永假式． 2．解：正确．
?( Q?P)? P 0 0 0 0 ┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式， 如果P的值为真，则┐P∧（P→┐Q）∨P为真，
如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真， 也即┐P∧（P→┐Q）∨P为真，
所以┐P∧（P→┐Q）∨P是永真式． 另种说明：
┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式， 只要其中一项为真，则整个公式为真．
可以看到，不论P的值为真或为假，┐P∧（P→┐Q）与P总有一个为真， 所以┐P∧（P→┐Q）∨P是永真式．
或用等价演算┐P∧（P→┐Q）∨P?T 3．解：错误． （2）应为F（y）→G（x），换名时，约束变元与自由变元不能混淆．
五．计算题
1．解：（1）?(P?Q)?(P??Q)??(?P?Q)?(?P??Q)
?(P??Q)?(?P??Q)?(P??Q??P)?(P??Q??Q)
?(P??Q) (主析取范式) ?(P?(Q??Q))?((P??P)??Q)
?(P?Q)?(P??Q)?(P??Q)?(?P??Q) ?(P?Q)?(P??Q)?(?P??Q) (主合取范式) （2）因为命题公式的成真赋值是(1, 0)， 所以它的成假赋值是(0, 0)，(0, 1)，(1, 1)． 2．解：(P?Q)?R??(P?Q)?R ?(?P??Q)?R
13
??P??Q?R （析取、合取、主合取范式） ?(┐P∧(┐Q∨Q)∧(┐R∨R))∨((┐P∨P)∧┐Q∧(┐R∨R))∨((┐P∨P) ∧(┐Q∨Q)∧R)
?(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R)∨(┐P∧Q∧┐R)∨(┐P∧Q∧R)
∨(P∧┐Q∧┐R)∨(P∧┐Q∧R)∨(P∧Q∧R) （主析取范式） 3．解：P→（R∨Q）
?┐P∨(R∨Q)
? ┐P∨Q∨R （析取、合取、主合取范式）
?(┐P∧┐Q∧┐R)∨(┐P∧┐Q∧R) ∨(┐P∧Q∧R) ∨
(┐P∧Q∧┐R)∨(P∧┐Q∧R) ∨(P∧Q∧┐R) ∨(P∧Q∧R) （主析取范式）
4．解：（P∨Q）→R?┐(P∨Q)∨R? (┐P∧┐Q)∨R（析取范式） ? (┐P∨R)∧ (┐Q∨R)（合取范式）
? ((┐P∨R)∨(Q∧┐Q))∧ ((┐Q∨R)∨(P∧┐P)) ? (┐P∨R∨Q)∧(┐P∨R∨┐Q)∧ (┐Q∨R∨P)
∧(┐Q∨R∨┐P)
? (┐P∨Q∨R)∧(┐P∨┐Q∨R)∧ (P∨┐Q∨R) （主合取范式） 5．解：（P∨Q）→（R∨Q）
??（P∨Q）∨（R∨Q） ?(?P∧?Q)∨（R∨Q）
?(?P∨R∨Q)∧(?Q∨R∨Q)
?(?P∨R∨Q) 合取范式
6．解：（1）?x量词的辖域为(P(x,y)??zQ(y,x,z))，
?z量词的辖域为Q(y,x,z), ?y量词的辖域为R(y,z)．
（2）自由变元为(P(x,y)??zQ(y,x,z))与F(y)中的y，以及R(y,z)中的z
约束变元为(P(x,y)??zQ(y,x,z))中的x与Q(y,x,z)中的z，以及R(y,z)中的y．
六、证明题
1．证明：(P?(Q??R))??P?Q?(?P?(Q??R))??P?Q ?(?P?Q??R)??P?Q
?(?P??P?Q)?(Q??P?Q)?(?R??P?Q) ?(?P?Q)?(?P?Q)?(?P?Q??R)
??P?Q （吸收律） ??(P??Q) （摩根律） 2．证明：（1）（?x）（P（x）∧R（x）） P
（2）P（a）∧R（a） ES(1) （3）P（a） T(2)I
14
（4）（?x）P（x） EG(3)
（5）R（a） T(2)I
（6）（?x）R（x） EG(5)
（7）（?x）P（x）∧（?x）R（x） T(5)(6)I
离散数学图论部分综合练习
本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是图论部分的综合练习。
一、单项选择题
1．设图G的邻接矩阵为
?0?1??1??0??01100?0011??0000?
?1001?1010??则G的边数为( )．
A．6 B．5 C．4 D．3 2．已知图G的邻接矩阵为
则G有（ ）．
，
A．5点，8边 B．6点，7边 C．6点，8边 D．5点，7边
3．设图G＝
a ? d ? b ?
? f
?deg(v)?2E D．?deg(v)?E
v?Vv?V4．图G如图一所示，以下说法正确的是 ( ) ． A．{(a, d)}是割边 B．{(a, d)}是边割集 C．{(d, e)}是边割集
? c
图一
? e
15
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学(本)2016年10月份试题(3)在线全文阅读。
相关推荐：