离散数学课程测试题
一、判断
（ ） 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 XA。
（ ） 10. 设A、B、C和D是四个非空集合, 且A×C B×D，则AB且CD。
（ ） 12. 非空集合上的关系不是对称的，则必是反对称的。
（ ） 13. 若R和S是二个有完全相同的二元组的集合，则称它们是相等的二元关系。
（ ） 14. 设Ａ是一个非空集合，则Ａ上的等价关系都不是偏序关系。
（ ） 15. 有限集上的全序关系必是良序关系。
（ ） 16. 有限集上的偏序关系必是全序关系。
（ ） 17 . <A;R>是偏序集，则Ａ的任何非空子集必有极小元。
（ ） 18. <A;R>是偏序集，则Ａ的非空子集Ｂ的上确界必是Ｂ的最大元。
（ ） 19. <A;R>是全序集，则Ａ的任何非空子集必有唯一极小元。
（ ） 20. <A;R>是全序集，则Ａ的非空子集Ｂ的下确界必是Ｂ的最小元。
（ ） 21. 无限集必与它的真子集等势。
（ ） 22. 若AB，且A与B等势，则B是无限集。
（ ） 23. 若AB，则#A<#B。
（ ） 24. 连通的4度正则图一定没有桥。
二、选择
（ ）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(Φ)))，下列关系式中正确的有：
① Φ∈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
③ (Ｒ－Ｓ)-1＝Ｒ-1－Ｓ-1 ④ (ＲＳ)-1＝Ｒ-1Ｓ-1
（ ）13. 函数f：Ｒ×Ｒ→Ｒ×Ｒ，f(<x,y>)=<x+y,x-y>是
① 入射 ② 满射 ③ 双射 ④ 以上答案都不对
（ ）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, 1, 2, 2, 2, 2, 2, 2 ) ② ( 1, 1, 1, 2, 2, 2, 2, 3 )
③ ( 1, 1, 2, 2, 2, 2, 3, 3 ) ④ ( 1, 1, 1, 1, 4, 4, 4, 4 )
三、填空
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”，那么命题“对任何整数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，
公式xy (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}，则BA= 。
9. 用ε表示字母表Σ={a,b}上的空串，定义f：Σ*→Σ*如下：
x∈Σ* f(x)=axb 则f({ε,a,b})= 。
10. 用ε表示字母表Σ={a,b}上的空串，定义f：Σ*→Σ*如下：
x∈Σ* f(x)=axb 则f( )={aab,abb,ab}。
11. 在集Ａ={1,2}上可定义两个不同的等价关系，它们是 和 。
12. 若Ｒ为集合Ａ上的等价关系，a b，那么等价类[a]R和[b]R的交[a]R∩[b]R= 。
13. 若G是p阶k度正则图，则它有 条边，它的补图有 条边。
14. 考虑下图，它含有_________等割点，___________等桥（列出具体的顶点和边）。
四、计算与作图
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＝{<a,1>,<b,2>}是Ａ到Ｂ的函数，试出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}上的等价关系Ｒ如下：<x,y>,<u,v>∈Ａ，<x,y>Ｒ< u, v> iff x+y=u+v。求出商集Ａ/Ｒ。
7. 设Ａ＝{1,2}，定义ＡＡ上的等价关系Ｒ如下：f,g∈ＡＡ，fＲg iff f(A)=g(A)。试求出商集ＡＡ/Ｒ。
8. 某班级成立了三个运动队：篮球队、排球队和足球队。今有张、王、李、赵、陈5名同学，若已知张、王为篮球队员；张、李、赵为排球队员；李、赵、陈为足球队员，问能否从这5人中选出3名不兼职的队长？ 9.图示出所有不同构的六阶树。
10. 出下图的一个最小生成树。
五、证明题
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议