自考離散數(shù)學(xué)串講

離散數(shù)學(xué)【02324】主講：王喜斌希賽網(wǎng)—專業(yè)的在線教育平臺(tái)離散數(shù)學(xué)課程包括數(shù)理邏輯、集合論、代數(shù)結(jié)構(gòu)、圖論等部分。數(shù)理邏輯包括命題演算和謂詞演算，重點(diǎn)是公式演算與推理證明；集合論的重點(diǎn)是關(guān)系理論與映射的描述；代數(shù)結(jié)構(gòu)主要是從系統(tǒng)宏觀的代數(shù)方法去研究客觀事物的各種性質(zhì)與特征；圖論則著重于數(shù)形結(jié)合的描述以及各種實(shí)際應(yīng)用。國(guó)家自學(xué)考試時(shí)間為150分鐘，在這段時(shí)間內(nèi)，如果不對(duì)離散數(shù)學(xué)的基礎(chǔ)知識(shí)有扎實(shí)的功底，就不可能得到理想的成績(jī)?？忌欢ㄒ囵B(yǎng)對(duì)概念、知識(shí)的熟練運(yùn)用。真值表、主析取和主合取范式、集合關(guān)系運(yùn)算、群環(huán)域及圖論幾部分，容易出現(xiàn)考試內(nèi)容，所占分值較高，考生要重點(diǎn)掌握。最后還要再提一下，基礎(chǔ)知識(shí)是參加離散數(shù)學(xué)自學(xué)考試的關(guān)鍵，考查基礎(chǔ)知識(shí)的基本題大約占試卷的百分之八十左右，要求我們一定要重點(diǎn)掌握。前面的選擇和填空題都是考察對(duì)基本概念和原理的掌握情況，后面的分析計(jì)算題是考查理解和運(yùn)用能力?？己藘?nèi)容與考核要求命題與命題聯(lián)結(jié)詞，要求達(dá)到“領(lǐng)會(huì)”層次。能對(duì)命題進(jìn)行符號(hào)化；掌握命題聯(lián)結(jié)詞，能夠使用聯(lián)結(jié)詞熟練構(gòu)造復(fù)合命題。命題公式的等值演算，要求達(dá)到“簡(jiǎn)單應(yīng)用”層次。掌握命題公式的概念，能夠構(gòu)造命題公式的真值表，能夠正確判斷重言式、矛盾式和可滿足公式。熟記常用的命題定律和蘊(yùn)含式，掌握命題公式的等值關(guān)系和蘊(yùn)含關(guān)系，能夠進(jìn)行簡(jiǎn)單的公式論證。聯(lián)結(jié)詞完備集，要求達(dá)到“領(lǐng)會(huì)”層次。第1章命題與命題公式重點(diǎn)：命題與命題聯(lián)結(jié)詞，將命題進(jìn)行符號(hào)化，命題公式的真值表，命題公式的化簡(jiǎn)及命題的等值演算。難點(diǎn)：命題公式的化簡(jiǎn)等值演算及其應(yīng)用第1章命題與命題公式命題基本概念數(shù)理邏輯的任務(wù)是采用數(shù)學(xué)方法研究抽象的思維規(guī)律，研究的中心問(wèn)題是推理，而推理基本要素是命題。具有確切真值的陳述句稱作命題。所謂真值就是命題為真或?yàn)榧俚男再|(zhì)。判斷一個(gè)語(yǔ)句是否為命題，首先要判斷它是否是陳述句，然后判斷是否具有唯一的真假值。在判斷一個(gè)陳述句是否具有唯一的真假時(shí)，要注意：一個(gè)陳述句的真假暫時(shí)不能唯一地確定，但總有一天可以唯一確定，與一個(gè)陳述句的真假不能唯一確定是兩件事。例如：明年國(guó)慶節(jié)是個(gè)晴天。雖然現(xiàn)在誰(shuí)也不知道它的真值，但是到了明年國(guó)慶節(jié)，就能判斷真假，因此它的真值仍然是唯一的。例如：這個(gè)語(yǔ)句是錯(cuò)的。不能判斷真值。真命題，假命題原子命題：不能再分解更簡(jiǎn)單的命題，也稱為簡(jiǎn)單命題。復(fù)合命題：能夠分解為更簡(jiǎn)單的命題。命題聯(lián)結(jié)詞：否定，合取，析取，條件，雙條件例1.1判斷下列句子中哪些構(gòu)成命題。(1)8不是素?cái)?shù);(2)雪是黑的;(3)到2049年世界人口將超過(guò)90億;(4)每臺(tái)計(jì)算機(jī)都有唯一的IP地址;(5)喜馬拉雅山好高啊!(6)基本粒子是不可分的;(7)離散數(shù)學(xué)難學(xué)嗎?(8)請(qǐng)遵守交通規(guī)則(9)x+1=2。例1.2將下面命題符號(hào)化,并指出它們的真值。(1)丌是有理數(shù);(2)所有的素?cái)?shù)都是奇數(shù);(3)6是一個(gè)合數(shù)。解:分別使用P、Q和R來(lái)表示上述三個(gè)命題:P:丌是有理數(shù)。Q:所有的素?cái)?shù)都是奇數(shù)。R:6是一個(gè)合數(shù)。丌是無(wú)理數(shù),所以P的真值為F。2是素?cái)?shù),也是偶數(shù),除此之外,其他的素?cái)?shù)都是奇數(shù)。Q的真值為F。因?yàn)?和3都是6的因子,所以6是合數(shù),R的真值為T(mén)。P￢PTFTFFTFT1.否定￢的定義五個(gè)命題聯(lián)結(jié)詞例1.3給出命題P：“今天是星期五”的否定，并用自然語(yǔ)言表示出來(lái)。解￢P：今天不是星期五2.合取∧的定義PQP∧QTTTTFFFTFFFF“并且”“既…又…”“不但…而且…”“雖然…但是…”“一面…一面…”具有對(duì)稱性P∧Q=Q∧P例1.4將下面命題符號(hào)化。(1)2既是偶數(shù),也是素?cái)?shù);(2)我今天不但聽(tīng)了離散數(shù)學(xué)課,還聽(tīng)了數(shù)據(jù)結(jié)構(gòu)課(3)今天的離散數(shù)學(xué)課停上,美元上漲。解:(1)設(shè)P:2是偶數(shù),Q:2是素?cái)?shù)。故(1)可表示為P∧Q(2)設(shè)P:我今天聽(tīng)了離散數(shù)學(xué)課,Q:我今天聽(tīng)了數(shù)據(jù)結(jié)構(gòu)課。故(2)可表示為P∧Q。(3)設(shè)P:今天的離散數(shù)學(xué)課停上,Q:今天美元上漲故(3)可表示為P∧Q。3.析取∨的定義PQP∨QTTTTFTFTTFFF具有對(duì)稱性P∨Q=Q∨P“同或”非“異或”例1.5將下面命題符號(hào)化。(1)王小林是本年度校運(yùn)動(dòng)會(huì)的跳高或100米短跑的冠軍(2)我今天或者去聽(tīng)離散數(shù)學(xué)課,或者去聽(tīng)數(shù)據(jù)結(jié)構(gòu)課。解:(1)設(shè)P:王小林是本年度校運(yùn)動(dòng)會(huì)的跳高冠軍,Q:王小林是本年度校運(yùn)動(dòng)會(huì)的100米短跑的冠軍。故(1)可表示為PVQ。這個(gè)命題表達(dá)的是王小林或者是跳高冠軍,或者是短跑冠軍,也有可能是兩個(gè)項(xiàng)目的冠軍。(2)設(shè)P:我今天去聽(tīng)離散數(shù)學(xué)課,Q:我今天去聽(tīng)數(shù)據(jù)結(jié)構(gòu)課。故(2)可表示為PVQ。這個(gè)命題表達(dá)的是我今天可能去聽(tīng)離散數(shù)學(xué)或者數(shù)據(jù)結(jié)構(gòu)課,也可能兩門(mén)課都去聽(tīng)。此處,“或”表示的是“相容”的含義,也稱為“同或”,即兩者并不互相排斥,可能同時(shí)成立。自然語(yǔ)言中有時(shí)會(huì)使用“或”來(lái)表示“相斥”的含義,即用“或”連接的兩者不能同時(shí)成立,這樣的語(yǔ)句不能表示為析取。例1.6分析以下的復(fù)合命題。(1)王小林今天或者去美國(guó),或者去歐洲。(2)王小林或者是坐火車(chē)去北京,或者是乘飛機(jī)去北京。解:(1)設(shè)P:王小林今天去美國(guó),Q:王小林今天去歐洲。顯然,如果王小林今天去了美國(guó),他就不可能去歐洲,反之也是一樣。王小林沒(méi)有分身術(shù),他只能去一個(gè)地方。所以(1)不能簡(jiǎn)單地表示為PVQ(2)設(shè)P:王小林坐火車(chē)去北京,Q:王小林乘飛機(jī)去北京。這個(gè)命題假設(shè)王小林只需乘坐一種交通工具即可到達(dá)北京。與(1)類似,王小林不能同時(shí)既坐火車(chē)又乘飛機(jī)。PVQ也不能精確地表達(dá)(2)中命題的含義。(1)和(2)所表述的這兩個(gè)例子有一個(gè)共同的特點(diǎn),即復(fù)合命題中的兩個(gè)原子命題不會(huì)同時(shí)成立，它們之間具有相斥性，這樣的“或”表示的是“異或”。實(shí)際上，（1）和（2）均可表示為：(P∧?Q)V(?P∧Q)4.P→Q的定義PQP→QTTTTFFFTTFFT不具有對(duì)稱性注意：條件（蘊(yùn)含）“如果……，則……”

