第3章命題邏輯

數(shù)理邏輯（MathematicalLogic）是研究演繹推理的一門(mén)學(xué)科,是邏輯學(xué)的主要分支（辯證邏輯、形式邏輯）；它的主要研究?jī)?nèi)容是推理，特別著重于推理過(guò)程是否正確；它不是研究某個(gè)特定的語(yǔ)句是否正確，而是著重于語(yǔ)句之間的關(guān)系。它的主要研究方法是采用數(shù)學(xué)的方法來(lái)研究數(shù)學(xué)推理、數(shù)學(xué)性質(zhì)和數(shù)學(xué)基礎(chǔ)；所謂數(shù)學(xué)方法就是引進(jìn)一套符號(hào)體系的方法，所以數(shù)理邏輯又叫符號(hào)邏輯（SymbolicLogic）。第二篇數(shù)理邏輯什么是數(shù)理邏輯？用數(shù)學(xué)的方法來(lái)研究推理的規(guī)律統(tǒng)稱(chēng)為數(shù)理邏輯。為什么要研究數(shù)理邏輯？

程序＝算法＋數(shù)據(jù) 算法＝邏輯＋控制數(shù)理邏輯在人類(lèi)腦力勞動(dòng)自動(dòng)化過(guò)程中，將發(fā)揮越來(lái)越大的作用！總結(jié)主要研究?jī)?nèi)容命題邏輯

命題的基本概念命題聯(lián)結(jié)詞命題公式命題的范式主要研究?jī)?nèi)容謂詞邏輯謂詞的基本概念謂詞公式公式的標(biāo)準(zhǔn)型推理與證明技術(shù)命題邏輯推理理論謂詞邏輯推理理論數(shù)學(xué)歸納法按定義證明法第3章命題邏輯

命題邏輯也稱(chēng)命題演算，或語(yǔ)句邏輯。它研究以命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系，研究什么是命題？如何表示命題？如何由一組前提推導(dǎo)一些結(jié)論？命題邏輯的特征：

在研究邏輯的形式時(shí)，我們把一個(gè)命題只分析到其中所含的命題成份為止，不再分析下去。不把一個(gè)簡(jiǎn)單命題再分析為非命題的集合，不把謂詞和量詞等非命題成份分析出來(lái)。3.0內(nèi)容提要命題公式3命題范式4命題基本概念1集合的表示方法2命題聯(lián)結(jié)詞23.1本章學(xué)習(xí)要求重點(diǎn)掌握一般掌握了解11、五種基本聯(lián)結(jié)詞2、24個(gè)基本的等價(jià)公式3掌握求命題范式的方法3聯(lián)結(jié)詞的完備集的理解和學(xué)習(xí)2公式的代入規(guī)則和替換規(guī)則3.2.1命題定義3.2.1

具有確切真值的陳述句稱(chēng)為命題,該命題可以取一個(gè)“值”，稱(chēng)為真值。3.2命題與命題聯(lián)結(jié)詞真值只有“真”和“假”兩種，分別用“Ｔ”(或“１”)和“Ｆ”(或“０”)表示。太陽(yáng)是圓的；成都是一個(gè)旅游城市；北京是中國(guó)的首都；1＋1＝10；我喜歡看足球比賽；3能被2整除；地球外的星球上也有人；中國(guó)是世界上人口最多的國(guó)家；今天是晴天；ｘ+y>０；例3.2.1T

TTT/FT/FFT/FTT/F非命題例3.2.1(續(xù))把門(mén)關(guān)上；滾出去！你要出去嗎？今天天氣真好??！這個(gè)語(yǔ)句是假的。非命題非命題非命題非命題非命題四川不是一個(gè)國(guó)家；3既是素?cái)?shù)又是奇數(shù)；張謙是大學(xué)生或是運(yùn)動(dòng)員；如果周末天氣晴朗，則我們將到郊外旅游；2+2=4當(dāng)且僅當(dāng)雪是白的。例3.2.2這些命題都不是簡(jiǎn)單的陳述句，它們是由一些簡(jiǎn)單的陳述句通過(guò)“不”、“并且”、“或者”、“如果…，則…”、‘“當(dāng)且僅當(dāng)”等這樣的關(guān)聯(lián)詞和標(biāo)點(diǎn)符號(hào)復(fù)合而成的，即它們都可以分解成更為簡(jiǎn)單的陳述句。一般來(lái)說(shuō)，命題可分兩種類(lèi)型：原子命題(簡(jiǎn)單命題)：不能再分解為更為簡(jiǎn)單命題的命題。復(fù)合命題：可以分解為更為簡(jiǎn)單命題的命題。而且這些簡(jiǎn)單命題之間是通過(guò)如“或者”、“并且”、“不”、“如果...，則...”、“當(dāng)且僅當(dāng)”等這樣的關(guān)聯(lián)詞和標(biāo)點(diǎn)符號(hào)復(fù)合而構(gòu)成一個(gè)復(fù)合命題。命題的分類(lèi)P：今天天氣很冷。Q：今天天氣很冷并且刮風(fēng)。R：今天天氣很冷并且刮風(fēng)，但室內(nèi)暖和。通常用大寫(xiě)的帶或不帶下標(biāo)的英文字母Ａ、Ｂ、Ｃ、...P、Q、R、...Ai、Bi

、Ci、...Pi、Qi、Ri、...等表示命題命題的表示3.2.2命題聯(lián)結(jié)詞定義3.2.2

設(shè)P是任一命題，復(fù)合命題“非P”(或“P的否定”)稱(chēng)為P的否定式(Negation)，記作P，“”為否定聯(lián)結(jié)詞。若P：四川是一個(gè)國(guó)家。則P：四川不是一個(gè)國(guó)家。PPO11OP為真當(dāng)且僅當(dāng)P為假。合取聯(lián)結(jié)詞定義3.2.3

設(shè)P、Q是任兩個(gè)命題，復(fù)合命題“P并且Q”(或“P和Q”)稱(chēng)為P與Q的合取式(Conjunction)，記作P∧Q，“∧”為合取聯(lián)結(jié)詞。P∧Q為真當(dāng)且僅當(dāng)P，Q同為真。若P：3是素?cái)?shù)；Q：3是奇數(shù)。則P∧Q：3既是素?cái)?shù)又是奇數(shù)。PQP∧QOOOO1O1OO111析取聯(lián)結(jié)詞定義3.2.4

設(shè)P、Q是任兩個(gè)命題，復(fù)合命題“P或者Q”稱(chēng)為P與Q的析取式(Disjunction)，記作P∨Q，“∨”為析取聯(lián)結(jié)詞。P∨Q為真當(dāng)且僅當(dāng)P，Q中至少一個(gè)為真。若P：張謙是大學(xué)生；Q：張謙是運(yùn)動(dòng)員。則P∨Q：張謙是大學(xué)生或是運(yùn)動(dòng)員。PQP∨QOOOO111O1111蘊(yùn)涵聯(lián)結(jié)詞定義3.2.5

