離散數(shù)學(xué)教案.ppt

1、1,離散數(shù)學(xué) 課程學(xué)時(shí)：14 講 授：倪紅,2,課程性質(zhì),離散數(shù)學(xué)（又稱(chēng)計(jì)算機(jī)數(shù)學(xué)）是現(xiàn)代數(shù)學(xué)的重要分支，是計(jì)算機(jī)專(zhuān)業(yè)核心基礎(chǔ)課程之一。,3,課程目標(biāo),離散數(shù)學(xué)是以研究離散量的結(jié)構(gòu)和相互之間的關(guān)系為主要目標(biāo)，其研究對(duì)象一般為：有限或可數(shù)個(gè)元素（例如：自然數(shù)、整數(shù)、真假值、有限個(gè)結(jié)點(diǎn)等），而離散性也是計(jì)算機(jī)科學(xué)的顯著特點(diǎn)。,4,與其他課程的關(guān)系,離散數(shù)學(xué)與計(jì)算機(jī)科學(xué)的其他課程,如：數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、算法分析、邏輯設(shè)計(jì)、系統(tǒng)結(jié)構(gòu)、容錯(cuò)技術(shù)、人工智能等有密切的聯(lián)系。它是這些課程的先導(dǎo)和基礎(chǔ)課程。,5,離散數(shù)學(xué) 高等教育出版社 耿素云、屈婉玲著,教材與參考書(shū),6,課程內(nèi)容,本課程根據(jù)大綱的

2、內(nèi)容和相關(guān)獨(dú)立性， 可分為四大部分 第一部分 數(shù)理邏輯 包括命題邏輯;謂詞邏輯 第二部分 集合論 包括集合與關(guān)系;函數(shù),7,課程內(nèi)容,第三部分 代數(shù)系統(tǒng) 包括代數(shù)結(jié)構(gòu);格與布爾代數(shù) 第四部分 圖論,8,學(xué)習(xí)方法,定義、定理多。 本課內(nèi)容定義定理例題 為了學(xué)好這門(mén)課，要求： （）弄懂定義、定理，弄懂例題，加深對(duì)定義、定理的理解； （）在復(fù)習(xí)基礎(chǔ)上，做好課外作業(yè)。同學(xué)之間可以討論，但要弄懂弄通。 （3）做好課堂筆記。,9,第一篇 數(shù)理邏輯,邏輯學(xué):研究思維形式及思維規(guī)律的科學(xué)。 邏輯學(xué)分為二類(lèi)： 辯證邏輯:是研究事物發(fā)展的客觀規(guī)律。 形式邏輯:對(duì)思維的形式結(jié)構(gòu)和規(guī)律進(jìn)行研究。 數(shù)理邏輯：是用數(shù)學(xué)的

3、方法研究概念、 判斷和推理的科學(xué)，屬于形式邏輯。,10,第一篇 數(shù)理邏輯,在數(shù)理邏輯中，用數(shù)學(xué)的方法是指引進(jìn)一套符號(hào)體系的方法來(lái)研究概念、判斷和推理。即對(duì)符號(hào)進(jìn)行判斷和推理。 數(shù)理邏輯分為四大分支：證明論、模型論、遞歸論和公理集合論。我們這里介紹的是屬于四大分支的共同基礎(chǔ)古典數(shù)理邏輯(命題邏輯和謂詞邏輯)。,11,第一章 命題邏輯,1.1 命題 1.2 命題聯(lián)結(jié)詞 1.3 命題公式 1.4 等價(jià)式 1.5 永真蘊(yùn)含式 1.6 其他命題聯(lián)結(jié)詞 1.7 范 式 1.8 推論理論,12,第一章 命題邏輯,教學(xué)目的及要求： 深刻理解和掌握命題邏輯中基本概念和基本方法。 教學(xué)內(nèi)容： 命題及表示、聯(lián)結(jié)詞、

4、命題公式與翻譯、真值表與等價(jià)公式、重言式與蘊(yùn)涵式、對(duì)偶與范式、推理理論。 教學(xué)重點(diǎn)： 命題邏輯中的基本概念和基本推理方法。 教學(xué)難點(diǎn)：推理理論。,13,1.1 命題,定義： 具有確定真假值的陳述句叫命題。 討論定義： （1）命題可以是真的，或者是假的，但不能 同時(shí)為真又為假。 （2）命題分類(lèi)： )原子命題（基本命題、本原命題）： 不能分解成為更簡(jiǎn)單的命題。 例：我是一位學(xué)生。,14,1.1 命題,)分子命題（復(fù)合命題）：若干個(gè)原子 命題使用適當(dāng)?shù)穆?lián)結(jié)詞所組成的新命題 例：我是一位學(xué)生和他是一位工人 （3）命題所用符號(hào)：常用大寫(xiě)個(gè)英文字母 表示命題。用、表示。 （4）命題中所有的“真”用“”表示

5、， 命題中所有的“假”用“”表示。,15,1.1 命題,例：判斷下列語(yǔ)句是否為命題。 陳述句一般為命題 （1）十是整數(shù)。 （） （2）上海是一個(gè)村莊。（） （3）今天下雨。 （4）加拿大是一個(gè)國(guó)家。（） （5）是偶數(shù)而是奇數(shù)。（T） （6）她不是護(hù)士。 （7） （8）今天是星期天。,16,1.1 命題,命令句，感嘆句，疑問(wèn)句均不是命題。 （1）把門(mén)關(guān)上！ （2）你到哪里去？ 語(yǔ)句既為真，同時(shí)又包含假的不是命題，這樣的句子稱(chēng)為“悖論”。 （3）他正在說(shuō)謊。 （在命題邏輯中不討論這類(lèi)問(wèn)題）,17,1.2 命題聯(lián)結(jié)詞,在命題演算中也有類(lèi)似的日常生活中的聯(lián)結(jié)詞稱(chēng)做： “命題聯(lián)結(jié)詞”,下面先介紹五個(gè)常用

6、的命題聯(lián)結(jié)詞。 否定詞：（否定運(yùn)算、非運(yùn)算） （）符號(hào) ,讀作“非”，“否定” 設(shè)命題為，則在的前面加否定詞 ，變成，讀做“的否定”或“非”,18,1.2 命題聯(lián)結(jié)詞,（）定義 P的真值表： （）舉例： ：每一種生物均是動(dòng)物。F ：有一些生物不是動(dòng)物。T 這里不能講成“每一種生物都不是動(dòng)物”。 對(duì)量化命題的否定，除對(duì)動(dòng)詞進(jìn)行否定外，同時(shí)對(duì)量化詞也要加以否定。,19,1.2 命題聯(lián)結(jié)詞,合取詞（“合取”、“積”、“與”運(yùn)算） (1)符號(hào)“” 設(shè)，為兩個(gè)命題，則稱(chēng)與的合 取，讀作：“與”、“與的合取”、“并 且”等。 (2)定義（由真值表給出）：,20,1.2 命題聯(lián)結(jié)詞,的真值表 ：,21,1.

