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

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

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

4、020/10/9,3.2.1 命題 定義3.2.1具有確切真值的陳述句稱為命題, 該命題可以取一個“值”，稱為真值。 真值只有“真”和“假”兩種， 分別用“”(或“”)和“”(或“”)表示。,3.2 命題與命題聯(lián)結詞,2020/10/9,（1）太陽是圓的； （2）成都是一個旅游城市； （3）北京是中國的首都； （4）這個語句是假的； （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）把門關上； （13）滾出去！ （14）你要出去嗎？ （15）今天天氣真好?。?非命題,非命題,非命題,非命題,注意： 一切沒有判斷內容的句子都不能作為命題，如命令句、感嘆句、疑問句、祈使句、二義性的陳述句等。,2020/10/9,命題一定是陳述句，但并非一切陳述句都是命題。 命題的真值有時可明確給出，有時還需要依靠環(huán)境、條件、實際情況時間才能確定其真值。,結論：,在數(shù)理邏輯中像字母“x”、“y”、“z”等字母總是表示變量。,約定：,2020/10/9,下列語句是否是命題？并判斷其真值結果？ （1）四川不是一個國家； （2）3既是素數(shù)又是奇數(shù)； （3）張謙是大學生

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

7、Bi 、Ci、.Pi、Qi、Ri、.等表示命題,2020/10/9,3.2.2 命題聯(lián)結詞,設命題P,Q表示任意兩個命題,則最常見的命題聯(lián)結詞有：,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.蘊涵,若P,則Q,P蘊涵Q,PQ,PQ=0 P=1,Q=0,5.等價,P當且僅當Q,P等價于Q,PQ,PQ=1P=1,Q=1 或P=0,Q=0,例如：命題P：2是素數(shù)；Q：北京是中國的首都,1.否定聯(lián)結詞,設p為命題，則p的否定是一個復合命題，記作： p ，讀作“非p”或“

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

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

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

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

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

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

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

15、(4) 2 + 2 4 當且僅當 美國位于非洲.,1,0,1,0,符號化命題，并指出它們的真值,是有理數(shù)是不對的(p) 2是偶素數(shù)(p,q) 2或者4是素數(shù)(p,r) 如果2是素數(shù)，則3也是素數(shù)(p,s) 2是素數(shù)當且僅當3也是素數(shù)(p,s) p ：1 p q ：1 p r ：1 p s ：1 p s ：1,2020/10/9,總結,2020/10/9,說明,1、聯(lián)結詞是句子與句子之間的聯(lián)結，而非單純的名詞、形容詞、數(shù)詞等地聯(lián)結； 2、聯(lián)結詞是兩個句子真值之間的聯(lián)結，而非句子的具體含義的聯(lián)結，兩個句子之間可以無任何地內在聯(lián)系；,2020/10/9,說明,3、聯(lián)結詞與自然語言之間的對應并非一一對

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

17、示為。,2020/10/9,（4）設：周末天氣晴朗； ：學院將組織我們到石像湖春游。 則命題（4）可表示為。 （5）設：兩個三角形全等； ：三角形的三條邊全部相等。 則命題（5）可表示為。,例3.2.4 解(續(xù)),2020/10/9,為了不使句子產生混淆，作如下約定，命題聯(lián)結詞之優(yōu)先級如下：,否定合取析取蘊涵等價 同級的聯(lián)結詞，按其出現(xiàn)的先后次序(從左到右) 若運算要求與優(yōu)先次序不一致時，可使用括號；同級符號相鄰時，也可使用括號。括號中的運算為最優(yōu)先級。,約 定,2020/10/9,設命題P：明天上午七點下雨；Q：明天上午七點下雪； R：我將去學校。 符號化下述語句： 如果明天上午七點不是雨夾

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

19、R,(PQ)R,(PQ)R,2020/10/9,設P:雪是白色的;Q:2+2=4。將下列命題符號化： （1）因為雪是白色的，所以2+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）雪是白色的當且僅當2+2=4； P Q,2020/10/9,3.2.4 命題聯(lián)結詞的應用,例 3.2.7 用復合命題表示如下圖所示的開關電路：,圖3.2.1 圖3.2.2 圖3.2.3,AB,AB,A,設：開關閉

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

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

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

