河北大学离散数学考试题

离散数学 考试题(后附详细答案)

一、命题符号化（共6小题，每小题3分，共计18分） 1. 用命题逻辑把下列命题符号化

a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（?P?Q）?(P?R?S)

b) 我今天进城，除非下雨。 设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：?Q→P或?P→Q c) 仅当你走，我将留下。 设P表示命题“你走”，Q表示命题“我留下”，命题符号化为： Q→P 2. 用谓词逻辑把下列命题符号化 a) 有些实数不是有理数 设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为：

?x(R(x) ??Q(x)) 或 ??x(R(x) →Q(x))

b) 对于所有非零实数x，总存在y使得xy=1。 设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为： ?x(R(x) ??E(x,0) →?y(R(y) ?E(f(x,y),1))))

c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=

离散数学 考试题(后附详细答案)

一、命题符号化（共6小题，每小题3分，共计18分） 1. 用命题逻辑把下列命题符号化

a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（?P?Q）?(P?R?S)

b) 我今天进城，除非下雨。 设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：?Q→P或?P→Q c) 仅当你走，我将留下。 设P表示命题“你走”，Q表示命题“我留下”，命题符号化为： Q→P 2. 用谓词逻辑把下列命题符号化 a) 有些实数不是有理数 设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为：

?x(R(x) ??Q(x)) 或 ??x(R(x) →Q(x))

b) 对于所有非零实数x，总存在y使得xy=1。 设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为： ?x(R(x) ??E(x,0) →?y(R(y) ?E(f(x,y),1))))

c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=

离散数学 考试题(后附详细答案)

一、命题符号化（共6小题，每小题3分，共计18分） 1. 用命题逻辑把下列命题符号化

a) 假如上午不下雨，我去看电影，否则就在家里读书或看报。 b) 我今天进城，除非下雨。 c) 仅当你走，我将留下。 2. 用谓词逻辑把下列命题符号化 a) 有些实数不是有理数

b) 对于所有非零实数x，总存在y使得xy=1。

c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b. 二、简答题（共6道题，共32分）

1. 求命题公式(P→(Q→R))?(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋

值。（5分） 2. 设个体域为{1,2,3}，求下列命题的真值（4分） a) ?x?y(x+y=4)

b) ?y?x (x+y=4)

3. 求?x(F(x)→G(x))→(?xF(x)→?xG(x))的前束范式。（4分） 4. 判断下面命题的真假，并说明原因。（每小题2分，共4分） a) （A?B）－C=(A-B) ?(A-C)

b) 若f是从集合A到集合B的入射函数，则|A|≤|B| 5. a) b) 6.

设A是有穷集，|A|=5，问（每小题2分，共4分） A上有多少种不同的等价关系？

1. 写出命题公式 ﹁（P →（P∨ Q））的真值表。

P?Q?(P?Q)?(?P??Q)2.证明

3. 证明以下蕴涵关系成立： ?P?(P?Q)?Q

4. 写出下列式子的主析取范式： ?(P?Q)?(P?R)

5. 构造下列推理的论证：p∨q, p→?r, s→t, ?s→r, ?t ? q

6. 用反证法证明：p→(?(r∧s)→?q), p, ?s ? ?q

7. 请将下列命题符号化：

所有鱼都生活在水中。

8. 请将下列命题符号化：

存在着不是有理数的实数。

9. 请将下列命题符号化：

尽管有人聪明，但并非一切人都聪明。

10. 请将下列命题符号化：

对于所有的正实数x,y，都有x+y≥x。

11. 请将下列命题符号化：

每个人都要参加一些课外活动。

12. 请将下列命题符号化：

某些人对某些药物过敏。 13. 求?y(P(x)?Q(y))??yR(y)的对偶式:

14. 求下列谓词公式的前束范式： ?x?y(?zP(x,z)?P(y,z))??uQ(x,y,u)

15. 证明：

16. 用反证法

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

一、证明题（10分）

1) (P∧Q∧A?C)∧(A?P∨Q∨C)? (A∧(P?Q))?C。P<->Q=(p->Q)合取（Q->p）

证明: (P∧Q∧A?C)∧(A?P∨Q∨C)

?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C)

?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C反用分配律 ??((P∧Q∧A)∨(A∧?P∧?Q))∨C

??( A∧((P∧Q)∨(?P∧?Q)))∨C再反用分配律 ??( A∧(P?Q))∨C ?(A∧(P?Q))?C

2) ?(P?Q)? ?P??Q。

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

