離散數(shù)學(xué)考研習(xí)題講解

離散數(shù)學(xué)考研復(fù)習(xí)2/3/20231復(fù)習(xí)時(shí)注意準(zhǔn)確掌握每個(gè)概念靈活應(yīng)用所學(xué)定理注意解題思路清晰證明問(wèn)題時(shí),先用反向思維(從結(jié)論入手)分析問(wèn)題,再按正向思維寫出證明過(guò)程.2/3/20232全書知識(shí)網(wǎng)絡(luò)：圖論篇同構(gòu)同構(gòu)<{1,0},,,,,><p(E),~,∩,∪,－,>格與布爾代數(shù)半群,獨(dú)異點(diǎn),群,環(huán),域<P(A×A),~,∩,∪,－,,,c,r,s,t><YX,~,∩,∪,－,,,-1>代數(shù)系統(tǒng)篇n元運(yùn)算命題邏輯謂詞邏輯集合初步二元關(guān)系函數(shù)集合論篇數(shù)理邏輯篇2/3/20233總復(fù)習(xí)復(fù)習(xí)重點(diǎn)第一章命題邏輯1.聯(lián)結(jié)詞的定義(含義及真值表定義).2.會(huì)命題符號(hào)化.3.重言式的證明.4.等價(jià)公式的證明,記住并能熟練應(yīng)用常用公式.5.會(huì)寫命題公式的范式,能應(yīng)用范式解決問(wèn)題.6.熟練掌握命題邏輯三種推理方法.2/3/20234第二章謂詞邏輯1.準(zhǔn)確掌握有關(guān)概念.2.會(huì)命題符號(hào)化.(如2.3題)3.掌握常用的等價(jià)公式和重言蘊(yùn)涵式.包括:

帶量詞的公式在個(gè)體域內(nèi)展開式,量詞否定,量詞轄域擴(kuò)充,量詞分配公式.4.會(huì)用等價(jià)公式求謂詞公式的真值.(如2.13)5.會(huì)寫前束范式6.熟練掌握謂詞邏輯推理.第三章集合論初步1.集合的表示,冪集,全集,空集.2.集合的三種關(guān)系(包含,相等,真包含)的定義.3.集合的五種運(yùn)算及相關(guān)性質(zhì).4.應(yīng)用包含排斥原理.2/3/20235第四章二元關(guān)系1.關(guān)系的概念,表示方法.2.二元關(guān)系的性質(zhì)的定義,熟練掌握性質(zhì)的判斷及證明.3.掌握關(guān)系的復(fù)合,求逆及閉包運(yùn)算(計(jì)算方法及有關(guān)性質(zhì))4.掌握等價(jià)關(guān)系的判斷,證明,求等價(jià)類和商集.5.偏序關(guān)系的判斷,會(huì)畫Hasse圖,會(huì)求一個(gè)子集的極小(大)元,最小(大)元,上界與下界,最小上界及最大下界.第五章函數(shù)1.函數(shù)的定義.2.函數(shù)的類型,會(huì)判斷,會(huì)證明.3.會(huì)計(jì)算函數(shù)的復(fù)合(左復(fù)合),求逆函數(shù).知道有關(guān)性質(zhì).4.了解集合的特征函數(shù).2/3/20236第六章代數(shù)系統(tǒng)1.掌握運(yùn)算的定義.2.熟練掌握二元運(yùn)算的性質(zhì)的判斷及證明.3.掌握代數(shù)系統(tǒng)的同構(gòu)定義,會(huì)證明.了解同構(gòu)性質(zhì)的保持.4.了解半群,獨(dú)異點(diǎn),*環(huán)和*域的概念.5.熟練掌握群,子群,交換群(會(huì)證明),了解循環(huán)群.*6,子群的陪集,Lagrange定理及其推論,(會(huì)應(yīng)用).*第七章格與布爾代數(shù)*

1.掌握格的定義,了解格的性質(zhì).*2.會(huì)判斷格,分配格,有補(bǔ)格和布爾格,*3.重點(diǎn)掌握兩個(gè)元素的布爾代數(shù)的性質(zhì)(10個(gè)).*4.會(huì)寫兩個(gè)元素的布爾表達(dá)式的范式.(實(shí)質(zhì)是第一章的主析取和主合取范式).2/3/20237第八章圖論1.掌握?qǐng)D的基本概念.(特別注意同構(gòu)的概念)2.熟練掌握?qǐng)D中關(guān)于結(jié)點(diǎn)度數(shù)的定理.(會(huì)應(yīng)用)3.無(wú)向圖的連通性的判定,連通分支及連通分支數(shù)的概念.4.有向圖的可達(dá)性,強(qiáng)連通,單側(cè)連通和弱連通的判定.求強(qiáng)分圖,單側(cè)分圖和弱分圖.5.會(huì)求圖的矩陣.有向圖鄰接矩陣的應(yīng)用。6.會(huì)判定歐拉圖和漢密爾頓圖.*7.二部圖與匹配.*8.會(huì)判定平面圖,掌握歐拉公式，了解對(duì)偶圖.9.掌握樹的基本定義,v和e間的關(guān)系式.會(huì)畫生成樹,會(huì)求最小生成樹.根樹的概念,完全m叉樹,會(huì)畫最優(yōu)樹,*會(huì)設(shè)計(jì)前綴碼.2/3/20238總復(fù)習(xí)復(fù)習(xí)重點(diǎn)第一章命題邏輯1.聯(lián)結(jié)詞的定義(含義及真值表定義).2.會(huì)命題符號(hào)化.3.重言式的證明.4.重言蘊(yùn)涵式的證明,記住并能熟練應(yīng)用常用公式.5.等價(jià)公式的證明,記住并能熟練應(yīng)用常用公式.6.會(huì)寫命題公式的范式,*能應(yīng)用范式解決問(wèn)題.7.熟練掌握命題邏輯三種推理方法.2/3/20239第一章命題邏輯1.聯(lián)結(jié)詞定義了六個(gè)邏輯聯(lián)結(jié)詞，分別是：

(1)否定“”

(2)合取“∧”

(3)析取“∨”

