離散數(shù)學(xué)知識(shí)點(diǎn).doc

緒論研究對(duì)象：離散量研究方法：解的存在性 解的能行性研究?jī)?nèi)容：數(shù)理邏輯 集合 代數(shù)系統(tǒng) 圖論 離散概率 組合數(shù)學(xué)例題1、A、B、C、D四人參加四次長(zhǎng)跑，問(wèn)：“A在B前三次，B在C前三次，C在D前三次，D在A前三次”是否有解，若有求出，否則說(shuō)明理由。方法一： A A B C D n個(gè)元素的環(huán)形排列可拆成n個(gè)元素的 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：在邊長(zhǎng)為1的正方形中任取五個(gè)點(diǎn)，則至少有兩個(gè)點(diǎn)的距離2/2。“中點(diǎn)分隔”將邊長(zhǎng)為1的正方形分成四個(gè)邊長(zhǎng)為1/2的小正方形，從中任取五個(gè)小點(diǎn)，必有兩個(gè)小點(diǎn)來(lái)自一個(gè)小正方形。例題3：“布魯英序列”-應(yīng)用旋轉(zhuǎn)鼓的設(shè)計(jì)，設(shè)旋轉(zhuǎn)鼓有8個(gè)區(qū)域，旋轉(zhuǎn)一圈可識(shí)別三位二進(jìn)制數(shù)，如何確定磁粉位置。（陰影0，非陰影1） 0111 000 0010001 0111 010 011 1 0 100 101 1 110 111 1思考題：四位二進(jìn)制 a1 a2 a3 a4例題4：有五位小姐排成一排，所有小姐姓不同，穿的衣服顏色不同，喝不同的飲料，養(yǎng)不同的寵物，吃不同的水果，已知：1.錢(qián)小姐穿紅衣服 2.翁小姐養(yǎng)了一只狗3.陳小姐喝茶 4.穿綠衣服的小姐在穿白色衣服小姐的左邊，穿綠衣服的小姐在喝咖啡5.吃西瓜的小姐養(yǎng)鳥(niǎo) 6.穿黃衣服的小姐吃梨7.站中間的小姐喝牛奶 8.趙小姐站最左邊9.吃桔子的小姐站在養(yǎng)貓的小姐旁邊 10.養(yǎng)魚(yú)的小姐旁邊小姐吃梨11.吃蘋(píng)果的小姐喝香檳 12.江小姐吃香蕉13.趙小姐站在穿藍(lán)色衣服小姐旁邊 14.喝開(kāi)水的小姐站在吃桔子的小姐旁邊問(wèn)每位小姐怎么站，她們分別養(yǎng)什么寵物，吃什么水果，喝什么飲料，穿什么顏色衣服，姓什么。12345姓趙陳錢(qián)江翁吃梨桔子西瓜香蕉蘋(píng)果喝開(kāi)水茶牛奶咖啡香檳顏色黃藍(lán)紅綠白寵物貓魚(yú)鳥(niǎo)狗例題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任意個(gè)整除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ù)理邏輯（一階） 演算 標(biāo)準(zhǔn)型 等價(jià) 謂詞邏輯 證明 推理 應(yīng)用 類型一、 命題：具有確定真假意義的陳述句（斷言）永T命題：真值為T(mén)（1）永F命題：假值為F（0）1+1=10 X3 X的取值有關(guān) 二進(jìn)制 十進(jìn)制 （T） （F） 費(fèi)晰邏輯原子命題：不可再拆開(kāi)的命題復(fù)合命題：由原子命題和聯(lián)結(jié)詞構(gòu)成的命題詞：命題的符號(hào)表示，用大寫(xiě)字母表示二、 聯(lián)結(jié)詞1. 否定（not）A為命題，若A為T(mén)，A為FA:張明是上海人 A：張明不是上海人2. 合取（and）A、 B是命題，AB為T(mén), iff(當(dāng)且僅當(dāng)）A、B均為T(mén)A 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 或 不可兼 量的估計(jì)4. 蘊(yùn)含命題（if-then）A、 B是命題，AB為F，iff A為T(mén)，B為F前提 結(jié)論AB：原命題 AB:反命題（否命題）BA：逆命題 BA:逆反（逆否）命題5. 等值詞（iff） A B為T(mén)，iff A、B的值相同P：生命息 Q：戰(zhàn)斗止（PQ）(QP) P Q三、 命題公式（合成公式）wff1. 命題變?cè)ＴＴ篢、F（僅有兩個(gè)）變?cè)涸赥、F中取值，用小寫(xiě)字母表示2. wff的定義一個(gè)wff定義遞歸（歸納）如下：基礎(chǔ)i) 命題變?cè)?，常元是wff歸納ii) 若A、B是wff,則（A）,(AB),(AB),(AB),(A B)也是wff極小化iii) 有限次使用i）和ii)得到的符號(hào)命題是wff 反進(jìn)P Q (P) (Q)約定：最外層括號(hào)可省略優(yōu)先級(jí)： 高 低 結(jié)合方向：左結(jié)合 如(PQ)R若優(yōu)先級(jí)，結(jié)合方向可確定計(jì)算順序時(shí)，括號(hào)可省略括號(hào)是用來(lái)改變運(yùn)算順序的擴(kuò)展：（1）n個(gè)變?cè)脑鲋当碛?n行（指派），可構(gòu)成22n wff（2）結(jié)合律：等值有結(jié)合侓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.指派（解釋）對(duì)wffG中全部變?cè)囊唤M賦值，成為一個(gè)指派N個(gè)變?cè)娜恐概捎?n個(gè)，可構(gòu)成2的2n個(gè)wff2.永T式（重言式）在任何指派下為T(mén) PP3.永F式（矛盾式）在任何指派下為F PP4.偶然式非永T，亦非永F PQ5.可滿足式至少在一組指派下取值為T(mén) PQ,P Q 二、邏輯恒等式1.定義：設(shè)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 對(duì)稱性（3）.若AB,且BC,則AC 傳遞性 4.三大規(guī)則（1）.代入規(guī)則代換實(shí)例：設(shè)wffG,P1，P2Pn是G中全部命題的變?cè)珹是wff，以A代Pi的全部出現(xiàn)，得到公式G為G的一個(gè)代換實(shí)例。如 wffG:(PQ)(QR) wffA:SRA代Q的全部出現(xiàn)：G(P(SR)(SR)R)代入規(guī)則：（1）.永T式的任何可代入實(shí)例是永T式 （2）.永F式的任何可代入實(shí)例是永F式 （3）.可滿足式是任何可代入實(shí)例是不確定的例題： wffG: PQ G G PRR RRQ 可滿足式 永T式 RRSS 永F式（2）.重?fù)Q規(guī)則設(shè)wffG，A是G的子公式，B是wff且AB,以B代A的某些出現(xiàn)，得到公式G,則GG例題：wffG:（PQ）(QR)(PQ)化簡(jiǎn)，取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）.對(duì)偶規(guī)則1.對(duì)偶式設(shè)wffG中僅含、且不包含和作用于變?cè)贕中，將與互換，T與F互換，得新公式G*,則稱G*為對(duì)偶式例題：求wffG:P(PQ)的對(duì)偶式解：P（PQ）P(PQ) G*:P(PQ)求（PQ）R的G*（PQ）R(PQ)R(PQ)RPQRG*:（PQ）R步驟：i)消、 ii)利用D-M定侓 iii)寫(xiě)G*，必要時(shí)加括號(hào)（2）.對(duì)偶規(guī)則設(shè)A、B是wff，A*、B*分別為A、B對(duì)偶式，若AB,則A*B*如： PQQP PQQP三大規(guī)則規(guī)則對(duì)象范圍要求結(jié)論代入變?cè)狿i全部出現(xiàn)永F式永T式重?fù)Q子公式A某些出現(xiàn)ABGG對(duì)偶、T、F全部不含、AB則A*B*四、 永真蘊(yùn)含式1.設(shè)A、B是wff，若AB永T，則稱A永真蘊(yùn)含B，記為ABAB iff AB永為T(mén) iff A為T(mén)，B必為T(mén)（肯定前件）Iff B為F，A必為F（否定后件）2.常用永真蘊(yùn)含式P10A BPPQ AB永為T(mén)PPQPPQTQT3.性質(zhì)（1）AA AA永為T(mén)？ AAAAT（2）AB,BA則AB（3）AB,BC則AC4.A與A*關(guān)系例： 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.基本積：變?cè)?、變?cè)姆穸?、合取基本和：變?cè)?、變?cè)姆穸?、析取如?p q 基本積：pq pq pp pqp 基本和: pq pq pp pqp2.性質(zhì)基本積（和）永F（T） Iff變?cè)捌浞穸ㄍ瑫r(shí)出現(xiàn)在基本積（和）中3.范式（1）析取范式若wffA，AA1A2Ak（*） Ai是基本積，稱（*）為A的析取范式若wffA，AA1A2Ac（*） Ai是基本積，稱（*）為A的合取范式PS：把其中運(yùn)算符最少的稱為最簡(jiǎn)析取范式例：設(shè)wffA:P（QR）求析（合）取范式解：P（QR）P(QR) (PQR) 析取范式 合取范式 基本積：P,Q，R 基本和：PQR二、主析取范式1.極小項(xiàng)及其性質(zhì)（1）Df：若基本積滿足i).每個(gè)變?cè)仨毘霈F(xiàn)且進(jìn)出現(xiàn)一次 ii).變?cè)捌浞穸ú荒芡瑫r(shí)出現(xiàn)則稱該基本積為極小項(xiàng)。 編碼 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.每個(gè)變?cè)臉O小項(xiàng)有2n個(gè)2.每個(gè)極小項(xiàng)僅在變?cè)囊唤M指派下取值為T(mén)，其余(2n)-1組指派下取值為F3.任兩個(gè)極小項(xiàng)的合取為永F式4.全部極小項(xiàng)的析取為永T式 2.編碼原變?cè)? 反變?cè)?M0:P1 P2Pn M1:P1Pn-1PnM(2n)-1:P1P2Pn3.主析取范式設(shè)wffA，若AA1A2Ak（*） Ai為極小項(xiàng)，則稱（*）為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最簡(jiǎn)范式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.編碼原變?cè)? 反變?cè)?極小項(xiàng)：1 1pq 極大項(xiàng)：1 1pq M3M3性質(zhì)4：MiMi注：永T式不存在主合取范式，仍記為T(mén)四主合取/主析取范式的計(jì)數(shù)問(wèn)題n個(gè)變?cè)臉O小項(xiàng)有2n個(gè)結(jié)論：（1）永F式的主析取范式不存在，仍記為F （2）永T式的主析取范式全部由極小項(xiàng)構(gòu)成 （3）可滿足式由部分極小項(xiàng)構(gòu)成 有2（2n）-1個(gè)聯(lián)結(jié)詞的擴(kuò)充與歸約已學(xué)過(guò)的聯(lián)結(jié)詞：，聯(lián)結(jié)詞的擴(kuò)充一元：Pf1f2f3f40001110永假1恒等0否定1永真f1:F f2:P f3:p f4:T一元無(wú)需擴(kuò)充二元：PQf1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16000100011100011011010010010011011101100001001010110111110000100101101111擴(kuò)充： 與非 ：P Q (PQ） 或非 ：P Q （PQ） 異或 ：PQ (PQ)全功能集： 設(shè)A是運(yùn)算符集，若在任一wff中可用A中運(yùn)算符表示，則稱A為全功能集。 若A中符號(hào)最少，則稱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的有效結(jié)論。P(PQ)Q (P(PQ)Q P(PQ)QTQ是P（PQ）的有效結(jié)論推理規(guī)則1、 前提引入 P 可在任何時(shí)刻引入2、 結(jié)論引入 T 若證明過(guò)程中，一個(gè)或多個(gè)wff永真蘊(yùn)含S，則S可加入證明中3、 邏輯恒等式4、 永真蘊(yùn)含式如： P Q PQ PQ PQ PQ P Q證明方法1.真值表 H1H2.HnC2.等值演算3.構(gòu)造性證明 步驟 斷言（真） 結(jié)論若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. 歸謬法相容性（一致性）： 設(shè)命題集合A1，A2，.,Ak，若A1A2.Ak為真，則稱A1Ak 是相容的（或一致的），否則稱為不相容的。 H1H2.HnC （H1H2.Hn）C (H1H2.HnC) 即證：H1H2.HnC為F H1，H2，.,Hn,C不相容計(jì)數(shù)問(wèn)題： 一組前提可得多少個(gè)有效結(jié)論步驟：i）求H1H2.Hn的主合取范式 ii）確定有效結(jié)論設(shè)其主合取范式有n個(gè)極大項(xiàng)，則：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)主范式的應(yīng)用： 主合取推理的結(jié)論計(jì)數(shù) 主析取方案的設(shè)計(jì)謂詞和量詞個(gè)體域討論問(wèn)題的范圍，記為DD中的元素稱為個(gè)體個(gè)體常元：特指時(shí)，a,b,c.個(gè)體變?cè)悍褐笗r(shí)，u,v,.,x,y,z謂詞刻畫(huà)個(gè)體的性質(zhì)或幾個(gè)個(gè)體間關(guān)系的模式叫謂詞。特指時(shí)：謂詞常元泛指時(shí)：謂詞變?cè)吭~全能量詞：xA(x)：對(duì)所有x，A(x)為T(mén)存在量詞；特性量詞：刻畫(huà)個(gè)體屬性1. 對(duì)，特性謂詞作為前件加入2. 對(duì)，特性謂詞作為合取式加入量化斷言和命題的關(guān)系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ù)無(wú)限集xA(x)A(0)A(1)A(2).xA(x)A(0)A(1)A(2).謂詞公式原子公式：無(wú)聯(lián)結(jié)詞約束變?cè)?，自由變?cè)犛颍壕o接于量詞之后最小的子公式叫量詞的轄域約束，自由變?cè)拿?guī)則：操作對(duì)象：約束變?cè)僮鞣秶喝刻鎿Q選用符號(hào)：不在公式中出現(xiàn)的符號(hào)謂詞演算的永真公式一、 基本概念A(yù)與B等價(jià)，設(shè)A、B是任意的謂詞公式，E是指定的論域，若：（1） 對(duì)A B中的謂詞指定E中的中心謂詞（2） 對(duì)A B中個(gè)體常元、變?cè)付‥中的個(gè)體有A與B的取值相同，則稱A與B在E上是等價(jià)的，記為A=B若E是任意的，當(dāng)A與B的取值相同時(shí)，稱A與B等價(jià) 2、類型：永真 永假 可滿足二、謂詞公式的永真式1、關(guān)于量詞 xAA XAA A中無(wú)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、 量詞與和的關(guān)系 x(A(x)B(x) xA(x) xB(x)6、 關(guān)于多個(gè)量詞xyP（x,y）yx P（x,y）xyP(x,y) yx P(x,y)三、謂詞運(yùn)算的三個(gè)規(guī)則 1、代入規(guī)則 操作對(duì)象：自由變?cè)?操作范圍：全部替換 最多代入：若公式中含有n個(gè)謂詞變?cè)疃嗫蓭雗個(gè)自由變?cè)?2、置換規(guī)則 A是G的子公式，AB,以B代A的某些出現(xiàn)，得G，則GG 3、對(duì)偶規(guī)則 謂詞公式A僅含 ， 與 ，T與F ，與，互換得A* AB A*B* AB A*-B*謂詞的推理規(guī)則一、A(x)關(guān)于y是自由的-x不在y的轄域中出現(xiàn) 推理規(guī)則：P規(guī)則，T規(guī)則，E1-E24，I1-I9，Q1-Q191、 全稱特指 US2、 存在特指 ES3、 全稱推廣 UG4、 存在推廣 EG集合 集合的行性質(zhì)：唯一，無(wú)序，確定，抽象 集合與元素的子集： 集合與集合的關(guān)系： =描述集合的方法：列舉法 命題法 歸納法 例：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集合的運(yùn)算 1定義AB=XAXBAB= XAXBA=XUXA (A的補(bǔ)集) 絕對(duì)補(bǔ)A-B=X| XAXB 相對(duì)補(bǔ)AB= XABXAB=AB-AB 對(duì)稱差A(yù)B=AB化為并、交、補(bǔ)、環(huán)和、環(huán)積 2性質(zhì) （1）關(guān)于 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)關(guān)于補(bǔ) A=A AB=AB AB=AB (3)關(guān)于 AA= AA=U AB=BA (4)關(guān)于冪集 2AB=2A2B 等號(hào)成立條件：AB或BA 2AB=2A2B 2A-B2A-2B 2A2A3、有限集合的計(jì)數(shù)問(wèn)題ABmin (A=B）AB=ABABAB=ABAB歸納法和自然數(shù) 一、用歸納法描述集合E=XXN且X是偶數(shù)=0,2,4,6 二、自然數(shù)1.集合的后繼 設(shè)A是任一集合，則A的后繼A”意義如下 A”=AA 如：A=Aa A=aa=a,a 性質(zhì):AA且AA2.自然數(shù)的構(gòu)造 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ù)學(xué)歸納法 1.第一數(shù)學(xué)歸納法（完全數(shù)學(xué)歸納法） P (n0） n(p(n)p(n+1) 所以np(n) 2.第二數(shù)學(xué)歸納法（不完全數(shù)學(xué)歸納法） P (n0 ) k（kn,p(k)p(n)） 所以np(n) 笛卡爾乘積1 序偶 Df，設(shè)x,y是任意兩個(gè)元素，稱為次序偶 X:第一分量；Y：第二分量 二.笛卡爾乘積 1.Df.設(shè)A，B是任意集合 |xAyB稱為A與B的笛卡爾乘積，記為AB 若A1,A2,，An,則 A1A2xAn=|xn Ai 稱為n個(gè)集合的笛卡爾乘積例：A=1，2，B=C，D=4，5（AB）D=,D =,4,5,4,5=, A(BD)=1,1,2,2(AB)DA(BD)不滿足交換律和結(jié)合律2. 性質(zhì)Th1.AB=,iffA=vB=證：“=” 假設(shè)A且B aA,bB 使ABAB,矛盾 “=” 假設(shè)AB AB,有xA,yBA且B矛盾Th2.設(shè)A，B，C，D是任意非空集合，則：ACBD，iffABCD，反之亦然Th3.假設(shè)A，B，C是任意集合，則：1） A（BC）=ABAC2） （BC）A=BACA3） A（BC）=ABAC4） （BC）A=BACATh4.若|A|=n,|B|=m,則|AB|=nm第3章 二元關(guān)系3.1基本概念 Df:1)AB的子集稱為A到B的二元關(guān)系 2)A1A2An的子集稱為A1，A2An間的n元關(guān)系（n2)3)若A1=A2=An=A 則n XA 的子集稱為A上的n元關(guān)系3.1.2二元關(guān)系1 Df RAB,稱為A到B的二元關(guān)系A(chǔ)為前域，B為陪域RAA，稱R為A上的二元關(guān)系d (R）=x|Rr (R)=y|R二 二元關(guān)系的表示1.列舉法2.命題法 例：A=1,2,3,4,5 R=|x+y4 =,3. 歸納法 例：設(shè)RNN定義如下. R ,i f f xyxRy iff xy基礎(chǔ)1）R歸納2）R,有R,R極小3）僅由1）和2）得到的序偶R4. 關(guān)系矩陣 RAB,|A|=n,|B|=m MR=(Vij)nm,如下0 R Vij =1 否則稱為R的關(guān)系矩陣1 0 10 1 00 0 0MR= 5.關(guān)系圖y GR：R xx=y，環(huán)3 性質(zhì) 1.自反性 1）Df.設(shè)RAxA若滿足xA,有R,則稱R是A上的自反關(guān)系例：A=1，2，3R=,1) 集上的關(guān)系是自反的 x(x), 永T2） 全關(guān)系是自反的 IA=|xA,稱為A上的恒等關(guān)系 R自反，iff x(xAR)3) 非集合上的關(guān)系不是自反的 x(xA),永F2） 特征 R自反iff xA,有R Iff,IAR (集合特征）Iff，MR主對(duì)角線全“1”GR中每個(gè)點(diǎn)有自圈2. 反自反性3. 對(duì)稱性 1）Df.RAA,x,yA,R有R,則稱R是A上的對(duì)稱關(guān)系 2）特征 MR:（1）允許有“1” (2) 關(guān)于主對(duì)角線對(duì)稱 GR：（1）允許有自圈 （2）不同結(jié)點(diǎn)若有邊必為雙向邊4. 反對(duì)稱性 1）Df.RAA，對(duì)x,yA.若xRyyRx=x=y,則稱R是A上的反對(duì)稱關(guān)系xy(RRx=y)永T xyRvR,永T2） 特征 MR：（1）主對(duì)角線可有“1” （2）aij=11,aj=0或aij=1,aji=0或1GR：（1）允許有自圈 （2）不同結(jié)點(diǎn)若有邊必為單向邊AA不是反對(duì)稱的IA 是反對(duì)稱的集上的關(guān)系是反對(duì)稱的非集上的關(guān)系也是反對(duì)稱的5. 傳遞性 1）Df:RAAx,y,zR,若xRy且yRz,則R,稱R是A上的傳遞關(guān)系2) 特征 MR，aij=1且ajk=1,有aik=1 GR,處處有捷徑3.2關(guān)系的合成 一.Df設(shè)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）“?！辈粷M足交換律2 關(guān)系矩陣，關(guān)系圖 1，關(guān)系矩陣， 設(shè)RAB，SBC，MR。S=MR * MS1 00 11 11 00 0MRMS2232 MR。S=1 11 00 0321 11 00 032MR * MS=2. 關(guān)系圖GR。STh1.R AB,SBC,TCD,則：（R。S)。T=R。（S。T）Th2.設(shè)RAB，S，TBC,WCD且ST，則：）R。SR。T）S。WT。WRS，iff：（）R，S有相同的前域和陪域（）作為集合有RSTh3，設(shè)RAB，S，TBC，WCD）R。（ST）R。SR。T）（S）。W）R。（ST）R。SR。T）（ST）。RS。RT。R三關(guān)系的冪運(yùn)算1、Df 設(shè)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 設(shè)RAA，若|A|=n,則存在i和j滿足:0ij2n2使Ri=Rj證：構(gòu)造序列：R0，R1，R2，R2n2共有2n2+1個(gè)，而A不同的二元關(guān)系有2n2個(gè)根據(jù)鴿籠原理可知：i,j 0ij2n2使Ri=Rj注：本定理對(duì)無(wú)限集不成立例：RII （I是整數(shù)集）定義如下：R=|y=x+1R0=|xI R1=|y=x+1 R2=|y=x+2 R3=|y=x+3 Rn=|y=x+nTh6 設(shè)RAA若存在ij使Ri=Rj，則i) 對(duì)所有KN,有Ri+k=Rj+kii) 對(duì)所有K，MN，有Ri+md+k=Ri+k d=j-iiii) 記s=R0，R1，R2，