離散數(shù)學(xué)第1章命題邏輯new

1、離散數(shù)學(xué),東北大學(xué)信息學(xué)院軟件所胡明涵,,,一. 課程的性質(zhì)、內(nèi)容：,數(shù)學(xué)所研究的對象根據(jù)它們的取值分為兩種： 連續(xù)的，如長度、溫度、面積等。 離散的，如商店商品，學(xué)生所學(xué)課程等。離散數(shù)學(xué)是研究離散對象的結(jié)構(gòu)以及它們之間相互關(guān)系的科學(xué)。課程性質(zhì)：是計算機(jī)科學(xué)與技術(shù)專業(yè)的重要的專業(yè)基礎(chǔ)課，也是該專業(yè)的主干課。,,,內(nèi)容：1. 數(shù)理邏輯 2. 集合論 3. 代數(shù)系統(tǒng)

2、 4. 圖論 *5. 組合數(shù)學(xué) *6. 形式語言與自動機(jī) (由于時間的關(guān)系，我們只討論前四部分內(nèi)容。),二.學(xué)習(xí)此課的目的 ：,1.計算機(jī)的誕生與發(fā)展和離散數(shù)學(xué)密切相關(guān) 正如馬克思所說的：“一門科學(xué)，只有當(dāng)它能夠運(yùn)用數(shù)學(xué)時，才算真正發(fā)展了?！庇嬎銠C(jī)正是在離散數(shù)學(xué)中的圖靈機(jī)的理論指導(dǎo)下誕生的(1936提出圖靈機(jī)---1946誕生計算機(jī))。計算機(jī)科學(xué)的發(fā)展十分迅速，計算機(jī)的硬件從第

3、一代起現(xiàn)在發(fā)展到第四代(電子管?晶體管 ?集成電路 ?大規(guī)模集成電路)，第五代即將問世，正在向網(wǎng)絡(luò)化發(fā)展。而且計算機(jī)技術(shù)發(fā)展速度越來越快。,,計算機(jī)科學(xué)的發(fā)展(硬件、軟件的發(fā)展)離不開計算機(jī)的理論 ：例如，程序設(shè)計語言的發(fā)展，從機(jī)器語言?匯編語言?高級面向過程語言?面向?qū)ο笳Z言?智能語言? …，系統(tǒng)軟件的發(fā)展，如操作系統(tǒng)，從單用戶? 多用戶? 網(wǎng)絡(luò)操作系統(tǒng)， …，即如DOS ?Windows ? Windows NT?...; 所有這

4、些發(fā)展都依賴于離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、編譯原理、操作系統(tǒng)、數(shù)據(jù)庫原理、軟件工程、網(wǎng)絡(luò)等理論。其中離散數(shù)學(xué)是基礎(chǔ)，其它的理論中都用到了離散數(shù)學(xué)中的基本概念、基本思想、基本方法。計算機(jī)專業(yè)的學(xué)生學(xué)習(xí)計算機(jī)不同于非計算機(jī)專業(yè)的學(xué)生學(xué)習(xí)計算機(jī)，必須掌握離散數(shù)學(xué)的理論，才能更好地了解和從事計算機(jī)科學(xué)的研究。,2.此課是主干課，也是后繼課的基礎(chǔ)課計算機(jī)專業(yè)的后續(xù)課中都大量地應(yīng)用到離散數(shù)學(xué)中的基本理論，所以要想學(xué)好專業(yè)課，必須先學(xué)好離散數(shù)學(xué)。3.培

5、養(yǎng)學(xué)生抽象的思維和邏輯推理能力和創(chuàng)新能力 在大學(xué)學(xué)習(xí)知識很重要，但是能力的培養(yǎng)更重要。正如著名的物理學(xué)家勞厄所說：“重要的不是獲得知識，而是發(fā)展思維能力。教育無非是一切已學(xué)過的東西都遺忘的時候，所剩下來的東西?！笔Ｏ碌木褪撬季S能力，它可以長期起作用。 “數(shù)學(xué)是學(xué)習(xí)科學(xué)技術(shù)的鑰匙和先決條件?！?數(shù)學(xué)修養(yǎng)包括：理解、抽象、見識、體驗(yàn)。理解能力：邏輯推理能力、不同語言對應(yīng)的轉(zhuǎn)換能力、想象能力等。,抽象能力：敏銳的洞察力，靈

