离散数学练习题

离散数学课后习题及答案离散数学是计算机科学与数学的重要基础课程之一，它涵盖了很多重要的概念和理论。

为了更好地掌握离散数学的知识，课后习题是必不可少的一部分。

本文将介绍一些常见的离散数学课后习题，并提供相应的答案，希望对读者有所帮助。

一、集合论1. 设A={1,2,3}，B={2,3,4}，求A∪B和A∩B的结果。

答案：A∪B={1,2,3,4}，A∩B={2,3}2. 设A={1,2,3}，B={2,3,4}，C={3,4,5}，求(A∪B)∩C的结果。

答案：(A∪B)∩C={3,4}二、逻辑与命题1. 判断下列命题的真假：a) 若2+2=5，则地球是平的。

b) 若今天下雨，则我会带伞。

c) 若x>0，则x^2>0。

答案：a)假，b)真，c)真。

2. 用真值表验证下列命题的等价性：a) p∧(q∨r) ≡ (p∧q)∨(p∧r)b) p→q ≡ ¬p∨q答案：a)等价，b)等价。

三、关系与函数1. 给定关系R={(1,2),(2,3),(3,4)}，求R的逆关系R^-1。

答案：R^-1={(2,1),(3,2),(4,3)}2. 设函数f(x)=x^2，g(x)=2x+1，求复合函数f(g(x))的表达式。

答案：f(g(x))=(2x+1)^2=4x^2+4x+1四、图论1. 给定图G，其邻接矩阵为：0 1 11 0 11 1 0求图G的度数序列。

答案：度数序列为(2,2,2)2. 判断下列图是否为连通图：a) G1的邻接矩阵为：0 1 11 0 01 0 0b) G2的邻接矩阵为：0 1 01 0 10 1 0答案：a)不是连通图，b)是连通图。

五、组合数学1. 从10个不同的球中，任选3个，求共有多少种选法。

答案：C(10,3)=120种选法。

2. 求下列排列的循环节：a) (123)(45)(67)b) (12)(34)(56)(78)答案：a)循环节为(123)(45)(67)，b)循环节为(12)(34)(56)(78)。

