离散数学练习题答案修改 Revised by BLUE on the afternoon of December 12,2020.2016注意事项：1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。

2、第二遍复习按照考试大纲的总结把重点内容再做复习。

另外，把大纲中指定的例题及书后习题认真做一做。

检验一下主要内容的掌握情况。

3、第三遍复习把随后发去的练习题认真做一做，检验一下复习情况，要认真理解,注意做题思路与方法。

离散数学综合练习题一、选择题1．令p: 今天下雪了，q:路滑，r:他迟到了。

则命题“下雪路滑，他迟到了”可符号化为（ A ）。

A. p q r∨→∧→ B. p q rC. p q r∨↔∧∧ D. p q r2.设()f x:x的绝对值，(,)L x y：x大于等于y；命题P x:x是整数，()“所有整数的绝对值大于等于0”可符号化为（ B ）。

A. (()((),0))∀→x P x L f xx P x L f x∀∧ B. (()((),0))C. ()((),0)xP x L f x ∀∧D. ()((),0)xP x L f x ∀→3.设()F x :x 是人，()G x :x 犯错误，命题“没有不犯错误的人”符号化为（D ）。

A ．(()())x F x G x ∀∧B ． (()())x F x G x ⌝∃→⌝C ．(()())x F x G x ⌝∃∧D ． (()())x F x G x ⌝∃∧⌝*4.下列命题公式不是永真式的是（ A ）。

A. ()p q p →→B. ()p q p →→C. ()p q p ⌝∨→D. ()p q p →∨5．设p ：我们划船，q ：我们跳舞，命题“我们不能既划船又跳舞”符号化正确的是（ B ）。

A. p q ∧B. ()p q ⌝∧C. p q ⌝∧⌝D. p q ⌝∧6．设()R x :x 为有理数；()Q x :x 为实数。

命题“任何有理数都是实数”的符号化为（ A ）A ．()(()())∀→x R x Q xB ．()(()())∀∧x R x Q xC ．()(()())x R x Q x ∃∧D ．(()())x R x Q x ∃→7. 设个体域{,}D a b =，与公式()xA x ∃等价的命题公式是( C )A ．()()A a A b ∧B ．()()A a A b →C ．()()A a A b ∨D ．()()A b A a →8．无向图G有20条边，4个6度顶点，2个5度顶点，其余均为2度顶点，则G一共有（ C ）个顶点。

*9.设集合A={c, {c}}，下列命题是假命题的为（ C ）。

A.{}()⊆ D.{{}}()⊆c P Ac P A∈ B.{{}}()∈ C.{}()c P Ac P A10.设X={,{},{,}}∅∅，则下列陈述正确的是（ C ）。

a aA.a X∈ B.{,}∅⊆a XC.{{,}}∅∈a X∅⊆ D.{}X11.有向图D是连通图，当且仅当（ D ）。

A. 图D中至少有一条通路B. 图D中有通过每个顶点至少一次的通路C. 图D的连通分支数为一D. 图D中有通过每个顶点至少一次的回路12.设A={a,b,c}，则下列是集合A的划分的是( B )A.{{,},{}}a b cb c c B. {{},{,}}C.{{,},{,}}a b ca b a c D. {{,},}13.下列谓词公式中是前束范式的是（ D ）。

A．()()()∀∨∀xF x yG y∀∧⌝∃B．()()xF x x G xC ．(()(,))x P x yQ x y ∀→∃D ．(()(,))x y P x Q x y ∀∃→14. 设简单图G 所有结点的度数之和为50，则G 的边数为（ B ）。

A. 50 B. 25 C. 10D. 515.设集合{1,2,3,4}A =,A 上的等价关系{1,1,3,2,2,3,R =<><><> 4,4}A I <>，则对应于R 的划分是（ A ）。

A. {{1},{2,3},{4}} B. {{1,3},{2,4}} C. {{1,3},{2},{4}}D. {{1},{2},{3},{4}}16. 设{1,2,3},{,,,},{1,,2,,3,}X Y a b c d f a b c ===<><><>，则f 是( C )。

A ．从X 到Y 的双射B ．从X 到Y 的满射，但不是单射C ．从X 到Y 的单射，但不是满射D ．从X 到Y 的二元关系，但不是从X 到Y 的映射 17.下列图是欧拉图的是（ D ）。

18.给定一个有n个结点的无向树，下列陈述不正确的是（ A ）。

A．所有结点的度数≥2B．无回路但若增加一条新边就会变成回路C．连通且1=-，其中e是边数，v是结点数e vD．无回路的连通图19．若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是（ C ）。

