離散數(shù)學(xué)PPT精品文檔

1、1第一章 命題邏輯什么是邏輯學(xué)：邏輯學(xué)是一門研究思維形式及思維規(guī)律的科學(xué)。邏輯學(xué)的分類：辯證邏輯與形式邏輯。其中，辯證邏輯是以辯證法認(rèn)識(shí)論的世界觀為基礎(chǔ)的邏輯學(xué)；形式邏輯主要是對(duì)人的思維形式結(jié)構(gòu)和規(guī)律進(jìn)行研究的類似于語法的一門工具性2學(xué)科。思維的形式結(jié)構(gòu)主要包括概念、判斷和推理之間的結(jié)構(gòu)和聯(lián)系，其中概念是思維的基本單位，通過概念對(duì)事物是否具有某種屬性進(jìn)行肯定或否定的回答，這就是判斷。由一個(gè)或幾個(gè)判斷推出另一判斷的思維形式就是推理。研究推理有很多方法，用數(shù)學(xué)的方法研究推理的規(guī)律稱為數(shù)理邏輯。所謂的數(shù)學(xué)方法就是引進(jìn)一套符號(hào)體系的方法，所以數(shù)理邏輯又稱符號(hào)邏輯，它是從量的方面來研究思維規(guī)律的。3現(xiàn)代

2、數(shù)理邏輯分為證明論、模型論、遞歸函數(shù)論、公理化集合論等。在此我們介紹的是數(shù)理邏輯最基本的內(nèi)容：命題邏輯和謂詞邏輯。4第一節(jié) 命題與命題聯(lián)結(jié)詞什么是命題：能夠判斷真假的陳述語句。命題的真值：真（T或1)和假（F或0）命題的種類：簡(jiǎn)單命題（原子命題）與復(fù)合命題命題的表示：大寫或小寫英文字母或帶下標(biāo)的英文字母。 表示命題的字母稱為命題標(biāo)識(shí)符。命題常量與命題變?cè)罕硎敬_定命題的標(biāo)識(shí)符成為命題常量；僅僅表示命題的的位置標(biāo)志的標(biāo)識(shí)符稱為命題變?cè)?注意：命題常量具有確定的真值；而命題變?cè)梢詷?biāo)識(shí)任意命題，它不能確定真值，它本身也不是命題。常用的命題聯(lián)結(jié)詞1、否定定義：設(shè)P為一命題，P的否定是一個(gè)新的命題，

3、記為P。若P為T，P為F，若P為F， P為T。2、合取定義：設(shè)P、Q是兩個(gè)命題，P與Q的合取是一個(gè)復(fù)合命題，記為PQ。當(dāng)且僅當(dāng)P，Q6P、Q同時(shí)為T時(shí)， PQ為T，否則PQ為F。注：合取類似于自然語言中的“與”，“且”等，但又不完全相同。合取是一個(gè)二元運(yùn)算。3、析取定義：設(shè)P、Q是兩個(gè)命題，P與Q的析取是一個(gè)復(fù)合命題，記為PQ。當(dāng)且僅當(dāng)P，Q同為F時(shí)， PQ為F，否則PQ為T。注： 析取類似于自然語言中的“或”但也不完全一樣。自然語言中的“或”分為二種，即：“排斥或”與“可兼或”。而析取表示的是自然語言中的“可兼或”7析取是二元運(yùn)算。4、條件定義：給定兩個(gè)命題P、Q，它們的條件命題是一個(gè)復(fù)合命

4、題，記為PQ。當(dāng)且僅當(dāng)P為T，Q為F時(shí)，PQ為F，否則PQ為T.注： 在PQ中P成為前件，Q稱為后件。條件聯(lián)結(jié)詞與自然語言中的“如果那么”類似，但也不盡相同。善意的推斷8二元運(yùn)算5、雙條件定義：給定兩個(gè)命題P、Q，它們的雙條件命題是一個(gè)復(fù)合命題，記為PQ。當(dāng)且僅當(dāng)P、Q的真值相同時(shí)， PQ為T，否則PQ為F.注： 雙條件聯(lián)結(jié)詞與自然語言中的“當(dāng)且僅當(dāng)”，“充分必要”類似，但也不盡相同。二元運(yùn)算9命題聯(lián)結(jié)詞除了上述五個(gè)之外，還有不可兼析取、條件否定、與非、或非聯(lián)結(jié)詞。在一個(gè)復(fù)合命題中往往含有多個(gè)命題聯(lián)結(jié)詞，其運(yùn)算的次序是：、第二節(jié) 命題公式及其分類直觀地說，由命題變?cè)?、命題常量、命題聯(lián)結(jié)詞、括號(hào)

5、組成的一個(gè)有意義的式子成為命題公式。10定義：命題常量、命題變?cè)敲}公式如果A是命題公式，則A是命題公式如果A、B是命題公式，則AB、AB、AB、AB也是命題公式只有有限次地應(yīng)用 產(chǎn)生的符號(hào)串才是命題公式。命題公式的賦值：命題公式的分類：重言式、矛盾式、可滿足式11第三節(jié) 等值演算等值的概念：設(shè)A，B是兩個(gè)命題公式，p1， p2， pn為出現(xiàn)在A，B中的所有的命題變?cè)?，如果?duì)p1， p2， pn的任何一種真值指派， A，B的真值都相同，則稱A，B是等價(jià)（或等值）的。記為AB驗(yàn)證命題公式等值常用的方法有：真值表法、蘊(yùn)含法、公式法（直接證法）。1、真值表法：例：證明AB(AB)(BA)122、蘊(yùn)

6、含法：定理1：設(shè)A，B是兩個(gè)命題公式，則AB當(dāng)且僅當(dāng)AB為永真式。蘊(yùn)含的定義：定義2：如果AB為永真式，則稱A蘊(yùn)含B，記為AB蘊(yùn)含常見的性質(zhì)：1、自反性 2、傳遞性 3、如果AB， AC，則ABC 4、如果AC， BC，則ABC13由前面的例子和定理1我們馬上可以得到定理2： AB當(dāng)且僅當(dāng)AB，BA分析蘊(yùn)含的驗(yàn)證方法例1：證明：Q(PQ)P例2：證明： (P Q) P Q3、公式法常用的等值演算公式有24個(gè)。置換規(guī)則子公式：如果X是命題公式A的一部分，且X本身也是一個(gè)命題公式，則稱X是命題公式A的子公式。定理： （置換規(guī)則）設(shè)X是命題公式A的子公式，14如果X Y，則將A中的X用Y置換所得到的