“若……，則……”除非Q否則￢P；P→Q為假當(dāng)且僅當(dāng)P為真且Q為假。例1.7將下面命題符號(hào)化。(1)如果今天不下雨,我就去公園鍛煉。(2)如果我考試通過(guò),就能拿到合格證書(shū)解:(1)設(shè)P:今天下雨,Q:我去公園鍛煉故(1)可表示為P→Q。注意：僅當(dāng)今天沒(méi)有下雨而我沒(méi)去公園鍛煉時(shí),命題(1)為F(2)設(shè)P:我考試通過(guò),Q:我拿到合格證書(shū)。故(2)可表示為P→Q。需要注意,條件命題的前件和后件之間可以在語(yǔ)義上不存在邏輯關(guān)系。這與我們?nèi)粘５谋硎鍪怯胁町惖?。?.8如果雪是黑的,則房間里有20張桌子解:設(shè)P:雪是黑的;Q:房間里有20張桌子。本例還是可以符號(hào)化為:P→Q。命題p→q表示“q是p的必要條件”。自然語(yǔ)言中表示“q是p的必要條件”有許多不同的敘述方式,例如,“只要p,就q”,“因?yàn)閜,所以q”,“p僅當(dāng)q”,“只有q才p”,等等。例1.9將下列命題符號(hào)化。(1)如果今天不下雨而且不刮風(fēng),我會(huì)去爬山;(2)若今天是星期一,則明天是星期二。(3)只有今天是星期一,明天才是星期二。解:(1)設(shè)P:今天下雨,Q:今天刮風(fēng),R:我去爬山則(1)可表示為(?P??Q)→R(2)設(shè)P:今天是星期一,Q:明天是星期二。則(2)可表示為P→Q本例還隱含著另一層意思,即如果今天不是星期一(前件為假時(shí)),則明天可能是星期二,也可能不是星期二,不得而知?；蛘叻催^(guò)來(lái)說(shuō),如果明天是星期二,則不表明今天一定是星期一。要注意,命題的含義一定要和我們?nèi)粘５母拍罘珠_(kāi)。(3)設(shè)P:今天是星期一,Q:明天是星期二。則(3)可表示為Q→P本例中表述的另一層含義是“明天是星期二”的話,“今天一定是星期一”。

PQTTTTFFFTFFFT具有對(duì)稱性P?Q=Q?P“等價(jià)”“充分必要條件”“當(dāng)且僅當(dāng)”5.例1.10將下面命題符號(hào)化,并指出其真值(1)當(dāng)且僅當(dāng)實(shí)數(shù)R可以表示為分?jǐn)?shù)時(shí),R是有理數(shù);(2)√3是無(wú)理數(shù)當(dāng)且僅當(dāng)加拿大位于亞洲。解:(1)設(shè)P:實(shí)數(shù)R可以表示為分?jǐn)?shù),Q:實(shí)數(shù)R是有理數(shù)。則(1)可表示為P?Q。由數(shù)學(xué)知識(shí)可知,(1)所表述的即是有理數(shù)的定義,所以它的真值為T(mén)。(2)設(shè)P:√3是無(wú)理數(shù),Q:加拿大位于亞洲則(2)可表示為P?Q。由數(shù)學(xué)知識(shí)知,P為T(mén),而由地理知識(shí)知,Q為F,所以(2)的真值為F綜合練習(xí)設(shè)P:今天下雨,Q:今天刮風(fēng),R:我去爬山。將下面命題用自然語(yǔ)言表述。(PVQ)→?R;R→(?P∧?Q);P∧?QP→?Q;Q→P表示:今天要是下雨或者刮風(fēng),我就不去爬山了;表示:如果我去爬山了,則今天既沒(méi)下雨也沒(méi)刮風(fēng)表示:今天下雨了,但沒(méi)有刮風(fēng);表示:如果今天下雨,就不會(huì)刮風(fēng);表示:如果今天刮風(fēng),就會(huì)下雨。命題公式命題符號(hào)化的過(guò)程中,可以用一個(gè)符號(hào)表示一個(gè)命題。當(dāng)符號(hào)P代表一個(gè)具體的命題時(shí),符號(hào)P稱為命題常項(xiàng),此時(shí)P的真值是確定的,所以稱為“?！表?xiàng)。這類似于數(shù)學(xué)表達(dá)式中的一個(gè)常數(shù)。而當(dāng)符號(hào)P僅僅表示是一個(gè)命題,但并沒(méi)有指明是哪個(gè)命題時(shí),P為命題變?cè)?。命題變?cè)狿可以代表任一個(gè)命題,正如數(shù)學(xué)表達(dá)式中的一個(gè)變量一樣。如果給P代入一個(gè)真值為T(mén)的命題,P的真值為T(mén);如果代入一個(gè)真值為F的命題,P的真值為F。在代入之前,P的值是不確定的,所以稱為“變”元。一般地,命題變?cè)皇敲}。在表示數(shù)學(xué)操作時(shí),我們可以用操作符將操作數(shù)連接起來(lái),得到一個(gè)數(shù)學(xué)表達(dá)式,比如a+3。同時(shí)可以使用圓括號(hào)改變操作符的運(yùn)算次序,比如2*(x+3)。在命題邏輯中也是一樣,可以使用聯(lián)結(jié)詞將命題連接起來(lái),得到一個(gè)更復(fù)雜的命題,即復(fù)合命題。這里,命題類似于表達(dá)式中的操作數(shù),聯(lián)結(jié)詞類似于表達(dá)式中的操作符。聯(lián)結(jié)詞連接的命題符號(hào)既可以是命題常項(xiàng),也可以是命題變?cè)?。同?也可以在這樣的式子中添加圓括號(hào)。將命題用聯(lián)結(jié)詞和圓括號(hào)按一定的邏輯關(guān)系聯(lián)結(jié)起來(lái)的符號(hào)串稱為合式公式

例1.12設(shè)P、Q、R分別代表命題變?cè)蛎}常項(xiàng),給定以下字符串,判斷哪些是合式公式。(P?Q)(P?Q)V(?P??Q)P?QV(?P??Q)PV→Q解:①、②、③都是合式公式。④不是合式公式。實(shí)際上,合式公式最外層的括號(hào)是可以省略的,所以①還可以表示為:P∧Q。③本身已去掉了最外層的括號(hào)。有意思的是③與②相比,它去掉了第一對(duì)括號(hào)。數(shù)理邏輯中規(guī)定,不影響運(yùn)算次序的括號(hào)也可以省去。與數(shù)學(xué)表達(dá)式一樣,合式公式中的括號(hào)可以改變運(yùn)算次序③與②相差的只是第一對(duì)括號(hào),去掉它會(huì)不會(huì)改變運(yùn)算次序呢?這要看各聯(lián)結(jié)詞的優(yōu)先級(jí)了。命題邏輯中規(guī)定,聯(lián)結(jié)詞優(yōu)先次序依次為:?,∧,V,→,??！牡膬?yōu)先級(jí)高于V的優(yōu)先級(jí),有沒(méi)有括號(hào),都要先計(jì)算∧運(yùn)算。定義設(shè)Ai是公式A的一部分,且Ai是一個(gè)合式公式,稱Ai是A的子公式,或公式分量。例1.13指出合式公式(PVQ)?(R→(?P∧Q))中的子公式有哪些。解:它的子公式有以下一些:A1:PA2:QA3:RA4:?PA5:PVQA6:?P∧QA7:R→(?P∧Q)在命題公式中,由于有命題變?cè)某霈F(xiàn),因而真值是不確定的。用命題常項(xiàng)替換公式中的命題變?cè)Q作指派。當(dāng)將公式中出現(xiàn)的全部命題變?cè)贾概沙删唧w的命題常項(xiàng)之后,公式就成了真值確定的命題。2、指派與真值表一個(gè)含有命題變?cè)拿}公式是沒(méi)有確定真值的。只有在命題公式中每個(gè)命題變?cè)弥付ǖ拿}常量代替后，命題公式才有確定的真值，成為命題。設(shè)P為一命題公式，P1，P2，…，Pn為出現(xiàn)在P中的所有命題變?cè)?，?duì)P1，P2，…，Pn指定一組真值稱為對(duì)P的一種指派（解釋或賦值）。若指定的一種指派，使P的值為真，則稱這組值為成真指派；使P的值為假，則稱這組值為成假指派。含n個(gè)命題變?cè)拿}公式，共有2n組指派。將命題公式P在所有指派下取值情況，列成表，稱為P的真值表。真值表構(gòu)造方法：如果公式A中有n個(gè)命題符（命題變?cè)?，則A的真值表共有2n+1行。第一行稱為表頭，在表頭的第一列寫(xiě)出所有的命題符，從表頭第二列開(kāi)始，依次寫(xiě)上公式A的生成過(guò)程中生成的子串（這些子串也是子公式）。剩下的2n行，每一行對(duì)應(yīng)一個(gè)指派。一般按二進(jìn)制的加法順序依次賦值。對(duì)于每一個(gè)指派，依次求出各個(gè)子串的值，直到最后求出A的值。例如：給出(P∧Q)∨(￢P∧￢Q)的真值表。PQ￢P￢QP∧Q￢P∧￢Q(P∧Q)∨(￢P∧￢Q)11001011001000011000000110113．公式分類設(shè)A為一命題公式，若A在它的各種指派情況下，其取值均為真，則稱公式A為重言式或永真式。設(shè)A為一命題公式，若A在它的各種指派情況下，其取值均為假，則稱公式A為矛盾式或永假式。設(shè)A為一命題公式，若A在各種真值指派下至少存在一組成真指派，稱A是可滿足式。若可滿足式A至少存在一個(gè)成假賦值，則A稱為非重言式的可滿足式。公式G，H是等價(jià)的，如果在其任意的指派下其真值相同。

證明兩個(gè)公式等價(jià)或永真永假或可滿足式，可用等值演算或真值表法。常用的命題定律如下表(P.28~P.29)：

