離散數(shù)學期末復習大綱PPT課件

1、.,1,離 散 數(shù) 學,期 末 總 復 習,.,2,復 習 時 注 意 準確掌握每個概念 靈活應用所學定理 注意解題思路清晰 證明問題時,先用反向思維(從結(jié)論入手)分析問題,再按正向思維寫出證明過程.,.,3,全書知識網(wǎng)絡：,.,4,總 復 習,復習重點 (注: 標有*的內(nèi)容,對網(wǎng)絡學院學生不作要求) 第一章 命題邏輯 1.聯(lián)結(jié)詞的定義(含義及真值表定義). 2.會命題符號化. 3.永真式的證明. 4.永真蘊涵式的證明,記住并能熟練應用常用公式. 5.等價公式的證明,記住并能熟練應用常用公式. 6.會寫命題公式的范式, *能應用范式解決問題. 7.熟練掌握命題邏輯三種推理方法.,.,5,第二章

2、 謂詞邏輯 1.準確掌握有關(guān)概念. 2.會命題符號化.(如P60題(2) 3.掌握常用的等價公式和永真蘊涵式.包括: 帶量詞的公式在論域內(nèi)展開式,量詞否定,量詞轄域擴充, 量詞分配公式. 4.會用等價公式求謂詞公式的真值.(如P66題(3) *5.會寫前束范式 6.熟練掌握謂詞邏輯推理. 第三章 集合論初步 1.集合的表示,冪集,全集,空集. 2.集合的三種關(guān)系(包含,相等,真包含)的定義及證明. 3.集合的五種運算及相關(guān)性質(zhì). *4.應用包含排斥原理.,.,6,第四章 二元關(guān)系 1.關(guān)系的概念,表示方法. 2.二元關(guān)系的 性質(zhì)的定義, 熟練掌握性質(zhì)的判斷及證明. 3.掌握關(guān)系的復合,求逆及閉

3、包運算(計算方法及有關(guān)性質(zhì)) 4.掌握等價關(guān)系的判斷,證明,求等價類和商集. *4.掌握相容關(guān)系定義,簡化圖和簡化矩陣,相容類,最大相容類,完全覆蓋. 5.偏序關(guān)系的判斷,會畫Hasse圖,會求一個子集的極小(大) 元,最小(大)元,上界與下界,最小上界及最大下界. 第六章 函數(shù) 1.函數(shù)的定義. 2.函數(shù)的類型, 會判斷,會證明. 3.會計算函數(shù)的復合(左復合),求逆函數(shù).知道有關(guān)性質(zhì). *4.了解集合的特征函數(shù),了解集合的基數(shù),可數(shù)集合.,.,7,第六章 代數(shù)系統(tǒng) 1.掌握運算的定義. 2.熟練掌握二元運算的性質(zhì)的判斷及證明. 3.掌握代數(shù)系統(tǒng)的同構(gòu)定義,會證明.了解同構(gòu)性質(zhì)的保持. 4.

4、了解半群,獨異點,*環(huán)和*域的概念. 5.熟練掌握群,子群,交換群(會證明), 了解循環(huán)群. *6,子群的陪集, Lagrange定理及其推論,(會應用). *第七章 格與布爾代數(shù) * 1.掌握格的定義,了解格的性質(zhì). * 2.會判斷格,分配格,有補格和布爾格, * 3.重點掌握兩個元素的布爾代數(shù)的性質(zhì)(10個). * 4.會寫兩個元素的布爾表達式的范式.(實質(zhì)是第一章的主析取和主合取范式).,.,8,第八章 圖論 1.掌握圖的基本概念.(特別注意相似的概念) 2.熟練掌握圖中關(guān)于結(jié)點度數(shù)的定理. (會應用) 3.無向圖的連通性的判定,連通分支及連通分支數(shù)的概念. 4.有向圖的可達性,強連通,

5、單側(cè)連通和弱連通的判定.求強 分圖,單側(cè)分圖和弱分圖. 5.會求圖的矩陣. 6.會判定歐拉圖和漢密爾頓圖. *7.會判定平面圖, 掌握歐拉公式. *8.了解對偶圖. 9.掌握樹的基本定義,v和e間的關(guān)系式.會畫生成樹,會求最 小生成樹.根樹的概念,完全m叉樹的公式,會畫最優(yōu)樹,*會 設計前綴碼.,.,9,總 復 習,復習重點 第一章 命題邏輯 1.聯(lián)結(jié)詞的定義(含義及真值表定義). 2.會命題符號化. 3.永真式的證明. 4.永真蘊涵式的證明,記住并能熟練應用常用公式. 5.等價公式的證明,記住并能熟練應用常用公式. 6.會寫命題公式的范式, *能應用范式解決問題. 7.熟練掌握命題邏輯三種推

6、理方法.,.,10,第一章 命題邏輯 1.聯(lián)結(jié)詞 定義了六個邏輯聯(lián)結(jié)詞，分別是： (1) 否定“” (2) 合取“” (3) 析取“” (4) 異或“ ” (5) 蘊涵“” (6) 等價“” 要熟練掌握這五個聯(lián)結(jié)詞在自然語言中所表示的含義以 及它們的真值表的定義。 ：否定 表示“不” ：合取 表示“不但,而且.”“并且” ：析取 表示“或者可兼取的或” ：異或 表示“或者不可兼取的或” ：蘊涵 表示“如果,則.” : 等價 表示“當且僅當”“充分且必要” 可以將這六個聯(lián)結(jié)詞看成六種“運算”。,.,11,聯(lián)結(jié)詞的定義(包括真值表和含義). 特別要注意： “或者”的二義性, 即要區(qū)分給定的“或”是

7、“可兼取的或”還是“不可兼取的或 ”。 “”的用法，它既表示“充分條件”也表示“必要條件”,即要弄清哪個作為前件,哪個作為后件.,P Q PQ PQ PQ PQ P Q,F F F F T T F,F T F T T F T,T F F T F F T,T T T T T T F,.,12,2.會命題符號化. 例如 P:我有時間. Q:我上街. R:我在家. 表示P是Q的充分條件: 如果p,則Q. 只要P,就Q. PQ 表示P是Q的必要條件: 僅當P,才Q. 只有P,才Q. QP 如果P,則Q;否則R. (PQ)(PR) 3.永真式的證明. 方法1.列真值表. (R(QR)(PQ)P 方法2.

8、用公式的等價變換,化簡成T. 例如證明(R(QR)(PQ)P是永真式. 證:上式(R(QR)(PQ)P(PQPQ) (R(QR) (PQ)P (公式的否定公式) (R(QR) (PQ)P) (結(jié)合律) (RQ)(RR)(PP)(QP) (分配律) (RQ)(QP) RQQP T (互補,同一律),.,13,4.永真蘊涵式的證明, 記住常用的公式. 永真蘊涵式: AB是永真式,則稱 A永真蘊涵B. (AB) 方法1.列真值表. 方法2.假設前件真,推出后件真. (即直接推理) 方法3.假設后件假,推出前件假.(即反證法) 例證明(P(QR)(PQ)(PR)是永真蘊涵式. 證:假設后件(PQ)(P

9、R)假, 則PQ為T, PR為F,于 是P為T,R為F, 進而又得Q為T. 所以QR為F, 所以前件 P(QR)為F. 所以(P(QR)(PQ)(PR)為 永真式. 對于給定一個題,究竟是用哪種方法,原則上哪種都可以. 但是哪個方法簡單,要根據(jù)具體題而定.,.,14,5.等價公式的證明,記住常用的公式. 方法1.列真值表. 方法2.用公式的等價變換. 例如:證明 P(QR)(PQ)R P(QR)P(QR) (PQ)R (PQ)R (PQ)R 注意:不論是證明永真蘊涵式,還是證明等價公式以及后邊 的求公式的范式,命題邏輯推理,都應用43頁的公式。 必須記憶一些常用的公式 如:P43表中的 永真蘊

10、涵式: I1, I3, I9, I10, I11, I12, I13, 等 價 公 式: E1 E16, E18, E19 , E20, E21,.,15,6.命題公式的范式 1)析取范式:A1A2.An (n1) Ai (i=1,2.n)是合取式. 2)合取范式:A1A2.An (n1) Ai (i=1,2.n)是析取式. 3)析取范式與合取范式的寫法. 4)小項及小項的性質(zhì). m3 m2 m1 m0 P Q PQ PQ PQ PQ 00 F F F F F T 01 F T F F T F 10 T F F T F F 11 T T T F F F,.,16,6)大項及其性質(zhì). M0 M1

11、 M2 M3 P Q PQ PQ PQ PQ 00 F F F T T T 01 F T T F T T 10 T F T T F T 11 T T T T T F 7)主析取范式: A1A2.An (n1) Ai (i=1,2.n)小項. 8)主合取范式: A1A2.An (n1) Ai (i=1,2.n)大項.,.,17,9).會寫主析取范式和主合取范式. 求下面命題公式的范式: A(P,Q,R) (PQ)R 方法1.列真值表. 主析取范式 A(P,Q,R) (PQ)R (PQR )(PQR )(PQR) (PQR )(PQR ) 主合取范式 A(P,Q,R) (PQ)R (PQR )(P

12、QR )(PQR),.,18,方法2.用公式的等價變換. 主析取范式;A(P,Q,R) (PQ)R (PQ)R (PQ)R (PQ(RR)(PP)(QQ)R) (PQR) (PQR)(PQR) (PQR)(PQR)(PQR) (PQR )(PQR )(PQR) (PQR )(PQR ) 主合取范式:A(P,Q,R) (PQ)R (PQ)R (PQ)R ( PR )(QR) ( P(QQ)R )(PP)QR) (PQR )(PQR)(PQR ),.,19,已知A(P,Q,R)的主析取范式中含有如下小項: m0,m3, m4,m5,m7求它的主合取范式. 解:A(P,Q,R)的主合取范式中含有大項