(4)異或“

”

(5)蘊(yùn)涵“”

(6)等價(jià)“”要熟練掌握這六個(gè)聯(lián)結(jié)詞在自然語(yǔ)言中所表示的含義以及它們的真值表的定義。：否定表示“不”∧：合取表示“不但…,而且...”“并且”∨：析取表示“或者－可兼取的或”：異或表示“或者－不可兼取的或”：蘊(yùn)涵表示“如果…,則...”

:等價(jià)表示“當(dāng)且僅當(dāng)”“充分且必要”可以將這六個(gè)聯(lián)結(jié)詞看成六種“運(yùn)算”。2/3/202310聯(lián)結(jié)詞的定義(包括真值表和含義).特別要注意：“或者”的二義性,即要區(qū)分給定的“或”是“可兼取的或∨”還是“不可兼取的或”?！啊钡挠梅?，它既表示“充分條件”也表示“必要條件”,即要弄清哪個(gè)作為前件,哪個(gè)作為后件.

PQP∧QP∨QPQPQPQ

0000110

0101101

10010011111110

2/3/2023112.會(huì)命題符號(hào)化.

例如P:我有時(shí)間.Q:我上街.R:我在家.

表示P是Q的充分條件:如果p,則Q.只要P,就Q.PQ

表示P是Q的必要條件:僅當(dāng)P,才Q.只有P,才Q.QP

如果P,則Q;否則R.(PQ)(PR)3.重言式的證明.

方法1.列真值表.(R(QR)(PQ))P

方法2.用公式的等值變換,化簡(jiǎn)成1.例如證明(R(QR)(PQ))P是重言式.證:上式(R(QR)(PQ))P(PQPQ)(R(QR)(PQ))P(公式的否定公式)((R(QR))((PQ)P)(結(jié)合律)((RQ)(RR))((PP)(QP)(分配律)(RQ)(QP)RQQP1(互補(bǔ),同一律)2/3/2023124.重言蘊(yùn)涵式的證明,

記住常用的公式.

重言蘊(yùn)涵式:AB是重言式,則稱A重言蘊(yùn)涵B.(AB)

方法1.列真值表.

方法2.假設(shè)前件真,推出后件真.(即直接推理)

方法3.假設(shè)后件假,推出前件假.(即反證法)例證明(P(QR))((PQ)(PR))是重言蘊(yùn)涵式.證:假設(shè)后件(PQ)(PR)假,則PQ為1,PR為0,于是P為1,R為0,進(jìn)而又得Q為1.所以QR為0,所以前件P(QR)為0.所以(P(QR))((PQ)(PR))為重言式.

對(duì)于給定一個(gè)題,究竟是用哪種方法,原則上哪種都可以.但是哪個(gè)方法簡(jiǎn)單,要根據(jù)具體題而定.ABA

B0010111001112/3/2023135.等值公式的證明,記住常用的公式.

方法1.列真值表.

方法2.用公式的等值變換.

例如:證明P(QR)(P∧Q)RP(QR)P(QR)(PQ)R

(PQ)∨R(P∧Q)R注意:不論是證明重言蘊(yùn)涵式,還是證明等值公式以及后邊的求公式的范式,命題邏輯推理,都應(yīng)用9，23頁(yè)的公式。必須記憶一些常用的公式2/3/2023146.命題公式的范式1)析取范式:A1∨A2∨...∨An(n≥1)Ai(i=1,2..n)是合取式.

2)合取范式:A1∧A2∧...∧An(n≥1)Ai(i=1,2..n)是析取式.3)析取范式與合取范式的求法.4)極小項(xiàng)及其性質(zhì).

m3m2m1

m0PQP∧QP∧QP∧QP∧Q000000010101001010100100111110002/3/2023156)極大項(xiàng)及其性質(zhì).M0M1M2M3PQP∨QP∨QP∨QP∨Q0000

011101011

011101011011111111

07)主析取范式:A1∨A2∨...∨An(n≥1)Ai(i=1,2..n)極小項(xiàng).

8)主合取范式:A1∧A2∧...∧An(n≥1)Ai(i=1,2..n)極大項(xiàng).2/3/2023169).會(huì)求主析取范式和主合取范式.求下面命題公式的范式:A(P,Q,R)

(P∨Q)R方法1.列真值表.主析取范式A(P,Q,R)

(P∨Q)R(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)主合取范式A(P,Q,R)

(P∨Q)R

(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)PQR(P∨Q)R000100110100011110001011110011112/3/202317方法2.用公式的等值變換.主析取范式;A(P,Q,R)

(P∨Q)R(P∨Q)∨R(P∧Q)∨R(P∧Q∧(R∨R))∨((P∨P)∧(Q∨Q)∧R)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)主合取范式:A(P,Q,R)

(P∨Q)R(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)2/3/202318已知A(P,Q,R)的主析取范式中含有如下極小項(xiàng):

m0,m3,m4,m5,m7求它的主合取范式.解:A(P,Q,R)的主合取范式中含有極大項(xiàng):M1,M2,M6A(P,Q,R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)*范式的應(yīng)用如習(xí)題:安排工作(排課表),攜帶工具箱,判斷礦樣種類，判斷輸出信號(hào)

…2/3/2023197.會(huì)用三種推理方法,進(jìn)行邏輯推理.

會(huì)用三個(gè)推理規(guī)則:前提引入，結(jié)論引入，附加前提引入例如:證明((A∧B)C)∧D∧(C∨D)A∨B1.直接推理:⑴D

前提引入⑵C∨D前提引入⑶C⑴⑵析取三段論Q,(P∨Q)P⑷(A∧B)C前提引入⑸(A∧B)⑶⑷拒取式Q,PQP⑹A∨B⑸德摩根

(P∧Q)P∨Q2/3/202320((A∧B)C)∧D∧(C∨D)A∨B2.附加前提論證:適用于結(jié)論是蘊(yùn)涵式.A∨BAB⑴A附加前提引入⑵(A∧B)C前提引入(3)(A∨B)∨C蘊(yùn)涵等值式⑷A∨(

B∨C)結(jié)合律⑸A(BC)⑷蘊(yùn)涵等值式⑹BC⑴⑸

