《離散數(shù)學(xué)》課件：2-命題邏輯

第二章

命題邏輯

第二章

命題邏輯2.1

命題以及邏輯聯(lián)結(jié)詞

2.2

命題公式

2.3

命題公式的等價關(guān)系和蘊涵關(guān)系

2.4

范式2.5

命題邏輯在二值邏輯器件

和語句邏輯中的應(yīng)用

2.1命題以及邏輯聯(lián)結(jié)詞

2.1.1命題

所謂命題是指一句有真假意義的話。例如：上海是中國最大的城市 今天是星期二 所有素數(shù)都是奇數(shù) 1+1=2命題用大寫英文字母P，Q，…，P1，P2，…，表示。

如果一個命題是真的，就說它的真值是1；

如果一個命題是假的，就說它的真值是0。

也用“1”代表一個抽象的真命題，用“0”代表一個抽象的假命題。

定義2.1.1設(shè)P是一個命題，命題“P是不對的”稱為P的否定，記以P，讀作非P。P是真的當(dāng)且僅當(dāng)P是假的。例如：

P：吉大是中國最大的大學(xué)。P：吉大不是中國最大的大學(xué)。定義2.1.2設(shè)P，Q是兩個命題，命題“P或者Q”稱為P，Q的析取，記以PQ，讀作P或Q。規(guī)定PQ是真的當(dāng)且僅當(dāng)P，Q中至少有一個是真的。例如：

P：今天下雨，Q：今天刮風(fēng)， PQ：今天下雨或者刮風(fēng)。定義2.1.3設(shè)P，Q是兩個命題，命題“P并且Q”稱為P，Q的合取，記以PQ，讀作P且Q。規(guī)定PQ是真的當(dāng)且僅當(dāng)P和Q都是真的。例如，P：22=5，Q：雪是黑的，

PQ：22=5并且雪是黑的。

定義2.1.4設(shè)P，Q是兩個命題，命題“如果P，則Q”稱為P蘊涵Q，記以PQ。規(guī)定，PQ是假的當(dāng)且僅當(dāng)P是真的而Q是假的。例如，P：f(x)是可微的，Q：f(x)是連續(xù)的，

PQ：若f(x)是可微的，則f(x)是連續(xù)的。由定義知，如果P是假命題，則不管Q是什么命題，命題“如果P，則Q”在命題邏輯中都被認為是真命題。例如，P：22=5，Q：雪是黑的，

于是，命題“如果22=5，則雪是黑的”是真命題。定義2.1.5設(shè)P，Q是兩個命題，命題“P當(dāng)且僅當(dāng)Q”稱為P等價Q，記以PQ。規(guī)定，PQ是真的當(dāng)且僅當(dāng)P，Q或者都是真的，或者都是假的。例如， P：a2+b2=a2，

Q：b=0，

PQ：a2+b2=a2當(dāng)且僅當(dāng)b=0。例2.1.1

如果你走路時看書，那么你會成為近視眼。令P：你走路；Q：你看書；R：你會成為近視眼。于是，上述語句可表示為（PQ）R。

例2.1.2

除非他以書面或口頭的方式正式通知我，否則我不參加明天的會議。

令P：他書面通知我；Q：他口頭通知我；R：我參加明天的會議。

于是，上述語句可表示為(PQ)R。

例2.1.3

設(shè)P，Q，R的意義如下：

P：蘋果是甜的；Q：蘋果是紅的；

R：我買蘋果。

試用日常語言復(fù)述下述復(fù)合命題：

(1)(PQ)R (2)(PQ)R解：(1)如果蘋果甜且紅，那么我買。(2)我沒買蘋果，因為蘋果不甜也不紅。2.2命題公式

§2.2.1公式我們用大寫的英文字母P，Q，R，…等代表一個抽象的命題，或稱為命題符號。定義2.2.1命題符號稱為原子。例如，Q，S，…等都是原子。定義2.2.2

命題公式命題邏輯中的公式，是如下定義的一個符號串： (1) 原子是公式；

(2) 0、1是公式；