13、:M1 ,M2, M6 A(P,Q,R)(PQR )(PQR)(PQR) * 范式的應用 如P39習題(7),(8): 安排工作(排課表), 判斷比賽名次,攜帶 工具箱, ,.,20,7.會用三種推理方法,進行邏輯推理. 會用三個推理規(guī)則:P,T,CP 例如:證明 (AB)C)D(CD) AB 1.直接推理: D P CD P C T I10 Q, (PQ) P (AB)C P (AB) T I12 Q, PQ P AB T E8 (PQ)PQ,.,21,(AB)C)D(CD) AB 2.條件論證:適用于結(jié)論是蘊涵式. AB AB A P(附加前提) (AB)C P A(BC) T E19 B

14、C T I11 D P CD P C T I10 B T I12 AB CP,.,22,(AB)C)D(CD) AB 3.反證法: (AB) P(假設前提) AB T E9 (AB)C P C T I11 D P CD P C T I10 CC T I9,.,23,第二章 謂詞邏輯 1.準確掌握有關(guān)概念. 2.會命題符號化.(如P60題(2) 3.掌握常用的等價公式和永真蘊涵式.包括: 帶量詞的公式在論域內(nèi)展開式,量詞否定,量詞轄域擴充, 量詞分配公式. 4.會用等價公式求謂詞公式的真值.(如P66題(3) *5.會寫前束范式 6.熟練掌握謂詞邏輯推理.,.,24,第二章 謂詞邏輯 1.準確掌

15、握有關(guān)概念. 客體: 客體變元, 謂詞, 量詞, 量詞后的指導變元, 量詞的轄域, 約束變元與自由變元, 論域, 全總個體域, 謂詞公式(WFF), 命題函數(shù), 前束范式,.,25,2.會命題符號化.(如P60題(2) 命題的符號表達式與論域有關(guān)。當論域擴大時，需要添加用來表示客體特性的謂詞，稱此謂詞為特性謂詞。特性謂詞往往就是給定命題中量詞后邊的那個名詞。如“所有自然數(shù).” 、“有些大學生.”。 如何添加特性謂詞，這是個十分重要的問題，這與前邊的量詞有關(guān)。 如果前邊是全稱量詞，特性謂詞后邊是蘊含聯(lián)結(jié)詞“”； 如果前邊是存在量詞，特性謂詞后邊是合取聯(lián)結(jié)詞“”。 另外有些命題里有的客體在句中沒有

16、明確的量詞 ,而在 寫它的符號表達式時,必須把隱含的量詞明確的寫出來.,.,26,例如金子閃光,但閃光的不一定都是金子. 設: G(x):x是金子. F(x):x閃光. x(G(x)F(x)x(F(x)G(x) x(G(x)F(x)x(F(x)G(x) 沒有大學生不懂外語. S(x):x是大學生. F(x):x外語. K(x,y):x懂得y. x(S(x)y(F(y)K(x,y) x(S(x)y(F(y)K(x,y) 有些液體可以溶解所有固體. F(x):x是液體.S(x):x是固體.D(x,y):x可溶解y. x(F(x)y(S(y)D(x,y) 每個大學生都愛好一些文體活動。 S(x):x

17、是大學生,L(x,y):x愛好y, C(x):x是文娛活動， P(x):x是體育活動.) x(S(x)y(C(y)P(y)L(x,y),.,27,3.掌握常用的等價公式和永真蘊涵式.包括: 帶量詞的公式在論域內(nèi)展開式,量詞否定,量詞轄域擴充, 量詞分配公式. 設論域為a1,a2,.,an，則 1). xA(x)A(a1)A(a2).A(an) 2). xB(x)B(a1)B(a2).B(an) 1). xA(x)xA(x) 2). xA(x)xA(x) 1). xA(x)Bx(A(x)B) 2). xA(x)Bx(A(x)B) 3). xA(x)Bx(A(x)B) 4). xA(x)Bx(x)

18、B) 5). BxA(x)x(BA(x),.,28,6). BxA(x)x(BA(x) 7). xA(x)Bx(A(x)B) 8). xA(x)Bx(A(x)B) 1). x(A(x)B(x)xA(x)xB(x) 2). x(A(x)B(x)xA(x)xB(x) 3). x(A(x)B(x)xA(x)xB(x) 4). xA(x)xB(x)x(A(x)B(x) 4.會用等價公式求謂詞公式的真值.(如P66題(3) 例設論域為1,2,A(x,y):x+y=xy, 求xyA(x,y)的真值. xyA(x,y) xyA(x,y) yA(1,y)yA(2,y) (A(1,1)A(1,2)(A(2,1)

19、A(2,2) (TT)(TF) T,.,29,*5.將下面謂詞公式寫成前束范式 (xF(x,y)yG(y)xH(x,y) (xF(x,y)yG(y)xH(x,y) (去) xF(x,y) yG(y) xH(x,y) (摩根) xF(x,y) yG(y) xH(x,y) (量詞否定) xF(x,z) yG(y) tH(t,z) (變元換名) xyt(F(x,z) G(y) H(t,z) (轄域擴充),.,30,6.熟練掌握謂詞邏輯推理. 1).注意使用ES、US、EG、UG的限制條件,特別是ES,UG 2).對于同一個客體變元，既有帶也有帶的前提，去量詞時，應先去后去，這樣才可以特指同一個客體

20、c. 3).去量詞時，該量詞必須是公式的最左邊的量詞，且此量詞的前邊無任何符號，它的轄域作用到公式末尾。 下面的作法是錯誤的： 正確作法: xP(x)xQ(x) P xP(x)xQ(x) P P(c)xQ(x) US xP(x)xQ(x) T E 或xP(x)Q(c)ES xP(x)xQ(x) T E 實際上x的轄域擴充后 x(P(x)Q(x) T E 量詞改成為x P(c)Q(c) ES P(c)Q(c) TE,.,31,下面的作法是錯誤的： 正確作法: xP(x) P xP(x) P P(c) US xP(x) T E 實際上中量詞不是 P(c) ES x而是x xyP(x,y) P xy

21、P(x,y) P xP(x,c) ES yP(c,y) US 令P(x,y):y是x的生母， 顯然是個假命題 4).添加量詞時，也要加在公式的最左邊，(即新加的量詞前也無任何符號！)且其轄域作用到公式的末尾。 例如下面作法是錯誤的: xP(x)Q(c) P xP(x)yQ(y) EG,.,32,例如.證明下面推理的有效性. 證明: x(A(x)D(x) P A(a)D(a) ES A(a) T I D(a) T I x(A(x)(B(x)C(x) P A(a)(B(a)C(a) US B(a)C(a) T I x(A(x)(C(x)D(x) P A(a)(C(a)D(a) US C(a)D(a

22、) T I C(a) T I B(a) T I A(a)B(a) T I x(A(x)B(x) EG ,.,33,第三章 集合論初步 1.集合的表示,冪集,全集,空集. 2.集合的三種關(guān)系(包含,相等,真包含)的定義及證明. 3.集合的五種運算及相關(guān)性質(zhì). *4.應用包含排斥原理.,.,34,第三章 集合論初步 基本概念:集合與元素,子集與真子集, 空集, 全集, 冪集, 并集, 交集, 相對補集(差集), 絕對補集(補集) 1.集合的表示,元素與集合的屬于關(guān)系. 集合的三種表示方法: 枚舉法:一一列出集合中的元素. 謂詞描述法:用謂詞描述集合中元素的性質(zhì). 文氏圖:用一個平面區(qū)域表示. 2.

23、集合的三種關(guān)系(被包含,相等,被真包含)的定義及證明. AB x(xAxB) A=B ABBAx(xAxB) ABABABx(xAxB)x(xBxA),.,35,3空集,全集, 冪集 空集:無元素的集合. x是矛盾式. (空集是唯一的) 全集E:包含所討論所有集合的集合. (全集不唯一) xE是永真式 冪 集:由A的所有子集構(gòu)成的集合. P(A)=X|XA |P(A)|=2|A| 4.掌握集合的五種運算及相關(guān)性質(zhì). AB=x|xAxB xAB xAxB AB =x|xAxB xAB xAxB A-B =x|xAx B xA-B xAxB A =E-A=x|xExA=x|xA xAxA A-B=

24、A B AB=(A-B)(B-A)=x|(xAxB)(xBxA) AB=(AB)-(AB),.,36,例1.已知全集E=, AE,計算: a)P()P()=( ) b)P(A)P(A)=( ) c)P(E)-P()=( ) 解:a) 因為任何集合A, 都有 A A= 所以 P()P()= b) 因為A A , 即P(A) P(A) 所以 P(A)P(A)= c) P(E)=, = P()=P( )= , P(E)-P() )=,-, =,.,37,例2 證明各式彼此等價。 PQ (PQ)(PQ) c)AB=B, AB=A, AB, B A. 證明. AB=B x(xAB xB) x(xAB x

25、B)(xABxB) x(xAxB)xB)(xAxB)xB) x(xAxB)xB) x(xAxB)(xBxB)x(xAxB) x(xAxB) AB x(xAxB)x(xBxA) x(xBxA) B A 由 AB=B 得 A (AB)=A B A=A B 類似由AB=A, 可以推出AB=B 所以 AB=B AB=A 從而證得 AB=B, AB=A, AB, B A 彼此等價。,T,.,38,例3 證明: (A-B)-C=A-(BC) 方法1. (A-B)-C=(A B) C=A( B C) =A (BC)=A-(BC) 方法2.任取x(A-B)-C(xAxB)xC xA( xBxC) xA( xB

26、xC) xA( xBC) xAxBC xA-(BC) 所以(A-B)-C=A-(BC) 例4. 令全集E為信息學院的學生的集合, C表示計算機專 業(yè)學生的集合,M表示學習了離散數(shù)學的學生的集合,D表 示學習了數(shù)據(jù)結(jié)構(gòu)課學生的集合,F表示一年級的學生的 集合.用集合的關(guān)系式表達下面句子. “學習了離散數(shù)學和數(shù)據(jù)結(jié)構(gòu)課的學生,一定是計算機 專業(yè)的非一年級的學生”. 解. (MD)(CF),.,39,例4 .在什么條件下，下面命題為真？ a) (A-B)(A-C)=A 解.(A-B)(A-C)= (AB)(AC)=A(BC) = A(BC)=A-(BC)=A 所以滿足此式的充要條件是：ABC= b)

27、 (A-B)(A-C)= 解.(A-B)(A-C)= A-(BC)= 充要條件是：A BC c) (A-B)(A-C)= 解.(A-B)(A-C)= (AB)(AC)=A(BC) = A(BC)=A-(BC)= 充要條件是: A BC d) (A-B)(A-C)= 解. 因為 當且僅當A=B ，才有AB= 所以滿足此式的充要條件是: A-B=A-C,.,40,*例5. 用謂詞邏輯推理證明 對任何集合A、B、C，如果有AB且 BC ，則AC。 證明: x(xAxB)x(xBxA), x(xBxC)x(xCxB)x(xAxC) x(xCxA) x(xAxB)x(xBxA) P x(xAxB) T

