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

1、離 散 數(shù) 學(xué)電子科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院示 范 性 軟 件 學(xué) 院24 八月 20222022/8/24數(shù)理邏輯（Mathematical Logic） 是研究演繹推理的一門學(xué)科，用數(shù)學(xué)的方法來研究推理的規(guī)律統(tǒng)稱為數(shù)理邏輯。第二篇 數(shù)理邏輯2022/8/24主要研究?jī)?nèi)容：推理 著重于推理過程是否正確 著重于語(yǔ)句之間的關(guān)系 主要研究方法：數(shù)學(xué)的方法 即引進(jìn)一套符號(hào)體系的方法， 所以數(shù)理邏輯又叫符號(hào)邏輯（Symbolic Logic）。 第二篇 數(shù)理邏輯2022/8/24什么是數(shù)理邏輯 ？ 用數(shù)學(xué)的方法來研究推理的規(guī)律統(tǒng)稱為數(shù)理邏輯。為什么要研究數(shù)理邏輯？ 程序 算法 數(shù)據(jù) 算法 邏輯 控制

2、總結(jié)2022/8/24第二篇 數(shù)理邏輯命題邏輯 命題的基本概念命題聯(lián)結(jié)詞命題公式命題的范式 主要研 究?jī)?nèi)容謂詞邏輯謂詞的基本概念謂詞公式公式的標(biāo)準(zhǔn)型推理與證明技術(shù)命題邏輯推理理論謂詞邏輯推理理論數(shù)學(xué)歸納法按定義證明法2022/8/24第三章 命題邏輯 命題邏輯也稱命題演算，或語(yǔ)句邏輯。 研究?jī)?nèi)容： （1）研究以命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系 （2）研究什么是命題？ （3）研究如何表示命題？ （4）研究如何由一組前提推導(dǎo)一些結(jié)論？2022/8/24第三章 命題邏輯 命題邏輯的特征： 在研究邏輯的形式時(shí)，我們把一個(gè)命題只分析到其中所含的命題成份為止，不再分析下去。 即：不把一個(gè)簡(jiǎn)單

3、命題再分析為非命題的集合，也不把謂詞和量詞等非命題成份分析出來。 2022/8/24第三章 命題邏輯集合的表示方法2命題公式3命題范式4命題基本概念1命題聯(lián)結(jié)詞22022/8/243.1 本章學(xué)習(xí)要求重點(diǎn)掌握一般掌握了解11、五種基本聯(lián)結(jié)詞2、24個(gè)基本的等價(jià)公式3 掌握求命題范式的方法3聯(lián)結(jié)詞完備集的理解和學(xué)習(xí)2公式的代入規(guī)則和替換規(guī)則2022/8/243.2.1 命題定義3.2.1 具有確切真值的陳述句稱為命題, 該命題可以取一個(gè)“值”，稱為真值。 真值只有“真”和“假”兩種， 分別用“”(或“”)和“”(或“”)表示。3.2 命題與命題聯(lián)結(jié)詞2022/8/24（1）太陽(yáng)是圓的； （2）北

4、京是中國(guó)的首都；（3）1110；（4）+y；（5）我喜歡踢足球；（6）3能被2整除；（7）地球外的星球上也有人；（8）中國(guó)是世界上人口最多的國(guó)家；例3.2.1TF非命題T/FFT/FTT2022/8/24例3.2.1（續(xù)）（1）把門關(guān)上；（2）一起來，更精彩?。?）你要出去嗎？（4）今天天氣真好??！ (5) 我正在說假話.非命題非命題非命題非命題注意：一切沒有判斷內(nèi)容的句子都不能作為命題，如命令句、感嘆句、疑問句、祈使句、二義性的陳述句(悖論)等。 非命題2022/8/24命題一定是陳述句，但并非一切陳述句都是命題。命題的真值有時(shí)可明確給出，有時(shí)還需要依靠環(huán)境、條件、實(shí)際情況時(shí)間才能確定其真值

5、。結(jié)論：在數(shù)理邏輯中像字母“x”、“y”、“z”等字母總是表示變量。約定：2022/8/24下列語(yǔ)句是否是命題？并判斷其真值結(jié)果？（1）四川不是一個(gè)國(guó)家；（2）3既是素?cái)?shù)又是奇數(shù)；（3）張謙是大學(xué)生或是運(yùn)動(dòng)員；（4）如果周末天氣晴朗，則我們將到郊外旅游；（5）2 + 2 = 4當(dāng)且僅當(dāng)雪是白的。例3.2.22022/8/24一般來說，命題可分兩種類型：原子命題(簡(jiǎn)單命題)：不能再分解為更為簡(jiǎn)單命題的命題。復(fù)合命題：可以分解為更為簡(jiǎn)單命題的命題。而且這些簡(jiǎn)單命題之間是通過如“或者”、“并且”、“不”、“如果.則.”、“當(dāng)且僅當(dāng)”等這樣的關(guān)聯(lián)詞和標(biāo)點(diǎn)符號(hào)復(fù)合而構(gòu)成一個(gè)復(fù)合命題。命題的分類2022/

