離散數(shù)學(xué)-第一學(xué)期習(xí)題課

1離散數(shù)學(xué)期中復(fù)習(xí)2第一章命題邏輯1.聯(lián)結(jié)詞定義了六個邏輯聯(lián)結(jié)詞，分別是：

(1)否定“”(2)合取“∧”

(3)析取“∨”(4)異或“”

(5)蘊(yùn)涵“”(6)等價“”要熟練掌握這六個聯(lián)結(jié)詞在自然語言中所表示的含義以及它們的真值表的定義。：否定表示“不”∧：合取表示“不但…,而且...”“并且”∨：析取表示“或者－可兼取的或”：異或表示“或者－不可兼取的或”：蘊(yùn)涵表示“如果…,則...”:等價表示“當(dāng)且僅當(dāng)”“充分且必要”可以將這六個聯(lián)結(jié)詞看成六種“運(yùn)算”。3聯(lián)結(jié)詞的定義(包括真值表和含義).特別要注意：“或者”的二義性,即要區(qū)分給定的“或”是“可兼取的或∨”還是“不可兼取的或”?！啊钡挠梅?，它既表示“充分條件”也表示“必要條件”,即要弄清哪個作為前件,哪個作為后件.

PQP∧QP∨QPQPQPQ

0000110

0101101

10010011111110

上次小測：(p∧q)∨(p∧r)∨(q∧r)自然推理系統(tǒng)中其公理集為：空集自然推理系統(tǒng)：與公理系統(tǒng)相對，是按照自然演繹思想構(gòu)造的形式系統(tǒng)。其出發(fā)點(diǎn)是一些變形規(guī)則或推演規(guī)則，但沒有公理。423452.命題符號化.

例如P:我有時間.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.用公式的等值變換,化簡成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ǔ),同一律)64.重言蘊(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))為重言式.

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

B00101110011175.等值公式的證明,記住常用的公式.

方法1.列真值表.

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

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

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

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

m3m2m1

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

011101011

011101011011111111

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

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

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

m0∨m1∨m3∨m5∨m7主合取范式(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)M2∧M4∧M6PQR(P∨Q)R0001001101000111100010111100111111方法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)12已知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)137.會用三種推理方法,進(jìn)行邏輯推理.

會用三個推理規(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∨Q14((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附加前提論證15((A∧B)C)∧D∧(C∨D)A∨B3.歸謬法:⑴(A∨B)假設(shè)結(jié)論錯誤⑵A∧B⑴德摩根⑶(A∧B)C前提引入⑷C

⑵

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

邏輯等值的主合取范式和主析取范式.20一.(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)主合取范式21(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)主析取范式22二.(8分)判斷下列各公式是:1.永真式2.永假式3.其它

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

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

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

23二.(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;這時前件也為0,所以(1)式不存在真值為0的情況,因此(1)為1永真式.24二.(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.其它25二.(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的情況,即是一個永假式.26例：三個人估計(jì)比賽結(jié)果，甲說“A第一，B第二”，乙說“C第二,D第四”,丙說：“A第二，D第四”。結(jié)果，3人估計(jì)的都不全對，但都對了一個，問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第四。27

第二章謂詞邏輯1.會命題符號化.

命題的符號表達(dá)式與個體域有關(guān)。當(dāng)個體域擴(kuò)大時，需要添加用來表示個體特性的謂詞，稱此謂詞為特性謂詞。特性謂詞往往就是給定命題中量詞后邊的那個名詞。如“所有自然數(shù)...”

、“有些大學(xué)生...”。如何添加特性謂詞，這是個十分重要的問題，這與前邊的量詞有關(guān)。

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

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

292.

一階邏輯公式的解釋給出下列公式的一個成真賦值和成假賦值：（1）x(F(x)G(x)H(x))取解釋I：個體域?yàn)槿说募?，F(xiàn)(x)：x是教師，G(x)：x是黨員，H(x):x是班主任。則在I解釋下，該命題為真命題。取解釋II：個體域?yàn)槿说募?，F(xiàn)(x):x是男生，G(x):x是女生，H(x):x是班長。則在II解釋下，該命題是假命題。（2）x(F(x)y(G(y)H(x,y)))取解釋I：個體域?yàn)檎麛?shù)集合，F(xiàn)(x):x是正整數(shù)，G(x):x是負(fù)整數(shù)，H(x,y):x比y大。則在I解釋下，該命題為真命題。取解釋II：個體域?yàn)樽匀粩?shù)集合，F(xiàn)(x):x是奇數(shù)，G(x):x是偶數(shù)，H(x,y):x比y大。則在II解釋下，該命題為假命題。303.

