离散数学-期中试卷

2014-2015年第一学期《离散数学》期中试卷

一、填空题（每空4分，共40 分）

1、设简单命题p：你努力，q：你失败。则命题“除非你努力，否则你将失败”可符号化为 ；命题“虽然你努力了，但还是失败了”可符号化为 。

2、设A={2,3,4,5,6}上的二元关系R = {|x

则用列举法R= ，R的关系矩阵MR= 。 3、设 f，g是自然数集N上的函数?x?N，f(x)=x+1，g(x)=2x， 则f。g(x)= 。

4、集合 A = {{?,2},{2} }的幂集P(A)= 。

5、设 P (x)：x是素数，E(x)：x是偶数，O(x)：x是奇数 ，N (x,y)：x可以整数y。则谓词公式?x (P(x) ??y(O(y) ?N(y,x)))的自然语言是 。 6、谓词合式公式?xP(x)??xQ(x)的前束范式为 。 7、设集合A={{a},{a,b}},求??A-??A= 。

8、设A为任意的公式，B为重言式，则A?B的类型为 。

二、证明题（每题15分，共30 分）

1、在自然推理系统P中构造下面推理的证明：

如果今天是周六，我们就到颐和园或圆明园玩. 如果颐和园游人太多，就不去颐和园. 今天是周六，并且颐和园游人太多. 所以, 我们去圆明园或动物园玩. 2、用消解法证明下述公式A是可满足的: A=(p??q)?(q??r)?(?q??r) 三、解答题（每题15分，共30分）

1、用等值演算法公式A=(p?q)?(?q??p)的求主析取范式和主合取范式 2、设R是集合A = {a, b, c, d}. R是A上的二元关系, R = {(a,b), (b,a), (b,c), (c,d)}, (1) 求出r(R), s(R), t(R)； (2) 画出r(R), s(R), t(R)的关系图.