4-邏輯與證明

1、1,數(shù)理邏輯部分,邏輯學(xué)(1ogic)是研究人類推理規(guī)則（過程）的科學(xué)。邏輯學(xué)分為兩大流派：傳統(tǒng)邏輯（亞式邏輯）數(shù)理邏輯（符號邏輯）,2,傳統(tǒng)邏輯由亞里士多德創(chuàng)立（故稱亞式邏輯） ，它是從日常生活的經(jīng)驗出發(fā)，訓(xùn)練我們在生活中如何使用概念，以及如何判斷和推理。其推理的主要規(guī)則是定言三段論。數(shù)理邏輯(mathematical logic)則是近代由歐美人創(chuàng)立的，使用的都是抽象的數(shù)學(xué)符號和數(shù)學(xué)公式，也就是用數(shù)學(xué)的方法來研究邏輯，所以數(shù)

2、理邏輯又叫符號邏輯（symbolic Logic）。,3,邏輯研究的內(nèi)容： ——著重于推理過程是否正確； ——著重于語句之間的關(guān)系，而不是一個具體語句的內(nèi)容。例: 語句1: 所有的數(shù)學(xué)家都穿涼鞋。語句2: 任何一個穿涼鞋的人都是代數(shù)學(xué)家。語句3: 所有數(shù)學(xué)家都是代數(shù)學(xué)家。從技術(shù)上來說， 邏輯并不幫助確定這些語句是否為真; 然而，如果前兩個語句為真， 邏輯可以保證語句3也為真。,4,傳統(tǒng)邏輯適用于日常生活中的推理；數(shù)理邏

3、輯則偏重演算，適用于計算機實現(xiàn)推理。數(shù)理邏輯是計算機軟件理論技術(shù)和硬件邏輯設(shè)計、人工智能等學(xué)科的重要理論基礎(chǔ)。程序＝算法＋數(shù)據(jù)算法＝邏輯＋控制本課程包含了數(shù)理邏輯的兩個基礎(chǔ)演算(命題演算和謂詞演算)，叫作邏輯代數(shù)。,5,第4章 邏輯與證明,6,4.1 命題邏輯,4.1.1命題的定義與運算一、命題的概念 推理的構(gòu)成: 前提(一個或多個判斷句) ? 結(jié)論(一個或多個判斷句) 判斷句----

4、表達判斷的陳述句----是推理的基本單位。 表達判斷----有真假意義, 要么為真, 要么為假, 但不能兼而有之。 【定義】能判斷出真假的陳述句，稱為命題（proposition 或 statement）。,7,命題的真值：作為命題的陳述句所表達的判斷結(jié)果。真值只有兩種取值：真(true)或假(false)。 任何命題的真值都是唯一的。 真命題： 假命題：

5、 判斷給定句子是否為命題，一般分為兩步： 首先判斷它是否為陳述句，然后判斷它是否有唯一真值。,8,【例】 判斷下列句子是不是命題: 4是素數(shù)（質(zhì)數(shù)）。 π是無理數(shù)。 x 大于 y。大于2的偶數(shù)等于兩個素數(shù)之和(歌德巴赫猜想)。 火星上有生物。 你能幫助我嗎？請不要吸煙！ 這朵花真美麗??！ 我正在說假話。,?,?,?,?,?,?,?,?,?,9,解： 6)是疑問句，7)是祈使句，8)

6、是感嘆句，因而這3句都不是命題。 3) 盡管是陳述句，但x,y表示變元，它們不是確定的對象（從而導(dǎo)致真值不惟一），所以不是命題。 9)是一個自相矛盾的病態(tài)語句----稱為悖論，我們不承認此類語句為陳述句，因而9）不是命題。 1)、2)、4)、5)這4句是命題，其中第１)句是假命題；第２)句是真命題； 第4)句和第5)句雖然目前暫時無法判斷其真假, 但它們的真值是客觀存在的，而且是唯一的，將來總會找到它們的真

7、值。,10,二、原子命題和復(fù)合命題 【定義】不能再分解為更簡單句子的命題叫原子命題（簡單命題），否則稱為復(fù)合命題。 例：今天是星期一。 例：今天是星期一并且今天天晴。 原子命題中的“原子”取原子的“不可再分”之意, 它是最基本的命題, 相當(dāng)于自然語言的簡單陳述句。,11,【例】 下面的命題由哪些原子命題組成: 1) 王斌貧窮但快樂。