23、做到身體好,Q：我們要做到學習好, R：我們要做到工作好，S：我們要為祖國四化建設而奮斗，則有： 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 設P1、P2、Pn是出現(xiàn)在公式G中的所有命題變元，指定P1、P2、Pn一組真值，則這組真值稱為G的一個解釋,常記為。 一般來說，若有個命題變元，則應有2n個不同的解釋。 如果公式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ù)）,進一步化簡為：,成真賦值， 成假賦值？,練習：,寫出下列公式的真值表, 并求它們的成真賦值和成假賦值 (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,從這三個真值表可以看到一個非常有趣的事實：,公式G1對所有可能的解釋具有“真”值 公式G3對所有可能的解釋均具有“假”值 公式G2則具有“真”和“假”值,結論,2020/10/9,定義3.3.5,公式G稱為永真公式(重言式)，如果在它的所有解釋之下都為“真”。 公式G稱為永假公式(矛盾式),如果在它的所有解釋之下都為“假”。 公式G稱為可滿足的，如果它不是永假的。,2020/10/9,從上述定義可知三種特殊公式之間的關系：,永真式G的否定G是矛盾式；矛盾式G的否定G是永真式。 永真式一定是可滿足式,可滿足式不一定是永真式 可滿足式的否定不

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

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

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

29、，S是任何的公式，則：,基本等價公式,1) 1：GGG (冪等律) 2：GGG 2) 3：GHHG (交換律) 4：GHHG 3)*5：G(HS)(GH)S(結合律) 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(矛盾律),基本等價公式（續(xù)）,2020/10/9,基本等價公式（續(xù)）,10) 17：(G)G (雙重否定律) 11)*1

30、8：(GH)GH (De MoRGan定律) 19：(GH)GH。 12)*20: (GH)(GH)(HG)(等價) 13)*21：(GH)(GH) (蘊涵) 14) E22：G G。 (假言易位) 15) E23：G G。 (等價否定等式) 16) E24：(G ) (G)G (歸謬論),補充*： A(AB)AB A(AB)AB,2020/10/9,這種圖是將G，H理解為某總體論域上的子集合，而規(guī)定GH為兩集合的公共部分（交集合），GH為兩集合的全部（并集合），G為總體論域（如矩形域）中G的補集，將命題中的真值“1”理解為集合中的總體論域（全集），將命題中的真值“0”理解為集合中的空集，則有

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

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(替換定理),設G1是G的子公式(即 G1是公式G的一部分)，H1是任意的命題公式，在G中凡出現(xiàn)G1處都以H1替換后得到新的命題公式H，若G1H1，則GH。,利用24個基本等價公式及代入定理和替換定理，可完成公式的轉化和等價判定。 有些教材

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

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

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

