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

1、1,離散數(shù)學(xué) 課程學(xué)時：14 講 授：倪紅,2,課程性質(zhì),離散數(shù)學(xué)（又稱計算機(jī)數(shù)學(xué)）是現(xiàn)代數(shù)學(xué)的重要分支，是計算機(jī)專業(yè)核心基礎(chǔ)課程之一。,3,課程目標(biāo),離散數(shù)學(xué)是以研究離散量的結(jié)構(gòu)和相互之間的關(guān)系為主要目標(biāo)，其研究對象一般為：有限或可數(shù)個元素（例如：自然數(shù)、整數(shù)、真假值、有限個結(jié)點(diǎn)等），而離散性也是計算機(jī)科學(xué)的顯著特點(diǎn)。,4,與其他課程的關(guān)系,離散數(shù)學(xué)與計算機(jī)科學(xué)的其他課程,如：數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、算法分析、邏輯設(shè)計、系統(tǒng)結(jié)構(gòu)、容錯技術(shù)、人工智能等有密切的聯(lián)系。它是這些課程的先導(dǎo)和基礎(chǔ)課程。,5,離散數(shù)學(xué) 高等教育出版社 耿素云、屈婉玲著,教材與參考書,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é)好這門課，要求： （）弄懂定義、定理，弄懂例題，加深對定義、定理的理解； （）在復(fù)習(xí)基礎(chǔ)上，做好課外作業(yè)。同學(xué)之間可以討論，但要弄懂弄通。 （3）做好課堂筆記。,9,第一篇 數(shù)理邏輯,邏輯學(xué):研究思維形式及思維規(guī)律的科學(xué)。 邏輯學(xué)分為二類： 辯證邏輯:是研究事物發(fā)展的客觀規(guī)律。 形式邏輯:對思維的形式結(jié)構(gòu)和規(guī)律進(jìn)行研究。 數(shù)理邏輯：是用數(shù)學(xué)的

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

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

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

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

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

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

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

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

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

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

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

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

15、。 該命題符號化為：PQ （4）首先用字母表示簡單命題。 P：三角形的一個角是直角。 Q：三角形是直角三角形。 該命題符號化為：P Q,50,1.2 命題聯(lián)結(jié)詞,（5）首先用字母表示簡單命題。 P：老王去上海出差。 Q：小李去上海出差。 該命題符號化為：P Q 也可符號化為：（PQ）（PQ）或者 （P Q） （PQ）,51,1.3 命題公式,約定： （）我們只注意命題的真假值，而不再去注意命題的漢語意義。 （）對命題聯(lián)結(jié)詞，我們只注意真值表的定義，而不注意它日常生活中的含義。,52,1.3 命題公式,命題公式 命題常元：表示確定的命題T，F(xiàn)。 命題變元：以真假為其變域之變元，或沒有指定真值的命

16、題。常用大寫英文字母表示。 命題公式：由命題變元、常元、聯(lián)結(jié)詞、括號， 以規(guī)定的格式聯(lián)結(jié)起來的字符串。,53,1.3 命題公式,定義命題公式(wff)可按下述法則來生成： ）單個的命題變元是一個命題公式。 ）若是命題公式，也為命題公式。 ）若、是命題公式，則（）、 （）、（）、（）均為命題公式。 ）當(dāng)且僅當(dāng)有限次使用（）（）（）所得到的包含有命題變元和命題常元，聯(lián)結(jié)詞，括號的符號串才是命題公式。,54,1.3 命題公式,例如：(PQ)，(P(QR)，(PQ)R)，P都是命題公式。而(P)，(P)都不是命題公式 命題公式的真值表 : 命題變元用特定的命題來取代，這一過程稱為對該命題變元進(jìn)行真值指

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

18、 命題公式,由上二例可見，個命題變元有組真值指派；個命題變元有23 組真值指派，個則有個2n個真值指派。,60,1.3 命題公式,命題公式的永真式、永假式和可滿足式 定義設(shè)公式中有n個不同的原子變元 p1,pn,(n為正整數(shù))。該變元組的任意一組確定的值（ u1,un）稱為關(guān)于p1,pn的一個完全指派，其中ui或為，或為。如果對于中部分變元賦以確定值，其余變元沒有賦以確定的值，則這樣的一組值稱為公式的關(guān)于該變元組的部分指派。 定義使公式取真的指派稱為成真指派。,61,1.3 命題公式,定義如果一個命題公式的所有完全指派均為成真指派，則該公式稱為永真式。如果一個命題公式的所有完全指派均為成假指派

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

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

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

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

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

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

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