8、2) 只要明天天氣好, 我就去春游。,12,三、 命題及真值的符號化1、用小寫字母p, q, r, …或加下標(biāo)的小寫字母pi, qi, ri, …表示命題。 【示例】 p: 4是素數(shù)。 （句中的“：”讀作“表示”） q: 1+1=2 r: 火星上有生物。 2、用 T 或1表示真，用 F或0表示假。示例中 p 的真值為0，q 的真值為1，r的真值暫時還不知道。,13,四

9、、邏輯常量與命題變元邏輯常量（命題常元）---- 表示一個確定的、具體的原子命題的標(biāo)識符。邏輯常量有確定的真值, 其真值不是０就是１。,14,深入的討論還需要引進命題變元的概念：命題變元（邏輯變量） ---- 表示任意一個命題的標(biāo)識符，以“T、F”或“1、0”為取值范圍, 仍用小寫字母表示。一個命題變元若被某個確定的命題替代, 就具有確定的真值。（參考：常量與變量）,15,注：1）命題變元不是命題。（參：整型變量不

10、 是整數(shù)。） 2） p表示命題常元還是命題變元可由上、 下文來確定。,16,4.1.2 邏輯聯(lián)結(jié)詞 由簡單命題通過 “非”、“并且”、“或者”、“如果…那么…”等聯(lián)結(jié)詞組合可產(chǎn)生新命題。 但在自然語言中出現(xiàn)的聯(lián)結(jié)詞有時有二義性。因而在數(shù)理邏輯中，必須給出聯(lián)結(jié)詞的嚴格定義，并且將它們形式化。,17,設(shè)p是一個命題, 復(fù)合命題“非p” 稱為p的否定式, 記作┐p。 ┐稱作否定聯(lián)結(jié)詞。,“┐”

11、的讀法：not （英） 非、…的否定（中）,1. 非,18,┐p的真值定義為： ┐p為真 iff p為假。（符號iff表示“當(dāng)且僅當(dāng)”） 命題┐p的取值（和p的關(guān)系）可以用表4.3表示。該 表稱為┐p的真值表。,表4.3 ┐p 的真值表,19,?常見錯誤：命題的表述不符合日常規(guī)范。 例： p：3是偶數(shù)，則┐p表示的命題是什么？ 常見的錯誤答案是：“不是

12、3是偶數(shù)”。 正確的答案是：“3不是偶數(shù)”。,20,?常見錯誤：部分否定與全部否定。 例： p：所有的蘋果都是紅的，則┐p表示的命題是什么？ 常見的錯誤答案是：“所有的蘋果都不是紅的”。 正確的答案是：“并非所有的蘋果都是紅的”。,21,設(shè)p, q是兩個命題, 復(fù)合命題“p并且q”稱為p與q的合取式，記做 p∧q， ∧ 稱為合取聯(lián)結(jié)詞。,“∧”的讀法：and （英）

13、合取、且（中）,2. 與（且）,22,表4.1 p∧q 真值表,p∧q的真值定義為： p∧q為真 iff p, q都為真。 復(fù)合命題p∧q 的取值，即p∧q的真值表如表4.1所示。,23,可以抽象成合取詞∧的自然語言的連接詞有:“并且”“和”“及”“既…又…”“不但…而且…”“雖然…但是…” “一面…一面…”,24,【例】 將下列命題符號化。(1)

14、吳穎不僅用功而且聰明。(2)吳穎雖然聰明但不用功，這不是真的。(3)張輝與王麗都是三好學(xué)生。(4)張輝與王麗是同學(xué)。,解 首先將原子命題符號化： p: 吳穎用功 q:吳穎聰明 r: 張輝是三好學(xué)生 s:王麗是三好學(xué)生 t: 張輝與王麗是同學(xué),25,則符號化的命題如下：(1) p∧q (2) ┐ ( ┐ p∧ q )(3) r∧s(4) t,26,關(guān)于命題

15、符號化需要注意以下兩點： （1）p、q、r等符號用來代表肯定形式的命題，而不是否定形式的命題。如下面的符號化不合適（不是原子命題）: 命題：今天不是星期二并且今天天晴。 設(shè) p：今天不是星期二 q：今天天晴 則命題符號化為：p∧q。 （2）p、q、r等符號不能用來代表復(fù)合命題（上例其實也是這種

16、情況），因為這樣會掩蓋命題的結(jié)構(gòu)，不利于推理。,27,設(shè)p, q是兩個命題, 復(fù)合命題“p或q”稱為p與q的析取式，記做 p∨q， ∨稱為析取聯(lián)結(jié)詞。,“ ∨”的讀法：or （英） 析取、或（中）,3. 或,28,表4.2 p∨q 真值表,p∨q的真值定義為： p∨q為真 iff p, q至少有一個為真 復(fù)合命題p∨q的取值，即p∨q的真值表如表4.2。,29,析取詞∨是自然語言中的連接詞“或者”

