第3章 命題邏輯.ppt

1、離 散 數(shù) 學(xué),2020年10月9日星期五,2020/10/9,數(shù)理邏輯（Mathematical Logic） 是研究演繹推理的一門學(xué)科，用數(shù)學(xué)的方法來研究推理的規(guī)律統(tǒng)稱為數(shù)理邏輯。 公元前四世紀(jì)由希臘的亞里斯多德首創(chuàng) 他力圖把思維形式和存在聯(lián)系起來， 并按照客觀實(shí)際來闡明邏輯的范疇。,第二篇 數(shù)理邏輯,2020/10/9,主要研究內(nèi)容：推理 著重于推理過程是否正確 著重于語句之間的關(guān)系 主要研究方法：數(shù)學(xué)的方法 就是引進(jìn)一套符號(hào)體系的方法，所以數(shù)理邏輯又叫符號(hào)邏輯（Symbolic Logic）。,第二篇 數(shù)理邏輯,2020/10/9,什么是數(shù)理邏輯 ？ 用數(shù)學(xué)的方法來研究推理的規(guī)律統(tǒng)稱為

2、數(shù)理邏輯。 為什么要研究數(shù)理邏輯？ 程序算法數(shù)據(jù) 算法邏輯控制,總結(jié),日常語言叫做自然語言。 自然語言豐富，但是也有模棱兩可的特性。,小朱和小張?jiān)趯嬍伊奶欤±钇崎T而入，小朱感嘆：“說曹操曹操到?！保ń?jīng)典問題） 1、請問是誰來了? A、小朱 B、小張 C、小李D、曹操 2、門破了沒有？ A、破了 B、沒破,一個(gè)風(fēng)和日麗的早晨，Summer跑過來對小王說：“好激動(dòng)啊，剛剛撿到了100塊錢啊！”小王說：“天上掉餡餅的事，你都遇到了！”請問：天上在下著什么？ A、小雨 B、錢 C、沒下 D、餡餅,需要引入一種形式化語言單一、明確 這種形式化語言在數(shù)理邏輯中叫做目標(biāo)語言 目標(biāo)語言和一些規(guī)定的公式與符號(hào)

3、構(gòu)成了數(shù)理邏輯的形式符號(hào)體系。,2020/10/9,第二篇 數(shù)理邏輯,2020/10/9,第三章 命題邏輯,命題邏輯也稱命題演算，或語句邏輯。 研究內(nèi)容： （1）研究以命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系 （2）研究什么是命題？ （3）研究如何表示命題？ （4）研究如何由一組前提推導(dǎo)一些結(jié)論？,2020/10/9,第三章 命題邏輯,命題邏輯的特征： 在研究邏輯的形式時(shí)，我們把一個(gè)命題只分析到其中所含的命題成份為止，不再分析下去。不把一個(gè)簡單命題再分析為非命題的集合，不把謂詞和量詞等非命題成份分析出來。,2020/10/9,第三章 命題邏輯,2020/10/9,3.1 本章學(xué)習(xí)要求,2

4、020/10/9,3.2.1 命題 定義3.2.1具有確切真值的陳述句稱為命題, 該命題可以取一個(gè)“值”，稱為真值。 真值只有“真”和“假”兩種， 分別用“”(或“”)和“”(或“”)表示。,3.2 命題與命題聯(lián)結(jié)詞,2020/10/9,（1）太陽是圓的； （2）成都是一個(gè)旅游城市； （3）北京是中國的首都； （4）這個(gè)語句是假的； （5）1110； （6）+y； （7）我喜歡踢足球； （8）3能被2整除； （9）地球外的星球上也有人； （10）中國是世界上人口最多的國家； （11）今天是晴天；,例3.2.1,T,T,T/F,非命題,T/F,F,T/F,T,T/F,T,非命題,2020/10/

5、9,例3.2.1（續(xù)）,（12）把門關(guān)上； （13）滾出去！ （14）你要出去嗎？ （15）今天天氣真好啊！,非命題,非命題,非命題,非命題,注意： 一切沒有判斷內(nèi)容的句子都不能作為命題，如命令句、感嘆句、疑問句、祈使句、二義性的陳述句等。,2020/10/9,命題一定是陳述句，但并非一切陳述句都是命題。 命題的真值有時(shí)可明確給出，有時(shí)還需要依靠環(huán)境、條件、實(shí)際情況時(shí)間才能確定其真值。,結(jié)論：,在數(shù)理邏輯中像字母“x”、“y”、“z”等字母總是表示變量。,約定：,2020/10/9,下列語句是否是命題？并判斷其真值結(jié)果？ （1）四川不是一個(gè)國家； （2）3既是素?cái)?shù)又是奇數(shù)； （3）張謙是大學(xué)生

6、或是運(yùn)動(dòng)員； （4）如果周末天氣晴朗，則我們將到郊外旅游； （5）2+2=4當(dāng)且僅當(dāng)雪是白的。,例3.2.2,T/F,T/F,T,T,T,2020/10/9,一般來說，命題可分兩種類型： 原子命題(簡單命題)：不能再分解為更為簡單命題的命題。 復(fù)合命題：可以分解為更為簡單命題的命題。而且這些簡單命題之間是通過如“或者”、“并且”、“不”、“如果.則.”、“當(dāng)且僅當(dāng)”等這樣的關(guān)聯(lián)詞和標(biāo)點(diǎn)符號(hào)復(fù)合而構(gòu)成一個(gè)復(fù)合命題。,命題的分類,2020/10/9,今天天氣很冷。 今天天氣很冷并且刮風(fēng)。 今天天氣很冷并且刮風(fēng)，但室內(nèi)暖和。,例3.2.3,通常用大寫的帶或不帶下標(biāo)的英文字母、.P、Q、R、. Ai、

