离散数学习历年真题

一、 填空 20% （每空 2分）

1、 设 f，g是自然数集N上的函数 x N,

f(x) x 1,g(x) 2x，

则f g(x) 。

2、 设A={a，b，c}，A上二元关系R={< a, a > , < a, b >,< a, c >, < c, c>} ,

则s（R）= 。

}，则用列举法 3、 A={1，2，3，4，5，6}，A上二元关系T { x,y |x y是素数

T= ； T的关系图为

； T具有 性质。

4、 集合A {{ ,2},{2}}的幂集2= 。

A

5、 P，Q真值为0 ；R，S真值为1。则wff(P (R S)) ((P Q) (R S))的真值

为 。

6、 wff ((P Q) R) R的主合取范式为 。

7、 设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。则谓词

wff

x(P(x) y(O(y) N(y,x)))的自然语言是

。 8、 谓词wff x y( z(P(x,z) P(y,z)) uQ(x,y,u))的前束范式为

。

二、 选择 20% （每小题 2分）

1、 下述命题公式中，是重言式的为（ ）。

A、(p q) (p q)； B、(p q) ((p q)) (q p))； C、 (p q) q； D、(p p) q。 2、 wff

(p q) r的主析取范式中含极小项的个数为（ ）。

A 、2； B、 3； C、5； D、0； E、 8 。 3、 给定推理

① x(F(x) G(x)) ②F(y) G(y) ③ xF(x) ④F(y) ⑤G(y)

P US① P ES③ T②④I