离散数学（本）2016年7月份试题
一、单项选择题（每小题3分，本题共15分）
1．若集合A＝{1,2,3,4}，B＝{1,3,5}，则下列表述正确的是 ( )． A．A＝B B．B ?A
C．B ?A D．B ? A
2．设A＝｛1,2,3｝，B={2,4,6}，A到B的关系R＝｛〈x, y〉| 2x=y｝，则R= ( )． A. {<1,3>,<2,4>,<3,5>} B. {<2,1 >,<4,3>,<6,5>} C. {<1,1>,<2,2>,<3,3>} D. {<1,2>,<2,4>,<3,6>} 3．无向图G是棵树，边数是10，则G的结点度数之和是（ ）． A. 20 B. 9 C. 10 D. 11
4．下面的推理正确的是（ ）．
A．(1) （?x）F（x）→G（x） 前提引入 (2) F（y）→G（y） US（1）． B．(1) （?x）F（x）→G（x） 前提引入
(2) F（y）→G（y） US（1）．
C．(1) （?x）(F（x）→G（x）） 前提引入 (2) F（y）→G（x） ES（1）．
D．(1) （?x）（F（x）→G（x）） 前提引入 (2) F（y）→ G（y） US（1）．
5．设个体域为整数集，则公式?x?y(x+y=2)的解释可为 ( )．
A. 任一整数x，对任意整数y满足x+y=2 B. 对任一整数x，存在整数y满足x+y=2 C. 存在一整数x，对任意整数y满足x+y=2 D. 存在一整数x，有整数y满足x+y=2
二、填空题（每小题3分，本题共15分）
6．设集合A={1, 2, 3}，B={2, 3, 4}，C={3, 4, 5}，则B∪(A–C)等于 ． 7．设A={1, 2}，B={2, 3}，C={3，4}，从A到B的函数f ={<1, 2>, <2, 3>}，从B到C的函数g={<2, 3>, <3, 4>}，则Ran(g? f)等于 ．
8．两个图同构的必要条件包括结点数相等、边数相等与 ． 9．设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，v值为5，e值为4则r的值为 ．
10．设个体域D＝{1, 2, 3, 4}，则谓词公式(?x)A(x)消去量词后的等值式为 ．
三、逻辑公式翻译（每小题6分，本题共12分）
11．将语句“昨天下雨，今天仍然下雨．”翻译成命题公式． 12．将语句“若不下雨，我们就去参加比赛．”翻译成命题公式．
四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）
13．若图G是一个欧拉图，则图G中存在欧拉路．
5
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分）
（
相关推荐：
loading