1. 證明或推翻下列命題：“設⊕表示集合的對稱差運算，則對于任意集合A和B 成立：P(A)⊕P(B)=P(A)⊕P(C)⇔B=C”。

　　解答與評分標準：

　　命題成立(2分)

　　證明：⊕有消去律，P(A)⊕P(B)=P(A)⊕P(C)⇔P(B)=P(C) (3分)

　　P(B)=P(C)⇔B=C (3分)

　　其他細節(2分)

　　2. 證明或推翻下列命題：“設 R 是從A 到B 的二元關系，則下列兩個條件互為充要條件。條件一：存在C⊆A 且D⊆B”使得R=C×D。條件二：對于A中任意x1,x2 和B 中y1,y2，有(x1Ry1∧x2Ry2)→x1Ry2.”

　　解答與評分標準：

　　命題成立(2 分)。

　　條件一 ⇒ 條件二：x1∈C，y2∈D(3 分)。

　　條件二⇒ 條件一：C=dom(R)，D=ran(R)(3 分)。

　　其他細節(2 分)

　　3. 設 A={1,2,…,10}，定義A 上的二元關系R={|x,y∈A∧x+y=10}，說明R具有哪些性質并說明理由。

　　解答與評分標準：

　　討論 5 種性質(各2 分)。

　　非自反：<1,1>不屬于A。

　　非反自反：<5,5>∈A。

　　對稱：定義。

　　非反對稱：<3,7>,<7,3>∈A 但7 不等于3。

　　非傳遞：<3,7>,<7,3>∈A 但<3,3>不屬于A。

　　3. 比較下列集合的基數大小并給出證明：A×A，P(A)，2→A，A→2.

　　解答與評分標準：

　　|A×A| = |2→A| = |A|2(2 分)，

　　|P(A)| = |A→2| = 2|A|(2 分)。

　　分情況討論：

　　(1) A 為空集：注意A→2={空關系}，

　　|A×A| = |2→A| = 0 < |P(A)| = |A→2| = 1。(1 分)

　　(2) A 為有限集且|A|=1：

　　|A×A| = |2→A| = |A|2 = 1 < 2 = 2|A| = |P(A)| = |A→2| 。(1 分)

　　(3) A 為有限集且|A|=2：

　　|A×A| = |2→A| = |A|2 = 4 = 2|A| = |P(A)| = |A→2| 。(1 分)

　　(4) A 為有限集且|A|=3：

　　|A×A| = |2→A| = |A|2 =9 > 8 = 2|A| = |P(A)| = | A→2| 。(1 分)

　　(5) A 為有限集且|A|>4：

　　|A×A| = |2→A| = |A|2 < 2|A| = |P(A)| = |A→2| 。(1 分)

　　(6) A 為無限集：

　　|A×A| = |2→A| = |A|2 = |A| < 2|A|(康托定理)= |P(A)| = | A→2| (1 分)。

　　注(1)(2)(5)(6)結果相同，可合并。

　　4. 在一種計算機信息檢索的模型中，一個文件是由一些關鍵字組成的，而一個倒排文件是由含有某個關鍵字的所有文件組成的。一次查詢的輸入是一個關鍵字，輸出是這個關鍵字的倒排文件，一次查詢的開銷就是包含這個關鍵字的文件個數。多次查詢就是查詢一個關鍵字序列(其中可能有重復關鍵字)中的每個關鍵字，多次查詢的開銷是各次查詢的開銷之和，其中重復查詢同一個關鍵字的開銷之只計算一次。假設關鍵字和文件的個數都是有限的，試用集合論或圖論的術語來描述這個模型，并給出上述斜體字概念的形式化定義。

　　解答與評分標準：

　　集合論：

　　文件集合 D={d1,d2,…,dn}，關鍵字集合K={k1,k2,…,km}，倒排文件集合

　　K’={k1’,k2’,…,km’ }與關鍵字集合K 一一對應。D 包含于P(K)，K’包含于

　　P(D)，ki 屬于dj 當且僅當dj 屬于ki’(4 分)。查詢是從K 到P(D)的函數

　　Q：K→P(D)，查詢k 是求Q(k)(2 分)，查詢k 的開銷是|Q(k)|(2 分)。

　　多次查詢(s1,s2,…,st)就是求(Q(s1),Q(s2),…,Q(st))，多次查詢的開銷是對不同的si 求|Q(si)|之和(2 分)。

　　圖論：

　　二部圖 G=，D 為文件集合，K 為關鍵字集合，E 為邊集合，(d,k)是E 中的邊當且僅當文件d 含有關鍵字k(4 分)。文件d 的內容就是d的相鄰頂點集合(鄰域)，倒排文件k 的內容就是k 的鄰域，查詢k 就是求k 的鄰域(2 分)，查詢k 的開銷就是k 的度數(2 分)。多次查詢就是求一組關鍵字的鄰域，多次查詢的開銷就是這組關鍵字頂點的度數之和，重復關鍵字只計算一次(2 分)。