7月全国自考离散数学试题试卷真题及答案_自考离散数学历年试题

7月全国自考离散数学试题试卷真题及答案由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“自考离散数学历年试题”。

www.daodoc.com 专注于收集各类历年试卷和答案

2006年7月全国自考离散数学试题试卷真题

一、单项选择题（本大题共15小题，每小题1分，共15分）1．下列语句中不是命题的只有（）．A．鸡毛也能飞上天？ C．不经一事，不长一智。

B．或重于泰山，或轻于鸿毛。D．牙好，胃口就好。

2．从真值角度看，命题公式的全部类型是（）

A．永真式

B．永假式

C．永真式，永假式

D．永真式，永假式，可满足式

3．设M（x）：x是人；F（x）：x要吃饭。用谓词公式表达下述命题：所有的人都要吃饭，其中错误的表．．达式是（）A．(x)(M(x)F(x))C．(x)(M(x)F(x))

B．(x)(M(x)F(x))D．(x)(M(x)F(x))

4．下列公式是前束范式的是（）A．(x)(y)(F(z,x)G(y))B．((x)F(x)(y)G(y))H(z)C．(x)F(x,y)(y)G(y)D．(x)(F(x,y)(y)G(x,y))5．设论域为整数集，下列真值为真的公式是（）A．(x)(y)(xy0)

B．(y)(x)(xy0)C．(x)(y)(xy0)D．(x)(y)(xy0)

6．下列是谓词演算中的合式公式的是（）

A．(x)(p(x)y)

B．(x)F(x)G(x,y)

C．(x)P(x,y)Q(y,z)

D．(x)xP(x,y)．（）A．B． C．D． ．（）

8．下列式子正确的是（）A．（A－B）-C=A-（B∪C）

（）

B．A－（B∪C）=（A－B）∪C C．~（A－B）=~（B－A）D．~（A∩B）A 9．下列集合对所给的运算是封闭的只有（）

A．非零整数集合Z*上的除法运算

B．全体n×n实可逆矩阵集合Mn（R）上的矩阵加法和乘法运算 C．全体n×n实矩阵集合Mn（R）上的矩阵加法和乘法运算 D．A={1，2，„，10}，x*y=LCM（x，y），即x，y最小公倍数

+，*>是环，则下列说法不正确的是（）10．设是交换群 A．

B．是半群

+对*是可分配的 D．○11．下列四个格，是分配格的是（）

www.daodoc.com 专注于收集各类历年试卷和答案

12．下列各图是无向完全图的是（）

13．下列各有向图是强连通图的是（）

14．设Ｇ是具有n个结点的无向简单图，若在Ｇ中存在一条汉密尔顿路，则Ｇ中每一对结点的度数之和与n-1的关系为（）

A．大于

B．大于等于

C．等于

D．小于

15．设连通平面图Ｇ，共有n个结点，e条边，r个面，则欧拉证明成立的公式是（）A．e-n+r=2

B．n+r-e=2

C．n-r+e=2

D．n-e-r=2

二、填空题（本大题共10小题，每小题2分，共20分）

请在每小题的空格中填上正确答案。错填、不填均无分。

16．所谓___是指不能再分解的命题，而复合命题是由一些____经过联结词复合而成的命题。17．在命题演算中，两个____的合取、析取、条件、双条件均为____。

18．使公式(x)(y)(A(x)B(y))(x)A(x)(y)B(y)成立的条件是____中不含y，____中不含x。19．设A={1，2，3，4}，R是A上的二元关系，R={|x/y是素数}，则domR=_____;ranR=____。20．设无向图Ｇ有n个结点m条边，每个结点的度数为k或k+1，记Nk为度数等于k的结点数，则Nk=_____。如果无向简单图C的结点的度数均为相同的偶数，且m=7，则n=____。

21．设X={1，3，5，9，15，45}，R是X上的整除关系，则R是X上的偏序，其最大元是___，极小元是____。

22．设是有界格，a,bL,若ab=0,则a=b=_____；若ab=1,则a=b=____。

2-1-223．设e是群G上的幺元，若aG且a=e,则a=____ ,a=__________。24．代数系统，其中A为命题公式集合。为析取运算，则中零元素是____，幺元是____。25．树是不包含_____的___图。

三、计算题（本大题共6小题，第26、27题各4分，第28、29题各5分，第30、31题各6分，共30分）26．如果论域是集合{a,b,c}，试消去下面公式中的量词：(x)(y)(xy0)27．求公式（pq)(qr)的主析取范式。

28．设A={a,b,c},A上二元关系R={，},用关系矩阵法求最小的自然数m,n,m

（2）奇数个顶点，奇数条边

（3）偶数个顶点，奇数条边

（4）奇数个顶点，偶数条边

30．下列各整数集合对于整除关系“|”都构成偏序集，判断哪些偏序集能构成格？并说明理由。1)L={1,2,3,4,5}

2)L={1,2,3,6,12}

www.daodoc.com 专注于收集各类历年试卷和答案

3)L={1,2,3,4,6,9,12,18,36}

4)L={1,2,2,2,„,2} 31．设A={2，3，5，12，19}，等价关系R={|x, yAxy(mod 3)},写出各元素的等价类，并求A/R。

四、证明题（本大题共3小题，第32、33题各6分，第34题8分，共20分）32．用等价变换法证明：(PQ)((RQ)((PR)Q))是永真式。

33．若无向图G是欧拉图，G中是否存在割边？为什么？ 34．设A是一个集合，X=P（A），R是X上元素之间的包含关系，试证明是偏序集。（注：P（A）为A的幂集）

五、应用题（本大题共2小题，第35题6分，第36题9分，共15分）35．设有n个村庄要修路，（1）若要使所有村庄之间都有通路，问需在两村之间至少修几条路？（2）若要使任意两村庄之间有一条直接的路，则至少修几个路？（3）若修一条连接所有村庄的环路，问有多少种修路方案？ 36．设有推理：

(a)没有不守信用的人是可信赖的；

(b)有些可以信赖的人是受过教育的人；

(c)因此有些受过教育的人是守信用的。

试构造推理的证明，要求把推理的前提，结论符号化为谓词形式，并写出推理过程。（个体域：人的集合）提示：设F（x）表示x是守信用的人；G（x）表示x是可信赖的人；H（x）表示x是受过教育的人。

23n 3

www.daodoc.com 专注于收集各类历年试卷和答案

www.daodoc.com 专注于收集各类历年试卷和答案

www.daodoc.com 专注于收集各类历年试卷和答案