考核內(nèi)容與考核要求范式，要求達(dá)到“領(lǐng)會(huì)”層次。范式的概念，掌握范式的概念與性質(zhì)，能夠正確計(jì)算給定公式的范式。小項(xiàng)與大項(xiàng)，掌握小項(xiàng)與大項(xiàng)的概念與性質(zhì)，能夠正確計(jì)算給定公式的成真賦值、成假賦值及對(duì)應(yīng)的編碼。主范式，要求達(dá)到“簡(jiǎn)單應(yīng)用”層次。主析取范式，掌握主析取范式的概念及性質(zhì)，能夠正確計(jì)算給定公式的主析取范式。主合取范式，掌握主合取范式的概念及性質(zhì)，能夠正確計(jì)算給定公式的主合取范式。自然推理系統(tǒng)，要求達(dá)到“簡(jiǎn)單應(yīng)用”層次。第2章命題邏輯的推理理論第2章命題邏輯的推理理論重點(diǎn)：命題公式的主范式表示及相互轉(zhuǎn)換，使用P規(guī)則、T規(guī)則、CP規(guī)則進(jìn)行命題推理。難點(diǎn)：命題推理及其應(yīng)用范式的概念：命題變項(xiàng)及其否定統(tǒng)稱作文字。僅有有限個(gè)文字構(gòu)成的析取式稱作簡(jiǎn)單析取式。僅有有限個(gè)文字構(gòu)成的合取式稱作簡(jiǎn)單合取式。p,┐q等為一個(gè)文字構(gòu)成簡(jiǎn)單析取式，p∨┐p，┐p∨q等為2個(gè)文字構(gòu)成的簡(jiǎn)單析取式，┐p∨┐q∨r,p∨┐q∨r等為3個(gè)文字構(gòu)成的簡(jiǎn)單析取式。┐p,q等為一個(gè)文字構(gòu)成的簡(jiǎn)單合取式，┐p∧p，p∧┐q等為2個(gè)文字構(gòu)成的簡(jiǎn)單合取式,p∧q∧┐r,┐p∧p∧q等為3個(gè)文字構(gòu)成的簡(jiǎn)單合取式。應(yīng)該注意，一個(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式。為方便起見(jiàn)，有時(shí)用A1,A2,…,As表示s個(gè)簡(jiǎn)單析取式或s個(gè)簡(jiǎn)單合取式。簡(jiǎn)單合取式的重要特點(diǎn)是它的成真指派很容易找到，且它的永假性也容易判定一個(gè)簡(jiǎn)單合取式是永假的，當(dāng)且僅當(dāng)它至少含一個(gè)變?cè)捌浞穸ǘɡ恚海?）一個(gè)簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)及它的否定式。（2）一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變項(xiàng)及它的否定式。證明：設(shè)Ai是含n個(gè)文字的簡(jiǎn)單析取式，若Ai中既含有某個(gè)命題變項(xiàng)pj，又含有它的否定式┐pj，由交換律、排中律和零律可知，Ai為重言式。反之，若Ai為重言式，則它必同時(shí)含某個(gè)命題變項(xiàng)及它的否定式，否則，若將Ai中的不帶否定號(hào)的命題變項(xiàng)都取0，帶否定號(hào)的命題變項(xiàng)都取1，此賦值為Ai的成假賦值，這與Ai是重言式相矛盾。類似的討論可知，若Ai是含n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式，且Ai為矛盾式，則Ai中必同時(shí)含有某個(gè)命題變項(xiàng)及它的否定式，反之亦然。如：p∨┐p，p∨┐p∨r都是重言式。┐p∨q，┐p∨┐q∨r都不是重言式小項(xiàng)：

n個(gè)命題變員的合取式，稱作布爾合取或小項(xiàng)，其中每個(gè)變?cè)c它的否定不能同時(shí)存在，但兩者之一必須出現(xiàn)且僅出現(xiàn)一次。兩個(gè)命題變?cè)狿和Q，其小項(xiàng)為P∧Q，P∧￢Q，￢P∧Q，￢P∧￢Q

三個(gè)命題變?cè)拇箜?xiàng)：M000=P∨Q∨RM001=P∨Q∨￢RM010=P∨￢Q∨RM011=P∨￢Q∨￢RM100=￢P∨Q∨RM101=￢P∨Q∨￢RM110=￢P∨￢Q∨RM111=￢P∨￢Q∨￢R或記為Mi(i=0，1，2，3，4，5，6，7)。主析取范式：對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅由小項(xiàng)的析取所組成，則該等價(jià)式稱作原式的主析取范式。主合取范式：對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅由大項(xiàng)的合取所組成，則該等價(jià)式稱作原式的主合取范式。真值表法：在真值表中，一個(gè)公式的真值為T(mén)的指派所對(duì)應(yīng)的小項(xiàng)的析取，即為此公式主析取范式。在真值表中，一個(gè)公式的真值為F的指派所對(duì)應(yīng)的大項(xiàng)的合取，即為此公式主合取范式。除了真值表法外，還可以用等值演算法求主析取范式和主合取范式。

例

寫(xiě)出公式(￢p→q)→(q→￢p)的主析取范式解：方法一，真值表法：列出真值表從真值表看出，真值為1的小項(xiàng)有m00，m01，m10三項(xiàng)，故原式的析取范式為m00∨m01∨m10=(￢p∧￢q)∨(￢p∧q)∨(p∧￢q)例

求p∧q∨r的主合取范式。解：方法一，真值表法：列出真值表:PqrP∧qp∧q∨r0000000101010000110110000101011101111111從表中可以看出，真值為F所對(duì)應(yīng)的大項(xiàng)編碼有M000，M010，M100，所以與原式等價(jià)的主合取范式為M000∧M010∧M100=∏(0,2,4)方法二，等值演算法：p∧q∨r?(p∧q)∨r?(p∨r)∧(q∨r)

?(p∨(q∧￢q)∨r)∧((p∧￢p)∨q∨r)?(p∨q∨r)∧(p∨￢q∨r)∧(p∨q∨r)∧(￢p∨q∨r)

?(p∨q∨r)∧(p∨￢q∨r)∧(￢p∨q∨r)

?M000∧M010∧M100?M0∧M2∧M4=∏(0,2,4)主范式之間的關(guān)系：設(shè)命題公式A中含有n個(gè)命題變?cè)?，且A的主析取范式中含有k個(gè)小項(xiàng)mi1，mi2，…，mik，則A的主合取范式必含有2n-k個(gè)大項(xiàng)如果命題公式A的主析取范式為∑(i1,i2,…,ik)，

則A的主合取范式為：∏(0，1，2，…，i1-1，i1+1，…，ik-1，ik+1，…，2n-1)。從A的主析取范式求其主合取范式步驟為：（1）求出A的主析取范式中未包含小項(xiàng)的下標(biāo)。（2）把（1）中求出的“下標(biāo)”寫(xiě)成對(duì)應(yīng)大項(xiàng)。（3）做（2）中寫(xiě)成的大項(xiàng)合取，即為A的主合取范式。例(P→Q)∧Q主析取范式∑(1,3)=m01∨m11(P→Q)∧Q主合取范式∏(0,2)=M00∧M10（1）真值表法（2）主范式方法及等值演算法（3）構(gòu)造論證法（4）間接證明法這部分常出大題考查（1）等值公式表整理歸納(P.48)（2）推理定律表整理歸納(P.32或P.48-P.49)（3）構(gòu)造論證法常用的推理規(guī)則有：前提引入規(guī)則：在證明的任何步驟上，都可以引入前提，簡(jiǎn)稱P規(guī)則。結(jié)論引入規(guī)則：在證明的任何步驟上，所證明的結(jié)論都可作為后續(xù)證明的前提，稱為T(mén)規(guī)則。置換規(guī)則：在證明的任何步驟上，命題公式中的任何子命題公式都可以用與之等值的命題公式置換。亦記為T(mén)規(guī)則。例證明：(P∨Q)∧(P→R)∧(Q→S)├S∨R。證明：（1）P∨Q

P（步驟1，引用P規(guī)則得P∨Q）（2）￢P→Q

T.（1）E（步驟2，由（1），根據(jù)等價(jià)公式表E，引用T規(guī)則得￢P→Q）（3）Q→S

P（4）￢P→S

T.（2）（3）I（步驟4，由（2）（3），根據(jù)蘊(yùn)含公式表I，引用T規(guī)則得￢P→S）

（5）￢S→P

T.（4）E

（6）P→R

P

（7）￢S→R

T.（5）（6）I

（8）S∨R

T.（7）E

（步驟8，S∨R是有效結(jié)論）（4）間接證明法：包括附加前提和CP規(guī)則法。要注意的是，這兩種方法都要引入附加的前提，但是附加前提的引入是有目的的，不是隨心所欲的。附加前提。引入結(jié)論的否定作為前提，導(dǎo)致最后推出F，則得證。這實(shí)際上是一種反證法，有的書(shū)上也叫反證推理規(guī)則。CP規(guī)則。常用于結(jié)論為蘊(yùn)涵式情況。引入結(jié)論的前件作為前提，最后推出后件。等價(jià)證明考核內(nèi)容與考核要求謂詞的概念與表示，要求達(dá)到“領(lǐng)會(huì)”層次。理解謂詞、個(gè)體詞、命題函數(shù)的概念;能使用謂詞表示相關(guān)命題。量詞與合式公式，要求達(dá)到“識(shí)記”層次。理解全稱量詞、存在量詞的概念，能夠使用謂詞與恰當(dāng)?shù)牧吭~表示命題；理解合式公式并能夠正確判別，能指明合式公式中的指導(dǎo)變?cè)?、量詞的轄域、個(gè)體變?cè)淖杂沙霈F(xiàn)和約束出現(xiàn)等；能使用約束變?cè)拿?guī)則和自由變?cè)胍?guī)則改寫(xiě)命題公式。第3章謂詞邏輯考核內(nèi)容與考核要求謂詞演算的等價(jià)式與蘊(yùn)含式，要求達(dá)到“領(lǐng)會(huì)”層次。理解對(duì)謂詞公式賦值的含義，掌握謂詞演算的規(guī)則；熟記謂詞演算的等值式與蘊(yùn)含式。前束范式，要求達(dá)到“簡(jiǎn)單應(yīng)用”層次。理解前束范式的概念；能夠?qū)⑺o公式變換為等值的前束范式。謂詞演算的推理理論，要求達(dá)到“簡(jiǎn)單應(yīng)用”層次。掌握謂詞演算的推理理論；能夠進(jìn)行正確的構(gòu)造推理證明。第3章謂詞邏輯第3章謂詞邏輯重點(diǎn)：使用謂詞及量詞表示相關(guān)命題并能確定量詞的轄域，能將帶量詞的公式變換為等價(jià)的前束范式，能進(jìn)行正確的謂詞演算推理。難點(diǎn)：帶量詞的公式變換，即將公式變換為等價(jià)的前束范式，能夠進(jìn)行謂詞演算推理。學(xué)習(xí)指導(dǎo)謂詞演算引進(jìn)了客體和謂詞概念，并討論謂詞公式中引入量詞及其轄域的概念，為此，謂詞邏輯能處理更為復(fù)雜的問(wèn)題。本章的學(xué)習(xí)主要是在掌握命題邏輯的基礎(chǔ)上，理解個(gè)體，謂詞，量詞等概念，學(xué)會(huì)將命題進(jìn)一步用謂詞邏輯表示；在熟記謂詞邏輯中的等價(jià)式和蘊(yùn)含式的基礎(chǔ)上，將一個(gè)謂詞演算公式化為與它等價(jià)的前束范式；并能運(yùn)用US、UG、ES、EG等規(guī)則，進(jìn)行謂詞演算的推理。第3章謂詞邏輯一、謂詞的概念與表示客體（個(gè)體）和謂詞