28、I x(xBxA) T I x(xBxC)x(xCxB) P x(xBxC) T I xAxB US xBxC US xAxC T I x(xAxC) UG xBxA ES xB T I xA T I xC T I xCxA T I x(xCxA) EG x(xAxC) x(xCxA) T I,.,41,*有14位學生參加考試,9位同學數(shù)學得了優(yōu);5位同學物理 得了優(yōu);4位同學化學得了優(yōu);其中物理和數(shù)學都得優(yōu)的同 學有4人;數(shù)學和化學都得優(yōu)的同學有3人;物理和化學都得 優(yōu)的同學有3人;三門都得優(yōu)的同學有2人;問沒有得到優(yōu)的 有多少人?恰有兩門得優(yōu)的同學有多少人? 解.令A、B、C分別表示數(shù)學、

29、物理、化學得優(yōu)同學集合. 全集為E. 于是有 |E|=14 |A|=9 |B|=5 |C|=4 |AB|=4 |AC|=3 |BC|=3 |ABC|=2 |ABC|=|A|+|B|+|C|-|AB|-|BC|-|BC|+ |ABC| =9+5+4-4-3-3+2=10 于是得到優(yōu)的人數(shù)是10人. 沒有得到優(yōu)的人數(shù)是: 14-10=4 人 恰有兩門得優(yōu)的人數(shù): (|AB|-|ABC|)+ (|BC|-|ABC|)+(|BC|-|ABC|)=4-2+3-2+3-2=4,.,42,第四章 二元關(guān)系 1.關(guān)系的概念,表示方法. 2.二元關(guān)系的 性質(zhì)的定義, 熟練掌握性質(zhì)的判斷及證明. 3.掌握關(guān)系的復

