6．設連通圖g有k個奇數度的結點，證明在圖g中至少要新增條邊才能使其成為尤拉圖．
證明：由定理3.1.2，任何圖中度數為奇數的結點必是偶數，可知k是偶數．
又根據定理4.1.1的推論，圖g是尤拉圖的充分必要條件是圖g不含奇數度結點．因此只要在每對奇數度結點之間各加一條邊，使圖g的所有結點的度數變為偶數，成為尤拉圖．
故最少要加條邊到圖g才能使其成為尤拉圖．
7．設r是集合a上的對稱關係和傳遞關係，試證明：若對任意aa，存在ba，使得r，則r是等價關係．
證明：已知r是對稱關係和傳遞關係，只需證明r是自反關係．
aa，ba，使得r，因為r是對稱的，故r；
又r是傳遞的，即當r，r r；
由元素a的任意性，知r是自反的．
所以，r是等價關係．
8．若非空集合a上的二元關係r和s是偏序關係，試證明：也是a上的偏序關係．
證明：.①，所以有自反性；
②因為r，s是反對稱的，
所以，rs有反對稱性．
③ ，因為r，s是傳遞的，
所以，有傳遞性．
總之，r是偏序關係．
9．試證明命題公式 (p(qr))pq與（pq）等價．
證明：(p(qr))pq
(p(qr))pq(pqr)pq
(ppq)(qpq)(rpq)
(pq)(pq)(pqr)pq（吸收律）
(pq摩根律）
10．試證明（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)i
（4）（x）p（x） eg(3) （5）r（a） t(2)i
（6）（x）r（x） eg(5) （7）（x）p（x）∧（x）r（x）t(5)(6)i
11．若無向圖g中只有兩個奇數度結點，則這兩個結點一定是連通的．
證明：用反證法．設g中的兩個奇數度結點分別為u和v．假設u和v不連通，即它們之間無任何通路，則g至少有兩個連通分支g1，g2，且u和v分別屬於g1和g2，於是g1和g2各含有乙個奇數度結點．這與定理3.1.
2的推論矛盾．因而u和v一定是連通的．
12．設g是乙個n階無向簡單圖，n是大於等於2的奇數．證明圖g與它的補圖中的奇數度頂點個數相等．
證明：設，．則是由n階無向完全圖的邊刪去e所得到的．所以對於任意結點，u在g和中的度數之和等於u在中的度數．由於n是大於等於2的奇數，從而的每個結點都是偶數度的（度），於是若在g中是奇數度結點，則它在中也是奇數度結點．故圖g與它的補圖中的奇數度結點個數相等．
13．設連通圖g有k個奇數度的結點，證明在圖g中至少要新增條邊才能使其成為尤拉圖．
證明：由定理3.1.2，任何圖中度數為奇數的結點必是偶數，可知k是偶數．
又根據定理4.1.1的推論，圖g是尤拉圖的充分必要條件是圖g不含奇數度結點．因此只要在每對奇數度結點之間各加一條邊，使圖g的所有結點的度數變為偶數，成為尤拉圖．
故最少要加條邊到圖g才能使其成為尤拉圖．
離散數學證明題
證明題1.用等值演演算法證明下列等值式 1 pq p q p q 2 p q p q p q p q 證明 1 pq p q q p p q q p p q q p p q p p q q p q p q p q 2 p q p q p p p q q p q q p q p q 2 構造下列推理的...
離散證明題集錦
一 命題邏輯 例 給出 p q p q 的真值表 解 一般說來，n個命題變元組成的命題公式共有2n種真值指派。定理1 任何兩個重言式的合取或析取，仍然是重言式。證明 設a b為兩個重言式，則a b和a b的真值分別等於t t和t t。定理2 對乙個重言式的同一分量都用任何乙個命題公式置換，所得命題公...
離散數學模擬題及答案
離散數學試題 a捲及答案 一 證明題 10分 1 p q r q r p r r 證明 左端 p q r q p r p q r q p r p q r q p r p q q p r p q p q rt r 置換 r 2 x a x b x xa x xb x 證明 x a x b x x a ...