17、等的邏輯抽象。但自然語言中的“或者”具有二義性： (1) 相容或(可兼或)：用它聯(lián)結(jié)的命題具有相容性：命題可以同時為真，如：張三會講英語或日語。 (2) 排斥或(不可兼或)：用它聯(lián)結(jié)的命題具有排斥性：命題不能同時為真，如：(1)這張桌子是紅色或藍色。 (2)派小王或小李中的一人去開會?！疟硎鞠嗳莼?。,30,注： 在使用析取聯(lián)結(jié)詞時，首先應(yīng)分析表達的是可兼或還是不可兼或。若是可兼或，以及

18、p, q不能同時為真的不可兼或①，均可直接符號化為p∨q的形式。如果是不可兼或②，并且p與q可同時為真，就應(yīng)符號化為 (p∧┐q)∨(┐p∧q) 的形式。,31,【例】 將下列命題符號化。張三選修了英語課或者微積分課。今晚張三要么只看書要么只聽音樂。a>0或a=0。,32,分析： (1) 是“可兼或”（為什么？），可用析取式表示：p∨q 其中p:張三選修了英語課，

19、q:張三選修了微積分課(2) 是“不可兼或②”： (p∧┐q)∨(┐p∧q) (3) 是“不可兼或①”： p∨q,33,設(shè)p, q是兩個命題, 復(fù)合命題“如果p，則q”稱為p與q的蘊涵式（條件式），記做 p → q， → 稱為蘊涵聯(lián)結(jié)詞， p稱為前件， q稱為后件。,“→ ”的讀法：implies, if…then… （英） 蘊涵、如果…則… （中）,4. 條件,34,表4.4 p→q真值表,p→q的真值定義為：

20、 p→q為假 iff p為真而q為假 復(fù)合命題p→q的取值如表4.4所示。,35,蘊涵詞→是自然語言中的連接詞“如果……, 則……”“只要……, 就……”“因為……, 所以……” “只有……, 才……”“除非……, 否則……”等的邏輯抽象。 p→q表明的邏輯關(guān)系是：p是q的充分條件，q是p的必要條件。,36,日常生活中的“如果p, 則q”是聯(lián)系兩個有邏輯關(guān)系的語句p和q。 而在數(shù)理邏輯

21、中，前件p和后件q可以沒有任何邏輯聯(lián)系，蘊涵式p→q的真值僅由p, q的真值惟一確定。,例：如果1+1=2，那么雪是白的。,37,在數(shù)學(xué)和其他自然科學(xué)中， “如果p, 則q”往往表達前件p為真，后件也為真的推理關(guān)系；而在數(shù)理邏輯中，當(dāng)前件p為假，不管后件是真是假，規(guī)定 p→q都是真 (∵復(fù)合命題p →q應(yīng)有真值)。 例：校長宣布： 如果氣溫超過38℃，則全校停課。,38,?關(guān)于“只有……, 才……”和“除非……, 否

22、則……”的符號化：(1) 只有肚子餓了，我才去麥當(dāng)勞。 其意思相當(dāng)于： 如果我去麥當(dāng)勞，則我肚子餓了。 設(shè) p：我肚子餓了 q：我去麥當(dāng)勞 則原命題可符號化為：q → p 。,39,(2) 除非下雨，否則我就騎自行車上班。 其意思相當(dāng)于： 如果不下雨，我就騎自行車上班。 設(shè) p：天下雨 q：我騎自行車上班 則原

23、命題可符號化為： ┐ p → q 。,40,翻譯時, 為了減少圓括號, 我們對4個命題聯(lián)結(jié)詞的強弱次序規(guī)定為 ┐、 ∧、 ∨、→?聯(lián)結(jié)詞小結(jié)： 聯(lián)結(jié)詞類似于代數(shù)中的＋、－、×、/，只不過＋、－、×、/作用的是數(shù)（實數(shù)，甚至復(fù)數(shù)），而聯(lián)結(jié)詞作用的是命題。也就是說，聯(lián)結(jié)詞提供了命題之間的一種運算。在本質(zhì)上，聯(lián)結(jié)詞用于反映復(fù)合命題的內(nèi)部邏輯結(jié)構(gòu)。,41,【練習(xí)

