C．?(P?Q)?Q； D．P?(P?Q)。
2、命题公式 (?P?Q)?(?Q?P) 中极小项的个数为（ ），成真赋值的个数为（ ）。
A．0； B．1； C．2； D．3 。
S
3、设S?{?,{1},{1,2}}，则 2 有（ ）个元素。
A．3； B．6； C．7； D．8 。 4、 设S?{ 1, 2, 3 }，定义S?S上的等价关系
R?{??a,b?,?c,d? | ?a,b??S?S,?c,d??S?S,a?d?b?c}则由 R产 生
的S?S上一个划分共有（ ）个分块。
A．4； B．5； C．6； D．9 。 5、设S?{ 1, 2, 3 }，S上关系R的关系图为
则R具有（ ）性质。
A．自反性、对称性、传递性； B．反自反性、反对称性； C．反自反性、反对称性、传递性； D．自反性 。 6、设 ?,? 为普通加法和乘法，则（ ）?S,?,??是域。 A．S?{x|x?a?b3,C．S?{x|x?2n?1,a,b?Q} B．S?{x|x?2n,a,b?Z}
n?Z} D．S?{x|x?Z?x?0}= N 。
7、下面偏序集（ ）能构成格。
8、在如下的有向图中，从V1到V4长度为3 的道路有（ ）条。
A．1； B．2； C．3； D．4 。 9、在如下各图中（ ）欧拉图。
10、
设R是实数集合，“?”为普通乘法，则代数系统
A．群； B．独异点； C．半群 。
三、证明 46%
1、 设R是A上一个二元关系，
S?{?a,b?|(a,b?A)?(对于某一个c?A,有?a,c??R且?c,b??R)}试证
明若R是A上一个等价关系，则S也是A上的一个等价关系。（9分）
2、 用逻辑推理证明：
所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11分）
3、 若f:A?B是从A到B的函数，定义一个函数g:B?2对任意b?B有
Ag(b)?{x|(x?A)?(f(x)?b)}，证明：若f是A到B的满射，则g是从B到 2
A的单射。（10分）
4、 若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分）
5、 设G是具有n个结点的无向简单图，其边数
Hamilton图（8分）
m?1(n?1)(n?2)?22，则G是
四、计算 14%
1、 设
试求出
2、 权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分）
试卷三试题与答案
一、 填空 20% （每空 2分）
1、 设 f，g是自然数集N上的函数?x?N,f(x)?x?1,g(x)?2x，
则f?g(x)? 。
2、 设A={a，b，c}，A上二元关系R={< a, a > , < a, b >,< a, c >, < c, c>} ,
则s（R）= 。
3、 A={1，2，3，4，5，6}，A上二元关系T?{?x,y?|x?y是素数}，则用列举
法
T= ； T的关系图为
； T具有 性质。 4、 集
合
A?{{?,2},{2}}的幂集
2A= 。
5、 P，Q真值为0 ；R，S真值为1。则wff(P?(R?S))?((P?Q)?(R?S))的
真值为 。 6、 wff?((P?Q)?R)?R的
主
合
取
范
式
为 。
7、 设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。
则谓词wff?x(P(x)??y(O(y)?N(y,x)))的自然语言是
。 8、 谓词wff?x?y(?z(P(x,z)?P(y,z))??uQ(x,y,u))的前束范式为
。
二、 选择 20% （每小题 2分）
1、 下述命题公式中，是重言式的为（ ）。
A、(p?q)?(p?q)； B、(p?q)?((p?q))?(q?p))； C、?(p?q)?q； D、(p??p)?q。 2、 wff?(p?q)?r的主析取范式中含极小项的个数为（ ）。
A 、2； B、 3； C、5； D、0； E、 8 。 3、 给定推理
①?x(F(x)?G(x)) ②F(y)?G(y) ③?xF(x) ④F(y) ⑤G(y) ⑥?xG(x)
P US① P ES③ T②④I UG⑤
??x(F(x)?G(x))??xG(x)
推理过程中错在（ ）。
A、①->②; B、②->③; C、③->④; D、④->⑤; E、⑤->⑥
4、 设S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，
S5={3，5}，在条件X?S1且X?S3下X与（ ）集合相等。 A、 X=S2或S5 ； B、X=S4或S5；
C、X=S1，S2或S4； D、X与S1，…，S5中任何集合都不等。 5、 设
R
和
S
是
P
上的关系，P
是所有人的集合，
R?{?x,y?|x,y?P?x是y的父亲}，S?{?x,y?|x,y?P?x是y的母亲}则S?1?R表示关系 （ ）。
A、{?x,y?|x,y?P?x是y的丈夫}； B、{?x,y?|x,y?P?x是y的孙子或孙女}；
C、 ?； D、{?x,y?|x,y?P?x是y的祖父或祖母}。 6、 下面函数（ ）是单射而非满射。
A、f:R?R,?f:Z?R,B、
f(x)??x2?2x?1；
f(x)?lnx；
C、f:R?Z,D、f:R?R,f(x)?[x],[x]表示不大于x的最大整数；
f(x)?2x?1。
其中R为实数集，Z为整数集，R+，Z+分别表示正实数与正整数集。 7、 设S={1，2，3}，R为S上的关系，其关系图为
则R具有（ ）的性质。
A、 自反、对称、传递； B、什么性质也没有；
C、反自反、反对称、传递； D、自反、对称、反对称、传递。 8、 设S?{?,{1},{1,2}}，则有（ ）?S。
A、{{1,2}} ；B、{1,2 } ； C、{1} ； D、{2} 。 9、 设A={1 ,2 ,3 }，则A上有（ ）个二元关系。
A、23 ； B、32 ； C、2； D、2。 10、全体小项合取式为（ ）。
A、可满足式； B、矛盾式； C、永真式； D、A，B，C 都有可能。 三、 用CP规则证明 16% （每小题 8分） 1、A?B?C?D,D?E?F2332?A?F
2、?x(P(x)?Q(x))??xP(x)??xQ(x) 四、（14%）
集合X={<1,2>, <3,4>, <5,6>,… }，R={<
设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >} 要求 1、写出R的关系矩阵和关系图。（4分） 2、用矩阵运算求出R的传递闭包。（6分）