第1章命题逻辑一、单项选择题1. 下列命题公式等值的是( )BBAAQPQQPQB AABAAQPQP),()D(),()C() (),()B(,)A(∧∨⌝∨∨⌝∨→→→⌝→→∨⌝∧⌝2. 设命题公式G：)(RQP∧→⌝,则使公式G取真值为1的P，Q，R赋值分别是( )0,0,1)D(0,1,0)C(1,0,0)B(0,0,0)A(3. 命题公式QQP→∨)(为( )(A) 矛盾式(B) 仅可满足式(C) 重言式(D) 合取范式4 命题公式)(QP→⌝的主析取范式是( )．(A) QP⌝∧(B) QP∧⌝(C) QP∨⌝(D) QP⌝∨5. 前提条件PQP,⌝→的有效结论是( )．(A) P(B) ⌝P(C) Q(D)⌝Q6. 设P：我将去市里，Q：我有时间．命题“我将去市里，仅当我有时间时”符号化为( )QPQPQPPQ⌝∨⌝↔→→)D()C()B()A(二、填空题1. 设命题公式G：P→⌝(Q→P)，则使公式G为假的真值指派是2. 设P：我们划船，G：我们跑步，那么命题“我们不能既划船，又跑步”可符号化为3. 含有三个命题变项P，Q，R的命题公式P∧Q的主析取范式是4. 若命题变元P，Q，R赋值为(1,0,1)，则命题公式G＝)())((QPRQP∨⌝↔→∧的真值是5. 命题公式P→⌝(P∧Q)的类型是．6. 设A，B为任意命题公式，C为重言式，若C⇔∧，那么A∧CBA↔是式(重言式、矛盾式或可满B足式)三、解答化简计算题1.判别下列语句是否命题？如果是命题，指出其真值.(1) 中国是一个人口众多的国家. (2) 存在最大的质数.(3) 这座楼可真高啊！(4) 请你跟我走! (5) 火星上也有人.2.作命题公式)P∨∧→→的真值表，并判断该公式的类Q)((P)(PQ型．3. 试作以下二题：(1) 求命题公式(P∨⌝Q)→(P∧Q)的成真赋值．(2) 设命题变元P,Q,R的真值指派为(0,1,1),求命题公式∨P→R→⌝↔的真值．∧P⌝(()Q)((QR))4. 化简下式命题公式)⌝∧P∧∨Q⌝∧(P))Q((P5. 求命题公式))⌝∧→的主合取范式.Q→P∧P)(P((Q6. 求命题公式R→∧⌝⌝)((的真值．→(∧))QP∨PRQ∨↔RP7. 求命题公式)→∧→⌝的主析取范式，并求该命题公P⌝(Q)(PQ式的成假赋值．8. 将命题公式)⌝∧⌝化为只含∨和⌝的尽可能简单的⌝∧RQP→(P等值式．9. 求命题公式)∨⌝∧的真值表.P⌝∧)((QPQ四、证明题1. 证明S∧∧→)∨⌝)⌝(()(RQRS∧QP⌝P⌝∨⇒2. 构造推理证明：QR→→())((⇒S→)RPSQ→P∧∧3. 证明命题公式(P→(Q∨⌝R))∧⌝P∧Q与⌝（P∨⌝Q）等值．4. 证明命题公式)R→与QP→∧)(有相同的主析取范∨)((QRP→Q式．命题逻辑习题参考答案一、1. C 2. D 3. B 4. A 5. D 6. B二、1. 1,0；1,1 2. )(Q P ∧⌝或Q P ⌝∨⌝ 3. (P ∧Q ∧R )∨(P ∧Q ∧⌝R )4. 05. 非永真式的可满足式6. 重言三、1. (1) 是命题，真值为1. (2) 是命题，真值为0. (3), (4)不是命题. (5)是命题.1. 判别下列语句是否命题？如果是命题，指出其真值.(1) 中国是一个人口众多的国家. (2) 存在最大的质数.(3) 这座楼可真高啊！ (4) 请你跟我走! (5) 火星上也有人.2. 命题公式))(()(P Q P Q P ∨∧→→的真值表 P Q P →Q Q P ∧ P Q P ∨∧)())(()(P Q P Q P ∨∧→→ 0 0 1 0 0 00 1 1 0 0 01 0 0 0 1 11 1 1 1 1 1原式为可满足式.3. (1) (P ∨⌝Q )→(P ∧Q )⇔(⌝P ∧Q )∨(P ∧Q )⇔(⌝P ∨P )∧Q ⇔Q可见(P ∨⌝Q )→(P ∧Q )的成真赋值为(0,1)，(1,1)．(2) ))()(()(Q R Q P R P →⌝∨⌝→⌝∧↔0))10()01(()10(⇔→∨→∧↔⇔4. ))()((P Q P Q P ∧⌝∧⌝∨∧P Q P Q P ∧⌝∧⌝∨∧⇔)()()()(P P Q P Q P ∧⌝∧⌝∨∧∧⇔0)(∨∧⇔Q PQ P ∧⇔5. ))()((Q P P Q P ∧⌝∧→→))()((Q P P Q P ∧⌝∧∨⌝∨⌝⇔)())(Q P P Q P Q P ∧⌝∧∨∧⌝∧⌝∨⌝⇔)00(∧∨⌝⇔P)(Q Q P ⌝∧∨⌝⇔)()(Q P Q P ⌝∨⌝∧∨⌝⇔6. R P R Q P P R Q ∨↔∨→⌝∧→⌝∧)())((R P R Q P P R Q ∨↔∨∨∧∨∨⌝⇔)()(R P Q Q R P ∨↔∧⌝∨∨⇔)(1⇔7. Q P Q P Q P Q P Q P ⌝∧⇔⌝∨⌝∧⌝∧⇔⌝→∧→⌝)()()()(因为成真赋值是（1，0），故成假赋值为（0，0），（0，1），（1，1）8. ))()()(R P Q P P R Q P ∨∧∨⌝⇔→⌝∧⌝∧⌝))()((R P Q P ∨⌝∨∨⌝⇔不唯一．9. 作真值表P Q P∧Q⌝P⌝Q⌝P∨⌝Q (P∧Q)∧(⌝P∨⌝Q)0 0 0 1 1 1 00 1 0 1 0 1 01 0 0 0 1 1 01 1 1 0 0 0 0四、证明题1.①⌝Q∨R P②⌝R P③⌝Q①，②析取三段论④P→Q P⑤P⌝③，④拒取式⑥P∨⌝S P⑦⌝S⑤，⑥析取三段论2.前提：QPRSQP,)),((→→→结论：SR→证明：①R附加前提②R→P前提引入③P①，②假言推理④P→(Q→S) 前提引入⑤Q→S③,④假言推理⑥Q前提引入⑦S⑤,⑥假言推理3. (P→(Q∨⌝R))∧⌝P∧Q⇔(⌝P∨(Q∨⌝R))∧⌝P∧Q⇔(⌝P∧⌝P∧Q)∨(Q∧⌝P∧Q)∨(⌝R∧⌝P∧Q)⇔(⌝P∧Q)∨(⌝P∧Q)∨(⌝P∧Q∧⌝R)⇔⌝P∧Q⇔⌝(P∨⌝Q)4.方法1．)()(QRQP→∨→⇔)()(QRQP∨⌝∨∨⌝⇔∨∧⌝⇔QRP)(QRP→∧)(因为两命题公式等值，由主合取范式的惟一性，可知两命题公式的主合取范式是相同．方法2．)()(QRQP→∨→⇔)()(QRQP∨⌝∨∨⌝RQPQRP⌝∨∨⌝⇔∨⌝∨⌝⇔RQPQRPQRP⌝∨∨⌝⇔∨⌝∨⌝⇔→∧)(因为它们的主合取范式相同，可知它们的主析取范式也相同．第2章谓词逻辑习题一、 单项选择题1. 谓词公式)())()((x Q y yR x P x →∃∨∀中量词∀x 的辖域是( )(A) ))()((y yR x P x ∃∨∀ (B) P (x ) (C) )()(y yR x P ∃∨ (D) )(x Q2. 谓词公式∃xA (x )∧⌝∃xA (x )的类型是（ ）(A) 永真式 (B) 矛盾式(C) 非永真式的可满足式 (D) 不属于(A ),(B ),(C )任何类型3 设个体域为整数集，下列公式中其真值为1的是( )(A) )0(=+∃∀y x y x(B) )0(=+∀∃y x x y (C))0(=+∀∀y x y x (D) )0(=+∃⌝∃y x y x 4 设L (x )：x 是演员，J (x )：x 是老师，A (x ,y )：x 佩服y. 那么命题“所有演员都佩服某些老师”符号化为( )(A) ),()(y x A x xL →∀ (B) ))),()(()((y x A y J y x L x ∧∃→∀(C) )),()()((y x A y J x L y x ∧∧∃∀ (D) )),()()((y x A y J x L y x →∧∃∀ 5. 设个体域是整数集合，P 代表∀x ∃y ((x <y )→(x -y <0))，下面4个命题中为真的是( )(A) P 是真命题 (B) P 是谓词逻辑公式，但不是命题(C) P 是假命题 (D) P 不是谓词逻辑公式6. 表达式))(),(())(),((z zQ y x R y z Q y x P x ∀→∃∧∨∀中x ∀的辖域是( )(A) P (x ,y ) (B)R (x ,y ) (C)P (x ,y )∧R (x ,y ) (D) P (x ,y )∨Q (z )二、 填空题1. 设个体域D ＝{1,2},那么谓词公式)()(y yB x xA ∀∨∃消去量词后的等值式为.2. 设个体域D＝{a,b},公式))Gx→∀消去量词化为yHx∃(y,()(x3. 设N(x)：x是自然数，Z(y)；y是整数，则命题“每个自然数都是整数，而有些整数不是自然数”符号化为4. 谓词公式∀x(F(x)→G(x))∧⌝∀y(F(y)→G(y))的类型是．5. 设个体域{1,2},谓词P(1)=1,P(2)=0，Q(1)=0，Q(2)=1，则∀x(P(x)∨Q(x))的真值是三、解答化简计算题1. 判别谓词公式),(x∃yF∀→∃的类型.∀x,)yx(yyxF2. 指出谓词公式)(xQyPx∀中∀x和∃x的辖xR→∧∃x∧(,))x))(S)((x(域，并指出该公式的约束变元和自由变元以及约束出现次数和自由出现次数．3. 求谓词公式))PQx∧→x∀的真值．(R(())f(a其中P：4>3，Q（x）：x>1，R（x）：x≤2．f（-3）=1，f（1）=5，f（5）= -3．a：5．个体域D=（-3，1，5）．4.说明公式))xP∀xyG→(∀是逻辑有效式(永真式)．→x∃()y(,)(xxP5. 通过等值演算说明下列等值式成立：PxxxPQ∃→⇔∀→x∃)()()))(xQ(x(x6. 求谓词公式),,(xyyGxxF∃∧∀的前束范式.→∀yzH)(,,(xy(z))四、证明题1. 试利用代换实例证明谓词公式xyzGxF∀∃∀→∀x→,)())((xF(x)z是逻辑有效式(永真式)．2. 构造推理证明))xxQxxP∀∃．→∀⇒xP→(()()(Q(x)x（提示：))xA∨xxBx∀x∨∀⇒∀.))(()(()xB(xA谓词逻辑习题参考答案一、1. C ；2.. B ；3 A ；4. B ；5. A 6. D二、1. A (1)∨A (2)∨(B (1)∧B (2)) 2. (G (a )→(H (a ,a )∨H (a ,b )))∧ (G (b )→(H (b ,a )∨H (b ,b )))3.))()(())()((x N x Z x x Z x N x ⌝∧∃∧→∀ 4. 永假式 5. 1三、1.设I 为任意一个解释，D 为I 的个体域. 若在解释I 下，该公式的前件为0，无论),(y x xF y ∃∀如何取值，),(),(y x xF y y x yF x ∃∀→∀∃为1； 若在解释I 下，该公式的前件为1，则,0D x ∈∃使得),(y x yF ∀为1，它蕴含着),(,0y x F D y '∈'∀为1),(y x xF '∃⇒为1，由y '的任意性，必有),(y x xF y ∃∀为1，于是),(),(y x xF y y x yF x ∃∀→∀∃为1. 所以，),(),(y x xF y y x yF x ∃∀→∀∃是永真式．2. ∀x 的辖域为：P (x )→Q (x ,y )∧∃xR (x )∃x 的辖域为：R (x )x 既是约束变元，也是自由变元，约束出现3次，自由出现1次．y是自由变元，自由出现1次． 3. ))(())((a f R x Q P x ∧→∀=))5(())5(())1(())3((f R Q P Q P Q P ∧→∧→∧-→=)3()11()01()01(-∧→∧→∧→R01100=∧∧∧=4. 已知1)()(⇔∨⌝∨⌝⇔∨⌝∨⌝⇔→→P Q P P Q P P Q P因为))(),(()(x xP y x yG x xP ∀→∃→∀是)(P Q P →→的代换实例，可知))(),(()(x xP y x yG x xP ∀→∃→∀是逻辑有效式．或))(),(()(x xP y x yG x xP ∀∨⌝∃∨⌝∀1)(),()(⇔∨⌝∃∨⌝∀⇔x P y x yG x xP5. ⇔→∃))()((x Q x P x )()((x Q x P x ∨⌝∃))()(x xQ x P x ∃∨⌝∃⇔)()(x xQ x xP ∃∨⌝∀⇔)()(x xQ x xP ∃→∀⇔6. ),,()),(),((z y x zH y x yG y x xF ∃∧∀→∀),,()),(),((z y x zH y x yG y x xF ∃∧∀∨⌝∀⇔),,()),(),((z y x zH v u vG y u F u ∃∧∀∨⌝∃⇔)),,()),(),((z y x zH v u vG y u F u ∃∧∀∨⌝∃⇔)),,()),(),(((z y x H v u Q y u F z v u ∧∨⌝∃∀∃⇔(或)),,()),(),(((z y x H v u Q y u F z v u ∧→∃∀∃⇔)四、1.谓词公式))(),(()(x xF z x zG y x xF ∀→∃∀→∀ 是命题公式)(P Q P →→的代换实例．因为命题公式⇔∨⌝∨⌝⇔→→P Q P P Q P )(1是永真式， 故))(),(()(x xF z x zG y x xF ∀→∃∀→∀是逻辑有效式．2.前提：)()(x xQ x xP ∀→∃．结论：)()(x xQ x xP ∀→∃．证 ① )()(x xQ x xP ∀→∃ 前提引入② )()(x xQ x xP ∀∨⌝∃ T ①,蕴含等值式③ )()(x xQ x P x ∀∨⌝∀ T ②,量词否定④ ))()((x Q x P x ∨⌝∀⑤ ))()((x Q x P x →∀ T ④,蕴含等值式第3章 集合及其运算一、 单项选择题1. 设a 是集合A 的元素，则以下正确的是( )A a A a A a a a ∈⊆⊆⊆}){D ()C (}){B (}){A (2. 设集合A ={1,2,3,4},B ＝{2,4,6,9}，那么集合A ，B 的对称差A ⊕B＝( )(A) {1,3} (B) {2,4,6} (C) {1,3,6,9} (D) {1,2,3,4,6,9}3. 设集合A ＝{{1,2,3},{4,5},{6,7,8}}，则下列各式为真的是( )(A) 1∈A (B) {{4,5}}⊂A(C) {1,2,3}⊆A (D) ∅∈A4. 设A , B , C 都是集合，如果A ⋂C ＝B ⋂C ，则有( ) (A) A ＝B (B) A ≠B (C) 当A －C ＝B －C 时,有A =B(D) 当C =U 时, 有A ≠B5. 设集合A ＝{∅，a }，则P (A )＝ ( )}},{},{},{,){D (}}}},{,{},{},{,){C (}},{},{},){{B (}},{},{,){A (a a A a a a a a a ∅∅∅∅∅∅∅∅∅∅6. 设A ={1，2，3}，B ={2，3，4，5}，C ={2，3}，则（A ∪B ）⊕C 为（ ）(A) {1，2} (B) {2，3} (C) {1，4，5} (D) {1，2，3}二、 填空题1.设A , B 代表集合，命题A -B =∅⇔A=B 的真值为 ．2. 设A , B 为任意集合，命题A -B =∅⇔A⊆B 的真值为 ．3. 设集合A ={∅,{a }}，则A 的幂集P (A )=4. 设集合A ={{a ,b },c }, B ={c ,d }, 那么A －B ＝5. 设集合A ＝{1,2,3,4}，B ={a ，b ，c }，则∣A ×B ∣＝三、解答化简计算题1. 试作以下二题：(1) 设有序对＜2x +y ,6＞=＜5,x +y ＞,求x ,y ；(2)设集合A ＝{1,2},求A ×P (A ).2. 设集合A ＝{a ,b ,c },B ={b ,d ,e }，求B ⋂A ，A ⋃B ，A －B ，B ⊕A ．3. 化简集合表达式：((A ⋃B ⋃C )⋂(A ⋃B ))－((B ⋃(B －C ))－A )4. 判断下列哪些运算结果是对的？哪些是错的？请将错误的运算结果更正过来．(1) ∅=∅⋂∅}{ (2) ∅=∅⋃∅}{(3) }{}}{,{}{∅=∅∅⋂∅ (4) }}{,{}{}}{,{∅∅=∅-∅∅（5）A B B A =⋃-)( （6）A B B A =-⋃)(（7）A A A =⊕ （8）∅=-⋂A B A )(5.易,0.5,8,掌握,2-2 设全集E ＝(a ,b ,c ,d ,e ,f ), A ={a ,d }，B ={a ,b ,e }，C ={b ,d }，求下列集合：(1) C B A ~)(⋃⋂； (2))()(A P A A ⋃⊕.6. 设},{},,,{},,{},,,,,{42=521=41=54321=C B A E求 (A ⋂B )⋃~C ，P (A )－P (B )，A ⊕B ．四、证明题1. 设A ，B ，C 为三个集合，证明若C ⊆A ．则(A ⋂B )⋃C ⊆A ⋂(B ⋃C )2. 试证明对任意集合A ，B ，C ，如果B A ⊆且D C ⊆，则C BD A -⊆- 3. 设A ，B ，C 为任意集合，证明：)()()(C B C A C B A ---=--集合练习题参考答案一、1. B 2. C 3. B 4. C 5. D 6. C 二、1. 0 2. 1 3. }}}{,{}},{{},{,{a a ∅∅∅ 4. {{a ,b }} 5.12三、解答化简题1. (1) 由有序对定义，解方程⎩⎨⎧=+=+652y x y x 解得x=－1，y=7．(4分)（2）P （A ）={∅,{1},{2}{1,2}}A ⨯P (A )={<1,∅>,<2,∅>,<1,{1}>,<2,{1}>,<1,{2}>,<2,{2}>,<1,{1,2}>,<2,{1,2}>}2. B ⋂A ＝{b } A ⋃B ={a ,b ,c ,d ,e } A －B ={a ,c } B ⊕A ={a ,b ,c ,d ,e }－{b }={a ,c ,d ,e }3. ((A ⋃B ⋃C )⋂(A ⋃B ))－((B ⋃(B －C ))－A )＝(A ⋃B )－(B －A ) =(A ⋃B )⋂(～B ⋃A ) =A ⋃(B ⋂～B )=A ⋃∅=A4. (1) 对． (2) 错．应为}{∅． (3) 对． (4) 错．应为{}{∅}（5）错．应为B A ⋃ （6）错．应为B A -(或B A ~⋂或A －AB )（7）错．应为∅，即∅=⋂-⋃=⊕A A A A A A （8）对． 5. (1) },,,{},,,{}{~)(f e c a f e c a a C B A =⋃=⋃⋂ (2)∅=⋂-⋃=⊕)()()(A A A A A A . }},{},{},{,{)(d a d a A P ∅=.故)()(A P A A ⋃⊕＝}},{},{},{,{d a d a ∅ 6. (A ⋂B )⋃~C ={1}⋃}5,3,1{}5,3,1{=}},{},{{}},{},{},{,{}},{},{},{,{)()(411=4242-4141=-φφC P A PA⊕B =(A⋃B)－（A⋂B）=}5,4,2{}5,4,2,1{=-}1{四、证明题1. 已知xC∀⊆,A∈⋂∨⇔⋃(∈)x∈⋂CAxABxBC∈∧(⇔)∈∨Cx∈BxAx∨∈x∈∧⇔A∈∨∈x(C)(x)BCx∈∈x⋃∨⋂∧A⇒∈∈⇔B(C(xA)BxC)即)⋂A⋃⊆⋂B⋃(CC)(AB2. 由于C⇔~⊆⊆，DC~D又有BA⊆，所以⊆⋂~⋂DCA~B即C-．⊆A-DB3. )A⋂CC⋂B---A=⋂~)~(~C(B(C))(⋂A⋃C=⋂~B(~))(CA⋂CB⋂⋂A⋂⋃=(~))~(C~C＝C)~~(⋂⋂⋂=⋂= C)(BBAC~A~(-)BA-第3章 二元关系练习题一、 单项选择题1. 设集合A ＝{0,b },B ={1,b ,3},则A ⋃B 上的恒等关系是 ( ).(A) {<0,0>,<1,1>,<3,3>} (B){<0,0>,<1,1>,<b ,b >,<3,3>}(C) {<1,1>,<b ,b >,<3,3>} (D) {<0,1>,<1,b ><b ,3>,<3,0>} 2. 已知集合A ＝{a ,b ,c }上的二元关系R 的关系矩阵M R ＝⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001011010，那么R ＝( )，(A) {<a ,b >,<b ,a >,<b ,b >,<a ,c >} (B) {<a ,b >,<b ,a >,<b ,b >,<c ,b >} (C) {<a ,b >,<a ,a >,<b ,b >,<c ,a >} (D) {<a ,b >,<b ,a >,<b ,b >,<c ,a >} 3. 设集合A ={1,2,3,4}, A 上的二元关系R 的关系矩阵为M R ＝⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡00000001011001则关系R 的表达式是( )(A) {<1,1>,<1,4>,<2,1>,<2,3>} (B) {<1,1>,<1,2>,<1,4>,<2,3>} (C) {<1,1>,<2,1>,<3,2>,<1,4>} (D) {<1,1>,<2,1>,<3,2>,<4,1>}4. 设A ={a ，b ，c }，R ={<a ，a >，<b ，b >}，则R 具有性质（ ） (A) 自反的 (B) 反自反的 (C) 反对称的 (D) 等价的5. 设R 是集合A 上的二元关系，I A 是A 上的恒等关系，如果R ⊂I A ，则下面四个命题中为真的是（ ）(A) R 不是自反的 (B) R 不是传递的 (C) R 不是对称的 (D) R不是反对称的 二、填空题1. 设R ，S 都是集合A 上的等价关系，则对称闭包s (R ⋂S )=2. 如果关系R 是传递的，则R ∙R ⊆ ．3. 设集合A ={1,2,3,4 }, B ={6,8,12}, A 到B 的关系R ＝},,2,{B y A x x y y x ∈∈=><,那么R －1＝4. 设X ＝{a ,b ,c }，R 是X 上的二元关系，其关系矩阵为 M R＝⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001001101，那么R 的关系图为 ．5. 设A ={1,2,3,4}，A 上的二元关系}3,{Z ∈-><=y x y x R ,其中Z 是整数集合．试用列举法那么R＝ ． 三、解答化简计算题1. 设集合A ＝{a ,b ,c ,d }，在A 上定义二元关系R ＝{<a ,a >,<a ,d >,<b ,b >,<b ,c >,<c ,b >,<c ,c >,<d ,a >,<d ,d >} R 是否为等价关系，说明理由.2. 设R 是实数集，R 上的二元关系S 为 S ＝{<x ,y >∣x ,y ∈R ∧x =y }试问二元关系S 具有哪些性质？简单说明理由．3. 设A ＝{1,2},B ={a ,b },试问从A 到B 的二元关系有多少个?4. 设集合A ＝{0，1，2，3，4，5，6}上的偏序关系R 如下： R={<0,1>,<0,2>,<0,3>,<0,4>,<0,5>,<0,6>,<4,6>,<2,5>,<3,5>}⋃I A 做偏序集<A ,R >的哈斯图，并求B ={0,2,3}的极大元、极小元、最大元和最小元．5. 设集合A ={0,1,2,3,4}，定义A 上的二元关系R 为： R ＝{<x ,y >⎪x ,y ∈A ∧(x =y ∨x +y ∈A )}试写出二元关系R 的集合表达式，并指出R 具有的性质．6. 已知集合A 上的二元关系R 的关系图如图4－1，试写出R 的集合表达式和R 的关系矩阵．并指出R 所有的性质．7. 设集合A ＝{1,2,3,4}, B ＝{2,4,6} 从A 到B 的二元关系R 定义为R ＝},{N k k xy B y A x y x ∈∧=∧∈∧∈><试求R 的集合表达式和关系矩阵M R .8. 设R 1是A 1＝{1,2}到A 2＝(a ,b ,c )的二元关系，R 2是A 2到A 3＝{βα,}的二元关系，R 1= {<1,a >,<1,b >,<2,c >}, R 2={<a ,β>,<b ,β>} 试用关系矩阵求R 1∙R 2的集合表达式.9. 设集合X ＝{a ,b ,c ,d },X 上的二元关系R 的关系图如图4－2所示．试写出R 的表达式和关系矩阵．10. 设集合S ＝{1,2,3,4},定义S 上的二元关系 })(,,{2y x S y x S y x y x R >∧∈-∧∈><=},,{是素数yx S y x y x T ∧∈><=试求R ，T 的元素表达式，并计算R ∙T ． 四、证明题1. 证明如果非空集合A 上的二元关系R 和S 是偏序关系，则S R ⋂也是A 上的偏序关系．2. 设R 是集合A 上的二元关系，试证明R 是自反的当且仅当R I A ⊆．3. 假设R 是非空集合A 上的等价关系，证明R 的逆关系R －1也是A 上的等价关系．0 ∙ ∙2 1∙ 图4－ 1a db c图4－2二元关系习题参考答案一、1. B 2. D 3. A 4. C 5. A二、1. R ⋂S 2. R 3. {<6,3>,<8,4> }4. 如图4－3．5. }1,4,4,1{><><⋃A I三、1. R 含有<a ,a >,<b ,b >,<c ,c >,<d ,d >, 是自反的；R 含有<a ,a >,<b ,b >,<c ,c >,<d ,d >,<a ,d >,<d ,a >,<b ,c >,<c ,b >, 是对称的； 对R z x R z y R y x >∈⇒<>∈<>∈<∀,,,,，是传递的.故R 是A 上的等价关系.2. S 具有自反性，显然<x ,x >∈S ； S 具有对称性，∀<x ,y >∈S ，有x =y ，则<y ,x >∈S ； S 具有反对称性，∀<x ,y >,<y ,x >∈S ，有x =y ； S 具有传递性，∀<x ,y >,<y ,z >∈S ,因为x =y =z ，故<x ,z >∈S ．3. 二元关系共有16个．4. A ＝{0,1,2,3,4,5,6}, B ={0，2，3}， 哈斯图如图4－4．B 的极大元：2，3, B 的极小元：0 B 的最大元：无 B 的最小元：05. 由题设，R ＝I A ⋃{<0,1>,<1,0>,<0,2>,<2,0>,<0,3>,<3,0>,<0,4>,<4,0>,<1,2>,<2,1>,<1,3>,<3,1>}易知，R 具有自反性和对称性．6. }0,2,2,0,2,2,0,0{><><><><=R⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=101000101RMR 有对称性和传递性．7. R ＝{<1,2>,<1,4>,<1,6>,<2,2>,<2,4>,<2,6>,<3,6>,<4,4>}M R =⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡01100111111 a c b 图4－3 6∙ 5∙∙4 3∙ 2∙ ∙10∙ 图4－48. ,100111⎥⎦⎤⎢⎣⎡=R M⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=0010102R M ⎥⎦⎤⎢⎣⎡=∙10001121R R M ⎥⎦⎤⎢⎣⎡=⎥⎥⎦⎤⎢⎢⎣⎡0010001010 },1{21><=∙βR R9. R ＝{<a ,a >,<a ,c >,<b ,c >,<d ,d >}⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=1000000001000101R M 10. }2,4,3,4,2,3,1,2{><><><><=R}2,4,1,3,1,2{><><><=T }1,4,1,3{><><=⋅T R四、证明题1. .① S R x x S x x R x x A x ⋂>∈⇒<>∈<>∈<∈∀,,,,,，所以S R ⋂有自反性；②,,A y x ∈∀因为R ，S 是反对称的，yx x y y x S x y S y x R x y R y x S x y R x y S y x R y x S R x y S R y x =⇔=∧=⇒>∈<∧>∈<∧>∈<∧>∈<⇔>∈<∧>∈<∧>∈<∧>∈<⇔⋂><∧⋂><),,(),,(),,(),,(,, 所以，R ⋂S 有反对称性．③ A z y x ∈∀,,，因为R ，S 是传递的， S R z y S R y x ⋂>∈<∧⋂>∈<,,S z y R z y S y x R y x >∈<∧>∈<∧>∈<∧>∈⇔<,,,, S z y S y x R z y R y x >∈<∧>∈<∧>∈<∧>∈⇔<,,,, S R z x S z x R z x ⋂>∈⇔<>∈<∧>∈⇒<,,,所以，S R ⋂有传递性． 总之，R 是偏序关系. 2. 先证必要性．假设R I A ⊆/，则必存在x ∈A ,使得<x ,x >∈I A ,且<x ,x >∉R ,这与R 是自反的相矛盾．所以R I A ⊆．再证充分性．设R I A ⊆，则对,,,A I x x A x >∈<∈∀因为R I A ⊆，所以R x x >∈<,．因此R 是自反的．3. (1) ∀x ∈A ，则<x ,x >∈R ，显然<x ,x >∈R －1，R －1具有自反性． (2) ∀x ，y ∈A ， 如果<x ,y >∈R －1⇔<y ,x >∈R⇒<x ,y >∈R (R 是对称的)⇔<y ,x >∈R －1， R －1具有对称性．(3) ∀x ,y ,z ∈A ，如果<x ,y >∈R －1∧<y ,z >∈R 1⇔<y ,x >∈R ∧<z ,y >∈R ⇔<z ,y >∈R ∧<y ,x >∈R ⇒<z ,x >∈R （R 是传递的）⇔<x ,z >R －1，R 具有传递性．总之，R 是等价关系．第5章 群练习题一、单项选择题1. 设A ＝Q ×Q ，其中Q 是有理数集，定义A 上的二元运算*为:),,(b a ∀,A y x ∈),(,),(),(),(b ay ax y x b a +=*,则(1,2)*(3,4)=())6,3)(D ()8,6)(C ()1,5)(B ()10,3)(A (-2. 下列集合和运算能构成群的是 ( )．(A) (M n (R ),+),其中M n (R )是定义在实数集上的n 阶矩阵，＋是普通加法 (B)(A ,+),其中A ＝{0,±1,±2,…,±n },+是普通加法 (C)({21,0,2},+),其中＋是普通加法(D) ({0,1,2,3},⊗),其中运算⊗是模4乘法3. 在自然数集N 上定义的二元运算*，满足结合律的是( )ba b a b a b a b a b a b a b a -=*=*2+=*-=*)D (},max{)C ()B ()A (4. 以下代数系统中，只是半群的为( )． (A) (Z ，︒)，其中Z 是整数集，∀a ,b ∈Z ,a ︒b =a +b －2 (B) (Z ，︒)，其中Z 是整数集，∀a ,b ∈Z ,a ︒b =b (C) (Z ，︒)，其中Z 是整数集，∀a ,b ∈Z ,a ︒b =a +b －ab(D) (R －{0}，︒)，其中R 是实数集，∀a ，b ∈R ,a ︒b =ab 5. 以下群中，是循环群的为( )． (A) (Z ，+)，其中Z 是整数集，+是数的加法 (B) (Q +，×)，其中Q +是正有理数集，×是数的乘法 (C) (Q ，+)，其中Q 是有理数集，+是数的加法(D) (P (A),⊕)，其中A ={a ,b },P (A)是A 的幂集，⊕是集合的对称差运算 二、填空题 1. 设R 是实数集，∀a ,b ∈R ,定义二元运算*：a *b =a +b +ab ,已知0∈R 是其单位元，那么∀a ∈R ,但a ≠－1，则a 的逆元是 .2. 设(R *, )是代数系统，其中R *＝R －{0}，二元运算 定义为abb a R b a =∈∀ ,,*,那么，a R a ,*∈∀的逆元是3. 设集合A ＝{1，2，3}，在A 上定义二元运算︒为：,,A b a ∈∀a ︒b =},min{b a ，则︒的运算表为︒ 1 2 3 1 2 34. 设S 是非空有限集合，P （S ）是S 的幂集，则代数系统<P (S ),⋃ >存在单位元是 三、解答化简计算题1. 设代数系统(R *, ︒)，其中R *是非0实数集，二元运算︒为：∀a ,b ∈R , a ︒b =ab. 试问︒是否满足交换律、结合律，并求单位元以及可逆元素的逆元.2. 验证H 2={e ,a 3}是6阶循环群G ={ e ,a 1,a 2,a 3,a 4, a 5}的子群．3. 验证代数系统(Z ,+)与(2Z ，+)同构．4. 设集合A ＝{1,2,3}，P (A )是A 的幂集合，⊕是集合的对称差运算．求运算⊕在P (A )上的单位元．∀x ∈P (A )，求x 关于运算⊕的逆元．并解方程{1,2}⊕y ={1}．四、证明题1. 设群(G ,*), 若∀a ∈G ,都有a 的逆元a －1=a ，则G 是交换群.2. 设R *=R －{0}，集合S 定义为},00{*R b a b a S ∈⎥⎦⎤⎢⎣⎡= 证明代数系统(S ，*)是群，其中*是矩阵的乘法运算．3. 在整数集合Z 上定义二元运算︒：∀x ,y ∈Z , x ︒y =x +y －2，已知<Z , ︒>是半群，证明<Z ，︒>是群．4. 证明群(R ，+)与(R +，∙)同构，其中+和∙分别是数的加法和乘法．(提示：考虑函数f (x )=e x )群练习题参考答案一、1. D 2. A 3. C 4. B 5. A 二、1. 1+-a a 2.a1 3.4. ∅三、1. ∀a ,b ,c ∈R *, a ︒b =ab =ba =b ︒a ，可交换； (a ︒b )︒c =ab ︒c =abc =a (bc )=a ︒(bc )=a ︒(b ︒c )，可结合. 易见，单位元为1.对∀a ∈R *, a ︒a －1=aa －1=1=a －1a ＝a －1︒a ，故a 的逆元：aa 11=-2. (1) H 2⊂G ．易验证∀x ,y ∈H 2,有xy ∈H 2．且在H 2上满足结合律． e 是其单位元，(e )－1=e ，(a 3)－1=a 3． 故H 2是G 的子群．3. ∀z ∈Z ，f (z )=2z ，有f ：Z →2Z ．∀z 1,z 2∈Z ，f (z 1+z 2)=2(z 1+z 2)= 2z 1+2z 2= f (z 1)+f (z 2) 所以，(Z ,+)与(2Z ，+)同态．又因为f (z )=2z 是双射函数，故(Z ,+)与(2Z ，+)同构． 4. ∀S ∈P (A)，S ⊕∅=∅⊕S =S ，故∅是单位元． ∀x ∈P (A)，x ⊕x =∅，故x 的逆元是它自己． 因为(1,2)的逆元是{1,2}，故y ={1,2}⊕{1}={2}． 四、1. 111,,)(,,,---==*=*∈*∈∀b b a a b a b a G b a G b a 由题设(3分) 于是有a b a b b a b a b a *====--------11111111)(*)()*()*(* 所以G 是一个交换群.2. 任取S 中的元素⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡d c y x b a00,00,00，其中a ,b ,x ,y ,c ,d ∈R *，有⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡=⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡byd axc yd xcb a dc y x b a byd axc d c by ax d c y x b a 0000*00)00*00(*000000*0000*)00*00(︒1 2 3 1 1 1 1 21 2 2 3123可见，*满足结合律，故(S ，*)是半群． 取E =S ∈⎥⎦⎤⎢⎣⎡1001，∀A ∈S ，有AE ＝EA ＝A ．E 为S 的单位元．∀X ∈S ，X =⎥⎦⎤⎢⎣⎡y x0，x ,y ∈R *，则存在⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡y x 1001∈S ，则有⎥⎦⎤⎢⎣⎡y x0*⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡y x 1001＝⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡y x 1001*⎥⎦⎤⎢⎣⎡y x 00=E ，即X －1＝⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡y x 1001．S 的每个元素都有逆元.故(S , *)是群． 3. 因为<Z ，︒>是半群，易见二元运算︒满足交换律．设幺元为e , ∀x ∈Z ，有x ︒e =x +e －2=x ，得到e =2∈Z ，幺元存在惟一；∀x ∈Z , x 的逆元记作x －1, x ︒x －1=x +x －1－2=2, 即x －1=4－x ∈Z ，即x 的逆元存在且惟一．所以，<Z ，︒>是群． 4.设f (x )=e x ，可知f ：R →R +．(1) ∈∀21,x x R ，)()(e e e )(21212121x f x f x x f x x x x ∙===++∈R +． 0和1分别是(R ，+)和(R +，∙)的单位元，有 f (0)=e 0=1对任意x ∈R ，x 关于+的逆元为－x ，而f (－x )＝e －x ＝)(11x f ex=．(2) f ：R →R +是双射函数．所以，(R ，+)与(R +，∙)同构．第6章 格与布尔代数及环、域练习题一、 单项选择题1.下列偏序集中是格的为( )2. 设布尔代数式c b a f ⋅+=，则f 的对偶式f *=( )(A) c b a ⋅+ (B) c b a ⋅+ (C) c b a +⋅ (D) c b a +⋅ 3. ( )是布尔代数． (A) 有余有界格 (B) 有余分配格 (C) 有界分配格 (D) 有余代数格 4. 设G 是非空集合，G 上二元运算︒和*，*对︒有左、右分配律，又满足( )，则(G ,︒,*)称为环．(A) (G ,*)是交换群，(G ,︒)是交换群 (B) (G ,*)是半群，(G ,︒)是半群(C) (G ,*)是群，(G ,︒)是群 (D) (G ,*)是半群，(G ,︒)是交换群二、 填空题1. 设代数系统(L ，︒，*)，若(L ，︒)是 ，(L ，*)是半群，又二元运算*对︒满足分配律，则(L ，︒，*)是环.2. 布尔代数式))(()1(c a b a +⋅+⋅的对偶式是3.在布尔代数中，有b a b a a +=⋅+)(成立，则其对偶式 一定成立．4. 若<G ,+,∙>是环，那么∀a ,b ∈G ，有 则称<G ,+,∙>是交换环． 三、解答化简计算题1. 设代数系统(Z ，+，×)，已知(Z ，×)是半群，验证(Z ，+，×)是环．2. 设(L ，*，︒)是有补格，∀a ,b ∈L ，化简表达式 (a *b )*(a '︒b ')(其中a ',b '分别是元素a ,b 的补元)3. 已知(L ，*，︒)是格，且二元运算*和︒满足分配律，∀a ,b ,c ∈L ，化简表达式 ((a *b )︒(a *c ))* ((a *b )︒(b *c ))4. 试作以下二题：(1)已知A ≠∅，则(P (A )，⋃，⋂，～，∅，A )是布尔代数，∀S ∈P (A )，求S 的补元，说明理由．（2）布尔代数(),,,+∙B ，其中}1,0{=B ，若B 上的三个变元的表达式c b c b a c b a E ++∙+=),,(求)1,1,0(E 的真值．四、证明题1. 设R 为实数集，证明(R ，＋)是交换群，(R ,×)是半群，且×对＋满足左、右分配律，即(R ，＋，×)是环．其中＋，×是普通加法和乘法．2. 设<S ,+,∙,,0,1>为一布尔代数，证明∀a ,b ∈S ，有b a b a a +=∙+)(；b a b a a ∙=+∙)((A)(B) (C) (D)格等代数系统习题参考答案一、 1. B 2. C 3. B 4. D二、1.交换群 2. ))(()0(c a b a ⋅+⋅+ 3. b a b a a ⋅=+⋅)( 4. a ∙b =b ∙a 三、1.只需验证(Z ，+)是交换群． 易验证整数具有结合律，交换律． 0是加法的单位元．(4分)∀k ∈Z ，∃－k ∈Z ，有 k +(―k )=(―k )+k =0Z 中每个元素有逆元．故(Z ,+)是交换群． 所以(Z ,+,×)是环．(8分)2. (a *b )*(a '︒b ')＝(a *b )* (a *b ) '=13. ((a *b )︒(a *c ))*((a *b )︒(b *c ))＝(a *b )︒ ( (a *c )* (b *c ))(分配律) =(a *b ) ︒((a *b )*c ) (幂等律) =a *b (吸收律)4. (1) 对任意S ， 因为S ⋃(A －S )=(S ⋃A )⋂(S ⋃~S )=A ，S ⋂(A －S )=S ⋂(A ⋂~S )=∅故S 的补元为A －S ．（2） 因为c b c b a c b a E ++∙+=),,(所以， E (0,1,1) =11110++∙+=1110++∙=0+1=1四、1. (1)∀x ,y ,z ∈R ,有(x +y )+z =x +(y +z ),满足加法 R 上满足加法结合律． (2) ∀x ,y ∈R ,有x +y =y +x ,满足加法R 上满足加法交换律．(3)R 中存在元素0，使得∀x ∈R ,有x +0 =0＋x , 加法单位元存在，为0． (4) ∀x ∈R , 存在－x ∈R ，使得x +(－x )=0，加法逆元存在，x －1=－x ． 可见(R ,+)是交换群； (5) ∀x ,y ,z ∈R ,有(x ×y )×z =x ×(y ×z ),满足乘法结合律． 可见(R ,×)是半群； (6) ∀x ,y ,z ∈R ,有(x +y )×z =x ×z +(y ×z ), z ×(x +y )=z ×x +z ×y , 满足左、右分配律．二元运算×对＋满足左右分配律．总之，(R ，＋，×>是环． 2. b a b a b a a a b a a +=+∙=+∙+=∙+)(1)()()( b a b a b a a a b a a ∙=∙+=∙+∙=+∙0)()(第７章 图的基本概念一、 单项选择题1. 设V ＝{a ,b ,c ,d },与V 能构成强连通图的边集E ＝( )(A) {<a ,b >,<a ,c >,<d ,a >,<b ,d >,<c ,d >} (B) {<a ,d >,<b ,a >,<b ,c >,<b ,d >,<d ,c >} (C) {<a ,c >,<b ,a >,<b ,c >,<d ,a >,<d ,c >} (D) {<a ,d >,<b ,a >,<b ,d >,<c ,d >,<d ,c >} 2. 有向完全图D ＝<V ,E >, 则图D 的边数是( )(A)2)1(-E E (B)2)1(-V V (C) ∣E ∣(∣E ∣－1) (D) ∣V ∣(∣V ∣－1)3. n 阶无向完全图K n 中的边数为（ ） (A)2)1(-n n (B)2)1(+n n (C) n (D)n (n +1)4. 给定无向图G 图5－1所示，下面给出的顶点集子集中，不是点割集的为（ ）(A) {b ,d } (B) {d } (C) {a ,c } (D) {g ,e } 5. 下列数组中，不能构成无向图的度数列的数组是( )(A) (1,1,1,2,3) (B) (1,2,3,4,5) (C) (2,2,2,2,2) (D) (1,3,3,3)二、 填空题1.设有向图D ＝<V ,E >的邻接矩阵为A (D )=0110101000010110⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦，那么∣E ∣＝ . 2. 无向图G (如图5－2)的关联矩阵M (G )=3. 数列{2，3，3，4}不能构成无向简单图的度数列，此命题的真值为4. 在有向图的邻接矩阵中，第i 行元素之和与第j 列元素之和分别为 ．5. 图G 如图5－3，那么图G 的割点是6. 有16条边，每个顶点都是2度顶点的无向图有个顶点．三、解答化简计算题 1. 设图G 如图5－4所示．已知通路(1) v 1e 5 v 5e 7 v 2e 2 v 3(2) v 5e 6 v 2e 2 v 3e 3 v 4e 8 v 2e 7 v 5 (3) v 2e 7 v 5e 6 v 2(4) v 1e 1 v 2e 2 v 3e 3 v 4e 8 v 2e 6 v 5试回答它们各是简单通路、简单回路、 初级通路还是初级回路．a gb d fc e 图5－ 1 v 2e 2 v 3 e 1 e 3 v 1 e 4 v 4 图5－2a bf ce d图5－3 v 1 e 1 e 5 v 2 e 6 v 5 e 2 e 7 e 4 e 8v 3 e 3 v 4 图5－42. 指出有向图D(如图5－5)中各图是强连通，单侧连通还是弱连通？3. 找出无向图G（如图5－6所示）中的一个点割集，三条边和四条边的边割集各一个．4. 已知有向图D(如图5－7)的邻接矩阵为A(D)=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡111111111求从v2到v4长度为2和从v3到v3长度为2的通路条数，并将它们具体写出.5. 设图G＝<V，E>，其中V＝{a,b,c,d,e}, E={(a,b),(b,c),(c,d), (a,e)}试作出图G的图形，并指出图G是简单图还是多重图？是连通图吗？说明理由.6. 设简单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G中有多少个结点．试作一个满足该条件的简单无向图．四、证明题1. 若无向图G中只有两个奇数度结点，则这两个结点一定是连通的．2 证明在任何有向完全图中，所有结点的入度平方之和等于所有结点的出度平方之和．(1)(2)(3)(4)(5)图5－5a bce d图5－6v4 v3v1 v2图5－7图的基本概念习题参考答案一、1. A 2. D 3. A 4. A 5. B二、1. 7 2. ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡11001101101001 3. 1 4.结点v i 的出度与结点v j 的入度 5. a , f 6. 16 三、1. (1) 初级通路； (2) 简单回路； (3) 初级回路； (4) 简单通路．2. 强连通图为：图5－5的(1),(4),(5)；单侧连通图为：如图5－5的(1),(2),(4),(5)，或图5－5的(2)； 弱连通图为：图5－5(1)～(5)，或图5－5的(3).．3. 点割集：{a ,c ,d }(不惟一) 三条边的边割集：{(b ,c ),(c ,e ),(c ,d )}(不惟一) 四条边的边割集：{(a ,b ),(a ,d ),(d ,e ),(c ,e )}(不惟一)4.. A 2(D )=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡2120020221201212从矩阵A 2(D )中a 24=2,a 33=2可知，从v 2到v 4长度为2的通路有2条. 它们是： v 2v 3v 4,和v 2v 1v 4, 从v 3到v 3长度为2的通路有2条. 它们是： v 3v 4v 3,和v 3v 2v 3,5. 图G 如图5－8.图G 中既无环，也无平行边，是简单图.图G 是连通图. G 中任意两点都连通. 6. 设图G 有x 个结点，有握手定理 2⨯1+2⨯2+3⨯4+3⨯（x -2-2-3）＝12⨯2271821243=-+=xx ＝9 图G 有9个结点． 作图如图5－10四、1. 用反证法．设G 中的两个奇数度结点分别为u 和v ．假若u 和v 不连通． 即它们之间无任何通路，则G 至少有两个连通分支G 1，G 2，且u 和v 分别属于G 1和G 2，于是G 1和G 2各含有一个奇数度结点．这与握手定理的推论矛盾．因而u 和v 一定是连通的．ab ec d图5－8 图5－10第七章几种特殊图练习题一、 单项选择题1. 以下命题真值为1的是( )(A) 无向完全图都是欧拉图 (B) 有n 个结点n －1条边的无向图都是树 (B) 无向完全图都是平面图 (D) 树的每条边都是割边 2. 有4个结点的非同构的无向树有 ( )个． (A) 2 (B) 3 (C) 4 (D) 5 3. 无向完全图K 4是（ ）（A ）欧拉图 （B ）哈密顿图 （C ）树 （D ）非平面图 4. 以下各图中存在哈密顿回路的图是 ( )5. 设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． (A) e －v ＋2 (B)v ＋e －2 (C)e －v －2 (D) e ＋v ＋26. 无向图G 是欧拉图，当且仅当( )(A) G 中所有结点的度数全为偶数 (B) G 中所有结点的度数全为奇数 (C) G 连通且所有结点的度数全为偶数 (D) G 连通且所有结点的度数全为奇数 7. 设G 是有6个结点的无向完全图，从G 中删去( )条边，则得到树． (A) 6 (B) 9 (C) 10 (D) 15二、填空题1. 无向连通图G 含有欧拉回路的充分必要条件是2. 设图G =<V ,E >，其中|V |=n ,|E |=m ．则图G 是树当且仅当G 是连通的，且m = ．3. 图G （如图6－1所示）带权图中最小生成树的权是4.在平面图>=<E V G ,中,则∑=ri i r 1)deg(＝ ,其中r i (i =1,2,…,r )是图G 的面．5. 设图>=<E V G ,是简单图，若图中每对结点的度数之和 ，则G 一定是哈密顿图．6. 设G 是连通平面图，v ,e ,r 分别表示G 的结点数，边数和面数，则v ,e 和r 满足的关系式是三、解答化简计算题1. 设无向图G ＝<V ,E >, 那么图G 中∣V ∣与∣E ∣满足什么条件，图G 一定是树.2. 图G (如图6－2)能否一笔画出？说明理由. 若能画出，请写出一条通路或回路.3. 给定三个图如图6－3所示，试判断它们是否 为欧拉图、哈密顿图、或平面图？并说明理由．(A) (B) (C) (D)∙2 2 3∙ 1 ∙7 9 2∙ 8 ∙ 6 图6－1v 5 d v 4 v 1 v 2 v 3 图6－2 e f n c a h g b。

离散数学及其应用第2版课后练习题含答案1. 引言《离散数学及其应用》是一本经典的离散数学教材，是计算机科学和数学专业的必修课程。

本文将为读者提供《离散数学及其应用》第2版课后练习题的答案，并希望能够帮助读者加深对离散数学的理解。

2. 答案解析第一章习题 1.11.给定一组七个数字 {1, 3, 3, 4, 6, 9, 12}，请给出这组数字的中位数。

答案：中位数为 4。

2.给出两个整数 a 和 b 的三进制表示： a = 111011，b = 101101。

求 a + b。

答案：a + b = 1011000。

3.证明奇奇数的积为奇数。

答案：令两个奇数分别为 2n + 1 和 2m +1，则有：(2n + 1) × (2m + 1) = 4nm + 2n + 2m + 1 = 2(2nm + n + m) + 1，即奇奇数的积还是一个奇数。

习题 1.21.证明：如果一个整数 n 能同时被 2 和 3 整除，则它也能被 6 整除。

答案：首先，n 能同时被 2 和 3 整除，则分别有 n = 2k 和 n = 3m。

联立方程组 2k = 3m，得 k = (3/2)m。

因此，n = 2k = (3m/2) × 2 = 3m× (2/2) = 6m，可以被 6 整除。

2.求 10010 的八进制表示。

答案：将 10010 转换为四位一组的二进制数，得 0010 0100。

将 0010 和 0100 分别转换为八进制数，得 2 和 4。

因此，10010 的八进制表示为 24。

3.已知 547a5 是 11 的倍数，求 a 的值。

答案：根据 11 的倍数的规律，将 547a5 中的奇数位数字相加，再将偶数位数字相加，然后将两个和的差求出来： (5 + 7 + a) - (4 + 5) = 13 + a - 9 = a + 4。

因为547a5 是 11 的倍数，所以 a + 4 也必须是 11 的倍数。

1-1．都是命题：1-2设P：明天天气晴朗Q：我们就去郊游则P →Q：如果明天天气晴朗，我们就去郊游1-3根据真值表求公式P → (P∧(Q →R ))的主析取范式。

解表1.15 例1.42真值表则P → (P∧(Q →R )) ⇔ (﹁P∧Q∧R )∨(﹁P∧Q∧﹁R )∨(﹁P∧﹁Q∧R )∨⌝(﹁P∧Q∧﹁R )∨(P∧﹁Q∧R )∨(P∧﹁Q∧﹁R )∨(P∧Q∧R ) ■由于任意一组命题变元P1, P2, …, P n的真值指派和它的极小项之间是一一对应的，故可以对极小项进行编码。

首先需要规定变元在极小项中的排列次序，假设为P1, P2, …, P n，用m表示极小项，若P i出现在极小项中，则编码的第i个位置上的值为1，否则为0。

比如变元P, Q, R（规定次序为P, Q, R）的极小项P∧﹁Q∧﹁R的编码为100，将此极小项记为m100。

若将编码看作是一个二进制数，又可将例中的极小项记为m4。

用此方法，可以简写所求得的给定公式的主析取范式。

P → (P∧(Q →R )) ⇔m0∨m1∨m2∨m3∨m4∨m5∨m7（规定P, Q, R的次序为P, Q, R）公式P → (P∧(Q →R ))的主析取范式。

解P → (P∧(Q →R ))⇔﹁P∨(P∧(﹁Q∨R ))⇔ (﹁P∨P)∧(﹁P∨﹁Q∨R)⇔ (﹁P∨﹁Q∨R )⇔ (﹁P∨﹁Q∨R )1-4试证明(﹁P →Q )∧(P →R )∧(﹁Q∨S ) ⇒S∨R。

证明（1）﹁P →Q P（2）﹁Q∨S P（3）Q →S T, (2), E16（4）﹁P →S T, (1), (3), I13（5）﹁S →P T, (4), E18（6）P →R P（7）﹁S →R T, (5),(6), I13（8）﹁﹁S∨R T, (7),E16（9）S∨R T, (8), E11-5如果迈克有电冰箱，则或者他卖了洗衣机，或者他向别人借了钱。

第4章图论综合练习一、单项选择题1．设L是n阶无向图G上的一条通路，则下面命题为假的是( )．(A) L可以不是简单路径，而是基本路径(B) L可以既是简单路径,又是基本路径(C) L可以既不是简单路径，又不是基本路径(D) L可以是简单路径，而不是基本路径答案：A2．下列定义正确的是( )．(A) 含平行边或环的图称为多重图 (B) 不含平行边或环的图称为简单图(C) 含平行边和环的图称为多重图 (D) 不含平行边和环的图称为简单图答案：D3．以下结论正确是 ( )．(A) 仅有一个孤立结点构成的图是零图(B) 无向完全图K n每个结点的度数是n(C) 有n(n>1)个孤立结点构成的图是平凡图(D) 图中的基本回路都是简单回路答案：D4．下列数组中，不能构成无向图的度数列的数组是( )．(A) (1,1,1,2,3) (B) (1,2,3,4,5) (C) (2,2,2,2,2) (D) (1,3,3,3)答案：B5．下列数组能构成简单图的是( )．(A) (0,1,2,3) (B) (2,3,3,3) (C) (3,3,3,3) (D) (4,2,3,3)答案：C6．无向完全图K3的不同构的生成子图的个数为（）．(A) 6 (B) 5 (C) 4 (D) 3答案：C7．n阶无向完全图K n中的边数为（）．(A)2)1(+nn(B)2)1(-nn(C) n (D)n(n+1)答案：B8．以下命题正确的是( )．(A) n (n1)阶完全图K n都是欧拉图(B) n(n 1)阶完全图K n都是哈密顿图(C) 连通且满足m=n－1的图<V,E>(V=n,E=m)是树(D) n(n5)阶完全图K n都是平面图答案：C10．下列结论不正确是( )．(A) 无向连通图G是欧拉图的充分必要条件是G不含奇数度结点(B) 无向连通图G有欧拉路的充分必要条件是G最多有两个奇数度结点(C) 有向连通图D是欧拉图的充分必要条件是D的每个结点的入度等于出度(D) 有向连通图D有有向欧拉路的充分必要条件是除两个结点外，每个结点的入度等于出度 答案：D11．无向完全图K 4是（ ）．（A ）欧拉图 （B ）哈密顿图 （C ）树 答案：B12．有4个结点的非同构的无向树有 ( )个． (A) 2 (B) 3 (C) 4 (D) 5 答案：A13．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树．(A) 1+-n m (B) m n - (C) 1++n m (D) 1+-m n 答案：A14．设G 是有6个结点的完全图，从G 中删去( )条边，则得到树． (A) 6 (B) 9 (C) 10 (D) 15 答案：C二、 填空题1．数组{1，2，3，4，4}是一个能构成无向简单图的度数序列， 此命题的真值是 . 答案：02．无向完全图K 3的所有非同构生成子图有 个． 答案：43．设图G V ,E ，其中V n ,E m ．则图G 是树当且仅当G 是连通的，且m ． 答案：n －14．连通图G 是欧拉图的充分必要条件是 ． 答案：图G 无奇数度结点5．连通无向图G 有6个顶点9条边，从G 中删去 条边才有可能得到G 的一棵生成树T ． 答案：46．无向图G 为欧拉图，当且仅当G 是连通的，且G 中无 结点． 答案：奇数度7．设图>=<E V G ,是简单图，若图中每对结点的度数之和 ，则G 一定是哈密顿图．答案：V ≥8．如图1所示带权图中最小生成树的权是 ．答案：12三、化简解答题1．设无向图G ＝<V ,E >，V ={v 1，v 2，v 3，v 4，v 5，v 6}， E ={( v 1，v 2), ( v 2，v 2), ( v 4，v 5), ( v 3，v 4), ( v 1，v 3),( v 3，v 1), ( v 2，v 4)}． 1 v 2 v 6 v 53 v 4图2•2 23 • 1 • 7 9 2• 8 • 6 图1(1) 画出图G 的图形；(2) 写出结点v 2, v 4，v 6的度数； (3) 判断图G 是简单图还是多重图． 解：(1) 图G 的图形如图5所示．(2) 0)deg(,3)deg(,4)deg(642===v v v ．(3) 图G 是多重图．作图如图2. 2．设图G ＝<V ，E >，其中V ＝{a ,b ,c ,d ,e }, E ={(a ,b ),(b ,c ),(c ,d ), (a ,e )}试作出图G 的图形，并指出图G 是简单图还是多重图？是连通图吗？说明理由. 解：图G 如图8所示．. 图G 中既无环，也无平行边，是简单图． 图G 是连通图．G 中任意两点都连通.所以，图G 有9个结点．作图如图3．四、计算题1．设简单连通无向图G 有12条边，G 中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3．求G 中有多少个结点．试作一个满足该条件的简单无向图．解：设图G 有x 个结点，由握手定理21+22+34+3（x 223）＝122 271821243=-+=x x ＝9 故图G 有9个结点．满足该条件的简单无向图如图4所示2．设图G (如图5表示)是6个结点a ,b ,c , d ,e ,f的图，试求，图G 的最小生成树，并计算它的权．解：构造连通无圈的图，即最小生成树，用克鲁斯克尔算法：第一步： 取ab ＝1；第二步： 取af =4 第三步： 取fe ＝3；第四步： 取ad =9 第五步： 取bc =23如图6．权为1+4+3+9+23=403．一棵树T 有两个2度顶点，1个3度顶点；3个4度顶点， 问它有几片树叶？解：设T 有n 顶点，则有n －1条边．T 中有2个 2度顶点，1个3度顶点，3个4度顶点， 其余n －2－1-3个1度顶点．由握手定理： 2·2+1·3+3·4+ (n －2－1-3)=2(n －1) 解得 n =15．于是T 有15-6=9片树叶五、证明题1．若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的．证：用反证法．设G 中的两个奇数度结点分别为u 和v ．假若u 和v 不连通．即它们之间无任何通路，则G 至少有两个连通分支G 1，G 2，且u 和v 分别属于G 1和G 2，于是G 1和G 2各含有一个奇数度结点．这与握手定理的推论矛盾．因而u 和v 一定是连通的．a b ec d 图3图4b • 23 1c • • a 4 • f 9 3d • •e 图6b •23 1 15 c • 25 •a 4 • f 28 9 16 3 d • 15 • e 图5。

集合论练习题一、选择题1.设B = { {2}, 3, 4, 2},那么下列命题中错误的就是( ).A.{2}∈BB.{2, {2}, 3, 4}⊂BC.{2}⊂BD.{2, {2}}⊂B2.若集合A ={a ,b ,{ 1,2 }},B ={ 1,2},则( ).A.B ⊂ A ,且B ∈AB.B ∈ A ,但B ⊄AC.B ⊂ A ,但B ∉AD.B ⊄ A ,且B ∉A3.设集合A = {1, a },则P (A ) = ( ).A.{{1}, {a }}B.{∅,{1}, {a }}C.{∅,{1}, {a }, {1, a }}D.{{1}, {a }, {1, a }}4、已知A ⊕B ={1,2,3}, A ⊕C ={2,3,4},若2∈ B,则( )A. 1∈CB.2∈CC.3∈CD.4∈C5、 下列选项中错误的就是( )A. ∅⊆∅B. ∅∈∅C. {}∅⊆∅D.{}∅∈∅6、 下列命题中不正确的就是( )A. x ∈{x }-{{x }}B.{}{}{{}}x x x ⊆-C.{}A x x =⋃,则x ∈A 且x A ⊆D. A B A B -=∅⇔=7、 A , B 就是集合,P (A ),P (B )为其幂集,且A B ⋂=∅,则()()P A P B ⋂=( )A. ∅B. {}∅C. {{}}∅D.{,{}}∅∅8、 空集∅的幂集()P ∅的基数就是( )A. 0B.1C.3D.49.设集合A = {1,2,3,4,5,6 }上的二元关系R ={<a , b >⎢a , b ∈A , 且a +b = 8},则R 具有的性质为( ).A.自反的B.对称的C.对称与传递的D.反自反与传递的10、 设集合A ={1 , 2 , 3 , 4}上的二元关系R = {<1 , 1>,<2 , 2>,<2 , 3>,<4 , 4>},S = {<1 , 1>,<2 , 2>,<2 , 3>,<3 , 2>,<4 , 4>},则S就是R的( )闭包.A.自反B.传递C.对称D.以上都不对11、设A={1,2,3,4},下列关系中为等价关系。

离散数学练习题离散数学练习题1、图中度为零的结点称为孤⽴结点。

A. 正确B. 错误正确：【A】2、域是整环。

A. 正确B. 错误正确：【A】3、有限格都是有界格。

A. 正确B. 错误正确：【A】4、连通且不含圈的图称为树。

A. 正确B. 错误正确：【A】5、“如果1+1≠3，则2+2≠4”是真命题。

A. 正确B. 错误正确：【B】6、⽆向图G为欧拉图，则G是连通的。

A. 正确B. 错误正确：【A】7、若A和B都是谓词公式，则(A∧B)、(A∨B)、(A→B)、(A<->B)都是谓词公式。

A. 正确B. 错误8、设A, B, C是命题公式，则AVBV﹁C 也是命题公式。

A. 正确B. 错误正确：【A】9、设〈L，≤〉是格，则格的交∧和并∨运算满⾜等幂律。

A. 正确10、“x+3>1。

”是命题。

A. 正确B. 错误正确：【B】11、半群满⾜交换律。

A. 正确B. 错误正确：【B】12、在任何图中，奇数度的结点数必是偶数。

A. 正确B. 错误正确：【A】13、在格〈L，∨，∧〉中，如果交运算对并运算是可分配的，则并运算对交运算也是可分配的。

A. 正确B. 错误正确：【A】14、完全图Kn没有割集，它的连通性能是最好的。

A. 正确B. 错误15、对任意集合A，都有??A。

A. 正确B. 错误正确：【A】17、强连通图⼀定是单向连通图。

A. 正确B. 错误正确：【A】18、代数系统〈G，°〉为群的条件是存在零元素。

A. 正确B. 错误正确：【B】19、对应⽇常⽣活中的“任意的”，“所有的”，“⼀切的”等词，⽤符号“任意”表⽰。

A. 正确20、如果a是集合A中的元素，则称a属于A，记作a?A。

A. 正确B. 错误正确：【B】21、A,B是集合,P（A），P（B）为其幂集,且,则P(A)∩P(B)为（）A. B.C. D.正确：【B】22、设M={x|f1(x)=0},N={x|f2(x)=0}，则⽅程f1(x)?f2(x)=0的解为（）A. M∩NB. M∪NC. MND. M-N正确：【B】23、设集合A={1，2，3}，下列关系R中不是等价关系的是（）A. R={<1,1>,<2,2>,<3,3>}B. R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}C. R={<1,1>,<2,2>,<3,3>,<1,2>}D.R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>} 正确：【C】24、设是环，则下列说法不正确的是（）A. 是交换群B. 是半群C. *对?是可分配的D. ?对*是可分配的正确：【D】25、平⾯图(如下)的三个⾯的次数分别是（）A. 11，3，4B. 11，3，5C. 12，3，6D. 10，4，3正确：【A】26、下列命题正确的是（）A. {l，2} {{1，2}，{l，2，3}，1}B. {1，2} {1，{l，2}，{l，2，3}，2}C. {1，2} {{1}，{2}，{1，2}}D. {1，2}∈{1，2，{2}，{l，2，3}}正确：【B】27、设D的结点数⼤于1，D=是强连通图，当且仅当（）A. D中⾄少有⼀条通路B. D中⾄少有⼀条回路C. D中有通过每个结点⾄少⼀次的通路D. D中有通过每个结点⾄少⼀次的回路正确：【D】28、下列等价式正确的是（）A. ┐┐AB.C. ┐┐AD.正确：【C】29、设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（）A. PQB. PQC. QPD. Q=P正确：【C】30、设，则有（）A. B.C. D.正确：【C】31、下列各图中既是欧拉图，⼜是汉密尔顿图的是（）A. B.C. D.正确：【C】32、⽆向图G是欧拉图当且仅当G是连通的且（）A. G中各顶点的度数均相等B. G中各顶点的度数之和为偶数C. G中各顶点的度数均为偶数D. G中各顶点的度数均为奇数正确：【C】33、下列式⼦正确的是（）A. （A－B）－C = A－（B∪C）B. A－（B∪C）=（A－B）∪CC. ~（A－B）= ~（B－A）D.正确：【A】34、设有代数系统G=〈A，*〉，其中A是所有命题公式的集合，*为命题公式的合取运算，则G的⼳元是（）A. ⽭盾式B. 重⾔式C. 可满⾜D. 公式p∧q正确：【B】35、设P：天下⼤⾬,Q：他在室内运动,命题“除⾮天下⼤⾬，否则他不在室内运动”可符合化为（）A. ┐P∧QB. ┐P→QC. ┐P→┐QD. P→┐Q正确：【C】36、集合A={1，2，…，10}上的关系R={|x+y=10，x∈A，y ∈A}，则R的性质是（）A. ⾃反的B. 对称的C. 传递的、对称的D. 反⾃反的、传递的正确：【B】37、设集合A={a,b, c}上的关系如下，具有传递性的是（）A. R={,,,}B. R={,}C. R={,,,}D. R={}正确：【D】38、下列等价式不正确的是（）A. B.正确：【A】39、设M（x）：x是⼈；F（x）：x要吃饭。

离散数学 章节练习2范围：谓词逻辑班级：________________ 学号：________________ 姓名： ________________一、单项选择题1. 下列那个公式是永真式： ( )A (p ∧r)∨(p ∧s) ； B. (p ∧⌝p)→qC ⌝∃xB(x)⇔∃x ⌝B(x) D. (p ∨⌝p)→q2. 下列公式中正确的等价式是 ( )A. ⌝∃xA(x)⇔∃x ⌝A(x)B. ⌝∀xA(x)⇔∃x ⌝A(x)C. ∀x ∀yA(x,y)⇔∃y ∀xA(x,y)D.∀x(A(x)∨B(x))⇔∀xA(x)∨∀xB(x)3. “人总是要死的”谓词公式表示为 ( )（论域为全总个体域）M(x)：x 是人；Mortal(x)：x 是要死的。

A 、M(x) →Mortal(x)B 、M(x) ∧Mortal(x)C 、∀x (M(x) →Mortal(x))D 、∃x (M(x) →Mortal(x))4.谓词公式∀x(P(x)∨(∃y)R(y))→Q(x)中的x( )A.只是约束变元。

B. 既是约束变元又是自由变元。

C.既非约束变元又非自由变元。

D. 只是自由变元。

5.当个体域 D={a, b}时，下列与∀xP(x)等值的式子是( )A.P(a)∨P(b)B. p(a)∧P(b)C.P(a)→P(b)D.⌝P(a)→P(b)6. 设个体域是正整数集，则下列公式中真值为真的公式是A. (∀x)(∃y)(x ·y=0)B. (∀x)(∃y)(x ·y=1)C. (∃ x)(∃y)(x ·y=2)D. (∀x)(∀y)(∃z)(x-y=z)7.下列公式中正确的等价式是( )A. ⌝(∃x)A(x)⇔( ∃ x)⌝A(x)B. ⌝(∀x)A(x)⇔( ∃ x)⌝A(x)C. (∀x)(∀y)A(x,y)⇔(∃y)(∀x)A(x,y)D. (∀x)(A(x)∨B(x))⇔(∀x)A(x)∨(∀x)B(x)8.命题逻辑中一组公式H 1，H 2， ···,H n .，C ，存在关系H 1∧H 2∧···∧H n ⇒C 当且仅当H 1∧H 2∧···∧H n →C 是A. 矛盾式B. 永假式C. 可满足式D. 永真式。

离散数学练习题 TTA standardization office【TTA 5AB- TTAK 08- TTA 2C】一、填空题（10分，每空1分，请将本题答案填在原题横线．．．．上！）1、设集合X={0，1，2}，R 是X 上的二元关系，R={<0，0>，<0，2>，<1，2>，<2，0>，<2，1>}，则R 的关系矩阵M R = 。

2、66,Z <⊕>为模6整数加群， 则由2生成的子群<2>= ，右陪集<2>⊕65= 。

3、设A 和B 为有限集，|A|=m ，|B|=n ，则有 个从A 到B 的关系，有 个从A 到B 的函数。

4、无向图G 如下图所示，G 的点连通度κ为 ，边连通度λ为 。

5、在上面无向图中，已给出了一棵生成树T （粗边所示），则树枝d 对应的基本割集是 ，弦b 对应的基本回路是 。

6、令F(x)： x 是整数，G(x)：x 是奇数，则“不存在不是奇数的整数”符号化为 。

7、含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 （用m i 形式表示最小项）。

二、单选题（20分，每题1分，请将本题答案写在下方表格．．．．中！）A 、{}1111,110,10,0B 、{}01,001,000,10C 、{}1101,1001,101,110,D 、{}abc aba ac aa c b ,,,,,2、下列( )组赋值不是命题公式C ()A B →∨⌝的成真赋值。

A 、010B 、011C 、110D 、1013、设A={a ，b ，c ，d}，A 上的等价关系R={<a ，b>，<b ，d>，<d ，a>}∪R -1∪I A ，则对应于R 的A 的划分是（ ）。

A 、{{a ，b}，{c ，d}}B 、{{a ，b ，d}，{c}}C 、{{a}，{b}，{c}，{d}}D 、{{a}，{b ，c}，{d}} 4、二部图3,3K 是( ) 。