电大离散数学证明题参考题

五、证明题1设G是一个n阶无向简单图，n是大于等于3的奇数证明图G与它的补图中的奇数度顶点个数相等 证明：设，则是由n阶无向完全图的边删去E所得到的所以对于任意结点，u在G和中的度数之和等于u在中的度数由于n是大于等于3的奇数，从而的每个结点都是偶数度的（度），于是若在G中是奇数度结点，则它在中也是奇数度结点故图G与它的补图中的奇数度结点个数相等 2设连通图G有k个奇数度的结点，证明在图G中至少要添加条边才能使其成为欧拉图证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图故最少要加条边到图G才能使其成为欧拉图五、证明题 1试证明集合等式：A (BC)=(AB) (AC)证：若xA (BC)，则xA或xBC，即 xA或xB 且 xA或xC即xAB 且 xAC ，即 xT=(AB) (AC)，所以A (BC) (AB) (AC) 反之，若x(AB) (AC)，则xAB 且 xAC， 即xA或xB 且 xA或xC，即xA或xBC，即xA (BC)，所以(AB) (AC) A (BC) 因此A (BC)=(AB) (AC) 2对任意三个集合A, B和C，试证明：若AB = AC，且A，则B = C 证明：设xA，yB，则AB， 因为AB = AC，故 AC，则有yC， 所以B C 设xA，zC，则 AC， 因为AB = AC，故AB，则有zB，所以CB 故得B = C 3、设A，B是任意集合，试证明：若AA=BB，则A=B 许多同学不会做，是不应该的我们看一看证明：设xA，则AA， 因为AA=BB，故BB，则有xB，所以AB 设xB，则BB， 因为AA=BB，故AA，则有xA，所以BA 故得A=B 1试证明命题公式 (P(QR)PQ与（PQ）等价 证：(P(QR)PQ(P(QR)PQ (PQR)P)Q PQ （吸收律） (PQ) （摩根律）2试证明($x)(P(x)R(x)($x)P(x)($x)R(x)分析：前提：($x)(P(x)R(x)， 结论：($x)P(x)($x)R(x) 证明 (1) ($x)(P(x)R(x) P(2) P(a)R(a) ES(1) (存在指定规则)(3) P(a) T(2) （化简） (4) ($x)P(x) EG(3) (存在推广规则)(5) R(a) T(2) （化简）(6) ($x)R(x) EG(5) (存在推广规则)(7) ($x)P(x)($x)R(x) T(4)(6) （合取引入）2设集合A=1, 2, 3, 4，B=2, 4, 6, 8，判断下列关系f：AB是否构成函数，并说明理由(1) f =, , , ； (2) f =, , ；(3) f =, , , 解：(1) f不能构成函数因为A中的元素3在f中没有出现 (2) f不能构成函数 因为A中的元素4在f中没有出现 (3) f可以构成函数 因为f的定义域就是A，且A中的每一个元素都有B中的唯一一个元素与其对应，满足函数定义的条件三、公式翻译题 1请将语句“今天是天晴”翻译成命题公式解：设P：今天是天晴； 则命题公式为： P 问：“今天不是天晴”的命题公式是什么？ 2请将语句“小王去旅游，小李也去旅游”翻译成命题公式 解：设 P：小王去旅游，Q：小李去旅游， 则命题公式为：P Q 注：语句中包含“也”、“且”、“但”等连接词，命题公式要用合取“” 3请将语句“他去旅游，仅当他有时间”翻译成命题公式解：设 P：他去旅游，Q：他有时间， 则命题公式为：P Q 注意：命题公式的翻译还要注意“不可兼或”的表示 例如，教材第164页的例6 “T2次列车5点或6点钟开”怎么翻译成