试卷二试题与答案

一、填空

1、 设P：你努力，Q：你失败。

2、 “除非你努力，否则你将失败”的符号化为 ； 3、 “虽然你努力了，但还是失败了”的符号化为 。 2、论域D={1，2}，指定谓词P

P (1,1) T P (1,2) T P (2,1) F P (2,2) F 则公式?x?yP(y,x)真值为 。 3设A={2，3，4，5，6}上的二元关系RR= ?{?x,y?|x?y?x是质数}，则

（列举法）。

R的关系矩阵MR=

。 4、 设A={1，2，3}，则

A上既不是对称的又不是反对称的关系R= ； A上既是对称的又是反对称的关系R= 。 5、设代数系统，其中A={a，b，c}, * a b c a b c a b c b b c c c b

则幺元是 ；是否有幂等 性 ；是否有对称性 。

6、4阶群必是 群或 群。

7、下面偏序格是分配格的是 。

8、n个结点的无向完全图Kn的边数为 ，欧拉图的充要条件是 。 二、选择

1、在下述公式中是重言式为（ ）

A．(P?Q)?(P?Q)；B．(P?Q)?((P?Q)?(Q?P))；

1 / 5

C．?(P2、命题公式

?Q)?Q； D．P?(P?Q)。

(?P?Q)?(?Q?P) 中极小项的个数为（ ），成真赋值的个数为（ ）。

A．0； B．1； C．2； D．3 。 3、设S?{?,{1},{1,2}}，则 2S 有（ ）个元素。

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．SC．S?{x|x?a?b3,a,b?Q} B．S?{x|x?2n,a,b?Z}

?{x|x?2n?1,n?Z} D．S?{x|x?Z?x?0}= N 。

7、下面偏序集（ ）能构成格。

8、在如下的有向图中，从V1到V4长度为3 的道路有（ ）条。

A．1； B．2； C．3； D．4 。 9、在如下各图中（ ）欧拉图。

2 / 5

10、

10、设R是实数集合，“?”为普通乘法，则代数系统 是（ ）。

A．群； B．独异点； C．半群 。

三、证明

1、设R是A上一个二元关系，

S?{?a,b?|(a,b?A)?(对于某一个c?A,有?a,c??R且?c,b??R)}

试证明若R是A上一个等价关系，则S也是A上的一个等价关系。 2、 用逻辑推理证明：

所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。 3、若无向图G中只有两个奇数度结点，则这两个结点一定连通。

m?4、设G是具有n个结点的无向简单图，其边数四、计算

1(n?1)(n?2)?22，则G是Hamilton图。

1、 1、设A={1，2，3，4}，S={{1}，{2，3}，{4}}，为A的一个分划，求由S导出的等价关系。 （4分）

2、 设Ｚ为整数集，关系R?{?a,b?|a,b?Z?a?b(modk)}为Z上等价关系，求R的模K等

3、 设A={1，2，3，4，5}，A上的偏序关系为

求A的子集{3，4，5}和{1，2，3}，的上界，下界，上确界和下确界。（6分）

价关系的商集Z/R，并指出R有秩。（5分）

4、权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。

试卷二参考答案：

一、 填空

1、?P?Q；P?Q 2、T

3、R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,

<5,2>,<5,3>,<5,4>,<5,5>,<5,6>}；

3 / 5