1、緒論研究對象：離散量研究方法：解的存在性 解的能行性研究內(nèi)容：數(shù)理邏輯 集合 代數(shù)系統(tǒng) 圖論 離散概率 組合數(shù)學(xué)例題1、A、B、C、D四人參加四次長跑，問：“A在B前三次，B在C前三次，C在D前三次，D在A前三次”是否有解，若有求出，否則說明理由。方法一： 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：在邊長為1

2、的正方形中任取五個(gè)點(diǎn)，則至少有兩個(gè)點(diǎn)的距離2/2?！爸悬c(diǎn)分隔”將邊長為1的正方形分成四個(gè)邊長為1/2的小正方形，從中任取五個(gè)小點(diǎn)，必有兩個(gè)小點(diǎn)來自一個(gè)小正方形。例題3：“布魯英序列”-應(yīng)用旋轉(zhuǎn)鼓的設(shè)計(jì)，設(shè)旋轉(zhuǎn)鼓有8個(gè)區(qū)域，旋轉(zhuǎn)一圈可識別三位二進(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.錢小姐穿紅衣服 2.翁小姐養(yǎng)了一只狗3.陳小姐喝

3、茶 4.穿綠衣服的小姐在穿白色衣服小姐的左邊，穿綠衣服的小姐在喝咖啡5.吃西瓜的小姐養(yǎng)鳥 6.穿黃衣服的小姐吃梨7.站中間的小姐喝牛奶 8.趙小姐站最左邊9.吃桔子的小姐站在養(yǎng)貓的小姐旁邊 10.養(yǎng)魚的小姐旁邊小姐吃梨11.吃蘋果的小姐喝香檳 12.江小姐吃香蕉13.趙小姐站在穿藍(lán)色衣服小姐旁邊 14.喝開水的小姐站在吃桔子的小姐旁邊問每位小姐怎么站，她們分別養(yǎng)什么寵物，吃什么水果，喝什么飲料，穿什么顏色衣服，姓什么。12345姓趙陳錢江翁吃梨桔子西瓜香蕉蘋果喝開水茶牛奶咖啡香檳顏色黃藍(lán)紅綠白寵物貓魚鳥狗例題5：同態(tài)加密R+ f:ax(a>1) R* f(x+y)=f(x)*f(y)X

4、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（1）

5、永F命題：假值為F（0）1+1=10 X>3 X的取值有關(guān) 二進(jìn)制 十進(jìn)制 （T） （F） 費(fèi)晰邏輯原子命題：不可再拆開的命題復(fù)合命題：由原子命題和聯(lián)結(jié)詞構(gòu)成的命題詞：命題的符號表示，用大寫字母表示二、 聯(lián)結(jié)詞1. 否定（not）¬A為命題，若A為T，¬A為FA:張明是上海人 ¬A：張明不是上海人2. 合取（and）A、 B是命題，AB為T, iff(當(dāng)且僅當(dāng)）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均

6、為F 或 不可兼 量的估計(jì)4. 蘊(yùn)含命題（if-then）A、 B是命題，AB為F，iff A為T，B為F前提 結(jié)論AB：原命題 ¬A¬B:反命題（否命題）BA：逆命題 ¬B¬A:逆反（逆否）命題5. 等值詞（iff） A B為T，iff A、B的值相同P：生命息 Q：戰(zhàn)斗止（¬P¬Q）(¬Q¬P) ¬P ¬Q三、 命題公式（合成公式）wff1. 命題變元，常元常元：T、F（僅有兩個(gè)）變元：在T、F中取值，用小寫字母表示2. wff的定義一個(gè)wff定義遞歸（歸納）如下：基礎(chǔ)i) 命題變元，常元是

7、wff歸納ii) 若A、B是wff,則（¬A）,(AB),(AB),(AB),(A B)也是wff極小化iii) 有限次使用i）和ii)得到的符號命題是wff 反進(jìn)¬P ¬Q (¬P) (¬Q)約定：最外層括號可省略優(yōu)先級： ¬ 高 低 結(jié)合方向：左結(jié)合 如(PQ)R若優(yōu)先級，結(jié)合方向可確定計(jì)算順序時(shí)，括號可省略括號是用來改變運(yùn)算順序的擴(kuò)展：（1）n個(gè)變元的增值表有2n行（指派），可構(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

8、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中全部變元的一組賦值，成為一個(gè)指派N個(gè)變元的全部指派有2n個(gè)，可構(gòu)成2的2n個(gè)wff2.永T式（重言式）在任何指派下為T P¬P3.永F式（矛盾式）在任何指派下為F P¬P4.偶然式非永T，亦非永F PQ5.可滿足式至少在一組指派下取值為T PQ,P Q 二、邏輯恒等式1.定義：設(shè)A，B是wff,若A B為永T，則稱A與B是邏輯恒等式，記為A B例題：A:PQ B:¬PQ

9、求證 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ī)則代換實(shí)例：設(shè)wffG,P1，P2Pn是G中全部命題的變元，A是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式

