1、第一章 命題邏輯 11 命題及其表示法 1.什么是命題 命題：能判斷真假的陳述句。 命題的值叫它的真值。 真值：“真”：表示判斷正確。記作True，用T表示。 “假”：表示判斷錯(cuò)誤。記作False，用F表示。,1,例1 判斷下列句子中哪些是命題？ （1）2是素?cái)?shù)。 （2）雪是黑色的。 （3）2+3=5 （4）明年10月1日是晴天。 （5）3能被2整除。 （6）這朵花真好看呀！ （7）明天下午有會(huì)嗎？ （8）請(qǐng)關(guān)上門(mén)！ （9）X+Y5 （10）地球外的星球上也有人。 （11）我正在說(shuō)謊。,2,2命題的符號(hào)化表示 命題的符號(hào)化就是用符號(hào)表示命題。 簡(jiǎn)單命題（或原子命題）：簡(jiǎn)單陳述句表示的命題。用P

2、，Q，R,Pi,Qi,Ri,表示。 例 P:2是偶數(shù)。 Q:雪是黑色的。 命題常量（或命題常元）：簡(jiǎn)單命題。 命題變項(xiàng)（或命題變?cè)赫嬷悼梢宰兓暮?jiǎn)單陳述句。不是命題。 例：x+y5,3,命題變項(xiàng)也用P，Q，R, Pi,Qi,Ri,表示。 復(fù)合命題：由簡(jiǎn)單命題用聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。,4,例2 將下列命題符號(hào)化。 （1）3 不是偶數(shù)。 （2）2 是素?cái)?shù)和偶數(shù)。 （3）林芳學(xué)過(guò)英語(yǔ)或日語(yǔ)。 （4）如果角A和角B是對(duì)頂角，則角A 等于角B。 解：（1）設(shè)P：3是偶數(shù)。 P（：表示并非） （2）設(shè)P：2 是素?cái)?shù)；Q：2是偶數(shù)。 PQ ( :表示和) （3）設(shè)P：林芳學(xué)過(guò)英語(yǔ)；Q：林芳學(xué)過(guò)日語(yǔ)。 P

3、Q(:表示或) （4）設(shè)P：角A和角B是對(duì)頂角；Q：角A 等于角B。 PQ（個(gè)表示如果則）,5,12.聯(lián)結(jié)詞 定義12.1 設(shè)P為任一命題，P的否定是一個(gè)新的命題，稱(chēng)為P的否定式，記作P。為否定聯(lián)結(jié)詞。,例 p：3是偶數(shù)。 p：3不是偶數(shù)。,6,定義12.2 設(shè)P、Q為兩命題，復(fù)合命題“P并且Q”（或“P和Q”）稱(chēng)為 P與Q的合取式，記作PQ，為合取聯(lián)結(jié)詞。 表示自然語(yǔ)言中的“既又”， “不僅而且”， “雖然但是”,7,例3將下列命題符號(hào)化。 （1）李平既聰明又用功。 （2）李平雖然聰明，但不用功。 （3）李平不但聰明，而且用功。 （3）李平不是不聰明，而是不用功。 解：設(shè)P：李平聰明；Q：李

4、平用功。 （1）PQ （2）PQ （3）PQ （4）（P）Q 注意：不是見(jiàn)到“和” 、“與”就用 。 例：“李文和李武是兄弟”，“王芳和陳蘭是好朋友”是簡(jiǎn)單命題。,8,定義12.3 設(shè)P、Q為兩命題，復(fù)合命題“P或Q”稱(chēng)為 P與Q的析取式，記作PQ，為析取聯(lián)結(jié)詞。,9,析取式PQ表示的是一種相容性或，即允許P和Q同時(shí)為真。 例：“王燕學(xué)過(guò)英語(yǔ)或日語(yǔ)” PQ 自然語(yǔ)言中的“或”具有二義性，有時(shí)表示不相容的或。 例：“派小王或小李中的一人去開(kāi)會(huì)” 。為排斥性的或。 P：派小王去開(kāi)會(huì)；Q：派小李去開(kāi)會(huì)。 （PQ）（PQ） ， （PQ）（PQ）,10,定義12.4 設(shè)P、Q為兩命題，復(fù)合命題“如果P，

5、則Q”稱(chēng)作 P與Q的蘊(yùn)涵式，記作PQ，為蘊(yùn)涵聯(lián)結(jié)詞。,11,在PQ中，Q是P的必要條件，P是Q的充分條件。表示自然語(yǔ)言 “只要P就Q” ， “P僅當(dāng)Q”， “只有Q，才P” 注意：1.在自然語(yǔ)言中，“如果P，則Q”中的P與Q往往有某 種內(nèi)在的聯(lián)系，但在數(shù)理邏輯中，PQ中的P與Q不一定有內(nèi)在的聯(lián)系。 2.在數(shù)學(xué)中，“如果P，則Q”表示P為真，Q為真的邏輯關(guān)系，但在數(shù)理邏輯中，當(dāng)P為假時(shí)PQ為真。,12,例4將下列命題符號(hào)化。 (1)只要不下雨，我就騎自行車(chē)上班。 (2)只有不下雨，我才騎自行車(chē)上班。 (3)若 2+24，則太陽(yáng)從東方升起。 (3)若 2+24，則太陽(yáng)從東方升起。 (4)若 2+2

6、4，則太陽(yáng)從西方升起。 (5)若 2+24，則太陽(yáng)從西方升起。 解：在（1）、（2）中，設(shè)P：天下雨；Q：我騎自行車(chē)上班。 （1）PQ（2）Q P 在（3）（6）中，設(shè)P： 2+24；Q：太陽(yáng)從東方升起；R: 太陽(yáng)從西方升起。 （1）PQ， 真值為T(mén) （2）PQ， 真值為T(mén) （3）PR ， 真值為F （4）PR 真值為T(mén),13,定義1-2.5 設(shè)P、Q為兩命題，復(fù)合命題“P當(dāng)且僅當(dāng) Q”稱(chēng)作 P與Q的等價(jià)式，記作P Q， 為等價(jià)聯(lián)結(jié)詞。 PQ表示P與Q互為充分必要條件。,14,例5將下列命題符號(hào)化。 （1）2+24，當(dāng)且僅當(dāng)3是奇數(shù)。 （2）2+24，當(dāng)且僅當(dāng)3不是奇數(shù)。 （3）2+24，當(dāng)且

