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

1、離散數(shù)學(xué)期末復(fù)習(xí),,1.1 命題概念,命題：具有唯一真值的陳述句,1.1 命題概念,練習(xí)：1.下列句子為命題的是（ ）A.全體起立！ B. X=0 C. 我在說謊 D.張三生于1886年的春天2.下列句子不是命題的是（ ）A.中華人民共和國的首都是北京 B.張三是學(xué)生 C.雪是黑色的

2、 D.太好了！,D,D,1.2 復(fù)合命題與聯(lián)結(jié)詞,常用的聯(lián)結(jié)詞（1）否定定義1.2.1 設(shè)P為一命題，P的否定是一個(gè)新的命題，記作¬P。 “¬”表示命題的否定. ¬ P的真值： 若P為T，¬ P為F；若P為F，¬ P為T,1.2 復(fù)合命題與聯(lián)

3、結(jié)詞,常用的聯(lián)結(jié)詞（2）合取定義1.2.2 兩個(gè)命題P和Q的合取是一個(gè)復(fù)合命題，記作P∧Q?！姆Q作合取聯(lián)結(jié)詞， 在自然語言中的“并且”、“和”、“既...又...”、“不僅....而且....”、“雖然...但是...”等都可以符號(hào)化為∧ 例1 2是素?cái)?shù)和偶數(shù) 設(shè)P：2是素?cái)?shù)，Q:2是偶數(shù)，故上述命題可表述為P∧Q 例2 王乙工作努力且

4、身體好。 設(shè)P:王乙工作努力，Q:王乙身體好，故上述命題可表述為P∧Q,1.2 復(fù)合命題與聯(lián)結(jié)詞,常用的聯(lián)結(jié)詞（2）合取P∧Q的真值 當(dāng)且僅當(dāng)P與Q同時(shí)為T時(shí)，P∧Q為T.其余情況，P∧Q為F,1.2 復(fù)合命題與聯(lián)結(jié)詞,常用的聯(lián)結(jié)詞（2）合取注意: 命題聯(lián)結(jié)詞“合取”可將兩個(gè)互為否定的命題聯(lián)結(jié)在一起：P∧¬P 此

5、時(shí)其真值永為F,1.2 復(fù)合命題與聯(lián)結(jié)詞,常用的聯(lián)結(jié)詞（3）析取定義1.2.3 兩個(gè)命題P, Q的析取是個(gè)復(fù)合命題，記作P∨Q?！欧Q作析取聯(lián)結(jié)詞， 與自然語言中的“或”有些相似例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米短跑的冠軍。

6、 所以本例可描述為： P∨Q,1.2 復(fù)合命題與聯(lián)結(jié)詞,常用的聯(lián)結(jié)詞（3）析取P∨Q的真值 當(dāng)且僅當(dāng)P與Q同時(shí)為F時(shí)，P∨Q為F.否則，P∨Q為T,1.2 復(fù)合命題與聯(lián)結(jié)詞,常用的聯(lián)結(jié)詞（4）條件定義1.2.4 給定兩個(gè)命題P, Q，其條件命題是一個(gè)復(fù)合命題，記作P→Q。其中P為前件，Q為后件。P→Q讀作“如果P那么Q”，“若P則Q”例6 如果我有就學(xué)機(jī)會(huì)，那么我必用

7、功讀書。 設(shè)P: 我有就學(xué)機(jī)會(huì)； Q:我必用功讀書。 所以本例可描述為： P→Q,1.2 復(fù)合命題與聯(lián)結(jié)詞,常用的聯(lián)結(jié)詞（4）條件P→Q的真值 當(dāng)且僅當(dāng)P的真值為T，Q的真值為F時(shí)，P→Q 為F.其余情況，P∨Q為T,1.2 復(fù)合命題與聯(lián)結(jié)詞,常用的聯(lián)結(jié)詞（5）雙條件定義1.2.6 給定

