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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、命題1、2、3寫(xiě)成： P?Q 命題4、5、6寫(xiě)成： Q?P可見(jiàn)“?”表達(dá)的必須是 前件是后件的充分條件 ；這一點(diǎn)要特別注意!!!它決定了哪個(gè)作為前件，哪個(gè)作為后件。,五.等價(jià)(雙條件）“?”,表示“當(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(mén)，否則為F 。,比較下面二表：,P Q ? ?(P?Q),本節(jié)小結(jié)：,要熟練掌握這五個(gè)聯(lián)結(jié)詞在自然語(yǔ)言中所表示的含義以及它們的真值表的定義。,,,,,特別

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

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

27、與命題變?cè)?常值命題：即是具體的命題，有固定的真值。例如：“3是素?cái)?shù)?！本褪浅Ｖ得}。命題變?cè)喝我幻}用大寫(xiě)的英字母如P、Q 等表示。對(duì)命題變?cè)髦概?給命題變?cè)粋€(gè)解釋)：將一個(gè)常值命題賦予命題變?cè)倪^(guò)程，或者是直接賦給命題變?cè)嬷怠癟”或“F”的過(guò)程。注意：命題變?cè)旧聿皇敲}，只有給它一個(gè)解釋?zhuān)抛兂擅}。,二.合式公式( wff )(well formed formulas),

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

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

30、, P ∧ Q ∨ R,一個(gè)含有命題變?cè)拿}公式不是命題，因它沒(méi)有固定真值，但是給其中的所有命題變?cè)髦概梢院笏陀辛苏嬷?。將所有各種指派情況匯列成表，即為該命題公式的真值表。例如命題 公式 (?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,三.命題公式的真值表,由于對(duì)每個(gè)命題變?cè)伎梢杂袃蓚€(gè)真值(T,F)被指派，所以含有n個(gè)命題變?cè)拿}公式 A(P1,P2,…,Pn) 的真值表有2n行。為了有序地列

32、出公式的真值表，在對(duì)命題變?cè)鲋概蓵r(shí)，可以按照二進(jìn)制數(shù)的次序列表。補(bǔ)充：關(guān)于“二進(jìn)制數(shù)”見(jiàn)下頁(yè)。,關(guān)于二進(jìn)制數(shù)簡(jiǎn)介：,由于計(jì)算機(jī)的硬件是由二個(gè)狀態(tài)的邏輯元件組成的，所以它只處理二進(jìn)制的信息.二進(jìn)制數(shù)：只有兩個(gè)基本符號(hào)0和1，計(jì)算時(shí)，逢二進(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,命題符號(hào)化，就是用命題公式的符號(hào)串來(lái)表示給定的命題。命題符號(hào)化的方法： (1) 首先要明確給定命題的含義。 (2)

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

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

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

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

42、P2,…, Pn 的命題公式，如不論對(duì)P1, P2 , …, Pn作任何真值指派，都使得A和B的真值相同，則稱(chēng)之為A與B等價(jià)，記作A?B。由真值表 P?Q??P∨Q??Q??P3. 重要的等價(jià)公式 ⑴ 對(duì)合律 ??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. 等價(jià)公式的證明方法方法1：列真值表。方法2：用公式的等價(jià)變換.(用置換定

45、律)置換定律:A是一個(gè)命題公式，X是A中的一部分且也是合式公式，如果X?Y，用Y代替A中的X得到公式B，則A?B。應(yīng)用置換定律以及前面列出的等價(jià)公式可以對(duì)給定公式進(jìn)行等價(jià)變換。,例題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) (對(duì)合律) ?P∧(?Q

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

48、合律，冪等律)?(P∧Q)∨(Q∨?P) (交換律)?((P∧Q)∨Q)∨?P (結(jié)合律)?Q∨?P (吸收律)公式 ： P?Q??P∨Q,5. 等價(jià)的性質(zhì) 1) 有自反性：任何命題公式A，有A?A。 2) 有對(duì)稱(chēng)性：若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可見(jiàn)A(?P,?Q)?B(?P, ?Q),6.等價(jià)公式的對(duì)偶性 從前面列出的等價(jià)公式看出，有很多是成對(duì)出現(xiàn)的。 ⑴對(duì)偶式：在一個(gè)只含有聯(lián)結(jié)詞 ?

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