6、活的聯(lián)想類比、舉一反三能力，特別是把實(shí)際問題轉(zhuǎn)化為數(shù)學(xué)問題的能力。 見識：就是讓學(xué)生見識一些重要的數(shù)學(xué)思想、數(shù)學(xué)方法以及用數(shù)學(xué)解決實(shí)際問題的著名事例。有了這樣見識才會思路寬，辦法多，遇到問題會自覺求助于數(shù)學(xué)。 體驗(yàn):數(shù)學(xué)是一種分析問題、解決問題的實(shí)踐活動。與打獵一樣是活本領(lǐng)。像轉(zhuǎn)換觀點(diǎn)、選擇方法、熟悉軟件、檢驗(yàn)結(jié)果、發(fā)現(xiàn)毛病、查找原因多環(huán)節(jié)只有親身經(jīng)歷才能學(xué)到手。 學(xué)到這些活本領(lǐng)，就是一些基本素質(zhì)問題。

7、 離散數(shù)學(xué)可以幫助學(xué)生提高數(shù)學(xué)素質(zhì)。提高創(chuàng)造力。,三. 特點(diǎn)及學(xué)習(xí)方法：,特點(diǎn)：內(nèi)容較雜，概念多，定理多，比較抽象，給學(xué)習(xí)帶來一定難度。學(xué)習(xí)方法： 1.準(zhǔn)確掌握每個概念(包括內(nèi)涵及外延)。 2.要有刻苦鉆研精神,不斷總結(jié)經(jīng)驗(yàn)。 3.在理解內(nèi)容的基礎(chǔ)上，要較多地做些習(xí)題，從而再進(jìn)一步加深理解所學(xué)內(nèi)容。 4.注意培養(yǎng)分析問題和解決問題的能力,,第一篇 數(shù)理邏輯,邏輯--是研究人的思維的科學(xué)。 它

8、包含：1.辯證邏輯：是研究人的思維中的辯證法。例如：用全面的和發(fā)展的觀點(diǎn)觀察事物； 具體問題具體分析； 實(shí)踐是檢查事物正誤的唯一標(biāo)準(zhǔn)；等等。2.形式邏輯：研究人思維的形式結(jié)構(gòu)和一般規(guī)律。 我們只關(guān)心形式邏輯。,,一 形式邏輯,人的思維過程： 概

9、念 ? 判斷 ? 推理 概念和判斷人們通過學(xué)習(xí)(理論學(xué)習(xí)和從實(shí)踐中學(xué)習(xí))來掌握。人的思維形式主要表現(xiàn)為推理，所以形式邏輯主要研究推理。推理： 是由若干個已知的判斷(前提)，推出新的判斷(結(jié)論)的思維過程。,正確的思維,如何能正確的思維？ 概念清楚，判斷正確， 推理合乎邏輯。,二 推理方

10、法,類比推理：由個別事實(shí)推出個別結(jié)論。 如：地球上有空氣、水、 陽光，地球上有生物。火星上有空氣、水、 陽光。 ?火星上有生物。歸納推理：由若干個別事實(shí)推出一般結(jié)論。 如：銅能導(dǎo)電。鐵能導(dǎo)電。錫能導(dǎo)電。鉛能導(dǎo)電?！??一切金屬都導(dǎo)電。演繹推理：由一般規(guī)律推出個別事實(shí)。 形式邏輯主要研究演繹推理。,演繹推理 舉例,如果天下雨，則路上有水。(一般規(guī)律) 今天下雨了。

11、 (個別事實(shí)) 推出結(jié)論：今天路上有水。 (個別結(jié)論)(大前提)：所有金屬都導(dǎo)電。 (一般規(guī)律) (小前提)：銅是金屬。 (個別事實(shí)) 推出結(jié)論：銅能導(dǎo)電。 (個別結(jié)論),三 數(shù)理邏輯,數(shù)理邏輯是用數(shù)學(xué)的方法研究形式邏輯。 “數(shù)學(xué)方法”：建立一套有嚴(yán)格定義的符號，即建立一套形式語言，來研究形式邏輯。 所以數(shù)理邏輯也稱為“符號邏輯”。

12、 這里只討論“命題邏輯”和“謂詞邏輯”。,第一章 命題邏輯命題邏輯以命題為中心,1-1 命題與命題的真值,1. 命題的概念 命題是表達(dá)判斷的陳述句。2. 命題的真值 一個判斷只有兩種可能：是正確的判斷或者是錯誤的判斷, 所以命題的真值只有兩個：“真” 或 “假”真值為真:一個命題所表達(dá)的判斷與客觀情況一致, 記作T (True)。真值為假:一個命題表達(dá)的判斷與客觀情況不一致, 記作F (False

13、)。,判斷一句話是否是命題有兩個關(guān)鍵：（1）是陳述句 （2）有且只有一個真值,例: 判定下面這些句子哪些是命題?,⑴ 2是個素數(shù)。 ⑵ 雪是黑色的。 ⑶ 2020年人類將到達(dá)火星。 ⑷ 如果 a>b且b>c，則a>c。 ⑸ x+y<5 ⑹ 請打開書！ ⑺ 您去嗎？ ⑻ 我正在撒謊。 ⑴⑵⑶⑷是命題,3. 原