7、命題公式B與A等價(jià)。例題：1、證明：(PQ) (P Q) P2、證明：(PQ) (Q R) (P Q) R對(duì)偶式：對(duì)偶的概念：對(duì)偶定理：設(shè)A，B是命題公式，如果A B，則A* B*15第四節(jié) 主析取范式與主合取范式命題公式的規(guī)范化1、命題聯(lián)結(jié)的歸約：最小命題聯(lián)結(jié)詞組2、命題范式定義1：一個(gè)命題公式稱為合取范式，如果它具有如下形式：A1 A2 An，其中A1 ， A2 ， ，An都是由命題變?cè)蚱浞穸ㄋM成的析取式。定義1：一個(gè)命題公式稱為析取范式，如果它具有如下形式：A1 A2 An，其中A1 ，16A2 ， ，An都是由命題變?cè)蚱浞穸ㄋM成的合取式。求一個(gè)命題公式的析取或合取范式的步驟：化

8、歸：將命題公式中的聯(lián)結(jié)詞化歸為，移非：利用狄.摩根律，將求非符號(hào)移到命題變?cè)那懊?。歸約：利用分配律將之化為析取或合取范式。17例子：1、(pq) r) p2、（p q) (p q)注：一個(gè)命題公式的析取或合取范式并不是唯一的。主析取范式與主合取范式定義：n個(gè)命題變?cè)暮先∈?，稱為布爾小項(xiàng)或合取，如果每個(gè)命題變?cè)蚱浞穸ú荒芡瑫r(shí)出現(xiàn)，但二者必須出現(xiàn)且僅出現(xiàn)一個(gè)。注：n個(gè)命題變?cè)獦?gòu)成的布爾小項(xiàng)有2n個(gè)布爾小項(xiàng)的編碼：命題變?cè)?1，其否定-018布爾小項(xiàng)的常見性質(zhì)：1、每個(gè)小項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為1，在其余2n -1中指派情況下均為0。2、任意兩個(gè)不同的小項(xiàng)合取式為0。3、全體小項(xiàng)的

9、析取式為1。定義：對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅有小項(xiàng)的析取所組成，則該等價(jià)式稱為原式的主析取范式。定理：在真值表中，一個(gè)公式的真值為T的指派所對(duì)應(yīng)的小項(xiàng)的析取，即為此公式19的主析取范式。證明：略命題公式的主析取范式的求法1、真值表法例1：求命題公式PQ，P Q， (PQ)的主析取范式。求命題公式(PQ) (P R) (Q R)的主析取范式2、公式法20基本步驟：1、化歸為析取范式2、合并同類同類項(xiàng)，去掉永假項(xiàng)。3、對(duì)合取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變?cè)?，即添加PP項(xiàng)，然后利用分配律展開公式。例子：求P(P Q ) ( Q P)的主析取范式。注：對(duì)于一個(gè)命題公式的主析取范式，如將其命題

10、變?cè)膫€(gè)數(shù)及出現(xiàn)次序固定后，則此公式的主析取范式是唯一的。21類似于主析取范式，也有主合取范式。定義：n個(gè)命題變?cè)奈鋈∈?，稱為布爾大項(xiàng)或析取，如果每個(gè)命題變?cè)蚱浞穸ú荒芡瑫r(shí)出現(xiàn)，但二者必須出現(xiàn)且僅出現(xiàn)一個(gè)。注：n個(gè)命題變?cè)獦?gòu)成的布爾 大項(xiàng)有2n個(gè)布爾大項(xiàng)的編碼：命題變?cè)?0，其否定-1布爾大項(xiàng)的常見性質(zhì)：1、每個(gè)大項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，22其真值為0，在其余2n -1中指派情況下均為1。2、任意兩個(gè)不同的大項(xiàng)析取式為1。3、全體大項(xiàng)的合取式為0。定義：對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅有大項(xiàng)的合取所組成，則該等價(jià)式稱為原式的主合取范式。定理：在真值表中，一個(gè)公式的真值為F的

11、指派所對(duì)應(yīng)的大項(xiàng)的合取，即為此公式的主合取范式。23證明：略求一個(gè)命題公式的主和取范式的方法，也有真值表法與公式法。其中公式法也分為三個(gè)步驟：1、化歸為合取范式2、合并同類項(xiàng)，去掉永真項(xiàng)。3、對(duì)析取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變?cè)?，即添加PP項(xiàng)，然后利用分配律展開公式。24例子：1、求(PQ) ( P R)的主合取范式。2、求(P Q)R的主合取范式。第五節(jié) 命題邏輯的推理理論定義：設(shè)A,C是兩個(gè)命題公式，如A C為一重言式，即AC，則稱C是A的有效結(jié)論，或C可以由A邏輯推出。注：通常情況下，前提可能有若干個(gè)，即：H1 H2 Hn C從定義可以看到，推理正確并不能保證結(jié)論為真，這與現(xiàn)實(shí)中的推理有所不同

12、。25如何驗(yàn)證命題邏輯的推理，通常有以下三種方法：真值表法、直接證法、間接證法（反證法）。1、真值表法：分析驗(yàn)證的方法例：一份統(tǒng)計(jì)表的錯(cuò)誤或者是由于材料不可靠，或者是由于計(jì)算有錯(cuò)誤；這份統(tǒng)計(jì)表的錯(cuò)誤不是由于材料不可靠，所以這份統(tǒng)計(jì)表是由于計(jì)算有錯(cuò)誤。262、直接證法直接證法就是由一組前提，利用一些公認(rèn)的推理規(guī)則，根據(jù)已知的等價(jià)或蘊(yùn)含公式，推演得到有效結(jié)論。在推演的過程中，還需要用到以下兩個(gè)規(guī)則：P規(guī)則：前提的推導(dǎo)過程中的任何時(shí)候都可以引入使用。T規(guī)則：在推導(dǎo)中，如果有一個(gè)或多個(gè)公式、重言蘊(yùn)含著公式S，則公式S可以引入推導(dǎo)中。27例：證明：(P Q) (P R) (Q S) S R證明(W R)