(3) 若G，H是公式，則(G)，(GH)， (GH)，(GH)，(GH)是公式； (4) 所有公式都是有限次使用(1)，(2)，(3)

得到的符號串。規(guī)定：公式(G)的括號可以省略，寫成G。整個公式的最外層括號可以省略。五種邏輯聯(lián)結(jié)詞的優(yōu)先級按如下次序遞增： ，，，，例如，我們寫符號串

PQRQSR

就意味著是如下公式： ((P(QR))(Q((S)R)))§2.2.2解釋

定義2.2.3設(shè)G是命題公式，A1,…,An是出現(xiàn)在G中的所有原子。指定A1,…,An的一組真值，則這組真值稱為G的一個解釋。設(shè)G是公式，I是G的一個解釋，顯然，G在I下有真值，通常記為TI(G)。

例

G=PQ，設(shè)解釋I，I’如下：

I： I’：

則TI(G)=1，TI’(G)=0PQ

11

PQ

10

定義2.2.4公式G在其所有可能的解釋下所取真值的表，稱為G的真值表。顯然，有n個不同原子的公式，共有2n個解釋。

例：G=(PQ)R，其真值表如下：

PQRG00010011010101111001101111001111

若公式G中出現(xiàn)的所有原子為A1，…，An，有時我們用{m1，…，mn}表示G的一個解釋I，其中

例如，上例公式G的真值表中第二個解釋就可以記為{P，Q，R}定義2.2.5公式G稱為恒真的(或有效的)，如果G在它的所有解釋下都是真的；

公式G稱為恒假的(或不可滿足的)，如果G在它的所有解釋下都是假的；公式G稱為可滿足的，如果它不是恒假的?？紤]G1=

(P→Q)→P，G2=(P→Q)P，G3=PP。從真值表可以看出G1對所有解釋具有“真”值，公式G3對所有解釋具有“假”值，而G2具有“真”和“假”值。PQG1PQG2PG30010000001101110101100111111G是恒真的當(dāng)且僅當(dāng)G是恒假的。G是可滿足的當(dāng)且僅當(dāng)至少有一個解釋I，使G在I下為真。若G是恒真的，則G是可滿足的；反之不對。如果公式G在解釋I下是真的，則稱I滿足G；

如果G在解釋I下是假的，則稱I弄假G。在邏輯研究和計算機推理以及決策判斷中，人們對于所研究的命題，最關(guān)心的莫過于“真”、“假”問題，所以恒真公式在數(shù)理邏輯研究中占有特殊且重要的地位。判定問題能否給出一個可行方法，對任意的公式，判定其是否是恒真公式。因為一個命題公式的解釋的數(shù)目是有窮的，所以命題邏輯的判定問題是可解的(可判定的，可計算的)，亦即，命題公式的恒真，恒假性是可判定的。§2.3 命題公式的等價關(guān)系

和蘊涵關(guān)系

§2.3.1公式的等價定義2.3.1公式G，H說是等價的，記以G=H，如果G，H在其任意解釋I下，其真值相同。顯然，公式G，H等價的充要條件是公式GH是恒真的?；镜葍r式1) (GH)=(GH)(HG)；2) (GH)=(GH)；3) GG=G，GG=G； (等冪律)4)

GH=HG，GH=HG； (交換律)5)

G(HS)=(GH)S，

G(HS)=(GH)S； (結(jié)合律)基本等價式6) G(GH)=G，G(GH)=G； (吸收律)7)

G(HS)=(GH)(GS)，

G(HS)=(GH)(GS)； (分配律)8)

G0=G，G1=G； (同一律)9)

G0=0，G1=1； (零一律)10)

(GH)=GH，