設(shè)P、Q是任兩個(gè)命題，復(fù)合命題“如果P，則Q”稱(chēng)為P與Q的蘊(yùn)涵式(Implication)，記作P→Q，“→”稱(chēng)為蘊(yùn)涵聯(lián)結(jié)詞，P稱(chēng)為蘊(yùn)涵式的前件，Q稱(chēng)為蘊(yùn)涵式的后件。P→Q為假當(dāng)且僅當(dāng)P為真且Q為假。若P：周末天氣晴朗；Q：我們將到郊外旅游。則P→Q：如果周末天氣晴朗，則我們將到郊外旅游。PQP→QOO1O111OO111等價(jià)聯(lián)結(jié)詞定義3.2.6

設(shè)P、Q是任兩個(gè)命題，復(fù)合命題“P當(dāng)且僅當(dāng)Q”稱(chēng)為P與Q的等價(jià)式(Enuivalence)，記作PQ，“”稱(chēng)為等價(jià)聯(lián)結(jié)詞。PQ為真當(dāng)且僅當(dāng)P、Q同為真假。

若P：2+2=4；Q：雪是白的。則PQ：2+2=4當(dāng)且僅當(dāng)雪是白的。PQPQOO1O1O1OO111總結(jié)聯(lián)結(jié)詞記號(hào)復(fù)合命題記法讀法真值結(jié)果否定┐非A┐AA的否定┐A為真當(dāng)且僅當(dāng)A為假合取∧A并且BA∧BA合取BA∧B為真當(dāng)且僅當(dāng)A,B同為真析取∨A或者BA∨BA析取BA∨B為真當(dāng)且僅當(dāng)A,B中至少一個(gè)為真蘊(yùn)涵→若A，則BA→BA蘊(yùn)涵BA→B為假當(dāng)且僅當(dāng)A為真B為假等價(jià)A當(dāng)且僅當(dāng)BABA等價(jià)于BAB為真當(dāng)且僅當(dāng)A,B同為真假說(shuō)明1、聯(lián)結(jié)詞是句子與句子之間的聯(lián)結(jié)，而非單純的名詞、形容詞、數(shù)詞等的聯(lián)結(jié)；2、聯(lián)結(jié)詞是兩個(gè)句子真值之間的聯(lián)結(jié)，而非句子的具體含義的聯(lián)結(jié)，兩個(gè)句子之間可以無(wú)任何的內(nèi)在聯(lián)系；3、聯(lián)結(jié)詞與自然語(yǔ)言之間的對(duì)應(yīng)并非一一對(duì)應(yīng)；（1）合取聯(lián)結(jié)詞“∧”對(duì)應(yīng)了自然語(yǔ)言的“既…又…”、“不僅…而且…”、“雖然…但是…”、“并且”、“和”、“與”等；（4）析取聯(lián)結(jié)詞“”對(duì)應(yīng)的是“或”、“或者”。（3）等價(jià)聯(lián)結(jié)詞“”對(duì)應(yīng)了自然語(yǔ)言中的“等價(jià)”、“當(dāng)且僅當(dāng)”、“充分必要”等；（2）蘊(yùn)涵聯(lián)結(jié)詞“→”,“P→Q”對(duì)應(yīng)了自然語(yǔ)言中的“如P則Q”、“只要P就Q”、“P僅當(dāng)Q”、“只有Q才P”、“除非Q否則P”、“沒(méi)有 Q，就沒(méi)有P”等；說(shuō)明符號(hào)化下列命題（1）四川不是人口最多的省份；（2）王超是一個(gè)德智體全面發(fā)展的好學(xué)生；（3）教室的燈不亮可能是燈管壞了或者是停電了；（4）如果周末天氣晴朗，那么學(xué)院將組織我們到石像湖春游；（5）兩個(gè)三角形全等當(dāng)且僅當(dāng)三角形的三條邊全部相等。例3.2.3設(shè)Ｐ：四川是人口最多的省份。則命題（1）可表示為┐Ｐ。設(shè)Ｐ：王超是一個(gè)思想品德好的學(xué)生；Ｑ：王超是一個(gè)學(xué)習(xí)成績(jī)好的學(xué)生；

R：王超是一個(gè)體育成績(jī)好的學(xué)生。則命題（2）可表示為Ｐ∧Ｑ∧R。設(shè)Ｐ：教室的燈不亮可能是燈管壞了Ｑ：教室的燈不亮可能是停電了則命題（3）可表示為Ｐ∨Ｑ。設(shè)Ｐ：周末天氣晴朗；Ｑ：學(xué)院將組織我們到石像湖春游。則命題（4）可表示為Ｐ→Ｑ。設(shè)Ｐ：兩個(gè)三角形全等；Ｑ：三角形的三條邊全部相等。則命題（5）可表示為ＰＱ。為了不使句子產(chǎn)生混淆，作如下約定，命題聯(lián)結(jié)詞之優(yōu)先級(jí)如下：否定→合取→析取→蘊(yùn)涵→等價(jià)同級(jí)的聯(lián)結(jié)詞，按其出現(xiàn)的先后次序(從左到右)若運(yùn)算要求與優(yōu)先次序不一致時(shí)，可使用括號(hào)；同級(jí)符號(hào)相鄰時(shí)，也可使用括號(hào)。括號(hào)中的運(yùn)算為最優(yōu)先級(jí)。約定設(shè)命題 P：明天下雨；

Q：明天下雪； R：我將去學(xué)校。符號(hào)化下述語(yǔ)句：除非明天不下雨并且不下雪，否則我將不去學(xué)校。只要明天不下雨或不下雪，我就去學(xué)校。只有明天不是雨夾雪，我才去學(xué)校。明天上午我將雨雪無(wú)阻一定去學(xué)校例3.2.4R→┐P∧┐Q

┐P∨┐Q→RR→┐(P∧Q)(P∧Q∧R)∨(┐P∧Q∧R)∨ (P∧┐Q∧R)∨(┐P∧┐Q∧R)((P∧Q)∨(┐P∧Q)∨(P∧┐Q) ∨(┐P∧┐Q))∧R例3.2.5設(shè)命題

P：你陪伴我；

Q：你代我叫車(chē)子；

R：我將出去。

符號(hào)化下述語(yǔ)句：

⑴．除非你陪伴我或代我叫車(chē)子，否則我將不出去

⑵．如果你陪伴我并且代我叫輛車(chē)子，則我將出去

⑶．如果你不陪伴我或不代我叫輛車(chē)子，我將不出去R→(P∨Q)或┐(P∨Q)→┐R(P∧Q)→R(┐P∨┐Q)→┐R3.2.3聯(lián)結(jié)詞理解難點(diǎn)（1）聯(lián)結(jié)詞“┐”是自然語(yǔ)言中的“非”、“不”和“沒(méi)有”等的邏輯抽象；（2）聯(lián)結(jié)詞“∧”是自然語(yǔ)言中的“并且”、“既…又…”、“但”、“和”等的邏輯抽象；（3）聯(lián)結(jié)詞“∨”是自然語(yǔ)言中的“或”、“或者”等邏輯抽象；但“或”有“可兼或”、“不可兼或”二種，如：張明明天早上9點(diǎn)乘飛機(jī)到北京或者到上海(不可兼或)我喜歡學(xué)習(xí)或喜歡音樂(lè)(可兼或)。（4）聯(lián)結(jié)詞“→”是自然語(yǔ)言中的“如果…，則…”，“若…，才能…”、“除非…，否則…”等的邏輯抽象。主要描述方法有：

