離散數(shù)學第3章命題邏輯

離散數(shù)學電子科技大學計算機科學與工程學院主講教師 王慶先Tel：

QQ:6176754242021年7月3日星期六Logic）是研究演繹推理2021/7/3數(shù)理邏輯（Mathematical的一門學科；它的主要研究內(nèi)容是推理，特別著重于推理過程是否正確；它不是研究某個特定的語句是否正確，而是著重于語句之間的關(guān)系。它的主要研究方法是采用數(shù)學的方法來研究數(shù)學推理、數(shù)學性質(zhì)和數(shù)學基礎(chǔ)；而所謂數(shù)學方法就是引進一套符號體系的方法，所以數(shù)理邏輯又叫符號邏輯（Symbolic Logic）。第二篇數(shù)理邏輯什么是數(shù)理邏輯？用數(shù)學的方法來研究推理的規(guī)律統(tǒng)稱為數(shù)理邏輯。為什么要研究數(shù)理邏輯？程序＝算法＋數(shù)據(jù)算法＝邏輯＋控制2021/7/3總結(jié)第二篇 數(shù)理邏輯命題邏輯命題的基本概念命題聯(lián)結(jié)詞命題公式

命題的范式命題邏輯推理理論主要

研究內(nèi)容謂詞邏輯謂詞的基本概念謂詞公式公式的標準型謂詞邏輯推理理論推理與證明技術(shù)定理證明的方法數(shù)學歸納法按定義證明法2021/7/3第3章 命題邏輯2021/7/3命題邏輯也稱命題演算，或語句邏輯。它研究以命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導關(guān)系，研究什么是命題？如何表示命題？如何由一組前提推導一些結(jié)論？命題邏輯的特征：在研究邏輯的形式時，我們把一個命題只分析到其中所含的命題成份為止，不再分析下去。不把一個簡單命題再分析為非命題的集合，不把謂詞和量詞等非命題成份分析出來。3.0內(nèi)容提要命題公式3命題范式4命題基本概念1集合命的題表聯(lián)示結(jié)方詞法2命題邏輯推理理論2021/7/353.1本章學習要求重點掌握一般掌握了解11、五種基本聯(lián)結(jié)詞2、24個基本的等價公式

3、掌握求命題范式的方法

4、掌握命題邏輯的推理規(guī)則和公理3聯(lián)結(jié)詞的完備集的理解和學習22021/7/3公式的代入規(guī)則和替換規(guī)則3.2.1命題定義3.2.1

具有確切真值的陳述句稱為命題,該命題可以取一個“值”，稱為真值。真值只有“真”和“假”兩種，分別用“Ｔ”(或“１”)和“Ｆ”(或“0”)表示。3.2命題與命題聯(lián)結(jié)詞真假含義2021/7/3太陽是圓的；成都是一個旅游城市；北京是中國的首都；1＋1＝10；我喜歡踢足球；3能被2整除；地球外的星球上也有人；中國是世界上人口最多的國家；今天是晴天；ｘ+y>0；2021/7/3例3.2.1TTTT/FT/FFT/FTT非命題例3.2.1(續(xù))把門關(guān)上；滾出去！你要出去嗎？今天天氣真好啊！本語句是假的。非命題非命題非命題非命題非命題悖論2021/7/3說明注意：一切沒有判斷內(nèi)容的句子都不能作為命題，如命令句、感嘆句、疑問句、祈使句、二義性的陳述句等。約定：在數(shù)理邏輯中像字母“x”、“y”、“z”等字母總是表示變量。結(jié)論：命題一定是陳述句，但并非一切陳述句都是命題。命題的真值有時可明確給出，有時還需要依靠環(huán)境、條件、實際情況時間才能確定其真值。四川不是一個國家；3既是素數(shù)又是奇數(shù)；張謙是大學生或是運動員；如果周末天氣晴朗，則我們將到郊外旅游；2+2=4當且僅當雪是白的。2021/7/3例3.2.2一般來說，命題可分兩種類型：原子命題(簡單命題)：不能再分解為更為簡單命題的命題。復合命題：可以分解為更為簡單命題的命題。而且這些簡單命題之間是通過如“或者”、“并且”、“不”、“如果...則...”、“當且僅當”等這樣的關(guān)聯(lián)詞和標點符號復合而構(gòu)成一個復合命題。2021/7/3命題的分類例3.2.3今天天氣很冷。今天天氣很冷并且刮風。今天天氣很冷并且刮風，但室內(nèi)暖和。通常用大寫的帶或不帶下標的英文字母Ａ、Ｂ、Ｃ、...P、Q、R、...

Ai、Bi

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

設(shè)P是任一命題，復合命題“非P”(或“P的否定”)稱為P的否定式(Negation)，記作

P，“”為否定聯(lián)結(jié)詞。若則P：四川是一個國家。

P：四川不是一個國家。PPO11OP為真當且僅當P為假。2021/7/3合取聯(lián)結(jié)詞定義3.2.3

設(shè)P、Q是任兩個命題，復合命題“P并且

Q”(

或

“

P

和

Q”)

稱

為

P

與

Q

的

合

取

式(Conjunction)，記作P∧Q，“∧”為合取聯(lián)結(jié)詞。P∧Q為真當且僅當P，Q同為真。若 P：3是素數(shù)； Q：3是奇數(shù)。則 P∧Q：3既是素數(shù)又是奇數(shù)。PQP∧QOOOO1O1OO1112021/7/3析取聯(lián)結(jié)詞PQP∨QOOOO111O1111定義3.2.4

設(shè)P、Q是任兩個命題，復合命題“P或者Q”稱為P與Q的析取式(Disjunction)，記作P∨Q，“∨”為析取聯(lián)結(jié)詞。P∨Q為真當且僅當P，Q中至少一個為真。若 P：張謙是大學生；Q：張謙是運動員。則 P∨Q：張謙是大學生或是運動員。張三是一班或二班的學生。2021/7/3蘊涵聯(lián)結(jié)詞P→Q為假當且僅當P為真且Q為假。定義3.2.5設(shè)P、Q是任兩個命題，復合命題“如果P，則Q”稱為P與Q的蘊涵式(Implication)，記作P→Q，“→”稱為蘊涵聯(lián)結(jié)詞，P稱為蘊涵式的前件，Q稱為蘊涵式的后件。若P：周末天氣晴朗；Q：我們將到郊外旅游。則P→Q：如果周末天氣晴朗，則我們將郊外旅游。PQP→QOO1O111OO1112021/7/3等價聯(lián)結(jié)詞定義3.2.6設(shè)P、Q是任兩個命題，復合命題“P當且僅當Q”稱為P與Q的等價式(Enuivalence)，記作

P?Q，“?”稱為等價聯(lián)結(jié)詞。P?Q為真當且僅當P、Q同為真假。若P：2+2=4；Q：雪是白的。則P?Q：2+2=4當且僅當雪是白的。PQP

?

QOO1O1O1OO1112021/7/3總結(jié)聯(lián)結(jié)詞記號復合命題記法讀法真值結(jié)果否定┐A是不對的┐A非A┐A為真當且僅當A為假合取∧A并且BA∧BA合取BA∧B為真當且僅當A,B同為真析取∨A或者BA∨BA析取BA∨B為真當且僅當A,B中至少一個為真蘊涵→若A，則BA→BA蘊涵BA→B為假當且僅當A為真B為假等價?A當且僅當BA?