14、子命題與復(fù)合命題原子命題 (簡單命題)： 不能再分解成更簡單的陳述句的命題。復(fù)合命題 (分子命題)：由若干個連結(jié)詞，標(biāo)點(diǎn)符號及原子命題復(fù)合構(gòu)成的命題。,4. 命題的表示例 P: 今天下雨。 Q1 : 小王是大學(xué)生。,作業(yè),第8頁: (1)(3)(4)(6),1-2 聯(lián)結(jié)詞,復(fù)合命題是用“聯(lián)結(jié)詞”將原子命題聯(lián)結(jié)起來構(gòu)成的。歸納自然語言中的聯(lián)結(jié)詞，定義了六個邏輯聯(lián)結(jié)詞，分別是： (

15、1) 否定“?” (2) 合取“∧” (3) 析取“∨” (4) 異或“ ” (5) 蘊(yùn)涵“?” (6) 等價“?”,一. 否定“?”,表示：“并非…”，“不…”等。用于對一個命題P的否定，寫成?P，并讀成“非P”。“?”為一元運(yùn)算定義：設(shè)P 為一命題，P 的否定是一個新命題，記作?P。?P的真值與P的真值相反。 例

16、 P：2是素數(shù)。 ?P：2不是素數(shù)。,二. 合取“∧”,表示：“并且”、“不但…而且...”、“既…又 ...”“盡管…還… ”等。例 P：小王能唱歌。 Q：小王能跳舞。 P∧Q：小王能歌善舞。 P∧Q讀成P合取Q。P∧Q為二元運(yùn)算。,定義：兩個命題P和Q的合取是一個復(fù)合命題，記作 P∧Q。當(dāng)且僅當(dāng)P和Q的真值均為T時，P∧Q的真值為T，其他情況下， P∧Q的

17、真值均為F。 可看出真值規(guī)定符合 語言與思維的習(xí)慣。,三. 析取“∨”、異或“ ”,連接詞“或者”有兩種情況：可兼取的或，即兩件事情可以同時發(fā)生。用析取“∨”表達(dá)。不可兼取的或，即兩件事情不能同時發(fā)生。用異或（也稱排斥或） “ ” 表達(dá)。,1. 析取“∨”,例 P：小王能唱歌。 Q：小王能跳舞。 P∨Q：小王能唱歌或者能跳舞。P∨Q，讀成P析取Q 當(dāng)且僅當(dāng)P與Q的真值

18、 均為F時,P∨Q的真值為F, 其他情況均為T。,2. 異或“ ”,例 P：十二次列車早晨8:30 開。 Q：十二次列車早晨9:00開。 十二次列車早晨8:30或者早晨9:00開 表示成P Q， 讀成 P異或Q。當(dāng)且僅當(dāng)P與Q的真值相同時， P Q的真值為F 。,T T F,T F T,F T T,,

19、P Q P Q,F F F,四. 條件 “?”,表示“如果… 那么 …”，“若…則…”等。例 P：土壤缺少水分。 Q：這顆植物會死亡。 P?Q：如果土壤缺少水分，這顆植 物就會死亡。P?Q讀成 “如果P則Q”。稱P是P?Q 的前件，Q是P?Q的后件。還可以說P是Q的充分條件，Q是P的必要條件。,P?Q 的真值表：,P:土壤缺少

20、水分。Q:這顆植物會死亡。 P?Q: 如果土壤缺少水分, 這顆植物就會死亡。 當(dāng)且僅當(dāng)P為T， Q為F時， P?Q的 真值為F，而其它都

21、 為T。 注意“善意規(guī)定”,充分條件：就是只要條件成立，結(jié)論就成立，則該條件就是充分條件。 上例中，“缺少水分”就是“這顆植物會死亡” 的充分條件。在自然語言中表示充分條件的詞有 ： 如果 …則… ，只要… 就…，若…則… 。必要條件：就是如果該條件不成立，那么結(jié)論就不成立, 則該條件就是必要條件。 上例中，“這顆