6、8/24今天天氣很冷。今天天氣很冷并且刮風(fēng)。今天天氣很冷并且刮風(fēng)，但室內(nèi)暖和。例3.2.3 通常用大寫的帶或不帶下標(biāo)的英文字母、.P、Q、R、. Ai、Bi 、Ci、.Pi、Qi、Ri、.等表示命題2022/8/243.2.2 命題聯(lián)結(jié)詞設(shè)命題P,Q表示任意兩個(gè)命題,則最常見的命題聯(lián)結(jié)詞有：聯(lián)接詞記號(hào)復(fù)合命題讀法 記法真值結(jié)果 3.析取 P或者QP與Q的析取PQPQ=1P=1或Q=12.合取 P并且QP與Q的合取PQPQ=1P=1且Q=11.否定 非PP的否定PP=1 P=04.蘊(yùn)涵若P,則QP蘊(yùn)涵QPQPQ=0 P=1,Q=05.等價(jià) P當(dāng)且僅當(dāng)QP等價(jià)于QPQPQ=1P=1,Q=1或P=0

7、,Q=0例如：命題P：2是素?cái)?shù)；Q：北京是中國(guó)的首都2022/8/24總結(jié)P QPPQPQPQPQ0 0100110 1101101 0001001 1011112022/8/24說明1、聯(lián)結(jié)詞是句子與句子之間的聯(lián)結(jié)，而非單純的名詞、形容詞、數(shù)詞等地聯(lián)結(jié)；2、聯(lián)結(jié)詞是兩個(gè)句子真值之間的聯(lián)結(jié)，而非句子的具體含義的聯(lián)結(jié)，兩個(gè)句子之間可以無任何地內(nèi)在聯(lián)系；2022/8/24說明3、聯(lián)結(jié)詞與自然語(yǔ)言之間的對(duì)應(yīng)并非一一對(duì)應(yīng)；聯(lián)結(jié)詞自然語(yǔ)言既又、不僅而且、雖然但是、并且、和、與，等等；如P則Q、只要P就Q、P僅當(dāng)Q、只有Q才P、除非Q否則P，等等等價(jià)、當(dāng)且僅當(dāng)、充分必要、等等；相容（可兼）的或2022/8

8、/24符號(hào)化下列命題（1）四川不是人口最多的省份；（2）王超是一個(gè)德智體全面發(fā)展的好學(xué)生；解：（1）設(shè)：四川是人口最多的省份。 則命題（1）可表示為。（2）設(shè)：王超是一個(gè)思想品德好的學(xué)生； ：王超是一個(gè)學(xué)習(xí)成績(jī)好的學(xué)生； R：王超是一個(gè)體育成績(jī)好的學(xué)生。 R例3.2.42022/8/24符號(hào)化下列命題（3）教室的燈不亮可能是燈管壞了或者是停電了；（4）如果周末天氣晴朗，那么學(xué)院將組織我們到石像湖春游；解：（3）設(shè)：教室的燈亮 ：燈管壞 R：教室的燈不亮可能是停電了 則命題（3）可表示為() ( R) 。（4）設(shè)：周末天氣晴朗； ：學(xué)院將組織我們到石像湖春游。 則命題（4）可表示為。例3.2.4

9、（續(xù)）2022/8/24符號(hào)化下列命題（5）兩個(gè)三角形全等當(dāng)且僅當(dāng)三角形的三條邊全部相等。解：（5）設(shè)：兩個(gè)三角形全等； ：三角形的三條邊全部相等。 則命題（5）可表示為。例3.2.42022/8/24 為了不使句子產(chǎn)生混淆，作如下約定，命題聯(lián)結(jié)詞之優(yōu)先級(jí)如下：否定 合取, 析取 蘊(yùn)涵 等價(jià)同級(jí)的聯(lián)結(jié)詞合取, 析取，按其出現(xiàn)的先后次序(從左到右)確定運(yùn)算順序若運(yùn)算要求與優(yōu)先次序不一致時(shí)，可使用括號(hào)；同級(jí)符號(hào)相鄰時(shí)，也可使用括號(hào)。括號(hào)中的運(yùn)算為最優(yōu)先級(jí)。約 定2022/8/24設(shè)命題P：明天上午七點(diǎn)下雨；Q：明天上午七點(diǎn)下雪；R：我將去學(xué)校。符號(hào)化下述語(yǔ)句：如果明天上午七點(diǎn)不是雨夾雪，則我將去學(xué)

10、校如果明天上午七點(diǎn)不下雨并且不下雪，則我將去學(xué)校例3.2.5可符號(hào)化為：(PQ)R?？煞?hào)化為:(PQ)R。2022/8/24 設(shè)命題P：明天上午七點(diǎn)下雨；Q：明天上午七點(diǎn)下雪；R：我將去學(xué)校。符號(hào)化下述語(yǔ)句：如果明天上午七點(diǎn)下雨或下雪，則我將不去學(xué)校明天上午我將雨雪無阻一定去學(xué)校解： 1)可符號(hào)化為:(PQ)R 2)可符號(hào)化為：(PQR)(PQR)(PQR)(PQR) 或 (PQ)(PQ)(PQ)(PQ)R例3.2.5（續(xù)）2022/8/24例3.2.6設(shè)命題P：你陪伴我； Q：你代我叫車子； R：我將出去。 符號(hào)化下述語(yǔ)句： 除非你陪伴我或代我叫車子，否則我將不出去 如果你陪伴我并且代我叫