BA等價于BA?B為真當且僅當A,B同為真假2021/7/3說明2021/7/31、聯(lián)結(jié)詞是句子與句子之間的聯(lián)結(jié)，而非單純的名詞、形容詞、數(shù)詞等地聯(lián)結(jié)；2、聯(lián)結(jié)詞是兩個句子真值之間的聯(lián)結(jié)，而非句子的具體含義的聯(lián)結(jié)，兩個句子之間可以無任何地內(nèi)在聯(lián)系；3、聯(lián)結(jié)詞與自然語言之間的對應(yīng)并非一一對應(yīng)；合取聯(lián)結(jié)詞“∧”對應(yīng)了自然語言的“既…又…”、“不僅…而且…”、“雖然…但是…”、“并且”、“和”、“與”等；蘊涵聯(lián)結(jié)詞“→”,“P→Q”對應(yīng)了自然語言中的“如P則Q”、“只要P就Q”、“P僅當Q”、“只有Q才P”、“除非Q否則P”等；等價聯(lián)結(jié)詞“?”對應(yīng)了自然語言中的“等價”、“當且僅當”、“充分必要”等；析取聯(lián)結(jié)詞“”對應(yīng)的是相容（可兼）的或。2021/7/3說明例設(shè)設(shè)Ｐ3Ｐ.：2：.四王4川超是是人一口個最思多想的品省德份好。的學生；則命Ｑ題：（王1）超可是表一示個為學┐習Ｐ成。績好的學生；符號設(shè)化ＰR下：：列王教命超室題是的一燈個不體育亮成可績能好是的燈學管生壞。了（1則）命Ｑ四題：川（教不2是）室人可的口表燈最示不多為亮的Ｐ可省∧能份Ｑ；∧是R停。電了則命題（3）可表示為Ｐ∨Ｑ。設(shè)Ｐ：周末天氣晴朗；（2）Ｑ王：超學是一院個將德組智織體我全們面到發(fā)展石的像好湖學春生游；。（3則）命教題室（的燈4）不可亮表可能示是為燈Ｐ管→壞Ｑ了?；蛘呤峭ｋ娏耍辉O(shè)Ｐ：兩個三角形全等；Ｑ如：果三周末角天形氣的晴三朗條，邊那全么學部院相將等組。織我們到石則像命湖題春（游5；）可表示為Ｐ?Ｑ。兩個三角形全等當且僅當三角形的三條邊全部相等。2021/7/3為了不使句子產(chǎn)生混淆，作如下約定，命題聯(lián)結(jié)詞之優(yōu)先級如下：否定→合取→析取→蘊涵→等價同級的聯(lián)結(jié)詞（合取與析取，蘊涵與等價）按其出現(xiàn)的先后次序(從左到右)若運算要求與優(yōu)先次序不一致時，可使用括號；同級符號相鄰時，也可使用括號。括號中的運算為最優(yōu)先級。2021/7/3約

定設(shè)命題P：明天上午七點下雨；

Q：明天上午七點下雪；R：我將去學校。符號化下述語句：學校如果明天上午七點下雨或下雪，則我將不去學校明天上午七點我將雨雪無阻一定去學校例3.2.5(P∨Q)→┐R2.如果明天上午(P七∧點Q∧不R下)雨∨并(┐且P不∧下Q雪∧，R)則∨我將去(P∧┐Q∧R)∨(┐P∧┐Q∧R)((P∧Q)∨(┐P∧Q)∨(P∧┐┐(PQ∧)

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

P∧┐Q)→R1.如果明天上午七點不是雨夾雪，則我將去學校2021/7/3例3.2.6設(shè)命題P：你陪伴我；Q：你代我叫車子；

R：我將出去。符號化下述語句：⑴．除非你陪伴我或代我叫車子，否則我將不出去⑵．如果你陪伴我并且代我叫輛車子，則我將出去⑶．如果你不陪伴我或不代我叫輛車子，我將不出去R→(P∨Q)或

┐(P∨Q)→┐R(P∧Q)→R(┐P∨┐Q)→┐R2021/7/33.2.3

聯(lián)結(jié)詞理解難點2021/7/3（1）聯(lián)結(jié)詞“┐”是自然語言中的“非”、“不”和

“沒有”等的邏輯抽象；（2）聯(lián)結(jié)詞“∧”是自然語言中的“并且”、“既…又…”、“但”、“和”等的邏輯抽象；（3）聯(lián)結(jié)詞“∨”是自然語言中的“或”、“或者”等邏輯抽象；但“或”有“可兼或”、“不可兼或”二種，如：張明明天早上9點乘飛機到北京或者到上海(不可兼或)我喜歡學習或喜歡音樂(可兼或)。（4）聯(lián)結(jié)詞“→”是自然語言中的“如果…，則…”，“若…，才能…”、“除非…，否則…”等的邏輯抽象。主要描述方法有：2021/7/3（2）只要P就Q；（4）只有Q，才P；（6）除非Q，否則非P；（1）因為P所以Q；（3）P僅當Q；（5）除非Q，才P；（7）沒有Q，就沒有P。聯(lián)結(jié)詞理解難點聯(lián)結(jié)詞理解難點(續(xù)1)2021/7/3Q：2+2=4。如：設(shè)P：雪是白色的；將下列命題符號化：①因為雪是白色的，所以2+2=4；P→Q②

如果2+2=4，則雪是白色的；

Q→P③只有雪是白色的，才有2+2=4；Q→P④

只有2+2=4，雪才是白色的；

P→Q⑤

只要雪不是白色的，就有2+2=4；

P→Q⑥

除非雪是白色的，否則2+2≠4；

P→Q或Q→P⑦

雪是白色的當且僅當2+2=4；

P?

Q聯(lián)結(jié)詞理解難點(續(xù)2)2021/7/3在自然語言中，前件為假，不管結(jié)論真假，整

個語句的意義，往往無法判斷。但在數(shù)理邏輯中，

當前件P為假時，不管Q的真假如何，則P→Q都為真。此時稱為“善意推定”；這里要特別提醒一下“→”的含義，在自然語言中，條件式中前提和結(jié)論間必

含有某種因果關(guān)系，但在數(shù)理邏輯中可以允許兩者

無必然因果關(guān)系，也就是說并不要求前件和后件有

什么聯(lián)系；聯(lián)結(jié)詞理解難點(續(xù)3)2021/7/3（5）雙條件聯(lián)結(jié)詞“”是自然語言中的“充分必要條件”、“當且僅當”等的邏輯抽象；（6）聯(lián)結(jié)詞連接的是兩個命題真值之間的聯(lián)結(jié)，而不是命題內(nèi)容之間的連接，因此復合命題的真值只取決于構(gòu)成他們的各原子命題的真值，而與它們的內(nèi)容、含義無關(guān)，與聯(lián)結(jié)詞所連接的兩原子命題之間是否有關(guān)系無關(guān)；（7）聯(lián)結(jié)詞“∧”、“∨”、“?”具有對稱性，而聯(lián)結(jié)詞“┐”、“→”沒有；（8）聯(lián)結(jié)詞“∧”、“∨”、“┐”同構(gòu)成計算機的與門、或門和非門電路是相對應(yīng)的，從而命題邏輯是計算機硬件電路的表示、分析和設(shè)計的重要工具。2021/7/3聯(lián)結(jié)詞理解難點(續(xù)4)3.2.4命題聯(lián)結(jié)詞的應(yīng)用例3.2.7

用復合命題表示如下圖所示的開關(guān)電路：P

QPPQ：開：開設(shè)：

Ａ關(guān)Ｐ閉合；Ｂ關(guān)Ｑ閉合。A∧BA∨BA2021/7/3用復合命題表示如下圖所示的邏輯電路：例3.2.8P

QWWP

W

QWWP

QP

W

QP2021/7/3P解:設(shè)P：輸入端Ｐ為高電位，Q：輸入端Ｑ為高電位,則“與門”對應(yīng)于P∧Q“或門”對應(yīng)于P∨Q“非門”對應(yīng)于P3.3命題公式、解釋與真值表2021/7/3定義3.3.1一個特定的命題是一個常值命題，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。一個任意的沒有賦予具體內(nèi)容的原子命題是一個變量命題，常稱它為命題變量(或命題變元)，該命題變量無具體的真值，它的變域是集合{T，F(xiàn)}(或{0，1})當原子命題是命題變元時，此復合命題也即為命題變元的“函數(shù)”，且該“函數(shù)”的值仍為“真”或“假”值，這樣的函數(shù)可形象地稱為“真值函數(shù)”,或稱為命題公式,此命題公式?jīng)]有確切真值。3.3.1

