离散复习资料

一、判断

离散数学课程测试题

（ ） 1. 若wff A是可满足式，那么~A是矛盾式。 （ ） 2. P=>P∨Q是合适公式。

（ ） 3.?x(A(x)→B)→(?xA(x) →B)是重言式。 （ ） 4. 可满足式的代入实例一定是可满足式。

（ ） 5. wff A(P)=P的对偶式为~P。

（ ） 6. 若A*和B*是wff A和B的对偶式，且A=>B，则A*=>B*。 （ ） 7. 重言式的主析取范式为T。

（ ） 8. 空集是非空集合的一个元素。

（ ） 9. 设A和X是集合，则X∈2A iff X?A。

（ ） 10. 设A、B、C和D是四个非空集合, 且A×C ? B×D，则A?B且C?D。 （ ） 11. 传递关系的对称闭包仍是传递的。

（ ） 12. 非空集合上的关系不是对称的，则必是反对称的。

（ ） 13. 若R和S是二个有完全相同的二元组的集合，则称它们是相等的二元关系。 （ ） 14. 设Ａ是一个非空集合，则Ａ上的等价关系都不是偏序关系。 （ ） 15. 有限集上的全序关系必是良序关系。

（ ） 16. 有限集上的偏序关系必是全序关系。

（ ） 17 . 是偏序集，则Ａ的任何非空子集必有极小元。

（ ） 18. 是偏序集，则Ａ的非空子集Ｂ的上确界必是Ｂ的最大元。 （ ） 19. 是全序集，则Ａ的任何非空子集必有唯一极小元。

（ ） 20. 是全序集，则Ａ的非空子集Ｂ的下确界必是Ｂ的最小元。 （ ） 21. 无限集必与它的真子集等势。

（ ） 22. 若A?B，且A与B等势，则B是无限集。 （ ） 23. 若A?B，则#A<#B。

（ ） 24. 连通的4度正则图一定没有桥。 （ ） 25. p阶图的直径不可能等于p。

二、选择

（ ）1. 是wff （P→Q）∧R∧(S→(P→Q))的代入实例的有 ① P∧R∧(S→P) ② (~P→Q)∧~R∧(~S→(~P→Q)) ③ (P→Q)∧S∧(R→(P→Q)) ④ (P→Q)∧R∧(R→(P→Q)) （ ）2. 与公式?x ((P(x)∧?y Q(y))∧?z R(z)) →S(t)等价的有：

① ② ③ ④

?u ((P(u)∧?y Q(y))∧?z R(z)) →S(t) ?u ((P(u)∧?u Q(u))∧?z R(z)) →S(t) ?u ((P(u)∧?u Q(u))∧?u R(u)) →S(t) ?u ((P(u)∧?u Q(u))∧?u R(u)) →S(u)

（ ）3. 下列关系中正确的有： （

① {a}∈{a, {a}} ② {a}?{a, {a}} ③ {a}∈{a, {{a}}} ④ {a}?{a, {{a}}} ⑤ {a}∈{{a}, {{a}}} ⑥ {a}?{{a}, {{a}}} ）4.设A=P(P(P(Φ)))，下列关系式中正确的有：

1

① Φ∈A ② Φ?A ③ {Φ}∈A

④ {Φ}?A ⑤ {{Φ}}∈A ⑥ {{Φ}}?A

（ ）5.下列说法中正确的有：

① 任何集合都不是它自身的元素 ② 任何集合的幂集都不是空集

③ 若Ａ×Ｂ＝Φ，则Ａ＝Ｂ＝Φ ④ 任意两集合的笛卡尔积都不是空集 （ ）6. {1,2,3,4,5}上的关系R={<1,1>,<1,3>,<2,3>}是

① 自反的 ② 反自反的 ③ 对称的 ④ 反对称的 ⑤ 传递的 （ ）⒎ 空集上的空关系是 关系。

