淮海工学院2011-2012-2离散数学期末复习题答案(1)

淮海工学院2011-2012-2离散数学期末复习题答案

一、选择题（每题3分）

1、下列句子中哪个不是命题？ ( C )

A、你通过了离散数学考试 B、我俩五百年前是一家 C、 我说的是真话 D、 淮海工学院是一座工厂 2、下列联接词运算不可交换的是( C )

A、? B、? C、 ? D、 ? 3、命题公式?P?Q不能表述为( B )

A、P或Q B、非P每当Q C、非P仅当Q D、除非P，否则Q 4、 下列公式中为永真式的是 ( C )

A、P?(P?Q) B、?P?(P?Q) C、(P?Q)?Q D、(P?Q)?Q 5、 下列公式中为非永真式的是( B )

A、 (P??P)?Q B、(P??P)?Q C、P?(?P?Q)D、P?(?P?Q) 6、设个体域A?{a,b}，则谓词公式?x(F(x)?G(x))消去量词后，可表示为为（ C ） A、(F(a)?F(b))?(G(a)?G(b)) B、(F(a)?F(b))?(G(a)?G(b)) C、(F(a)?G(a))?(F(b)?G(b)) D、(F(a)?G(a))?(F(b)?G(b)) 7、设个体域A?{a,b}，则谓词公式?x?yR?x,y?去掉量词后，可表示为（ D ） A、R?a,a??R?a,b??R?b,a??R?b,b? B、R?a,a??R?a,b??R?b,a??R?b,b? C、R?a,a??R?a,b??R?b,a??R?b,b? D、?R?a,a??R?a,b????R?b,a??R?b,b?? 8、设D：全总个体域，H(x)：x是人， P(x)：x犯错误， 则命题“没有不犯错误的人”的逻辑符号化为（ D ）

A、?x(H(x)?P(x))B、?x(H(x)?P(x))C、?x(H(x)?P(x)) D、?x(H(x)?P(x)) 9、设D：全总个体域，F(x)：x是花，M(x)：x是人，H(x,y)：x喜欢y， 则命题“有的人喜欢所有的花”的逻辑符号化为（ D ）

