离散数学复习题答案一、填空题1. }}{},,{},,{},{{c c b b a a B A =⋃，}}{{c B A =⋂，{)(=A P ∅, {{a , b }}, {{c }}, {{a , b }, {c }}}.2. 27933,3,3. 3. 0)(↓∨q p . 4. {{a , b }, a , b , ∅}， {{a , b }, a , b }，16. 5. 92, 27. 6. 22,2,m mn mn . 7. g , g , g . 8. 1,2,4.9. 32，0，30. 10. ))()(())()((x G x F x x F x G x ⌝∧∃∧→∀. 11. ∅，X ，X . 12. ∈，∈，⊆. 13. {(1,5), (3, 2), (2, 5)}, {(4, 2), (3, 2), (1, 4)}, {(1, 2), (2, 2)}. 14. 12, 144. 15. {1, 3, {1, 2}, {3}}；{{2, 3}, {1}}；{1, 3, {1, 2}, {3}, {2, 3}, {1}}. 16. 0，1，0. 二、选择题1(C); 2(A); 3(D). 4(B); 5(D); 6(C). 7(C); 8(A); 9(D). 10(C); 11(D); 12(D); 13(A). 14(D); 15(B); 1(B); 17(C); 18(A). 三、计算与证明1、证 1）对于任意∈x N ，由于x x x 2=+是偶数，于是R x x ∈),(，因此R 是N 上的自反关系.对于任意∈y x ,N ，若R y x ∈),(，则y x +是偶数，即x y +是偶数，于是R x y ∈),(，因此R 是N 上的对称关系.对于任意∈z y x ,,N ，若R y x ∈),(且R z y ∈),(，则y x +是偶数且z y +是偶数，于是y z y y x z x 2)()(-+++=+是偶数，进而R z x ∈),(，因此R 是N 上的传递关系.综上所述，R 是N 上的等价关系.2）N 关于等价关系R 的所有等价类为,...}6,4,2,0{]0[=R 和,...}7,5,3,1{]1[=R . 3）令⎩⎨⎧=→是奇数是偶数x x x f f ,1,0)(,N N :，显然)}()(,N ,|),{(y f x f y x y x R =∈=.2、解 1） R 的关系图R G 如下：2）(1)由于R b b ∉),(，所以R 不是自反的. (2)由于R a a ∈),(，所以R 不是反自反的.(3)因为R b d ∈),(，而R d b ∉),(，因此R 不是对称的. (4)因R a c c a ∈),(),,(，于是R 不是反对称的.(5)经计算知R c d a d c c b c a c c a b a a a R R ⊆=)},(),,(),,(),,(),,(),,(),,(),,{( ，进而R 是传递的.综上所述，所给R 是传递的.3）R 的关系矩阵⎪⎪⎪⎪⎪⎭⎫⎝⎛=0111011100000111R M . 3、解 命题公式))(())((p q r r q p A →→↔→→=的真值表如下:p , q , r )(r q p →→)(p q r →→A 1, 1, 1 1 1 1 1, 1, 0 0 1 0 1, 0, 1 1 1 1 1, 0, 0 1 1 1 0, 1, 1 1 0 0 0, 1, 0 1 1 1 0, 0, 1 1 1 1 0, 0, 0111由表可知，))(())((p q r r q p A →→↔→→=的主析取范式为).()()()()()(r q p r q p r q p r q p r q p r q p A ⌝∧⌝∧⌝∨∧⌝∧⌝∨⌝∧∧⌝∨⌝∧⌝∧∨∧⌝∧∨∧∧=a b cdA 的主合取范式为)()(r q p r q p A ⌝∨⌝∨∧∨⌝∨⌝=.4、证 不妨设G 的阶数3≥n ，否则结论是显然的. 根据推论1知，63-≤n m . 若G 的任意节点v 的度数均有5)deg(≥v ，由握手定理知n v m v5)deg(2≥=∑.于是m n 52≤，进而652363-⋅≤-≤m n m . 因此30≥m ，与已知矛盾. 所以必存在节点v 使得4)deg(≤v .5、证 (1) 显然，B A A B A ⊆⇔=⋂.(2)可以证明：B A A B B A =⇔-=-.(⇐)当A = B 时，A – B = ∅且B – A = ∅, 于是A B B A -=-.(⇒)假定A B B A -=-，先证明B A ⊆: 对于任意A x ∈，若B x ∉，则B A x -∈，进而A B x -∈，根据差运算定义知B x ∈，与B x ∉矛盾. 所以B x ∈，因此B A ⊆. 同理可证A B ⊆. 故A = B .(3)容易证明：=⇔=-⋃-B A A B B A )()(∅.(⇐)显然.(⇒)(反证)若B ≠ ∅，则存在B x ∈. 分两种情况讨论：若A x ∉，则A B x -∈，由于A AB B A =-⋃-)()(，于是A x ∈，矛盾；若A x ∈，则B A x -∉且A B x -∉, 进而A x ∉，矛盾. 证毕.6、证 1）对于任意x ∈ R , 因为03=-xx 是整数，所以(x , x ) ∈ S ，即S 是R 上的自反关系. 2）对于任意x , y ∈ R , 若(x , y ) ∈ S ，则3y x -是整数，而33yx x y --=-也是整数，于是(y , x ) ∈ S .3）对于任意x , y , z ∈ R , 若(x , y ) ∈ S 且(y , z ) ∈ S ，则3y x -是整数且3zy -是整数. 由于333zy y x z x -+-=-是整数，由此得出(x , z ) ∈ S . 综上所述，知S 是R 上的等价关系.7、证 ==⇔=-B A B B A ∅. (⇐)显然.(⇒)因为B A B A ⋂=-，根据B B A =-得B B B B A ⋂=⋂⋂)(，于是B = ∅，进而A = ∅.8、解 由于R 和S 是对称的，所以S S R R==--11,.(⇐)因为R S S R =，两边取逆得11)()(--=R S S R ，而S R S R R S ==---111)(.所以S R S R =-1)(，因此S R 是对称关系.(⇒)由于S R 对称，所以S R S R =-1)(. 而R S R S S R ==---111)(，因而R S S R =.9、解 (1)等值演算法 A 的主合取范式:))(())((r q p p q r A ∨→→→∨⌝== ))(())((r q p p q r ∨∨⌝→∨⌝∨⌝ = )())((r q p p q r ∨∨⌝∨∨⌝∨⌝⌝ = )()(r q p p q r ∨∨⌝∨⌝∧∧ = r q p ∨∨⌝(由吸收律得到). 于是，A 的主析取范式为))(())((r q p p q r A ∨→→→∨⌝== ∨⌝∧⌝∧∨⌝∧∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝)()()()(r q p r q p r q p r q p)()()(r q p r q p r q p ∧∧∨⌝∧∧∨∧⌝∧.(2)真值表法命题公式))(())((r q p p q r A ∨→→→∨⌝=的真值表如下:由表可知，))(())((r q p p q r A ∨→→→∨⌝=的主合取范式为r q p A ∨∨⌝=.A 的主析取范式为A = ∨⌝∧⌝∧∨⌝∧∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝)()()()(r q p r q p r q p r q p)()()(r q p r q p r q p ∧∧∨⌝∧∧∨∧⌝∧.10、证(反证) 假设G 中不含圈. 设G 有k (k ≥ 1)个连通分支k G G G ,...,,21，其节点个数分别为k n n n ,...,,21，其边数分别为k m m m ,...,,21. 这时，i G 为树，根据树的基本性质有1-=i i n m )1(k i i ≤≤. 进而n k n n m m ki i k i i <-=-==∑∑==)1(11，与已知n m ≥矛盾. 证毕.11、解 R 的关系图如下：, }),(),,(),,(),,(),,(),,(),,{()(a c b d a b c a c c d b b a R s =. }),(),,(),,(),,(),,{()(d a c a c c d b b a R t =.12、解(1)q P(附加) (2))(s r q →→ P (3)s r → T(1)(2)I (4)p P (5) P (6)r q ∨⌝ T(4)(5)I (7)r T(1)(6)I}),(),,(),,(),,(),,(),,(),,{()(d d b b a a c a c c d b b a R r =s q p s r q r q p →⇒→→∨⌝∨⌝),(),()(r q p ∨⌝∨⌝abcd(8)s T(3)(7)I (9)s q → CP13、证 (1)对于任意x ∈ Z , 由于x x x x +=+22, 所以(x , x ) ∈ R , 即R 是自反的. (2)因为(0, 0) ∈ R , 因此R 不是反自反的.(3)对于任意x , y ∈ Z , 若(x , y ) ∈ R , 则y y x x +=+22, 于是x x y y +=+22, 进而(y , x ) ∈ R , 即R 是对称的.(4)因为(2, -3) ∈ R 且(-3, 2) ∈ R ，因此R 不是反对称的.(5)对于任意x , y , z ∈ Z , 若(x , y ) ∈ R 且(y , z ) ∈ R , 则y y x x +=+22且z z y y +=+22，于是z z x x +=+22，所以(x , z ) ∈ R , 即R 是传递的. 综上所述，知R 是自反的、对称的和传递的.14、解 命题公式)())(q p q p A ⌝→↔→⌝=的真值表如下：A )()(q p q p A ⌝∧∨∧=.A 的主合取范式为：)()(q p q p A ∨∧⌝∨=.15、证 将组里的每个人看作节点，两个人是朋友当且仅当对应的节点邻接，于是得到一个n 阶简单无向图G ，进而G 中每节点的度数可能为1,...,2,1,0-n 中一个.当G 中无孤立点时，于是每节点的度数可能为1,...,2,1-n . 由于共有n 个节点，于是必有两节点度数相同.当G 中有孤立点时，这时每节点的度数只可能为2,...,2,1,0-n . 同样由于共有n 个节点，因此必有两节点度数相同.。