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

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

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

(1)否定“”

(2)合取“∧”

(3)析取“∨”

(4)異或“

”

(5)蘊涵“”

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

:等價表示“當且僅當”“充分且必要”可以將這六個聯結詞看成六種“運算”。2/3/202310聯結詞的定義(包括真值表和含義).特別要注意：“或者”的二義性,即要區分給定的“或”是“可兼取的或∨”還是“不可兼取的或”。“”的用法，它既表示“充分條件”也表示“必要條件”,即要弄清哪個作為前件,哪個作為后件.

PQP∧QP∨QPQPQPQ

0000110

0101101

10010011111110

2/3/2023112.會命題符號化.

例如P:我有時間.Q:我上街.R:我在家.

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

表示P是Q的必要條件:僅當P,才Q.只有P,才Q.QP

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

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

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

記住常用的公式.

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

方法1.列真值表.

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

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

對于給定一個題,究竟是用哪種方法,原則上哪種都可以.但是哪個方法簡單,要根據具體題而定.ABA

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

方法1.列真值表.

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

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

(PQ)∨R(P∧Q)R注意:不論是證明重言蘊涵式,還是證明等值公式以及后邊的求公式的范式,命題邏輯推理,都應用9，23頁的公式。必須記憶一些常用的公式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)極小項及其性質.

m3m2m1

m0PQP∧QP∧QP∧QP∧Q000000010101001010100100111110002/3/2023156)極大項及其性質.M0M1M2M3PQP∨QP∨QP∨QP∨Q0000

011101011

011101011011111111

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

8)主合取范式:A1∧A2∧...∧An(n≥1)Ai(i=1,2..n)極大項.2/3/2023169).會求主析取范式和主合取范式.求下面命題公式的范式: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)的主析取范式中含有如下極小項:

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

…2/3/2023197.會用三種推理方法,進行邏輯推理.

會用三個推理規則:前提引入，結論引入，附加前提引入例如:證明((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.附加前提論證:適用于結論是蘊涵式.A∨BAB⑴A附加前提引入⑵(A∧B)C前提引入(3)(A∨B)∨C蘊涵等值式⑷A∨(

B∨C)結合律⑸A(BC)⑷蘊涵等值式⑹BC⑴⑸

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

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

⑵

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

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

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

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

符號化為(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

符號化為(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))

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

(2)(notporq)<->(pand(pandq))解:先符號化為(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)

符號化為:(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的情況,即是一個永假式.2/3/202333二.(8分)判斷下列各公式是:1.永真式2.永假式3.其它

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

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

解：設p：電燈亮，q:燈泡發生故障，r：開關發生故障

2.僅當你去，我才留下。2/3/202335例：三個人估計比賽結果，甲說“A第一，B第二”，乙說“C第二,D第四”,丙說：“A第二，D第四”。結果，3人估計的都不全對，但都對了一個，問A,B,C,D的名次。[解答]設P：A是第一；Q：B是第二；R：C是第二；S：D是第四。E：A是第二。則根據題意有：(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.準確掌握有關概念.2.會命題符號化.3.掌握常用的等值公式和重言蘊涵式.包括:

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

命題的符號表達式與個體域有關。當個體域擴大時，需要添加用來表示個體特性的謂詞，稱此謂詞為特性謂詞。特性謂詞往往就是給定命題中量詞后邊的那個名詞。如“所有自然數...”、“有些大學生...”。如何添加特性謂詞，這是個十分重要的問題，這與前邊的量詞有關。

如果前邊是全稱量詞，特性謂詞后邊是蘊含聯結詞“→”；

如果前邊是存在量詞，特性謂詞后邊是合取聯結詞“∧”。另外有些命題里有的個體詞在句中沒有明確的量詞,而在寫它的符號表達式時,必須把隱含的量詞明確的寫出來.2/3/202338例如1、金子閃光,但閃光的不一定都是金子.設: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、每個大學生都愛好一些體育活動。S(x):x是大學生,L(x,y):x愛好y,P(x):x是體育活動.x(S(x)y((P(y))L(x,y)))

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

帶量詞的公式在個體域內展開式,量詞否定,量詞轄域擴充,量詞分配公式.

設個體域為{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.會用等值公式求謂詞公式的真值.例設個體域為{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)(變元換名)xyt((F(x,z)G(y)H(t,z))(轄域擴充)2/3/2023426.熟練掌握謂詞邏輯推理.1).注意使用EI、UI、EG、UG的限制條件,特別是EI,UG2).對于同一個個體變元，既有帶也有帶的前提，去量詞時，應先去后去，這樣才可以特指同一個個體c.3).去量詞時，該量詞必須是公式的最左邊的量詞，且此量詞的前邊無任何符號，它的轄域作用到公式末尾。下面的作法是錯誤的：正確作法:⑴xP(x)→xQ(x)前提引入

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

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

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

⑵

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

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

⑴EI⑶A(a)⑵化簡規則⑷D(a)

⑵化簡規則⑸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(x):x是人，D(x):x怕困難，S(x)：x獲得成功，F(x):x失敗過。則本題符號化為前提：結論：2/3/202346中科院99.(9分)問anyxexistyP(x,y)->existyanyxP(x,y)是否謂詞演算的有效式?證明你的結論.解答：用謂詞公式表示：判斷xyP(x,y)→yxP(x,y)是否為重言蘊涵式。不是，取一特定的解釋I如下：設P(x,y)：x<=y,個體域為自然數集合。則有：xyP(x,y)為真，而yxP(x,y)為假，故給定公式在解釋I下為假，故不是謂詞公式的有效式。2/3/202347

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

鳥會飛,猴子不會飛;所以,猴子不是鳥.解：設P(x):x會飛；Q(x):x是鳥；R(x):x是猴子前提：x(Q(x)→P(x)),x(R(x)→P(x))結論：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中的每個數都小于或等于E2中的每個數"按以下要求的形式

表達出來:

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

(2)出現存在量詞,不出現全稱量詞.解：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))推出結論x(r(x)→p(x))證明：⑴x(r(x)∧q(x))前提引入⑵r(c)∧q(c)⑴EI⑶q(c)⑵化簡規則⑷r(c)⑵化簡規則⑸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）量詞轉換，蘊涵等值式2/3/202350重慶大學98年：用推理規則證明：x(P(x)∨Q(x))xP(x)→xQ(x)證明：⑴xP(x)附加前提引入⑵xP(x)⑴量詞轉換⑶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重慶大學98年：填空題（2分）若個體域是非負數集，A(x,y)表示x+y=y，則xyA(x,y)的真值是：

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

集合的三種表示方法:

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

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

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

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

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

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

4.掌握集合的五種運算及相關性質.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,計算:a)P({Φ})P({Φ})=()b)P(A)∩P(~A)=()c)P(E)-P(~{{Φ}})=()解:a)因為任何集合A,都有AA=Φ所以