13、 V,V C S,S U, C U W3、間接證法反證法欲證H1 H2 Hn C，將 C作為一個(gè)前提加以引用，推出一個(gè)矛盾式。28例：證明AB,(BC)A證明：PQ,PR,QSSRCP規(guī)則：欲證H1H2Hn(RC),可以將R作為一個(gè)邏輯前提加以引用，證明C為真即可。（分析理由）例子：證明:A(BC),DA,BDC證明：AB,CBAC應(yīng)用簡(jiǎn)介29第二章謂詞邏輯為什么要引入謂詞邏輯：第一節(jié)謂詞的概念與表示在一個(gè)簡(jiǎn)單命題中，表示主語的詞稱為客體或個(gè)體，表示謂語的詞稱為謂詞。通?？腕w是可以獨(dú)立存在的對(duì)象，它可以是一個(gè)具體的事物，也可以是抽象的概念。謂詞一般是用來刻劃個(gè)體的性質(zhì)或個(gè)體之間的關(guān)系。30對(duì)個(gè)

14、體我們通常用小寫字母表示，而謂詞我們則用大寫字母表示。一個(gè)命題我們就可以用A(b)這種形式來表示，叫做謂詞填式。用來表示特定個(gè)體的小寫字母我們將之稱為個(gè)體常量，用來表示某一些個(gè)體的小寫字母稱為個(gè)體變量。一個(gè)個(gè)體變量的取值范圍叫做個(gè)體域或論域。將考慮的所有的事物組成的個(gè)體域，稱為全總個(gè)體域。31從前面我們可以看到，在一個(gè)謂詞填式中可以含有個(gè)體變?cè)?。定義：有一個(gè)謂詞，若干個(gè)個(gè)體變?cè)M成的表達(dá)式，稱為命題函數(shù)或謂詞變項(xiàng)。注：、在一個(gè)謂詞變項(xiàng)中，根據(jù)其所含變量的個(gè)數(shù)，有一元謂詞,，n元謂詞。其中0元謂詞是命題。、在謂詞變項(xiàng)中，如果含有變?cè)?，則它不是命題，只有對(duì)其中的變?cè)既√囟ǖ膫€(gè)體時(shí)，它才表示確定的

15、命題。32量詞使用上述概念有時(shí)還不能用符號(hào)很好地表達(dá)日常生活中的各種命題，例如：S(x)表示x是大學(xué)生，x的個(gè)體域是某單位職工。則可以理解為某單位的職工都是大學(xué)生，或某單位的有些職工是大學(xué)生。為避免這種理解上的混亂，我們引入量詞，以刻劃“所有”、“有一些”的不同概念。、全稱量詞用來表達(dá)“所有的”,“每一個(gè)”，“任一個(gè)”等33的量詞。例子：所有人都要呼吸：(x)M(x)H(x)每個(gè)學(xué)生都要參加考試： (x)P(x)Q(x)2、存在量詞 用以表示“有一些”，“至少有一個(gè)”等概念的量詞。例子：有些人是聰明的：34有的人早飯吃面包：全稱量詞與存在量詞統(tǒng)稱為量詞。在上面的例子中，每個(gè)由量詞確定的表達(dá)式，

16、都與個(gè)體域有關(guān)。我們通常總是在全總個(gè)體域中考慮問題，因此就要通過相應(yīng)的謂詞對(duì)個(gè)體變?cè)娜≈捣秶右哉f明，這就是特性謂詞。一般地，對(duì)全稱量詞，特性謂詞常做蘊(yùn)含的前件；對(duì)存在量詞，特性謂詞常作合取項(xiàng)。353637383940L(2,3)=L(3,2)=0在解釋I下，求下列謂詞公式的真值41定義：給定謂詞公式A,如對(duì)任何一種解釋，A的真值都為真，則稱A為永真的。如對(duì)任何一種解釋，A的真值都為假，則稱A為永假的。如至少有一種解釋，使得A的真值為真，則稱A為可滿足的。命題公式的推廣：命題公式的等價(jià)公式和蘊(yùn)含式均可推廣到謂詞演算中來。例如：42例：設(shè)P(x)表示x今天來校上課， P(x)表示x今天沒來校上

17、課。比較可以得到：P(x) P(x)P(x) P(x)量詞作用域的擴(kuò)張與收縮：B) B B) BB) B B) B43量詞與命題聯(lián)結(jié)詞之間的一些等價(jià)式：B(x) B(x) B(x) B(x)前束范式定義：一個(gè)謂詞公式如果量詞均在全式的開頭,它們的作用域延伸到整個(gè)公式的末尾，則該公式叫做前束范式?；拘问剑憾ɡ恚喝我庖粋€(gè)謂詞公式，均和一個(gè)前束范式等價(jià)。44例子第四節(jié) 謂詞演算的推理理論常用的等值式以及牽涉到量詞推理規(guī)則例子：略45第三章 集合、關(guān)系、映射第一節(jié) 集合的基本概念集合的定義：若干個(gè)確定事物的全體。注：若干個(gè)：可以是有限也可以是無限。組成集合的事物成為集合的元素。元素的確定性：集合的表

18、示：常用集合的習(xí)慣表示法：46子集與冪集：第二節(jié) 集合的基本運(yùn)算交、并、補(bǔ)、差、對(duì)稱差。第三節(jié) 笛卡爾積與關(guān)系序偶：有序偶與無序偶定義：設(shè)A,B是兩個(gè)集合，有所有序偶(a,b)，其中aA,bB，構(gòu)成的集合稱為集合A與B的笛卡爾積，記為：AB注：47A = 一般地： ABBA (AB)C A(BC)推廣：A1A2 An=(a1,a2,an)/aiAiAAA(n個(gè)）記為：An關(guān)系的定義： AB的任一子集稱為是A到B的一個(gè)關(guān)系。注： 空關(guān)系、全關(guān)系48A上的二元關(guān)系常用關(guān)系說明關(guān)系的定義域、值域、域關(guān)系的交、并、補(bǔ)、差仍是關(guān)系。第四節(jié) 關(guān)系的表示與關(guān)系的性質(zhì)關(guān)系的兩種表示方法：1、關(guān)系的圖表示設(shè)R是

19、有限集合A到B一個(gè)關(guān)系將集合A,B中的元素在平面上用結(jié)點(diǎn)表示49如果集合A中的元素a與集合B中的元素b有關(guān)系R，則從a到b聯(lián)結(jié)一條有向弧線。特別地：n元集合A上的一個(gè)二元關(guān)系，只需在平面上劃出n個(gè)結(jié)點(diǎn)即可。例：略2、關(guān)系的矩陣表示設(shè)A=a1,a2,am,B=b1,b2,bn是兩個(gè)集合，R是A到B個(gè)一個(gè)關(guān)系，則mn矩陣MR= 其中rij= 稱為關(guān)系R的mnmmnnrrrrrrrrr.212222111211jijiRaRaaa10?50關(guān)系矩陣。例：略關(guān)系的性質(zhì):引入：例子定義：設(shè)R是集合A上的二元關(guān)系1)如果對(duì)任意xA，有(x,x)R，則稱R是自反的2) 如果對(duì)任意xA，有(x,x)R，則稱R

