试卷二十三试题与答案
一、单项选择题：（每小题1分，本大题共10分）
1．命题公式P?(Q?P)是（ C ）。
A、 矛盾式； B、可满足式； C、重言式； D、等价式。 2．下列各式中哪个不成立（ A ）。 A、?x(P(x)?Q(x))??xP(x)??xQ(x)； B、?x(P(x)?Q(x))??xP(x)??xQ(x)； C、?x(P(x)?Q(x))??xP(x)??xQ(x)； D、?x(P(x)?Q)??xP(x)?Q。
3．谓词公式?x(P(x)??yR(y))?Q(x)中的 x是（ C ）。 A、自由变元； B、约束变元；
C、既是自由变元又是约束变元； D、既不是自由变元又不是约束变元。 4．在0 ?之间应填入（ D ）符号。 A、= ； B、?； C、?； D、?。 5．设< A ，
? > 是偏序集，B?A，下面结论正确的是（ D ）。 A、B的极大元b?B且唯一； B、B的极大元b?A且不唯一； C、B的上界b?B且不唯一； D、B的上确界b?A且唯一。 6．在自然数集N上，下列（ B ）运算是可结合的。
（对任意a,b?N）
A、a?b?a?b； B、a?b?max(a,b)； C、a?b?a?5b； D、
a?b?a?b。
7．Q为有理数集N，Q上定义运算*为a*b = a + b – ab ,则
8．给定下列序列，（ B ）可以构成无向简单图的结点度数序列。 A、（1，1，2，2，3）； B、（1，1，2，2，2）；
C、（0，1，3，3，3）； D、（1，3，4，4，5）。
9．设G是简单有向图，可达矩阵P(G)刻划下列 （ C ）关系。
A、点与边； B、边与点； C、点与点； D、边与边。
10．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（ A、5； B、7； C、9； D、8。
D ）。 C ）。
二、填空：（每空1分，本大题共15分）
1．在自然数集中，偶数集为N1、奇数集为N2，则N1?N2= ；
N1?N2 = 。
2．设X?{1,2,3,4},R?{?1,2?,?2,4?，?3,3?}，则
r (R) = ；s (R) = ；t (R) = 。
3．设R为集合A上的等价关系，对?a?A，集合[a]R= ， 称
为
元
素
a
形
成
的
R
等
价
类
，
[a]R??，因
为 。
4．任意两个不同小项的合取为 ，全体小项的析取式为 。
5．设Q(x):x为偶数，P(x):x为素数，则下列命题：（1）存在唯一偶素数；（2）至多有一个偶素数；分别形式化：（1） ；
（2） 。
6．设T为根树，若 ，则称T为m元树；
若 则称T为完全m叉树。
7．含5个结点，4条边的无向连通图（不同构）有 个，
它们是 。
三、判断改正题：（每小题2分，本大题共20分）
1．命题公式(A?(A?B))?B是一个矛盾式。 （ × ） 2．任何循环群必定是阿贝尔群，反之亦真。 （ × ） 3．根树中最长路径的端点都是叶子。 （ × ） 4．若集合A上的关系R是对称的，则R也是对称的。 （ √ ） 5．数集合上的不等关系（≠）可确定A的一个划分。 （ × ） 6．设集合A、B、C为任意集合，若A×B = A×C，则B = C。 （ √ ） 7．函数的复合运算“。”满足结合律。 （ √ ） 8．若G是欧拉图，则其边数e合结点数v的奇偶性不能相反。 （ × ） 9．图G为（n , m）图，G的生成树TG必有n个结点。 （ √ ） 10．使命题公式P?(Q?R)的真值为F的真值指派的P、Q、R值分别是T、F、F。 （ √ ）
?1
四、简答题（每小题5分，本大题共25分）
1．设?H,??和?K,??都是群?G,??的子群，问?H?K,??和?H?K,??是否是
?G,??的子并说明理由。
3，4，9}，B?{2，4，7，10,12}，从A到B的关系 2．设A?{2，R?{?a,b?a?A,b?B,且a整除b}，试给出R的关系图和关系矩阵，并说明此
关系是否为函数？为什么？
3．设?S,??是半群，OL是左零元，对任x?S,x?OL是否是左零元？为什么？
4．某次会议有20人参加，其中每人至少有10个朋友，这20人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？（理由）
5．通过主合取范式，求出使公式?(?P?Q)?R的值为F的真值指派。
五、证明题：（共30分）
1．设R为集合A上的二元关系，如果R是反自反的和可传递的，则R一定是反对称的。
2．试证明若?G,??是群，H?G，且任意的a?H，对每一个x?G，有a?x?x?a，则?H,??是?G,??的子群。
3．设G是每个面至少由k（k?3）条边围成的连通平面图，试证明为结点数，e为边数。
4．符号化下列各命题，并说明结论是否有效（用推理规则）。任何人如果他喜欢美术，他就不喜欢体育。每个人或喜欢体育，或喜欢音乐，有的人不喜欢音乐，因而有的人不喜欢美术。 答案
e?k(v?2)k?2，其中v一、单项选择题：
题号 1 2 3 4 5 6 7 8 9 10 答案 C A C D D B D B C C 二、填空题： 1．N2 ? , 2 ? , 4 ? , 3 ? , 1 ? , 2 ? , 4 ?r ( R ) ?{ 1, ?2, ?3, ?1, ?2, ?4} ，;?。 2．
s(R)?{?1,2?,?2,4?,?3,3?,?2,1?,?4,2?}， R?R?R?{?1,4?,?3,3?}，
R?R?R?{?3,3?}，R?R?R?{?3,3?}，
所以， t(R)?{?1,2?,?2,4?,?3,3?,?1,4?}。
3．
32432[a]R?{xx?A,aRx}；a?[a]R。4．永假式（矛盾式）
，永真式（重言式）。
5．（1）?x((Q(x)?P(x))??y(Q(y)?P(y)?x?y))。 （2）?x?y(Q(x)?P(x)?Q(y)?P(y)?x?y)。
6．每个结点的出度都小于等于m；除叶子外，每个结点的出度都等于m。 7．3。
三、判断改正题：
1．× 命题公式(A?(A?B))?B是一个重言式。 2．× 任何循环群必定是阿贝尔群，但反之不真。 3．× 根树中最长路径的端点不都是叶子。
4．√ 5．× ≠不能确定A的一个划分。 6．√ 7．√ 8．× 欧拉图其边数e和结点数v的奇偶性可以相反。 9．√ 10．√
四、简答题
1．解：
?H ?K , ?? ?G,??是 的子群，?H?K,??不一定是?G,??的子群。
??a,b?H?K,则a,b?H,a,b?K,由?H,??和?K,??都是?G,??的子群，
?a?b?1?H且a?b?1?K,?a?b?1?H?K,??H?K,??是?G,?如：G = {1，5，7，11}，?：模12乘，则?G,??为群。且H = {1，5}，K = {1，7}，
的子群。
?H,??和?K,??皆为?G,??的子群，但H?K?{1,5,7}，
相关推荐：
loading