P({Φ})P({Φ})=Φb)因為ΦAΦ~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為信息學院的學生的集合,C表示計算機專業學生的集合,M表示學習了離散數學的學生的集合,D表示學習了數據結構課學生的集合,F表示一年級的學生的集合.用集合的關系式表達下面句子.“學習了離散數學和數據結構課的學生,一定是計算機專業的非一年級的學生”.

解.(M∩D)(C∩~F)2/3/202359上海交大99年考研（6分）某年級共有200名學生，喜歡打籃球的有134人，喜歡打排球的有101人，喜歡打乒乓球的有90人，籃球、乒乓球都不喜歡的23人，籃球、排球都喜歡的54人，喜歡排球但不喜歡乒乓球的有48人，三樣都喜歡的有12人。求：1。三樣運動都不喜歡的有多少人？2。只喜歡一項運動的人有多少？2/3/202360解：設某年級學生集合為全集E，喜歡打籃球的學生集合為A，喜歡打排球的學生集合為B，喜歡打乒乓球的學生集合為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只喜歡一種運動的人數分別為：|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)并說明等號成立的條件。證明：因為P(A)表示由A的所有子集構成的集合.

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)（因為XA∪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)中的元素。當XA∪BXA∨XB時，等號成立。即A∪B=A，或

A∪B=B。2/3/202364有14位學生參加考試,9位同學數學得了優;5位同學物理得了優;4位同學化學得了優;其中物理和數學都得優的同學有4人;數學和化學都得優的同學有3人;物理和化學都得優的同學有3人;三門都得優的同學有2人;問沒有得到優的有多少人?恰有兩門得優的同學有多少人?解.令A、B、C分別表示數學、物理、化學得優同學集合.全集為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于是得到優的人數是10人.∴沒有得到優的人數是:14-10=4人恰有兩門得優的人數:(|A∩B|-|A∩B∩C|)+(|A∩C|-|A∩B∩C|)+(|B∩C|-|A∩B∩C|)=4-2+3-2+3-2=42/3/202365中山大學2004五、設A、B、C、D為集合，證明下列各式。（20分）1.A-B=A-A∩B2.A((B∪C)∩D)=((AB)∪(AC))∩(AD)證明：1.因為A-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,問A和B是什么集合？說明理由。解答：A和B必為空集。這是因為：A-B=A∩~B~B,而已知A-B=B，故有B~B，B中一定不包含任何元素。否則若存在x∈B，x∈~B同時成立，這是不可能的。由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=Φ，因此對于任意的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=Φ。因為A(B-C)∪(C-B)，所以A(B∪C)-(B∩C)，所以對于任意的x∈A，有x∈B∪C∧xB∩C，因此A∩B∩C=Φ。證畢。2/3/202369

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

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

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

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

設A={0,1}，B={a,b}，求AB。

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

B的二元關系。如果RA×A,則稱R是A上的二元關系.

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

即將關系中所有序偶一一列舉出，寫在大括號內.

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

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

3。

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

設A={a1,a2,,am}，B={b1,b2,,bn}是個有限集，

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

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

ΦA×B，(或ΦA×A)，即無任何元素的關系.

它的關系圖中只有結點,無任何邊；它的矩陣中全是0。2).完全關系(全域關系)

：

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

即含有全部序偶的關系。它的矩陣中全是1。

1若<ai,bj>∈R

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

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

熟練掌握性質的判斷及證明.1.自反性定義:設R是集合A中的關系，如果對于任意x∈A都有

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

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

<x,x>R，則稱R為A中的反自反關系。即

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

yRx,則稱R為A中的對稱關系。

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

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

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

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

性質判定:2/3/202377判斷下面關系的性質：Y-有N-無1。2。。1。2。。1。2。。1。2。。3333R2R1R3R4自反性反自反性對稱性反對稱性傳遞性R1YNNYYR2NYNYNR3YNYNYR4YNYYY2/3/202378R5NYNYYR6