7、2 命題聯(lián)結(jié)詞,當(dāng)且僅當(dāng)和的真值均為“”，則（） 的真值為“”。否則，其真值為“”。 注意：和是互為獨(dú)立的；地位是平等的，和的位置可以交換而不會(huì)影響的結(jié)果。,22,1.2 命題聯(lián)結(jié)詞,(3)舉例： (a) P：王華的成績(jī)很好 Q：王華的品德很好。 則：王華的成績(jī)很好并且品德很好。 (b)P：我們?nèi)シN樹(shù) Q：房間里有一臺(tái)電視機(jī) 則：我們?nèi)シN樹(shù)與房間里有一臺(tái)電視機(jī)。,23,1.2 命題聯(lián)結(jié)詞,(c) P：今天下大雨 Q：3+3=6 則：今天下大雨和3+3=6 由例(b)(c)可見(jiàn)，在日常生活中，合取詞應(yīng)用在二個(gè)有關(guān)系的命題之間。而在邏輯學(xué)中，合取詞可以用在二個(gè)毫不相干的命題之間。,24,1.2 命

8、題聯(lián)結(jié)詞,(d)P: 王大和王二是親兄弟。 Q: 他打開(kāi)箱子然后拿出一件衣服來(lái)。 該語(yǔ)句不是合取聯(lián)結(jié)詞組成的命題。,25,1.2 命題聯(lián)結(jié)詞,析取詞（或運(yùn)算） （）符號(hào)“” 設(shè)、為二個(gè)命題，則（）稱(chēng)作與的“析取”，讀作：“或”。 （）定義（由真值表給出）：,26,1.2 命題聯(lián)結(jié)詞,當(dāng)且僅當(dāng)、均為“”時(shí)，（）為“”。否則，其真值為“”,的真值表：,27,1.2 命題聯(lián)結(jié)詞,區(qū)分“可兼或”與“不可兼或（異或，排斥或）” “可兼或”即P或Q為“T”時(shí)（PQ）為“T”，是析取。 例如： 燈泡有故障或開(kāi)關(guān)有故障。 今晚寫(xiě)字或看書(shū)。 今天下雨或打雷。 以上例句均為“可兼或”。,28,1.2 命題聯(lián)結(jié)詞,

9、“不可兼或”即P和Q的真值不同時(shí)，PQ為T(mén)。 （異或用“”表示）不是析取。,PQ的真值表：,29,1.2 命題聯(lián)結(jié)詞,例： 他通過(guò)電視看雜技或到劇場(chǎng)看雜技。 他乘火車(chē)去北京或乘飛機(jī)去北京。 以上兩句均為“不可兼或”。,30,1.2 命題聯(lián)結(jié)詞,單條件聯(lián)結(jié)詞： （）符號(hào)“”，讀作：“如果則” 、為二個(gè)命題，（）為新的命題，讀作：“如果則” 。 （）定義 （由真值表給出）,31,1.2 命題聯(lián)結(jié)詞,的真值表：,32,1.2 命題聯(lián)結(jié)詞,當(dāng)為“”，為“”時(shí)，則（）為“”， 否則（）均為“”。 ：稱(chēng)為前件、條件、前提、假設(shè) ：稱(chēng)為后件、結(jié)論。 （）舉例： P：我拿起一本書(shū) Q：我一口氣讀完了這本書(shū),3

10、3,1.2 命題聯(lián)結(jié)詞,PQ：如果我拿起一本書(shū)，則我一口氣讀完 了這本書(shū)。 (b) P：月亮出來(lái)了 Q：33=9 PQ：如果月亮出來(lái)了，則33=9。 通常稱(chēng)： (a)為形式條件命題前提和結(jié)果有某種形式 和內(nèi)容上的聯(lián)系。,34,1.2 命題聯(lián)結(jié)詞,(b)為實(shí)質(zhì)條件命題前提和結(jié)果可以有聯(lián) 系，也可以沒(méi)有聯(lián)系，只要滿足單條件命 題的定義。 所以,是形式條件命題一定是實(shí)質(zhì)條件命題,反 之不一定?！啊笔菍?shí)質(zhì)條件命題。 例：我買(mǎi)到了魚(yú)；:我吃魚(yú)。 ：如果我買(mǎi)到了魚(yú)，則我吃魚(yú)。 但“如果我沒(méi)買(mǎi)到魚(yú)，則我吃魚(yú)”，在日常生活中不可能，但在單條件命題的定義中是允許的。,35,1.2 命題聯(lián)結(jié)詞,可以證明： Q P

11、 原命題 逆反命題 逆命題 反命題,36,1.2 命題聯(lián)結(jié)詞,列出真值表,由真值表得： 原命題逆反命題；逆命題反命題。,37,5雙條件聯(lián)結(jié)詞（等價(jià)聯(lián)結(jié)詞）： （）符號(hào)“”，讀作：“當(dāng)且僅當(dāng)” 、為二個(gè)命題，（）為新的命題，讀作：“當(dāng)且僅當(dāng)” 。 （）定義 （由真值表給出）,38,1.2 命題聯(lián)結(jié)詞,P Q的真值表: 每當(dāng)和的真值相同時(shí)，則（）的真值為“”，否則（ ）的真值為“”。,39,1.2 命題聯(lián)結(jié)詞,（）舉例： （a）設(shè) ：ABC是等腰三角形 ：ABC有兩只角相等 ：ABC是等腰三角形當(dāng)且僅當(dāng) 有兩只角相等。,40,1.2 命題聯(lián)結(jié)詞,（b）下面均為等價(jià)聯(lián)結(jié)詞： 春天來(lái)了當(dāng)且僅當(dāng)燕子飛回

12、來(lái)了。 平面上二直線平行，當(dāng)且僅當(dāng)二直線不相交。 當(dāng)且僅當(dāng)雪是白色的。,41,1.2 命題聯(lián)結(jié)詞,（）,中，、的地位是平等的，、 交換位置不會(huì)改變真值表中的值。 （）當(dāng)且僅當(dāng) 僅當(dāng) 當(dāng)且,42,1.2 命題聯(lián)結(jié)詞,命題聯(lián)結(jié)詞在使用中的優(yōu)先級(jí) （）先括號(hào)內(nèi)，后括號(hào)外 （）運(yùn)算時(shí)聯(lián)結(jié)詞的優(yōu)先次序?yàn)椋?（由高到低） （）聯(lián)結(jié)詞按從左到右的次序進(jìn)行運(yùn)算 （）最外層的括號(hào)一律均可省去 （）可寫(xiě)成,43,1.2 命題聯(lián)結(jié)詞,例 （）可省去括號(hào) 因?yàn)椤啊边\(yùn)算是可結(jié)合的。 而（）中的括號(hào)不能省去，因“”不滿足結(jié)合律。,44,1.2 命題聯(lián)結(jié)詞,命題聯(lián)結(jié)詞小結(jié)： （1）五個(gè)聯(lián)結(jié)詞的含義與日常生活中的聯(lián)結(jié)詞 的含