24、】下列命題是否是含有蘊涵的復(fù)合命題? 若是, 指出其前件和后件。a) 只要你發(fā)給我一個電子郵件，我就會把地址寄給你。b) 暖天持續(xù)一周蘋果樹就開花。c) 活塞隊贏得冠軍就意味著他們打敗了湖人隊。d) 必須走8英里才能到朗斯峰的頂峰。e) 只有你購買的Mp4機不超過90天，你的保修單才有效。f) 如果你駕車超過400英里，就需要買汽油了。,42,g) 你獲得這一職位表明你有最好的信譽。h) 要成為美國公民，只要你生在美國就

25、行了。i) 有風(fēng)暴時沙灘受侵蝕。j) 要在服務(wù)器登錄必須有一個有效的口令。,43,4.1.3 邏輯等價一、命題公式的真值表 1、命題公式的賦值 命題公式的真值情況取決于其所含命題變元的真值。 【定義】 設(shè)p1,p2,…,pn是出現(xiàn)在公式A中的所有命題變元，給p1,p2,…,pn各指定一個真值，稱為對公式A的一個真值指派（也稱解釋）。,44,由定義可知, 具有n個命題變元的公式有2n組不同的真值指派。

26、 在命題公式中，將各分量的所有可能的指派以及由此確定的命題公式的真值匯列成表，稱為命題公式的真值表。,45,p∧q真值表,例：,46,2、真值表的構(gòu)造【示例】 求公式(p∧q)∧┐p的真值表。 解 分以下３步求得: 1) 寫出公式p∧q的真值表; 2) 寫出公式┐p的真值表; 3) 根據(jù)1)和2), 寫出公式(p∧q)∧┐p的真值表。 為清楚起見, 我們將這３步列在一個表內(nèi)

27、, 見下表。,47,(p∧q)∧┐p的真值表,48,構(gòu)造真值表注意事項：命題變元按下標(biāo)進行排列，若無下標(biāo)，則按字典順序進行排列；命題變元的取值按二進制編碼從小到大（或從大到小）排列，這樣容易做到“不重不漏”；根據(jù)經(jīng)驗，最好是逐列求值，而不是逐行求值，這樣不容易出錯；對于一個具體的命題公式，其真值表究竟分成幾列，要根據(jù)自己的熟練程度來定。,49,【示例】 求 (┐ p∧q) → ┐r的真值表。,50,二、邏輯等價的概念,若命題公式

28、A和B在任何真值指派下的真值總是相同的，則稱這兩個命題公式A和B是邏輯等價 (邏輯等值)的，記作A = B 。,51,對兩個含有相同命題變元的公式A和B, 當(dāng)A=B時, 公式A和B的真值表完全相同，即在任何賦值情形下，A和B的真值相同（?稱為邏輯等值）, 而反過來也成立。 注：邏輯等值具有①自反性；②對稱性；③傳遞性。 （?又稱為邏輯等價）,52,我們常常利用真值表來判斷兩個命題公式是否邏輯等價。 【例】證明p→q = ┐p∨q

29、,從真值表可以看出： p→q = ┐p∨q,53,【例4.1.1】證明p→q = ┐q→┐p證明：寫出它們的真值表,從真值表可以看出： p→q = ┐q→┐p,54,【例4.1.2】證明 ┐(p∨q) = ┐p∧┐q證明：寫出它們的真值表,從真值表可以看出： ┐(p∨q) = ┐p∧┐q,55,【例4.1.3】證明 ┐(p∧q) = ┐p∨┐q證明：寫出它們的真值表,從真值表可以看出： ┐(p∧q) = ┐p∨┐q,56,【例】

30、判斷下面兩組公式是否等值： (1) p→ (q→ r) 與 (p∧q) → r (2) ( p→ q)→ r 與 (p∧q) → r 解：,從真值表可以看出： p→ (q→ r) = (p∧q) → r 但：( p→ q)→ r ? (p∧q) → r,57,4.2 謂詞邏輯,前面學(xué)習(xí)的命題邏輯不能描述數(shù)學(xué)和計算機科學(xué)中的多數(shù)命題。例

31、如，考慮句子P：n ? 0常見于數(shù)學(xué)斷言和計算機程序，但句子P不是命題（ n不是確定的對象）。由于數(shù)學(xué)和計算機科學(xué)中的多數(shù)句子使用變元，所以必須擴展邏輯系統(tǒng)，使之包括這樣的句子。,58,為了克服命題邏輯的局限性，弗雷格（Frege）的天才著作《概念演算》，提出了謂詞演算方法。 處理思路：將原子命題進一步分解，分析出個體詞、謂詞、量詞，以期表達命題之間的內(nèi)在聯(lián)系和數(shù)量關(guān)系。,59,一、個體詞與謂詞 在謂

