离散数学第一次作业题及答案.doc

一、单项选择题(本大题共40分，共20小题，每小题2分)

1.

表达式FA (PV (QA-i S))的对偶式为 ___________ o

A.

FV(PA(QV-i S))

B.

T-(PV(QVn S))

C.

TV(PA(QV-| S))

D.

TV(PA(QAS))

2.公式VxF(x) —3xG(x),下面给出的前束范式等价式中，哪一个是对的()O

A.

3x(F(x) V^G(x))

B.

VxF (x) VG(x)

C.

3x(-F(x) VG(x)) Vx (「F(x) VG(X))

3.

设两个群＜乙+＞和V,•＞，,其中 Z为整数集，Zx = {•••,10-3/10~2,10_1,10°,101,102,103,'-}, + 为普通 加法，为普通乘法。设(p： Z-»Z\\屮(n)-io”。则V乙+＞和＜Z-,•＞ ()

A.

是同构

B.

是单一同态

C.

是满同态

D.

不是同态

4.不是命题的是()。 A. 5大于3

B.

11是质数

C.

他是优秀学牛

k是太阳

5.

对任意的公式P、Q、R,若P=>Q、Q=>R,则有

A. R=>P

B.

P=>R

C. Q=>P

D.

RnQ

6. 下列代数系统中， _________ 是群。 A.

S={0, 1,3, 5}, *是模 7 加法

B.

S=Q （有理数集），*是普通乘法

C.

S=Z （整数集合），*是普通减法

D.

S={1,3, 4, 5, 9}, *是模 11 乘法

7.

P：今天下雨。Q：明天下雨。上述命题的合取为 ____________ o （符号表示）

A.

-1 PA-i Q

B.

-I PVQ

C.

n PV-i Q

D.

PAQ

&

A.

B.

C. 6

D. 3

9.

他虽聪明单不用功。 设P：他聪明。Q：他用功。 则命题符号化为 _______ o

A.

PA-i Q

B.

-I PVQ

C.

n PVQ

D.

QAP

10. 设G为至少有三个结点的连通平面图，则G中必有一个结点u,使得 deg(u)<5

B. deg(u)=5

C. deg(u)>5

D. deg(u) W5

11. 下列关系中哪些能构成函数？() A.

{ B.

{ C.

{ D.

{ 12.

联结词一可以转化为由「和V表示，P-Qo

n PAn Q

B.

-i PVQ

C.

-1 PV-i Q

D.

PAQ

13.连通图G有6个顶点9条边，从G中删去 ___________ 条边才可能得到G的一•棵生

成树T。

A.

B. 3

C. 4

D. 5

14.设个体域是整数集合，P代表VxVy((xP是一阶逻辑公式，但不是命题

B.

P是假命题

c.

P是真命题

D.

P不是一阶逻辑公式

15.

设N为自然数集合。©,△＞在XAY二 _____________ 时不构成代数系统。(*, +, -分 别为普通乘法、加法和减法)

A.

X+Y-2*X*Y

B.

X*Y

C.

D.

|X|+|Y|

16.

设＜x, +, X＞是代数系统，+和是普通数的加法和乘法。当X二 _______ 吋，＜x, +, x是整环。()

{x | x=2n, nW 1}

＞ B.

{x | x=2n+l, nW 1}

C.

{x | xMO, xE T}

D.

{x | x=a+b V3, a, bER}

17.

在代数系统屮，整环和域的关系为()

A.

域不一定是整环

B.

域一定是整环

C.

域一定不是整环

D.

整环一定是域

18. 给定序列集合{000, 001, 01, 10, 000

0},若去掉其中的元素(),则该序 列集合构成前缀码。

B. 001

C. 01

D. 0

19.

给定一命题公式，若无论对分量做怎样的指派，其对应的真值永为T,则称该 命题公式为 _______ o

A.

重言式

B.

永假式

C. 可满足式 D.

矛盾式

20.

下列命题公式与「(AVB)等价的是 ___________ 。

A.

n A An B

B.

-I AVB

C.

1 AV-] B

D.

AAB

二、多项选择题(本大题共30分，共10小题，每小题3分)

1.

下图是()。

A.

是强连通的

B.

是弱连通的

C.

是单侧连通的

D.

是不连通的

2.

下列集合关于指定的运算能构成半群的是（）

A.

G={a^n | neZ} （a是正实数）,运算*是普通乘法

B.

R为实数集，运算*定义为：V a,beR, a*b-a+b+ab

C.

Q\"+为正有理数集，运算+为普通加法

D.

Q\"+为正冇理数集，运算+为普通乘法

3.

设〈G, *〉为由a生成的循环群，下列表述正确的是（）

A.

若G为无限群,则G有无限多个子群,它们分别由…,S・・生 成。

B.

若G为有限群，则G有无限多个子群,它们分别由aQaJ ,a2…,a\\,…生成

c.

若G为无限群,且|G|=n,且n有因子k_l , k_2,k_r,那么G有r个循环子 群。它们分别由

a7k_l ) ,a7k_2 a7k_r )生晟。

D.

若G为有限群,且|G|=n,且n有因子k_l , k_2,k_r,那么G有r个循环子 群。它们分别由*(k_l ),『(k_2 a7k_r )生成。

4.

设〈A ,+, •＞是一个代数系统，如果满足()，则〈A ,+,A.

\是阿贝尔群

B.

vA,+＞是阿贝尔群

C.

vA, •＞是可交换独异点，且无零因子

D.

运算•对于运算+是可分配的

5.

判别有效结论的过程就是论证过程。常见的证明方法有三 种

、 、

C

A.

・＞是整环。真值表法

B.

逆向推理

C.

直接证法

D.

间接证法

6.

逻辑学是一门研究 _______ 及 _______ 的科学。

A.

思维形式

B.

思维规律

C.

口然规律

D.

人文社会

7.

两个命题变元P和Q生成的4个小项为： __________ 。

A.

PAQ

B. 1 PAQ

C.

PA-i Q

D.

n PAn Q

&

间接证法主要有两种，一种称之为 __________ ,还有一种是

A.

真值表法

B. CP规则

反证法（也叫归谬法）

D.

直接推理

9.

同构的必要条件（）o

A.

节点数目相等

B.

边数和等

C.

度数相同的节点数目相等

D.

每个节点的入度相等

10.

下列集合关于指定的运算能构成半群的是（）

A. G二{*n | nez} （a是正实数），运算*是普通乘法 B.

R为实数集，运算*定义为：V a, b^R, a*b二a+b+ab

Q\"+为止有理数集，运算+为普通加法

D.

Q\"+为正有理数集，运算+为普通乘法

三、判断题（本大题共30分，共10小题，每小题3分） 1. 判断对错:用列举法表示集合A={a|aGP且a〈20},表示为 {2, 3, 5, 7, 11, 13, 17, 19} o 2. 判断对错：集合{2,4,6, 是无限集（）

3. 用描述法表示下列集合B={2, 4,&…，1024},则可表示为{2、山日且 nW10}。 4. 集合A={1, {2}, 3, 4}, B={a, b, {c}},判定下题的正确与错误: ⑴WA 5. 用描述法表示下列集合A二{0,2,4,…，200},表示为{2x|xWZ且xWlOO}。

6. 由公式的等价性知：C_ 1AC_2 A• • • AC_n-> （A->B） <=> C_ 1AC_2 A• • • AC_n/\\ （A-*B）

7. 设G是一个联结词的集合，若任意一个命题公式都町用G中联结词构成的公 式來表示，则称G为最小联结词组。

8•循环群一定是阿贝尔群，阿贝尔群也一定是循环群。 9.

设△和5是简单图G的最大度和最小度，则6W2ni / n^Ao

10.设A是任意集合，则A上的恒等关系和全域关系UJ\\均是A上的等价关 系。（）

答案:

一、 单项选择题（40分，共20题，每小题2分）

1. C 2. C 3. A 4. D 5. B 6. D 7. D 8. B 9. A 10. D 11. C 12. B 13. C 14. A 15. A 16. D 17. B 1& D 19. A 20. A

二、 多项选择题（30分，共10题，每小题3分）

1. BC 2. ABCD 3. AD 4. BCD 5. ACD 6. AB 7. ABCD 8. BC 9. ABCD 10. ABCD

三、 判断题（30分，共10题，每小题3分）

1. J 2. J 3. J 4. X 5. J 6. J 7. X 8. X 9. V 10. V