（1）因?yàn)镻所以Q；（2）只要P就Q；（3）P僅當(dāng)Q；（4）只有Q，才P；（5）除非Q，才P；（6）除非Q，否則非P；（7）沒(méi)有Q，就沒(méi)有P。聯(lián)結(jié)詞理解難點(diǎn)如：設(shè)P：雪是白色的； Q：2+2=4。將下列命題符號(hào)化：因?yàn)檠┦前咨?，所?+2=4；如果2+2=4，則雪是白色的；只有雪是白色的，才有2+2=4；只有2+2=4，雪才是白色的；只要雪不是白色的，就有2+2=4；除非雪是白色的，否則2+2≠4；雪是白色的當(dāng)且僅當(dāng)2+2=4；P→QQ→PQ→PP→Q

P→Q

P→Q或Q→PPQ聯(lián)結(jié)詞理解難點(diǎn)在自然語(yǔ)言中，前件為假，不管結(jié)論真假，整個(gè)語(yǔ)句的意義，往往無(wú)法判斷。但在數(shù)理邏輯中，當(dāng)前件P為假時(shí)，不管Q的真假如何，則P→Q都為真。此時(shí)稱(chēng)為“善意推定”；這里要特別提醒一下“→”的含義，在自然語(yǔ)言中，條件式中前提和結(jié)論間必含有某種因果關(guān)系，但在數(shù)理邏輯中可以允許兩者無(wú)必然因果關(guān)系，也就是說(shuō)并不要求前件和后件有什么聯(lián)系；聯(lián)結(jié)詞理解難點(diǎn)（5）雙條件聯(lián)結(jié)詞“”是自然語(yǔ)言中的“充分必要條件”、“當(dāng)且僅當(dāng)”等的邏輯抽象；（6）聯(lián)結(jié)詞連接的是兩個(gè)命題真值之間的聯(lián)結(jié)，而不是命題內(nèi)容之間的連接，因此復(fù)合命題的真值只取決于構(gòu)成他們的各原子命題的真值，而與它們的內(nèi)容、含義無(wú)關(guān)，與聯(lián)結(jié)詞所連接的兩原子命題之間是否有關(guān)系無(wú)關(guān)；聯(lián)結(jié)詞理解難點(diǎn)（7）聯(lián)結(jié)詞“∧”、“∨”、“”具有對(duì)稱(chēng)性，而聯(lián)結(jié)詞“┐”、“→”沒(méi)有；（8）聯(lián)結(jié)詞“∧”、“∨”、“┐”同構(gòu)成計(jì)算機(jī)的與門(mén)、或門(mén)和非門(mén)電路是相對(duì)應(yīng)的，從而命題邏輯是計(jì)算機(jī)硬件電路的表示、分析和設(shè)計(jì)的重要工具。聯(lián)結(jié)詞理解難點(diǎn)3.2.4命題聯(lián)結(jié)詞的應(yīng)用例3.2.6

用復(fù)合命題表示如下圖所示的開(kāi)關(guān)電路：設(shè)：Ａ：開(kāi)關(guān)Ｐ閉合；Ｂ：開(kāi)關(guān)Ｑ閉合。

A∧BA∨B┐A用復(fù)合命題表示如下圖所示的邏輯電路：例3.2.7P

QP

QP解:設(shè)P：輸入端Ｐ為高電位，Q：輸入端Ｑ為高電位,則

“與門(mén)”對(duì)應(yīng)于P∧Q

“或門(mén)”對(duì)應(yīng)于P∨Q“非門(mén)”對(duì)應(yīng)于┐P3.3命題公式、解釋與真值表定義3.3.1

一個(gè)特定的命題是一個(gè)常值命題，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。而一個(gè)任意的沒(méi)有賦予具體內(nèi)容的原子命題是一個(gè)變量命題，常稱(chēng)它為命題變量(或命題變?cè)?，該命題變量無(wú)具體的真值，它的變域是集合{T，F(xiàn)}(或{0，1})當(dāng)原子命題是命題變?cè)獣r(shí)，則復(fù)合命題為命題變?cè)摹昂瘮?shù)”，且該“函數(shù)”的值仍為“真”或“假”值，這樣的函數(shù)可形象地稱(chēng)為“真值函數(shù)”,或稱(chēng)為命題公式，此命題公式?jīng)]有確切真值。3.3.1命題公式定義3.3.2(命題公式)命題變?cè)旧硎且粋€(gè)公式；如G是公式，則(┐G)也是公式；如G，H是公式，則(G∧H)、(G∨H)、(G→H)、(GH)也是公式；命題公式是僅由有限步使用規(guī)則1-3后產(chǎn)生的結(jié)果。該公式常用符號(hào)G、H、…等表示。（Ｐ∧Ｑ∧），（Ｐ→Ｑ）→等是命題公式嗎？例3.3.1

符號(hào)串：

((P∧(Q∨R))→(Q∧(┐S∨R)))；

(┐P∧Q)；(P→(┐(P∧Q)))；

(((P→Q)∧(R→Q))(P→R))。等都是命題公式。例3.3.2

符號(hào)串： (P→Q)∧┐Q)； (P→Q； (┐P∨Q∨(R；P∨Q∨。等都不是合法的命題公式。例例3.3.3試用符號(hào)形式寫(xiě)出下列命題：雖然今天天氣晴朗，老陳還是不來(lái)；除非你陪伴我或代我叫車(chē)子，否則我將不出去；停機(jī)的原因在于語(yǔ)法錯(cuò)誤或者程序錯(cuò)誤；若a和b是偶數(shù)，則a+b是偶數(shù)；我們要做到身體好、學(xué)習(xí)好、工作好，為祖國(guó)四化建設(shè)而奮斗。

P：今天天氣晴朗，Q：老陳要來(lái),則有：P∧┐QP：你陪伴我；Q：你代我叫車(chē)子；R：我出去。則有：R→P∨Q或┐P∧┐Q→┐RP：停機(jī)的原因在于語(yǔ)法錯(cuò)誤，Q：停機(jī)的原因在于程序錯(cuò)誤，則有：P∨

QP：a是偶數(shù)，Q：b是偶數(shù)，R：a+b是偶數(shù)，則有：P∧Q→RP：我們要做到身體好Q：我們要做到學(xué)習(xí)好R：我們要做到工作好S：我們要為祖國(guó)四化建設(shè)而奮斗則有：P∧Q∧R S公式(P∧(Q∨R))→(Q∧(┐S∨R))可表示如下： (P∧(Q∨R))→(Q∧(┐S∨R))P∧(Q∨R)

Q∧(┐S∨R)P

Q∨R

Q

┐S∨RQ

R

┐SRS例3.3.43.3.2公式的解釋與真值表定義3.3.3設(shè)P1、P2、…、Pn是出現(xiàn)在公式G中的所有命題變?cè)?，指定P1、P2、…、Pn一組真值，則這組真值稱(chēng)為G的一個(gè)解釋,常記為Ｉ。

一般來(lái)說(shuō)，若有ｎ個(gè)命題變?cè)瑒t應(yīng)有2n個(gè)不同的解釋。

如果公式G在解釋?zhuān)上率钦娴?，則稱(chēng)Ｉ滿(mǎn)足G；如果G在解釋?zhuān)上率羌俚?，則稱(chēng)Ｉ弄假G。定義3.3.4