32、詞邏輯中, 我們首先對原子命題加以分解, 引入個體和謂詞的概念。 1、概念　 原子命題的構(gòu)成： 1) 個體(object)－－客體，可以是一個具體的事物，也可以是一個抽象的概念 ，在句中作主語或賓語。 2) 謂詞(predicate)－－謂語部分，用以刻畫客體的性質(zhì)或客體之間的關(guān)系。,60,例如：　　1) 張三是大學(xué)生?！　?) 小李比小王高2cm。 “張三”、“小李”、“小王”是個體

33、詞；　“……是大學(xué)生”、“……比……高2cm”是謂詞。,61,2、個體與謂詞的符號化表示　　1）個體： ①個體常元－－具體或特定的客體的個體詞，常用小寫字母a, b, c,……等表示。　?、趥€體變元－－抽象或泛指的個體詞, 常用小寫字母x, y, z,……等表示。,62,個體變量的取值范圍叫個體域(論域)。個體域可以是有限集, 也可以是無限集。 有一個特殊的個體域，它是由宇宙間一切事物構(gòu)成的，稱為全總

34、個體域。 　　2）謂詞：用小寫字母p, q, r 等表示，如　　p(b)：個體b具有性質(zhì)A ，如“b是整數(shù)”?！　(a,b)：個體a與b具有關(guān)系B ，如“a大于b”。,63,【示例】考慮下面句子，指出其中的個體詞與謂詞： (1) π是無理數(shù)。 (2) 小王與小李同歲。 (3) 南京位于武漢和上海之間。,64,一元謂詞：只與一個個體相聯(lián)系的謂詞, 稱之為一元謂詞，記為p( )或p(x) 。 一元謂詞刻畫了一個個體的性質(zhì)。

35、 二元謂詞：與兩個個體相聯(lián)系的謂詞，稱之為二元謂詞，記為p( , )或p(x,y) 。二元謂詞刻畫了兩個個體的關(guān)系。 ...... n 元謂詞：與n個個體相聯(lián)系的謂詞叫n元謂詞,記為p(x1,x2,…,xn) 。它刻畫了n 個個體間的關(guān)系。,65,注意：在n元謂詞p(x1, x2, …, xn)和n個個體a1, a2, …, an所表示的命題p(a1, a2, …, an)中,

36、要注意n個個體a1, a2, …, an的排列次序, 一般是不能隨意調(diào)換的。,【例】設(shè) r：……是……的算術(shù)平方根, a：５, b：25, 則有 r(a,b)：5是25的算術(shù)平方根。（真命題） r(b,a)：25是5的算術(shù)平方根。 （假命題）,66,3、謂詞填式 【示例】設(shè) p(x)：x是偶數(shù)， a：2, 則： p(a) 表示命題“2是偶數(shù)”。 因為

37、x是個體變元, p(x)不能判斷真假，所以不是命題。 但是一旦x用具體確定的個體, 如2替換后就得到一個命題, 所以我們稱p(a)是謂詞填式，謂詞填式是命題（有真值）。,67,【例】考慮下面的謂詞填式： (1) 令p(x) 表示“x大于3”， p(4) 和p(2) 的值是什么？ (2)令q(x,y) 表示“x=y+3”， q(1,2) 和q(3,0) 的值是什么？ (3)令r(x,y,z) 表示“x+y=z”， r(1

38、,2,3) 和r(0,0,1) 的值是什么？,68,【例】考慮C語句 if x >0 x=x+1; 當(dāng)程序運行到這一條語句時，變量x的值即被代入謂詞p(x): x >0，也就是代入“x>0”。如果對x的這一值p(x)為真，即執(zhí)行賦值語句x=x+1;于是x的值增加1。如果對x的這一值p(x)為假，則不執(zhí)行賦值語句，所以x的值不改變。,69,二

39、、量詞－－表示數(shù)量的詞 有了個體、謂詞、命題函數(shù)的概念以后, 對于有些命題，還是不能正確地符號化。以下面的三段論斷言為例: r: 凡人必死。 s: 蘇格拉底是人。 t: 蘇格拉底必死。,70,令 p(x): x是人。 q(x): x必死。 a: 蘇格拉底。 則s可以表示為