8、兩個(gè)命題P, Q，其復(fù)合命題P?Q稱作雙條件命題，讀作P當(dāng)且僅當(dāng)Q。例 兩個(gè)三角形全等，當(dāng)且僅當(dāng)它們的三組對(duì)應(yīng)邊相等。 設(shè)P: 兩個(gè)三角形全等； Q:它們的三組對(duì)應(yīng)邊相等。 所以本例可描述為： P?Q,1.2 復(fù)合命題與聯(lián)結(jié)詞,常用的聯(lián)結(jié)詞（5）雙條件P?Q 的真值 當(dāng)P與Q的真值為相同時(shí)

9、，P?Q 為T.其余情況，P?Q 為F,1.2 復(fù)合命題與聯(lián)結(jié)詞,1.2 復(fù)合命題與聯(lián)結(jié)詞,1.3 命題公式與真值表,真值表定義1.3.3 設(shè)P為一命題公式，P1 , P2, P3,...Pn 為出現(xiàn)在P中的所有命題變?cè)?對(duì) P1 , P2, P3,...Pn 指定一組真值稱為對(duì)P的一種指派。若指定的一種指派，使P的值為真，則稱這組值為成真指派；若指定的一種指派，使P的值為假，則

10、稱這組值為成假指派。,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à)的，記作A?B。從上述真值表的例子中，可以知道： ¬ P ? Q

11、 ? P→Q (P?Q) ?(¬ P?¬ Q)?P?Q 上述二式以后經(jīng)常作為等值公式直接應(yīng)用。,1.3 命題公式與真值表,定義1.3.5 設(shè)A為一命題公式，若A在它的各種指派情況下，其取值均為真, 則稱公式A為重言式或永真式。定義1.3.6 設(shè)A為一命題公式，若A在它的各種指派情況下，其取值均為假, 則稱公式A為矛盾式或永假式。定義1.3.7 設(shè)

12、A為一命題公式，若A在它的各種真值指派下至少存在一組成真指派，則稱A是可滿足式。,1.3 命題公式與真值表,對(duì)合律 ??P?P冪等律 P?P?P, P?P?P結(jié)合律 (P?Q)?R?P?(Q?R), (P?Q)?R?P?(Q?R)交換律 P?Q?Q?P,

13、 P?Q?Q?P分配律 P?(Q?R)?(P?Q)?(P?R), P?(Q?R)?(P?Q)?(P?R),1.3 命題公式與真值表,吸收律 P?(P?Q)?P, P?(P?Q)?P德摩根律 ?(P?Q)??P??Q, ?(P?Q)??P??Q同一律

14、 P?F?P , P?T?P零律 P?T?T, P?F?F否定律 P ??P?T, P??P?F,,兩個(gè)等值公式：¬ P ? Q

15、? P→Q (P?Q) ?(¬ P?¬ Q)?P?Q,1.4 等價(jià)變換與蘊(yùn)含式,等價(jià)變換定理1.4.1 設(shè) X 是合式公式 A 的子公式，若有Y也是一個(gè)合式公式，且X?Y，如果將A中的X用Y置換， 得到公式B,則 A?B。例：證明Q→(P?(P?Q))?Q→P 證：設(shè)A：Q→(P?(P?Q))， 因?yàn)镻?(P?Q)?P（吸收律）

16、故B:Q→P，即A?B,1.4 等價(jià)變換與蘊(yùn)含式,等價(jià)變換判斷命題公式是重言式或矛盾式,,真值表,等價(jià)變換,1.4 等價(jià)變換與蘊(yùn)含式,1.5 最小聯(lián)結(jié)詞組與范式,最小聯(lián)結(jié)詞組（1）由P?Q?(P→Q)?(Q→P)，故可把包含?的公式等價(jià)變換為包含“→”和“?”的公式。（2）由P→Q?¬P?Q，故可把包含→的公式等價(jià)變換為包含“¬”和“?”的公式。（3）由P?Q?¬(¬P?¬Q)，

17、P?Q?¬(¬P?¬Q)說明“?”與“?”可以相互交換。故由“¬”“?”“?”“→”“?”這5個(gè)聯(lián)結(jié)詞中若干個(gè)組成的命題公式，必可由{¬,?}或{¬,?}組成的命題公式所替代。我們把{¬,?}及{¬,?}稱為命題公式的最小聯(lián)結(jié)詞組。,1.5 最小聯(lián)結(jié)詞組與范式,范式定義1.5.1 一個(gè)命題公式稱為合取范式，當(dāng)且僅當(dāng)它具有形式