11、輛車子，則我將出去 如果你不陪伴我或不代我叫輛車子，我將不出去R(PQ) 或 (PQ)R(PQ)R(PQ)R2022/8/24例:(粗略閱讀）設(shè)P:雪是白色的;Q:2+2=4。將下列命題符號(hào)化：（1）因?yàn)檠┦前咨模?+2=4； PQ （2）如果2+2=4，則雪是白色的； QP（3）只有雪是白色的，才有2+2=4； QP（4）只有2+2=4，雪才是白色的； PQ（5）只要雪不是白色的，就有2+2=4； PQ（6）除非雪是白色的，否則2+24； P Q或QP（7）雪是白色的當(dāng)且僅當(dāng)2+2=4； P Q2022/8/243.2.4 命題聯(lián)結(jié)詞的應(yīng)用例 3.2.7 用復(fù)合命題表示如下圖所示的開關(guān)

12、電路： 圖3.2.1 圖3.2.2 圖3.2.3ABABA設(shè)： ：開關(guān)閉合；：開關(guān)閉合。 2022/8/24用復(fù)合命題表示如下圖所示的邏輯電路：例 3.2.8圖3.2.4 圖3.2.5 圖3.2.6P QPQP解:設(shè)P：輸入端為高電位,Q：輸入端為高電位,則 “與門”對(duì)應(yīng)于PQ； “或門”對(duì)應(yīng)于PQ； “非門”對(duì)應(yīng)于P。2022/8/243.3 命題公式、解釋與真值表定義3.3.1 一個(gè)特定的命題是一個(gè)常值命題，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。 一個(gè)任意的沒有賦予具體內(nèi)容的原子命題是一個(gè)變量命題，常稱它為命題變量(或命題變?cè)?。 該命題變量無具體的真值，其變域是集合T