40、命題p(a), t可以表示為命題q(a)。然而, r卻不能表示為p(x)→q(x)。 因為, “凡人要死”是一個真的命題, 而p(x)→q(x)是由謂詞p(x)和q(x)以及命題聯(lián)結(jié)詞“→”構(gòu)成的更復(fù)雜的謂詞, 它不是一個謂詞填式，所以不是命題。 這說明僅用個體和謂詞等概念還不能確切地表示命題 r。,r: 凡人必死。 s: 蘇格拉底是人。 t: 蘇格拉底必死。,71,1. 全稱量詞(universal quantification)

41、 日常生活中常用的“一切”、“凡”、“所有的”、“任意的”、“每一個”等，對應(yīng)數(shù)理邏輯中的全稱量詞? 。?x表示“對個體域中所有的x”、 “對個體域任意一個x”、 “對個體域每一個x”。,72,2. 存在量詞(existential quantification) 日常生活中常用的 “至少有一個”、“存在”、“有一個”、“有的”等，對應(yīng)數(shù)理邏輯中的存在量詞? 。 符號?x表示“對個體域中某一個x”、“

42、個體域中至少存在一個x”、 “個體域中存在某一個x”等。,73,【例 】在不同的個體域限制條件下，將下面命題符號化。凡人都要死。 有的人用左手寫字。其中: (a) 個體域D1為人類集合 (b) 個體域D2為全總個體域,74,解 令 p(x): x是人； q(x): x要死； r(x): x用左手寫字。,(a) 個體域D1為人類集合 ，則 (1) 可以符號

43、化為： x q(x) (2) 可以符合化為: x r(x),(b) 個體域D2為全總個體域 ，則 (1) 可以符號化為： x (p(x)→q(x)) (2) 可以符合化為: x (p(x)∧r(x)),謂詞p(x)描述了個體域中一個特定的個體域，這種謂詞稱為特性謂詞,(1)凡人都要死。 (2)有的人用左手寫字。,75,比較p(x)→q(x)和?x(p(x) → q(x) )可知

44、, 前者僅僅是個謂詞, 其中x是個體變元, 它可以取個體域中的任何個體, 而后者是一個真的命題, 其中的 x 不再起變元的作用, 它被全稱量詞?x限制住了。 該例說明, 對不同的個體域, 同一命題可能有不同形式的謂詞公式, 這對我們討論問題是很不方便的。一般沒有特別說明，論域采用全總個體域。,76,【示例】 把下面命題符號化: 1) 至少有一個人不死。 解 設(shè) p(x): x是人； q(x)

45、: x要死。 則原命題可以表示為?x(p(x)∧┐q(x)) 2) 所有的蘋果都是紅的。 解 設(shè) p(x): x是蘋果。 r(x): x是紅的。 則原命題可以表示為?x(p(x)→r(x)),由前例可看出，特性謂詞與全稱量詞? 結(jié)合使用時，要用→；特性謂詞與存在量詞?結(jié)合使用時，要用∧。,77,【練】 將下列命題符合化，并討論真值。所有人都長著黑頭發(fā)。有的人登上過月球。沒有人登上木星。在美國留學(xué)的學(xué)生未必都是亞洲人

46、。其中: (a) 個體域D1為人類集合 (b) 個體域D2為全總個體域,78,【示例】 將下列謂詞公式譯為自然語句并判斷是不是命題: 1) ?x(p(x)→q(x)) ，其中 p(x): x是人。 q(x): x犯錯誤。 解: 該謂詞公式可以譯為“對于所有的x, 如果x是人, 則x要犯錯誤”，即為命題“人都要

47、犯錯誤”。,79,2) ?x(p(x)∧q(x))，其中 p(x): x是孩子。 q(x): x是天才。 解:該謂詞公式可以譯為“存在一些x, x是孩子且x是天才”，即為命題“有些孩子是神童”。,80,3)?x(p(x)∧q(x))∧┐(?x(p(x)→q(x))) ，其中 p(x)

48、: x是人。 q(x): x聰明。 解：該謂詞公式可以譯為“有些人聰明, 但不是所有的人都聰明?！?81,【例】將下列命題符合化。兔子比烏龜跑得快。有的兔子比所有的烏龜跑得快。并不是所有的兔子都比烏龜跑得快。解: p(x): x是兔子。 q(x): x是烏龜。 r(x,y): x比y跑得快。(1) ?x?y(p(x)?q(y)

49、→r(x,y))(2) ?x(p(x)??y(q(y)→r(x,y))) (3)??x?y(p(x)?q(y)→r(x,y))或?x?y(p(x)?q(y)??r(x,y)),82,【例】 D＝{1，2，3}，p(x)：x是奇數(shù)，則 ?xp(x) = p(1)∧p(2)∧p(3) = 0 ?xp(x) = p(1)∨p(2)∨p(3) = 1,補充：量詞消去等值式： 若個體域D＝｛a1, a