18、 A1 ?A2?...?An （n≧1）其中A1 ，A2，...，An 都是由命題變?cè)云浞穸ńM成的析取式。例如：（P?Q）?（P?¬R）?（¬P?¬Q）是一個(gè)合取范式,1.5 最小聯(lián)結(jié)詞組與范式,范式定義1.5.2 一個(gè)命題公式稱為析取范式，當(dāng)且僅當(dāng)它具有形式 A1 ?A2?...?An

19、 （n≧1）其中A1 ，A2，...，An 都是由命題變?cè)云浞穸ńM成的合取式。例如：（P?Q）?（P?¬R）?（¬P?¬Q）是一個(gè)析取范式,1.5 最小聯(lián)結(jié)詞組與范式,范式一個(gè)命題公式的合取范式或析取范式不是唯一的。,1.5 最小聯(lián)結(jié)詞組與范式,主范式定義1.5.3 n個(gè)命題變?cè)暮先∈?，稱作布爾合取或小項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)僅且出現(xiàn)一次。例如

20、：2個(gè)命題變?cè)狿和Q，其小項(xiàng)為： P?Q, P?¬Q, ¬P?Q, ¬P?¬Q 3個(gè)命題變?cè)狿，Q和R，其小項(xiàng)為： P?Q?R, P?Q?¬R, P?¬Q?R, P?¬Q?¬R, 

21、2;P?Q?R, ¬P?Q?¬R, ¬P?¬Q?R, ¬P?¬Q?¬R,1.5 最小聯(lián)結(jié)詞組與范式,小項(xiàng)的表示一般來說，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= ¬P?¬Q?¬R m001=¬

22、;P?¬Q?R m010=¬P?Q?¬R m011=¬P?Q?R m100=P?¬Q?¬R m101=P?¬Q?R m110=P?Q

23、?¬R m111=P?Q?R,1.5 最小聯(lián)結(jié)詞組與范式,主范式定義1.5.4 對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅由小項(xiàng)的析取所組成，則該等價(jià)式稱作原式的主析取范式。定理1.5.1 在真值表中，一個(gè)公式的真值為T的指派所對(duì)應(yīng)的小項(xiàng)的析取，即為此公式主析取范式。定理1.5.2 任意含n個(gè)命題變?cè)姆怯兰倜}公式，其主析取范式是唯一的。,1

24、.5 最小聯(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)為： P?Q, P?¬Q, ¬P?Q, ¬P?¬Q 3個(gè)命題變?cè)狿，Q和R，其大項(xiàng)為：

25、 P?Q?R, P?Q?¬R, P?¬Q?R, P?¬Q?¬R, ¬P?Q?R, ¬P?Q?¬R, ¬P?¬Q?R, ¬P?¬Q?¬R,1.5 最小聯(lián)結(jié)詞組與范式,大項(xiàng)的表示與小項(xiàng)情況類似，每個(gè)大項(xiàng)也可以編碼。具體方法：首先將n個(gè)命題變?cè)判?，將每個(gè)命題變?cè)?/p>

26、對(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)： P?Q=M00=M0 P?¬Q=M01=M1, ¬P?Q=M10=M2, ¬P?¬Q=M11=M3,1.5 最小聯(lián)結(jié)詞組與范式,主范式定理1.5.3 在真值表中一個(gè)公式的真值為F的指派所對(duì)應(yīng)的大

27、項(xiàng)的合取，即為此公式主合取范式。定理1.5.2 任意含n個(gè)命題變?cè)姆怯勒婷}公式A，其主合取范式是唯一的。,1.5 最小聯(lián)結(jié)詞組與范式,主范式從A的主析取范式求主合取范式步驟：（1）求出A的主析取范式中為包含小項(xiàng)的下標(biāo)（2）把（1）中求出的下標(biāo)寫成對(duì)應(yīng)大項(xiàng)。（3）做（2）中寫成的大項(xiàng)合取，即為A的主合取范式。,1.5 最小聯(lián)結(jié)詞組與范式,主范式例：公式A：（¬p→q）→（q→¬p）?

