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

1、五、证明题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不含奇数度结点因此只要在每对奇数度结点之间各

2、加一条边，使图G的所有结点的度数变为偶数，成为欧拉图故最少要加条边到图G才能使其成为欧拉图五、证明题 1试证明集合等式：AÈ (BÇC)=(AÈB) Ç (AÈC)证：若xAÈ (BÇC)，则xA或xBÇC，即 xA或xB 且 xA或xC即xAÈB 且 xAÈC ，即 xT=(AÈB) Ç (AÈC)，所以AÈ (BÇC)Í (AÈB) Ç (AÈC) 反之，若x(AÈB) Ç (A&#

3、200;C)，则xAÈB 且 xAÈC， 即xA或xB 且 xA或xC，即xA或xBÇC，即xAÈ (BÇC)，所以(AÈB) Ç (AÈC)Í AÈ (BÇC) 因此AÈ (BÇC)=(AÈB) Ç (AÈC) 2对任意三个集合A, B和C，试证明：若A´B = A´C，且A¹，则B = C 证明：设xÎA，yÎB，则<x，y>ÎA´B， 因为A

4、0;B = A´C，故<x，y>Î A´C，则有yÎC， 所以B Í C 设xÎA，zÎC，则<x，z>Î A´C， 因为A´B = A´C，故<x，z>ÎA´B，则有zÎB，所以CÍB 故得B = C 3、设A，B是任意集合，试证明：若A´A=B´B，则A=B 许多同学不会做，是不应该的我们看一看证明：设xÎA，则<x，x>ÎA´A， 因为A

5、80;A=B´B，故<x，x>ÎB´B，则有xÎB，所以AÍB 设xÎB，则<x，x>ÎB´B， 因为A´A=B´B，故<x，x>ÎA´A，则有xÎA，所以BÍA 故得A=B 1试证明命题公式 (P®(QÚØR)ÙØPÙQ与Ø（PÚØQ）等价 证：(P®(QÚØR)ÙØPÙ

6、QÛ(ØPÚ(QÚØR)ÙØPÙQ Û(ØPÚQÚØR)ÙØP)ÙQ ÛØPÙQ （吸收律） ÛØ(PÚØQ) （摩根律）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)

7、7;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 =<1, 4>, <2, 2,>, <4, 6>, <1, 8>； (2) f =<

8、1, 6>, <3, 4>, <2, 2>；(3) f =<1, 8>, <2, 6>, <3, 4>, <4, 2,> 解：(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 注意：命题公式的翻译还要注意“不可兼或”的表示 例如，教材第1