將公式G在其所有可能解釋下的真值情況列成的表，稱(chēng)為G的真值表。例3.3.5求下面公式的真值表：Ｇ＝(P→((PQ)∧R))∨Q其中，Ｐ、Ｑ、Ｒ是Ｇ的所有命題變?cè)?0

0

0010

0

0

011

1

1

0000

1

011

1

1

111

0

1

11100

111

00

1111110101100011010001000GP→((PQ)∧R)((PQ)∧RPQPPQR例3.3.5（續(xù)）PQR(P→((PQ)∧R))∨Q000001010011100101110111進(jìn)一步化簡(jiǎn)為：1001110011110111111101000011110000100001例3.3.6PQ(Ｐ→Ｑ)→Ｐ

(Ｐ→Ｑ)∧Ｐ(Ｐ∧Ｑ)(Ｐ→Q)00

01

10

11

求下面這組公式的真值表： Ｇ1＝(Ｐ→Ｑ)→Ｐ；Ｇ2＝(Ｐ→Ｑ)∧Ｐ；Ｇ3＝(Ｐ∧Ｑ)(Ｐ→Q)。10110101110110100011100101100100011001100100從這三個(gè)真值表可以看到一個(gè)非常有趣的事實(shí)：公式G1對(duì)所有可能的解釋具有“真”值公式G3對(duì)所有可能的解釋均具有“假”值公式G2則具有“真”和“假”值結(jié)論定義3.3.5公式G稱(chēng)為永真公式(重言式)，如果在它的所有解釋之下都為“真”。公式G稱(chēng)為永假公式(矛盾式),如果在它的所有解釋之下都為“假”。公式G稱(chēng)為可滿(mǎn)足的，如果它不是永假的。從上述定義可知三種特殊公式之間的關(guān)系：永真式G的否定G是矛盾式；矛盾式G的否定G是永真式。永真式一定是可滿(mǎn)足式,可滿(mǎn)足式不一定是永真式可滿(mǎn)足式的否定不一定為不可滿(mǎn)足式(即為矛盾式)G是可滿(mǎn)足的當(dāng)且僅當(dāng)至少有一個(gè)解釋?zhuān)?，使G在Ｉ下為真。結(jié)論例3.3.7寫(xiě)出下列公式的真值表，并驗(yàn)證其公式是重言式、矛盾式、可滿(mǎn)足公式。（1）G1=(Ｐ→Ｑ)(Ｐ∨Ｑ)；（2）G2=(ＰQ)((Ｐ→Q)∨(Q→Ｐ))；（3）G3=(P→Q)∨Q。解PQ(Ｐ→Ｑ)(Ｐ∨Ｑ)(Ｐ

Q)((Ｐ→Q)∨(Q→Ｐ))(P→Q)∨Q001

0

1011

0

1101

0

11110

0永真公式可滿(mǎn)足公式永假公式可滿(mǎn)足公式三個(gè)公式的真值表如下：若將其看成兩個(gè)公式，分別令：

Ｇ＝Ｐ→Ｑ，Ｈ＝┐Ｐ∨Ｑ。則ＧＨ是一個(gè)永真公式，即這兩個(gè)公式對(duì)任何解釋都必同為真假，從真值的角度來(lái)說(shuō)，Ｇ和Ｈ是相等的。定義3.3.6

設(shè)G、H是公式，如果在任意解釋?zhuān)上?，G與H的真值相同，則稱(chēng)公式G與H是等價(jià)的，記作

G＝H。分析公式（1）定理3.3.1公式G與H等價(jià)的充分必要條件是公式GH是永真公式。證明:“”假定G，H等價(jià)，則G，H在其任意解釋?zhuān)上禄蛲瑸檎婊蛲瑸榧?，于是由“”的意義知，GH在其任何的解釋?zhuān)上?，其真值為“真”，即GH為永真公式?！啊奔俣ü紾H是永真公式，Ｉ是它的任意解釋?zhuān)冢上?，GH為真，因此，G、H或同為真，或同為假，由于Ｉ的任意性，故有G＝H。定理

首先，雙條件詞“”是一種邏輯聯(lián)結(jié)詞，公式GH是命題公式，其中“”是一種邏輯運(yùn)算，GH的結(jié)果仍是一個(gè)命題公式。而邏輯等價(jià)“＝”則是描述了兩個(gè)公式G與H之間的一種邏輯等價(jià)關(guān)系，G＝H表示“命題公式G的真值結(jié)果等于命題公式H的真值結(jié)果”，G＝H的結(jié)果不是命題公式。

其次，如果要求用計(jì)算機(jī)來(lái)判斷命題公式G、H是否邏輯等價(jià)，即G＝H那是辦不到的，然而計(jì)算機(jī)卻可“計(jì)算”公式GH是否是永真公式。

“＝”與“”的區(qū)別“=”的性質(zhì)由于“=”不是一個(gè)聯(lián)結(jié)詞，而是一種關(guān)系，為此，這種關(guān)系具有如下三個(gè)性質(zhì)：（1）自反性G=G；（2）對(duì)稱(chēng)性若G=H，則H=G；（3）傳遞性若G=H，H=S，則G=S。這三條性質(zhì)體現(xiàn)了“=”的實(shí)質(zhì)含義。3.3.4命題公式的基本等價(jià)關(guān)系例3.3.5

證明公式G1＝(ＰＱ)與公式G2＝(P→Q)∧(Q→P)之間是邏輯等價(jià)的。解：根據(jù)定理3.3.1，只需判定公式G3＝(ＰＱ)((P→Q)∧(Q→P))為永真公式。11100100G3＝(ＰＱ)((Ｐ→Q)∧(Q→Ｐ))PQ

1111101100

