苏XI友离散数学模拟试题2and answer

离散数学模拟试题2

一、单选题（本大题共8小题，每小题2分，共16分）

1．设p：天下大雨，q：我们乘公共汽车。命题“除非天下大雨，否则我们不乘公共汽车。”符号化为 （ ） A. p?q B. q?p C. p∧q D. ?q ?? p 2．设N(x):x是自然数，H(x,y):y是x的后继数。 命题“每个自然数都有后继数.”符号化为（ ）.

A.?x(N(x)??y(N(y)∧H(x,y))) B.?x(N(x)∧?y(N(y)?H(x,y))) C.?x(N(x)??y(N(y)∧H(x,y))) D.?x(N(x)??y(N(y)∧H(x,y))) 3．设集合A=｛?，a｝，下面四个命题为真的是 （ ）

A. a?A B. ??A C.｛?｝? A D.｛a｝? A 4．设集合A=｛a,b,c,d｝,A上的关系R=｛〈a,b〉,〈b,a〉, 〈c,d〉,〈d,c〉｝∪IA，则下面命题为真的是 （ ） A. R是A上的等价关系 B. R是A上的偏序关系 C. R是A上的全序关系 D. R是A上的全域关系 5．设V=〈N，+〉，其中N为自然数集合，+为数的普通加法。令φ:N→N， φ（x）=2x。下面四个命题为真的是 （ ） A.是满同态 B.是单自同态 C.是自同构 D.是V到自身的映射，但A，B，C都不是 6．设Z是整数集合，∩是Z的幂集P（Z）上的交运算。 令V=〈P（Z）；∩〉，则V是 （ ） A.循环群 B. 有限群 C. 无限群 D. 含幺半群 7．设G是有n 个顶点m 条边的无向简单图, 并且m=n－1,则有结论 （ ） A. G一定是树 B. G不一定是树 C.G一定不是树 D.G是森林 8．完全图K4是 （ ） A. 欧拉图 B.二部图 C.平面图 D.非平面图

二、填空题（本大题共8小题，每小题3分，共24分）

1．含n个命题变项的矛盾式的主析取范式为 。 2．设个体域为实数集合R，命题?x?y(x+y=1)的真值为 。 3．设A=｛a,b｝，IA是A上的恒等关系，则商集A/IA= 。 4．设S=｛1,2,3,4｝，则S上的4元对称群是 阶群。 5．群中唯一的幂等元是 。 6．设Z是整数集合，×是数的乘法运算. 令V=〈Z,×〉，则命题“V是群”的真值为 。

7．两个同构的图的顶点数一定 。

1

8．设二元正则树T的顶点数为n，则n必为 数。

三、简答题（本大题共8小题，每小题5分，共40分） 1．用主析取范式法判断命题公式(p?q)→r的类型。

2．给定解释I如下：D=｛1,2｝，P(1,1)=P(2,2)=0，P(1,2)=P(2,1)=1。 求?x?yP(x,y)在解释I下的真值。

3．设A=｛1，2，3｝，A上关系R=｛〈1,1〉,〈1,2〉，〈2,1〉,〈2,2〉,〈3,1〉,〈3,3〉｝,

（1） 写出R的关系矩阵； （2） 画出R的关系图； （3） 并确定R具有哪些性质。

4．设集合A=｛2,3,5,7,8,12｝，A上的偏序关系R=｛〈x, y〉∣x能整除y｝。求出集合A的极小元、极大元、最小元、最大元、上界、下界、最小上界、最大下界。

5．设〈L ，∧ ，∨〉是格，?a, b∈L ，验证：a∧ b=a?a∨b= b。

6．设R为实数集合，?定义为：对任意?x，y?R，有x?y = x + y – x y，这里+、-为数的加法和减法运算。验证：〈R，?〉是否为群。

7．画出带权为2，2，5，5，10，11的最优树T，求T对应的前缀码，计算T的权。

8．设10阶平面图G有5个面，求G中的边数。

四、证明题（本大题共4小题，每小题5分，共20分） 1．在命题逻辑中构造下面推理的证明 前提：q→p，?p∨r，q∨s. 结论：? r→s .

2．设R是集合A上的关系，证明：R是反自反的当且仅当R∩IA=?。 3．设群G中含有2阶元a（即2是使ak =e的最小正整数，其中e为单位元），证明与a 可交换的元素构成G的子群。

4．试证明：简单连通无向图G的任何一条边，都是G的某一棵生成树的边。

2

离散数学模拟试题2参考答案

一、单项选择题

1.B 2.D 3.B 4.A 5.B 6.D 7.B 8.C 二、填空题

1.0. 2.0. 3.{{a},{b}}. 4. 4!=24. 5.幺元(单位元). 6.0(假). 7.相同. 8.奇. 三、简答题

1. (p∧q)?r??(p∧q)∨r??p∨?q∨r?M6.

该式为公式(p∧q)?r的主合取范式，由主合取范式定义知，110为公式的成假赋值，000,001,010,011,100,101,111为公式的成真赋值，而成真赋值与公式主析取范式中的极小项一一对应，故公式的主析取范式为:

(p∧q)?r?m0∨m1∨m2∨m3∨m4∨m5∨m7.

公式的主析取范式只包含了部分极小项，故公式 (p∧q)?r为非重言式的可满足式.

2. ?x?yP(x,y)??x(P(x,1)∧P(x,2))?(P(1,1)∧P(1,2))∧(P(2,1)∧P(2,2)) ?(0∧1)∧(1∧0)?0∧0?0.

?110???3.(1)MR??110?.

?101???(2) R的关系图为:

123

(3)因为IA={<1,1>,<2,2>,<3,3>}?R，所以R是自反的，不是反自反的；

3

因为<3,1>∈R，但<1,3>?R，所以R不是对称的； 因为<1,2>,<2,1>∈R，所以R也不是反对称的；

因为<3,1>∈R，<1,2>∈R，但<3,2>?R，所以R不是传递的. 4. A上偏序关系的哈斯图为:

8 1252 37由哈斯图A的极小元为2,3,5,7，最小元无；极大元为5,7,8,12，最大元无；不存在上界、上确界、下界、下确界. 5.必要性. 由a∧b=a，有a∨b=(a∧b)∨b=b. 充分性. 由a∨b=b，有a∧b=a∧(a∨b)=a.

6.(1)?x,y?R，x?y=x+y-xy?Z，所以，为代数系统； (2)?x,y,z?Z，(x?y)?z=(x+y-xy)?z=x+y+z-xz-yz+xyz，

x?(y?z)=x?(y+z-yz)=x+y+z-xz-yz+xyz，

即(x?y)?z=x?(y?z)，所以，为半群；

(3)设e?Z为?的幺元，则对?x?Z，有x?e=e?x=x，即

x+e-xe=e+x-ex=x，

解得e=0，故e=0为?的幺元，所以为独异点； (4)?x?Z，设y?Z为x的逆元，则有x?y=y?x=0，即

x+y-xy=y+x-yx=0，

解得y=x/(x-1)(x≠1)，从而x=1时无逆元，所以，不是群. 7.用Huffman算法画出最优树如下:

4