离散数学2

离散数学（2）复习题一、判断题1、两个集合相等的充分必要条件是这两个集合互为补集。

（ × ）2、两个集合相等的充分必要条件是这两个集合互为子集。

（ √ ）3、两个集合相等的充分必要条件是这两个集合互为幂集。

（ × ）4、对于任意一个集合A ，A f Í。

（ √ ）5、对于任意一个集合A ，A f Î。

（ × ）6、如果有限集合有n 个元素，则其幂集有2n 个元素。

（ √ ）7、设R 、S 是集合A 上的关系，且R S Ê，则()()s R s S Ê。

（ √ ）8、设R 、S 是集合A 上的关系，且R S Ê，则()()t R t S Ê。

（ √ ）9、设R 、S 是集合A 上的关系，且R S Ê，则()()r R r S Ê。

（ √ ）10、一个关系可以：既不满足自反性，也不满足非自反性。

（ √ ）11、一个关系可以：既不满足对称性，也不满足反对称性。

（ √ ）12、一个关系可以：既满足对称性，同时也满足反对称性。

（ √ ）13、若图G 是不连通的，则图G 的补图G -是连通的。

（ √ ）二、单项选择题1、由集合运算定义，下列各式正确的有（ A ）。

A.X ⊆X ⋃YB.X ⊇X ⋃YC.X ⊆X ⋂YD.Y ⊆X ⋂Y2、设A B -=∅，则有（ C ）。

A.B =∅B.B ≠∅C.A B ⊆D.A B ⊇3、对任意的集合A 、全集U ，下列命题为假的是（ D ）。

A.A ⋃∅ ＝A ，B.A ⋃U = UC.A ⋂∅ = ∅，D.A ⋂U = U4、集合A={1，2，…，10}上的关系R={<x,y>|x+y=10,x ∈A,y ∈A},则R 的性质为（ B ）。

A.自反的B.对称的C.传递的，对称的D.反自反的，传递的5、设R 和S 是集合A 上的任意关系，则下列命题为真的是（ A ）。

A.若R和S是自反的，则R o S也是自反的B.若R和S是反自反的，则R o S也是反自反的C.若R和S是对称的，则R o S也是对称的D.若R和S是传递的，则R o S也是传递的6、设R和S是非空集合A上的等价关系，则下面是A上的等价关系的是（ D）。

A.()⨯- B.S RA A R⋂⋃ C.S R- D.S R7、设函数f：N→N（N 为自然数集），f(n)=n+1，下面四个命题为真的是（ A）。

A.f是单射B.f是满射C.f是双射的D.f非单射非满射8、图G和'G的结点和边分别存在一一对应关系是G和'G同构的（ B ）。

A.充分条件B.必要条件C.充要条件D.既不充分也不必要条件9、平面图(如下)的三个面的次数分别是（ A ）。

A．11，3，4 B．11，3，5 C．12，3，6 D．10，4，310、G是连通平面图，有5个顶点、6个面，则G的边数为（ D ）。

A.6B.5C.11D.911、下面哪一组命题公式不是等值的？（ B ）。

A.(),⌝↔∧⌝∨⌝∧A B A B A B⌝→∧⌝ B.(),()()A B A BC.(),()A B C A B C→∨∧⌝→→∨⌝∧∨ D.(),()A B C A B C12、设R是集合A上的偏序关系，则R不一定是（ B ）。

A.自反的B.对称的C.反对称的D.传递的13、设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（ B ）。

A.3B.4C.5D.614、下列各图中既是欧拉图，又是汉密尔顿图的是（ C ）。

A． B． C． D．15、下面哪一种图不一定是树？（ C ）。

A.无回路的连通图B.有n个结点n-1条边的连通图C.每对结点间都有通路的图D.连通但删去一条边则不连通的图16、设A＝{a，b，c}，B＝{a，b}，则下列命题不正确的是（ A ）。

A．A∪B＝{a，b} B．BAC．A－B＝{c} D．B－A＝Φ17、下列语句中不是．．命题的只有（ A ）。

A.这个语句是假的B.1+1=1C.飞碟来自地球外的星球D.凡石头都可练成金18、设P: 我有时间，Q: 我去书店买书，将命题“只要我有时间，我就去书店买书”符号化为（ D ）。

A．P∨Q B．⌝P→⌝QC．P∧Q D．P→Q19、结点数为奇数且所有结点的度数也为奇数的连通图必定是（ D ）。

A.欧拉图B.汉密尔顿图C.非平面图D.不存在的20、无向图G是欧拉图当且仅当G是连通的且（ C ）。

A.G中各顶点的度数均相等B.G中各顶点的度数之和为偶数C.G中各顶点的度数均为偶数D.G中各顶点的度数均为奇数21、设A＝{Φ}，B＝P（P（A）），以下不正确的式子是（ D ）。

A.{{Φ}，Φ}∈BB.{{Φ}}∈BC.{{Φ}}包含于BD.{{{{Φ}}，Φ}}包含于B22、下列命题正确的是（ D ）。

A.{}↑不是可交换的，{}↓也不是可交换的B.{}↑不是可交换的，但{}↓是可交换的C.{}↑是可交换的，但{}↓不是可交换的D.{}↑是可交换的，{}↓也是可交换的23、谓词公式(()())()x P x yR y Q x ∀∨∃→中中量词x ∀的作用域是（ C ）。