22、植物死亡”就是“缺少水分”的必要條件(這顆植物未死亡，一定不缺少水分)。 在自然語言中表示必要條件的詞有： 只有 …才… ； 僅當(dāng)…，… ; …, 僅當(dāng)…。,關(guān)于充分條件和必要條件的說明：,舉例：,令：P：天氣好。 Q：我去公園。1.如果天氣好，我就去公園。2.只要天氣好，我就去公園。3.天氣好，我就去公園。4.僅當(dāng)天氣好，我才去公園。5.只有天氣好，我才去公園。6.我去公園，僅當(dāng)天氣好。

23、命題1、2、3寫成： P?Q 命題4、5、6寫成： Q?P可見“?”表達(dá)的必須是 前件是后件的充分條件 ；這一點(diǎn)要特別注意!!!它決定了哪個作為前件，哪個作為后件。,五.等價(雙條件）“?”,表示“當(dāng)且僅當(dāng)”、“充分且必要”例： P：⊿ABC是等邊三角形。 Q：⊿ABC是等角三角形。 P?Q ：⊿ABC是等邊三角形當(dāng)且僅當(dāng) 它是等角三角形。,P Q

24、 P?Q,T T T,T F F,F T F,F F T,P?Q 的真值表：,當(dāng)且僅當(dāng)P與Q的真值相同，P?Q的真值為T，否則為F 。,比較下面二表：,P Q ? ?(P?Q),本節(jié)小結(jié)：,要熟練掌握這五個聯(lián)結(jié)詞在自然語言中所表示的含義以及它們的真值表的定義。,,,,,特別

25、要注意“或者”的二義性，即要區(qū)分給定的“或”是“可兼取的或”還是“不可兼取的或”。特別要注意“?”的用法，要弄清哪個作為前件，哪個作為后件。,練習(xí)：填空已知P∧Q為T，則P為( )，Q為( )。已知P∨Q為F，則P為( )，Q為( )。已知P為F，則P∧Q為( )。已知P為T，則P∨Q為( )。已知P∨Q為T，且P為F ，則Q為( )。已知P?Q為F，則P為( )，Q為( )。已知P為

26、F，則P?Q為( )。已知Q為T，則P?Q為( )。已知 ?P??Q為F，則P為( )， Q為( )。,已知P為T， P?Q為T，則Q為( )。已知?Q為T, P?Q為T，則P為( )。已知P?Q為T，P為T , 則Q為( ).已知P?Q為F，P為T , 則Q為( ).P?P 的真值為( ).P?P 的真值為( )。,1-3 命題公式及命題符號化,一.常值命題

27、與命題變元,常值命題：即是具體的命題，有固定的真值。例如：“3是素數(shù)?！本褪浅Ｖ得}。命題變元：任一命題用大寫的英字母如P、Q 等表示。對命題變元作指派(給命題變元一個解釋)：將一個常值命題賦予命題變元的過程，或者是直接賦給命題變元真值“T”或“F”的過程。注意：命題變元本身不是命題，只有給它一個解釋，才變成命題。,二.合式公式( wff )(well formed formulas),

28、定義： ⑴ 單個命題變元是個合式公式。 ⑵ 若A是合式公式，則?A是合式公式。 ⑶ 若A和B是合式公式，則(A∧B)，(A∨B)，(A?B)和(A?B)都是合式公式。 ⑷ 當(dāng)且僅當(dāng)有限次地應(yīng)用⑴，⑵，⑶所得到的含有命題變元、聯(lián)結(jié)詞和括號的符號串是合式公式。注意這個定義是遞歸的。(1)是遞歸的基礎(chǔ)，由(1)開始，使用(2)(3)規(guī)則進(jìn)行遞歸，可以得到任意的合式公式。,這里所謂的合式公式可以解釋為合法的命題

29、公式之意，也稱之為命題公式，有時也簡稱公式 。下面的式子是合式公式： (P∧Q)，(?P?R)，((P ∧ Q) ∨ R) P∧Q， P??R， P∧Q∨R 上面的式子不是合式公式約定： (1)最外層括號可省， (2)不影響運(yùn)算次序的括號可省運(yùn)算次序由高到低為: ?, ∧, ∨, ?, ? 上面的合式公式可以寫成： P∧Q，?P?R， (P ∧ Q) ∨ R

30、, P ∧ Q ∨ R,一個含有命題變元的命題公式不是命題，因它沒有固定真值，但是給其中的所有命題變元作指派以后它就有了真值。將所有各種指派情況匯列成表，即為該命題公式的真值表。例如命題 公式 (?P?Q)∨Q 的真值表如下所示： P Q ?P ?P?Q (?P?Q)∨Q F F T F F F T