50、2, …, an｝, 則有: ?xp(x) = p(a1)∧p(a2) ∧…∧p(an)  ?xp(x) = p(a1)∨p(a2) ∨…∨p(an),83,【例】 設(shè)個體域Ｄ={-2, 3, 6}，謂詞p(x): x5求下列謂詞公式的真值: 1) ?x (p(x)∧q(x))2) ?x (p(x)∨q(x)),84,解：個體域Ｄ={-2,3,6}，謂詞p(x): x51) ? x(p(x)∧q(x))

51、=(p(-2)∧q(-2)) ∧(p(3)∧q(3)) ∧(p(6)∧q(6))=(1∧0)) ∧(1∧0) ∧(0∧1)=02) ? x(p(x) ∨q(x))=(p(-2) ∨q(-2)) ∨(p(3) ∨q(3)) ∨(p(6) ∨q(6))=(1∨0)) ∨(1∨0) ∨(0∨1)=1,85,【練】 將下列命題符號化: 1) 金子是閃光的, 但閃光的并不一定都是金子。 2) 所有運動員都欽佩某些教練員。3

52、) 有些大學(xué)生不欽佩運動員。,86,4.4 推理與證明,在人類的思維活動中存在大量邏輯推理, 即從一些已知的條件（即前提）推出新的命題（即結(jié)論）。 在這些推理過程中, 只有在假設(shè)前提為真, 而且從前提得出結(jié)論的推理過程又是依據(jù)了某些公認的推理規(guī)則時, 我們才承認這樣得到的結(jié)論是真的、 正確的。,87,4.4.1 等式推理 等式推理是建立在命題邏輯中的一種邏輯推理形式化系統(tǒng)。它由兩部分組成：（1）基本等式－

53、－基本邏輯等價式 （2）推理規(guī)則 推理過程就是應(yīng)用基本等式與推理規(guī)則，對一個命題公式逐步推導(dǎo)，最后得到預(yù)期的新的公式作為結(jié)論。,88,1. 基本邏輯等價式 人們已經(jīng)驗證一組基本而又重要的邏輯等價式，以它們?yōu)榛A(chǔ)可進行公式之間的演算。第1組：結(jié)合律 （1） (p∨q)∨r = p∨(q∨r) （2） (p∧q)∧r = p∧(q∧r)第2組：交換率

54、（3） p∨q = q∨p （4） p∧q = q∧p,89,第3組： 分配律 （5） p∧(q∨r) = (p∧q)∨(p∧r) （6） p∨(q∧r) = (p∨q)∧(p∨r) 第4組：否定深入 （7） ┐ ┐p = p （雙否定律） （8） ┐(p∨q) = ┐p∧┐q （德摩根律）

55、 （9） ┐(p∧q) = ┐p∨┐q （德摩根律）,90,第5組：變元等同 （10） p∨p = p （等冪律） （11） p∧p = p （等冪律） （12） p∧┐p = 0 （矛盾律） （13） p∨┐p = 1 （排中律）第6組：常值與變元的聯(lián)結(jié) （14） 1∧p

56、 = p （同一律） （15） 0∧p = 0 （零律） （16） 1∨p = 1 （零律） （17） 0∨p = p （同一律）,91,第7組： 聯(lián)結(jié)詞化歸 （18） p→q = ┐q → ┐p （逆否等值式 ） （19） p→q = ┐p∨q （蘊涵等值式 ）,9

57、2,說明:1) 在上面的基本等值式中，很多是成對出現(xiàn)的，如果將∧, ∨, ０, １分別換為∨, ∧, １, ０, 就得到另外一個等值式。2) 這些等值式都可用列真值表的方法證明。 3) 由于聯(lián)結(jié)詞∨、 ∧滿足可結(jié)合性， 因此可將(p∨q)∨r和p∨(q∨r)簡記為p∨q∨r； (p∧q)∧r和p∧(q∧r)簡記為p∧q∧r。 4) 性質(zhì)(1)-(17)可對照集合運算的性質(zhì)記憶（P10－P11）。,93,?關(guān)于上述基本等值式應(yīng)

58、注意以下問題：在使用上述基本等值式時，應(yīng)做到能熟練地將左邊替換成右邊，同時能熟練地將右邊替換成左邊。應(yīng)特別重視如下基本等值式：分配律、德摩根律、蘊涵等值式。常見錯誤：┐(p∨q) = ┐p∨┐q ┐(p∨q) = ┐p∧q,94,邏輯等價的應(yīng)用,【例】利用基本的邏輯等價關(guān)系，化簡電路圖,解：上述電路圖可描述為：((p∧q∧r)∨(p∧q∧s))∧((p∧r)∨(p∧s)),95