A、?x(M(x)??y(F(y)?H(x,y)) B、?x(M(x)??y(F(y)?H(x,y)) C、 ?x(M(x)??y(F(y)?H(x,y)) D、?x(M(x)??y(F(y)?H(x,y)) 10、设?为空集，则下列为假命题的是（ A ）

A、??? B、??? C、??{?} D、??{?} 11、设a,b各不相同，则下述等式为真的是（ D ）

A、{a,b}?{{a},{b}} B、{a,b}?{{a,b}} C、{{a}?{b}}?{a,b} D、{{a}?{b}}?{{a,b}}

12、 设集合A?{0,?}，?为空集， ?(A)为A的幂集，则下列为假命题的是（ B ） A、???(A) B、0??(A) C、{?}??(A) D、{0}??(A) 13、 设集合A?{0,?}，?为空集， ?(A)为A的幂集，则下列为假命题的是（ B ） A、???(A) B、{0}??(A) C、{?}??(A) D、{{0}}??(A) 14、非空集合X上的空关系?不具备的性质是（ A ）

A、自反性 B、反自反性 C、对称性 D、传递性

10、设A?{1,2,3}上的关系R的关系图如下，则R不具备的性质为（ A ）

????

A、自反性 B、反自反性 C、反对称性 D、传递性 15、A?{1,2,3,4}上的关系R???1,3?,?1,4?,?2,3,??2,4,?3?,4??只不具备（ C ）

A、 反自反性 B、 反对称性 C、对称性 D、传递性

16、设R为A?{1,2,3}上的关系，其关系图如下，则下列为真命题的是（ C ）

A、R对称，但不反对称 B、R反对称，但不对称 C、R对称，又反对称 D、R不对称，也不反对称

17、设R为A?{1,2,3,4}上的关系，其关系图如下，则下列为假命题的是（ C ）

A、R不自反，也不反自反 B、R不对称，也不反对称 C、R传递 D、R不传递

18、设A?{ 1, 2, 3 }，则A上不同等价关系的个数为（ C ） A、3 B、4 C、5 D、6 19、设A?{ 1, 2, 3, 4 }，则A上不同等价关系的个数为（ C ）

A、13 B、14 C、15 D、16

20、设R、Z分别为实数集、整数集，则下列函数为满射而非单射的是（ C ） A、f:R?R,C、f:R?Z,A、f:R?R,C、f:R?R,f(x)?(x?6)2

f(x)?[x] D、f:R?R,f(x)?x6?6x

f(x)?x?6 B、f:R?R,21、设R、非负实数集、正整数集，下列函数为单射而非满射的是（ B ） R、Z?分别为实数集、

f(x)??x2?7x?1 B、f:Z??R,f(x)?lnx；

f(x)?7x?1

f(x)?x D、f:R?R,22、设X?3,Y?4，则从X到Y可以生成不同的单射个数为（ B ）． A、12 B、24 C、64 D、81 23、设X?3,Y?2，则从X到Y可以生成不同的满射个数为（ B ）．

A、6 B、8 C、9 D、64

?、?、?为集合的交、并、差、笛卡尔乘积运算，则下列24、设集合A的幂集为?(A)，?、系统中是代数系统的为（ D ） A、

?(A),? B、?(A),? C、?(A),? D、?(A),?

25、在自然数集上定义的下列四种运算，其中满足结合律的是（C）

A、a?b?a?b B、a?b?|a?b| C、a?b?max{a,b}D、a?b?a?2b

26、设Nk为前k?2个自然数集，?k表示模k加法，对代数系统A?Nk,?k，有（ A ） A、0是么元，无零元 B、1是么元，无零元 C、无么元，0是零元 D、无么元，无么元 27、设Nk为前k?2个自然数集，?k表示模k乘法，对代数系统A?Nk, ?k，有（ B ）A、1是么元，无零元 B、1是么元，0是零元 C、无么元，0是零元 D、无零元，无么元 28、设非空有限集S的幂集为?(S)，对代数系统A?29、设非空有限集S的幂集为?(S)，对代数系统A??(S),?，有（ B ）

A、?是么元，S是零元 B、?是零元，S是么元 C、唯一等幂元 D、无等幂元

?(S),?，有（ A ）

A、?是么元，S是零元 B、?是零元，S是么元 C、唯一等幂元 D、无等幂元

30、设Z是由所有整数组成的集合，对于下列*运算，代数系统为独异点的是（ B ） A、a*b=ab B、a*b=a C、a*b=a+ab D、a*b=max(a,b) 31、任意具有多个等幂元的半群，它（A ）

A、不能构成群B、不一定能构成群 C、能构成群 D、能构成阿贝尔群

32、下列命题正确的是（ B ）

A、简单回路必为基本回路 B、基本回路必为简单回路 C、简单回路必不是基本回路 D、基本回路必不是简单回路 33、欧拉回路是（ B ）

A、路径 B、简单回路 C、既是基本回路也是简单回路 D、既非基本回路也非简单回路 34、哈密尔顿回路是（ C ）

A、路径 B、简单回路 C、既是基本回路也是简单回路 D、既非基本回路也非简单回路 35、在任何有向图中，下列命题正确的是（ C ）

A、任意顶点的入度与出度都相等 B、任意顶点的入度与出度都不相等

C、所有顶点的入度之和与出度之和都相等 D、所有顶点的入度之和与出度之和都不相等 36、设有向线图G的顶点集V?{v1,v2,?,vn}，邻接矩阵A?(aij)n?n，则d eg(?)vi?（ D ）A、aii B、

n?ai?1ii C、

?aj?1nij D、

?aj?1nji

37、设有向线图G的顶点集V?{v1,v2,?,vn}，邻接矩阵A?(aij)n?n，则d eg(?)vi?（ C ）A、aii B、

?ai?1nii C、

?aj?1nij D、

?aj?1nji

38、在有n个结点的简单无向图中，其边数（ C ） A、 最多有n-1条 B、至少有n-1条 C、最多有

n(n?1)n(n?1)条 D、至少有条 2239、在有n个结点的简单有向图中，其边数（ C ）

A、 最多有n-1条 B、至少有n-1条 C、最多有n(n?1)条 D、至少有n(n?1)条 40、在有n个结点的连通图中，其边数（ B ）

A、 最多有n-1条 B、至少有n-1条 C、最多有n条 D、至少有n条 41、设A?{?,{1},{1,3},{1,2,3}}，则A上包含关系“?”的哈斯图为（ C ）

42、集合A?{ 1, 2, 3,4 }上的偏序关系图为

则它的哈斯图为（ A ）

43、下列哪一种图不一定是树（ C ）

A、无简单回路的连通图 B、 有n个顶点n-1条边的连通图 C、每对顶点间都有通路的图 D、连通但删去一条边便不连通的图

44、设G是有5个结点的无向完全图，则从G中删去（ C ）条边可以得到树 A、 4 B、5 C、6 D、10

二、填充题（每题4分）

1、当赋予极小项足标相同的指派时，该极小项的真值为1，当赋予极大项足标相同的指派时，该极大项的真值为0.

2、任意两个不同极小项的合取式的真值为0，而全体极小项的析取式的真值为1. 3、任意两个不同极大项的析取式的真值为1，而全体极大项的合取式的真值为0. 4、n个命题变元可构造包括F的不同的主析取范式类别为2.

5、n个命题变元可构造包括T的不同的主合取范式类别为2.

6、若已证?xA(x)为真，则可假设某一确定的个体y使A(y)为真，此推理规则被称为ES． 7、令?是公理与前提的合取，?中无x的自由出现，若从?可推出A(x)，则从?也可推出?xA(x)，此推理规则被称为UG．

8、?(?)?{?}，?(?(?))?{?,{?}}， ?(?({?}))?{?,{?},{{?}},{?,{?}}}． 9、?(?)???{?}，?(?(?))??(?)?{{?}}．

10、设A??a?，则?(A)??(A)? ???,??,??,a?,?A,??,?A,A??． 11、设集合A,B分别含有m,n个不同元素，则A?B的基数为mn，?(A?B)的基数为212、A??(B)的基数为m2，?(A)?B的基数为n2，?(A)??(B)的基数为2nmm?nmn2n2n，

．

1 ,2,3,4,6,8,12,24} 13、设A?{，“?”为A上整除关系，则偏序集?A,??的极小元为1，最小元为1，极大元为24、最大元为24． 14、设A?{ 2,3,4,6,8,12 }，“?”为A上整除关系，则偏序集?A,??的极小元为2,3，

最小元为无，极大元为8,12，最大元为无，既非极小元也非极大元的是4,6． 15、设X?m,Y?n，则从X到Y有2有n! 种不同的双射．

17、设A={2,4,6}，A上*为：a*b=max{a,b}，则在代数系统中，么元是2，零元为6． 18、设A={3,6,9}，A上*为：a*b=min{a,b}，则在代数系统中，么元是9，零元为3 ． 19、设〈G,*〉是一个群，则

(1) 若a,b,x∈G，a?x=b，则x= a?b；(2) 若a,b,x∈G，a?x=a?b，则x= b． 20、群的等幂元是么元，有1个，零元有0个．

21、设a是12阶群的生成元， 则a是6阶元素，a是4阶元素． 22、设a是10阶群的生成元， 则a是5阶元素，a是10阶元素． 23、在一个群〈G,*〉中，若G中的元素a的阶是k，则a的阶是k． 24、n阶无向完全图Kn 的边数是

?14323mn 种不同的二元关系，有n 种不同的函数．

nm

16、在一个有n个元素的集合上，可以有2 种不同的二元关系，有n 种不同的函数，

n2?1n(n?1)，每个结点的度数是n?1． 2?0?1?25、设有向图G = < V，E >，V?{v1,v2,v3,v4}的邻接矩阵A??1??1则v1的入度deg(v1)= 3 ，v4的出度deg(v4)=1 ．

??101001001??1?， 0??0?26、设无向图G有18条边且每个顶点的度数都是3，则图G有12个顶点． 27、一棵无向树的顶点数为n，则其边数为n-1 ，其结点度数之和是2n-2. 28、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在2片树叶.