离散数学期末试卷及答案

《离散数学》期末考试试卷（A卷）

--------------------------------------------------------------------------------------------------------------------------------------------------- 03．A?{?,{a},{b},{a,b}}上的包含关系为?，则子集C?{{a},{b}}的极大元为

＿＿＿＿，极小元为＿＿＿＿，上界为＿＿＿＿，下界为＿＿＿＿，最大元为＿＿＿， 最小元为＿＿＿（若没有填无）。 04．设A?{a,b}，则A上共有＿＿＿个不同的等价关系。

05．有一个函数f:X?Y，若要使f有逆函数，f就必须是＿＿＿。

三、演算题（每小题10分，总30分）

年级 专业 姓名 学号 座位号

大登

一、单项选择（在备选答案中选出一个正确答案，并将其号码填在题干后的括号内。每题3分，共18分） 01．下列语句中，真命题是（ ）

A、我正在说谎； B、若1?2?3，则雪是黑的； C、这句话

离散数学期末复习

一、选择题 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具有 性质。

离散数学期末复习各个章节要点纲要（及定理）

离散数学定义定理

1.3.1命题演算的合式公式规定为： （1）单个命题变元本身是一个合式公式。 （2）如果A是合式公式，那么┐A是合式公式。

（3）如果A和B是合式公式，那么（A∨B）、（A∧B）、（A→B）、（A?B）、都是合式公式。 （4）当且仅当有限次地应用（1）（2）（3）所得到的包含命题变元，连接词和圆括号的符号串是合式公式。

1.3.2 设Ai是公式A的一部分，且Ai是一个合式公式，称Ai是A的子公式。

1.3.3 设P为一命题公式，P1,P2,……，Pn为出现在P中的所有命题变元，对P1,P2,……，Pn指定一组真值称为对P的一种指派。若指定的一种指派，使P的值为真，则称这组指派为成真指派。若指定的一种指派，使P的值为假，则称这种指派为成假指派。 含n个命题变元的命题公式，共有2n个指派。

1.3.4 给定两个命题公式A和B，设P1,P2,……，Pn为所有出现于A和B中的原子变元，若给P1,P2,……，Pn任一组真值指派，A和B的真值都相同，称A和B是等价的，记做A <=>B。

1.3.5 设A为一命题公式，若A在它的各种指派情况下，其取值均为真，则称A为重言式或永真式。 1.3.6

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

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

离散数学期末复习题

一、选择题

1、永真式的否定是（2） (2) 永假式

2、设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，则下列真命题为(1) (1)P?Q?R

3、设P：我听课，Q：我看小说，则命题R“我不能一边听课，一边看小说”的符号化为⑵ ⑵P??Q(3)

提示：R??(P?Q)?P??Q 4、下列表达式错误的有⑷ ⑷P?(?P?Q)?P?Q 5、下列表达式正确的有⑷ ⑷?(P?Q)??Q

6、下列联接词运算不可交换的是(3) (3)?

6、设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢y，则命题“有的人喜欢所有的花”的逻辑符号化为⑷ ⑷?x(M(x)??y(F(y)?H(x,y))

7、设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些

老

师”的逻辑符号化为⑵

⑵?x(L(x)??y(J(y)?A(x,y)))

8、谓词公式?x(P(x)??yR(y))?Q(x)中的 x是⑶ ⑶既是自由变元又是约束变元 9、下列表达式错误的有⑴

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

离散数学期末复习题

一、选择题

1、永真式的否定是（2） (2) 永假式

2、设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，则下列真命题为(1) (1)P?Q?R

3、设P：我听课，Q：我看小说，则命题R“我不能一边听课，一边看小说”的符号化为⑵ ⑵P??Q(3)

提示：R??(P?Q)?P??Q 4、下列表达式错误的有⑷ ⑷P?(?P?Q)?P?Q 5、下列表达式正确的有⑷ ⑷?(P?Q)??Q

6、下列联接词运算不可交换的是(3) (3)?

6、设D：全总个体域，F（x）：x是花，M(x) ：x是人，H(x,y)：x喜欢y，则命题“有的人喜欢所有的花”的逻辑符号化为⑷ ⑷?x(M(x)??y(F(y)?H(x,y))

7、设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些

老

师”的逻辑符号化为⑵

⑵?x(L(x)??y(J(y)?A(x,y)))

8、谓词公式?x(P(x)??yR(y))?Q(x)中的 x是⑶ ⑶既是自由变元又是约束变元 9、下列表达式错误的有⑴

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

1 / 6

一、 命题逻辑部分

1．计算真值表、并由此写出主析取与主合取范式(一个命题公式的主范式具有唯一的表示形式，这样可以精减一个推理系统，去掉多余的等价的前提。其唯一性借助于小项或大项的设计，一个公式中所用到的小项或大项个数与其真值表中所对应的1或0的个数相对应，不能多也不能少)。注意：真值表与公式有什么区别？

2．设 A 、B 是两个命题公式，证明：

a) A B 当且仅当A B 是永真式。b) A B 的充要条件是A B 且B A 。

等价与蕴涵是对两个公式进行比较的概念，性质b)说明两者之间的关系，相对而言蕴涵比等价更重要。与上面两个性质相关联的一个等价公式是：A B A →B ∧B →A.3．证明 P →(Q →R )?Q →(P →R )? ┐R →(Q → ┐P ) 4．证明从前提P →Q ，┐(Q ∨R)可演绎出┐P .

5．证明R →S 可从前提P →(Q →S)，┐R ∨P 和Q 推出。 ├ 6、使用推理规则或归结推理，论证推理形式 1) P →Q, R →?Q ,R ∨S, S →?Q ├?P

2)?P ?Q, S →?Q, ?R, R ∨S ├ P

二、 谓词逻辑

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，

《离散数学》期末复习

一、各章复习要求与重点

第一章 命题逻辑

[复习知识点]

１、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题 ２、命题公式与解释，真值表，公式分类（永真、永假、可满足），公式的等价 ３、析取范式、合取范式，极小（大）项，主析取范式、主合取范式 ４、公式类别的判别方法（真值表法、等值演算法、主析取/合取范式法） ５、公式的蕴涵与逻辑结果 ６、形式演绎

本章重点内容：命题与联结词、公式与解释、析取范式与合取范式、公式永真性的判定、形式演绎 [复习要求]

１、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。

２、理解公式与解释的概念；掌握求给定公式真值表的方法，用基本等价式化简其他公式，公式在解释下的真值。

３、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等价式或真值表将公式化为主析取（合取）范式的方法。

４、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价的方法。

５、理解公式蕴涵与逻辑结果的概念，掌握基本蕴涵式。 6、掌握形式演绎的证明方法。 [本章重点习题]

P93，1； P98，2，3； P104，2，3； P107