《离散数学》试卷（A卷）
专业 年级 班 姓名 学号 题号 一 二 三 四 五 得分 一、 选择题（共5 小题，每题 3 分，共15 分）
1、设A={1,2,3},B={2,3,4,5},C={2,3},则(A?B)?C为(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、?x?y(x*y?y) B、?x?y(x*y?4) C、?x(x*y?x) D、?x?y(x*y?2) 4、全域关系EA不具有下列哪个性质（ B ）。
A、自反性 B、反自反性 C、对称性 D、传递性
5、函数f:R?R,f(x)??12x?6是（ D ）。
A、单射函数 B、满射函数 C、既不单射也不满射 D、双射函数
二、填充题（共 5 小题，每题 3 分，共15 分）
1、设|A|=4，|P(B)|=32，|P(A?B)|=128，则|A?B|=??2???.
总分 - 1 -
2、公式Q?(P??Q)的主合取范式为 。
3、对于公式?x(P(x)?Q(x))，其中P(x)：x=1， Q(x)：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、(p??p)?((q??q)?r)是矛盾式。 （ T ） 4、R?S?R?T?R?(S?T)。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f、g分别是单射,则f?g是单射。 （ T ） 7、若f?g是满射，则g是满射。 （ F ） 8、若B?A，则P(B)?P(A)。 （ T ） 9、若R具有自反性，则R?1也具有自反性。 （ T ）
10、A?B并且A?B不可以同时成立。 （F ）
四、计算题（共 3 小题，每题 10 分，共30 分）
1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问
（１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？
- 2 -
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。
求公式?x?y(F(x,y)?F(f(x),f(y)))在I下的真值。 解: 由消去量词不等式得：
?x?y(F(x,y)?F(f(x),f(y)))
?( 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}} 。 则对应的等价关系如下:
- 3 -
R1={<2,3>,<3,2>}∪IA；R2={<1,3>,<3,1>}∪IA ； R3={<1,2>,<2,1>}∪IA；R4= EA ；R5= IA 。
五、证明题（共 3 小题，每题 10 分，共30 分）
1、 符号化下列命题，并证明其有效性：
三角函数都是都是周期函数；一些三角函数是连续函数。所以一些周期函数是连续函数。
证明：设P(x)：x 是三角函数； Q(x) ：x是周期函数； S(x)：x是连续函数。
上述句子符号化为：
前提：?x(P(x)?Q(x))、?x(P(x)?S(x))
结论： ?x(Q(x)?S(x))
①?x(P(x)?S(x)) ②P(a)?S(a) ③?x(P(x)?Q(x)) ④P(a)?Q(a) ⑤P(a)
P ES① P US② T①化简
⑥S(a) T①化简
⑦Q(a) T④⑤假言推理 ⑧S(a)?Q(a) ⑨?x(S(x)?Q(x)
2、设R表示Z×Z上的二元关系，当且仅当xy=uv时，便有
(1)自反性：
对任意的
对任意的
T⑥⑦合取 EG⑧
uv?xy??u,v?R?x,y??R对称；
(3)传递性：
对任意的对任意的
? xy?wt ?u,v?R?w,t?? xy?uv且uv?wt
- 4 -