自考離散數學期末復習

1、離散數學期末復習1.1 1.1 命題概念命題：具有唯一真值的陳述句1.1 1.1 命題概念練習：1.下列句子為命題的是（ ）A.全體起立！ B. X=0 C. 我在說謊 D.張三生于1886年的春天2.下列句子不是命題的是（ ）A.中華人民共和國的首都是北京 B.張三是學生 C.雪是黑色的 D.太好了！DD1.2 1.2 復合命題與聯結詞常用的聯結詞（1）否定定義1.2.1 設P為一命題，P的否定是一個新的命題，記作P。 “”表示命題的否定. P的真值： 若P為T， P為F；若P為F， P為T P PFTTF1.2 1.2 復合命題與聯結詞常用的聯結詞（2）合取定義1.2.2 兩個命題P和Q的

2、合取是一個復合命題，記作PQ。稱作合取聯結詞， 在自然語言中的“并且”、“和”、“既.又.”、“不僅.而且.”、“雖然.但是.”等都可以符號化為 例1 2是素數和偶數 設P：2是素數，Q:2是偶數，故上述命題可表述為PQ 例2 王乙工作努力且身體好。 設P:王乙工作努力，Q:王乙身體好，故上述命題可表述為PQ 1.2 1.2 復合命題與聯結詞常用的聯結詞（2）合取PQ的真值 當且僅當P與Q同時為T時，PQ為T.其余情況，PQ為FP QPQT TTT FFF TFF FF1.2 1.2 復合命題與聯結詞常用的聯結詞（2）合取注意: 命題聯結詞“合取”可將兩個互為否定的命題聯結在一起：PP 此時其

3、真值永為F P PPPT FFF T F1.2 1.2 復合命題與聯結詞常用的聯結詞（3）析取定義1.2.3 兩個命題P, Q的析取是個復合命題，記作PQ。稱作析取聯結詞， 與自然語言中的“或”有些相似例4 王強是這次校運動會的跳高或100米短跑的冠軍。 設P: 王強是這次校運動會的跳高冠軍； Q:王強是這次校運動會的100米短跑的冠軍。 所以本例可描述為： PQ 1.2 1.2 復合命題與聯結詞常用的聯結詞（3）析取PQ的真值 當且僅當P與Q同時為F時，PQ為F.否則，PQ為TP QPQT TTT FTF TTF FF1.2 1.2 復合命題與聯結詞常用的聯結詞（4）條件定義1.2.4 給定

4、兩個命題P, Q，其條件命題是一個復合命題，記作PQ。其中P為前件，Q為后件。PQ讀作“如果P那么Q”，“若P則Q”例6 如果我有就學機會，那么我必用功讀書。 設P: 我有就學機會； Q:我必用功讀書。 所以本例可描述為： PQ 1.2 1.2 復合命題與聯結詞常用的聯結詞（4）條件PQ的真值 當且僅當P的真值為T，Q的真值為F時，PQ 為F.其余情況，PQ為T P QPQT TTT FFF TTF FT1.2 1.2 復合命題與聯結詞常用的聯結詞（5）雙條件定義1.2.6 給定兩個命題P, Q，其復合命題PQ稱作雙條件命題，讀作P當且僅當Q。例 兩個三角形全等，當且僅當它們的三組對應邊相等。

5、 設P: 兩個三角形全等； Q:它們的三組對應邊相等。 所以本例可描述為： PQ 1.2 1.2 復合命題與聯結詞常用的聯結詞（5）雙條件PQ 的真值 當P與Q的真值為相同時，PQ 為T.其余情況，PQ 為F P QPQT TTT FFF TFF FT1.2 1.2 復合命題與聯結詞1.2 1.2 復合命題與聯結詞1.3 1.3 命題公式與真值表真值表定義1.3.3 設P為一命題公式，P1 , P2, P3,.Pn 為出現在P中的所有命題變元， 對 P1 , P2, P3,.Pn 指定一組真值稱為對P的一種指派。若指定的一種指派，使P的值為真，則稱這組值為成真指派；若指定的一種指派，使P的值為

6、假，則稱這組值為成假指派。1.3 1.3 命題公式與真值表1.3 1.3 命題公式與真值表等價式定義1.3.4 給定兩個命題公式A和B，設P1 , P2, P3,.Pn為所有出現于A和B中的原子變元，若給P1 , P2, P3,.Pn任一組真值指派，A和B的真值都相同，稱A和B是等價的，記作AB。從上述真值表的例子中，可以知道： P Q PQ (PQ) ( P Q)PQ 上述二式以后經常作為等值公式直接應用。 1.3 1.3 命題公式與真值表定義1.3.5 設A為一命題公式，若A在它的各種指派情況下，其取值均為真, 則稱公式A為重言式或永真式。定義1.3.6 設A為一命題公式，若A在它的各種指