10、 （2）.永F式的任何可代入實(shí)例是永F式 （3）.可滿足式是任何可代入實(shí)例是不確定的例題： wffG: PQ G G PR¬R R¬RQ 可滿足式 永T式 R¬RS¬S 永F式（2）.重?fù)Q規(guī)則設(shè)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)（&

11、#172; QR）(PQ)（¬P¬Q¬PRQ¬QQR）(PQ)¬PRQPQQRQR（¬PPT）QRQR（3）.對偶規(guī)則1.對偶式設(shè)wffG中僅含¬、且不包含和作用于變元在G中，將與互換，T與F互換，得新公式G*,則稱G*為對偶式例題：求wffG:P(PQ)的對偶式解：P（PQ）P(¬PQ) G*:P(¬PQ)求（PQ）R的G*（PQ）R¬(PQ)R¬(¬PQ)RP¬QRG*:（PQ）R步驟：i)消、 ii)利用D-M定侓 iii)寫G*，必要時(shí)加括號（2）.對偶規(guī)則

12、設(shè)A、B是wff，A*、B*分別為A、B對偶式，若AB,則A*B*如： PQQP PQQP三大規(guī)則規(guī)則對象范圍要求結(jié)論代入變元Pi全部出現(xiàn)永F式永T式重?fù)Q子公式A某些出現(xiàn)ABGG對偶、T、F全部不含、AB則A*B*四、 永真蘊(yùn)含式1.設(shè)A、B是wff，若AB永T，則稱A永真蘊(yùn)含B，記為ABAB iff AB永為T iff A為T，B必為T（肯定前件）Iff B為F，A必為F（否定后件）2.常用永真蘊(yùn)含式P10A BPPQ AB永為TPPQ¬PPQTQT3.性質(zhì)（1）AA AA永為T？ AA¬AAT（2）AB,BA則AB（3）AB,BC則AC4.A與A*關(guān)系例： A（P,Q）

13、:PQ¬PQ A*（P,Q）:¬PQ ¬A*（P,Q）:P¬Q A（¬P,¬Q）:P¬QA（¬P1，¬P2¬Pn）¬A* （P1，P2Pn）A（P1，P2Pn）¬A*（¬P1，¬P2¬Pn）¬A（¬P1，¬P2¬Pn） A* （P1，P2Pn）¬A （P1，P2Pn） A*（¬P1，¬P2¬Pn）th1 :AB,A*B* th2:AB,B*A*范式一、基本積（和）1.