7、僅當(dāng)3是奇數(shù)。 （4）2+24，當(dāng)且僅當(dāng)3不是奇數(shù)。 （5）兩圓的面積相等，當(dāng)且僅當(dāng)它們的半徑相同。 （6）兩角相等當(dāng)且僅當(dāng)它們是對(duì)頂角。 解：（1）（4）設(shè)P：2+24；Q：3是奇數(shù)。 （1）PQ 真命題 （2）PQ 假命題 （3）PQ假命題 （4）PQ真命題 （5）設(shè)P：兩圓的面積相等；Q：兩圓的面積相同。 PQ真命題 （6）設(shè)P：兩角相等；Q：它們是對(duì)頂角。 PQ假命題,15,4.5種聯(lián)結(jié)詞的優(yōu)先級(jí)順序：，,16,1-3命題公式與翻譯 1.命題公式 命題公式：由命題常量、命題變?cè)?、?lián)結(jié)詞、括號(hào) 等組成的符號(hào)串。 命題公式中的命題變?cè)Q(chēng)作命題公式的分量。,17,定義13.1 （1）單個(gè)命題

8、常量或命題變 元,Q,R,Pi,Qi,Ri, ，F(xiàn)，T是合式公式。 （2）如果A是合式公式，則（A）也是合式公式。 （3）如果A、B是合式公式，則（AB）、（A B）、（AB）、（AB）也是合式公式。 （4）只有有限次地應(yīng)用（1）（3）組成的符號(hào)串才是合式公式。 例：P, P, (P), (0P),P(PQ), (PQ) R) (R)是公式； PQR, (P), PQ)不是公式。,18,2.翻譯 翻譯就是把自然語(yǔ)言中的有些句子符號(hào)化。 復(fù)合命題符號(hào)化的基本步驟： （1）分析出各簡(jiǎn)單命題，將它們符號(hào)化。 （2）使用合適的聯(lián)結(jié)詞，把簡(jiǎn)單命題逐個(gè)聯(lián)結(jié)起來(lái)，組成復(fù)合命題的符號(hào)化表示。,19,例 將下列

9、命題符號(hào)化。 （1）小王是游泳冠軍或是百米冠軍。PQ （2）小王現(xiàn)在在宿舍或在圖書(shū)館。PQ （排斥性或，不可能同時(shí)為真） (3)選小王或小李中的一人當(dāng)班長(zhǎng)。 （P Q） （PQ）或 （PQ） （排斥性或，可能同時(shí)為真）,20,(4)如果我上街，我就去書(shū)店看看，除非我很累。 R(PQ) 或 （RP）Q （除非：如果不） (5)王一樂(lè)是計(jì)算機(jī)系的學(xué)生，他生于1968年或1969年，他是三好學(xué)生。P（Q R）S （6）我們要做到身體好、學(xué)習(xí)好、工作好，為祖國(guó)四化建設(shè)而奮斗。 A：我們要做到身體好 B：我們要做到學(xué)習(xí)好 C：我們要做到工作好 P：我們要為祖國(guó)四化建設(shè)面奮斗。 命題符號(hào)化形式為：（ABC

10、）P,21,14真值表與等價(jià)公式 1.真值表 定義14.1含n個(gè)（n1）個(gè)命題變?cè)ǚ至浚┑拿}公式，共有2n組真值指派。將命題公式A在所有真值指派之下取值的情況列成表，稱(chēng)為A的真值表。 構(gòu)造真值表的步驟： (1)找出命題公式中所含的所有命題變?cè)狿1,P2,Pn。列出所有可能的真值指派。 (2)對(duì)應(yīng)每種真值指派，計(jì)算命題公式的各層次的值，直到最后計(jì)算出命題公式的值。,22,例1 構(gòu)造求PQ的真值表。,23,例2 給出（PQ）P的真值表。,24,例3 給出（PQ）（PQ）的真值表。,25,例4 給出（PQ）（PQ）的真值表。,由以上例子可以看出有一類(lèi)命題公式不論各命題變?cè)骱畏N批派，其值永為真（

11、假），我們把這類(lèi)公式記為T(mén)（F）。如例4和例2,26,2等價(jià)公式 從真值表中可以看到，有些命題公式在分量的各種指派下，其對(duì)應(yīng)的真值都完全相同，如PQ與PQ的對(duì)應(yīng)真值相同。,（PQ）（PQ）與PQ對(duì)應(yīng)的真值相同。,27,定義14.2 給定兩個(gè)命題公式A和B，設(shè)P1，P2，Pn為所有出現(xiàn)于A和B中的原子變?cè)?若給P1，P2，Pn任一組真值指派,A和B的真值都相同,則稱(chēng)A和B是等價(jià)的或邏輯相等。記作AB。 例5 證明PQ（PQ）（ QP） 證明 列出真值表,28,24個(gè)重要的等價(jià)式 PP 雙重否定律 PPP等冪律 PPP PQQP交換律 PQQP （PQ）RP（QR）結(jié)合律 （PQ）RP（QR） P

12、（QR）（PQ）（PR）分配律 P（QR）（PQ）（PR） （PQ）PQ 德摩根律 （PQ）PQ,29,P（PQ）P吸收律 P（PQ）P PT T零律 PF F PFP同一律 PT P PP T排中律 PP F矛盾律 PQ PQ蘊(yùn)涵等價(jià)式 P Q （PQ）（QP）等價(jià)等價(jià)式 PQ QP假言易位 P Q P Q等價(jià)否定等價(jià)式 （PQ）（PQ）P歸謬論 其中P、Q和R代表任意的命題公式。,30,例6 驗(yàn)證吸收律P（PQ）P和 P（PQ）P,31,定義1-4.3 如果X是合式公式A的一部分,且X本身也是一個(gè)合式 公式,則稱(chēng)X為公式 A的子公式。 定理14.1如果X是合式公式A的子公式，若XY，如果將