7、派情況下，其取值均為假, 則稱公式A為矛盾式或永假式。定義1.3.7 設A為一命題公式，若A在它的各種真值指派下至少存在一組成真指派，則稱A是可滿足式。1.3 1.3 命題公式與真值表對合律 PP冪等律 P PP, P PP結合律 (P Q) RP (Q R), (P Q) RP (Q R)交換律 P QQ P, P QQ P分配律 P (Q R)(P Q) (P R), P (Q R)(P Q) (P R)1.3 1.3 命題公式與真值表吸收律 P (P Q)P, P (P Q)P德摩根律 (P Q)PQ, (P Q)PQ同一律 P FP , P TP零律 P TT, P FF否定律 P P

8、T, PPF兩個等值公式：兩個等值公式： P Q PQ (PQ) ( P Q)PQ 1.4 1.4 等價變換與蘊含式等價變換定理1.4.1 設 X 是合式公式 A 的子公式，若有Y也是一個合式公式，且XY，如果將A中的X用Y置換， 得到公式B,則 AB。例：證明Q(P(PQ)QP 證：設A：Q(P(PQ)， 因為P(PQ)P（吸收律） 故B:QP，即AB1.4 1.4 等價變換與蘊含式等價變換判斷命題公式是重言式或矛盾式真值表等價變換1.4 1.4 等價變換與蘊含式1.5 1.5 最小聯結詞組與范式最小聯結詞組（1）由PQ(PQ)(QP)，故可把包含的公式等價變換為包含“”和“”的公式。（2）

9、由PQPQ，故可把包含的公式等價變換為包含“”和“”的公式。（3）由PQ(PQ)，PQ(PQ)說明“”與“”可以相互交換。故由“”“”“”“”“”這5個聯結詞中若干個組成的命題公式，必可由,或,組成的命題公式所替代。我們把,及,稱為命題公式的最小聯結詞組。1.5 1.5 最小聯結詞組與范式范式定義1.5.1 一個命題公式稱為合取范式，當且僅當它具有形式 A1 A2.An （n1）其中A1 ，A2，.，An 都是由命題變元以其否定組成的析取式。例如：（PQ）（PR）（PQ）是一個合取范式1.5 1.5 最小聯結詞組與范式范式定義1.5.2 一個命題公式稱為析取范式，當且僅當它具有形式 A1 A2

10、.An （n1）其中A1 ，A2，.，An 都是由命題變元以其否定組成的合取式。例如：（PQ）（PR）（PQ）是一個析取范式1.5 1.5 最小聯結詞組與范式范式一個命題公式的合取范式或析取范式不是唯一的。1.5 1.5 最小聯結詞組與范式主范式定義1.5.3 n個命題變元的合取式，稱作布爾合取或小項，其中每個變元與它的否定不能同時存在，但兩者必須出現僅且出現一次。例如：2個命題變元P和Q，其小項為： PQ, PQ, PQ, PQ 3個命題變元P，Q和R，其小項為： PQR, PQR, PQR, PQR, PQR, PQR, PQR, PQR1.5 1.5 最小聯結詞組與范式小項的表示一般來說

11、，n個命題變元有2n個小項，n個命題變元的小項，將命題變元看成1，其否定看成0，則每個小項對應著一個二進制數。例： m000= PQR m001=PQR m010=PQR m011=PQR m100=PQR m101=PQR m110=PQR m111=PQR1.5 1.5 最小聯結詞組與范式主范式定義1.5.4 對于給定的命題公式，如果有一個等價公式，它僅由小項的析取所組成，則該等價式稱作原式的主析取范式。定理1.5.1 在真值表中，一個公式的真值為T的指派所對應的小項的析取，即為此公式主析取范式。定理1.5.2 任意含n個命題變元的非永假命題公式，其主析取范式是唯一的。1.5 1.5 最小

12、聯結詞組與范式主范式定義1.5.5 n個命題變元的析取式，稱作布爾析取或大項，其中每個變元與它的否定不能同時存在，但兩者必須出現僅且出現一次。例如：2個命題變元P和Q，其大項為： PQ, PQ, PQ, PQ 3個命題變元P，Q和R，其大項為： PQR, PQR, PQR, PQR, PQR, PQR, PQR, PQR1.5 1.5 最小聯結詞組與范式大項的表示與小項情況類似，每個大項也可以編碼。具體方法：首先將n個命題變元排序，將每個命題變元對應成0，其否定對應成1，則可將2n個大項按二進制數編碼，記為Mi，其下標是由二進制化為十進制數。例： 2個命題變元P,Q的命題公式，應有4個大項：

13、PQ=M00=M0 PQ=M01=M1, PQ=M10=M2, PQ=M11=M3 1.5 1.5 最小聯結詞組與范式主范式定理1.5.3 在真值表中一個公式的真值為F的指派所對應的大項的合取，即為此公式主合取范式。定理1.5.2 任意含n個命題變元的非永真命題公式A，其主合取范式是唯一的。1.5 1.5 最小聯結詞組與范式主范式從A的主析取范式求主合取范式步驟：（1）求出A的主析取范式中為包含小項的下標（2）把（1）中求出的下標寫成對應大項。（3）做（2）中寫成的大項合取，即為A的主合取范式。1.5 1.5 最小聯結詞組與范式主范式例：公式A：（pq）（qp） ，則公式A的主合取范式為例：（

14、PQ）Q =m01m11 （PQ）Q =M00M10210 ，331，20，1.5 1.5 最小聯結詞組與范式主范式根據主范式的定義和定理,可以判定含n個命題變元的公式: （1）若A可化為與其等價的,含2n個小項的主析取范式,則A為永真式. （2）若A可化為與其等價的,含2n個大項的主合取范式,則A為永假式. （3）若A的主析取范式不含2n個小項,或A的主合取范式不含2n個大項,則A為可滿足式.判斷公式類型： 1，真值表 2.等值演算 3.主范式1.4 1.4 等價變換與蘊含式1.4 1.4 等價變換與蘊含式蘊含式定理1.4.2 設A,B為兩命題公式，AB，當且僅當AB為一個重言式。定義1.4

15、.1 當且僅當PQ是一個重言式時，我們稱“P蘊含Q”，并記作P Q。P Q稱作P蘊含Q或蘊含式，亦稱作永真條件式。 1.4 1.4 等價變換與蘊含式蘊含式（1）化簡式 PQ P. PQ Q（3）附加式 P PQ（4）變形附加式 P PQ，Q PQ（5）變形簡化式 （PQ） P;（PQ） Q （6）假言推論 P（PQ） Q（7）拒取式 Q（PQ） P（8）析取三段論 P(PQ) Q（9）條件三段論 （PQ）(QR) PR（10）雙條件三段論 （PQ）（QR） PR（11）合取構造二難 （PQ）（RS）（PR） QS（12）析取構造二難 （PQ）（RS）（PR） QS（13）前后件附加 PQ （P

16、R）（QR）; PQ （PR）（QR） 1.6 1.6 推理理論有效推理：從前提出發(fā)，根據確認的推理規(guī)則推導出一個結論，這個過程叫有效推理。定義1.6.1 設H1，H2，.，Hn，C是命題公式，當且僅當H1H2.Hn C，稱C是一組前提的有效結論。1.6 1.6 推理理論判別有效結論的方法：（3）構造論證法在推理過程中，如果命題變元很多，用真值表、等值演算法及主范式法等作推理證明都很不方便。表1.6.2及表1.6.3的公式可直接應用。常用的推理規(guī)則：（1）前提引入規(guī)則：在證明的任何步驟上，都可以引入前提，簡稱P規(guī)則。（2）結論引入規(guī)則：在證明的任何步驟上，所證明的結論都可作為后續(xù)證明的前提。（

17、3）置換規(guī)則：在證明的任何步驟上，命題公式中的任何子命題公式都可以用與之等值的命題公式置換（表1.6.2，表1.6.3），記為T規(guī)則。1.6 1.6 推理理論1.6 1.6 推理理論判別有效結論的方法：（3）構造論證法定理 1.6.2 若H1H2.Hn C為永假式，則H1H2.Hn C成立。 附加前提法： 把結論的否定作為前提，推出F。1.6 1.6 推理理論定理1.6.3 （CP規(guī)則 ） 若H1H2.Hn R C,則H1H2.Hn RC。2.1 2.1 謂詞的概念與表示客體：指可以獨立存在的對象，一個具體的事物，一個抽象的概念謂詞：指明客體性質或指明客體之間關系2.2 2.2 量詞與合式公式

18、量詞：表示數量的詞量詞有2種：1.全稱量詞：對應日常語言中的“一切”“任意的”“所有”“凡是”等詞。用符號“ ”表示。 表示對個體域里所有的x，而 表示個體域里所有個體，都有性質F。2.存在量詞：對應日常語言中的“存在的”“有一個”“至少有一個”等詞。用符號“ ”表示。 表示存在個體域中的個體，而 表示存在個體域中的個體具有性質F。x)(xxFx)(xxF2.2 2.2 量詞與合式公式在全稱量詞中，特性謂詞是條件式的前件。在存在量詞中，特性謂詞后跟一個合取項。2.2 2.2 量詞與合式公式2.2 2.2 量詞與合式公式定義2.2.1 由一個或幾個原子命題函數以及邏輯聯結詞組合而成的表達式稱為復

19、合命題函數。定義2.2.2 謂詞演算的合式公式，可由下述各條組成（合式公式A記為WffA）：（1）原子謂詞公式是合式公式。（2）若A是合式公式，則A是一個合式公式。（3）若A和B都是合式公式，則（AB），（AB），（AB），（AB）是合式公式。（4）如果A是合式公式，x是A中出現的任何變元，則 和 都是合式公式。（5）只有經過有限次應用規(guī)則（1）（2）（3）（4）所得到的公式是合式公式。Ax)(Ax)(2.2 2.2 量詞與合式公式2.2 2.2 量詞與合式公式定義2.2.3 給定謂詞合式公式A，其中一部分公式形式為 或稱量詞 ， 后面所跟的x為指導變元或作用變元。稱B(x)為相應量詞的轄域（

20、或作用域）。 在轄域中，x的一切出現稱為約束出現。B(x)中除去約束出現的其他變項的出現為自由出現。)()(xBx)()(xBx2.3 2.3 謂詞演算的等價式與蘊含式當確定論域后 ，與 都是一個特定的命題。例如 表示x是個大學生，論域是a,b,c,則： 即是S(a)S(b)S(c) 即是S(a)S(b)S(c)例：如果論域是集合a,b,c,試消去下面公式中的量詞：解：原式 (R(a)R(b)R(c)(S(a)S(b)S(c)()(xPx)()()()(xSxxRx)()(xPx)()(xSx)()(xSx)()(xSx2.3 2.3 謂詞演算的等價式與蘊含式2.3 2.3 謂詞演算的等價式與

21、蘊含式2.3 2.3 謂詞演算的等價式與蘊含式定義2.3.1 給定任何兩個謂詞公式WffA和WffB，設它們有共同的個體域E，若對A和B的任一組變元進行賦值，所得命題的真值相同，則稱謂詞公式A和B在E上是等價的，并記作BA 2.3 2.3 謂詞演算的等價式與蘊含式2.3 2.3 謂詞演算的等價式與蘊含式定理 2.3.1 量詞與否定聯結詞之間有如下關系：（1）（2）)()(xQxxxQ)()(xQxxxQ2.3 2.3 謂詞演算的等價式與蘊含式2.4 2.4 前束范式定義2.4.1 一個公式，如果量詞均在全式的開頭，它們的作用域，延伸到整個公式的末尾，則該公式叫做前束范式。2.5 2.5 謂詞演

22、算的推理理論（1）全稱指定規(guī)則（US）：由 得到P(c)。 P是謂詞，而c是論域中的任意某個個體，如果論域中全部個體有P(x)，那么全稱指定規(guī)則有結論P(c)（2）全稱推廣規(guī)則（UG）：由P(c)得到 如果能夠證明對論域中任一客體x斷言P(x)都成立，則全稱推廣規(guī)則可得到結論（3）存在指定規(guī)則（ES）：由 得到P(c) C是論域中某些個體（不是任意存在的）（4）存在推廣規(guī)則（EG）：由P(c)得到)()(xPx)()(xPx)()(xPx)()(xPx)()(xPx2.5 2.5 謂詞演算的推理理論3.1 3.1 集合的基本概念集合：把一些事物匯集到一起組成一個整體例：教室內的桌椅，圖書館全部

23、藏書，直線上的點的集合，中國的全部縣市的集合集合常用的表示方法：（1）列舉法：將集合的元素列舉出來例：A=a,b,c,d，B=桌子，燈泡，老虎，自然數，地球，E=2，4，6，.,2n，.，S=a,1,2,q,a 集合的元素可以是一個集合。以集合作為元素組成的集稱為集合簇3.1 3.1 集合的基本概念集合常用的表示方法：（2）敘述法：集合的元素，用謂詞概括其所屬特性例：A=X|是中國的高等學校，B=x|x是實數x2-1=0，C=x|x為小于500的質數，敘述法實際可用謂詞描述屬性，實際上上述各例可描述為B=x|P(x)，如果P(b)為真，即b是B的元素，記作b B，否則b B3.1 3.1 集合

24、的基本概念集合常用的表示方法：（3）特定字母集：有些數集用特定字母表示N-自然數集 Z-整數集Q-有理數集 R-實數集C-復數集 Z+-正整數集Q-負有理數集 Q+-正有理數集3.1 3.1 集合的基本概念集合常用的表示方法：（4）圖示法：用封閉曲線表示集合，封閉曲線內的點表示集合內的元素。這種圖常稱作文氏圖。AB3.1 3.1 集合的基本概念定義3.1.1 設A,B是任意兩個集合，若A=B，當且僅當它們有相同的成員。定義3.1.2 設A、B為任意兩個集合，如果A的每一個元素都是B的元素，則稱集合A為集合B的子集，或A包含在B內或B包含A。記作： A B(或B A)根據子集的定義，顯然有對任意

25、集合A,B,C，必有 )(BxAxxBACACBBAAA,3.1 3.1 集合的基本概念定理3.1.1 集合A和集合B相等的充分必要條件是兩個集合互為子集。定義3.1.3 如果集合A的每個元素都屬于B，但集合B中至少有一個元素不屬于A，則稱A為B的真子集。記作： A B例如，a,b a,b,d定義3.1.4 不包含任何元素的集合稱為空集，記為 或 定理3.1.2 對于任意集合A必有 A3.1 3.1 集合的基本概念定義3.1.5 設A為任意集合，以A的子集為元素所組成的集合，稱為集合A的冪集，記為P(A) 3.1 3.1 集合的基本概念定理3.1.3 如果有限集合A有n個元素，則其冪集P(A)

26、有2n個元素。定義3.1.6 在一定范圍內，如果所有集合均為某一集合的子集，則稱該集合為全集。記為E 3.2 3.2 集合的運算（1）集合的交定義3.2.1設A，B為任意兩個集合。 由集合A和 B 所共有的全部元素構成的集合S,稱為A與B的交集，記為AB。)()( |BxAxxBAS3.2 3.2 集合的運算（2）集合的并定義3.2.2 任意兩個集合A和B。 所有屬于集合A又屬于集合 B 的元素構成的集合S,稱為A與B的并集，記為AUB。)()( |BxAxxBAS3.2 3.2 集合的運算（2）集合的并定理3.2.1 設A,B,C為三個集合，則:a.A(BUC)=(AB)U(AC)b.AU(

27、BC)=(AUB)(AUC)并運算與交運算之間尚有下列性質：吸收律：AU(AB)=A A(AUB)=ABBABAABABA3.2 3.2 集合的運算（3）集合的補定義3.2.3 任意兩個集合A和B。 所有屬于集合A而不屬于集合 B 的元素構成的集合S,稱為A與B的補集，記為A-B。例：設E=a,b,c,d,e，A=a,b.c，B=a,c,d，A-B=d，B-A=d定義3.2.4 設E為全集，對任一集合A,關于E的補E-A，稱為集合A的絕對補，記作A)()( |-BxAxxBAS)()( |-AxExxBEA3.2 3.2 集合的運算（4）集合的對稱差定義3.2.5 任意兩個集合A和B。 所有或

28、屬于集合A或屬于集合 B 但不能即屬于A，又屬于B的元素構成的集合S,稱為A與B的對稱差， 記為A B。定理3.2.3設任意集合A,B,C，則有以下性質：)()(|)()( |ABxBAxxBAxBxAxxBASABBAAAAA）（）（BABABA)(BACBAC）（3.3 3.3 笛卡爾積與關系定義3.3.1 由兩個客體x和y，按一定的順序，組成一個二元組，稱此二元組為有序對或稱序偶，記作或（x，y）。其中x是該序偶的第一個元素，y是該序偶的第二個元素。定義3.3.2 兩個序偶相等，=,iff x=u,y=v.定義3.3.3 設A,B為集合。用A中的元素x作為第一元素，B中的元素y作為第二元

29、素，構成有序對，所有這樣的有序對組成的集合，叫做A和B的笛卡爾積，記作AB。例：A=0,1,2，B=a,b， AB=,BA=,可看出ABBA,|ByAxxBA3.3 3.3 笛卡爾積與關系我們約定：若A=或B=，則AB=由笛卡爾積的定義：),( |,CB)(ACcBAbacba ),()( |,C)(BACBcbAacba3.3 3.3 笛卡爾積與關系定義3.3.4 設A,B是任意兩個集合，AB的子集R稱為從A到B的二元關系。當A=B時，稱R為A上的二元關系。 稱a與b有關系R，記作aRb 稱a與b沒有關系R，記作aRb若R=稱為空關系，若R=AB稱R為全關系，當A=B時，全關系A上的恒等關系

30、例：A=0,1,2，IA=,Rba ,Rba ,AAAyAxyxEA|,|,AxxxIA3.3 3.3 笛卡爾積與關系定義3.3.5 設R為二元關系，由 R的所有x組成集合domR，稱為R的前域。 使 R的所有y組成的集合ranR稱作R的值域，即R的前域和值域一起稱作R的域，記為FLDR，FLDR=domRUranR ),y)( |x=RyxdomR ),x)( |y=RyxranR3.4 3.4 關系的表示與關系性質關系的表示：（1）關系圖設X=x1,x2,x3,x4,x5,x6,x7，Y=y1,y2,y3,y4,y5,y6，R=,，ranR=x3,x4,x5 ranR=y1,y2,y4x1

31、x2x6x7x3x4x5Xy1y2y4y3y5y6YdomRranR3.4 3.4 關系的表示與關系性質關系的表示：（2）布爾矩陣設給定兩個有限集合X=x1,x2,x3,.,xm，Y=y1,y2,.,yn，R為X到Y的一個二元關系，則對應于R有一個關系矩陣其中， 1，當 0, 當例1的R表示：nmijRrMijrRyxji,Ryxji,3.4 3.4 關系的表示與關系性質定義3.4.1 設R是集合X上的二元關系，（1）如果對任意 ，必有xRx,則稱關系R在X上是自反的。（2）如果對任意 ，必有xRx，則稱關系R在X上的反自反的。（3）如果對任意 ，若xRy必有yRx，則稱關系R在X上是對稱的。

32、（4）如果對任意 ，若xRy且yRx必有x=y，則稱R在X上是反對稱的。（5）如果對任意 ，xRy且yRz必有xRz，則稱關系R在X上是傳遞。XxXxXyx,Xyx,Xzyx,3.4 3.4 關系的表示與關系性質為了判別關系性質，也可以從關系矩陣和關系圖上給予驗證。 若關系R是自反的，當且僅當在關系矩陣中，對角線上的所有元素都是1，在關系圖中每個結點都有自回路。 若關系R是對稱的，當且僅當在關系矩陣是對稱的，在關系圖中，任兩個結點間若有定向弧線，必是成對出現。 若關系R是反自反的，當且僅當在關系矩陣中，對角線上的所有元素都是0，在關系圖中每個結點都沒有自回路。 若關系R是反對稱的，當且僅當在關

33、系矩陣以對角線為對稱的元素不能同時為1，在關系圖中，兩個結點間若有定向弧線，不可能成對出現。3.5 3.5 關系運算與閉包二元關系是以序偶為元素的集合，因此可以對它進行集合的運算。定義3.5.1 設R是從X到Y的二元關系，如將R中每一序偶的元素順序互換，所得到的集合稱為R的逆關系，記作R-1例：設X=1,2,3,4,Y=a,b,c,R=,求R-1R-1=,|,1RyxxyR3.5 3.5 關系運算與閉包定義3.5.2 設R為A到B的關系，S為B到C的關系，則RS稱R和S的復合關系。例：設A=p,q,r,s,B=a,b,C=1,2,3,4,A到B的關系R1=,，從B到C的關系R2=,則A到C的復

34、合關系RS=,),)(|,SzyRyxByyCzAxzxSRo3.5 3.5 關系運算與閉包設R是X到Y的關系，S是Y到Z的關系，P是Z到W的關系，易證(RS)P=R(SP)，即滿足結合律一般來說復合運算不滿足交換律。由關系的結合律可以知道關系R本身組成的復合關系可以寫成RR，RRR，.,RR.R,可分別記作R2,R3,.,Rmm3.5 3.5 關系運算與閉包定理3.5.2 設A=a1,a2,.,am，B=b1,b2,.,bn，C=c1,c2,.,cr從A到B的關系R1關系矩陣MR1=(xij)是mn階矩陣。從B到C的關系R2的關系矩陣MR2=(yij)是nr階矩陣，那么從A到C的關系矩陣:M

35、R1R2=(Zij)是mr階矩陣布爾運算的加法和乘法，規(guī)定0，1運算為：00=0，01=1，10=1，11=1，00=0，01=0，10=0，11=1例：設集合A=1,2,3,4,B=2,3,4,C=1,2,3,A到B的關系R1=,，B到C的關系R2=,，求A到C的關系R=R1R23.5 3.5 關系運算與閉包定義3.5.3 設R是A上二元關系，如果有另一個關系R，滿足：（1）R是自反的（對稱的，可傳遞的）；（2）R R；（3）對于任何自反的（對稱的，可傳遞的）關系R,如果有R R，就有R R，則稱關系R為R的自反（對稱，傳遞）閉包，記作r(R)(S(R),t(R) 定理3.5.3 設R的非空

36、有窮集合A上的二元關系。（1）r(R)=RUIA（2）S(R)=RUR-1（3）t(R)=RUR2U.URn,其中n是集合A中元素的數目。 3.5 3.5 關系運算與閉包檢查關系R的關系圖，在每個結點上加上一個自環(huán)，即得r(R)的關系圖。如果將R的關系圖中，每條單向邊全部改成雙向邊，其余不變，則得到S(R)關系圖。關于傳遞閉包，檢查R關系圖的每個結點x，從x出發(fā)長度不超過n（n是圖中結點個數）的所有路徑終點都找到，如果x到這樣的終點沒有邊，就加上此邊。例：設A=a,b,c，給定A上的二元關系R=,求r(R),S(R),t(R)3.6 3.6 相容關系與覆蓋定義3.6.1 給定集合A上的關系p，

37、若p是自反的，對稱的，則稱p是A上的相容關系。3.7 3.7 等價關系與劃分定義3.7.1 設R為定義在集合A上的一個關系，若R是自反的，對稱的和傳遞的，則稱R為等價關系。3.7 3.7 等價關系與劃分定義 3.7.2 設給定非空集合A,若有集合S=S1,S2,.Sm,其中Si A，Si ，(i=1,2,.,m),且SiSj= ，（i j），同時有 ，稱S為A的劃分。例：A=a,b,c,d,B=a,b,c,d,D=a,b,c,d,E=b,a,c,d,F=a,b,cd,則B,D,E,F都是A的不同劃分。?ASimiU13.7 3.7 等價關系與劃分定理3.7.3 集合A的一個劃分確定A的元素間的

38、一個等價關系。證明：設集合A有一個劃分S=S1,S2,.Sm，先定義一個關系R，當aRb，當且僅當a，b在同一分塊中，這樣：（1）a與a在同一分塊中，故必有aRa，即R是自反的。（2）若a，b在同一分塊中，則b，a也在同一分塊中，即aRb bRa，故R是對稱的。（3）若a與b在同一分塊中，b與c在同一分塊中，故有：aRbbRc aRc，即R是傳遞的。從以上證明三點，說明R是A上的等價關系。3.7 3.7 等價關系與劃分例：設A=a,b,c,d,e,f的一個劃分，S=a,b,c,d,e,f，由S確定A上等價關系為R，R=(a,ba,b)U(c,dc,d)U(e,fe,f)=,3.8 3.8 序關

39、系定義3.8.1 設A是一個集合，如果A上的關系R滿足自反性，反對稱性，以及傳遞性，則稱R是A上的一個偏序關系，并記作。序偶稱作偏序集。例：在實數集R上，證明小于等于關系，“”是偏序關系。證明：a)對任意實數a，都有aa，故在實數集R上是自反的。 b)對任意實數a,b,有ab,ba，必有a=b,這說明在實數集上是反對稱的。 c)對任意實數a,b,c,如果ab,bc,則在實數集上必有ac，所以是傳遞的。從上述三點，說明在實數集上是偏序關系。3.8 3.8 序關系偏序集可以通過圖形表示。表示偏序集的圖形是哈斯圖。畫法如下：A中每個元素可用結點表示。對于a，b A，若ab，則將結點a畫在結點b下，若

