南京郵電離散數(shù)學(xué)集合13-4

1、11.3 命題邏輯等值演算命題邏輯等值演算 np,q是命題變項(xiàng)是命題變項(xiàng)，pq 與與 p q在在4個(gè)賦值個(gè)賦值00、01、10、11下均有相同的真值，即下均有相同的真值，即(pq)( p q)的取值都為的取值都為1（重言式，永（重言式，永真式）。真式）。n給定給定n個(gè)命題變項(xiàng)，按合式公式的規(guī)則可以個(gè)命題變項(xiàng)，按合式公式的規(guī)則可以形成無(wú)數(shù)個(gè)命題公式。形成無(wú)數(shù)個(gè)命題公式。nn個(gè)命題變項(xiàng)共個(gè)命題變項(xiàng)共2n個(gè)賦值，每個(gè)賦值時(shí)命題個(gè)賦值，每個(gè)賦值時(shí)命題公式的值為公式的值為0或或1，因此，因此n個(gè)命題變項(xiàng)共生成個(gè)命題變項(xiàng)共生成22(n)個(gè)真值不同的命題公式。如個(gè)真值不同的命題公式。如n=2，共，共16個(gè)真

2、值不同的命題公式。個(gè)真值不同的命題公式。 如何判斷那些命題公式具有相同的真值？如何判斷那些命題公式具有相同的真值？2等值式等值式 定義定義 若等價(jià)式若等價(jià)式AB是重言式，則稱是重言式，則稱A與與B等值等值， 記作記作AB，并稱，并稱AB是是等值式等值式 說(shuō)明：說(shuō)明： 1. 不是聯(lián)結(jié)詞不是聯(lián)結(jié)詞 2. 等值關(guān)系是自反的、對(duì)稱的、傳遞的等值關(guān)系是自反的、對(duì)稱的、傳遞的 用真值表可驗(yàn)證兩個(gè)公式是否等值用真值表可驗(yàn)證兩個(gè)公式是否等值 AB是重言式是重言式 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) A和和B的值相同的值相同請(qǐng)驗(yàn)證：請(qǐng)驗(yàn)證： p(qr) (p q) r p(qr) (pq) r 3基本等值式基本等值式 (A,B,

3、C代表任意的命題公式代表任意的命題公式)n雙重否定律雙重否定律 : AAn等冪律：等冪律： A AA, A AAn交換律交換律: A BB A, A BB An結(jié)合律結(jié)合律: (A B) CA (B C) (A B) CA (B C)n分配律分配律: A (B C)(A B) (A C) A (B C) (A B) (A C)n德德摩根律摩根律: (A B)AB (A B)ABn矛盾律矛盾律: AA04基本等值式基本等值式( (續(xù)續(xù)) )n吸收律吸收律: A (A B)A, A (A B)An零律零律: A 11, A 00 n同一律同一律: A 0A, A 1An排中律排中律: AA1n蘊(yùn)涵

4、等值式蘊(yùn)涵等值式: ABA Bn等價(jià)等值式等價(jià)等值式: AB(AB) (BA)n假言易位假言易位: ABB An等價(jià)否定等值式等價(jià)否定等值式: ABA Bn歸謬論歸謬論: (AB) (A B) A5等值演算與置換規(guī)則等值演算與置換規(guī)則 n等值演算等值演算: 由已知的等值式推演出新的等值式的過(guò)由已知的等值式推演出新的等值式的過(guò)程程n置換規(guī)則置換規(guī)則： (A)是含有命題公式是含有命題公式A的命題公式，的命題公式，若若AB, 則則 (B) (A) n等值演算的基礎(chǔ)：等值演算的基礎(chǔ)： (1) 等值關(guān)系的性質(zhì)：自反、對(duì)稱、傳遞等值關(guān)系的性質(zhì)：自反、對(duì)稱、傳遞 (2) 基本的等值式基本的等值式 (3) 置

5、換規(guī)則置換規(guī)則 np(q r) 因?yàn)橐驗(yàn)?(p r)pr 則，則， p(q r) p ( pr) 6應(yīng)用舉例應(yīng)用舉例證明兩個(gè)公式等值證明兩個(gè)公式等值 例例1 證明證明 p(qr) (p q)r證證 p(qr) p ( q r) （蘊(yùn)涵等值式，置換規(guī)則）（蘊(yùn)涵等值式，置換規(guī)則） ( pq) r （結(jié)合律，置換規(guī)則）（結(jié)合律，置換規(guī)則） (p q) r （德摩根律，置換規(guī)則）（德摩根律，置換規(guī)則） (p q) r （蘊(yùn)涵等值式，置換規(guī)則）（蘊(yùn)涵等值式，置換規(guī)則） 說(shuō)明說(shuō)明: :也可以從右邊開(kāi)始演算（請(qǐng)做一遍）也可以從右邊開(kāi)始演算（請(qǐng)做一遍） 因?yàn)槊恳徊蕉加弥脫Q規(guī)則，故可不寫出因?yàn)槊恳徊蕉加弥脫Q規(guī)則

