計(jì)算機(jī)問(wèn)題求解：集合及其運(yùn)算

計(jì)算機(jī)問(wèn)題求解

–

論題1-8

集合及其運(yùn)算問(wèn)題1:兩個(gè)集合“相等”究竟是什么意思？關(guān)于集合相等集合“完全由其包含的元素所確定”。因此：兩個(gè)集合相等，就是“兩個(gè)集合所包含的元素完全一樣”。完全一樣如何以嚴(yán)格的數(shù)學(xué)方式表述？與集合包含的關(guān)系對(duì)任意集合A,B,A=Biff.A

B,且B

A基本證明方式（1）直接使用集合包含或相等定義例1：A

B=B

A

B例2：A

B

A

B=A例1，待證結(jié)論：A

B即：對(duì)任何x,xAxB因此：證明過(guò)程如下：

對(duì)任何x,假設(shè)xA

<填入適當(dāng)內(nèi)容>xB

因此：A

B因此：證明過(guò)程如下：

對(duì)任何x,假設(shè)xA

由集合并定義：xAB

由已知條件：AB=BxB

因此：A

B基本證明方式（2）利用運(yùn)算定義作邏輯等值式推演例：A-(B

C)=(A-B)

(A-C)A-(BC)={x|xA,butxB

C}={x|xA,but(xBandxC)}={x|(xA,butxB)and(xA,butxC)}=(A-B)

(A-C)另一種等價(jià)的描述方式：

xA-(BC)(xA)?(x(BC))xA?xB?xC(xA?xB)?(xA?xC)

(x(A-B))?(x(A-C))x((A-B)

(A-C))基本證明方式（3）利用已知恒等式或等式作集合代數(shù)推演例：A

B=A

A-B=

例：A

(A

B)=A例：已知A

B=A

C,證明B=C一個(gè)比較復(fù)雜的代入的例子：利用A

B=A

A

B證明：((A

B

C)

(A

B))-((A

(B-C))

A)=B-AAB=AA-B=:A-B=AB=(AB)(AA)=A(BA)=A(AB)=AA=A-B=AB=A:AB=(AB)(AB)=A(BB)=AE=A(A

B

C)

(A

B)=(A

B)(A

(B-C))

A)=A,so原式左邊=(A

B)-A=B-AA(AB)=(AE)(AB)=A(EB)=AE=AB=?B=(AA)B=A(AB)=A(AC)=C基本證明方式（4）循環(huán)證明一系列邏輯等值式A

B=B

A

B

A

B=A

A-B=

對(duì)于上述等價(jià)命題序列，我們只需要證明：

(1)(2)(3)(4)(1)在以上例子的基礎(chǔ)上，只要再證明：A-B=

A

B=B。注意：A

B=(A

B)

E=(A

B)

(

B

B)=(A

B)

B=B(1)(2)(3)(4)問(wèn)題2：文氏圖是否可以用于關(guān)于集合的數(shù)學(xué)證明？文氏圖與數(shù)學(xué)證明文氏圖不能代替數(shù)學(xué)證明,但可以幫助推測(cè)結(jié)論例子：(1)(A-B)

(A-C)=A充要條件：A

B

C=

證明從圖形得到的猜想(A-B)

(A-C)=A當(dāng)且僅當(dāng)A

B

C=

假設(shè)A

B

C

，即：存在xA

B

C,

則x(A-B),x(A-C),x(A-B)

(A-C),但由已知：(A-B)

(A-C)=A，矛盾。

A

B

C=

根據(jù)相對(duì)補(bǔ)運(yùn)算定義，A-BA,A-CA;假設(shè)(A-B)

(A-C)

A，則(A-B)

(A-C)是A的真子集;則存在x

A,但x(A-B)

(A-C),即x(A-B)且x(A-C),由相對(duì)補(bǔ)運(yùn)算定義，xA

B

C,與已知條件矛盾，

(A-B)

(A-C)=A問(wèn)題3：你是否覺(jué)得有關(guān)集合運(yùn)算的性質(zhì)都“似曾相識(shí)”，你想到過(guò)為什么嗎？邏輯表達(dá)式與集合表達(dá)式如何“對(duì)應(yīng)”？一個(gè)例子美國(guó)的總統(tǒng)大選采用一種非常特別的“選舉人”制度。每個(gè)州的選舉人數(shù)是事先確定的。問(wèn)題：有“平局”的可能嗎？問(wèn)題4：如果一個(gè)問(wèn)題的解可以通過(guò)枚舉有限多個(gè)子集的集合來(lái)得到，這個(gè)問(wèn)題“難”嗎？一個(gè)著名的“難”問(wèn)題–背包問(wèn)題優(yōu)化問(wèn)題簡(jiǎn)化版本優(yōu)化問(wèn)題一般版本另一個(gè)關(guān)于子集的問(wèn)題：精確覆蓋問(wèn)題問(wèn)題的描述:GivenasetAandafinitenumberofA:A1,A2,…Ak,aexactcoverofAwithrespecttotheAi’sisasetS

{A1,A2,…Ak},satisfying:AnytwosetsinSaredisjoint,and

S=AMathematically,wecallSapartitionofA.一個(gè)例子:A={a,b,c,d,e,f,g,h,i,j};A1={a,c,d},A2={a,b,e,f},

A3={b,f,g},A4={d,h,i},A5={a,h,j},A6={e,h},A7={c,i,j},A8={i,j}解是：{A1,A3,A6,A8

}精確覆蓋問(wèn)題的矩陣表示Let|A|=n,andtherearemsubsetsforAi’s,wecanrepresenttheinputofexactcoverproblemasam

nmatrix,witheachrowforaAi.Solution:FindacollectionofrowsofM:r1,r2,…rk,satisfying:ri

rj=0for1i,jk,andr1

r2…rk=1where0=[0000000000]

1=[1111111111]and,isbooleanproduct,is booleansum Knuth’sXAlgorithminput:matrixAInitialization:labeltherowsofA;

M=A;L={};(1)Ifthereisacolumnof0’sinM,return“Nosolution”(2)Otherwise:Choosethecolumncwiththefewest1’s;Choosearowrwitha1incolumnc,L=L{r};Eliminateanyrowrihavingtheproperty:r

ri

0;

Eliminateallcolumnsinwhichrhasa1;Eliminaterowr;IfNorowandcolumnleft,thenoutputL,otherwiserepeat(1)and(2)onresultedM;結(jié)果是:

{A1,A3,A6,A8}問(wèn)題5:你能否用集合模型描述“數(shù)獨(dú)”（Soduku)問(wèn)題?簡(jiǎn)單一點(diǎn)，且考慮3

3的。精確覆蓋問(wèn)題與“數(shù)獨(dú)”Describetheprobleminsuitableform9constraintsforcells9constraintsforcolumns9constraintsforrowsConstructthematrixofcovering27columnsforconstraints27rowsfor“moves