28、 ，則公式A的主合取范式為例：（P→Q）?Q? =m01?m11 （P→Q）?Q? =M00?M10,1.5 最小聯(lián)結(jié)詞組與范式,主范式根據(jù)主范式的定義和定理,可以判定含n個(gè)命題變?cè)墓? （1）若A可化為與其等價(jià)的,含2n個(gè)小項(xiàng)的主析取范式,則A為永真式. （2）若A可化為與其等價(jià)的,含2n個(gè)大項(xiàng)的

29、主合取范式,則A為永假式. （3）若A的主析取范式不含2n個(gè)小項(xiàng),或A的主合取范式不含2n個(gè)大項(xiàng),則A為可滿足式.判斷公式類型： 1，真值表 2.等值演算 3.主范式,1.4 等價(jià)變換與蘊(yùn)含式,1.4 等價(jià)變換與蘊(yùn)含式,蘊(yùn)含式定理1.4.2 設(shè)A,B為兩命題公式，A?B，當(dāng)且僅當(dāng)A?B為一個(gè)重言式。定義1.4.1 當(dāng)且僅當(dāng)P→Q

30、是一個(gè)重言式時(shí)，我們稱“P蘊(yùn)含Q”，并記作P Q。P Q稱作P蘊(yùn)含Q或蘊(yùn)含式，亦稱作永真條件式。,,,1.4 等價(jià)變換與蘊(yùn)含式,蘊(yùn)含式（1）化簡(jiǎn)式 P?Q P. P?Q Q（3）附加式 P P?Q（4）變形附加式 ¬P P→Q，Q P→Q（5）變形簡(jiǎn)化式 ¬（

31、P→Q） P;¬（P→Q） ¬Q （6）假言推論 P?（P→Q） Q（7）拒取式 ¬Q?（P→Q） ¬P（8）析取三段論 ¬P?(P?Q) Q（9）條件三段論 （P→Q）?(Q→R) P→R（10）雙條件三段論 （P?Q）?（Q

32、?R） P?R（11）合取構(gòu)造二難 （P→Q）?（R→S）?（P?R） Q→S（12）析取構(gòu)造二難 （P→Q）?（R→S）?（P?R） Q?S（13）前后件附加 P→Q （P?R）→（Q?R）; P→Q （P?R）→（Q?R）,,,,,,,,,,,,,,,,,1.6 推理理論,有效推理：從前提出發(fā)，根據(jù)確認(rèn)的推理規(guī)則推導(dǎo)出一個(gè)結(jié)

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

34、。（2）結(jié)論引入規(guī)則：在證明的任何步驟上，所證明的結(jié)論都可作為后續(xù)證明的前提。（3）置換規(guī)則：在證明的任何步驟上，命題公式中的任何子命題公式都可以用與之等值的命題公式置換（表1.6.2，表1.6.3），記為T規(guī)則。,1.6 推理理論,1.6 推理理論,判別有效結(jié)論的方法：（3）構(gòu)造論證法定理 1.6.2 若H1?H2?...?Hn ? ¬C為永假式，則H1?H2?...?Hn ? C成立。 附加前提法：

35、 把結(jié)論的否定作為前提，推出F。,1.6 推理理論,定理1.6.3 （CP規(guī)則 ） 若H1?H2?...?Hn ?R C,則H1?H2?...?Hn R→C。,,,2.1 謂詞的概念與表示,客體：指可以獨(dú)立存在的對(duì)象，一個(gè)具體的事物，一個(gè)抽象的概念謂詞：指明客體性質(zhì)或指明客體之間關(guān)系,2.2 量詞與合式公式,量詞：表示數(shù)量的詞量詞有2種：1.全稱量詞：對(duì)應(yīng)日常語言中的“一切”“任意的”“所有”“凡是”等詞

