《 离散数学 》
同步测试1、命题逻辑
一．填空：
1．公式(p?q)?(r?s)的真值表中共有 16 种真值指派。
2．命题公式（?P ?Q）?（?Q?P）的主析取范式为m11?m10?m00或（P?Q）?（P?? Q）?（?P??Q），主合取范式为：M01或P?? Q。
3．设A、B、C和D四个人中派两个人出差，需要满足下列条件：（1）若A去，
则C和D中要去一人；（2）B和C不能都去；（3）C去则D要留下。则有3 种派法，分别为AC,AD,BD。 4．给定命题公式：P?（?P?（Q?(? Q?R)）则它的成真指派为001，010，011，100，101，110，111，成假指派为000。
二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。
1、设A、B、C为任意命题公式，若A?B?B? C，则A?B。（×） 2、设A、B为任意命题公式，若?A??B，则A?B。（√） 3、公式(p?q)?(p?q)是重言式。（√）
4、公式P?Q是合取范式，不是析取范式。（×） 5、所有极大项的析取为永真式。（√）
6、一个命题公式可以有多个与之等价的析取范式。（√） 7、任一命题的主合取范式是唯一的。（√） 8、下面推理是正确的：（×） （1）P?Q P （2）?P P （3）?Q T(1)(2)
9、公式（P?Q）?（R??S）的对偶式为（P?Q）?（R??S）。（×） 10、公式（?P?Q）?（P?R）与P?（Q? R）。（√）
三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的括号内(多选不给分)。
1、给定命题公式如下：A．（P?Q）?（P?Q）?（Q?P） B．（P??P）?Q C．（P??P）?（（Q ??Q）?R）
则重言式为：( A )，矛盾式为：( C )，可满足式为：( B ) 2．给定命题公式如下：（?P ?Q）?（?P?Q）
1
该命题公式的成真赋值个数是（D），成假赋值个数是（B），与它等价的主析取范式中极小项个数为（D），主合取范式中极大项个数为（B） A．0 B．1 C．2 D．3 E. 4
3．给定命题公式：P?（Q?R）则它的成真赋值为（A），成假赋值为（C） A．111，011，100，101，110B．111，011 C．000，010，001D．000 4．给定真值表： P Q 0 0 0 1 1 0 1 1 F 1 1 1 0 则F等价于（D）
A．P ?QB．P?QC．P?QD．?P??Q 5．给定命题公式：（?P?Q）?（P?R），与之等价的是 (C ) A．P?（?Q?R）B．P?（Q?R） C．P?（Q?R） D．?P?（Q?R） 6．前提条件：P?（Q?S），Q, P??R,则它的有效推论为 (B ) A．SB．R?S C．P D．R?Q
同步测试2、谓词逻辑
一．填空：
1．对谓词公式（（?x）P（x）?（?y）Q（y））?（?x）R（x）中约束变元应用 变换规则所得到的前束范式是（?x）（? y）（?z）（P（x）?Q（y））?R（z）） 2．谓词公式（?x）（P（x）?Q（x））?（?z）（R（x）?S（z））中，量词（?x）的辖域为（P（x）?Q（x））。
3．给定命题“不存在两片完全一样的叶子”（假设L（x）：x是叶子，S（x，y）: x是y，T（x，y）:：x与y完全相同。），则该命题符号化后的公式为（?x）（? y）（（L（x）?L（y））?（?S（x，y）??T（x，y））） 4．谓词公式（?x）F（x）?（（?x）F（x）?（?y）G（y））是逻辑有效式，?（F（x,y）?R（x,y））?R（x,y）是矛盾式，（?x）（?y）F（x,y）?（?x）（?y）F（x,y）是可满足式。 5．由前提（?x）（F（x）?H（x））,（?x）?H（x）可得出的有效结论是（?x）?F（x）。
二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。
2
1、（?x）（A（x）?B（x））?（?x）A（x）?（?x）B（x）。（×） 2、（?x）（?y）A（x,y）?（?y）（?x）A（x,y）。（×） 3、（?x）（A（x）?B（x））?（?x）A（x）?（?x）B（x）。（√） 4、谓词公式（?x）（?y）（P（x,y）?Q（y,z））中，x,y 是约束变元，z 是自由变元。（√）
5、谓词公式（?y）（?z）（P（y）?Q（x,z））中，无自由变元，是闭式。（×） 6、对谓词公式（?x）（P（y）?Q（x,y））? R（x,y）中的自由变元进行代入后得到公式（?x）（P（z）?Q（x,z））? R（x,y）。（×） 7、对谓词公式（?x）（P（x）?Q（x,y））? R（x,y）中的约束变元进行换名后得到公式（?y）（P（y）?Q（y,y））? R（x,y）（×） 8、谓词公式的前束范式不是唯一的。（√） 9、如下推理是正确的: 前提（?x）（F（x）?G（x））, （?y）F（y） 结论（?y）G（y）（√） 10．（?x）（A（x）?B（x））?（?x）A（x）?（?x）B（x）。（√） 11、（?y）（?x）A（x,y）的斯柯林范式是（?x）（?y）A（x,y）（×） 三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的括号内(多选不给分)。
1、取个体域为整数集，则下列公式中真命题为（A），假命题为（B）。 A．（?x）（?y）（x×y=0）B．（?x）（?y）（x×y=1） C．x?y??y?x D．（?x）（x×y=x）
2．给定公式（?x）F（y ,x）?（?y）G（y），它的前束范式（C）， A．(?x)(?y)(F(y ,x)?G(y)) B．(?x)(?y)(F(z ,x)?G(y))
C．(?x)(?y)(?F(z ,x)?G(y)) D．(?x)(?y)(?F(z ,x)?G(y)) 3．下列公式中，（A）是逻辑有效式，（C）是矛盾式。
A．(?x) F（x）?(?y)F（y）B．(?x) (?y) F(x,,y)?(?x) (?y) F(x,,y) C．?(P（x）?((?y)G(x,,y)?P（x）)) D． (?x) (?P（x）??P（a）)
4．命题“所有的马都比某些牛跑得快”的符号化公式为（C） 假设：H（x）：x是马，C（y）：y是牛，F（x，y）：x跑得比y快。
A．(?x) (H（x）? (?y)((C（y）? F(x,,y))) B．(?x) (H（x）? (?y)((C（y）? F(x,,y))) C．(?x) (H（x）? (?y)((C（y）? F(x,,y))) D．(?y) (?x) (H（x）?((C（y）? F(x,,y))) 5．由前提：(?x) (P（x）?（Q（x）??R（x）），(?x) (P（x）?（R（x）?S（x）））, (?x) (P（x）??S（x））,则它的有效推论为 (C ) A．(?x) (P（x）??Q（x））B．(?x) (P（x）??Q（x）） C．(?x) (P（x）??Q（x）） D．(?x) (P（x）?Q（x）） 6．给定公式：(?x) (A（x）?B），与之等价的公式是 (B ) A．(?x)A（x）?BB．(?x)A（x）?B
C．?B?(?x)A（x） D．?B?(?x)?A（x） 7．下面推理中，正确的是（D）
3
A．（1）(?x) (F(x)?G(x)) P （2）F(a)?G(b) US B．（1）F(a)?G(b)P
（2）(?x)(F(x)?G(x)) EG C．（1）F(x )?G(b)P
（2）(?x)(F(x)?G(x)) EG D．（1）(?x) (F(x)?G(x)) P （2）F(y)?G(y) US
同步测试3、集合
一．填空：
1．设A??x3?x?12,x?N?,B??x1?x?15,x?2k,k?N?，则A?B??4,6,8,10?， A?B??2,4,5,6,7,8,9,10,11,12,14?，A?B??5,7,9,11?，A?B??2,5,7,9,11,12,14?。
1,2,3,4,5,6,7,8,9,10?的子集为A??2,4,6,8,10?，B??1,3,5,7,9?，2．设全集E??C??3,6,9?，则A?B??，B?C??3,9?，~A?~B??1,5,7?，A?C??1,5,7?，1,2,3,4,5,6,7,8,9,10?，B?C??1,5,6,7? A?B??3．设A、B是集合，求A、B之间的关系： A.如果A??a?,B??a,?a,b??，则A?B B.如果A??,B????，则A?B且A?B C.如果A??a?,B???,a,????，则A?B D.如果A????,B???,????，则A?B且A?B 4．设A???,a,b,?a,b??，求下列各式的结果：
A??a,b????,?a,b??；A??????a,b,?a,b??；??a,b???A??；??A??；?(A)??{?a,b?,?,a},{?,b,c},{?,{a,b},b},{a,b,{a,b}},{?,a,b,{a,b}}}??
??,{?},{a},{b},{?a,b?},{?,a},{?,b},{?,{a,b}},{a,b},{a,{a,b}},{b,{a,b}}}?A??a????,b,?a,b??；A???a,b?????,a,b?；?a,b??A??
,c??,B???a??,b??,c??，试写出：A?B???a,b??,c?,{b},{c}?，5．集合A???a,b??},{?c?},A?，{c}?，A?B???a,b??，A?B???a,b?,{a}?b??， ?(A)???,{?a,b?A?B??4
},{{b}},{?c?},{{a},{b}},{{b},{c}},{{c},{a}},B? ?(B)???,{?a?6．若集合A的元素的个数为A?10，则其幂集的元素的个数为??A??210?1024 7．确定下列各式： A.??????? B.??,?????????,???? C.??,?????{?}?????? D.??{?}?{?}
1,2?，确定下面集合： 8．设A??0,1?,B??1?B?{<<0,1>,1>,<<0,1>,2>,<<1,1>,1>,<<1,1>,2>} A.A???B.A2?B?{<<0,0>,1>,<<0,0>,2>,<<0,1>,1>,<<0,1>,2>, <<1,0>,1>,<<1,0>,2>,<<1,1>,1>,<<1,1>,2>} C.(B?A)2?{<<1,0>,<1,0>>,<<1,0>,<1,1>>,<<1,0>,<2,0>>, <<1,0>,<2,1>>,<<1,1>,<1,0>>,<<1,1>,<1,1>>,<<1,1>,<2,0>>,<<1,1>,<2,1>>, <<2,0>,<1,0>>,<<2,0>,<1,1>>,<<2,0>,<2,0>>,<<2,0>,<2,1>>, <<2,1>,<1,0>>,<<2,1>,<1,1>>,<<2,1>,<2,0>>,<<2,1>,<2,1>>} D.B2?A?{<<1,1>,0>,<<1,1>,1>,<<1,1>,0>,<<1,1>,1>,} 9．设A??a,b?，确定下面集合： A.?(A)???,{a},{b},{a,b}?
B.?(A)?A????,a?,?{a},a?,?{b},a?,?{a,b},a??
????,b?,?{a},b?,?{b},b?,?{a,b},b??
C.?(A)??(A)????,??,??,{a}?,??,{b}?,??,{a,b}??
???{a},??,?{a},{a}?,?{a},{b}?,?{a},{a,b}?? ???{b},??,?{b},{a}?,?{b},{b}?,?{b},{a,b}?? ???{a,b},??,?{a,b},{a}?,?{a,b},{b}?,?{a,b},{a,b}?? D.A??(A)???a,??,?a,{a}?,?a,{b}?,?a,{a,b}??
???b,??,?b,{a}?,?b,{b}?,?b,{a,b}??
5
二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。
1、若A?B?A?C，则B?C。（√） 2、若P?Q?Q,P?Q??，则P??。（√） 3、??????,????且??????,????。（√）
4、设A????，则有????????A??，且????????A??。（√） 5、设A、B为任意集合，则?(A?B)??(A)??(B)。（×） 6、若A?B?B，则A?B。（√） 7、对每一个集合A，有A???A?（√） 8、对每一个集合A，有{A}???A?（√） 9、对每一个集合A，有{A}???A?（×） 10、对每一个集合A，有A???A?（×） 11．若A?B?A?C，则B?C（×） 12．若A?B?A?C，则B?C（×）
13．对任意集合A、B、C，有(A?B)?C?(A?C)?B。（√） 14．对任意集合A、B、C，有(A?B)?C?(A?C)?(B?C)。（√）
15．对任意集合A、B、C、D，若A?B,C?D，则A?B?C?D。（√）
16．若A?B,B?C，则A?C（√） 17．如果A?B，且B?C，则A?C（×） 18．如果A?B，且B?C，则A?C（×） 19．若A?B，则A?C?B?C（√）
20．若A?B,C?D，则A?C?B?C（√）
21．若A?B，则~B?~A（√）
22．若A?B??，则A?~B,B?~A（√）
6
23．若A?B?E，则~A?B,~B?A（√）
24．设A、B、C是任意集合，则A?(B?C)?(A?B)?(A?C)。（√） 25．设A、B、C是任意集合，则A?(B?C)?(A?B)?(A?C)。（×） 26．设A、B是任意两个集合，若A??或B??则A?B??。（√） 27．设A、B、C是任意三个集合，则A?(B?C)?(A?B)?C。（×）
三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的括号内(多选不给分)。
1、对任意集合A、B、C，下面论断正确的是( A ) A．若A?B,B?C，则A?C B．若A?B,B?C，则A?C C．若A?B,B?C，则A?C D．若A?B,B?C，则A?C
,d,e??,f,g,h??，下面选项正确的是( C ) 2．设A???a,b,c??A．a?AB．?a,b,c??AC．??d,e???AD．??A 3．下列选项错误的是（B）
A．???B．???C．??{?}D．??{?} 4．在0（D）?之间填上正确的符号。
A．= B．?C．?D．? 5．设A?B??，则( C )
A．A??B．B??C．A?B D．A?B
1,??1?，下列选项错误的是( B ) 6．设A??1???A?B．??1???A?C．{??1}???A? D．{??1}???A? A．??7．设A????，下列选项错误的是( D )
}?????A?? D．{?,???}???A? A．??????A??B．????????A??C．{???8．幂集为?(???????)为( C )
7
{?},??,?????B．??,??,????,???? A．?C．??,??,????,?????,???? D．??,??,?????
9．对任意集合A、B、C、D，下列选项正确的是 ( D ) A．(A?B)?(C?D)?(A?C)?(B?D) B．(A?B)?(C?D)?(A?C)?(B?D) C．(A?B)?(C?D)?(A?C)?(B?D) D．(A?B)?C?(A?C)?(B?C)
10．设M??xf1?x??0?，N??xf2?x??0?，则方程f1?x??f2?x??0的解为( B ) A．M?NB．M?NC．M?N D．M?N
《 离散数学 》
同步测试卷4 关系
一．填空：
1．关系R是自反的，当且仅当关系矩阵中主对角线的元素均为1 ，在关系图中每一个节点均有自环。
2．关系R是反自反的，当且仅当关系矩阵中主对角线的元素均0 ，在关系图中每一个节点均无自环。
3．关系R是对称的，当且仅当关系矩阵为对称阵，在关系图中两个节点间若有有向弧必成对出现。
4．关系R是反对称的，当且仅当关系矩阵中若rij?1，则rji?0，在关系图中两个节点间若有有向弧必单条出现。
5．设集合X??1,2,3?，设关系R为X上的小于关系，则R=_{<1，2>，<1，3>，<2，3>}_，R?R??_{2，3}_，D?R??_{1，2}_。
6．一个二元关系的表达方式有三种，分别是、__序偶的集合_、_关系图_、_关系矩阵_。 7．设集合A??1,2,3,4?，R和S均为A上的二元关系，且R???1,2?,?3,4??,
S???2,3?,?4,1??，则R?S?_{<1，3>，<3，1>}_，S?R?_{<2，4>，<4，??2>}，R?S?R?_{<1，4>，<3，2>}，S?R?S?_{<2，1>，<4，3>}，R?S?R8
_?。
8．设A??a,b,c?上的二元关系R={
R具备__反对称性，可传递性__性质，不具备性质 _自反性，反自反性，对称性_。
,c,d,9．设A??ab?上的二元关系R={
10．设集合A仅含有三个元素，则：
A. 在A上可定义__512_______种不同的二元关系； B. 在A上可定义___64______种不同的自反关系； C. 在A上可定义___64______种不同的反自反关系； D. 在A上可定义____64_____种不同的对称关系； E. 在A上可定义____64_____种不同的反对称关系。
11. 设R是集合A??1,2,3,4,5,6,7,8,9,10?上的模7同余关系，则[2]R?_{2,9}_ 12．设A??a,b,c?上的偏序集???A?,??，则??A?的子集B={{a},{b}，{a，b},{b,c}，{}}的极大元是{
13．A?{2,3,4,5,6,8,10,12,24},R是A上整除关系，则A的极大元是 10，24 _，极小元是_2，3，5__
14．A?{1,2,3,?,12},R是A上整除关系。子集B?{2,4,6}，则B的最大元是无_，最
小元是_2_, 极大元是 4，6 _，极小元是_2__，上界是 12 _，下界是 1，2 _，上确界是_12__，下确界是_2_。
二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。
1. 一个不是自反的关系，一定是反自反的。（×）
2．集合A??a,b,c?上的任何二元关系R都不可能既是对称的又是反对称的.(×) 3、集合A??a,b,c?上的二元关系R={
?也是对称的.(√) 4. 若集合A上的关系R是对称的，则R5. 若R和S是集合A上的任意两个自反关系，则R?S也是自反的.(√) 6．若R和S是集合A上的任意两个反自反关系，则R?S也是反自反的.(×)
9
7. 若R和S是集合A上的任意对称关系，则R?S也是对称的.(×) 8．若R和S是集合A上的任意传递关系，则R?S也是转递的.(×)
9．设R:X?Y的关系，S:Y?Z的关系，若R的值域与S的定义域的交集是空集，
即R?R??D?S???，则R?S??(√)
10．设R:X?Y的关系，S:Y?Z的关系，若R?R??D?S???，则R?S?? (√) 11．设R1:X?Y,R2:Y?Z,R3:Y?Z，则R1?(R2?R3)?(R1?R2)?(R1?R3)(×) 12．有限集上的不同关系的数目是无限多个的。(×) 13．如果R是反对称的，则t?R?也是反对称的。(×) 14．如果R是可传递的，则s?R?也是可传递的。(×)
15．设A和B是任意两个集合，若?A?B,B?A?是A?B的一个划分，则有A?B(√) 16．给定一个非空集合，则它的划分是不唯一的。(√)
17．若R和S是集合A上的关系，则r?R?S??r?R??r?S?。(√) 18．若R和S是集合A上的关系，则s?R?S??s?R??s?S?。(√) 19．．若R和S是集合A上的关系，则t?R?S??t?R??t?S?。(×)
20．平面上的三角形集合上的三角形相似关系是等价关系。(√) 21．平面上的直线集合上的直线间的平行关系是等价关系。(√) 22．是等价关系一定是相容关系，反之亦然。(×)
23．若R和S是集合A上的等价关系，则R?S一定是等价关系(×)
24．若R和S是集合A上的两个相容关系，则R?S与R?S都是相容关系(×) 25．若R和S是集合A上的等价关系，则R?S一定是等价关系(√)
26．设?P,??是一个偏序集合，若最大成员存在，则该最大成员必然是极大成员。(√) 27．设?P,??是一个偏序集合，最小成员不一定存在，且若最大成员存在的话也不一定唯一。(×)
28．．设?P,??是一个偏序集合，极小成员是不唯一的，且极小成员之间是不可比的，它们处于哈斯图的同一层。(√)
29．设?P,??是一个偏序集合，P的某一个子集Q可能没有上界，如果有也是不唯一的。(√)
30．设?P,??是一个偏序集合，Q?P，如果y是Q的最大成员，则y必是Q的最小上界。(√)
10
三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内(多选不给分)。
1．若X??，则X上的空关系不具有的性质是( A ) A．自反性B．反自反性C．对称性D．可传递性 2．若X??，则X上的空关系不具有的性质是( D ) A．自反性B．对称性C．可传递性D．不可传递性
3．设A为一非空集合，则??A?上的包含关系不具有的性质是( B ) A．自反性B．对称性C．反对称性D．可传递性
4．设A为一非空集合，则??A?上的真包含关系不具有的性质是( A ) A．自反性B．反自反性C．反对称性D．可传递性 5．设A={1，2，3}上的关系如下，有传递性的有（ D ）
A．{<1，2 >，<2，1 >，<1，3>，<3，1>} B．{<1 ,3>，<3 ,1>}
C．{<1，2 >，<2, 3 >，<1，1>} D．{<1 ,2 >，<3，2 >}
6．设R和S都是集合X上的二元关系，则下述结论正确的是（A） A．若R和S都是自反的，则R?S也是自反的 B．若R和S都是对称的，则R?S也是对称的 C．若R和S都是反对称的，则R?S也是反对称的 D．若R和S都是可传递的，则R?S也是可传递的 7．集合A={1,2,3,6}上的整除关系具有的性质是（C）
A．自反性，对称性，可传递性B．反自反性，对称性，可传递性 C．自反性，反对称性，可传递性D．反自反性，反对称性，可传递性 8．实数集合R上的小于关系所具有的性质是（A）
A．反自反性，反对称性，可传递性B．自反性，反对称性，可传递性 C．反自反性，对称性，可传递性D．自反性，对称性，可传递性
9．设A={1，2，3}，关系R是A上的二元关系，且R={<1，2 >}，则关系R所具有的性质是（B）
A．自反性，反对称性，可传递性B．反自反性，反对称性，可传递性
11
C．自反性，对称性，可传递性D．反自反性，反对称性 10．集合X上的恒等关系所具有的性质是（A） A．自反性，对称性，反对称性，可传递性 B．反自反性，可传递性
C．反自反性，反对称性，可传递性D．都不是
?1?011．关系R所具有的关系矩阵MR???0??0010??101?，则关系R所具有的性质是（B）
010??001?A．自反的，对称的，可传递的B．自反的，反对称的，可传递的 C．自反的，对称的D．都不是
12．关系R的关系图如图所示（图略R={<1，2 >,<2，3 >,<3，1 >}），则关系R所具有的性质是（B）
A．反自反的，反对称的，可传递的B．反自反的，反对称的 C．反自反的，对称的，可传递的D．都不是
?是（B） ?是R的逆关系，则R?R13．设R是集合A上的偏序关系，RA．偏序关系B．等价关系C．相容关系D．都不是 14．集合A上的关系R是相容关系的必要条件是（B） A．自反的，反对称的B．自反的，对称的 C．反自反的，对称的D．自反的，可传递的
15．设R是集合X中的二元关系，则下列结论不正确的是（D）
?也是自反的B．若R是对称的，则R?也是对称的 A．若R是自反的，则R?也是可传递的D．都不是 C．若R是可传递的，则R16．设R1和R2都是集合X上的等价关系，则下列结论正确的是（A） A．R1?R2也是X上的等价关系B．R1?R2也是X上的等价关系 C．R1?R2也是X上的等价关系D．都不是
17．设R和S是集合A上的相容关系，则下列结论中不正确的是（C） A．R?S也是A上的等价关系B．R?S也是A上的等价关系
12
C．R?S也是A上的等价关系D．都不是
18.．设R是集合A上的关系，则下列结论中不正确的是（D）
?也是A上的偏序关系 A．R是A上的偏序关系，则R?也是A上的全序关系 B．R是A上的全序关系，则R?也是A上的拟序关系 C．R是A上的拟序关系，则RD．都不是
同步测试卷5：函数
一．填空：
1．设A??a,b,c?,B?{x,y,z},R,S,T:A?B的关系，且S???a,x?,?a,y??,R???a,x?,?b,y?,?c,y??,T???a,x?,?b,x?,?c,x??,则
R和T 可定义为A到B的函数。
2．设A?{1,2,3},B??a,b?,C?{x,y,z},f:A?B,g:A?C的函数，且有
f???1,a?,?2,b?,?3,b??,g???1,x?,?2,y?,?3,z??,则f是满射函数，g是
双射函数。若有h:B?C的函数，且h???a,x?,?b,x??,，则h是既非单射也非满射。
3．设R是实数集合，f:R?R，g:R?R，且f?x??x2,g?x??2x，则g?f?
2，f?g?4x。
4．设f:{0,1,2}?{a,b,c}的函数，且f???0,c?,?1,a?,?2,b??,，则f?1x2?
??c,0?,?a,1?,?b,2??。
5．设A??1,2,3?,f,g,h均为A到A的函数，即f,g,h:A?A，其中
f???1,1?,?2,1?,?3,1??,g???1,1?,?2,3?,?3,2??, h???1,3?,?2,1?,?3,1??,则g是单射，g是满射，g是双射。
6．设A??1,2,3?,R,S,T是A上的二元关系，且R???1,1?,?1,2?,?1,3??，
13
S???1,1?,?2,2?,?3,3??，T???1,1?,?2,3?,?3,2??，则这三个二元关系的逆关系中_S和T__可以定义为A到A的函数。
7．设A?{1,2,3,4,5},B??a,b?集，则可定义25?32种不同的从A到A的函数。 8．设I是整数集合，f:I?I，且f?x??x?2x，则f是__单射___函数
二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。
2. 若f和g均为从X到Y的函数，则f?g也是从X到Y的函数。（×）
2．设f:X?Y的函数，g:Y?Z的函数，若?g?f??1是从X到Z的函数，则f和g
均为单射函数。.(×)
3、设X?{a,b,c},Y?{0,1}，则从X到Y的函数共有23个。.(√) 4. 当X和Y都是有限集合时，若f:X?Y是满射函数，则X?Y.(√) 5. 当X和Y都是有限集合时，若f:X?Y是单射函数，则X?Y (√) 6．当X和Y都是有限集合时，若f:X?Y是双射函数，则X?Y .(√) 7. ．设X?{1,2,3,4},f:X?X的关系，且
f???1,4?,?2,1?,?2,3?,?3,2?,?4,4??,，则f是函数.(×)
8设X?{1,2,3,4},f:X?X的关系，且给定f???1,1?,?3,1?,?4,2??,，则f不是
从X到X的函数.(√)
9．设N是自然数集合，f:N?N，且f?j??j?2，则f是单射函数(√)
210．设N是自然数集合，f:N?N，且f?j??j(mod3)，则f是满射函数.(×)
三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内(多选不给分)。
1．函数的复合运算满足( B )
A．交换律B．结合律C．等幂律D．分配律 2．若f和g是满射函数，则g?f必是 ( C ) A．函数B．单射C．满射D．双射
14
3．若g?f是满射函数，则( C )
A．f必是满射B．f必是单射C．g必是满射D．g必是单射 4．若g?f是单射函数，则( B )
A．f必是满射B．f必是单射C．g必是满射D．g必是单射 5．若g?f是双射函数，则( D ) A．f，g必是满射B．f，g必是单射
C．f必是满射，g必是单射D．f必是单射，g必是满射 6．设f:X?Y的函数，当f是（ C ），f才有反函数fA．单射B．满射C．双射D．函数
7．设N是自然数集合，R是实数集合，f:N?R，且给定f?j??log10j，则（A） A．f是单射B．f是满射C．f是双射D．都不是
8．设X和Y都是有穷集合，且X?m,Y?n，则从X到Y有（D）种不同的双射函
数。（要设满足存在双射的前提条件！）
?1。
A．m?nB．m?nC．nmD．m!
同步测试卷6：代数系统初步
一．填空：
1．如果A是任意一个集合，*是一个二元运算，如果运算*对集合A 封闭，则称
幺元是__A，零元是?；对于∪运算的幺元是?，零元是_A_；
6．在代数系统
加法，则对于运算“＋”存在幺元_0_，对任意的元素的i?I,i的逆元为?i。 7．在代数系统
15
8．设?X,??和?Y,*?是两个代数系统，其中?和*都是二元运算。若存在函数
f:X?Y且对任意的a,b?X有f?a?b?f?a??f?b?，则称f是从?X,??到?Y,*?的同态。
9．给定代数系统U??X,*?，其中*是二元运算，E是X中的等价关系。如果等价关系E对运算*满足_代换_性质，则称E是代数系统U中的_同余_关系。 10．设
二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。
1．设
2．设
的子代数系统。.( √ )
3、非空集合A上的二元运算*封闭，则意味着对任意的a,b?A，有a?b?A。.( √ ) 4. 如果A是任意非空集合，*是一个二元运算，则称
6．设*是非空集合A上的一个二元运算，b?A且对任意的a?A有b*a?b，则b是A中关于运算*的左幺元。( ×)
7.．设
有a*b?a，则运算*是可结合的。.( √ )
8 设
有a*b?a，则运算*是可交换的。( ×)
9．在一个代数系统中，若每个元素都是等幂的，则运算一定是可结合的。 ( ×) 10．在一个代数系统中，若每个元素都是等幂的，则运算一定是可交换的。( ×)
11．若代数系统
(a*b)*(a*b)?(a*b)。 .( √ )
16
12．设*是A中可结合的二元运算，若a?A且是可逆的，则元素a一定是可约的。.( √ ) 13．在整数集合I上定义一个二元运算*为：a*b?(a?b)?2，其中a,b?I，则
14．在整数集合I上定义一个二元运算*为：a*b?(a?b)?2，其中a,b?I，则运算*具有幺元。.( √ )
15．设A为任意非空集合，则联合运算?对集合A的幂集?(A)是封闭的且A
是个幺元。( ×)
16．
17．设
18．设f是代数系统?X,??到?Y,*?同态，若运算?是可交换的，则运算?也是可交换的。( ×)
19．设E是代数系统?X,??的关系，若E对*满足代换性质，则E必是?X,??上的同余关系。( ×)
20．设Q是有理数集合，Q上的二元运算*的定义为：a*b?a?b?ab,a,b?Q，则运算*是可结合的。.( √ )
三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内(多选不给分)。
1．设A={1,2,…,10},下面的哪种运算对于集合A是不封闭的？ ( C ) A．a*b?max(a,b)B．a*b?min(a,b) C．a*b?a?bD．a*b?(a?b)(mod10)
2．在自然数N中，下列哪种运算是可结合的？( B ) A．a*b?a?bB．a*b?max(a,b) C．a*b?a?2bD．a*b?|a?b|
3．设A={0,1,2,3},下列的哪种运算是不可交换的？ ( D ) A．a*b?(a?b)(mod3)B．a*b?max(a,b) C．a*b?min(a,b)D．a*b?a?b
17
4．设A={0,1},下列哪种运算可使
5．设A={0,1},下列哪种运算不能使
6．设U=<{0,1},×>是一个代数系统，则（A）是U的子代数系统。 A．<{1},×>B．<{1},+>C．<{0},+>D．
7．设A={1,2,…,10},下面的哪种运算对于集合A是不封闭的？ ( D ) A．a*b?max(a,b)B．a*b?min(a,b)
C．a*b?a,b的最大公约数D．a*b?a,b的最大公倍数 8．在自然数N中，下列哪种运算是不可结合的？( C ) A．a*b?a?b?3B．a*b?min(a,b) C．a*b?a?2bD．a*b?(ab)(mod3)
9．设Q是有理数集合，Q上的运算*的定义为：a*b?a?b?ab,a,b?Q，则运算*（B）。
A．不可交换的 B．可交换且可结合的 C．不可结合的 D．可交换但不可结合
10．设?X,??到?Y,*?是两个代数系统，f是?X,??到?Y,*?的同态，则（D） A．运算?与运算*性质完全相同 B．运算?具有的性质，运算*不一定具有 C．运算*与运算?性质完全相同D．运算*具有的性质，运算?不一定具有
《 离散数学 》
同步测试卷7:半群、独异点与群
一．填空：
1．设
的子半群。
2．设 18 e>是 3．给定一个半群U= 5．设 6．设 8．集合Zm?{[0],[1],[2],?,[m?1]}，在Zm上定义运算?m为：对任意的[i],[j]?Zm 有：[i]?m[j]?[(i?j)(modm)]则?Zm,?m?幺元是_0_，[i]?Zm逆元是[m?i]。 9．设H是有限群G的子群，则H的阶必__整除__G的阶。 10．一个由a生成的循环群 周期（或阶）。 二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。 3. 设 2．设 5. 设 交换子含幺半群。.(√) 6．设 7. 设 换半群。.(√) 8．若半群 9．若半群 10．若半群 11．若半群 19 12．循环半群 13．如果 16．如果 18．设f:X?则有：如果U是个阿贝尔群，Y是群U??X,*?到V??Y,*?的群同构。则V也一定是个阿贝尔群。(√) 19．非循环群的每一个子群也必是个非循环群。(×) 20．设I为整数集合，定义I上的二元运算为：对任意的x,y?I有x*y?x?y?2，则 三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内(多选不给分)。 1．下列运算中，哪种运算关于整数集合不能构成半群？( D ) A．a*b?max(a,b)B．a*b?b C．a*b?2abD．a*b?|a?b| 2．R为实数集合，运算*的定义为：对任意的x,y?R有x*y?x?|y|，则代数系统 ?R,*?是( A ) A．半群B．独异点C．群D．阿贝尔群 3．设集合A={0，1}，下列哪种运算可使 4．在自然数N上，下列哪种运算可使 5．设Q是有理数集合，Q上的运算*定义为a*b?a?b?2，则?Q,*?不能构成（ C ） 20 A．半群B．群C．循环群D．阿贝尔群 6．设集合Zm?{[0],[1],[2],?,[m?1]}，在Zm上定义运算?m为：对任意的 [i],[j]?Zm有：[i]?m[j]?[(i?j)(modm)]，则?Zm,?m?不能构成（D） A．半群B．群C．循环群D．置换群 7．下列运算中，哪种运算关于整数集合不能构成半群（A） A．a*b?|a?b|B．a*b?b C．a*b?2abD．a*b?max(a,b) 8．设Q是有理数集合，则?Q,*?（其中*为普通的乘法运算）不能构成（ A ） A．群B．独异点C．半群D．减缓半群 9．设I是整数集合，+为一般的加法运算。定义函数f:I?I，则下列定义的函数中，哪一个不是群?I,??的自同态？（C） A．f?x??2xB．f?x??500x C．f?x??|x|D．f?x??0 10．6阶群的任何非平凡子群一定不是（C）阶。 A．2 B．3 C．4 D．6 《 离散数学 》 同步测试卷8:环和域 一．填空： 1．设 a?b。其中0是加法幺元，?a是a的加法逆元，?b是b的加法逆元。 3．设 其中0是加法幺元，也等价于乘法消去律，，即对于c?0和c?a?c?b必有 21 a?b。 二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。 4. 设 4. 设I是整数集合，Q是有理数集合，R是实数集合，C是复数集合，+和×是普通的加法运算和乘法运算，则 6．整数环 8．设 是加法幺元）.(√) 9．若 10．设 b为零因子。其中0是加法幺元。.(√) 11．若 13．整环和域都至少含有两个元素。(√) 14．是域一定是整环。(√) 15．整数环 16．有理数环 三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内(多选不给分)。 1．设I是整数集合，+和×分别是普通的加法和乘法运算，则 A．整数环 22 A．奇数B．偶数C．素数D．都不是 5．环 6．设+和×分别是普通的加法和乘法运算，则下列代数系统 A．S?{xx?a?b3,a,b?Q}B．S?{xx?2n,n?I} C．S?{xx?2n?1,n?I}D．S?{xx?0,x?I} 同步测试卷9:格与布尔代数 一．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。 5. 设??S?是给定集合S的幂集，则???S?,?,??是一个代数格。（√） 2．设 a1a2a5a3a6a8图9-11S1={a1,a2,a3,a4}，则 3、仅有1个、2个或3个元素的格，分别同构于1个、2个或3个元素的链。( √) 4. 若 a4a76．设 9．设非空有限集S，则???S?,?,??是分配格。 ( √ ) 10．设 11．设 abc,,S,?12．设A??格同构。( √ ) 是30的所有因子的集合，D是S上的整除关系，则??(A),??与 13．设 14．设 则b不一定等于c。( × ) 23 15．设S是非空集合，则???S?,?,?,~,?,S?是一个布尔代数，且对任意的 A???S?,~A?S?A。( √ ) 三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内(多选不给分)。 1．设N是自然数集，≤是定义在N上的小于等于关系，则 (a)(b)图9-12(c)(d) 3．图9-12所示的偏序集中不能构成格的是( A ) (a)(b)图9-13(c)(d) 4．下述偏序集中能构成格的是( D ) A．A?{a,b,c,d},??{?a,a?,?b,a?,?b,b?,?c,b?,?c,c?,?d,a?,?d,b?, ?d,c?,?d,d?} B．A?{a,b,c,d,e},??{?a,a?,?b,a?,?b,b?,?c,b?,?c,c?,?d,b?,?d,d?, ?e,b?,?e,c?,?e,d?,?e,e?} C．A?{a,b,c,d,e,f,g},??{?a,a?,?b,a?,?b,b?,?c,b?,?c,c?,?c,d?, 24 ?d,a?,?d,d?,?e,e?,?f,e?,?f,f?,?g,f?,?g,g?} D．A?{1,2,3,4}, ??{?1,1?,?1,2?,?1,3?,?1,4?,?2,2?,?2,4?,?3,3?,?3,4?,?4,4?} 5．下述偏序集中能构成格的是( D ) A．?N,??B．?I,??C．?S12,D?D．???A?,?? 6．图9-14所示的偏序集中能构成分配格的是( C ) (a)(b)(c)(d)图9-14 7．设?L,??是一条链，且L?3，则?L,??( C ) A．是布尔代数B．是有补格 C．是分配格D．都不是 8．设A为一个集合，???A?,??为有补格，??A?中每个元素的补元( A．存在且唯一B．不存在 C．存在但不唯一D．可能存在 9．在有界格中，若有一个元素有补元，则补元( C ) A．必唯一B．不惟一C．不一定唯一D．都不是 10．设?L,??是一个有界格，它也是有补格，只要满足( B ) A．每一个元素都只有一个补元B．每一个元素都至少有一个补元 C．每一个元素都有多个补元D．都不是 11．图9-15所示的偏序集中能构成有补格的是( A ) 25 A ) (a)(b)图9-15(c)(d) 12．设?L,?1?和?S,?2?是两个格，f:L?S是双射，则对任意的a,b?L， ?L,?1?和?S,?2?格同构的( C )是a?1b?f(a)?2f(b) A．必要条件B．充分条件C．充分必要条件D．都不是 三．填空： 1．设?L,??是一个有界格，其哈斯图如图9-16所示，则e的补元是b，f的 补元是无，该偏序集的全上界h，全下界是i。 2．设?L?,?L2?{a,b,d,f}，是一个格，其哈斯图如图9-17所示，取L1?{a,b,c,d}， L3?{b,c,d,f}，则L1是?L,??的子格。 3．设?A,??是格，其中A?{1,2,3,4,6,8,12,24},?为A上的整除关系，其对应的哈斯 图如图9-18所示，则1的补元是 24，2的补元是无，3的补元是 8，4的补元是无，6的补元是无，8的补元是 3，12的补元是无，24的补元是 1。 hacefi图9-16abbdg248c12631图9-18deg图9-174f2 4．设 26 同步测试卷10:图的基本概念 一．填空： 1．一个无向图表示为G= 2．设无向图G中有12条边，已知G中度为3的结点有6个，其余的结点度均 小于3，则G中至少有 9 个结点。 3．设G=(n,m)是简单图，v是G中一个度为k的结点，e是G中的一条边，则G – v中有n?1个结点，m?k条边；G – e中有n个结点，m?1条边。 4．设G是个有向图，当且仅当G中有一条经过每一个结点的路径时，G才是 单向连通图。 5．设图G= 若E中的每条边都是_有向边__，则称图G为有向图。 6．设图G中无自环和无平行边，则称图G为简单图。 7．设G是个无自环的无向图，其中有2个结点的度数为4，其余结点的度为2， 有6条边。则G中共有_ 4 个结点。因此，G是个多重边_图。 8．一个无向图G有16条边，若G中每一个结点的度均为2，则G有16个结点。 9．设G是个具有5个结点的简单无向完全图，则G有__10_条边。 10．设G是个具有5个结点的简单有向完全图，则G有_20_条边。 11．设G是个n阶简单有向图，G?是G的子图，已知G?的边数E??n?n?1?， 则G的边数m为n?n?1?。 12．35条边，每个结点的度数至少是3的图最多有__23_个结点。 二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。 6. 设图G= 2．设图G= 5. 在简单无向图G的邻接矩阵A?aij??n?n中，结点vi所对应的行中1的个数等于vi的出 ??n?n中，结点vi所对应的行中1的个数等于vi的 度。.(√) 6．若无向图中恰有两个奇结点，则这两个奇结点比相互可达。.(√) 7. 若有向图中恰有两个奇结点，则必有从一个结点到另一个结点可达或相互可达。.(×) 8．对任何一个图，其奇结点的个数一定是偶数。.(√) 9．在有向图中，结点间的可达关系一定是个等价关系。.(×) 10．割边（或桥）一定是悬挂边。.(×) 27 11．悬挂边一定是割边（或桥）。.(√) 12．悬挂点一定是割点。(×) 13．割点一定是悬挂点。 (×) 14．有向图中的每个结点都恰处于一个单向分图中。(×) 15．在完全无向图中，任意两个点都是邻接结点。(√) 16．如果无向图G的邻接矩阵中所有元素均为零，则G必为零图。(√) 17．如果简单无向图G的邻接矩阵中除主对角线外所有元素均为“1”，则G一定是完全图。(×) 18．如果G是一个非连通无向图，则G的一个连通子图称为G的一个分支。(×) 19．如果一个简单无向图G连通且无回路，则G中的每条边必为割边。(√) 20．具有n个结点的连通图中，至少有n条边。(×) 三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内(多选不给分)。 1．在具有n个结点的无向连通图中，( B ) A．恰好有n条边B．至少有n?1条边 C．最多有n条边D．至少有n条边 2．设G= 3．设G= 4．设G= 5．如果无向图G中( D )，则称G是个简单无向图。 A．无回路B．无自环C．五多重边D．无自环且无多重边 6．设G=(n,m)，若G中每个结点的度数不是k就是k?1，则G中度数为k的结点 个数为( A ) A．n?k?1??2mB．n?n?1?C．nkD． n 27．任何无向图G中结点间的可达关系是( B ) A．偏序关系B．等价关系C．相容关系D．逆序关系 8．设有向图G= 28 A．强连通图B．单向连通图 C．弱连通图D．非连通图 9．设有向图G= A．强连通图B．单向连通图 C．弱连通图D．非连通图 10．设有向图G= 12．设G是具有n个结点的3次正则图，则结点数n( B ) A．必是奇数B．必是偶数 C．或者是奇数或者是偶数D．必等于6 13．无向图G中的边e是G中的割边的充要条件是：e( C ) A．是悬挂边B．不是多重边 C．不包含在G的任一简单回路中 D．不包含在G的某一回路中 14．设无向图G中有5条边，已知G中度为2的结点有2个，其余结点的度为3，则G中共有( C )个结点。 A．6B．6 C．4D．10 15．图G与G?的结点和边分别存在一一对应的关系是G与G?同构的( B ) 29 A．充分条件B．必要条件 C．充要条件D．既不是充分条件也不是必要条件 《 离散数学 》 同步测试卷11:特殊图与应用 一．填空： 1．一个连通无向图G是欧拉图，当且仅当G中所有结点的度数为偶数。 2．在一个连通无向图G是欧拉图中，当且仅当结点vi和vj的度为奇数，其余结点的度均为偶数，结点vi和vj之间才存在欧拉路径。 3．设G= 的边集M为G的一个匹配。 4．无向图G有生成树的充要条件是G连通。 5．如果T是无向图G的一棵生成树，则T中的边称为树枝_，属于G但不属于 T的边称为T的_连枝（弦）_。 6．在根树中，从根到结点v的距离称为该结点的层次，从根到叶结点的最大距 离称为树的高度。 7．设G是(n,m)无向简单连通，用避回路法求G的一棵生成树，必须在G中选 择n?1条边且不构成回路。 8．设G是(n,m)无向简单连通，用破回路法求G的一棵生成树，必须在G中去 掉m?n?1。 9．连通图G是一棵树，当且仅当G中每一条边均为_割边_。 10．无向图G是由k?k?2?棵树组成的森林，至少要添加k?1条边才能使G成为一棵树。 11．设A是根树T的邻接矩阵，则矩阵A中行全为0所对应的结点为_树叶__， 列全为0所对应的结点为_树根_。 12．设A是一棵k元树的邻接矩阵，则矩阵A的所有行中1的个数最多为k个。 13．设G是个连通无向图，e是G中的一条边，如果边e包含在G的任何一棵 生成树中，则e必为G的一条_割边，不包含在G的任何生成树中的边一定是_自环。 14．设T是具有n个结点的一棵完全二元树，则T中树叶数为 n?1。 230 n?1，内结点数2为 二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。 7. 欧拉路径一定是简单路径。（√） 2．哈密顿路径一定是简单路径。（×） 3、若有向图G是强连通图，则G一定是个欧拉图。（×） 4. 若有向图G是欧拉图，则G必是个强连通图。.( √ ) 5. 如果能将无向图G画在平面上，若边与边之间有交叉，则G必为非平面图。.( × ) 6．一个连通赋权图的最小生成树不是唯一的。.( √ ) 7. 若G是个连通图，且e是G的割边，则边e必包含在G的每棵生成树中。( √ ) 8．设图G是有n个结点、n?1条边的无向图，则G一定是树。( × ) 9．设G=(n,m)是个无向图，若去掉任何一条边G的支有所增加，则G必为树。( × ) 10．设G=(n,m)是个无向图，若G无回路且m?n?1，则G必为根树。( √ ) 11．有向图G仅有一个结点的入度为0，其余结点的入度均为1，则G必为根树。( × )？ 12．若无向图G=(n,m)连通，则必有m?n。( × ) 13．若无向图G=(n,m)连通，则必有m?n?1。 ( √ ) 14．在完全二元树中，若有t片树叶，则其边的总数为E?2t?1。( × ) 15．在完全二元树中，若有t片树叶，则其分支结点数为i?t?1。( √ ) 16．若无向图G中的每条边都是割边，则G必为树。( × ) 17．带权为?1,?2,?,?t的最优二叉树是唯一的。( × ) 18．若无向图G中任意两点间恰好有一条路径，则G必是树。( √ ) 19．若森林F??n,m?是由k棵树组成，则m?n?k。( √ ) 20．设图G是个连通无向图，则G的生成子图，一定是G的生成树。( × ) 三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内(多选不给分)。 1．给定一个无向图G，如果( D )，则G必是个欧拉图。 A．G中每个结点的度均为偶数B．G是连通图 C．G是个简单完全图D．G连通且每个结点的度均为偶数 2．设G是个(n,m)简单连通平面图，若G的每个区至少由3条边围成，则有( A ) A．m?3n?6B．m?2n?4C．m?5n?10D．m?6n?12 3．设G=(n,m)是连通赋权图，如果用破圈法求G的一个生成树，则必须从G中去掉( D )条边。 A．n?1B．m?n?1C．m?1D．m?n?1 4．设G=(n,m)是连通赋权图，如果用避回路求G的一个生成树，则必须从G中选取( A )条边。 31 A．n?1B．m?n?1C．m?1D．m?n?1 5．具有n个结点的无向图G，如果( D )，则G一定是树。 A．G中恰有n?1条边B．G中每对结点间都相互可达 C．G中的每条边都是割边D．G连通但去掉一条边就不连通 6．T为完全二元树，有t片树叶，m条边，则有( C )。 A．m?2?t?1?B．m?2?t?1?C．m?2?t?1?D．m?2?t?1? 7．5个结点构成的根树中，其元数m最多为( C ) A．2B．3 C．4D．5 8．一棵树中有2个4度结点，3个3度结点，其余的都是树叶，则该树的树叶总数为( C ) A．7B．8 C．9D．10 9．一棵完全k元树中有t片树叶，i个分支结点，则有关系式( B ) A．i?t?1B．?k?1?i?1?tC．?k?1?i?tD．?k?1?t?t?i 10．一棵完全k元树中有t片树叶，m条边，则有关系式( C ) A．m? k?t?1?kB．m?k?t?1??1C．m?k?t?1?k?1D．m?k?t?1? 32