假言推理⑺D前提引入⑻C∨D前提引入⑼C⑺⑻

析取三段論(10)B⑹⑼拒取式(11)AB附加前提論證2/3/202321((A∧B)C)∧D∧(C∨D)A∨B3.歸謬法:⑴(A∨B)假設(shè)前提錯(cuò)誤⑵A∧B⑴德摩根⑶(A∧B)C前提引入⑷C

⑵

⑶假言推理⑸D前提引入⑹C∨D前提引入⑺C⑸⑹析取三段論⑻C∧C⑷⑺合取引入由⑻得出矛盾，根據(jù)歸謬法說(shuō)明推理正確。2/3/202322考研題分析：例1：將下列句子翻譯成命題公式：（1）僅當(dāng)我有時(shí)間且天不下雨，我才去鎮(zhèn)上。（2）張剛總是在圖書館看書，除非圖書館不開門或張剛生病。[分析]“僅當(dāng)”是指“僅當(dāng)”后面的事件是結(jié)論成立的必要條件；“除非”是指只要不出現(xiàn)“除非”后面的事件，則結(jié)論一定成立。[解答]（1）設(shè)P：我有時(shí)間。Q：天下雨。R：我去鎮(zhèn)上則原命題翻譯成：R(P∧Q)(2)設(shè)P:張剛在圖書館看書。Q:圖書館開門.R:張剛生病則原命題翻譯成:(Q∧R)P2/3/202323例2：甲乙丙丁4人有且僅有2人參加圍棋優(yōu)勝比賽。關(guān)于誰(shuí)參加比賽，下列4種判斷是正確的。（1）甲和乙只有一人參加。（2）丙參加，丁必參加。（3）乙或丁至多參加一人。（4）丁不參加，甲也不會(huì)參加。請(qǐng)推出哪兩個(gè)人參加了比賽。[分析]本題考察兩個(gè)知識(shí)點(diǎn)：命題公式的翻譯和范式。[解答]首先將命題符號(hào)化：設(shè)A:甲參加了比賽；B:乙參加了比賽；C:丙參加了比賽；D:丁參加了比賽。依題意有：2/3/202324（1）AB(A∧B)∨(A∧B)（2）CD(C∨D)（3）(B∧D)B∨D（4）DAD∨A所以，原命題為：((A∧B)∨(A∧B))∧(C∨D)∧(B∨D)∧(D∨A)((A∧B∧C)∨(A∧B∧D)∨(A∧B∧C)∨(A∧B∧D))∧((B∧D)∨(B∧A)∨(D∧D)∨(D∧A)(A∧B∧C∧D)∨(A∧B∧C∧D)∨(A∧B∧D)1根據(jù)題意有且僅有2人參加比賽，故(A∧B∧C∧D)真值為0，所以只有(A∧B∧C∧D)為真，甲和丁參加了比賽。2/3/202325中科院計(jì)算機(jī)技術(shù)研究所1999年離散數(shù)學(xué)考研試題和答案

一.(8分)求與公式(x2ornotx1)->x3

邏輯等值的主合取范式和主析取范式.2/3/202326一.(8分)求與公式(x2ornotx1)->x3

邏輯等值的主合取范式和主析取范式.解：(x2ornotx1)->x3

符號(hào)化為(x2

∨x1)->x3

(x2

∨x1)∨x3(x2

∧x1)∨x3

(x2∨x3)∧(x1∨x3)(x2∨x3∨(x1∧x1))∧(x1∨x3∨(x2∧x2))(x1∨x2∨x3)

∧(x1∨x2∨x3)

∧(x1∨x2∨x3)主合取范式2/3/202327(x2ornotx1)->x3

符號(hào)化為(x2

∨x1)->x3

(x2

∨x1)∨x3(x2

∧x1)∨x3

(x2∧x1∧(x3∨x3))∨(x3∧(x2∨x2)∧(x1∨x1))(x1∧x2∧x3)∨(x1∧x2∧x3)∨(x1∧x2∧x3)∨(x1∧x2∧x3)∨(x1∧x2∧x3)主析取范式2/3/202328主合取范式:(notx1ornotx2orx3)and(x1ornotx2orx3)and(x1orx2orx3)

主析取范式:(x1andnotx2andnotx3)or(x1andx2andx3)or(x1andnotx2and

x3)or(notx1andx2andx3)or(notx1andnotx2andx3)

2/3/202329二.(8分)判斷下列各公式是:1.永真式2.永假式3.其它

(1)(p->(q->r))->(q->(p->r))

(2)(notporq)<->(pand(pandq))

(3)(notporq)andnot(qornotr)andnot(rornotpornotq)

(4)(qandp)->(porq)2/3/202330二.(8分)判斷下列各公式是:1.永真式2.永假式3.其它

(1)(p->(q->r))->(q->(p->r))

解:用公式的等值演算和真值表法都較麻煩,下面先分析一下.公式具有蘊(yùn)涵式的結(jié)構(gòu),蘊(yùn)涵式真值為0當(dāng)且僅當(dāng)蘊(yùn)涵式的前件為1后件為0.假設(shè)后件為0,則可以得出q為1,p為1,r為0;這時(shí)前件也為0,所以(1)式不存在真值為0的情況,因此(1)為1永真式.2/3/202331二.(8分)判斷下列各公式是:1.永真式2.永假式3.其它

(2)(notporq)<->(pand(pandq))解:先符號(hào)化為(p∨q)(p∧(p∧q))(pq)(p∧q)

pqpqp∧q(pq)(p∧q)0010001100100

0111111

所以(2)為3.其它2/3/202332二.(8分)判斷下列各公式是:1.永真式2.永假式3.其它

(3)(notporq)andnot(qornotr)andnot(rornotpornotq)

符號(hào)化為:(p∨q)∧(q∨r)∧(r∨p∨q)解:先分析是否有可能真值為1.若真值為1,則p∨q真值為1;(q∨r)真值為1,q為0,r為1;(r∨p∨q)真值為1,則r∨p∨q真值為0,r為0,p為1,q為1,矛盾.所以(3)式不存在真值為1的情況,即是一個(gè)永假式.2/3/202333二.(8分)判斷下列各公式是:1.永真式2.永假式3.其它

解:(4)(qandp)->(porq)符號(hào)化為

(p∧q)(p∨q)(p∧q)∨(p∨q)p∨q∨p∨q1所以(4)式為1永真式.2/3/202334一、在命題邏輯中將下列命題符號(hào)化1.電燈不亮當(dāng)且僅當(dāng)燈泡或開關(guān)發(fā)生故障。

解：設(shè)p：電燈亮，q:燈泡發(fā)生故障，r：開關(guān)發(fā)生故障

2.僅當(dāng)你去，我才留下。2/3/202335例：三個(gè)人估計(jì)比賽結(jié)果，甲說(shuō)“A第一，B第二”，乙說(shuō)“C第二,D第四”,丙說(shuō)：“A第二，D第四”。結(jié)果，3人估計(jì)的都不全對(duì)，但都對(duì)了一個(gè)，問(wèn)A,B,C,D的名次。[解答]設(shè)P：A是第一；Q：B是第二；R：C是第二；S：D是第四。E：A是第二。則根據(jù)題意有：(PQ)∧(RS)∧(ES)((P∧Q)∨(P∧Q))∧((R∧S)∨(R∧S))∧((E∧S)∨(E∧S))利用分配律展開(P∧Q∧R∧S∧E)∨(P∧Q∧R∧E∧S)因R與E矛盾，故只有P∧Q∧R∧E∧S為真，即C第一，B第二，A第三，D第四。2/3/202336

第二章謂詞邏輯1.準(zhǔn)確掌握有關(guān)概念.2.會(huì)命題符號(hào)化.3.掌握常用的等值公式和重言蘊(yùn)涵式.包括:

帶量詞的公式在個(gè)體域內(nèi)展開式,量詞否定,量詞轄域擴(kuò)充,量詞分配公式.4.會(huì)用等值公式求謂詞公式的真值.5.會(huì)寫前束范式6.熟練掌握謂詞邏輯推理.2/3/2023372.會(huì)命題符號(hào)化.

命題的符號(hào)表達(dá)式與個(gè)體域有關(guān)。當(dāng)個(gè)體域擴(kuò)大時(shí)，需要添加用來(lái)表示個(gè)體特性的謂詞，稱此謂詞為特性謂詞。特性謂詞往往就是給定命題中量詞后邊的那個(gè)名詞。如“所有自然數(shù)...”、“有些大學(xué)生...”。如何添加特性謂詞，這是個(gè)十分重要的問(wèn)題，這與前邊的量詞有關(guān)。

如果前邊是全稱量詞，特性謂詞后邊是蘊(yùn)含聯(lián)結(jié)詞“→”；

如果前邊是存在量詞，特性謂詞后邊是合取聯(lián)結(jié)詞“∧”。另外有些命題里有的個(gè)體詞在句中沒有明確的量詞,而在寫它的符號(hào)表達(dá)式時(shí),必須把隱含的量詞明確的寫出來(lái).2/3/202338例如1、金子閃光,但閃光的不一定都是金子.設(shè):G(x):x是金子.F(x):x閃光.x(G(x)F(x))x(F(x)G(x))x(G(x)F(x))x(F(x)G(x))2、有些液體可以溶解所有固體.F(x):x是液體.S(x):x是固體.D(x,y):x可溶解y.x(F(x)y(S(y)D(x,y)))3、每個(gè)大學(xué)生都愛好一些體育活動(dòng)。S(x):x是大學(xué)生,L(x,y):x愛好y,P(x):x是體育活動(dòng).x(S(x)y((P(y))L(x,y)))

2/3/2023393.掌握常用的等值公式和重言蘊(yùn)涵式.包括:

帶量詞的公式在個(gè)體域內(nèi)展開式,量詞否定,量詞轄域擴(kuò)充,量詞分配公式.

設(shè)個(gè)體域?yàn)閧a1,a2,....,an}，則