A. (1,2,2,3,4,5)B. (1,2,3,4,5,5)C. (1,1,1,2,3)D. (2,3,3,4,5,6)20. 设{,{},{,{}}}P A的元素总个数为（ C ）。

A a a a a=则其幂集()A. 3B. 4C. 8D. 1621. 设简单图G所有结点的度数之和为48，则G的边数为( B )A. 48B. 24C. 16D. 1222．下面既是哈密顿图又是欧拉图的图形是（ B ）。

23.下列必为欧拉图的是（ D ）A.有回路的连通图B.不可以一笔画的图C.有1个奇数度结点的连通图D.无奇数度结点的连通图24.二部图K是（ B ）。

3,3A.欧拉图B. 哈密顿图C.平面图D. 完全图25．下列所示的哈斯图所对应的偏序集中能构成格的是（ C ）。

A. B.C. D.26.设集合{,,}=<><><>，则R是R a a a c c aA a b c=，A上的关系{,,,,,}（ B ）A ．自反的B ．对称的C ．传递的D ．反对称的27．设12,R R 是集合{,,,}A a b c d =上的两个关系，其中1{,,,,R a a b b =<><>,,,}b c d d <><>，2{,,,,,,,,,}R a a b b c b b c d d =<><><><><>，则2R 是1R 的（ B ）闭包。

A ．自反 B ．对称C ．传递D ．自反、对称且传递闭包28. 下列公式是前束范式的是（ A ）。

A ．()()((,)())x y F z x G y ∀∀⌝∨B ．(()()()())()x F x y G y H z ⌝∃∨∀∧C ．()(,)()()x F x y y G y ∃→∀D ．()((,)()(,))x F x y y G x y ∀→∀ 29. 设R 为实数集，函数:f R R →，2()25f x x x =-++，则f 是（ D ）。

A ．单射而非满射B ．满射而非单射C ．双射D ．既不是单射，也不是满射30．下列各图中既是欧拉图，又是汉密尔顿图的是（ C ）。

A ．B ．C ．D ．12.设12{|()0},{|()0}M x f x N x f x ====，则方程12()()0f x f x ⋅=的解为（B ）。

A ．M ∩NB ．M ∪NC ．MN C ．M-N13.设,G A =<*>是群，则下列陈述不正确的是（ C ）。

A. 11()a a --=B. n m n m a a a +=C. 111()ab a b ---=D. 11()n n a ba a b a --=二、填空题1．命题公式()p p q →∧的成真指派为 00 01 11, 成假指派为_10__。

2．公式()()(()(,))()(,)x y P y Q x z y R x y ∀∀→∧∃约束变元为 x ,y ，自由变元为 x ,z 。

3．设{,,{,}}A a b a b =，{,}B a b =，则B A - , A B ⊕= {{a,b}} 。

4．设{,,}A a b c =，A 上的关系{,,,}R a b b a =<><>，则对称闭包()s R ={,,,}a b b a <><>，传递闭包()t R ={,,,,,,,}a b b a a a b b <><><><>。

5.一棵无向树的顶点数n 与边数m 的关系是 n-1 。

6阶无向连通图至多有 6 棵不同构的生成树。

6．设()1f x x =-，2()g x x =，则复合函数()()f g x =2(1)x -,()()g f x=21x -。

7. ,n Z <⊕>是一个群，其中{0,1,2,,1}n Z n =-，()mod x y x y n ⊕=+，则当n =6时，在6,Z <⊕>中，2的阶为__3____, 3的阶为_2 。

8．设<A ，≤>是格，其中A={1, 3,4，6，8，12，24}，≤为整除关系，则1的补元是___24 __，3的补元是__8__。

9．设A=｛<1，3>，<3，5>，<4，4>｝，B=｛<1,3>,<4,5>,<5,5>｝,那么dom()A B ={1,3,4,5} ran ()A B = {3} _。

10. 设A ={l,2,3,4},A 上的二元关系R ={<1,2>,<2,3>,<3,2>}，S ={<l,3>,<2,3>，<4，3>}，则R S = {<1,3>,<3,3>} ,1()R S -= {<3,1>,<3,3>} 。

11．设复合函数g f 是从A 到C 的函数，如果g f 是满射，那么__g ___必是满射，如果g f 是单射，那么__f _必是单射。

12．给出A ={l ，2}上的一个等价关系{1,1,2,2}<><>，并给出其对应的划分{{1},{2}}。

13．设{,,,}A a b c d =，A 上的二元关系{,,,,,}R a b a d b b =<><><>，则R 的自反闭包()r R =A R I ，传递闭包()t R = R14．设个体域是实数集，命题)3(x x x <-∀的真值为 1 ；命题2(10)x x ∃+=的真值为 0 。