13、A中的X用Y來(lái)置換，所得到公式B與公式A等價(jià)，即AB。 證明 因?yàn)樵谙鄳?yīng)變?cè)娜我环N指派下，X與Y的真值相同，故以Y取代X后，公式B與公式 A在相應(yīng)的指派下，其真值必相同，故AB。 滿足定理14.1的置換稱(chēng)為等價(jià)置換（等價(jià)代換）,32,例7 證明PQ（PQ） 證明 PQ PQ， （根據(jù)蘊(yùn)涵等價(jià)式） PQ （Pq），（德摩根律） 即Pq（Pq）,33,例8 證明P(QR) (PQ) R 證明 P(QR) P(QR) （蘊(yùn)涵等價(jià)式） P(QR) （蘊(yùn)涵等價(jià)式） (PQ) R（結(jié)合律） (PQ) R（德摩根律） (PQ) R（蘊(yùn)涵等價(jià)式）,34,例9 證明 P(PQ) (PQ) 證明 P P1 (同

14、一律) P(QQ)（排中律） (PQ) (PQ)（分配律）,35,練習(xí) 1.證明 Q( (PQ) P)T; 2.證明 (PP) ( (QQ) R) F 3.證明 (PQ) PP,36,1,證明Q( (PQ) P) Q( (PP) (PQ) )（分配律） Q( F (PQ) )（矛盾律） Q(PQ)（同一律） Q(PQ) （德摩根律） (QQ) P（結(jié)合律） TP（排中律） T（零律）,37,2.證明(PP) ( (QQ) R) T( (QQ) R)（排中律） T(FR)（矛盾律 ） TF（零律） TF（蘊(yùn)涵等值式） FFF（等冪律）,38,3. 證明 (PQ) P (PQ) P（蘊(yùn)涵等價(jià)值式）

15、 P（吸收律）,39,1-5 重言式與蘊(yùn)涵式 定義15.1 給定一命題公式 ，若無(wú)論對(duì)分量作什么樣的指 派，其對(duì)應(yīng)的真值永為T(mén)，則稱(chēng)該命題公式 為重言式或永真式。 定義15.2 給定一命題公式 ，若無(wú)論對(duì)分量作什么樣的指 派，其對(duì)應(yīng)的真值永為F，則稱(chēng)該命題公式 為矛盾式或永假式。,40,定理15.1 任何兩個(gè)重言式的合取或析取，仍然是一個(gè)重言式。 定理15.2 一個(gè) 重言式，對(duì)同一分量，都 用任何合式公式 置換，其結(jié)果仍為一重言式。 證明 由于重言式的真值與分量的指派無(wú)關(guān)，幫對(duì)同一分量以任何合式公式置換后，重言式的真值仍永為真。 對(duì)于矛盾式也有類(lèi)似于定理15.1和定理51.2的結(jié)果。,41,例

16、1 證明 （PS）R）（PS）R）為重言式。 證明 因?yàn)?PPT，用（PS）R）置換P得 （PS）R）（PS）R）T,42,定理15.3 設(shè)A 、B為兩命題公式AB ，當(dāng)且僅當(dāng)AB 為一個(gè)重言式。 證明 若 AB ，則A、B有相同的真值，即有AB 永為T(mén)。 若 AB 為重言式，則AB 永為T(mén)， 故A、B的真值相同，即AB 。,43,例2 證明 （PQ）（PQ） 證明 做（PQ）（PQ）的真值表。,由以上真值表可知， （PQ） PQ 為重言式，根據(jù)定理15.3得 （PQ）（PQ）,44,定義15.3 當(dāng)且僅當(dāng) PQ 是重言式時(shí)，我們稱(chēng)“P蘊(yùn)涵Q”，并記作PQ。 做PQ QP，PQ，Qp 的真值表

17、,由此得 PQ QP， QP PQ， 因此要PQ，只要證明QP，反之亦然。,45,要證明PQ，即證PQ 是重言式，對(duì)于PQ 來(lái)說(shuō)，除P的真值取T，Q的真值取F這樣一種指派時(shí)，PQ 的真值為F外，其余情況PQ 的真值為T(mén)，故要征PQ，只要對(duì)條件PQ 的前件P，指定真值為T(mén)，若由此指出Q的真值為T(mén)，則PQ 為重言式，即PQ 成立；同理，如對(duì)條件命題PQ 中，假定后件Q的真值為F，若由此推出P的真值為F，即推證了QP。 故PQ成立。即 若P為T(mén)時(shí)，推出Q為T(mén) 或若Q為F時(shí)，推出P為F 則PQ。,46,例1 推證Q（PQ ）P 證法1 假定Q （PQ ）為T(mén)，則Q為T(mén)，且PQ 為T(mén)。 所以Q為F，PQ

18、 為T(mén)， 所以P為F，故P為T(mén)。 證法2 假定P為F，則P為T(mén)， 若Q為F，則PQ 為F，Q（PQ ）為F， 若Q為T(mén)，則Q為F，Q（PQ ）為F， 所以 Q（PQ ）P,47,常用的蘊(yùn)涵式如下： PQ P PQ Q PPQ PPQ QPQ （PQ） P （PQ） Q P（PQ）Q Q（PQ ）p P（ PQ）Q （PQ ）（QR）PR （PQ）（PR）（QR）R （PQ ）（RS）（PR）（QS） （PQ）（QR）（PR）,48,定理15.4 設(shè)P、Q為任意兩個(gè) 命題公式，PQ 的充分 必要條件是 PQ 且 QP 證明 若PQ，則PQ為重言式。 因?yàn)镻Q （ PQ）（QP）， 故 PQ為T(mén)，

19、 且QP 為T(mén)， 因?yàn)镻Q 且QP成立。 反之，若PQ 且QP， 則PQ為T(mén)， 且QP 為T(mén)， 因此PQ （ PQ）（QP）為T(mén)， 即PQ 這個(gè)定理也可以作為兩個(gè)公式等價(jià)的定義。,49,蘊(yùn)涵的幾個(gè)常用的性質(zhì)： （1）設(shè)A、B、C為合式公式，若AB且A為重言式，則B也是重 言式。 證明 因?yàn)?AB 永為T(mén)，所以當(dāng)A為T(mén)時(shí)，B必T。 （2）若AB，BC，則 AC 證明 由AB， BC 得AB ，BC 為重言式 所以（AB）（BC）為重言式， 根據(jù)（PQ ）（QR）PR 所以 （AB）（BC）AC， 由性質(zhì)（1）得： AC為重言式，即 AC,50,（3）AB，且AC，那么A（BC） 證明 由假設(shè)知A

