离散数学2015年7月份试题

离散数学（本）2015年7月份试题

一、单项选择题（每小题3分，本题共15分） 1．若集合A＝{1,2,3}，则下列表述正确的是 ( )． A．{1, 2, 3 }?A B．A ? {1, 2 }

C．{1, 2, 3 }?A D．{1, 2}?A

2．已知无向图G 有10条边，则G的结点度数之和为（ ）． A．10 B．20 C．30 D．5

3．无向图G是棵树，边数为10，则G的结点数是（ ）． A． 5 B． 10 C． 9 D． 11

4．设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))

5．下面的推理正确的是（ ）．

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（y） ES（1）．

D．(1) （?x）(F（x）→G（x）） 前提引入 (2) F（y）→G（x） ES（1）．

二、填空题（每小题3分，本题共15分）

6．设A={1，2}，B={ a, b, c }，作f：A→B，则不同的函数个数为 ． 7．有n个结点的无向完全图的边数为 ．

8．设无向图G中存在欧拉回路，则G的奇数度数的结点数为 个． 9．设G是有8个结点的连通图，结点的度数之和为24，则可从G中删去 条边后使之变成树．

10．设个体域D＝{a, b, c}，则谓词公式(?x)A(x)消去量词后的等值式为 ．

三、逻辑公式翻译（每小题6分，本题共12分） 11．将语句“学生的主要任务是学习”翻译成命题公式．

12．将语句“我们下午2点或者去礼堂看电影或者去教室看书．”翻译成命题公式．

四、判断说明题（判断各题正误，并说明理由．每小题7分，本题共14分）

13．不存在集合A与B，使得A?B与A?B同时成立． 14．如下完全图K4（如下图）是平面图．

1

五．计算题（每小题12分，本题共36分）

15．设偏序集的哈斯图如下图所示，B为A的子集，其中B={ a, b, c }，试

（1）写出R的关系表达式； （2）画出关系R的关系图；

（3）求出B的最大元素、极小元素、上界．

16．．设图G=，V={ v1，v2，v3，v4，v5}，E={ (v1, v2)，(v1, v4)，(v1, v5)，(v2, v4)，(v3, v5) }，试

（1）画出G的图形表示； （2）写出其邻接矩阵； （3）求出每个结点的度数； （4）画出图G的补图的图形．

17．求P→（Q∧R）的析取范式与主合取范式．

六、证明题（本题共8分）

18．设A，B，C均为任意集合，试证明：A ?( B ? C ) = (A? B ) ?(A ?C )．

2

离散数学（本）2015年7月份试题

参考解答

一、单项选择题（每小题3分，本题共15分）

1．C 2．B 3．D 4．A 5．C

二、填空题（每小题3分，本题共15分） 6．9 7．n(n-1)/2 8．0 9．5

10．A(a ) ∧A(b) ∧ A(c)

三、逻辑公式翻译（每小题6分，本题共12分）

11．设P：学生的主要任务是学习． （2分） 则命题公式为：P． （6分）

12．设P：我们下午2点去礼堂看电影，

Q：我们下午2点去教室看书． （2分） 则命题公式为：?（P?Q）． （6分） 注：或者（?P∧Q）∨（ P∧?Q ）

四、判断说明题（每小题7分，本题共14分）

13．错误． （3分） 例：设A={a}，B={a，{a}} （5分） 则有A?B且A?B． （7分） 说明：举出符合条件的反例均给分．

14．正确． （3分） 完全图K4是平面图， （5分） 如K4可以如下图示嵌入平面． （7分）

五．计算题（每小题12分，本题共36分）

15．（1）R={< a, a >,< b, b >,< c, c >,< d, d >,< a, b >,< a, c >,< a, d >,< b, d >,< c, d >}．

（4分）

（2）关系图

? d

（8分）

? ? c b 3

? a

（3）集合B无最大元素、极小元素为a、上确界为d （12分） 16．解： （1）关系图

（2）邻接矩阵

??01011?0010? ?1??00001?? ?11000????10100??（3）deg(v1)=3

deg(v2)=2

deg(v3)=1 deg(v4)=2

deg(v5)=2 （4）补图

17．P→（Q∧R）

??P∨(Q∧R) 析取范式 ?(?P∨Q)∧(?P∨R) ?(?P∨Q) ∨(R∧?R) ∧ (?P∨R) ?(?P∨Q) ∨(R∧?R) ∧ (?P∨R) ∨(Q∧?Q) ?(?P∨Q∨R )∧(?P∨Q∨?R) ∧ (?P∨R∨Q )∧(?P∨R∨?Q) ?(?P∨Q∨R )∧(?P∨Q∨?R)∧(?P∨?Q∨R) 主合取范式

六、证明题（本题共8分）

18．证明：

设S= A ?( B ? C )，T=(A? B ) ?(A ?C )，

4

（3分）（6分）

（9分） （12分）2分） 5分） 7分） 9分） 11分） 12分）

（ （ （ （ （ （

若x∈S，则x∈A且x∈B ?C，即 x∈A，并且x∈B 且 x?C， （2分） 所以x∈(A? B )且x?(A ?C )，得x∈T， （3分） 所以S?T． （4分） 反之，若x∈T，则x∈(A?B ) 且 x?(A ?C )， （5分） 即x∈A，x∈B ，且x ?C，则得x∈B ?C， （6分）

即得x∈A ?( B ? C )，即x∈S，所以T?S． （7分） 因此T=S． （8分）

另，可以用恒等式替换的方法证明．

5