离散数学习题

1 离散数学（本）复习题

1.请给出公式G=（P（QP））（P（PQ））的真值表。

2.设A={1，2，3，4，5，6}，其上一个划分为C={{1}，{2，4}，{3，5，6}}，请给出对应划分C的等价关系RC。

3.R，S是集合A上的两个关系。试证明下列等式：

（1）(R•S)-1= S-1•R-1

（2）(R-1)-1= R

（3）(R∪S)-1= R-1∪S-1

（4）(R∩S)-1= R-1∩S-1

4.设R是集合A上的关系，令

R+={(x, y)|xA，yA，并且存在n>0，使得xRny}，

则称R+是R的传递闭包，证明：R+是包含R的最小具有传递性的关系。

5.若非空集合上的非空关系R是反自反的，是对称的，试证明R不是传递的。

6.设A={1，2，3，4，5，6，7，8，9}，R为A上的整除关系，请给出部分序集（A，R）的Hasse图。

7.设G是含有3个不同原子的命题公式，当G是恒假公式的时候，G的主析取范式中有多少极小项，主合取范式中有多少极大项？

8.有人说：“等价关系中的反身性可以不要，因为反身性可以从对称性和传递性推出：由对称性，从a  b可得b  a，再由传递性得a  a”。你的意见呢？

9.若集合A上的关系R，S具有对称性，证明：R•S具有对称性的充要条件为R•S= S•R。

10.若R是等价关系，试证明R-1也是等价关系。

11.给P和Q指派真值1，给R和S指派真值0，求出下面命题的真值：

a) (P(QR))((PQ)(RS))

b) ((PQ)R)(((PQ)R)S)

c) ((PQ)R)((QP)(RS))

d) (P(Q(RP)))(QS)

12.试将下列公式化成等价的前束范式：

(1)x(P(x)yQ(x，y))；

(2)x((yP(x，y))(zQ(z)R(x)))；

离散数学习题

集合论

1.A={?,1}，B={{a}}求A的幂集、A×B、A∪B、A+B。

2.A={1,2,3,4,5},

R={(x,y)|x

3.A={a,b,c},R={(a,a),(b,a)},求

R-1,R2,R-I A,I A-R,r(R),s(R),t(R),st(R),ts(R)。

4.A={a,b,c},R= I A∪{(a,b),(b,a)}，求a和b关于R的

等价类。

5.R是A上的等价关系，A/R={{1,2}，{3}},求A，R。

6.请分别判断以下结论是否一定成立，如果一定成立请证

明，否则请举出反例。

①如果A∪B?C，则A?C或者B?C。

②如果A×B=A×C且A≠?，则B=C。

7.如果R是A上的等价关系，R2,r(R)是否一定是A上的等

价关系？证明或举例。

8.已知A∩C?B∩C,A-C?B-C,证明：A?B。

9.证明：A X(B∩C)=(A X B)∩(A X C)

10.证明：P(A)∪P(B)?P(A∪B)

11.证明：R[sym] iff R=R-1

12.证明：r(R)=R∪I A,S(R)=R∪R-1,t(R)=R∪R2∪...

13.证明：s(R∪S)=s(R)∪s(S)

14.R是A上的关系，证明：如果R是对称的，则r(R)也是

对称的。

15.I是整数集，R={(x,y)|x-y是3的倍数}，证明：R是I

上的等价关系。

16.如果R是A上的等价关系，则A/R一定是A的划分。

17.R是集合A上的自反关系，S是A上的自反和对称关系，

证明t(R∪S)是A上的等价关系。 18.I是正整数集合，R是I×I上的二元关系，

R={<,>|xv=yu},证明：R是等价关系。

19.f:A→B，R是B上的等价关系，令S={|x∈A且y∈A

且∈R}，证明：S是A上的等价关系。

20.R是集合A上的自反关系，S是A上的自反和对称关系，

证明t(R∪S)是A上的等价关系。

易自考

02324# 离散数学试题 第 1 页 共4页 离散数学试题

第一部分 选择题

一、单项选择题

1．下列是两个命题变元p，q的小项是（ C ）

A．p∧┐p∧q B．┐p∨q

C．┐p∧q D．┐p∨p∨q

2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）

A．p→┐q B．p∨┐q

C．p∧q D．p∧┐q

3．下列语句中是命题的只有（ A ）

A．1+1=10 B．x+y=10

C．sinx+siny<0 D．x mod 3=2

4．下列等值式不正确的是（ C ）

A．┐(x)A(x)┐A

B．(x)(B→A(x))B→(x)A(x)

C．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)