20、B ，AC為重言式。 設(shè)A這T，則B、C為T(mén)， 故BC為T(mén)， 因此A（BC）為T(mén)， 若A為F，則A（BC）為T(mén)， 所以A（BC）,51,（4）若AB 且 CB ，則ACB 證明 因?yàn)锳B 為T(mén)，CB為T(mén)， 故（AB）（ C B）為T(mén)， 則（AC）B 為T(mén)， 即（AC）B為T(mén)， 即 （AC）B為T(mén)， 所以（AC）B,52,16 其他聯(lián)結(jié)詞 定義16.3 設(shè)P、Q是兩個(gè)命題公式，復(fù)合命題P Q稱(chēng)作P和Q的“與非”。 PQ（PQ）,53,聯(lián)結(jié)詞“”的幾個(gè)性質(zhì)： （1） PP （PP）p （2） （PQ）（PQ）（PQ）PQ （3）（PP）（QQ）PQ （Pq）PQ,54,定義16.3 設(shè)P、Q是兩個(gè)

21、命題公式，復(fù)合命題P Q稱(chēng)作P和Q的“或非”。 P Q（PQ）,55,聯(lián)結(jié)詞“ ”的幾個(gè)性質(zhì)： （1） P P （PP）p （2） （P Q）（PQ）（PQ）PQ （3）（PP）（QQ）PQ PQ 當(dāng)有n個(gè)命題變?cè)獣r(shí)，可構(gòu)成22 n種不等價(jià)的命題公式，如n2時(shí)，有16種不等價(jià)的命題公式。，見(jiàn)27頁(yè)表16.5。,56,最小聯(lián)結(jié)詞組：對(duì)于任何一個(gè)命題公式，都能由僅含這些聯(lián)結(jié)詞的命題公式等價(jià)代換。 由于（1）（PQ）（PQ）（QP） （2）（PQ）PQ （3） PQ（ P Q） （4）PQ（Pq） 故由“”、“”、“”，“”、“”這五個(gè)聯(lián)結(jié)詞組成的命題公式，必可以由，或，組成的命題公式所替代。,57

22、,17 對(duì)偶與范式 定義17.1在給定的命題公式A中，將換成，換成，若有特殊變?cè)狥和T亦相互取代，所得命題公式A*稱(chēng)為A的對(duì)偶式。 A和A*互為對(duì)偶式。 例1: PQ與 PQ, (PQ )與 (PQ) ( PQ) R與 (PQ) R (PT) Q 與(P F) Q 均為對(duì)偶式. 例2：PQ、 P Q的對(duì)偶式。 解： PQ (PQ )，PQ的對(duì)偶式為(PQ) P Q（PQ） ，P Q的對(duì)偶式為(PQ ),58,定理17.1設(shè)A和A*互為對(duì)偶式, P1,P2,Pn，是出現(xiàn)在A和A*中的全部的命題變?cè)?則 A(P1,P2,Pn) A*(P1, P2, Pn) A(P1, P2, Pn) A*(P1,

23、 P2, Pn) 例:設(shè) A(P,Q,R) P(QR) 得:A*(P,Q,R) P(QR) (1)由知:A(P,Q,R) P(QR) 由知: A*(P, Q, R) P(QR) 所以: A(P,Q,R) A*(P, Q, R) 類(lèi)似地,有A(P, Q, R) A*(P,Q, R),59,定理17.2設(shè)P1,P2,Pn 是出現(xiàn)有命題公式A和B中的所有命題變?cè)?，若A B，則A* B*。 證明：因?yàn)锳 B， 即A(P1,P2,Pn) B(P1,P2,Pn) 是重言式， A(P1, P2, Pn) B(P1, P2, Pn) 是重言式， 故A(P1, P2, Pn) B(P1, P2, Pn) 由定理

24、17.1得 A*(P1,P2,Pn) B*(P1,P2,Pn) 因此A* B*,60,例4 如果A(P,Q,R) 是P（Q（RP），求它的對(duì)偶式A*(P,Q,R) 。并求與A及 A*等價(jià)，但僅包含聯(lián)結(jié)詞“”、“”、“”的公式。 解： 因 A(P,Q,R) 是 P（Q（RP） 故 A*(P,Q,R) 是P （Q（RP） 但P（Q（RP） P（Q（RP） （P（Q（RP） 所以P （Q（RP） (P（Q（RP）),61,定義17.2 一個(gè)命題公式 稱(chēng)為合取范式，當(dāng)且僅當(dāng)它具有形式A1A2An（n1）。其中A1，A2，An 都是命題變?cè)蚱浞穸ㄋM成的析取式。 例P(PQ) (PP ) (PR) 定

25、義17.3 一個(gè)命題公式 稱(chēng)為析取范式，當(dāng)且僅當(dāng)它具有形式A1A2 An（n1）。其中A1，A2，An 都是命題變?cè)蚱浞穸ㄋM成的合取式。 例 (PQR) (PQ) (PQR),62,求合取范式或 析取范式的步驟： （1）將公式中的聯(lián)結(jié)詞化歸成、。 （2）將消去或內(nèi)移。 （3）利用分配律、交換律求合取范式或析取范式。 （求合取范式：對(duì)； 求析取范式： 對(duì) ） 注意任何命題的析取范式和合取范式都不是唯一的。,63,例求下面命題公式的合取范式和析取范式。 （PQ）R）P 解（1）求合取范式 （PQ）R）P （PQ）R）P (PQ) R) P (PQ) R) P (PQ) R) P (PQ) R)

26、 P (PQ) R) P (PQP) (RP) （PQ）(RP) (2)求析取范式 (PQ) R) P (PR) (QR) PP（P R） (QR) P(QR),64,練習(xí)：求下面命題公式的合取范式和析取范式。 （1）求合取范式 (PQ) R (PQ) R (PQ) R) (R(PQ) (PQ) R) (R(PQ) (PQ) R) (RPQ) (PR) (QR) (RPQ) （2）求析取范式 (PQ) R) (RPQ) （(PQ) (RPQ)）(R(RPQ) (PQ) R) (PQ) P) (PQ) Q) (RR) (RP) (RQ) (PQR) (PPQ) (PQQ) (RR) (PR) (

27、QR) (PQR) (PR) (QR),65,定義17.4 n個(gè)命題變?cè)暮先∈?，稱(chēng)作布爾合取或小項(xiàng)，其中變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。 n個(gè)命題變?cè)?共有2n個(gè)小項(xiàng)。 例兩個(gè)命題變?cè)?P和Q，其小項(xiàng)為：PQ，PQ，PQ，PQ,66,3個(gè)命題變項(xiàng)P、Q、R可形成8個(gè)小項(xiàng)： m000 PQR m001PQR m010PQR m011PQR m100PQR M101PQR m110PQR m111PQR,67,小項(xiàng)的性質(zhì)： （1）每一個(gè)小項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為T(mén)，其余均為F。 （2）任意兩個(gè)不同小項(xiàng)的合取永為F。 （3） m0m1m2m3m4m5m6m7T,