1).xA(x)A(a1)∧A(a2)∧......∧A(an)2).xB(x)B(a1)∨B(a2)∨......∨B(an)1).xA(x)xA(x)2).xA(x)xA(x)1).xA(x)∨Bx(A(x)∨B)2).xA(x)∧Bx(A(x)∧B)3).xA(x)∨Bx(A(x)∨B)4).xA(x)∧Bx(Ａ(x)∧B)5).B→xA(x)x(B→A(x))2/3/2023406).B→xA(x)x(B→A(x))7).xA(x)→Bx(A(x)→B)8).xA(x)→Bx(A(x)→B)1).x(A(x)∨B(x))xA(x)∨xB(x)2).x(A(x)∧B(x))xA(x)∧xB(x)3).x(A(x)∧B(x))xA(x)∧xB(x)4).xA(x)∨xB(x)x(A(x)∨B(x))4.會(huì)用等值公式求謂詞公式的真值.例設(shè)個(gè)體域?yàn)閧1,2},A(x,y):x+y=xy,求xyA(x,y)的真值.xyA(x,y)xyA(x,y)yA(1,y)yA(2,y)(A(1,1)A(1,2))(A(2,1)A(2,2))(11)(10)12/3/2023415.將下面謂詞公式寫成前束范式(xF(x,y)yG(y))xH(x,y)(xF(x,y)yG(y)xH(x,y)(去)xF(x,y)yG(y)xH(x,y)(德.摩根)xF(x,y)yG(y)xH(x,y)(量詞否定)xF(x,z)yG(y)tH(t,z)(變?cè)獡Q名)xyt((F(x,z)G(y)H(t,z))(轄域擴(kuò)充)2/3/2023426.熟練掌握謂詞邏輯推理.1).注意使用EI、UI、EG、UG的限制條件,特別是EI,UG2).對(duì)于同一個(gè)個(gè)體變?cè)扔袔б灿袔У那疤?，去量詞時(shí)，應(yīng)先去后去，這樣才可以特指同一個(gè)個(gè)體c.3).去量詞時(shí)，該量詞必須是公式的最左邊的量詞，且此量詞的前邊無(wú)任何符號(hào)，它的轄域作用到公式末尾。下面的作法是錯(cuò)誤的：正確作法:⑴xP(x)→xQ(x)前提引入