30、合,求逆及閉包運算(計算方法及有關(guān)性質(zhì)) 4.掌握等價關(guān)系的判斷,證明,求等價類和商集. *5.掌握相容關(guān)系的概念,關(guān)系圖和矩陣的簡化,求相容類,最大相容類和完全覆蓋. 6.偏序關(guān)系的判斷,會畫Hasse圖,會求一個子集的極小(大) 元,最小(大)元,上界與下界,最小上界及最大下界. 注意本章證明題的證明過程的思路,.,43,一.關(guān)系的概念,表示方法,三個特殊關(guān)系. 1.集合的笛卡 爾 積 AB=|xAyB |A|=m,|B|=n |AB|=mn 設A=0,1，B=a,b，求AB 。 AB=, 2.二元關(guān)系的概念 定義1:設A、是集合,如果AB,則稱R是一個從A到 B的二元關(guān)系。如果 RAA,

31、則稱R是A上的二元關(guān)系. 如果|A|=m |B|=n 則可以確定2mn個從A到B的不同關(guān)系. 定義2:任何序偶的集合，都稱之為一個二元關(guān)系。,.,44,3.關(guān)系的表示方法 1). 枚舉法: 即將關(guān)系中所有序偶一一列舉出，寫在大括號內(nèi). 如:R=, 2).(描述法)謂詞公式法： 即用謂詞公式描述序偶中元素的關(guān)系。例如 R=|xy 3).有向圖法：,.,45,4).矩陣表示法：(實際上就是圖論中的鄰接矩陣) 設A=a1, a2, , am，B=b1, b2, , bn是個有限集， RAB，定義R的mn階矩陣 MR=(rij)mn，其中 4.三個特殊關(guān)系 1).空關(guān)系： AB，(或AA)，即無任何元