變元的約束例：指出下列各公式中指導(dǎo)變元、量詞轄域、自由變元和約束變元。1）x(F(x)

yH（x,y）)；2）xF(x)G（x,y）；3）xy（R(x,y)L(y,z)）

xH(x,y)。解：（1）yH（x,y）中，y為約束變元，轄域?yàn)镠(x,y)，其中y為約束出現(xiàn)，x是自由出現(xiàn)。在整個公式中，x為指導(dǎo)變元，x的轄域?yàn)椋‵(x)

yH（x,y）），x,y都是約束出現(xiàn)。（2）在xF(x)中，x轄域?yàn)镕(x)，x為約束出現(xiàn)G（x,y）中，x,y都是自由出現(xiàn)。在整個公式中，x約束出現(xiàn)一次，自由出現(xiàn)一次，y自由出現(xiàn)。（3）可以類似分析，x為約束出現(xiàn)，y既約束出現(xiàn)，又自由出現(xiàn)。z是自由出現(xiàn)。

31換名規(guī)則（針對約束變元）例：對xP(（x）R（x,y））Q（x,y）換名?？蓳Q為：z（P(z)R(z,y)）Q(x,y)。注：（1）對于約束變元可以換名，其更改的變元名稱范圍是量詞中的指導(dǎo)變元，以及該量詞作用域中所出現(xiàn)的該變元，在公式的其余部分不變。（2）換名時一定要為作用域中沒有出現(xiàn)過的變元名稱。*最好是公式中沒有的變元名。

32代入規(guī)則（針對自由變元）代入規(guī)則：對于某自由出現(xiàn)的個體變元用與原公式中所有個體變元符號不同的變元符號去代替，且處處代替。例：對以下公式中的自由變元進(jìn)行代入。(x)(P(y)∧R(x,y))→(y)Q(y)解：用z代換y，代入后為：(x)(P(z)∧R(x,z))→(y)Q(y)注：不能換成:(x)(P(x)∧R(x,x))→(y)Q(y)(與約束變元x同名)

或(x)(P(z)∧R(x,y))→(y)Q(y)(部分替換)334.掌握常用的等值公式和重言蘊(yùn)涵式.包括:

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

設(shè)個體域?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))346).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))5.會用等值公式求謂詞公式的真值.例設(shè)個體域?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)1356.將下面謂詞公式寫成前束范式直觀來看，就是將量詞放在最前面，去作用整個公式例：(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))(轄域擴(kuò)充)367.熟練掌握謂詞邏輯推理.1).注意使用EI、UI、EG、UG的限制條件,特別是EI,UG2).對于同一個個體變元，既有帶也有帶的前提，去量詞時，應(yīng)先去后去，這樣才可以特指同一個個體c.3).去量詞時，該量詞必須是公式的最左邊的量詞，且此量詞的前邊無任何符號，它的轄域作用到公式末尾。下面的作法是錯誤的：正確作法:⑴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)涵等值式37下面的作法是錯誤的：正確作法:⑴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的生母，顯然⑵是個假命題4).添加量詞時，也要加在公式的最左邊，(即新加的量詞前也無任何符號?。?且其轄域作用到公式的末尾。 例如下面作法是錯誤的:⑴xP(x)→Q(c)前提引入

⑵

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

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

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

⑵化簡規(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))⒀EG39

例：

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

例.將下列推理符號化并給出形式證明:

鳥會飛,猴子不會飛;所以,猴子不是鳥.解：設(shè)P(x):x會飛；Q(x):x是鳥；R(x):x是猴子前提：x(Q(x