13、義大致相同。 （2）“或”可分為可兼或（）和異或（ ） （不可兼或） （3） “”為一元運(yùn)算，其余四個(gè)均為二元運(yùn)算。,45,1.2 命題聯(lián)結(jié)詞,(4) “”分為形式條件和實(shí)質(zhì)條件命題，當(dāng)前件為“”時(shí)，不論后件怎樣，則單條件命題的真值均為“”。 (5)命題聯(lián)結(jié)詞是命題或命題之間的聯(lián)結(jié)詞，而不是名詞之間、數(shù)字之間和動(dòng)詞之間的聯(lián)結(jié)詞。,46,1.2 命題聯(lián)結(jié)詞,以上介紹了五種常用的聯(lián)結(jié)詞及其相應(yīng)的復(fù)合命題形式。數(shù)理邏輯的特點(diǎn)是把邏輯推理變成類(lèi)似數(shù)學(xué)演算的完全形式化了的邏輯演算，為此，首先要把推理所涉及到的各命題符號(hào)化。 步驟如下： 找出各簡(jiǎn)單命題，分別符號(hào)化。 找出各聯(lián)結(jié)詞，把簡(jiǎn)單命題逐個(gè)聯(lián)結(jié)起來(lái)。

14、,47,1.2 命題聯(lián)結(jié)詞,例. 將下列命題符號(hào)化： （1）李明是計(jì)算機(jī)系的學(xué)生，他住在312室或 313室。 （2）張三和李四是朋友。 （3）雖然交通堵塞，但是老王還是準(zhǔn)時(shí)到達(dá)了 車(chē)站。 （4）只有一個(gè)角是直角的三角形才是直角三角 形。 （5）老王或小李中有一個(gè)去上海出差。,48,1.2 命題聯(lián)結(jié)詞,解： （1）首先用字母表示簡(jiǎn)單命題。 P：李明是計(jì)算機(jī)系的學(xué)生。 Q：李明住在312室。 R：李明住在313室。 該命題符號(hào)化為：P（QR） （2）張三和李四是朋友。是一個(gè)簡(jiǎn)單句 該命題符號(hào)化為：P,49,1.2 命題聯(lián)結(jié)詞,（3）首先用字母表示簡(jiǎn)單命題。 P：交通堵塞。 Q：老王準(zhǔn)時(shí)到達(dá)了車(chē)站

15、。 該命題符號(hào)化為：PQ （4）首先用字母表示簡(jiǎn)單命題。 P：三角形的一個(gè)角是直角。 Q：三角形是直角三角形。 該命題符號(hào)化為：P Q,50,1.2 命題聯(lián)結(jié)詞,（5）首先用字母表示簡(jiǎn)單命題。 P：老王去上海出差。 Q：小李去上海出差。 該命題符號(hào)化為：P Q 也可符號(hào)化為：（PQ）（PQ）或者 （P Q） （PQ）,51,1.3 命題公式,約定： （）我們只注意命題的真假值，而不再去注意命題的漢語(yǔ)意義。 （）對(duì)命題聯(lián)結(jié)詞，我們只注意真值表的定義，而不注意它日常生活中的含義。,52,1.3 命題公式,命題公式 命題常元：表示確定的命題T，F(xiàn)。 命題變?cè)阂哉婕贋槠渥冇蛑冊(cè)驔](méi)有指定真值的命

16、題。常用大寫(xiě)英文字母表示。 命題公式：由命題變?cè)⒊Ｔ?、?lián)結(jié)詞、括號(hào)， 以規(guī)定的格式聯(lián)結(jié)起來(lái)的字符串。,53,1.3 命題公式,定義命題公式(wff)可按下述法則來(lái)生成： ）單個(gè)的命題變?cè)且粋€(gè)命題公式。 ）若是命題公式，也為命題公式。 ）若、是命題公式，則（）、 （）、（）、（）均為命題公式。 ）當(dāng)且僅當(dāng)有限次使用（）（）（）所得到的包含有命題變?cè)兔}常元，聯(lián)結(jié)詞，括號(hào)的符號(hào)串才是命題公式。,54,1.3 命題公式,例如：(PQ)，(P(QR)，(PQ)R)，P都是命題公式。而(P)，(P)都不是命題公式 命題公式的真值表 : 命題變?cè)锰囟ǖ拿}來(lái)取代，這一過(guò)程稱(chēng)為對(duì)該命題變?cè)M(jìn)行真值指

17、派。 命題公式可以看成是一個(gè)以真假值為定義域和真假值為值域的一個(gè)函數(shù)。寫(xiě)成(x),55,1.3 命題公式,例如：公式 P (Q R) 定義三元函數(shù) Y(P，Q，R) P (Q R) 定義命題公式A在其所有可能的賦值下取得的值列成的表稱(chēng)為A的真值表。,56,1.3 命題公式,構(gòu)造真值表的步驟如下： 1)找出給定命題公式中所有的命題變?cè)?出所有可能的賦值。 2)按照從低到高順序?qū)懗雒}公式的各層次。 3)對(duì)應(yīng)每個(gè)賦值，計(jì)算命題公式各層次的值，直到最后計(jì)算出整個(gè)命題公式的值。,57,1.3 命題公式,例構(gòu)造命題公式（）的真值表：,58,1.3 命題公式,例寫(xiě)出命題公式 （）的真值表,59,1.3

18、 命題公式,由上二例可見(jiàn)，個(gè)命題變?cè)薪M真值指派；個(gè)命題變?cè)?3 組真值指派，個(gè)則有個(gè)2n個(gè)真值指派。,60,1.3 命題公式,命題公式的永真式、永假式和可滿足式 定義設(shè)公式中有n個(gè)不同的原子變?cè)?p1,pn,(n為正整數(shù))。該變?cè)M的任意一組確定的值（ u1,un）稱(chēng)為關(guān)于p1,pn的一個(gè)完全指派，其中ui或?yàn)椋驗(yàn)?。如果?duì)于中部分變?cè)x以確定值，其余變?cè)獩](méi)有賦以確定的值，則這樣的一組值稱(chēng)為公式的關(guān)于該變?cè)M的部分指派。 定義使公式取真的指派稱(chēng)為成真指派。,61,1.3 命題公式,定義如果一個(gè)命題公式的所有完全指派均為成真指派，則該公式稱(chēng)為永真式。如果一個(gè)命題公式的所有完全指派均為成假指派

19、，則該公式稱(chēng)為永假式。既不是永真式，又不是永假式，則稱(chēng)此命題公式是可滿足式。 討論： （）永真式的否定為永假式（）；永假式的否定為永真式（）。 （）二個(gè)永真式的析取、合取、蘊(yùn)含、等價(jià) 均為永真式。,62,1.4 等價(jià)式,等價(jià)式 定義如果對(duì)兩個(gè)公式，不論作何種指派，它們真值均相同，則稱(chēng)，是邏輯等價(jià)的，亦說(shuō)（）等價(jià)于（）,并記作：,63,1.4 等價(jià)式,例：,64,1.4 等價(jià)式,例：判斷公式A：(PQ)(PQ)與 B：(PR)(PR)是否等價(jià)。 解：列該公式的真值表：,65,1.4 等價(jià)式,66,1.4 等價(jià)式,定理 命題公式的充要條件是為永真式。 說(shuō)明： “”為等價(jià)關(guān)系符，表示和有等價(jià)關(guān)系。