(GH)=GH。 (摩根律)從上述眾多的等價公式可以看出，每一個命題公式的表達式是不唯一的，這種不唯一性使得人們在進行邏輯推理時可以有千變?nèi)f化的方式，即對于一個公式G，可根據(jù)如上等價公式，在等價的意義下，對其進行推演，從而得到G的各種等價形式。經(jīng)驗表明，自覺的使用邏輯規(guī)律和不自覺的使用是完全不一樣的，熟悉這些規(guī)律可以使我們的思維正確而敏銳。定義2.3.2完備集設(shè)Q是邏輯運算符號集合，若所有邏輯運算都能由Q中元素表示出來，而Q的任意真子集無此性質(zhì)，則稱Q是一個完備集?？梢宰C明，{，}，{，}都是完備集。

定義2.3.3與非式設(shè)P，Q是兩個命題，命題“P與Q的否定”稱為P與Q的與非式，記作PQ。“”稱作與非聯(lián)結(jié)詞。PQ為真當(dāng)且僅當(dāng)P，Q不同時為真。由定義可知：

PQ=(PQ)。

定義2.3.4或非式設(shè)P，Q是兩個命題，命題“P或Q的否定”稱為P與Q的或非式，記作PQ，

稱作或非聯(lián)結(jié)詞。PQ為真當(dāng)且僅當(dāng)P，Q同時為假。由定義可知：

PQ=(PQ){}是完備集下面我們來說明{}是完備集。

P=PPPQ=(PP)(QQ)PQ=(PQ)(PQ)讀者可以自己證明{}也是完備集。

§2.3.2公式的蘊涵

邏輯的一個重要功能是研究推理。固然，依靠等價關(guān)系可以進行推理。但是，進行推理時，不必一定要依靠等價關(guān)系，只需是蘊涵關(guān)系就可以了。例如，若三角形等腰，則兩底角相等，

這個三角形等腰，

所以，這個三角形兩底角相等。又如，若行列式兩行成比例，則行列式值為0，

這個行列式兩行成比例，

所以，這個行列式值為0。上面兩個例子的推理關(guān)系涵義不同，但依據(jù)的推理規(guī)則相同，推理形式為：

若P則Q，P，所以Q。

推理的正確性與命題P，Q涵義無關(guān)，只決定于邏輯形式，命題邏輯中用公式表示命題，命題間演繹推理關(guān)系，反映為公式間邏輯蘊涵關(guān)系。定義2.3.5蘊涵設(shè)G，H是兩個公式。稱H是G的邏輯結(jié)果(或稱G蘊涵H)，當(dāng)且僅當(dāng)對G，H的任意解釋I，如果I滿足G，則I也滿足H，記作GH。注意：符號“”和“=”一樣，它們都不是邏輯聯(lián)結(jié)詞，因此，G=H，GH也都不是公式。

是一種部分序關(guān)系。公式G蘊涵公式H的充要條件是：公式GH是恒真的。例如：(PQ)P，(PQ)Q定義2.3.6設(shè)G1,…,Gn，H是公式。稱H是G1,…,Gn的邏輯結(jié)果(或稱G1,…,Gn共同蘊涵H)，當(dāng)且僅當(dāng)公式G1…

Gn蘊涵H。顯然，公式H是G1,…,Gn的邏輯結(jié)果的充要條件是：公式((G1…

Gn)H)是恒真的。例如，P，PQ共同蘊涵Q。

定理2.3.1如果H1，…，Hm，P共同蘊涵公式Q，則H1，…，Hm共同蘊涵公式PQ。例如，因為公式PQ，QR，P共同蘊涵R，所以PQ，QR共同蘊涵PR。

定理2.3.1證明：因為(H1…HmP)Q，所以公式(H1…HmP)Q是恒真的。利用下面的基本等價公式：

P1(P2P3)=(P1P2)P3于是，(H1…HmP)Q=(H1…Hm)(PQ)。故(H1…Hm)(PQ)是恒真的。所以H1，…，Hm共同蘊涵PQ。§2.3.3演繹

定義2.3.7設(shè)S是一個命題公式的集合(前提集合)。從S推出公式G的一個演繹是公式的一個有限序列：

G1,G2,…,Gk

其中，Gi或者屬于S，或者是某些

Gj

(j<i)的邏輯結(jié)果。

并且

Gk就是G。我們稱公式G為此演繹的邏輯結(jié)果，或稱從S演繹出G。

