北邮离散数学期末考试题

离散数学期末复习题

第一章集合论

一、判断题

（1）空集是任何集合的真子集． （ 错 ） （2）???是空集． （ 错 ） （3）?a???{a},a? （ 对 ） （4）设集合A???,则??1,2???2A. ( 对 ） 1,2,?1,2?（5）如果a?A?B，则a?A或a?B． （ 错 ） 解 a?A?B则a?A?B?A?B，即a?A且a?B，所以a?A且a?B （6）如果A∪B?B,则A?B. （ 对 ） （7）设集合A?{a1,a2,a3}，B?{b1,b2,b3}，则

A?B?{?a1,b1?,?a2,b2?,?a3,b3?} （ 错 ）

A

（8）设集合A?{0,1}，则??{??,0?,??,1?,?{0},0?,?{0},1?}是

离散数学期末复习题

第一章集合论

一、判断题

（1）空集是任何集合的真子集． （ 错 ） （2）???是空集． （ 错 ） （3）?a???{a},a? （ 对 ） （4）设集合A???,则??1,2???2A. ( 对 ） 1,2,?1,2?（5）如果a?A?B，则a?A或a?B． （ 错 ） 解 a?A?B则a?A?B?A?B，即a?A且a?B，所以a?A且a?B （6）如果A∪B?B,则A?B. （ 对 ） （7）设集合A?{a1,a2,a3}，B?{b1,b2,b3}，则

A?B?{?a1,b1?,?a2,b2?,?a3,b3?} （ 错 ）

A

（8）设集合A?{0,1}，则??{??,0?,??,1?,?{0},0?,?{0},1?}是

离散数学试题(B卷答案1）

一、证明题（10分）

1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R

证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)

?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R

2) ?x (A(x)?B(x))? ?xA(x)??xB(x)

证明 ：?x(A(x)?B(x))??x(?A(x)∨B(x))

??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)??xB(x)

二、求命题公式(P∨(Q∧R))?(P∧Q∧R)的主析取范式和主合取范式（10分）。

证明：(P∨(Q∧R))?(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R))

?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R)

?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨

(P∧Q∧R)

?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6

三、推理证明题（10分）

1） C∨D， (C∨D)? ?E，

一、填空

2．A，B，C表示三个集合，文图中阴影部分的集合表达式为 (B⊕C)-A

A C 4．公式(P?R)?(S?R)??P的主合取范式为 (?P?S?R)?(?P??S?R) 。 5．若解释I的论域D仅包含一个元素，则 ?xP(x)??xP(x) 在I下真值为 1 。 6．设A={1，2，3，4}，A上关系图如下，则 R^2= {(1,1),(1,3),(2,2),(2,4)} 。

?1??0???0?0?010??

101?000??000?? //备注：

?0??1R???0?0?100? ?010?001??000??

R2

7．设A={a，b，c，d}，其上偏序关系R的哈斯图如下，则R= {(a,b),(a,c), (a,d), (b,d), (c,d)} U {(a,a),(b,b)(c,c)(d,d)} 。

//备注：偏序满足自反性，反对称性，传递性

8．图的补图为 。

//补图:给定一个图G,又G中所有结点和所有能使G成为完全图的添加边组成的图,成为补图. 自补图:一个图如果同构于它的补图,则是自补图 9．设A={a，b，c，d} ，A上二元运算如下

广东技术师范学院

模拟试题

科 目：离散数学

考试形式：闭卷 考试时间: 120 分钟

系别、班级： 姓名： 学号：

一．填空题（每小题2分，共10分）

1. 谓词公式 xP(x) xQ(x)的前束范式是__ x y¬P(x)∨Q(y) __________。 2. 设全集E 1,2,3,4,5 ,A 1,2,3 ,B 2,5 ,则A∩ _{4,5}____，

3. 设A a,b,c ,B a,b ，则 (A) (B) __ {{c},{a,c},{b,c},{a,b,c}} __________，

(B) (A) _____Φ_______。

4. 在代数系统（N，+）中，其单位元是0，仅有 5．如果连通平面图G有n个顶点，e条边，则G有___e+2-n____个面。

二．选择题（每小题2分，共10分）

1. 与命题公式P (Q R)等价的公式是（ ）

（A）(P Q) R （B）(P Q) R （C）P (Q R) （D）P (Q R) 2. 设集合A a,b,c ,A上的二元关系R a,a , b,b 不具备关系( )

厦门大学《离散数学》课程试卷

软件学院2008年级

主考教师：金贤安 试卷类型：（A卷）

一、 选择题（共10题，每题3分，共30分）CDDAC DCADD

1、下列语句为命题的是（ ）。

A．勿踏草地；。

B．你去图书馆吗？； C．月球上有水； D．本命题为假。

2．下列推理中，（ ）是错误的。

A. 如果x是有理数，则它为整数。1/2是有理数。所以1/2是整数。

