>>}
C．{<<1,a>,
>,<<1,b>,
>,<<2,a>,
>,<<2,b>,
>}
D．{{1,2},{a,b},{
}}
4．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}，则集合B的最大元、最小元、上界、下界依次为___d___．
A．8、1、6、1B．8、2、8、2
C．6、2、6、2D．无、2、无、2
5．有5个结点的无向完全图K5的边数为___a___．
A．10B．20
C．5D．25
6．设完全图K
有n个结点（n≥2），m条边，当___b___时，K
中存在欧拉回路．
A．n为偶数B．n为奇数
C．m为偶数D．m为奇数
7．一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，则T有__c___个顶点．
A．3B．8
C．11D．13
8．命题公式（P∨Q）→R的析取范式是___b___．
A．（P∧Q）∨RB．（P∨Q）∨R
C．（P∧Q）∨RD．（P∨Q）∨R
9．下列等价公式成立的是___b___．
A．PQPQB．P（QP）P（PQ）
C．P（PQ）QD．Q（PQ）Q（PQ）
10．谓词公式
的类型是__c____．
A．蕴涵式B．永假式
C．永真式D．非永真的可满足式
二、填空题（每小题3分，本题共15分）
6．命题公式
的真值是 T（或1） ．
7．若图G=中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为W|S|．
8．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素0，则该序列集合构成前缀码．
9．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为5．
10．（x）（P（x）→Q（x）∨R（x，y））中的自由变元为R（x，y）中的y
6．若集合A的元素个数为10，则其幂集的元素个数为 1024．
7．设A={a，b，c}，B={1，2}，作f：
A→B，则不同的函数个数为8．
8．若A={1,2}，R={|xA,yA,x+y=10}，则R的自反闭包为{<1,1>,<2,2>}．
9．结点数v与边数e满足e=v-1关系的无向连通图就是树．
6．设集合A＝{a，b}，那么集合A的幂集是{,{a,b},{a},{b}}．
7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有2个．
8．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去4条边后使之变成树．
9．设连通平面图G的结点数为5，边数为6，则面数为3．
10．设个体域D＝{a,b}，则谓词公式（x）A（x）∧（x）B（x）消去量词后的等值式为（A（a）∧A（b））∧（B（a）∨B（b））．
6．设集合A={0,1,2,3}，B={2,3,4,5}，R是A到B的二元关系，
则R的有序对集合为{<2,2>，<2,3>，<3,2>}，<3,3>．
7．设G是连通平面图，v,e,r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r=2．
8．设G＝是有6个结点，8条边的连通图，则从G中删去3条边，可以确定图G的一棵生成树．
9．无向图G存在欧拉回路，当且仅当G连通且所有结点的度数全为偶数
10．设个体域D＝{1,2}，则谓词公式
消去量词后的等值式为A
（1）A
（2）
6．命题公式
的真值是 T（或1） ．
7．若图G=中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为W|S|．
8．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素0，则该序列集合构成前缀码．
9．已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为5．
10．（x）（P（x）→Q（x）∨R（x，y））中的自由变元为R（x，y）中的y
6．若集合A的元素个数为10，则其幂集的元素个数为 1024．
7．设A={a，b，c}，B={1，2}，作f：
A→B，则不同的函数个数为8．
8．若A={1,2}，R={|xA,yA,x+y=10}，则R的自反闭包为{<1,1>,<2,2>}．
9．结点数v与边数e满足e=v-1关系的无向连通图就是树．
10．设个体域D＝{a,b,c}，则谓词公式（x）A（x）消去量词后的等值式为A（a）∧A（b）∧A（c）
6．若集合A={1，3，5，7}，B={2，4，6，8}，则A∩B=空集（或）．
7．设集合A={1，2，3}上的函数分别为：
f={<1,2>,<2,1>,<3,3>,}，g={<1,3>,<2,2>,<3,2>,}，则复合函数gf={<1,2>,<2,3>,<3,2>,}
8．设G是一个图，结点集合为V，边集合为E，则G的结点度数之和为2|E|（或“边数的两倍”）
9．无向连通图G的结点数为v，边数为e，则G当v与e满足e=v-1关系时是树．
10．设个体域D＝{1,2,3}，P（x）为“x小于2”，则谓词公式（x）P（x）的真值为假（或F，或0）．
6．设集合A={2,3,4}，B={1,2,3,4}，R是A到B的二元关系，
则R的有序对集合为{<2,2>，<2,3>，<2,4>，<3,3>}，<3,4>，<4,4>}
7．如果R是非空集合A上的等价关系，aA，bA，则可推知R中至少包含，等元素．
8．设G＝是有4个结点，8条边的无向连通图，则从G中删去5条边，可以确定图G的一棵生成树．
9．设G是具有n个结点m条边k个面的连通平面图，则m等于n+k2
10．设个体域D＝{1,2}，A（x）为“x大于1”，则谓词公式
的真值为真（或T，或1）
11．设集合A={1,2,3}，用列举法写出A上的恒等关系IA，全关系EA：
IA=__IA={<1,1>,<2,2>,<3,3>}；
EA={<1,1>,<1,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}
12．设集合A＝{a，b}，那么集合A的幂集是{,{a},{b},{a,b}}
13．设集合A={1,2,3}，B={a,b}，从A到B的两个二元关系R={<1,a>,<2,b>,
<3,a>}，S={<1,a>,<2,a>,<3,a>}，则R-S=_R-S={<2,b>}．
14．设G是连通平面图，v,e,r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r=2．
15．无向连通图G是欧拉图的充分必要条件是结点度数均为偶数．
16．设G＝是有6个结点，8条边的连通图，则从G中删去3条边，可以确定图G的一棵生成树．
17．设G是完全二叉树，G有15个结点，其中有8个是树叶，则G有____14___条边，G的总度数是___28_____，G的分支点数是____7____．
18．设P，Q的真值为1，R，S的真值为0，则命题公式
的真值为___0_____．
19．命题公式
的合取范式为
析取范式为
20．设个体域为整数集，公式
真值为___1_____．
11．设集合A={1,2,3,4}，B={3,4,5,6}，则：
___{3,4}_____，
_____{1,2,3,4,5,6}_____．
12．设集合A有n个元素，那么A的幂集合P（A）的元素个数为．
13．设集合A={a,b,c,d}，B={x,y,z}，R={,,,,}
则关系矩阵MR＝
．
14．设集合A={a,b,c,d,e}，A上的二元关系R={,,}，S={,
,}，则R·S={,,}
15．无向图G存在欧拉回路，当且仅当G连通且__所有结点的度数全为偶数
16．设连通平面图G的结点数为5，边数为6，则面数为3．
17．设正则二叉树有n个分支点，且内部通路长度总和为I，外部通路长度总和为E，则有E=___I+2n
18．设P，Q的真值为0，R，S的真值为1，则命题公式
的真值为_____1___．
19．已知命题公式为G＝（PQ）R，则命题公式G的析取范式是（PQ）R
20．谓词命题公式（x）（P（x）→Q（x）∨R（x，y））中的约束变元为___x___．
三、逻辑公式翻译（每小题4分，本题共12分）
11．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式．
设P：
所有人今天都去参加活动，Q：
明天的会议取消，（1分）
PQ．（4分）
12．将语句“今天没有人来．”翻译成命题公式．
设P：
今天有人来，（1分）
P．（4分）
13．将语句“有人去上课．”翻译成谓词公式．
设P（x）：
x是人，Q（x）：
x去上课，（1分）
（x）（P（x）Q（x））．（4分）
11．将语句“如果你去了，那么他就不去．”翻译成命题公式．
设P：
你去，Q：
他去，（1分）
PQ．（4分）
12．将语句“小王去旅游，小李也去旅游．”翻译成命题公式．
设P：
小王去旅游，Q：
小李去旅游，（1分）
PQ．（4分）
13．将语句“所有人都去工作．”翻译成谓词公式．
设P（x）：
x是人，Q（x）：
x去工作，（1分）
（x）（P（x）Q（x））．（4分）
11．将语句“他不去学校．”翻译成命题公式．
设P：
他去学校，（1分）
P．（4分）
12．将语句“他去旅游，仅当他有时间．”翻译成命题公式．
设P：
他去旅游，Q：
他有时间，（1分）
PQ．（4分）
13．将语句“所有的人都学习努力．”翻译成命题公式．
设P（x）：
x是人，Q（x）：
x学习努力，（1分）
（x）（P（x）Q（x））．（3分）
11．将语句“尽管他接受了这个任务，但他没有完成好．”翻译成命题公式．
设P：
他接受了这个任务，Q：
他完成好了这个任务，（2分）
PQ．（6分）
12．将语句“今天没有下雨．”翻译成命题公式．
设P：
今天下雨，（2分）
P．（6分）
11．将语句“他是学生．”翻译成命题公式．
设P：
他是学生，（2分）
则命题公式为：
P．（6分）
12．将语句“如果明天不下雨，我们就去郊游．”翻译成命题公式．
设P：
明天下雨，Q：
我们就去郊游，（2分）
则命题公式为：
PQ．（6分）
11．将语句“今天考试，明天放假．”翻译成命题公式．
设P：
今天考试，Q：
明天放假．（2分）
则命题公式为：
P∧Q．（6分）
12．将语句“我去旅游，仅当我有时间．”翻译成命题公式．
设P：
我去旅游，Q：
我有时间，（2分）
则命题公式为：
PQ．（6分）
⑴将语句“如果明天不下雨，我们就去春游．”翻译成命题公式．
⑵将语句“有人去上课．”翻译成谓词公式．
⑴设命题P表示“明天下雨”，命题Q表示“我们就去春游”.
则原语句可以表示成命题公式
P→Q.（5分）
⑵设P（x）：
x是人，Q（x）：
x去上课
则原语句可以表示成谓词公式（x）（P（x）Q（x））．
四、判断说明题（每小题7分，本题共14分）
14．┐P∧（P→┐Q）∨P为永真式．
正确．（3分）
┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，
如果P的值为真，则┐P∧（P→┐Q）∨P为真，（5分）
如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真，
也即┐P∧（P→┐Q）∨P为真，
所以┐P∧（P→┐Q）∨P是永真式．（7分）
15．若偏序集的哈斯图如图一所示，则集合A的最大元为a，最小元不存在．
正确．（3分）
对于集合A的任意元素x，均有R（或xRa），所以a是集合A中的最大元．（5分）
14．如果R1和R2是A上的自反关系，则R1∪R2是自反的．
正确．（3分）
R1和R2是自反的，xA，R1，R2，
则R1R2，
所以R1∪R2是自反的．（7分）
15．如图二所示的图G存在一条欧拉回路．
正确．（3分）
因为图G为连通的，且其中每个顶点的度数为偶数．（7分）
14．设N、R分别为自然数集与实数集，f：
N→R，f（x）=x+6，则f是单射．
正确．（3分）
设x1，x2为自然数且x1x2，则有f（x1）=x1+6x2+6=f（x2），故f为单射．（7分）
15．设G是一个有6个结点14条边的连通图，则G为平面图．
错误．（3分）
不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”
13．下面的推理是否正确，试予以说明．
（1）（x）F（x）→G（x）前提引入
（2）F（y）→G（y）US
（1）．
错误．（3分）
（2）应为F（y）→G（x），换名时，约束变元与自由变元不能混淆．（7分）
14．若偏序集的哈斯图如图二所示，则集合A的最大元为a，最小元不存在．
错误．（3分）
集合A的最大元不存在，a是极大元．（7分）
13．下面的推理是否正确，试予以说明．
（1）（x）F（x）→G（x）前提引入
（2）F（y）→G（y）US
（1）．
错误．（3分）
（2）应为F（y）→G（x），换名时，约束变元与自由变元不能混淆．（7分）
14．如图二所示的图G存在一条欧拉回路．
错误．（3分）
因为图G为中包含度数为奇数的结点．（7分）
13．如果图G是无向图，且其结点度数均为偶数，则图G是欧拉图．
错误．（3分）
当图G不连通时图G不为欧拉图．（7分）
升级会员 