離散數(shù)學(xué)命題邏輯等值演算

1、1離離 散散 數(shù)數(shù) 學(xué)學(xué) 周周 塔塔計(jì)算機(jī)教研室計(jì)算機(jī)教研室 20122012年年9 9月月江蘇科技大學(xué)本科生必修課程江蘇科技大學(xué)本科生必修課程第2章 命題邏輯等值演算2本章說(shuō)明q本章的主要內(nèi)容本章的主要內(nèi)容 等值式與基本的等值式等值式與基本的等值式 等值演算與置換規(guī)則等值演算與置換規(guī)則 析取范式與合取范式、主析取范式與主合取范式析取范式與合取范式、主析取范式與主合取范式 聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集(不講不講)q本章與后續(xù)各章的關(guān)系本章與后續(xù)各章的關(guān)系 是第一章的抽象與延伸是第一章的抽象與延伸 是后續(xù)各章的現(xiàn)行準(zhǔn)備是后續(xù)各章的現(xiàn)行準(zhǔn)備32.1 等值式o兩公式什么時(shí)候代表了同一個(gè)命題呢？o抽象地看

2、，它們的真假取值完全相同時(shí)即代表了相同的命題。o設(shè)公式A,B共同含有n個(gè)命題變項(xiàng)，可能對(duì)A或B有啞元，若A與B有相同的真值表，則說(shuō)明在2n個(gè)賦值的每個(gè)賦值下，A與B的真值都相同。于是等價(jià)式AB應(yīng)為重言式。 4等值的定義及說(shuō)明定義定義2.12.1 設(shè)設(shè)A,BA,B是兩個(gè)命題公式，若是兩個(gè)命題公式，若A,BA,B構(gòu)成的等構(gòu)成的等價(jià)式價(jià)式AB為重言式，則稱則稱A A與與B B是是等值的，記作的，記作A AB B。 定義中定義中, ,A,B,A,B,都是都是元語(yǔ)言符號(hào)元語(yǔ)言符號(hào)。A A或或B B中可能有啞元出現(xiàn)。中可能有啞元出現(xiàn)。pq pq ( (pq)(pq)(rr)rr)r r為左邊公式中的啞元。

3、為左邊公式中的啞元。用真值表可以驗(yàn)證兩個(gè)公式是否等值。用真值表可以驗(yàn)證兩個(gè)公式是否等值。5例題例2.1 判斷下面兩個(gè)公式是否等值(pq) 與 pq 解答在用真值表法判斷在用真值表法判斷A AB B是否為重言式時(shí)，真值是否為重言式時(shí)，真值表的最后一列可以省略表的最后一列可以省略。等值等值6例題例題2.2 判斷下列各組公式是否等值(1)p(qr)與(pq)r (2)(pq)r與(pq)r 解答等值等值不等值不等值7基本等值式1.雙重否定律A A2.冪等律A AA, A AA 3.交換律AB BA，AB BA4.結(jié)合律(AB)C A(BC) (AB)C A(BC) 5.分配律 A(BC) (AB)(

4、AC) （對(duì)的分配律）A(BC) (AB)(AC)（對(duì)的分配律）6.德摩根律 (AB) AB(AB) AB 7.吸收律 A(AB) A，A(AB) A 8基本等值式 8.零律 A1 1,A0 0 9.同一律 A0 A，A1 A 10.排中律 AA 1 11.矛盾律 AA 0 12.蘊(yùn)涵等值式 AB AB13.等價(jià)等值式 AB (AB)(BA)14.假言易位 AB BA15.等價(jià)否定等值式 AB AB16.歸謬論 (AB)(AB) A 9對(duì)偶原理一個(gè)邏輯等值式，如果只含有、0、1那么同時(shí)把和互換把0和1互換得到的還是等值式。10等值演算與置換規(guī)則o各等值式都是用元語(yǔ)言符號(hào)書(shū)寫(xiě)的，其中A,B,C可