⑴xP(x)→xQ(x)前提引入

⑵P(c)→xQ(x)UI⑴⑵xP(x)∨xQ(x)⑴蘊(yùn)涵或⑵xP(x)→Q(c)EI⑴⑶xP(x)∨xQ(x)⑵實(shí)際上x的轄域擴(kuò)充后⑷x(P(x)∨Q(x))⑶量詞改成為x⑸P(c)∨Q(c)⑷EI⑹P(c)→Q(c)⑸蘊(yùn)涵等值式2/3/202343下面的作法是錯(cuò)誤的：正確作法:⑴xP(x)前提引入⑴xP(x)前提引入⑵P(c)⑴UI⑵xP(x)⑴實(shí)際上⑴中量詞不是⑶P(c)⑵EIx而是x

⑴xyP(x,y)前提引入⑴xyP(x,y)前提引入⑵xP(x,c)EI⑴⑵yP(c,y)UI⑴令P(x,y):y是x的生母，顯然⑵是個(gè)假命題4).添加量詞時(shí)，也要加在公式的最左邊，(即新加的量詞前也無(wú)任何符號(hào)?。?且其轄域作用到公式的末尾。 例如下面作法是錯(cuò)誤的:⑴xP(x)→Q(c)前提引入

⑵

xP(x)→yQ(y)⑴EG2/3/202344例如.證明下面推理的有效性.證明:⑴x(A(x)∧D(x))

前提引入⑵A(a)∧D(a)

⑴EI⑶A(a)⑵化簡(jiǎn)規(guī)則⑷D(a)

⑵化簡(jiǎn)規(guī)則⑸x(A(x)→(B(x)→C(x)))前提引入⑹A(a)→(B(a)→C(a))⑸UI⑺B(a)→C(a))⑶⑹假言推理⑻x(A(x)→(C(x)∨D(x)))前提引入⑼A(a)→(C(a)∨D(a)))⑻UI⑽C(a)∨D(a)⑶⑼假言推理⑾C(a)⑷⑽析取三段論⑿B(a)⑺⑾拒取式⒀A(a)∧B(a))⑶⑿合取引入⒁x(A(x)∧B(x))⒀EG2/3/202345

在謂詞邏輯中符號(hào)化下列命題，并給出結(jié)論有效性的證明：如果一個(gè)人怕困難，那么他就不會(huì)獲得成功。每個(gè)人或者獲得成功或者失敗過(guò)，有些人未曾失敗過(guò)，所以有些人不怕困難。解：令H(x):x是人，D(x):x怕困難，S(x)：x獲得成功，F(xiàn)(x):x失敗過(guò)。則本題符號(hào)化為前提：結(jié)論：2/3/202346中科院99.(9分)問(wèn)anyxexistyP(x,y)->existyanyxP(x,y)是否謂詞演算的有效式?證明你的結(jié)論.解答：用謂詞公式表示：判斷xyP(x,y)→yxP(x,y)是否為重言蘊(yùn)涵式。不是，取一特定的解釋I如下：設(shè)P(x,y)：x<=y,個(gè)體域?yàn)樽匀粩?shù)集合。則有：xyP(x,y)為真，而yxP(x,y)為假，故給定公式在解釋I下為假，故不是謂詞公式的有效式。2/3/202347

四.(9分)將下列推理符號(hào)化并給出形式證明:

鳥會(huì)飛,猴子不會(huì)飛;所以,猴子不是鳥.解：設(shè)P(x):x會(huì)飛；Q(x):x是鳥；R(x):x是猴子前提：x(Q(x)→P(x)),x(R(x)→P(x))結(jié)論：x(R(x)→Q(x))證明：⑴x(Q(x)→P(x))前提引入⑵x(R(x)→P(x))前提引入⑶Q(a)→P(a)

(1)UI⑷R(a)→P(a)

⑵UI⑸P(a)→Q(a)(3)假言易位⑹R(a)→Q(a)(4)⑸假言三段論⑺x(R(x)→Q(x))

⑹UG2/3/202348中科院98：(12分)將命題"并非E1中的每個(gè)數(shù)都小于或等于E2中的每個(gè)數(shù)"按以下要求的形式

表達(dá)出來(lái):

(1)出現(xiàn)全稱量詞,不出現(xiàn)存在量詞;