A.(()())x P x yR y ∀∨∃B.()P xC.(()())P x yR y ∨∃D.()P x ，()Q x24、如果解释I 使公式A 为真，且使公式B A →也为真，则解释I 使公式B 为（ A ）。

A.真B.假C.可满足D.与解释I 无关25、在谓词演算中：如果对个体域中的某个个体变量a ，()P a 成立，则必存在x ，使得()P x 成立，其理论依据是（ D ）。

A.全称量词消去规则（US ）B.全称量词引入规则（UG ）C.存在量词消去规则（ES ）D.存在量词引入规则（EG ）26、下列是命题的是（ A ）。

A.小李不是大学生。

B.这朵花多么好看啊！C.今天下午开会么？D.x+2=427、下列语句中哪个是真命题（ D ）。

A.我正在说谎B.严禁吸烟C.如果1+2=3，那么雪是黑的D.如果1+2=5，那么雪是黑的28、一个公式在等价意义下，下面哪个写法是唯一的（ C ）。

A.析取范式B.合取范式C.主析取范式D.以上答案都不对29、设谓词():P x x 是人，():Q x x 犯错误，命题“没有不犯错误的人”符号化为（ D ）。

A.(()())x P x Q x ∀∧B.(()())x P x Q x ⌝∃→⌝C.(()())x P x Q x ⌝∃∧D.(()())x P x Q x ⌝∃∧⌝30、下列命题中是原子命题的是（ B ）。

A.张明和张洪都是大学生B.张丽和张华是亲姐妹C.张珏或张强是河北省人D.王辉不是工人31、设A 和B 都是命题，则A B →的真值为假当且仅当（ D ）。

A ．A 为假，B 为真 B ．A 为假，B 也假C ．A 为真，B 也真D ．A 为真，B 为假32、命题公式()P Q R ⌝∧→的成真赋值为（ B ）。

A ．000，001，110B ．001，011，101，110，111C ．全体赋值D ．无33、下列命题联结词集合中哪个不是完备集？（ A ）A ．},{↔⌝B ．},{→⌝C ．{}↑D ．{}↓34、下列各式中，哪些是析取范式？（ A ）A ．P Q ⌝∧B ．()P Q R ⌝∧∨C ．(())P Q R ∧⌝⌝∨D ．()P Q R ⌝∧∨⌝35、与命题公式()P Q P →→等值的公式是（ D ）。

A. ()P Q R ∨→B. ()P Q R →∨C ．()P Q R →→D ．()P Q R ∧→三、填空题1、设X ，U ，V ，Y 都是实数集，f 1：X →U ，且f l (x)→e x ； f 2：U →V ，且f 2(u)＝u (1+u)；f 3：V →Y ，且f 3(v)=cosv 。

那么f 3οf 2οf 1的定义域是 X ，而复合函数(f 3οf 2οf 1)(x)= _ cosv （e x （1 + e x ）） 。

2、对代数系统<S ，*>，其中*是S 上的二元运算，若a ，b ∈S ，且对任意的x ∈S ，都有a*x=x*a=x ，b*x=x*b=b ，则称a 为运算“*”的 幺元 ，称b 为运算“*”的 零元 。

3、一个 连通 且 无回路 的无向图称为树。

4、设R 为非空集合A 上的二元关系，如果R 具有自反性、 反对称性 、 传递性 则称R 为A 上的一个偏序关系。

5、设x＝{1，3，5，9，15，45}，R是x上的整除关系，则R是x上的偏序，其最大元是 45 ，极小元是 1 。

6、设<S，*>是群，则<S，*>满足结合律和_消去律_；若｜S｜>l，S中不可能有_零元_。

7、写出如右有向图的一条初级回路：__v2v3v2_，其长度是_ 2 _。

8、在简单无向图G=<V，E>中，如果V中的每个结点都与其余的所有结点邻接，则该图称为_完全图_，如果V有n个结点，那么它还是_n-1_度正则图。

9、()P Q T仝的对偶式()P Q T谫。

10、()()P Q Q S刳仝的对偶式()()P Q Q S刭谫。

11、“并非每个实数都是有理数。

”谓词逻辑表示为()(()())x R x Q x??。

12、没有不犯错误的人。

”表示为((()()))x M x F x?儇。

四、计算题1、求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。

解：最优二叉树权＝1482、在极坐标系中，单位圆外的点集（不包括单位圆周）。

解：2{,|1}S r q r=<>>。

3、设X={{{1，2}，{1}}，{1，0}}，求XÈ，XÇ。

解：XÈ={{1，2}，{1}，{1，0}} X??4、所有一元一次方程的解组成的集合。

解：S ={x | ax + b = 0,a ≠ 0}5、一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。

但对任意两个人，他们各自认识的人的数目之和不小于20。

问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么? 解：可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。

根据：构造无向简单图G=<V,E>,其中V={v1,v2,…，V20}是以20个人为顶点的集合，E中的边是若任两个人vi 和vj相互认识则在vi与vj之间连一条边。

∀Vi ∈V,d(vi)是与vi相互认识的人的数目，由题意知∀vi,vj∈V有d(vi )+d(vj)≥20,于是G中存在汉密尔顿回路。