離散數(shù)學知識點.doc

緒論研究對象：離散量研究方法：解的存在性 解的能行性研究內(nèi)容：數(shù)理邏輯 集合 代數(shù)系統(tǒng) 圖論 離散概率 組合數(shù)學例題1、A、B、C、D四人參加四次長跑，問：“A在B前三次，B在C前三次，C在D前三次，D在A前三次”是否有解，若有求出，否則說明理由。方法一： A A B C D n個元素的環(huán)形排列可拆成n個元素的 B C D A 線性排列D B C D A B D A B CC方法二：集合Sa=X|A在B前 SaSbSc=A B C DSb=X|B在C前 SaSbSd=D A B CSc=X|C在D前 SaScSd=C D A BSd=X|D在A前 SbScSd=B C D A例題2：在邊長為1的正方形中任取五個點，則至少有兩個點的距離2/2?！爸悬c分隔”將邊長為1的正方形分成四個邊長為1/2的小正方形，從中任取五個小點，必有兩個小點來自一個小正方形。例題3：“布魯英序列”-應用旋轉(zhuǎn)鼓的設計，設旋轉(zhuǎn)鼓有8個區(qū)域，旋轉(zhuǎn)一圈可識別三位二進制數(shù)，如何確定磁粉位置。（陰影0，非陰影1） 0111 000 0010001 0111 010 011 1 0 100 101 1 110 111 1思考題：四位二進制 a1 a2 a3 a4例題4：有五位小姐排成一排，所有小姐姓不同，穿的衣服顏色不同，喝不同的飲料，養(yǎng)不同的寵物，吃不同的水果，已知：1.錢小姐穿紅衣服 2.翁小姐養(yǎng)了一只狗3.陳小姐喝茶 4.穿綠衣服的小姐在穿白色衣服小姐的左邊，穿綠衣服的小姐在喝咖啡5.吃西瓜的小姐養(yǎng)鳥 6.穿黃衣服的小姐吃梨7.站中間的小姐喝牛奶 8.趙小姐站最左邊9.吃桔子的小姐站在養(yǎng)貓的小姐旁邊 10.養(yǎng)魚的小姐旁邊小姐吃梨11.吃蘋果的小姐喝香檳 12.江小姐吃香蕉13.趙小姐站在穿藍色衣服小姐旁邊 14.喝開水的小姐站在吃桔子的小姐旁邊問每位小姐怎么站，她們分別養(yǎng)什么寵物，吃什么水果，喝什么飲料，穿什么顏色衣服，姓什么。12345姓趙陳錢江翁吃梨桔子西瓜香蕉蘋果喝開水茶牛奶咖啡香檳顏色黃藍紅綠白寵物貓魚鳥狗例題5：同態(tài)加密R+ f:ax(a1) R* f(x+y)=f(x)*f(y)X f(x)y f(y)x+y f(x+y)例題6:100被2、3、5任意個整除2 5 4 68 31 A=X|被2整除 |A|=100/2=50B=X|被3整除 |B|=100/3=337C=X|被5整除 |C|=100/5=20|AB|=16 |AC|=10|BC|=6 |ABC|=31:|A|-|AB|-|AC|+|ABC|=278:|U|-|ABC|=|U|-(|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|)=26第一章 命題邏輯 求職數(shù)理邏輯（一階） 演算 標準型 等價 謂詞邏輯 證明 推理 應用 類型一、 命題：具有確定真假意義的陳述句（斷言）永T命題：真值為T（1）永F命題：假值為F（0）1+1=10 X3 X的取值有關 二進制 十進制 （T） （F） 費晰邏輯原子命題：不可再拆開的命題復合命題：由原子命題和聯(lián)結詞構成的命題詞：命題的符號表示，用大寫字母表示二、 聯(lián)結詞1. 否定（not）A為命題，若A為T，A為FA:張明是上海人 A：張明不是上海人2. 合取（and）A、 B是命題，AB為T, iff(當且僅當）A、B均為TA B AB AB AB A BF F F F T TF T F T T FT F F T F FT T T T T T3. 析?。╫r） 可兼A、 B是命題，AB為F, iff A、B均為F 或 不可兼 量的估計4. 蘊含命題（if-then）A、 B是命題，AB為F，iff A為T，B為F前提 結論AB：原命題 AB:反命題（否命題）BA：逆命題 BA:逆反（逆否）命題5. 等值詞（iff） A B為T，iff A、B的值相同P：生命息 Q：戰(zhàn)斗止（PQ）(QP) P Q三、 命題公式（合成公式）wff1. 命題變元，常元常元：T、F（僅有兩個）變元：在T、F中取值，用小寫字母表示2. wff的定義一個wff定義遞歸（歸納）如下：基礎i) 命題變元，常元是wff歸納ii) 若A、B是wff,則（A）,(AB),(AB),(AB),(A B)也是wff極小化iii) 有限次使用i）和ii)得到的符號命題是wff 反進P Q (P) (Q)約定：最外層括號可省略優(yōu)先級： 高 低 結合方向：左結合 如(PQ)R若優(yōu)先級，結合方向可確定計算順序時，括號可省略括號是用來改變運算順序的擴展：（1）n個變元的增值表有2n行（指派），可構成22n wff（2）結合律：等值有結合侓A B C (A B) C A (B C)0 0 0 1 0 0 10 0 1 1 1 1 00 1 0 0 1 1 00 1 1 0 0 0 11 0 0 0 1 1 11 0 1 0 0 0 01 1 0 1 0 0 01 1 1 1 1 1 1重言式（永T式）一、基本概念1.指派（解釋）對wffG中全部變元的一組賦值，成為一個指派N個變元的全部指派有2n個，可構成2的2n個wff2.永T式（重言式）在任何指派下為T PP3.永F式（矛盾式）在任何指派下為F PP4.偶然式非永T，亦非永F PQ5.可滿足式至少在一組指派下取值為T PQ,P Q 二、邏輯恒等式1.定義：設A，B是wff,若A B為永T，則稱A與B是邏輯恒等式，記為A B例題：A:PQ B:PQ 求證 A B即求證A B為永T? P Q PQ PQ0 0 1 1 10 1 1 1 11 0 0 1 01 1 1 1 1 所以PQ PQ2.常用恒等式 P93.性質(zhì)（1）.A A,A A為永T 自反性（2）.若A B,則BA 對稱性（3）.若AB,且BC,則AC 傳遞性 4.三大規(guī)則（1）.代入規(guī)則代換實例：設wffG,P1，P2Pn是G中全部命題的變元，A是wff，以A代Pi的全部出現(xiàn)，得到公式G為G的一個代換實例。如 wffG:(PQ)(QR) wffA:SRA代Q的全部出現(xiàn)：G(P(SR)(SR)R)代入規(guī)則：（1）.永T式的任何可代入實例是永T式 （2）.永F式的任何可代入實例是永F式 （3）.可滿足式是任何可代入實例是不確定的例題： wffG: PQ G G PRR RRQ 可滿足式 永T式 RRSS 永F式（2）.重換規(guī)則設wffG，A是G的子公式，B是wff且AB,以B代A的某些出現(xiàn)，得到公式G,則GG例題：wffG:（PQ）(QR)(PQ)化簡，取A:PQ B:PQG1：(PQ)（QR）(PQ) GG1取:A:QR B:QR GG2G2：(PQ)（QR）(PQ) G1G2（PQ）(QR)(PQ) (PQ)（ QR）(PQ)（PQPRQQQR）(PQ)PRQPQQRQR（PPT）QRQR（3）.對偶規(guī)則1.對偶式設wffG中僅含、且不包含和作用于變元在G中，將與互換，T與F互換，得新公式G*,則稱G*為對偶式例題：求wffG:P(PQ)的對偶式解：P（PQ）P(PQ) G*:P(PQ)求（PQ）R的G*（PQ）R(PQ)R(PQ)RPQRG*:（PQ）R步驟：i)消、 ii)利用D-M定侓 iii)寫G*，必要時加括號（2）.對偶規(guī)則設A、B是wff，A*、B*分別為A、B對偶式，若AB,則A*B*如： PQQP PQQP三大規(guī)則規(guī)則對象范圍要求結論代入變元Pi全部出現(xiàn)永F式永T式重換子公式A某些出現(xiàn)ABGG對偶、T、F全部不含、AB則A*B*四、 永真蘊含式1.設A、B是wff，若AB永T，則稱A永真蘊含B，記為ABAB iff AB永為T iff A為T，B必為T（肯定前件）Iff B為F，A必為F（否定后件）2.常用永真蘊含式P10A BPPQ AB永為TPPQPPQTQT3.性質(zhì)（1）AA AA永為T？ AAAAT（2）AB,BA則AB（3）AB,BC則AC4.A與A*關系例： A（P,Q）:PQPQ A*（P,Q）:PQ A*（P,Q）:PQ A（P,Q）:PQA（P1，P2Pn）A* （P1，P2Pn）A（P1，P2Pn）A*（P1，P2Pn）A（P1，P2Pn） A* （P1，P2Pn）A （P1，P2Pn） A*（P1，P2Pn）th1 :AB,A*B* th2:AB,B*A*范式一、基本積（和）1.基本積：變元、變元的否定、合取基本和：變元、變元的否定、析取如： p q 基本積：pq pq pp pqp 基本和: pq pq pp pqp2.性質(zhì)基本積（和）永F（T） Iff變元及其否定同時出現(xiàn)在基本積（和）中3.范式（1）析取范式若wffA，AA1A2Ak（*） Ai是基本積，稱（*）為A的析取范式若wffA，AA1A2Ac（*） Ai是基本積，稱（*）為A的合取范式PS：把其中運算符最少的稱為最簡析取范式例：設wffA:P（QR）求析（合）取范式解：P（QR）P(QR) (PQR) 析取范式 合取范式 基本積：P,Q，R 基本和：PQR二、主析取范式1.極小項及其性質(zhì)（1）Df：若基本積滿足i).每個變元必須出現(xiàn)且進出現(xiàn)一次 ii).變元及其否定不能同時出現(xiàn)則稱該基本積為極小項。 編碼 1 1 1 0 0 1 0 0p q pq pq pq pq0 0 0 0 0 10 1 0 0 1 01 0 0 1 0 01 1 1 0 0 0（2）性質(zhì)1.每個變元的極小項有2n個2.每個極小項僅在變元的一組指派下取值為T，其余(2n)-1組指派下取值為F3.任兩個極小項的合取為永F式4.全部極小項的析取為永T式 2.編碼原變元1 反變元0M0:P1 P2Pn M1:P1Pn-1PnM(2n)-1:P1P2Pn3.主析取范式設wffA，若AA1A2Ak（*） Ai為極小項，則稱（*）為A的主析取范式例：求P(QP)的主析式范式方法一：等值演算（E1 E24）P(QP) P(QP) P QP(PP) QTQT方法二：真值表P Q P(QP) PQPQPQPQ0 0 1 1 M0M1M2M30 1 1 01 0 1 11 1 1 1求（PQ）P （PQ）P PQP P(QT) PT P最簡范式PQPT PQP(Q Q) PQPQPQM2M3(2，3)三、主合取范式 編碼 0 0 0 1 1 0 1 1p q pq pq pq pq0 0 0 1 1 10 1 1 0 1 11 0 1 1 0 11 1 1 1 1 02.編碼原變元0 反變元1極小項：1 1pq 極大項：1 1pq M3M3性質(zhì)4：MiMi注：永T式不存在主合取范式，仍記為T四主合取/主析取范式的計數(shù)問題n個變元的極小項有2n個結論：（1）永F式的主析取范式不存在，仍記為F （2）永T式的主析取范式全部由極小項構成 （3）可滿足式由部分極小項構成 有2（2n）-1個聯(lián)結詞的擴充與歸約已學過的聯(lián)結詞：，聯(lián)結詞的擴充一元：Pf1f2f3f40001110永假1恒等0否定1永真f1:F f2:P f3:p f4:T一元無需擴充二元：PQf1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16000100011100011011010010010011011101100001001010110111110000100101101111擴充： 與非 ：P Q (PQ） 或非 ：P Q （PQ） 異或 ：PQ (PQ)全功能集： 設A是運算符集，若在任一wff中可用A中運算符表示，則稱A為全功能集。 若A中符號最少，則稱A為最小全功能集。歸約 找全功能集： ，是全功能集，但不是全功能集。例證明：是全功能集P(PP)PPTPP(PP)(PP)P(PP)FPP(P(P)P(P)(P(PP)(P(PP)PQ(PQ)(PQ)(PQ)(PQ)PQ(PQ)(PQ)(P)(Q)(PP)(QQ)PQPQ(PQ)PQP(QQ)PQ(PQ)(QP)(PQ)(QP)(PQ)(QP)(PQ)(PQ)推理規(guī)則和證明方法如：H1：PH2：PQC：Q求Q是否為H1H2的有效結論。P(PQ)Q (P(PQ)Q P(PQ)QTQ是P（PQ）的有效結論推理規(guī)則1、 前提引入 P 可在任何時刻引入2、 結論引入 T 若證明過程中，一個或多個wff永真蘊含S，則S可加入證明中3、 邏輯恒等式4、 永真蘊含式如： P Q PQ PQ PQ PQ P Q證明方法1.真值表 H1H2.HnC2.等值演算3.構造性證明 步驟 斷言（真） 結論若H1H2.HnCH1H2.Hn C形如H1H2.HnC的證明即證：H1H2.HnC是永真的H1H2.HnC （H1H2.Hn）C （H1C）（H2C）.（HnC） (H1C)(H2C).(HnC)i使得HiC永真形如H1H2.HnC的證明（H1H2.Hn）C (H1H2.Hn)C H1H2.HnC (H1C)(H2C).(HnC) (H1C)(H2C).(HnC)即證：i有HnC永真 i有HnC形如H1H2.HnAB的證明H1H2.Hn（AB）（H1H2.Hn）A）B （H1H2.HnA）B H1H2.HnAB4. 歸謬法相容性（一致性）： 設命題集合A1，A2，.,Ak，若A1A2.Ak為真，則稱A1Ak 是相容的（或一致的），否則稱為不相容的。 H1H2.HnC （H1H2.Hn）C (H1H2.HnC) 即證：H1H2.HnC為F H1，H2，.,Hn,C不相容計數(shù)問題： 一組前提可得多少個有效結論步驟：i）求H1H2.Hn的主合取范式 ii）確定有效結論設其主合取范式有n個極大項，則：CC2n1.P(PQ)P(PQ) (PF)(PQ) (PQQ)(PQ) (PQ)(PQ)(PQ)PQ,PQ,PQ(PQ)(PQ):P(PQ(PQ):Q(PQ)(PQ):PQ(PQ)(PQ)(PQ):P(PQ)主范式的應用： 主合取推理的結論計數(shù) 主析取方案的設計謂詞和量詞個體域討論問題的范圍，記為DD中的元素稱為個體個體常元：特指時，a,b,c.個體變元：泛指時，u,v,.,x,y,z謂詞刻畫個體的性質(zhì)或幾個個體間關系的模式叫謂詞。特指時：謂詞常元泛指時：謂詞變元量詞全能量詞：xA(x)：對所有x，A(x)為T存在量詞；特性量詞：刻畫個體屬性1. 對，特性謂詞作為前件加入2. 對，特性謂詞作為合取式加入量化斷言和命題的關系1. 論域D是有限D(zhuǎn)=a1,a2,.,anxA(x)A(a1)A(a2).A(an)xA(x)A(a1)A(a2).A(a1)2.D可數(shù)無限集xA(x)A(0)A(1)A(2).xA(x)A(0)A(1)A(2).謂詞公式原子公式：無聯(lián)結詞約束變元，自由變元轄域：緊接于量詞之后最小的子公式叫量詞的轄域約束，自由變元改名規(guī)則：操作對象：約束變元操作范圍：全部替換選用符號：不在公式中出現(xiàn)的符號謂詞演算的永真公式一、 基本概念A與B等價，設A、B是任意的謂詞公式，E是指定的論域，若：（1） 對A B中的謂詞指定E中的中心謂詞（2） 對A B中個體常元、變元指定E中的個體有A與B的取值相同，則稱A與B在E上是等價的，記為A=B若E是任意的，當A與B的取值相同時，稱A與B等價 2、類型：永真 永假 可滿足二、謂詞公式的永真式1、關于量詞 xAA XAA A中無XxA(x)=A(Y) A(Y)=xA(x)所以xA(x)= xA(x)2、量詞的否定xA(x) xA(x) xA(x) xA(x)3、量詞的轄域 縮小x(A(x)P) xA(x)P 增大例：PQPQ P: xA(x) Q: xB(x)xA(x) xB(x) xA(x)xB(x) xA(x)xB(x)x(A(x)B(x) x(A(x) B(x)4、量詞的分配形式x(A(x)B(x) xA(x)xB(x)x(A(x)B(x) xA(x)xB(x)x(A(x) B(x)= xA(x)xB(x)x(A(x)B(x)= xA(x)xB(x)5、 量詞與和的關系 x(A(x)B(x) xA(x) xB(x)6、 關于多個量詞xyP（x,y）yx P（x,y）xyP(x,y) yx P(x,y)三、謂詞運算的三個規(guī)則 1、代入規(guī)則 操作對象：自由變元 操作范圍：全部替換 最多代入：若公式中含有n個謂詞變元，最多可帶入n個自由變元 2、置換規(guī)則 A是G的子公式，AB,以B代A的某些出現(xiàn)，得G，則GG 3、對偶規(guī)則 謂詞公式A僅含 ， 與 ，T與F ，與，互換得A* AB A*B* AB A*-B*謂詞的推理規(guī)則一、A(x)關于y是自由的-x不在y的轄域中出現(xiàn) 推理規(guī)則：P規(guī)則，T規(guī)則，E1-E24，I1-I9，Q1-Q191、 全稱特指 US2、 存在特指 ES3、 全稱推廣 UG4、 存在推廣 EG集合 集合的行性質(zhì)：唯一，無序，確定，抽象 集合與元素的子集： 集合與集合的關系： =描述集合的方法：列舉法 命題法 歸納法 例：N=(0，1，2、)（1） ON（2） xN,X+1N（3） 若SN滿足(1)(2),則S=N 冪集1. 定義：P(A)=X|XA2. 性質(zhì)（1）P(A) (A) (2) P(A) (3)|A|=N |P(A)|=2 =2A集合的運算 1定義AB=XAXBAB= XAXBA=XUXA (A的補集) 絕對補A-B=X| XAXB 相對補AB= XABXAB=AB-AB 對稱差AB=AB化為并、交、補、環(huán)和、環(huán)積 2性質(zhì) （1）關于 AA=A AA=A AB=BA AB=BA A（BC）=（AB）（AC） A(BC)=(AB)(AC) ABA ABB ABA ABB AB且CD則ACBD ACBD AB ACABC ABC (2)關于補 A=A AB=AB AB=AB (3)關于 AA= AA=U AB=BA (4)關于冪集 2AB=2A2B 等號成立條件：AB或BA 2AB=2A2B 2A-B2A-2B 2A2A3、有限集合的計數(shù)問題ABmin (A=B）AB=ABABAB=ABAB歸納法和自然數(shù) 一、用歸納法描述集合E=XXN且X是偶數(shù)=0,2,4,6 二、自然數(shù)1.集合的后繼 設A是任一集合，則A的后繼A”意義如下 A”=AA 如：A=Aa A=aa=a,a 性質(zhì):AA且AA2.自然數(shù)的構造 0= 1= 2=1=, 3=2=,3.皮亞諾定理 （1）0N (2)nN有nN (3)0不是任一元素的后繼 (4)n,mN,若m=n,則m=n (5) 若SN滿足0S nS,有nS 則S=N三數(shù)學歸納法 1.第一數(shù)學歸納法（完全數(shù)學歸納法） P (n0） n(p(n)p(n+1) 所以np(n) 2.第二數(shù)學歸納法（不完全數(shù)學歸納法） P (n0 ) k（kn,p(k)p(n)） 所以np(n) 笛卡爾乘積1 序偶 Df，設x,y是任意兩個元素，稱為次序偶 X:第一分量；Y：第二分量 二.笛卡爾乘積 1.Df.設A，B是任意集合 |xAyB稱為A與B的笛卡爾乘積，記為AB 若A1,A2,，An,則 A1A2xAn=|xn Ai 稱為n個集合的笛卡爾乘積例：A=1，2，B=C，D=4，5（AB）D=,D =,4,5,4,5=, A(BD)=1,1,2,2(AB)DA(BD)不滿足交換律和結合律2. 性質(zhì)Th1.AB=,iffA=vB=證：“=” 假設A且B aA,bB 使ABAB,矛盾 “=” 假設AB AB,有xA,yBA且B矛盾Th2.設A，B，C，D是任意非空集合，則：ACBD，iffABCD，反之亦然Th3.假設A，B，C是任意集合，則：1） A（BC）=ABAC2） （BC）A=BACA3） A（BC）=ABAC4） （BC）A=BACATh4.若|A|=n,|B|=m,則|AB|=nm第3章 二元關系3.1基本概念 Df:1)AB的子集稱為A到B的二元關系 2)A1A2An的子集稱為A1，A2An間的n元關系（n2)3)若A1=A2=An=A 則n XA 的子集稱為A上的n元關系3.1.2二元關系1 Df RAB,稱為A到B的二元關系A為前域，B為陪域RAA，稱R為A上的二元關系d (R）=x|Rr (R)=y|R二 二元關系的表示1.列舉法2.命題法 例：A=1,2,3,4,5 R=|x+y4 =,3. 歸納法 例：設RNN定義如下. R ,i f f xyxRy iff xy基礎1）R歸納2）R,有R,R極小3）僅由1）和2）得到的序偶R4. 關系矩陣 RAB,|A|=n,|B|=m MR=(Vij)nm,如下0 R Vij =1 否則稱為R的關系矩陣1 0 10 1 00 0 0MR= 5.關系圖y GR：R xx=y，環(huán)3 性質(zhì) 1.自反性 1）Df.設RAxA若滿足xA,有R,則稱R是A上的自反關系例：A=1，2，3R=,1) 集上的關系是自反的 x(x), 永T2） 全關系是自反的 IA=|xA,稱為A上的恒等關系 R自反，iff x(xAR)3) 非集合上的關系不是自反的 x(xA),永F2） 特征 R自反iff xA,有R Iff,IAR (集合特征）Iff，MR主對角線全“1”GR中每個點有自圈2. 反自反性3. 對稱性 1）Df.RAA,x,yA,R有R,則稱R是A上的對稱關系 2）特征 MR:（1）允許有“1” (2) 關于主對角線對稱 GR：（1）允許有自圈 （2）不同結點若有邊必為雙向邊4. 反對稱性 1）Df.RAA，對x,yA.若xRyyRx=x=y,則稱R是A上的反對稱關系xy(RRx=y)永T xyRvR,永T2） 特征 MR：（1）主對角線可有“1” （2）aij=11,aj=0或aij=1,aji=0或1GR：（1）允許有自圈 （2）不同結點若有邊必為單向邊AA不是反對稱的IA 是反對稱的集上的關系是反對稱的非集上的關系也是反對稱的5. 傳遞性 1）Df:RAAx,y,zR,若xRy且yRz,則R,稱R是A上的傳遞關系2) 特征 MR，aij=1且ajk=1,有aik=1 GR,處處有捷徑3.2關系的合成 一.Df設RAB，SBC|yB,使RS稱為R與S的合成，記為R。SA=1，2，3 B=a,b C=4,5R =, S=,R 。S=,S 。R不存在 注：1）yran(R)dom(s),若ran(R)dom(R)=,則R。S 2）“。”不滿足交換律2 關系矩陣，關系圖 1，關系矩陣， 設RAB，SBC，MR。S=MR * MS1 00 11 11 00 0MRMS2232 MR。S=1 11 00 0321 11 00 032MR * MS=2. 關系圖GR。STh1.R AB,SBC,TCD,則：（R。S)。T=R。（S。T）Th2.設RAB，S，TBC,WCD且ST，則：）R。SR。T）S。WT。WRS，iff：（）R，S有相同的前域和陪域（）作為集合有RSTh3，設RAB，S，TBC，WCD）R。（ST）R。SR。T）（S）。W）R。（ST）R。SR。T）（ST）。RS。RT。R三關系的冪運算1、Df 設RAA R自身合成n次（n0）稱為r的n次冪，記為Rn,定義如下：Rn = IA n=0Rn-1R n0 *IA=|xA例：A=1,2,3R=,則：R0=, R1=, R2=, R3=,=R0 R4=R1 , R5=R2一般的有 Rn=3=RN(n0)2、性質(zhì)Th4 RAA RnRM=Rm+n (Rn)m=RnmTh5 設RAA，若|A|=n,則存在i和j滿足:0ij2n2使Ri=Rj證：構造序列：R0，R1，R2，R2n2共有2n2+1個，而A不同的二元關系有2n2個根據(jù)鴿籠原理可知：i,j 0ij2n2使Ri=Rj注：本定理對無限集不成立例：RII （I是整數(shù)集）定義如下：R=|y=x+1R0=|xI R1=|y=x+1 R2=|y=x+2 R3=|y=x+3 Rn=|y=x+nTh6 設RAA若存在ij使Ri=Rj，則i) 對所有KN,有Ri+k=Rj+kii) 對所有K，MN，有Ri+md+k=Ri+k d=j-iiii) 記s=R0，R1，R2，