离散数学（本）2016年10月份试题

离散数学（本）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=，其中V={a, b, c, d}，E={ (a, b), (a, c), (a, d), (b, c), (b, d), (c, d) }，对应边的权值依次为1、1、5、2、3及4，请画出G的图形、写出G的邻接矩阵并求出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分）

（