離散數(shù)學(xué)(第12-13)陳瑜

1、2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院1 1陳瑜陳瑜Email：2022-2-142022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院2 2主要內(nèi)容主要內(nèi)容n 命題合適公式與真值表命題合適公式與真值表 1 1）命題常項(xiàng)與命題變項(xiàng)）命題常項(xiàng)與命題變項(xiàng) 2 2）命題公式與賦值）命題公式與賦值 3 3）永真式）永真式 4 4）矛盾式）矛盾式n 命題公式的等價(jià)命題公式的等價(jià) 1 1）基本等價(jià)式）基本等價(jià)式 2 2）等價(jià)式的判斷）等價(jià)式的判斷 2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院3 31.2 1.2 命

2、題合適公式與真值表命題合適公式與真值表n 一個(gè)特定的命題是一個(gè)一個(gè)特定的命題是一個(gè)常值命題常值命題，它不是具有它不是具有值值“T”(“1”)“T”(“1”)，就是具有值，就是具有值“F”(“0”)“F”(“0”)。n 而一個(gè)任意的沒(méi)有賦予具體內(nèi)容的原子命題是而一個(gè)任意的沒(méi)有賦予具體內(nèi)容的原子命題是一個(gè)變量命題，常稱(chēng)它為命題變量一個(gè)變量命題，常稱(chēng)它為命題變量( (或命題變或命題變?cè)? )，該命題變量無(wú)具體的真值，該命題變量無(wú)具體的真值，它的它的值域是值域是集合集合 T T，F(xiàn)(F(或或00，1)1)。n 當(dāng)原子命題是命題變?cè)獣r(shí)，當(dāng)原子命題是命題變?cè)獣r(shí)，其其復(fù)合命題也即為復(fù)合命題也即為命題變?cè)?/p>

3、命題變?cè)摹昂瘮?shù)函數(shù)”，且該，且該“函數(shù)函數(shù)”的值仍為的值仍為“真真”或或“假假”值，這樣的函數(shù)可形象地稱(chēng)為值，這樣的函數(shù)可形象地稱(chēng)為“真值函數(shù)真值函數(shù)”,”,或稱(chēng)為命題公式或稱(chēng)為命題公式, ,此命題公式?jīng)]此命題公式?jīng)]有確切真值。有確切真值。2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院4 41.2 1.2 命題合適公式與真值表命題合適公式與真值表n 一個(gè)特定的命題是一個(gè)常值命題一個(gè)特定的命題是一個(gè)常值命題，它不是具有它不是具有值值“T”(“1”)“T”(“1”)，就是具有值，就是具有值“F”(“0”)“F”(“0”)。n 而一個(gè)任意的沒(méi)有賦予具體內(nèi)容的原子命題是

4、而一個(gè)任意的沒(méi)有賦予具體內(nèi)容的原子命題是一個(gè)一個(gè)變量命題變量命題，常稱(chēng)它為，常稱(chēng)它為命題變量命題變量( (或或命題變命題變?cè)? )，該命題變量，該命題變量無(wú)具體無(wú)具體的真值，的真值，它的它的值域是值域是集合集合 T T，F(xiàn)(F(或或00，1)1)。n 當(dāng)原子命題是命題變?cè)獣r(shí)，當(dāng)原子命題是命題變?cè)獣r(shí)，其其復(fù)合命題也即為復(fù)合命題也即為命題變?cè)拿}變?cè)摹昂瘮?shù)函數(shù)”，且該，且該“函數(shù)函數(shù)”的值仍為的值仍為“真真”或或“假假”值，這樣的函數(shù)可形象地稱(chēng)為值，這樣的函數(shù)可形象地稱(chēng)為“真值函數(shù)真值函數(shù)”,”,或稱(chēng)為命題公式或稱(chēng)為命題公式, ,此命題公式?jīng)]此命題公式?jīng)]有確切真值。有確切真值。2022-2-

5、142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院5 51.2 1.2 命題合適公式與真值表命題合適公式與真值表n 一個(gè)特定的命題是一個(gè)常值命題一個(gè)特定的命題是一個(gè)常值命題，它不是具有它不是具有值值“T”(“1”)“T”(“1”)，就是具有值，就是具有值“F”(“0”)“F”(“0”)。n 而一個(gè)任意的沒(méi)有賦予具體內(nèi)容的原子命題是而一個(gè)任意的沒(méi)有賦予具體內(nèi)容的原子命題是一個(gè)變量命題，常稱(chēng)它為命題變量一個(gè)變量命題，常稱(chēng)它為命題變量( (或命題變或命題變?cè)? )，該命題變量無(wú)具體的真值，該命題變量無(wú)具體的真值，它的它的值域是值域是集合集合 T T，F(xiàn)(F(或或00，1)1)。n 當(dāng)原

6、子命題是命題變?cè)獣r(shí)，當(dāng)原子命題是命題變?cè)獣r(shí)，其其復(fù)合命題也即為復(fù)合命題也即為命題變?cè)拿}變?cè)摹昂瘮?shù)函數(shù)”，且該，且該“函數(shù)函數(shù)”的值仍為的值仍為“真真”或或“假假”值，這樣的函數(shù)可形象地稱(chēng)為值，這樣的函數(shù)可形象地稱(chēng)為“真值函數(shù)真值函數(shù)”,”,或稱(chēng)為或稱(chēng)為命題公式命題公式, ,此命題公式此命題公式?jīng)]沒(méi)有確切真值有確切真值。2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院6 6命題公式（合適公式）命題公式（合適公式）n定義定義1-2.1(1-2.1(命題公式命題公式, ,簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)公式公式) ) 1 1）命題命題變?cè)冊(cè)ㄔ用}變?cè)用}變?cè)┍旧硎且粋€(gè)公式；）本

7、身是一個(gè)公式； 2 2）如如P P，Q Q是公式，則是公式，則( (P)P)、(PQ)(PQ)、(PQ)(PQ)、 (PQ)(PQ)、(P(PQ)Q)也是公式；也是公式； 3 3）命題公式命題公式僅由僅由有限步有限步使用規(guī)則使用規(guī)則1-21-2后產(chǎn)生的結(jié)果。后產(chǎn)生的結(jié)果。 該公式常用符號(hào)該公式常用符號(hào)G G、H H、等表示。等表示。 注：為簡(jiǎn)單期間，以后稱(chēng)合適公式為公式。注：為簡(jiǎn)單期間，以后稱(chēng)合適公式為公式。n為書(shū)寫(xiě)和輸入計(jì)算機(jī)及計(jì)算方便起見(jiàn)，約定：為書(shū)寫(xiě)和輸入計(jì)算機(jī)及計(jì)算方便起見(jiàn)，約定： 1 1）最外層括號(hào)可以省略）最外層括號(hào)可以省略 2 2）按聯(lián)結(jié)詞的優(yōu)先級(jí)的括號(hào)可以省略）按聯(lián)結(jié)詞的優(yōu)先級(jí)