5、以代表任意的公式，稱這樣的等值式為等值式模式等值式模式。o每個(gè)等值式模式都給出無(wú)窮多個(gè)同類型的具體的等值式。例如，在蘊(yùn)涵等值式 ABAB 中，取A=p，B=q時(shí)，得等值式 pqpq 取A=pqr，B=pq時(shí)，得等值式(pqr)(pq) (pqr)(pq)o這些具體等值式都被稱為原來(lái)的等值式模式的代入實(shí)例代入實(shí)例。o由已知等值式推演出另外一些等值式的過(guò)程為等值演算等值演算。o置換規(guī)則置換規(guī)則 設(shè)(A)是含公式A的命題公式，(B)是用公式B置換了(A)中所有的A后得到的命題公式，若BA，則(B)(A)。11關(guān)于等值演算的說(shuō)明o等值演算的基礎(chǔ)n等值關(guān)系的性質(zhì)：自反性：AA。對(duì)稱性：若AB，則BA。傳

6、遞性：若AB且BC，則AC。n基本的等值式n置換規(guī)則o等值演算的應(yīng)用n證明兩個(gè)公式等值n判斷公式類型n解判定問(wèn)題12等值演算的應(yīng)用舉例證明兩個(gè)公式等值(pq)r (pr)(qr)( (pqpq)r )r (pq)(pq)rr（蘊(yùn)含等值式、置換規(guī)則）蘊(yùn)含等值式、置換規(guī)則） (pq)pq)rr（蘊(yùn)含等值式、置換規(guī)則）蘊(yùn)含等值式、置換規(guī)則） ( (pq)pq)rr（德摩根律、置換規(guī)則）德摩根律、置換規(guī)則） ( (pr)(qr)pr)(qr) （分配律、置換規(guī)則）分配律、置換規(guī)則）也可以從右邊開(kāi)始演算也可以從右邊開(kāi)始演算因?yàn)槊恳徊蕉加弥脫Q規(guī)則，故可不寫(xiě)出因?yàn)槊恳徊蕉加弥脫Q規(guī)則，故可不寫(xiě)出熟練后，基本等

7、值式也可以不寫(xiě)出熟練后，基本等值式也可以不寫(xiě)出通常不用等值演算直接證明兩個(gè)公式不等值通常不用等值演算直接證明兩個(gè)公式不等值解答13例題例2.3 用等值演算法驗(yàn)證等值式(pq)r (pr)(qr) (pr)(qr)(pr)(qr) (pr)(qr)(pr)(qr)( (蘊(yùn)含等值式蘊(yùn)含等值式) ) (pq)r(pq)r( (分配律分配律) ) (pq)r(pq)r( (德摩根律德摩根律) ) (pq)r(pq)r( (蘊(yùn)含等值式蘊(yùn)含等值式) ) 解答14例題例2.4 證明：(pq)r 與 p(qr) 不等值方法一、真值表法真值表法。 方法二、觀察法觀察法。易知，010是(pq)r的成假賦值，而01

8、0是p(qr)的成真賦值，所以原不等值式成立。 方法三、通過(guò)等值演算化容易觀察真值的情況，再進(jìn)行判斷。A=(pq)r (pq)r （蘊(yùn)涵等值式） (pq)r （蘊(yùn)涵等值式） (pq)r （德摩根律） B=p(qr) p(qr) （蘊(yùn)涵等值式） pqr （結(jié)合律） 000，010是A的成假賦值，而它們是B的成真賦值。 解答15例題 例題例題2.5 用等值演算判斷下列公式的類型：（1）(pq)pq （2）(p(pq)r （3）p(pq)p)q) 16例2.5 解答(1) (pq)pq (1) (pq)pq (pq)pq (pq)pq （蘊(yùn)涵等值式）蘊(yùn)涵等值式） (pq)p)pq)p)q q （蘊(yùn)涵