32、素的關(guān)系. 它的關(guān)系圖中只有結(jié)點,無任何邊；它的矩陣中全是0。 2).完全關(guān)系(全域關(guān)系) ： AB(或AA)本身是一個從A到B(或A上)的完全關(guān)系. 即含有全部序偶的關(guān)系。它的矩陣中全是1。,.,46,3). 恒等關(guān)系IA： IAAA,且IA =|xA稱之為A 上的恒等關(guān)系。例如A=1,2,3, 則IA =, A上的、完全關(guān)系AA及IA的關(guān)系圖及矩陣如下：,.,47,二.關(guān)系的性質(zhì): 熟練掌握性質(zhì)的判斷及證明. 1.自反性 定義:設R是集合A中的關(guān)系，如果對于任意xA都有 R (xRx)，則稱R是A中自反關(guān)系。即 R是A中自反的x(xAxRx) 2.反自反性 定義：設R是集合A中的關(guān)系，如果

33、對于任意的xA都有 R ，則稱R為A中的反自反關(guān)系。即 R是A中反自反的x(xAR) 3.對稱性 定義:R是集合A中關(guān)系,若對任何x, yA,如果有xRy,必有 yRx,則稱R為A中的對稱關(guān)系。 R是A上對稱的xy(xAyAxRy) yRx),.,48,4.反對稱性 定義:設R為集合A中關(guān)系,若對任何x, yA,如果有xRy,和 yRx,就有x=y,則稱R為A中反對稱關(guān)系 。 R是A上反對稱的xy(xAyAxRyyRx) x=y) xy(xAyAxyR)R) 5. 傳遞性 定義:R是A中關(guān)系，對任何x,y,zA,如果有xRy,和yRz,就 有xRz,則稱R為A中傳遞關(guān)系。 即R在A上傳遞 xy

34、z(xAyAzAxRyyRz)xRz) 這些性質(zhì)要求會判斷,會證明. 這里特別要注意的是, 這些定義都是蘊涵式, 所以當蘊涵 式當前件為假時 ,此蘊涵式為真,即此性質(zhì) 成立!,.,49,從關(guān)系的矩陣,從關(guān)系的有向圖,性質(zhì)判定:,.,50,判斷下面關(guān)系的性質(zhì):,.,51,.,52,關(guān)系性質(zhì)當證明方法歸納: 設R是A上關(guān)系， 1.證明R的自反性： 方法1 用自反定義證：任取 xA,證出R. 方法2 用恒等關(guān)系IA證：證出IA R. (見教材P119(2) 方法3 用自反閉包證：證出r(R)=R, 即RIA=R. 2.證明R的反自反性： 方法1 用反自反定義證：任取 xA,證出R. 3.證明R的對稱

35、性： 方法1 用對稱定義證： 任取 x,yA,設R, 證出 R. 方法2 用求逆關(guān)系證：證出 Rc=R. 方法3 用對稱閉包證：證出 s(R)=R, 即RRc =R.,.,53,4.證明R的反對稱性： 方法1 用定義1證： 任取 x,yA,設R, R.證出 x=y。 方法2用定義2證： 任取 x,yA,xy, 設R,證出R. 方法3 用定理證：證出 RRc IA . (見教材P118) 5.證明R的傳遞性： 方法1 用傳遞定義證： 任取 x,y,zA,設R,R, 證出 R. 方法2 用傳遞閉包證：證出 t(R)=R, 即 RR2R3. =R. 方法3用定理證：證出 (見教材P119(2) 同學

36、們可以根據(jù)具體情況,選用相應方法證明.其中必須掌 握的是用基本定義證明.,.,54,三.掌握關(guān)系復合,求逆及閉包運算(計算方法及性質(zhì)) (一)關(guān)系的復合 1.定義 :設RXY，SYZ，則 RSXZ。 RS=|xXzZy(yY RS) 2.計算方法(俗稱過河拆橋法) 枚舉法 R=, S=, RS=, 有向圖,.,55,矩陣 3.性質(zhì) 1).滿足結(jié)合律:RAB SBC TCD 則 R(ST)=(RS)T 2). RAB SBC TBC R (ST)=(RS)(RT) R (ST)(RS)(RT) 3). R是從A到B的關(guān)系，則 R IB=IA R=R 推論: RAA, 則 R IA=IA R=R

