《离散数学》试卷（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 时，便有<x,y>R<u,v>。
证明R 是Z ×Z 上的等价关系。
证明：
(1)自反性：
对任意的<x,y>∈Z ×Z ，有xy xy =，所以><><y x R y x ,,⇒R 自反；
(2)对称性：
对任意的<x,y>,<u,v>∈Z ×Z,若><><v u R y x ,,⇒ uv xy =⇒ xy uv =⇒><><y x R v u ,,⇒R 对称；
(3)传递性：
对任意的对任意的<x,y>,<u,v>,<w,t>∈Z ×Z, 若><><v u R y x ,,且
><><t w R v u ,,⇒ uv xy =且wt
uv =⇒ wt xy =
⇒><><t w R y x ,,⇒R 传递；
所以R 是等价关系。
3、设>-+=<><⨯→⨯y x y x y x f R R R R f ,),(,:，证明f 是双射函数。
证明：
（1）满射性：>-+<∃⨯>∈<∀2
,2,,v u v u R R v u 使得 >=<>-+<v u v u v u f ,)2
,2( f ∴满射。
（2）单射性：R R v u y x ⨯>∈<><∀,,,，有
>-+>=<-+⇔<><=><v u v u y x y x v u f y x f ,,),(),(
⇔v u y x v u y x -=-+=+,
⇔v y u x ==,
⇔>>=<<v u y x ,,
f ∴单射
综上所述，f 双射。