8、的括號(hào)可以省略2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院7 7命題公式（合適公式）命題公式（合適公式）n定義定義1-2.1(1-2.1(命題公式命題公式) ) 1 1）命題變?cè)ǎ┟}變?cè)ㄔ用}變?cè)用}變?cè)┍旧硎且粋€(gè)公式；）本身是一個(gè)公式； 2 2）如）如P P，Q Q是公式，則是公式，則( (P)P)、(PQ)(PQ)、(PQ)(PQ)、 (PQ)(PQ)、(P(PQ)Q)也是公式；也是公式； 3 3）命題公式僅由有限步使用規(guī)則）命題公式僅由有限步使用規(guī)則1-21-2后產(chǎn)生的結(jié)果。后產(chǎn)生的結(jié)果。 該公式常用符號(hào)該公式常用符號(hào)G G、H H、等表示。

9、等表示。 注：為簡(jiǎn)單期間，以后稱(chēng)合適公式為公式。注：為簡(jiǎn)單期間，以后稱(chēng)合適公式為公式。n為書(shū)寫(xiě)和輸入計(jì)算機(jī)及計(jì)算方便起見(jiàn)，約定：為書(shū)寫(xiě)和輸入計(jì)算機(jī)及計(jì)算方便起見(jiàn)，約定： 1 1）最外層括號(hào)可以省略）最外層括號(hào)可以省略 2 2）按聯(lián)結(jié)詞的優(yōu)先級(jí)的括號(hào)可以省略）按聯(lián)結(jié)詞的優(yōu)先級(jí)的括號(hào)可以省略2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院8 8命題公式（合適公式）命題公式（合適公式）n定義定義1-2.1(1-2.1(命題公式命題公式) ) 1 1）命題變?cè)ǎ┟}變?cè)ㄔ用}變?cè)用}變?cè)┍旧硎且粋€(gè)公式；）本身是一個(gè)公式； 2 2）如）如P P，Q Q是公式，則是

10、公式，則( (P)P)、(PQ)(PQ)、(PQ)(PQ)、 (PQ)(PQ)、(P(PQ)Q)也是公式；也是公式； 3 3）命題公式僅由有限步使用規(guī)則）命題公式僅由有限步使用規(guī)則1-21-2后產(chǎn)生的結(jié)果。后產(chǎn)生的結(jié)果。 該公式常用符號(hào)該公式常用符號(hào)G G、H H、等表示。等表示。 注：為簡(jiǎn)單期間，以后稱(chēng)合適公式為公式。注：為簡(jiǎn)單期間，以后稱(chēng)合適公式為公式。n為書(shū)寫(xiě)和輸入計(jì)算機(jī)及計(jì)算方便起見(jiàn)，為書(shū)寫(xiě)和輸入計(jì)算機(jī)及計(jì)算方便起見(jiàn)，約定約定： 1 1）最外層括號(hào)可以省略）最外層括號(hào)可以省略 2 2）按聯(lián)結(jié)詞的優(yōu)先級(jí)的括號(hào)可以省略）按聯(lián)結(jié)詞的優(yōu)先級(jí)的括號(hào)可以省略2022-2-142022-2-14計(jì)算

11、機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院9 9命題公式（合適公式）命題公式（合適公式）n定義定義1-2.1(1-2.1(命題公式命題公式) ) 1 1）命題變?cè)ǎ┟}變?cè)ㄔ用}變?cè)用}變?cè)┍旧硎且粋€(gè)公式；）本身是一個(gè)公式； 2 2）如）如P P，Q Q是公式，則是公式，則( (P)P)、(PQ)(PQ)、(PQ)(PQ)、 (PQ)(PQ)、(P(PQ)Q)也是公式；也是公式； 3 3）命題公式僅由有限步使用規(guī)則）命題公式僅由有限步使用規(guī)則1-21-2后產(chǎn)生的結(jié)果。后產(chǎn)生的結(jié)果。 該公式常用符號(hào)該公式常用符號(hào)G G、H H、等表示。等表示。 注：為簡(jiǎn)單期間，以后稱(chēng)合適公式為公式。注：為