(2)出現(xiàn)存在量詞,不出現(xiàn)全稱量詞.解：F(x):x屬于E1;G(x):x屬于E2;H(x,y):x小于或等于y。（1）x(F(x)→y(G(y)→H(x,y))(2)x(F(x∧y(G(y)∧H(x,y))

2/3/202349中科院2000：在謂詞邏輯中是否可以從前提x(p(x)→q(x))，x(r(x)∧q(x))推出結(jié)論x(r(x)→p(x))證明：⑴x(r(x)∧q(x))前提引入⑵r(c)∧q(c)⑴EI⑶q(c)⑵化簡(jiǎn)規(guī)則⑷r(c)⑵化簡(jiǎn)規(guī)則⑸x(p(x)→q(x))前提引入⑹p(c)→q(c)⑸UI⑺p(c)(3)⑹拒取式(8)r(c)∧p(c)(4)(7)合取引入(9)x(r(x)∧p(x))(8)EG(10)

x(r(x)∨p(x))⑼德摩根（11）x(r(x)→p(x))（10）量詞轉(zhuǎn)換，蘊(yùn)涵等值式2/3/202350重慶大學(xué)98年：用推理規(guī)則證明：x(P(x)∨Q(x))xP(x)→xQ(x)證明：⑴xP(x)附加前提引入⑵xP(x)⑴量詞轉(zhuǎn)換⑶P(c)⑵EI⑷x(P(x)∨Q(x))前提引入(5)P(c)∨Q(c)(4)UI(6)Q(c)(3)(5)析取三段論(7)xQ(x)(6)EG2/3/202351重慶大學(xué)98年：填空題（2分）若個(gè)體域是非負(fù)數(shù)集，A(x,y)表示x+y=y，則xyA(x,y)的真值是：

12/3/202352上海交大99年考研（6分）設(shè)A(x):x是人；B(x):x是錯(cuò)誤；C(x,y):x犯了y；D(x,y):y能改正x。用上述謂詞構(gòu)成下列語(yǔ)句的謂詞公式：(1)人都會(huì)犯錯(cuò)誤。(2)并非所有人犯錯(cuò)誤都能改。(3)有的錯(cuò)誤任何人犯了都不能改。x(A(x)→y(B(y)∧C(x,y))xy(A(x)∧B(y)∧C(x,y)∧D(y,x))y(B(y)∧x((A(x)∧C(x,y))→D(y,x))2/3/202353第三章集合論初步1.集合的表示,冪集,全集,空集.2.集合的三種關(guān)系(包含,相等,真包含)的定義及證明.3.集合的五種運(yùn)算交∩，并∪，相對(duì)補(bǔ)－，絕對(duì)補(bǔ)~，對(duì)稱差及相關(guān)性質(zhì).4.應(yīng)用包含排斥原理.2/3/202354第三章集合論初步基本概念:集合與元素,子集與真子集,空集,全集,冪集,并集,交集,相對(duì)補(bǔ)集(差集),絕對(duì)補(bǔ)集(補(bǔ)集)1.集合的表示,元素與集合的屬于關(guān)系∈.

集合的三種表示方法:

枚舉法:一一列出集合中的元素.

謂詞描述法:用謂詞描述集合中元素的性質(zhì).

文氏圖:用一個(gè)平面區(qū)域表示.2.集合的三種關(guān)系(被包含,相等,被真包含)的定義及證明.ABx(x∈Ax∈B)A=BABBAx(x∈Ax∈B)ABABA≠Bx(x∈Ax∈B)x(x∈BxA)

2/3/2023553空集,全集,冪集空集φ:無(wú)元素的集合.x∈Φ是矛盾式.(空集是唯一的)

全集E:包含所討論所有集合的集合.(全集不唯一)x∈E是重言式冪集:由A的所有子集構(gòu)成的集合.

P(A)={X|XA}|P(A)|=2|A|

4.掌握集合的五種運(yùn)算及相關(guān)性質(zhì).A∩B={x|x∈A∧x∈B}x∈A∩Bx∈A∧x∈BA∪B={x|x∈A∨x∈B}x∈A∪Bx∈A∨x∈BA-B={x|x∈A∧xB}x∈A-Bx∈A∧xB~A=E-A={x|x∈E∧xA}={x|xA}x∈~AxAA-B=A∩~BAB=(A-B)∪(B-A)={x|(x∈A∧xB)∨(x∈B∧xA)}AB=(A∪B)-(A∩B)2/3/202356例1.已知全集E={Φ,{Φ}},AE,計(jì)算:a)P({Φ})P({Φ})=()b)P(A)∩P(~A)=()c)P(E)-P(~{{Φ}})=()解:a)因?yàn)槿魏渭螦,都有AA=Φ所以

P({Φ})P({Φ})=Φb)因?yàn)棣礎(chǔ)Φ~A,即Φ∈P(A)Φ∈P(~A)所以

P(A)∩P(~A)={Φ}c)P(E)={Φ,{Φ},{{Φ}},{Φ,{Φ}}}~{{Φ}}={Φ}P(~{{Φ}})=P({Φ})={Φ,{Φ}}P(E)-P(~{{Φ}}))={Φ,{Φ},{{Φ}},{Φ,{Φ}}}-{Φ,{Φ}}={{{Φ}},{Φ,{Φ}}}2/3/202357例2

證明各式彼此等值。PQ(P∨Q)∧(P∨Q)c)A∪B=B,A∩B=A,AB,~B~A.證明.A∪B=B