例如，王強(qiáng)是個(gè)大學(xué)生；其中“是個(gè)大學(xué)生”是謂詞；而“王強(qiáng)”是客體（主語(yǔ)、賓語(yǔ)）。個(gè)體變項(xiàng)的取值范圍稱為個(gè)體域(或稱論域)。全總個(gè)體域。當(dāng)我們討論問(wèn)題時(shí)，作為討論對(duì)象的非空集合就稱為論域（個(gè)體域），論域中的元素就是我們要討論的對(duì)象，這就是個(gè)體。在簡(jiǎn)單命題中，表示一個(gè)個(gè)體性質(zhì)或多個(gè)個(gè)體之間關(guān)系的詞稱為謂詞。謂詞和個(gè)體一起，就構(gòu)成了簡(jiǎn)單命題中的主謂結(jié)構(gòu)。由一個(gè)謂詞，一些個(gè)體變?cè)M成的表達(dá)式簡(jiǎn)稱為謂詞變項(xiàng)或稱為命題函數(shù)。命題函數(shù)不是命題，只有命題函數(shù)中的變?cè)既樘囟ň唧w的個(gè)體時(shí)，才是確定的命題。例如L(x,y)：x小于y。若x，y為有理數(shù)，則L(x,y)為謂詞變項(xiàng)即命題函數(shù)；若x，y取3，5，則L(3,5)是謂詞常項(xiàng)，即L(3,5)是命題。謂詞變項(xiàng)中，個(gè)體變員的數(shù)目稱為謂詞變項(xiàng)的元數(shù)。如P(x1,x2,…,xn)為n元謂詞，但是當(dāng)n元謂詞中某一個(gè)體變項(xiàng)取作常量時(shí)，即P(a,x1,x2,…,xn-1)，其中a是常量，x1，x2，…，xn-1為變項(xiàng)，則上式成為n—1元謂詞。不帶個(gè)體變項(xiàng)的謂詞稱為0元謂詞。用謂詞符號(hào)化命題：先把語(yǔ)句分析成幾個(gè)簡(jiǎn)單命題與聯(lián)結(jié)詞的聯(lián)結(jié)；然后對(duì)每個(gè)簡(jiǎn)單命題，用大寫(xiě)字母表示謂詞，小寫(xiě)字母表示客體；最后把已符號(hào)化的簡(jiǎn)單命題用正確的聯(lián)結(jié)詞聯(lián)結(jié)起來(lái)。例如，用0元謂詞符號(hào)化下述命題。如果3小于4，且4小于5，則3小于5。解：設(shè)L(x,y)：x小于yL(3，4)∧L(4，5)→L(3，5)

二、合式公式對(duì)命題符號(hào)化用量詞時(shí)，首先要考慮論域的情況。用來(lái)指明論域的謂詞，稱為特性謂詞。如果事先沒(méi)有明確出個(gè)體域，則認(rèn)為個(gè)體域是全總個(gè)體域，才產(chǎn)生特性謂詞；如果事先規(guī)定了個(gè)體域，則可免去特性謂詞。在全稱量詞中，特性謂詞是條件式的前件；在存在量詞中，特性謂詞后跟一個(gè)合取項(xiàng)。

例2有些自然數(shù)是偶數(shù)。在例1，例2中，N(x)和S(x)等都是特性謂詞

例1每個(gè)自然數(shù)都是實(shí)數(shù)。形如A(x1,x2,…,xn)稱作謂詞的原子公式。為由一個(gè)謂詞，一些個(gè)體變?cè)M成的表達(dá)式稱為原子命題函數(shù)。由一個(gè)或幾個(gè)原子命題函數(shù)以及邏輯聯(lián)結(jié)詞組合而成表達(dá)式稱為復(fù)合命題函數(shù)。

在謂詞合式公式中，有的個(gè)體變?cè)瓤梢允羌s束出現(xiàn)，又可以是自由出現(xiàn)，為了避免混淆采用下面兩個(gè)改名規(guī)則：約束變?cè)拿?guī)則：將量詞轄域中，某個(gè)約束出現(xiàn)的個(gè)體變?cè)跋鄳?yīng)指導(dǎo)變?cè)某杀据犛蛑形丛霈F(xiàn)過(guò)的個(gè)體變?cè)?，其余不變。自由變?cè)胍?guī)則：對(duì)某自由出現(xiàn)的個(gè)體變?cè)捎脗€(gè)體常元或用在原子公式中和所有個(gè)體變?cè)煌膫€(gè)體變?cè)ゴ?，且處處代入?/p>

此定理可在有限論域D={a1,a2,…,an}上證明，參考教材P.60常見(jiàn)謂詞演算的等值式與蘊(yùn)含式（P.61）

前束范式的轉(zhuǎn)換步驟：先將蘊(yùn)含或等價(jià)聯(lián)結(jié)詞轉(zhuǎn)換；利用量詞否定等值式，把否定深入到命題變?cè)椭^詞公式前面；換名或替換利用量詞轄域的收縮與擴(kuò)張等值式，把量詞提到前面。

求下列公式的前束公式

謂詞演算的推理理論謂詞演算的推理方法，可以看作是命題演算推理方法的擴(kuò)張。命題演算中的推理規(guī)則如P，T和CP規(guī)則等亦可在謂詞演算推理理論中應(yīng)用。但是在謂詞推理中，必須有消去和添加量詞的規(guī)則。加入或消去量詞時(shí)，量詞必須在公式的最前端全稱量詞消去規(guī)則US全稱量詞引入規(guī)則UG存在量詞消去規(guī)則ES存在量詞引入規(guī)則EG如果同時(shí)有全稱，存在量詞，則先消存在量詞，再消全稱量詞，即先應(yīng)用ES規(guī)則，再應(yīng)用US規(guī)則。因?yàn)镋S中c是論域中的某些個(gè)體，而US中c是全部個(gè)體.推理過(guò)程中綜合使用P,T,(CP),ES,US,EG,UG.例專業(yè)委員會(huì)成員都是教授，并且是計(jì)算機(jī)設(shè)計(jì)師，有些成員是資深專家，所以有些成員是計(jì)算機(jī)設(shè)計(jì)師，且是資深專家。請(qǐng)用謂詞推理理論證明上述推理。

考核內(nèi)容與考核要求集合的基本概念，要求達(dá)到“領(lǐng)會(huì)”層次。集合的概念，了解可數(shù)集與不可數(shù)集及基數(shù)的比較;集合的表示法，包括列舉法、描述法及圖示法，了解子集的概念，能判別集合之間的相等、包含等關(guān)系。集合的運(yùn)算，要求達(dá)到“簡(jiǎn)單應(yīng)用”層次。集合的基本運(yùn)算，能正確計(jì)算集合的并、交、補(bǔ)及差，能正確求出集合的冪，領(lǐng)會(huì)集合運(yùn)算滿足的性質(zhì)；集合運(yùn)算的恒等式，掌握集合運(yùn)算的相關(guān)公式，能運(yùn)用集合的運(yùn)算定律進(jìn)行集合恒等式的證明。第4章集合考核內(nèi)容與考核要求有序?qū)εc笛卡爾積，要求達(dá)到“簡(jiǎn)單應(yīng)用”層次。有序?qū)?，掌握有序?qū)?、有序n元組的概念，掌握有序?qū)Φ募闲远x及相關(guān)定理；笛卡爾積，掌握笛卡爾積的定義及性質(zhì)。第4章集合第4章集合重點(diǎn)：集合的表示，集合的冪集及集合的運(yùn)算，集合恒等式的證明。難點(diǎn)：集合的運(yùn)算，集合恒等式的證明。集合的概念集合是指具有某種特定性質(zhì)的具體的或抽象的對(duì)象匯總而成的集體。其中，構(gòu)成集合的這些對(duì)象則稱為該集合的元素，例如，全中國(guó)人的集合，它的元素就是每一個(gè)中國(guó)人。通常用大寫(xiě)字母如A,B,S,T,...表示集合，而用小寫(xiě)字母如a,b,x,y,...表示集合的元素。若x是集合S的元素，則稱x屬于S，記為x∈S。若y不是集合S的元素，則稱y不屬于S，記為y?S。