7、Bi 、Ci、.Pi、Qi、Ri、.等表示命題,2020/10/9,3.2.2 命題聯(lián)結(jié)詞,設(shè)命題P,Q表示任意兩個(gè)命題,則最常見的命題聯(lián)結(jié)詞有：,3.析取,P或者Q,P與Q的析取,PQ,PQ=1P=1或Q=1,2.合取,P并且Q,P與Q的合取,PQ,PQ=1P=1且Q=1,1.否定,非P,P的否定,P,P=1 P=0,4.蘊(yùn)涵,若P,則Q,P蘊(yùn)涵Q,PQ,PQ=0 P=1,Q=0,5.等價(jià),P當(dāng)且僅當(dāng)Q,P等價(jià)于Q,PQ,PQ=1P=1,Q=1 或P=0,Q=0,例如：命題P：2是素?cái)?shù)；Q：北京是中國的首都,1.否定聯(lián)結(jié)詞,設(shè)p為命題，則p的否定是一個(gè)復(fù)合命題，記作： p ，讀作“非p”或“

8、p的否定”。定義為：若p真值為1，則 p為0；若p為0，則 p的真值為1。 聯(lián)結(jié)詞“”也可以看作邏輯運(yùn)算，它是一元運(yùn)算。 【例】否定下列命題。 p ：王強(qiáng)是一名大學(xué)生。 p ：王強(qiáng)不是一名大學(xué)生。,P:蘇州處處清潔 P: 蘇州不處處清潔 (注意,不是處處不清潔) S：蘇州處處不清潔 (假設(shè)蘇州有兩個(gè)地方寒山寺 、沙家浜）,所以P一定不是S,Q:這些都是男同學(xué),Q:這些不都是男同學(xué),S：這些都不是男同學(xué),S和Q、Q的關(guān)系？,2. 合取聯(lián)結(jié)詞,定義1.1.2設(shè)p和q均為命題，則p和q的合取是一個(gè)復(fù)合命題，記作pq ，讀作“p與q”或“p合取q”。 定義為：當(dāng)且僅當(dāng)p和q均為1時(shí)，pq的真值才為1，

9、其他情況pq 的真值都為0。,p：2是素?cái)?shù)。（真值？） q：2是偶數(shù)。（真值？） 則pq表示： 2是素?cái)?shù)和偶數(shù) 由于p，q的真值均為1，所以pq的真值也為1。,合取的概念與自然語言中的“與”“和”“并且”的意義很相似，但是不完全相同 小王是大學(xué)生，小張是大學(xué)生。 兩個(gè)命題的合取為小王和小張都是大學(xué)生 但是對于命題“小王與小張是好朋友”。這個(gè)就不是命題的合取，而是一個(gè)普通命題。,p：我去旅游 q：教室里面有電視 pq：我去旅游并且教室里面有電視 自然語言中，上述命題合取沒有任何意義。 但是在數(shù)理邏輯中， pq仍然是一個(gè)命題。滿足合取的真值定義,練習(xí):將下列命題符號(hào)化,張三既用功又聰明 p：張三用

10、功 q：張三聰明 p q,張三不僅用功又聰明 p：張三用功 q：張三聰明 p q,張三雖然聰明，但不用功 p：張三用功 q：張三聰明 q p,張三與李四是同班同學(xué) t：張三與李四是同班同學(xué) 簡單陳述句，t是原子命題,3. 析取聯(lián)結(jié)詞,定義設(shè)p和q均為命題，則p和q的析取是一個(gè)復(fù)合命題，記作pq，讀作“p或q”或者“p析取q”。定義為：當(dāng)且僅當(dāng)p和q真值均為0時(shí)， pq真值才為0。其他情況pq真值都為1 聯(lián)結(jié)詞“”也可以看成邏輯運(yùn)算，它是二元邏輯運(yùn)算,p：張山是大學(xué)生 q：張山是籃球運(yùn)動(dòng)員 pq的語義： 張山是大學(xué)生 或者張山是籃球運(yùn)動(dòng)員,“”與漢語中的“或”相似，但又不相同。 分析下列兩個(gè)命題

11、中的“或”，有什么區(qū)別？ 今晚9點(diǎn)，中央一臺(tái)播放“雍正王朝”或者轉(zhuǎn)播足球比賽 (不可兼) 燈泡有故障或開關(guān)有故障。 (可兼, “”是可兼或) 漢語中的或有可兼或與不可兼或(排斥或)的區(qū)分。,今晚9點(diǎn)，中央一臺(tái)播放“雍正王朝”或者轉(zhuǎn)播足球比賽,p：今晚9點(diǎn)，中央一臺(tái)播放“雍正王朝” q：今晚9點(diǎn)，中央一臺(tái)轉(zhuǎn)播足球比賽 (p q) ( p q) 此復(fù)合命題為真當(dāng)且僅當(dāng)p，q中一個(gè)為真一個(gè)為假,4. 排斥析取詞,定義: 設(shè)定p，q，則“p排斥析取q”也是一種命題，記作p q。,5. 條件聯(lián)結(jié)詞,定義:設(shè)p和q均為命題，復(fù)合命題”如果p，則q”，稱為p與q的蘊(yùn)含式，記為：pq。讀作“如果p，那么q”或