0100111111設(shè)G，H，S是任何的公式，則：基本等價(jià)公式Ｅ1：G∨(H∨S)＝(G∨H)∨S (結(jié)合律)Ｅ2:G∧(H∧S)＝(G∧H)∧SＥ3：G∨H＝H∨G (交換律)Ｅ4：G∧H＝H∧GＥ5：G∨G＝G (冪等律)Ｅ6：G∧G＝GＥ7：G∨(G∧H)＝G (吸收律)Ｅ8：G∧(G∨H)＝GＥ9：G∨(H∧S)＝(G∨H)∧(G∨S) (分配律）Ｅ10：G∧(H∨S)＝(G∧H)∨(G∧S)Ｅ11：G∨０＝G (同一律)Ｅ12：G∧１＝GＥ13：G∨１＝１ (零律)Ｅ14：G∧０＝０Ｅ15：G∨┐G＝１ (排中律)Ｅ16：G∧┐G＝０ (矛盾律)基本等價(jià)公式（續(xù)）基本等價(jià)公式（續(xù)）Ｅ17：┐(┐G)＝G (雙重否定律)Ｅ18：┐(G∨H)＝┐G∧┐H (DeMorgan定律)Ｅ19：┐(G∧H)＝┐G∨┐HＥ20：(GH)＝(G→H)∧(H→G)

(等價(jià)式)Ｅ21：(G→H)＝(┐G∨H) (蘊(yùn)涵式)E22：G→Ｈ＝Ｈ→G

(假言易位)E23：G

Ｈ＝GＨ (等價(jià)否定等式)E24：(G→Ｈ)∧(G→Ｈ)＝G

(歸謬論)這種圖是將G，H理解為某總體論域上的子集合，而規(guī)定G∧H為兩集合的公共部分（交集合），G∨H為兩集合的全部（并集合），┐G為總體論域（如矩形域）中G的補(bǔ)集，將命題中的真值“1”理解為集合中的總體論域（全集），將命題中的真值“0”理解為集合中的空集，則有：

G∧HG∨H┐GUABUABUA命題與集合之間的關(guān)系設(shè)G(P1,P2,…,Pn)是一個(gè)命題公式，其中：P1、P2、…、Pn是命題變?cè)?，G1(P1,P2,…,Pn)、G2(P1,P2,…,Pn)、...、Gn(P1,P2,…,Pn)為任意的命題公式，分別用G1、G2…、Gn取代G中的P1、P2、…、Pn后得到新的命題公式：G(G1,G2,…,Gn)＝G’(P1,P2,…,Pn)若G是永真公式（或永假公式），則G’也是一個(gè)永真公式（或永假公式）。定理3.3.2(代入定理)例3.3.6設(shè)Ｇ(Ｐ,Ｑ)＝(Ｐ∧(Ｐ→Ｑ))→Ｑ，證明公式G是一個(gè)永真公式。另有兩個(gè)任意公式： Ｈ(Ｐ,Ｑ)＝(Ｐ∨Ｑ)； Ｓ(Ｐ,Ｑ)＝(ＰＱ)。進(jìn)一步驗(yàn)證代入定理的正確性。解建立公式G的真值表如右所示?？梢?jiàn)為永真公式。PQ(Ｐ∧(Ｐ→Ｑ))→Ｑ001011101111例3.3.6（續(xù)）將Ｈ，Ｓ代入到Ｇ中分別取代G中的命題變?cè)狿、Q，所得到的公式Ｇ＇為：Ｇ＇(P,Q)=G(H,S)=(H∧(H→S))→S=((Ｐ∨Ｑ)∧((Ｐ∨Ｑ)→(ＰＱ)))→(ＰＱ)建立新公式Ｇ′(P,Q)的真值表，代入定理符合。11100100((Ｐ∨Ｑ)∧((Ｐ∨Ｑ)→(ＰＱ)))→(ＰＱ)PQ101110101001101010111001110111111001定理3.3.3(替換定理)設(shè)G1是G的子公式(即G1是公式G的一部分)，H1是任意的命題公式，在G中凡出現(xiàn)G1處都以H1替換后得到新的命題公式H，若G1＝H1，則G＝H。利用24個(gè)基本等價(jià)公式及代入定理和替換定理，可完成公式的轉(zhuǎn)化和等價(jià)判定。例3.3.7利用基本的等價(jià)關(guān)系，完成如下工作：（1）判斷公式的類(lèi)型：證明((Ｐ∨Ｑ)∧(Ｐ∧(Ｑ∨Ｒ)))∨ (Ｐ∧Ｑ)∨(Ｐ∧Ｒ)是一個(gè)永真公式。（2）證明公式之間的等價(jià)關(guān)系：證明Ｐ→(Ｑ→Ｒ)=(Ｐ∧Ｑ)→Ｒ（3）化簡(jiǎn)公式：證明(P∧(Ｑ∧R))∨((Ｑ∧R)∨(P∧R))=R證明（1）((Ｐ∨Ｑ)∧(Ｐ∧(Ｑ∨Ｒ)))∨(Ｐ∧Ｑ)∨(Ｐ∧Ｒ)=((Ｐ∨Ｑ)∧(Ｐ∨(Ｑ∧Ｒ)))∨((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))=((Ｐ∨Ｑ)∧((Ｐ∨Ｑ)∧(Ｐ∨Ｒ)))∨((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))=((Ｐ∨Ｑ)∧(Ｐ∨Ｑ)∧(Ｐ∨Ｒ))∨((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))=((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))∨((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))=T

即:((Ｐ∨Ｑ)∧(Ｐ∧(Ｑ∨Ｒ)))∨(Ｐ∧Ｑ)∨(Ｐ∧Ｒ)為永真公式；

┐(G∨H)＝┐G∧┐H┐(G∧H)＝┐G∨┐HG∨(H∧S)＝(G∨H)∧(G∨S)G∧(H∨S)＝(G∧H)∨(G∧S)排中律G∨┐G＝１

冪等律G∨G＝G G∧G＝G證明(續(xù))（2）要證P→(Q→R)=(P∧Q)→R；

P→(Q→R)=P∨(Q→R)=P∨(Q∨R)=(P∨Q)∨R=(P∧Q)∨R=(P∧Q)→R（3）要證

(P∧(Q∧R))∨((Q∧R)∨(P∧R))=R

(P∧(Q∧R))∨((Q∧R)∨(P∧R))=(P∧Q)∧R)∨((Q∨P)∧R)=((P∨Q)∧R)∨((Q∨P)∧R)=((P∨Q)∨(Q∨P))∧R=T∧R=R蘊(yùn)含式(G→H)＝(┐G∨H)

3.3.5命題公式的難點(diǎn)命題公式和命題不同，它是一個(gè)公式，無(wú)具體的真值可言，只有當(dāng)給予公式中的每個(gè)命題變?cè)跃唧w的真值指派，公式才有具體的真值；命題公式之間的等價(jià)聯(lián)結(jié)詞“”和等價(jià)關(guān)系“＝”之間是兩個(gè)完全不同的概念，前者是一種運(yùn)算，后者是一種關(guān)系，兩個(gè)公式之間，通過(guò)聯(lián)結(jié)詞“”的運(yùn)算以后，仍然是一個(gè)命題公式，但等價(jià)關(guān)系“＝”只能將一個(gè)命題公式轉(zhuǎn)化成與之等價(jià)的另一個(gè)命題公式，“＝”是不可計(jì)算的；命題公式的難點(diǎn)對(duì)于24個(gè)基本的等價(jià)公式，如果將運(yùn)算“﹁”、“∧”、“∨”分別對(duì)應(yīng)于集合中的運(yùn)算“￣”、“∩”、“∪”，真值“1”、“0”分別對(duì)應(yīng)于集合中的全集“U”和空集“”，則集合中的19個(gè)基本的等價(jià)公式對(duì)應(yīng)于命題的公式E1到E19，E20到E24是命題邏輯中所特有的公式，重點(diǎn)要求記住E20和E21。只有熟練地掌握這24個(gè)基本的等價(jià)公式，并且對(duì)聯(lián)結(jié)詞“∧”、“∨”注意用括號(hào)來(lái)標(biāo)識(shí)其優(yōu)先級(jí)別，才能正確地加以應(yīng)用。3.3.6命題公式的應(yīng)用例3.3.8