有時也記為SG。

例設(shè)S={PQ，QR，PM，M}則下面的公式序列:

M，PM，P，PQ，Q，QR，R

就是從S推出R的一個演繹。引理設(shè)G，H1，H2是公式。如果G蘊涵H1，G蘊涵H2，則G蘊涵H1H2。證明：任取G，H1，H2的一個解釋I。

若I滿足G，由假設(shè)知，I滿足

H1，I滿足H2，故I滿足

H1H2。由I的任意性，所以G(H1H2)。

定理2.3.2設(shè)S是公式集合，G是一個公式。于是，從S演繹出G的充要條件是G是S的邏輯結(jié)果。證明：必要性，設(shè)從S演繹出G，令

G1，…，Gk

是這個演繹。對任意Gi(i=1，…，k)，往證Gi

是S的邏輯結(jié)果。對i用歸納法:(1)當(dāng)i=1時，因G1S，顯然,G1

…G1

是恒真公式，故SG1

，即

G1

是S的邏輯結(jié)果。

(2)設(shè)i<n時，命題成立。(3)當(dāng)i=n時，若GnS，則S

Gn，歸納法完成。若Gn是某些Gj(j<n)的邏輯結(jié)果，不妨設(shè)

(Gj1

…Gjh)Gn(1)

其中j1，…，jh都小于n。

由歸納假設(shè)知，SGjm，m=1，…，h。由引理知：S(Gji

…Gjh)(2)

根據(jù)(1)，(2)式及蘊涵關(guān)系的傳遞性，得

S

Gn

即Gn是S的邏輯結(jié)果，歸納完成。

充分性，若G是S的邏輯結(jié)果，由演繹的定義知，G是如下演繹：

G1，…，Gk，G的邏輯結(jié)果，其中

G1

，…，Gk

是S中所有公式。

定理2.3.3設(shè)S是前提公式集合，G，H是兩個公式。如果從S∪{G}可演繹出H，則從S可演繹出GH。證明：因為從S∪{G}可演繹出H，由定理2.3.2知，H是S∪{G}的邏輯結(jié)果。亦即

(G1

…Gk

G)H

其中G1，…，Gk

是S中所有公式。

由定理2.3.1知：

(G1

…Gk)(GH)

即GH是S的邏輯結(jié)果，再由定理2.3.2知，從S可演繹出GH。

基本蘊涵式

PQPPQQPPQQPQP(PQ)Q(PQ)(PQ)P基本蘊涵式

(PQ)QP，QPQP，PQQP，PQQQ，PQPPQ，QRPRPQ，PR，QRR§2.3.4公式蘊涵的證明方法真值表法；證GH是恒真公式；利用一些基本等價式及蘊涵式進行推導(dǎo)；任取解釋I，若I滿足G，往證I滿足H；反證法，設(shè)結(jié)論假，往證前提假?！?.3.4公式蘊涵的證明方法若給出前提集合S={G1，…，Gk}，公式G，證明SG有如下兩種方法：

1.G1

…Gk

G

2.形式演繹法形式演繹法根據(jù)一些基本等價式和基本蘊涵式，從S出發(fā)，演繹出G，在演繹過程中遵循以下三條規(guī)則：規(guī)則1.可隨便使用前提。(根據(jù)演繹定義)規(guī)則2.可隨便使用前面演繹出的某些公式的邏輯結(jié)果。(根據(jù)演繹的定義)規(guī)則3.

如果需要演繹出的公式是PQ的形式，則我們可將P做為附加前提使用，而力圖去演繹出Q。(根據(jù)定理2.3.3)。

例2.3.1證明{(PQ)，(PR)，(QS)}SR

PQ 規(guī)則1

PQ 規(guī)則2，根據(jù)1 QS 規(guī)則1 PS 規(guī)則2，根據(jù)2，3 SP 規(guī)則2，根據(jù)4 PR 規(guī)則1 SR 規(guī)則2，根據(jù)5，6 SR 規(guī)則2，根據(jù)7。