20、不為命題公式 “”為等價(jià)聯(lián)結(jié)詞（運(yùn)算符），、為命題公式，則（ ）也為一命題公式。,67,1.4 等價(jià)式,證明： （）充分性： 為永真式，即、有相同的真值，所以。 （）必要性：，即、有相同的真值表，所以 為永真式。 例：證明； ,68,1.4 等價(jià)式,由定理可知： 若，則 若，C，則,69,1.4 等價(jià)式,下面列出組等價(jià)公式 （1）雙重否定律 （2）同等律 ； （3）交換律 ； ； （4）結(jié)合律 （）（）； （）（）； （） （）,70,1.4 等價(jià)式,（5）分配律 （）（）（）； （）（）（） （6）摩根律 （）； （） （7）吸收律 （） ； （） ,71,1.4 等價(jià)式,（8）蘊(yùn)含律 （9

21、）等價(jià)律 （）（） （10）零律； （11）同一律； （12）互補(bǔ)律； （13）輸出律 （）,72,1.4 等價(jià)式,（14）歸繆律 （）（） （15）逆反律 說(shuō)明： （）證明上述組等價(jià)公式的方法可用真值表法，把改為所得的命題公式為永真式，則成立。,73,1.4 等價(jià)式,（2） 、 均滿足結(jié)合律， 則在單一用、 聯(lián)結(jié)詞組成的命題公式中，括號(hào)可以省去。 （3）每個(gè)等價(jià)模式實(shí)際給出了無(wú)窮多個(gè)同類(lèi)型的具體的命題公式。 例如：(PQ) (P Q)， (PQ) (RS) (P Q) (R S)， (PQ) R) (P Q) R),74,1.4 等價(jià)式,置換規(guī)則 定義給定一命題公式，其中P1、 P2Pn 是

22、中的原子命題變?cè)?若（1）用某些命題公式代換中的一些原子命題變?cè)狿i （2）用命題公式i代換Pi，則必須用i代換中的所有Pi 由此而得到的新的命題公式稱(chēng)為命題公式的代換實(shí)例,75,1.4 等價(jià)式,討論定義： （）用命題公式只能代換原子命題變?cè)?能去代換分子命題公式 。 （）要用命題公式同時(shí)代換同一個(gè)原子命題變 元 。 （）永真式的代換實(shí)例仍為永真式；反之代換實(shí) 例為永真式時(shí)，則不能斷定原公式也一定是 永真式。,76,1.4 等價(jià)式,例：為一永真式，若用任何命題公式代換，則仍為永真式 為一個(gè)可滿足的命題公式，若用代換，則得（）為永真式，但（）并不是永真式。 （）一個(gè)命題公式的代換實(shí)例有許

23、多個(gè)，但不一定都等價(jià)于原來(lái)的命題公式,77,1.4 等價(jià)式,例 設(shè)：（Q）若用（）代換中的， 得：（）（Q（）是的代換實(shí)例， 而：（）（Q）不是B的代換實(shí)例。 例的代換實(shí)例有：（），（），（）等 所以，一個(gè)命題公式的代換實(shí)例有無(wú)限個(gè)。,78,1.4 等價(jià)式,下面討論取代過(guò)程（置換規(guī)則）： 定義給定一命題公式，是的任何部分，若也是一命題公式，則稱(chēng)是的子命題公式。 例：（）（） 的子命題公式有：、（）、 （）、（）、（）（）等。,79,1.4 等價(jià)式,定理給定一命題公式，是的子公式。設(shè)B是一命題公式，若 B，并用B取代中的，從而生成一新的命題公式B，則B。 從定理可見(jiàn)：一個(gè)命題公式A，經(jīng)多次取代，

24、所得到的新公式與原公式等價(jià)。 例：證明：（）（） ,80,1.4 等價(jià)式,（） （） 例：證明： （）（）（）（）為一永真式,81,1.4 等價(jià)式,證明：原式： （）（）（）（） （）（）（）（） （）（）（）（）（） （）（）（）（） 它是（永真式）的代換實(shí)例，永真式的代換實(shí)例仍為永真式！,82,1.4 等價(jià)式,對(duì)偶原理（對(duì)偶定律） 定義給定二個(gè)命題公式和A* ，若用代換，用代換，用代換，用代換，其中一個(gè)命題公式由另一個(gè)命題公式得來(lái)，則稱(chēng)和A*是互為對(duì)偶的，而聯(lián)結(jié)詞和也是互為對(duì)偶的 例：寫(xiě)出下列命題公式的對(duì)偶式： （） （） 對(duì)偶式 A* ,83,1.4 等價(jià)式,討論定義： （）若命題公式中

25、有聯(lián)結(jié)詞，則必須把化成由聯(lián)結(jié)詞， ，組成的等價(jià)的命題公式，然后求它的對(duì)偶式； 例：求(PQ)(PR)的對(duì)偶式,84,1.4 等價(jià)式,（）在寫(xiě)對(duì)偶式時(shí)，原命題公式中括號(hào)不能省去，必須按優(yōu)先級(jí)的次序畫(huà)上括號(hào)，并在求其對(duì)偶式時(shí)仍將保留括號(hào)。 例：（）對(duì)偶式寫(xiě)成 （），而不能寫(xiě)成,85,1.4 等價(jià)式,定理（摩根推廣定理） 設(shè)和A*為對(duì)偶式P1,P2Pn 是出現(xiàn)在和A*中的所有原子命題變?cè)?，于是有?（P1，P2Pn） A* （P1，P2Pn）（1） （P1，P2Pn） A*（P1，P2Pn）（）,86,1.4 等價(jià)式,證明：由摩根定理 （）（） （）（） 不難看出：一個(gè)命題公式的否定等價(jià)于它的對(duì)偶式

26、，且把變?cè)姆穸ù婷恳粋€(gè)變?cè)?例：設(shè)（，） （），驗(yàn)證上述定理：,87,1.4 等價(jià)式,證明： ()（，） （，） A*（，） A*（，） （）（ ，） A*（，）（ ） 有（ ， ， ） A*（，）,88,1.4 等價(jià)式,定理若二個(gè)命題公式互為等價(jià)，則它們的對(duì)偶式也互為等價(jià)，亦即若，則A*B*成立。 證明：已知：、為任一命題公式，且，要證明A*B* 設(shè)：P1、P2Pn 是出現(xiàn)在和中的原子命題變?cè)?89,1.4 等價(jià)式,由， 即（P1，P2Pn） （P1，P2Pn） （P1，P2Pn） （P1，P2Pn） 由摩根推廣定理 *（P1，P2Pn） *（P1，P2Pn）,90,1.4 等價(jià)式,