利用基本的等價(jià)關(guān)系，化簡(jiǎn)下列電路圖&&≥1≥1&TSRQPRPSQPSPQRP解：上述電路圖可描述為：（1）((P∧Q∧R)∨(P∧Q∧S))∧((P∧R)∨(P∧S))（2）((P∧Q∧R)∨(P∨Q∨S))∧(P∧S∧T)例3.3.8利用21個(gè)基本等價(jià)關(guān)系，化簡(jiǎn)公式(1)、(2)可得：（1）((P∧Q∧R)∨(P∧Q∧S))∧((P∧R)∨(P∧S))=((P∧Q∧(R∨S))∧(P∧(R∨S))=P∧Q∧(R∨S)；（2）((P∧Q∧R)∨(P∨Q∨S))∧(P∧S∧T)=(P∨Q∨S)∧(P∧S∧T)=P∧S∧T。SRQPPTS&

吸收律G∨(G∧H)＝G G∧(G∨H)＝G

例3.3.9將下面程序語(yǔ)言進(jìn)行化簡(jiǎn)。IfAthenifBthenXelseYelseifBthenXelseY

TFFTFTStartAXYEndBB

解：執(zhí)行X的條件為：

(Ａ∧Ｂ)∨(Ａ∧Ｂ)執(zhí)行Y的條件為：

(Ａ∧Ｂ)∨(Ａ∧Ｂ)例3.3.9(續(xù)）執(zhí)行X的條件可化簡(jiǎn)為：(Ａ∧Ｂ)∨(Ａ∧Ｂ)＝Ｂ∧(Ａ∨Ａ)＝Ｂ執(zhí)行Y的條件可化簡(jiǎn)為：(Ａ∧Ｂ)∨(Ａ∧Ｂ)＝Ｂ∧(Ａ∨Ａ)＝ＢTXYEndStartBF程序可簡(jiǎn)化為：IfBthenXelseY

例3.3.10

從前，有一個(gè)邏輯學(xué)家被關(guān)在大牢，有一天，國(guó)王對(duì)邏輯學(xué)家說(shuō)：“聽(tīng)說(shuō)你智慧過(guò)人，我給你一個(gè)機(jī)會(huì)，這個(gè)大牢有兩個(gè)門(mén)，有兩個(gè)戰(zhàn)士守著，其中一個(gè)人說(shuō)的是真話，另一個(gè)人說(shuō)的是假話，這兩個(gè)門(mén)，一個(gè)是生門(mén)，一個(gè)是死門(mén)，你只能問(wèn)兩個(gè)戰(zhàn)士中的一個(gè)，而且只能問(wèn)一句話，如果你能通過(guò)生門(mén)出去，我就放了你，否則……嘿嘿……”請(qǐng)問(wèn)：邏輯學(xué)家該怎樣回答？

邏輯學(xué)家沉思片刻，即向一戰(zhàn)士發(fā)問(wèn)，然后開(kāi)門(mén)從容離去。該邏輯學(xué)家應(yīng)如何發(fā)問(wèn)？解邏輯學(xué)家手指一門(mén)問(wèn)身旁的一名戰(zhàn)士說(shuō):“這扇門(mén)是死亡門(mén)，他(指另一名戰(zhàn)士)將回答‘是’,對(duì)嗎？”

當(dāng)被問(wèn)戰(zhàn)士回答“對(duì)”,則邏輯學(xué)家開(kāi)啟所指的門(mén)從容離去。當(dāng)被問(wèn)的戰(zhàn)士回答“否”,則邏輯學(xué)家開(kāi)啟另一扇門(mén)從容離去。

PQRS

0011

0100

1001

1110邏輯學(xué)家能夠從容離去嗎？P:被問(wèn)戰(zhàn)士是誠(chéng)實(shí)人；Q:被問(wèn)戰(zhàn)士的回答是“是”R:另一名戰(zhàn)士的回答是“是”S:這扇門(mén)是死亡門(mén)。例3.3.11一家航空公司，為了保證安全，用計(jì)算機(jī)復(fù)核飛行計(jì)劃。每臺(tái)計(jì)算機(jī)能給出飛行計(jì)劃正確或有誤的回答。由于計(jì)算機(jī)也有可能發(fā)生故障，因此采用三臺(tái)計(jì)算機(jī)同時(shí)復(fù)核。由所給答案，再根據(jù)“少數(shù)服從多數(shù)”的原則作出判斷，試將結(jié)果用命題公式表示，并加以簡(jiǎn)化，畫(huà)出電路圖。解設(shè)C1，C2，C3分別表示三臺(tái)計(jì)算機(jī)的答案。S表示判斷結(jié)果。

C1C2C3

S

000

0

001

0

010

0

011

1

100

0

1011

110

1

111

1真值表則根據(jù)真值表，利用聯(lián)結(jié)詞的定義，S可用C1，C2，C3所對(duì)應(yīng)的命題公式表示出來(lái)，同時(shí)可畫(huà)出該命題公式所對(duì)應(yīng)的電路圖。解(續(xù))S=(C1∧C2∧C3)∨(C1∧C2∧C3)∨(C1∧C2∧C3)∨(C1∧C2∧C3)=((C1∨C1)∧C2∧C3)∨(C1∧(C2∨C2)∧C3)∨(C1∧C2∧(C3∨C3))(冪等、交換、分配)=(C2∧C3)∨(C1∧C3)∨(C1∧C2)C1C2C3S&&&≥1≥1只要C1，C2，C3中有兩個(gè)一樣的取值，那么S就為該值3.5公式的標(biāo)準(zhǔn)型——范式3.5.1析取范式和合取范式定義3.5.1

（1）命題變?cè)蛎}變?cè)姆穸ǚQ(chēng)為文字（2）有限個(gè)文字的析取稱(chēng)為析取式(也稱(chēng)為子句）（3）有限個(gè)文字的合取稱(chēng)為合取式(也稱(chēng)為短語(yǔ)）（4）P與

P稱(chēng)為互補(bǔ)對(duì)。例（1）Ｐ、Ｐ是文字；（2）Ｐ∨Ｑ∨Ｒ是子句；（3）Ｐ∧Ｑ∧Ｒ是短語(yǔ)。┐P是一個(gè)子句，這種說(shuō)法正確么？一個(gè)命題變?cè)蛘咂浞穸瓤梢允呛?jiǎn)單的子句，也可以是簡(jiǎn)單的短語(yǔ)。因此，Ｐ，Ｐ不但是文字，也是子句、短語(yǔ)

定義3.5.2（1）有限個(gè)短語(yǔ)的析取式稱(chēng)為析取范式（2）有限個(gè)子句的合取式稱(chēng)為合取范式一個(gè)不含最外層括號(hào)的短語(yǔ)或子句既是是析取范式，也是合取范式。Ｐ、Ｐ是析取范式、合取范式；Ｐ∨Ｑ∨Ｒ是子句、析取范式、合取范式，(Ｐ∨Ｑ∨Ｒ)僅是子句、合取范式；Ｐ∧Ｑ∧Ｒ是短語(yǔ)、析取范式、合取范式，(Ｐ∧Ｑ∧Ｒ)僅是短語(yǔ)、析取范式；(Ｐ∧Ｑ)∨(Ｐ∧Ｑ)是析取范式；(Ｐ∨Ｑ)∧(Ｐ∨Ｑ)是合取范式；句子Ｐ∨(Ｑ∨Ｒ)、(Ｑ∨Ｒ)即不是析取范式也不是合取范式例總結(jié)單個(gè)的文字是子句、短語(yǔ)、析取范式，合取范式單個(gè)的子句是合取范式；單個(gè)的短語(yǔ)是析取范式；若單個(gè)的子句或短語(yǔ)無(wú)最外層括號(hào)，則它既是析取范式又是合取范式；析取范式、合取范式僅含聯(lián)結(jié)詞集{，∧，∨}“”聯(lián)結(jié)詞僅出現(xiàn)在命題變?cè)?。范式的求解方法定?.5.1