20、是反自反的3)對(duì)任意x,yA，如果(x,y)R(y,x)R，則稱R是對(duì)稱的514)對(duì)任意x,yA，如果(x,y)R， (y,x)R x=y，則稱R是反對(duì)稱的5)對(duì)任意x,y,zR，如果(x,y)R，(y,z)R (x,z)R，則稱R是傳遞的。注：1)關(guān)系有可能滿足的五個(gè)性質(zhì)的圖、矩陣特征。2)自反與反自反并不是非此即彼的關(guān)系，同樣對(duì)陳與反對(duì)稱也不是相互對(duì)立的。例：設(shè)A=1,2,3，521) R=(1,1),(1,2),(3,2),(2,3),(3,3)是A上的一個(gè)二元關(guān)系，但R既不是自反的也不是反自反的。2)S=(1,2),(2,1),(1,3)是A上的一個(gè)二元關(guān)系，S既不是對(duì)稱的也不是反對(duì)稱

21、的。例題：設(shè)A=1,2,3,4，A上的關(guān)系R=(1,1),(1,3),(2,2),(3,3),(3,1),(3,4),(4,3),(4,4)53試討論R的性質(zhì)。（自反、對(duì)稱）第五節(jié)關(guān)系的運(yùn)算與閉包、求逆運(yùn)算定義：設(shè)R是集合A到B的一個(gè)二元關(guān)系，則B到A的關(guān)系(b,a)/(a,b)R稱為R的逆關(guān)系，記為R-1。注：1)規(guī)定空關(guān)系的逆關(guān)系還是空關(guān)系。2)dom(R-1)=ran(R) ;ran(R-1)=dom(R)定理：設(shè)R,R1,R2均為A到B的二元關(guān)系，則541)(R-1)-1=R2)(R1R2)-1=R1-1 R2-1 (R1 R2)-1=R1-1 R2-1 3) -1=R-14)(AB)

22、-1=BA5)(R1 - R2)-1= R1-1 - R2-1 6)如果R1R2，則R1-1 R2-1 證明：略、關(guān)系的復(fù)合運(yùn)算R55定義：設(shè)R是集合A到B關(guān)系，S是集合B到C的關(guān)系，則A到C的關(guān)系(a,c)/bB,使得(a,b)R,(b,c)S稱為關(guān)系R與S的復(fù)合。記為RS注：1) R=R = 例題：略定理：設(shè)R1,R2分別為有限集A到B,B到C的關(guān)系，則M R1 R2=M R1M R2證明：略注：1)布爾乘56例題：略定理：設(shè)R1,R2, R3分別為集合AB, B C,CD的關(guān)系，則 （R1R2) R3 R1(R2 R3)證明：注：由于關(guān)系的復(fù)合運(yùn)算滿足結(jié)合律，因此我們可以給出以下關(guān)系的方

23、冪的定義，規(guī)定：Rn=RRR（n個(gè)）57、關(guān)系的閉包運(yùn)算定義：設(shè)R是集合A上的二元關(guān)系，如果R是A上的一個(gè)自反關(guān)系，且滿足：1)R R2)對(duì)A上的任何一個(gè)自反關(guān)系R，如果R R，必有R R，則稱關(guān)系R是關(guān)系R的自反閉包，記為r(R)注：仿上可以定義一個(gè)關(guān)系的對(duì)稱閉包與傳遞閉包s(R),t(R)定理：設(shè)R是非空集合A上的二元關(guān)系，58則：1)r(R)=RIA2)s(R)=RR-13)t(R)=RR2 R3 證明：注：當(dāng)A為n元集合時(shí),t(R)=RR2 Rn例題：設(shè)A=a,b,c，R=(a,b),(a,c),(b,c),求r(R),s(R),t(R)閉包的性質(zhì)定理：設(shè)R是非空集合A上的一個(gè)關(guān)系，5

24、91)R是自反的，則r(R)=R2)R是對(duì)稱的，則s(R)=R3)R是傳遞的，則t(R)=R定理：設(shè)R1,R2是非空集合A上的關(guān)系，且R1R2，則1) r(R1)r(R2)2) s(R1)s(R2)3) t(R1)t(R2)證明：60第六節(jié)等價(jià)關(guān)系與劃分（分類）引入定義：非空集合A上的一個(gè)關(guān)系R稱為是等價(jià)關(guān)系，如果R滿足自反性、對(duì)稱性、傳遞性。例題：人群中的同姓關(guān)系；整數(shù)集合上的同余關(guān)系由同余關(guān)系引入集合的劃分，等價(jià)類以及二者之間的關(guān)系。61商集：設(shè)R是集合A上的一個(gè)等價(jià)關(guān)系，則A關(guān)于R所產(chǎn)生的劃分的所有的等價(jià)類做成的集合，稱為集合A關(guān)于等價(jià)關(guān)系R的商集，記為：A/R例題：略第七節(jié) 偏序關(guān)系定