9、等值式）蘊(yùn)涵等值式） ( (pq)pq)p)q p)q （德摩根律）德摩根律） (pq)pq)pp)q)q（德摩根律）德摩根律） (pppp)(qp)q )(qp)q （分配律）分配律） ( (11( (q qp)p)q q （排中律）排中律） ( (qqqq)p )p （同一律）同一律） 1 1p p（排中律）排中律） 1 1 （零律）（零律）17例2.5 解答(2) (p(2) (p(pq)r (pq)r (ppq)r(ppq)r ( (ppppq)rq)r 00r r 0 0(3) (3) p(pq)p)p(pq)p)q) q) p(pq) p(pq)pp)q) )q) p( p(ppp

10、p)(qp)q) )(qp)q) p(p( (00(qp)q) (qp)q) p( p(qqppq q) ) p1 p1 p p18例2.6 應(yīng)用題在某次研討會(huì)的中間休息時(shí)間，3名與會(huì)者根據(jù)王教授的口音對(duì)他是哪個(gè)省市的人進(jìn)行了判斷：甲說(shuō)王教授不是蘇州人，是上海人。乙說(shuō)王教授不是上海人，是蘇州人。丙說(shuō)王教授既不是上海人，也不是杭州人。聽(tīng)完以上3人的判斷后，王教授笑著說(shuō)，他們3人中有一人說(shuō)的全對(duì)，有一人說(shuō)對(duì)了一半，另一人說(shuō)的全不對(duì)。試用邏輯演算法分析王教授到底是哪里人？ 19例2.6 解答設(shè)命題 p：王教授是蘇州人。 q：王教授是上海人。 r：王教授是杭州人。p,q,r中必有一個(gè)真命題，兩個(gè)假命題

11、，要通過(guò)邏輯演算將真命題找出來(lái)。設(shè)甲的判斷為A1=pq乙的判斷為A2=pq 丙的判斷為A3=qr 20例2.6 解答甲的判斷全對(duì) B1=A1=pq甲的判斷對(duì)一半 B2=(pq)(pq)甲的判斷全錯(cuò) B3=pq乙的判斷全對(duì) C1=A2=pq乙的判斷對(duì)一半 C2=(pq)(pq)乙的判斷全錯(cuò) C3=pq丙的判斷全對(duì) D1=A3=qr丙的判斷對(duì)一半 D2=(qr)(qr)丙的判斷全錯(cuò) D3=qr21例2.6 解答由王教授所說(shuō)E = (B1C2D3)(B1C3D2)(B2C1D3) (B2C3D1)(B2C1D2)(B3C2D1)為真命題。 經(jīng)過(guò)等值演算后,可得E (pqr)(pqr) 由題設(shè)，王教授

12、不能既是上海人，又是杭州人，因而p,r中必有一個(gè)假命題，即pqr0，于是E pqr為真命題，因而必有p,r為假命題，q為真命題，即王教授是上海人。甲說(shuō)的全對(duì)，丙說(shuō)對(duì)了一半，而乙全說(shuō)錯(cuò)了。22例2.6的進(jìn)一步思考王教授只可能是其中一個(gè)城市的人或者三個(gè)城市都不是。所以，丙至少說(shuō)對(duì)了一半。因此，可得甲或乙必有一人全錯(cuò)了。又因?yàn)椋艏兹e(cuò)了，則有pq，因此乙全對(duì)。同理，乙全錯(cuò)則甲全對(duì)。所以丙必是一對(duì)一錯(cuò)。根據(jù)上述推理，可對(duì)公式E進(jìn)行簡(jiǎn)化，方便等值演算。(如何簡(jiǎn)化，請(qǐng)同學(xué)們課后思考)232.2 析取范式和合取范式 定義2.2 命題變項(xiàng)及其否定統(tǒng)稱作文字文字（letters）。僅由有限個(gè)文字構(gòu)成的析取式稱

