离散数学（本）一、单项选择题1．设P ：a 是偶数，Q ：b 是偶数。

R ：a + b 是偶数，则命题“若a 是偶数，b 是偶数，则a + b 也是偶数”符号化为（D ． P Q →R ）。

2．表达式∀x （P （x ，y ）∨Q （z ））∧∃y （Q （x ，y ）→∀zQ （z ））中∀x 的辖域是（P （x ，y ） Q （z ））。

3．设)(}),({},{,4321∅=∅=∅=∅=P S P S S S 则命题为假的是（42S S ∈）。

4．设G 是有n 个结点的无向完全图，则G 的边数（ 1/2 n （n-1））。

5．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r=（ e-v+2）。

6．若集合A ={1，{2}，{1，2}}，则下列表述正确的是( {1}⊂A )．7．已知一棵无向树T 中有8个顶点，4度、3度、2度的分支点各一个，T 的树叶数为( 5 )．8．设无向图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0101110011000011100111110则G 的边数为( 7 )． 9．设集合A ={a }，则A 的幂集为({∅，{a }} )．10．下列公式中 (⌝A ∧⌝B ↔ ⌝(A ∨B ) )为永真式．11．若G 是一个汉密尔顿图，则G 一定是( 连通图 )．12．集合A ={1, 2, 3, 4}上的关系R ={<x ，y >|x =y 且x , y ∈A }，则R 的性质为（传递的 ）．13．设集合A ={1，2，3，4，5}，偏序关系≤是A 上的整除关系，则偏序集<A ，≤>上的元素5是集合A 的（极大元 ）．14．图G 如图一所示，以下说法正确的是 ( {(a, d ) ,(b, d )}是边割集 ) ．图一 15．设A （x ）：x 是人，B （x ）：x 是工人，则命题“有人是工人”可符号化为（(∃x )(A (x )∧B (x )) ）．16．若集合A ={1，2}，B ={1，2，{1，2}}，则下列表述正确的是(A ⊂B ，且A ∈B )． 17．设有向图（a ）、（b ）、（c ）与（d ）如图一所示，则下列结论成立的是 ( （d ）是强连通的 )．18．设图G 的邻接矩阵为⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡010*******000011100100110则G 的边数为( 5 )． 19．无向简单图G 是棵树，当且仅当(G 连通且边数比结点数少1 )．20．下列公式 ((P →(⌝Q →P ))↔(⌝P →(P →Q )) )为重言式．21．若集合A ＝{ a ，{a }，{1，2}}，则下列表述正确的是({a }⊆A )．22．设图G ＝<V , E >，v ∈V ，则下列结论成立的是 (E v Vv 2)deg(=∑∈ ) ．23．命题公式（P ∨Q ）→R 的析取范式是 (（⌝P ∧⌝Q ）∨R )24．下列等价公式成立的为(P →(⌝Q →P ) ⇔⌝P →(P →Q ) )．25．设A ={a , b }，B ={1, 2}，R 1，R 2，R 3是A 到B 的二元关系，且R 1={<a ，2>, <b ，2>}，R 2={<a ，1>, <a ，2>, <b ，1>}，R 3={<a ，1>, <b ，2>}，则（ R 2 ）不是从A 到B 的函数．26．设A ={1, 2, 3, 4, 5, 6, 7, 8}，R 是A 上的整除关系，B ={2, 4, 6}，则集合B 的最大元、最小元、上界、下界依次为 (无、2、无、2)．27．若集合A 的元素个数为10，则其幂集的元素个数为（1024）．28．如图一所示，以下说法正确的是 (e 是割点)．图一29．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ n 为奇数）时，K n 中存在欧拉回路．30．已知图G 的邻接矩阵为，则G 有（ 5点，7边 ）．二、填空题（每小题3分，共15分） 1．设A ，B 为任意命题公式，C 为重言式，若A∧C ⇔B ∧C ，那么A ↔B 是 重言 式（重言式、矛盾式或可满足式）。

2．命题公式（P →Q ）∨P 的主合取范式为 )()(Q P Q P ∨⌝∧∨ 。

3．设集合A={∅，{a}}，则P （A ）= }}}{,{}},{{},{,{a a ∅∅∅ 。

4．设图G =〈V ，E 〉， G ′=〈V ′，E ′〉，若 V ′=V,E ′ E ,则G ′是G 的生成子图。

5．在平面G =〈V ，E 〉中，则∑=r i i r 1)deg(= 2|E| ，其中i r （i=1，2，…，r ）是G 的面。

6．命题公式P P ⌝∧的真值是 假（或F ，或0） ．7．若无向树T 有5个结点，则T 的边数为 4 ．8．设正则m 叉树的树叶数为t ，分支数为i ，则(m -1)i = t-1 ．9．设集合A ={1，2}上的关系R ＝{<1, 1>,<1, 2>}，则在R 中仅需加一个元素 <2, 1> ，就可使新得到的关系为对称的．10．(∀x )(A (x )→B (x ，z )∨C (y ))中的自由变元有 z ，y ．11．若集合A={1，3，5，7}，B ={2，4，6，8}，则A ∩B = 空集（或∅） ．12．设集合A ={1，2，3}上的函数分别为：f ={<1,2>,<2,1>,<3,3>,}，g ={<1,3>,<2,2>,<3,2>,}，则复合函数g ︒f = {<1, 2>, <2, 3>, <3, 2>,} ．13．设G 是一个图，结点集合为V ，边集合为E ，则G 的结点度数之和为 2|E |（或“边数的两倍”） ．14．无向连通图G 的结点数为v ，边数为e ，则G 当v 与e 满足 e=v -1 关系时是树．15．设个体域D ＝{1, 2, 3}， P (x )为“x 小于2”，则谓词公式(∀x )P (x ) 的真值为 假（或F ，或0） ．16．命题公式)(P Q P ∨→的真值是 T （或1） ．17．若图G=<V , E>中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足的关系式为 W ≤|S| ．18．给定一个序列集合{000，001，01，10，0}，若去掉其中的元素 0 ，则该序列集合构成前缀码．19．已知一棵无向树T 中有8个结点，4度，3度，2度的分支点各一个，T 的树叶数为 5 ．20．(∀x )(P (x )→Q (x )∨R (x ，y ))中的自由变元为 R (x ，y )中的y ．21．设集合A ={0, 1, 2, 3}，B ={2, 3, 4, 5}，R 是A 到B 的二元关系，},,{B A y x B y A x y x R⋂∈∈∈><=且且则R 的有序对集合为{<2, 2>，<2, 3>，<3, 2>}，<3, 3> ．22．设G 是连通平面图，v , e , r 分别表示G 的结点数，边数和面数，则v ，e 和r 满足的关系式 v -e +r =2 ．23．设G ＝<V , E >是有6个结点，8条边的连通图，则从G 中删去 3 条边，可以确定图G 的一棵生成树．24．无向图G 存在欧拉回路，当且仅当G 连通且 所有结点的度数全为偶数 ．25．设个体域D ＝{1,2}，则谓词公式)(x xA ∃消去量词后的等值式为 A (1)∨A (2) ．26．设集合A ＝{a ，b }，那么集合A 的幂集是 {∅,{a ,b },{a },{b }} ．27．如果R 1和R 2是A 上的自反关系，则R 1∪R 2，R 1∩R 2，R 1-R 2中自反关系有 2 个．28．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去 4 条边后使之变成树．29．设连通平面图G 的结点数为5，边数为6，则面数为 3 ．30．设个体域D ＝{a , b }，则谓词公式(∀x )A (x )∧（∃x ）B （x ）消去量词后的等值式为 (A (a )∧A (b ))∧(B （a ）∨B （b ）) ．31. 设集合A={0，1 ，2} ，B={l ，2 ，3 ， 剖，R 是A 到B 的二元关系，R= {<x ,y> |x ∈A 且y ∈B 且x ， y ∈A ∩B} 则R 的有序对集合为___{<1,1>,<1,2>,<2,1>,<2,2>}___32. 设G 是连通平面图，v ， e ， r 分别表示G 的结点数， 边数和面数， 则 v ， e 和r 满足的关系式__v-e+r=2_____33.G=<V,E>是有20个结点，25 条边的连通图,则从G 中删去__6__条边，可以确定图G 的一棵生成树.34. 无向图G 存在欧拉回路， 当且仅当G 所有结点的度数全为偶数且_ 连通____35. 设个体域D={ 1, 2 } ， 则谓词公式∀ xA(x)消去量词后的等值式为__A(1)∧A(2)___三、化简解答题11．设集合A={1，2，3，4}，A 上的二元关系R ，R={〈1，1〉，〈1，4〉，〈2，2〉，〈2，3〉，〈3，2〉，〈3，3〉，〈4，1〉，〈4，4〉}，说明R 是A 上的等价关系。

解 从R 的表达式知，,),(,R x x A x ∈∈∀即R 具有自反性；三、逻辑公式翻译1．将语句“今天上课．”翻译成命题公式．设P ：今天上课， 则命题公式为：P ．2．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．设 P ：他去操场锻炼，Q ：他有时间， 则命题公式为：P Q ．3．将语句“他是学生．”翻译成命题公式． 设P ：他是学生， 则命题公式为： P ．4．将语句“如果明天不下雨，我们就去郊游．”翻译成命题公式．设P ：明天下雨，Q ：我们就去郊游， 则命题公式为：⌝ P → Q ．5．将语句“他不去学校．”翻译成命题公式．设P ：他去学校， ⌝ P ．6．将语句“他去旅游，仅当他有时间．”翻译成命题公式．设 P ：他去旅游，Q ：他有时间， P →Q ．7．将语句“所有的人都学习努力．”翻译成命题公式．设P (x )：x 是人，Q (x )：x 学习努力， （∀x ）(P (x )→Q (x ))．8．将语句“如果你去了，那么他就不去．”翻译成命题公式．设P ：你去，Q ：他去， P →⌝Q ．9．将语句“小王去旅游，小李也去旅游．”翻译成命题公式．设P ：小王去旅游，Q ：小李去旅游， P ∧Q ．10．将语句“所有人都去工作．”翻译成谓词公式．设P (x )：x 是人，Q (x )：x 去工作， (∀x )(P (x )→Q (x ))．11．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式．设P ：所有人今天都去参加活动，Q ：明天的会议取消， P → Q ．12．将语句“今天没有人来．” 翻译成命题公式．设 P ：今天有人来， ⌝ P ．13．将语句“有人去上课．” 翻译成谓词公式．设P (x )：x 是人，Q (x )：x 去上课， (∃x )(P (x) ∧Q (x ))．1 1. 将语句"如果小李学习努力，那么他就会取得好成绩. "翻译成命题公式.设P ：小李学习努力，Q:小李会取得好成绩，P →Q12. 将语句"小张学习努力,小王取得好成绩. "翻译成命题公式.设P ：小张学习努力，Q:小王取得好成绩，P ∧Q四、判断说明题1．设集合A ={1，2}，B ={3，4}，从A 到B 的关系为f ={<1, 3>}，则f 是A 到B 的函数．错误． 因为A 中元素2没有B 中元素与之对应，故f 不是A 到B 的函数．2．设G 是一个有4个结点10条边的连通图，则G 为平面图．错误． 不满足“设G 是一个有v 个结点e 条边的连通简单平面图，若v ≥3，则e ≤3v-6．”3．设N、R分别为自然数集与实数集，f：N→R，f (x)=x+6，则f是单射．正确．设x1，x2为自然数且x1≠x2，则有f(x1)= x1+6≠x2+6= f(x2)，故f为单射．4．下面的推理是否正确，试予以说明．(1) （∀x）F（x）→G（x）前提引入(2) F（y）→G（y）US（1）．错误．（2）应为F（y）→G（x），换名时，约束变元与自由变元不能混淆．5．如图二所示的图G存在一条欧拉回路．图二错误．因为图G为中包含度数为奇数的结点．6．设G是一个有6个结点14条边的连通图，则G为平面图．错误．不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”7．如果R1和R2是A上的自反关系，则R1∪R2是自反的．正确．R1和R2是自反的，∀x∈A，<x, x> ∈R1，<x, x> ∈R2，则<x, x> ∈R1⋃R2，所以R1∪R2是自反的．8．如图二所示的图G存在一条欧拉回路．正确．因为图G为连通的，且其中每个顶点的度数为偶数．9．┐P∧（P→┐Q）∨P为永真式．正确．┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，如果P的值为真，则┐P∧（P→┐Q）∨P为真，如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真，也即┐P∧（P→┐Q）∨P为真，所以┐P∧（P→┐Q）∨P是永真式．另种说明：┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，只要其中一项为真，则整个公式为真．可以看到，不论P的值为真或为假，┐P∧（P→┐Q）与P总有一个为真，所以┐P∧（P→┐Q）∨P是永真式．或用等价演算┐P∧（P→┐Q）∨P⇔T10．若偏序集<A，R>的哈斯图如图一所示，则集合A的最大元为a，最小元不存在．图一正确．对于集合A的任意元素x，均有<x, a>∈R（或xRa），所以a是集合A中的最大元．按照最小元的定义，在集合A中不存在最小元．v1v v3v5v4dbaefghn图二11. 如果R 1和R 2是A 上的自反关系， 则R 1∩R 2是自反的。