离散数学试题库(4)

A.?x?y(F(y,x)?G(y))；B.?x?y(F(z,x)?G(y))； C.?y?x(?F(z,x)?G(y))；D.?x?y(F(x,z)?G(x,y))；

3、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式 ?x (P(x)?Q(x)) 在哪个个体域中为真( ) A. 自然数 B. 实数 C.复数 D. A--C均成立

4、令 F(x): x是兔子，G(x): x是乌龟，H(x,y): x比y跑得快，命题“并不是所有的兔子比乌龟跑得快”可以符号化为 ???????????????（ ）

A. ??x?y(F(x)?G(y)?H(x,y))；B. ??x?y(F(x)?G(y)?H(x,y))； C.??x?y(F(x)?G(y)?H(x,y))；D. ??x?y(F(x)?G(y)?H(x,y)) 5、设S?{?,{1},{1,2}}，则P(S)有( )个元素

A. 3

B. 16

C. 6

D. 8

6、设S?{1,2,3}，左图是S上关系R1的关系图，

则它具有( )性质.

A. 自反的，对称的，传递的；B. 反自反的，反对称的；C. 自反的，传递的； D. 自反的； 7、设V??R?,··?，其中·为普通乘法，对任意x?R令?1(x)?2x，?2(x)??x2，

?(x)?31，

x?(x)??x，则其中有（ ）个是V的自同态，

4A. 0 B.1 C.2 D.3

8、设Z是整数集合，则下面定义的二元运算不能使Z与?构成代数系统的是( ) A. i?j=|i-j|,?i,j∈Z B. i?j=i·j-j2，?i,j∈Z C. i?j=i/j,?i,j∈Z D. i?j=i2+j2+1,?i,j∈Z 9、设?G,??是群，a,b?G,则下列结论不正确的是??????????（ ）

A.(ab)?1?b?1a?1 B.ax?b有惟一解 C.ax?ay,则x?y D.ab?ba

10、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。

A. 10 B. 4 C. 17 D. 16

十二、 填空题

11、命题公式 ?(p?q)?r的主析取范式中含极小项的个数为_____，成真赋值为________。 12、令F(x)：x是人。G(x)：x犯错误。则命题“没有不犯错误的人”符号化为_________________ 13、设n阶无向简单图G中，?(G)?n?1，问?(G)为____________. 14、素数阶群一定是______________群, 它的生成元是_________________。 15、全二部图Kn,m(n?1,m?1)都是欧拉图，这个命题的真值为_________________;

16

16、群 ，?为模6加法运算，则子群H＝{0,2,4}的所有的右陪集为_______, _________. 17、集合A的一个划分，确定A的元素间的关系为___________

18、设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，则代数系统的幺元是 ，零元是 。

十三、 解答题

19、求?(p?q)?r 的主析取范式和主合取范式。

20、用容斥原理解题：

某班级有学生四十名，共有三门选修课可供选择，选修课课程名称分别为A、B、C，其中有15名学生选A课程，有10名学生选B课程，6名学生选C课程，而且其中有5名学生三门课程都选。问至少有多少学生三门选修课一门也没选？