31、 T T T T F F T T T T F T T,三.命題公式的真值表,由于對每個命題變元都可以有兩個真值(T,F)被指派，所以含有n個命題變元的命題公式 A(P1,P2,…,Pn) 的真值表有2n行。為了有序地列

32、出公式的真值表，在對命題變元做指派時，可以按照二進(jìn)制數(shù)的次序列表。補(bǔ)充：關(guān)于“二進(jìn)制數(shù)”見下頁。,關(guān)于二進(jìn)制數(shù)簡介：,由于計算機(jī)的硬件是由二個狀態(tài)的邏輯元件組成的，所以它只處理二進(jìn)制的信息.二進(jìn)制數(shù)：只有兩個基本符號0和1，計算時，逢二進(jìn)一，如 0+1=1，1+1=10，10+1=11，11+1=100 0 1 10 11 +

33、 1 + 1 + 1 + 1 1 10 11 100,為了有序地列出A(P1,P2,…,Pn)的真值表，可以將F看成0，將T看成1，按照二進(jìn)制數(shù)00…0, 00…01, 00…010, …, 11…10, 11…1(即十進(jìn)制的0,1,2,…. ,2n -1)的次序進(jìn)行指派列真值表

34、。如A(P,Q)的真值表可按照如下次序指派：00(F,F)，01(F,T)，10(T,F)，11(T,T)如A(P,Q,R)的真值表可按照如下次序指派：000(F,F,F),001(F,F,T),010(F,T,F),011(F,T,T)100(T,F,F),101(T,F,T),110(T,T,F),111(T,T,T),例如列出P?(Q?R)的真值表,,,,,,,,,,,,,,,,,P Q

35、 R Q?R P?(Q?R),000 F F F T T,001 F F T T T,010 F T F F

36、 T,011 F T T T T,100 T F F T T,101 T F T T

37、 T,110 T T F F F,111 T T T T T,命題符號化，就是用命題公式的符號串來表示給定的命題。命題符號化的方法： (1) 首先要明確給定命題的含義。 (2)

38、將復(fù)合命題分解成各個原子命題。 每個原子命題都必須是一個句子。 (3) 用邏輯聯(lián)結(jié)詞聯(lián)結(jié)原子命題，構(gòu)成給定命題的符號表達(dá)式。,三.命題符號化,例1.如果小張與小王都不去，則小李去。 P：小張去。 Q：小王去。 R：小李去。 該命題可寫成： (?P∧?Q)?R例2.如果小張與小王不都去，則小李去。 該命題可寫成： ?(P∧Q)?R 也可以寫成： (?P∨?Q)?R例3.說離散數(shù)學(xué)無

39、用且枯燥無味是不對的。等價于“離散數(shù)學(xué)有用且也不枯燥無味” P：離散數(shù)學(xué)是有用的。 Q：離散數(shù)學(xué)是枯燥無味的。 該命題可寫成： P∧ ? Q,例4. 僅當(dāng)天不下雨且我有時間，才上街。 P：天下雨。Q：我有時間。R：我上街。 分析：由于“僅當(dāng)”是表示“必要條件”的，既“天不下雨且我有時間”，是“我上街”的必要條件。所以 該命題可寫成： R?(?P∧Q) 例5.人不犯我，我不犯人；

40、人若犯我，我必犯人。 P：人犯我。Q：我犯人。 該命題可寫成：(?P??Q)∧(P?Q) 或?qū)懗桑?P?Q,,,,,P是Q的充分條件,,,,P是Q的充分且必要條件,,例6 .若天不下雨，我就上街；否則在家。 P：天下雨。Q ：我上街。R：我在家。 該命題可寫成： (?P?Q)∧(P? R). 注意：中間的聯(lián)結(jié)詞一定是“∧”，不能是“∨”，也不是“ ”。因?yàn)樵}表示：“天不下雨時我做什么，天下雨

41、我又做什么”的兩種作法，其中有一種作法是假的，則題中的說法就不正確，所以中間的聯(lián)結(jié)詞一定是“∧ ”。,作業(yè),第11頁：（1）第12頁：（5）（6）（7）,1-4 等價公式,等價描述了兩個命題公式之間的關(guān)系1. 例子 看下面三個公式的真值表 從真值表可以看出，不論對P、Q作任何真值指派，P?Q、?P∨Q和?Q??P的真值都相同。 P?Q??P∨Q??Q??P,2. 定義：A、B是含有命題變元P1,

42、P2,…, Pn 的命題公式，如不論對P1, P2 , …, Pn作任何真值指派，都使得A和B的真值相同，則稱之為A與B等價，記作A?B。由真值表 P?Q??P∨Q??Q??P3. 重要的等價公式 ⑴ 對合律 ??P?P ⑵ 冪等律 P∨P?P P∧P?P ⑶ 結(jié)合律 P∨(Q∨R)?(P∨Q)∨R P∧(Q∧R)?(P∧Q)∧R ⑷交換律 P∨