B. 若周末气温超过30度，小红就去游泳。小红周末没去游泳。所以周末气温没超过30度。 C. 下午小明或者去看电影，或者去打篮球。下午小明没去打篮球。因此下午小明去看电影了。 D. 若a能被4整除，则a能被2整除。a能被2整除。因此a能被4整除。 3．谓词公式?x(P(x)??yR(y))?Q(x)中的x( )。 A．只是约束变元 B．只是自由变元

C．既非约束变元又非自由变元 D．既是约束变元又是自由变元

4. 下列关系中，（ ）不是等价关系。 A. 非空集合的幂集的元素间包含关系； B. 集合之间的等势关系； C. 公式之间的等值关系； D. 图之间的同构关系。

5. 下面等值式中，（ ）是不正确的。 A. ?x(A(x)?B(x))??xA(x)??x

一、填空

2．A，B，C表示三个集合，文图中阴影部分的集合表达式为 (B⊕C)-A

A C 4．公式(P?R)?(S?R)??P的主合取范式为 (?P?S?R)?(?P??S?R) 。 5．若解释I的论域D仅包含一个元素，则 ?xP(x)??xP(x) 在I下真值为 1 。 6．设A={1，2，3，4}，A上关系图如下，则 R^2= {(1,1),(1,3),(2,2),(2,4)} 。

?1??0???0?0?010??

101?000??000?? //备注：

?0??1R???0?0?100? ?010?001??000??

R2

7．设A={a，b，c，d}，其上偏序关系R的哈斯图如下，则R= {(a,b),(a,c), (a,d), (b,d), (c,d)} U {(a,a),(b,b)(c,c)(d,d)} 。

//备注：偏序满足自反性，反对称性，传递性

8．图的补图为 。

//补图:给定一个图G,又G中所有结点和所有能使G成为完全图的添加边组成的图,成为补图. 自补图:一个图如果同构于它的补图,则是自补图 9．设A={a，b，c，d} ，A上二元运算如下

离散试卷及答案 离散数学试题(A卷及答案）

一、证明题（10分）

1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R

证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R)

?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R

2)?x(A(x)?B(x))? ?xA(x)??xB(x)

证明 ：?x(A(x)?B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)??xB(x) 二、求命题公式(P∨(Q∧R))?(P∧Q∧R)的主析取范式和主合取范式（10分）

证明：(P∨(Q∧R))?(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R))

?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R)

?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6

三、推理证明题（10分）

1） C∨D, (C∨D)? ?E, ?

1 / 5 最新离散数学期末考试题(附答案和含解析3)

2.设集合A={1，2，3}，下列关系R 中不．

是等价关系的是（ D ） A.R={<1，1>，<2，2>，<3，3>}； B.R={<1，1>，<2，2>，<3，3>，<3，2>，<2，3>}；

C. R={<1，1>，<2，2>，<3，3>，<1，2>，<2，1>，<1，3>，<3，1>，<2，3>，<3，2>}；

D. R={<1，1>，<2，2>，<3，3>，<1，2 >}.

3．在公式（x ?）F （x ，y ）→（? y ）G （x ，y ）中变元x 是（ B ）

A ．自由变元；(前面无?或?量词)

B ．既是自由变元，又是约束变元；

C ．约束变元；(前面有?或?量词)

D ．既不是自由变元，又不是约束变元.

4．设A={{1，2，3}，{4，5}，{6，7，8}}，下列选项正确的是（ C ）

A ．1∈A ；

B ．{1，2，3}?A ；

C ．{{4，5}}?A ；

D ．?∈A.

5.设论域为{l ，2}，与公式)()(x A x ?等价的是( A )

A.A (1)∨A (2)；

B. A (1)→A (2)；

C.A (1)∧A (2)；

D. A (2)→A (1).

6.一棵树有5个3度结点，2个2度结点，其它的都是l 度结点，那么这棵树的结点数是( B )

A.13 ；

B.14 ；

C.16 ；

D.17 .

//设一度结点数为n ，则有：5×3+2×2+n=2[(5+2+n)-1]

解得

模拟题2

广东技术师范学院

模拟试题

科 目：离散数学

考试形式：闭卷 考试时间: 120 分钟

系别、班级： 姓名： 学号：

一、填空20%（每空2分）：

1．若对命题P赋值1，Q赋值0，则命题P?Q（?表示双条件）的真值为 0 。

2．命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为 ?P→?Q 3．公式?(P?Q)?(P??(Q??S))的对偶公式为___?（P∧Q）∨（P∧?（Q∨?S））____。

4．图 的对偶图为

5.若关系R是等价关系，则R满足______自反性，对称性，传递性_____________________________。 6．代数系统?A,??是群，则它满足____结合律，有幺元 ，每个元素都有递元______。 7．若连通平面图G??V,E?共有r个面，其中V?v,E?e，则它满足的Eul