13、，F(xiàn) 注意(1)復(fù)合命題為命題變?cè)摹昂瘮?shù)”,其函數(shù)值仍為真或“假”值。(2)真值函數(shù)或命題公式，沒有確切真值。真值函數(shù)2022/8/243.3.1 命題公式定義3.3.2 命題公式(遞歸定義)命題變?cè)旧硎且粋€(gè)公式；如G是公式，則(G)也是公式；如G，H是公式，則(GH)、(GH)、(GH)、(GH)也是公式；僅由有限步使用規(guī)則1-3后產(chǎn)生的結(jié)果。該公式常用符號(hào)G、H、等表示。2022/8/24符號(hào)串：(P(QR)(Q(SR) (PQ) (P(PQ) (PQ)(RQ)(PR) 等都是命題公式。例3.3.1例3.3.2 符號(hào)串：(PQ)Q) (PQ；(PQ(R PQ 等都不是合法的命題公式。2

14、022/8/24例3.3.3試用符號(hào)形式寫出下列命題：（1）雖然今天天氣晴朗，老陳還是不來；（2）除非你陪伴我或代我叫的士，否則我將不出去；（3）停機(jī)的原因在于語(yǔ)法錯(cuò)誤或者程序錯(cuò)誤；解：（1）P：今天天氣晴朗,Q：老陳要來,則有：PQ；（2）P：你陪伴我； Q：你代我叫的士；R：我出去。則有：RPQ或PQR；（3）P：停機(jī)的原因在于語(yǔ)法錯(cuò)誤，Q：停機(jī)的原因在于程序錯(cuò)誤，則有：PQ；2022/8/24例3.3.3(續(xù))試用符號(hào)形式寫出下列命題：（4）若a和b是偶數(shù)，則a + b是偶數(shù)；（5）我們要做到身體好、學(xué)習(xí)好、工作好，為祖國(guó)四化建設(shè)而奮斗。 解：（4）P：a是偶數(shù)；Q：b是偶數(shù)，R：a+b

15、是偶數(shù)，則有：PQR；（5）P：我們要做到身體好,Q：我們要做到學(xué)習(xí)好, R：我們要做到工作好，S：我們要為祖國(guó)四化建設(shè)而奮斗，則有：PQR S。2022/8/24公式(P(QR)(Q(SR)可表示如下：(P(QR)(Q(SR)P(QR) Q(SR)P QR Q SRQ R S RS例3.3.42022/8/243.3.2 公式的解釋與真值表定義3.3.3 設(shè)P1、P2、Pn是出現(xiàn)在公式G中的所有命題變?cè)?，指定P1、P2、Pn一組真值，則這組真值稱為G的一個(gè)解釋,常記為。 一般來說，若有個(gè)命題變?cè)?，則應(yīng)有2n個(gè)不同的解釋。 如果公式G在解釋下是真的，則稱滿足G；如果G在解釋下是假的，則稱弄假G

16、。定義3.3.4 將公式G在其所有可能解釋下的真值情況列成的表，稱為G的真值表。2022/8/24例3.3.5求下面公式的真值表： (P(PQ)R)Q 其中，、是的所有命題變?cè)?。P Q R PPQ(PQ)RP(PQ)R)G0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 10111000001111000001010011110100111101112022/8/24例3.3.5（續(xù)）P Q R(P(PQ)R)Q0 0 010 0 110 1 010 1 111 0 001 0 111 1 011 1 1 1進(jìn)一步化簡(jiǎn)為：2022/8/24例3.3

17、.6 P Q() ()() (Q)0 0 1 00 0 1 1 00 1 01 00 1 11 10 求下面這組公式的真值表： 1 ()； 2()； 3 () (Q)。2022/8/24從這三個(gè)真值表可以看到一個(gè)非常有趣的事實(shí)：公式G1對(duì)所有可能的解釋具有“真”值公式G3對(duì)所有可能的解釋均具有“假”值公式G2則具有“真”和“假”值結(jié)論 P Q() ()() (Q)0 0 1 00 0 1 1 00 1 01 00 1 11 10 2022/8/24定義3.3.5公式G稱為永真公式(重言式)，如果在它的所有解釋之下都為“真”。公式G稱為永假公式(矛盾式),如果在它的所有解釋之下都為“假”。公式G

18、稱為可滿足式，如果它不是永假的。2022/8/24從上述定義可知三種特殊公式之間的關(guān)系：永真式G的否定G是矛盾式；矛盾式G的否定G是永真式。永真式一定是可滿足式,可滿足式不一定是永真式可滿足式的否定不一定為矛盾式結(jié)論2022/8/24例3.3.7寫出下列公式的真值表，并驗(yàn)證其公式是重言式、矛盾式、可滿足公式。（1）G1=()()；（2）G2=(Q)(Q)(Q)；（3）G3=(PQ)Q。2022/8/24例3.3.7 解P Q() ()( Q) (Q)(Q)(PQ) Q0 0 0 1 1 0 1 1 永真式永假式可滿足式三個(gè)公式的真值表如下：1011100011102022/8/24設(shè)存在G和H

19、兩個(gè)公式，例如令： ， 。若是一個(gè)永真公式，即這兩個(gè)公式對(duì)任何解釋都必同為真假，此時(shí)，說和相等，記為。為此可定義：分析公式（1）定義3.3.6 設(shè)G、H是公式，如果在任意解釋下，G與H的真值相同，則稱公式G、H是等價(jià)的，記作GH。2022/8/24公式G、H等價(jià)的充分必要條件是公式GH是永真公式證明:“”假定G，H等價(jià)，則G，H在其任意解釋下或同為真或同為假。 于是由“”的意義知，GH在其任何的解釋下，其真值為“真”，即GH為永真公式?！啊奔俣ü紾H是永真公式，是它的任意解釋，在下，GH為真，因此，G、H或同為真，或同為假，由于的任意性，故有GH。定理3.3.12022/8/24 （1）“”

20、是一種邏輯聯(lián)結(jié)詞，公式GH是命題公式，其中“”是一種邏輯運(yùn)算，GH的結(jié)果仍是一個(gè)命題公式。而邏輯等價(jià)“”則是描述了兩個(gè)公式G與H之間的一種邏輯等價(jià)關(guān)系，GH表示“命題公式G等價(jià)于命題公式H”，GH 的結(jié)果不是命題公式。 （2）如果要求用計(jì)算機(jī)判斷命題公式G、H是否邏輯等價(jià)，即GH那是辦不到的然而計(jì)算機(jī)卻可“計(jì)算”公式GH是否為永真公式。 “” 與“”的區(qū)別2022/8/24“=”的性質(zhì)由于“=”不是一個(gè)聯(lián)結(jié)詞，而是一種關(guān)系，為此，這種關(guān)系具有如下三個(gè)性質(zhì)：（1）自反性 G = G；（2）對(duì)稱性 若G = H，則H = G；（3）傳遞性 若G = H，H = S，則G = S。這三條性質(zhì)體現(xiàn)了“

21、=”的實(shí)質(zhì)含義。 2022/8/243.3.4 命題公式的基本等價(jià)關(guān)系例3.3.8 證明公式G1()與公式G2(PQ)(QP)之間是邏輯等價(jià)的。 解：根據(jù)定理3.3.1，只需判定公式G3() (PQ)(QP)為永真公式。P Q G3() (Q)(Q)0 0 1 1 1 1 10 1 0 1 1 0 0 1 0 0 1 0 0 11 1 1 1 1 1 12022/8/24設(shè)G，H，S是任何的公式，則：基本等價(jià)公式1) 1：GGG (冪等律) 2：GGG2) 3：GHHG (交換律) 4：GHHG3) 5：G(HS)(GH)S(結(jié)合律) 6: G(HS)(GH)S4) 7：G(GH) G (吸收

22、律) 8：G(GH) G2022/8/245) 9：G(HS)(GH)(GS)(分配律） 10：G(HS)(GH)(GS)6) 11：GG(同一律) 12：GG 7) 13：G(零律） 14：G8) 15：GG1(排中律)9) 16：GG (矛盾律)基本等價(jià)公式（續(xù)）2022/8/24基本等價(jià)公式（續(xù)）10) 17：(G)G (雙重否定律)11) 18：(GH)GH (De MoRGan定律) 19：(GH)GH。12) 20: (GH)(GH)(HG)(等價(jià))13) 21：(GH)(GH) (蘊(yùn)涵)14) E22：G G。 (假言易位)15) E23：G G。 (等價(jià)否定等式)16) E24

23、：(G ) (G)G (歸謬論)如何推導(dǎo)？2022/8/24將G，H理解為某總體論域上的子集合，規(guī)定：GH為兩集合的公共部分（交集合）GH為兩集合的全部（并集合）G為總體論域（如矩形域）中G的補(bǔ)集將命題中的真值“1”理解為集合中的總體論域（全集），將命題中的真值“0”理解為集合中的空集GH GH GUABUABUA命題與集合之間的關(guān)系 “” 對(duì)“”與“”對(duì)“”的對(duì)比等冪律; GGG GGG交換律= GHHG GHHG結(jié)合律A(BC)=(AB)CA(BC)=(AB)CG(HS)=(GH)SG(HS)=(GH)S恒等律；GG GG零律；G G吸收律 A(AB)=A A(AB)=A G(GH)=G

