14．无向图G的结点数比边数多1，则G是树．
五．计算题（每小题12分，本题共36分） 15．设集合A={1, 2, 3, 4}上的关系：
R={<1，2>, <2，3>, <3，4>}，S={<1，1>, <2，2>, <3，3>}，
试计算（1）R?S； （2）R ?1； （3）r（R?S）．
16．图G=
17．求?（P∨Q）∨R的析取范式与主合取范式．
六、证明题（本题共8分）
18．设A，B，C均为任意集合，试证明：A ?( B ? C ) = (A? B ) ?(A ?C )．
6
离散数学（本）2016年1月份试题
参考解答
一、单项选择题（每小题3分，本题共15分） 1．C 2．D 3．A 4．D 5．B
二、填空题（每小题3分，本题共15分） 6．{1,2,3, 4} 7．{3, 4}
8．度数相同的结点数相等 9．1
10．A(1 ) ∨A(2) ∨ A(3) ∨ A(4)
三、逻辑公式翻译（每小题6分，本题共12分）
11．设P：昨天下雨，Q：今天下雨． （2分） 则命题公式为：P∧Q． （6分）
12．设P：下雨，Q：我们去参加比赛． （2分）
则命题公式为：?P→Q． （或 ? Q→P） （6分）
四、判断说明题（每小题7分，本题共14分）
13．正确． （3分） 因为若图G是一个欧拉图，则图中存在欧拉回路． （5分） 按定义知，欧拉回路也是欧拉路． （7分） 14．错误． （3分） 反例：如图G的结点数比边数多1，但不是树．
（或：按定义有：无向图G是树当且仅当无向图G是连通图且边数比结点数少1．）
（7分）
说明：举出符合条件的反例均给分．
五．计算题（每小题12分，本题共36分）
15．解：（1）R?S =={<1，2>，<2，3>}； （4分）
（2）R ?1={<2，1>, <3，2>, <4，3>}； （8分） （3）r（R?S）={<1，1>, <2，2> , <3，3>, <4，4>} （12分） 16．解：G的图形表示为：
7
（3分）
邻接矩阵：
??0111??1011??101?? ?1?1110??粗线表示的图是最小的生成树，权为5： 17．解：?（P∨ Q）∨R ?(?P∧?Q)∨R 析取范式 ?(?P∨R)∧(?Q∨R) ?((?P∨R )∨(Q∧?Q))∧ (?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) 主合取范式
六、证明题（本题共8分）
18．证明：
设S= A ?( B ? C )，T=(A? B ) ?(A ?C )，
若x∈S，则x∈A且x∈B ?C，即 x∈A，并且x∈B 且 x?C， 所以x∈(A? B )且x?(A ?C )，得x∈T， 所以S?T． 反之，若x∈T，则x∈(A?B ) 且 x?(A ?C )， 即x∈A，x∈B ，且x ?C，则得x∈B ?C， 即得x∈A ?( B ? C )，即x∈S，所以T?S． 因此T=S．
另，可以用恒等式替换的方法证明． 8
6分） （9分）
（12分） （5分） （7分） （9分） （10分） （11分） （12分） （2分） （3分） （4分） （5分） （6分）
（7分） （8分）
（
离散数学数理逻辑部分综合练习
本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是数理逻辑部分的综合练习。
一、单项选择题
1．设P：我将去市里，Q：我有时间．命题“我将去市里，仅当我有时间时”符号化为( )
A．Q?P B．P?Q C．P?Q D．?P??Q 2．设命题公式G：?P?(Q?R),则使公式G取真值为1的P，Q，R赋值分别是 ( ) A．0, 0, 0 B．0, 0, 1 C．0, 1, 0 D．1, 0, 0 A．?P??Q?P?Q B．(Q?(P?Q)) ?(?Q?(P?Q)) C．(P?(?Q?P))?(?P?(P?Q)) D．(?P?(P?Q)) ?Q 4．下列等价公式成立的为( )．
A．?P??Q?P?Q B．P?(?Q?P) ??P?(P?Q) C．Q?(P?Q) ??Q?(P?Q) D．?P?(P?Q) ?Q 5．命题公式?(P?Q)的主析取范式是( A )．
A．P??Q B．?P?Q C．?P?Q D．P??Q 6．命题公式（P∨Q）→R的析取范式是 ( B ) A．?（P∨Q）∨R B．（P∧Q）∨R
C．（P∨Q）∨R D．（?P∧?Q）∨R
7．设C(x): x是国家级运动员，G(x): x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为 ( )．
A．??x(C(x)??G(x)) B．??x(C(x)??G(x))
C．??x(C(x)??G(x)) D．??x(C(x)??G(x))
8．设A（x）：x是人，B（x）：x是学生，则命题“不是所有人都是学生”可符号化为（ ）． A．(?x)(A(x)∧B(x)) B．┐(?x)(A(x)∧B(x)) C．┐(?x)(A(x) →B(x)) D．┐(?x)(A(x)∧┐B(x))
9．表达式?x(P(x,y)?Q(z))??y(R(x,y)??zQ(z))中?x的辖域是( )． A．P(x, y) B．P(x, y)?Q(z) C．R(x, y) D．P(x, y)?R(x, y)
二、填空题
1．命题公式P?(Q?P)的真值是 ．
2．设P：他生病了，Q：他出差了．R：我同意他不参加学习. 则命题“如果他生病或
9
3．下列公式 ( )为重言式．
出差了，我就同意他不参加学习”符号化的结果为 ．
3．含有三个命题变项P，Q，R的命题公式P?Q的主析取范式是 ． 4．设F(x)：x是鸟，G(x)：x会飞翔．则命题“鸟会飞”符号化为 ．
5．设个体域D={1, 2},那么谓词公式?xA(x)??yB(y)消去量词后的等值式为 ．
6．设个体域D＝{a, b, c}，则谓词公式(?x)A(x)消去量词后的等值式为 ．
7．设个体域D＝{a, b}，则谓词公式(?x)A(x)∧（?x）B（x）消去量词后的等值式为 ．
A (a)∧A (b))∧(B（a）∨B（b）
8．设个体域D＝{1, 2}，则谓词公式?xA(x)消去量词后的等值式为 ． A(1)?A(2)
9．谓词命题公式(?x)(P(x)→Q(x)∨R(x，y))中的约束变元为 ．
10．(?x)(P(x)→Q(x)∨R(x，y))中的自由变元为 ．
三、公式翻译题
1．请将语句“今天不是天晴”翻译成命题公式．
2．将语句“今天没有下雨．”翻译成命题公式． 3．将语句“今天没有人来．” 翻译成命题公式．
4．将语句“他不去学校．”翻译成命题公式．
5．将语句“尽管他接受了这个任务，但他没有完成好．”翻译成命题公式．
6．将语句“小王去旅游，小李也去旅游．”翻译成命题公式．
7．将语句“他去旅游，仅当他有时间．”翻译成命题公式．
8．请将语句“我去书店，仅当天不下雨”翻译成命题公式．
9．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式．
10．将语句“如果你去了，那么他就不去．”翻译成命题公式．
11．请将语句 “有人不去工作”翻译成谓词公式．
12．将语句“有人去上课．” 翻译成谓词公式．
13．请将语句“所有人都努力工作．”翻译成谓词公式．
14．将语句“所有人都去工作．”翻译成谓词公式． 15．将语句“所有的人都学习努力．”翻译成命题公式．
10