例2.3.2證明{P(QS)，RP，Q}RS RP 規(guī)則1 R 規(guī)則3 P 規(guī)則2，根據(jù)1，2 P(QS) 規(guī)則1 QS 規(guī)則2，根據(jù)3，4 Q 規(guī)則1 S 規(guī)則2，根據(jù)5，6 RS 規(guī)則3，根據(jù)2，7例2.3.3若廠方拒絕增加工資，則罷工不會停止，除非罷工超過一年并且工廠經(jīng)理辭職。問：如果廠方拒絕增加工資，而罷工又剛剛開始，罷工是否能停止?令 P：廠方拒絕增加工資；

Q：罷工停止；

R：工廠經(jīng)理辭職；

S：

罷工超過一年。

于是， G1：(P(RS))Q G2：P G3：S H：Q我們要證明：H是{G1，G2，G3}的邏輯結(jié)果。1.

S 規(guī)則12.

SR 規(guī)則2，根據(jù)13.

(RS) 規(guī)則2，根據(jù)24.

P 規(guī)則15.

P(RS) 規(guī)則2，根據(jù)3，46.(P(RS))Q 規(guī)則17.

Q 規(guī)則2，根據(jù)5，6亦即，罷工不會停止?！?.4范式

§2.4.1析取范式和合取范式定義2.4.1原子或原子的否定稱為文字。

例如，P，P是文字。定義2.4.2

有限個文字的析取式稱為一個子句；

有限個文字的合取式稱為一個短語。特別，一個文字既可稱為是一個子句，也可稱為是一個短語。例如，P，PQ，PQ是子句，P，PQ，PQ是短語。

定義2.4.3析取范式、合取范式有限個短語的析取式稱為析取范式；

有限個子句的合取式稱為合取范式。特別，一個文字既可稱為是一個合取范式，也可稱為是一個析取范式。一個子句，一個短語既可看做是合取范式，也可看做是析取范式。例如，P，PQ，PQ，(PQ)(PQ)是析取范式。

P，PQ，PQ，(PQ)(PR)是合取范式。

定理2.4.1對于任意命題公式，都存在等價于它的析取范式和合取范式。

證明：對于公式G，通過如下算法即可得出等價于G的范式：步1.使用基本等價式，將G中的邏輯聯(lián)結(jié)詞， 刪除。步2.使用(H)=H和摩根律，將G中所有的否 定號都放在原子之前。

步3.

反復(fù)使用分配律，即可得到等價于G的范 式。

例：

G =(P(QR))S

=(P(QR))S =P(QR)S =P(QR)S……………. (析取范式) =P(QR)(S(QQ)) =P(QR)(SQ)(SQ)(析取范式) =(PS)(QR) =(PSQ)(PSR)……

(合取范式)

§2.4.2主析取范式和主合取范式

定義2.4.4設(shè)P1,…,Pn是n個不同原子，一個短語（子句）如果恰好包含所有這n個原子或其否定，且其排列順序與P1,…,Pn的順序一致，則稱此短語（子句）為關(guān)于P1,…,Pn的一個極?。ù螅╉?。顯然，共有2n個不同的極?。ù螅╉?。

例如，對原子P，Q，R而言，PQR，PQR，PQR都是極小項，但是，P，PQ不是極小項，而PQ對原子P，Q而言是極小項。

顯然，對于n個原子P1,…,Pn而言，其不同的解釋共有2n個，對于P1,…,Pn的任一個極小項m，2n個解釋中，有且只有一個解釋使m取1值。例如，對P，Q，R而言，PQR是極小項，解釋{P，Q，R}使該極小項取1值，其他解釋都使該極小項取0值。如果將真值1，0看做是數(shù)，則每一個解釋對應(yīng)一個n位二進制數(shù)。假設(shè)使極小項m取1值的解釋對應(yīng)的二進制數(shù)為i，今后將m記為mi。

例:對P，Q，R而言，PQR是極小項，解釋(0，1，0)使該極小項取1值，解釋(0，1，0)對應(yīng)的二進制數(shù)是2，于是PQR記為m2。

