离散数学自学考试复习题

离散数学自学考试复习题

课程代码：02324

一、单项选择题

1．下列命题公式为重言式的是（ ）

A．p→ (p∨q) C．q∧┐q

2．下列语句中不是命题的只有（ ） ．．A．这个语句是假的。 C．飞碟来自地球外的星球。 3．下列等价式正确的是（ ） A．┐(?x)A?(?x)┐A B．(?x)(?y)A?(?x)(?y)A C．┐(?x)A?(?x)┐A

D．(?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)

4．在公式(?x)(?y)(P(x,y)?Q(z))?(?y)P(y,z)中变元y是（ ） A．自由变元 B．约束变元

C．既是自由变元，又是约束变元 D．既不是自由变元，又不是约束变元

5．设A={1，2，3}，A上二元关系S={<1，1>，<1，2>，<3，2>，<3，3>}，则S是（ ） A．自反关系 C．对称关系

B．反自反关系 D．传递关系 B．1+1=1.0

D．凡石头都可练成金。 B．(p∨┐p)→q D．p→┐q

6．设集合X为人的全体，在X上定义关系R、S为R={

b>|a，b∈X∧a是b的母亲}，那么关系{|a，b∈x∧ a是b的祖母}的表达式为（ ） A．R?S C．S?R

B．R-1?S D．R?S-1

7．设A是正整数集，R={(x，y)|x，y∈A∧x+3y=12}，则R∩ ({2，3，4，6}×{2，3，4，6})=

（ ）

A． O / B．{<3，3>} C．{<3， 3> ，<6，2>} D．{<3，3>，<6，2>，<9，1>}

8．下列命题正确的是（ ） A．{l，2}?{{1，2}，{l，2，3}，1}

B．{1，2}?{1，{l，2}，{l，2，3}，2} C．{1，2}?{{1}，{2}，{1，2}} D．{1，2}∈{1，2，{2}，{l，2，3}}

9．在下列代数系统中，不是环的只有（ ）

A．，其中R为实数集，+为实数加法，a*b=a+2b。

D．，其中Mn(R)为实数集n×n阶矩阵结合，+，*是矩阵加法和乘法。 10．下列整数集对于整除关系都构成偏序集，而能构成格的是（ ） A．{l，2，3，4，5} C．{2，3，7}

B．{1，2，3，6，12} D．{l，2，3，7}

11．结点数为奇数且所有结点的度数也为奇数的连通图必定是（ ） A．欧拉图 C．非平面图

B．汉密尔顿图 D．不存在的

12．无向图G是欧拉图当且仅当G是连通的且（ ） A．G中各顶点的度数均相等 B．G中各顶点的度数之和为偶数 C．G中各顶点的度数均为偶数 D．G中各顶点的度数均为奇数

13．平面图(如下)的三个面的次数分别是（ ）

A．11，3，4 C．12，3，6

14．下列语句中不是命题的只有（ ） ．A．鸡毛也能飞上天？ C．不经一事，不长一智。

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

B．11，3，5 D．10，4，3

15．从真值角度看，命题公式的全部类型是（ ） A．永真式 C．永真式，永假式

16．下列公式是前束范式的是（ ） A．(?x)(?y)(?F(z,x)?G(y))

B．(?(?x)F(x)?(?y)G(y))?H(z) B．永假式

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

C．(?x)F(x,y)?(?y)G(y) D．(?x)(F(x,y)?(?y)G(x,y))

17．下列是谓词演算中的合式公式的是（ ） A．(?x)(p(x)??y) C．(?x)P(x,y)Q(y,z)

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

B．A－（B∪C）=（A－B）∪C D．~（A∩B）?A B．(?x)F(x)?G(x,y) D．(?x)?x?P(x,y)

19．下列集合对所给的运算是封闭的只有（ ） A．非零整数集合Z*上的除法运算

B．全体n×n实可逆矩阵集合Mn（R）上的矩阵加法和乘法运算 C．全体n×n实矩阵集合Mn（R）上的矩阵加法和乘法运算 D．A={1，2，…，10}，x*y=LCM（x，y），即x，y最小公倍数 +，*>是环，则下列说法不20．设是交换群 A．

+是可分配的 C．*对○

B．是半群 +对*是可分配的 D．○

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

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

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

B．n+r-e=2 D．n-e-r=2

二、填空题

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

3．使公式(?x)(?y)(A(x)?B(y))?(?x)A(x)?(?y)B(y)成立的条件是____中不含y，____中不