1、1.4 真值表與等價(jià)公式,1.4.1 真值表 前面在定義聯(lián)結(jié)詞時(shí),曾經(jīng)使用過真值表,下面給出真值表的定義.,定義1.4.1 (對(duì)公式的賦值或解釋或指派) 設(shè)P1 , P2 ,Pn是出現(xiàn)在公式A中的全部的命題變?cè)? 給P1 , P2 ,Pn各指定一個(gè)真值，稱為對(duì)A的一個(gè)賦值或指派。若指定的一組值使A的真值為真(假), 稱這組值為A的成真(假)賦值.,例如:對(duì)公式(PQ)R，賦值011(即令P=0， Q=1， R=1) 為(PQ)R的成真賦值; 另一組 賦值010為(PQ)R的成假賦值；還有000， 001，111,考慮：含有n個(gè)命題變?cè)墓焦灿卸嗌俳M不同的賦值？,定義1.4.2(真值表)在命題

2、公式A中, 對(duì)于命題變 元的每一組賦值和由它們所確定的命題公式A 的真值列成表，稱做命題公式A 的真值表。,為方便構(gòu)造真值表， 特約定如下： 命題變?cè)醋值湫蚺帕小?對(duì)每個(gè)指派，以二進(jìn)制數(shù)從小到大或從大到小順序列出。 若公式較復(fù)雜，可先列出各子公式的真值(若有括號(hào)，則應(yīng)從里層向外層展開)，最后列出所求公式的真值。,例1. 給出(PQ)(PQ)的真值表：,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,例2：構(gòu)造公式 (P Q) R的 真值表。,例2：構(gòu)造公式 (P Q) R的 真值表。,練習(xí)1：構(gòu)造公式 (PQ)(Q P)真值表。,練習(xí)1：構(gòu)造公式 (PQ)(Q P)真值表。,

3、練習(xí)2：構(gòu)造公式 (PQ)Q真值表。,練習(xí)2：構(gòu)造公式 (PQ)Q真值表。,1.4.2 公式分類與等價(jià)公式,1.4.2.1 公式分類 定義1.4.3 設(shè) A 為任意公式，則 對(duì)應(yīng)每一個(gè)指派，公式 A 均相應(yīng)確定真值為真，稱 A 為重言式，或永真式。 對(duì)應(yīng)每一個(gè)指派，公式 A 均相應(yīng)確定真值為假，稱 A 為矛盾式，或永假式。 至少存在一個(gè)指派，公式 A 相應(yīng)確定真值為真，稱 A 為可滿足式。,由定義可知，重言式必是可滿足式，反之一般不真。 重點(diǎn)將研究重言式，它最有用，因?yàn)樗幸韵绿攸c(diǎn)： 重言式的否定是矛盾式，矛盾式的否定是重言式，這樣只研究其一就可以了。 兩重言式的合取式、析取式、條件式和雙條件

4、式等都仍是重言式。于是，由簡(jiǎn)單的重言式可構(gòu)造出復(fù)雜的重言式。 由重言式使用公認(rèn)的規(guī)則可以產(chǎn)生許多有用等價(jià)式和蘊(yùn)涵式。,判定給定公式是否為永真式、永假式或可滿足式的問題，稱為給定公式的判定問題。 在命題邏輯中，由于任何一個(gè)命題公式的指派數(shù)目總是有限的，所以命題邏輯的判定問題是可解的。其判定方法有真值表法和公式推演法(等值演算法)。,等值演算在計(jì)算機(jī)硬件設(shè)計(jì)中,在開關(guān)理論和 電子元器件中都占有重要地位.,定義1.4.4:設(shè)A和B是兩個(gè)命題公式，如果A、B在其任意指派下，其真值都是相同的，則稱A和B是等價(jià)的，或邏輯相等，記作AB，讀作A等價(jià)B，稱AB為等價(jià)式。例1中， AB 。 顯然，若公式A和B的