對P，Q，R而言，8個極小項與其對應(yīng)的解釋如下：

極小項

解釋

記法

PQR000m0

PQR001m1

PQR010m2

PQR011m3

PQR100m4

PQR101m5

PQR110m6

PQR111m7

一般地，對P1,…,Pn而言，2n個極小項為定義2.4.5主析取范式設(shè)命題公式G中所有不同原子為P1,…,Pn，如果G的某個析取范式G’中的每一個短語，都是關(guān)于P1,…,Pn的一個極小項，則稱G’為G的主析取范式。

恒假公式的主析取范式用0表示。

定理2.4.2對于命題公式G，都存在等價于它的主析取范式。

證明：由定理2.4.1知，存在析取范式G’，使得G=G’。設(shè)G中所有不同原子為P1,…,Pn，對于G’中每一個短語Gi’進行檢查，如果Gi’不是關(guān)于P1,…,Pn的極小項，則Gi’中必然缺少原子Pj1,…,Pjk。因為：于是將G’中非極小項Gi’化成了一些極小項之析取。對G’中其他非極小項也做如上處理，最后得等價于G的主析取范式G*。

例求G=(RP)(Q(PR))主析取范式。

解：

G =(RP)(Q(PR)) =(RP)(QP)(QR) =(PR)(QP)(QR) =((PR)(QQ))((QP)(RR))( (QR)(PP)) =(PQR)(PQR)(PQR)(P QR)求G=(PQ)(PR)(QR)主析取范式。

PQRG0

00000110

10001111000101011011111G的主析取范式為(PQR)(PQR)(PQR)(PQR)例于是，G的主析取范式為(PQR)(PQR)(PQR)(PQR)證明真值表法的正確性對于公式G，用這種方法寫出主析取范式G’，若解釋I使G取1值，而在I下取1值的唯一極小項寫在G’中，故G’也取1值，若I使G取0值，而在I下取1的唯一極小項不在G’中且I弄假其它所有極小項，故G’取0值，所以G’是與G等價的主析取范式。

定理2.4.3設(shè)公式G，H是關(guān)于原子P1,…,Pn的兩個主析取范式。如果G，H不完全相同，則G，H不等價。證明：因為G，H不完全相同，所以或者G中有一個極小項不在H中；

或者反之。不妨設(shè)極小項mi

在G中而不在H中。

于是根據(jù)極小項的性質(zhì)，二進制數(shù)i所對應(yīng)的關(guān)于P1,…,Pn的解釋Ii使mi取1值，從而使公式G取1值。

Ii使所有不是mi的極小項取0值，從而使公式H取0值。

故G，H不等價。

定理2.4.4對于任意公式G，存在唯一一個與G等價的主析取范式。

§2.4.3恒真恒假性的判定

引理短語是恒假的當(dāng)且僅當(dāng)至少有一個原子及其否定(也稱互補對)同時在此短語中出現(xiàn)。證明：充分性，若有一個原子P及其否定P同時出現(xiàn)在短語中，則此短語有形式： PP…顯然，不管是什么解釋I，PP在I下取0值，于是此短語在I下取0值，故此短語恒假。必要性，若短語恒假，而任意原子及其否定均不同時在短語中出現(xiàn)。那么，取這樣的解釋I：指定帶有否定號的原子取0值，不帶否定號的原子取1值，顯然，此短語在這個解釋I下取1值，與此短語恒假矛盾。定理2.4.5命題公式G是恒假的當(dāng)且僅當(dāng)在等價于它的析取范式中，每個短語均至少包含一個原子及其否定。證明：設(shè)G的析取范式如下：

G=G1…Gn

其中Gi是短語，i=1，…，n。

顯然，公式G恒假的充要條件是每個Gi恒假。再根據(jù)引理，此定理結(jié)論顯然成立。例2.4.1

判斷公式G=(PQ)(QR)(RP)是否恒假?解：

G=(PQ)(QR)(RP)

=(PQ)(QR)(RP)

=((PQ)(QQ)(PR)(QR))(RP)

=(PQR)(QQR)(