12、“若p，則q”。 p是蘊(yùn)含式的前件，q為蘊(yùn)含式的后件 真值定義為：當(dāng)且僅當(dāng)p為1，q為0時(shí)， pq才為0。 pq的邏輯關(guān)系為q是p的必要條件,使用，注意幾點(diǎn)：,(1)q是p的必要條件有許多不同敘述方式： ”只要p就q”, ”因?yàn)閜，所以q”, ”p僅當(dāng)q”, ”只有q才p”, ”除非q才p”, ”除非q，否則非p”等等,(2)在自然語言中，如果p則q，前件p與后件q往往具有某種內(nèi)在聯(lián)系。但是在數(shù)理邏輯中，p與q可以無任何內(nèi)在聯(lián)系,(3)在數(shù)學(xué)或其他自然科學(xué)中，如果p則q，往往表達(dá)前件p為真，后見q也為真的推理關(guān)系。但是在數(shù)理邏輯中，作為一種規(guī)定，當(dāng)p為假時(shí)，無論q是真是假， pq均為真。 自然

13、語言中，前件為假，結(jié)論不管真假，整個(gè)語句的意義往往無法確定。,例 p： 月亮下山 q： 3+3=6,則pq： 若月亮下山,則3+3=6 （并沒有實(shí)質(zhì)蘊(yùn)含關(guān)系，仍承認(rèn)）,qp： 叫做pq的逆命題,qp： 叫做pq的逆否命題,【例】 p：小王努力學(xué)習(xí)。q：小王學(xué)習(xí)成績優(yōu)秀。 pq表示？ 如果小王努力學(xué)習(xí)，那么他的學(xué)習(xí)成績就優(yōu)秀。,如果小明學(xué)日語，小華學(xué)英語，則小芳學(xué)德語。 p：小明學(xué)日語 q：小華學(xué)英語 x：小芳學(xué)德語. 則原式可表示為：(pq)x,5. 等價(jià)(雙條件)聯(lián)結(jié)詞,定義：設(shè)p和q均為命題，其復(fù)合命題pq稱為雙條件命題，讀作：“p雙條件q”或者“p等價(jià)q”。定義為：當(dāng)且僅當(dāng)p和q的真值相

14、同時(shí)， pq真值為1。 聯(lián)結(jié)詞“”也可以理解成邏輯運(yùn)算，它是二元邏輯運(yùn)算 雙條件聯(lián)結(jié)詞表示的是一個(gè)充分必要關(guān)系,【例】 設(shè)p：張華是三好學(xué)生。 q：張華德、智、體全優(yōu)秀。 pq表示： 張華是三好學(xué)生當(dāng)且僅當(dāng)?shù)?、智、體全優(yōu)秀,p：2+2=4 q：雪是白的 pq表示： 2+2=4當(dāng)且僅當(dāng)雪是白的,若兩圓O1,O2的面積相等，則它們的半徑相等，反之亦然。 p:兩圓O1,O2的面積相等 q:兩圓O1,O2的半徑相等 pq,練習(xí)： 求下列復(fù)合命題的真值 (1) 2 + 2 4 當(dāng)且僅當(dāng) 3 + 3 6. (2) 2 + 2 4 當(dāng)且僅當(dāng) 3 是偶數(shù). (3) 2 + 2 4 當(dāng)且僅當(dāng) 太陽從東方升起.

15、(4) 2 + 2 4 當(dāng)且僅當(dāng) 美國位于非洲.,1,0,1,0,符號(hào)化命題，并指出它們的真值,是有理數(shù)是不對的(p) 2是偶素?cái)?shù)(p,q) 2或者4是素?cái)?shù)(p,r) 如果2是素?cái)?shù)，則3也是素?cái)?shù)(p,s) 2是素?cái)?shù)當(dāng)且僅當(dāng)3也是素?cái)?shù)(p,s) p ：1 p q ：1 p r ：1 p s ：1 p s ：1,2020/10/9,總結(jié),2020/10/9,說明,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)系；,2020/10/9,說明,3、聯(lián)結(jié)詞與自然語言之間的對應(yīng)并非一一對

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

17、示為。,2020/10/9,（4）設(shè)：周末天氣晴朗； ：學(xué)院將組織我們到石像湖春游。 則命題（4）可表示為。 （5）設(shè)：兩個(gè)三角形全等； ：三角形的三條邊全部相等。 則命題（5）可表示為。,例3.2.4 解(續(xù)),2020/10/9,為了不使句子產(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í)。,約 定,2020/10/9,設(shè)命題P：明天上午七點(diǎn)下雨；Q：明天上午七點(diǎn)下雪； R：我將去學(xué)校。 符號(hào)化下述語句： 如果明天上午七點(diǎn)不是雨夾