5、真值表是相同的，則A和B等價(jià)。因此，驗(yàn)證兩公式是否等價(jià)，只需做出它們的真值表即可。,1.4.2.2 等價(jià)公式,注: (1) “ ”不是邏輯聯(lián)結(jié)詞. (2)命題公式之間的邏輯相等關(guān)系具有： 自反性：AA ； 對(duì)稱性：若AB，則BA； 傳遞性：若AB且BC，則AC。,定理 1A B當(dāng)且僅當(dāng)AB是永真式。 有時(shí)也稱A B是永真雙條件式。,證明公式等價(jià)的方法： 1. 真值表法 2. 等值演算法 1. 真值表法 例1.(PQ) (PQ) 見真值表例題1.,例2. 證明: PQ (PQ)(QP),例3：判斷公式 P(QR)、(PQ)R是否等價(jià)。,例3：判斷公式 P(QR)、(PQ)R是否等價(jià)。,2. 等值

6、演算法,代入規(guī)則和替換規(guī)則 在定義合成公式時(shí)，已看到了邏輯聯(lián)結(jié)詞能夠從已知公式形成新的公式，從這個(gè)意義上可把邏輯聯(lián)結(jié)詞看成運(yùn)算。除邏輯聯(lián)結(jié)詞外，還要介紹“代入”和“替換”，它們也有從已知公式得到新的公式的作用，因此有人也將它們看成運(yùn)算，這不無道理，而且在今后討論中，它的作用也是不容忽視的。,(1)代入規(guī)則 定理2 在一個(gè)永真式A中，任何一個(gè)原子命題變?cè)猂出現(xiàn)的每一處， 用另一個(gè)公式代入，所得公式B仍是永真式。本定理稱為代入規(guī)則。 (2)替換規(guī)則 定理3 設(shè)A1是合式公式A的子公式，若A1B1，并且將A中的A1用B1 替換得到公式B，則AB。稱該定理為替換規(guī)則。 滿足定理3條件的替換，稱為等價(jià)替

7、換。,代入和替換有兩點(diǎn)區(qū)別： 代入是對(duì)原子命題變?cè)缘?，而替換可對(duì)命題公式實(shí)行。 代入必須是處處代入，替換則可部分替換，亦可全部替換。,定義1.4.5(等值演算)：根據(jù)已知的等價(jià)公式,推演出另外一些等價(jià)公式的過程稱為等值演算.,常用的等價(jià)式： 1.雙重否定律： P P 2.結(jié)合律：(PQ)RP(QR) (PQ)RP(QR) (PQ)RP(QR) 3.交換律: PQQP PQ QP PQ QP 4. 分配律: P(QR )(PQ)(PR) P(QR)(PQ)(PR) 5.冪等律: PP P PP P 6.吸收律: P(PQ) P P(PQ)P,7.德.摩根律: (PQ)PQ (PQ)PQ 8.

8、同一律: PFP PTP 9.零律: PTT PFF 10.否定律： PPT PPF 11. 蘊(yùn)涵等值式: PQ PQ 12. 等價(jià)等值式: PQ(PQ)(QP) (PQ)(PQ) 13. 假言易位: PQQP 14. 等價(jià)否定等值式: PQPQ 15. 歸謬論: (PQ )( PQ)P 16. 輸出律：(PQ)RP(QR),例1： 證明 Q(P(PQ)QP 證: Q(P(PQ) QP P(吸收律) 例2： 證明 (PQ)QPQ 證： 左式=(PQ)Q (PQ)(QQ) (PQ)T PQ =右式,例3：證明(PQ)(QR) PQR 證：左式=(PQ)(QR) (PQ)(QR) (PQ)(QR) (PQ)(QR) (PQR)(QQR) PQR =右式,例4：驗(yàn)證P(QR) (PQ)R 證: 右(PQ)R PQR P(QR) P(QR) P(QR) 左 練習(xí)：1.(PQ)(PR)P(QR) 2.(PQ)(PQ)(PQ)(PQ),小結(jié)