25、義：設(shè)R是非空集合A上的關(guān)系，如果R滿足自反性、反對(duì)稱性、傳遞性，則稱R是一個(gè)偏序關(guān)系。例題：略62注：1)一個(gè)偏序關(guān)系通常用“”符號(hào)表示。2）集合A與其上的一個(gè)偏序關(guān)系“”組成的序偶稱為偏序集。例題：整除關(guān)系、小于等于關(guān)系、包含關(guān)系等偏序集的HASSE圖：1)元素用結(jié)點(diǎn)表示2)如果元素x覆蓋y，則將x畫在y的上方，并且在它們之間畫一線段。注：因?yàn)槠蚣拿總€(gè)結(jié)點(diǎn)都有環(huán)，所以在畫Hasse圖時(shí)，可以省略。63例題：略偏序集中的特殊元素1、極大元與極小元定義：設(shè)是偏序集，BA，b B，如果B中不存在元素x，使得xb,且bx（xb)，則稱b為B的極大(小）元。例：略2、最大元與最小元定義：設(shè)是偏序

26、集，BA，b B，如果對(duì)B中任意元素x，都有xb（bx)，64則稱b為B的最大（?。┰?。例：略3、上界與下界定義：設(shè)是偏序集，BA，a A，如對(duì)x B，有xa(ax)，則稱a是B的一個(gè)上(下)界例：略4、上確界與下確界定義：設(shè)是偏序集，BA，a是B的一個(gè)上（下）界，如對(duì)B的任意上（下）界x，65都有ax(xa)，則稱a是B的上(下)確界例：略例題：集合A=a,b,c的冪集關(guān)于包含關(guān)系 分析：在Hasse圖中，幾種特殊元素所處的位置。66另外幾種常見的重要的序集：定義：設(shè)A是一個(gè)非空集合，如果A上的關(guān)系R滿足反自反性和傳遞性，則稱R是A上的擬序關(guān)系。注：擬序關(guān)系通常用符號(hào)“”表示。擬序集可以表示

27、為。例題：略定義：設(shè)是集合A上的偏序關(guān)系，如果對(duì)A中的任意二個(gè)元素a,b，總有ab或ba成立，則稱是A上的全序關(guān)系或線性序關(guān)系。稱是全序集。67例題：略定義：設(shè)是一偏序集，如果A的任意非空子集都含有最小元，則稱為良序集。例題：略例1：設(shè)R是A上的二元關(guān)系，證明：1)如果R是A上的擬序關(guān)系，則r(R)是A上的偏序關(guān)系2)如果R是A上的偏序關(guān)系，則R-IA是A上的擬序關(guān)系。68例2：證明良序集必是全序集，反之則未必第八節(jié) 函數(shù)定義：設(shè)X，Y是兩個(gè)集合，f是X到Y(jié)的一個(gè)關(guān)系，如果對(duì)任意的xX，都存在唯一的yY，使得(x,y)f，則稱關(guān)系f是X到Y(jié)的一個(gè)函數(shù)。記為：f:XY或XY。注：1)如果(x,y

28、)f，則稱x是自變量，y是x在f作用下的象，(x,y)f也可以記作y=f(x),且記f(X)=f(x)/xX 2)dom(f)=X;ran(f)Y693)X到Y(jié)函數(shù)也叫做X到Y(jié)的映射。4)到的一個(gè)關(guān)系未必是函數(shù)。例題：略因?yàn)楹瘮?shù)是序偶的集合，因此函數(shù)的相等可以利用集合相等的概念加以定義。定義：設(shè)f,g均為集合A到B的函數(shù)，如果對(duì)任意xA，都有f(x)=g(x)，則稱函數(shù)f,g相等，記為f=g例題：略70思考題：假設(shè)A是m元集合，B是n元集合，則A到B的函數(shù)有多少個(gè)？三種特殊的函數(shù)：定義：假設(shè)f:XY，如果ran(f)Y，則稱f是滿射。例題：略定義：假設(shè)f:XY，如果對(duì)任意x,yX， 當(dāng)xyf(

29、x)f(y)，則稱f為單射。例題：略71定義：假設(shè)f:XY，如果f既是滿射又是單射，則稱f為雙射或一一映射。例題：略第九節(jié)逆函數(shù)和復(fù)合函數(shù)函數(shù)作為一個(gè)特殊的關(guān)系，我們可以求其逆關(guān)系，但是其逆關(guān)系未必是函數(shù)。例如：略因此，對(duì)函數(shù)求逆。要保證其逆也是一個(gè)函數(shù)，需要規(guī)定一些條件。定理：設(shè)f: XY是一個(gè)雙射函數(shù)，則f-1是72YX的雙射函數(shù)。證明：略定義：設(shè)f:XY是一雙射函數(shù)，稱YX的雙射函數(shù)f-1是f的逆函數(shù)。例：略定理：設(shè)f:XY是一雙射函數(shù)，則 (f-1)-1=f證明：略利用關(guān)系的復(fù)合我們可以給出函數(shù)的復(fù)合73定義：設(shè)函數(shù)f:XY，g:YZ，則g f=(x,z)/yY,使得y=f(x),z=

30、g(y)稱為g對(duì)f的左復(fù)合例如：略定理：設(shè)函數(shù)f:XY，g:YZ，則g對(duì)f的左復(fù)合g f是一個(gè)XZ的函數(shù)。證明：略注：根據(jù)復(fù)合函數(shù)的定義，顯然有g(shù) f(x)=g(f(x)74性質(zhì)定理：1)若g,f是滿射，則g f是滿射。2）若g,f是單射，則g f是單射。3）若g,f是雙射，則g f是雙射。證明：略定理：設(shè)函數(shù)f:XY，則f=f IX=IY f定理：設(shè)雙射函數(shù)f:XY，則f-1 f= IXf f-1= IY證明：略75定理：設(shè)f:XY，g:YZ均為雙射函數(shù)，則：(g f)-1=f-1 g-1證明：略76第四章 代數(shù)系統(tǒng)第一節(jié) 代數(shù)運(yùn)算及其性質(zhì)引入定義：一個(gè)AB到D的映射，稱為是AB到D的代數(shù)運(yùn)