集合的表示法：圖像法，又稱韋恩圖法、韋氏圖法，是一種利用二維平面上的點(diǎn)集表示集合的方法。一般用平面上的矩形或圓形表示一個(gè)集合，是集合的一種直觀的圖形表示法，符號(hào)法，有些集合可以用一些特殊符號(hào)表示常用符號(hào)表示的集合N：非負(fù)整數(shù)集合或自然數(shù)集合{0,1,2,3,…}N*或N+：正整數(shù)集合{1,2,3,…}Z：整數(shù)集合{…,-1,0,1,…}Q：有理數(shù)集合Q+：正有理數(shù)集合Q-：負(fù)有理數(shù)集合R：實(shí)數(shù)集合(包括有理數(shù)和無(wú)理數(shù)）R+：正實(shí)數(shù)集合R-：負(fù)實(shí)數(shù)集合C：復(fù)數(shù)集合?：空集（不含有任何元素的集合）空集有一類特殊的集合，它不包含任何元素，如{x|x∈Rx2+1=0}，稱之為空集，記為??？占莻€(gè)特殊的集合它有2個(gè)特點(diǎn)：空集?是任意一個(gè)非空集合的真子集。空集是任何一個(gè)集合的子集

。

全集在一定范圍內(nèi)，如果所有集合均為某一集合的子集，則稱該集合為全集，一般記為E或U。全集概念相當(dāng)于論域，例如考慮某大學(xué)的系或班級(jí)的學(xué)生時(shí)，該大學(xué)的全體學(xué)生組成了全集。

集合的基本運(yùn)算交集定義：由屬于A且屬于B的相同元素組成的集合，記作A∩B（或B∩A），讀作“A交B”（或“B交A”），即A∩B={x|x∈A,且x∈B}，如右圖所示。注意交集越交越少。若A包含B，則A∩B=B，A∪B=A。并集定義：由所有屬于集合A或?qū)儆诩螧的元素所組成的集合，記作A∪B（或B∪A），讀作“A并B”（或“B并A”），即A∪B={x|x∈A,或x∈B}，如右圖所示。注意并集越并越多，這與交集的情況正相反。集合的基本運(yùn)算補(bǔ)集補(bǔ)集又可分為相對(duì)補(bǔ)集（差集）和絕對(duì)補(bǔ)集。相對(duì)補(bǔ)集定義：由屬于A而不屬于B的元素組成的集合，稱為B關(guān)于A的相對(duì)補(bǔ)集，記作A-B或A\B，即A-B={x|x∈A，且x?B}。絕對(duì)補(bǔ)集定義：A關(guān)于全集合U的相對(duì)補(bǔ)集稱作A的絕對(duì)補(bǔ)集，記作A'或?u（A）或~A。有U'=Φ；Φ'=U。集合運(yùn)算的恒等式（P.71~P.72)冪等律結(jié)合律交換律分配律包含律同一律零律排中律矛盾律吸收律德摩根律雙重否定律

有序?qū)Γㄐ蚺迹簝蓚€(gè)元素x和y按一定順序組成的序列，稱為序偶或二元組，記作<x，y>或(x，y)。其中x是該序偶的第一元素，y是該序偶的第二元素。序偶與兩個(gè)元素的集合不同，對(duì)集合來(lái)說(shuō)，不要規(guī)定元素的次序，例如{x，y}和{y，x}是兩個(gè)相同的集合，而對(duì)序偶來(lái)說(shuō)，元素的次序是重要的，當(dāng)x≠y時(shí)，<x，y>≠<y，x>例如：二維平面上的一個(gè)點(diǎn)的坐標(biāo)(x,y)。笛卡爾積：設(shè)A，B為集合，如果序偶的用第一元素x是A的元素，第二元素y是B的元素，所有這樣的序偶組成的集合，叫做A和B的笛卡爾積，記作A×B

例如，A={0，1，2}，B={a，b}，A×B={<0，a>，<0，b>，<1，a>，<1，b>，<2，a>，<2，b>}，B×A={<a，0>，<a，1>，<a，2>，<b，0>，<b，1>，<b，2>}。A×B≠B×A。注意n元組是個(gè)序偶，它的第一元素本身也是序偶，是一個(gè)n-1元組。兩個(gè)集合的笛卡兒積不服從交換律，三個(gè)集合的笛卡兒積不服從結(jié)合律。集合(A×B)×C的元素都是三元組，而集合A×(B×C)的元素不符合三元組的定義。第5章關(guān)系與函數(shù)考核內(nèi)容與考核要求關(guān)系與關(guān)系的性質(zhì)，要求達(dá)到“領(lǐng)會(huì)”層次。關(guān)系的定義及表示，掌握關(guān)系的定義及三種表示方法，掌握關(guān)系的定義域與值域；關(guān)系的性質(zhì)，理解關(guān)系的性質(zhì)，包括自反性、對(duì)稱性、傳遞性、反自反性和反對(duì)稱性，能進(jìn)行正確的判斷。關(guān)系的運(yùn)算，要求達(dá)到“領(lǐng)會(huì)”層次。關(guān)系的常規(guī)運(yùn)算，能正確進(jìn)行關(guān)系的運(yùn)算；復(fù)合運(yùn)算，理解復(fù)合關(guān)系概念，能正確進(jìn)行關(guān)系的復(fù)合運(yùn)算；關(guān)系矩陣的布爾運(yùn)算，理解關(guān)系矩陣的定義，熟練進(jìn)行關(guān)系矩陣的計(jì)算；關(guān)系的閉包，理解關(guān)系的自反、對(duì)稱、傳遞閉包，能正確進(jìn)行計(jì)算、表示及判別。第5章關(guān)系與函數(shù)考核內(nèi)容與考核要求等價(jià)關(guān)系與序關(guān)系，要求達(dá)到“簡(jiǎn)單應(yīng)用”層次。等價(jià)關(guān)系，掌握等價(jià)關(guān)系、等價(jià)類、劃分等概念，能對(duì)給定的關(guān)系進(jìn)行正確判別；序關(guān)系，掌握偏序關(guān)系、擬序關(guān)系及全序關(guān)系，能正確畫(huà)出表示偏序關(guān)系的哈斯圖，能給定的關(guān)系正確判斷，正確求出偏序關(guān)系中的極大（小）元，最大（小）元。函數(shù)的概念，要求達(dá)到“領(lǐng)會(huì)”層次。函數(shù)的概念，掌握函數(shù)的概念，能正確判別所給關(guān)系是否為函數(shù)，是否是單射、滿射和雙射等；復(fù)合函數(shù)，理解復(fù)合函數(shù)概念，能正確計(jì)算函數(shù)的復(fù)合。第5章關(guān)系與函數(shù)重點(diǎn)集合上的關(guān)系與運(yùn)算集合上的函數(shù)與運(yùn)算難點(diǎn)等價(jià)關(guān)系的判定與證明相容關(guān)系的判定與證明序關(guān)系的判定與證明關(guān)系設(shè)A，B是任意兩個(gè)集合，A×B的子集R稱為從A到B的二元關(guān)系。屬于R的序偶<a，b>，稱a與b有關(guān)系R，記作aRb；不屬于R的序偶<a，b>，則稱a與b沒(méi)有關(guān)系R，記作aRb。對(duì)集合A，可構(gòu)成A到A的二元關(guān)系R，或稱R是集合A上的關(guān)系。關(guān)系與笛卡爾積是不同的。關(guān)系可能在兩個(gè)集合的部分元素之間有定義，沒(méi)有定義的元素之間不存在關(guān)系。而笛卡爾積是兩個(gè)集合全部元素之間都有定義。例設(shè)B={1，2，3，6}，求B上整除關(guān)系。

前域也稱定義域例設(shè)A={a，b，c，e}，B={a，b，d}，在A×B上關(guān)系R定義為：R={<a，b>，<a，d>，<b，d>，<c，d>}。求：domR，ranR，fldR。解：domR={a，b，c}，

ranR={b，d}，fldR={a，b，c，d}。

解

集合表示：

解

關(guān)系矩陣表示：解

關(guān)系圖表示：

集合X上二元關(guān)系R的性質(zhì)自反性反自反性集合X上二元關(guān)系R的性質(zhì)對(duì)稱性反對(duì)稱性集合X上二元關(guān)系R的性質(zhì)傳遞性注意不是自反的關(guān)系，并不一定是反自反的。例如集合A={1，2，3}，A上的關(guān)系R={<1,1>,<1,2>,<2,3>,<3,1>}，它既不是自反的，也不是反自反的。不是對(duì)稱的關(guān)系，并非就是反對(duì)稱的。例如R={<1,3>,<2,3>,<3,1>}既不是對(duì)稱的，也不是反對(duì)稱的；但是有的關(guān)系既是對(duì)稱的，又是反對(duì)稱的，例如R={<1,1>,<2,2>,<3,3>}。常見(jiàn)關(guān)系的性質(zhì)匯總表關(guān)系的常規(guī)運(yùn)算若Z和S是從集合X到Y(jié)的兩個(gè)關(guān)系，則Z，S的并、交、補(bǔ)、差仍是X到Y(jié)的關(guān)系。因?yàn)殛P(guān)系也是集合，它的元素是序偶，所以集合的各種運(yùn)算都可以應(yīng)用于同一域上的關(guān)系運(yùn)算。

例

設(shè)集合X={a，b，c}，集合Y={x，y，z}，R是集合X到集合Y的關(guān)系R={<a，x>，<b，y>，<c，z>}，求從集合Y到集合X的逆關(guān)系

其中,

關(guān)系的閉包運(yùn)算關(guān)系的閉包運(yùn)算是將已知的關(guān)系R，增加必要的序偶組成新的關(guān)系R’，使R’包含R并且具備一定的性質(zhì)（如自反性、對(duì)稱性、傳遞性等），而且添加的序偶要盡可能少。

