1、121.4.1 真值表真值表(Truth Table)1.4.2 等價(jià)公式等價(jià)公式(1.4.1 真值表真值表 前面在定義聯(lián)結(jié)詞時(shí)前面在定義聯(lián)結(jié)詞時(shí),曾經(jīng)使用過真值表曾經(jīng)使用過真值表,下面給出下面給出真值表的定義真值表的定義. 定義定義1.4.1 (對公式的賦值或解釋對公式的賦值或解釋)設(shè)設(shè)P1 , P2 ,Pn是出是出現(xiàn)在公式現(xiàn)在公式A中的全部的命題變元中的全部的命題變元, 給給P1 , P2 ,Pn各指各指定一個(gè)真值，稱為對定一個(gè)真值，稱為對A的一個(gè)的一個(gè)賦值賦值或或解釋解釋。若指定的。若指定的一組值使一組值使A的真值為真的真值為真(假假), 稱這組值為稱這組值為A的的成真成真(假假)賦值賦

2、值.3比如比如:對公式對公式(PQ)R,賦值賦值FTT(即令即令P=F,Q=T,R=T) 為為(PQ)R的成真賦值的成真賦值; 另一組賦值另一組賦值FTF為為(PQ)R的成假賦值；還有的成假賦值；還有FFF，F(xiàn)FT，TTT考慮：考慮：含有含有n個(gè)命題變元的公式共有多少組個(gè)命題變元的公式共有多少組不同的賦值？不同的賦值？定義定義1.4.2(真值表真值表)在命題公式在命題公式A中中, 對于命題變元的對于命題變元的每一組賦值和由它們所確定的命題公式每一組賦值和由它們所確定的命題公式A的真值列的真值列成表，稱做命題公式成表，稱做命題公式A 的的真值表真值表。4對公式對公式A構(gòu)造真值表的具體步驟為：構(gòu)造

3、真值表的具體步驟為：（1）找出公式中所有命題變元）找出公式中所有命題變元P1 , P2 ,Pn , 列出全部的列出全部的2n組賦值。組賦值。（2）按從小到大的順序列出對命題變元）按從小到大的順序列出對命題變元P1 , P2 ,Pn ,的全部的全部2n組賦值。組賦值。（3）對應(yīng)各組賦值計(jì)算出公式）對應(yīng)各組賦值計(jì)算出公式A的真值，并的真值，并將其列在對應(yīng)賦值的后面。將其列在對應(yīng)賦值的后面。5例例1. 1. 給出給出(P(P Q)Q)(P(P Q)Q)的真值表：的真值表：P P Q Q P P Q Q (P(P Q)Q) PP Q Q(P(P Q) Q) (P (P Q)Q)F F F FF F T

4、 TT T F FT T T T6例例1. 1. 給出給出(P(P Q)Q)(P(P Q)Q)的真值表：的真值表：P P Q Q P P Q Q (P(P Q)Q) PP Q Q(P(P Q) Q) (P (P Q)Q)F F F FF FT TT TT TF F T TF FT TT TT TT T F FF FT TT TT TT T T TT TF FF FT T7例例2：構(gòu)造公式：構(gòu)造公式 (P Q) R的的 真值表。真值表。PQRPQ(P Q) RFFFFFTFTFFTTTFFTFTTTFTTT8例例2：構(gòu)造公式：構(gòu)造公式 (P Q) R的的 真值表。真值表。PQRPQ(P Q) R

5、FFFTFFFTTTFTFTFFTTTTTFFFFTFTFFTTFTFTTTTT9 練習(xí)練習(xí)1：構(gòu)造公式：構(gòu)造公式 (PQ)( Q P真值表。真值表。P Q P QP Q Q P(P Q)( Q P)FFFTTFTT10 練習(xí)練習(xí)1：構(gòu)造公式：構(gòu)造公式 (PQ)( Q P真值表。真值表。P Q P QP Q Q P(P Q)( Q P)FFTTTTTFTTFTTTTFFTFFTTTFFTTT11PQ (P Q) (P Q) (P Q) QFFFTTFTT練習(xí)練習(xí)2：構(gòu)造公式：構(gòu)造公式 (P Q Q 真值表。真值表。12PQ (P Q) (P Q) (P Q) QFFTFFFTTFFTFFTFT

6、TTFF練習(xí)練習(xí)2：構(gòu)造公式：構(gòu)造公式 (P Q Q 真值表。真值表。131.4.2 等價(jià)公式等價(jià)公式給定給定n個(gè)個(gè) 命題命題變元變元, 按合式按合式公式的形公式的形成規(guī)則可以形成無數(shù)多個(gè)命題公式成規(guī)則可以形成無數(shù)多個(gè)命題公式, 但這但這些無窮盡的些無窮盡的命題公式中，有些具有相同的命題公式中，有些具有相同的真值表。真值表?？紤]：考慮：由由n個(gè)命題變元能生成個(gè)命題變元能生成? 種真值種真值(表表)不同的命題公式？不同的命題公式？) 1( n141.4.2 等價(jià)公式等價(jià)公式定義定義1.4.3: 給定兩個(gè)命題公式給定兩個(gè)命題公式A和和B,設(shè)設(shè)P1 , P2 ,Pn為出現(xiàn)于為出現(xiàn)于A和和B中的所有原

7、子變元中的所有原子變元,若給若給P1 , P2 ,Pn任一組真值指派任一組真值指派, A和和B的真值都相同的真值都相同,則稱則稱A和和B是是等價(jià)的或邏輯相等等價(jià)的或邏輯相等.記作記作A B注注: (1) “ ”不是邏輯聯(lián)結(jié)詞不是邏輯聯(lián)結(jié)詞.(2)命題公式之間的邏輯相等關(guān)系具有命題公式之間的邏輯相等關(guān)系具有： 自反性：自反性：A A ；對稱性：若；對稱性：若A B，則，則B A； 傳遞性：若傳遞性：若A B且且B C，則，則A C。15 證明公式等價(jià)的方法：證明公式等價(jià)的方法： 1. 真值表法真值表法 2. 等值演算法等值演算法v1. 真值表法真值表法 例例1. (P1. (P Q) Q) (P

8、(P Q) Q) 見真值表例題見真值表例題1.1. 例例2. 2. 證明證明: P: PQ Q (PQ)(PQ) (QP)(QP)P PQ QP PQ QQPQPPQPQ (PQ)(PQ) (QP)(QP)F FF FF FT TT TF FT TT T16 證明公式等價(jià)的方法：證明公式等價(jià)的方法： 1. 真值表法真值表法 2. 等值演算法等值演算法v1. 真值表法真值表法 例例1. (P1. (P Q) Q) (P(P Q) Q) 見真值表例題見真值表例題1.1. 例例2. 2. 證明證明: P: PQ Q (PQ)(PQ) (QP)(QP)P PQ QP PQ QQPQPPQPQ (PQ)

9、(PQ) (QP)(QP)F FF FT TT TT TT TF FT TF FF FT TF FT TF FF FT TF FF FT TT TT TT TT TT T17例例3：判斷公式：判斷公式 P(QR)、(PQ)R是否等價(jià)。是否等價(jià)。P Q RP QQ R P (Q R) (P Q RFFFFTTTFFTFTTTFTFFFTTFTTFTTTTFFFTTTTFTFTTTTTFTFFFTTTTTTT18 由真值表可知，兩個(gè)公式為等價(jià)式。由真值表可知，兩個(gè)公式為等價(jià)式。 2、等值演算法、等值演算法(Equivalent Caculation)（利用（利用P15表表1-4.8) 重要的等價(jià)式

10、重要的等價(jià)式(補(bǔ)充補(bǔ)充): 11. 蘊(yùn)涵等值式蘊(yùn)涵等值式: : P PQ Q P P Q Q 12. 等價(jià)等價(jià)等值式等值式: : P PQ Q (PQ)(PQ) (QP)(QP) 13. 假言易位假言易位: P PQ Q Q Q PP 14. 等價(jià)否定等價(jià)否定等值式等值式: : P PQ Q PPQ Q 15. 歸謬論歸謬論: (P PQ Q ) ( ( P P Q)Q) P P 19 其中其中P, Q, R等代表任意命題公式等代表任意命題公式. 這樣上面的每一這樣上面的每一個(gè)公式都是一個(gè)模式個(gè)公式都是一個(gè)模式, 它可以代表無數(shù)多個(gè)同類它可以代表無數(shù)多個(gè)同類型的命題公式型的命題公式. 例如例如

11、, P P PPT T 中中, , 用用(P(P Q)Q)置置換換P,P,則得則得 (P(P Q)Q) (P(P Q)Q)T ,T ,用用PP置換置換P,P,則則得得 (P(P) ) (P(P) )T T 。等值演算中使用的一條重要規(guī)則：等值演算中使用的一條重要規(guī)則：置換規(guī)則。置換規(guī)則。 定義定義1.4.4(1.4.4(子公式子公式) )：如果如果X X是是wff Awff A的的一部分一部分, ,且且X X本身也是本身也是wffwff，則稱，則稱X X是是A A的的子公式。例如子公式。例如, P, P (P(P Q)Q)為為Q Q (P P (P(P Q)Q)的子公式。的子公式。20定理定理

12、1.4.1(置換定理置換定理Axiom of replacement)設(shè)設(shè)X X是是wff wff A A的子的子wffwff，若，若X XY Y，則若將，則若將A A中的中的X X用用Y Y來置換，來置換，所得公式所得公式B B與與A A等價(jià)，即等價(jià)，即A AB B。證：因?yàn)閷ψ冊娜我恢概勺C：因?yàn)閷ψ冊娜我恢概?X,X與與Y Y真值相同，所以真值相同，所以Y Y 取代取代X X后，公式后，公式B B與公式與公式A A對變元的任一指派真對變元的任一指派真值也相同值也相同, ,所以所以A AB B。注注: : 滿足滿足定理定理1.4.1的條件的置換稱為等價(jià)置換的條件的置換稱為等價(jià)置換(或等或

13、等價(jià)代換價(jià)代換).定義定義1.4.5(1.4.5(等值演算等值演算) )：根據(jù)已知的等價(jià)公式根據(jù)已知的等價(jià)公式, ,推演推演出另外一些等價(jià)公式的過程稱為出另外一些等價(jià)公式的過程稱為等值演算等值演算. 21例例1 1： 證明證明 QQ（P P （P P Q Q）QPQP 證證: Q: Q（P P （P P Q Q）QPQP P( P(吸收律吸收律) ) 例例2 2： 證明證明 P P QQ Q Q P P Q Q證：證： (P(P Q)Q) Q Q(P(P Q)Q) ( (QQ Q)Q)( (P P Q)Q) T TP P Q Q例例3 3：證明（：證明（PQPQ）（Q Q R R ） P P

14、Q Q R R證：（證：（PQPQ）（Q Q R R ） （PP Q Q）（Q Q R R） （PP Q Q） （Q Q R R） （P P QQ） （Q Q R R） （P P Q Q R R） （QQ Q Q R R） P Q R 22例例4：驗(yàn)證驗(yàn)證P(QR) (P Q) R證證: 右右 (P Q) R P Q R P ( Q R) P (Q R) P (Q R)練：練：1.(P Q) (P R) P (Q R) 2.(P Q) ( P Q) (P Q) (P Q) 23v等值演算等值演算在計(jì)算機(jī)硬件設(shè)計(jì)中在計(jì)算機(jī)硬件設(shè)計(jì)中,在開關(guān)理論和電子元在開關(guān)理論和電子元器件中都占有重要地位器件中都