D．(x)(y)(A(x)→B(y))(x)A(x)→(y)B(y)

5．谓词公式(x)P(x,y)∧(x)(Q(x,z)→(x)(y)R(x,y,z)中量词x的辖域是（ C ）

A．(x)Q(x,z)→(x)(y)R(x,y,z))

B．Q(x,z)→(y)R(x,y,z)

C．Q(x,z)→(x)(y)R(x,y,z)

D．Q(x,z)

6．设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划分是（ D ）

A．{{a},{b,c},{d}} B．{{a,b},{c},{d}}

C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}

7．设A={Ø}，B=P(P(A))，以下正确的式子是（ A ）

A．{Ø,{Ø}}∈B B．{{Ø,Ø}}∈B

C．{{Ø},{{Ø}}}∈B D．{Ø,{{Ø}}}∈B

福建应用技术大学 信息学院计算机系 * 离散数学 * 大一期末练习 1. 针对下面的推理陈述回答问题： “或者英语难学，或者有少数学生不喜欢它；如果语文容易学，那么英语并不难学。因此，如果许多学生喜欢英语，那么语文并不难学。” （1） 请写出这段推理陈述的命题符号化形式； （2） 在自然推理系统P中构造这段推理的证明。 2. 解答下面的问题： （1） 用一阶逻辑对如下陈述符号化： “在美国留学的学生未必都是亚洲人”； （2） 将下式转化为与其等价的前束范式。 (((,))(()()))xyPxyzQzRx 3. 针对下面的陈述回答问题： 今天或者天晴或者下雨。如果天晴，我去看电影；若我去看电影，我就不看书。故我在看书时，说明今天下雨。

（1） 对这段陈述进行命题符号化； （2） 在自然推理系统P中，证明这段推理的结论有效。 4. 回答下面的问题： （1） 用一阶逻辑对如下陈述符号化： “兔子比乌龟跑得快” （2） 用一阶逻辑演算方法证明下面等值式： ┐x(M(x)∧F(x))  x(M(x)→┐F(x)) 5． 解答下列问题： （1） 用一阶逻辑对下面这段陈述进行符号化，要求逻辑清楚： 有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草 （2） 求下式的前束范式： xF(x,y)→yG(x,y) 6. 已知偏序集的哈斯图如下。 （1） 分别写出集合A和偏序关系R≤的集合表达式。 （2） 如果x、y∈A，填写下面的一阶逻辑公式中缺失的两个联结词 xy (∈R ∈R) （x=y） 7. 设R是定义在所有8位二进制数串构成的集合上的关系，如果s1和s2中0的个数相同，则s1Rs2。

（1） 证明R是等价关系。 （2） 共有多少个等价类？ （3） 列举出每个等价类的一个成员。 8. 已知集合A＝{a，b，c，d}，现有A上的二元关系R的关系图如下： （1） 列表给出R的全部有序对。 （2） 证明R是等价关系，并求出A中各元素的等价类。 （3） 给出上述关系R对应的关系矩阵。 9. 设函数f：R×R→R×R，f()=<2x+y,x-2y>， （1） 说明f是否为双射？ （2） f的反函数是否存在？如果存在，求出f的反函数。 （3） 如果函数f：N×N→N×N，且f()=<2x+y,x-2y>，那么f是否为双射？有反函数存在吗？ 10.