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

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

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

一、单项选择题（本大题共15小题，每小题1分，共15分） 1．下列语句中不是命题的只有（ ） ．

A．鸡毛也能飞上天？ B．或重于泰山，或轻于鸿毛。 C．不经一事，不长一智。 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） C．~（A－B）=~（B－A）

（ ）

B．A－（B∪C）=（A－B）∪C 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．是半群 +是可分配的 +对*是可分配的 C．*对○D．○

11．下列四个格，是分配格的是（ ）

1

www.4juan.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=____。

23．设e是群G上的幺元，若a?G且a2=e,则a-1=____ ,a-2=__________。 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

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

2

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

3)L={1,2,3,4,6,9,12,18,36} 4)L={1,2,22,23,…,2n}

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是受过教育的人。

3