自考離散數(shù)學(xué)期末復(fù)習(xí)

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

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

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

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

5、 設(shè)P: 兩個(gè)三角形全等； Q:它們的三組對(duì)應(yīng)邊相等。 所以本例可描述為： PQ 1.2 1.2 復(fù)合命題與聯(lián)結(jié)詞常用的聯(lián)結(jié)詞（5）雙條件PQ 的真值 當(dāng)P與Q的真值為相同時(shí)，PQ 為T(mén).其余情況，PQ 為F P QPQT TTT FFF TFF FT1.2 1.2 復(fù)合命題與聯(lián)結(jié)詞1.2 1.2 復(fù)合命題與聯(lián)結(jié)詞1.3 1.3 命題公式與真值表真值表定義1.3.3 設(shè)P為一命題公式，P1 , P2, P3,.Pn 為出現(xiàn)在P中的所有命題變?cè)?對(duì) P1 , P2, P3,.Pn 指定一組真值稱為對(duì)P的一種指派。若指定的一種指派，使P的值為真，則稱這組值為成真指派；若指定的一種指派，使P的值為

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

7、派情況下，其取值均為假, 則稱公式A為矛盾式或永假式。定義1.3.7 設(shè)A為一命題公式，若A在它的各種真值指派下至少存在一組成真指派，則稱A是可滿足式。1.3 1.3 命題公式與真值表對(duì)合律 PP冪等律 P PP, P PP結(jié)合律 (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兩個(gè)等值公式：兩個(gè)等值公式： P Q PQ (PQ) ( P Q)PQ 1.4 1.4 等價(jià)變換與蘊(yùn)含式等價(jià)變換定理1.4.1 設(shè) X 是合式公式 A 的子公式，若有Y也是一個(gè)合式公式，且XY，如果將A中的X用Y置換， 得到公式B,則 AB。例：證明Q(P(PQ)QP 證：設(shè)A：Q(P(PQ)， 因?yàn)镻(PQ)P（吸收律） 故B:QP，即AB1.4 1.4 等價(jià)變換與蘊(yùn)含式等價(jià)變換判斷命題公式是重言式或矛盾式真值表等價(jià)變換1.4 1.4 等價(jià)變換與蘊(yùn)含式1.5 1.5 最小聯(lián)結(jié)詞組與范式最小聯(lián)結(jié)詞組（1）由PQ(PQ)(QP)，故可把包含的公式等價(jià)變換為包含“”和“”的公式。（2）

9、由PQPQ，故可把包含的公式等價(jià)變換為包含“”和“”的公式。（3）由PQ(PQ)，PQ(PQ)說(shuō)明“”與“”可以相互交換。故由“”“”“”“”“”這5個(gè)聯(lián)結(jié)詞中若干個(gè)組成的命題公式，必可由,或,組成的命題公式所替代。我們把,及,稱為命題公式的最小聯(lián)結(jié)詞組。1.5 1.5 最小聯(lián)結(jié)詞組與范式范式定義1.5.1 一個(gè)命題公式稱為合取范式，當(dāng)且僅當(dāng)它具有形式 A1 A2.An （n1）其中A1 ，A2，.，An 都是由命題變?cè)云浞穸ńM成的析取式。例如：（PQ）（PR）（PQ）是一個(gè)合取范式1.5 1.5 最小聯(lián)結(jié)詞組與范式范式定義1.5.2 一個(gè)命題公式稱為析取范式，當(dāng)且僅當(dāng)它具有形式 A1 A2

10、.An （n1）其中A1 ，A2，.，An 都是由命題變?cè)云浞穸ńM成的合取式。例如：（PQ）（PR）（PQ）是一個(gè)析取范式1.5 1.5 最小聯(lián)結(jié)詞組與范式范式一個(gè)命題公式的合取范式或析取范式不是唯一的。1.5 1.5 最小聯(lián)結(jié)詞組與范式主范式定義1.5.3 n個(gè)命題變?cè)暮先∈?，稱作布爾合取或小項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)僅且出現(xiàn)一次。例如：2個(gè)命題變?cè)狿和Q，其小項(xiàng)為： PQ, PQ, PQ, PQ 3個(gè)命題變?cè)狿，Q和R，其小項(xiàng)為： PQR, PQR, PQR, PQR, PQR, PQR, PQR, PQR1.5 1.5 最小聯(lián)結(jié)詞組與范式小項(xiàng)的表示一般來(lái)說(shuō)

