离散数学大一考试题

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

一、命题符号化（共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上有多少种不同的等价关系？

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))? ________________

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.

一、填空题

1 设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; (B)＝ __________________________ .

2. 设有限集合A, |A| = n, 则 | (A×A)| = __________________________.

3. 设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________.

4. 已知命题公式G＝ (P Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________.

6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A B＝_________________________; A B＝_________________________;A－B＝ _____________________

《离散数学》试题及答案

一、填空题

1 设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝ {3} ; {3},{1,3},{2,3},{1,2,3}} .

2. 设有限集合A, |A| = n, 则 |?(A×A)| = 2 .

3. 设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是?1= {(a,1), (b,1)}, ?2= {(a,2), (b,2)},?3= {(a,1), (b,2)}, ?4= {(a,2), (b,1)}, 其中双射的是 ?3, ?4 .

4. 已知命题公式G＝?(P?Q)∧R，则G的主析取范式是 (P∧?Q∧R) 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为 12 ，分枝点数为 3 .

6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝ {4} ; A?B＝{1,2,3,4}; A－B＝ {1,2} .

7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是 自反性 , 对

一、填空题

1 设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝__{3}__________________;

?(A) - ?(B)＝ ___________________{3},{1,3},{2,3},{123}______ .

2. 设有限集合A, |A| = n, 则 |?(A×A)| = _____2^(n^2)_____________________.

3. 设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________.

4. 已知命题公式G＝?(P?Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________.

5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________.

6 设A、B为两个集合, A= {1,2,4}

第1章

一.填空题 1.

2. 公式P→(Q→R)在联结词全功能集{﹁,∨}中等值形式为___________________。

3. 4.

5. 6.

7. 全体小项的析取式必为____________________式。

8. P,Q为两个命题，则德摩根律可表示为7. 全体小项的析取式必为_________式。

9. P,Q为两个命题，则吸收律可表示为____________________ 。

10. 设P：我有钱，Q：我去看电影。命题“虽然我有钱，但是我不去看电影”符号化为_____ _______________。

11. 设P：我生病，Q：我去学校。命题“如果我生病，那么我不去学校”符号化为_________ ___________。 12. 13.

14.

15. 设P、Q为两个命题，交换律可表示为____________________。 16.

17. 命题“如果你不看电影，那么我也不看电影”（P：你看电影，Q：我看电影）的符号化 为____________________ 。 18. 19. 20.

21. P：你努力，Q：你失败。命题“除非你努力，否则你将失败”的翻译为__________

《离散数学I》模拟试题

一、单选题（每小题2分，共20分）

1 以下语句是命题的是（ B ）。 A． y等于x。 B． 每个自然数都是奇数。 C． 请爱护环境。 D． 你今天有空吗？

2 设α是一赋值，α(p)= α(q)=1，α(r)=0，下列公式的值为真值为假的是（ ）。 A．p∧(q∨r) B．(p?r) ? (?r?q) C．(r?q) ∧(q?p) D．(r?q)

3 以下联结词的集合（ D ）不是完备集。 A．{?,∧,∨, ?,?} B．{?,∧,∨} C．{?, ?} D．{∧,∨}

4 公式A的对偶式为A*，下列结果成立的是（ ）。 A．A?A* B．?A?A* C．A|=|A* D．?A|=|A*

5 假设论域是正整数集合，下列自然语言的符号化表示中，（ ）的值是真的。 A．?x?yG(x,y)，其中G(x,y)表示xy=y B．?x?yF(x,y)，其中F(x,y)表示x+y=y C．?x?yH(x,y)，其中H(x,y)表示x+y=x D．?x?yM(x,y)，其中M(x,y)表示xy=x

6．以下式子错误的是（ ）。 A．?x?A(x) |=