關(guān)系的閉包運(yùn)算定理設(shè)R為非空有窮集合A上的二元關(guān)系，（1）r(R)=R∪IA（2）s(R)=R∪R-1（3）t(R)=R∪R2∪…∪Rn，其中n是集合A中元素的數(shù)目.例設(shè)A={a,b,c}，給定A上二元關(guān)系R={<a,b>,<b,c>,<c,a>}，求r(R)，s(R)，t(R)為了求出t(R)，先寫(xiě)出：相容關(guān)系設(shè)R是集合A上的關(guān)系，若R是自反的和對(duì)稱的，則稱R是A上的相容關(guān)系。相容關(guān)系的關(guān)系矩陣是主對(duì)角線元素全為1的對(duì)稱矩陣.

例設(shè)集合A={1，2，3}中的一個(gè)覆蓋為B={{1，2}，{2，3}}，求由B確定的相容關(guān)系。

等價(jià)關(guān)系設(shè)R為集合A上的一個(gè)關(guān)系，若R是自反的、對(duì)稱的和傳遞的，則R是等價(jià)關(guān)系。

例在整數(shù)集Z上同余模4的集合，可以分為4類：在整數(shù)集中以模4同余關(guān)系的數(shù)集只有上述四類，就是Z的一種劃分。

例設(shè)R是模4同余關(guān)系，則[0]R=[-4]R=[4]R=[8]R=…，[1]R=[-7]R=[-3]R=[5]R=…，[2]R=[-6]R=[-2]R=[6]R=…，[3]R=[-5]R=[-1]R=[7]R=…。

集合A上的任一等價(jià)關(guān)系R可以唯一確定A上的一個(gè)劃分：商集A/R就是這個(gè)劃分；任一劃分，可以唯一地確定A上的等價(jià)關(guān)系：定義一個(gè)關(guān)系R，aRb當(dāng)且僅當(dāng)a，b在同一分塊中，R就是這個(gè)等價(jià)關(guān)系。即集合A上給出一個(gè)劃分和給出一個(gè)等價(jià)關(guān)系是一一對(duì)應(yīng)的。相容關(guān)系和等價(jià)關(guān)系區(qū)別與聯(lián)系相容關(guān)系和覆蓋是自反的、對(duì)稱的集合中的相容關(guān)系能構(gòu)成該集合的覆蓋相容關(guān)系不一定是等價(jià)關(guān)系覆蓋不一定是劃分等價(jià)關(guān)系和劃分是自反的、對(duì)稱的和傳遞的集合中的等價(jià)關(guān)系能構(gòu)成該集合的劃分等價(jià)關(guān)系一定是相容關(guān)系劃分一定是覆蓋

解：m=12其因子集合A={1，2，3，4，6，12}，?={<1，2>，<1，3>，<1，4>，<1，6>，<1，12>，<2，4>，<2，6>，

<2，12>，<3，6>，<3，12>，<4，12>，<6，12>，<1，1>，<2，2>，<3，3>，<4，4>，<6，6>，<12，12>}，COVA={<1，2>，<1，3>，<2，4>，<2，6>，<3，6>，<4，12>，<6，12>}。哈斯圖如下整除關(guān)系的最小元是1，最大元是12;如果取子集{2，3，6}，最小元不存在，最大元是6.整除關(guān)系的極小元是1，極大元是12;如果取子集{2，3，6}，極小元是2，3，極大元是6.

最小元最大元極小元極大元

上界下界上確界下確界極小元1極大元8，12最小元1最大元無(wú)對(duì)于子集{2，3，6}極小元2，3極大元6最小元無(wú)最大元6某偏序集的哈斯圖某偏序集的哈斯圖集合上界上確界下界下確界{a,b,c}e,f,j,heaa{j,h}無(wú)無(wú)a,b,c,d,e,ff{a,c,d,f}f,j,hfaa{b,d,g}g,hga,bb上下界及上下確界可能不屬于所討論的集合

例設(shè)X={1，2，3}，Y={a,b,c}，則從X到Y(jié)的函數(shù)共有8個(gè)

單射就是只能一對(duì)一，不能多對(duì)一滿射只要Y中的元素在X中都能找到原像就行了(一對(duì)一，多對(duì)一都行).雙射就是既是單射又是滿射(一個(gè)對(duì)一個(gè),每個(gè)都不漏掉).

考核內(nèi)容與考核要求代數(shù)系統(tǒng)，要求達(dá)到“領(lǐng)會(huì)”層次。正確理解運(yùn)算及運(yùn)算的封閉性、運(yùn)算的結(jié)合律、交換律、冪等律、分配律和吸收律等；理解幺元、零元、冪等元及逆元的概念，并能正確計(jì)算。群與半群，要求達(dá)到“領(lǐng)會(huì)”層次。半群與獨(dú)異點(diǎn)，正確理解半群與獨(dú)異點(diǎn)并能進(jìn)行判斷。群，正確理解群及子群的概念，并能進(jìn)行判別，掌握子群的判別條件。環(huán)與域，要求達(dá)到“識(shí)記”層次。正確理解環(huán)與域的概念并能進(jìn)行判別。第6章代數(shù)系統(tǒng)的一般概念重點(diǎn)能正確判別半群、獨(dú)異點(diǎn)、群、環(huán)等第6章代數(shù)系統(tǒng)的一般概念難點(diǎn)能正確判別半群、獨(dú)異點(diǎn)、群、環(huán)等代數(shù)運(yùn)算/代數(shù)系統(tǒng)代數(shù)運(yùn)算的定義已經(jīng)蘊(yùn)含了封閉性，這是代數(shù)運(yùn)算與一般運(yùn)算（例如，整數(shù)中的除法運(yùn)算）的區(qū)別。幺元和零元幺元e，也稱單位元，唯一性零元o，唯一的。在元素個(gè)數(shù)大于1的代數(shù)系統(tǒng)中，關(guān)于某個(gè)二元運(yùn)算的幺元與零元是不相等的。逆元逆元一般來(lái)說(shuō)，一個(gè)元素的左逆元不一定等于它的右逆元，而且可以有左（右）逆元而沒(méi)有右（左）逆元。—個(gè)元素的左右逆元也不一定是唯一的。對(duì)于任何二元運(yùn)算，幺元是可逆的，幺元的逆元是它本身，一般零元是不可逆的。設(shè)*是集合A上可結(jié)合的二元運(yùn)算，且有幺元，如果某元素x有左逆元，則其左逆元必定也是其右逆元，且是x的唯一逆元。如果兩個(gè)代數(shù)系統(tǒng)中運(yùn)算的個(gè)數(shù)相同，對(duì)應(yīng)運(yùn)算的元數(shù)也相同，則稱這兩個(gè)代數(shù)系統(tǒng)是同類型的。同類型的代數(shù)系統(tǒng)僅僅是構(gòu)成成分相同，不一定具有相同運(yùn)算性質(zhì)。子代數(shù)不是任意一個(gè)子集和運(yùn)算都可以構(gòu)成子代數(shù)，必須該子集對(duì)這些運(yùn)算都是封閉的。子代數(shù)也是代數(shù)系統(tǒng)。二元運(yùn)算的一些重要性質(zhì)設(shè)“⊙”是非空集合A上的二元運(yùn)算，如果對(duì)任意的a、b、c∈A，有(a⊙b)⊙c=a⊙(b⊙c)，則稱運(yùn)算“⊙”滿足集合律

。設(shè)“⊙”是非空集合A上的二元運(yùn)算，如果對(duì)任意的a,b∈A，有a⊙b=b⊙a(bǔ)，則稱運(yùn)算“⊙”滿足交換律

。設(shè)(A；*，⊙)是一代數(shù)系統(tǒng)，如果對(duì)任意的a、b、c∈A，有(1)a*(b⊙c)=(a*b)⊙(a*c)，則稱“*”對(duì)“⊙”有左分配律；(2)(b⊙c)*a=(b*a)⊙(c*a)，則稱“*”對(duì)“⊙”有右分配律還有封閉性、冪等律、吸收律……

群代數(shù)系統(tǒng)<G,*>

（滿足封閉域），其中G是非空集合，*是G上的二元運(yùn)算，滿足結(jié)合律成立，即對(duì)任意x,y,z，有x*(y*z)=(x*y)*z。（半群）單位元存在，即G中存在一個(gè)元素e，對(duì)任意x，有e*x=x*e=x。（獨(dú)異點(diǎn)）逆元存在，即對(duì)任意x，存在x’，滿足x*x’=x’*x

=e。（群）則稱<G,*>是一個(gè)群。獨(dú)異點(diǎn)<N,+>,<Z,+>,<Q,+>,<R,+>中，<N,+>不是群。群的階、有限群和無(wú)限群設(shè)<G,*>是一個(gè)群，G的元素個(gè)數(shù)|G|稱為群G的階，|G|有限則稱<G,*>為有限群，|G|無(wú)限則稱<G,*>為無(wú)限群。平凡群：階為1的群<G,*>稱為平凡群，即|G|=1且G={e}.

阿貝爾群(Abel)：滿足交換律（交換群）

*eabceeabcaaecbbbceaccbae例

設(shè)G={e,a,b,c}，運(yùn)算*的定義如表所示：

這個(gè)群稱作克萊（Klein）四元群。

定理：階大于1的群（非平凡群）中沒(méi)有零元。對(duì)于平凡群，它有唯一的元素，這個(gè)元素可以看作是幺元，也可看作是零元。定理：設(shè)<G,*>是一個(gè)群，對(duì)于任意a,b，必存在唯一x，使得a*x=b.兩個(gè)定理的證明見(jiàn)教材P.117冪等元在代數(shù)系統(tǒng)<G,*>中，如果存在某元a，滿足a*a=a，則稱a為等冪元。若運(yùn)算*滿足冪等律，G中的所有元素均是冪等元。在群<G,*>中，除幺元外，再無(wú)冪等元，即幺元是唯一的冪等元。循環(huán)群在群<G,*>中，如果在G中存在某元素a，對(duì)G中的每個(gè)元素均能由a的冪組成，則稱該群是循環(huán)群，元素a是該循環(huán)群的生成元。要證明群<G,*>是循環(huán)群，則在G中找到一個(gè)生成元即可。若g為生成元，G＝(g)表示由g生成的循環(huán)群。循環(huán)群的生成元不唯一.