31、算。注：代數(shù)運(yùn)算的表示一般地，如果 是AB到D的代數(shù)運(yùn)算， 未必是BA到D的代數(shù)運(yùn)算一個(gè)AA到A的代數(shù)運(yùn)算 叫做A上的代數(shù)元算或77A上的二元運(yùn)算或A對(duì)運(yùn)算 是封閉的凱萊運(yùn)算表代數(shù)運(yùn)算可能滿足的運(yùn)算規(guī)律：結(jié)合律、交換律、冪等律、分配律、吸收律。代數(shù)結(jié)構(gòu)：一個(gè)帶有運(yùn)算的集合稱為代數(shù)結(jié)構(gòu)或代數(shù)系統(tǒng)代數(shù)結(jié)構(gòu)中可能存在的特殊元素：零元、單位元（幺元）、可逆元78第二節(jié) 子代數(shù)與積代數(shù)定義：設(shè)為一代數(shù)系統(tǒng)，A1A，如果A1關(guān)于運(yùn)算是封閉的，則稱是的子代數(shù)。注：具有n個(gè)運(yùn)算的代數(shù)系統(tǒng)的子代數(shù)的定義例：略定義：設(shè)與是兩個(gè)代數(shù)系統(tǒng)，在AB中規(guī)定運(yùn)算： (a1,b1)(a2,b2)=(a1 a2,b1*b2)，

32、79則也是一個(gè)代數(shù)系統(tǒng)，稱為與的積代數(shù)注：具有多個(gè)運(yùn)算的代數(shù)系統(tǒng)的積代數(shù)的概念。例：略積代數(shù)的性質(zhì)：定理：設(shè)與是兩個(gè)代數(shù)系統(tǒng)， 是他們的積代數(shù)如果,*滿足交換律，則也滿足交換律80如果,*滿足結(jié)合律，則也滿足結(jié)合律如果,*滿足冪等律，則也滿足冪等律如果與都有單位元，則也有單位元。如果與都有零元，則也有零元。證明：略定理：設(shè)與是兩個(gè)代數(shù)系統(tǒng)， 是它們的積代數(shù)81如1對(duì)2， *1對(duì) *2分別滿足分配律，則1對(duì)2也滿足分配律如1對(duì)2， *1對(duì) *2分別滿足吸收律，則1對(duì)2也滿足吸收律第三節(jié) 代數(shù)系統(tǒng)的同態(tài)與同構(gòu)引入定義：設(shè)與是兩個(gè)代數(shù)系統(tǒng)，是A到B映射，如對(duì)a1,a2A,有(a1a2)=(a1)*(

33、a2)，則稱是代數(shù)系統(tǒng)到的同態(tài)映射。82注：具有多個(gè)運(yùn)算的代數(shù)系統(tǒng)的同態(tài)定義特殊的同態(tài)映射定義：設(shè)與是兩個(gè)代數(shù)系統(tǒng)，是A到B滿射，如對(duì)a1,a2A,有(a1a2)=(a1)*(a2)，則稱是代數(shù)系統(tǒng)到的同態(tài)滿射。此時(shí)也稱與是同態(tài)的。記為： 同態(tài)滿射的性質(zhì)定理1：設(shè)83如滿足交換律，則也滿足交換律如滿足結(jié)合律，則也滿足結(jié)合律如滿足冪等律，則也滿足冪等律如有單位元，則有單位元如有零元，則有零元如有單位元，aA在A中有逆元，則a的象在B中也有逆元，且a的逆元的象就是a的象的逆元。證明：略84定理2：設(shè)如1對(duì)2 滿足分配律，則*1對(duì)*2也滿足分配律如1對(duì)2 滿足吸收律，則*1對(duì)*2也滿足吸收律定義:設(shè)

34、與是兩個(gè)代數(shù)系統(tǒng)，是A到B雙射，如對(duì)a1,a2A,有(a1a2)=(a1)*(a2)，則稱是代數(shù)系統(tǒng)到的同構(gòu)映射。此時(shí)也稱與是同構(gòu)的。記為： 85注：同態(tài)具備的性質(zhì)同構(gòu)肯定具備。反之則未必自同態(tài)與自同構(gòu)例:略兩個(gè)同構(gòu)的代數(shù)結(jié)構(gòu)稱之為是代數(shù)相等的。第四節(jié) 半群與獨(dú)異點(diǎn)定義：設(shè)是一代數(shù)系統(tǒng)，如果運(yùn)算滿足結(jié)合律，則稱是半群。例：略86定義：一個(gè)具有單位元的半群稱為幺半群或獨(dú)異點(diǎn)。例：略在獨(dú)異點(diǎn)中我們可以進(jìn)一步規(guī)定：a2=aa,an+1=ana,a0=e,a-n=(a-1)n定義：是半群，BS，如果也是半群，則稱是子半群。注：驗(yàn)證方法定義：是獨(dú)異點(diǎn)，TS，如果也是半群，且eT，則稱是子獨(dú)異點(diǎn)。87第五

35、節(jié) 群與子群定義：設(shè)為一代數(shù)系統(tǒng)，如果滿足：1、G對(duì)運(yùn)算是封閉的2、運(yùn)算滿足結(jié)合律3、 有單位元4、對(duì)aG在G中有逆元?jiǎng)t稱是群。例：略有限群、無限群以及群的階88定義：如果在群中交換律成立，則稱是交換群或Abel群例：略循環(huán)群的引入：例子定義：設(shè)是群，aG，如果G中任意一個(gè)元素均可以表示為a的方冪，則稱是由a所生成的一個(gè)循環(huán)群，記為G=(a)，其中a叫做循環(huán)群G的一個(gè)生成元。注：循環(huán)群的生成元一般不唯一。有限循環(huán)群與無限循環(huán)群的構(gòu)造89群的性質(zhì)：定理1：在群中，對(duì)a,bG，方程ax=b與ya=b在G中都有唯一解定理2：在群中左、右消去律成立。即：ab=acb=c， ba=cab=c定理3：在群

36、中，單位元是唯一的冪等元定理4：在群中，(a-1)-1=a，(ab)-1=b-1a-1 ,anam=an+m，(an)m=anm90思考：(ab)n=anbn嗎？子群定義：群的非空子集H如果關(guān)于G的運(yùn)算也構(gòu)成一個(gè)群，則稱是群的一個(gè)子群，記為：HG例子：略子群的判定定理1:設(shè)H是群的非空子集,則HG對(duì)a,bHabH 對(duì)aHa-1H 91例：略定理2:設(shè)H是群的非空子集,則HG對(duì)a,bHab-H 例：略第六節(jié)環(huán)與域引入環(huán)的定義：設(shè)R,+,是一代數(shù)系統(tǒng),如果 R,+是一個(gè)交換群 R,是一個(gè)半群 在R,+,中對(duì)+滿足分配律92則稱R,+,是一個(gè)環(huán)。例：略注：在環(huán)中，關(guān)于加法：?jiǎn)挝辉覀兺ǔＳ糜浿?；元?/p>