26、，且把變元的否定代替每一個變元。 例：設(shè)（，） （），驗證上述定理：,87,1.4 等價式,證明： ()（，） （，） A*（，） A*（，） （）（ ，） A*（，）（ ） 有（ ， ， ） A*（，）,88,1.4 等價式,定理若二個命題公式互為等價，則它們的對偶式也互為等價，亦即若，則A*B*成立。 證明：已知：、為任一命題公式，且，要證明A*B* 設(shè)：P1、P2Pn 是出現(xiàn)在和中的原子命題變元，,89,1.4 等價式,由， 即（P1，P2Pn） （P1，P2Pn） （P1，P2Pn） （P1，P2Pn） 由摩根推廣定理 *（P1，P2Pn） *（P1，P2Pn）,90,1.4 等價式,

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

28、含”，“蘊(yùn)含”，“能推得” “ ”是關(guān)系符， 不為命題公式。 例：證明： ； P （）列出真值表 證明：（）和（）為永真式,94,1.5 永真蘊(yùn)含式,（）可用等價公式證： （） （） T （） （） T,95,1.5 永真蘊(yùn)含式,定理設(shè)、是二個命題公式 的充分必要條件是 且 。 證明：若，則為一永真式 由定律：（）（）（） （）且（）也為一永真式 即： 且成立 反之 且 則也成立 此定理把“”和“ ”之間建立了相應(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、：（） 后件為“”的所有條件是：為“”， 代入前件得 （）若為，則（）為“”； （）若為，則（）為“”； （） 成立 若后件簡單則可選用(3)；若前件簡單則可選用(2)。 二種方法是互為獨(dú)立的，只需使用一種證明就行。,101,1.5 永真蘊(yùn)含式,討論一下永真式 可得出三個結(jié)論： （）若一個命題公式等價于一個永真式，則該公式一定為永真式。 （）若一個永真的命題公式永真蘊(yùn)含一個命題公式，則此命題公式一定也為永真式。 （）若一個永假的命題公式永真蘊(yùn)含一個命題公式，則該公式可能是永真式、永假式或可滿足的。,102,1.5 永真蘊(yùn)含式,定理給定命題公式、， 若，且，則。 證明：，且， （）（）為永真式，

31、 由I6：（）（） （）， （）也為永真式；即，成立,103,1.5 永真蘊(yùn)含式,推論若B1、B1 B2Bm ，則。 定理給定一個命題公式、，若,，則（） 證明：， （）（）為永真式， 由條件，若一定為“”，則、均為“”， （）也為“”，結(jié)論：（）為“”。,104,1.5 永真蘊(yùn)含式,上述也可用等價公式證明它： （）（） （）（ ） （） （）也為永真式 （）成立 定義設(shè)H1,H2.Hm,均為命題公式，若（H1H2 Hm ） ，則稱 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)符號:(),讀作“異或” (b)定義:（由真值表） (c)異或的性質(zhì)： （）（ ） （）（ ） （） ()(),107,1.6 其他聯(lián)結(jié)詞,（）（） （） （對 可分配的） 若 ，則有： ， ,108,1.6 其他聯(lián)結(jié)詞,()“與非”聯(lián)結(jié)詞： (a)符號,讀作“與的否定”或“與非” (b)定義：（由真值表） （

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

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

35、算符 :、 、 括號 :（） 關(guān)系符 : 、,。,C,116,1.6 其他聯(lián)結(jié)詞,全功能聯(lián)結(jié)詞集合： 定義一個聯(lián)結(jié)詞集合，用其中聯(lián)結(jié)詞構(gòu)成的式子足以把一切命題公式等價的表達(dá)出來，則稱此聯(lián)結(jié)詞集合為全功能聯(lián)結(jié)詞集合。 定義設(shè)有一聯(lián)結(jié)詞集合，若 （）用中的聯(lián)結(jié)詞的等價式能表達(dá)任何的一個命題公式； （）刪除中的任一聯(lián)結(jié)詞，從而形成一個新的聯(lián)結(jié)詞集合，至少有一個命題公式不能用中的聯(lián)結(jié)詞的等價式來表示，則稱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 范式,如何判定命題公式為永真式、永假式和可滿足式或二個命題公式等價，歸納有三種方法： （1）真值表法：對于變元的所有真值指 派，看對應(yīng)命題公式的真值。 （2）命題演算方法：化簡命題公式至最簡式，看是否存在和 （）、（）等價，若不則為可滿足的。 （3）范式方法：本節(jié)就介紹此法。,120,1.7 范式,什么叫范式 把命題公式化歸為一種標(biāo)準(zhǔn)的形式，稱此標(biāo)準(zhǔn)形式為范式。 什么叫判定 以有限次步驟來決定命題公式是否為永真式、永假式，還是可滿足的，或者判定二個命題

37、公式是否等價等這一類的問題，統(tǒng)稱為判定問題。 討論范式和主范式的目的就是為了進(jìn)行判定。,121,1.7 范式,析取范式和合取范式： 設(shè)命題變元為：、，則：（）的析取式稱為“和”；（）的合取式稱為“積”。 定義命題公式的變元和變元的否定之積稱為基本積，而變元和變元的否定之和稱為基本和。,122,1.7 范式,例：設(shè)、為二個命題變元，則：， ， 稱為基本和；， ， ， 稱為基本積。 若“基本和”或“基本積”中的子公式”，稱為此基本積 （和）的因子。 例： 的因子有： 、 、 ,123,1.7 范式,定理一個基本積必定是永假式，它的充分必要條件是，它至少包含一對因子,其中一個是另一個的否定。 證明：

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

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

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

