离散数学模拟题A-2013

一、单选题(每小题1分，共计11分)

1. 设S?{N,Q,R}，则下列命题正确的是( ) A.2?N,N?S,则2?S; B.N?Q,Q?S,则N?S C.N?Q,Q?S,则S?N;D.N?Q,Q?R,则N?R 2. A,B,C是集合，下列选项正确的是( )

A. A?B?B?C?A?C; B. A?B?B?C?A?C C. A?B?B?C?A?C; D. a?A?A?B?a?B

3.定义幂集上的关系R为：当且仅当“x?y”时，xRy,在R不满足如下哪个性质（ ）

A.自反性 B.对称性 C.反对称性 D.可传递性

4.设R1和R2是A上的等价关系，下列选项哪个是等价关系( )

A.A?A?R1?R2; B.R2?R1 C.R1?R2; D. R1?R2

5.R和S是A上的二元关系，下列命题正确的是( ) A. 如果R和S是自反的，则R?S也是自反的 B. 如果R和S是反自反的，则R?S也是反自反的 C. 如果R和S是对称的，则R?S也是对称的 D. 如果R和S是传递的，则R?S也是传递的 6.下列语句不是命题的是( )

A. 我是个歌唱家。 B. 计算机有空吗？ C. 老虎是动物。 D. 正整数只有有限个。 7.下列哪个命题是永真式( )

A. P?(Q?R) B. P?(Q?R)

C. P?(P?Q) D. (P?Q)?(P?R) 8. 设P表示“我快乐”，Q表示 “天下雨”,则命题 “如果我快乐，那么天就下雨”可符号化为（ ）：

A. P?Q B. P?Q C. P?Q D.P?Q 9.下列哪个谓词公式不是永真式( )

A. ?x(?F(x)??F(x)) B. ?xF(x)??xF(x)

x?F(x)?F(x)）C. ?（ D. F(x)??F(x) 10. 下图中是哈密尔顿图的是( )

1

11. 已知无向图G有12条边，1度顶点有2个，2度顶点、3度顶点、5度顶点各1个，其余顶点度数均为4，则4度顶点的个数为（ ）

(A) 4； (B) 3； (C) 2； (D) 1。

二、填空题（每空1分，共计12分）

1.设A={xx是book中的字母},B={xx是black中的字母},则AUB= , A∩B= 。

2.集合A={1,2,3}，则A上有 种不同的具有自反性的二元关系；有 种不同的具有对称性的二元关系；有 种即是自反又是对称的二元关系。 3. 1到1000之间不能被5，6和8任何一个整除的整数个数有 个。 4. 设A={1,2,3,4,5,6},R与T是A上的二元关系，R?{(x,y)(x?y)2?A},则R= ；T?{(x,y)x/y是素数}，则T= 。

5.命题公式P:((A?B)?C)?(B?(D?C))，命题公式Q:(B?(D?A))?C，则命题公式P与Q之间的关系是 。

6. P(x)表示x是鸟，Q(x)表示x会飞，命题 “有些鸟会飞，但并非所有鸟都会飞”符号化为 。

7.无向完全图Kn(n?3) 中共有 条不同的哈密尔顿回路。 8.设一个无向树有两个2度接点，一个3度结点和三个4度结点，它有 个1度结点。

三、计算题（每题4分，共计28分）

1.对下列集合C,求?C，?C。

s?cs?C(1) C?{?} ; (2) C?{{a},{b},{a,b}}

R?{(i,j)(j?i?1)或（j=i/2）}；2.设A={0，1，2，3}，R和S是A上的二元关系，

S?{(i,j)(i?j?2)}

(1)用关系矩阵法求复合运算R?S; (2)求S?R，并用关系图表示。

3.设集合Ａ＝{a,b,c,d}, A上的二元关系R＝{(a,b),(b,c),(c,d)},

2

求r(s(R)),t(r(R)),t(s(R))。

4. A={2,3,4,5,6,8,12,16,24},R是A上的整除关系，

(1)画哈斯图; (2)求A的极大元，极小元，最大元，最小元。

5.用等值演算方法求命题公式?(P?Q)?(Q?R)主析取范式和主合取范式。 6.求谓词公式?x(P(x)?Q(x,y))?(?yP(y)??zQ(y,z))的前束范式。 7.在由6个结点、12条边构成的简单连通平面图G中，每个面由几条边围成？为什么？

四、证明题（每题5分，共计25分）

1.设A,B是集合，证明如果(A?B)?(B?A)?AUB，则A?B??。

2.设A是集合，P(A)是A的幂集，R是P(A)上的包含关系，证明R是偏序关系。

3.利用推理规则证明(M?Q)?P,M?S,S??R,?P?R?Q 4.证明(?x(?A(x)?B(x)))??xA(x)??x(B(x)?A(x))

5.证明在任何由两个或两个以上人组成的组内，存在两个人在组内有相同个数的朋友。

五、综合题（每题8分，共计24分）

1. 学校后勤中心为了准备招待的食物做了一项调查，调查的100人中，37人说吃水果，33人说吃蔬菜，9人说吃奶酪和水果，12人说吃奶酪和蔬菜，12人说吃水果和蔬菜，12人只吃奶酪，3人三种食物都吃，问受调查的人中有多少人吃奶酪？三种食物都不吃的有多少人？

2. 设有一个在internet上下载新闻的程序，为避免程序产生死循环和重复下载同一条新闻条目，程序必须根据下述4个条件对给定的新闻条目判断是否执行下载任务：

条件1：该新闻条目在程序的前一次执行中已经下载，用符号E表示； 条件2：该新闻条目在程序的本次执行中已经下载，用符号N表示； 条件3：该新闻条目是一个动态更新的新闻条目，用符号D表示；

条件4：该新闻条目已经过期，程序需要重新下载，用命题符号O表示。 执行下载任务的规划是：

a.该新闻条目在程序的前一次执行中没有下载，则不论其他条件如何，一定下载；

b.如果是一条动态新闻，并且该新闻条目在程序的本次执行中没有下载，则执行下载，否则不执行下载；

c.如果新闻条目在程序的前一次执行中已经下载，并且该新闻条目在程序的本次执行中没有下载，那么，如果是一个过期的新闻条目，则执行下载，否则不执行下载。

3

回答下列问题：

(1)根据上述条件，设计是否执行下载所对应的真值表； (2)根据上面的真值表写出是否执行下载对应的主合取范式。

3.每个人或者喜欢坐汽车或者喜欢骑自行车，每一个喜欢步行的人都不喜欢坐汽车，有的人不喜欢骑自行车，所以有的人不喜欢步行。 若令M(x)：x是人，W(x)：x喜欢步行，C(x)：x喜欢坐汽车，D(x)：x喜欢骑自行车。回答下列问题：

(1)符号化这段语言。

(2)利用推理规则进行推理。

4

5