离散数学试题A卷

一、单项选择题（本大题共10小题，每小题2分，共20分） 1．下列命题公式中不是重言式的是（ ） ．A．p→(q→r) C．p→(p→p)

B．p→(q→p)

D．(p→(q→r))(q→(p→r))

2．设个体域是整数集，则下列命题的真值为真的是（ ） A．yx(x·y=1) C．xy (x·y=y2)

B．xy (x·y≠0) D．yx(x·y=x2)

3．关于谓词公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中错误的是（ ） ．．A．（x）的辖域是（y）（P（x,y）∧Q(y,z)） B．z是该谓词公式的约束变元 C．（x）的辖域是P（x,y）

D．x是该谓词公式的约束变元

4．设有代数系统G=〈A，*〉，其中A是所有命题公式的集合，*为命题公式的合取运算，则G的幺元是（ ） A．矛盾式 C．可满足式

B．重言式 D．公式p∧q

5．设A={Ø}，B=P（P（A）），以下不正确的式子是（ ） ．A．{{Ø }，{{Ø }}，{Ø ，{Ø }}}包含于B C．{{Ø ，{Ø }}}包括于B

B．{{{Ø }}}包含于B

D．{{Ø }，{{Ø ，{Ø }}}}包含于B

6．设Z是整数集，E={…，-4，-2，0，2，4，…}，f：Z→E，f（x）=2x，则f（ ） A．仅是满射 C．是双射

B．仅是入射 D．无逆函数

7．设A={1，2，3，4，5}，A上二元关系R={〈1，2〉，〈3，4〉，〈2，2〉}，S={〈2，4〉，〈3，1〉，〈4，2〉}，则S-1R-1的运算结果是（ ）

1

A．{〈4，1〉，〈2，3〉，〈4，2〉} C．{〈4，1〉，〈2，3〉，〈2，4〉}

B．{〈2，4〉，〈2，3〉，〈4，2〉} D．{〈2，2〉，〈3，1〉，〈4，4〉}

8．在实数集合R上，下列定义的运算中不可结合的是（ ） ．A．a*b=a+b+2ab C．a*b=a+b+ab

B．a*b=a+b D．a*b=a-b

9．设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（ ） A．3 C．5

B．4 D．6

10．设无向图G的边数为m，结点数为n，则G是树等价于（ ） A．G连通且m=n+1 C．G连通且m=2n

B．G连通且n=m+1

D．每对结点之间至少有一条通路

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

11．不能再分解的命题称为____________，至少包含一个联结词的命题称为____________。

12．在命题演算中，五个联结词的含义是由其____________表唯一确定的，而不是由其类似的____________

语言的含义确定。

13．使公式（x）（y）（A（x）→B（y））（（x）A（x）→（y）B（y））成立的条件是____________

不含有y，____________不含有x。

14．设A为任意集合，请填入适当的运算符，使式子A____________A=Ø；A____________~A=Ø成立。 15．设A={0，1，2，3，6}，R={〈x,y〉|x≠y∧(x,y∈A)∧y≡x(mod 3)}，则domR=____________，

ranR=____________。

16．称集合S是给定非空集合A的覆盖：若S={S1，S2，…，Sn}，其中SiA，Si≠Ø，i=1，2，…，n，

且____________；进一步若____________，则S是集合A的划分。

17．对实数的普通加法和乘法，____________是加法的幂等元，____________是乘法的幂等元。 18．在代数系统〈A，*〉中，A={a}，*是A上二元运算，则该代数系统的单位元是____________，零元

2

是____________。

19．设〈A，≢〉是偏序集，若A中____________都有最小上界和____________则称A关于偏序≢构成格。 20．若一条路中，所有边均不相同，则此路称作____________；若一条路中所有的结点均不相同，则称此

路为____________。

三、计算题（本大题共5小题，每小题6分，共30分） 21．求命题公式(PQ)(PQ)的真值表。

22．试求谓词公式x(P(x)xQ(x,y)yR(x,y))A(x,y)中，x,x,y的辖域，试问R(x,y)和A(x,y)

中x,y是自由变元，还是约束变元？

23．求命题公式（p→q）→（q∨p）的主析取范式。

24．设代数系统(Z,*)，其中Z是整数集，二元运算定义为a,bZ,a*bab2， aZ，求a的逆元。

3

25．已知图D(如下图)的邻接矩阵为

v1v2v3v411

v4   v3

01

10v1   v2

01

求从v2到v4长度为2和从v3到v3长度为2的通路条数，并将它们具体写出。

v10A(D)=v21v30v4110 10

四、证明题（本大题共2小题，每小题6分，共12分）

26．设〈{a,b},*〉是半群，其中a*a=b，证明：（1）a*b=b*a；（2）b*b=b。

27．若一棵树恰有2个结点的度数为1，则它必是一条欧拉路。

五、应用题（本大题共3小题，每小题6分，共18分）

28．设I是整数集，<，>，＝，≢，≣，≠是Ｉ上的二元关系，分别表示小于，大于、等于、小于等于，

大于等于，不等于，那么这些关系会满足什么性质？试填写下表。

4

< > = ≢ ≣ ≠ ≢∩≣ ≢∪≣ 自反 反自反 对称 反对称 传递

29. 完成下列推理：只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考 场，考试才能准时进行。所以，如果考试准时进行，那么天气就好。

30．75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这

三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场 总共收入70元，求有多少儿童没有乘坐过其中任何一种。

5