40、a與b之間不存在其他元素c，使ac，cb，則在a與b之間用一直線相連，得到的圖形為哈斯圖。因偏序集每個結點都有環(huán)，畫哈斯圖時可以省略。3.8 3.8 序關系定義3.8.4 在偏序集中，如果x，y A，xy，且xy，且沒有其他元素z，滿足xz，zy，則稱元素y蓋住元素x。記COVA=|x,y A;y蓋住x3.8 3.8 序關系定義3.8.6 設是一個偏序集，且B是A的子集，對于B中一個元素b，如果沒有任何元素x，滿足bx，且bx，則稱b為B的極大元。同理，若B中沒有任何元素x，滿足bx，且xb，則稱b為B的極小元。3.8 3.8 序關系定義3.8.7 令為一偏序集，B A，若有元素b B,對B中

41、每一個元素x有xb，則稱b為的最大元，同理，若對每一個元素x都有bx，則稱b為的最小元。3.8 3.8 序關系定義3.8.8 令為一偏序集，B A，若有元素a A,且對B中任意元素x有xa，則稱a為子集B的上界，同理，若對B任意元素x都有ax，則稱a為B的下界。定義3.8.9 令為一偏序集，B A，若a為B的任意上界,且、若對B的所有上界y均有ay，則稱a為B的上確界，同理，若b為B的任意下界若對B的所有下界z，都有zb，則稱z為B的下確界。3.9 3.9 函數的概念定義3.9.1 設X和Y是任意兩個集合，而f是X到Y的一個關系，如果對于每一個x X，有唯一的y Y，使得 f，稱關系f為函數，