28、68,定義17.3 對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅由小項(xiàng)的析取所組成，則該等價(jià)式稱(chēng)作原式的主析取范式。 定理17.3 在真值表中，一個(gè) 公式的真值為T(mén)的指派所對(duì)小項(xiàng)的析取，即為此公式的主析取范式。,69,例6給定P Q，PQ和（PQ），求這些公式的主析取范式。 解：真值表如下：,故P Q（PQ）（PQ）（PQ） PQ（PQ）（PQ）（PQ） （PQ）（PQ）（PQ）（PQ）,70,例7 設(shè)一公式A的真值表如下，求公式 A的主析取范式。,解 公式A的主析取范式 為： A（PQR）（PRR）（PQR）,71,例8 求（PQ）（PR）（QR）的主析取范式。 解：原式（PQ（RR） （P

29、R（QQ） （QR（Pp） （PQR）（PQR） （PQR）（PQR） （PQR）（PQR） （PQR）（PQR） （PQR）（PQR）,72,例9求P（PQ）（QP）的主析取范式。 解：原式P（PQ）（QP） P（PQP）（QQP） P（QP） P（QQ）（PQ） （PQ）（PQ）（PQ）,73,求主析取范式的步驟： （1）求析取范式。 （2）去掉永假的析取項(xiàng)。 （3）去掉重復(fù)的合取項(xiàng)、合并相同變?cè)?（4）對(duì)合取項(xiàng)補(bǔ)入沒(méi)出現(xiàn)的命題變?cè)?。（PP）,74,定義17.6 n個(gè)命題變?cè)奈鋈∈?，稱(chēng)作布爾析取或大項(xiàng)，其中變?cè)c它的否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。 n個(gè)命題變?cè)?共有2n

30、個(gè)小項(xiàng)。 例 兩個(gè)命題變?cè)?P和Q，其小項(xiàng)為：PQ， PQ，PQ，PQ,75,3個(gè)命題變項(xiàng)P、Q、R可形成8個(gè)大項(xiàng)： M000 PQR M001PQR M010PQR M011PQR M100PQR M101PQR M110PQR M111PQR,76,大項(xiàng)的性質(zhì)： （1）每一個(gè)大項(xiàng)當(dāng)其真值指派與編碼相同時(shí)，其真值為F，其余均為T(mén)。 （2）任意兩個(gè)不同大項(xiàng)的析取永為T(mén)。 （3） M0M1M2M3M4M5M6M7F,77,定義17.7 對(duì)于給定的命題公式，如果有一個(gè)等價(jià)公式，它僅由大項(xiàng)的合取所組成，則該等價(jià)式稱(chēng)作原式的主合取范式。 定理17.4 在真值表中，一個(gè)公式的真值為F的指派所對(duì)大項(xiàng)的合取

31、，即為此公式的主合取范式。,78,例10 利用真值表求（PQ）（PR）的主合取范式與主析取范式。,79,主合取范式：（PQR）（PQR）（PQR）（PQR） 主析取范式：（PQR）（PQR）（PQR）（PQR）,80,求主合取范式的步驟： （1）求合取范式。 （2）去掉所有為T(mén)的合取項(xiàng)。 （3）合并相同的析取項(xiàng)和變?cè)?（4）補(bǔ)入沒(méi)出現(xiàn)的命題變?cè)?。（即添加PP）,81,例11 求（PQ）（PR）的主合取范式。 解：原式 （PQ）P）（PQ）R） （Pp）（Qp）（PR）（QR） （Qp）（PR）（QR） （QP（RR） （ PR（QQ） （QR（PP） （QPR）（QPR） （PRQ）（PRQ

32、） （QRP）（QRP） （PQR）（PQR） （PQR）（PQR）,82,用表示小項(xiàng)的析取 用表示大項(xiàng)的合取 例如（PQ）（PR） （PQR）（PQR） （PQR）（PQR） M000M010M100M101 0,2,4,5 m001m011m110m111 1,3,6,7,83,1-8推理理論 推理是從前提推出結(jié)論的思維過(guò)程,前提是指已知的命題公式,結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出來(lái)的命題公式。前提可以是多個(gè) 。 定義18.1設(shè)H1，H2，H n ，C是命題公式，若（H1H2Hn）C為重言式,則稱(chēng)C是一組前提H1,H2,Hn的有效結(jié)論。記作： H1H2Hn C 真值表法 推理方法 直接證法

33、 間接證法,84,（1）真值表法 若H1，H2，H n 都為T(mén)的行，C也為真； 或若C為假的行，H1，H2，H n 中至少有一個(gè)為假 則 H1H2Hn C 成立。,85,例1 一份統(tǒng)計(jì)表格的錯(cuò)誤或者是由于材料不可靠，或者是由于計(jì)算有錯(cuò)誤；這份統(tǒng)計(jì)表格的錯(cuò)誤不是由于材料不可靠，所以這份統(tǒng)計(jì)表格是由于計(jì)算有錯(cuò)誤。 解：設(shè) P：統(tǒng)計(jì)表格的錯(cuò)誤是由于材料不可靠。 Q：統(tǒng)計(jì)表格的錯(cuò)誤是由于計(jì)算不可靠。 前提是：PQ，P ，結(jié)論是：Q ，即證明 （ PQ）P Q,故（ PQ）P Q,86,例2 如果張老師來(lái)了，這個(gè)問(wèn)題可以得到解答，如果李老師來(lái)了，這個(gè)問(wèn)題也可以得到解答，總之張老師或李老師來(lái)了，這個(gè)問(wèn)題就

