国开离散数学本科试题

《离散数学》复习资料 2014年12月

一、单项选择题（每小题3分，本题共15分）

1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( A )．

A． A?B，且A?B B．B?A，且A?B C．A?B，且A?B D．A?B，且A?B 2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( D )．

图一 A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的 3．设图G的邻接矩阵为

?01100??10011???

?10000???01001????01010??则G的边数为( B )．

A．6 B．5 C．4 D．3

4．无向简单图G是棵树，当且仅当( A )．

A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 C．G的边数比结点数少1 D．G中没有回路． 5．下列公式 ( C

《离散数学》复习资料 2014年12月

一、单项选择题（每小题3分，本题共15分）

1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( A )．

A． A?B，且A?B B．B?A，且A?B C．A?B，且A?B D．A?B，且A?B 2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( D )．

图一 A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的 3．设图G的邻接矩阵为

?01100??10011???

?10000???01001????01010??则G的边数为( B )．

A．6 B．5 C．4 D．3

4．无向简单图G是棵树，当且仅当( A )．

A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 C．G的边数比结点数少1 D．G中没有回路． 5．下列公式 ( C

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

一、填空题

1、对于所有的真值指派，命题公式_______________，这种命题叫做重言式。

对于所有的真值指派，命题公式_______________，这种命题叫做矛盾式。 2、具有_______________________的______________________是命题。

3、一个命题标识符如表示确定的命题，就称为_____________，如果命题标识符只表示任意命题的位置标志，就称为______________。 4、设有命题“如果天不下雨，我就去游泳”。

则其逆换式为__________________________；

反换式为______________________________； 逆反式为______________________________。 5、已知原命题为：“如果天不下雨，我就去。”则该命题的

反换式是___________________________________________，

逆换式是___________________________________________， 逆反式是___________________________________________。 其中意义相同的

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 / 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、 写出谓词的含义、一个谓词公式的解释应包含什么

第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：你失败。命题“除非你努力，否则你将失败”的翻译为__________