36、。用符號(hào)“ ”表示。 表示對(duì)個(gè)體域里所有的x，而 表示個(gè)體域里所有個(gè)體，都有性質(zhì)F。2.存在量詞：對(duì)應(yīng)日常語言中的“存在的”“有一個(gè)”“至少有一個(gè)”等詞。用符號(hào)“ ”表示。 表示存在個(gè)體域中的個(gè)體，而 表示存在個(gè)體域中的個(gè)體具有性質(zhì)F。,2.2 量詞與合式公式,在全稱量詞中，特性謂詞是條件式的前件。在存在量詞中，特性謂詞后跟一

37、個(gè)合取項(xiàng)。,2.2 量詞與合式公式,2.2 量詞與合式公式,定義2.2.1 由一個(gè)或幾個(gè)原子命題函數(shù)以及邏輯聯(lián)結(jié)詞組合而成的表達(dá)式稱為復(fù)合命題函數(shù)。定義2.2.2 謂詞演算的合式公式，可由下述各條組成（合式公式A記為WffA）：（1）原子謂詞公式是合式公式。（2）若A是合式公式，則¬A是一個(gè)合式公式。（3）若A和B都是合式公式，則（A?B），（A?B），（A→B），（A?B）是合式公式。（4）如果A是合式公式，x是A

38、中出現(xiàn)的任何變?cè)?，則 和 都是合式公式。（5）只有經(jīng)過有限次應(yīng)用規(guī)則（1）（2）（3）（4）所得到的公式是合式公式。,2.2 量詞與合式公式,2.2 量詞與合式公式,定義2.2.3 給定謂詞合式公式A，其中一部分公式形式為 或稱量詞 ， 后面所跟的x為指導(dǎo)變?cè)蜃饔米冊(cè)?。稱B(x)為相應(yīng)量詞的轄域（或作用域）。 在轄域中，x的

39、一切出現(xiàn)稱為約束出現(xiàn)。B(x)中除去約束出現(xiàn)的其他變項(xiàng)的出現(xiàn)為自由出現(xiàn)。,2.3 謂詞演算的等價(jià)式與蘊(yùn)含式,當(dāng)確定論域后 ，與 都是一個(gè)特定的命題。例如 表示x是個(gè)大學(xué)生，論域是{a,b,c},則： 即是S(a)?S(b)?S(c) 即是S(a)?S

40、(b)?S(c)例：如果論域是集合{a,b,c},試消去下面公式中的量詞：解：原式 (R(a)?R(b)?R(c))?(S(a)?S(b)?S(c)),2.3 謂詞演算的等價(jià)式與蘊(yùn)含式,2.3 謂詞演算的等價(jià)式與蘊(yùn)含式,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à)的，并

41、記作,2.3 謂詞演算的等價(jià)式與蘊(yùn)含式,2.3 謂詞演算的等價(jià)式與蘊(yùn)含式,定理 2.3.1 量詞與否定聯(lián)結(jié)詞之間有如下關(guān)系：（1）（2）,2.3 謂詞演算的等價(jià)式與蘊(yùn)含式,2.4 前束范式,定義2.4.1 一個(gè)公式，如果量詞均在全式的開頭，它們的作用域，延伸到整個(gè)公式的末尾，則該公式叫做前束范式。,2.5 謂詞演算的推理理論,（1）全稱指定規(guī)則（US）：由 得到P(c)。

42、 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)得

43、到,2.5 謂詞演算的推理理論,3.1 集合的基本概念,集合：把一些事物匯集到一起組成一個(gè)整體例：教室內(nèi)的桌椅，圖書館全部藏書，直線上的點(diǎn)的集合，中國的全部縣市的集合集合常用的表示方法：（1）列舉法：將集合的元素列舉出來例：A={a,b,c,d}，B={桌子，燈泡，老虎，自然數(shù)，地球}，E={2，4，6，...,2n，...}，S={a,{1,2},q,{a}} 集合的元素可以是一個(gè)集合。以集合作為元素組成的集稱為