13、作簡(jiǎn)單析取式簡(jiǎn)單析取式。僅由有限個(gè)文字構(gòu)成的合取式稱作簡(jiǎn)單合取式簡(jiǎn)單合取式。o簡(jiǎn)單析取式舉例：p,qpp，pq pqr,pqro簡(jiǎn)單合取式舉例：p,qpp，pqpqr,ppq一個(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式。一個(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式。242.2 析取范式和合取范式o為討論方便，有時(shí)用A1,A2,As表示s個(gè)簡(jiǎn)單析取式或s個(gè)簡(jiǎn)單合取式。o設(shè)Ai是含n個(gè)文字的簡(jiǎn)單析取式，若Ai中既含某個(gè)命題變項(xiàng)pj，又含它的否定式pj， 即pjpj，則Ai為重言式。o類似的討論可知，若Ai是含n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式，且Ai為矛盾式，則Ai中必同時(shí)含某個(gè)命題變項(xiàng)及它的否定式，反之亦然。 252

14、.2 析取范式和合取范式定理定理2.1(1)一個(gè)簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變項(xiàng)及它的否定式。(2)一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變項(xiàng)及它的否定式。 定義定義2.3 (1)由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式稱為析取范式析取范式（disjunctive normal form）。(2)由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式稱為合取范式合取范式（conjunctive normal form）。(3)析取范式與合取范式統(tǒng)稱為范式范式。 262.2 析取范式和合取范式o設(shè)Ai(i=1,2,s)為簡(jiǎn)單合取式，則A=A1A2As為析取范式。例如，A1=pq，A2=qr，A3=p，則

15、由A1,A2,A3構(gòu)造的析取范式為A=A1A2A3=(pq)(qr)p o設(shè)Ai(i=1,2,s)為簡(jiǎn)單析取式，則A=A1A2As為合取范式。例如，取A1=pqr，A2=pq，A3=r，則由A1,A2,A3組成的合取范式為A=A1A2A3=(pqr)(pq)r形如形如pqrpqr的公式既是一個(gè)簡(jiǎn)單合取式構(gòu)成的析取的公式既是一個(gè)簡(jiǎn)單合取式構(gòu)成的析取范式，又是由三個(gè)簡(jiǎn)單析取式構(gòu)成的合取范式。范式，又是由三個(gè)簡(jiǎn)單析取式構(gòu)成的合取范式。形如形如pqrpqr的公式既是含三個(gè)簡(jiǎn)單合取式的析取范的公式既是含三個(gè)簡(jiǎn)單合取式的析取范式，又是含一個(gè)簡(jiǎn)單析取式的合取范式。式，又是含一個(gè)簡(jiǎn)單析取式的合取范式。27析取

16、范式和合取范式的性質(zhì)定理定理2.2(1)一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單合取式都是矛盾式。(2)一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析取式都是重言式。 研究范式的目的在于，將給定公式化成與之等值的析取研究范式的目的在于，將給定公式化成與之等值的析取范式或合取范式，進(jìn)而將公式化成與之等值的主析取范式或合取范式，進(jìn)而將公式化成與之等值的主析取范式或主合取范式。范式或主合取范式。28范式存在的討論o在范式中不會(huì)出現(xiàn)聯(lián)結(jié)詞與，否則可使用等值式消除AB ABAB (AB)(AB)o在范式中不會(huì)出現(xiàn)如A,(AB),(AB)的公式：A A(AB) AB (AB)ABo在析取范式中不會(huì)出現(xiàn)形如A(

17、BC)的公式：A(BC) (AB)(AC)o在合取范式中不出現(xiàn)形A(BC)的公式：A(BC) (AB)(AC) o定理2.3 任一命題公式都存在著與之等值的析取范式與合取范式任一命題公式都存在著與之等值的析取范式與合取范式。 29求給定公式范式的步驟 (1)消去聯(lián)結(jié)詞、(若存在)。AB ABAB (AB)(AB)(2)否定號(hào)的消去(利用雙重否定律)或內(nèi)移(利用德摩根律)。A A(AB) AB(AB)AB(3)利用分配律：利用對(duì)的分配律求析取范式， 對(duì)的分配律求合取范式。A(BC) (AB)(AC)A(BC) (AB)(AC)30例題例題例題2.7 求下面公式的析取范式與合取范式：(pq) r

18、( (1) 1) 求合取范式求合取范式 ( (p pq)q) r r (pq) (pq) r r （消去消去） ( (pq)pq)r)(rr)(r(pq) (pq) （消去消去） ( (pq)r)(rpq)pq)r)(rpq) （消去消去） (pq)pq)rr)(pqr)(pqr) （否定號(hào)內(nèi)移）否定號(hào)內(nèi)移） ( (pr)(qr)(pqr)pr)(qr)(pqr)（對(duì)對(duì)分配律）分配律）解答31例題(2) (2) 求析取范式求析取范式 ( (pq)pq) r r (pq)pq)r)r)(p(pq qr)r) ( (pqp)(pqq)(pqr)pqp)(pqq)(pqr) (rp)(rq)(rr)