34、可以得到解答。 解：設(shè)P：張老師來(lái)了。 Q：李老師來(lái)了。 R：這個(gè)問(wèn)題可以得到解答。 本題可譯為： （P R）（QR）（PQ）R,87,88,（2）直接證法 就是由一組前提，利用一些公認(rèn)的推理規(guī)則，根據(jù)已知的等價(jià)公式或蘊(yùn)涵公式，推出有效結(jié)論。 P規(guī)則：前提在推導(dǎo)過(guò)程中隨時(shí)可以引用。 T規(guī)則：已經(jīng)推出的公式在以后的推導(dǎo)過(guò)程中可隨時(shí)引用。 常用蘊(yùn)涵式見(jiàn)43頁(yè)表18.3,89,例1 證明（PQ）（PR）（ QS）SR 證法1 （1）PQ P （2）PQ T（1）E （3） QS P （4）PS T（2），（3）I （5）SP T（4）E （6）PR P （7）SR T（5），（6）I （8）SR T

35、（7）E,90,證法2 （1）PR P （2） PQRQ T（1）I （3）QS P （4）QRSR T（3）I （5）PQSR T（2），（4）I （6）PQ P （7）SR T（5），（6）I,91,例2 證明（WR）V，VCS，SU，C U W 證明 （1） C U P （2）U T（1）I （3） SU P （4）S T（2）,（3）I (5) C T（1）I (6) C S T(4),(5) I (7) (C S) T(6)E (8) （WR）V P (9) V(CS) P (10) （WR）(CS) T(8),(9)I (11) (（WR） T(7),(10)I (12) W R

36、T(11)E (13) W T(12)E,92,(3) 間接證法1(歸謬法) 要證 H1H2Hn C 即要證 H1H2Hn C 為重言式 H1H2Hn C (H1H2Hn ) C (H1H2Hn C) 因此只要證 H1H2Hn C 為矛盾式.,93,例3 證明 AB, (BC)可邏輯推出A 證明 (1) AB P (2) A P(附加前提) (3) (BC) P (4) BC T(3)E (5) B T(1),(2)I (6) B T(4) I (7) BB (矛盾) T(5),(6) I,94,例4 證明 (PQ) (PR) (QS) SR 證明 (1) (SR) P (2) SR T(1)

37、E (3) PQ P (4) PQ T(3)E (5) QS P (6) PS T(4),(5) I (7) SP T(6) (8) (SR ) (PR) T(7) I (9) PR T(2),(8) I (10) PR P (11) P R T(10)E (12) (P R ) T(11)E (13) (P R ) (P R ) (矛盾) T(9),(12) I,95,(4) 間接證法2(附加前提法) 要證 H1H2Hn RC 只要證 ( H1H2Hn )(R C) 為重言式 (H1H2Hn )(R C) ( H1H2Hn ) (R C) ( H1H2HnR ) C ( H1H2Hn R)

38、C 只要證 ( H1H2Hn R) C 由 (SR) C 證得S(R C) 稱(chēng)為CP規(guī)則。,96,例5 證明 A (BC), DA, B 重言蘊(yùn)涵 DC 證明 (1) D P(附加前提) (2) DA P (3) A T(1),(2) I (4) A (BC) P (5) BC T(3),(4) I (6) B P (7) C T(5),(6) I (8) DC CP,97,例6 設(shè)有下列情況,結(jié)論是否有效? (a) 或者是天晴,或者是下雨。 (b) 如果是天晴，我去看電影。 (c) 如果我去看電影，我就不看書(shū)。 結(jié)論：如果我在看書(shū)則天在下雨。 解 若設(shè) M：天晴。 Q：下雨 。 S：我看電影

39、。 R：我看書(shū)。 即證：MQ，MS，SR，推出RQ 其中 MQ (MQ）,98,(1) R P（附加前提） (2) SR P (3) R S T(2) E (4) S T(1),(3) I (5) MS P (6) M T(4),(5) I (7) (M Q） P (8) M Q T(7) E (9) ( MQ) (QM) T(8) E (10) QM T(9) I (11) MQ T(10) E (12) Q T(6),(11) I (13) RQ CP,99,第二章 謂詞邏輯 原子命題是命題邏輯研究的基本單位,沒(méi)有對(duì)原子的內(nèi)部結(jié)構(gòu)及其相互之間的邏輯關(guān)系進(jìn)行分析,這樣就無(wú)法處理一些簡(jiǎn)單而又常

40、見(jiàn)的推理問(wèn)題。 例如: 所有的人都是要死的，蘇格拉底是人，所以,蘇格拉底是要死的。 P: 所有的人是要死的. Q: 蘇格拉底是人. R: 所以,蘇格拉底是要死的 PQR 不是重言式。,100,21 謂詞的概念與表示 原子命題由主語(yǔ)和謂語(yǔ)兩部分組成。 主語(yǔ)一般是客體。 客體：可以是一個(gè)具體的事物，也可以是一種抽象事物。是命題所研究的對(duì)象。 謂詞：用以刻劃客體的性質(zhì)或客體之間的性質(zhì)。 例 李明是一個(gè)學(xué)生。 李明比王杰高。 哥白尼指出地球繞著太陽(yáng)轉(zhuǎn)。,101,謂詞用大寫(xiě)字母表示。 客體名稱(chēng)用小寫(xiě)字母表示。 客體常元：表示具體或特定的客體的詞。 一般用小寫(xiě)字母a,b,c,表示。 客體變?cè)罕硎境橄蟮幕?/p>

41、泛指的客體的詞。 一般用小寫(xiě)字母x,y,z,表示。 例如：A表示“是個(gè)大學(xué)生”， c表示張三， e表示李四， 則 A（c）表示“張三是個(gè)大學(xué)生”， A（e）表示“李四是個(gè)大學(xué)生”，,102,“b是A” 類(lèi)型的命題可用A（b）表示。 兩個(gè)客體之間關(guān)系的命題可表示為B（a,b）。 A（b）為一元謂詞。 B（a,b）為二元謂詞。依此類(lèi)推。 單獨(dú)一個(gè)謂詞不是命題，只有將變?cè)獂,y,z等取特定客體時(shí)，才確定了一個(gè)命題。,103,22 命題函數(shù)與量詞 定義22.1 由一個(gè)謂詞，一些客體變?cè)M成的表達(dá)式稱(chēng)為簡(jiǎn)單命題函數(shù)。 例 B（x,y）。 n元謂詞就是有n個(gè)客體變?cè)拿}函數(shù)。 當(dāng)n0時(shí)，它本身就是一個(gè)命