命題公式定義3.3.2(命題公式)命題變元本身是一個公式；如G是公式，則(┐G)也是公式；如G，H是公式，則(G∧H)、(G∨H)、(G→H)、(G?H)也是公式；基礎(chǔ)歸納 極小性合取式 析取式

蘊含式條件式命題公式是僅由有限步使用規(guī)則1-3后產(chǎn)生的結(jié)果。該公式常用符號G、H、…等表示。等價式雙條件式2021/7/3約定2021/7/3對于公式中最外層的括號，常可省略。如(┐G)可寫成┐G，(G→H)可寫成G→H。但必須指出這僅僅是一種約定，把程序輸入計算機時，括號是不可隨意省略的；否定聯(lián)結(jié)詞“┐”只作用于鄰接后的原子命題變元，如可把(┐G)∨H寫成是┐G∨H。相同聯(lián)結(jié)詞按其出現(xiàn)的先后次序,括號可以省略；五種邏輯聯(lián)結(jié)詞的優(yōu)先級按如下次序遞減：┐，∧，∨，→，

?例3.3.1

符號串：2021/7/3((P∧(Q∨R))→(Q∧((┐S)∨R)))；((┐P)∧Q)；

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

符號串：(P→Q)∧┐Q)；(┐P∨Q∨(R；(P→Q；P∨Q∨。等都不是合法的命題公式。例3.3.2公式的解釋與真值表2021/7/3定義3.3.3設(shè)P1、P2、…、Pn是出現(xiàn)在公式G中的所有命題變元，指定P1、P2、…、Pn一組真值，則這組真值稱為G的一個解釋,常記為Ｉ。一般來說，若有ｎ個命題變元，則應(yīng)有2n個不同的解釋。如果公式G在解釋Ｉ下是真的，則稱Ｉ滿足G；如果G在解釋Ｉ下是假的，則稱Ｉ弄假G。定義3.3.4

將公式G在其所有可能解釋下的真值情況列成的表，稱為G的真值表。例3.3.5求下面公式的真值表：Ｇ＝(P→((

P?

Q)∧R))∨Q其中，Ｐ、Ｑ、Ｒ是Ｇ的所有命題變元。PQRPP?

Q((

P?

Q)∧RP→((

P?

Q)∧R)G00010011001100110101101101111111100010001010111111000001111000012021/7/3PQRP→((P?Q)∧R)∨Q0001100100111001010111010111111110000100101101111100000111100001例3.3.5（續(xù)）PQR(P→((

P?

Q)∧R))∨Q000100110101011110001011110111112021/7/3進一步化簡為：例3.3.62021/7/3PQ(Ｐ→Ｑ)→Ｐ(Ｐ→Ｑ)∧Ｐ(Ｐ∧

Ｑ)?

(Ｐ→Q)00100011001010011110求下面這組公式的真值表：Ｇ1＝

(Ｐ→Ｑ)→Ｐ；Ｇ2＝(Ｐ→Ｑ)∧Ｐ；Ｇ3＝

(Ｐ∧Ｑ)?

(Ｐ→Q)。從這三個真值表可以看到一個非常有趣的事實：公式G1對所有可能的解釋具有“真”值公式G3對所有可能的解釋均具有“假”值公式G2則具有“真”和“假”值2021/7/3結(jié)論定義3.3.52021/7/3公式G稱為永真公式(重言式)，如果在它的所有解釋之下都為“真”。公式G稱為永假公式(矛盾式),如果在它的所有解釋之下都為“假”。公式G稱為可滿足的，如果它不是永假的。從上述定義可知三種特殊公式之間的關(guān)系：①永真式G的否定G是矛盾式；矛盾式G的否定G是永真式。②永真式一定是可滿足式,可滿足式不一定是永真式③可滿足式的否定不一定為不可滿足式(即為矛盾式)④如果公式G在解釋Ｉ下是真的，則稱Ｉ滿足G；如果G在解釋Ｉ下是假的，則稱Ｉ弄假于G。2021/7/3結(jié)論例3.3.72021/7/3寫出下列公式的真值表，并驗證其公式是重言式、矛盾式、可滿足公式。=

(Ｐ→Ｑ)?

(=

(Ｐ?

Q)?

((Q→Ｐ))；G1G2G3=

(P→

Q)∨Ｐ∨Ｑ)；(Ｐ→Q)∨Q。解：PQ(Ｐ→Ｑ)

?(

Ｐ∨Ｑ)(Ｐ?

Q)?( (Ｐ→Q)∨

(Q→Ｐ))(P→

Q)∨

Q00101011011010111100永真公式

可滿足公式永假公式可滿足公式2021/7/3三個公式的真值表如下：分析公式（1）2021/7/3若將其看成兩個公式，分別令：Ｇ＝Ｐ→Ｑ， Ｈ＝┐Ｐ∨Ｑ。則Ｇ?Ｈ是一個永真公式，即這兩個公式對任何解釋都必同為真假，此時，說Ｇ和Ｈ相等，記為

Ｇ＝Ｈ。定義3.3.6

設(shè)G、H是公式，如果在任意解釋Ｉ下，

G與H的真值相同，則稱公式G、H是等價的，記作G＝H。公式G、H等價的充分必要條件是公式G?H是永真公式證明:“”假定G，H等價，則G，H在其任意解釋

Ｉ下或同為真或同為假，于是由“?”的意義知，

G?H在其任何的解釋Ｉ下，其真值為“真”，即

G?H為永真公式。“”假定公式G?H是永真公式，Ｉ是它的任意解釋，在Ｉ下，G?H為真，因此，G、H或同為真，或同為假，由于Ｉ的任意性，故有G＝H。2021/7/3定理3.3.1首先，雙條件詞“?”是一種邏輯聯(lián)結(jié)詞，公式G?H是命題公式，其中“?”是一種邏輯運算，G?H的結(jié)果仍是一個命題公式。而邏輯等價

“＝”則是描述了兩個公式G與H之間的一種邏輯等價關(guān)系，G＝H表示“命題公式G等價于命題公式

H”，G＝H的結(jié)果不是命題公式。其次，如果要求用計算機來判斷命題公式G、H是否邏輯等價，即G＝H那是辦不到的，然而計算機卻可“計算”公式G?H是否是永真公式。2021/7/3“＝”與“?”的區(qū)別“=”的性質(zhì)2021/7/3由于“=”不是一個聯(lián)結(jié)詞，而是一種關(guān)系，為此，這種關(guān)系具有如下三個性質(zhì)：（1）自反性（2）對稱性（3）傳遞性G=G；若G=H，則H=G；若G=H，H=S，則G=S。這三條性質(zhì)體現(xiàn)了“=”的實質(zhì)含義。3.3.4命題公式的基本等價關(guān)系2021/7/3例3.3.5

證明公式G1

＝(Ｐ

?

Ｑ

)

與公式G2

＝(P→Q)∧(Q→P)之間是邏輯等價的。解：根據(jù)定理3.3.1，只需判定公式G3＝(Ｐ?Ｑ)?((P→Q)∧(Q→P))為永真公式。PQG3＝(Ｐ?Ｑ)?((Ｐ→Q)∧(Q→Ｐ))0011111010110010010011111111基本等價公式2021/7/3(結(jié)合律)(交換律)(冪等律)(吸收律)設(shè)G，H，S是任何的公式，則：Ｅ1：G∨(H∨S)＝(G∨H)∨SＥ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(分配律）2021/7/3(同一律)(零律)Ｅ9：G∨(H∧S)＝(G∨H)∧(G∨S)Ｅ10：G∧(H∨S)＝(G∧H)∨(G∧S)Ｅ11：G∨0＝GＥ12：G∧１＝GＥ13：G∨１＝１ Ｅ14：G∧0＝0Ｅ15：G∨┐G

＝１Ｅ16：G∧┐G

＝0(排中律)(矛盾律)基本等價公式（續(xù)）基本等價公式（續(xù)）2021/7/3(雙重否定律)

(De

MoRGan定律)Ｅ17：┐(┐G)＝GＥ18：┐(G∨H)＝┐G∧┐H Ｅ19：┐(G∧H)＝┐G∨┐HＥ20:

(G?

H)＝(G→H)∧(H→G)Ｅ21：(G→H)＝(┐G∨H)(等價式)(蘊涵式)(假言易位)

(等價否定等式)E22：G

→Ｈ＝

Ｈ→

GE23：G

?

Ｈ＝

G?

ＨE24：(G

→Ｈ)

∧(G→Ｈ)＝

G

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

BG∨HUA

BG∧HUA2021/7/3命題與集合之間的關(guān)系設(shè)G(P1,P2,…,Pn)是一個命題公式，其中：P1、P2、…、Pn

是

命

題

變

元

，

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’也是一個永真公式（或永假公式）。2021/7/3定理3.3.2(代入定理)例3.3.6設(shè)Ｇ(Ｐ,Ｑ)＝(Ｐ∧(Ｐ→Ｑ))→Ｑ，證明公式G是一個永真公式。另有兩個任意公式：Ｈ(Ｐ,

Ｑ)＝(Ｐ∨

Ｑ)；Ｓ(Ｐ,Ｑ)＝(Ｐ?Ｑ)。進一步驗證代入定理的正確性。解建立公式

G的真值表如右所示?？梢姙橛勒婀健?021/7/3PQ(Ｐ∧(Ｐ→Ｑ))→Ｑ001011101111例3.3.6（續(xù)）將Ｈ，Ｓ代入到Ｇ中分別取代G中的命題變元P、Q，所得到的公式Ｇ＇為：Ｇ＇(P,

Q)

=

G(H,

S)

=

(H∧(H→S))→S=

((Ｐ∨

Ｑ)∧((Ｐ∨

Ｑ)→(Ｐ?

Ｑ)))→(Ｐ?

Ｑ)建立新公式Ｇ‘(P,Q)的真值表，代入定理符合。2021/7/3PQ((Ｐ∨

Ｑ)∧((Ｐ∨

Ｑ)→(Ｐ?

Ｑ)))→(Ｐ?

Ｑ)00111111110010000010101011011001011101101111定理3.3.3(替換定理)2021/7/3設(shè)G1是G的子公式(即G1是公式G的一部分)，H1是任意的命題公式，在G中凡出現(xiàn)G1處都以H1替換后得到新的命題公式H，若G1＝H1，則G＝H。利用24個基本等價公式及代入定理和替換定理，可完成公式的轉(zhuǎn)化和等價判定。例3.3.72021/7/3利用基本的等價關(guān)系，完成如下工作：（1）判斷公式的類型：證明

((Ｐ∨Ｑ)∧ (

Ｐ∧(

Ｑ∨

Ｒ)))∨(

Ｐ∧

Ｑ)∨(

Ｐ∧

Ｒ)是一個永真公式。（2）證明公式之間的等價關(guān)系：

證明Ｐ→(Ｑ→Ｒ)=(Ｐ∧Ｑ)→Ｒ（3）化簡公式：證明(P∧(Ｑ∧R))∨((Ｑ∧R)∨(P∧R))=R證明2021/7/3Ｑ)∨(

Ｐ∧

Ｒ)（1）((Ｐ∨Ｑ)∧ (

Ｐ∧(

Ｑ∨

Ｒ)))∨(

Ｐ∧=((Ｐ∨Ｑ)∧(Ｐ∨(Ｑ∧Ｒ)))∨

((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))=

((Ｐ∨Ｑ)∧((Ｐ∨Ｑ)

∧(Ｐ∨Ｒ)))∨

((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))=((Ｐ∨Ｑ)∧(Ｐ∨Ｑ)∧(Ｐ∨Ｒ))∨

((Ｐ∨Ｑ)∧(Ｐ∨Ｒ)=

((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))∨

((Ｐ∨Ｑ)∧(Ｐ∨Ｒ))=T即:((Ｐ∨Ｑ)∧(

Ｐ∧(

Ｑ∨

Ｒ)))∨(Ｐ∧Ｑ)∨(Ｐ∧Ｒ)為永真公式；證明(續(xù))2021/7/3（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))=

(

P∧

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

(=

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

T∧R=

R即有:

(

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

命題公式的難點2021/7/3命題公式和命題不同，它是一個公式，無具體的真值可言，只有當給予公式中的每個命題變元以具體的真值指派，公式才有具體的真值；命題公式之間的等價聯(lián)結(jié)詞“?”和等價關(guān)系

“＝”之間是兩個完全不同的概念，前者是一種運算，后者是一種關(guān)系，兩個公式之間，通過聯(lián)結(jié)詞“?”的運算以后，仍然是一個命題公式，但等價關(guān)系“＝”只能將一個命題公式轉(zhuǎn)化成與之等價的另一個命題公式，“＝”是不可計算的；命題公式的難點2021/7/3對于24個基本的等價公式，如果將運算“”、

“∧”、“∨”分別對應(yīng)于集合中的運算

“￣”、“∩”、“∪”，真值“1”、“0”分別對應(yīng)于集合中的全集“U”和空集“F

”，則集合中的19個基本的等價公式對應(yīng)于命題的公式E1到E19，E20到E24是命題邏輯中所特有的公式，重點要求記住E20和E21。只有熟練地掌握這24個基本的等價公式，并且對聯(lián)結(jié)詞“∧”、“∨”注意用括號來標識其優(yōu)先級別，才能正確地加以應(yīng)用。3.3.6例3.3.8命題公式的應(yīng)用利用基本的等價關(guā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)2021/7/3例3.3.8利用21個基本等價關(guā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&2021/7/3例3.3.9TFFTFT將下面程序語言進行化簡。If

A

then

if

B

thenX

elseY

else

if

Bthen

X

else

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

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

Ｂ)∨(

Ａ∧

Ｂ)2021/7/3例3.3.9(續(xù)）執(zhí)行X的條件可化簡為：(Ａ∧Ｂ)∨(＝Ｂ∧(Ａ∨Ａ∧Ｂ)Ａ)＝Ｂ執(zhí)行Y的條件可化簡為：

(Ａ∧Ｂ)∨(Ａ∧Ｂ)＝ Ｂ∧(Ａ∨

Ａ)＝

ＢTXYEndStartBF程序可簡化為：If

B

then

X

else

Y2021/7/3例3.3.102021/7/3有一邏輯學家誤入某部落，被拘于勞獄，酋長意欲放行，他對邏輯學家說：“今有兩門，一為自由，一為死亡，你可任意開啟一門。為協(xié)助你脫逃，今加派兩名戰(zhàn)士負責解答你所提的任何問題。惟可慮者，此兩戰(zhàn)士中一名天性誠實，一名說謊成性，今后生死由你自己選擇。”邏輯學家沉思片刻，即向一戰(zhàn)士發(fā)問，然后開門從容離去。該邏輯學家應(yīng)如何發(fā)問？解：輯學家開啟另一扇門PQRS0011

從010010011110邏輯能夠從容離去嗎？邏輯學家手指一門問身旁的一名戰(zhàn)士說:“這扇門是死亡門，他(指另一名戰(zhàn)士)將回答‘是’,對嗎？”當被問戰(zhàn)士回答“對”,則邏輯學家開啟所指的門從容離去。P當:被問的戰(zhàn)戰(zhàn)士士是回誠答實“人否；”,則邏

Q容:離被去問。戰(zhàn)士的回答是“是”R:另一名戰(zhàn)士的回答是“是”

S:這扇門是死亡門。2021/7/3例3.3.112021/7/3一家航空公司，為了保證安全，用計算機復核飛行計劃。每臺計算機能給出飛行計劃正確或有誤的回答。由于計算機也有可能發(fā)生故障，因此采用三臺計算機同時復核。由所給答案，再根據(jù)“少數(shù)服從多數(shù)”的原則作出判斷，試將結(jié)果用命題公式表示，并加以簡化，畫出電路圖。解：C1C2C3S000000100100011110001011110111112021/7/3真值表設(shè)C1

，C2

，C3

分別表示三臺計算機的答案。S表示判斷結(jié)果。則根據(jù)真值表，利用聯(lián)結(jié)詞的定義，S可用C1，C2，C3所對應(yīng)的命題公式表示出來，同時可畫出該命題公式所對應(yīng)的電路圖。解：（續(xù)）C2)∧C3)S

=

(

C1∧C2∧C3)∨(C1∧

C2∧C3)∨(C1∧C2∧

C3)∨(C1∧C2∧C3)=((C1∨

C1)∧C2∧C3)∨(C1∧(C2∨∨(C1∧C2∧(C3∨

C3))=(C2∧C3)∨(C1∧C3)∨(C1∧C2)C1C2C3S&&&≥1≥12021/7/3習題

P95-963、(2)(3)(4)(7)(9)4、(3)(4)(5)5、(1)(3)(4)7、(1)(3)(5)(7)(9)8、(1)(3)9、(1)(4)2021/7/33.5 公式的標準型——范式2021/7/33.5.1

析取范式和合取范式定義3.5.1命題變元或命題變元的否定稱為文字有限個文字的析取稱為析取式(也稱為子句）有限個文字的合取稱為合取式(也稱為短語）P與 P稱為互補對。例子（1）Ｐ、Ｐ是文字；（2）Ｐ∨Ｑ∨Ｒ是子句；（3）Ｐ∧Ｑ∧Ｒ是短語。┐P是一個子句，這種說法正確么？一個命題變元或者其否定既可以是簡單的子句，也可以是簡單的短語。因此，Ｐ，Ｐ不但是文字，也是子句、短語2021/7/3定義3.3.6有限個短語的析取式稱為析取范式有限個子句的合取式稱為合取范式一個不含最外層括號的短語（子句）也可以是析取范式（合取范式）。2021/7/3例子2021/7/31.Ｐ、Ｐ是子句、短語、析取范式、合取范式；2.Ｐ∨Ｑ∨(Ｐ∨Ｑ∨Ｒ是子句、析取范式、合取范式，

Ｒ)僅是子句、合取范式；3.

Ｐ∧Ｑ∧Ｒ是短語、析取范式、合取范式，

(Ｐ∧Ｑ∧Ｒ)僅是短語、析取范式；(Ｐ∧Ｑ)∨((Ｐ∨Ｑ)∧(Ｐ∧Ｑ)是析取范式；

Ｐ∨Ｑ)是合取范式；6.句子Ｐ∨(Ｑ∨

Ｒ)、

(Ｑ∨Ｒ)既不是析取范式也不是合取范式總結(jié)2021/7/3單個的文字是子句、短語、析取范式，合取范式單個的子句是合取范式；單個的短語是析取范式；若單個的子句（短語）無最外層括號，則是合取范式（析取范式）；析取范式、合取范式僅含聯(lián)結(jié)詞集{，∧，∨}；“”聯(lián)結(jié)詞僅出現(xiàn)在命題變元前。范式的求解方法定理3.5.1

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

=

(Ｇ∨Ｈ)；(Ｇ?

Ｈ)

=

(Ｇ→Ｈ)∧(Ｈ→Ｇ)=(Ｇ∨Ｈ)∧(Ｈ∨Ｇ)。范式的求解方法(續(xù))（2）重復使用德?摩根定律將否定號移到各個命題變元的前端，并消去多余的否定號，這可利用如下2021/7/3等價關(guān)系：(Ｇ)=Ｇ；(Ｇ∨Ｈ)

=Ｇ∧Ｈ；(Ｇ∧Ｈ)

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

(Ｐ→

Ｑ)∨(Ｐ?

R)=

(

Ｐ∨

Ｑ)∨((

Ｐ∨R)∧(

R∨P))=

(

Ｐ∨

Ｑ)∨(

Ｐ∨R))∧((

Ｐ∨

Ｑ)∨(R∨P）R∨P))=

(

Ｐ∨

Ｑ∨

Ｐ∨R)∧(

Ｐ∨

Ｑ∨=

(

Ｐ∨

Ｑ∨R)= Ｐ∨

Ｑ∨R——合取范式——析取范式合取范式2021/7/3范式的不惟一性2021/7/3考慮公式：(Ｐ∨Ｑ)∧(Ｐ∨Ｒ)，其與之等價的析取范式：Ｐ∨(Ｑ∧Ｒ)；(Ｐ∧Ｐ)∨(Ｑ∧Ｒ)；Ｐ∨(Ｑ∧Ｑ)∨(Ｑ∧Ｒ)；

Ｐ∨(Ｐ∧Ｒ)∨(Ｑ∧Ｒ)。這種不惟一的表達形式給研究問題帶來了不便。3.3.6主析取范式和主合取范式1.極小項和極大項定義3.5.3

在含有n個命題變元P1、P2、P3、…、Pn的短語或子句中，若每個命題變元與其否定不同時存在，但二者之一恰好出現(xiàn)一次且僅一次，則稱此短語或子句為關(guān)于P1、P2、P3、…、Pn的一個極小項或極大項。2021/7/3對于n個命題變元，可構(gòu)成2n個極小項和2n個極大項例子2021/7/3（1）一個命題變元P，對應(yīng)的極小項有兩項：P、極大項有兩項：P、P；P。（2）兩個命題變元P、Q，對應(yīng)的極小項有四項：P∧

Q；P∧Q、 P∧Q、P∧ Q、極大項有四項：P∨Q、 P∨Q、P∨ Q、P∨ Q。例子（續(xù)）2021/7/3（3）三個命題變元P、Q、R，對應(yīng)的極小項有八項：Ｐ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧ＲＰ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧Ｒ

Ｐ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧Ｒ；極大項有八項：Ｐ∨Ｑ∨Ｒ、Ｐ∨Ｑ∨ＲＰ∨Ｑ∨Ｒ、Ｐ∨Ｑ∨Ｒ、Ｐ∨Ｑ∨Ｒ

Ｐ∨Ｑ∨Ｒ、Ｐ∨Ｑ∨Ｒ、Ｐ∨Ｑ∨Ｒ。2兩個命題變元的所對應(yīng)極小項真值表PQ┐P∧┐Q┐P∧QP∧┐QP∧Q001000010100100010110001注意：（1）沒有等價的兩個極小項；（2）使該極小項的真值為真的指派是唯一的；（3）使極小項為真的那組指派為對應(yīng)極小項的編碼（4）命題變元與1對應(yīng)，命題變元的否定與0對應(yīng)。021/7/3Ｐ∧

Ｑ→{0、0}為真→{00}→m00(m0)Ｐ∧Ｑ→{0、1}為真→{01}→m01(m1)Ｐ∧Ｑ→{1、0}為真→{10}→m10(m2)

；Ｐ∧Ｑ→{1、1}為真→{11}→m11(m3)2021/7/3兩個命題變元的所對應(yīng)極大項真值表PQ┐P∨┐Q┐P∨QP∨┐QP∨Q001110011101101011110111注意：（1）沒有等價的兩個極大項；（2）使該極大項的真值為假的指派是唯一的；（3）使極大項為假的那組指派為對應(yīng)極大項的編碼；（4）命題變元與0對應(yīng)，命題變元的否定與1對應(yīng)。Ｐ∨Ｑ→{0、0}為假→{00}→M00(M0)Ｐ∨

Ｑ→{0、1}為假→{01}→M01(M1)Ｐ∨Ｑ→{1、0}為假→{10}→M10(M2)Ｐ∨

Ｑ→{1、1}為假→{11}→M11(M3)2021/7/3三個命題變元的極小項和極大項PQR極小項極大項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任意兩個不同極小項的合取必為假任意兩個不同極大項的析取必為真極大項的否定是極小項；極小項的否定是極大項；所有極小項的析取為永真公式；所有極大項的合取是永假公式。2021/7/3極小項和極大項的性質(zhì)；mi∧mj=F,

i≠j；Mi∨Mj=T,

i≠j┐Mi=

miMi=┐mi2n

-1m =

1i=

0

i2n

-1M

=0。i=

0

i2

主析取范式和主合取范式2021/7/3定義3.5.4①在給定的析取范式中，每一個短語都是極小項，則稱該范式為主析取范式②在給定的合取范式中，每一個子句都是極大項，則稱該范式為主合取范式③如果一個主析取范式不包含任何極小項，則稱該主析取范式為“空”；如果一個主合取范式不包含任何極大項，則稱主合取范式為“空”。定理3.3.62021/7/3任何一個公式都有與之等價的主析取范式和主合取范式。證明：（1）利用定理3.4.1先求出該公式所對應(yīng)的析取范式和合取范式；（2）在析取范式的短語和合取范式的子句中，如同一命題變元出現(xiàn)多次，則將其化成只出現(xiàn)一次；（3）去掉析取范式中所有永假式的短語和合取范式中所有永真式的子句，即去掉含有形如P∧┐P子公式的短語和含有形如P∨┐P子公式的子句；證明（續(xù)1）2021/7/3（4）若析取范式的某一個短語中缺少該命題公式中所規(guī)定的命題變元，則可用公式：(Ｐ∨┐Ｐ)∧Q

=

Q將命題變元P補進去，并利用分配律展開，然后合并相同的短語，此時得到的短語將是標準的極小項；若合取范式的某一個子句中缺少該命題公式中所規(guī)定的命題變元，則可用公式：(Ｐ∧┐Ｐ)∨Q

=

Q將命題變元P補進去，并利用分配律展開，然后合并相同的子句，此時得到的子句將是標準的極大項；證明（續(xù)2）（5）利用等冪律將相同的極小項和極大項合并，同時利用交換律進行順序調(diào)整，由此可轉(zhuǎn)換成標準的主析取范式和主合取范式。2021/7/3需要說明求任何一個公式的主析取范式和主合取范式不僅要取決于該公式，而且取決于該公式所包含的命題變元。如公式：G1(P,

Q)

=

(P→Q)∧Q，G2(P,Q,R)=(P→Q)∧Q。前者是依賴于兩個命題變元的，后者應(yīng)依賴于三個命題變元。2021/7/33

求主析取范式和主合取范式的方法公式轉(zhuǎn)換法

利用基本等價公式進行變換（證明見定理

3.3.6)主范式真值表技術(shù)對公式的真值結(jié)果進行分解，分解成等價的極小項的析取或者極大項的合取2021/7/3例3.3.6利用等價公式轉(zhuǎn)換法求公式(P→Q)→(Q∧R)的主析取范式和主合取范式。解

（1）求主析取范式(P→Q)→(Q∧R)=

(2021/7/3Q)∨(Q∧R)P∨Q)∨(Q∧R)——析取范式Q∧(R∨

R))∨((P∨

P)∧Q∧R)＝(P∧=

(P∧=

(P∧Q∧R)∨(P∧

Q∧∨(

P∧Q∧R)R)∨(P∧Q∧R)——主析取范式例3.3.6（續(xù)）（2）求主合取范式

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

Q∨Q)∧(=

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

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

R))∧(P∨(Q∧((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經(jīng)∨學R)會∧使(P用∨公Q∨式轉(zhuǎn)R)換法，那么，用真值表2021/7/3技術(shù)又如何求解主范式呢？如何用極小項來構(gòu)成主析取范式？P

Q

m0

m1

m2

m3

P→Q0

0100010

101

0

0

11

00

01

100011備

注m0必須包含在主析取范式中m3必須包含在主析取范式中m一定不能包含2在主析取范式中主析取范式中必須且只能包含m1必須包含在2021/7/3使得公式真值為真的那些解釋主析取范式中對應(yīng)的極小項。1

0

0如何用極大項來構(gòu)成主合取范式？P

Q

M0

M1

M2

M3

P?

Q0

0

0

1

1

1

10

110110101111101M2必須包含在主合取范式中備

注M0一定不能包含在主合取范式中M3一定不能包含在主合取范式中1主合取0

范式1

中必1須且只0能包含M1必須包含在2021/7/3使得公式真值為假的那些解釋主合取范式中對應(yīng)的極大項。真值表技術(shù)2021/7/3①列出公式對應(yīng)的真值表，選出公式的真值結(jié)果為真的所有的行，在這樣的每一行中，找到其每一個解釋所對應(yīng)的極小項，將這些極小項進行析取即可得到相應(yīng)的主析取范式。②列出公式對應(yīng)的真值表，選出公式的真值結(jié)果為假的所有的行，在這樣的每一行中，找到其每一個解釋所對應(yīng)的極大項，將這些極大項進行合取即可得到相應(yīng)的主合取范式。例3.5.4利用真值表技術(shù)求公式G=┐(Ｐ→Ｑ)∨Ｒ的主析取范式和主合取范式。PQRP→Q┐（P→Q）┐(P→Q)∨R0001000011010101000111011000111010111101001111012021/7/3例3.5.4(續(xù)1)2021/7/3（1）求主析取范式找出真值表中其真值為真的行：2.001；4.011；5.100；6.101；8.111。這些行所對應(yīng)的極小項分別為：┐P∧┐Ｑ∧Ｒ，┐P∧Ｑ∧Ｒ，P∧┐Ｑ∧┐Ｒ，P∧┐Ｑ∧Ｒ，P∧Ｑ∧Ｒ。例3.5.4(續(xù)2)2021/7/3將這些極小項進行析取即為該公式G的主析取范式。

G=┐(Ｐ→Ｑ)∨Ｒ=

(┐P∧┐Ｑ∧Ｒ)∨(┐P∧Ｑ∧Ｒ)∨(P∧┐Ｑ∧┐Ｒ)∨(P∧┐Ｑ∧Ｒ)∨(P∧Ｑ∧Ｒ)例3.5.4(續(xù)3)2021/7/3（2）求主合取范式找出真值表中其真值為假的行：1．0

0 0；3．0

1 0；7．1

1 0。這些行所對應(yīng)的極大項分別為：

P∨Ｑ∨Ｒ、P∨┐Ｑ∨Ｒ、┐Ｐ∨┐Ｑ∨Ｒ將這些極大項進行合取即為該公式G的主合取范式：

G=(Ｐ→Ｑ)∨Ｒ=(P∨Ｑ∨Ｒ)∧(P∨┐Ｑ∨Ｒ)∧(┐Ｐ∨┐Ｑ∨Ｒ)4

主析取范式和主合取范式之間的轉(zhuǎn)換2021/7/3（1）已知公式G的主析取范式，求公式G的主合取范式（a）求

G的主析取范式，即G的主析取范式中沒為Ｇ的主析取范式。其中，mj

(i=1，2，…，2n-k)是mi(i=0,1,2,…,2n-i1)中去掉mli(i=１,２,…,k)后剩下的極小項。iii=1有出現(xiàn)過的極小項的析取，若kG

=

mli=1為Ｇ的主析取范式，則2n

-kG

=

mj主析取范式主合取范式2021/7/3（b）G=(G)即是G的主合取范式。即2n

-

k2n

-

kG

=

G

=

(

m

)=m

=Mjjjii=

1為G的主合取范式。2n

-

ki

i=

1i

i=

1主合取范式主析取范式2021/7/3n

n其中，mji

(i=1,2,…,2

-k)是Mi(i=0,１,２,…,2

-1)中去掉mli

(i=１,２,…,k)后剩下的極大項。ii=

1（2）已知公式G的主合取范式，求公式G的主析取范式（a）求G的主合取范式，即G的主合取范式中沒有出現(xiàn)過的極大項的合取，若kG

=

M

lni-

kli=

12為Ｇ的主合取范式，則G

=為Ｇ的主合取范式。M主合取范式主析取范式2021/7/3（b）G=(G)即是G的主析取范式。即，為G的主析取范式。i

iii=1

i=1i=12n-k

2n-k

2n-kG

= G

=

( Mj

)=( Mj

)=(mj

)例3.5.52021/7/3Ｒ)，求其設(shè)Ｇ=(Ｐ∧Ｑ)∨(Ｐ∧Ｒ)∨(Ｑ∧對應(yīng)的主析取范式和主合取范式。解 Ｇ=

(Ｐ∧Ｑ)∨(

Ｐ∧Ｒ)∨(

Ｑ∧

Ｒ)=(Ｐ∧Ｑ∧(Ｒ∨

Ｒ))∨(

Ｐ∧(Ｑ∨

Ｑ)∧Ｒ)∨(Ｐ∨

Ｐ)∧

Ｑ∧

Ｒ)，=

(Ｐ∧Ｑ∧Ｒ)∨(Ｐ∧Ｑ∧

Ｒ)∨(

Ｐ∧Ｑ∧Ｒ)∨(

Ｐ∧

Ｑ∧Ｒ)∨(Ｐ∧

Ｑ∧

Ｒ)∨(

Ｐ∧

Ｑ∧

Ｒ)=

(

Ｐ∧

Ｑ∧

Ｒ)∨(

Ｐ∧

Ｑ∧Ｒ)∨(

Ｐ∧Ｑ∧Ｒ)∨(Ｐ∧

Ｑ∧

Ｒ)∨(Ｐ∧Ｑ∧

Ｒ)∨(Ｐ∧Ｑ∧Ｒ)=m0∨m1∨m3∨m4∨m6∨m7

───主析取范式例3.5.5（續(xù)）2021/7/3Ｇ=

m2∨m5Ｇ=

Ｇ＝

(m2∨m5)＝=(Ｐ∨

Ｑ∨Ｒ)∧(

Ｐ∨Ｑ∨m2∧

m5=

M2∨M5Ｒ)──主合取范式3.5.3

范式中的難點2021/7/3如何正確的理解范式定義中的“有限個文字”、

“有限個短語”、“有限個子句”的概念是很關(guān)鍵的，“有限個”∈N={0,1,2,…,n,…}；使用真值表技術(shù)求主范式時注意正確地建立真值表,正確地掌握真值解釋還原成子句和短語的方法；使用公式轉(zhuǎn)換法求主范式時，需要增加某一個命題變元，此時注意關(guān)于該變元的永真公式和永假公式的正確加入，同時注意公式的正確化簡；利用主析取求主合取或者利用主合取求主析取時，注意是“Ｇ”的主析取范式的否定或“Ｇ”的主合取范式的否定，而非直接是G的否定。3.5.4

范式的應(yīng)用（3）2021/7/3(P→Q)∧(Q→P)定理3.5.3公式G為永真式當且僅當G的合取范式中每個簡單的析取式(子句)至少包含一個命題變元及其否定；公式G為永假式當且僅當G的析取范式中每個簡單的合取式(短語)至少包含一個命題變元及其否定；例3.5.6

判斷下面公式為何種類型的公式。（1）(P∧

Q)?

(

P∨Q)（2）(P→Q)?

R例3.5.62021/7/3解（1）(P∧

Q)?

(

P∨Q)P∨Q)→(P∧

Q))P∨Q)∨(P∧

Q))P∨Q∨(P∧

Q))∧((P∨Q)∨(P∧

Q))＝((P∧

Q)→

(

P∨Q))∧(

(＝(

(P∧

Q)∨

(

P∨Q))∧((＝(＝(P∨Q∨P)∧(P∨Q∨

Q))∧(

P∨Q∨P)∧(P∨Q∨Q)

—合取范式由于該合取范式中每個簡單析取式至少包含一個命題變元及其否定，由定理3.5.3知，該公式為永真公式。例3.5.6（續(xù)）2021/7/3P∨Q))（2）(P→Q)?

R

＝

((

P∨Q)→R)∧(R→(＝

(

(

P∨Q)∨R)∧(

R∨(

P∨Q))＝

((P∧

Q)∨R)∧(

R∨

P∨Q)＝

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

Q∧P)∨＝

(P∧

Q∧(P∧

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

P)∨Q∧

R)∨(R∧

Q∧

P)∨R∧R)∨(R∧R∧

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

Q∧Q)∨(R∧(R∧R∧Q)＝

(P∧

Q∧

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

Q∧

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

——析取范式例3.5.6（續(xù)）2021/7/3由于該公式所對應(yīng)的合取范式及析取范式都不

滿足定理3.4.3中的條件，所以它既不是永真公式，也不是永假公式，而是一個可滿足公式。例3.5.6（續(xù)）2021/7/3（3）

(P→Q)∧(P∧

Q)＝(

P∨Q)∧(P∧

Q)＝(P∧P∧Q)∨(Q∧P∧Q)——析取范式由于該公式所對應(yīng)的析取范式中的每一個簡單的合取式至少包含一個命題變元及其否定，根據(jù)定理3.5.3知，該公式是一個永假公式。定理3.5.42021/7/3如果命題公式是永真公式當且僅當它的主析取范式包含所有的極小項，此時無主合取范式或者說主合取范式為“空”。如果命題公式是永假公式當且僅當它的主合取范式包含所有的極大項，此時無主析取范式或者說主析取范式為“空”。兩個命題公式是相等的當且僅當它們對應(yīng)的主析取范式之間相等，或者(可兼或)它們對應(yīng)的主合取范式之間相等。例3.5.7求證(P→Q)∧(P→R)＝P→(Q∧R)證明左式=(P→Q)∧(P→R)=(2021/7/3P∨R)P∨Q)∧(Q)∨R)=

(

P∨Q∨(R∧

R))∧(

P∨(Q∧=

(

P∨Q∨R)∧(

P∨Q∨

R)∧(

P∨Q∨R)∧(

P∨

Q∨R)=

(

P∨Q∨R)∧(

P∨Q∨=

M4∧M5∧M6右式=P→(Q∧R)=R)∧(

P∨

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

(

P∨Q)∧(

P∨R)

=

M4∧M5∧M6兩個公式具有相同的主合取范式，故兩公式等價。習題

P9710、(3)(4)(7)11、(1)(4)(5)(7)2021/7/33.6

命題邏輯的推理理論概念描述問題的句子判斷對概念的肯A定dd

與You否r

T定ex的T判斷推理2021/7/3從一個或多個前提推出結(jié)論的思維過程認識世界的漸進過程推理的有效性和結(jié)論的真實性有效的推理不一定產(chǎn)生真實的結(jié)論；而產(chǎn)生真實結(jié)論的推理過程未必是有效的。有效的推理中可能包含為“假”的前提，而無效的推理卻可能得到為

“真”的結(jié)論。所謂推理有效，指的是它的結(jié)論是它前提的合乎邏輯的結(jié)果。也即，如果它的前提都為真，那么所得的結(jié)論也必然為真，而并不是要求前提或結(jié)論一定為真或為假，如果推理是有效的話，那么不可能它的前提都為真時，而它的結(jié)論為假。2021/7/33.6.1

推理的基本概念和推理形式2021/7/3定義3.6.0設(shè)G,H是公式，對任意解釋I，如果I滿足G，那么I滿足H，則稱H是G的邏輯結(jié)果(或稱G蘊涵H),記為GＨ，此時稱G為前提，H為結(jié)論。判定定理2021/7/3定理3.6.0設(shè)G,H是公式，H是G的邏輯結(jié)果當且僅當G→Ｈ為永真公式。證明：“”若GＨ，但G→H不是永真公式。于是，必存在一個解釋I，使得G→H為假，即在解釋

I下，G為真，而H為假，這與GＨ矛盾，故G→H是永真公式?！啊比鬐→H是永真式，但GＨ不成立，故存在

G,H的一個解釋I，使得G為真，而H為假，從而在解釋I下，G→H為假，這與G→H是永真公式矛盾，所以GＨ。推廣2021/7/3定義3.6.1

設(shè)G1,G2,…,Gn,H是公式，稱H是G1,G2,…,

Gn的邏輯結(jié)果(G1,G2,…,Gn共同蘊涵H),當且僅當H是G1∧G2∧…∧Gn的邏輯結(jié)果(logic

conclusion)。記為G1,G2,…,GnＨ，此時稱G1,G2,…,GnＨ為有效的(efficacious),否則稱為無效的(inefficacious)。

G1,G2,…,Gn稱為一組前提(Premise),有時用集合Г來

表示，記Г={G1,G2,…,Gn}。H稱為結(jié)論

(conclusion)。又稱H是前提集合Г的邏輯結(jié)果。記為ГH。判定定理2021/7/3定理3.6.1公式H是前提集合Г={G1,G2,…,Gn}的邏輯結(jié)果當且僅當G1∧G2∧…∧Gn→Ｈ為永真公式。證明：略。“”與“→”的不同2021/7/3“→”僅是一般的蘊涵聯(lián)結(jié)詞，G→H的結(jié)果仍是一個公式，而“”卻描述了兩個公式G，H之間的一種邏輯蘊涵關(guān)系，G

H的“結(jié)果”，是非命題公式；用計算機來判斷G

H是辦不到的。然而計算機卻可“計算”公式G→H是否為永真公式。3.6.2

判斷有效結(jié)論的常用方法要求Г=｛G1,

G2,

…,Gn｝Г

H也就是G1∧G2∧…∧Gn→Ｈ為永真公式因而真值表技術(shù)、演繹法和間接證明方法2021/7/31、真值表技術(shù)2021/7/3設(shè)P1,P2,…,Pn

是出現(xiàn)在前提G1,G2,…,Gn

和結(jié)論H中的一切命題變元，如果將P1,P2,…,Pn中所有可能的解釋及G1,G2,…,Gn，H的對應(yīng)真值結(jié)果都列在一個表中，根據(jù)“→”的定義，則有判斷方法如下：對所有G1,G2,…,Gn都具有真值T的行(表示前提為真的行),如果在每一個這樣的行中，H也具有真值T，則H是G1,G2,…,Gn的邏輯結(jié)果。對所有H具有真值為F的行(表示結(jié)論為假的行),如果在每一個這樣的行中，G1,G2,…,Gn中至少有一個公式的真值為F(前提也為假),則H是G1,G2,…,Gn的邏輯結(jié)果。例3.6.12021/7/3判斷下列H是否是前提G1,G2的邏輯結(jié)果PQG1G2H00010010111010011111(1)PQG1G2H00111011011001011100(2)PQG1G2H00110011111000011011(3)(1)H：Q；G1：P；G2：P→Q；是(2)H：┐P；G1：P→Q；G2：┐Q；是(3)H：Q；G1：┐P；G2：P→Q。否解2

推理定律2021/7/3設(shè)G，H，I，J是任意的命題公式，則有：(簡化規(guī)則)(添加規(guī)則)I1：G∧HGI2：G∧HHI3：GG∨HI4：HG∨HI5：┐GG→HI6：HG→HI7：┐(G→H)GI8：┐(G→H)┐HI9：G，HG∧H2 推理定律(續(xù))(選言三段論)(分離規(guī)則)(否定后件式)(假言三段論)I10：┐G，G∨HHI11：┐G，G

HHI12：G，G→HHI13：┐H，G→H┐GI14：G→H，H→IG→II15：G∨H，G→I，