6、，故可不寫出 熟練后，基本等值式也可以不寫出熟練后，基本等值式也可以不寫出 7應(yīng)用舉例應(yīng)用舉例證明兩個(gè)公式不等值證明兩個(gè)公式不等值例例2 證明證明: p(qr) (pq) r 用等值演算不能直接證明兩個(gè)公式不等值用等值演算不能直接證明兩個(gè)公式不等值,證明兩證明兩個(gè)公式不等值的基本思想是找到一個(gè)賦值使一個(gè)成個(gè)公式不等值的基本思想是找到一個(gè)賦值使一個(gè)成真真,另一個(gè)成假另一個(gè)成假. 方法一方法一 真值表法（自己證）真值表法（自己證） 方法二方法二 觀察賦值法觀察賦值法. 容易看出容易看出000, 010等是左邊的等是左邊的成真賦值，是右邊的成假賦值成真賦值，是右邊的成假賦值. 方法三方法三 用等值演

7、算先化簡(jiǎn)兩個(gè)公式，再觀察用等值演算先化簡(jiǎn)兩個(gè)公式，再觀察.8應(yīng)用舉例應(yīng)用舉例判斷公式類型判斷公式類型 例例3 3 用等值演算法判斷下列公式的類型用等值演算法判斷下列公式的類型(1) q(pq) 解解 q(pq) q( p q) （蘊(yùn)涵等值式）（蘊(yùn)涵等值式） q (pq) （德摩根律）（德摩根律） p (qq) （交換律，結(jié)合律）（交換律，結(jié)合律） p 0 （矛盾律）（矛盾律） 0 （零律）（零律）由最后一步可知，該式為矛盾式由最后一步可知，該式為矛盾式. 9例例3 (續(xù)續(xù))(2) (pq)( qp) 解解 (pq)( qp) ( p q)(qp) （蘊(yùn)涵等值式）（蘊(yùn)涵等值式） ( p q)(

8、p q) （交換律）（交換律） 1由最后一步可知，該式為重言式由最后一步可知，該式為重言式.問(wèn)：最后一步為什么等值于問(wèn)：最后一步為什么等值于1？ (3) q ( p q) p)101.4 聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集 復(fù)合聯(lián)結(jié)詞復(fù)合聯(lián)結(jié)詞 排斥或排斥或 與非式與非式 或非式或非式真值函數(shù)真值函數(shù)聯(lián)結(jié)詞全功能集聯(lián)結(jié)詞全功能集11復(fù)合聯(lián)結(jié)詞復(fù)合聯(lián)結(jié)詞 n排斥或（異或）排斥或（異或）: “p、q之中恰好有一個(gè)成立之中恰好有一個(gè)成立” p q(pq) ( p q) n與非式與非式: “p與與q的否定的否定” p q(p q)n或非式或非式: “p或或q的否定的否定” p q(p q) 問(wèn)題：多少個(gè)聯(lián)結(jié)