42、題。,104,由一個(gè)或幾個(gè)簡(jiǎn)單命題函數(shù)以及聯(lián)結(jié)詞組合而成的表達(dá)式稱(chēng)為復(fù)合命題函數(shù)。 例1 （1） 2是素?cái)?shù)且是偶數(shù)。 解： 設(shè)A（x）：x是素?cái)?shù)； B（x）：x是偶數(shù)； a：2 則命題表示為： A（a）B（a） （2）如果2大于3，則2大于4。 解： 設(shè)L（x,y）：x大于y； a ：2； b：3 ； c：4 則命題表示為：L（a,b）L（a,c）。,105,（3）如果張明比李民高，李民比趙亮高，則張明比趙亮高。 解：設(shè) H（x,y）：x比y高； a：張明； b：李民； c：趙亮。 則命題符號(hào)化為 ： H（a,b）H（b，c）H（a,c）。 命題函數(shù)不是命題，只有客體變?cè)√囟腕w名稱(chēng)時(shí)，才能

43、成為命題。,106,個(gè)體域：客體變?cè)娜≈捣秶?個(gè)體域可以是有限的，也可以是無(wú)限的。 例 學(xué)生、工人，實(shí)數(shù)，a,b，c。 全總個(gè)體域：宇宙間的一切事物。,107,量詞：表示數(shù)量的詞。 全稱(chēng)量詞“” 用來(lái)表達(dá)“對(duì)所有的”、“每一個(gè)”，“對(duì)任何一個(gè)”。 例2 （1）所有的人都是要呼吸的。 解：設(shè)M（x）：X是人； H（x）：x要呼吸。 則符號(hào)化為：（x）（ M（x） H（x） 域?yàn)槿傆颉?108,（2）每個(gè)學(xué)生都要參加考試。 解：設(shè)P（x）：x是學(xué)生；Q（x）：x要參加考試。 符號(hào)化為: （x）（ P（x）Q（x） (3) 任何整數(shù)或是正的或是負(fù)的。 解：設(shè) I（x）：x是整數(shù)； R（x）：X

44、是正數(shù)； M（x）：x是負(fù)數(shù)。 符號(hào)化為：（x）（ I（x）R（x）M（x）,109,存在量詞“”：表示“存在一些”。 例3 （1）存在一個(gè)數(shù)是質(zhì)數(shù)。 解：設(shè) P（x）：x是質(zhì)數(shù)。 符號(hào)化為： （x ）（ P（x） （2）一些人是聰明的。 解：設(shè) M（x）：x是； R（x）：x是聰明的。 符號(hào)化為：（x ）（ M（x）R（x）,110,注意： （1）在不同的個(gè)體域中，命題符號(hào)化的形式可能不一樣。 （2）如果事先沒(méi)有給出個(gè)體域，都應(yīng)以全總個(gè)體域?yàn)閭€(gè)體域。 （3）在引入特性謂詞后，使用全稱(chēng)量詞與存在量詞符號(hào)化的形式是不同的。 對(duì)全稱(chēng)量詞，特性謂詞常作蘊(yùn)涵的前件； 對(duì)存在量詞，特性謂詞常作合取 項(xiàng)。

45、,111,例：（1）所有的人都是要死的。 （2）有的人活百歲以上。 解：第一種情況：考慮個(gè)體域D為人類(lèi)集合。 （1）符號(hào)化為：x F(x)。 其中F(x)：x是要死的。 （2）xF(x)。 其中F(x)：x活百歲以上。 第二種情況：考慮個(gè)體域?yàn)槿倐€(gè)體域， 對(duì)所有個(gè)體而言，如果它是人，則它是要死的。 存在著個(gè)體，它是人并且活百歲以上/ 引進(jìn)特性謂詞：M（x）：X是人。 （1）符號(hào)化為：x（M（x） F(x)） （2）符號(hào)化為：x（M（x）F(x)）,112,23 謂詞公式與解釋 原子謂詞公式：若P（x1,x2,xn）是n元謂詞，則稱(chēng)P（ x1,x2,xn）是原子謂詞公式。 其中x1,x2,xn

46、是客體變?cè)?例 Q， R（x），A（x,y), A(f(x),y), A(a,y,z),113,合式公式定義如下： （1）原子公式是合式公式； （2）若A是合式公式，則（A）也是合式公式； （3）若A、B是合式公式，則（AB）、（AB）、（A B）、（AB）也是合式公式； （4）若A是合式公式，則xA、xA也是合式公式； （5）只有有限次地使用(1)(4）生成的符號(hào)串才是合式公式.,114,例1并非每個(gè)實(shí)數(shù)都是有理數(shù)。 解：設(shè) R（x）：x是實(shí)數(shù)； Q（x）：x是有理數(shù)。 謂詞公式為：（x R(x) Q（x） 例2 一切人都不一樣高。 解：設(shè)M（x）：x是人； H（x，y）：x y； L（x

47、，y）：x與y一樣高。 謂詞公式為： x y （M(x)M（x）H（x，y）L（x，y）,115,例3 每個(gè)自然數(shù)都有后繼數(shù)。 解：設(shè)F（x）：x是自然數(shù)； H（x，y）：y是x的后繼數(shù)。 謂詞公式為： x（ F(x) y（ F(y) H（x，y） 例4 這只大紅書(shū)包擺滿了那些古書(shū)。 解：設(shè)F（x，y）：x擺滿了y； Q（y）：y是古書(shū)； a: 這只； b：那些。 謂詞公式為： R（a）Q（b）F(a, b),116,24 變?cè)募s束 1、變?cè)募s束 定義24.1 在合式公式xA或xA中,稱(chēng)x為指導(dǎo)變項(xiàng)，稱(chēng)A為相應(yīng)量詞的轄域。在轄域中，x的所有出現(xiàn)稱(chēng)為約束出現(xiàn)（即x受相應(yīng)量詞指導(dǎo)變?cè)募s束），

48、A中不是約束出現(xiàn)的其它變?cè)Q(chēng)為自由出現(xiàn)。,117,例1 指出下列合式公式中的指導(dǎo)變?cè)?、量詞的轄域與客體變?cè)淖杂沙霈F(xiàn)和約束出現(xiàn)。 (1) x(F(x) yH(x,y); (2) xF(x) G(x,y); (3) xy(R(x,y) L(y,z) x H(x,y),118,2、變?cè)母拿?（1） 約束變?cè)母拿?將量詞的轄域中出現(xiàn)的某個(gè)約束出現(xiàn)的客體變?cè)皩?duì)應(yīng)的指導(dǎo)變?cè)某勺饔糜蛏衔闯霈F(xiàn)的變?cè)Q(chēng)，公式其余部分不變。（換名規(guī)則） （2）自由變?cè)母拿?將自由變?cè)迷街械乃锌腕w變?cè)?hào)不同的變?cè)?hào)去代替，且處處代替。（代替規(guī)則）,119,例2：在xF(x) G(x,y)中， 利用換