14、基本積：變元、變元的否定、合取基本和：變元、變元的否定、析取如： p q 基本積：pq p¬q pp pq¬p 基本和: pq p¬q pp pq¬p2.性質(zhì)基本積（和）永F（T） Iff變元及其否定同時(shí)出現(xiàn)在基本積（和）中3.范式（1）析取范式若wffA，AA1A2Ak（*） Ai是基本積，稱（*）為A的析取范式若wffA，AA1A2Ac（*） Ai是基本積，稱（*）為A的合取范式PS：把其中運(yùn)算符最少的稱為最簡析取范式例：設(shè)wffA:P（QR）求析（合）取范式解：P（QR）¬P(QR) (¬P¬QR) 析取范式 合取范式

15、 基本積：¬P,¬Q，R 基本和：¬P¬QR二、主析取范式1.極小項(xiàng)及其性質(zhì)（1）Df：若基本積滿足i).每個(gè)變元必須出現(xiàn)且進(jìn)出現(xiàn)一次 ii).變元及其否定不能同時(shí)出現(xiàn)則稱該基本積為極小項(xiàng)。 編碼 1 1 1 0 0 1 0 0p q pq p¬q ¬pq ¬p¬q0 0 0 0 0 10 1 0 0 1 01 0 0 1 0 01 1 1 0 0 0（2）性質(zhì)1.每個(gè)變元的極小項(xiàng)有2n個(gè)2.每個(gè)極小項(xiàng)僅在變元的一組指派下取值為T，其余(2n)-1組指派下取值為F3.任兩個(gè)極小項(xiàng)的合取為永F式4.全部極小項(xiàng)的析取為

16、永T式 2.編碼原變元1 反變元0M0:¬P1¬ P2¬Pn M1:¬P1¬Pn-1PnM(2n)-1:P1P2Pn3.主析取范式設(shè)wffA，若AA1A2Ak（*） Ai為極小項(xiàng)，則稱（*）為A的主析取范式例：求P(QP)的主析式范式方法一：等值演算（E1 E24）P(QP) ¬P(¬QP) ¬P¬ QP(¬PP)¬ QT¬QT方法二：真值表P Q P(QP) ¬P¬Q¬PQP¬QPQ0 0 1 1 M0M1M2M30 1 1 01 0

17、 1 11 1 1 1求（PQ）P ¬（¬PQ）P P¬QP P(¬QT) PT P最簡范式P¬QPT P¬QP(Q¬ Q) P¬QPQP¬QM2M3(2，3)三、主合取范式 編碼 0 0 0 1 1 0 1 1p q pq p¬q ¬pq ¬p¬q0 0 0 1 1 10 1 1 0 1 11 0 1 1 0 11 1 1 1 1 02.編碼原變元0 反變元1極小項(xiàng)：1 1pq 極大項(xiàng)：1 1¬p¬q ¬M3M3性質(zhì)4：¬M

18、iMi注：永T式不存在主合取范式，仍記為T四主合取/主析取范式的計(jì)數(shù)問題n個(gè)變元的極小項(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é)過的聯(lián)結(jié)詞：，聯(lián)結(jié)詞的擴(kuò)充一元：Pf1f2f3f40001110永假1恒等0否定1永真f1:F f2:P f3:¬p f4:T一元無需擴(kuò)充二元：PQf1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f1600010001110001101101001001001101110110000100101011011

19、1110000100101101111擴(kuò)充： 與非 ：P Q (PQ） 或非 ：P Q （PQ） 異或 ：PQ (PQ)全功能集： 設(shè)A是運(yùn)算符集，若在任一wff中可用A中運(yùn)算符表示，則稱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ī)則和證明

20、方法如：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 若證明過程中，一個(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)

21、.(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ù)問

22、題： 一組前提可得多少個(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è)體域討論問題的范圍，記為DD中的元素稱為個(gè)體個(gè)體常元：特指時(shí)，a,b,c.個(gè)體變元：泛指時(shí)，u,v,.,x,y,z謂詞刻畫個(gè)體的性質(zhì)或幾個(gè)個(gè)體間關(guān)系的模式叫謂詞。特指時(shí)：謂詞常元泛指時(shí)：謂詞變元量詞全能量

