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

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

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

3、為左邊公式中的啞元。用真值表可以驗證兩個公式是否等值。用真值表可以驗證兩個公式是否等值。5例題例2.1 判斷下面兩個公式是否等值(pq) 與 pq 解答在用真值表法判斷在用真值表法判斷A AB B是否為重言式時，真值是否為重言式時，真值表的最后一列可以省略表的最后一列可以省略。等值等值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.結合律(AB)C A(BC) (AB)C A(BC) 5.分配律 A(BC) (AB)(

4、AC) （對的分配律）A(BC) (AB)(AC)（對的分配律）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.蘊涵等值式 AB AB13.等價等值式 AB (AB)(BA)14.假言易位 AB BA15.等價否定等值式 AB AB16.歸謬論 (AB)(AB) A 9對偶原理一個邏輯等值式，如果只含有、0、1那么同時把和互換把0和1互換得到的還是等值式。10等值演算與置換規(guī)則o各等值式都是用元語言符號書寫的，其中A,B,C可

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

6、遞性：若AB且BC，則AC。n基本的等值式n置換規(guī)則o等值演算的應用n證明兩個公式等值n判斷公式類型n解判定問題12等值演算的應用舉例證明兩個公式等值(pq)r (pr)(qr)( (pqpq)r )r (pq)(pq)rr（蘊含等值式、置換規(guī)則）蘊含等值式、置換規(guī)則） (pq)pq)rr（蘊含等值式、置換規(guī)則）蘊含等值式、置換規(guī)則） ( (pq)pq)rr（德摩根律、置換規(guī)則）德摩根律、置換規(guī)則） ( (pr)(qr)pr)(qr) （分配律、置換規(guī)則）分配律、置換規(guī)則）也可以從右邊開始演算也可以從右邊開始演算因為每一步都用置換規(guī)則，故可不寫出因為每一步都用置換規(guī)則，故可不寫出熟練后，基本等

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

8、0是p(qr)的成真賦值，所以原不等值式成立。 方法三、通過等值演算化容易觀察真值的情況，再進行判斷。A=(pq)r (pq)r （蘊涵等值式） (pq)r （蘊涵等值式） (pq)r （德摩根律） B=p(qr) p(qr) （蘊涵等值式） pqr （結合律） 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 （蘊涵等值式）蘊涵等值式） (pq)p)pq)p)q q （蘊涵

9、等值式）蘊涵等值式） ( (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 應用題在某次研討會的中間休息時間，3名與會者根據(jù)王教授的口音對他是哪個省市的人進行了判斷：甲說王教授不是蘇州人，是上海人。乙說王教授不是上海人，是蘇州人。丙說王教授既不是上海人，也不是杭州人。聽完以上3人的判斷后，王教授笑著說，他們3人中有一人說的全對，有一人說對了一半，另一人說的全不對。試用邏輯演算法分析王教授到底是哪里人？ 19例2.6 解答設命題 p：王教授是蘇州人。 q：王教授是上海人。 r：王教授是杭州人。p,q,r中必有一個真命題，兩個假命題

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

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

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

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

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

16、范式和合取范式的性質定理定理2.2(1)一個析取范式是矛盾式當且僅當它的每個簡單合取式都是矛盾式。(2)一個合取范式是重言式當且僅當它的每個簡單析取式都是重言式。 研究范式的目的在于，將給定公式化成與之等值的析取研究范式的目的在于，將給定公式化成與之等值的析取范式或合取范式，進而將公式化成與之等值的主析取范式或合取范式，進而將公式化成與之等值的主析取范式或主合取范式。范式或主合取范式。28范式存在的討論o在范式中不會出現(xiàn)聯(lián)結詞與，否則可使用等值式消除AB ABAB (AB)(AB)o在范式中不會出現(xiàn)如A,(AB),(AB)的公式：A A(AB) AB (AB)ABo在析取范式中不會出現(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)結詞、(若存在)。AB ABAB (AB)(AB)(2)否定號的消去(利用雙重否定律)或內移(利用德摩根律)。A A(AB) AB(AB)AB(3)利用分配律：利用對的分配律求析取范式， 對的分配律求合取范式。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) （否定號內移）否定號內移） ( (pr)(qr)(pqr)pr)(qr)(pqr)（對對分配律）分配律）解答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個命題變項的簡單合取式（簡單析取式）中，若每個命題變項和它的否定式不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個命題變項或它的否定式出現(xiàn)在從左算起的第i位上（若命題變項無角標，就按字典順序排列），稱這樣的簡單合取式（簡單析取式）為極小項極小項（極大項極大項）。on個命題變項共可產(chǎn)生2n個不同的極小項。其中每個極小項都有且僅有一個成

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

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

22、寫出A的真值表。(2)找出A的成真賦值。(3)求出每個成真賦值對應的極小項（用名稱表示），按角標從小到大順序析取。37求公式A的主合取范式的方法與步驟方法一、等值演算法方法一、等值演算法(1)化歸為合取范式。 (2)除去合取范式中所有永真的合取項。(3)將合取式中重復出現(xiàn)的析取項和相同的變元合并。(4)對析取項補入沒有出現(xiàn)的命題變元，即添加如(pp)式，然后應用分配律展開公式。方法二、真值表法方法二、真值表法(1)寫出A的真值表。(2)找出A的成假賦值。(3)求出每個成假賦值對應的極大項（用名稱表示），按角標從小到大順序析取。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判斷兩個命題公式是否等值 o應用主析取范式分析和解決實際問題 42求公式的成真賦值與成假賦值o若公式A中含n個命題變項，A的主析取范式含s(0s2n)個極小項，則A有s個成真賦值，它們是所含極小項角標的二進制表示，其余2n-s個賦值都是成假賦值。o在例2

25、.8中，(pq)r m1m3m4m7,各極小項均含三個文字，因而各極小項的角標均為長為3的二進制數(shù)，它們分別是001，011，100，111，這四個賦值為該公式的成真賦值,其余的為成假賦值。o在例2.9中，pq m0m1m3，這三個極小項均含兩個文字，它們的角標的二進制表示00，01，11為該公式的成真賦值，10是它的成假賦值。 43判斷公式的類型設公式A中含n個命題變項，容易看出：oA為重言式當且僅當A的主析取范式含全部2n個極小項。oA為矛盾式當且僅當A的主析取范式不含任何極小項。此時，記A的主析取范式為0。oA為可滿足式當且僅當A的主析取范式至少含一個極小項。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判斷兩個命題公式是否等值o設公式A,B共含有n個命題變項，按n個命題變項求出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應用主析取范式分析和解決實際問題例例2.12某科研所要從3名科研骨干A,B,C中挑選12名出國進修。由于工作原因，選派時要滿足以下條件：(1)若A

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