24、G(GH)=G否定律 (G)G分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)G(HS)=(GH)(GS)G(HS)=(GH)(GS)2022/8/24設(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也是永真(或永假)式。定理3.3.2(代入定理)2022/8/24例3.3.9設(shè)(, )()，證明公

25、式G是一個(gè)永真公式。另有兩個(gè)任意公式： (, )()； (, )()。 進(jìn)一步驗(yàn)證代入定理的正確性。 解 建立公式G的真值表如右所示?？梢姙橛勒婀?。P Q()0 010 111 011 112022/8/24例3.3.9（續(xù)）將(, )()；(, )() 分別取代G中的命題變?cè)狿、Q，所得到的公式： (P, Q) = G(H, S) = (H(HS)S = ()()()() 建立新公式(P, Q)的真值表。P Q()()()()0 0 0 1 1 0 1 1 (, )()1 1 1 1 1 1 1 1 10 0 0 0 0 1 0 1 01 1 0 1 1 0 0 1 01 0 1 1 0

26、1 1 1 12022/8/24定理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à)判定。2022/8/24例3.3.10利用基本的等價(jià)關(guān)系，完成如下工作：（1）判斷公式的類型： 證明 () ()()()是一個(gè)永真公式。（2）證明公式之間的等價(jià)關(guān)系：證明() = ()（3）化簡(jiǎn)公式：證明(P(R)(R)(PR) = R 2022/8/24例3.3.10 證明（1）() ()()() = ()()()() = (

27、)()() ()() = ()()() ( ()() = ()()()() = T 即:() ()()()為永真公式； 2022/8/24例3.3.10 證明（續(xù)）（2） P(QR)=P(QR)=P(QR) =(PQ)R=(PQ)R=(PQ)R 即有: P(QR)=(PQ)R； （3） (P(QR)(QR)(PR) = (PQ)R)(QP)R) = (PQ)R)(QP)R) = (PQ)(QP)R = TR = R 即有: (P(QR)(QR)(PR) = R。 2022/8/243.3.6 命題公式的應(yīng)用例3.3.11 利用基本的等價(jià)關(guān)系，化簡(jiǎn)下列電路圖 &11&TSRQPRPSQPSPQR

28、P解：上述電路圖可描述為：（1）(PQR)(PQS)(PR)(PS)（2）(PQR)(PQS)(PST)2022/8/24例3.3.11（續(xù)）利用24個(gè)基本等價(jià)關(guān)系，化簡(jiǎn)公式(1)、(2)可得： （1）(PQR)(PQS)(PR)(PS) = (PQ(RS)(P(RS) = PQ(RS)； （2）(PQR)(PQS)(PST) = (PQS)(PST) = PST 。 SRQPPSQ&2022/8/24例3.3.12將下面程序語(yǔ)言進(jìn)行化簡(jiǎn)。If A then if B then X else Y else if B then X else Y TFFTFTStartAXYEndBB 解：執(zhí)行X

29、的條件為： ()() 執(zhí)行Y的條件為： ()()2022/8/24例3.3.12(續(xù)） 執(zhí)行X的條件可化簡(jiǎn)為：()()( )執(zhí)行Y的條件可化簡(jiǎn)為：()() ()TXYEndStartAF程序可簡(jiǎn)化為：If B then X else Y 2022/8/24例3.3.13有一邏輯學(xué)家誤入某部落，被拘于勞獄，酋長(zhǎng)意欲放行，他對(duì)邏輯學(xué)家說： “今有兩門，一為自由，一為死亡，你可任意開啟一門。為協(xié)助你脫逃，今加派兩名戰(zhàn)士負(fù)責(zé)解答你所提的任何問題。惟可慮者，此兩戰(zhàn)士中一名天性誠(chéng)實(shí)，一名說謊成性，今后生死由你自己選擇?！?邏輯學(xué)家沉思片刻，即向一戰(zhàn)士發(fā)問，然后開門從容離去。該邏輯學(xué)家應(yīng)如何發(fā)問？ 2022

30、/8/24例3.3.13 解P:被問戰(zhàn)士是誠(chéng)實(shí)人； Q:被問戰(zhàn)士的回答是“是”R:另一名戰(zhàn)士的回答是“是”S:這扇門是死亡門。 P Q R S 0 0 1 1 0 1 0 0 1 0 0 1 1 1 1 0邏輯學(xué)家手指一門問身旁的一名戰(zhàn)士說:“這扇門是死亡門，而他(指另一名戰(zhàn)士)將回答是,對(duì)嗎？” 邏輯學(xué)家能安全離去嗎？當(dāng)被問戰(zhàn)士回答“對(duì)”,則邏輯學(xué)家開啟所指的門從容離去當(dāng)被問的戰(zhàn)士回答“否”,則邏輯學(xué)家開啟另一扇門從容離去。2022/8/24例3.3.14一家航空公司，為了保證安全，用計(jì)算機(jī)復(fù)核飛行計(jì)劃。每臺(tái)計(jì)算機(jī)能給出飛行計(jì)劃正確或有誤的回答。由于計(jì)算機(jī)也有可能發(fā)生故障，因此采用三臺(tái)計(jì)算機(jī)

31、同時(shí)復(fù)核。由所給答案，再根據(jù)“少數(shù)服從多數(shù)”的原則作出判斷，試將結(jié)果用命題公式表示，并加以簡(jiǎn)化，畫出電路圖。 2022/8/24例3.3.14 解設(shè)C1，C2，C3分別表示三臺(tái)計(jì)算機(jī)的答案。S表示判斷結(jié)果。 C1 C2 C3 S 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 真值表則根據(jù)真值表，利用聯(lián)結(jié)詞的定義，S可用C1，C2，C3所對(duì)應(yīng)的命題公式表示出來，同時(shí)可畫出該命題公式所對(duì)應(yīng)的電路圖。2022/8/24例3.3.14 解（續(xù)） S = (C1C2C3)(C1C2C3) (C1C2C3)(C1C2C3)

32、=(C1C1)C2C3)(C1(C2C2) C3)(C1C2(C3C3) =(C2C3)(C1C3)(C1C2) C1C2C3S&112022/8/243.5 公式的標(biāo)準(zhǔn)型范式3.5.1 析取范式和合取范式定義3.5.1 （1）命題變?cè)蛎}變?cè)姆穸ǚQ為文字（2）有限個(gè)文字的析取稱為析取式(也稱為子句）（3）有限個(gè)文字的合取稱為合取式(也稱為短語(yǔ)）（4）P與 P稱為互補(bǔ)對(duì)。2022/8/24例子（1）、是文字；（2）是子句； （3）是短語(yǔ)。 P是一個(gè)子句，這種說法正確么？一個(gè)命題變?cè)蛘咂浞穸瓤梢允呛?jiǎn)單的子句，也可以是簡(jiǎn)單的短語(yǔ)。因此，不但是文字，也是子句、短語(yǔ) 2022/8/24定義3.

33、5.2（1）有限個(gè)短語(yǔ)的析取式稱為析取范式（2）有限個(gè)子句的合取式稱為合取范式一個(gè)不含最外層括號(hào)的短語(yǔ)（子句）也可以是析取范式（合取范式）。2022/8/24例子（1）、是析取范式、合取范式；（2）是子句、析取范式、合取范式， ( )僅是子句、合取范式；（3） 是短語(yǔ)、析取范式、合取范式， ()僅是短語(yǔ)、析取范式；（4）()()是析取范式；（5）()()是合取范式；（6）句子()、()既不是析取范式也不是合取范式2022/8/24總結(jié)（1）單個(gè)的文字是子句、短語(yǔ)、析取范式，合取范式（2）單個(gè)的子句是析取范式；（3）單個(gè)的短語(yǔ)是合取范式；（4）若單個(gè)的子句（短語(yǔ)）無最外層括號(hào)，則是合取范式（析取

34、范式）；（5）析取范式、合取范式僅含聯(lián)結(jié)詞集，（6） “”聯(lián)結(jié)詞僅出現(xiàn)在命題變?cè)啊?022/8/24范式的求解方法定理3.5.1 對(duì)于任意命題公式，都存在與其等價(jià)的析取范式和合取范式。轉(zhuǎn)換方法：（1）利用等價(jià)公式中的等價(jià)式和蘊(yùn)涵式將公式中的、用聯(lián)結(jié)詞 、來取代，這可利用如下等價(jià)關(guān)系：() = ()；() = ()() = ()()。2022/8/24范式的求解方法(續(xù))（2）重復(fù)使用德摩根定律將否定號(hào)移到各個(gè)命題變?cè)那岸?，并消去多余的否定?hào)，這可利用如下等價(jià)關(guān)系：() =； () = ； () = 。（3）重復(fù)利用分配律，可將公式化成一些合取式的析取，或化成一些析取式的合取，這可利用如下等