37、(IA是運算的幺元) 4).關(guān)系的乘冪 R0 =IA， RAA, Rm Rn = Rm+n (Rm)n =Rmn (m,n為非負整數(shù)),.,56,(二). 逆關(guān)系 1.定義 :設RXY，R的逆關(guān)系 RC=|R RC R 2. 計算方法 1). R=, RC =, 2). RC的有向圖:是將R的有向圖的所有邊的方向顛倒. 3). RC的矩陣 MRC =(MR)T 即為R矩陣的轉(zhuǎn)置 3.性質(zhì) 令R、S都是從X到Y(jié)的關(guān)系，則 1). (RC)C = R 2). (RS)C = RCSC 。 3). (RS)C = RCSC 。 4). (RS)C = RCSC 。,.,57,5). RS RC SC

38、 。 6). (R)C=RC 7).令R是從X到Y(jié)的關(guān)系，S是Y到 Z的關(guān)系，則 (R S)C= SC RC 。 8). R是A上關(guān)系，則 R是對稱的，當且僅當 RC =R R是反對稱的，當且僅當 RRC IA。,.,58,(三).閉包運算 1.定義：給定 A中關(guān)系R,若A上另一個關(guān)系R，滿足：RR； R是自反的(對稱的、傳遞的)； R是“最小的”，即對于任何A上自反(對稱、傳遞) 的關(guān)系R”, 如果RR”, 就有RR”。則稱R是R的自反 (對稱、傳遞)閉包。記作r(R)、(s(R) 、t(R) (reflexive、 symmetric、transitive) 2.計算方法 給定 A中關(guān)系R

39、 r(R)=RIA。 s(R)=RRC 。 t(R)=RR2R3. 。 t(R)=RR2.Rn *求t(R)矩陣的Warshall算法.,.,59,閉包的運算有三種形式: 如A=a.b.c R AA R=, a).集合形式. r(R)=RIA =, =, s(R)=RRC =, =, R2=, R3=, t(R)=RR2R3 =, , =,. , , ,.,60,b)有向圖形式 .,.,61,c)矩陣形式.,.,62,3.性質(zhì) 1). R是A上關(guān)系，則 R是自反的，當且僅當 r(R)=R. R是對稱的，當且僅當 s(R)=R. R是傳遞的，當且僅當 t(R)=R. 2). R是A上關(guān)系，則 R

40、是自反的，則s(R)和t(R)也自反。 R是對稱的，則r(R)和t(R)也對稱。 R是傳遞的，則r(R)也傳遞。 * 3).設R是A上關(guān)系，則 sr(R)=rs(R) tr(R)=rt(R) st(R)ts(R),.,63,四.等價關(guān)系 掌握等價關(guān)系的判斷,證明,求等價類和商集. 1.了解集合的劃分與覆蓋的概念. 例 X=1,2,3, A1=1,2,3, A2=1,2,3, A3=1,2,3, A4=1,2,2,3, A5=1,3 A1, A2 ,A3 ,A4 是覆蓋。 A1, A2 ,A3也是劃分。 2.等價關(guān)系定義 :設R是A上關(guān)系,若R是自反的、對稱的和傳遞 的，則稱R是A中的等價關(guān)系。

41、 3.等價關(guān)系R的有向圖:可能由若干個獨立子圖構(gòu)成的，每個獨立子圖都是完全關(guān)系圖。,.,64,4.等價類： 1).定義:R是A上的等價關(guān)系,aA,由a確定的集合aR aR=x|xAR 稱集合aR為由a形成的R等價類。 2).由等價關(guān)系圖求等價類：R圖中每個獨立子圖上的結(jié)點構(gòu)成一個等價類。不同的等價類個數(shù)=獨立子圖個數(shù)。 3).等價類性質(zhì) R是A上等價關(guān)系，任意a,b,cA 同一個等價類中的元素，彼此有等價關(guān)系R。 aRbR=， 當且僅當 R。 aR=bR 當且僅當 R。 .A中任何元素a,a必屬于且僅屬于一個等價類。 .任意兩個等價類 aR,bR, 要么aR=bR ，要么aRbR= 。 R的所

42、有等價類構(gòu)成的集合是A的一個劃分。,.,65,5.商集:定義：R是A上等價關(guān)系，由R的所有等價類構(gòu)成的集合稱之為A關(guān)于R的商集。記作A/R。即 A/R=aR |aA 6.商集應用. 1)按照集合的等勢關(guān)系(是等價關(guān)系)“”對集合族S進行劃分，得到商集S/，進而得到基數(shù)類的概念。 S=0,1,1,a,2,0,1,a,b,3,0,1,2,N,I,R,. S/=0,1,2,3,N,R,. 2).無向圖結(jié)點之間的連通關(guān)系是個等價關(guān)系. 令G=是無向圖, R是V上連通關(guān)系, 即 R=|u和v是連通的 例. 給定圖G如右上圖所示: V/R=a,b,g,c,d,e,f,h,.,66,3).圖的同構(gòu)關(guān)系是個等

43、價關(guān)系. 令上述圖構(gòu)成的集合A=a,b,c,d,e,f,g,h,i,j,求商集A/. A/=a,h,b,i,c,e,d,f,g,j,.,67,練習1.R和S都是A上等價關(guān)系,下面哪個是A上等價關(guān)系? 證明或舉反例說明. a) RS b) RS c) R (即AA-R) d) R-S e)R2 f) r(R-S) e) Rc 解.a) c) d) f)不是. 請看反例:,.,68,b) RS是等價關(guān)系. 證明：1. 證明RS的自反性 方法1 用自反定義證：任取 xA, (證出RS) 因R和S都自反，所以有R，S，于是有 RS，所以RS也自反。 方法2 用恒等關(guān)系IA證：(證出IA R) 因R和S