44、集合簇,3.1 集合的基本概念,集合常用的表示方法：（2）敘述法：集合的元素，用謂詞概括其所屬特性例：A={X|是中國的高等學(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 B,3.1 集合的基本概念,集合常用的表示方法：（3）特定字母集：有些數(shù)集用特定字母

45、表示N-自然數(shù)集 Z-整數(shù)集Q-有理數(shù)集 R-實(shí)數(shù)集C-復(fù)數(shù)集 Z+-正整數(shù)集Q--負(fù)有理數(shù)集 Q+-正有理數(shù)集,3.1 集合的基本概念,集合常用的表示方法：（4）圖示法：用封閉曲線表示集合，封閉曲線內(nèi)的點(diǎn)表示集合內(nèi)的元素。這種圖常稱作文氏圖。,,,A,B,3.1 集合的基本概念,定義3.1.1

46、 設(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ì)任意集合A,B,C，必有,3.1 集合的基本概念,定理3.1.1 集合A和集合B相等的充分必要條件是兩個(gè)集合互為

47、子集。定義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必有,3.1 集合的基本概念,定義3.1.5 設(shè)A為任意集合，以A的子集為元素所組成的

48、集合，稱為集合A的冪集，記為P(A),3.1 集合的基本概念,定理3.1.3 如果有限集合A有n個(gè)元素，則其冪集P(A)有2n個(gè)元素。定義3.1.6 在一定范圍內(nèi)，如果所有集合均為某一集合的子集，則稱該集合為全集。記為E,3.2 集合的運(yùn)算,（1）集合的交定義3.2.1設(shè)A，B為任意兩個(gè)集合。 由集合A和 B 所共有的全部元素構(gòu)成的集合S,稱為A與B的交集，記為A∩B。,3.2 集合的運(yùn)算,（2）集合的并定義3.2.2 任意兩

49、個(gè)集合A和B。 所有屬于集合A又屬于集合 B 的元素構(gòu)成的集合S,稱為A與B的并集，記為AUB。,3.2 集合的運(yùn)算,（2）集合的并定理3.2.1 設(shè)A,B,C為三個(gè)集合，則:a.A∩(BUC)=(A∩B)U(A∩C)b.AU(B∩C)=(AUB)∩(AUC)并運(yùn)算與交運(yùn)算之間尚有下列性質(zhì)：吸收律：AU(A∩B)=A A∩(AUB)=A,3.2 集合的運(yùn)算,（3）集合的補(bǔ)定義3.2.3 任意兩個(gè)集合A和B。 所有屬于

50、集合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=3vfpxvp，B-A=vp9lrdr定義3.2.4 設(shè)E為全集，對(duì)任一集合A,關(guān)于E的補(bǔ)E-A，稱為集合A的絕對(duì)補(bǔ)，記作～A,3.2 集合的運(yùn)算,（4）集合的對(duì)稱差定義3.2.5 任意兩個(gè)集合A和B。 所有或?qū)儆诩螦或?qū)儆诩?B 但不能即屬于A，又屬于B的元素構(gòu)成的集合S,稱為A與B

51、的對(duì)稱差， 記為A B。定理3.2.3設(shè)任意集合A,B,C，則有以下性質(zhì)：,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作為第二元素，構(gòu)成有序

52、對(duì)，所有這樣的有序?qū)M成的集合，叫做A和B的笛卡爾積，記作A×B。例：A={0,1,2}，B={a,b}， A×B={,,,,,}B×A={,,,,,}可看出A×B≠B×A,3.3 笛卡爾積與關(guān)系,我們約定：若A=Φ或B=Φ，則A×B=Φ由笛卡爾積的定義：,3.3 笛卡爾積與關(guān)系,定義3.3.4 設(shè)A,B是任意兩個(gè)集合，A×B的子集R稱為從A到B的二元關(guān)系

53、。當(dāng)A=B時(shí)，稱R為A上的二元關(guān)系。 稱a與b有關(guān)系R，記作aRb 稱a與b沒有關(guān)系R，記作aRb若R=Φ稱為空關(guān)系，若R=A×B稱R為全關(guān)系，當(dāng)A=B時(shí)，全關(guān)系A(chǔ)上的恒等關(guān)系例：A={0,1,2}，IA={,,},,3.3 笛卡爾積與關(guān)系,定義3.3.5 設(shè)R為二元關(guān)系，由 R的所有x組成集合domR，稱為R的前域。