35、價(jià)關(guān)系：() = ()()； () = ()()。2022/8/24例3.5.1求公式：()(R)的析取范式和合取范式解 ()(R) = ()(R)(RP)= (R)( RP）= ()(R)()( RP) = (R)合取范式= R析取范式 2022/8/24范式的不惟一性 考慮公式： ()()， 其與之等價(jià)的析取范式： ()； ()()； ()()； ()()。這種不惟一的表達(dá)形式給研究問題帶來了不便。2022/8/243.5.2 主析取范式和主合取范式1 極小項(xiàng)和極大項(xiàng)定義 3.5.3 在含有n個(gè)命題變?cè)狿1、P2、P3、Pn的短語(yǔ)或子句中，若每個(gè)命題變?cè)c其否定不同時(shí)存在，但二者之一恰好出

36、現(xiàn)一次且僅一次，則稱此短語(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) 2022/8/24例子（1）一個(gè)命題變?cè)狿，對(duì)應(yīng)的極小項(xiàng)有兩項(xiàng)：P、 P；對(duì)應(yīng)的極大項(xiàng)有兩項(xiàng)：P、 P。（2）兩個(gè)命題變?cè)狿、Q，對(duì)應(yīng)的極小項(xiàng)有四項(xiàng)： PQ、 PQ、P Q、 P Q；對(duì)應(yīng)的極大項(xiàng)有四項(xiàng)： PQ、 PQ、P Q、 P Q。2022/8/24例子（續(xù)）（3）三個(gè)命題變?cè)狿、Q、R，對(duì)應(yīng)的極小項(xiàng)有八項(xiàng)： 、 、 、；對(duì)應(yīng)的極大項(xiàng)有八項(xiàng)： 、 、 、。2022/8/24兩個(gè)命題變?cè)乃鶎?duì)應(yīng)極小項(xiàng)真值表 P QPQPQ PQ PQ 0 0 1 0 0

