《离散数学》试卷（A 卷）
一、 选择题（共5 小题，每题 3 分，共15 分）
1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕⋃)(为(C )。
A 、{1,2}
B 、{2,3}
C 、{1,4,5}
D 、{1,2,3}
2、下列语句中哪个是真命题 ( A )
A 、如果1+2=3，则4+5=9；
B 、1+2=3当且仅当4+5≠9。
C 、如果1+2=3，则4+5≠9；
D 、1+2=3仅当4+5≠9。
3、个体域为整数集合时，下列公式（ C ）不是命题。
A 、)*(y y x y x =∀∀
B 、)4*(=∃∀y x y x
C 、)*(x y x x =∃
D 、)2*(=∃∃y x y x
4、全域关系A E 不具有下列哪个性质（ B ）。
A 、自反性
B 、反自反性
C 、对称性
D 、传递性
5、函数612)(,:+-=→x x f R R f 是（ D ）。
A 、单射函数
B 、满射函数
C 、既不单射也不满射
D 、双射函数
二、填充题（共 5 小题，每题 3 分，共15 分）
1、设|A|=4，|P(B)|=32，|P(A ⋃B)|=128，则|A ⋂B|=ˍˍ2ˍˍˍ.
2、公式)(Q P Q ⌝∨∧的主合取范式为 。
3、对于公式))()((x Q x P x ∨∃，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为ˍˍˍ1ˍˍˍ。
4、设A ＝{1,2,3,4}，则A 上共有ˍˍˍ15ˍˍˍˍ个等价关系。
5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。
三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分）
1、“这个语句是真的”是真命题。 （ F ）
2、“张刚和小强是同桌。”是复合命题。 （ F ）
3、))(()(r q q p p ∧⌝∧→⌝∨是矛盾式。 （ T ）
4、)(T S R T R S R ⋂⋅⊆⋅⋃⋅。 （ F ）
5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ）
6、若f 、g 分别是单射,则g f ⋅是单射。 （ T ）
7、若g f ⋅是满射，则g 是满射。 （ F ）
8、若A B ⊆，则)()(A P B P ⊆。 （ T ）
9、若R 具有自反性，则1-R 也具有自反性。 （ T ）
10、B A ∈并且B A ⊆不可以同时成立。 （F ）
四、计算题（共 3 小题，每题 10 分，共30 分）
1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问
（１）三门课程都不选的学生有多少？
（２）只选修计算机课程的学生有多少？
1、解：设A ：选数学课程，B ：选计算机课程，C ：选商贸课程。文氏图如下所示：
则(1)三门课都不会选修的人有：260-(64+94+58)+(28+26+22)-14=106。
(2)只选修计算机课程的学生有：94-12-14-8=60。
2、给定解释I 如下：
(a)个体域D={3,4};
(b)f(x)为f(3)=4,f(4)=3;
(c)F(x,y)为F(3,3)=F(4,4)=0,F(3,4)=F(4,3)=1。
求公式)))(),((),((y f x f F y x F y x →∀∀在I 下的真值。
解: 由消去量词不等式得：
)))(),((),((y f x f F y x F y x →∀∀ ⇔( F(3,3)→F(f(3),f(3)))∧ ( F(4,3)→F(f(4),f(3))) ∧( F(3,4)→F(f(3),f(4)))∧( F(4,4)→F(f(4),f(4)))
⇔ (0→0) ∧(1→1) ∧(1→1) ∧(0→0)
⇔1
所以公式在I 下的真值为1。
3、设A={1,2,3}，求A 上所有的等价关系。
解： A 的所有划分如下：
π1={{1}，{2,3}}；π2={{2}，{1,3}}；
π3={{3}，{1,2}}；π4={{1,2,3}}；
π5 ={{1},{2},{3}} 。
则对应的等价关系如下:
R1={<2,3>,<3,2>}∪I A ；R2={<1,3>,<3,1>}∪I A ； R3={<1,2>,<2,1>}∪I A ；R4= E A ；R5= I A 。
五、证明题（共 3 小题，每题 10 分，共30 分）
1、 符号化下列命题，并证明其有效性：
三角函数都是都是周期函数；一些三角函数是连续函数。所以一些周期函数是连续函数。
证明：设P(x)：x 是三角函数； Q(x) ：x 是周期函数； S(x)：x 是连续函数。
上述句子符号化为：
前提：))()((x Q x P x →∀、))()((x S x P x ∧∃
结论： ))()((x S x Q x ∧∃
①))()((x S x P x ∧∃
P ②)()(a S a P ∧
ES ① ③))()((x Q x P x →∀
P ④)()(a Q a P →
US ② ⑤)(a P T ①化简
⑥)(a S T ①化简
⑦)(a Q T ④⑤假言推理
⑧)()(a Q a S ∧
T ⑥⑦合取 ⑨)()((x Q x S x ∧∃
EG ⑧
2、设R 表示Z ×Z 上的二元关系，当且仅当xy=uv 时，便有R。证明R 是Z ×Z 上的等价关系。
证明：
(1)自反性：
对任意的∈Z ×Z ，有xy xy =，所以><>(2)对称性：
对任意的,∈Z ×Z,若><><>(3)传递性：
对任意的对任意的,,∈Z ×Z, 若><>><>uv =⇒ wt xy =