27、*（P1，P2Pn） *（P1，P2Pn）為永真式 前面講過(guò)永真式的代換實(shí)例仍為永真式，所以用 Pi代換A*和B*中的Pi （1in) 則得： *（ P1， P2 Pn） *（ P1， P2 Pn） 即為：*（P1，P2Pn） *（P1，P2Pn）,91,1.4 等價(jià)式,例：證明： （）（）（ ） （） （）（） （） （） 證明： （）左邊(）（ ） （） （ ） （）（ ） （ ）,92,1.4 等價(jià)式,（）左邊 （） （） （） （） （） 結(jié)論：（）和（）是互為對(duì)偶的。,93,1.5 永真蘊(yùn)含式,定義命題公式稱(chēng)為永真蘊(yùn)含命題公式，當(dāng)且僅當(dāng) 是一個(gè)永真式，記作： 說(shuō)明：“ ”讀作“永真蘊(yùn)

28、含”，“蘊(yùn)含”，“能推得” “ ”是關(guān)系符， 不為命題公式。 例：證明： ； P （）列出真值表 證明：（）和（）為永真式,94,1.5 永真蘊(yùn)含式,（）可用等價(jià)公式證： （） （） T （） （） T,95,1.5 永真蘊(yùn)含式,定理設(shè)、是二個(gè)命題公式 的充分必要條件是 且 。 證明：若，則為一永真式 由定律：（）（）（） （）且（）也為一永真式 即： 且成立 反之 且 則也成立 此定理把“”和“ ”之間建立了相應(yīng)的關(guān)系。,96,1.5 永真蘊(yùn)含式,下面給出常用的永真蘊(yùn)含式 I1 （） I2 （ ） I3（） I4 （） I5 （） I6 （）（） （） I7 （）（） （） I8 （）（）

29、（） I9 P ,97,1.5 永真蘊(yùn)含式,I10 I11 （） I12 （） I13 （）（）（） 證明上述永真蘊(yùn)含式的方法有三種： （）把“ ”關(guān)系符改為“”聯(lián)結(jié)詞，證明它為永真式。 (a)真值表法 (b)命題演算法,98,1.5 永真蘊(yùn)含式,（）找出使單條件命題前件為“”的所有真值指派，試看能否導(dǎo)致后件均為“”，若為“”，則永真蘊(yùn)含關(guān)系成立。,99,1.5 永真蘊(yùn)含式,例：（） 前件為“”的所有指派為、（）均為“”， 為“”，為“”，也應(yīng)為“”， （） 成立 （）找出使單條件命題的后件均為“”的所有真值指派，試看前件的所有真值是否為“”，若是，則蘊(yùn)含成立。,100,1.5 永真蘊(yùn)含式,例

30、：（） 后件為“”的所有條件是：為“”， 代入前件得 （）若為，則（）為“”； （）若為，則（）為“”； （） 成立 若后件簡(jiǎn)單則可選用(3)；若前件簡(jiǎn)單則可選用(2)。 二種方法是互為獨(dú)立的，只需使用一種證明就行。,101,1.5 永真蘊(yùn)含式,討論一下永真式 可得出三個(gè)結(jié)論： （）若一個(gè)命題公式等價(jià)于一個(gè)永真式，則該公式一定為永真式。 （）若一個(gè)永真的命題公式永真蘊(yùn)含一個(gè)命題公式，則此命題公式一定也為永真式。 （）若一個(gè)永假的命題公式永真蘊(yùn)含一個(gè)命題公式，則該公式可能是永真式、永假式或可滿足的。,102,1.5 永真蘊(yùn)含式,定理給定命題公式、， 若，且，則。 證明：，且， （）（）為永真式，

31、 由I6：（）（） （）， （）也為永真式；即，成立,103,1.5 永真蘊(yùn)含式,推論若B1、B1 B2Bm ，則。 定理給定一個(gè)命題公式、，若,，則（） 證明：， （）（）為永真式， 由條件，若一定為“”，則、均為“”， （）也為“”，結(jié)論：（）為“”。,104,1.5 永真蘊(yùn)含式,上述也可用等價(jià)公式證明它： （）（） （）（ ） （） （）也為永真式 （）成立 定義設(shè)H1,H2.Hm,均為命題公式，若（H1H2 Hm ） ，則稱(chēng) H1,H2.Hm,共同蘊(yùn)含，并記作： H1,H2.Hm 。,105,1.5 永真蘊(yùn)含式,定理若 （H1 H2Hm ）,P ， 則（H1 H2Hm ） （）。 證明

32、：（H1 H2Hm P） （H1 H2Hm P）Q （ H1 H2 Hm ） （ P Q ） （H1 H2Hm ） （ P Q ） H1 H2 . Hm（）也為永真式 （ H1 ,H2 . Hm ）（）成立,106,1.6 其他聯(lián)結(jié)詞,其他命題聯(lián)結(jié)詞： (1)不可兼或（異或，異） (a)符號(hào):(),讀作“異或” (b)定義:（由真值表） (c)異或的性質(zhì)： （）（ ） （）（ ） （） ()(),107,1.6 其他聯(lián)結(jié)詞,（）（） （） （對(duì) 可分配的） 若 ，則有： ， ,108,1.6 其他聯(lián)結(jié)詞,()“與非”聯(lián)結(jié)詞： (a)符號(hào),讀作“與的否定”或“與非” (b)定義：（由真值表） （

33、）（）,109,1.6 其他聯(lián)結(jié)詞,(c)性質(zhì)： （）（） （） （）（）（） （）（）（） （）（） 不可結(jié)合 （）（） 不可結(jié)合 ，,110,1.6 其他聯(lián)結(jié)詞,()“或非”聯(lián)結(jié)詞： (a)符號(hào)：“” （）讀作：“或的否定”或 “或非” (b)定義（由真值表給出）： （） （）,111,1.6 其他聯(lián)結(jié)詞,(c)性質(zhì)： （可交換的） （）（） （）（） （）（） 不可結(jié)合 （）（） 不可結(jié)合 ； (d)由（）和（）中的性質(zhì)可見(jiàn)，和是互為對(duì)偶的。,112,1.6 其他聯(lián)結(jié)詞,(4)“ 蘊(yùn)含否定”聯(lián)結(jié)詞： (a)符號(hào)： (b)定義(由真值表給出）： P Q (PQ),“”,c,c,c,113,

34、1.6 其他聯(lián)結(jié)詞,()不同真值表的命題公式： 按命題公式的生成規(guī)則，用聯(lián)結(jié)詞可組成無(wú)限個(gè)命題公式。下面討論這些命題公式有多少種不同的真值表： (a)若命題變?cè)挥幸粋€(gè)，則用聯(lián)結(jié)詞組成的命題公式由四種不同的真值表，即為：,114,1.6 其他聯(lián)結(jié)詞,所有依賴(lài)于的命題公式均等價(jià)于這四個(gè)中的一個(gè) (b)若有二個(gè)命題變?cè)?，則命題公式的不同真值表有：222=24=16種。 推廣到一般：若有個(gè)變?cè)拿}公式，則可構(gòu)成不同的真值表為22n（個(gè)）。,115,1.6 其他聯(lián)結(jié)詞,（）二元運(yùn)算中的全部聯(lián)結(jié)詞總結(jié)： 、 是五個(gè)基本聯(lián)結(jié)詞。 到此為止，一個(gè)符號(hào)系統(tǒng)已定義完畢，它們是： 命題變?cè)?:、 值 :、 運(yùn)