12、簡(jiǎn)單期間，以后稱(chēng)合適公式為公式。n為書(shū)寫(xiě)和輸入計(jì)算機(jī)及計(jì)算方便起見(jiàn)，為書(shū)寫(xiě)和輸入計(jì)算機(jī)及計(jì)算方便起見(jiàn)，約定約定： 1 1）最外層括號(hào)可以省略）最外層括號(hào)可以省略 2 2）按聯(lián)結(jié)詞的優(yōu)先級(jí)的括號(hào)可以省略）按聯(lián)結(jié)詞的優(yōu)先級(jí)的括號(hào)可以省略 2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院1010n 符號(hào)串：符號(hào)串：(P(QR)(Q(P(QR)(Q(SR)SR)； ( (PQ)PQ)； (P( (P(PQ)(PQ)； (PQ)(RQ) (PQ)(RQ)(PR)(PR)。 等都是等都是命題公式命題公式。 符號(hào)串：符號(hào)串：(PQ)(PQ)Q)Q)；(PQ(PQ；( (PQ(RP

13、Q(R； PQ PQ。等都不是合法的命題公式。等都不是合法的命題公式。例例2.12.1：定義定義1-2.21-2.2：如公式：如公式A A是公式是公式B B的一部分，則稱(chēng)的一部分，則稱(chēng)A A是是B B的子公式。的子公式。2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院1111n 符號(hào)串：符號(hào)串：(P(QR)(Q(P(QR)(Q(SR)SR)； ( (PQ)PQ)； (P( (P(PQ)(PQ)； (PQ)(RQ) (PQ)(RQ)(PR)(PR)。 等都是命題公式。等都是命題公式。 符號(hào)串：符號(hào)串：(PQ)(PQ)Q)Q)； (PQ (PQ；( (PQ(RPQ(R；

14、 PQ PQ。等等都不是合法的命題公式都不是合法的命題公式。例例2.12.1：定義定義1-2.21-2.2：如公式：如公式A A是公式是公式B B的一部分，則稱(chēng)的一部分，則稱(chēng)A A是是B B的子公式。的子公式。2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院1212n 符號(hào)串：符號(hào)串：(P(QR)(Q(P(QR)(Q(SR)SR)； ( (PQ)PQ)； (P( (P(PQ)(PQ)； (PQ)(RQ) (PQ)(RQ)(PR)(PR)。 等都是命題公式。等都是命題公式。 符號(hào)串：符號(hào)串：(PQ)(PQ)Q)Q)；(PQ(PQ；( (PQ(RPQ(R； PQ PQ。

15、等都不是合法的命題公式。等都不是合法的命題公式。例例2.12.1：n定義定義1-2.21-2.2：如公式：如公式A A是公式是公式B B的一部分，則稱(chēng)的一部分，則稱(chēng)A A是是B B的的子公式子公式。2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院1313公式的解釋與真值表：公式的解釋與真值表：n 定義定義1-2.31-2.3 設(shè)設(shè)P P1 1、P P2 2、P Pn n是出現(xiàn)在公式是出現(xiàn)在公式G G中的所有命題變?cè)械乃忻}變?cè)?，指定指定P P1 1、P P2 2、P Pn n的的一組一組真值（如真值（如1 1，0 0，1 1，0 0，1 1），），則則這組真值這

16、組真值稱(chēng)稱(chēng)為為G G的的一個(gè)解釋一個(gè)解釋, ,常記為常記為。一般來(lái)說(shuō)，若有個(gè)命題變?cè)瑒t應(yīng)有一般來(lái)說(shuō)，若有個(gè)命題變?cè)瑒t應(yīng)有2 2n n個(gè)個(gè)不同的解釋。不同的解釋。n 定義定義1-2.4 1-2.4 如果公式如果公式G G在解釋下是真的，則在解釋下是真的，則稱(chēng)滿(mǎn)足稱(chēng)滿(mǎn)足G G；如果；如果G G在解釋下是假的，則稱(chēng)在解釋下是假的，則稱(chēng)弄假弄假G G。將公式。將公式G G在其所有可能解釋下在其所有可能解釋下的的真值情真值情況列成況列成的表，稱(chēng)為的表，稱(chēng)為G G的真值表的真值表。n個(gè)個(gè)2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院1414公式的解釋與真值表：公式的解釋與

17、真值表：n 定義定義1-2.3 1-2.3 設(shè)設(shè)P P1 1、P P2 2、P Pn n是出現(xiàn)在公式是出現(xiàn)在公式G G中的所有命題變?cè)械乃忻}變?cè)?，指定指定P P1 1、P P2 2、P Pn n的的一組一組真值（如真值（如1 1，0 0，1 1，0 0，1 1），），則則這組真值這組真值稱(chēng)稱(chēng)為為G G的一個(gè)解釋的一個(gè)解釋, ,常記為。常記為。一般來(lái)說(shuō)，若有個(gè)命題變?cè)?，則應(yīng)有一般來(lái)說(shuō)，若有個(gè)命題變?cè)?，則應(yīng)有2 2n n個(gè)個(gè)不同的解釋。不同的解釋。n 定義定義1-2.4 1-2.4 如果公式如果公式G G在解釋下是真的，則在解釋下是真的，則稱(chēng)滿(mǎn)足稱(chēng)滿(mǎn)足G G；如果；如果G G在解釋下是假的，

18、則稱(chēng)在解釋下是假的，則稱(chēng)弄假弄假G G。將公式。將公式G G在其所有可能解釋下在其所有可能解釋下的的真值情真值情況列成況列成的表，稱(chēng)為的表，稱(chēng)為G G的真值表的真值表。n個(gè)個(gè)2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院1515公式的解釋與真值表：公式的解釋與真值表：n 定義定義1-2.3 1-2.3 設(shè)設(shè)P P1 1、P P2 2、P Pn n是出現(xiàn)在公式是出現(xiàn)在公式G G中的所有命題變?cè)械乃忻}變?cè)?，指定指定P P1 1、P P2 2、P Pn n的的一組一組真值（如真值（如1 1，0 0，1 1，0 0，1 1），），則則這組真值這組真值稱(chēng)稱(chēng)為為G G的

19、一個(gè)解釋的一個(gè)解釋, ,常記為。常記為。一般來(lái)說(shuō)，若有個(gè)命題變?cè)?，則應(yīng)有一般來(lái)說(shuō)，若有個(gè)命題變?cè)?，則應(yīng)有2 2n n個(gè)個(gè)不同的解釋。不同的解釋。n 定義定義1-2.41-2.4 如果公式如果公式G G在解釋下是真的，則在解釋下是真的，則稱(chēng)稱(chēng)滿(mǎn)足滿(mǎn)足G G；如果；如果G G在解釋下是假的，則稱(chēng)在解釋下是假的，則稱(chēng)弄假弄假G G。將。將公式公式G G在其所有可能解釋下在其所有可能解釋下的的真值情真值情況列成況列成的表，稱(chēng)為的表，稱(chēng)為G G的真值表的真值表。n個(gè)個(gè)2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院1616構(gòu)造構(gòu)造公式公式G G1 1：P PQ Q的的真值表如

20、下：真值表如下：P PQ QP PPQPQ0 00 01 11 10 01 11 11 11 10 00 00 01 11 10 01 1例例2.22.2 P PQ Q和和PQPQ的的真值表完全一致真值表完全一致2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院1717構(gòu)造構(gòu)造公式公式G G1 1：P PQ Q的的真值表如下：真值表如下：P PQ QP PPQPQ0 00 01 11 10 01 11 11 11 10 00 00 01 11 10 01 1例例2.22.2 P PQ Q和和PQPQ的的真值表完全一致真值表完全一致2022-2-142022-2-14計(jì)

21、算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院1818構(gòu)造構(gòu)造公式公式G G2 2：( (PQPQ) () () )的真值表的真值表P PQ QPQPQ( (PQPQ) () () )0 00 01 10 0 0 00 01 11 10 0 0 01 10 00 01 1 0 01 11 11 10 0 0 0例例2.32.3該公式對(duì)所有可能的解釋取值均為該公式對(duì)所有可能的解釋取值均為0 02022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院1919P PQ QPQPQ( (PQPQ)0 00 01 11 10 01 11 11 11 10 00 01 11 11 11 11

22、1例例2.42.4構(gòu)造構(gòu)造公式公式G G3 3 ：( (PQPQ)的真值表的真值表該公式對(duì)所有可能的解釋取值均為該公式對(duì)所有可能的解釋取值均為1 12022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院2020從這三個(gè)真值表可以看到一個(gè)非常有趣的從這三個(gè)真值表可以看到一個(gè)非常有趣的事實(shí)：事實(shí)： 公式公式G G3 3對(duì)所有可能的解釋具有對(duì)所有可能的解釋具有“真真”值值 公式公式G G2 2對(duì)所有可能的解釋均具有對(duì)所有可能的解釋均具有“假假”值值 公式公式G G1 1則具有則具有“真真”和和“假假”值值結(jié)論：結(jié)論：G1：PQG2：(PQ) ()G3 ：(PQ)2022-2-1

23、42022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院2121定義定義1-2.51-2.5：1 1）公式公式G G3 3稱(chēng)為稱(chēng)為永真公式永真公式( (重言式重言式) )，如果在如果在它的所有解釋之下都為它的所有解釋之下都為“真真”。2 2）公式）公式G G2 2稱(chēng)為永假公式稱(chēng)為永假公式( (矛盾式，不可滿(mǎn)矛盾式，不可滿(mǎn)足公式足公式),),如果在它的所有解釋之下都為如果在它的所有解釋之下都為“假假”。3 3）公式）公式G G1 1稱(chēng)為可滿(mǎn)足的，如果它不是永假稱(chēng)為可滿(mǎn)足的，如果它不是永假的（即存在解釋使公式取值的（即存在解釋使公式取值1 1）。）。2022-2-142022-2-14計(jì)算機(jī)科

24、學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院2222定義定義1-2.51-2.5：1 1）公式公式G G3 3稱(chēng)為永真公式稱(chēng)為永真公式( (重言式重言式) )，如果在，如果在它的所有解釋之下都為它的所有解釋之下都為“真真”。2 2）公式公式G G2 2稱(chēng)為稱(chēng)為永假公式永假公式( (矛盾式，不可滿(mǎn)矛盾式，不可滿(mǎn)足公式足公式),),如果在它的所有解釋之下都為如果在它的所有解釋之下都為“假假”。3 3）公式）公式G G1 1稱(chēng)為可滿(mǎn)足的，如果它不是永假稱(chēng)為可滿(mǎn)足的，如果它不是永假的（即存在解釋使公式取值的（即存在解釋使公式取值1 1）。）。2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程

25、學(xué)院2323定義定義1-2.51-2.5：1 1）公式公式G G3 3稱(chēng)為永真公式稱(chēng)為永真公式( (重言式重言式) )，如果在，如果在它的所有解釋之下都為它的所有解釋之下都為“真真”。2 2）公式公式G G2 2稱(chēng)為永假公式稱(chēng)為永假公式( (矛盾式，不可滿(mǎn)矛盾式，不可滿(mǎn)足公式足公式),),如果在它的所有解釋之下都為如果在它的所有解釋之下都為“假假”。3 3）公式公式G G1 1稱(chēng)為稱(chēng)為可滿(mǎn)足的可滿(mǎn)足的，如果它不是永假如果它不是永假的的（即存在解釋使公式取值（即存在解釋使公式取值1 1）。）。2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院2424n1 1）永真式永真

26、式G G的否定的否定G G是矛盾式；矛盾式是矛盾式；矛盾式G G的否定的否定G G是永真式。是永真式。 2 2）永真式一定是可滿(mǎn)足式永真式一定是可滿(mǎn)足式, ,可滿(mǎn)足式不一定是永真式?？蓾M(mǎn)足式不一定是永真式。3 3）兩個(gè)永真式的合取、析取、條件、雙條件均為永兩個(gè)永真式的合取、析取、條件、雙條件均為永真式。真式。n這樣由簡(jiǎn)單的重言式，可以推出無(wú)數(shù)個(gè)復(fù)雜的重言式。這樣由簡(jiǎn)單的重言式，可以推出無(wú)數(shù)個(gè)復(fù)雜的重言式。判定給定公式是否為永真式，永假式或可滿(mǎn)足式的問(wèn)判定給定公式是否為永真式，永假式或可滿(mǎn)足式的問(wèn)題，稱(chēng)為給定公式的判定問(wèn)題。題，稱(chēng)為給定公式的判定問(wèn)題。n在邏輯研究和計(jì)算機(jī)推理以及決策判斷時(shí)，人們

27、對(duì)于在邏輯研究和計(jì)算機(jī)推理以及決策判斷時(shí)，人們對(duì)于所研究的命題，最關(guān)心的莫過(guò)于所研究的命題，最關(guān)心的莫過(guò)于“真真”、“假假”問(wèn)題，問(wèn)題，所以永真公式在數(shù)理邏輯的研究中占有特殊且重要的所以永真公式在數(shù)理邏輯的研究中占有特殊且重要的地位。地位。 永真式的特點(diǎn)：永真式的特點(diǎn)：2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院2525n1 1）永真式）永真式G G的否定的否定G G是矛盾式；矛盾式是矛盾式；矛盾式G G的否定的否定G G是永真式。是永真式。 2 2）永真式一定是可滿(mǎn)足式）永真式一定是可滿(mǎn)足式, ,可滿(mǎn)足式不一定是永真式。可滿(mǎn)足式不一定是永真式。3 3）兩個(gè)永真

28、式的合取、析取、條件、雙條件均為永）兩個(gè)永真式的合取、析取、條件、雙條件均為永真式。真式。n這樣由簡(jiǎn)單的重言式，可以推出無(wú)數(shù)個(gè)復(fù)雜的重言式。這樣由簡(jiǎn)單的重言式，可以推出無(wú)數(shù)個(gè)復(fù)雜的重言式。判定給定公式是否為永真式、永假式或可滿(mǎn)足式的問(wèn)判定給定公式是否為永真式、永假式或可滿(mǎn)足式的問(wèn)題，稱(chēng)為給定公式的題，稱(chēng)為給定公式的判定問(wèn)題判定問(wèn)題。n在邏輯研究和計(jì)算機(jī)推理以及決策判斷時(shí)，人們對(duì)于在邏輯研究和計(jì)算機(jī)推理以及決策判斷時(shí)，人們對(duì)于所研究的命題，最關(guān)心的莫過(guò)于所研究的命題，最關(guān)心的莫過(guò)于“真真”、“假假”問(wèn)題，問(wèn)題，所以永真公式在數(shù)理邏輯的研究中占有特殊且重要的所以永真公式在數(shù)理邏輯的研究中占有特殊且

29、重要的地位。地位。 永真式的特點(diǎn)：永真式的特點(diǎn)：2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院2626n1 1）永真式）永真式G G的否定的否定G G是矛盾式；矛盾式是矛盾式；矛盾式G G的否定的否定G G是永真式。是永真式。 2 2）永真式一定是可滿(mǎn)足式）永真式一定是可滿(mǎn)足式, ,可滿(mǎn)足式不一定是永真式?？蓾M(mǎn)足式不一定是永真式。3 3）兩個(gè)永真式的合取、析取、條件、雙條件均為永）兩個(gè)永真式的合取、析取、條件、雙條件均為永真式。真式。n這樣由簡(jiǎn)單的重言式，可以推出無(wú)數(shù)個(gè)復(fù)雜的重言式。這樣由簡(jiǎn)單的重言式，可以推出無(wú)數(shù)個(gè)復(fù)雜的重言式。判定給定公式是否為永真式，永假式或

30、可滿(mǎn)足式的問(wèn)判定給定公式是否為永真式，永假式或可滿(mǎn)足式的問(wèn)題，稱(chēng)為給定公式的判定問(wèn)題。題，稱(chēng)為給定公式的判定問(wèn)題。n在邏輯研究和計(jì)算機(jī)推理以及決策判斷時(shí)，人們對(duì)于在邏輯研究和計(jì)算機(jī)推理以及決策判斷時(shí)，人們對(duì)于所研究的命題，最關(guān)心的莫過(guò)于所研究的命題，最關(guān)心的莫過(guò)于“真真”、“假假”問(wèn)題，問(wèn)題，所以永真公式在數(shù)理邏輯的研究中占有特殊且重要的所以永真公式在數(shù)理邏輯的研究中占有特殊且重要的地位。地位。 永真式的特點(diǎn)：永真式的特點(diǎn)：2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院2727 命題邏輯的命題邏輯的基本任務(wù)基本任務(wù)之一，就是找出那些之一，就是找出那些屬于永真式的命

31、題公式。屬于永真式的命題公式。（1 1）真值表法（簡(jiǎn)單、直觀）真值表法（簡(jiǎn)單、直觀）（2 2）置換（代換，代入）法則）置換（代換，代入）法則 如果公式如果公式A A中的一些變?cè)靡恍┕酱?，中的一些變?cè)?，用一些公式代入，而且每次出現(xiàn)同一變?cè)獣r(shí)，總用同一公式代入，而且每次出現(xiàn)同一變?cè)獣r(shí)，總用同一公式代入，就可從公式就可從公式A A得到公式得到公式B B，則稱(chēng)公式，則稱(chēng)公式B B為公式為公式A A的的置換（代入）實(shí)例（例式）。置換（代入）實(shí)例（例式）。置換定理：永真式的任何置換（代入）實(shí)例仍是置換定理：永真式的任何置換（代入）實(shí)例仍是一個(gè)永真式。一個(gè)永真式。永真式的判斷：永真式的判斷：2022

32、-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院2828 命題邏輯的基本任務(wù)之一，就是找出那些命題邏輯的基本任務(wù)之一，就是找出那些屬于永真式的命題公式。屬于永真式的命題公式。（1 1）真值表法）真值表法（簡(jiǎn)單、直觀）（簡(jiǎn)單、直觀）（2 2）置換（代換，代入）法則）置換（代換，代入）法則 如果公式如果公式A A中的一些變?cè)?，用一些公式代入，中的一些變?cè)?，用一些公式代入，而且每次出現(xiàn)同一變?cè)獣r(shí)，總用同一公式代入，而且每次出現(xiàn)同一變?cè)獣r(shí)，總用同一公式代入，就可從公式就可從公式A A得到公式得到公式B B，則稱(chēng)公式，則稱(chēng)公式B B為公式為公式A A的的置換（代入）實(shí)例（例式）。置換

33、（代入）實(shí)例（例式）。置換定理：永真式的任何置換（代入）實(shí)例仍是置換定理：永真式的任何置換（代入）實(shí)例仍是一個(gè)永真式。一個(gè)永真式。永真式的判斷：永真式的判斷：2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院2929 命題邏輯的基本任務(wù)之一，就是找出那些命題邏輯的基本任務(wù)之一，就是找出那些屬于永真式的命題公式。屬于永真式的命題公式。（1 1）真值表法（簡(jiǎn)單、直觀）真值表法（簡(jiǎn)單、直觀）（2 2）置換（代換，代入）法則）置換（代換，代入）法則 如果公式如果公式A A中的一些變?cè)靡恍┕酱?，中的一些變?cè)靡恍┕酱?，而且每次出現(xiàn)同一變?cè)獣r(shí)，總用同一公式代入，而且

34、每次出現(xiàn)同一變?cè)獣r(shí)，總用同一公式代入，就可從公式就可從公式A A得到公式得到公式B B，則稱(chēng)公式，則稱(chēng)公式B B為公式為公式A A的的置換置換（代入）（代入）實(shí)例實(shí)例（例式）。（例式）。置換定理：永真式的任何置換（代入）實(shí)例仍是置換定理：永真式的任何置換（代入）實(shí)例仍是一個(gè)永真式。一個(gè)永真式。永真式的判斷：永真式的判斷：2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院3030 命題邏輯的基本任務(wù)之一，就是找出那些命題邏輯的基本任務(wù)之一，就是找出那些屬于永真式的命題公式。屬于永真式的命題公式。（1 1）真值表法（簡(jiǎn)單、直觀）真值表法（簡(jiǎn)單、直觀）（2 2）置換（代換，

35、代入）法則置換（代換，代入）法則 如果公式如果公式A A中的一些變?cè)?，用一些公式代入，中的一些變?cè)?，用一些公式代入，而且每次出現(xiàn)同一變?cè)獣r(shí)，總用同一公式代入，而且每次出現(xiàn)同一變?cè)獣r(shí)，總用同一公式代入，就可從公式就可從公式A A得到公式得到公式B B，則稱(chēng)公式，則稱(chēng)公式B B為公式為公式A A的的置換（代入）實(shí)例（例式）。置換（代入）實(shí)例（例式）。n 置換定理置換定理：永真式的任何置換（代入）實(shí)例仍：永真式的任何置換（代入）實(shí)例仍是一個(gè)永真式。是一個(gè)永真式。永真式的判斷：永真式的判斷：2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院3131 例如：例如： PQPQ P

36、 P（永真式永真式） 對(duì)上式中的對(duì)上式中的P P，用（，用（RSRS）代入，）代入， 對(duì)對(duì)Q Q，用（，用（M M N N）代入后得到：）代入后得到： （RSRS）（M M N N）（RSRS） 該公式也是一個(gè)永真式該公式也是一個(gè)永真式（3 3）公式推演法（等價(jià)變換、替換（取代）規(guī)）公式推演法（等價(jià)變換、替換（取代）規(guī)（范）則）（范）則） 具體方法在下節(jié)中介紹具體方法在下節(jié)中介紹永真式的判斷：永真式的判斷：2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院3232 例如：例如： PQPQ P P（永真式）（永真式） 對(duì)上式中的對(duì)上式中的P P，用（，用（RSRS）代入

37、，）代入， 對(duì)對(duì)Q Q，用（，用（M M N N）代入后得到：）代入后得到： （RSRS）（M M N N）（RSRS） 該公式也是一個(gè)永真式該公式也是一個(gè)永真式（3 3）公式推演法）公式推演法（等價(jià)變換、替換（取代）規(guī)（等價(jià)變換、替換（取代）規(guī)（范）則）。（范）則）。 具體方法在下節(jié)中介紹具體方法在下節(jié)中介紹永真式的判斷：永真式的判斷：2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院3333n 定義定義1-3.11-3.1設(shè)設(shè)G G、H H是是公式，公式，如果在如果在任意解釋任意解釋下，下，G G與與H H的的真值相同，則稱(chēng)公式真值相同，則稱(chēng)公式G G、H H是是

38、等價(jià)等價(jià)的的 ，記記作作G GH H。n 定理定理1-3.21-3.2公式公式G G、H H等價(jià)的充分必要條件是公式等價(jià)的充分必要條件是公式 G GH H是永真公式。是永真公式。 此定理是從另一角度來(lái)看待等價(jià)性此定理是從另一角度來(lái)看待等價(jià)性n 等價(jià)式的性質(zhì):1 1）自反性：）自反性：A A A A2 2）對(duì)稱(chēng)性：若）對(duì)稱(chēng)性：若 A A B B，則，則 B B A A3 3）可傳遞性）可傳遞性: :若若 A A B B，B B C C，則，則A A C C1.3 1.3 命題公式的等價(jià)命題公式的等價(jià)2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院3434n 定義定義1

39、-3.11-3.1設(shè)設(shè)G G、H H是是公式，公式，如果在任意解釋下，如果在任意解釋下，G G與與H H的的真值相同，則稱(chēng)公式真值相同，則稱(chēng)公式G G、H H是等價(jià)的是等價(jià)的 ，記記作作G GH H。n 定理定理1-3.21-3.2公式公式G G、H H等價(jià)的等價(jià)的充分必要條件充分必要條件是公式是公式 G GH H是永真公式。是永真公式。 此定理是從另一角度來(lái)看待等價(jià)性此定理是從另一角度來(lái)看待等價(jià)性n 等價(jià)式的性質(zhì):1 1）自反性：）自反性：A A A A2 2）對(duì)稱(chēng)性：若）對(duì)稱(chēng)性：若 A A B B，則，則 B B A A3 3）可傳遞性）可傳遞性: :若若 A A B B，B B C C，

40、則，則A A C C1.3 1.3 命題公式的等價(jià)命題公式的等價(jià)2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院3535n 定理定理1-3.21-3.2公式公式G G、H H等價(jià)的充分必要條件是公式等價(jià)的充分必要條件是公式 G GH H是永真公式。是永真公式。 證明：證明： 如果如果G GH H，根據(jù)定義對(duì)任何解釋公式根據(jù)定義對(duì)任何解釋公式G G和和H H取相同的真值，因此取相同的真值，因此G GH H恒取真值恒取真值1 1，即，即G GH H是是永真式。永真式。 反過(guò)來(lái)，如果反過(guò)來(lái)，如果G GH H是永真式，根據(jù)聯(lián)結(jié)詞是永真式，根據(jù)聯(lián)結(jié)詞的定義，對(duì)任何解釋的定義，

41、對(duì)任何解釋G G和和H H必取相同的真值，必取相同的真值，從而從而G GH H成立。成立。 1.3 1.3 命題公式的等價(jià)命題公式的等價(jià)2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院3636n 定理定理1-3.21-3.2公式公式G G、H H等價(jià)的充分必要條件是公式等價(jià)的充分必要條件是公式 G GH H是永真公式。是永真公式。 證明：證明： 如果如果G GH H，根據(jù)定義對(duì)任何解釋公式根據(jù)定義對(duì)任何解釋公式G G和和H H取相同的真值，因此取相同的真值，因此G GH H恒取真值恒取真值1 1，即，即G GH H是是永真式。永真式。 反過(guò)來(lái)，如果反過(guò)來(lái)，如果G G

42、H H是永真式，根據(jù)聯(lián)結(jié)詞是永真式，根據(jù)聯(lián)結(jié)詞的定義，對(duì)任何解釋的定義，對(duì)任何解釋G G和和H H必取相同的真值，必取相同的真值，從而從而G GH H成立。成立。 1.3 1.3 命題公式的等價(jià)命題公式的等價(jià)2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院3737n 定理定理1-3.21-3.2公式公式G G、H H等價(jià)的充分必要條件是公式等價(jià)的充分必要條件是公式 G GH H是永真公式。是永真公式。 證明：證明： 如果如果G GH H，根據(jù)定義對(duì)任何解釋公式根據(jù)定義對(duì)任何解釋公式G G和和H H取相同的真值，因此取相同的真值，因此G GH H恒取真值恒取真值1 1

43、，即，即G GH H是是永真式。永真式。 反過(guò)來(lái)，如果反過(guò)來(lái)，如果G GH H是永真式，根據(jù)聯(lián)結(jié)詞是永真式，根據(jù)聯(lián)結(jié)詞的定義，對(duì)任何解釋的定義，對(duì)任何解釋G G和和H H必取相同的真值，必取相同的真值，從而從而G GH H成立。成立。 1.3 1.3 命題公式的等價(jià)命題公式的等價(jià) 這個(gè)定理建立了這個(gè)定理建立了和和之間轉(zhuǎn)換的關(guān)之間轉(zhuǎn)換的關(guān)系系。 然而，如果直接用這個(gè)定理來(lái)證明兩然而，如果直接用這個(gè)定理來(lái)證明兩個(gè)公式等價(jià)，常常會(huì)使得證明變得更加繁個(gè)公式等價(jià)，常常會(huì)使得證明變得更加繁瑣！瑣！2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院3838n 定義定義1-3.11-

44、3.1設(shè)設(shè)G G、H H是是公式，公式，如果在任意解釋下，如果在任意解釋下，G G與與H H的的真值相同，則稱(chēng)公式真值相同，則稱(chēng)公式G G、H H是等價(jià)的是等價(jià)的 ，記記作作G GH H。n 定理定理1-3.21-3.2公式公式G G、H H等價(jià)的充分必要條件是公式等價(jià)的充分必要條件是公式 G GH H是永真公式。是永真公式。 此定理是從另一角度來(lái)看待等價(jià)性此定理是從另一角度來(lái)看待等價(jià)性n 等價(jià)式的性質(zhì)等價(jià)式的性質(zhì): :1 1）自反性：）自反性：A A A A2 2）對(duì)稱(chēng)性：若）對(duì)稱(chēng)性：若 A A B B，則，則 B B A A3 3）可傳遞性）可傳遞性: :若若 A A B B，B B C

45、C，則，則A A C C1.3 1.3 命題公式的等價(jià)命題公式的等價(jià)2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院3939n 首先首先，雙條件詞，雙條件詞“”是一種邏輯聯(lián)結(jié)詞，公式是一種邏輯聯(lián)結(jié)詞，公式G GH H是命題公式，其中是命題公式，其中“”是一種邏輯運(yùn)算，是一種邏輯運(yùn)算，G GH H的結(jié)果仍是一個(gè)命題公式的結(jié)果仍是一個(gè)命題公式。n 而邏輯等價(jià)而邏輯等價(jià)“”則是描述了兩個(gè)公式則是描述了兩個(gè)公式G G與與H H之間之間的一種邏輯等價(jià)關(guān)系，的一種邏輯等價(jià)關(guān)系，G GH H表示表示“命題公式命題公式G G等等價(jià)價(jià)于命題公式于命題公式H H”，G GH H 的結(jié)果

46、不是命題公式。的結(jié)果不是命題公式。n 其次，如果要求用計(jì)算機(jī)來(lái)判斷命題公式其次，如果要求用計(jì)算機(jī)來(lái)判斷命題公式G G、H H是是否邏輯等價(jià)，即否邏輯等價(jià)，即G GH H那是辦不到的那是辦不到的，然而計(jì)算機(jī)然而計(jì)算機(jī)卻可卻可“計(jì)算計(jì)算”公式公式G GH H是否是永真公式。是否是永真公式。 “” ” 與與“”的區(qū)別的區(qū)別2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院4040n 首先，雙條件詞首先，雙條件詞“”是一種邏輯聯(lián)結(jié)詞，公式是一種邏輯聯(lián)結(jié)詞，公式G GH H是命題公式，其中是命題公式，其中“”是一種邏輯運(yùn)算，是一種邏輯運(yùn)算，G GH H的結(jié)果仍是一個(gè)命題公式的結(jié)

47、果仍是一個(gè)命題公式。n 而邏輯等價(jià)而邏輯等價(jià)“”則是描述了兩個(gè)公式則是描述了兩個(gè)公式G G與與H H之間之間的一種邏輯等價(jià)關(guān)系，的一種邏輯等價(jià)關(guān)系，G GH H表示表示“命題公式命題公式G G等等價(jià)價(jià)于命題公式于命題公式H H”，G GH H 的結(jié)果不是命題公式的結(jié)果不是命題公式。n 其次，如果要求用計(jì)算機(jī)來(lái)判斷命題公式其次，如果要求用計(jì)算機(jī)來(lái)判斷命題公式G G、H H是是否邏輯等價(jià)，即否邏輯等價(jià)，即G GH H那是辦不到的那是辦不到的，然而計(jì)算機(jī)然而計(jì)算機(jī)卻可卻可“計(jì)算計(jì)算”公式公式G GH H是否是永真公式。是否是永真公式。 “” ” 與與“”的區(qū)別的區(qū)別2022-2-142022-2-1

48、4計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院4141n 首先，雙條件詞首先，雙條件詞“”是一種邏輯聯(lián)結(jié)詞，公式是一種邏輯聯(lián)結(jié)詞，公式G GH H是命題公式，其中是命題公式，其中“”是一種邏輯運(yùn)算，是一種邏輯運(yùn)算，G GH H的結(jié)果仍是一個(gè)命題公式的結(jié)果仍是一個(gè)命題公式。n 而邏輯等價(jià)而邏輯等價(jià)“”則是描述了兩個(gè)公式則是描述了兩個(gè)公式G G與與H H之間之間的一種邏輯等價(jià)關(guān)系，的一種邏輯等價(jià)關(guān)系，G GH H表示表示“命題公式命題公式G G等等價(jià)價(jià)于命題公式于命題公式H H”，G GH H 的結(jié)果不是命題公式。的結(jié)果不是命題公式。n 其次其次，如果要求用計(jì)算機(jī)來(lái)判斷命題公式，如果要求用計(jì)算機(jī)來(lái)判斷

49、命題公式G G、H H是是否邏輯等價(jià)，即否邏輯等價(jià)，即G GH H那是辦不到的那是辦不到的，然而計(jì)算機(jī)然而計(jì)算機(jī)卻可卻可“計(jì)算計(jì)算”公式公式G GH H是否是永真公式。是否是永真公式。 “” ” 與與“”的區(qū)別：的區(qū)別：2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院4242基本等價(jià)式基本等價(jià)式命題定律命題定律 EquivalenceEquivalence： 設(shè)設(shè)G G，H H，S S是任何的公式，則：是任何的公式，則：1 1: :(G(G H)H)(GH)(HG)(GH)(HG)( (等價(jià)等價(jià)) ) 2 2：(GH) (GH) ( (GH) GH) ( (蘊(yùn)涵蘊(yùn)涵

50、) ) 3 3：GG GG G (G (冪等律冪等律) )4 4：GG GG G G5 5：GH GH HG (HG (交換律交換律) )6 6：GH GH HGHG7 7：G(HS) G(HS) (GH)S(GH)S ( (結(jié)合律結(jié)合律) )8 8: G(HS) : G(HS) (GH)S(GH)S9 9：G(GH) G(GH) G ( G (吸收律吸收律) ) 1010：G(GH) G(GH) G G 2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院4343基本等價(jià)式基本等價(jià)式命題定律命題定律 EquivalenceEquivalence： 設(shè)設(shè)G G，H H，

51、S S是任何的公式，則：是任何的公式，則：1 1:(G:(G H)H)(GH)(HG)(GH)(HG)( (等價(jià)等價(jià)) )2 2：(GH) (GH) ( (GH) GH) ( (蘊(yùn)涵蘊(yùn)涵) )3 3：GG GG G G ( (冪等律冪等律) )4 4：GG GG G G5 5：GH GH HG (HG (交換律交換律) )6 6：GH GH HGHG7 7：G(HS) G(HS) (GH)S(GH)S ( (結(jié)合律結(jié)合律) )8 8: G(HS) : G(HS) (GH)S(GH)S9 9：G(GH) G(GH) G ( G (吸收律吸收律) ) 1010：G(GH) G(GH) G G 20

52、22-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院4444基本等價(jià)式基本等價(jià)式命題定律命題定律 EquivalenceEquivalence： 設(shè)設(shè)G G，H H，S S是任何的公式，則：是任何的公式，則：1 1:(G:(G H)H)(GH)(HG)(GH)(HG)( (等價(jià)等價(jià)) )2 2：(GH) (GH) ( (GH) GH) ( (蘊(yùn)涵蘊(yùn)涵) )3 3：GG GG G (G (冪等律冪等律) )4 4：GG GG G G5 5：GH GH HG HG ( (交換律交換律) )6 6：GH GH HGHG7 7：G(HS) G(HS) (GH)S(GH)S ( (結(jié)

53、合律結(jié)合律) )8 8: G(HS) : G(HS) (GH)S(GH)S9 9：G(GH) G(GH) G ( G (吸收律吸收律) ) 1010：G(GH) G(GH) G G 2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院4545基本等價(jià)式基本等價(jià)式命題定律命題定律 EquivalenceEquivalence： 設(shè)設(shè)G G，H H，S S是任何的公式，則：是任何的公式，則：1 1:(G:(G H)H)(GH)(HG)(GH)(HG)( (等價(jià)等價(jià)) )2 2：(GH) (GH) ( (GH) GH) ( (蘊(yùn)涵蘊(yùn)涵) )3 3：GG GG G (G (冪等

54、律冪等律) )4 4：GG GG G G5 5：GH GH HG (HG (交換律交換律) )6 6：GH GH HGHG7 7：G(HS) G(HS) (GH)S(GH)S ( (結(jié)合律結(jié)合律) )8 8: G(HS) : G(HS) (GH)S(GH)S9 9：G(GH) G(GH) G ( G (吸收律吸收律) ) 1010：G(GH) G(GH) G G 2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院4646基本等價(jià)式基本等價(jià)式命題定律命題定律 EquivalenceEquivalence： 設(shè)設(shè)G G，H H，S S是任何的公式，則：是任何的公式，則：1

55、 1:(G:(G H)H)(GH)(HG)(GH)(HG)( (等價(jià)等價(jià)) )2 2：(GH) (GH) ( (GH) GH) ( (蘊(yùn)涵蘊(yùn)涵) )3 3：GG GG G (G (冪等律冪等律) )4 4：GG GG G G5 5：GH GH HG (HG (交換律交換律) )6 6：GH GH HGHG7 7：G(HS) G(HS) (GH)S(GH)S ( (結(jié)合律結(jié)合律) )8 8: G(HS) : G(HS) (GH)S(GH)S9 9：G(GH) G(GH) G G ( (吸收律吸收律) ) 1010：G(GH) G(GH) G G 2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工

56、程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院47471111：G(HS) G(HS) (GH)(GS)(GH)(GS) ( (分配律分配律) )1212：G(HS) G(HS) (GH)(GS)(GH)(GS)1313：GF GF G G( (同一律同一律) )1414：GTGT G G 1515：GTGT T T( (零律零律) )1616：GFGF F F 1717：GGG G T (T (矛盾律矛盾律) )1818：GGG G F F1919： ( (G) G) G G ( (雙重否定律雙重否定律) )2020：（：（GH)S GH)S G G（HSHS） （輸出律）（輸出律）2121：（：（G G H