,22,55,110}是110的正因子集，?A,??构成偏序集，其中?为整除关系。21、设A?{1,2,5,10,11（1）画出偏序集?A,??的哈斯图。

（2）说明该偏序集是否构成布尔代数，为什么？

22、设某编码系统中只出现A,B,C,D,E,F,G,H等八个字符，它们的使用频率相应为

0.05,0.07,0.25,0.15,0.08,0.12,0.06,0.22，画出相应的哈夫曼树，然后给出各字符的哈夫曼编码。

24、今有工人甲、乙、丙要完成三顶任务a,b,c，已知工人甲能胜任a,b,c三项任务；工人乙能胜任a,b,两项任务；工人丙能胜任b,c两项任务，给出一种可能的安排方案，使得每个工人各完成一项他们能胜任的任务。

四、证明题

25、构造推理证明。

前提：(P→Q)?(R→S)，(Q→W)?(S→X)，?(W?X)，P→R 。 结论：

?p。

26、设正整数集合

I?上的二元关系

R?{?x,y?|x,y?I?,x?y?I}2，证明：R为等价关系。

27、设G1＝,G2=,其中R*为非零实数的集合，＋和 . 分别表示数的加法和乘法。 f：Z－>R*, f(x)= 1

1 x是偶数

－1 x是奇数 （1）验证f为同态映射。（4分） （2）说明f是否为单同态和满同态。（4分） （3）计算 kerf。(2分)

模拟试题(九)

17

十四、 单项选择题

在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。 1、若p：天下大雨；q：他乘公共汽车上班；则“仅当天下雨的时候他才乘公共汽车上班。”，可符

号化为( ) ，

A. p∨q B. p∧┐q C. p→┐q D . q→p 2、使命题公式p→(p∧q)为假的赋值是( )

A.10 B.01 C. 00 D.11 3、设S?{1,2,4,8,16}，?是S上的整除关系，则?S,??的哈斯图是( )

A. 一棵树；B. 一条链；C. 一些独立的点； D. 以上都不对

4、设函数f：N→N（N 为自然数集），f(n)=n+1，下面四个命题为真的是( ) A. f是单射 B. f是满射 C. f是双射的 D.f非单射非满射 5、设S?{1,2,3}，左图是S上关系R的关系图， 则它具有( )性质.

A. 自反的，对称的，传递的；B. 反自反的，反对称的；

C. 自反的，传递的； D. 自反的，对称的，反对称的，传递的。 6、设X，Y，Z是集合，下列结论不正确的是（ ） ．．．

A．若X?Y,则X∩Y=X B．(X-Y)-Z=X-(Y∩Z) C．X?X?? D．X?Y?X?(~Y) 7、设G?{0,1,2,3}，若?为模4加法，则中的4阶元是（ ）。

A.0;

B.1和3

C.2；

D.不存在。

8、4阶无向连通图G是欧拉图，则它的度序列可能是（ ）

A.1,2,3,4 B.2,4,6,8 C.1,2,4,6 D.5,2,3,4 9、下面给出的符号串集合中，( )是前缀码：

B1?{0,10,110,1111}

B2?{1,01,001,0011}B3?{1,11,101,001,0011}

B4?{a,c,,aa,ac,aba,abb,abc} B5?{b,c,a,aa,ac,aba,abb,abc}

A.B1 B. B1、B2和B3

C.B4和B5

D.以上都不对

10.G??1,?1,i,?i?　,?是一个群(其中?是数的乘法运算,i?下列代数系统为G的子群的是(　　　　)

?1),

A.<{-1},×> B. <{i},×> C. <{i,-i},×> D. <{1,-1},×>

11、以下系统是代数系统的是（ ）

B.，其中A={a,b}，*运算定义为 C. ，其中Z为整数集，÷是数的除法运算 D. ，其中R为实数集，÷是数的除法运算

12、设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ） A．2 B．3 C．4 D．5

十五、 填空题

13、量词否定等值式??xA(x)? ___________________。

14、设F(x):x是人，H(x):x呼吸，在一阶逻辑中，命题“凡是人都呼吸”的符号化形式为________

18

15、设D是n阶有向简单图，D'是D的子图，已知D'的边数m'?n(n?1)，则D的边数m为_______.

16、完全二部图Kr,s中，边数m为_______________________ 17、 设S?{1,2,3,4}，R为S上的关系，其关系矩阵是：??1001??1000?，则R的关系表达式是??0001???1000??_____;R的对称闭包是_____, domR?_____，ranR?_____; R?R中有_____有序对;R?1的关系图中有_____ …… 此处隐藏：3524字，全部文档内容请下载后查看。喜欢就下载吧 ……