19、 (rp)(rq)(rr) ( (pqr)(pr)(qr) pqr)(pr)(qr) 由此例可知，命題公式的析取范式不唯一。由此例可知，命題公式的析取范式不唯一。同樣，合取范式也是不唯一的。同樣，合取范式也是不唯一的。32范式的規(guī)范化形式o定義定義2.4 在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式（簡(jiǎn)單析取式）中，若每個(gè)命題變項(xiàng)和它的否定式不同時(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個(gè)命題變項(xiàng)或它的否定式出現(xiàn)在從左算起的第i位上（若命題變項(xiàng)無(wú)角標(biāo)，就按字典順序排列），稱這樣的簡(jiǎn)單合取式（簡(jiǎn)單析取式）為極小項(xiàng)極小項(xiàng)（極大項(xiàng)極大項(xiàng)）。on個(gè)命題變項(xiàng)共可產(chǎn)生2n個(gè)不同的極小項(xiàng)。其中每個(gè)極小項(xiàng)都有且僅有一個(gè)成

20、真賦值。若成真賦值所對(duì)應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)i，就將所對(duì)應(yīng)極小項(xiàng)記作mi 。o類似地，n個(gè)命題變項(xiàng)共可產(chǎn)生2n個(gè)極大項(xiàng)，每個(gè)極大項(xiàng)只有一個(gè)成假賦值，將其對(duì)應(yīng)的十進(jìn)制數(shù)i做極大項(xiàng)的角標(biāo)，記作Mi。33表2.3 p,q形成的極小項(xiàng)與極大項(xiàng) 34表2.4 p,q,r形成的極小項(xiàng)與極大項(xiàng) 35范式的規(guī)范化形式定理定理2.4 設(shè)mi與Mi是命題變項(xiàng)p1,p2,pn形成的極小項(xiàng)和極大項(xiàng)，則 mi Mi， Mi mi 定義定義2.52.5 設(shè)由設(shè)由n n個(gè)命題變項(xiàng)構(gòu)成的析取范式（合取范個(gè)命題變項(xiàng)構(gòu)成的析取范式（合取范式）中所有的簡(jiǎn)單合取式（簡(jiǎn)單析取式）都是極式）中所有的簡(jiǎn)單合取式（簡(jiǎn)單析取式）都是極小項(xiàng)