37、a的逆元稱為a的負(fù)元，用-a記之；a+a+a na;a+(-b) a-b環(huán)中的運(yùn)算性質(zhì) a+0=0+a=a-a+a=a+(-a)=0-(-a)=a-(a+b)=-a-b930a=a0=0a(-b)=(-a)b=-(ab)(-a)(-b)=ab a(b-c)=ab-ac; (b-c)a=ba-ca a(b1+b2+bn)= ab1+ ab2+ abn(b1+b2+bn)a= b1a +b2a +bna給出與數(shù)的運(yùn)算不同的例子幾種特殊類型的環(huán)：、交換環(huán)94、有單位元環(huán)、無零因子環(huán)、整環(huán)、除環(huán)與域第七節(jié)格與布爾代數(shù)引入偏序格的定義：設(shè)是一個(gè)偏序集，如果L中任意兩個(gè)元素都有上、下確界，則稱偏序集是格。

38、例：略95在格中,我們可以規(guī)定： ab=supa,b ab=infa,b則，是格的兩個(gè)二元運(yùn)算，即：是一個(gè)代數(shù)系統(tǒng)。該代數(shù)系統(tǒng)滿足定理：在格所誘導(dǎo)的代數(shù)系統(tǒng)中，結(jié)合律、交換律、冪等律、吸收律成立。證明：略命題：設(shè)是一個(gè)代數(shù)系統(tǒng)，其中96, 都是二元運(yùn)算且滿足吸收律，則,都滿足冪等律。證明：略定理2：設(shè)是一個(gè)代數(shù)系統(tǒng)，其中, 都是二元運(yùn)算且滿足結(jié)合律、交換律、和吸收律， 則L上存在偏序關(guān)系“”，使得是一個(gè)格。證明：略定義：設(shè)是一個(gè)代數(shù)系統(tǒng)，其中, 都是二元運(yùn)算且滿足結(jié)合律、交換律、和吸收律，則稱是一個(gè)代數(shù)格。97注：在偏序格在格中,我們可以規(guī)定： ab=supa,b ab=infa,b，則是一個(gè)

39、代數(shù)格，稱為是由所誘導(dǎo)的代數(shù)格。如在代數(shù)格中，規(guī)定：abab=a(或ab=b)，則是一個(gè)偏序格，稱為是由代數(shù)格所誘導(dǎo)的偏序格。格的性質(zhì)：p.p1 設(shè)是一個(gè)格，對(duì)a,b,cL，如果ab,cd，則acbd,acbd98p.p2 設(shè)是一個(gè)格，對(duì)a,b,cL，有：a(bc)(ab)(ac) (ab)(ac)a(bc)p.p3設(shè)是一個(gè)格，對(duì)a,b,cL，如ac，則a(bc) (ab)c注：性質(zhì)3的逆也成立。子格的定義：99子格定義：設(shè)是一個(gè)代數(shù)格，S是L的子集，如果也是一個(gè)格，則稱其是格的子格。例：略注：上述定義是代數(shù)子格；對(duì)偏序格也可以定義子格；但是一個(gè)偏序子格未必是代數(shù)子格。格的同態(tài)與同構(gòu)定義：設(shè)與

40、是兩個(gè)代數(shù)格，f是L1到L2的映射，如果對(duì)任意的100a,bL1有f(a1b)=f(a)2f(b), f(a1b)=f(a)2f(b),則稱f是到同態(tài)映射。注：當(dāng)f是滿射與雙射時(shí)，有相應(yīng)的同態(tài)滿射與同構(gòu)映射。命題：設(shè)格與所誘導(dǎo)的代數(shù)系統(tǒng)為到，f是到的格同態(tài)，對(duì)x,y L1,如x 1y,則f(x) 2f(y)分配格與有補(bǔ)格定義：設(shè)是一個(gè)代數(shù)格，如果101對(duì)以及對(duì)均滿足分配律，則稱是一個(gè)分配格。注：一個(gè)格未必是分配格例如：鉆石格與五角格都不是分配格。注：一個(gè)格L是分配格當(dāng)且僅當(dāng)L不含有與鉆石格或五角格同構(gòu)的子格。分配格的簡(jiǎn)單性質(zhì) 定理1：如果在一個(gè)格中交運(yùn)算對(duì)于并運(yùn)算可分配，則并運(yùn)算對(duì)交運(yùn)算也一定

41、可分配。反之亦然。102證明：略定理2：設(shè)是一個(gè)分配格，對(duì)a,b,cL,如果ab=ac,ab=ac,則b=c證明：略103有補(bǔ)格定義：設(shè)是一個(gè)格，aL，如果對(duì)任意xL，有小xa（ax） ，則稱a是格的全上（下）界注：一個(gè)格如果有全上（下）界，則必唯一。通常全上界用表示，全下界用表示定義：一個(gè)具有全上界與全下界的格稱為有界格。記為例子：略104定理：設(shè)是有界格，則對(duì)任意aL，有a1=1,a1=a,a0=a,a0=0定義：設(shè)為有界格，aL，如果存在bL，使得ab=1,ab=0，則稱b是a的一個(gè)補(bǔ)元。105注：通常在有界格中，一個(gè)元素如果有補(bǔ)元，未必唯一。定義：在有界格中，如果每個(gè)元素都有補(bǔ)元，則稱

42、是一個(gè)有補(bǔ)格。例：略在一個(gè)有界分配格中，由前述定理2我們可以知道，如果一個(gè)元素有補(bǔ)元，則必唯一。定義：一個(gè)有補(bǔ)分配格稱為布爾代數(shù)。106第五章 圖論第一節(jié) 無向圖與有向圖定義：一個(gè)三元組G=稱為圖，其中1)V是一個(gè)非空集合，通常稱為結(jié)點(diǎn)集2)E是一個(gè)集合，通常稱為邊集3)f是從VV到E的一個(gè)映射注：1)如果E是無向邊集，則稱圖G是無向圖；如E是有向邊集，則稱圖G是有向圖2)通常當(dāng)邊集給定后，映射f即可確定，所以一般情況下，一個(gè)圖我們都用一個(gè)二元組G=來表示。1073)一條邊我們通?？梢杂闷涠它c(diǎn)構(gòu)成的序偶加以表示。無向邊用無序偶，有向邊用有序偶表示。4)如果構(gòu)成一條邊的二個(gè)結(jié)點(diǎn)相同，則該邊稱為環(huán)