37、0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1注意：（1）沒有等價(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)。2022/8/24兩個(gè)命題變?cè)乃鶎?duì)應(yīng)極小項(xiàng)真值表 P QPQPQ PQ PQ 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 10、0為真 0 0 m00(m0)0 1為真0 1 m01(m1) 1 0為真1 0 m10(m2)1 1為真1 1 m11(m3)2022/8/24兩個(gè)命題變?cè)乃鶎?duì)應(yīng)極大項(xiàng)真值

38、表 P QPQ PQ PQ PQ 0 0 1 1 1 0 0 1 1 1 0 1 1 0 1 0 1 1 1 1 0 1 1 1注意：（1）沒有等價(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)。2022/8/24兩個(gè)命題變?cè)乃鶎?duì)應(yīng)極大項(xiàng)真值表 P QPQ PQ PQ PQ 0 0 1 1 1 0 0 1 1 1 0 1 1 0 1 0 1 1 1 1 0 1 1 10、0為假 0 0 M00(M0)0 1為假0 1 M01(M1)1 0為假1 0 M10(M2)1 1為假1 1 M11(

39、M3)2022/8/24三個(gè)命題變?cè)臉O小項(xiàng)和極大項(xiàng)PQR極小項(xiàng)極大項(xiàng)000m0=PQRM0=PQR001010011100101110111m1=PQRM1=PQRm2=PQRM2=PQRm3=PQRM3=PQRm4=PQRM4=PQRm5=PQRM5=PQRm6=PQRM6=PQRm7=PQRM7=PQRmimj=F2022/8/24極小項(xiàng)和極大項(xiàng)的性質(zhì)任意兩個(gè)極小項(xiàng)的合取必為假；任意兩個(gè)極大項(xiàng)的析取必為真；極大項(xiàng)的否定是極小項(xiàng)；極小項(xiàng)的否定是極大項(xiàng)；所有極小項(xiàng)的析取為永真公式；所有極大項(xiàng)的合取是永假公式。Mi=miMiMj=TMi= mi2022/8/242 主析取范式和主合取范式 定義

40、3.5.4 （1）在給定的析取范式中，每一個(gè)短語(yǔ)都是極小項(xiàng)，則稱該范式為主析取范式（2）在給定的合取范式中，每一個(gè)子句都是極大項(xiàng)，則稱該范式為主合取范式（3）如果一個(gè)主析取范式不包含任何極小項(xiàng)，則稱該主析取范式為“空”；如果一個(gè)主合取范式不包含任何極大項(xiàng)，則稱主合取范式為“空”。 2022/8/24定理3.5.2 任何一個(gè)公式都有與之等價(jià)的主析取范式和主合取范式。證明（1）利用定理3.5.1先求出該公式所對(duì)應(yīng)的析取范式和合取范式；（2）在析取范式的短語(yǔ)和合取范式的子句中重復(fù)出現(xiàn)的命題變?cè)?，將其化成只出現(xiàn)一次；（3）去掉析取范式中的所有永假式（ PP ）， 去掉合取范式中所有永真式（ PP ）2

41、022/8/24定理3.5.2 證明（續(xù)）（4）若析取范式的某一個(gè)短語(yǔ)中缺少該命題公式中所規(guī)定的命題變?cè)?，則可用公式()Q = Q將命題變?cè)狿補(bǔ)進(jìn)去，并利用分配律展開，然后合并相同的短語(yǔ)，此時(shí)得到的短語(yǔ)將是標(biāo)準(zhǔn)的極小項(xiàng)若合取范式的某一個(gè)子句中缺少該命題公式中所規(guī)定的命題變?cè)?，則可用公式()Q = Q將命題變?cè)狿補(bǔ)進(jìn)去，并利用分配律展開，然后合并相同的子句，此時(shí)得到的子句將是標(biāo)準(zhǔn)的極大項(xiàng)；2022/8/24證明（續(xù)）（5）利用等冪律將相同的極小項(xiàng)和極大項(xiàng)合并，同時(shí)利用交換律進(jìn)行順序調(diào)整，由此可轉(zhuǎn)換成標(biāo)準(zhǔn)的主析取范式和主合取范式。2022/8/243 求主析取范式和主合取范式的方法公式轉(zhuǎn)換法利用基

42、本等價(jià)公式進(jìn)行變換（證明見定理3.5.2)主范式真值表技術(shù)對(duì)公式的真值結(jié)果進(jìn)行分解，分解成等價(jià)的極小項(xiàng)的析取或者極大項(xiàng)的合取2022/8/24例3.5.2利用等價(jià)公式轉(zhuǎn)換法求公式(PQ)(QR)的主析取范式和主合取范式 。解 （1）求主析取范式 (PQ)(QR)= (PQ)(QR)=(PQ)(QR) 析取范式= (PQ(RR)(PP)QR)= (PQR)(PQR)(PQR) (PQR) 主析取范式2022/8/24例3.5.2（續(xù)）（2）求主合取范式 (PQ)(QR)= (PQ)(QR) =(PQ)(PR)(QQ)(QR) = (PQ)(PR)(QR)合取范式 2022/8/24例3.5.2（