59、,利用基本邏輯等價式，化簡公式可得： ((p∧q∧r)∨(p∧q∧s))∧((p∧r)∨(p∧s)) = ((p∧q∧(r∨s))∧(p∧(r∨s)) = p∧q∧(r∨s)；,96,【例】將下面程序語言進行化簡。if A then if B then X else Y else if B then X else Y,解：執(zhí)行X的條件為： (Ａ∧Ｂ)∨(?Ａ∧Ｂ),執(zhí)行Y的條件為： (Ａ

60、∧?Ｂ)∨(?Ａ∧?Ｂ),97,執(zhí)行X的條件可化簡為： (Ａ∧Ｂ)∨(?Ａ∧Ｂ)＝ (Ａ∨ ?Ａ) ∧Ｂ＝Ｂ執(zhí)行Y的條件可化簡為： (Ａ∧?Ｂ)∨(?Ａ∧?Ｂ)＝ (Ａ∨?Ａ) ∧ ?Ｂ ＝?Ｂ,程序可簡化為：If B then X else Y,98,2. 推理規(guī)則（1）假言推理 如果： p→q 為真，且 p 為真 則： q 為真（2）三段論推理 如

61、果： p→q 為真，且 q→r 為真 則： p→r 為真（3）拒取推理 如果： p→q 為真，且 ┐q 為真 則： ┐p 為真,99,（4）合取推理如果： p 為真，且 q 為真則： p∧q 為真（5）附加推理如果： p 為真則： p∨q 為真,100,（6）化簡推理 如果：p∧q 為真 則： p 為真（7）析取推理 如果： p∨q

62、 為真， 且 ┐p 為真 則： q 為真,101,在推理過程中還經(jīng)常用到以下推理規(guī)則：,1）前提引入規(guī)則（P規(guī)則）: 在推理過程中,任何地方都可以引用前提。,2）結(jié)論引用規(guī)則（Ｔ規(guī)則）: 在推理過程中得到的中間結(jié)論S可以作為后繼證明的前提引入。,102,3. 命題邏輯的等式推理 命題邏輯的等式推理系統(tǒng):命題邏輯的符號系統(tǒng)+基本等式+推理規(guī)則,（1）推理問題的描述： 前提： P1,

63、 P2, …, Pn 結(jié)論：Q,（2）按照推理規(guī)則逐步由前提推出結(jié)論。,103,【例 】 試證 p→q, q→r, p ? r 　。 前提： p→q （1） q→r （2） p （3） 結(jié)論： r 證明：,（1）（3

64、）? q （4） 假言推理,（2）（4）? r （5） 假言推理,104,例4.4.1：設(shè)如果學(xué)生認真上課就能做好作業(yè)。學(xué)生或者不認真上課或者通過考試。學(xué)生做好作業(yè)且通過考試則綜合成績就合格。證明：如果學(xué)生認真上課，綜合成績就合格。,證明：分別用命題 p、q、r、t 表示： p：學(xué)生認真上課。 q：學(xué)生能做好作業(yè)。 r：學(xué)生能通過考試。 t：學(xué)生綜合成績合格

65、。,105,前提： p→q (1) ┐p∨r (2) (p∧r)→t (3) p (4)結(jié)論： t 證明： (1) (4) => q （5） 假言推理 (2) =>

66、; p→r （6） 基本等式 (6) (4) => r （7） 假言推理 (4) (7) => p∧r （8） 合取推理 (3) (8) => t （9） 假言推理,106,【例】 證明: 如果今天是星期三, 那么我有離散數(shù)學(xué)或數(shù)字邏輯測驗。如果離散數(shù)學(xué)課老師有事, 那么沒有離散數(shù)學(xué)測驗。 今天是星期三且

67、離散數(shù)學(xué)老師有事。所以, 我有數(shù)字邏輯測驗。 證明： 設(shè) p: 今天是星期三。 q: 我有離散數(shù)學(xué)測驗。 r: 我有數(shù)字邏輯測驗。 s: 離散數(shù)學(xué)課老師有事。 前提： p→q∨r （1） s→┐q （2）

68、 p∧s （3） 結(jié)論：r,107,（3）? p （4） 化簡推理,（1）（4）? q∨r （5） 假言推理,（3）? s （6） 化簡推理,（2）（6）? ┐q