如果滿足a，則<G,*>是代數(shù)系統(tǒng)；如果滿足a、b，則<G,*>是半群；如果滿足a、b、c，則<G,*>是獨(dú)異點(diǎn)，也稱含幺半群；如果滿足a、b、c、d，則<G,*>是群；如果滿足a、b、c、d、e，則<G,*>是阿貝爾群，也稱交換群。環(huán)設(shè)<R，＋，·>是一個(gè)代數(shù)系統(tǒng)，如果滿足（1）<R，＋>是阿貝爾群；（2）<R，·>是半群；（3）運(yùn)算·對(duì)于運(yùn)算＋是可分配的；則稱<R，＋，·>是環(huán)。通常我們把第—個(gè)二元運(yùn)算＋稱為“加法”，把第二個(gè)二元運(yùn)算·稱為“乘法”。在環(huán)<R，＋，·>中，我們所說(shuō)的環(huán)R的幺元和零元是對(duì)于乘法而言的；而0表示的是乘法零元，也是加法幺元。整數(shù)環(huán)集合Z（整數(shù)集）對(duì)于運(yùn)算+（數(shù)學(xué)加法）是一個(gè)阿貝爾群；對(duì)于運(yùn)算×（數(shù)學(xué)乘法）是一個(gè)半群；所以集合Z是一個(gè)環(huán)（整數(shù)環(huán)）有理數(shù)環(huán)集合Q（有理數(shù)集）對(duì)于運(yùn)算+（數(shù)學(xué)加法）是一個(gè)阿貝爾群；對(duì)于運(yùn)算×（數(shù)學(xué)乘法）是一個(gè)半群；所以集合Q是一個(gè)環(huán)（有理數(shù)環(huán)）不僅如此實(shí)數(shù)集R及其上定義的普通加法和乘法也構(gòu)成環(huán)，稱為實(shí)數(shù)環(huán)。全體偶數(shù)及其上定義的普通加法和乘法也構(gòu)成環(huán)。n（n大于等于2）階實(shí)數(shù)方陣，關(guān)于矩陣的普通加法和乘法也構(gòu)成環(huán)，稱為n階實(shí)矩陣環(huán)。集合A的冪集關(guān)于集合的對(duì)稱差運(yùn)算和交運(yùn)算也構(gòu)成環(huán)。環(huán)的性質(zhì)零因子：設(shè)<R，＋，·>是環(huán)，a，b?R且a≠0，b≠0但a·b＝0，則稱a是R中的一個(gè)左零因子，b是R中的一個(gè)右零因子。若一個(gè)元素既是左零因子，又是右零因子，則稱它是一個(gè)零因子。無(wú)零因子環(huán)：設(shè)R是一個(gè)環(huán)，對(duì)于任意a，b?R，若a·b＝0則a＝0或b＝0，就稱R是一個(gè)無(wú)零因子環(huán)。環(huán)<R，＋，·>是無(wú)零因子環(huán)，當(dāng)且僅當(dāng)在R中乘法適合消去律，即對(duì)任意a，b，c?R且a≠0，若有a·b＝a·c（或b·a＝c·a），則有b＝c。無(wú)零因子環(huán)如果R中無(wú)零因子，則稱R為無(wú)零因子環(huán)。交換環(huán)如果<R，·>是可交換的，稱R為交換環(huán)。含幺環(huán)如果<R，·>是獨(dú)異點(diǎn)，則稱R是含幺環(huán)。整環(huán)如果R是無(wú)零因子環(huán)、含幺環(huán)、交換環(huán)，則R是整環(huán)。除環(huán)如果R是非平凡環(huán)，有幺元且每一個(gè)非零元素有逆元，則R是除環(huán)。域交換除環(huán)是域。除環(huán)不一定是整環(huán)，因?yàn)槌h(huán)不一定是交換的；整環(huán)不一定是除環(huán)，因?yàn)檎h(huán)的非零元素不一定有逆元；域既是整環(huán)，也是除環(huán)。數(shù)的普通加法和乘法滿足交換律，所以整數(shù)環(huán)、有理數(shù)環(huán)、實(shí)數(shù)環(huán)等均是可交換環(huán)，也都有各自的幺元1，所以也都是含幺環(huán)。偶數(shù)集及其上定義的普通加法和乘法構(gòu)成的環(huán)是交換環(huán)，但沒(méi)有幺元，所以它不是含幺環(huán)。整數(shù)環(huán)、有理數(shù)環(huán)、實(shí)數(shù)環(huán)等均是無(wú)零因子環(huán)，所以也都是整環(huán)。由于矩陣乘法不滿足交換律，故n階實(shí)矩陣環(huán)不是可交換環(huán)，單位矩陣是它的乘法幺元。集合A的冪集關(guān)于集合的對(duì)稱差運(yùn)算和交運(yùn)算構(gòu)成的環(huán)是含幺元交換環(huán)。有理數(shù)環(huán)Q和實(shí)數(shù)環(huán)R都是域。但整數(shù)環(huán)Z不是域。群阿貝爾群環(huán)交換環(huán)有單位元整環(huán)除環(huán)域無(wú)零因子考核內(nèi)容與考核要求格的基本概念，要求達(dá)到“領(lǐng)會(huì)”層次。格的定義，掌握格的概念，正確理解偏序集中任意兩個(gè)元素的最大下界、最小上界的概念并能正確判別這些元素是否存在；格的性質(zhì)，領(lǐng)會(huì)格的性質(zhì)，掌握格的兩種不同的定義方法及它們之間的聯(lián)系，能正確判別所給偏序集是否是一個(gè)格。分配格與有補(bǔ)格，要求達(dá)到“領(lǐng)會(huì)”層次。分配格，領(lǐng)會(huì)分配格的定義并能正確判別。有補(bǔ)格，領(lǐng)會(huì)有補(bǔ)格的定義并能正確判別。布爾代數(shù)，要求達(dá)到“識(shí)記”層次。了解布爾代數(shù)的概念。第7章格與布爾代數(shù)重點(diǎn)格、分配格、有補(bǔ)格的概念與性質(zhì)第7章格與布爾代數(shù)難點(diǎn)格、分配格、有補(bǔ)格的概念與性質(zhì)格含兩個(gè)元素的子集是否存在最大下界及最小上界是偏序集的一個(gè)非常重要的特征。設(shè)<L，?>是一個(gè)偏序集，如果L中任意兩個(gè)元素都有最小上界和最大下界，則稱<L，?>為格。a∨b表示{a，b}的最小上界，a∧b表示{a，b}的最大下界。設(shè)<L，?>是格，P是由格中元素及?，=，?，?，?等符號(hào)所表示的命題，如果將P中的?，?，?，?分別替換成?，?，?，?得到的命題P’稱為P的對(duì)偶命題，簡(jiǎn)稱對(duì)偶。格的對(duì)偶原理如果命題P對(duì)一切格L為真，則P的對(duì)偶命題也對(duì)一切格L為真。格的實(shí)例全序集肯定是格，但并不是所有的偏序集都是格。冪集上的偏序集<?(S),?>，由集合論知識(shí)，?(S)中任意兩個(gè)元素的最大下界為它們的交，最小上界為它們的并，所以<?(S),?>是格。正整數(shù)集合Z+，整除操作D+

，偏序集<Z+,D+>是格。Z+中子集{a,b}的最小上界是它們的最小公倍數(shù)，最大下界是它們的最大公約數(shù)。格的實(shí)例設(shè)n是一個(gè)正整數(shù)，Sn是n的所有因數(shù)組成的集合。例如，S6={1，2，3，6}，S24={1，2，3，4，6，8，12，24}.設(shè)D+整除操作，則<S6,D+>，<S8,D+>，<S24,D+>,<S30,D+>都是格。格的性質(zhì)1設(shè)<L，?>是格，對(duì)任意的a，b?L，滿足（1）a?a∨b，b?a∨b；（2）a∧b?a，a∧b?b；（3）a?b?a∨b＝b；（4）a?b?a∧b＝a.格的性質(zhì)2（1）對(duì)任意的a，b，c，d?L，如果a?d且b?c，則a∨b?d∨c，a∧b?d∧c；（2）對(duì)任意的a，b，c?L，如果a?b且a?c，則a?b∧c；（3）對(duì)任意的a，b，c?L，如果b?c，則a∨b?a∨c，a∧b?a∧c，該性質(zhì)稱為格的保序性。格的性質(zhì)3設(shè)<L，?>是格，對(duì)任意的a，b，c?L，滿足（1）交換律：a∧b＝b∧a，a∨b＝b∨a；（2）結(jié)合律：(a∧b)∧c＝a∧(b∧c)，(a∨b)∨c＝a∨(b∨c)；（3）吸收律：a∧(a∨b)＝a，a∨(a∧b)＝a。（4）等冪律：a∧a＝a，a∨a＝a；作為代數(shù)系統(tǒng)的格設(shè)<L，∨，∧>是代數(shù)系統(tǒng)，其中∨和∧是二元運(yùn)算，若∨和∧運(yùn)算滿足交換律、結(jié)合律和吸收律，則稱<L，∨，∧>是一個(gè)格。作為偏序集合的格，是通過(guò)規(guī)定一個(gè)集合L，集合L上的偏序關(guān)系?，以及偏序關(guān)系?要滿足的條件來(lái)定義的；作為代數(shù)系統(tǒng)的格，通過(guò)規(guī)定集合，集合上的運(yùn)算以及運(yùn)算所遵從的算律來(lái)定義的。今后不再區(qū)分是偏序的格還是代數(shù)系統(tǒng)的格。子格設(shè)<L，∨，∧>是格，T是L的非空子集，如果運(yùn)算∨和∧在T上是封閉的，則稱<T，∨，∧>是格L的子格。例如，<S6，D+>是<S24，D+>的子格。分配格設(shè)<L，∨，∧>是格，如果對(duì)任意的a，b，c?L，滿足a∧(b∨c)＝(a∧b)∨(a∧c)，a∨(b∧c)＝(a∨b)∧(a∨c)，則稱<L，∨，∧>是分配格。當(dāng)格中定義的兩個(gè)運(yùn)算滿足分配律時(shí)，格即是分配格。例