44、都自反，所以 IA R ，IA S，所以IA RS 所以RS也自反。 方法3 用自反閉包證： (證出r(RS)=RS, 即 (RS)IA= RS) 因R和S都自反，所以r(R)=R, r(S)=S, r(RS)=(RS)IA= (RIA)(SIA) =r(R)r(S)=RS 所以RS也自反。,.,69,2.證明RS的對稱性： 方法1 用對稱定義證： 任取 x,yA,設RS, (證出 RS.) 則R，S，因為R和S對稱，所以有 R，S，于是RS。RS對稱。 方法2 用求逆關(guān)系證：(證出 (RS)c=RS.) 因為R和S對稱，所以有Rc=R， Sc=S，而 (RS)c=RcSc= RS ， RS對

45、稱。 方法3 用對稱閉包證： (證出 s(RS)=RS, ) 因為R和S對稱，所以s(R)=R,s(S)=S s(RS)= (RS)(RS)c =(RS)(RcSc) =(RRc)(RSc)(SSc)(SRc) =(s(R)(RSc)(s(S)(SRc) =(R(RSc)(S(SRc)=RS (吸收律) RS對稱。,.,70,3.證明RS的傳遞性： 方法1 用傳遞定義證：任取 x,y,zA, 設RS,RS, (證出RS) RSRS RSRS (RR)(S S) RS （因為R、S傳遞） RS 所以RS傳遞。 所以RS是A上等價關(guān)系.,.,71,e)證明. R2是等價關(guān)系. 方法1.由P119習

46、題(3)得:如果R自反和傳遞,則R2 =R, 所以 R2也是等價關(guān)系. 方法2.證R2自反: 任取aA,因為R自反,所以R,根據(jù)關(guān)系的復合得, R R, 即R2,所以R2自反。 證R2對稱: (R2)c=(Rc)2=R2 (由R對稱得Rc=R) R2對稱 證R2傳遞: 任取a,b,cA,設有R2,R2, 根據(jù)關(guān)系的復合得, (dARR)(eARR) , 由于R傳遞,所以有R,R, R2 所以R2傳遞。 最后得R2是等價關(guān)系。,.,72,g). R是A上等價關(guān)系,則Rc也是A上等價關(guān)系. 證明1) 證Rc自反。 因為任取xA,因R自反，所以R, Rc 2) R對稱，證Rc也對稱。 因為R對稱，所