18、雪，則我將去學(xué)校 如果明天上午七點(diǎn)不下雨并且不下雪，則我將去學(xué)校 如果明天上午七點(diǎn)下雨或下雪，則我將不去學(xué)校 明天上午我將雨雪無阻一定去學(xué)校,可符號(hào)化為： (PQR)(PQR) (PQR)(PQR)。 或 (PQ)(PQ)(PQ) (PQ)R。,例3.2.5,可符號(hào)化為：(PQ)R。,可符號(hào)化為:(PQ)R。,可符號(hào)化為:(PQ)R。,2020/10/9,例3.2.6,設(shè)命題P：你陪伴我； Q：你代我叫車子； R：我將出去。 符號(hào)化下述語句： 除非你陪伴我或代我叫車子，否則我將不出去 如果你陪伴我并且代我叫輛車子，則我將出去 如果你不陪伴我或不代我叫輛車子，我將不出去,R(PQ) 或 (PQ)

19、R,(PQ)R,(PQ)R,2020/10/9,設(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 Q,2020/10/9,3.2.4 命題聯(lián)結(jié)詞的應(yīng)用,例 3.2.7 用復(fù)合命題表示如下圖所示的開關(guān)電路：,圖3.2.1 圖3.2.2 圖3.2.3,AB,AB,A,設(shè)：開關(guān)閉

20、合；：開關(guān)閉合。,2020/10/9,3.3 命題公式、解釋與真值表,定義3.3.1 一個(gè)特定的命題是一個(gè)常值命題，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。 而一個(gè)任意的沒有賦予具體內(nèi)容的原子命題是一個(gè)變量命題，常稱它為命題變量(或命題變元)，該命題變量無具體的真值，它的變域是集合T，F(xiàn)(或0，1) 注意 (1)復(fù)合命題為命題變元的“函數(shù)”,其函數(shù)值仍為真或“假”值。 (2)真值函數(shù)或命題公式，沒有確切真值。,真值函數(shù),2020/10/9,3.3.1命題公式,定義3.3.2 (命題公式) 命題變元本身是一個(gè)公式； 如G是公式，則(G)也是公式； 如G，H是公式，則(GH)、(

21、GH)、(GH)、(GH)也是公式； 僅由有限步使用規(guī)則1-3后產(chǎn)生的結(jié)果。該公式常用符號(hào)G、H、等表示。,2020/10/9,符號(hào)串： (PQ)； (P(PQ) ) )； ( ( (PQ)(RQ) ) (PR) )。 都是命題公式。,例3.3.1,例3.3.2符號(hào)串： (PQ)Q)；(PQ； (PQ(R； PQ。 等都不是合法的命題公式。,2020/10/9,例3.3.3,試用符號(hào)形式寫出下列命題： （1）雖然今天天氣晴朗，老陳還是不來； （2）除非你陪伴我或代我叫車子，否則我將不出去； （3）停機(jī)的原因在于語法錯(cuò)誤或者程序錯(cuò)誤； （4）若a和b是偶數(shù)，則a+b是偶數(shù)； （5）我們要做到身體

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

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

24、.4 將公式G在其所有可能解釋下的真值情況列成的表，稱為G的真值表。,2020/10/9,例3.3.5,求下面公式的真值表： (P(PQ)R)Q 其中，、是的所有命題變元。,2020/10/9,例3.3.5（續(xù)）,進(jìn)一步化簡為：,成真賦值， 成假賦值？,練習(xí)：,寫出下列公式的真值表, 并求它們的成真賦值和成假賦值 (pq) r (qp) qp,(1) A = (pq) r,成真賦值:000,001,010,100,110; 成假賦值:011,101,111,(2) B(qp)qp,成真賦值:00,01,10,11; 無成假賦值,2020/10/9,例3.3.6,求下面這組公式的真值表： 1 (

25、)； 2()； 3 () (Q)。,2020/10/9,從這三個(gè)真值表可以看到一個(gè)非常有趣的事實(shí)：,公式G1對所有可能的解釋具有“真”值 公式G3對所有可能的解釋均具有“假”值 公式G2則具有“真”和“假”值,結(jié)論,2020/10/9,定義3.3.5,公式G稱為永真公式(重言式)，如果在它的所有解釋之下都為“真”。 公式G稱為永假公式(矛盾式),如果在它的所有解釋之下都為“假”。 公式G稱為可滿足的，如果它不是永假的。,2020/10/9,從上述定義可知三種特殊公式之間的關(guān)系：,永真式G的否定G是矛盾式；矛盾式G的否定G是永真式。 永真式一定是可滿足式,可滿足式不一定是永真式 可滿足式的否定不

26、一定為不可滿足式(即為矛盾式),結(jié)論,2020/10/9,例3.3.7,寫出下列公式的真值表，并驗(yàn)證其公式是重言式、矛盾式、可滿足公式。 （1）G1=()()； （2）G2=(Q)(Q)(Q)； （3）G3=(PQ)Q。,2020/10/9,例3.3.7 解,三個(gè)公式的真值表如下：,2020/10/9,若將其看成兩個(gè)公式，分別令： ， 。 則是一個(gè)永真公式，即這兩個(gè)公式對任何解釋都必同為真假，此時(shí)，說和相等，記為。為此可定義：,分析公式（1）,定義3.3.6 設(shè)G、H是公式，如果在任意解釋下，G與H的真值相同，則稱公式G、H是等價(jià)的，記作GH。,() (),2020/10/9,公式G、H等價(jià)的

27、充分必要條件是公式GH是永真公式 證明:“”假定G，H等價(jià)，則G，H在其任意解釋下或同為真或同為假，于是由“”的意義知，GH在其任何的解釋下，其真值為“真”，即GH為永真公式。 “”假定公式GH是永真公式，是它的任意解釋，在下，GH為真，因此，G、H或同為真，或同為假，由于的任意性，故有GH。,定理3.3.1,2020/10/9,首先，雙條件詞“”是一種邏輯聯(lián)結(jié)詞，公式GH是命題公式，其中“”是一種邏輯運(yùn)算，GH的結(jié)果仍是一個(gè)命題公式。而邏輯等價(jià)“”則是描述了兩個(gè)公式G與H之間的一種邏輯等價(jià)關(guān)系，GH表示“命題公式G等價(jià)于命題公式H”，GH 的結(jié)果不是命題公式。 其次，如果要求用計(jì)算機(jī)來判斷命

28、題公式G、H是否邏輯等價(jià)，即GH那是辦不到的，然而計(jì)算機(jī)卻可“計(jì)算”公式GH是否是永真公式。,“” 與“”的區(qū)別,2020/10/9,“=”的性質(zhì),由于“=”不是一個(gè)聯(lián)結(jié)詞，而是一種關(guān)系，為此，這種關(guān)系具有如下三個(gè)性質(zhì)： （1）自反性 G=G； （2）對稱性 若G=H，則H=G； （3）傳遞性 若G=H，H=S，則G=S。 這三條性質(zhì)體現(xiàn)了“=”的實(shí)質(zhì)含義。,2020/10/9,3.3.4 命題公式的基本等價(jià)關(guān)系,例3.3.8 證明公式G1()與公式G2(PQ)(QP)之間是邏輯等價(jià)的。 解：根據(jù)定理3.3.1，只需判定公式 G3() (PQ)(QP)為永真公式。,2020/10/9,設(shè)G，H

29、，S是任何的公式，則：,基本等價(jià)公式,1) 1：GGG (冪等律) 2：GGG 2) 3：GHHG (交換律) 4：GHHG 3)*5：G(HS)(GH)S(結(jié)合律) 6: G(HS)(GH)S 4)*7：G(GH) G (吸收律) 8：G(GH) G,2020/10/9,5)*9：G(HS)(GH)(GS)(分配律） 10：G(HS)(GH)(GS) 6) 11：GG(同一律) 12：GG 7) 13：G(零律） 14：G 8) 15：GG1(排中律) 9) 16：GG0(矛盾律),基本等價(jià)公式（續(xù)）,2020/10/9,基本等價(jià)公式（續(xù)）,10) 17：(G)G (雙重否定律) 11)*1

