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

　　解答與評分標(biāo)準(zhǔn)：

　　命題成立(2分)

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

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

　　其他細(xì)節(jié)(2分)

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

　　解答與評分標(biāo)準(zhǔn)：

　　命題成立(2 分)。

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

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

　　其他細(xì)節(jié)(2 分)

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

　　解答與評分標(biāo)準(zhǔn)：

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

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

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

　　對稱：定義。

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

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

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

　　解答與評分標(biāo)準(zhǔn)：

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

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

　　分情況討論：

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

　　|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)結(jié)果相同，可合并。

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

　　解答與評分標(biāo)準(zhǔn)：

　　集合論：

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

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

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

　　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 為關(guān)鍵字集合，E 為邊集合，(d,k)是E 中的邊當(dāng)且僅當(dāng)文件d 含有關(guān)鍵字k(4 分)。文件d 的內(nèi)容就是d的相鄰頂點(diǎn)集合(鄰域)，倒排文件k 的內(nèi)容就是k 的鄰域，查詢k 就是求k 的鄰域(2 分)，查詢k 的開銷就是k 的度數(shù)(2 分)。多次查詢就是求一組關(guān)鍵字的鄰域，多次查詢的開銷就是這組關(guān)鍵字頂點(diǎn)的度數(shù)之和，重復(fù)關(guān)鍵字只計(jì)算一次(2 分)。