21、（極大項(xiàng)），則稱該析取范式（合取范式）小項(xiàng)（極大項(xiàng)），則稱該析取范式（合取范式）為為主析取范式主析取范式（主合取范式主合取范式）。）。 定理定理2.52.5 任何命題公式都存在著與之等值的主析取任何命題公式都存在著與之等值的主析取范式和主合取范式，并且是唯一的。范式和主合取范式，并且是唯一的。 36求公式A的主析取范式的方法與步驟方法一、等值演算法方法一、等值演算法(1)化歸為析取范式。 (2)除去析取范式中所有永假的析取項(xiàng)。(3)將析取式中重復(fù)出現(xiàn)的合取項(xiàng)和相同的變?cè)喜ⅰ?4)對(duì)合取項(xiàng)補(bǔ)入沒(méi)有出現(xiàn)的命題變?cè)?，即添加?pp)式，然后應(yīng)用分配律展開(kāi)公式。方法二、真值表法方法二、真值表法(1)

22、寫(xiě)出A的真值表。(2)找出A的成真賦值。(3)求出每個(gè)成真賦值對(duì)應(yīng)的極小項(xiàng)（用名稱表示），按角標(biāo)從小到大順序析取。37求公式A的主合取范式的方法與步驟方法一、等值演算法方法一、等值演算法(1)化歸為合取范式。 (2)除去合取范式中所有永真的合取項(xiàng)。(3)將合取式中重復(fù)出現(xiàn)的析取項(xiàng)和相同的變?cè)喜ⅰ?4)對(duì)析取項(xiàng)補(bǔ)入沒(méi)有出現(xiàn)的命題變?cè)刺砑尤?pp)式，然后應(yīng)用分配律展開(kāi)公式。方法二、真值表法方法二、真值表法(1)寫(xiě)出A的真值表。(2)找出A的成假賦值。(3)求出每個(gè)成假賦值對(duì)應(yīng)的極大項(xiàng)（用名稱表示），按角標(biāo)從小到大順序析取。38例題例2.9 求命題公式 pq 的主析取范式和主合取范式。(1)

23、(1)求主合取范式求主合取范式pq pq pq pq M M2 2(2)(2)求主析取范式求主析取范式pq pq pqpq （pp（qqqq） （( (pppp)q)q） (pq)(pq)(pq)(pq) pq)(pq)(pq)(pq) (pq)(pq)(pq) (pq)(pq)(pq) m m0 0mm1 1mm3 3 解答pqp q00101110011139例2.8 求例2.7中公式的主析取范式和主合取范式(1)求主析取范式(pq)r (pqr)(pr)(qr)pqr m4pr p（qq）r (pqr)(pqr) m1m3 qr (pp)qr (pqr)(pqr) m3m7 (pq)r

24、m1m3m4m740例2.8 求例2.7中公式的主析取范式和主合取范式(2)求主合取范式(pq)r (pr)(qr)(pqr) pqr M5 pr p(qq)r (pqr)(pqr) M0M2 qr (pp)qr (pqr)(pqr) M2M6 (pq)r M0M2M5M6 41主析取范式的用途 o求公式的成真賦值與成假賦值o判斷公式的類型 o判斷兩個(gè)命題公式是否等值 o應(yīng)用主析取范式分析和解決實(shí)際問(wèn)題 42求公式的成真賦值與成假賦值o若公式A中含n個(gè)命題變項(xiàng)，A的主析取范式含s(0s2n)個(gè)極小項(xiàng)，則A有s個(gè)成真賦值，它們是所含極小項(xiàng)角標(biāo)的二進(jìn)制表示，其余2n-s個(gè)賦值都是成假賦值。o在例2

25、.8中，(pq)r m1m3m4m7,各極小項(xiàng)均含三個(gè)文字，因而各極小項(xiàng)的角標(biāo)均為長(zhǎng)為3的二進(jìn)制數(shù)，它們分別是001，011，100，111，這四個(gè)賦值為該公式的成真賦值,其余的為成假賦值。o在例2.9中，pq m0m1m3，這三個(gè)極小項(xiàng)均含兩個(gè)文字，它們的角標(biāo)的二進(jìn)制表示00，01，11為該公式的成真賦值，10是它的成假賦值。 43判斷公式的類型設(shè)公式A中含n個(gè)命題變項(xiàng)，容易看出：oA為重言式當(dāng)且僅當(dāng)A的主析取范式含全部2n個(gè)極小項(xiàng)。oA為矛盾式當(dāng)且僅當(dāng)A的主析取范式不含任何極小項(xiàng)。此時(shí)，記A的主析取范式為0。oA為可滿足式當(dāng)且僅當(dāng)A的主析取范式至少含一個(gè)極小項(xiàng)。44判斷公式的類型例2.10

