离散数学考试试卷

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

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1．下列语句中不是命题的只有（ ）

A．或重于泰山，或轻于鸿毛。 B．鸡毛也能飞上天？

C．不经一事，不长一智。 D．牙好，胃口就好。

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

A．永真式 B．永假式

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

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

A．

B．

C．

D．

4．下列公式是前束范式的是（ ）

A．

B．

C．

D．

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

A．P→(P∨Q) B．(P ∨┐P) →Q

C．Q∧┐Q D．P→┐Q

6.设P：我很累，Q：我去学习，命题：除非我很累，否则我就去学习的符号化正确的是：（ ）

A．┐P∧Q B．┐P→Q

C．┐P→┐Q D．P→┐Q

7.下列等价式正确的是：

A．┐（x）A(x)〈＝〉（x）┐A(x)

B．(x) (y) A(x) 〈＝〉（x）(y) A(x)

C．┐(x) A(x) 〈＝〉（x）┐A(x)

D．(x)( A(x) ∧B(x)) 〈＝〉(x) A(x) ∨(x) B(x)

8.在公式（x）(y)P(x,y) ∧Q(z)) →（y）P(y,z)中变元y是（ ）

姓 名：＿＿＿＿＿＿ 得 分 ：＿＿＿＿＿＿

A.自由变元 B.约束变元

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

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

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

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

（1）能判断真假而不是可真可假的陈述句被称为________，真值只取两个值：________或________。

（2）所谓________是指不能再分解的命题，而复合命题是由一些________经过联结词复合而成的命题。

（3）P：小红用功，Q：小红聪明，则下列两个命题可符号化为：

小红既用功又聪明________，

小红虽然聪明但不用功________。

（4）写出 的对偶式________。

（5）令M(x)：x为人，F(x)：x要死去，G(x)：x去过火星，将下列命题符号化：

所有人都是要死去的________，

没有人去过火星________。

（6）在公式(x)(F(x,y)→G(x,y))中，________是约束变元，________是自由变元。

（7）设A=｛2,3｝,B=｛4,5｝，求A×B=________。

(8)设R=｛＜1,2＞, ＜2,4＞, ＜3,2＞, ＜4,5＞｝,则

domR=________. ranR=________, fldR=________。

(9)关系的性质主要有________，________，________，________和________。

（10）对于任意的连通的平面图G，其中n,m,r分别为G的顶点数，边数和面数

应满足关系：________。

三、判断题（本大题共5小题，每小题2分，共10分）

（1）“请不要大声喧哗”为命题。（ ）

（2）“如果3+2≠5,则雪是白色的”的真值为1. （ ）

（3）A∨(B∧C) 〈＝〉(A∨B) ∧(A∨C). （ ）

(4) 在公式(x)(F(x) →G(y)) →（y）(H(x) ∧L(x,y,z))中，x和y既是约束变元又是自由变元，z是自由变元. （ ）

(5)设A =｛1,2｝,则P(A)= ｛｛1｝,｛2｝,｛1,2｝｝（ ）.

四、用命题公式符号化命题（1）（2）（3），用谓词公式符号下列命题（4）（5）（6）（6*4分=24分）

（1）仅当今晚有时间，我去看电影。

（2）张涛是河南人或湖北人。

（3）只有小华努力学习了才会取得优异的成绩。

（4）并非发光的都是金子。

（5）有些男同志，既是教练员又是国家选手。

（6）有的兔子比所有的乌龟跑得快。

五、用等值演算法判断下列公式的类型(即为重言式还是矛盾式)：（2*8分=16）

（1）（P→Q）∧P→Q （8分）

(2) ┐(P→(P∨Q)) ∧R （8分）

六、设A=｛1,2,3｝,B=｛a,b｝(10分)

(1)写出A,B的关系矩阵；(5分)

（2）求A×B,dom(A×B).（5分）