54、 使 R的所有y組成的集合ranR稱作R的值域，即R的前域和值域一起稱作R的域，記為FLDR，F(xiàn)LDR=domRUranR,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} ra

55、nR={y1,y2,y4},,,,,,,,,,,,,,,,,,x1,x2,x6,x7,x3,x4,x5,X,y1,y2,y4,y3,y5,y6,Y,,,domR,ranR,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)

56、 0, 當(dāng)例1的R表示：,,,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ì)任

57、意 ，若xRy必有yRx，則稱關(guān)系R在X上是對(duì)稱的。（4）如果對(duì)任意 ，若xRy且yRx必有x=y，則稱R在X上是反對(duì)稱的。（5）如果對(duì)任意 ，xRy且yRz必有xRz，則稱關(guān)系R在X上是傳遞。,,,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，在

58、關(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)都沒有自回路。若關(guān)系R是反對(duì)稱的，當(dāng)且僅當(dāng)在關(guān)系矩陣以對(duì)角線為對(duì)稱的元素不能同時(shí)為1，在關(guān)系圖中，兩個(gè)結(jié)點(diǎn)間若有定向弧線，不可能成對(duì)出現(xiàn)。,3.5 關(guān)系運(yùn)算與閉包,二元關(guān)系是以序偶為元素的集合，因此可以對(duì)它進(jìn)行集合的運(yùn)算。

59、定義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={,,},3.5 關(guān)系運(yùn)算與閉包,定義3.5.2 設(shè)R為A到B的關(guān)系，S為B到C的關(guān)系，則R◎S稱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

60、={,,}則A到C的復(fù)合關(guān)系R◎S={,,,,,,,},3.5 關(guān)系運(yùn)算與閉包,設(shè)R是X到Y(jié)的關(guān)系，S是Y到Z的關(guān)系，P是Z到W的關(guān)系，易證(R◎S)◎P=R◎(S◎P)，即滿足結(jié)合律一般來說復(fù)合運(yùn)算不滿足交換律。由關(guān)系的結(jié)合律可以知道關(guān)系R本身組成的復(fù)合關(guān)系可以寫成R◎R，R◎R◎R，.....,R◎R◎....◎R,可分別記作R2,R3,...,Rm,,,m,3.5 關(guān)系運(yùn)算與閉包,定理3.5.2 設(shè)A={a1,a2,...,

61、am}，B={b1,b2,...,bn}，C={c1,c2,...,cr}從A到B的關(guān)系R1關(guān)系矩陣MR1=(xij)是m×n階矩陣。從B到C的關(guān)系R2的關(guān)系矩陣MR2=(yij)是n×r階矩陣，那么從A到C的關(guān)系矩陣:MR1◎R2=(Zij)是m×r階矩陣布爾運(yùn)算的加法和乘法，規(guī)定0，1運(yùn)算為：0?0=0，0?1=1，1?0=1，1?1=1，0?0=0，0?1=0，1?0=0，1?1=1例：設(shè)集合

62、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=R1◎R2,,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

63、，就有R'' R'，則稱關(guān)系R'為R的自反（對(duì)稱，傳遞）閉包，記作r(R)(S(R),t(R)) 定理3.5.3 設(shè)R的非空有窮集合A上的二元關(guān)系。（1）r(R)=RUIA（2）S(R)=RUR-1（3）t(R)=RUR2U...URn,其中n是集合A中元素的數(shù)目。,,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)系圖中，每條單向邊全