43、續(xù)） =(PQ(RR)(P(QQ)R) (PP)QR) = (PQR)(PQR)(PQR) (PQR)(PQR) (PQR) = (PQR)(PQR) (PQR)(PQR) 主合取范式 2022/8/24需要說明求任何一個(gè)公式的主析取范式和主合取范式不僅要取決于該公式，而且取決于該公式所包含的命題變?cè)Ｈ绻剑?G1 = (PQ)Q， G2(P, Q, R) = (PQ)Q。前者是依賴于兩個(gè)命題變?cè)?，后者?yīng)依賴于三個(gè)命題變?cè)?2022/8/24如何用極小項(xiàng)來構(gòu)成主析取范式？P Qm0m1 m2 m3P-Q備 注0 01 0 0 010 10 1 0 011 00 0 1 001 10 0

44、011m1必須包含在主析取范式中m0必須包含在主析取范式中m3必須包含在主析取范式中m2一定不能包含在主析取范式中主析取范式中，必須且只能包含使得公式真值為真的解釋所對(duì)應(yīng)的極小項(xiàng)。2022/8/24如何用極大項(xiàng)來構(gòu)成主合取范式？P QM0M1 M2 M3P Q備 注0 0011110 1101101 0110101 111101M1必須包含在主合取范式中M2必須包含在主合取范式中M0一定不能包含在主合取范式中M3一定不能包含在主合取范式中主合取范式中，必須且只能包含使得公式真值為假的解釋所對(duì)應(yīng)的極大項(xiàng)。2022/8/24利用真值表求主析（合）取范式（1）列出公式對(duì)應(yīng)的真值表，選出公式的真值結(jié)果

45、為真的所有的行，在這樣的每一行中，找到其每一個(gè)解釋所對(duì)應(yīng)的極小項(xiàng)，將這些極小項(xiàng)進(jìn)行析取即可得到相應(yīng)的主析取范式。 （2）列出公式對(duì)應(yīng)的真值表，選出公式的真值結(jié)果為假的所有的行，在這樣的每一行中，找到其每一個(gè)解釋所對(duì)應(yīng)的極大項(xiàng)，將這些極大項(xiàng)進(jìn)行合取即可得到相應(yīng)的主合取范式。2022/8/24例3.5.4利用真值表求公式G = ()的主析取范式和主合取范式。 P Q R PQ（PQ）(PQ)R0 0 01000 0 11010 1 01000 1 11011 0 00111 0 10111 1 01001 1 11012022/8/24例3.5.4（續(xù)）（1）求主析取范式找出真值表中其真值為真的行

46、： 2. 0 0 1； 4. 0 1 1； 5. 1 0 0； 6. 1 0 1； 8. 1 1 1。這些行所對(duì)應(yīng)的極小項(xiàng)分別為： P， P，P， P，P。2022/8/24例3.5.4（續(xù)）將這些極小項(xiàng)進(jìn)行析取即為該公式G的主析取范式。 G = ()= (P)(P)(P)(P)(P)P Q R PQ（PQ）(PQ)R0 0 11010 1 11011 0 00111 0 10111 1 11012022/8/24例3.5.4（續(xù)）（2）求主合取范式 找出真值表中其真值為假的行：將這些極大項(xiàng)進(jìn)行合取即為該公式G的主合取范式： G = () =(P)(P)()P Q R PQ（PQ）(PQ)R0

47、 0 01000 1 01001 1 01002022/8/244 主析取范式與主合取范式的轉(zhuǎn)換（1）已知公式G的主析取范式，求公式G的主合取范式（a）求G的主析取范式，即G的主析取范式中沒有出現(xiàn)過的極小項(xiàng)的析取，若為的主析取范式。其中，mji(i=1,2,2n-k)是mi(i=0,2n-1)中去掉mli(i=,k)后剩下的極小項(xiàng)。為的主析取范式，則2022/8/24主析取范式主合取范式（b）G=(G)即是G的主合取范式。即，為G 的主合取范式。 2022/8/24主合取范式主析取范式（1）已知公式G的主合取范式，求公式G的主析取范式（a）求G的主合取范式，即G的主合取范式中沒有出現(xiàn)過的極大項(xiàng)

48、的合取，若為的主合取范式。其中，Mji(i=1,2,2n-k)是Mi(i=0,2n-1)中去掉Mli(i=,k)后剩下的極大項(xiàng)。為的主合取范式，則2022/8/24主合取范式主析取范式（2）已知公式G的主合取范式，求公式G的主析取范式 （a）求G的主合取范式，即G的主合取范式中沒有出現(xiàn)過的極大項(xiàng)的合取，若為的主合取范式，則為的主合取范式。其中，mji (i=1,2,2n-k)是Mi(i=0,2n-1)中去掉mli (i=,k)后剩下的極大項(xiàng)。2022/8/24主合取范式主析取范式（b）G=(G)即是G的主析取范式。即，為G 的主析取范式。 2022/8/24例3.5.5設(shè)=()()()，求其對(duì)應(yīng)的主析取范式和主合取范式。 解 = ()()( )=()() () = ()()() ()()()=