43、Q?Q∨P P∧Q?Q∧P,⑸分配律 P∨(Q∧R)?(P∨Q)∧(P∨R) P∧(Q∨R)?(P∧Q)∨(P∧R)⑹ 吸收律 P∨(P∧Q)?P P∧(P∨Q)?P⑺底-摩根定律 ?(P∨Q)??P∧?Q ?(P∧Q)??P∨?Q⑻ 同一律 P∨F?P

44、 P∧T?P⑼ 零律 P∨T?T P∧F?F⑽ 互補(bǔ)律 P∨?P?T P∧?P?F⑾ P?Q??P∨Q ⑿ P?Q??Q??P⒀ P?Q ?(P?Q)∧(Q?P)⒁ P?Q ?(?P∨Q)∧(P∨?Q) ⒂ P?Q ?(P∧Q)∨(?P∧?Q ),4. 等價公式的證明方法方法1：列真值表。方法2：用公式的等價變換.(用置換定

45、律)置換定律:A是一個命題公式，X是A中的一部分且也是合式公式，如果X?Y，用Y代替A中的X得到公式B，則A?B。應(yīng)用置換定律以及前面列出的等價公式可以對給定公式進(jìn)行等價變換。,例題1. 求證吸收律 P∧(P∨Q)?P證明 P∧(P∨Q) ? (P∨F)∧(P∨Q) (同一律) ?P∨(F∧Q) (分配律) ?P∨F

46、 (零律) ?P (同一律),例題2. 求證 (?P∨Q)→(P∧Q) ?P證明：(?P∨Q)→(P∧Q) ??(?P∨Q)∨(P∧Q) (公式E16) ? (??P∧?Q)∨(P∧Q) (摩根定律) ? (P∧?Q)∨(P∧Q) (對合律) ?P∧(?Q

47、∨Q) (分配律) ?P∧T (互補(bǔ)律) ?P (同一律)公式 ： P?Q??P∨Q,例題3.化簡?(P∧Q)→(?P∨(?P∨Q))解 原公式???(P∧Q)∨((?P∨?P)∨Q) (E16,結(jié)合)?(P∧Q)∨(?P∨Q) (對

48、合律，冪等律)?(P∧Q)∨(Q∨?P) (交換律)?((P∧Q)∨Q)∨?P (結(jié)合律)?Q∨?P (吸收律)公式 ： P?Q??P∨Q,5. 等價的性質(zhì) 1) 有自反性：任何命題公式A，有A?A。 2) 有對稱性：若A?B，則B?A 3) 有傳遞性：若A?B且B?C，則A?C 如果A(P1,P2,…,Pn)?B(P1,P2,…,P

49、n)，則 A(?P1,?P2,…,?Pn)?B(?P1,?P2,…,?Pn) 例 A(P,Q)?P→Q B(P,Q)??P∨Q 有 A(P,Q)?B(P,Q) A(?P,?Q)??P→?Q B(?P, ?Q)?P∨?Q可見A(?P,?Q)?B(?P, ?Q),6.等價公式的對偶性 從前面列出的等價公式看出，有很多是成對出現(xiàn)的。 ⑴對偶式：在一個只含有聯(lián)結(jié)詞 ?

50、 、∨、∧的公式A中，將∨換成∧，∧換成∨，T換成F，F(xiàn)換成T，其余部分不變，得到另一個公式A*，稱A與A*互為對偶式。 例如： A A* P P ?Q∧R ?Q∨R (P∨T)∧?Q (P∧F)∨?Q,⑵用

51、對偶式求公式的否定 定理1-5.1 令A(yù)(P1,P2,…,Pn)是一個只含有聯(lián)結(jié)詞 ? 、∨、∧的命題公式，則 ?A(P1,P2,…,Pn) ? A*(?P1,?P2,…,?Pn) 此定理可以反復(fù)地使用底-摩根定律證明。 下面我們驗(yàn)證一下。 令 A(P,Q)?P∨Q A*(P,Q)?P∧Q ?A(P,Q)??(P∨Q) A*(?P, ?Q)??P∧?Q 可見

