离散数学(本)2024年10月份试题

（3分） （2）邻接矩阵

?0? ?1?0??1（3）deg(v1)=2

deg(v2)=2 deg(v3)=0

101?001?? （6分） 000??100?deg(v4)=2 （9分）

（4）补图

（12分）

17．解：?P∨(Q∧R) ?(?P∨Q)∧(?P∨R) 合取范式 （2分）

?(?P∨Q) ∨(R∧?R) ∧ (?P∨R) （5分） ?(?P∨Q) ∨(R∧?R) ∧ (?P∨R) ∨(Q∧?Q) （7分） ?(?P∨Q∨R )∧(?P∨Q∨?R) ∧ (?P∨R∨Q )∧(?P∨R∨?Q) （10分） ?(?P∨Q∨R )∧(?P∨Q∨?R)∧(?P∨?Q∨R) 主合取范式 （12分）

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

18．证明：设S= A? ( B?C )，T=( A? B) ? ( A? C )，

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

则有x∈A且y∈B，或x∈A且y∈C，即有x∈A且y∈B或y∈C， （6分） 则有x∈A且y∈( B?C )， 即有∈S，

所以T?S． （7分） 得证 A? ( B?C )=( A? B) ? ( A? C )． （8分）

36

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

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

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

2．设A={1, 2, 3｝，B ={1, 2, 3, 4}，A到B的关系R ={ | x大于y｝，则R = ( )． A．{<2, 1>, <3, 1>, <3, 2 >} B．{<1, 1>, <1, 2>, <1, 3>, <1, 4>, <1, 5>} C．{<1, 1>, <2, 1>} D．{<1, 2>, <2, 3>} 3．无向图G的结点的度数之和是10，则图G的边数为（ ）． A．10 B．15 C．20 D．5

4．设连通平面图G有v个结点，e条边，r个面，则（ ）． A．v + e - r=2 B．v + e - r=4 C．r + v - e =2 D．v + e – r = – 4

5．设个体域D是整数集合，则命题?x?y (x?y = y)的真值是（ ）． A．不确定 B．由y的取值确定 C．F D．T

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

6．设集合A={a, b, c}，B={b, c}，C={c, d}，则A∩(B∪C)等于 ． 7．设A={2，3}，B={1，2}，C={3，4}，从A到B的函数f={<2, 2>, <3, 1>}，从B到C的函数g={<1，3>, <2，4>}，则Dom(g? f)等于 ．

8．若图G=，其中V={ a, b, c, d }，E={ (a, b), (b, c) , (b, d)}，则该图中的割点为 ．

9．设G是汉密尔顿图，S是其结点集的一个子集，若S的元素个数为4，则在G -S中的连通分支数不超过 ．

10．设个体域D＝{1,2, 3, 4}，A(x)为“x大于5”，则谓词公式(?x)A(x)的真值为 ．

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

11．将语句“雪是白色的，但天是蓝色的．”翻译成命题公式． 12．将语句“如果下雨，则活动取消．”翻译成命题公式．

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

13．集合的元素可以是集合．

14．(?x)(P(x)→Q(y)∧R(z))中的自由变元为x．

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

15．设A={1，2，3}，R={|x?A，y?A且x +y >4}，S={|x?A，y?A且x

37

试求R，S，R-1，s(S)．

16．图G=，其中V={ a, b, c, d }，E={ (a, b), (a, c) , (a, d), (b, c) , (b, d) , (c, d)}，对应边的权值依次为2、3、4、5、6及7，试

（1）画出G的图形； （2）写出G的邻接矩阵；

（3）求出G权最小的生成树及其权值．

17．试画一棵带权为1, 1, 3, 4, 4的最优二叉树,并计算该最优二叉树的权．

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

18．试证明：?P∨Q ? P→（? (?P∨?Q)）

38

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

参考解答

一、单项选择题（每小题3分，本题共15分） 1．B 2．A 3．D 4．C 5．D

二、填空题（每小题3分，本题共15分） 6．{b，c }

7．{2，3} （或A） 8．b 9．4

10．假（或F，或0）

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

11．设P：雪是白色的，Q：天是蓝色的． 则命题公式为： P∧Q． 12．设P：下雨，Q：活动取消． 则命题公式为：P→Q．

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

13．正确． 例：集合{{1}}中的元素{1}是集合． 14．错误． (?x)(P(x)→Q(y)∧R(z))中的约束变元为x，自由变元为y与z．

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

R={<2, 3>, <3, 2>, <3, 3>} S={<1, 2>, <1, 3>, <2, 3>} R-1={<2, 3>, <3, 2>, <3, 3>} s(S)={ <1, 2>, <1, 3>, <2, 3>, <2, 1>, <3, 1>, <3, 2>}

．（1）G的图形表示为： a ? 4

? d

2 3 7

6 b ? 5

? c 39

（2分） （6分） （2分） （6分） （3分） （7分） （3分） （7分） （3分） （6分） （9分） （12分）3分）

16

（

?0?1（2）邻接矩阵： ??1??1111?011?? （6分） 101??110?（3）粗线与结点表示的是最小生成树， a 4 ? ? d

3 2 7 （10分）

6 b ? ? c 5

权值为9 （12分） 17．

13 ? 5 ? 2 ? ? 8

? ? ? 4 3 4

? 1 ? （10分）

1

权为1?3+1?3+3?2+4?2+4?2=28 （12分）

六、证明题（本题共8分） 18．证明：

（1）?P∨Q P （1分） （2）P P（附加前提） （3分） （3）Q T（1）（2）I （5分） （4）P∧Q T（2）（3）I （6分） （5）? (?P∨?Q) T（4）E （7分） （6）P→? (?P∨?Q) CP规则 （8分）

说明：1、因证明过程中，公式引用的次序可以不同，一般引用前提正确得1分，利用两个公式得出有效结论得1或2分，最后得出结论得2或1分．

另，可以用真值表验证．采用反证法可参照给分．

离散数学（本）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

40

百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库离散数学(本)2024年10月份试题在线全文阅读。