① 相容 ② 等价 ③ 偏序 ④ 拟序 ⑤ 良序 （ ）⒏ 集Ａ={0,1}上的恒等关系ＩA是 关系。 ① 相容 ② 等价 ③ 偏序 ④ 拟序 ⑤ 良序 （ ）⒐ {1,2,3,4,5}上的全关系是 关系。

① 相容 ② 等价 ③ 偏序 ④ 拟序 ⑤ 良序 （ ）⒑ {1,2,3,4,5}上的全序关系一定是 关系。 ① 相容 ② 等价 ③ 偏序 ④ 拟序 ⑤ 良序 （ ）11. {1,2,3,4,5}上的良序关系一定是

① 自反的 ② 反自反的 ③ 对称的 ④ 反对称的 ⑤ 传递的 （ ）12. 设Ｒ和Ｓ都是Ａ到Ｂ的关系，则下列关系式中正确的有： ① (Ｒ∪Ｓ)-1＝Ｒ-1∪Ｓ-1 ② (Ｒ∩Ｓ)-1＝Ｒ-1∩Ｓ-1 ③ (Ｒ－Ｓ)＝Ｒ－Ｓ ④ (Ｒ○＋Ｓ)＝Ｒ○＋Ｓ （ ）13. 函数f：Ｒ×Ｒ→Ｒ×Ｒ，f()=是 ① 入射 ② 满射 ③ 双射 ④ 以上答案都不对 （ ）14. 设Σ={a,b}为字母表，则f：Σ*→Σ*，f(x)=axb是

① 入射 ② 满射 ③ 双射 ④ 以上答案都不对 （ ）15. 若f、g是Ａ上的函数且g·f是双射，则

① f和g都是双射 ② f为满射 ③ g为入射 ④ f有左逆 ⑤ g有右逆

（ ）16. 设p阶图G不含圈，且恰有p-1条边（p≥2），则

① G连通 ② G的任一边都是桥 ③ G是树 ④ 加入任一边，G便含圈 （ ）17. 下列序列中，有哪个（些）不可能是一棵树的度序列： 三、填空

1. 公式A(P, Q, R)= Q∧R∨P∧R∨T∧~P∧R的对偶式为A*= 。

2. 若公式A(P, Q, R, S)的主析取范式为∑1,3,4,5,7，则A的主合取范式为∏ 。 3. 给命题变元P和Q指派真值T，R和S指派真值F，公式P∨(Q→R∧~P)→~Q∨S的真值为 。

4. 量词?!表示“有且仅有”，?!xP(x)表示恰好有一个个体满足谓词P。那么用量词?，?及等号“=”表示谓词?!后得到的公式__________与?!xP(x)有相同的意义。 5. 若用谓词I(x)表示“x是整数”，E(x)表示“x=y”，G(x,y)表示“x>y”，那么命题“对任何

2

-1

-1

-1

-1

-1

-1

① ( 1, 1, 2, 2, 2, 2, 2, 2 ) ③ ( 1, 1, 2, 2, 2, 2, 3, 3 )

② ( 1, 1, 1, 2, 2, 2, 2, 3 ) ④ ( 1, 1, 1, 1, 4, 4, 4, 4 )

整数x和y，x≤y且y≤x是x=y的充要条件”的谓词表达式为： 。 6. 给定论域D={1，2}和谓词P：P(1,1)=T，P(1,2)=F，P(2,1)=F，P(2,2)=T， 公式?x?y (P(x, y) →P(y, x))的真值为 。

7.若集Ａ={1,2,3,4}上的关系Ｒ={<1,2>,<2,3>,<3,4>}，Ｓ={<2,4>,<1,2>,<3,1>}，则dom(Ｒ·Ｓ)= 。

8. 若A={a,b}，B={1,2}，则B= 。

9. 用ε表示字母表Σ={a,b}上的空串，定义f：Σ*→Σ*如下：

?x∈Σ* f(x)=axb 则f({ε,a,b})= 。 10. 用ε表示字母表Σ={a,b}上的空串，定义f：Σ*→Σ*如下：