35、算符 :、 、 括號(hào) :（） 關(guān)系符 : 、,。,C,116,1.6 其他聯(lián)結(jié)詞,全功能聯(lián)結(jié)詞集合： 定義一個(gè)聯(lián)結(jié)詞集合，用其中聯(lián)結(jié)詞構(gòu)成的式子足以把一切命題公式等價(jià)的表達(dá)出來(lái)，則稱(chēng)此聯(lián)結(jié)詞集合為全功能聯(lián)結(jié)詞集合。 定義設(shè)有一聯(lián)結(jié)詞集合，若 （）用中的聯(lián)結(jié)詞的等價(jià)式能表達(dá)任何的一個(gè)命題公式； （）刪除中的任一聯(lián)結(jié)詞，從而形成一個(gè)新的聯(lián)結(jié)詞集合，至少有一個(gè)命題公式不能用中的聯(lián)結(jié)詞的等價(jià)式來(lái)表示，則稱(chēng)A為最小的全功能聯(lián)結(jié)詞集合。,117,1.6 其他聯(lián)結(jié)詞,我們可以證明：，；，；，；均為全功能聯(lián)結(jié)詞集合，且均是最小的全功能聯(lián)結(jié)詞集合。 例：用上述最小全功能聯(lián)結(jié)詞集合中的聯(lián)結(jié)詞單一表達(dá)下述命題公式：

36、,118,1.6 其他聯(lián)結(jié)詞,（） ， （） （ ） ， （） ， () ， （ ） （）（） （ ） （ ） （） ,c,c,119,1.7 范式,如何判定命題公式為永真式、永假式和可滿足式或二個(gè)命題公式等價(jià)，歸納有三種方法： （1）真值表法：對(duì)于變?cè)乃姓嬷抵?派，看對(duì)應(yīng)命題公式的真值。 （2）命題演算方法：化簡(jiǎn)命題公式至最簡(jiǎn)式，看是否存在和 （）、（）等價(jià)，若不則為可滿足的。 （3）范式方法：本節(jié)就介紹此法。,120,1.7 范式,什么叫范式 把命題公式化歸為一種標(biāo)準(zhǔn)的形式，稱(chēng)此標(biāo)準(zhǔn)形式為范式。 什么叫判定 以有限次步驟來(lái)決定命題公式是否為永真式、永假式，還是可滿足的，或者判定二個(gè)命題

37、公式是否等價(jià)等這一類(lèi)的問(wèn)題，統(tǒng)稱(chēng)為判定問(wèn)題。 討論范式和主范式的目的就是為了進(jìn)行判定。,121,1.7 范式,析取范式和合取范式： 設(shè)命題變?cè)獮椋?、，則：（）的析取式稱(chēng)為“和”；（）的合取式稱(chēng)為“積”。 定義命題公式的變?cè)妥冊(cè)姆穸ㄖe稱(chēng)為基本積，而變?cè)妥冊(cè)姆穸ㄖ头Q(chēng)為基本和。,122,1.7 范式,例：設(shè)、為二個(gè)命題變?cè)瑒t：， ， 稱(chēng)為基本和；， ， ， 稱(chēng)為基本積。 若“基本和”或“基本積”中的子公式”，稱(chēng)為此基本積 （和）的因子。 例： 的因子有： 、 、 ,123,1.7 范式,定理一個(gè)基本積必定是永假式，它的充分必要條件是，它至少包含一對(duì)因子,其中一個(gè)是另一個(gè)的否定。 證明：

38、 （）充分條件：、為基本積中一對(duì)因子該 基本積一定為永假式。 （）（）（） （）必要條件：基本積為永假式基本積中包含、這對(duì)因子。,124,1.7 范式,反證法：假設(shè)基本積中不包含、這樣的因子，且為永假式。若給基本積中的命題變?cè)概伞啊?，而命題變?cè)姆穸ㄖ概蔀椤啊保?在基本積中不包含、這對(duì)因子， 基本積得到的真值為“”，這和假設(shè)相矛盾； 基本積中必然包含、這對(duì)因子才能使基本積為“”。,125,1.7 范式,定理一個(gè)“基本和”必定為永真式，其充要條件（當(dāng)且僅當(dāng)）是，它至少包含一對(duì)因子，其中一個(gè)是另一個(gè)的否定。 定義與給定命題公式等價(jià)的一個(gè)公式，如果是由基本積之和組成，則稱(chēng)它為命題公式的析取范式。并

39、記為：PP1 P2 Pn（nI+）。其中P1，P2Pn均為基本積。 方法可按下列三步（或四步）進(jìn)行：,126,1.7 范式,（）利用等價(jià)公式：化去“”、“”聯(lián)結(jié)詞，把命題公式變?yōu)榕c其等價(jià)的用，表達(dá)的公式。 例: ， （）（） （）（） （）將“”深入到原子命題變?cè)?，并使變?cè)白疃嘀挥幸粋€(gè)“”詞。 例：（） ,127,1.7 范式,（）利用“”對(duì)“”的分配，將公式化為析取范式。 （）除去永假項(xiàng)得最簡(jiǎn)析取范式。 例：求（）（）的析取范式： 解：原式 (（） （）) (（） （）),128,1.7 范式,( （） （）) ( （） （）) -（1）化去詞 （ ）（）（ ） -（2）將“”深入到

40、變?cè)懊?，并最多保留一個(gè) （ ）（ ）（ ）（ ）（ ） -（3）“”對(duì)或“”的分配，化成為析取范式 （）（） -（4）最簡(jiǎn)析取范式,129,1.7 范式,討論定義： （）從上例看出，一個(gè)命題公式的析取范式不是唯一的，但同一命題公式的析取范式一定是等價(jià)的。 （）若一個(gè)命題公式的析取范式中每一個(gè)基本積均為永假式，則該公式也一定為永假式。 即PP1P2Pn（P1，P2Pn均為基本積） 則當(dāng)P1P2 Pn F時(shí)，一定為永假式。 (可用來(lái)判定是否為永假式),130,1.7 范式,例：（析取范式） （ ）（ ） 永假式 定義與給定命題公式等價(jià)的一個(gè)公式，如果它是由基本和之積所組成，則稱(chēng)它是給定命題公式的

41、合取范式。 并表示成： Q Q1 Q2 Qn，(nI+),其中Q!,Q2,Qn均為基本和。,131,1.7 范式,求一個(gè)命題公式的合取范式的方法和求析取范式的方法類(lèi)同： 第（）、（）步相同； 第（）利用“”對(duì)“”的分配就行； 第（）去掉永真的析取項(xiàng)。,132,1.7 范式,例：求（）（）的合取范式 原式 （）（） 化去“”詞 （ ）（ ） “”深入到變?cè)埃⒆疃啾Ａ粢粋€(gè) （）（ ）（ ） “”對(duì)“”的分配 （ ）（ ）（ ）（ ） （最簡(jiǎn)合取范式）,133,1.7 范式,討論定義： （）給定一命題公式的合取范式不是唯一的，但同一命題公式的合取范式一定是等價(jià)的。 （）若一個(gè)命題公式的合取范式中

42、的各基本和的真值為“”，則該命題公式一定是永真式。 (可用來(lái)判定是否為永真式) 例: ）（）（）,134,1.7 范式,主析取范式。 定義在個(gè)變?cè)幕痉e中，若每個(gè)變?cè)捌浞穸ú⒉煌瑫r(shí)存在，且二者之一出現(xiàn)一次且僅出現(xiàn)一次，則稱(chēng)此基本積為極小項(xiàng)。 例:對(duì)二個(gè)命題變?cè)v,極小項(xiàng)有22=4個(gè),即、 、 對(duì)一個(gè)命題變?cè)v,極小項(xiàng)有21=2個(gè),即:、,135,1.7 范式,對(duì)三個(gè)命題變?cè)v，極小項(xiàng)有23=8個(gè)， 即：、 、 、 推廣到一般：個(gè)命題變?cè)獦?gòu)成的不同極小項(xiàng)有2n個(gè)（nI+）。使得每個(gè)極小項(xiàng)為真的賦值僅有一個(gè)。,136,1.7 范式,定義對(duì)給定的命題公式來(lái)講，僅含有極小項(xiàng)的析取的等價(jià)式稱(chēng)為給定命