30、8：(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：(G ) (G)G (歸謬論),補(bǔ)充*： A(AB)AB A(AB)AB,2020/10/9,這種圖是將G，H理解為某總體論域上的子集合，而規(guī)定GH為兩集合的公共部分（交集合），GH為兩集合的全部（并集合），G為總體論域（如矩形域）中G的補(bǔ)集，將命題中的真值“1”理解為集合中的總體論域（全集），將命題中的真值“0”理解為集合中的空集，則有

31、：,命題與集合之間的關(guān)系,“” 對“”與“”對“”的對比,2020/10/9,設(shè)G(P1,P2,Pn)是一個(gè)命題公式，其中： 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也是一個(gè)永真公式（或永假公式）。,定理3.3.2(代入定理),2020/10/9,例3.3.9,設(shè)(, )()，證明公式G是一個(gè)永真公式。另有兩個(gè)任意公式： (, )()； (, )()。 進(jìn)一步驗(yàn)

32、證代入定理的正確性。,解 建立公式G的真值表如右所示?？梢姙橛勒婀?。,2020/10/9,例3.3.9（續(xù)）,將，代入到中分別取代G中的命題變元P、Q，所得到的公式為： (P, Q) = G(H, S) = (H(HS)S = ()()()() 建立新公式(P, Q)的真值表。,(, )() (, )()； (, )(),2020/10/9,定理3.3.3(替換定理),設(shè)G1是G的子公式(即 G1是公式G的一部分)，H1是任意的命題公式，在G中凡出現(xiàn)G1處都以H1替換后得到新的命題公式H，若G1H1，則GH。,利用24個(gè)基本等價(jià)公式及代入定理和替換定理，可完成公式的轉(zhuǎn)化和等價(jià)判定。 有些教材

33、叫等值演算,利用等值演算證明p(qr) = (pq)r 證p(qr) = p(qr) （蘊(yùn)涵等值式，置換規(guī)則） = (pq)r （結(jié)合律，置換規(guī)則） = (pq)r （德摩根律，置換規(guī)則） = (pq)r （蘊(yùn)涵等值式，置換規(guī)則） 今后在注明中省去置換規(guī)則 注意：用等值演算不能直接證明兩個(gè)公式不等值,2020/10/9,例3.3.10,利用基本的等價(jià)關(guān)系，完成如下工作： （1）判斷公式的類型： 證明 () ()()()是一個(gè)永真公式。 （2）證明公式之間的等價(jià)關(guān)系： 證明() = () （3）化簡公式： 證明(P(R)(R)(PR) = R,練習(xí)：用等值式判斷公式類型(1),(pq) ( q

34、p) = (pq) (pq) （假言易位） =1 永真式,練習(xí)：用等值式判斷公式類型(2),(pq) q = ( pq) q =p q q =0 永假式,練習(xí)：用等值式判斷公式類型(3),(p q) q = (p q) q (得摩根律) = ( p q) q = q (吸收律) 可滿足式,練習(xí)：用等值式判斷公式類型(4),(pq)(qp) = (pq)(qp) （蘊(yùn)涵等值式） = (pq)(pq) （交換律） = 1 重言式,2020/10/9,例3.3.12,將下面程序語言進(jìn)行化簡。 If A then if B then X else Y else if B then X else Y,解

35、：執(zhí)行X的條件為： ()(),執(zhí)行Y的條件為： ()(),3.3.6 命題公式的應(yīng)用,2020/10/9,例3.3.12(續(xù)）,執(zhí)行X的條件可化簡為： ()() ( ) 執(zhí)行Y的條件可化簡為： ()() (),程序可簡化為：If B then X else Y,2020/10/9,例3.3.14,一家航空公司，為了保證安全，用計(jì)算機(jī)復(fù)核飛行計(jì)劃。每臺(tái)計(jì)算機(jī)能給出飛行計(jì)劃正確或有誤的回答。由于計(jì)算機(jī)也有可能發(fā)生故障，因此采用三臺(tái)計(jì)算機(jī)同時(shí)復(fù)核。由所給答案，再根據(jù)“少數(shù)服從多數(shù)”的原則作出判斷，試將結(jié)果用命題公式表示，并加以簡化，畫出電路圖。,2020/10/9,例3.3.14 解,設(shè)C1，C2，

36、C3分別表示三臺(tái)計(jì)算機(jī)的答案。 S表示判斷結(jié)果。,真值表,則根據(jù)真值表，利用聯(lián)結(jié)詞的定義，S可用C1，C2，C3所對應(yīng)的命題公式表示出來，同時(shí)可畫出該命題公式所對應(yīng)的電路圖。,2020/10/9,例3.3.14 解（續(xù)）,S= (C1C2C3)(C1C2C3) (C1C2C3)(C1C2C3) =(C1C1)C2C3)(C1(C2C2) C3)(C1C2(C3C3) =(C2C3)(C1C3)(C1C2),2020/10/9,3.5 公式的標(biāo)準(zhǔn)型范式,3.5.1 析取范式和合取范式 定義3.5.1 （1）命題變元或命題變元的否定稱為文字 （2）有限個(gè)文字的析取稱為析取式(也稱為子句） （3）有

37、限個(gè)文字的合取稱為合取式(也稱為短語） （4）P與 P稱為互補(bǔ)對。,2020/10/9,例子,（1）、是文字； （2）是子句； （3）是短語。,P是一個(gè)子句，這種說法正確么？,一個(gè)命題變元或者其否定既可以是簡單的子句，也可以是簡單的短語。,因此，不但是文字，也是子句、短語,2020/10/9,定義3.5.2,（1）有限個(gè)短語的析取式稱為析取范式 （2）有限個(gè)子句的合取式稱為合取范式,一個(gè)不含最外層括號(hào)的短語（子句）也可以是析取范式（合取范式）。,2020/10/9,例子,（1）、是析取范式、合取范式； （2）是子句、析取范式、合取范式， ( )僅是子句、合取范式； （3） 是短語、析取范式、合

38、取范式， ()僅是短語、析取范式； （4）()()是析取范式； （5）()()是合取范式； （6）句子()、()既不是析取范式也不是合取范式,2020/10/9,總結(jié),（1）單個(gè)的文字是子句、短語、析取范式，合取范式 （2）單個(gè)的子句是析取范式； （3）單個(gè)的短語是合取范式； （4）若單個(gè)的子句（短語）無最外層括號(hào)，則是合取范式（析取范式）； （5）析取范式、合取范式僅含聯(lián)結(jié)詞集， （6） “”聯(lián)結(jié)詞僅出現(xiàn)在命題變元前。,2020/10/9,范式的求解方法,定理3.5.1 對于任意命題公式，都存在與其等價(jià)的析取范式和合取范式。,轉(zhuǎn)換方法：,（1）利用等價(jià)公式中的等價(jià)式和蘊(yùn)涵式將公式中的、用聯(lián)結(jié)

39、詞 、來取代，這可利用如下等價(jià)關(guān)系：,() = ()； () = ()() = ()()。,2020/10/9,范式的求解方法(續(xù)),（2）重復(fù)使用德摩根定律將否定號(hào)移到各個(gè)命題變元的前端，并消去多余的否定號(hào)，這可利用如下等價(jià)關(guān)系：() =； () = ； () = 。,（3）重復(fù)利用分配律，可將公式化成一些合取式的析取，或化成一些析取式的合取，這可利用如下等價(jià)關(guān)系：() = ()()； () = ()()。,2020/10/9,例3.5.1,求公式：()(R)的析取范式和合取范式,解 ()(R),= ()(R)(RP),= (R)( RP）,= ()(R) ()( RP),= (R)合取范式

40、 = R析取范式,2020/10/9,范式的不惟一性,考慮公式： ()()， 其與之等價(jià)的析取范式： ()； ()()； ()()； ()()。 這種不惟一的表達(dá)形式給研究問題帶來了不便。,2020/10/9,3.5.2 主析取范式和主合取范式,1 極小項(xiàng)和極大項(xiàng),定義 3.5.3 在含有n個(gè)命題變元P1、P2、P3、Pn的短語或子句中，若每個(gè)命題變元與其否定不同時(shí)存在，但二者之一恰好出現(xiàn)一次且僅一次，則稱此短語或子句為關(guān)于P1、P2、P3、Pn的一個(gè)極小項(xiàng)或極大項(xiàng)。,對于n個(gè)命題變元，可構(gòu)成2n個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng),2020/10/9,例子,（1）一個(gè)命題變元P， 對應(yīng)的極小項(xiàng)有兩項(xiàng)：P、

41、 P； 對應(yīng)的極大項(xiàng)有兩項(xiàng)：P、 P。 （2）兩個(gè)命題變元P、Q， 對應(yīng)的極小項(xiàng)有四項(xiàng)： PQ、 PQ、P Q、 P Q； 對應(yīng)的極大項(xiàng)有四項(xiàng)： PQ、 PQ、P Q、 P Q。,2020/10/9,例子（續(xù)）,（3）三個(gè)命題變元P、Q、R， 對應(yīng)的極小項(xiàng)有八項(xiàng)： 、 、 、； 對應(yīng)的極大項(xiàng)有八項(xiàng)： 、 、 、。,2020/10/9,兩個(gè)命題變元的所對應(yīng)極小項(xiàng)真值表,注意：（1）沒有等價(jià)的兩個(gè)極小項(xiàng)； （2）使該極小項(xiàng)的真值為真的指派是唯一的,并且 使得其它極小項(xiàng)為假； （3）使極小項(xiàng)為真的那組指派為對應(yīng)極小項(xiàng)的編碼； （4）命題變元與1對應(yīng)，命題變元的否定與0對應(yīng)。,0、0為真 0 0 m0

42、0(m0) 0 1為真0 1 m01(m1) 1 0為真1 0 m10(m2) 1 1為真1 1 m11(m3),2020/10/9,兩個(gè)命題變元的所對應(yīng)極大項(xiàng)真值表,注意：（1）沒有等價(jià)的兩個(gè)極大項(xiàng)； （2）使該極大項(xiàng)的真值為假的指派是唯一的并且 使得其它極大項(xiàng)為真； （3）使極大項(xiàng)為假的那組指派為對應(yīng)極大項(xiàng)的編碼； （4）命題變元與0對應(yīng)，命題變元的否定與1對應(yīng)。,0、0為假 0 0 M00(M0) 0 1為假0 1 M01(M1) 1 0為假1 0 M10(M2) 1 1為假1 1 M11(M3),2020/10/9,三個(gè)命題變元的極小項(xiàng)和極大項(xiàng),mimj=F,2020/10/9,極小項(xiàng)

43、和極大項(xiàng)的性質(zhì),任意兩個(gè)極小項(xiàng)的合取必為假； 任意兩個(gè)極大項(xiàng)的析取必為真； 極大項(xiàng)的否定是極小項(xiàng)； 極小項(xiàng)的否定是極大項(xiàng)； 所有極小項(xiàng)的析取為永真公式； 所有極大項(xiàng)的合取是永假公式。,Mi=mi,MiMj=T,Mi= mi,2020/10/9,2 主析取范式和主合取范式,定義3.5.4 （1）在給定的析取范式中，每一個(gè)短語都是極小項(xiàng)，則稱該范式為主析取范式 （2）在給定的合取范式中，每一個(gè)子句都是極大項(xiàng)，則稱該范式為主合取范式 （3）如果一個(gè)主析取范式不包含任何極小項(xiàng)，則稱該主析取范式為“空”；如果一個(gè)主合取范式不包含任何極大項(xiàng)，則稱主合取范式為“空”。,2020/10/9,定理3.5.2,任

44、何一個(gè)公式都有與之等價(jià)的主析取范式和主合取范式。,證明（1）利用定理3.5.1先求出該公式所對應(yīng)的析取范式和合取范式；,（2）在析取范式的短語和合取范式的子句中重復(fù)出現(xiàn)的命題變元，將其化成只出現(xiàn)一次；,（3）去掉析取范式中的所有永假式（ PP ）， 去掉合取范式中所有永真式（ PP ）,2020/10/9,定理3.5.2 證明（續(xù)）,（4）若析取范式的某一個(gè)短語中缺少該命題公式中所規(guī)定的命題變元，則可用公式：()Q = Q將命題變元P補(bǔ)進(jìn)去，并利用分配律展開，然后合并相同的短語，此時(shí)得到的短語將是標(biāo)準(zhǔn)的極小項(xiàng) 若合取范式的某一個(gè)子句中缺少該命題公式中所規(guī)定的命題變元，則可用公式：()Q = Q

45、 將命題變元P補(bǔ)進(jìn)去，并利用分配律展開，然后合并相同的子句，此時(shí)得到的子句將是標(biāo)準(zhǔn)的極大項(xiàng)；,2020/10/9,證明（續(xù)）,（5）利用等冪律將相同的極小項(xiàng)和極大項(xiàng)合并，同時(shí)利用交換律進(jìn)行順序調(diào)整，由此可轉(zhuǎn)換成標(biāo)準(zhǔn)的主析取范式和主合取范式。,2020/10/9,3 求主析取范式和主合取范式的方法,主范式,2020/10/9,例3.5.2,利用等價(jià)公式轉(zhuǎn)換法求公式(PQ)(QR)的主析取范式和主合取范式 。,解 （1）求主析取范式 (PQ)(QR)= (PQ)(QR),=(PQ)(QR) 析取范式,= (PQ(RR)(PP)QR),= (PQR)(PQR)(PQR) (PQR) 主析取范式,20

46、20/10/9,例3.5.2（續(xù)）,（2）求主合取范式 (PQ)(QR)= (PQ)(QR) =(PQ)(PR)(QQ)(QR) = (PQ)(PR)(QR)合取范式,2020/10/9,例3.5.2（續(xù)）,=(PQ(RR)(P(QQ)R) (PP)QR) = (PQR)(PQR)(PQR) (PQR)(PQR) (PQR) = (PQR)(PQR) (PQR)(PQR) 主合取范式,2020/10/9,需要說明,求任何一個(gè)公式的主析取范式和主合取范式不僅要取決于該公式，而且取決于該公式所包含的命題變元。,如公式： G1 = (PQ)Q， G2(P, Q, R) = (PQ)Q。 前者是依賴于

47、兩個(gè)命題變元的，后者應(yīng)依賴于三個(gè)命題變元。,2020/10/9,如何用極小項(xiàng)來構(gòu)成主析取范式？,m1必須包含在 主析取范式中,m0必須包含在 主析取范式中,m3必須包含在 主析取范式中,m2一定不能包含 在主析取范式中,主析取范式中必須且只能包含使得公式 真值為真的那些解釋對應(yīng)的極小項(xiàng)。,P-Q 與m0m1m3 一定等價(jià),2020/10/9,如何用極大項(xiàng)來構(gòu)成主合取范式？,M1必須包含在 主合取范式中,M2必須包含在 主合取范式中,M0一定不能包含 在主合取范式中,M3一定不能包含 在主合取范式中,主合取范式中必須且只能包含使得公式 真值為假的那些解釋對應(yīng)的極大項(xiàng)。,2020/10/9,真值表

48、技術(shù),（1）列出公式對應(yīng)的真值表，選出公式的真值結(jié)果為真的所有的行，在這樣的每一行中，找到其每一個(gè)解釋所對應(yīng)的極小項(xiàng)，將這些極小項(xiàng)進(jìn)行析取即可得到相應(yīng)的主析取范式。,（2）列出公式對應(yīng)的真值表，選出公式的真值結(jié)果為假的所有的行，在這樣的每一行中，找到其每一個(gè)解釋所對應(yīng)的極大項(xiàng)，將這些極大項(xiàng)進(jìn)行合取即可得到相應(yīng)的主合取范式。,2020/10/9,例3.5.4,利用真值表技術(shù)求公式G = ()的主析取范式和主合取范式。,2020/10/9,例3.5.4（續(xù)）,（1）求主析取范式 找出真值表中其真值為真的行： 2. 0 0 1； 4. 0 1 1； 5. 1 0 0； 6. 1 0 1； 8. 1

49、1 1。 這些行所對應(yīng)的極小項(xiàng)分別為： P， P，P， P，P。,2020/10/9,例3.5.4（續(xù)）,將這些極小項(xiàng)進(jìn)行析取即為該公式G的主析取范式。 G = () = (P)(P) (P)(P)(P),2020/10/9,例3.5.4（續(xù)）,（2）求主合取范式 找出真值表中其真值為假的行： 10 0 0； 30 1 0； 71 1 0。 這些行所對應(yīng)的極大項(xiàng)分別為： P、P 、 將這些極大項(xiàng)進(jìn)行合取即為該公式G的主合取范式： G = () =(P)(P)(),2020/10/9,4 主析取范式和主合取范式之間的轉(zhuǎn)換,（1）已知公式G的主析取范式，求公式G的主合取范式,（a）求G的主析取范式

50、，即G的主析取范式中沒有出現(xiàn)過的極小項(xiàng)的析取，若,為的主析取范式。其中，mji(i=1,2,2n-k)是mi(i=0,2n-1)中去掉mli(i=,k)后剩下的極小項(xiàng)。,為的主析取范式，則,2020/10/9,主析取范式主合取范式,（b）G=(G)即是G的主合取范式。即，,為G 的主合取范式。,2020/10/9,主合取范式主析取范式,（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)。,為的主合取范式，則

51、,2020/10/9,主合取范式主析取范式,（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)。,2020/10/9,主合取范式主析取范式,（b）G=(G)即是G的主析取范式。即，,為G 的主析取范式。,2020/10/9,例3.5.5,設(shè)=()()()，求其對應(yīng)的主析取范式和主合取范式。,解 = ()()( ),=()() (),= ()()() ()()(),= ()()() ()()(),= m0m1m3m4m6m7 主析取范式,2020/10/9,例3.5.5（續(xù)）,= m2m5 = (m2m5) m2 m5= M2M5 =()() 主合取范式,補(bǔ)充：命題公式如何化為主析取范式 例1. 用真值表求出PQ的主析取范式 P Q PQ 0 0 1 0 1 1 1 0 0 1 1 1 所以PQ ( P Q) （ P Q ) （P Q） m0 m1 m3,補(bǔ)充： 例2 .用真值表求出PQ的主合取范式 P Q PQ 0 0 1 0 1 1 1 0 0 1