離散數(shù)學(xué)之集合論

離散數(shù)學(xué)之集合論離散數(shù)學(xué)之集合論P(yáng)AGEPAGE141離散數(shù)學(xué)之集合論第二篇集合與關(guān)系集合論是現(xiàn)代各科數(shù)學(xué)的基礎(chǔ)，它是德國(guó)數(shù)學(xué)家康托（GeogCantor,1845~1918)于1874年創(chuàng)立的，1876～1883年康托一系列有關(guān)集合論的文章，對(duì)任意元的集合進(jìn)行了深入的探討，提出了關(guān)于基數(shù)、序數(shù)和良序集等理論，奠定了集合論深厚的基礎(chǔ)，19世紀(jì)90年代后逐漸為數(shù)學(xué)家們采用，成為分析數(shù)學(xué)、代數(shù)和幾何的有力工具。隨著集合論的發(fā)展，以及它與數(shù)學(xué)哲學(xué)密切聯(lián)系所作的討論，在1900年前后出現(xiàn)了各種悖論，使集合的發(fā)展一度陷入僵滯的局面。1904～1908年，策墨羅(Zermelo）列出了第一個(gè)集合論的公理系統(tǒng),它的公理，使數(shù)學(xué)哲學(xué)中產(chǎn)生的一些矛盾基本上得到了統(tǒng)一,在此基礎(chǔ)上以后就逐漸形成了公理化集合論和抽象集合論，使該學(xué)科成為在數(shù)學(xué)中發(fā)展最為迅速的一個(gè)分支?，F(xiàn)在，集合論已經(jīng)成為內(nèi)容充實(shí)、實(shí)用廣泛的一門(mén)學(xué)科,在近代數(shù)學(xué)中占據(jù)重要地位，它的觀點(diǎn)已滲透到古典分析、泛函、概率、函數(shù)論、信息論、排隊(duì)論等現(xiàn)代數(shù)學(xué)各個(gè)分支，正在影響著整個(gè)數(shù)學(xué)科學(xué)。集合論在計(jì)算機(jī)科學(xué)中也具有十分廣泛的應(yīng)用,計(jì)算機(jī)科學(xué)領(lǐng)域中的大多數(shù)基本概念和理論幾乎均采用集合論的有關(guān)術(shù)語(yǔ)來(lái)描述和論證,成為計(jì)算機(jī)科學(xué)工作者必不可少的基礎(chǔ)知識(shí).集合論可作為數(shù)學(xué)學(xué)科的通用語(yǔ)言,一切必要的數(shù)據(jù)結(jié)構(gòu)都可以利用集合這個(gè)原始數(shù)據(jù)結(jié)構(gòu)而構(gòu)造出來(lái),計(jì)算機(jī)科學(xué)家或許也可以利用這種方法。本篇介紹集合論的基礎(chǔ)知識(shí)，主要內(nèi)容包括集合及其運(yùn)算、性質(zhì)、序偶、關(guān)系、映射、函數(shù)、基數(shù)等。第2—1章集合及其運(yùn)算§2-1—1集合的概念及其表示一、集合的概念“集合"是集合論中的一個(gè)原始的概念，因此它不能被精確地定義出來(lái).一般地說(shuō)，把具有某種共同性質(zhì)的許多事物，匯集成一個(gè)整體,就形成一個(gè)集合。構(gòu)成這個(gè)集合的每一個(gè)事物稱為這個(gè)集合的一個(gè)成員(或一個(gè)元素），構(gòu)成集合的這些成員可以是具體東西，也可以是抽象東西。例如：教室內(nèi)的桌椅；圖書(shū)館的藏書(shū)；全國(guó)的高等學(xué)校；自然數(shù)的全體；程序設(shè)計(jì)語(yǔ)言C的基本字符的全體等均分別構(gòu)成一個(gè)集合。通常用大寫(xiě)的英文字母表示集合的名稱;用小寫(xiě)的英文字母表示元素。若元素屬于集合記作,讀作“屬于”.否則，若不屬于，就記為，讀作“不屬于”.一個(gè)集合，若其組成集合的元素個(gè)數(shù)是有限的,則稱作“有限集”，否則就稱作“無(wú)限集”.集合的表示方法有兩種：一種是列舉法又稱窮舉法，它是將集合中的元素全部列出來(lái)，元素之間用逗號(hào)“，”隔開(kāi)，并用花括號(hào)“{｝”在兩邊括起來(lái)，表示這些元素構(gòu)成整體.例2—1—1.1＝｛a,b,c，d｝；＝｛1,2，3，…}；＝｛桌子,臺(tái)燈，鋼筆，計(jì)算機(jī)，掃描儀,打印機(jī)｝;。集合的另一種表示方法叫做謂詞法又叫敘述法,它是利用一項(xiàng)規(guī)則，概括集合中元素的屬性，以便決定某一事物是否屬于該集合的方法。設(shè)為某類(lèi)對(duì)象的一般表示,為關(guān)于的一個(gè)命題,我們用表示“使成立的對(duì)象所組成的集合”,其中豎線“｜”前寫(xiě)的是對(duì)象的一般表示，右邊寫(xiě)出對(duì)象應(yīng)滿足（具有)的屬性。例2—1-1.2全體正奇數(shù)集合表示為，所有偶自然數(shù)集合可表示為其中2｜m表示2能整除m。[0，1］上的所有連續(xù)函數(shù)集合表示為集合的元素也可以是集合。例如，SaSa{q}{1，2}p12q但必須注意:，而,同理，，而。兩個(gè)集合相等是按下述原理定義的。外延性原理:兩個(gè)集合相等，當(dāng)且僅當(dāng)兩個(gè)集合有相同的元素。兩個(gè)集合，相等,記作，兩個(gè)集合不相等，記作。集合中的元素是無(wú)次序的，集合中的元素也是彼此不相同的。例如：。集合中元素可以是任何事物（如例2-1—1。1）。不含任何元素的集合稱為空集，記為Φ。例如，方程的實(shí)根的集合是空集.二、集合與集合間的關(guān)系“集合”、“元素”、元素與集合間的“屬于"關(guān)系是三個(gè)沒(méi)有精確定義的原始概念，對(duì)它們僅給出了直觀的描述，以說(shuō)明它們各自的含義?，F(xiàn)利用這三個(gè)概念定義集合間的相等關(guān)系，集合的包含關(guān)系，集合的子集和冪集等概念。定義2-1—1.1設(shè)，是任意兩個(gè)集合，如果中的每一個(gè)元素都是的元素,則稱是的子集,或包含于內(nèi)，或包含.記作，或。即可等價(jià)地表示為.例2-1—1。3設(shè)N為自然數(shù)集合,Q為一切有理數(shù)組成的集合.R為全體實(shí)數(shù)集合，C為全體復(fù)數(shù)集合，則，.如果不是的子集，則記為（讀作不包含在內(nèi)），顯然，。集合間的包含關(guān)系“”具有下述性質(zhì):2-1-1.自反性;2.傳遞性。證明：采用邏輯演繹的方法證明。⑴P⑵T（1)E⑶US（2）⑷P⑸T（4）E⑹US（5）⑺T(3)（6)I⑻UG（8）⑼T(8）E定義2-1—1。2如果集合的每一元素都屬于集合，而集合中至少有一元素不屬于,則稱為的真子集，記作。即例如：是的真子集；N是Q的真子集，Q是R的真子集;R是C的真子集。注意符號(hào)“∈”和“”在概念上的區(qū)別，“∈”表示元素與集合間的“屬于”關(guān)系，“”表示集合間的“包含”關(guān)系。定理2—1-1.1集合＝的充分必要條件是：且。（外延性原則)證明：必要性，即證：充分性,即證：或#定理2—1-1.2對(duì)于任一集合A，，且空集是唯一的。證明:假設(shè)為假，則至少存在一個(gè)元素x，使且，因?yàn)榭占话魏卧?，所以這是不可能的。設(shè)與都是空集，由上述可知，且,根據(jù)定理2—1—1.1知，所以，空集是唯一的。注意：，P（x）是任一謂詞.例2-1—1.4設(shè)為方程的根組成的集合，則＝。定理2-1—1.1指出了一個(gè)重要原則：要證明兩個(gè)集合相等,即要證明每一個(gè)集合中的任一元素均是另一集合的元素.這種證明是靠邏輯推理理論，而不是靠直觀。證明兩個(gè)集合相等是應(yīng)該掌握的方法。定義2-1-1.3在一定范圍內(nèi)，如果所有集合均為某一集合的子集，則稱該集合為全集，記作E.對(duì)于任一，因，所以，也即恒為真故，為任一謂詞.注意：全集的概念相當(dāng)于論域，只包含與討論有關(guān)的所有對(duì)象，并不一定包含一切對(duì)象與事物。例如：在初等數(shù)論中，全體整數(shù)組成了全集；方程的解集合，在全集為實(shí)數(shù)集時(shí)為空集，而全集為復(fù)數(shù)集時(shí)解集合就不再是空集，此時(shí)解集合為。三、冪集定義2-1—1。4給定集合A，由集合A的所有子集為元素組成的集合，稱為集合A的冪集.記為P（A）（或記為）。即P（A)＝{X|XA｝。例2-1-1.5A={0,1,2｝，則P(A)＝｛Φ,｛0}，｛1｝，｛2},{0，1}，｛0,2},{1，2}，｛0，1,2｝｝；P（Φ)＝{Φ｝；P({a｝）=｛Φ，{a｝}；P(｛Φ})=｛Φ，{Φ｝}.定理2-1-1.3設(shè),則｜P（A）|＝。其中:|P(A）|表示集合P（A）中元素的個(gè)數(shù)。證明：集合A的m(m=0,1，2,…，n）個(gè)元素組成的子集個(gè)數(shù)為從n個(gè)元素中取m個(gè)元素的組合數(shù)，即，故P(A)的元素個(gè)數(shù)為：|P(A)｜＝根據(jù)二項(xiàng)式定理令x=y=1得故｜P（A)|＝。四、集合的數(shù)碼表示在中學(xué)學(xué)習(xí)集合時(shí),特別強(qiáng)調(diào)了集合中元素的無(wú)序性，但是，為了用計(jì)算機(jī)表示集合及其冪集，需要對(duì)集合中元素規(guī)定次序，即給集合中元素附上排列指標(biāo),以指明一個(gè)元素關(guān)于集合中其他元素的位置。如A2=｛計(jì)算機(jī)，打印機(jī)｝是二個(gè)元素的集合，令“計(jì)算機(jī)"為集合A的第一個(gè)元素，“打印機(jī)"為集合A2的第二個(gè)元素。改記為A2=｛x1,x2｝，則P（A2）的四個(gè)元素，可記為，，，，，其中S的下標(biāo),從左到右分別記為第一位,第二位，它們的取值是1還是0由第一個(gè)和第二個(gè)元素是否在該子集中出現(xiàn)來(lái)決定，如果第i個(gè)元素出現(xiàn)在該子集中，那么S下標(biāo)的第i位取值為1，否則取值為0（i=0,1）.即令J=｛00，01,10,11}={i｜i是二位二進(jìn)制數(shù)，00≤i≤11}，則P（A2）＝｛Si|i∈J｝。類(lèi)似地，三個(gè)元素集合A3={x1,x2,x3｝的冪集P（A3)＝｛Si|i∈J,J={i｜i二進(jìn)制數(shù),000≤i≤111｝}，因此,S010=｛x2}，S101={x1,x3}。上述冪集中元素表示法實(shí)際上是一種編碼，可以推廣到n個(gè)元素的集合An的冪集上,P(An)的2n個(gè)元素可以表示為nnnnSi，i∈J=｛i|i是二進(jìn)制數(shù)，00…0≤i≤11…1｝如果，P(A6)的個(gè)元素記為，此時(shí)S的下標(biāo)是十進(jìn)制整數(shù),如何求出是A6的那些元素組成的子集呢？將下標(biāo)轉(zhuǎn)換為二進(jìn)制的整數(shù),不足六位的在左邊補(bǔ)入需要個(gè)數(shù)的零，使之成為六位的二進(jìn)制整數(shù)，由排列的六位二進(jìn)制整數(shù)推斷出,含有那些元素。凡第i位為0，表示xi不在此子集中，凡第i位為1表示xi在此子集中，故,。這種方法可以推廣到一般情況，即將十進(jìn)制整數(shù)轉(zhuǎn)換為二進(jìn)制整數(shù)，在左邊補(bǔ)入需要個(gè)數(shù)的零使之成為n位的二進(jìn)制數(shù),若第i位為0，表示xi不在此子集中，若第i位為1表示xi在此子集中。子集的這種編碼法，不僅給出了一個(gè)子集含那些元素的判別方法，還可以用計(jì)算機(jī)表示集合、存貯集合以供使用.§2-1—2集合的基本運(yùn)算集合的運(yùn)算，就是以集合為對(duì)象，按照確定的規(guī)則得到另外一些新集合的過(guò)程.給定集合A，B,可以通過(guò)集合的并（∪）、交（∩）、相對(duì)補(bǔ)（－）、絕對(duì)補(bǔ)（ˉ）和對(duì)稱差(⊕）等運(yùn)算產(chǎn)生新的集合。一、集合并（∪)運(yùn)算定義2-1-2。1設(shè)A，B為任意兩集合，所有屬于集合A或?qū)儆诩螧的元素組成的集合,稱為集合A和B的并集。記作A∪BABAB并集的文氏（英國(guó)數(shù)學(xué)家JohanWenn(1834～1883））圖例2-1-2.1設(shè)A={1，2，3，4｝,B={2，4，5,6}則A∪B=｛1,2,3，4,5,6}.注意：集合是由互不相同元素組成的，在A∪B中2，4各寫(xiě)一次，不能重寫(xiě)。由集合并運(yùn)算的定義知，并運(yùn)算具有如下性質(zhì)：定理2-1—2.1設(shè)A，B，C為任意三個(gè)集合，則=1\*GB2⑴冪等律A∪A=A;=2\＊GB2⑵交換律A∪B=B∪A;=3\*GB2⑶結(jié)合律(A∪B)∪C=A∪（B∪C）；=4\＊GB2⑷同一律A∪Φ=A;=5\*GB2⑸零律A∪E=E;=6\＊GB2⑹AA∪B，BA∪B；=7\*GB2⑺A∪B=BAB。證明：性質(zhì)=1\*GB2⑴，=2\*GB2⑵,=4\*GB2⑷，=5\＊GB2⑸，=6\＊GB2⑹由定義2—1—2。1立即可以得到。=3\*GB2⑶的證明（A∪B)∪C＝{x｜x∈(A∪B）∪C}={x|（x∈A∪B)∨（x∈B)｝＝{x｜（(x∈A）∨(x∈B）)∨(x∈B）｝=｛x｜(x∈A）∨（（x∈B)∨(x∈C)）｝=｛x|（x∈A）∨(x∈B∪C)}={x｜x∈A∪(B∪C)}=A∪（B∪C）。=7\*GB2⑺的證明:必要性證明所以AB。充分性證明由=6\＊GB2⑹知BA∪B，現(xiàn)證明A∪BB所以有A∪B=B。例2—1-2。2設(shè)AB，CD，則A∪CB∪D證明：＝即A∪CB∪D成立。同理可證。因?yàn)榧系牟⑦\(yùn)算滿足結(jié)合律，對(duì)n個(gè)集合A1,A2，…,An的并集定義為至少屬于A1,A2,…,An之一的那些元素構(gòu)成的集合。通常縮寫(xiě)成。其中N是自然數(shù)集合。一般地,。集合的并運(yùn)算，就是把給定集的那些元素放到一起合并成一個(gè)集合，在這個(gè)合并中相同的元素只要一個(gè)。如設(shè)則。二、集合的交（∩）運(yùn)算定義2—1—2.2設(shè)任意兩個(gè)集合A和B，由集合A和BAB共同元素組成的集合,稱為集合A和B的交集,記作A∩B。.AB交集的文圖例2-1—2。3設(shè)則。例2-1—2.4設(shè)A={X高等學(xué)校的本科學(xué)生｝,B={X高等學(xué)校計(jì)算機(jī)專業(yè)的學(xué)生}，則A∩B=｛X高等學(xué)校計(jì)算機(jī)專業(yè)的本科學(xué)生}例2—1—2。5設(shè)A是所有能被k整除的整數(shù)集合，B是所有能被l整除的整數(shù)集合，則A∩B是所有能被k與l最小公倍數(shù)整除的整數(shù)集合.由集合交運(yùn)算的定義知,集合交運(yùn)算具有如下性質(zhì):定理2-1-2。2設(shè)A，B，C是任意三個(gè)集合，則（1)冪等律A∩A=A；(2）交換律A∩B=B∩A；（3)結(jié)合律(A∩B)∩C=A∩(B∩C)；（4）零律Φ∩A=Φ；（5)同一律E∩A=A；（6)A∩BA，A∩BB；（7）A∩B=AAB。證明：根據(jù)定義2—1-2。2，性質(zhì)(1），(2）,(4),（5)，(6）立即可以得到。性質(zhì)（3)的證明：(A∩B)∩C=｛x|x∈（A∩B)∩C}=｛x｜（x∈A∩B)∧(x∈C)}={x|(（x∈A)∧（x∈B))∧(x∈C)}=｛x｜（x∈A）∧（（x∈B）∧（x∈C)｝={x|（x∈A）∧(x∈B∩C）｝=｛x|x∈A∩(B∩C)｝=A∩(B∩C)性質(zhì)(7）的證明:必要性的證明：即得A∩B=AAB充分性得證明：由性質(zhì)（6）知A∩BA,現(xiàn)證AA∩B采用邏輯演繹推理法（1）P（附加前提)（2）US（1）（3）ABP(4）T(3)E(5)US(4）(6)T（2，5）I(7)T(2，6)I(8)UG(7)(9)T（8）E（10）AA∩BCP若集合A,B沒(méi)有共同的元素，則可記為A∩B=Φ,這時(shí)稱A，B不相交.由集合的交運(yùn)算具有結(jié)合律，同樣可以定義n個(gè)集合A1,A2，…，An的交集,也可以定義集序列A1，A2,…，An,…的交集,分別記為一般地，集合族{Ak｝k∈I中各集的交記成其定義為.若序列A1，A2,…,An,…任意兩集合Ai，Aj()不相交，則稱A1，A2，…，An，…是兩兩不相交的集序列.三、交運(yùn)算與并運(yùn)算之間的聯(lián)系定理2-1—2.3（分配律）設(shè)A,B,C為任意三個(gè)集合，則(1)交運(yùn)算對(duì)并運(yùn)算的分配律(2)并運(yùn)算對(duì)交運(yùn)算的分配律證明：（1）A∩（B∪C）=｛x｜x∈A∩(B∪C)}={x|（x∈A）∧（x∈B∪C）}=｛x|(x∈A)∧(（x∈B）∨(x∈C）)｝={x|(（x∈A)∧（x∈B）)∨（(x∈A)∧（x∈C))｝=｛x|（x∈A∩B)∨(x∈A∩C)｝=｛x|x∈(A∩B）∪（A∩C）}=（A∩B）∪(A∩C）當(dāng)然可以仿照（1)的證明方法證明（2）的成立，現(xiàn)在采用（1）來(lái)證明（2），注意到AA∪B，A∩CA，由（1）可得（A∪B)∩(A∪C)=((A∪B）∩A)∪（(A∪B)∩C)=A∪(A∩C）∪(B∩C)=A∪（B∩C）.同理可以利用(2)證得（1）成立（讀者自行完成)，于是（1）成立(2）的成立。定理2-1—2.4（吸收律）設(shè)A，B為任意兩集合，則（1）A∪（A∩B)=A；（2）A∩(A∪B)=A；證明：由分配律可得(1)A∪（A∩B)=（A∩E)∪(A∩B）=A∩(E∪B）=A∩E=A(2）A∩(A∪B）=(A∪Φ)∩(A∪B）=A∪(Φ∩B）=A∪Φ=A﹟四、集合的補(bǔ)運(yùn)算定義2-1—2。3設(shè)A，B為任意兩集合，由屬于A而不屬于B的一切元素構(gòu)成的集合，稱為A與B的差運(yùn)算（又稱B對(duì)于A的補(bǔ)運(yùn)算,或相對(duì)補(bǔ)),記為A—B，A—B稱為A與B的差集（或B對(duì)于A的補(bǔ)集）.若A=E，對(duì)任意集合B關(guān)于E的補(bǔ)ABAEABAEEA-B例2—1-2.6設(shè)A={1，2，3,4,5｝，B={1，2,4，7，9｝，則A-B={3,5}.例2-1—2。7設(shè)A是素?cái)?shù)集合,B是奇數(shù)集合，則A-B={2}。例2-1—2.8設(shè)E={X高校計(jì)算機(jī)專業(yè)學(xué)生｝,A={X高校校計(jì)算機(jī)專業(yè)本科學(xué)生}，則={X高校計(jì)算機(jī)專業(yè)研究生}。由集合補(bǔ)運(yùn)算的定義知,補(bǔ)(差）集合有如下性質(zhì)定理2—1-2。5設(shè)A,B，C為任意三集合，則（1）對(duì)合律；（2）；（3）；(4）排中律；（5）矛盾律；(6）（De。Morgan定理）=1\*GB3①,=2\*GB3②；（7)=1\*GB3①,=2\*GB3②;（8)；(9)若,當(dāng)且僅當(dāng)=1\*GB3①；=2\*GB3②。證明：由補(bǔ)運(yùn)算的定義立即可得性質(zhì)(1）～（5).（6)的證明:=1\＊GB3①=2\＊GB3②的證法與=1\*GB3①類(lèi)似，請(qǐng)讀者自行證明。（7）的證明：=1\*GB3①;=2\*GB3②。（8）的證明：。（9）的證明：證明=1\*GB3①必要性即;充分性即。證明=2\＊GB3②必要性;充分性。﹟五、集合的對(duì)稱差運(yùn)算定義2-1—2。4設(shè)A，B為任意兩集合，由“屬于A而不EAB屬于B”或“屬于B而不屬于A”的一切元素構(gòu)成的集合，稱為A,B的對(duì)稱差，記作AEAB對(duì)稱差運(yùn)算的性質(zhì)定理2—1-2。6設(shè)A，B,C為任意三集合,則（1）；（2）；（3)；（4）；（5）；（6）交關(guān)于對(duì)稱差的分配律；（7)若，則B=C.證明:由對(duì)稱差的定義立即可得(1）,（2），（3），（4）的證明。(5）的證明所以。（6）的證明（7)的證明從對(duì)稱差定義或文圖容易看出，.§2-1-3集合中元素的計(jì)數(shù)一、兩個(gè)基本原理加法原理：若一個(gè)事件以m種方式出現(xiàn)（這些方式構(gòu)成集合A）,另一個(gè)事件以n種方式出現(xiàn)（這些方式構(gòu)成集合B），這兩個(gè)事件完成一件即能達(dá)到目的（構(gòu)成集合A∪B)，則達(dá)到目的的方式數(shù)為m+n。例2—1—3。1假設(shè)從城市A到城市B有鐵路兩條，公路三條，航線一條，那么按加法原理,從城市A到城市B有2＋3＋1＝6種走法。乘法原理：若一個(gè)事件以m種方式出現(xiàn)（這些方式構(gòu)成集合A）,另一個(gè)事件以n種方式出現(xiàn)（這些方式構(gòu)成集合B）,這兩個(gè)事件同時(shí)完成才能達(dá)到目的（構(gòu)成集合A∩B），則達(dá)到目的的方式數(shù)為mn。例2—1-3.2一位學(xué)生想從圖書(shū)館借離散數(shù)學(xué)和C#語(yǔ)言書(shū)各一本，書(shū)架上有三種不同作者的離散數(shù)學(xué)書(shū),有兩種不同作者的C#語(yǔ)言書(shū)，那么這位學(xué)生共有3×2＝6種不同的選法.二、排列、組合中學(xué)里已學(xué)過(guò)的計(jì)數(shù)公式是排列組合公式。從n個(gè)元素的集合中每次取m個(gè)的排列和組合的公式分別為：，對(duì)排列：若m=n時(shí)稱為全排列，m<n時(shí)稱為選排列。排列和組合的最基本恒等式有:例2—1-3。3將computer的字母全部取出進(jìn)行全排列，其中c不在第一位，r不在末位，問(wèn)共有多少種排法?解:computer字母的全排列數(shù)為，其中c排在第一位的排法共有7!種，r排在末位的排法共有7!,除去這些不合要求的排法，還有8！-（7!＋7!）=30240種，然而這還不是答案,因?yàn)閏在第一位的7！種排法中r可能排至末位的7！中c可能排在第一位,即c在第一位，r在末位的排法被減去了兩次，實(shí)際上應(yīng)該只減一次，故把不應(yīng)該減的加回去才能得到正確的答案。所求的答案為：（種）.這種分析問(wèn)題的方法稱為“多退少補(bǔ)法”，這種思想在“包含排斥原理”中還要用到。例2—1—3。4將1,2,3三個(gè)數(shù)字排成2行3列的矩陣,要求同行和同列上都沒(méi)有相同的數(shù)字，問(wèn)這樣的數(shù)字矩陣有多少?（實(shí)際上這就是集合｛1，2，3｝到自身上的一些雙射或置換，這些雙射不允許一個(gè)元素以自身為像）解：先排矩陣的第一行共有種排法,如果不管題目的要求,第二行也有6種排法,由乘法原理，知共有6×6＝36種矩陣。這些矩陣包含了有一列數(shù)字相同的情況,有兩列因而就有三列數(shù)字相同的情況,按題目要求這些矩陣都應(yīng)該除去,這些矩陣的個(gè)數(shù)可如下計(jì)算：一列數(shù)字相同其余兩列數(shù)字不同的矩陣數(shù)有種；有兩列數(shù)字相同從而就有三列數(shù)字相同的矩陣數(shù)有3！＝6個(gè)，因此所求的矩陣個(gè)數(shù)為.與是從n個(gè)元素中任意取m個(gè)元素(不重復(fù)抽?。┑呐帕信c組合，但是有些實(shí)際問(wèn)題需要在n個(gè)元素中重復(fù)抽取若干個(gè)元素來(lái)排列,如用0,1,2,3,4,5，6，7,8，9這十個(gè)數(shù)字來(lái)編制代碼，，每個(gè)號(hào)碼就可以重復(fù)使用某個(gè)數(shù)字.一般地，從n個(gè)元素的集合中抽取m個(gè)元素,允許重復(fù)的排列數(shù)為：。實(shí)際上可以設(shè)想有m個(gè)位子，每個(gè)位子都可以放上n個(gè)元素中的任一個(gè)，允許mm重復(fù)，由乘法原理即知有n×n×…×n=nm種排法。例2-1-3。5求電子計(jì)算機(jī)中的6位二進(jìn)制數(shù)。解：電子計(jì)算機(jī)中的數(shù)碼第一位數(shù)不能為0,故首位必須為1，后面五位每位都可選0或1,固有種排法,因而6位二進(jìn)制數(shù)有32個(gè)。例2-1-3.6考試時(shí)有25個(gè)正確或錯(cuò)誤的問(wèn)題，學(xué)生也可能不作答，問(wèn)有多少種不同的考試結(jié)果?解:對(duì)每一問(wèn)題的回答有三種情況：正確、錯(cuò)誤和不作答,因而考試結(jié)果共有個(gè)。關(guān)于重復(fù)組合數(shù)的計(jì)算問(wèn)題。先從一個(gè)實(shí)例來(lái)研究它的計(jì)算公式,從{1，2，3}中每次取出兩個(gè)（允許重復(fù)抽?。┑慕M合按自然數(shù)順序?qū)懗鰜?lái)（即枚舉)為:11，12,13，22，23，33(a)現(xiàn)將各種組合分別加上01，就得到12，13,14，23,24,34（b）（b）中的6個(gè)組合恰好是從{1，2，3,4｝中任取兩個(gè)元素不重復(fù)的組合情況。反之從(b）中的組合中分別減去01即得（a）,說(shuō)明(a）與（b）存在1—1對(duì)應(yīng)關(guān)系（雙射)，因而從三個(gè)相異元素中任取兩個(gè)的重復(fù)組合數(shù)可化為從四個(gè)相異元素中任取兩個(gè)不重復(fù)的組合數(shù)來(lái)計(jì)算，即得到。一般地計(jì)算仿上面的討論，即從{1，2，…，n}中任取m個(gè)允許重復(fù)的每一個(gè)組合,將其元素分別加上0,1，2,…，m—1即變成從｛1，2，…，n,n+1,…，n+（m—1）｝中任取m個(gè)不重復(fù)的組合，故。例2—1-3。7求成自然序的四位數(shù)碼個(gè)數(shù).解：四位數(shù)碼是從{0,1，2,3，4，5,6,7，8，9}中選四個(gè)數(shù)字組成,數(shù)字可以重復(fù)使用，由于規(guī)定自然順序,故只有一種排法，因而變?yōu)?0個(gè)相異元素中任取四個(gè)允許重復(fù)的組合問(wèn)題，所求個(gè)數(shù)為。關(guān)于環(huán)狀排列問(wèn)題，由于環(huán)狀排列旋轉(zhuǎn)后仍是同一種排列,故可以令其中任一個(gè)元素固定位置，不讓它移動(dòng)，其余n-1個(gè)元素任意排列，因而n個(gè)相異元素的環(huán)狀排列數(shù)為（n-1)！,它恰好為n個(gè)相異元素的全排列數(shù)n！被n除的結(jié)果，這種想法可以推廣到不盡相異元素的排列情形.例2—1—3.88為朋友圍圓桌而坐，若座位不編號(hào)有多少種坐法？座位編號(hào)又有多少種坐法？座位不編號(hào)為環(huán)狀排列問(wèn)題，有7！=5040種坐法。座位編號(hào)為非環(huán)狀排列問(wèn)題，故有8！=40320種坐法.例2-1—3.95顆紅珠，3顆白珠穿在一個(gè)項(xiàng)鏈上，有多少種方法？解:如果只穿在一條線上就是不盡相異元素的全排列問(wèn)題。排列數(shù)為?，F(xiàn)在項(xiàng)鏈上是環(huán)狀排列問(wèn)題，因而穿法為種。三、容斥原理設(shè)集合A={a1,a2，…，an}，它含有n個(gè)元素，可以說(shuō)集合A的基數(shù)是n,記作CardA=n?；鶖?shù)是表示集合中所含元素多少的量。如果集合A的基數(shù)是n，可記為｜A｜=n，這時(shí)稱A為有窮集，顯然空集的基數(shù)是0,即|Φ|=0。如果A不是有窮集，則稱A為無(wú)窮集。容斥原理也稱包含與排斥原理或逐步淘汰原則,它也是“多退少補(bǔ)”計(jì)數(shù)思想的應(yīng)用。定理2—1-3.1(容斥原理)設(shè)A,B為有限集合，則。證明：=1\＊GB3①當(dāng)A，B不相交，即時(shí)，=2\＊GB3②當(dāng)時(shí)，所以，但是,因此，定理2-1-3。2設(shè)A,B是有限集合，則。證明：例2—1—3.10假設(shè)10名青年中有5名是工人，7名是學(xué)生，其中既是工人又是學(xué)生的青年有3名，問(wèn)既不是工人又不是學(xué)生的青年的有幾名？解：設(shè)該10名青年組成集合Y，｜Y|=10，其中工人集合設(shè)為W，|W|=5;學(xué)生集合設(shè)為S，｜S|=7。|W∩S｜=3,又因?yàn)樗约匆虼耍炔皇枪と擞植皇菍W(xué)生的青年有1人。這個(gè)例子的計(jì)算過(guò)程用到了容斥原理。一般，令有限集A的元素具有m個(gè)不同的性質(zhì)P1，P2,…，Pm。A中具有性質(zhì)Pi的元素組成子集記為Aii=1,2，…，m；Ai∩Aj(i≠j）表示A中同時(shí)具有性質(zhì)Pi和Pj的元素組成的子集；Ai∩Aj∩Ak（i≠j≠k）表示A中同時(shí)具有性質(zhì)Pi,Pj，Pk的元素組成的子集；…;A1∩A2∩…∩Am表示A中同時(shí)具有性質(zhì)P1,P2,…，Pm的元素組成的子集。表示A中不具有性質(zhì)Pi的元素組成的子集。那么包含排斥原理可以敘述為定理2—1—3.3（容斥原理的推廣)A中不具有性質(zhì)P1，P2，…,Pm的元素?cái)?shù)是,注意：上式右邊共項(xiàng)證明：等式左邊是A中不具有性質(zhì)P1，P2，…，Pm的元素?cái)?shù)。下面我們要證明:對(duì)A中的任何元素a，如果它不具有這m條性質(zhì)，那么它對(duì)等式右邊的貢獻(xiàn)是1；如果a至少具有這m條性質(zhì)中的一條，那么它對(duì)等式右邊的貢獻(xiàn)是0。設(shè)a不具有性質(zhì)P1，P2,…,Pm，那么。對(duì)任何整數(shù)i和j，，都有.對(duì)任何整數(shù)i、j和k，,都有，…，。但是，所以在等式右邊的計(jì)數(shù)中它的貢獻(xiàn)是:1–0+0–0+…+（-1)m·0=1。設(shè)a具有這m條性質(zhì)中的k條性質(zhì)，,則a對(duì)｜A｜的貢獻(xiàn)是1；對(duì)的貢獻(xiàn)是；對(duì)的貢獻(xiàn)是；…；對(duì)的貢獻(xiàn)是，所以a對(duì)等式右邊計(jì)數(shù)的總貢獻(xiàn)是：﹟推論A中至少具有m個(gè)性質(zhì)之一的元素個(gè)數(shù)為證明：因?yàn)樗?例2-1-3。11試求不超過(guò)1000的自然數(shù)中能被2或3或5整除的數(shù)的個(gè)數(shù)。解：設(shè)A=｛1，2,…,1000｝，這是研究對(duì)象的集合，在A上定義性質(zhì)P1,P2，P3。對(duì)任意n∈A，若n具有性質(zhì)P1(P2,P3）當(dāng)且僅當(dāng)2｜n(3｜n，5｜n）.令A(yù)i為A中具有性質(zhì)Pi的數(shù)組成的子集，i=1，2，3，則A1={2，4,6，…,1000｝={2k|k=1,2，,500}，A2=｛3,6,9,,999｝=｛3k｜k=1，2,…,[］｝，A3=｛5，10,15，…,1000｝={5k｜k=1，2,…,｝。于是，|A1|==500,｜A2｜==333，|A3｜==200。而;；；。由定理2—1—3。3推論知｜A1∪A2∪A3｜=(500+333+200)—（166+100+66）+33=1033–332+33=734。所以，不超過(guò)1000的自然數(shù)中，至少能被2，3，5之一整除的數(shù)共有734個(gè)。例2-1—3。12某汽車(chē)工廠裝配了三十輛汽車(chē)，可供選擇的設(shè)備是收錄機(jī)，空調(diào)器，防盜器，三十輛汽車(chē)中有15輛汽車(chē)裝有收錄機(jī)，8輛裝有空調(diào)器，8輛裝有防盜器,三種設(shè)備都具有的汽車(chē)有3輛，問(wèn)這三種設(shè)備都沒(méi)有的汽車(chē)有幾輛？解：設(shè)A1，A2,A3分別表示具有收錄機(jī)，空調(diào)器，防盜器的汽車(chē)的集合。由題設(shè)知|A1|=15，｜A2|=8，|A3｜=8，|A1∩A2∩A3｜=3。由定理2-1—3.3推論知，|A1∪A2∪A3|=15+8+8—(|A1∩A2|+|A1∩A3|+|A2∩A3｜)+3=34-（|A1∩A2|+｜A1∩A3|+｜A2∩A3｜）。|A1∩A2|≥｜A1∩A2∩A3｜＝3，｜A1∩A3｜≥｜A1∩A2∩A3｜＝3，｜A2∩A3｜≥｜A1∩A2∩A3|＝3，所以,|A1∪A2∪A3|≤34—（3+3+3)＝25，故,即三種設(shè)備都沒(méi)有的汽車(chē)至少有5輛.第2-2章二元關(guān)系在現(xiàn)實(shí)世界中，事物不是孤立的，事物之間都有聯(lián)系,單值依賴聯(lián)系是事物之間聯(lián)系中比較簡(jiǎn)單的，比如說(shuō)日常生活中事物的成對(duì)出現(xiàn)，而這種成對(duì)出現(xiàn)的事物具有一定的順序，例如,上、下；大、小；左、右；父、子；高、矮等等。通過(guò)這種聯(lián)系,研究事物的運(yùn)動(dòng)規(guī)律或狀態(tài)變化。世界是復(fù)雜的,運(yùn)動(dòng)也是復(fù)雜的，事物之間的聯(lián)系形式是各種各樣的,不僅有單值依賴關(guān)系，更有多值依賴關(guān)系。“關(guān)系”這個(gè)概念就提供了一種描述事物多值依賴的數(shù)學(xué)工具。這樣，集合，映射關(guān)系等概念是描述自然現(xiàn)象及其相互聯(lián)系的有力工具,為建立系統(tǒng)的、技術(shù)過(guò)程的數(shù)學(xué)模型提供了描述工具和研究方法。映射是關(guān)系的一種特例.系統(tǒng)地研究“關(guān)系”這個(gè)概念及其數(shù)學(xué)性質(zhì)，是本章的任務(wù)。本章將通過(guò)笛卡爾積的給出關(guān)系的數(shù)學(xué)定義,特別給出關(guān)系的幾種等價(jià)定義和常用性質(zhì)、二元關(guān)系的運(yùn)算，特別研究了計(jì)算機(jī)科學(xué)中具有重要應(yīng)用的關(guān)系閉包運(yùn)算、等價(jià)關(guān)系和偏序關(guān)系。等價(jià)關(guān)系和偏序關(guān)系不僅在計(jì)算機(jī)科學(xué)中，而且在數(shù)學(xué)中都是極為重要的?！?—2—1集合的笛卡爾積一、序偶定義2—2-1。1由兩個(gè)元素x和y（允許x=y）按一定的順序排列成的二元組叫做有序?qū)?也稱序偶）,記作<x，y〉。其中x是它的第一元素,y是它的第二元素.上述例子可表示為<上，下〉；〈大，小〉；〈左，右>；〈父，子〉；〈高，矮>等.平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)就是有序?qū)Γ纭?,—1>，<—1，1>,〈1，1>，〈2,0〉，…代表著不同的點(diǎn)。一般來(lái)說(shuō)序偶具有以下特點(diǎn)：定義2—2—1.1序偶可以看成是兩個(gè)具有固定次序的客體組成的有序?qū)?，常常用它?lái)表達(dá)兩個(gè)客體之間的關(guān)系，它與一般集合不同的是序偶具有確定的次序。在集合中｛a，b｝={b，a}，但對(duì)序偶<a，b〉≠<b,a>(這里a≠b）.2.兩個(gè)序偶相等，<x,y>=〈u,v〉， 當(dāng)且僅當(dāng)x=u，y=v。3。序偶〈a,b>中兩個(gè)元素不一定來(lái)自同一集合，它們可以代表不同類(lèi)型的事物。如a代表操作碼，b代表地址碼，則序偶<a，b>代表一條單地址指令；當(dāng)然也可以用b代表操作碼，a代表地址碼,則序偶<a，b>也代表一條單地址指令。但上述約定,已經(jīng)確定，序偶的次序就不能再變化了。在實(shí)際問(wèn)題中，有時(shí)會(huì)用到有序3元組,有序4元組,…,有序n元組。定義2—2-1。2一個(gè)有序n元組（n≥3)是一個(gè)序偶,其中第一個(gè)元素是一個(gè)有序n—1元組,第二個(gè)元素是一個(gè)客體。一個(gè)有序n元組記作<x1,x2，…,xn〉，即<x1,x2，…，xn>=<〈x1，x2,…,xn—1〉，xn>.由序偶相等的定義,<〈x，y〉，z>=<〈u,v〉，w>當(dāng)且僅當(dāng)<x，y>=<u，v>,z=w，也即x=u，y=v,z=w。應(yīng)該注意的是：當(dāng)x≠y時(shí),〈x,y，z〉≠〈y,x,z〉?！础磝，y〉,z〉≠<x,〈y，z〉〉,因?yàn)椤磝，<y,z>>不是三元組.<〈x1，x2,…,xn—1>，xn〉=<<y1，y2，…，yn-1〉，yn>(x1=y1)∧（x2=y2）∧(xn—1=yn—1)∧（xn=yn)。二、笛卡爾積定義2-2—1.3設(shè)A，B為任意兩個(gè)集合，則稱集合為A,B的笛卡爾積，記為A×B。即A×B=。注意：2-1—1。A×B與A,B的次序有關(guān),一般地A×B≠B×A，即交換律不成立。2.若AS，BS則都是S的子集,但是.3.對(duì)任意集合A,有。4。笛卡爾積不滿足結(jié)合律，即實(shí)際上，當(dāng)A≠Φ，B≠Φ,C≠Φ時(shí),=｛〈〈a，b>，c>|（a∈A)∧（b∈B）∧（c∈C）｝;=｛<a，<b,c〉>｜(a∈A）∧（b∈B）∧（c∈C）｝按有序?qū)ο嗟鹊亩x知，笛卡爾積的結(jié)合律不成立。根據(jù)笛卡爾積中元素相等的定義，可知，和，是彼此不相等的集合，但是為了方便起見(jiàn)，通常約定一般笛卡爾積從左到右加括號(hào),即。在這個(gè)約定下，省去括號(hào)而簡(jiǎn)寫(xiě)為。例2—2-1。1設(shè)A=｛1,2，3}，B={a，b}，C=｛0},D=Φ，則A×B={〈1，a〉,<1,b>,<2,a>,<2，b〉,〈3,a>，<3,b〉}；B×A=｛<a,1〉,〈a,2>，<a,3>,<b，1>，<b，2〉，<b,3〉｝；A×C=｛<1,0>，〈2,0〉,<3，0>}；C×A=｛<0，1〉,〈0，2>,〈0，3〉};A×D=Φ,B×D=Φ。笛卡爾積運(yùn)算的性質(zhì)定理2-2-1。1設(shè)A，B，C為任意三個(gè)集合，則笛卡爾積運(yùn)算對(duì)集合的并、交、差運(yùn)算分別滿足分配律，即（1）A×（B∪C）=（A×B)∪(A×C)；（2）（A∪B)×C=(A×C）∪（B×C）;(3)A×（B∩C)=(A×B）∩(A×C);（4)(A∩B)×C=（A×C)∩（B×C）；（5）A×（B—C)=（A×B）-(A×C）；（6）（A-B）×C=(A×C）-（B×C)。證明:用命題演算的方法證明。(1）的證明：對(duì)于任意<x，y〉<x，y〉∈A×(B∪C）（x∈A)∧（y∈B∪C）（x∈A）∧((y∈B）∨(y∈C）)((x∈A）∧(y∈B))∨（(x∈A）∧（y∈C)）（(〈x,y〉∈A×B））∨(〈x,y>∈A×C)<x,y〉∈(A×B)∪（A×C)所以，A×（B∪C)=（A×B）∪（A×C)。(2）的證明與（1)類(lèi)似，請(qǐng)讀者自行完成。（3)的證明：對(duì)于任意<x,y〉<x,y>∈A×（B∩C)（x∈A)∧（y∈B∩C)（x∈A)∧（(y∈B）∧（y∈C））((x∈A)∧(y∈B）)∧（(x∈A)∧(y∈C）)((〈x，y>∈A×B)）∧（<x，y〉∈A×C)<x,y〉∈（A×B）∩（A×C）所以，A×（B∩C)=（A×B）∩(A×C)。（4）的證明與（3）類(lèi)似，請(qǐng)讀者自行完成。(5）的證明：對(duì)于任意〈x，y〉〈x，y〉∈A×（B-C)（x∈A）∧(y∈B-C）（x∈A)∧((y∈B）∧（yC））（(x∈A)∧(y∈B))∧((x∈A)∧(yC))((〈x，y〉∈A×B））∧(<x,y〉A(chǔ)×C）〈x，y>∈（A×B)-（A×C)所以，A×(B-C）=（A×B)—(A×C)。（6）的證明與(5）類(lèi)似，請(qǐng)讀者自行完成。﹟定理2-2-1。2設(shè)A，B,C為任意三個(gè)集合，C≠Φ,則（1）AB的充要條件是A×CB×C;（2）AB的充要條件是C×AC×B。證明：（1)的證明：必要性：即證ABA×CB×C任意<x，y〉〈x,y>∈A×C(x∈A）∧（y∈C）（x∈B）∧(y∈C）<x,y>∈B×C所以,A×CB×C。充分性：即證A×CB×CAB,<x,c〉∈A×C〈x，c>∈B×C（x∈B)∧（c∈C），所以,AB.同理可以證明（2）.定理2-2-1。3設(shè)A，B，C，D為四個(gè)非空集合，則當(dāng)且僅當(dāng)。證明:必要性，即證明所以，。充分性,即證明對(duì)于任意所以，。定義2-2—1。4設(shè)A1,A2,…，An是集合（n≥2）,它們的n階笛卡爾積，記作A1×A2×…×An,其中A1×A2×…×An＝{<x1，x2，…,xn>|（x1∈A1)∧（x2∈A2）∧…∧（xn∈An）}當(dāng)A1=A2=…=An時(shí),它們的笛卡爾積簡(jiǎn)記為An.例如:設(shè)A=｛a,b｝,則A3=｛〈a,a，a〉,<a,a,b>,〈a,b,a〉,<a,b，b>,<b,b,b〉,〈b，b,a>，〈b,a，b>，<b，a,a>｝.§2-2-2二元關(guān)系一、二元關(guān)系的基本概念所謂二元關(guān)系就是在集合中兩個(gè)元素之間的某種相關(guān)性。例如A，B，C三人進(jìn)行一種比賽，如果任何兩個(gè)人之間都要比賽一場(chǎng)，那么總共要比賽三場(chǎng)，假設(shè)這三場(chǎng)比賽的結(jié)果是：B勝A,A勝C，B勝C,把這個(gè)結(jié)果記為｛〈B，A>，〈A,C>,〈B,C>｝，其中〈x,y>表示x勝y。它表示了集合｛A,B,C}中元素之間的一種勝負(fù)關(guān)系。再如,A,B，C三個(gè)人和α,β，γ，δ四項(xiàng)工作,已知A可做α和δ工作，B可做δ工作，C可做α和β工作，那么任何工作之間的對(duì)應(yīng)關(guān)系可以記作R=｛<A,α〉,〈A，β〉，<B，δ>，〈C，α〉,〈C,β〉}這是人的集合｛A，B，C}到工作集合｛α，β,γ，δ}之間的關(guān)系。定義2—2—2。1任一序偶的集合確定了一個(gè)二元關(guān)系R，R中任一序偶<x，y>可記作<x，y>∈R或xRy。不在R中的任一序偶<x,y>可記作〈x,y>R或xy.定義2-2—2.2設(shè)A,B為集合，A×B的任意子集所定義的二元關(guān)系R，稱作從A到B的二元關(guān)系當(dāng)A=B時(shí)，R稱作A上的二元關(guān)系。即，。稱為二元關(guān)系R的前域，記為;稱為二元關(guān)系R的值域，記為；R的前域和值域一起稱作R的域，記作FLD=domR∪rangeR從關(guān)系的定義可以看出：domRA,rangeRB。今后把A×B的兩個(gè)平凡子集稱作A×B和Ф分別稱作A到B的全關(guān)系和空關(guān)系，其中。稱為恒等關(guān)系.當(dāng)A=B時(shí)，關(guān)系R是A×B的子集，這時(shí)稱R為在A上的二元關(guān)系。但是我們注意到:RA×B（A∪B)×(A∪B）=Z×Z（這里Z=A∪B）,因此任一關(guān)系總可以限定某一集合上進(jìn)行討論.如果｜A｜=n,那么|A×A｜=n2，A×A的子集有個(gè),每一個(gè)子集代表一個(gè)A上的關(guān)系,所以A上有個(gè)不同的二元關(guān)系。例如A=｛0，1,2｝,則A上可以定義個(gè)不同的關(guān)系。例2—2—2.1設(shè)A={1,2}，B=｛2，3,4},R=｛〈1，2〉，<1，4〉，〈2，2>｝,則domR={1，2}，rangeR={2，4}。即1R2，1R4，2R2，但13，23,24。例2-2-2.2設(shè)R表示實(shí)數(shù)集,,，是R×R的三個(gè)子集,它們所代表的關(guān)系如下：雙曲線在第一、三象限的點(diǎn)的橫坐標(biāo)與縱坐標(biāo)符合關(guān)系R1.圓心在坐標(biāo)原點(diǎn)，半徑為3的圓內(nèi)和圓上的點(diǎn)的橫坐標(biāo)與縱坐標(biāo)符合關(guān)系R2。拋物線上和線的外側(cè)之點(diǎn)的橫坐標(biāo)與縱坐標(biāo)符合關(guān)系R3。例2—2-2。3設(shè)A={2，3,4｝,B=｛2，3，4，5,6｝,R=｛<x,y〉｜x∈A,y∈B，x整除y｝,則R={〈2，2>,<2,4>,〈2，6>，〈3，3〉,〈3,6〉,〈4，4>｝。S=｛〈x，y〉｜x∈A，y∈B，x〉y+2}=Ф。二、二元關(guān)系的表示1。關(guān)系的矩陣表示設(shè)給定兩個(gè)集合和，R為從A到B的二元關(guān)系，則對(duì)應(yīng)于關(guān)系R有一個(gè)關(guān)系矩陣，其中例2-2—2.4設(shè)A=｛1,2,3,4}，寫(xiě)出集合A上大于關(guān)系“>”的關(guān)系矩陣。解：〉=｛<2,1>,<3,1〉,<3，2〉,〈4，1〉，〈4,2>,〈4，3〉｝，故。例2—2-2。3中的R關(guān)系矩陣為2.關(guān)系的圖形表示設(shè),，RA×B。在平面上用“°”或“·”分別標(biāo)出A，B中元素的點(diǎn)(稱為結(jié)點(diǎn))。如果,則自結(jié)點(diǎn)至結(jié)點(diǎn)作一條有向弧，箭頭指向，如果，則結(jié)點(diǎn)與之間沒(méi)有弧線連接，采用這種方法連接起來(lái)的圖稱為R的關(guān)系圖。例如，例2—2-2。3中R的關(guān)系圖為2323423456例2-2-2。5設(shè)A={1，2，3，4｝，RA×A，R=｛〈1,1>,<1,3〉，〈2,3〉,<4,4〉},R的關(guān)系圖為：11423注意：關(guān)系圖中點(diǎn)的位置,變得長(zhǎng)短可以任意。三、關(guān)系的運(yùn)算1．關(guān)系的并、交、補(bǔ)、差、對(duì)稱差和包含運(yùn)算因?yàn)閮蓚€(gè)集合的笛卡爾積的子集是二元關(guān)系,故二元關(guān)系就有并、交、補(bǔ)、差、對(duì)稱差和包含等運(yùn)算。如R，S是集合A上的兩個(gè)二元關(guān)系,<x,y>∈R∪S表示〈x，y〉∈A或〈x，y〉∈S；<x,y〉∈R∩S表示〈x，y>∈A且<x,y>∈S，表示xy,表示且。例2-2—2.6設(shè)A＝{1,2，3，4}，若H=｛〈x,y〉｜是整數(shù)｝,S={〈x,y>|是整數(shù)｝。求H∪S，H∩S,，S－H，H－S，S⊕H.解：H=｛〈1,1〉,<1,3>，<2,2>，〈2,4>,〈3,3〉，<3，1>,<4，4〉,〈4,2>｝；S={〈4,1〉｝.H∪S=｛〈1,1>，〈1，3〉,<2,2〉，<2，4〉，〈3，3〉，<3，1>,<4,4〉,〈4，2〉,〈4,1〉｝;H∩S=Ф；＝A×A－H=｛<1，2>,〈2,1〉，〈2,3〉,<3，2〉,<3,4>，〈4，3>,<1,4>,〈4,1〉}；S－H=S=｛<4，1>｝;H－S=H；S⊕H=H∪S.定理2—2—2。1若R和S是從集合A到集合B的兩個(gè)關(guān)系,則R、S的并、交、補(bǔ)、差仍是A到B的關(guān)系。證明：因?yàn)镽A×B,SA×B，故R∪SA×B,R∩SA×B，=A×B-SA×B，R-S=R∩A×B.2、關(guān)系的復(fù)合運(yùn)算在日常生活中，如果關(guān)系R表示：a是b的兄弟，關(guān)系S表示：b是c的父親，這時(shí)會(huì)得出關(guān)系T：a是c的叔叔或伯伯，稱關(guān)系T是由關(guān)系R和S復(fù)合而得到的新關(guān)系；又如關(guān)系R1表示：a是b的父親,關(guān)系S1表示：b是c的父親，則得出關(guān)系T1：a是c的祖父，關(guān)系T1是由關(guān)系R1和S1復(fù)合而得到的新關(guān)系。定義2-2-2.3設(shè)RA×B，SB×C是兩個(gè)二元關(guān)系，稱A到C的關(guān)系為R與S的復(fù)合關(guān)系，表示為：.從R和S求稱為關(guān)系的合成運(yùn)算.當(dāng)A=B時(shí)，規(guī)定，，…，，（R為自然數(shù)）.例2-2—2.7設(shè)A={a,b｝,B={1,2，3，4},C={5，6,7}，R=｛〈a,1〉，〈a,2>,<b，3>｝，S=｛<2,6>,<3,7>,〈4，5〉｝。則，。R與S的關(guān)系圖如下列點(diǎn)與虛線圖，關(guān)系圖的有向邊為下圖的實(shí)線弧.11a11ab1234567例2-2-2。8設(shè)A=｛1，2,3,4}，A上的關(guān)系R=｛<1,1>，<1，2>，〈2，4>},S={〈1,4〉，〈2,3>，<2,4〉，〈3,2>｝，求，,，。解:={〈1，4〉，<1，3>},=｛〈3,4〉｝,=={<1,1>，〈1，2〉,〈1，4〉｝，。例2-2—2。9設(shè)R，S是自然數(shù)集合N上的兩個(gè)二元關(guān)系，其定義為則.由此可知，，即復(fù)合關(guān)系是不可交換的，但是復(fù)合關(guān)系滿足結(jié)合律。定理2-2-2。2設(shè)，,，則證明:所以,。推論:設(shè)m，n為非負(fù)整數(shù),則,。定理2—2-2。3設(shè),，，則有(1）；（2)；（3）；（4）.證明：（1)的證明，任取所以，。同理可證（2）。（3)的證明，任取所以,。同理可證（4)?，F(xiàn)在討論復(fù)合關(guān)系的關(guān)系矩陣的求法。設(shè)，，，,，，，復(fù)合關(guān)系的關(guān)系矩陣構(gòu)造如下:如果,必然存在使，則中且中，故只要的第i行，的第k列中至少有一個(gè)這樣的j使且，則在的第i行k列位置上記1,否則記0.如此考察，即確定了中的元素。即，其中“∨"表示邏輯加：1∨1＝1，1∨0＝1，0∨1＝1，0∨0＝0?！啊?表示邏輯乘:1∧1＝1,1∧0＝0，0∧1＝0，0∧0＝0。如例2-2-2.7,，則.3、關(guān)系的逆運(yùn)算定義2—2-2.4給定二元關(guān)系，則稱為R的逆關(guān)系，記為。例2—2—2.10設(shè)是自然數(shù)集N上的二元關(guān)系，則關(guān)系R的逆關(guān)系的關(guān)系圖恰好是關(guān)系R的關(guān)系圖中，將有向弧的方向反置；的關(guān)系矩陣恰好是的轉(zhuǎn)置矩陣。關(guān)系逆運(yùn)算的主要性質(zhì)定理2—2—2。4設(shè)R，S都是A到B的二元關(guān)系，則下列各式成立:(1）；（2）;（3)；(4）;(5)；（6）;（7）。證明：（1），故得證。(2），故得證.同理可證（3）.（4)，故得證。（5)由補(bǔ)的定義立即得證。（6)即得證。（7），即得證?；蛘摺＃６ɡ?—2-2。5設(shè)R是A到B的二元關(guān)系，S是B到C的二元關(guān)系，則。證明:，即得證。四、關(guān)系的性質(zhì)通過(guò)上述討論,我們已經(jīng)看到在集合X上可以定義很多不同的關(guān)系，但真正有實(shí)際意義的只是其中的一小部分，它們一般都是有著某些性質(zhì)的關(guān)系，下面我們討論集合X上的二元關(guān)系R的一些特殊性質(zhì)。1、關(guān)系性質(zhì)的概念設(shè)R是X上的二元關(guān)系，R的主要性質(zhì)有以下5種：自反性，對(duì)稱性，傳遞性，反自反性和反對(duì)稱性。定義2-2-2.5設(shè)R為定義在集合X上的二元關(guān)系,(1）如果對(duì)于任意x∈X,都有<x，x>∈R,則稱X上的二元關(guān)系R具有自反性.即R在X上是自反的。(2）如果對(duì)于任意x,y∈X，當(dāng)時(shí)，就有,則稱集合X上的二元關(guān)系R具有對(duì)稱性。即R在X上是對(duì)稱的。（3）如果對(duì)任意，當(dāng)時(shí),就有，則稱R在X上具有傳遞性。即R在X上是傳遞的。（4）如果對(duì)于任意的，都有,則稱集合X上二元關(guān)系R具有反自反性。即R在X上是反自反的。(5）如果對(duì)任意的，當(dāng)必有,則稱R在X上具有反對(duì)稱性.即R在X上是反對(duì)稱的。反對(duì)稱的定義也可以表示為事實(shí)上：2、關(guān)系性質(zhì)舉例例2—2-2.11設(shè)A為任意集合，=1\＊GB3①A上的恒等關(guān)系具有自反性、對(duì)稱性和傳遞性，但不具有反自反性；=2\*GB3②實(shí)數(shù)集合R上的小于等于關(guān)系“”具有自反性、反對(duì)稱性和傳遞性，但不具有稱性;=3\*GB3③平面三角形上的全等關(guān)系“”具有自反性、對(duì)稱性、傳遞性，但不具有反自反性；=4\*GB3④設(shè)A是人的集合,R是A上的二元關(guān)系，，當(dāng)且僅當(dāng)x是y的祖先,顯然祖先關(guān)系R是傳遞的。=5\＊GB3⑤平面三角形上的相似關(guān)系“～"具有對(duì)稱性;例2—2-2。12設(shè)A={1，2｝，A上的關(guān)系R={〈1,2>｝,S=｛<1，1〉,<1,2>}，則R具有反自反性;S既不具有自反性，也不具有反自反性；又如，數(shù)的大于關(guān)系，日常生活中的父子關(guān)系等都是反自反的關(guān)系。例2-2—2.13設(shè)A=｛2,3，5,7},，則R在A上是自反和對(duì)稱的。證明：由于,所以,故R是自反的。又設(shè),如果，即是整數(shù),則也必是整數(shù)，即，因此，R是對(duì)稱的。例2—2—2。14設(shè)A=｛1，2,3}，R1=｛〈1,2>,<2,2>｝,R2=｛〈1，2>｝，R3={〈1，2>,〈2，3〉，<1,3〉,〈2,1〉}，，，則=1\*GB3①R1和R2是傳遞的。=2\＊GB3②對(duì)于R3，因?yàn)?，但?），故不是傳遞的。=3\＊GB3③對(duì)于由于，但故不是自反的,又，而，故不是反自反的,因此既不是自反的也不是反自反的。=4\＊GB3④在A上既是對(duì)稱的又是反對(duì)稱的。例2—2-2.15設(shè)兄弟三人組成一個(gè)集合A=｛a,b，c｝,在A上的兄弟關(guān)系R的性質(zhì)為：性質(zhì)關(guān)系自反性對(duì)稱性傳遞性反自反性反對(duì)稱性兄弟關(guān)系否是否是否注意：兄弟關(guān)系不具有反自反性,是因?yàn)樽约号c自己不構(gòu)成兄弟關(guān)系；兄弟關(guān)系不具有傳遞性，是因?yàn)槿绻?，由?duì)稱性知，但；兄弟關(guān)系不具有反對(duì)稱性，是因?yàn)榍?但。例2-2—2。16設(shè)集合A=｛1，2，3,4}，A上的二元關(guān)系R={<1，1〉,<1,3〉，〈2，2〉,〈3,3〉,<3,1>,〈3,4>,〈4,3>,〈4,4>}，討論R的性質(zhì)。解：性質(zhì)關(guān)系自反性對(duì)稱性傳遞性反自反性反對(duì)稱性R是是否否否注意:關(guān)系R不具有傳遞性，是因?yàn)?，但是。關(guān)系R不具有反自反性，是因?yàn)?關(guān)系R不具有反對(duì)稱性，是因?yàn)?，?3、關(guān)系性質(zhì)在關(guān)系圖及關(guān)系矩陣中的特征R性質(zhì)R表示自反性對(duì)稱性傳遞性反自反性反對(duì)稱性集合表示矩陣表示主對(duì)角線元素全是1矩陣為對(duì)稱矩陣在中1所在位置，在中相應(yīng)位置也為1主對(duì)角線元素全是0如果rij=1且i≠j則rij=0圖表示每個(gè)結(jié)點(diǎn)都有環(huán)如果兩個(gè)結(jié)點(diǎn)之間有邊，一定是一對(duì)方向相反的邊如果結(jié)點(diǎn)xi到xj之間有邊，xj到xk之間有邊,則xi到xk之間也有邊每個(gè)結(jié)點(diǎn)都無(wú)環(huán)如果兩個(gè)結(jié)點(diǎn)之間有邊,一點(diǎn)是一條有向邊傳遞關(guān)系的特征比較復(fù)雜，不易從關(guān)系矩陣和關(guān)系圖中直接判斷。五、關(guān)系的閉包運(yùn)算在§2-2-2的例子告訴我們,集合上的二元關(guān)系可能具有一種或多種性質(zhì),如整數(shù)集上的整除關(guān)系，實(shí)數(shù)集上的“≤”關(guān)系都同時(shí)具有自反性、反對(duì)稱性和傳遞性，但實(shí)數(shù)集上的“〈”關(guān)系就不具有自反性。自然想到能否通過(guò)一定的方法使這個(gè)關(guān)系具有自反性呢？一般來(lái)說(shuō)，是否有方法使給定的關(guān)系具有所希望的性質(zhì)呢？本節(jié)就來(lái)研究這個(gè)問(wèn)題。1、閉包的定義定義2-2—2。6設(shè)R是集合A上的二元關(guān)系，如果有另一個(gè)關(guān)系滿足下列條件:（1)是自反的（或?qū)ΨQ的，或傳遞的），（2），(3）若還有A上的二元關(guān)系也符合條件（1）和（2），則必有，則分別稱為R的自反閉包，對(duì)稱閉包和傳遞閉包，分別記為，,。由閉包定義可知,是包含R且具有自反性或?qū)ΨQ性或傳遞性的最小關(guān)系。2、關(guān)系R的閉包求法定理2—2-2.6設(shè)R是集合A上的二元關(guān)系，則（1）R是自反的當(dāng)且僅當(dāng);（2）R是對(duì)稱的當(dāng)且僅當(dāng)；(3）R是傳遞的當(dāng)且僅當(dāng).證明：（1）必要性證明，若R是自反的，令則是自反的且。對(duì)任意，若是自反的且則有。故就是R的自反閉包，即。充分性的證明，若,則由具有自反性知R是自反關(guān)系。同理可證(2)，（3）。﹟定理2—2-2.7設(shè)R是集合A上的二元關(guān)系,則（1);(2)；（3）證明：（1）令，顯然，，所以，具有自反性.設(shè)包含R且具有自反性的任一關(guān)系,即且，因此,由定義即知.（2）令，顯然,現(xiàn)證具有對(duì)稱性，事實(shí)上：任意設(shè)是包含R且具有對(duì)稱性的關(guān)系，現(xiàn)證，事實(shí)上：對(duì)任意所以，。（3)為證明，=1\＊GB3①證明。對(duì)任意自然數(shù)i用數(shù)學(xué)歸納法證明.當(dāng)i=1時(shí)，由傳遞閉包的定義即知.假設(shè)i=k時(shí)，成立。當(dāng)i=k+1時(shí),即說(shuō)明。由歸納原理知,任意自然數(shù)i，，因此。=2\*GB3②。因?yàn)?，現(xiàn)證明具有傳遞性,對(duì)任意,具有傳遞性,而是包含R具有傳遞性的最小關(guān)系,所以,。由=1\*GB3①和=2\＊GB3②即知。﹟例2—2—2.17設(shè)集合，A上的二元關(guān)系,則;；由于,，一般有故。在計(jì)算時(shí),一般來(lái)說(shuō)是較麻煩的，但是可以發(fā)現(xiàn)有一定的規(guī)律，也即存在著求的簡(jiǎn)單的方法。定理2-2—2.8設(shè)R是集合A上的二元關(guān)系，,則存在正整數(shù)k，使得.證明：。對(duì)任意，若,故存在最小正整數(shù)k使，即存在A的元素序列使。若,則這k個(gè)元素中至少有兩個(gè)相同,即有=1\＊GB3①某個(gè)使，于是有故,且;=2\*GB3②某使，于是有.因此，，,即，而。無(wú)論是=1\＊GB3①還是=2\＊GB3②都與時(shí)k的最小性矛盾，所以.即時(shí)，必有,，故，。﹟例2—2-2.18用關(guān)系矩陣求復(fù)合關(guān)系的方法,求例2。4.1中的。解：，，。于是，故.傳遞閉包的Warshall算法：前面已經(jīng)看到按復(fù)合關(guān)系定義求是麻煩的,即使對(duì)有限集合采用定理2。4。2的方法仍是比較麻煩的，特別當(dāng)有限集合元素比較多時(shí)計(jì)算量是很大的。1962年Warshall提出了一個(gè)求的有效計(jì)算方法：設(shè)R是n個(gè)元素集合上的二元關(guān)系，是R的關(guān)系矩陣，第一步：置新矩陣M，；第二步:置i，；第三步：對(duì)，若M的第j行i列處為1，則對(duì)作如下計(jì)算：將M的第j行第k列元素與第i行第k列元素進(jìn)行邏輯加，然后將結(jié)果送到第j行k列處，即；第四步:；第五步：若，轉(zhuǎn)到第三步,否則停止。Warshall算法為計(jì)算機(jī)解決集合分類(lèi)問(wèn)題奠定了基礎(chǔ)。例2—2-2。19設(shè)A=｛1，2,3,4，5}，R={〈1，1〉,〈1，2〉,<2，4>，<3，5〉，〈4，2>}，用Warshall方法求。解：，，。i=1時(shí)，M的第一列中只有M［1，1]=1，將M的第一行上元素與其本身作邏輯和，然后把結(jié)果送到第一行，得：，。時(shí)，M的第二列中有兩個(gè)1，即，分別將M的第一行和第四行與第二行對(duì)應(yīng)元素作邏輯和，將結(jié)果分別送到第一行和第四行，得。。時(shí)，M的第三列全為0，M不變..時(shí)，M的第四列中有三個(gè)1,即，分別將M的第一行，第二行，第四行與第四行對(duì)應(yīng)元素作邏輯和，將結(jié)果分別送到M的第一、二、四行得。.時(shí)，,將M的第三行與第五行對(duì)應(yīng)元素作邏輯和送到M的第三行，由于這里第五行全為0，故M不變。，這時(shí),停止。即得故。3、閉包的復(fù)合關(guān)系R的自反（對(duì)稱，傳遞）閉包還可以進(jìn)一步復(fù)合而成自反（對(duì)稱，傳遞）等閉包，它們之間有如下定理。定理2-2—2。9設(shè)是集合A上的兩個(gè)二元關(guān)系，且，則（1）；（2)；（3）。證明：（1)，即。（2），,則有即。（3)任意，則存在正整數(shù)s，使得，因此存在，使得，由,則有,即,所以,這說(shuō)明。定理2—2—2。10設(shè)R是集合A上的二元關(guān)系，(1)若R是自反的，則是自反的；（2）若R是對(duì)稱的，則是對(duì)稱的;（3）若R是傳遞的，則是傳遞的。證明：（1)因?yàn)镽是自反的，所以，，由自反閉包和傳遞閉包的定義知，且，因此。故和是自反的。（2）首先證明是對(duì)稱的.，若，即，=1\*GB3①若，由R的對(duì)稱性知，又因?yàn)?，?所以是對(duì)稱的；=2\＊GB3②若,則，由于是自反閉包，所以；由=1\＊GB3①，=2\*GB3②知:若就有，所以是對(duì)稱的。再證明是對(duì)稱的，若，則使得，即存在使得，由R的對(duì)稱性知,,即，所以，說(shuō)明具有對(duì)稱性。（3）,若，=1\＊GB3①若，由R的傳遞性知，即，所以具有傳遞性。=2\*GB3②若，有，即,所以具有傳遞性。=3\*GB3③,有，即,所以具有傳遞性。=4\*GB3④，有，即，所以具有傳遞性。綜上所述，具有傳遞性。#定理2—2-2.11設(shè)X是集合,R是X上的二元關(guān)系,則(1）；(2）；（3）。證明：令表示X上的恒等關(guān)系。（1）（2)(3）因?yàn)?由定理2—2—2。9知，，再由定理2-2—2.10知具有對(duì)稱性，所以,即.§2—2—3等價(jià)關(guān)系與集合的劃分在對(duì)集合的研究中,有時(shí)需要將一個(gè)集合分成若干個(gè)子集加以討論.一、集合的劃分定義2-2-3。1設(shè)集合A，S=｛A1，A2，…,Am｝，其中A1,A2，…，Am都是A的子集，若(1)當(dāng)ij，i，j=1，2,…，m時(shí)，AiAj=；（2）。則稱S為A的一個(gè)劃分（分類(lèi)，分劃）。例如，A=｛a，b,c}，考慮下列子集：P=｛｛a｝，{b,c}｝，Q={｛a,b，c｝}，R={{a}，｛b}，｛c｝｝，S={｛a,b}，｛b,c｝｝，T={{a}，{a,c}｝由定義2-2—3.1知，P,Q,R都是集合A的劃分,而S，T不是集合A的劃分。分劃Q中的元素是由集合A的全部元素組成的一個(gè)分塊（A的子集)，則稱Q為集合A的最小劃分。分劃R是由集合A中每個(gè)元素構(gòu)成一個(gè)單元素分塊（A的子集),組成的分劃，稱R為集合A的最大分劃。需要注意:集合的分劃不是唯一的，但已知一個(gè)集合卻很容易構(gòu)造出一種劃分.定義2-2—3。2設(shè)A=｛A1,A2,…,Am｝與B=｛B1，B2，…,Bn｝是集合X的兩個(gè)不同的劃分，稱S={AiBj（AiA）（BjB）(AiBj,i=1，2,…,m；j=1,2，…,n）｝為A與B的交叉劃分。例如，設(shè)X表示所有生物的集合。A=｛A1,A2｝，其中A1表示所有植物的集合，A2表示所有動(dòng)物的集合，則A是集合X的一種分劃；B={B1,B2｝，其中B1表示史前生物,B2表示史后生物，則B也是集合X的一種劃分。A,B的交叉劃分S=｛A1B1，A1B2,A2B1,A2B2｝，其中A1B1表示史前植物，A1B2表示史后植物,A2B1表示史前動(dòng)物，A2B2表示史后動(dòng)物。定理2—2—3.1設(shè)A=｛A1,A2，…,Am}與B={B1，B2，…,Bn}是集合X的兩個(gè)不同的劃分，則A，B的交叉劃分是集合X的一種劃分。證明：A，B的交叉劃分S={A1?B1,A1?B2，…,A1?Bn，A2?B1,A2?B2，…,A2?Bn，…,Am?B1，Am?B2,…,Am?Bn}（1）S中任意兩個(gè)元素都不相交任取S中兩個(gè)元素Ai?Bh，Aj?Bk,(Ai?Bh）?（Aj?Bk）有三種情況:=1\*GB3①若ij，h=k,因?yàn)锳i?Aj=，所以（Ai?Bh）?（Aj?Bk）=?Bh?Bk=F。=2\*GB3②若i=j，hk，因?yàn)锽h?Bk=，所以(Ai?Bh)?（Aj?Bk)=?Ai?Aj=F。=3\＊GB3③若ij，hk，因?yàn)锳i?Aj=，Bh?Bk=，所以（Ai?Bh）?(Aj?Bk)=?F=F。綜上所述，在交叉劃分中，任取兩元素,其交為(Ai?Bh）?(Aj?Bk)=（2）交叉劃分中所有元素的并等于X(A1?B1）(A1?B2)è…è（A1?Bn）è(A2?B1）è(A2?B2）è…è(A2?Bn）è…è(Am?B1）è（Am?B2）è…è（Am?Bn)=(A1?(B1èB2è…èBn））è（A2?(B1èB2è…èBn)）è…è(Amè（B1èB2è…èBn)）=(A1?X）è（A2?X）è…è（AmèX）=(A1èA2è…èAm）?X=X?X=X。定義2—2-3.3給定集合X的任意兩個(gè)劃分A={A1,A2,…,Am｝與B=｛B1，B2，…，Bn}，若對(duì)每個(gè)Ai均有Bj使得AiBj，則稱分劃A為分劃B的加細(xì)。定理2-2—3。2任何兩種分劃的交叉分劃都是原各分劃的一種加細(xì)。由交叉分劃的定義和集合交的性質(zhì)，容易證明定理成立。二、等價(jià)關(guān)系與等價(jià)類(lèi)定義2—2—3。4設(shè)集合A上的二元關(guān)系R，同時(shí)具有自反性、對(duì)稱性和傳遞性,則稱R是A上的等價(jià)關(guān)系。例2—2-3。1設(shè)Z為整數(shù)集,k是Z中任意固定的正整數(shù),定義Z上的二元關(guān)系R為：任一a，bZ，〈a，b>R的充要條件是a，b被k除余數(shù)相同，即k整除a—b，亦即a-b=kq，其中qZ.即R=｛〈a，b>(a?Z）（c?Z)（q?Z）ù（a-b=kq）}，則R是Z上的等價(jià)關(guān)系.證明：（1）R是Z上自反關(guān)系.a?Z，因?yàn)閍-a=k0，0?Z，所以〈a，a>?R。(2)R是Z上對(duì)稱關(guān)系.如果<a,b>?R，則a-b=kq（q?Z)，故b