离散数学综合练习题一、判断下列命题是否正确．如果正确，在题后括号内填“\/”；否则，填“⨯”（1）空集是任何集合的真子集． （ ）（2）{}φ是空集． （ ） （3）{}{}a a a },{∈ （ ） （4）如果B A a ⋃∉，则A a ∉或B a ∉． （ ）（5）设集合},,{321a a a A =，},,{321b b b B =，则},,,,,{332211><><><=⨯b a b a b a B A （ ）（6）设集合}1,0{=A ，则}1},0{,0},0{,1,,0,{><><><><=φφρ是A2到A 的关系． （ ）（7）关系的复合运算满足交换律． （ ）（8）设21,ρρ为集合 A 上的等价关系, 则21ρρ⋂也是集合 A 上的等价关系( )（9）设ρ是集合A 上的等价关系, 则当ρ>∈<b a ,时， ρρ][][b a = ( )（10）设21,ρρ为集合 A 上的等价关系, 则2121~~ρρρροο= ( ) （11）集合A 上的任一运算对A 是封闭的． （ ）（12）设A 是集合，A A A →⨯:ο，b b a =ο，则ο是可结合的． （ ）（13）设>⋅<,G 是群．如果对于任意G b a ∈,，有222)(b a b a ⋅=⋅则>⋅<,G 是阿贝尔群． （ ）（14）设a 是群>⋅<,G 的元素，记}|{y a a y G y y H ⋅=⋅∈=且则>⋅<,H 是>⋅<,G 的子群． （ ）（15）<{0，1，2，3，4}，max ，min>是格． （ ）（16）设a ，b 是格>∧∨<,,L 的任意两个元素，则a b a b b a =∧↔=∨． （ ）（17）设>∧∨<,,,B 是布尔代数，则>∧∨<,,B 是格． （ ）（18）设集合},{b a A =，则>⋂⋃<,},},{},{,{A b a φ是格． （ ）（19）设>∧∨<,,,B 是布尔代数，则对任意B b a ∈,，有b a b a ∨=∧． （ ）（20）设>∧∨<,,,B 是布尔代数，则对任意B a ∈，都有B b ∈，使得0,1=∧=∨b a b a ． （ ）（21）n 阶完全图的任意两个不同结点的距离都为1. （ ）（22）在有向图中，结点i v 到结点j v 的有向短程即为j v 到i v的有向短程． （ ）（23）强连通有向图一定是单向连通的． （ ）（24）不论无向图或有向图，初级回路一定是简单回路． （ ）（25）设图G 是连通的，则任意指定G 的各边方向后所得的有向图是弱连通的． （ ）（26）设A 是某个无向图的邻接矩阵，则T A A =(T A 是A 的转置矩阵)． （ ）（27）设有向图D 的可达矩阵为⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=1000110011101111P 则G 是单向连通的． （ ）（28）有生成树的无向图是连通的． （ ）（29）由r 棵树组成的森林的结点数n 与边数m 有下列关系：m=n-r. （ ）（30）如果有向图D 仅有一个结点的入度为0，其余结点的入度都为1，则D 是有向树． （ ）（31）“如果8＋7＞2，则三角形有四条边”是命题． （ ）（32）设Q P ,都是命题公式，则Q P ⇔也是命题公式． （ ）（33）命题公式Q P ,的真值分别为0，1，则Q P →的真值为0（以上是在对Q P ,所包含的命题变元的某个赋值下）． （ ）（34）逻辑结论是正确结论． （ ）（35）设B A ,都是谓词公式，则B A ⇔也是谓词公式． （ ）（36）设B A ,都是谓词公式，B A ⇒，则B A →是永真式． （ ）（37）设C B A ,,都是命题公式，则)()(C A C B A →→⌝∨∨也是命题公式． （ ）（38）命题公式Q P ,的真值分别为0，1，则Q P ↔的真值为0（以上是在对Q P ,所包含的命题变元的某个赋值下）． （ ）（39）设c 是个体域中某个元素，则)()()()(c Q c P x xQ x xP ∧⇒∃∧∃其中Q P ,都是谓词． （ ）（40）),(),(y x xA y y x yA x ∀∃⇔∃∀ （ ）二、填空题（1）设A 有n 个元素，则集合A 的幂集)(A P 中有 个元素。

（2）设}}{,{φφ=A ，则A2= .（3）设集合B A ,中元素的个数分别为5#=A ，7#=B ，且9)(#=⋃B A ，则集合B A ⋂中元素的个数=⋂)(#B A .（4）设集合}4,1001|{Z x x x x A ∈≤≤=的倍数，是，}5,1001|{Z x x x x B ∈≤≤=的倍数，是，则B A Y 中元素的个数为 .(5)设21,ρρ为集合 A 上的二元关系, 则=21ρρο .(6)集合A 上的二元关系ρ为传递的充分必要条件是 ．(7)设1ρ：a 称b 为母亲，2ρ：b 称c 为父亲，则21ρρο： ,(8)设N 为自然数的集合，“≤”为自然数的小于等于关系，N 的子集}9,7,5{=A ，则A 的下确界为 ，下确界为 ,(9)设10人集合=E {赵茵，钱小滨，孙丽春，赵萍，钱浩，李靖华，李秀娟，钱钰，李惠芝，李莉}上的同姓关系为ρ，则等价类[赵]= ，[钱]= ，(10)设 },{b a A =, ρ 是 A 2 上的包含于关系，,则有ρ= .(11)设S 为非空有限集，代数系统><Y ),(S P 中，)(S P 对运算Y 的单位元为 ，零元为 .(12)循环群>⊕<33,I 的生成元为 .(13)循环群>⊕<66,I 的所有子群为 .(14)代数系统>+<,Z 中（其中Z 为整数集合，+为普通加法），对任意的I x ∈，其=-1x .(15)在整数集合Z 上定义ο运算为b a b a ++=2ο，则><ο,Z 的单位元为 .(16)设}10,,4,3,2,1{Λ=T ,在代数系统><max ,T 中，><max ,T 的单位元为，可逆元为 .(17)设⋅,G 是群，则对于任意的G b a ∈,，方程 和 有唯一解。

(18)设⋅,G 是群，对任意G c b a ∈,,，如果,c a b a ⋅=⋅，则 .(19)设⋅,G 是群，e 为单位元，若G 元素a 满足a a =2，则=a .(20)在整数集合Z 上定义ο运算为ab b a b a -+=ο，则><ο,Z 的单位元为 .(21)设>=<E V T ,为树，T 中有4度，3度，2度分支点各1个，问T 中有片树叶。

(22)为了从（n ，m ）连通无向图得到一棵生成树，必须删除G 的 条边．(23)设树T 中有7片树叶，3个3度结点，其余都是4度结点，问T 中有 个4度结点。

(24)无环有向图的关联矩阵的所有元素之和为 ．(25)n 阶完全图的任意两个不同结点的距离都为 ．(26)图G 为n 阶无向完全图，则G 共有 条边。

(27)设G 为),(m n 图，则图中结点度数的总和为 。

(28)设图G 有6结点，若各结点的度数分别为：1，4，4，3，5，5，则G 共有条边。

(29)无向图G 是由)2(≥k k 棵树组成的森林，至少要添加 条边才能使G 成为一棵树。

(30)在任何图>=<E V G ,中，奇数结点必为 个。

(31)设:p 天气很冷，:q 老王还是来了，则命题“虽然天气很冷, 但老王还是来了”符号化为 .(32)设:p 天下雨，:q 我骑自行车上班，则命题“如果天不下雨, 我就骑自行车上班”符号化为 .(33)设:p 经一事, :q 长一智，则命题“不经一事, 不长一智”符号化为 .(34)设q p ,的真值为0，r 的真值为1，则命题公式)(r q p ∧∨的真值为 .(35)设q p ,的真值为0，s r ,的真值为1，则命题公式)()(s q r p ∨⌝∧↔的真值为 .(36)由n 个命题变项可以组成 个不等值的命题公式。

(37)设个体域},,,{21n a a a A Λ=，公式)()(x F x ∃在A 上消去量词后应为 .(38)设x x N :)(是自然数，x x F :)(是奇数，x x G :)(是偶数，则命题“任何自然数不是奇数就是偶数” 符号化为 .(39)设x x F :)(是素数，x x G :)(是偶数，2:a ，则命题“2既是偶数又是素数”符号化为 .(40)设x x G :)(是金子，x x F :)(是发光的，则命题“金子是发光的, 但发光的不一定是金子”符号化为 .三、选择题（每题后面有四个选项，四个选项中只有一个是正确的，请将正确的所对应的字母填在括号内）（1）设R 为实数集合，下列集合中哪一个不是空集 （ ） A. {}R x x x ∈=-且,01|2 B ．{}R x x x ∈=+且,09|2 C. {}R x x x x ∈+=且,1| D. {}R x x x ∈-=且,1|2 （2）设B A ,为集合，若φ=B A \，则一定有 （ ）A. φ=B B ．φ≠B C. B A ⊆ D. B A ⊇（3）下列各式中不正确的是 （ ）A. φφ⊆ B ．{}φφ∈ C. φφ⊂ D. {}}{,φφφ∈ （4）设{}}{,a a A =，则下列各式中错误的是 （ ）A. {}A a 2∈ B ．{}A a 2⊆ C. {}A a 2}{∈ D. {}Aa 2}{⊆ （5）设{}2,1=A ，{}c b a B ,,=，{}d c C ,=，则)(C B A I ⨯为 （ ） A. {}><><c c ,2,1, B ．{}><><c c ,2,,1C. {}><><2,,,1c cD. {}><><2,,1,c c（6）设{}b A ,0=，{}3,,1b B =，则B A Y 的恒等关系为 （ ） A. {}><><><><3,3,,,1,1,0,0b b B ．{}><><><3,3,1,1,0,0C. {}><><><3,3,,,0,0b bD. {}><><><><0,3,3,,,1,1,0b b（7）集合}10,,2,1{Λ=A 上的二元关系},10|),{(A y x y x y x ∈=+=且ρ，则ρ的性质为 （ ）A. 自反的； B ．对称的； C. 反对称的； D. 反自反的.（8）设{}c b a A ,,=上的二元关系如下，则具有传递性的为 （ ）A. {}><><><><=a b b a a c c a ,,,,,,,1ρB ． {}><><=a c c a ,,,2ρC. {}><><><><=c b a b c c b a ,,,,,,,3ρD. {}><=a a ,4ρ （9）设ρ为集合A 上的等价关系，对任意A a ∈，其等价类[]ρa 为 （ ）A. 空集； B ．非空集； C. 是否为空集不能确定； D. }|{A x x ∈.（10）映射的复合运算满足 （ ）A. 交换律 B ．结合律 C. 幂等律 D. 分配律（11）在整数集Z 上，下列哪种运算是可结合的 （ ）A. b a b a -=ο B ．},max{b a b a =οC. b a b a 2+=οD. ||b a b a -=ο（12）设集合{}10,,4,3,2,1Λ=A ，下面定义的哪种运算关于集合A 不是封闭的（ ）A. },max{y x y x =οB ． },min{y x y x =οC. },{GCD y x y x =ο，即y x ,的最大公约数D. },{LCM y x y x =ο，即y x ,的最小公倍数（13）下列哪个集关于减法运算是封闭的 （ ）A. N （自然数集）； B ．)}(|2{整数集I x x ∈；C. }|12{I x x ∈+；D. }|{是质数x x .（14）设Q 是有理数集，在Q 定义运算*为ab b a b a -+=*，则*,Q 的单位元为 （ ）A. a ； B ．b ； C. 1； D. 0（15）下列代数系统*,G 中，哪一个不构成群 （ ）A. *=},10,1{G 是模11乘法；B. *=},2,1,0{G 是模3加法；C. *=),(有理数集Q G 普通加法；D. *=,Q G 普通乘法.（16）循环群33,⊕I 的生成元为1和2，它们的周期为 （ ）A. 5 B ．6 C. 3 D. 9（17）循环群55,⊕I 的所有子群为 （ ） A. 55,⊕I B ．5},0{⊕ C. 55,⊕I 和5},0{⊕ D. φ（18）循环群+,Z 的所有生成元为 （ ）A. 1，0 B ．-1，2 C. 1，2 D. 1，-1（19）有限布尔代数的元素个数必定等于 （ ）A. n 2； B ．2n ； C. n 2； D. n 4.（20）在下面偏序集的哈斯图中，哪一个是格 （ ）A B C D（21）仅由孤立点组成的图称为 （）A. 零图； B ．平凡图； C. 完全图； D. 多重图.（22）仅由一个孤立点组成的图称为 （ ）A. 零图； B ．平凡图； C.多重图； D. 子图.（23）在任何图G 中必有偶数个 （ ）A. 度数为偶数的结点； B ．度数为奇数的结点；C. 入度为奇数的结点；D. 出度为奇数的结点.（24）设G 为有n 个结点的无向完全图，则G 的边数为 （ ）A. )1(-n n B ．)1(+n n C. 2)1(-n n D. 2)1(-n（25）图G 和G '的结点和边分别存在一一对应关系是G G '≅（同构）的 （ ）A. 充分条件； B ．必要条件；C. 充分必要条件；D. 既不充分也不必要条件.（26）给定下列序列，哪一个可构成无向简单图的结点度数序列 （ ）A. )3,2,2,1,1( B ．)2,2,2,1,1(C. )3,3,3,1,0(D. )5,4,4,3,1(（27）在有n 个结点的连通图G 中，其边数 （ ）A. 最多1-n 条； B ．至少1-n 条；C. 最多n 条；D. 至少n 条.（28）()mn ij m M ⨯=是无向图>=<E V G ,的关联矩阵，V v i ∈是G 中的孤立点，则 （ ）A. i v 对应的一行元素全为0； B ．i v 对应的一行元素全为1；C. i v 对应的一列元素全为0；D. i v 对应的一列元素全为1.（29）任何无向图G 中结点间的连通关系是 （ ）A. 偏序关系； B ．等价关系；C. 既是偏序关系又是等价关系；D. 既不是偏序关系也不是等价关系.（30）有向图>=<E V G ,，其中},,,,,{f e d c b a V =，,,,,,,{><><><=d a c b b a E },,,><><e f e d ，则有向图>=<E V G ,是 （ ）A. 强连通图； B ．单向连通图；C. 弱连通图；D. 不连通图.（31）下面哪个联结词不可交换 （ ）A. ∧； B ．→； C.∨； D.↔ .（32）命题公式q q p p →→∧))((是 （ ）A. 矛盾式； B ．非永真式的可满足式；C. 重言式；D. 等价式.（33）下列哪一组命题公式是等值的 （ ）A. q p ⌝∧⌝，q p ∨； B ．)(p q p →→，)(q p p →→⌝；C. )(q p q ∨∨，)(q p q ∨∧⌝；D. )(q p p ∧∨⌝，q（34）下面哪一个命题是假命题 （ ）A. 如果2是偶数，那么一个公式的析取范式唯一；B ．如果2是偶数，那么一个公式的析取范式不唯一；C. 如果2是奇数，那么一个公式的析取范式唯一；D. 如果2是奇数，那么一个公式的析取范式不唯一.（35）设论域为整数集，下列公式中哪个值为真 （ ）A. )0)()((=+∃∀y x y x ；B. )0)()((=+∀∃y x x y ；C. )0)()((=+∀∀y x y x ；D. )0)()((=+∃∃⌝y x y x .（36）设谓词x x P :)(是奇数，x x Q :)(是偶数，谓词公式))()()((x Q x P x ∧∃在哪个论域中是可满足的 （ ）A. 自然数； B ．整数； C. 实数； D. 以上均不成立.（37）命题“没有不犯错误的人”符号化为(设x x A :)(是人,x x B :)(犯错误) （ ）A. ))()()((x B x A x ∧∀；B.))()()((x B x A x →∃⌝；C. ))()()((x B x A x ∧∃⌝；D.))()()((x B x A x ⌝∧∃⌝.（38）设个体域},{b a A =，公式)()()()(x S x x P x ∃∧∀在A 上消去量词后应为 （ ）A. )()(x S x P ∧；B. ))()(()()(b S a S b P a P ∨∧∧；C. )()(b P a P ∧；D. )()()()(b S a S b P a P ∨∧∧.（39）在谓词演算中，下列各式中，哪一个是正确的 （ ）A.),())((),())((y x A x y y x A y x ∃∀⇔∀∃；B.),())((),())((y x A x y y x A y x ∃∃⇔∃∃；C.),())((),())((y x A y x y x A y x ∃∀⇔∀∃；D.),())((),())((y x B x y y x A y x ∀∀⇔∀∀.（40）“学习有如逆水行舟，不进则退”。