11、，n個(gè)命題變?cè)?n個(gè)小項(xiàng)，n個(gè)命題變?cè)男№?xiàng)，將命題變?cè)闯?，其否定看成0，則每個(gè)小項(xiàng)對(duì)應(yīng)著一個(gè)二進(jìn)制數(shù)。例： m000= PQR m001=PQR m010=PQR m011=PQR m100=PQR m101=PQR m110=PQR m111=PQR1.5 1.5 最小聯(lián)結(jié)詞組與范式主范式定義1.5.4 對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅由小項(xiàng)的析取所組成，則該等價(jià)式稱作原式的主析取范式。定理1.5.1 在真值表中，一個(gè)公式的真值為T(mén)的指派所對(duì)應(yīng)的小項(xiàng)的析取，即為此公式主析取范式。定理1.5.2 任意含n個(gè)命題變?cè)姆怯兰倜}公式，其主析取范式是唯一的。1.5 1.5 最小

12、聯(lián)結(jié)詞組與范式主范式定義1.5.5 n個(gè)命題變?cè)奈鋈∈?，稱作布爾析取或大項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)僅且出現(xiàn)一次。例如：2個(gè)命題變?cè)狿和Q，其大項(xiàng)為： PQ, PQ, PQ, PQ 3個(gè)命題變?cè)狿，Q和R，其大項(xiàng)為： PQR, PQR, PQR, PQR, PQR, PQR, PQR, PQR1.5 1.5 最小聯(lián)結(jié)詞組與范式大項(xiàng)的表示與小項(xiàng)情況類(lèi)似，每個(gè)大項(xiàng)也可以編碼。具體方法：首先將n個(gè)命題變?cè)判颍瑢⒚總€(gè)命題變?cè)獙?duì)應(yīng)成0，其否定對(duì)應(yīng)成1，則可將2n個(gè)大項(xiàng)按二進(jìn)制數(shù)編碼，記為Mi，其下標(biāo)是由二進(jìn)制化為十進(jìn)制數(shù)。例： 2個(gè)命題變?cè)狿,Q的命題公式，應(yīng)有4個(gè)大項(xiàng)：

13、PQ=M00=M0 PQ=M01=M1, PQ=M10=M2, PQ=M11=M3 1.5 1.5 最小聯(lián)結(jié)詞組與范式主范式定理1.5.3 在真值表中一個(gè)公式的真值為F的指派所對(duì)應(yīng)的大項(xiàng)的合取，即為此公式主合取范式。定理1.5.2 任意含n個(gè)命題變?cè)姆怯勒婷}公式A，其主合取范式是唯一的。1.5 1.5 最小聯(lián)結(jié)詞組與范式主范式從A的主析取范式求主合取范式步驟：（1）求出A的主析取范式中為包含小項(xiàng)的下標(biāo)（2）把（1）中求出的下標(biāo)寫(xiě)成對(duì)應(yīng)大項(xiàng)。（3）做（2）中寫(xiě)成的大項(xiàng)合取，即為A的主合取范式。1.5 1.5 最小聯(lián)結(jié)詞組與范式主范式例：公式A：（pq）（qp） ，則公式A的主合取范式為例：（

14、PQ）Q =m01m11 （PQ）Q =M00M10210 ，331，20，1.5 1.5 最小聯(lián)結(jié)詞組與范式主范式根據(jù)主范式的定義和定理,可以判定含n個(gè)命題變?cè)墓? （1）若A可化為與其等價(jià)的,含2n個(gè)小項(xiàng)的主析取范式,則A為永真式. （2）若A可化為與其等價(jià)的,含2n個(gè)大項(xiàng)的主合取范式,則A為永假式. （3）若A的主析取范式不含2n個(gè)小項(xiàng),或A的主合取范式不含2n個(gè)大項(xiàng),則A為可滿足式.判斷公式類(lèi)型： 1，真值表 2.等值演算 3.主范式1.4 1.4 等價(jià)變換與蘊(yùn)含式1.4 1.4 等價(jià)變換與蘊(yùn)含式蘊(yùn)含式定理1.4.2 設(shè)A,B為兩命題公式，AB，當(dāng)且僅當(dāng)AB為一個(gè)重言式。定義1.4

15、.1 當(dāng)且僅當(dāng)PQ是一個(gè)重言式時(shí)，我們稱“P蘊(yùn)含Q”，并記作P Q。P Q稱作P蘊(yùn)含Q或蘊(yùn)含式，亦稱作永真條件式。 1.4 1.4 等價(jià)變換與蘊(yùn)含式蘊(yùn)含式（1）化簡(jiǎn)式 PQ P. PQ Q（3）附加式 P PQ（4）變形附加式 P PQ，Q PQ（5）變形簡(jiǎn)化式 （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）合取構(gòu)造二難 （PQ）（RS）（PR） QS（12）析取構(gòu)造二難 （PQ）（RS）（PR） QS（13）前后件附加 PQ （P

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

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

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

