离散数学期末考试重点

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

软件学院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

离散数学试题(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，

广东技术师范学院

模拟试题

科 目：离散数学

考试形式：闭卷 考试时间: 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 不具备关系( )

离散试卷及答案 离散数学试题(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、

下列各选项错误的是

A、? ? ? B、? ? ? C、? ?{ ?} D、? ? {? }

2、命题公式 (p∧q) →p 是 A、矛盾式 B、重言式 C、可满足式 D、等值式

3、如果是R是A上的偏序关系，R-1是R的逆关系，则R∪R-1是

A、等价关系 B、偏序关系 C、全序关系 D、都不是

4、下列句子中那个是假命题？ A、

是无理数.

B、2 + 5 ＝8.

C、x + 5 ＞ 3 D、请不要讲话！ 5、下列各选项错误的是？ A、? ? ? B、? ? {? } C、? ?{ ?} D、{? } ? ?

6、命题公式 p→（p?q?r）是？ A、重言式 B、矛盾式 C、可满足式 D、等值式

7、函数f : N→N, f(x)=x+5,函数f是 A、单射 B、满射 C、双射 D、都不是

8、设D=,则V={a,b,c,d,e,f},R={ ,,,,},有向图D为 A、强连通 B、单向连通 C、弱连通

D、不连通的

9、关系R1和R2具有反自反性，下面运算后，不能保持自反性的是 A、R1 ?R2 B、R1-1 C、R1 ?R2 D、R1 -R2

10、连通平面图G有4个

离散数学

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

1．若对命题P赋值1，Q赋值0，则命题P?Q的真值为 。 2．命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化为 3．公式?(P?Q)?(P??(Q??S))的对偶公式为

4．图 的对偶图为

5．若关系R是等价关系，则R满足 性质。 6．关系R的传递闭包t (R) = 。 7．代数系统?A,??是群，则它满足 8．设?A,?,??和?B,?,??是两代数系统，f是从?A,?,??到?B,?,??的同态映射，则f具有 性质。

一、填空

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上二元运算如下

离散数学期末复习题

第一章集合论

一、判断题

（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?}是

一、填空

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上二元运算如下

模拟题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