43、題公式的主析取范式。 定理在真值表中，一個(gè)公式的真值為的指派所對(duì)應(yīng)的極小項(xiàng)的析取，即為此公式的主析取范式。,137,1.7 范式,例：求出、 （）、的主析取范式,138,1.7 范式,則可直接寫(xiě)出各命題公式的主析取范式： （ ）（ ）（） （）（）（） （）（）（）（） （） 討論此定理：,139,1.7 范式,（1）只要命題公式不是永假式，則一定可以根據(jù)該命題公式的真值表直接寫(xiě)出其主析取范式，其方法是找出該公式為“”的行，對(duì)應(yīng)寫(xiě)出極小項(xiàng)的析取式，且一定是唯一的。 （2）若命題公式是含有n個(gè)變?cè)挠勒媸?，則它的主析取范式一定含有2n個(gè)極小項(xiàng)。 （3）若二個(gè)命題公式對(duì)應(yīng)的主析取范式相同，則此二個(gè)

44、命題公式一定是等價(jià)的。 （4）命題公式的主析取范式中極小項(xiàng)的個(gè)數(shù)一定等于對(duì)應(yīng)真值表中真值為“”的個(gè)數(shù)。,140,1.7 范式,下面介紹不用真值表，直接求命題公式主析取范式的方法，分四步： （）將命題公式化歸為與其等價(jià)的析取范式； （）除去永假項(xiàng)，合并基本積中相同項(xiàng)（例：），變?yōu)樽詈?jiǎn)析取范式。 （）利用添變?cè)姆椒?，將所有基本積變?yōu)闃O小項(xiàng)。,141,1.7 范式,例：二個(gè)變?cè)?，利用“”?duì)或“”的分配添項(xiàng) （） （）（） （） （）（） （）合并相同的極小項(xiàng)變?yōu)橐豁?xiàng)。 例：求（）的主析取范式 解：原式（）（） -（1）化為析取范式,142,1.7 范式, （） -（2）消去永假項(xiàng)，變?yōu)樽詈?jiǎn)析取范

45、式 （）（） （）（）（） -（3）添項(xiàng) （）（） -（4）合并相同最小項(xiàng),143,1.7 范式,例：證明（） 證明方法是寫(xiě)出二命題公式的主析范式，看其是否相同： （）（） （）（）（） 而 （）（） （）（）（）（） （）（）（） 主析范式相同，有（） ,144,1.7 范式,主合取范式 定義在個(gè)變?cè)幕竞椭?，若每個(gè)變?cè)c其否定，并不同時(shí)存在，且二者之一出現(xiàn)一次且僅出現(xiàn)一次，則稱(chēng)這種基本和為極大項(xiàng)。 例：有二個(gè)變?cè)?的極大項(xiàng)有22=4個(gè)，（）、（）、（）、（） 有個(gè)變?cè)?，則有2n個(gè)極大項(xiàng) （nI+）。,145,1.7 范式,定理在真值表中，一個(gè)公式的真值為F的指派所對(duì)應(yīng)的極大項(xiàng)的合取，即為

46、此公式的主合取范式。 在真值表中真值為“”的個(gè)數(shù)等于主合取范式中極大項(xiàng)的個(gè)數(shù)。 例：求出（）、（）、（）、（）的主合取范式,146,1.7 范式,直接寫(xiě)出其主合取范式： （） （）（極大項(xiàng)） （ ）（ ）（）,147,1.7 范式,（） （） （ ）（ ）（） （） （ ） （ ）（ ）（ ） （） （）（ ）（ ）,148,1.7 范式,討論 （）與命題公式等價(jià)的主合范式中極大項(xiàng)的個(gè)數(shù)等于其真值表中真值為“”的個(gè)數(shù)。由真值表找極大項(xiàng)的方法為：將表中值為“”的對(duì)應(yīng)真值指派中，把變?cè)獙?xiě)成否定，把變?cè)姆穸▽?xiě)成變?cè)?（）只要命題公式不是永真式，則一定可以寫(xiě)出對(duì)應(yīng)與其等價(jià)的唯一的主合取范式。,14

47、9,1.7 范式,（）若命題公式為含有個(gè)變?cè)挠兰偈?，則主合取范式包含了2n個(gè)極大項(xiàng)的合取式。 （）可用主合取范式判定二個(gè)命題公式是否等價(jià)。 （）已知一個(gè)命題公式的主析取范式，則一定可以直接寫(xiě)出與其等價(jià)的主合取范式來(lái)。反之也行。 例： （ ）（）（） 主析取范式 （ ） 主合取范式,150,1.7 范式,（）對(duì)應(yīng)于有個(gè)變?cè)拿}公式，則一定有： 主析范式極小項(xiàng)數(shù)主合范式極大項(xiàng)數(shù)2n 下面介紹不用真值表求一命題公式主合取范式的方法： （1）化為與命題公式等價(jià)的合取范式； （2）除去真值為“T”的析取項(xiàng)和除去析取項(xiàng)中相同變?cè)抑槐Ａ粢粋€(gè)，變?yōu)樽詈?jiǎn)合取式； （3）添項(xiàng)，使析取項(xiàng)均變?yōu)闃O大項(xiàng)；,151

48、,1.7 范式,例如：、為二個(gè)變?cè)?即：（） （）（ ） （4）合并相同的極大項(xiàng)，保留一項(xiàng)。 例：求（）的主合取范式 解：原式 （） （） （） （）（ ）,152,1.7 范式,主范式序（列）的唯一性 （）極小項(xiàng)極其編碼 為了確保主范式的唯一性，二個(gè)安排： （a）各命題變?cè)奈恢冒才乓还潭ù涡颍?（b）對(duì)極小項(xiàng)、極大項(xiàng)安排一個(gè)次序。 對(duì)于有個(gè)變?cè)拿}公式，則最多可有2n個(gè)極 小項(xiàng)，用m0 m1 m2n-1來(lái)表示。 下面列出三個(gè)變?cè)?、的位置已排定，則,153,1.7 范式,154,1.7 范式,例：設(shè)一命題公式有五個(gè)變?cè)?，P0,P1,P2,P3,P4（次序已定），則必可寫(xiě)出25=32個(gè)

49、極小項(xiàng)， 下列出m(11)十和m(18)十的極小項(xiàng)表示： 即， m(11)十 m(01011)二 （ P0 P1 P2 P3 P4 ） m(18)十 m(10010)二 （ P0 P1 P2 P3 P4 ）,155,1.7 范式,通過(guò)上例歸納出一求極小項(xiàng)m(i)十的方法： (a)把(i)十變換成等價(jià)的(J0,J1Jn-1)二 (b)由二進(jìn)制寫(xiě)出其對(duì)應(yīng)的極小項(xiàng)： 例：求（）（）的編碼表達(dá)式：（設(shè)、次序已定） 解：原式（ ）（ ）（）（ ）,156,1.7 范式, m(001) 二 m(010)二 m(100)二 m(101)二 m(1)十 m(3)十 m(7)十 m(6)十 m1,m3,m7,m