23、詞：xA(x)：對所有x，A(x)為T存在量詞；特性量詞：刻畫個(gè)體屬性1. 對，特性謂詞作為前件加入2. 對，特性謂詞作為合取式加入量化斷言和命題的關(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ù)無限集xA(x)A(0)A(1)A(2).xA(x)A(0)A(1)A(2).謂詞公式原子公式：無聯(lián)結(jié)詞約束變元，自由變元轄域：緊接于量詞之后最小的子公式叫量詞的轄域約束，自由變元改名規(guī)則：操作對象：約束變元操作范圍：全部替換選用符號：不在公式中出現(xiàn)的符號謂詞演算的永真公式一、 基本概念A(yù)與B等價(jià)，設(shè)A、B是任

24、意的謂詞公式，E是指定的論域，若：（1） 對A B中的謂詞指定E中的中心謂詞（2） 對A B中個(gè)體常元、變元指定E中的個(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中無XxA(x)=>A(Y) A(Y)=>xA(x)所以xA(x)=> xA(x)2、量詞的否定¬xA(x)ó x¬A(x) ¬ xA(x)ó x¬A(x)3、量詞的轄域 縮小x(A(x)P)ó xA(x

25、)P 增大例：PQó¬PQ P: xA(x) Q: xB(x)xA(x) xB(x)ó¬ xA(x)xB(x)ó x¬A(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

26、、 關(guān)于多個(gè)量詞xyP（x,y）óyx P（x,y）xyP(x,y)ó yx P(x,y)三、謂詞運(yùn)算的三個(gè)規(guī)則 1、代入規(guī)則 操作對象：自由變元 操作范圍：全部替換 最多代入：若公式中含有n個(gè)謂詞變元，最多可帶入n個(gè)自由變元 2、置換規(guī)則 A是G的子公式，AóB,以B代A的某些出現(xiàn)，得G，則GóG 3、對偶規(guī)則 謂詞公式A僅含¬ ， 與 ，T與F ，與，互換得A* AóB A*óB* AB A*<-B*謂詞的推理規(guī)則一、A(x)關(guān)于y是自由的-x不在y的轄域中出現(xiàn) 推理規(guī)則：P規(guī)則，T規(guī)則，E1-E24，I1-I9，

27、Q1-Q191、 全稱特指 US2、 存在特指 ES3、 全稱推廣 UG4、 存在推廣 EG集合 集合的行性質(zhì)：唯一，無序，確定，抽象 集合與元素的子集： 集合與集合的關(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ǔ)集) 絕對補(bǔ)A-B=X| XAXB 相對補(bǔ)AB=

28、 XABXAB=AB-AB 對稱差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 等號成立條件：AB或BA 2AB=2A2B 2A-B2A-2B 2A2A3、有限集合的計(jì)數(shù)問題ABmin (A=B）AB=ABABAB=ABAB歸納法和自然數(shù) 一、用歸納法描述集合E=XXN且

29、X是偶數(shù)=0,2,4,6 二、自然數(shù)1.集合的后繼 設(shè)A是任一集合，則A的后繼A”意義如下 A”=AA 如：A=Aa A"=aa=a,a 性質(zhì):AA"且AA"2.自然數(shù)的構(gòu)造 0= 1="= 2=1"=, 3=2"=,3.皮亞諾定理 （1）0N (2)nN有n"N (3)0不是任一元素的后繼 (4)n,mN,若m=n,則m"=n" (5) 若SN滿足0S nS,有n"S 則S=N三數(shù)學(xué)歸納法 1.第一數(shù)學(xué)歸納法（完全數(shù)學(xué)歸納法） P (n0） n(p(n)p(n+1) 所以np(n) 2.第二數(shù)

30、學(xué)歸納法（不完全數(shù)學(xué)歸納法） P (n0 ) k（k<n,p(k)p(n)） 所以np(n) 笛卡爾乘積1 序偶 Df，設(shè)x,y是任意兩個(gè)元素，<x,y>稱為次序偶 X:第一分量；Y：第二分量 二.笛卡爾乘積 1.Df.設(shè)A，B是任意集合 <x,y>|xAyB稱為A與B的笛卡爾乘積，記為A×B 若A1,A2,，An,則 A1×A2×xAn=<x1,x2xn>|xn Ai 稱為n個(gè)集合的笛卡爾乘積例：A=1，2，B=C，D=4，5（A×B）×D=<1,C>,<2,C>×D

31、 =<<1,C>,4>,<<1,C>,5>,<<2,C>,4>,<<2,C>,5>=<1,C,4>,<1,C,5>,<2,C,4>,<2,C,5> A×(B×D)=<1,<C,4>>,<1,<C,5>>,<2,<C,4>>,<2<<C,5>>(A×B)×DA×(B×D)不滿足交換律和結(jié)合律2.

32、 性質(zhì)Th1.A×B=,iffA=vB=證：“=>” 假設(shè)A且B aA,bB 使<a,b>A×BA×B,矛盾 “<=” 假設(shè)A×B <a,b>A×B,有xA,yBA且B矛盾Th2.設(shè)A，B，C，D是任意非空集合，則：ACBD，iffA×BC×D，反之亦然Th3.假設(shè)A，B，C是任意集合，則：1） A×（BC）=A×BA×C2） （BC）×A=B×AC×A3） A×（BC）=A×BA×C4） （BC）&

33、#215;A=B×AC×ATh4.若|A|=n,|B|=m,則|A×B|=nm第3章 二元關(guān)系3.1基本概念 Df:1)A×B的子集稱為A到B的二元關(guān)系 2)A1×A2××An的子集稱為A1，A2An間的n元關(guān)系（n>2)3)若A1=A2=An=A 則n XA 的子集稱為A上的n元關(guān)系3.1.2二元關(guān)系1 Df RA×B,稱為A到B的二元關(guān)系A(chǔ)為前域，B為陪域RA×A，稱R為A上的二元關(guān)系d (R）=x|<x,y>Rr (R)=y|<x,y>R二 二元關(guān)系的表示1.列舉法2.

34、命題法 例：A=1,2,3,4,5 R=<x,y>|x+y4 =<1,1>,<2,2>,<1,2>,<1,3>,<2,1>,<3,1>3. 歸納法 例：設(shè)RN×N定義如下.<x,y> R ,i f f x<yxRy iff x<y基礎(chǔ)1）<0,1>R歸納2）<x,y>R,有<x,y+1>R,<x+1,y+1>R極小3）僅由1）和2）得到的序偶R4. 關(guān)系矩陣 RA×B,|A|=n,|B|=m MR=(Vij)n×

35、;m,如下0 <x,y>R Vij =1 否則稱為R的關(guān)系矩陣1 0 10 1 00 0 0MR= 5.關(guān)系圖y GR：<x,y>R xx=y，環(huán)3 性質(zhì) 1.自反性 1）Df.設(shè)RAxA若滿足xA,有<x,x>R,則稱R是A上的自反關(guān)系例：A=1，2，3R=<1,1>,<2,2>,<3,3>,<1,2>1) 集上的關(guān)系是自反的 x(x<x,x>), 永T2） 全關(guān)系是自反的 IA=<x,x>|xA,稱為A上的恒等關(guān)系 R自反，iff x(xA<x,x>R)3) 非集合上的關(guān)

36、系不是自反的 x(xA<x,x>),永F2） 特征 R自反iff xA,有<x,x>R Iff,IAR (集合特征）Iff，MR主對角線全“1”GR中每個(gè)點(diǎn)有自圈2. 反自反性3. 對稱性 1）Df.RA×A,x,yA,<x,y>R有<y,x>R,則稱R是A上的對稱關(guān)系 2）特征 MR:（1）允許有“1” (2) 關(guān)于主對角線對稱 GR：（1）允許有自圈 （2）不同結(jié)點(diǎn)若有邊必為雙向邊4. 反對稱性 1）Df.RA×A，對x,yA.若xRyyRx=>x=y,則稱R是A上的反對稱關(guān)系xy(<x,y>R<y

37、,x>Rx=y)永T xy<x,y>Rv<y,x>R,永T2） 特征 MR：（1）主對角線可有“1” （2）aij=11,aj=0或aij=1,aji=0或1GR：（1）允許有自圈 （2）不同結(jié)點(diǎn)若有邊必為單向邊A×A不是反對稱的IA 是反對稱的集上的關(guān)系是反對稱的非集上的關(guān)系也是反對稱的5. 傳遞性 1）Df:RA×Ax,y,zR,若xRy且yRz,則<x,Z>R,稱R是A上的傳遞關(guān)系2) 特征 MR，aij=1且ajk=1,有aik=1 GR,處處有捷徑3.2關(guān)系的合成 一.Df設(shè)RA×B，SB×C<x

38、,z>|yB,使<x,y>R<y,z>S稱為R與S的合成，記為R。SA=1，2，3 B=a,b C=4,5R =<1,4>,<1,b>,<2,a> S=<a,4>,<b,5>R 。S=<1,4>,<1,5>,<2,4>S 。R不存在 注：1）yran(R)dom(s),若ran(R)dom(R)=,則R。S 2）“?！辈粷M足交換律2 關(guān)系矩陣，關(guān)系圖 1，關(guān)系矩陣， 設(shè)RA×B，SB×C，MR。S=MR * MS1 00 11 11 00 0MRMS

39、2×23×2 MR。S=1 11 00 03×21 11 00 03×2MR * MS=2. 關(guān)系圖GR。STh1.R A×B,SB×C,TC×D,則：（R。S)。T=R。（S。T）Th2.設(shè)RA×B，S，TB×C,WC×D且ST，則：）R。SR。T）S。WT。WRS，iff：（）R，S有相同的前域和陪域（）作為集合有RSTh3，設(shè)RA×B，S，TB×C，WC×D）R。（ST）R。SR。T）（S）。W）R。（ST）R。SR。T）（ST）。RS。RT。R三關(guān)系的冪運(yùn)算

40、1、Df 設(shè)RA×A R自身合成n次（n0）稱為r的n次冪，記為Rn,定義如下：Rn = IA n=0Rn-1R n>0 *IA=<x,x>|xA例：A=1,2,3R=<1,2>,<2,3>,<3,1>則：R0=<1,1>,<2，2>,<3，3> R1=<1,2>,<2,3>,<3,1> R2=<1,3>,<2,1>,<3,2> R3=<1,1>,<2,2>,<3,3>=R0 R4=R1

41、, R5=R2一般的有 Rn=3=RN(n0)2、性質(zhì)Th4 RA×A RnRM=Rm+n (Rn)m=RnmTh5 設(shè)RA×A，若|A|=n,則存在i和j滿足:0i<j2n2使Ri=Rj證：構(gòu)造序列：R0，R1，R2，R2n2共有2n2+1個(gè)，而A不同的二元關(guān)系有2n2個(gè)根據(jù)鴿籠原理可知：i,j 0i<j2n2使Ri=Rj注：本定理對無限集不成立例：RI×I （I是整數(shù)集）定義如下：R=<x,y>|y=x+1R0=<x,y>|xI R1=<x,y>|y=x+1 R2=<x,y>|y=x+2 R3=<x,y>|y=x+3 Rn=<x,y>|y=x+nTh6 設(shè)RA×A若存在i<j使Ri=Rj，則i) 對所有KN,有Ri+k=Rj+kii) 對所有K，MN，有Ri+md+k=Ri+k d=j-iiii) 記s=R0，R1，R2，Rj-1,則對所有nN皆有RnSTh7 設(shè)RA×B, IA A×A, IBB×B則 IAR=R=RIB 若RA×A，則I