离散数学练习题

更新时间:2024-03-06 10:28:01 阅读量: 综合文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

一、填空题(10分,每空1分,请将本题答案填在原题横线上!) ....

1设集合X={0,1,2},R是X上的二元关系,R={<0,0>,<0,2>,<1,2>,<2,0>,<2,1>},则R的关系矩阵MR= 。 2?Z6,?6?为模6整数加群, 则由2生成的子群<2>= ,右陪集<2>⊕65= 。

3设A和B为有限集,|A|=m,|B|=n,则有 个从A到B的关系,有 个从A到B的函数。

4无向图G如下图所示,G的点连通度κ为 ,边连通度λ为 。

5在上面无向图中,已给出了一棵生成树T(粗边所示),则树枝d对应的基本割集是 ,弦b对应的基本回路是 。 6令F(x): x是整数,G(x):x是奇数,则“不存在不是奇数的整数”符号化为 。

7含有三个命题变项P,Q,R的命题公式P?Q的主析取范式是 (用mi形式表示最小项)。

二、单选题(20分,每题1分,请将本题答案写在下方表格中!) ....1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 19 10 20 1下面给出的符号串集合中,( )不是前缀码。 ? B、?01,001,000,10? A、?0,10,110,11111101,1001,101,110,?C、? D、?b,c,aa,ac,aba,abc? 2、下列( )组赋值不是命题公式C?(A??B)的成真赋值。 A、010 B、011 C、110 D、101

3设A={a,b,c,d},A上的等价关系R={,}∪R-1∪IA,则对应于R的A的划分是( )。

A、{{a,b},{c,d}} B、{{a,b,d},{c}} C、{{a},{b},{c},{d}} D、{{a},{b,c},{d}} 4二部图K3,3是( ) 。

A、欧拉图 B、 哈密顿图 C、 非连通图 D、完全图

5令p: 我将去上网,q: 我有时间,则“我将去上网,仅当我有时间”可符号化为( )。

(A) p?q (B) p?q (C)q?p (D)?p??q

6下面( )图不一定是树。

A、每对结点间都有路的图 B、无回路的连通图

C、连通但删去一条边则不连通的图 D、有n个顶点n—1条边的连通图 7集合A = {1, 2, …, 10}上的关系R ={|x + y = 10, x, y ∈A}, 则R的性质是( )。

(A) 自反的 (B) 传递的、对称的 (C) 对称的 (D) 反自反的、传递的 8设G如右图,那么G不是( )。 (A)哈密顿图 (B)完全图 (C)欧拉图 (D)树

?0?19设图D的邻接矩阵为??1??1??11111?0100??,则D的顶点数与边数分别为

1011??0101?0110??( ) 。

A、4, 5 B、5, 16 C、4, 10 D、5, 8 10下列式子中正确的是( )。

A、?=1 B、??? C、??{?} D、?={?}

11由2个命题变元p和q组成的不等值的命题公式的个数有( )。 (A)2 (B)4 (C) 16 (D) 8

12给定下列非负整数序列,可构成简单无向图的节点度数序列的为( )。 (A) (1, 3, 4, 4, 5) (B) (1, 1, 2, 2, 2) (C) (0, 1, 3, 3, 5) (D) (1, 1, 2, 2, 3)

13 4阶完全无向图K4中含3条边的不同构的生成子图有( )。 (A)5 (B)4 (C)3 (D)2

14 任意12阶群的子群的阶一定不为 ( )。

(A)3 (B)6 (C)8 (D)4 15在公式?xF(x, y)→ ? yG(x,y)中变元x是( )。

(A) 既是自由变元,又是约束变元 (B) 既不是自由变元,又不是约束变元 (C) 自由变元 (D) 约束变元

16设图G=为无向图,|V|=5,|E|=20,则G一定是( ) 。 A、完全图 B、正则图 C、多重图 D、简单图

17给定公式?xP(x)??xP(x),当D={a,b}时,解释( )使该公式真值为0。 A.P(a)=0、P(b)=0 B.P(a)=0、P(b)=1 C.P(a)=1、P(b)=1 18设A={1 ,2 ,3 },则A上有( )个二元关系。

A、2 B、3 C、 2 D、2

19设Z是整数集合,“+”是数的加法运算,则的单位元是( ) A、1 B、-1 C、没有单位元 D、0

20设R和S是集合A={1,2,3,4}上的二元关系,则S是R的( )闭包。

3

2

2332R = {?1 ,1?,?1 ,2?,?2 ,2?,?2 ,3?,?4 ,4?}

S = {?1 ,1?,?1 ,2?,?2 ,2?,?2 ,3?,?3 ,3?,?4 ,4?} A、对称 B、自反 C、传递 D、以上都不对 三、求解题(40分,每题8分,请将本题答案写在后面答题纸上!) 1、在自然推理系统中构造证明: 已知张三或李四的彩票中奖了。如果张三的彩票中奖了,那么你会知道张三的彩票中奖了。如果李四的彩票中奖了,那么王五的彩票也中奖了。你不知道张三的彩票中奖了。所以,李四和王五的彩票都中奖了。

2、设A={a,b,c,d,e},A上的偏序关系R={}?IA ,求: (1) 画出偏序集的哈斯图;

(2) 求子集B={c,d,e}的极大元,极小元,最大元,最小元。

四、证明题(30分,每题7、7、8、8分,请将本题答案写在后面答题纸上!) 1、例如,f和g都是群到群的同态映射,C={x|x∈G1∧f(x)=g(x)}。证明:的一个子群。

2、要在七天安排七场考试,同一个老师监的任何两场考试不能安排在接连的两天内进行。假如每个教师最多监四场考试,请证明:安排这样的考试日程表是可以的。

二、单选题(20分,每题1分,请将本题答案写在下方表格中!) ....1 C 11 C 2 B 12 B 3 B 13 C 4 B 14 C 5 A 15 A 6 A 16 C 7 C 17 B 8 D 18 D 9 B 19 D 10 C 20 B

本文来源:https://www.bwwdw.com/article/s3ba.html

Top