* *
离散数学综合练习题
一、判断下列命题是否正确．如果正确，在题后括号内填“\\/”； 否则，填“?”
（1）空集是任何集合的真子集． （ ）
??是空集． （ ） （2）?{a},a? （ ） （3）?a??? （4）如果a?A?B，则a?A或a?B． （ ） （5）设集合A?{a1,a2,a3}，B?{b1,b2,b3}，则
A?B?{?a1,b1?,?a2,b2?,?a3,b3?} （ ） （6）设集合A?{0,1}，则
??{??,0?,??,1?,?{0},0?,?{0},1?} 是2到A的关系． （ ）
（7）关系的复合运算满足交换律． （ ）
（8）设?1,?2为集合 A 上的等价关系, 则?1??2也是集合 A 上的等价关系
( )
（9）设?是集合A上的等价关系, 则当?a,b???时，
A
[a]??[b]? ( )
（10）设?1,?2为集合 A 上的等价关系, 则
~??~ ( ) ?1??2??12（11）集合A上的任一运算对A是封闭的． （ ） （12）设A是集合，?:A?A?A，a?b?b，则?是可结合的． （ ） （13）设?G,??是群．如果对于任意a,b?G，有 (a?b)?a?b
则?G,??是阿贝尔群． （ ） （14）设a是群?G,??的元素，记 H?{y|y?G且y?a?a?y}
则?H,??是?G,??的子群． （ ）
（15）<{0，1，2，3，4}，max，min>是格． （ ） （16）设a，b是格?L,?,??的任意两个元素，则 a?b?b?a?b?a． （ ）
（17）设?B,?,?,?是布尔代数，则?B,?,??是格． （ ） （18）设集合A?{a,b}，则?{?,{a},{b},A},?,??是格． （ ）
（19）设?B,?,?,?是布尔代数，则对任意a,b?B，有
222* *
a?b?a?b． （ ）
（20）设?B,?,?,?是布尔代数，则对任意a?B，都有b?B，使得 a?b?1,a?b?0． （ ）
（21）n阶完全图的任意两个不同结点的距离都为1. （ ） （22）在有向图中，结点vi到结点vj的有向短程即为vj到vi 的有向短程． （ ）
（23）强连通有向图一定是单向连通的． （ ） （24）不论无向图或有向图，初级回路一定是简单回路． （ ） （25）设图G是连通的，则任意指定G的各边方向后所得的有 向图是弱连通的． （ ）
（26）设A是某个无向图的邻接矩阵，则A?A(A是A的转置 矩阵)． （ ）
（27）设有向图D的可达矩阵为
TT?1111???0111?? P??
0011????0001???则G是单向连通的． （ ）
（28）有生成树的无向图是连通的． （ ） （29）由r棵树组成的森林的结点数n与边数m有下列关系： m=n-r. （ ）
（30）如果有向图D仅有一个结点的入度为0，其余结点的入度都为1， 则D是有向树． （ ）
（31）“如果8＋7＞2，则三角形有四条边”是命题． （ ） （32）设P,Q都是命题公式，则P?Q也是命题公式． （ ） （33）命题公式P,Q的真值分别为0，1，则P?Q的真值为0 （以上是在对P,Q所包含的命题变元的某个赋值下）． （ ）
（34）逻辑结论是正确结论． （ ）
（35）设A,B都是谓词公式，则A?B也是谓词公式． （ ） （36）设A,B都是谓词公式，A?B，则A?B是永真式． （ ） （37）设A,B,C都是命题公式，则 (A?B??C)?(A?C)
也是命题公式． （ ） （38）命题公式P,Q的真值分别为0，1，则P?Q的真值为0 （以上是在对P,Q所包含的命题变元的某个赋值下）． （ ）
* *
（39）设c是个体域中某个元素，则 ?xP(x)??xQ(x)?P(c)?Q(c)
其中P,Q都是谓词． （ ） （40）?x?yA(x,y)??y?xA(x,y) （ ）
二、填空题
（1）设A有n个元素，则集合A的幂集P(A)中有 个元素。 （2）设A?{?,{?}}，则2A= .
（3）设集合A,B中元素的个数分别为#A?5，#B?7，且#(A?B)?9， 则集合A?B中元素的个数#(A?B)? .
（4）设集合A?{x|1?x?100,x是4的倍数，x?Z}，
B?{x|1?x?100,x是5的倍数，x?Z}，则A?B中元素的个数为 .
(5)设?1,?2为集合 A 上的二元关系, 则?1??2? . (6)集合A上的二元关系?为传递的充分必要条件是 ． (7)设?1：a称b为母亲，?2：b称c为父亲，则?1??2： ,
(8)设N为自然数的集合，“?”为自然数的小于等于关系，N的子集A?{5,7,9}，则
A的下确界为 ，下确界为 ,
(9)设10人集合E?{赵茵，钱小滨，孙丽春，赵萍，钱浩，李靖华，李秀娟，钱钰，李
惠芝，李莉}上的同姓关系为?，则等价类[赵]= ，[钱]= ，
(10)设 A?{a,b}, ? 是 2 上的包含于关系，,则有
A
?= .
(11)设S为非空有限集，代数系统?P(S),??中，P(S)对运算?的单位元为 ，零元为 .
(12)循环群?I3,?3?的生成元为 .
(13)循环群?I6,?6?的所有子群为 .
(14)代数系统?Z,??中（其中Z为整数集合，+为普通加法），对任意的x?I，其
x?1? .
(15)在整数集合Z上定义?运算为a?b?a?2?b，则?Z,??的单位元为 . (16)设T?{1,2,3,4,?,10},在代数系统?T,max?中，?T,max?的单位元为 ，可逆元为 .
(17)设G,?是群，则对于任意的a,b?G，方程 和 有唯一解。 (18)设G,?是群，对任意a,b,c?G，如果a?b?a?c,，则 .
2 (19)设G,?是群，e为单位元，若G元素a满足a?a，则a? .
(20)在整数集合Z上定义?运算为a?b?a?b?ab，则?Z,??的单位元为 .
* *
(21)设T??V,E?为树，T中有4度，3度，2度分支点各1个，问T中有 片树叶。
(23)设树T中有7片树叶，3个3度结点，其余都是4度结点，问T中有 个4度结点。
(24)无环有向图的关联矩阵的所有元素之和为 ． (25)n阶完全图的任意两个不同结点的距离都为 ． (26)图G为n阶无向完全图，则G共有 条边。 (27)设G为(n,m)图，则图中结点度数的总和为 。
(28)设图G有6结点，若各结点的度数分别为：1，4，4，3，5，5，则G共有 条边。
(29)无向图G是由k(k?2)棵树组成的森林，至少要添加 条边才能使G成为一棵树。
(30)在任何图G??V,E?中，奇数结点必为 个。
(31)设p: 天气很冷，q:老王还是来了，则命题“虽然天气很冷, 但老王还是来了”符号化为 .
(32)设p:天下雨，q: 我骑自行车上班，则命题“如果天不下雨, 我就骑自行车上班”符号化为 .
(33)设p:经一事, q:长一智，则命题“不经一事, 不长一智”符号化为 . (34)设p,q的真值为0，r的真值为1，则命题公式p?(q?r)的真值为 .
(35)设p,q的真值为0，r,s的真值为1，则命题公式(p?r)?(?q?s)的真值为 . (36)由n个命题变项可以组成 个不等值的命题公式。
(37)设个体域A?{a1,a2,?,an}，公式(?x)F(x)在A上消去量词后应 为 .
(38)设N(x):x是自然数，F(x):x是奇数，G(x):x是偶数，则命题“任何自然数不是奇数就是偶数” 符号化为 .
(39)设F(x):x是素数，G(x):x是偶数，a:2，则命题“2既是偶数又是素数”符号化为 .
(40)设G(x):x是金子，F(x):x是发光的，则命题“金子是发光的, 但发光的不一定是金子”符号化为 .
三、选择题（每题后面有四个选项，四个选项中只有一个是正确的，请将正确的所对应的字母填在括号内）
（1）设R为实数集合，下列集合中哪一个不是空集 （ ）
(22)为了从（n，m）连通无向图得到一棵生成树，必须删除G的 条边．
* *
A. x|x?1?0,且x?R B．x|x?9?0,且x?R
22C. ?x|x?x?1,且x?R? D. x|x??1,且x?R
2??????（2）设A,B为集合，若A\\B??，则一定有 （ ） A. B?? B．B?? C. A?B D. A?B （3）下列各式中不正确的是 （ ）
?? C. ??? D. ????,{?}? A. ??? B．???A（4）设A??a,{a}?，则下列各式中错误的是 （ ）
A{a}??2A D. ?{a}??2A A. ?a??2 B．?a??2 C. ?1,2?，B??a,b,c?，C??c,d?，则A?(B?C)为 （ ） （5）设A??A. ??c,1?,?2,c?? B．??1,c?,?2,c?? C. ??1,c?,?c,2?? D. ??c,1?,?c,2??
1,b,3?，则A?B的恒等关系为 （ ） （6）设A??0,b?，B??A. ??0,0?,?1,1?,?b,b?,?3,3?? B．??0,0?,?1,1?,?3,3?? C. ??0,0?,?b,b?,?3,3?? D. ??0,1?,?1,b?,?b,3?,?3,0??
（7）集合A?{1,2,?,10}上的二元关系??{(x,y)|x?y?10且x,y?A}，则?的 性质为 （ ）
A. 自反的； B．对称的； C. 反对称的； D. 反自反的. A. ?1???a,c?,?c,a?,?a,b?,?b,a?? B． ?2???a,c?,?c,a?? D. ?4???a,a??
C. ?3???a,b?,?c,c?,?b,a?,?b,c??
（9）设?为集合A上的等价关系，对任意a?A，其等价类?a??为 （ ） A. 空集； B．非空集； C. 是否为空集不能确定； D. {x|x?A}. （10）映射的复合运算满足 （ ） A. 交换律 B．结合律 C. 幂等律 D. 分配律
（11）在整数集Z上，下列哪种运算是可结合的 （ ） A. a?b?a?b B．a?b?max{a,b} C. a?b?a?2b D. a?b?|a?b|
（8）设A??a,b,c?上的二元关系如下，则具有传递性的为 （ ）
1,2,3,4,?,10?，下面定义的哪种运算关于集合A不是封闭的 （12）设集合A?? （ ）
A. x?y?max{x,y} B． x?y?min{x,y}
C. x?y?GCD{x,y}，即x,y的最大公约数 D. x?y?LCM{x,y}，即x,y的最小公倍数
离散数学2017年度秋综合理解练习知识题