19、合命題函數(shù)。定義2.2.2 謂詞演算的合式公式，可由下述各條組成（合式公式A記為WffA）：（1）原子謂詞公式是合式公式。（2）若A是合式公式，則A是一個(gè)合式公式。（3）若A和B都是合式公式，則（AB），（AB），（AB），（AB）是合式公式。（4）如果A是合式公式，x是A中出現(xiàn)的任何變?cè)瑒t 和 都是合式公式。（5）只有經(jīng)過(guò)有限次應(yīng)用規(guī)則（1）（2）（3）（4）所得到的公式是合式公式。Ax)(Ax)(2.2 2.2 量詞與合式公式2.2 2.2 量詞與合式公式定義2.2.3 給定謂詞合式公式A，其中一部分公式形式為 或稱量詞 ， 后面所跟的x為指導(dǎo)變?cè)蜃饔米冊(cè)?。稱B(x)為相應(yīng)量詞的轄域（

20、或作用域）。 在轄域中，x的一切出現(xiàn)稱為約束出現(xiàn)。B(x)中除去約束出現(xiàn)的其他變項(xiàng)的出現(xiàn)為自由出現(xiàn)。)()(xBx)()(xBx2.3 2.3 謂詞演算的等價(jià)式與蘊(yùn)含式當(dāng)確定論域后 ，與 都是一個(gè)特定的命題。例如 表示x是個(gè)大學(xué)生，論域是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 謂詞演算的等價(jià)式與蘊(yùn)含式2.3 2.3 謂詞演算的等價(jià)式與

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

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

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

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

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

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

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

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

29、素，構(gòu)成有序?qū)?，所有這樣的有序?qū)M成的集合，叫做A和B的笛卡爾積，記作AB。例：A=0,1,2，B=a,b， AB=,BA=,可看出ABBA,|ByAxxBA3.3 3.3 笛卡爾積與關(guān)系我們約定：若A=或B=，則AB=由笛卡爾積的定義：),( |,CB)(ACcBAbacba ),()( |,C)(BACBcbAacba3.3 3.3 笛卡爾積與關(guān)系定義3.3.4 設(shè)A,B是任意兩個(gè)集合，AB的子集R稱為從A到B的二元關(guān)系。當(dāng)A=B時(shí)，稱R為A上的二元關(guān)系。 稱a與b有關(guān)系R，記作aRb 稱a與b沒(méi)有關(guān)系R，記作aRb若R=稱為空關(guān)系，若R=AB稱R為全關(guān)系，當(dāng)A=B時(shí)，全關(guān)系A(chǔ)上的恒等關(guān)系

30、例：A=0,1,2，IA=,Rba ,Rba ,AAAyAxyxEA|,|,AxxxIA3.3 3.3 笛卡爾積與關(guān)系定義3.3.5 設(shè)R為二元關(guān)系，由 R的所有x組成集合domR，稱為R的前域。 使 R的所有y組成的集合ranR稱作R的值域，即R的前域和值域一起稱作R的域，記為FLDR，F(xiàn)LDR=domRUranR ),y)( |x=RyxdomR ),x)( |y=RyxranR3.4 3.4 關(guān)系的表示與關(guān)系性質(zhì)關(guān)系的表示：（1）關(guān)系圖設(shè)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 關(guān)系的表示與關(guān)系性質(zhì)關(guān)系的表示：（2）布爾矩陣設(shè)給定兩個(gè)有限集合X=x1,x2,x3,.,xm，Y=y1,y2,.,yn，R為X到Y(jié)的一個(gè)二元關(guān)系，則對(duì)應(yīng)于R有一個(gè)關(guān)系矩陣其中， 1，當(dāng) 0, 當(dāng)例1的R表示：nmijRrMijrRyxji,Ryxji,3.4 3.4 關(guān)系的表示與關(guān)系性質(zhì)定義3.4.1 設(shè)R是集合X上的二元關(guān)系，（1）如果對(duì)任意 ，必有xRx,則稱關(guān)系R在X上是自反的。（2）如果對(duì)任意 ，必有xRx，則稱關(guān)系R在X上的反自反的。（3）如果對(duì)任意 ，若xRy必有yRx，則稱關(guān)系R在X上是對(duì)稱的。

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

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

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

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

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

37、若p是自反的，對(duì)稱的，則稱p是A上的相容關(guān)系。3.7 3.7 等價(jià)關(guān)系與劃分定義3.7.1 設(shè)R為定義在集合A上的一個(gè)關(guān)系，若R是自反的，對(duì)稱的和傳遞的，則稱R為等價(jià)關(guān)系。3.7 3.7 等價(jià)關(guān)系與劃分定義 3.7.2 設(shè)給定非空集合A,若有集合S=S1,S2,.Sm,其中Si A，Si ，(i=1,2,.,m),且SiSj= ，（i j），同時(shí)有 ，稱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 等價(jià)關(guān)系與劃分定理3.7.3 集合A的一個(gè)劃分確定A的元素間的

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

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

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

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

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

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

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

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

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

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

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

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