57、H）( (GH)(GGH)(GH) (H) (排中律排中律) )2222：PQ PQ QQP P （逆反律）（逆反律）2323： (GH) (GH) GGH (De MorganH (De Morgan定律定律) )2424： (GH) (GH) GGH H?；镜葍r(jià)式（續(xù)）：基本等價(jià)式（續(xù)）：2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院48481111：G(HS) G(HS) (GH)(GS)(GH)(GS) ( (分配律分配律) )1212：G(HS) G(HS) (GH)(GS)(GH)(GS)1313：GF GF G G( (同一律同一律) )1414：

58、GTGT G G 1515：GTGT T T( (零律零律) )1616：GFGF F F 1717：GGG G T (T (矛盾律矛盾律) )1818：GGG G F F1919： ( (G) G) G G ( (雙重否定律雙重否定律) )2020：（：（GH)S GH)S G G（HSHS） （輸出律）（輸出律）2121：（：（G G H H）( (GH)(GGH)(GH) (H) (排中律排中律) )2222：PQ PQ QQP P （逆反律）（逆反律）2323： (GH) (GH) GGH (De MorganH (De Morgan定律定律) )2424： (GH) (GH) GGH

59、 H?；镜葍r(jià)式（續(xù)）：基本等價(jià)式（續(xù)）：2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院49491111：G(HS) G(HS) (GH)(GS)(GH)(GS) ( (分配律分配律) )1212：G(HS) G(HS) (GH)(GS)(GH)(GS)1313：GF GF G G( (同一律同一律) )1414：GTGT G G 1515：GTGT T T( (零律零律) )1616：GFGF F F 1717：GGG G T (T (矛盾律矛盾律) )1818：GGG G F F1919： ( (G) G) G G ( (雙重否定律雙重否定律) )2020：（

60、：（GH)S GH)S G G（HSHS） （輸出律）（輸出律）2121：（：（G G H H）( (GH)(GGH)(GH) (H) (排中律排中律) )2222：PQ PQ QQP P （逆反律）（逆反律）2323： (GH) (GH) GGH (De MorganH (De Morgan定律定律) )2424： (GH) (GH) GGH H?；镜葍r(jià)式（續(xù)）：基本等價(jià)式（續(xù)）：2022-2-142022-2-14計(jì)算機(jī)科學(xué)與工程學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院50501111：G(HS) G(HS) (GH)(GS)(GH)(GS) ( (分配律分配律) )1212：G(HS) G(HS) (