x(x∈A∪Bx∈B)x((xA∪Bx∈B)(x∈A∪BxB))x(((xAxB)x∈B)((x∈Ax∈B)xB))x((xAxB)x∈B)x((xAx∈B)(xBx∈B))x((xAx∈B)x(x∈Ax∈B)ABx(x∈Ax∈B)x(xBxA)x(x∈~Bx∈~A)~B~A

由A∪B=B得A(A∪B)=AB又A(A∪B)=A，所以

A=AB類似由A∩B=A,可以推出A∪B=B

所以A∪B=BA∩B=A從而證得A∪B=B,A∩B=A,AB,~B~A彼此等值。12/3/202358例3

令全集E為信息學(xué)院的學(xué)生的集合,C表示計(jì)算機(jī)專業(yè)學(xué)生的集合,M表示學(xué)習(xí)了離散數(shù)學(xué)的學(xué)生的集合,D表示學(xué)習(xí)了數(shù)據(jù)結(jié)構(gòu)課學(xué)生的集合,F表示一年級(jí)的學(xué)生的集合.用集合的關(guān)系式表達(dá)下面句子.“學(xué)習(xí)了離散數(shù)學(xué)和數(shù)據(jù)結(jié)構(gòu)課的學(xué)生,一定是計(jì)算機(jī)專業(yè)的非一年級(jí)的學(xué)生”.

解.(M∩D)(C∩~F)2/3/202359上海交大99年考研（6分）某年級(jí)共有200名學(xué)生，喜歡打籃球的有134人，喜歡打排球的有101人，喜歡打乒乓球的有90人，籃球、乒乓球都不喜歡的23人，籃球、排球都喜歡的54人，喜歡排球但不喜歡乒乓球的有48人，三樣都喜歡的有12人。求：1。三樣運(yùn)動(dòng)都不喜歡的有多少人？2。只喜歡一項(xiàng)運(yùn)動(dòng)的人有多少？2/3/202360解：設(shè)某年級(jí)學(xué)生集合為全集E，喜歡打籃球的學(xué)生集合為A，喜歡打排球的學(xué)生集合為B，喜歡打乒乓球的學(xué)生集合為C。則有：|E|=200|A|=134|B|=101|C|=90|A∩B|=54|~A∩~C|23|B∩~C|=48|A∩B∩C|=12|A∩C|=-|A∪C|+|A|+|C|=|A|+|C|-(|E|-|~(A∪C)|)=134+90-(200-23)=47|B∩C|=|B|-|B∩~C|=101-48=53所以，1.|~(A∪B∪C)|=|E|-(|A|+|B|+|C|-|A∩B|-|B∩C|-|B∩C|+|A∩B∩C|)=200-(134+101+90-54-53-47+12)=172/3/2023612只喜歡一種運(yùn)動(dòng)的人數(shù)分別為：|A∩~B∩~C|，|~A∩B∩~C|，|~A∩~B∩C||A∩~B∩~C|=|(A-A∩B)∩~C|=|(A-A∩B)|-|(A-A∩B)∩C|=80-(|(A∩C|-|B∩C|)=80-(47-53)=88|~A∩B∩~C|=|(B-A∩B)∩~C|=|(B-A∩B)|-|(B-A∩B)∩C|=47-(|(B∩C|-|A∩C|)=47-(53-47)=39|~A∩~B∩C|=|(C-C∩B)∩~A|=|(C-C∩B)|-|(C-C∩B)∩A|=37-(|(C∩A|-|B∩A|)=80-(47-54)=87所以，2.只喜歡籃球的有88人，只喜歡排球的有39人，只喜歡乒乓球的有87人。2/3/202362

六、（5分）證明：P(A)∪P(B)P(A∪B)并說(shuō)明等號(hào)成立的條件。證明：因?yàn)镻(A)表示由A的所有子集構(gòu)成的集合.

P(A)={X|XA}

，P(B)={X|XB}

P(A)∪P(B)={X|XA}P(A∪B)={X|XA∪B}X∈P(A)∪P(B)

X∈P(A)∨X∈P(B)XA∨XB任取x∈X，則有x∈A∨x∈B，所以x∈A∪B，所以有XA∪B，即X∈P(A∪B)，因此P(A)∪P(B)P(A∪B)。但是，不一定有P(A∪B)P(A)∪P(B)（因?yàn)閄A∪B不一定有XA∨XB）2/3/202363如：A={1,2}B={2,3}A∪B={1,2,3}P(A)={Φ,{1},{2},{1,2}}P(B)={Φ,{2},{3},{3,2}}P(A∪B)={Φ,{1},{2},{3},{1,2},{2,3}{3,1},{1,2,3}}{1,2,3}∈P(A∪B),但是{1,2,3}不是P(A)∪P(B)中的元素。當(dāng)XA∪BXA∨XB時(shí)，等號(hào)成立。即A∪B=A，或

A∪B=B。2/3/202364有14位學(xué)生參加考試,9位同學(xué)數(shù)學(xué)得了優(yōu);5位同學(xué)物理得了優(yōu);4位同學(xué)化學(xué)得了優(yōu);其中物理和數(shù)學(xué)都得優(yōu)的同學(xué)有4人;數(shù)學(xué)和化學(xué)都得優(yōu)的同學(xué)有3人;物理和化學(xué)都得優(yōu)的同學(xué)有3人;三門都得優(yōu)的同學(xué)有2人;問(wèn)沒有得到優(yōu)的有多少人?恰有兩門得優(yōu)的同學(xué)有多少人?解.令A(yù)、B、C分別表示數(shù)學(xué)、物理、化學(xué)得優(yōu)同學(xué)集合.全集為E.于是有|E|=14|A|=9|B|=5|C|=4|A∩B|=4|A∩C|=3|B∩C|=3|A∩B∩C|=2|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|B∩C|+|A∩B∩C|=9+5+4-4-3-3+2=10于是得到優(yōu)的人數(shù)是10人.∴沒有得到優(yōu)的人數(shù)是:14-10=4人恰有兩門得優(yōu)的人數(shù):(|A∩B|-|A∩B∩C|)+(|A∩C|-|A∩B∩C|)+(|B∩C|-|A∩B∩C|)=4-2+3-2+3-2=42/3/202365中山大學(xué)2004五、設(shè)A、B、C、D為集合，證明下列各式。（20分）1.A-B=A-A∩B2.A((B∪C)∩D)=((AB)∪(AC))∩(AD)證明：1.因?yàn)锳-B=A∩~BA-A∩B=A∩~(A∩B)=A∩(~A∪~B)=(A∩~A)∪(A∩~B)=A∩~B所以A-B=A-A∩B。2.任取<x,y>A((B∪C)∩D)

xAy((B∪C)∩D

xA(yB∪C)yDxA(yB∨yC)yD(xAyB)∨(xAyC)(xAyD)<x,y>((AB)∪(AC))∩(AD)所以A((B∪C)∩D)=((AB)∪(AC))∩(AD)2/3/202366考研題分析：1、若A-B=B,問(wèn)A和B是什么集合？說(shuō)明理由。解答：A和B必為空集。這是因?yàn)椋篈-B=A∩~B~B,而已知A-B=B，故有B~B，B中一定不包含任何元素。否則若存在x∈B，x∈~B同時(shí)成立，這是不可能的。由B是空集可知A也是空集。2/3/202367求證：若(A-B)∪(B-A)=C,則A(B-C)∪(C-B)的充要條件是A∩B∩C=Φ.證明：(充分性)：即已知A∩B∩C=Φ，證明A(B-C)∪(C-B)。B∪C=B∪(A-B)∪(B-A)=B∪(A∩~B)∪(~

A∩B)=B∪A∪(~

A∩B)=B∪A。故AB∪C。而A∩B∩C=Φ，因此對(duì)于任意的x∈A，有x∈B∪C∧xB∩C，即x∈(B∪C)-(B∩C).又(B-C)∪(C-B)=(B∩~C)∪(~B∩C)=(B∪C)-(B∩C),所以x∈(B-C)∪(C-B)，即A(B-C)∪(C-B)2/3/202368(必要性)：即已知A(B-C)∪(C-B)，證明A∩B∩C=Φ。因?yàn)锳(B-C)∪(C-B)，所以A(B∪C)-(B∩C)，所以對(duì)于任意的x∈A，有x∈B∪C∧xB∩C，因此A∩B∩C=Φ。證畢。2/3/202369