對(duì)于任意命題公式，都存在與其等價(jià)的析取范式和合取范式。轉(zhuǎn)換方法：（1）利用等價(jià)公式中的蘊(yùn)涵式和等價(jià)式將公式中的→、用聯(lián)結(jié)詞、∧、∨來(lái)取代，這可利用如下等價(jià)關(guān)系：

(Ｇ→Ｈ)=(Ｇ∨Ｈ)；(ＧＨ)=(Ｇ→Ｈ)∧(Ｈ→Ｇ)=(Ｇ∨Ｈ)∧(Ｈ∨Ｇ)。范式的求解方法(續(xù))（2）重復(fù)使用德摩根定律將否定號(hào)移到各個(gè)命題變?cè)那岸?，并消去多余的否定?hào)，這可利用如下等價(jià)關(guān)系：(Ｇ)=Ｇ；

(Ｇ∨Ｈ)=Ｇ∧Ｈ；

(Ｇ∧Ｈ)=Ｇ∨Ｈ。（3）重復(fù)利用分配定律，可將公式化成一些合取式的析取，或化成一些析取式的合取，這可利用如下等價(jià)關(guān)系：Ｇ∨(Ｈ∧Ｓ)=(Ｇ∨Ｈ)∧(Ｇ∨Ｓ)；Ｇ∧(Ｈ∨Ｓ)=(Ｇ∧Ｈ)∨(Ｇ∧Ｓ)。例3.5.1求公式：(Ｐ→Ｑ)∨(ＰR)的析取范式和合取范式解

(Ｐ→Ｑ)∨(ＰR)=(Ｐ∨Ｑ)∨((Ｐ∨R)∧(R∨P))=((Ｐ∨Ｑ)∨(Ｐ∨R)) ∧((Ｐ∨Ｑ)∨(R∨P))=(Ｐ∨Ｑ∨Ｐ∨R)∧(Ｐ∨Ｑ∨

R∨P）

=(Ｐ∨Ｑ∨R) ——合取范式=Ｐ∨Ｑ∨R ——析取范式

范式的不惟一性考慮公式：(Ｐ∨Ｑ)∧(Ｐ∨Ｒ)，其與之等價(jià)的析取范式： Ｐ∨(Ｑ∧Ｒ)； (Ｐ∧Ｐ)∨(Ｑ∧Ｒ)； Ｐ∨(Ｑ∧Ｑ)∨(Ｑ∧Ｒ)； Ｐ∨(Ｐ∧Ｒ)∨(Ｑ∧Ｒ)。這種不惟一的表達(dá)形式給研究問(wèn)題帶來(lái)了不便。3.5.2主析取范式和主合取范式1.極小項(xiàng)和極大項(xiàng)定義3.5.3

在含有n個(gè)命題變?cè)狿1、P2、P3、…、Pn的短語(yǔ)或子句中，若每個(gè)命題變?cè)c其否定不同時(shí)存在，但二者之一恰好出現(xiàn)一次且僅一次，則稱(chēng)此短語(yǔ)或子句為關(guān)于P1、P2、P3、…、Pn的一個(gè)極小項(xiàng)或極大項(xiàng)。對(duì)于n個(gè)命題變?cè)?，可?gòu)成2n個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng)（1）一個(gè)命題變?cè)狿，對(duì)應(yīng)的極小項(xiàng)有兩項(xiàng)：P、

P；極大項(xiàng)有兩項(xiàng)：P、

P。（2）兩個(gè)命題變?cè)狿、Q，對(duì)應(yīng)的極小項(xiàng)有四項(xiàng)：P∧Q、

P∧Q、P∧Q、

P∧Q；極大項(xiàng)有四項(xiàng)：P∨Q、

P∨Q、P∨Q、

P∨Q。例（3）三個(gè)命題變?cè)狿、Q、R，對(duì)應(yīng)的極小項(xiàng)有八項(xiàng)：

Ｐ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧ＲＰ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧ＲＰ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧Ｒ；極大項(xiàng)有八項(xiàng)：

Ｐ∨Ｑ∨Ｒ、Ｐ∨Ｑ∨ＲＰ∨Ｑ∨Ｒ、Ｐ∨Ｑ∨Ｒ、Ｐ∨Ｑ∨ＲＰ∨Ｑ∨Ｒ、Ｐ∨Ｑ∨Ｒ、Ｐ∨Ｑ∨Ｒ。例(續(xù))兩個(gè)命題變?cè)乃鶎?duì)應(yīng)極小項(xiàng)真值表

PQ┐P∧┐Q┐P∧Q

P∧┐Q

P∧Q

001000

010100

100010

110001注意：（1）沒(méi)有等價(jià)的兩個(gè)極小項(xiàng)；（2）使該極小項(xiàng)的真值為真的指派是唯一的；（3）使極小項(xiàng)為真的那組指派為對(duì)應(yīng)極小項(xiàng)的編碼；（4）命題變?cè)c1對(duì)應(yīng)，命題變?cè)姆穸ㄅc0對(duì)應(yīng)。

Ｐ∧Ｑ→{0、0}為真→{00}→m00(m0)Ｐ∧Ｑ→{0、1}為真→{01}→m01(m1)Ｐ∧Ｑ→{1、0}為真→{10}→m10(m2)Ｐ∧Ｑ→{1、1}為真→{11}→m11(m3)兩個(gè)命題變?cè)乃鶎?duì)應(yīng)極大項(xiàng)真值表PQ┐P∨┐Q┐P∨QP∨┐QP∨Q001

110011

101101

011110