51、對(duì)偶式求公式的否定 定理1-5.1 令A(yù)(P1,P2,…,Pn)是一個(gè)只含有聯(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 可見(jiàn)

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,對(duì)偶原理(定理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頁(yè)：（1）b)c)d) （2）題改為化簡(jiǎn)第18頁(yè)（6）（選做）第19頁(yè) （7）（8）,1-5 重言式與重言蘊(yùn)涵式,1.例子： P ?P∨P ?P∧P F T F

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

56、派，都使得A(P1,P2,…, Pn) 為真(假)，則稱(chēng)之為重言式(矛盾式), 也稱(chēng)之為永真式 (永假式)。即若公式 A ? T，則A為重言式或永真式 若公式 A ? F，則A為矛盾式或永假式3.重言式的證明方法 方法1：列真值表。 方法2：公式的等價(jià)變換，化簡(jiǎn)成“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：等價(jià)公式變換(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) 是含有命題變?cè)?P1,P2,…, Pn的命題公式，如果用合式公式X替換某個(gè)Pi (如果Pi在A(P1,P2,…,Pn) 中多處出現(xiàn)，則各處均用X替換 )，其余變?cè)蛔儯鎿Q后得到新的公式B，則稱(chēng)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也是永真式。如果可以斷定給定公式是某個(gè)永真式的置換例式的話，則這個(gè)公式也是永真式。,定理1 設(shè)A,B為兩個(gè)命題公式，A?B當(dāng)且僅當(dāng) A?B是一個(gè)

61、重言式。證明：,作業(yè),第19頁(yè)（9）第23頁(yè) （1）,1.定義：當(dāng)且僅當(dāng)公式A?B是重言式，則稱(chēng)A重言(永真)蘊(yùn)涵 B ，記作A?B。 即若A?B?T，則A?B。注意符號(hào)“?”不是聯(lián)結(jié)詞，它是表示公 式間的“永真蘊(yùn)涵”關(guān)系，也可以看成是“推導(dǎo)”關(guān)系。即A?B可以理解成由A可推出B，即由A為真，可以推出B也為真。思考：符號(hào) “? ”是不是連接詞？,二.重言(永真)蘊(yùn)涵式,定理2:設(shè)A,B為任意兩個(gè)命題公式, 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為永真式，則真值表中第三行的情況就不會(huì)出現(xiàn)。于是有下面兩種證明方法。,1. 假設(shè)前件A為真，若在此假設(shè)下能推出后件B也為真，則A?B成立。例：求證 P∧(P→Q) ?Q證明：假設(shè) P∧(P→Q)為T(mén)，則P為T(mén) 并且(P→Q)為T(mén)，于是Q為T(mén)，所以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(mén)，則D為F，由 ?C∨D為T(mén)， 于是?C為T(mén)，即C為F， 再由 ((A∧B)?C為T(mén)，則(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(mén)。1.如C為F，則(A∧B)?C為F，所以前件 ((A∧B)?C)∧?D∧(?C∨D) 為F2.如C為T(mén)，則⑴若D為T(mén)，則?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頁(yè)所示) 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、) 有自反性：對(duì)任何命題公式A，有A?A。 2) 有傳遞性：若A?B且B?C，則A?C。 3) 有反對(duì)稱(chēng)性：若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è)的基本蘊(yùn)含公式 。2.

69、第23頁(yè) （2）（4）（6）（7）（8）,1-6.范式,范式就是命題公式形式的規(guī)范形式，分為析取范式與合取范式。一.定義:1.析取范式 公式A如果可等價(jià)地寫(xiě)成如下形式： A1∨A2∨...∨An (n≥1) 其中每個(gè)項(xiàng)Ai (i=1,2..n)都是命題變?cè)蚱浞穸ㄐ问降暮先∈?，稱(chēng)該式為A的析取范式。 2.合取范式 公式A如果可等價(jià)地寫(xiě)成如下形式： A1∧A2∧...∧An (n≥1) 其中每個(gè)項(xiàng)