下圖給出了Ll，L2，L3，L4四個(gè)格，Ll，L2是分配格。L3稱鉆石格，L4稱五角格，這兩個(gè)格都不是分配格。（記住結(jié)論，可驗(yàn)證不滿足分配律）分配格判定定理格L是分配格，當(dāng)且僅當(dāng)L既不含有與五角格同構(gòu)的子格，也不含有與鉆石格同構(gòu)的子格。從該定理可以直接推得下面兩個(gè)結(jié)論：（1）每一條鏈都是分配格；（2）小于五個(gè)元素的格都是分配格。兩格同構(gòu)，實(shí)際上是兩格的偏序集合圖在結(jié)構(gòu)上是一樣的。要判斷一個(gè)格<L，∧，∨>是否分配格，則根據(jù)判定定理，如果格L中有與鉆石格或五角格同構(gòu)的子格，則格L不是分配格；否則，格L是分配格。運(yùn)用此定理時(shí)，要注意尋找的與鉆石格或五角格同構(gòu)的是格L的子格，而不是其它。例

下圖給出了Ll，L2，L3三個(gè)格Ll，L2，L3三個(gè)格都不是分配格，Ll中子格{a,b,c,d,e}與鉆石格同構(gòu)，L2中子格{a,b,c,e,f}與五角格同構(gòu)，L3中子格{a,b,c,e,f}與鉆石格同構(gòu)。格的全上界與全下界設(shè)<A，?>是一個(gè)格，如果存在元素a?A,對(duì)于?x?A，都有a?x，則稱a為格<A，?>的全下界。如果存在元素b?A,對(duì)于?x?A，都有x?b，則稱b為格<A，?>的全上界。格<A，?>的全下界就是偏序集的最小元，全上界就是偏序集的最大元。格<A，?>若存在全下界或全上界，一定是唯一的。一般地，全下界記為0，全上界記為1.有界格設(shè)<A，?>是一個(gè)格，若A存在全下界和全上界，則稱A為有界格。記作：<A,?,?,0,1>。鉆石格和五角格都是有界格，同時(shí)任何有限格L也是有界格。設(shè)L={a1,a2,…,an}，則a1?a2?…?an是L的全下界，a1?a2?…?an是L的全上界。設(shè)有限集合S，那么格<?(S)，∩，∪>中，空集就是該格的全下界，集合S就是該格的全上界。補(bǔ)元設(shè)<A,?,?,0,1>是有界格，a?A，若存在b?A，使得a?b=1，a?b=0，b稱為a的補(bǔ)元。顯然a和b互為補(bǔ)元。在任何有界格中，全下界0與全上界1總是互補(bǔ)的。而對(duì)于其它元素可能存在補(bǔ)元，也可能不存在補(bǔ)元。如果存在補(bǔ)元，可能是唯一的，也可能有多個(gè)補(bǔ)元。定理：對(duì)于有界分配格，如果它的元素存在補(bǔ)元，則一定是唯一的。根據(jù)這個(gè)定理，如果在格中某個(gè)元素有不止一個(gè)補(bǔ)元，則該格不是分配格。設(shè)<A,?,?,0,1>是有界格，若對(duì)于任意

在A中都有a的補(bǔ)元存在，則A稱為有補(bǔ)格。Ll，L2是分配格L3，L4不是分配格，哪些是有補(bǔ)格？L1中，a與c互補(bǔ)，b不存在補(bǔ)元。a是全下界，b是全上界。不是有補(bǔ)格。L2中，a與d互補(bǔ)，b與c互補(bǔ)，a是全下界，d是全上界。是有補(bǔ)格。L3中，a與e互補(bǔ)，b、c、d三個(gè)元素中，對(duì)于任意一個(gè)，另外兩個(gè)都是它的補(bǔ)元。a是全下界，e是全上界。是有補(bǔ)格。L4中，a與e互補(bǔ)，b的補(bǔ)元是c和d，c和d的補(bǔ)元都是b。a是全下界，e是全上界。是有補(bǔ)格。布爾代數(shù)一個(gè)有補(bǔ)分配格稱為布爾格（或布爾代數(shù)）。布爾代數(shù)記為<K，∧，∨，ˊ>，其中ˊ是一元運(yùn)算，補(bǔ)運(yùn)算。例集合S的冪集格<ρ(S)，∩，∪，～，φ，S>是布爾代數(shù)，也稱為集合代數(shù)，其中∩和∪分別為集合的交和并運(yùn)算，～是絕對(duì)補(bǔ)運(yùn)算，其全下界和全上界分別為空集φ和全集S。例題設(shè)B={0，1}，定義*，⊕,?運(yùn)算如下：可以驗(yàn)證，<B，*，⊕,?，0，1>是布爾格，也稱為二值布爾代數(shù)。*01000101⊕01001111x?x0110布爾格定理設(shè)K是至少包含兩個(gè)元素的集合，∧和∨為K上的兩個(gè)二元運(yùn)算，ˊ為K上的一元運(yùn)算，如果對(duì)任意a，b，c?K，滿足(H1)a∧b＝b∧a，a∨b＝b∨a（交換律）(H2)a∧(b∨c)＝(a∧b)∨(a∧c)，a∨(b∧c)＝(a∨b)∧(a∨c)（分配律）(H3)在K中存在零元0，使a∨0＝a，a∧0＝0，存在單位元1，使a∧1＝a，a∨1＝1（同一律）(H4)存在aˊK，使a∧aˊ＝0，a∨aˊ＝1（補(bǔ)元律）則<K，∧，∨，ˊ，0，1>是布爾格。布爾代數(shù)的等價(jià)定義定義設(shè)K是至少包含兩個(gè)元素的集合，∧和∨為K上的兩個(gè)二元運(yùn)算，ˊ為K上的一元運(yùn)算，如果滿足條件(H1)—(H4)，則稱<K，∧，∨，ˊ，0，1>為布爾代數(shù)。例如在命題代數(shù)中，可以驗(yàn)證命題集合上聯(lián)結(jié)詞的定義具有(H1)—(H4)各性質(zhì)，故命題集合<S，∧，∨，ˊ，0，1>構(gòu)成布爾代數(shù)。定理在布爾代數(shù)<B，∧，∨，ˊ，0，1>中，1是運(yùn)算∧的單位元，0是運(yùn)算∨的單位元?？梢宰C明，1是運(yùn)算∨的零元，0是運(yùn)算∧的零元。定理在布爾代數(shù)<B，∧，∨，ˊ，0，1>中，?a?B,(a’)’=a(雙重否定律）?a,b?B,(a?b)’=a’?b’,(a?b)’=a’?b’（德摩根律）證明時(shí)，注意布爾代數(shù)的一個(gè)性質(zhì)就是，任一元的補(bǔ)元時(shí)唯一的。例題設(shè)B={0，1}，Bn=BxBx…xB,Bn中的元素a=<a1,a2,…,an>,b=<b1,b2,…,bn>,其中ai與bi取0或1，<0,0,…,0>表示為0n，<1,1,…,1>表示為1n.定義*,⊕,?運(yùn)算如下：a*b=<a1*b1,a2*b2,…,an*bn>,a⊕b=<a1⊕b1,a2⊕b2,…,an⊕bn>,?a=<~a1,~a2,…,~an>,可以驗(yàn)證，<Bn，*,⊕,?，0n，1n>構(gòu)成布爾代數(shù)。考核內(nèi)容與考核要求圖的基本概念，要求達(dá)到“識(shí)記”層次。了解有向圖、簡(jiǎn)單圖、完全圖、零圖、圖的階、子圖、生成子圖、無(wú)向圖、關(guān)聯(lián)、鄰接、頂點(diǎn)的度、自補(bǔ)圖等基本概念；熟記圖的相關(guān)性質(zhì)。圖的連通性，要求達(dá)到“領(lǐng)會(huì)”層次。了解通路、回路、簡(jiǎn)單通路、簡(jiǎn)單回路、初級(jí)通路和初級(jí)回路的定義并能進(jìn)行識(shí)別。了解圖的連通性質(zhì)。圖的表示，要求達(dá)到“簡(jiǎn)單應(yīng)用”層次。能使用鄰接矩陣表示圖，能根據(jù)鄰接矩陣找出圖的相關(guān)元素，了解鄰接矩陣冪的含義。第8章圖重點(diǎn)：圖的定義、相關(guān)性質(zhì)以及判別方法，圖的鄰接矩陣表示法。難點(diǎn)：路徑矩陣。第8章圖圖一個(gè)圖G=<V,E>是二元組，其中V是非空有限結(jié)點(diǎn)集（頂點(diǎn)），E是連接結(jié)點(diǎn)的邊集（邊）。頂點(diǎn)的總數(shù)記為|V|，邊的總數(shù)記為|E|。如果圖中邊的數(shù)目較少（相對(duì)于頂點(diǎn)數(shù)來(lái)說(shuō)），圖稱為稀疏圖。特別地，一條邊也沒(méi)有的圖稱為零圖。反之，邊數(shù)較多的圖稱為密集圖或稠密圖。僅有一個(gè)頂點(diǎn)的圖叫做平凡圖，平凡圖必為零圖。當(dāng)圖中的邊限定為從一個(gè)頂點(diǎn)指向另一個(gè)頂點(diǎn)時(shí)，這樣的邊稱為有向邊，也稱為??；不限定方向的邊稱為無(wú)向邊。有向圖與無(wú)向圖、簡(jiǎn)單圖與多重圖圖中的邊均為有向邊的圖稱為有向圖。如果圖中僅含有無(wú)向邊，這樣的圖稱為無(wú)向圖。如果一個(gè)圖中既含有有向邊又含有