52、 ?A(P,Q)?A*(?P,?Q) 推論:?A(P1,P2,…,Pn)? A*(?P1,?P2,…,?Pn),例如，利用上述求公式的否定公式求?(((P∧Q)∨(P∧?Q))∨R) ?((?P∨?Q)∧(?P∨Q))∧?R,對偶原理(定理1-5.2)： 令A(yù)(P1,P2,…,Pn) 、B(P1,P2,…,Pn) 是只含有聯(lián)結(jié)詞?、∨、∧的命題公式， 如果 A(P1,P2,…,Pn) ? B(P1,P2,…,

53、Pn) 則 A*(P1,P2,…,Pn) ? B*(P1,P2,…, Pn) 證明：因?yàn)?A(P1,P2,…,Pn) ? B(P1,P2,…,Pn) 故 A(?P1,?P2,…,?Pn) ? B(?P1,?P2,…,?Pn) 而 A(?P1,?P2,…,?Pn) ? ?A*(P1,P2,…,Pn) B(?P1,?P2,…,?Pn) ? ?B*(P1,P2,…,Pn) 故 ?A*(P1,P2,…,Pn) ?

54、 ?B*(P1,P2,…,Pn)所以 A*(P1,P2,…,Pn) ? B*(P1, P2,…, Pn),作業(yè),第17頁：（1）b)c)d) （2）題改為化簡第18頁（6）（選做）第19頁 （7）（8）,1-5 重言式與重言蘊(yùn)涵式,1.例子： P ?P∨P ?P∧P F T F

55、 T T F 可見不論P(yáng)取什么真值?P∨P 的真值總是為真，?P∧P的真值總是為假。故稱 ?P∨P為重言式(永真式)，稱?P∧P為矛盾式(永假式)。,,,,,,,,一.重言式(永真式)與矛盾式(永假式),2 .重言式(矛盾式)定義 A(P1,P2,…,Pn) 是含有命題變元P1,P2,…, Pn的命題公式，如不論對P1, P2 , …, Pn作任何真值指

56、派，都使得A(P1,P2,…, Pn) 為真(假)，則稱之為重言式(矛盾式), 也稱之為永真式 (永假式)。即若公式 A ? T，則A為重言式或永真式 若公式 A ? F，則A為矛盾式或永假式3.重言式的證明方法 方法1：列真值表。 方法2：公式的等價變換，化簡成“T”。 方法3：用公式A的主析取范式。,例：證明 (P∧(P?Q))?Q 為重言式。方法1. 列真值表 P Q

57、 P?Q P∧(P?Q) (P∧(P?Q))?Q F F T F T F T T F T T F F F T T T T T

58、 T 永真式真值表的最后一列全是“T”。,方法2：等價公式變換(P∧(P?Q))?Q?(P∧(?P∨Q))?Q?((P∧?P)∨(P∧Q))?Q?(F∨(P∧Q))?Q ?(P∧Q)?Q ? ?(P∧Q)∨Q ? (?P∨?Q)∨Q ? ?P∨ (?Q∨Q)? ?P∨ T? T,4. 永真式的性質(zhì) 1) 如果A是永真式，則?A是永假式。 2) 如果A，B是永真式，則(A

59、∧B)、(A∨B)、 (A?B)和(A?B)也都是永真式。 3) 如果A是永真式，則A的置換例式也是永真式。 置換例式：A(P1,P2,…,Pn) 是含有命題變元 P1,P2,…, Pn的命題公式，如果用合式公式X替換某個Pi (如果Pi在A(P1,P2,…,Pn) 中多處出現(xiàn)，則各處均用X替換 )，其余變元不變，替換后得到新的公式B，則稱B是A(P1,P2,…,Pn) 的置換例式。,例如： 公式A：P∨(

60、?P∧((P?Q)?R)) 用(D?E)替換A中P得到A的置換例式 B： (D?E)∨(?(D?E)∧(((D?E)?Q)?R))如果A是永真式，例如A為?P∨P，用 (D?E)替換A中P，得到A的置換例式 B： ? (D?E)∨(D?E) ， 顯然B也是永真式。如果可以斷定給定公式是某個永真式的置換例式的話，則這個公式也是永真式。,定理1 設(shè)A,B為兩個命題公式，A?B當(dāng)且僅當(dāng) A?B是一個

61、重言式。證明：,作業(yè),第19頁（9）第23頁 （1）,1.定義：當(dāng)且僅當(dāng)公式A?B是重言式，則稱A重言(永真)蘊(yùn)涵 B ，記作A?B。 即若A?B?T，則A?B。注意符號“?”不是聯(lián)結(jié)詞，它是表示公 式間的“永真蘊(yùn)涵”關(guān)系，也可以看成是“推導(dǎo)”關(guān)系。即A?B可以理解成由A可推出B，即由A為真，可以推出B也為真。思考：符號 “? ”是不是連接詞？,二.重言(永真)蘊(yùn)涵式,定理2:設(shè)A,B為任意兩個命題公式, A?B

