离散数学期末试卷A卷及标准答案 下载本文

《离散数学》试卷(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人同时选修三门课程。问

(1)三门课程都不选的学生有多少? (2)只选修计算机课程的学生有多少?

- 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时,便有R。证明R是Z×Z上的等价关系。 证明:

(1)自反性:

对任意的?Z×Z,有xy?xy,所以?x,y?R?x,y??R自反; (2)对称性:

对任意的,?Z×Z,若?x,y?R?u,v?? xy?uv?

T⑥⑦合取 EG⑧

uv?xy??u,v?R?x,y??R对称;

(3)传递性:

对任意的对任意的,,?Z×Z, 若?x,y?R?u,v?且

? xy?wt ?u,v?R?w,t?? xy?uv且uv?wt

- 4 -