64、部改成雙向邊，其余不變，則得到S(R)關(guān)系圖。關(guān)于傳遞閉包，檢查R關(guān)系圖的每個(gè)結(jié)點(diǎn)x，從x出發(fā)長度不超過n（n是圖中結(jié)點(diǎn)個(gè)數(shù)）的所有路徑終點(diǎn)都找到，如果x到這樣的終點(diǎn)沒有邊，就加上此邊。例：設(shè)A={a,b,c}，給定A上的二元關(guān)系R={,,},求r(R),S(R),t(R),,3.6 相容關(guān)系與覆蓋,定義3.6.1 給定集合A上的關(guān)系p，若p是自反的，對(duì)稱的，則稱p是A上的相容關(guān)系。,,3.7 等價(jià)關(guān)系與劃分,定義3.7.1 設(shè)R

65、為定義在集合A上的一個(gè)關(guān)系，若R是自反的，對(duì)稱的和傳遞的，則稱R為等價(jià)關(guān)系。,,3.7 等價(jià)關(guān)系與劃分,定義 3.7.2 設(shè)給定非空集合A,若有集合S={S1,S2,...Sm},其中Si A，Si ，(i=1,2,...,m),且Si∩Sj= ，（i j），同時(shí)有 ，稱S為A的劃分。例：A={a,b,c,d},B={{a},,{c,d}},D={{a,b},{c,d}

66、},E={,{a,c,d}},F={{a},,{c}jd55drv},則B,D,E,F都是A的不同劃分。,,3.7 等價(jià)關(guān)系與劃分,定理3.7.3 集合A的一個(gè)劃分確定A的元素間的一個(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

67、 bRa，故R是對(duì)稱的。（3）若a與b在同一分塊中，b與c在同一分塊中，故有：aRb?bRc aRc，即R是傳遞的。從以上證明三點(diǎn)，說明R是A上的等價(jià)關(guān)系。,,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,b}×{a,b})U({c,d}×{c,d})U({e,f}×{e,f})={

68、,,,,,,,,,,,},,3.8 序關(guān)系,定義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，都有a≤a，故≤在實(shí)數(shù)集R上是自反的。 b)對(duì)任意實(shí)數(shù)a,b,有a≤b,b≤a，必有a=b,這說明≤在實(shí)數(shù)集上是反對(duì)稱的。

69、 c)對(duì)任意實(shí)數(shù)a,b,c,如果a≤b,b≤c,則在實(shí)數(shù)集上必有a≤c，所以≤是傳遞的。從上述三點(diǎn)，說明≤在實(shí)數(shù)集上是偏序關(guān)系。,,3.8 序關(guān)系,偏序集可以通過圖形表示。表示偏序集的圖形是哈斯圖。畫法如下：A中每個(gè)元素可用結(jié)點(diǎn)表示。對(duì)于a，b A，若a≤b，則將結(jié)點(diǎn)a畫在結(jié)點(diǎn)b下，若a與b之間不存在其他元素c，使a≤c，c≤b，則在a與b之間用一直線相連，得到的圖形為哈斯圖。因偏序集每個(gè)結(jié)點(diǎn)都有環(huán)，畫哈斯圖時(shí)可以省略

70、。,,3.8 序關(guān)系,定義3.8.4 在偏序集中，如果x，y A，x≤y，且x≠y，且沒有其他元素z，滿足x≤z，z≤y，則稱元素y蓋住元素x。記COVA={|x,y A;y蓋住x},,3.8 序關(guān)系,定義3.8.6 設(shè)是一個(gè)偏序集，且B是A的子集，對(duì)于B中一個(gè)元素b，如果沒有任何元素x，滿足b≠x，且b≤x，則稱b為B的極大元。同理，若B中沒有任何元素x，滿足b≠x，且x≤b，則稱b為B的極小元。,,3.8 序關(guān)系,定義3

71、.8.7 令為一偏序集，B A，若有元素b B,對(duì)B中每一個(gè)元素x有x≤b，則稱b為的最大元，同理，若對(duì)每一個(gè)元素x都有b≤x，則稱b為的最小元。,,3.8 序關(guān)系,定義3.8.8 令為一偏序集，B A，若有元素a A,且對(duì)B中任意元素x有x≤a，則稱a為子集B的上界，同理，若對(duì)B任意元素x都有a≤x，則稱a為B的下界。定義3.8.9 令為一偏序集，B A，若a為B的任意上界,且、若對(duì)B的所有上界y均有a≤y