49、名規(guī)則，將約束出現(xiàn)的x改成z,得： z F(z) G(x,y)。 利用代替規(guī)則，將自由出現(xiàn)的x用z代替，得： xF(x) G(z ,y)。 例3：在xy(R(x,y) L(y,z) x H(x,y)中， 將x H(x,y)中的x利用換名規(guī)則換成t,對(duì)y利用代替規(guī)則，用w代替，得： xy(R(x,y) L(y,z) t H(t,w).,120,3、謂詞公式的解釋 謂詞公式的解釋:對(duì)謂詞公式中各種變項(xiàng)用具體的常項(xiàng)元去代替。通過(guò)對(duì)謂詞的解釋?zhuān)蟪鲋^詞公式的真值。 謂詞公式的解釋由四部分組成 （1）非空的個(gè)體域D； （2）D中的一些特定元素； （3）D上一些特定函數(shù)； （4）D上的一些特定的謂詞。,1

50、21,例4 給定解釋I如下： 1）DI2，3； 2）DI中特定元素a=2; 3）函數(shù)f(x)為 f(2)=3,f(3)=2; 4）謂詞 F(x)為 F(2)=F,F(3)=T; G(x,y) 為G(i,j)=T, i,j=2,3; L(x,y)為 L(2,2)=L(3,3)=T, L(2,3)=L(3,2)=F; 在解釋I下,求x(F(x) G(x, a)的真值。 解: x(F(x) G(x, a) （F（2）G（2，2）（F（3）G （3，2） （FT）（TT） F,122,例5給定解釋I如下： 1）DI2，3； 2）DI中特定元素a=2; 3）函數(shù)f(x)為 f(2)=3,f(3)=2;

51、4）謂詞 F(x)為 F(2)=F,F(3)=T; G(x,y) 為G(i,j)=T,i,j=2,3; L(x,y)為 L(2,2)=L(3,3)=T, L(2,3)=L(3,2)=F; 在解釋I下,求x (F(f(x) G(x,f(x)的真值。 解： x (F(f(x) G(x,f(x) （F(f(2）G（2，f（2） (F(f(3) G(3,f(3) (F(3) G(2,3) (F(2) G(3,2) (TT) (FT) T,123,例6 給定解釋I如下： 1）DI2，3； 2）DI中特定元素a=2; 3）函數(shù)f(x)為 f(2)=3,f(3)=2; 4）謂詞 F(x)為 F(2)=F,F

52、(3)=T; G(x,y) 為G(i,j)=T, i,j=2,3; L(x,y)為 L(2,2)=L(3,3)=T, L(2,3)=L(3,2)=F; 在解釋I下,求 xyL(x,y)的真值。 解： xyL(x,y) (L(2,2) (L(2,3) (L(3,2) L(3,3) TTT,124,4、謂詞公式的類(lèi)型 定義 設(shè)A為一謂詞公式，如果A在任何解釋下 都是真的，則稱(chēng)A為邏輯有效式（或稱(chēng)永真式）；如果A在任何解釋下都是假 的，則稱(chēng)A是矛盾式（或稱(chēng)永假式）；若至少存在一個(gè)解釋使A為真，則稱(chēng)A是可滿足式。,125,例7 判斷下列公式中哪些是邏輯有效式?哪些是矛盾式? （1）x F（x）xF（x

53、） 解:(1)設(shè)I為任意的解釋,其個(gè)體域?yàn)镈. 若存在x0 D,使得F（x0）為假,則x F（x）為假,所以x F（x）xF（x）為真. 若對(duì)任意的x D,都有F（x）為真, 則有 x F（x）, xF（x）為真,所以x F（x）xF（x）為真. 故在任何解釋I下,原公式為真,由于I的任意性,所以原公式為邏輯有效式。,126,（2）x F（x）(xyG（x, y）x F（x）) 解：因?yàn)镻(QP) P(QP) P(QP) (PP)QT 由于P(QP) 是重言式,而(2)中公式是該式的代換實(shí)例,因而（2）是邏輯有效式。 （3）x F（x）(xF(x) yG（y）) 解：因?yàn)?P(PQ) P(PQ

54、) (PP) Q T 由于P(PQ) 是重言式,而(3)中公式是該式的代換實(shí)例,因而是邏輯有效式。,127,（4）(F(x,y) R(x,y) R(x,y) 解：因?yàn)?PQ) Q (PQ) Q PQQ F (4) 中公式是(PQ) Q的代換實(shí)例,而(PQ) Q 是重言式, 因而(4)中的公式是邏輯有效式。,128,25 謂詞演算的等價(jià)式與蘊(yùn)涵式 定義25.1 設(shè)A和B是謂詞公式，若A和B在任何解釋下的取值都相同，則稱(chēng)A和B是等價(jià)的，記為AB。 （1）命題公式的推廣： 如： x（ P(x)Q(x) x(P（x）Q(x) ) x P(x) yR（x, y） (x P(x) yR(x, y) ) x

55、 H（x, y）x H（x, y）F,129,(2)量詞與聯(lián)結(jié)詞之間的關(guān)系 例1 設(shè)P(x): x今天來(lái)上課,則p(x):x今天沒(méi)來(lái)上課. 不是所有的人今天來(lái)上課與存在一些人今天沒(méi)來(lái)上課意義相同.即: x P（x）x P（x） 不存在一些人今天來(lái)上課與所有的人今天都沒(méi)來(lái)上課相同. x P（x）x P（x） 關(guān)于量詞的轉(zhuǎn)化律可以在有限個(gè)體域上證明.,130,(3)量詞作用域的擴(kuò)張與收縮 x (A（x）B) (x A（x）B) x (A（x）B) (x A（x）B) x (A（x）B) (x P（x）B) x (A（x）B) (x P（x）B) (x A（x）B) x ( A（x）B) (x A（x）B) x (A（x）B) (Bx A（x）) x (BA（x）) (Bx A（x）) x (B A（x）),131,例2 證明 (x A（x）B) x ( A（x）B) 證明: (x A（x）B) x A（x）B x A（x）B