【文章內容簡介】 ┐ P∨ R∨┐ Q)∧ (┐ Q∨ R∨ P) ∧ (┐ Q∨ R∨┐ P) ? (┐ P∨ Q∨ R)∧ (┐ P∨┐ Q∨ R)∧ (P∨┐ Q∨ R) 8．設 A={{a, b}, 1, 2}， B={ a, b, {1}, 1}，試計算 （ 1）（ A?B） （ 2）（ A∪ B） （ 3） （ A∪ B） ?（ A∩ B） ． （ 1）（ A?B） ={{a, b}, 2} （ 2）（ A∪ B） ={{a, b}, 1, 2, a, b, {1}} （ 3）（ A∪ B） ?（ A∩ B） ={{a, b}, 2, a, b, {1}} 9．圖 G=V, E，其中 V={ a, b, c, d, e}， E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，對應邊的權值依次為 4 及 5，試 （ 1）畫出 G 的圖形； （ 2）寫出 G 的鄰接矩陣； （ 3）求出 G 權最小的生成樹及其權值． （ 1） G 的圖形表示為： （ 2）鄰接矩陣： ????????????????0111110110110011100110110 （ 3）粗線表示最小的生成樹， 7 / 11 權為 7： 10．設謂詞公式 )(),()),(),(( yFzyyRzxyzQyxPx ?????? ，試（ 1）寫出量詞的轄域； （ 2）指出該公式的自由變元和約束變元． （ 1） ?x 量詞的轄域為 )),(),(( zxyzQyxP ?? ， ?z 量詞的轄域為 ),( zxyQ , ?y 量詞的轄域為 ),( zyR ． （ 2）自由變元為 )),(),(( zxyzQyxP ?? 與 )yF 中的 y，以及 ),( zyR 中的 z 約束變元為 x 與 ),( zxyQ 中的 z，以及 ),( zyR 中的 y． 11．設 A={{1},{2},1,2}， B={1,2,{1,2}}，試計算 （ 1）（ A?B）； （ 2）（ A∩ B）； （ 3） A B． （ 1） A?B ={{1},{2}} （ 2） A∩ B ={1,2} （ 3） AB={{1},1， {1},2， {1},{1,2}， {2},1， {2},2， {2},{1,2}， 1,1， 1,2， 1, {1,2}， 2,1， 2,2, 2, {1,2}} 12．設 G=V， E， V={ v1， v2， v3， v4， v5}， E={ (v1,v3)， (v2,v3)， (v2,v4)， (v3,v4)， (v3,v5)， (v4,v5) }，試 （ 1）給出 G 的圖形表示； （ 2）寫出其鄰接矩陣； （ 3）求出每個結點的度數； （ 4）畫出其補圖 的圖形． （ 1） G 的圖形表示為： （ 2）鄰接矩陣： ????????????????0110010110110110110000100 （ 3） v1， v2， v3， v4， v5 結點的度數依次為 1， 2， 4， 3， 2 （ 4）補圖如下： 8 / 11 13．設集合 A={1， 2， 3， 4}， R={x, y|x, y?A； |x?y|=1 或 x?y=0}，試 （ 1）寫出 R 的有序對表示； （ 2）畫出 R 的關系圖； （ 3）說明 R 滿足自反性，不滿足傳遞性． （ 1） R={1,1,2,2,3,3,4,4,1,2,2,1,2,3,3,2,3,4,4,3} （ 2）關系圖為 3）因為 1,1,2,2,3,3,4,4均屬于 R，即 A 的每個元素構成的有序對均在 R 中，故 R 在 A 上是自反的。 因有 2,3與 3,4屬于 R，但 2,4不屬于 R，所以 R 在 A 上不是傳遞的。 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．設圖 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) 求出每個結點的度數； (4) 畫出圖 G 的補圖的圖形． （ 1）關系圖 （ 2）鄰接矩陣 ????????????????0110010110110110110100110 （ 3） deg(v1)=2 deg(v2)=3 deg(v3)=4 deg(v4)=3 deg(v5)=2 （ 4） 補圖 16．設謂詞公式 ?x(A(x,y)∧ ? zB(x,y, z)) ∧ ? yC(y,z) 試 (1)寫出量詞的轄域 。 ?x 量詞的轄域為 (A(x,y)∧ ? zB(x,y, z)), ? z 量詞的轄域為 B(x,y,z), ? y 量詞的轄域為 C(y,z) (2)指出該公式的自由變元和約束變元 . 自由變元為 (A(x,y) ∧ ? zB(x,y, z))中的 y,以及 C(y,z)中的 z. 約束變元為 (A(x,y) ∧ ? zB(x,y, z))中的 x 與 B(x,y,z)中的 z,以及 C(y,z)中的 y。 ? ? ? ? 1 2 3 4 v1 v2 v3 v4 v5 ? ? ? ? ? v1 v2 v3 v4 v5 ? ? ? ? ? 9 / 11 六、證明題 1．試證明：若 R 與 S 是集合 A 上的自反關系，則 R∩S 也是集合 A 上的自反關系 ． 證明：設 ?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) ． 證明：設 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)． 證明：設 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) ． 證明：設 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）