43、。5)構(gòu)成兩條邊的結(jié)點(diǎn)對(duì)相同，則這兩條邊稱為平行邊。含有平行邊的圖稱為多重圖；不含平行邊和環(huán)的圖稱為簡(jiǎn)單圖。6）任何兩個(gè)結(jié)點(diǎn)之間都有邊相連的簡(jiǎn)單圖108稱為完全圖；具有n個(gè)結(jié)點(diǎn)的完全圖記為Kn顯然 Kn有n(n-1)/2條邊。7)一個(gè)具有n個(gè)結(jié)點(diǎn)，m條邊的圖稱為(n,m）圖。特別：(n,0)圖8）如果在兩個(gè)結(jié)點(diǎn)間有邊相連，則稱這兩個(gè)結(jié)點(diǎn)是鄰接的109不與任何結(jié)點(diǎn)鄰接的結(jié)點(diǎn)稱為孤立點(diǎn)。9)與結(jié)點(diǎn)v相關(guān)聯(lián)的邊的條數(shù)稱為該結(jié)點(diǎn)的度數(shù)，記為deg(v)。對(duì)有向圖而言，以該結(jié)點(diǎn)為起點(diǎn)的邊的條數(shù)稱為該結(jié)點(diǎn)的出度,記為od(v)；以該結(jié)點(diǎn)為終點(diǎn)的邊的條數(shù)稱為該結(jié)點(diǎn)的入度,記為id(v)。無向圖G如果每個(gè)結(jié)點(diǎn)

44、的度數(shù)均為k,則稱為k度正則圖例：略定理（握手定理）： =2mVvv)deg(110推論：在一個(gè)圖中，度數(shù)是奇數(shù)的結(jié)點(diǎn)有偶數(shù)個(gè)。注：對(duì)有向圖而言，顯然定義：設(shè)G=與G=是兩個(gè)無向圖，如果VV，E E則稱G是G的子圖特別地：如果VV，E E則稱G是G的真子圖如果V=V，E E則稱G是G的生成子圖定義：設(shè)G=與G=是兩個(gè)圖，如果存在雙射f: V1 V2,使得對(duì)任意mvidvodVvVv)()(111(vi,vj)E1(f(vi),f(vj) )E2,則稱f是圖G1到G2的同構(gòu)映射。此時(shí)稱圖G1與G2是同構(gòu)的，記為G1G2注：如果G1G2，則1)它們的結(jié)點(diǎn)個(gè)數(shù)相同，邊數(shù)相等2)保持邊的關(guān)聯(lián)關(guān)系3)對(duì)

45、應(yīng)的結(jié)點(diǎn)的度數(shù)相等第二節(jié) 路、回路與圖的連通性定義：在圖G中從結(jié)點(diǎn)vi到結(jié)點(diǎn)vj的點(diǎn)與邊的交替序列稱為連接vi與vj的路（通路）112vi與vj分別稱為起點(diǎn)和終點(diǎn)；通路中邊的條數(shù)稱為通路的長(zhǎng)度。如果一條路的起點(diǎn)與終點(diǎn)相同，則稱該路為回路。如果一條路中各邊互不相同，則稱該路為跡。如果一條路中，各結(jié)點(diǎn)互不相同，則稱該路為初級(jí)路或路徑。在一條回路中，除了起點(diǎn)和終點(diǎn)外，如果其余結(jié)點(diǎn)互不相同，則稱為初級(jí)回路或圈。113在一個(gè)回路中，如果有邊重復(fù)出現(xiàn)，則稱為復(fù)雜回路。注：1)在一個(gè)圖中，如果每個(gè)結(jié)點(diǎn)的度數(shù)均大于等于2，則必包含一條初級(jí)回路。2)在求路的長(zhǎng)度時(shí)，如果有環(huán)的話，計(jì)算時(shí)，環(huán)的長(zhǎng)度為2。如果有平行

46、邊，長(zhǎng)度為2。定義：在無向圖G中，如果結(jié)點(diǎn)u與v之間存在一條通路，則稱結(jié)點(diǎn)u與v是連通的。如果圖G的任何兩點(diǎn)均是連通的，則稱G是連通圖。114對(duì)有向圖其連通性可以分為強(qiáng)連通、弱連通以及單連通定義：在有向圖G=中，如果從結(jié)點(diǎn)u到v存在一條路，則稱從結(jié)點(diǎn)u到v是可達(dá)的，也稱為單向可達(dá)的。如果從結(jié)點(diǎn)u到v是可達(dá)的，從結(jié)點(diǎn)v到u也是可達(dá)的，則稱為是雙向可達(dá)的。定義：在簡(jiǎn)單有向圖D中1）如果任何一對(duì)結(jié)點(diǎn)都是單向可達(dá)的，則稱圖D是單連通的。1152）如果任何一對(duì)結(jié)點(diǎn)都是雙向可達(dá)的，則稱圖D是強(qiáng)連通的。3）如果在D中不考慮邊的方向，D是一個(gè)無向連通圖，則稱D是弱連通的。注：雙連通必為單連通，單連通必為弱連通。第三節(jié) 圖的矩陣表示一、無向圖矩陣表示1、鄰接矩陣定義：設(shè)G=是n階無向圖，且116V=v1,v2,vn，nn矩陣A=(aij)成為圖G的鄰接矩陣。其中aij表示結(jié)點(diǎn)vi,vj之間鄰接邊的條數(shù)（ij),如果（vi,vi）是環(huán)， aii =2,否則為0。例題：略鄰接矩陣的性質(zhì)：1、鄰接矩陣是對(duì)稱矩陣2、鄰接矩陣的第i行元素之和是結(jié)點(diǎn)vi的度數(shù)定理：設(shè)簡(jiǎn)單圖G的