41、合取范式。 并表示成： Q Q1 Q2 Qn，(nI+),其中Q!,Q2,Qn均為基本和。,131,1.7 范式,求一個命題公式的合取范式的方法和求析取范式的方法類同： 第（）、（）步相同； 第（）利用“”對“”的分配就行； 第（）去掉永真的析取項。,132,1.7 范式,例：求（）（）的合取范式 原式 （）（） 化去“”詞 （ ）（ ） “”深入到變元前，并最多保留一個 （）（ ）（ ） “”對“”的分配 （ ）（ ）（ ）（ ） （最簡合取范式）,133,1.7 范式,討論定義： （）給定一命題公式的合取范式不是唯一的，但同一命題公式的合取范式一定是等價的。 （）若一個命題公式的合取范式中

42、的各基本和的真值為“”，則該命題公式一定是永真式。 (可用來判定是否為永真式) 例: ）（）（）,134,1.7 范式,主析取范式。 定義在個變元的基本積中，若每個變元及其否定并不同時存在，且二者之一出現(xiàn)一次且僅出現(xiàn)一次，則稱此基本積為極小項。 例:對二個命題變元講,極小項有22=4個,即、 、 對一個命題變元講,極小項有21=2個,即:、,135,1.7 范式,對三個命題變元講，極小項有23=8個， 即：、 、 、 推廣到一般：個命題變元構(gòu)成的不同極小項有2n個（nI+）。使得每個極小項為真的賦值僅有一個。,136,1.7 范式,定義對給定的命題公式來講，僅含有極小項的析取的等價式稱為給定命

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

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

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

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

47、9,1.7 范式,（）若命題公式為含有個變元的永假式，則主合取范式包含了2n個極大項的合取式。 （）可用主合取范式判定二個命題公式是否等價。 （）已知一個命題公式的主析取范式，則一定可以直接寫出與其等價的主合取范式來。反之也行。 例： （ ）（）（） 主析取范式 （ ） 主合取范式,150,1.7 范式,（）對應(yīng)于有個變元的命題公式，則一定有： 主析范式極小項數(shù)主合范式極大項數(shù)2n 下面介紹不用真值表求一命題公式主合取范式的方法： （1）化為與命題公式等價的合取范式； （2）除去真值為“T”的析取項和除去析取項中相同變元且只保留一個，變?yōu)樽詈喓先∈剑?（3）添項，使析取項均變?yōu)闃O大項；,151

48、,1.7 范式,例如：、為二個變元， 即：（） （）（ ） （4）合并相同的極大項，保留一項。 例：求（）的主合取范式 解：原式 （） （） （） （）（ ）,152,1.7 范式,主范式序（列）的唯一性 （）極小項極其編碼 為了確保主范式的唯一性，二個安排： （a）各命題變元的位置安排一固定次序； （b）對極小項、極大項安排一個次序。 對于有個變元的命題公式，則最多可有2n個極 小項，用m0 m1 m2n-1來表示。 下面列出三個變元，且、的位置已排定，則,153,1.7 范式,154,1.7 范式,例：設(shè)一命題公式有五個變元，P0,P1,P2,P3,P4（次序已定），則必可寫出25=32個

49、極小項， 下列出m(11)十和m(18)十的極小項表示： 即， m(11)十 m(01011)二 （ P0 P1 P2 P3 P4 ） m(18)十 m(10010)二 （ P0 P1 P2 P3 P4 ）,155,1.7 范式,通過上例歸納出一求極小項m(i)十的方法： (a)把(i)十變換成等價的(J0,J1Jn-1)二 (b)由二進(jìn)制寫出其對應(yī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 （）極大項及其編碼 用M0,M1,M2n-1表示個變元的命題公式的極大項。 求極大項的方法：,157,1.7 范式,(a)把(i)十變換成等價的(J0,J1Jn-1)二 (b)由二進(jìn)制數(shù)寫出其對應(yī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 范式,極大項和極小項編碼約定剛好相反， 從上例中，（）（ ） 1,3,6,7 0,2,4,5

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

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

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

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

55、介紹二個規(guī)則： P規(guī)則：在推導(dǎo)的任何步驟上都可以引入前提（條件） T規(guī)則：在推導(dǎo)過程中，如果前面有一個或多個公式永真蘊(yùn)含S，則可以把S引入推導(dǎo)過程之中。 例1：證明：PQ,Q R,PR 推理過程：,171,1.8 推理理論,步驟 推理過程 規(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來，則就能從前提集合中推導(dǎo)出（Q R）來。 即: (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)