华中科技大学年《离散数学》期末考试试题

1、PAGE 判断（ ） 1. 若wff A是可满足式，那么A是矛盾式。（ ） 2. P=PQ是合适公式。（ ） 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是集合，则X2A iff XA。（ ） 10. 设A、B、C和D是四个非空集合, 且AC BD，则AB且CD。（ ） 11. 传递关系的对称闭包仍是传递的。（ ） 12.

2、 非空集合上的关系不是对称的，则必是反对称的。（ ） 13. 若R和S是二个有完全相同的二元组的集合，则称它们是相等的二元关系。（ ） 14. 设是一个非空集合，则上的等价关系都不是偏序关系。（ ） 15. 有限集上的全序关系必是良序关系。（ ） 16. 有限集上的偏序关系必是全序关系。（ ） 17 . 是偏序集，则的任何非空子集必有极小元。（ ） 18. 是偏序集，则的非空子集的上确界必是的最大元。（ ） 19. 是全序集，则的任何非空子集必有唯一极小元。（ ） 20. 是全序集，则的非空子集的下确界必是的最小元。（ ） 21. 无限集必与它的真子集等势。（ ） 22. 若AB，且A与B等势

3、，则B是无限集。（ ） 23. 若AB，则#A#B。（ ） 24. 连通的4度正则图一定没有桥。（ ） 25. p阶图的直径不可能等于p。选择（ ）1. 是wff （PQ）R(S(PQ)的代入实例的有 PR(SP) (PQ)R(S(PQ) (PQ)S(R(PQ) (PQ)R(R(PQ)（ ）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. 下列关系中正确的有： aa

4、, a aa, a aa, a aa, a aa, a aa, a（ ）4.设A=P(P(P()，下列关系式中正确的有： A A A A A A（ ）5.下列说法中正确的有： 任何集合都不是它自身的元素 任何集合的幂集都不是空集 若，则 任意两集合的笛卡尔积都不是空集（ ）6. 1,2,3,4,5上的关系R=,是 自反的 反自反的 对称的 反对称的 传递的（ ） 空集上的空关系是 关系。 相容 等价 偏序 拟序 良序（ ） 集=0,1上的恒等关系A是 关系。 相容 等价 偏序 拟序 良序（ ） 1,2,3,4,5上的全关系是 关系。 相容 等价 偏序 拟序 良序（ ） 1,2,3,4,5上的全

5、序关系一定是 关系。 相容 等价 偏序 拟序 良序（ ）11. 1,2,3,4,5上的良序关系一定是 自反的 反自反的 对称的 反对称的 传递的（ ）12. 设和都是到的关系，则下列关系式中正确的有： ()-1-1-1 ()-1-1-1 ()-1-1-1 ( eq oac(,)-1-1 eq oac(,)-1（ ）13. 函数f：，f()=是 入射 满射 双射 以上答案都不对（ ）14. 设=a,b为字母表，则f：*，f(x)=axb是 入射 满射 双射 以上答案都不对（ ）15. 若f、g是上的函数且gf是双射，则 f和g都是双射 f为满射 g为入射 f有左逆 g有右逆 （ ）16. 设p阶

6、图G不含圈，且恰有p-1条边（p2），则 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)= QRPRTPR的对偶式为A*= 。2. 若公式A(P, Q, R, S)的主析取范式为1,3,4,5,7，则A的主合取范式为 。3. 给命题变元P和Q指派真值T，R和S指派真值F，公式P(

7、QRP)QS的真值为 。4. 量词表示“有且仅有”，xP(x)表示恰好有一个个体满足谓词P。那么用量词，及等号“=”表示谓词后得到的公式_与xP(x)有相同的意义。5. 若用谓词I(x)表示“x是整数”，E(x)表示“x=y”，G(x,y)表示“xy”，那么命题“对任何整数x和y，xy且yx是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上的关系=,，=,，则dom()= 。8. 若A=a,b，B=1,2，则BA= 。9

8、. 用表示字母表=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，那么等价类aR和bR的交aRbR= 。13. 若G是p阶k度正则图，则它有 条边，它的补图有 条边。14. 考虑下图，它含有_等割点，_等桥（列出具体的顶点和边）。V2V4V5V1V3四、计算与作图1. 若集合=1,2,3,4上的关系=,。请用集合列举表示法表示r()、用关系图表示s()，

9、用关系矩阵表示t()。2. 设R和S都是1,2,3,4,5上的二元关系，且 R=,，S=,，则RS= ，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,是到的函数，试找出f的所有左逆和右逆(如果存在的话)。6. 定义1,21,2,3上的等价关系如下：,， iff x+y=u+v。求出商集/。7. 设1,2，定义上的等价关系如下：f,g，fg iff f(A)=g(A

10、)。试求出商集/。8. 某班级成立了三个运动队：篮球队、排球队和足球队。今有张、王、李、赵、陈5名同学，若已知张、王为篮球队员；张、李、赵为排球队员；李、赵、陈为足球队员，问能否从这5人中选出3名不兼职的队长？图示出所有不同构的六阶树。10. 找出下图的一个最小生成树。bcad546036388404820452815383062251210hgef五、证明题1. A(BC), CDE, PDE = A(BP)2. 判断下列公式是不是永真式，并加以说明：(x P(x) xQ(x)x (P(x) Q(x)3. 设A、B是两个集合，证明：AB iff P(A) P(B)4设U是全集，对U的任何子集A定义A的特征函数A如下：0 xA1 xAA：U0,1 A (x)=证明：f(A)=XA是2U到0，1U的双射。5. 证明：若图G不连通，则GC必连通。6. 设R是集合A上的关系。证明：R是偏序关