111注意：（1）沒(méi)有等價(jià)的兩個(gè)極大項(xiàng)；（2）使該極大項(xiàng)的真值為假的指派是唯一的；（3）使極大項(xiàng)為假的那組指派為對(duì)應(yīng)極大項(xiàng)的編碼；（4）命題變?cè)c0對(duì)應(yīng)，命題變?cè)姆穸ㄅc1對(duì)應(yīng)。Ｐ∨Ｑ→{0、0}為假→{00}→M00(M0)Ｐ∨Ｑ→{0、1}為假→{01}→M01(M1)Ｐ∨Ｑ→{1、0}為假→{10}→M10(M2)Ｐ∨Ｑ→{1、1}為假→{11}→M11(M3)三個(gè)命題變?cè)臉O小項(xiàng)和極大項(xiàng)PQR極小項(xiàng)極大項(xiàng)000m0=┐P∧┐Q∧┐RM0=P∨Q∨R001m1=┐P∧┐Q∧RM1=P∨Q∨┐R010m2=┐P∧Q∧┐RM2=P∨┐Q∨R011m3=┐P∧Q∧RM3=P∨┐Q∨┐R100m4=P∧┐Q∧┐RM4=┐P∨Q∨R101m5=P∧┐Q∧RM5=┐P∨Q∨┐R110m6=P∧Q∧┐RM6=┐P∨┐Q∨R111m7=P∧Q∧RM7=┐P∨┐Q∨┐R任意兩個(gè)不同極小項(xiàng)的合取必為假；任意兩個(gè)不同極大項(xiàng)的析取必為真；極大項(xiàng)的否定是極小項(xiàng)；極小項(xiàng)的否定是極大項(xiàng)；所有極小項(xiàng)的析取為永真公式；所有極大項(xiàng)的合取是永假公式。mi∧mj=F,i≠j極小項(xiàng)和極大項(xiàng)的性質(zhì)Mi=┐miMi∨Mj=T,i≠j

┐Mi=

mi2主析取范式和主合取范式定義3.5.4

在給定的析取范式中，每一個(gè)短語(yǔ)都是極小項(xiàng)，則稱(chēng)該范式為主析取范式在給定的合取范式中，每一個(gè)子句都是極大項(xiàng)，則稱(chēng)該范式為主合取范式如果一個(gè)主析取范式不包含任何極小項(xiàng)，則稱(chēng)該主析取范式為“空”；如果一個(gè)主合取范式不包含任何極大項(xiàng)，則稱(chēng)主合取范式為“空”。定理3.5.2任何一個(gè)公式都有與之等價(jià)的主析取范式和主合取范式。證明：（1）利用定理3.5.1先求出該公式所對(duì)應(yīng)的析取范式和合取范式；（2）在析取范式的短語(yǔ)和合取范式的子句中，如同一命題變?cè)霈F(xiàn)多次，則將其化成只出現(xiàn)一次；（3）去掉析取范式中所有永假式的短語(yǔ)和合取范式中所有永真式的子句，即去掉含有形如P∧┐P子公式的短語(yǔ)和含有形如P∨┐P子公式的子句；證明(續(xù)1)（4）若析取范式的某一個(gè)短語(yǔ)中缺少該命題公式中所規(guī)定的命題變?cè)?，則可用公式：(Ｐ∨┐Ｐ)∧Q=Q將命題變?cè)狿補(bǔ)進(jìn)去，并利用分配律展開(kāi)，然后合并相同的短語(yǔ)，此時(shí)得到的短語(yǔ)將是標(biāo)準(zhǔn)的極小項(xiàng)；若合取范式的某一個(gè)子句中缺少該命題公式中所規(guī)定的命題變?cè)?，則可用公式：(Ｐ∧┐Ｐ)∨Q=Q將命題變?cè)狿補(bǔ)進(jìn)去，并利用分配律展開(kāi)，然后合并相同的子句，此時(shí)得到的子句將是標(biāo)準(zhǔn)的極大項(xiàng)；證明(續(xù)2)（5）利用冪等律將相同的極小項(xiàng)和極大項(xiàng)合并，同時(shí)利用交換律進(jìn)行順序調(diào)整，由此可轉(zhuǎn)換成標(biāo)準(zhǔn)的主析取范式和主合取范式。證明該定理的過(guò)程，實(shí)際上就是求一個(gè)公式的主析取范式和主合取范式的方法，將該方法稱(chēng)為等價(jià)公式轉(zhuǎn)換法。需要說(shuō)明求任何一個(gè)公式的主析取范式和主合取范式不僅要取決于該公式，而且取決于該公式所包含的命題變?cè)Ｈ绻剑?/p>

G1(P,Q)=(P→Q)∧Q，G2(P,Q,R)=(P→Q)∧Q。前者是依賴(lài)于兩個(gè)命題變?cè)?，后者?yīng)依賴(lài)于三個(gè)命題變?cè)?求主析取范式和主合取范式的方法主范式真值表技術(shù)對(duì)公式的真值結(jié)果進(jìn)行分解，分解成等價(jià)的極小項(xiàng)的析取或者極大項(xiàng)的合取公式轉(zhuǎn)換法利用基本等價(jià)公式進(jìn)行變換定理3.5.2例3.5.2利用等價(jià)公式轉(zhuǎn)換法求公式(P→Q)→(Q∧R)的主析取范式和主合取范式。解

（1）求主析取范式(P→Q)→(Q∧R)=(P∨Q)∨(Q∧R)＝(P∧Q)∨(Q∧R)——析取范式=(P∧Q∧(R∨R))∨((P∨P)∧Q∧R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)——主析取范式例3.5.2（續(xù)）（2）求主合取范式(P→Q)→(Q∧R)=(P∧Q)∨(Q∧R)

=(P∨Q)∧(P∨R)∧(Q∨Q)∧(Q∨R)=(P∨Q)∧(P∨R)∧(Q∨R) ——合取范式=(P∨Q∨(R∧R))∧(P∨(Q∧Q)∨R)∧ ((P∧P)∨Q∨R)=(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧((P∨Q∨R)∧(P∨Q∨R)=(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)——主合取范式

我們已經(jīng)學(xué)會(huì)使用公式轉(zhuǎn)換法，那么用真值表技術(shù)又如何求解主范式呢？如何用極小項(xiàng)來(lái)構(gòu)成主析取范式？

PQm0m1

m2m3P→Q備注0010001010100110001001100011m1必須包含在主析取范式中m0必須包含在主析取范式中m3必須包含在主析取范式中m2一定不能包含在主析取范式中主析取范式中必須且只能包含使得公式真值為真的那些解釋對(duì)應(yīng)的極小項(xiàng)。如何用極大項(xiàng)來(lái)構(gòu)成主合取范式？PQM0M1M2M3PQ備注0001111011011010110101111101M1必須包含在主合取范式中M2必須包含在主合取范式中M0一定不能包含在主合取范式中M3一定不能包含在主合取范式中主合取范式中必須且只能包含使得公式真值為假的那些解釋對(duì)應(yīng)的極大項(xiàng)。例3.5.3求公式G=(Ｐ→Ｑ)Ｒ的主析取范式和主合取范式。解：首先列出其真值表：PQRP→Q(P→Q)R00010001110101001111100011010011010111111)、求公式的主析取范式PQR(P→Q)R00000011010001111001101011001111P∧Ｑ∧ＲP∧Ｑ∧ＲP∧Ｑ∧ＲP∧Ｑ∧Ｒ00001000000001000010000000000001將極小項(xiàng)全部進(jìn)行析取后，可得到相應(yīng)的主析取范式：G=(Ｐ→Ｑ)Ｒ=(┐P∧┐Ｑ∧Ｒ)∨(┐P∧Ｑ∧Ｒ)∨ (Ｐ∧┐Ｑ∧┐Ｒ)∨(Ｐ∧Ｑ∧Ｒ)2)、求公式的主合取范式PQR(P→Q)R00000011010001111001101011001111P∨Ｑ∨ＲP∨Ｑ∨ＲP∨Ｑ∨ＲP∨Ｑ∨Ｒ0