第四章二元關(guān)系1.關(guān)系的概念,表示方法.2.二元關(guān)系的性質(zhì)的定義,熟練掌握性質(zhì)的判斷及證明.3.掌握關(guān)系的復(fù)合,求逆及閉包運(yùn)算(計(jì)算方法及有關(guān)性質(zhì))4.掌握等價(jià)關(guān)系的判斷,證明,求等價(jià)類和商集.5.掌握相容關(guān)系的概念

6.偏序關(guān)系的判斷,會(huì)畫Hasse圖,會(huì)求一個(gè)子集的極小(大)元,最小(大)元,上界與下界,最小上界及最大下界.

注意本章證明題的證明過(guò)程的思路2/3/202370一.關(guān)系的概念,表示方法,三個(gè)特殊關(guān)系.1.集合的笛卡爾積

A×B={<x,y>|x∈A∧y∈B}|A|=m,|B|=n|A×B|=mn

設(shè)A={0,1}，B={a,b}，求AB。

AB={<0,a>,<0,b>,<1,a>,<1,b>}2.二元關(guān)系的概念定義1:設(shè)A、Ｂ是集合,如果ＲA×B,則稱R是一個(gè)從A到

B的二元關(guān)系。如果RA×A,則稱R是A上的二元關(guān)系.

如果|A|=m|B|=n則可以確定2mn個(gè)從A到B的不同關(guān)系.定義2:任何序偶的集合，都稱之為一個(gè)二元關(guān)系。2/3/2023713.關(guān)系的表示方法1).枚舉法:

即將關(guān)系中所有序偶一一列舉出，寫在大括號(hào)內(nèi).

如:R={<1,2>,<3,4>,<4,2>}2).(描述法)謂詞公式法：即用謂詞公式描述序偶中元素的關(guān)系。例如

R={<x,y>|x<y}3).有向圖法：1。2。

3。

4。。。。ABabcR1:1。。4。。23R2:2/3/2023724).矩陣表示法：(實(shí)際上就是圖論中的鄰接矩陣)

設(shè)A={a1,a2,,am}，B={b1,b2,,bn}是個(gè)有限集，

RA×B，定義R的m×n階矩陣

MR=(rij)m×n，其中4.三個(gè)特殊關(guān)系1).空關(guān)系Φ：

ΦA(chǔ)×B，(或ΦA(chǔ)×A)，即無(wú)任何元素的關(guān)系.

它的關(guān)系圖中只有結(jié)點(diǎn),無(wú)任何邊；它的矩陣中全是0。2).完全關(guān)系(全域關(guān)系)

：

A×B(或A×A)本身是一個(gè)從A到B(或A上)的完全關(guān)系.

即含有全部序偶的關(guān)系。它的矩陣中全是1。

1若<ai,bj>∈R

0若<ai,bj>∈R(1≤i≤m,1≤j≤n)rij=2/3/2023733).恒等關(guān)系IA：

IAA×A,且IA={<x,x>|x∈A}稱之為A上的恒等關(guān)系。例如A={1,2,3},則IA={<1,1>,<2,2>,<3,3>}A上的Φ、完全關(guān)系A(chǔ)×A及IA的關(guān)系圖及矩陣如下：MIA=1000100013×31。2。。31。2。。31111111113×31。。2。30000000003×3MΦ=MA×A=ΦA(chǔ)×AIA2/3/202374二.關(guān)系的性質(zhì):

熟練掌握性質(zhì)的判斷及證明.1.自反性定義:設(shè)R是集合A中的關(guān)系，如果對(duì)于任意x∈A都有

<x,x>∈R(xRx)，則稱R是A中自反關(guān)系。即

R是A中自反的x(xAxRx)2.反自反性定義：設(shè)R是集合A中的關(guān)系，如果對(duì)于任意的x∈A都有

<x,x>R，則稱R為A中的反自反關(guān)系。即

R是A中反自反的x(xA<x,x>R)3.對(duì)稱性定義:R是集合A中關(guān)系,若對(duì)任何x,y∈A,如果有xRy,必有

yRx,則稱R為A中的對(duì)稱關(guān)系。

R是A上對(duì)稱的xy((xAyAxRy)yRx)2/3/2023754.反對(duì)稱性定義:設(shè)R為集合A中關(guān)系,若對(duì)任何x,y∈A,如果有xRy,和

yRx,就有x=y,則稱R為A中反對(duì)稱關(guān)系。R是A上反對(duì)稱的xy((xAyAxRyyRx)

x=y)xy((xAyAxy<x,y>∈R)<y,x>R)5.傳遞性定義:R是A中關(guān)系，對(duì)任何x,y,z∈A,如果有xRy,和yRz,就

有xRz,則稱R為A中傳遞關(guān)系。即R在A上傳遞xyz((xAyAzAxRyyRz)xRz)2/3/202376自反性反自反性對(duì)稱性傳遞性反對(duì)稱性每個(gè)結(jié)點(diǎn)都有環(huán)主對(duì)角線全是1每個(gè)結(jié)點(diǎn)都無(wú)環(huán)主對(duì)角線全是0不同結(jié)點(diǎn)間如果有邊,則有方向相反的兩條邊.是以對(duì)角線為對(duì)稱的矩陣不同結(jié)點(diǎn)間,最多有一條邊.以主對(duì)角線為對(duì)稱的位置不會(huì)同時(shí)為1如果有邊<a,b>,<b,c>,則也有邊<a,c>.或者使得前件為假.如果aij=1,且ajk=1,則aik=1從關(guān)系的矩陣從關(guān)系的有向圖

性質(zhì)判定:2/3/202377判斷下面關(guān)系的性質(zhì)：Y-有N-無(wú)1。2。。1。2。。1。2。。1。2。。3333R2R1R3R4自反性反自反性對(duì)稱性反對(duì)稱性傳遞性R1YNNYYR2NYNYNR3YNYNYR4YNYYY2/3/202378R5NYNYYR6