26、 用公式的主析取范式判斷公式的類型：(1) (pq)q (2) p(pq) (3) (pq)r解答(1)(1)(pq)q pq)q （pqpq）q q (pq)q (pq)q 0 0 (2)p(pq) (2)p(pq) m m0 0mm1 1mm2 2mm3 3 (3)(3)(pq)r pq)r m m0 0mm1 1mm3 3mm5 5mm7 7 矛盾式矛盾式重言式重言式可滿足式可滿足式45判斷兩個(gè)命題公式是否等值o設(shè)公式A,B共含有n個(gè)命題變項(xiàng)，按n個(gè)命題變項(xiàng)求出A與B的主析取范式A與B。若AB,則AB；否則，A與B不等值。例2.11 判斷下面兩組公式是否等值：(1) p與(pq)(pq)

27、 (2) (pq)r與(q)r (1) (1) p p p(qq) p(qq) (pq)(pq) (pq)(pq) m m2 2mm3 3 ( (pq)(pq) pq)(pq) m m2 2mm3 3 兩公式等值。兩公式等值。(2) (2) ( (pq)r pq)r m m1 1mm3 3mm4 4mm5 5mm7 7 ( (q)r q)r m m0 0mm1 1mm2 2mm3 3mm4 4mm5 5mm7 7 兩公式不等值。兩公式不等值。解答46應(yīng)用主析取范式分析和解決實(shí)際問(wèn)題例例2.12某科研所要從3名科研骨干A,B,C中挑選12名出國(guó)進(jìn)修。由于工作原因，選派時(shí)要滿足以下條件：(1)若A

28、去，則C同去。(2)若B去，則C不能去。(3)若C不去，則A或B可以去。問(wèn)應(yīng)如何選派他們?nèi)ィ?分析：分析：(1)將簡(jiǎn)單命題符號(hào)化(2)寫(xiě)出各復(fù)合命題(3)寫(xiě)出由(2)中復(fù)合命題組成的合取式（前提）(4)將(3)中公式化成析取式（最好是主析取范式）(5)這樣每個(gè)小項(xiàng)就是一種可能產(chǎn)生的結(jié)果。去掉不符合題意的小項(xiàng)，即得結(jié)論。 47應(yīng)用主析取范式分析和解決實(shí)際問(wèn)題設(shè) p:派A去，q:派B去，r:派C去 由已知條件可得公式 (pr)(qr)(r(pq) 經(jīng)過(guò)演算可得 (pr)(qr)(r(pq) m1m2m5 由于 m1=pqr, m2=pqr, m5=pqr可知，選派方案有3種：(a)C去，而A,B都不去。(b)B去，而A,C都不去。(c)A,C去，而B(niǎo)不去。解答48由公式的主析取范式求主合取范式 設(shè)公式A含n個(gè)命題變項(xiàng)。A的主析取范式含s(0s2n)個(gè)極小項(xiàng)，即sjimmmAnjiiis, 2 , 1, 120 ,21沒(méi)有出現(xiàn)的極小項(xiàng)設(shè)為沒(méi)有出現(xiàn)的極小項(xiàng)設(shè)為snjjjmmm221,它們的角標(biāo)的二進(jìn)制表示為它們的角標(biāo)的二進(jìn)制表示為A A的成真賦值，因而的成真賦值，因而A A的主的主析取范式為析取范式為snjjjmm