【正文】 ?Q)?M1?m0∨ m2∨ m3 10．例 5 在邊長為 1 的正方形內(nèi)任意放置九個點，證明其中必存在三個點，使得由它們組成的三角形（可能是退化的）面積不超過 1/8。 (2)由 a*(a*b*a)＝ (a*a)*(b*a)＝ a*b*(a*a)＝ (a*b*a)*a，所以有 a*b*a＝ a。 證明 由題意可知，若 a*b＝ b*a，則必有 a＝ b。 (2)對 A 中任意元 a 和 b，有 a*b*a＝ a。 ? ? ? ? 1 2 3 4 v1 v2 v3 v4 v5 ? ? ? ? ? v1 v2 v3 v4 v5 ? ? ? ? ? 9 / 11 六、證明題 1．試證明：若 R 與 S 是集合 A 上的自反關(guān)系，則 R∩S 也是集合 A 上的自反關(guān)系 ． 證明：設(shè) ?x?A，因為 R 自反，所以 x R x，即 x, x?R； 又因為 S 自反，所以 x R x，即 x, x ?S． 即 x, x?R∩ S 故 R∩ S 自反． 2． 試證明集合等 式 A? (B?C)=(A?B) ? (A?C) ． 證明：設(shè) S= A? (B?C)， T=(A?B) ? (A?C)，若 x∈ S，則 x∈ A 或 x∈ B?C，即 x∈ A 或 x∈ B 且 x∈ A 或 x∈ C． 也即 x∈ A?B 且 x∈ A?C ，即 x∈ T，所以 S?T． 反之，若 x∈ T，則 x∈ A?B 且 x∈ A?C， 即 x∈ A 或 x∈ B 且 x∈ A 或 x∈ C， 也即 x∈ A 或 x∈ B?C，即 x∈ S，所以 T?S． 因此 T=S． 3．試證明集合等 式 A? (B?C)=(A?B) ? (A?C)． 證明：設(shè) S=A∩ (B∪ C)， T=(A∩ B)∪ (A∩ C)， 若 x∈ S，則 x∈ A 且 x∈ B∪ C，即 x∈ A 且 x∈ B 或 x∈ A 且 x∈ C， 也即 x∈ A∩ B 或 x∈ A∩ C ，即 x∈ T，所以 S?T． 反之，若 x∈ T，則 x∈ A∩ B 或 x∈ A∩ C， 即 x∈ A 且 x∈ B 或 x∈ A 且 x∈ C 也即 x∈ A 且 x∈ B∪ C，即 x∈ S，所以 T?S． 因此 T=S． 4．試證明集合等 式 A? (B?C)=(A?B) ? (A?C) ． 證明：設(shè) S= A? (B?C)， T=(A?B) ? (A?C)，若 x∈ S，則 x∈ A 或 x∈ B?C，即 x∈ A 或 x∈ B 且 x∈ A 或 x∈ C． 也即 x∈ A?B 且 x∈ A?C ，即 x∈ T，所以 S?T． 反之，若 x∈ T，則 x∈ A?B 且 x∈ A?C， 即 x∈ A 或 x∈ B 且 x∈ A 或 x∈ C， 也即 x∈ A 或 x∈ B?C，即 x∈ S，所以 T?S． 因此 T=S． 5．試證明（ ?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 6．設(shè) m 是一個取定的正整數(shù)，證明：在任取 m＋ 1 個整數(shù)中，至少有兩個整數(shù)，它們的差是 m 的整數(shù)倍 證明 設(shè) 1a ， 2a ，?， 1?ma 為任取的 m＋ 1 個整數(shù)，用 m去除它們所得余數(shù)只能是 0， 1，?， m－ 1，由抽屜原理可知， 1a ， 2a ，?， 1?ma這 m＋ 1 個整數(shù)中至少存在兩個數(shù) sa 和 ta ，它們被 m 除所得余數(shù)相同，因此 sa 和 ta 的差是 m 的整數(shù)倍。 14．求 P?Q?R 的析取范式，合取范式、 主析取范式，主合取范式． P→（ R∨ Q） ?┐ P∨ (R∨ Q) ? ┐ P∨ Q∨ R （析取、合取、主合取范式） ?(┐ P∧┐ Q∧┐ R)∨ (┐ P∧┐ Q∧ R) ∨ (┐ P∧ Q∧ R) ∨ (P∧┐ Q∧┐ R) ∨ (P∧┐ Q∧ R) ∨ (P∧ Q∧┐ R) ∨ (P∧ Q∧ R) （主析取范式） 15．設(shè)圖 G=V， E， V={ v1， v2， v3， v4， v5}， E={ (v1, v2)， (v1, v3)， (v2, v3)， (v2, v4)， (v3, v4)， (v3, v5)， (v4, v5) }，試 (1) 畫出 G 的圖形表示； (2) 寫出其鄰接矩陣； (3) 求出每個結(jié)點的度數(shù)； (4) 畫出圖 G 的補圖的圖形． （ 1）關(guān)系圖 （ 2）鄰接矩陣 ????????????????0110010110110110110100110 （ 3） deg(v1)=2 deg(v2)=3 deg(v3)=4 deg(v4)=3 deg(v5)=2 （ 4） 補圖 16．設(shè)謂詞公式 ?x(A(x,y)∧ ? zB(x,y, z)) ∧ ? yC(y,z) 試 (1)寫出量詞的轄域 。 五．計算題（每小題 12 分，本題共 36 分） 1．試求出（ P∨ Q）→（ R∨ Q）的析取范式． （ P∨ Q）→（ R∨ Q） ? ┐ (P∨ Q)∨（ R∨ Q） ? (┐ P∧┐ Q)∨（ R∨ Q） ? (┐ P∧┐ Q)∨ R∨ Q（析取范式） 2．設(shè) A={{1}, 1, 2}， B={ 1, {2}}，試計算（ 1）（ A∩ B） （ 2）（ A∪ B） （ 3） A ?（ A∩ B）． （ 1）（ A∩ B） ={1} （ 2）（ A∪ B） ={1, 2, {1}, {2}} （ 3） A?（ A∩ B） ={{1}, 1, 2} 3．圖 G=V, E，其中 V={ a, b, c, d }， E={ (a, b), (a, c) , (a, d), (b, c), (b, d), (c, d)}，對應(yīng)邊的權(quán)值依次為 4 及 5，試 （ 1）畫出 G 的圖形； （ 2）寫出 G 的鄰接矩陣； （ 3）求出 G 權(quán)最小的生成樹及其權(quán)值． （ 1） G 的圖形表示如圖一所示： （ 2）鄰接矩陣：????????????0111101111011110 （ 3）最小的生成樹如圖二中的粗線所示： 權(quán)為： 1+1+3=5 4． 畫一棵帶權(quán)為 1, 2, 2, 3, 4 的 最優(yōu)二叉樹 ,計算它們的權(quán) ． 最優(yōu)二叉樹 如圖三所示 圖三 圖二 ? ? ? ? a b c d 1 1 2 4 5 3 圖一 ? ? ? ? a b c d 1 1 2 4 5 3 ? ? ? ? ? ? ? ? ? 1 2 2 3 3 4 7 5 12 6 / 11 權(quán)為 1?3+2?3+2?2+3?2+4?2=27 5． 求（ P∨ Q）→ R 的析取范式與合取范式． （ P∨ Q）→ R ? ?（ P∨ Q）∨ R ? (?P∧ ?Q)∨ R （析取范式） ? (?P∨ R)∧ (?Q∨ R) （合取范式） 6．設(shè) A={0， 1， 2， 3}， R={x， y|x?A， y?A 且 x+y0}， S={x， y|x?A， y?A 且 x+y?2}，試求 R， S， R?S， S 1， r(R)． R=?, S={0,0,0,1,0,2,1,0,1,1,2,0} R?S=?， S 1= S， r(R)=IA={0,0,1,1,2,2,3,3}． 7．試求出（ P∨ Q）→ R 的析取范式，合取范式，主合取范式． （ P∨ Q）→ R?┐ (P∨ Q)∨ R? (┐ P∧┐ Q)∨