离散数学课程测试题
一、判断
（）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(Φ)))，下列关系式中正确的有：
①Φ∈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(
①入射②满射③双射④以上答案都不对
（）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”，那么命题“对任何