47、以Rc =R Rc也對稱。 3) R傳遞，證Rc也傳遞。 方法1 .任取x,y,zA, 且有Rc ,Rc, 于是 R ,R，因R傳遞，R,于是有 Rc， Rc傳遞。 方法2. t(Rc)=Rc(Rc)2(Rc)3 = Rc(R2)c(R3)c= (RR2R3)c = (t(R)c=Rc 所以Rc傳遞。 所以Rc是A上等價關(guān)系.,.,73,練習2.五.設X=1,2,3 Y=1,2, 在X的冪集P(X)上定義二元關(guān)系R如下: 對于任何A,BP(X), ARB 當且僅當 AY=BY 1.畫出關(guān)系R的有向圖. 2.R是等價關(guān)系嗎?如果是,請寫出商集P(X)/R. 如果不是請說明原因 解.1.關(guān)系R的有

48、向圖. 2. 從R有向圖看出R有自反,對稱和傳遞性,故是等價關(guān)系 P(X)/R=,1,2,1,2,3,1,3,2,3,1,2,3,.,74,*五.相容關(guān)系 1.定義:給定集合X上的關(guān)系r, 若r是自反的、對稱的,則r是A上相容關(guān)系。 2.圖的簡化：不畫環(huán)； 兩條對稱邊用一條無向直線代替。 3.矩陣的簡化：因為r的矩陣是對稱陣且主對角線全是1， 用下三角矩陣(不含主對角線)代替r的矩陣。 4.相容類：設r是集合X上的相容關(guān)系，CA,如果對于C 中任意兩個元素x,y有r ,稱C是r的一個相容類. 5. 最大相容類:設r是集合X上的相容關(guān)系，C是r的一個相容類，如果C不能被其它相容類所真包含，則稱C

49、是一個最大相容類。-最大完全多邊形. 6.完全覆蓋：r是中的相容關(guān)系，由r的所有最大相容類 為元素構(gòu)成的集合，稱之為X的完全覆蓋。記作Cr(X)。,.,75,練習.已知X=1,2,3,4,5,6,7上的相容關(guān)系r的交換矩陣為: 求完全覆蓋Cr(X) 解.先畫出r的簡化圖, 如右上圖所示. 于是得完全覆蓋為: Cr(X)=1,2,4,5,1,3,7,1,3,4,7,6,1,2,3, 4, 5, 6,7,.,76,五.偏序關(guān)系判斷,會畫Hasse圖,會求一個子集的極小 (大)元,最小(大)元,上界與下界,最小上界及最大下界. 1. 定義：R是A上自反、反對稱和傳遞的關(guān)系，則稱R 是A上的偏序關(guān)系。

50、并稱是偏序集。 2. x與y是可比較的：是偏序集，x,yA，如果要 么xy,要么yx, 則稱x與y是可比較的。 3.定義：是偏序集，任何x,yA，如果x與y都是可比較的，則稱是全序關(guān)系(線序、鏈)。 4.偏序集Hasse圖的畫法： 令是偏序集， 1).用“ ”表示A中元素。 2).如果xy,且xy，則結(jié)點y要畫在結(jié)點x的上方。 3). 如果xy,且y蓋住x，x與y之間連一直線。 4). 從最下層結(jié)點(全是射出的邊與之相連，逐層向上畫，直到最上層結(jié)點(全是射入的邊與之相連)。,.,77,例如,.,78,5. 重要元素 y是B的極小元y(yBx(xBxyxy) (在B中沒有比y更小的元素了，y就是

51、極小元) y是B的極大元y(yBx(xBxyyx) (在B中沒有比y更大的元素了，y就是極大元) y是B的最小元y(yBx(xB yx) (最小元y是B中元素，該元素比B中所有元素都小) y是B的最大元y(yBx(xB xy) (最大元y是B中元素，該元素比B中所有元素都大) y是B的上界y(yAx(xB xy) (上界y是A中元素，該元素比B中所有元素都大) y是B的下界y(yAx(xB yx) (下界y是A中元素，該元素比B中所有元素都小),.,79,y是B的上界，并且對B的所有上界x,都有yx,則 稱y是B的最小上界(上確界)，記作LUB B=y 。 (即y是上界中最小的。如果B有上確界

52、，則是唯一的) y是B的下界，并且對B的所有下界x,都有xy,則 稱y是B的最大下界(下確界)，記作GLB B=y 。 (即y是下界中最大的。如果B有上確界，則是唯一的) 例如 B=2,3,6 B的極小元:2,3 極大元: 6 最小元:無 最大元:6 下界:1 上界:6,12,18 下確界:1 上確界:6,.,80,第六章 函數(shù) 1.函數(shù)的定義. 2.函數(shù)的類型, 會判斷,會證明. 3.會計算函數(shù)的復合(左復合),求逆函數(shù).知道有關(guān)性質(zhì). *4.了解集合特征函數(shù)和模糊子集的表示及計算. *5.了解自然數(shù)的定義, 集合的等勢定義, 集合基數(shù)的定義, 可數(shù)集定義,可數(shù)集的基數(shù), 連續(xù)統(tǒng)基數(shù), 基數(shù)

53、的比較.,.,81,一.概念 1.定義：X與Y集合，f是從X到Y(jié)的關(guān)系，如果任何xX， 都存在唯一yY，使得f,則稱f是從X到Y(jié)的函數(shù)， (變換、映射)，記作f:XY. 如果f:XX是函數(shù), 也稱f是X上的函數(shù). 要求會判斷某些給定關(guān)系是否是函數(shù). 2.函數(shù)相等: f:AB, g:CD,f=gA=CB=Df(x)=g(x) 3.從X到Y(jié)函數(shù)的集合YX： YX =f| f:XY YX ：它是由所有的從X到Y(jié)函數(shù)構(gòu)成的集合. 4.特殊函數(shù) 1). 常值函數(shù)：函數(shù)f:XY ，如果y0Y, 使得對xX, 有f(x)=y0 , 即ran f=y0 ,稱f是常值函數(shù)。 2).恒等函數(shù)：恒等關(guān)系IX是X到X

54、函數(shù)，即IX:XX,稱 之為恒等函數(shù)。顯然對于xX，有 IX(x)=x 。,.,82,5.函數(shù)的類型, 會判斷,會證明. 1).滿射的：f:XY是函數(shù)，如果 Rf=Y,則稱f 是滿射的。 證明方法:任取yY, 看是否能夠找到對應的自變元 xX, 使得 y=f(x). 2).映內(nèi)的：f:XY是函數(shù)，如果 RfY 則稱f 是映內(nèi)的。 3).入射的：f:XY是函數(shù)，如果對于任何x1,x2X, 如果 x1x2 有f(x1)f(x2),(或者若f(x1)=f(x2),則x1=x2),則稱f 是 入射的，也稱f 是單射的，也稱f 是一對一的。 證明的方法:如定義中所說. 4).雙射的：f:XY是函數(shù)，如果

55、 f 既是滿射的，又是 入射的，則稱 f 是雙射的，也稱f 是一一對應的。 雙射是個重要概念, 我們用雙射定義了如下概念: 集合的等勢關(guān)系“”; 代數(shù)系統(tǒng)的同構(gòu)關(guān)系“” 圖的同構(gòu)關(guān)系“”,.,83,練習題:R是實數(shù)集合，給定R上的五個關(guān)系如下: R1=|x=y2 R2=|y=x+6 R3=|y=(x-1)-1 R4=|y=2x R5=|x2+y2=4 上述五個關(guān)系中，哪些 是從R到R的函數(shù)。如果是函數(shù)， 說明它是屬于什么類型的（指滿射、入射、雙射）。 如果不是函數(shù)，說明理由。 解.R1不是從R到R的函數(shù), x是負數(shù)時 無定義,另外當x0時,有兩個y值與之對應. R2是從R到R的函數(shù),是雙射的.

56、 R3不是從R到R的函數(shù),因為x=1時,無定義. R4是從R到R的函數(shù),是入射的,不是滿射的. R5不是從R到R的函數(shù),因為|x|2時,無定義.|x|2時 對應的函數(shù)值不唯一.,.,84,二.會計算函數(shù)復合(左復合),求逆函數(shù).知道有關(guān)性質(zhì). 1.函數(shù)的復合 1)定義: f:XY, g:YZ是函數(shù),則定義 g f =|xXzZy(yY fg) 則稱 g f 為f與g的復合函數(shù)(左復合). 注意:這里把g寫在f的左邊了.所以叫左復合. g f :XZ,即 g f 是X到Z的函數(shù).這樣寫是為了 照顧數(shù)學習慣: g f(x)=g(f(x) xX 2).復合函數(shù)的計算 計算方法同復合關(guān)系的計算. 但要

57、注意是左復合. 3).函數(shù)復合的性質(zhì) (1).滿足可結(jié)合性。 f:XY, g:YZ, h:ZW 是函數(shù),則 (h g)f=h(g f),.,85,(2).定理5-2.2 f:XY, g:YZ是兩個函數(shù), 則 a).如果f和g是 滿射的，則 g f 也是滿射的； b).如果f和g是入射的，則 g f 也是入射的； c).如果f和g是雙射的，則 g f 也是雙射的。 (3).如果gf是滿射的，則g是 滿射的； 如果gf是入射的，則 f 是入射的； 如果gf 是雙射的，則f是入射的和g是 滿射的。 (4). f:XY是函數(shù), 則 f IX = f 且 IY f = f 。 f:XX是函數(shù), 則 f IX=IX f=f 。IX是運算“”的幺元.,.,