二、分别用真值表法和公式法求(P?(Q∨R))∧(?P∨(Q?R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。

主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由 析取范式经等值演算法算得。 证明：

公式法：因为(P?(Q∨R))∧(?P∨(Q?R))

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

?(?P∨Q∨R)∧(((?P∨Q)∧(?P∨R))∨(?Q∧?R))分配律

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

一、证明题（10分）

1) (P∧Q∧A?C)∧(A?P∨Q∨C)? (A∧(P?Q))?C。P<->Q=(p->Q)合取（Q->p）

证明: (P∧Q∧A?C)∧(A?P∨Q∨C)

?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C)

?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C反用分配律 ??((P∧Q∧A)∨(A∧?P∧?Q))∨C

??( A∧((P∧Q)∨(?P∧?Q)))∨C再反用分配律 ??( A∧(P?Q))∨C ?(A∧(P?Q))?C

2) ?(P?Q)? ?P??Q。

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

二、分别用真值表法和公式法求(P?(Q∨R))∧(?P∨(Q?R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。

主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由 析取范式经等值演算法算得。 证明：

公式法：因为(P?(Q∨R))∧(?P∨(Q?R))

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

?(?P∨Q∨R)∧(((?P∨Q)∧(?P∨R))∨(?Q∧?R))分配律

北大离散数学课件

第7讲 关系幂运算与关系闭包 北京大学内容提要 关系幂(power)运算 关系闭包(closure)

2013-8-14

《集合论与图论》第7讲

北大离散数学课件

关系的幂运算

n次幂的定义 指数律 幂指数的化简

2013-8-14

《集合论与图论》第7讲

北大离散数学课件

关系的n次幂 关系的n次幂(nth

power): 设R A A,

n N, 则 (1) R0 = IA; (2) Rn+1 = Rn○R, (n 1).

R R R R n n个R

Rn表示的关系,12013-8-14

是R的关系图中长度为n 的有向路径的起点与终点的关系.2 n-1《集合论与图论》第7讲

n3

北大离散数学课件

关系幂运算(举例) 例:

设A={a,b,c}, R A A, R={<a,b>,<b,a>,<a,c>}, 求R的各次幂. b 解: bc G( R ) a G( R0 ) c

a

2013-8-14

《集合论与图论》第7讲

北大离散数学课件

关系幂运算(举例,续) 解(续):

R0 = I A , R1 = R0○R = R = {,,}, R2

2010级《离散数学》试题

一、判断题（每题1分，共10分）

1.任何命题公式都存在惟一的析取范式。 （ ） 2. 封闭的公式在任何解释下都变成命题。 ( ) 3. (?p?q)?(r?s)的层数是3 （ ）4.??x(B?A(x))??x?(B?A(x)). ( ) 5. 设A,B,C是三集合，已知A?B＝A?C，则一定有B＝C. ( ) 6.矩阵的等价、相似、合同都是等价关系。 ( ) 7.已知a是群集的二阶元，则={a,a2}. ( ) 8.有界格中某元的的补元不止一个，则它不是分配格。 ( ) 9.有向图是强连通的，则它一定是单向连通的，也弱连通的。 ( ) 10.二部图K3,3是欧拉图也是哈密顿图。 ( ) 二、填空题（每小题2分，共20分）

1.((p?q)??q)?p从公式的类型看，它属于 式。 2.?x(A(x)?B(x))? ________________

东北大学17秋学期《离散数学》在线作业2

东大100分 1/d 2/d 3/d

一、单选题（共 10 道试题，共 50 分。）

1. 下面的命题公式中不是永真式的是（ ）。 A. (P∧Q)→Q B. (P∧(P→Q))→Q C. P→(P∨Q) D. (P∨Q)→P 正确答案：D

2. 一个有向图是根树，当且仅当 该图（ A. 有树根，也有树叶；

B. 忽略边的方向时，是连通无回路的无向图； C. 有一个结点可以到达任何其余结点； D. 恰有一个结点入度为0：其余结点入度为1。 正确答案：D

3. 一棵树有7片树叶，3个3度结点，其余都是4度结点，该树有（ A. 4； B. 3； C. 2； D. 1；

E. 不在给定的选择的范围内。 正确答案：D

1

4度结点。）个 东北大学17秋学期《离散数学》在线作业2

4. 下面是

\

的谓词推理过程。在这个过程中每一步中的（ ）处是此步所用的推理规则。请写出这些推理规则。

⑴ $x(A(x)úB(x)), ( )

www.4juan.com 专注于收集各类历年试卷和答案

一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选

项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路

2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14

3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c)

B.(a∧b)∨(a’∧b)

C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.