2015年西南大学离散数学第一次作业.docVIP

《离散数学》第1次作业 一、填空题 1. 若，则()，A到B的2元关系共有()个，A上的2元关系共有()个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则(g)是单射，(g)是满射，(g)是双射. 3. 下列5个命题公式中，是永真式的有(1,2,4)(选择正确答案的番号). (1)； (2)； (3)； (4)； (5). 4. 设D24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元(8)，4的补元(不存在)，6的补元(不存在). 5. 设G是(7, 15)简单平面图，则G一定是(连通)图，且其每个面恰由(3)条边围成，G的面数为(10). 二、单选题 1. 设A, B, C是集合，则下述论断正确的是( C ). (A)若A ( B， B ( C，则A ( C. (B)若A ( B， B ( C，则A ( C. (C)若A ( B， B ( C，则A ( C. (D)若A ( B， B ( C，则A ( C. 2. 设R ( A ( A，S ( A ( A，则下述结论正确的是( A ). (A)若R和S是自反的，则R ( S是自反的. (B)若R和S是对称的，则是对称的. (C)若R和S是反对称的，则是反对称的. (D)若R和S是传递的，则R ( S是传递的. 3.在谓词逻辑中，下列各式中不正确的是(B). (A) (B) (C) (D) 4. 域与整环的关系为(A). (A)整环是域 (B)域是整环 (C)整环不是域 (D) 域不是整环 5.设G是(n, m)图，且G中每个节点的度数不是k就是k + 1，则G中度数为k的节点个数为(D). (A). (B)n(n + 1). (C)nk. (D). 三、设A和B是集合，使下列各式(1)； (2)；(3)成立的充要条件是什么，并给出理由. 证 (1) 显然，. (2)可以证明：. (()当A = B时，A – B = (且B – A = (, 于是. (()假定，先证明: 对于任意，若，则，进而，根据差运算定义知，与矛盾. 所以，因此. 同理可证. 故A = B. (3)容易证明：(. (()显然. (()(反证)若B ( (，则存在. 分两种情况讨论：若，则，由于，于是，矛盾；若，则且, 进而，矛盾. 证毕. 四、设S是实数集合R上的关系，其定义如下 R且是是整数}， 证明: S是R上的等价关系. 证 1. 对于任意x ( R, 因为是整数，所以(x, x) ( S，即S是R上的自反关系. 2. 对于任意x, y ( R, 若(x, y) ( S，则是整数，而也是整数，于是(y, x) ( S. 3. 对于任意x, y, z ( R, 若(x, y) ( S且(y, z) ( S，则是整数且是整数. 由于是整数，由此得出(x, z) ( S. 综上所述，知S是R上的等价关系. 五、求谓词公式的前束范式. 解 = = = = = = = = = . 六、若n个人，每个人恰有3个朋友，则n必为偶数，试证明之. 证 用n个节点代表n个人，两个人是朋友则在相应的两个节点之间连一条无向边，于是得到一个n阶图, 其中每个节点的度数均为3. 由于每个节点度数为3, 根据握手定理知, 其中m为G的边数. 于是n必为偶数. 证毕.