36、C3分別表示三臺計算機的答案。 S表示判斷結果。,真值表,則根據(jù)真值表，利用聯(lián)結詞的定義，S可用C1，C2，C3所對應的命題公式表示出來，同時可畫出該命題公式所對應的電路圖。,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 公式的標準型范式,3.5.1 析取范式和合取范式 定義3.5.1 （1）命題變元或命題變元的否定稱為文字 （2）有限個文字的析取稱為析取式(也稱為子句） （3）有

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

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

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

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

41、 P； 對應的極大項有兩項：P、 P。 （2）兩個命題變元P、Q， 對應的極小項有四項： PQ、 PQ、P Q、 P Q； 對應的極大項有四項： PQ、 PQ、P Q、 P Q。,2020/10/9,例子（續(xù)）,（3）三個命題變元P、Q、R， 對應的極小項有八項： 、 、 、； 對應的極大項有八項： 、 、 、。,2020/10/9,兩個命題變元的所對應極小項真值表,注意：（1）沒有等價的兩個極小項； （2）使該極小項的真值為真的指派是唯一的,并且 使得其它極小項為假； （3）使極小項為真的那組指派為對應極小項的編碼； （4）命題變元與1對應，命題變元的否定與0對應。,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,兩個命題變元的所對應極大項真值表,注意：（1）沒有等價的兩個極大項； （2）使該極大項的真值為假的指派是唯一的并且 使得其它極大項為真； （3）使極大項為假的那組指派為對應極大項的編碼； （4）命題變元與0對應，命題變元的否定與1對應。,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,三個命題變元的極小項和極大項,mimj=F,2020/10/9,極小項

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

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

45、 將命題變元P補進去，并利用分配律展開，然后合并相同的子句，此時得到的子句將是標準的極大項；,2020/10/9,證明（續(xù)）,（5）利用等冪律將相同的極小項和極大項合并，同時利用交換律進行順序調整，由此可轉換成標準的主析取范式和主合取范式。,2020/10/9,3 求主析取范式和主合取范式的方法,主范式,2020/10/9,例3.5.2,利用等價公式轉換法求公式(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,需要說明,求任何一個公式的主析取范式和主合取范式不僅要取決于該公式，而且取決于該公式所包含的命題變元。,如公式： G1 = (PQ)Q， G2(P, Q, R) = (PQ)Q。 前者是依賴于

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

48、技術,（1）列出公式對應的真值表，選出公式的真值結果為真的所有的行，在這樣的每一行中，找到其每一個解釋所對應的極小項，將這些極小項進行析取即可得到相應的主析取范式。,（2）列出公式對應的真值表，選出公式的真值結果為假的所有的行，在這樣的每一行中，找到其每一個解釋所對應的極大項，將這些極大項進行合取即可得到相應的主合取范式。,2020/10/9,例3.5.4,利用真值表技術求公式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。 這些行所對應的極小項分別為： P， P，P， P，P。,2020/10/9,例3.5.4（續(xù)）,將這些極小項進行析取即為該公式G的主析取范式。 G = () = (P)(P) (P)(P)(P),2020/10/9,例3.5.4（續(xù)）,（2）求主合取范式 找出真值表中其真值為假的行： 10 0 0； 30 1 0； 71 1 0。 這些行所對應的極大項分別為： P、P 、 將這些極大項進行合取即為該公式G的主合取范式： G = () =(P)(P)(),2020/10/9,4 主析取范式和主合取范式之間的轉換,（1）已知公式G的主析取范式，求公式G的主合取范式,（a）求G的主析取范式

50、，即G的主析取范式中沒有出現(xiàn)過的極小項的析取，若,為的主析取范式。其中，mji(i=1,2,2n-k)是mi(i=0,2n-1)中去掉mli(i=,k)后剩下的極小項。,為的主析取范式，則,2020/10/9,主析取范式主合取范式,（b）G=(G)即是G的主合取范式。即，,為G 的主合取范式。,2020/10/9,主合取范式主析取范式,（1）已知公式G的主合取范式，求公式G的主析取范式,（a）求G的主合取范式，即G的主合取范式中沒有出現(xiàn)過的極大項的合取，若,為的主合取范式。其中，Mji(i=1,2,2n-k)是Mi(i=0,2n-1)中去掉Mli(i=,k)后剩下的極大項。,為的主合取范式，則

51、,2020/10/9,主合取范式主析取范式,（2）已知公式G的主合取范式，求公式G的主析取范式 （a）求G的主合取范式，即G的主合取范式中沒有出現(xiàn)過的極大項的合取，若 為的主合取范式，則 為的主合取范式。 其中，mji (i=1,2,2n-k)是Mi(i=0,2n-1)中去掉mli (i=,k)后剩下的極大項。,2020/10/9,主合取范式主析取范式,（b）G=(G)即是G的主析取范式。即，,為G 的主析取范式。,2020/10/9,例3.5.5,設=()()()，求其對應的主析取范式和主合取范式。,解 = ()()( ),=()() (),= ()()() ()()(),= ()()() ()()(),= m0m1m3m4m6m7 主析取范式,2020/10/9,例3.5.5（續(xù)）,= m2m5 = (m2m5) m2 m5= M2M5 =()() 主合取范式,補充：命題公式如何化為主析取范式 例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,補充： 例2 .用真值表求出PQ的主合取范式 P Q PQ 0 0 1 0 1 1 1 0 0 1