50、61,3,6,7 （）極大項(xiàng)及其編碼 用M0,M1,M2n-1表示個(gè)變?cè)拿}公式的極大項(xiàng)。 求極大項(xiàng)的方法：,157,1.7 范式,(a)把(i)十變換成等價(jià)的(J0,J1Jn-1)二 (b)由二進(jìn)制數(shù)寫(xiě)出其對(duì)應(yīng)的極大項(xiàng)： 例：求（）（）的極大項(xiàng)編碼表示（設(shè)、次序已定）,158,1.7 范式,解：原式 （）（ ） （ ）（ ） M(000) 二 M(010)二 M(100)二 (110)二 M (0)十 M (2)十 M (4)十 M (5)十 M0,M2,M4,M5 0,2,4,5,159,1.7 范式,極大項(xiàng)和極小項(xiàng)編碼約定剛好相反， 從上例中，（）（ ） 1,3,6,7 0,2,4,5

51、 例：寫(xiě)出（ ）的主析和主合編碼表示,160,1.7 范式,P Q1 0,2,3 主析范式為:( ）（ ）（） 主合范式為： P Q 且PQ( ）（ ）（）,161,1.7 范式,主范式的個(gè)數(shù) 在介紹聯(lián)結(jié)詞總結(jié)時(shí)講到： 一個(gè)原子命題變?cè)兴膫€(gè)不同的真值表（221個(gè)）； 二個(gè)原子命題變?cè)?6個(gè)不同的真值表（222個(gè)）； 以此類(lèi)推，若有個(gè)變?cè)拿}公式，則可構(gòu)成 22n個(gè)不同的真值表。 得到結(jié)論： 對(duì)于含有個(gè)變?cè)拿}公式，必定可寫(xiě)出 22n個(gè)主范式，若排除永真式或永假式，則實(shí)際可寫(xiě)出（ 22n ）個(gè)主析（或主合）范式。,162,1.8 推理理論,按公認(rèn)的推論規(guī)則，從前提集合中推導(dǎo)出一個(gè)結(jié)論來(lái)，

52、這樣的推導(dǎo)過(guò)程稱(chēng)為演繹，或者叫形式證明。 在任何論證中，若認(rèn)定前提是真的，且從前提集合推導(dǎo)出結(jié)論的論證是遵守了邏輯規(guī)則的，則我們稱(chēng)此結(jié)論是合法的。 根據(jù)邏輯規(guī)則推導(dǎo)出來(lái)的任何結(jié)論稱(chēng)為有效結(jié)論。 推論規(guī)則就是指確定論證的有效性的判據(jù)，常是用命題形式表示這些規(guī)則，而不涉及實(shí)際命題和它的真值。,163,1.8 推理理論,本節(jié)介紹的證明方法，歸納分成三類(lèi)： （一）真值表技術(shù)； （二）推論規(guī)則； （三）間接證明法。 真值表技術(shù)的主要依據(jù)是“”的真值表定義。 若當(dāng)且僅當(dāng) （）為永真式。,164,1.8 推理理論,真值表技術(shù)： 定義給定二個(gè)命題公式和，當(dāng)且僅當(dāng)是一個(gè)永真式，才可以說(shuō)是從推導(dǎo)出來(lái)的，或稱(chēng)是前提

53、的有效結(jié)論。 定義設(shè)H1，H2,Hm,都是命題公式，當(dāng)且僅當(dāng)H1 H2 Hm ，才可以說(shuō)是前提集合 H1，H2,Hm 的有效結(jié)論。,165,1.8 推理理論,從給定真值表常用的判斷方法有二種： （）檢查真值表中H1，H2,Hm全部為“”的所有行，看結(jié)論是否也均為“”，若均為“”，則結(jié)論有效。否則結(jié)論無(wú)效。 （）看結(jié)論為“”的所有行，檢查每行前提H1，H2,Hm中是否至少有一個(gè)為，若有“”，則結(jié)論有效；若有均為“”的行，則結(jié)論無(wú)效。 例：試證明下列結(jié)論是否有效： 畫(huà)出真值表：,166,1.8 推理理論,由真值表可見(jiàn)： （）， 有效 （），無(wú)效 （）， （） 有效 （） ， （） 有效,167,1

54、.8 推理理論,（）， 無(wú)效 例：H1：如果大連是一個(gè)大城市，則大寨是 一個(gè)鄉(xiāng)村； H2：大寨是一個(gè)鄉(xiāng)村； ：大連是一個(gè)大城市； 則：， 或者稱(chēng)：不能從前提集合中推導(dǎo)出來(lái)。,168,1.8 推理理論,推理（論）規(guī)則： 從這節(jié)開(kāi)始，我們只討論命題論證的有效性，而不去討論命題的真假值； 在推論規(guī)則中不需要有真值表，也不需要對(duì)命題進(jìn)行真值指派。 推理規(guī)則的依據(jù)是常用的永真蘊(yùn)含式和等價(jià)公式。 I1； I2； I3，,169,1.8 推理理論,I4 （）， I5 ，（） I6 （），（） （） I7 （） （）（） I8 （），（） （） I9 （），（） （） I10 ,170,1.8 推理理論,下面

55、介紹二個(gè)規(guī)則： P規(guī)則：在推導(dǎo)的任何步驟上都可以引入前提（條件） T規(guī)則：在推導(dǎo)過(guò)程中，如果前面有一個(gè)或多個(gè)公式永真蘊(yùn)含S，則可以把S引入推導(dǎo)過(guò)程之中。 例1：證明：PQ,Q R,PR 推理過(guò)程：,171,1.8 推理理論,步驟 推理過(guò)程 規(guī)則 根據(jù) (1) PQ P (2) P P (3) Q T I(1)(2) (4) Q R P (5) R T I(3)(4) 也可以這樣推理： (1) PQ P (2) Q R P (3) PR T I(1)(2),172,1.8 推理理論,(4) P P (5) R T I(3)(4) 例2 證明： (PQ),(P R),(Q S)SR (1) (PQ

56、) P (2) P Q T(1) E16 (3) Q S P (4) P S T(2)(3) I6 (5) S P T(4) E18,173,1.8 推理理論,(6) P R P (7) S R T(6) I6 (8) SR T(7)E16 下面引進(jìn)條件證明規(guī)則CP：如果能從Q和給定的前提集合P中推導(dǎo)出R來(lái)，則就能從前提集合中推導(dǎo)出（Q R）來(lái)。 即: (PQR)則：P (QR),174,1.8 推理理論,例1： P(Q S), RP,Q RS 證: (1) R 附加前提 (2) RP P (3) RP T(2) E (4) P T(1)(3) I (5) P(Q S) P (6) Q S T(4)(5) I,175,1.8 推理理論,(7) Q P (8) S T(6)(7) I (9) RS CP 例2: PQ P(P Q) (1) P 附加前提 (2) PQ P (3) Q T(1)(2) I (4)