?x∈Σ* f(x)=axb 则f( )={aab,abb,ab}。

A

11. 在集Ａ={1,2}上可定义两个不同的等价关系，它们是 和 。

12. 若Ｒ为集合Ａ上的等价关系，a b，那么等价类[a]R和[b]R的交[a]R∩[b]R= 。 13. 若G是p阶k度正则图，则它有 条边，它的补图有 条边。

14. 考虑下图，它含有_________等割点，___________等桥（列出具体的顶点和边）。

四、计算与作图

V2 ?

V1 ? ? V4 ?

V5

?

V3

1. 若集合Ａ={1,2,3,4}上的关系Ｒ={<1,1>,<2,3>,<3,2>,<3,4>,<4,1>}。请用集合列举表示法表示r(Ｒ)、用关系图表示s(Ｒ)，用关系矩阵表示t(Ｒ)。

2. 设R和S都是{1,2,3,4,5}上的二元关系，且

R={<2,4>,<4,1>,<3,5>,<5,3>}，S={<1,2>,<3,4>,<5,2>}，则R·S= ，R2= ，t(R)= 。

3. 设Ａ={3,6,9,15,54,90,135,180}，｜为自然数的整除关系。画出<Ａ;｜>的Ｈasse图，并求{6,15,90}的上、下确界。

4. 设Ａ＝{a,b},Ｂ＝{1,2,3,4}，f＝{,}是Ａ到Ｂ的函数，试找出f的所有左逆和右逆(如果存在的话)。

5. 设Ａ＝{1,2,3,4,5},Ｂ＝{a,b}，f＝{<1,a>,<2,a>,<3,b>,<4,a>,<5,b>}是Ａ到Ｂ的函数，试找出f的所有左逆和右逆(如果存在的话)。

6. 定义Ａ＝{1,2}×{1,2,3}上的等价关系Ｒ如下：?,∈Ａ，Ｒ< u, v> iff x+y=u+v。求出商集Ａ/Ｒ。

7. 设Ａ＝{1,2}，定义ＡＡ上的等价关系Ｒ如下：?f,g∈ＡＡ，fＲg iff f(A)=g(A)。试求出商集ＡＡ/Ｒ。

8. 某班级成立了三个运动队：篮球队、排球队和足球队。今有张、王、李、赵、陈5名同学，若已知张、王为篮球队员；张、李、赵为排球队员；李、赵、陈为足球队员，问能否从这5人中选出3名不兼职的队长？ 9. 图示出所有不同构的六阶树。

3

10. 找出下图的一个最小生成树。

f

5a

33

4b 8 h

461

2213

e 3g 4c

126

d

五、证明题

1. A→(B→C), C∧D→E, ~P→D∧~E => A→(B→P) 2. 判断下列公式是不是永真式，并加以说明：

(?x P(x) →?xQ(x))??x (P(x) →Q(x))

3. 设A、B是两个集合，证明：A?B iff P(A) ?P(B)

4．设U是全集，对U的任何子集A定义A的特征函数ΧA如下：

0 x?A

ΧA：U?{0,1}

ΧA (x)=

1 x?A

证明：f(A)=XA是2U到{0，1}U的双射。 5. 证明：若图G不连通，则GC必连通。

6. 设R是集合A上的关系。证明：R是偏序关系，iff R-1∩R=IA且Ｒ=Ｒ*。 7. 设R是集合A上的关系。证明：R是拟序关系，iff R-1∩R=Φ且Ｒ=Ｒ+。 8．证明：在任何简单平面图G中，必存在度不超过5的顶点。

9. 证明：设R和S都是A上的二元关系，证明t(R∪S)?t(R)∪t(S)。并用关系图的形式给出一个使真包含成立的例子。 10. 证明：（8，13）简单平面图不可2着色。

4

本文来源：https://www.bwwdw.com/article/b4ov.html