42、記作： f：XY。函數與其他關系有別于兩點：（1）函數的定義域為X，而不能是X的某個真子集。domf=X。（2）一個x X只能對應唯一的y Y。假如 f,則稱x為自變量，y稱為在f作用下x的像。 f，可記為y=f(x),f(X)=f(x)|x X如果 f, f,必有y=z，函數y=f(x)的定義域記作domf=X，f的值域ranf Y3.9 3.9 函數的概念從X到Y的函數，有時也稱作X到Y的映射。定義3.9.4 給定函數f:XY, 若randf=Y，稱f是滿射的或f為到上的。 若函數f滿足x1，x2 X，若x1x2時必有f(x1)f(x2),則稱f為入射的。 若函數f即是滿射又是入射，則稱f

43、為雙射。3.10 3.10 復合函數與逆函數定義3.10.1 設f：XY，g：YZ，合成關系gf=|(x X)(z Z)( y)(y Y)(y=f(x)z=g(y),稱gf為f，g的左復合運算或復合運算。定理3.10.1 設f：XY，g：YZ是兩個函數，合成運算gf是XZ的函數，且對每一個x X有(gf)(x)=g(f(x)3.10 3.10 復合函數與逆函數定義3.10.1 設f：XY，g：YZ，合成關系gf=|(x X)(z Z)( y)(y Y)(y=f(x)z=g(y),稱gf為f，g的左復合運算或復合運算。定理3.10.1 設f：XY，g：YZ是兩個函數，合成運算gf是XZ的函數，且

44、對每一個x X有(gf)(x)=g(f(x)例：設集合X,Y,Z，X=x1,x2,x3,x4，Y=y1,y2,y3,y4,y5，Z=z1,z2,z3，函數f：XY，g：YZ定義為：f=,g=,則gf：XZ為：gf=,4.1 4.1 代數系統(tǒng)世界上各種事物的作用，實際上都可以看作是運算。定義4.1.1 設A，B為任意集合，一個從An到B的映射，稱為集合A上的一個n元運算。如果B A，則稱該n元運算是封閉的。在n元運算中，經常遇到的是二元運算。而且在A上對該運算是封閉的。例：整數集合上的加法、減法、乘法是Z上的二元運算。例：設A為任意集合，則U,，-、 為A的冪集P(A)上的二元運算。定義4.1.

45、2 一個非空集合A，連同若干個定義在該集合上的運算f1,f2,f3,.,fk所組成的系統(tǒng)，就稱為一個代數系統(tǒng)，記作4.1 4.1 代數系統(tǒng)定義4.1.3 設A為任意非空集合，*是集合A上二元運算。1.封閉性：對任意a，b A，若有a*b A,則稱運算*關于集合是封閉的。2.結合律：對任意a，b，c A，若有a*(b*c)=(a*b)*c,則稱運算*在集合A上是可結合的，或稱運算*在A上滿足結合律。3.交換律：對任意a，b A，若有a*b=b*a,則稱運算*在集合A上是可交換的，或稱運算*在A上滿足交換律。4.冪等率：若對 a A，有a*a=a,則稱運算*在A上是冪等的，或稱運算*在A上滿足冪等

46、律。5.分配律：若對任意a，b，c A，若有a(b*c)=(ab)*(ac)和(b*c)a=(ba)*(ca),則稱運算對*在集合A上是可分配的，或稱運算對*在A上滿足分配律。6.吸收律：若和*滿足交換律且有：任意a，b A，并有a(a*b)=a,a*(ab)=a,則稱運算對*在集合A上是可吸收的，或稱運算對*在A上滿足吸收律。4.1 4.1 代數系統(tǒng)定義4.1.4 設*為集合A上二元運算，若存在eL A（或er A），使得對于任意x A，都有eL*x=x（x*er=x）,則稱eL（或er）是A中關于*運算的左（或右）幺元（或單位元）。如果A中一個元素e，它既是左幺元，又是右幺元，則稱e是A中

47、關于運算*的幺元。4.1 4.1 代數系統(tǒng)定義4.1.5 設*為集合A上二元運算，若有一個元素OL A（或Or A），使得對于任意x A，都有OL*x=OL（x*Or=Or）,則稱OL（或Or）是A中關于*運算的左（或右）零元。如果A中一個元素O，它既是左零元，又是右零元，則稱O是A中關于運算*的零元。定理4.1.1 設*是集合A上的二元運算，且在A中有關于運算*的左幺元eL和右幺元er，則eL=er=e，且A中幺元是唯一的。定理4.1.2 設*是定義在集合A上的二元運算，在A中有關于運算*的左零元OL和右零元Or，則OL=Or=O，且A中零元是唯一的。4.1 4.1 代數系統(tǒng)定義4.1.6

48、設代數系統(tǒng)中，e是關于*運算的單位元，若對A中某個元素a，存在A的一個元素b，使得b*a=e,則稱b是a的左逆元；a*b=e,則稱b是a的右逆元。如果一個元素b，它既是a的左逆元，又是a的右逆元，則稱b是a的一個逆元，記作b-1一個元素的左逆元不一定等于它的右逆元，而且一個元素可以有左（右）逆元而沒有右（左）逆元。一個元素的左右逆元也不一定是唯一的。4.2 4.2 半群與獨異點定義4.2.1 設*是集合S的上的二元運算，若運算*是封閉的，并且*是可結合的，則稱這個代數系統(tǒng)為半群。這個定義包括兩點，即對任意a，b，c S，（1）a*b S（2）a*(b*c)=(a*b)*c4.2 4.2 半群與

49、獨異點定理4.2.1 設為一個半群，B S，且運算*在B上是封閉的，那么也是一個半群，通常稱是半群的子半群。定義4.2.2 若半群中存在一個幺元，則稱為獨異點。（或含幺半群）定理4.2.2 設是獨異點，對于a，b S，且a，b均有逆元，則：(1)(a-1)-1=a(2)若a*b有逆元，則(a*b)-1=b-1*a-14.3 4.3 群與子群定義4.3.1 設為一個代數系統(tǒng)，其中G是非空集合，*是G上一個二元運算， 如果*是封閉的； 運算*是可結合的； 存在幺元e； 對于每一個元素x G，存在它的逆元x-1；則稱是一個群。4.3 4.3 群與子群定義4.3.2 設為一個群，如果G是有限集合，則稱是有限群。G中元素的個數通常稱為有限群的階數，記為|G|。4.3 4.3 群與子群定義4.3.4 設為一個群，若運算*在G上滿足交換律，則稱G為交換群或Abel群。定義4.3.5 設為一個群，若a G，使得ak=e成立的最小正整數k稱為a的階，記作|a|。4.3 4.3 群與子群定理4.3.1 設為一個群，任意a,b G，有： (a-1)-1=a (ab)-1=b-1a-1 anam