62、的充要條件是 A?B且B?A.證明:若A?B 則 A?B ?T， 而 A?B?(A→B)∧(B→A) 于是A→B ?T 且 B→A ?T， 即A?B且B?A 成立. 若A?B且B?A 則 A→B ?T且B→A ?T，于是(A→B)∧(B→A) ?T。而A?B?(A→B)∧(B→A)，于是 A?B ?T, 即知 A?B 成立.,2.重言(永真)蘊(yùn)涵式證明方法（1）方法1.列真值表。即列A?B的真值表。（2）蘊(yùn)

63、涵式的兩種基本證明方法：,先看一看A?B的真值表，如果A?B為永真式，則真值表中第三行的情況就不會出現(xiàn)。于是有下面兩種證明方法。,1. 假設(shè)前件A為真，若在此假設(shè)下能推出后件B也為真，則A?B成立。例：求證 P∧(P→Q) ?Q證明：假設(shè) P∧(P→Q)為T，則P為T 并且(P→Q)為T，于是Q為T，所以P∧(P→Q) ?Q 成立。,例2：求證： ((A∧B)?C)∧?D∧(?C∨D) ? ?A∨?B證明:設(shè)前件((A∧B)?

64、C)∧?D∧(?C∨D) 為 真。則((A∧B)?C)、?D、(?C∨D)均為真， ?D為T，則D為F，由 ?C∨D為T， 于是?C為T，即C為F， 再由 ((A∧B)?C為T，則(A∧B)為F，即 ?(A∧B)為F，于是 ?A∨?B 為 T所以((A∧B)?C)∧?D∧(?C∨D) ? ?A∨?B,2. 假設(shè)后件B為假，若在此假設(shè)下能推出前件A也為假，則A?B成立。例：求證 P?P∨Q，Q?P∨Q證明：假設(shè)

65、 P∨Q 為 F， 則 P為 F， Q 為 F，所以 P?P∨Q，Q?P∨Q 成立。,例2：求證： ((A∧B)?C)∧?D∧(?C∨D) ? ?A∨?B證明:假設(shè)后件?A∨?B為F，則A與B均為T。1.如C為F，則(A∧B)?C為F，所以前件 ((A∧B)?C)∧?D∧(?C∨D) 為F2.如C為T，則⑴若D為T，則?D為F，所以 前件((A∧B)?C)∧?D∧(?C∨D) 為F。

66、 ⑵若D為F，則?C∨D為F，所以 前件((A∧B)?C)∧?D∧(?C∨D) 為F。所以((A∧B)?C)∧?D∧(?C∨D)? ?A∨?B 成立。,3.重要的重言蘊(yùn)涵式(如教材第43頁所示) I1.P∧Q?P I2. P∧Q?Q I3. P?P∨Q I4. Q?P∨Q I5. ?P?P?Q I6. Q?P?Q I7. ?

67、(P?Q)?P I8. ?(P?Q)??Q I9. P,Q ?P∧Q I10. ?P∧(P∨Q)?Q I11. P∧(P?Q)?Q I12. ?Q∧(P?Q)??P I13. (P?Q)∧(Q?R)?P?R I14. (P∨Q)∧(P?R)∧(Q?R)?R I15. A?B ?(A∨C)?(B∨C) I16. A?B ?(A∧C)?(B∧C),4.蘊(yùn)含的性質(zhì)： 1

68、) 有自反性：對任何命題公式A，有A?A。 2) 有傳遞性：若A?B且B?C，則A?C。 3) 有反對稱性：若A?B且B?A， 則 A?B。 4) 若A?B 且 A?C，則A?B∧C。 5) 若A?B 且 C?B，則A∨C?B。,重點(diǎn)掌握：永真式及永真蘊(yùn)涵式的定義、證明方法、以及常用的公式。,作業(yè),1. 用 證明蘊(yùn)含的基本方法 證明21頁的基本蘊(yùn)含公式 。2.

69、第23頁 （2）（4）（6）（7）（8）,1-6.范式,范式就是命題公式形式的規(guī)范形式，分為析取范式與合取范式。一.定義:1.析取范式 公式A如果可等價地寫成如下形式： A1∨A2∨...∨An (n≥1) 其中每個項(xiàng)Ai (i=1,2..n)都是命題變元或其否定形式的合取式，稱該式為A的析取范式。 2.合取范式 公式A如果可等價地寫成如下形式： A1∧A2∧...∧An (n≥1) 其中每個項(xiàng)