9、詞最合適？問(wèn)題：多少個(gè)聯(lián)結(jié)詞最合適？12真值函數(shù)真值函數(shù) n問(wèn)題：含問(wèn)題：含n個(gè)命題變項(xiàng)的所有公式共產(chǎn)生多少個(gè)互個(gè)命題變項(xiàng)的所有公式共產(chǎn)生多少個(gè)互不相同的真值表？不相同的真值表？ 答案為答案為 個(gè)，為什么？個(gè)，為什么？n定義定義 稱定義域?yàn)榉Q定義域?yàn)?00, 001, , 111，值域，值域?yàn)闉?,1的函數(shù)是的函數(shù)是n元真值函數(shù)元真值函數(shù)，定義域中的元素是，定義域中的元素是長(zhǎng)為長(zhǎng)為n的的0,1串串. 常用常用F:0,1n0,1 表示表示F是是n元真值元真值函數(shù)函數(shù). 共有共有 個(gè)個(gè)n元真值函數(shù)元真值函數(shù). n 例如例如 F:0,120,1，且，且F(00)=F(01)=F(11)=0，F(xiàn)(10

10、)=1，則，則F為一個(gè)確定的為一個(gè)確定的2元真值函數(shù)元真值函數(shù).n22n22132元真值函數(shù)對(duì)應(yīng)的真值表元真值函數(shù)對(duì)應(yīng)的真值表p q0 00 11 01 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 )2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0FFFFFFFFp q0 00 11 01 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 )2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(

11、8FFFFFFFF14命題公式與真值函數(shù)命題公式與真值函數(shù) )2(13Fn對(duì)于任何一個(gè)含對(duì)于任何一個(gè)含n個(gè)命題變項(xiàng)的命題公式個(gè)命題變項(xiàng)的命題公式A，都存，都存在惟一的一個(gè)在惟一的一個(gè)n元真值函數(shù)元真值函數(shù)F為為A的真值表的真值表. .n等值的公式對(duì)應(yīng)的真值函數(shù)相同等值的公式對(duì)應(yīng)的真值函數(shù)相同. 例如：例如：pq, p q, ( p q) ( (pq) q) 等等都對(duì)應(yīng)都對(duì)應(yīng)表中的表中的15聯(lián)結(jié)詞的全功能集聯(lián)結(jié)詞的全功能集 n定義定義 在一個(gè)聯(lián)結(jié)詞的集合中，如果一個(gè)聯(lián)結(jié)詞可在一個(gè)聯(lián)結(jié)詞的集合中，如果一個(gè)聯(lián)結(jié)詞可由集合中的其他聯(lián)結(jié)詞定義，則稱此聯(lián)結(jié)詞為由集合中的其他聯(lián)結(jié)詞定義，則稱此聯(lián)結(jié)詞為冗余冗

12、余的聯(lián)結(jié)詞的聯(lián)結(jié)詞，否則稱為，否則稱為獨(dú)立的聯(lián)結(jié)詞獨(dú)立的聯(lián)結(jié)詞.例如例如,在聯(lián)結(jié)詞集在聯(lián)結(jié)詞集 , , , , 中，由于中，由于 pqp q, 所以，所以，為冗余的聯(lián)結(jié)詞為冗余的聯(lián)結(jié)詞; 類似地，類似地，也是冗余的聯(lián)結(jié)詞也是冗余的聯(lián)結(jié)詞. 又在又在 , , 中，由于中，由于p q( pq), 所以，所以， 是冗余的聯(lián)結(jié)詞，但是冗余的聯(lián)結(jié)詞，但 , 無(wú)冗余的聯(lián)結(jié)詞無(wú)冗余的聯(lián)結(jié)詞.類似地，類似地， 也是冗余的聯(lián)結(jié)詞，但也是冗余的聯(lián)結(jié)詞，但 , 無(wú)冗余的無(wú)冗余的聯(lián)結(jié)詞聯(lián)結(jié)詞. 16聯(lián)結(jié)詞的全功能集聯(lián)結(jié)詞的全功能集( (續(xù)續(xù)) )n定義定義 設(shè)設(shè)S是一個(gè)聯(lián)結(jié)詞集合，如果任何是一個(gè)聯(lián)結(jié)詞集合，如果任何n

13、(n 1) 元真值函數(shù)都可以由僅含元真值函數(shù)都可以由僅含S中的聯(lián)中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱結(jié)詞構(gòu)成的公式表示，則稱S是是聯(lián)結(jié)詞全功聯(lián)結(jié)詞全功能集能集.如果聯(lián)結(jié)詞全功能集不含冗余的聯(lián)結(jié)如果聯(lián)結(jié)詞全功能集不含冗余的聯(lián)結(jié)詞，則稱為詞，則稱為極小功能集極小功能集.n說(shuō)明：說(shuō)明： 1. 若若S是聯(lián)結(jié)詞全功能集，則任何命題公式是聯(lián)結(jié)詞全功能集，則任何命題公式都可用都可用S中的聯(lián)結(jié)詞表示中的聯(lián)結(jié)詞表示. 2. 若若S1, S2是兩個(gè)聯(lián)結(jié)詞集合，且是兩個(gè)聯(lián)結(jié)詞集合，且S1 S2. 若若S1是全功能集，則是全功能集，則S2也是全功能集也是全功能集. 17聯(lián)結(jié)詞的全功能集實(shí)例聯(lián)結(jié)詞的全功能集實(shí)例 (1) S1= , , , (2) S2= , , , , (3) S3= , (4) S4= , (5) S5= , (6) S6= (7) S7= 而而 , 等則不是聯(lián)結(jié)詞全功能集等則不是聯(lián)結(jié)詞全功能集. 18n例例 如已知如已知 , 是全功能集，證明是全功能集，證明 , 也是全也是全功能集功能集證：證： 因?yàn)橐驗(yàn)?, 是全功能集，任意一