第3章命題邏輯

1、離 散 數(shù) 學(xué),計算機(jī)科學(xué)與工程學(xué)院2011年?秋,第二部分,數(shù)理邏輯,第3章 命題邏輯,第4章 謂詞邏輯,邏輯學(xué)是研究思維形式及思維規(guī)律尤其是推理的學(xué)科, 早在兩千多年前就受到人們的重視。,邏輯學(xué),古希臘（邏輯）,戰(zhàn)國（名學(xué)）,古印度（因明）,德國數(shù)學(xué)家、哲學(xué)家萊布尼茨(1647~1716)首先提出用數(shù)學(xué)方法研究邏輯,就是建立一套表意符號體系,在符號之間進(jìn)行形式推理. 萊布尼茨是數(shù)理邏輯的創(chuàng)始人。也正因為這樣, 數(shù)理邏輯又稱

2、為符號邏輯。,數(shù)理邏輯概述,數(shù)理邏輯是一門新興的邊緣性學(xué)科，分為五個部分：即邏輯演算、證明論、公理集合論、遞歸論和模型論。從創(chuàng)始至今約有300年的歷史。特別是近百年來,它取得了長足的發(fā)展,在現(xiàn)代的數(shù)學(xué)、計算機(jī)科學(xué)以及自然科學(xué)和社會科學(xué)中都有廣泛的應(yīng)用。,數(shù)理邏輯概述,數(shù)理邏輯是用數(shù)學(xué)的方法來研究人類思維活動的一門數(shù)學(xué)學(xué)科，其顯著特征是： 符號化、形式化即把邏輯所涉及的“概念、判斷、推理”用符號來表示，用公

3、理體系來刻劃, 并基于符號串形式的演算來描述推理過程的一般規(guī)律。,數(shù)理邏輯概述,回顧計算機(jī)科學(xué)的發(fā)展，我們可以清晰地發(fā)現(xiàn)數(shù)理邏輯一直是計算機(jī)科學(xué)的理論基礎(chǔ)和發(fā)展動力。,數(shù)理邏輯的起源與計算機(jī)科學(xué),？,設(shè)想用機(jī)械模擬人的思維活動。,思維機(jī)械化,《邏輯的數(shù)學(xué)分析》《思維規(guī)律的研究》,關(guān)系邏輯德摩根定律,數(shù)理邏輯的起源與計算機(jī)科學(xué),《概念演算》,一種按算術(shù)語言構(gòu)成的思維符號語言,德國G.W. Leibniz(1626-1716)把數(shù)學(xué)引入

4、形式邏輯，明確提出用數(shù)學(xué)方法研究推理。英國G. Boole(1815-1864)等創(chuàng)立了邏輯代數(shù)，1847年Boole實現(xiàn)了命題演算。德國G.Frege(1848-1925)在1879年建立了第一個謂詞演算系統(tǒng)。英國B.Russell (1872-1970)等從邏輯學(xué)的基本法則建立了自然數(shù)理論、實數(shù)理論及解析幾何學(xué)等。奧地利K.Godel(1906-1978)在1931年提出Godel不完全性定理。英國Alan M. Turi

5、ng (1912-1954)在1936年提出一種抽象計算模型（數(shù)學(xué)邏輯機(jī)），引入圖靈機(jī)——一種理想的計算機(jī)。,數(shù)理邏輯發(fā)展史中的代表人物,數(shù)理邏輯的學(xué)習(xí),“我現(xiàn)在年紀(jì)大了，搞了這么多年的軟件，錯誤不知犯了多少，現(xiàn)在覺悟了。我想，假如我早年在數(shù)理邏輯上好好下點工夫的話，我就不會犯這么多的錯誤。不少東西邏輯學(xué)家早就說過了，可是我不知道。要是我能年輕二十歲的話，我就去學(xué)邏輯。” —— Edsger. W. Dijkstra

6、 1972年Turing獎獲得者 (1930-2002),單源點最短路徑算法,學(xué)習(xí)數(shù)理邏輯,⑴曹雪芹是《紅樓夢》的作者。⑵曹雪芹是小說家。⑶小說家是文學(xué)家。,數(shù)理邏輯是以數(shù)學(xué)的方法研究推理的形式結(jié)構(gòu)和規(guī)律的數(shù)學(xué)學(xué)科。所謂數(shù)學(xué)方法，是指建立一套符號，其作用是為了避免用自然語言討論問題時所帶來的歧義性。如，下面三條語句均用“是”作謂語動詞：,,三個語句中的三個“是”含義各不同。⑴曹

7、雪芹是《紅樓夢》的作者。此句中的“是”表示“＝”，其主語和謂語是對等的；⑵曹雪芹是小說家。此句中的“是”表示“∈”，小說家是集合，曹雪芹只是其中的一分子；⑶小說家是文學(xué)家。此句中的“是”表示“?”，文學(xué)家是包含著小說家的一個更大的集合?！　★@然，符號準(zhǔn)確地表達(dá)了語句的含義。,學(xué)習(xí)數(shù)理邏輯,玉龍雪山下的審判,在玉龍雪山腳下東巴谷的一條小路上立有一塊木牌，請過路行人對一個案子進(jìn)行審判。說的是有三個人，甲、乙、丙在玉龍山上射殺了一只老鷹

8、，這三個人的行為因違反《野生動物保護(hù)法》而被警察拘捕，但是這三個人都否認(rèn)老鷹是自己射殺的。經(jīng)過盤查和詢問，警察得出如下三個結(jié)論：⑴如果甲是無罪的，則乙和丙都有罪；⑵乙和丙中必有一人有罪；⑶要么甲無罪，要么乙有罪（但兩者不能同時成立）?，F(xiàn)在警方請求你協(xié)助判斷甲、乙、丙三人誰有罪，誰沒有罪，并在你認(rèn)為有罪的人前面的筐里投入一塊石頭。筆者查看三個筐發(fā)現(xiàn)，乙的筐里石頭最多，甲和丙的筐里則差不多。你認(rèn)為游客們的判斷是否正確呢？,,第3章

9、 命題邏輯,本章學(xué)習(xí)要求,,,3.1 命題的定義,命題 命題是能判斷出真假的語句.,⑴你媽喊你回家吃飯 . ⑵《建國大業(yè)》里面有大腕兒 .⑶北京是中國的首都.⑻火星上有生物.,⑷ x > 3。⑸立正?、蔬@朵花真漂亮！ ⑺你喜歡網(wǎng)絡(luò)游戲嗎? ⑼我說的都是假話。⑽雨上得泰山真火。,?,?,3.1 命題的定義,⑴必須是一個完整的句子，包括用數(shù)學(xué)式子表達(dá)；⑵句子必須具有真假意義（即有對錯之分）；⑶句子能判

10、斷出是真還是假。,例 下列句子都是命題嗎？,1960年杭州下雪了。太陽系外有宇宙人。好大的雪?。?>12。1+101=110。上海世博會開幕時天晴。大于2的偶數(shù)可表示成兩個素數(shù)之和。A>B。請勿吸煙。 姚明很帥。,具體命題的真假問題,在數(shù)理邏輯的學(xué)習(xí)中，不能去糾纏各種具體命題的真假問題，而是將命題當(dāng)成數(shù)學(xué)概念來處理，看成一個抽象的形式化的概念，把命題定義成非真必假的陳述句．,公説公

11、有理婆説婆有理,2.命題的真值,命題的真值就是命題的邏輯取值.,原子命題（簡單命題） 若一個命題不包含有更小的命題，即不可再分割的命題。小寫英文字母p, q, r, s,…或帶下標(biāo)p1, p2, p3, …等來表示原子命題。復(fù)合命題 若一個命題可以分解（分割）若干個原子命題。精確的定義為：設(shè)A1,A2,……An是原子命題，用邏輯聯(lián)結(jié)詞將這n個命題聯(lián)結(jié)起來，構(gòu)成的一個新命題，則稱這個新命題是復(fù)合命題。,3. 原子命題與

12、復(fù)合命題,把1和0稱為邏輯常量. 在邏輯表達(dá)式中出現(xiàn)的p, q, r或p1, p2 , p3 等稱為命題變元或邏輯變量. 命題變元可以代表任意命題, 從取值的角度看, 命題變元既可以取1又可以取0.,4. 常量與邏輯變量,字母p表示,,命題——具體的、特定的命題，有確定的真值,命題變元——任意命題，沒有確定的真值,3.2 邏輯聯(lián)結(jié)詞,五種常用的聯(lián)結(jié)詞： 否定聯(lián)結(jié)詞 ? 合取聯(lián)結(jié)詞 ∧ 析取聯(lián)結(jié)詞

13、 ∨ 蘊(yùn)含聯(lián)結(jié)詞 ? 等價聯(lián)結(jié)詞 ?,命題邏輯中出現(xiàn)更多的是復(fù)合命題. 一方面，復(fù)合命題是由原子命題構(gòu)成的，它需要聯(lián)結(jié)詞；另一方面，給定了原子命題，使用邏輯聯(lián)結(jié)詞，可以將它們構(gòu)成一個復(fù)合命題.邏輯聯(lián)結(jié)詞就是邏輯運(yùn)算.,1.否定詞 ?,設(shè)P是一個命題，命題 “P是不對的”稱為P的否定，記以?P，讀作非P。?P是真的當(dāng)且僅當(dāng)P是假的。,⑴否定聯(lián)結(jié)詞是一元邏輯運(yùn)算； ⑵若P是原子命題，則?P是復(fù)合命題。,日常語句中有：

14、 非 不 并非 ……,否定聯(lián)結(jié)詞的例子,P：長春是中國的城市。﹁P：長春不是中國的城市。 P是真命題，﹁P是假命題。 P：雪是黑色的。﹁P：雪不是黑色的。 命題P是假的，命題﹁P是真的。命題的真假，與其否定的真假，正好相反，這符合我們的直觀。,否定聯(lián)結(jié)詞使用的原則,將真命題變成假命題，將假命題變成真命題。但這并不是簡單的隨意加個不字就能完成的。,例

15、P: 這些都是學(xué)生。 ﹁P：這些不都是學(xué)生 ≠ 這些都不是學(xué)生例 （阿契貝難題）下述兩命題都是真命題：A: “本句是六字句”B: “本句不是六字句”,通常來講，若B是A的否定式，即一個為真，另一個為假。A與B的前提條件不相同， A的否定句應(yīng)為“本句非六字句”。,2.合取聯(lián)結(jié)詞 ?,設(shè)P，Q是兩個命題，命題 “P并且Q”稱為P，Q的合取，記以P?Q，讀作P且Q。 規(guī)定P?Q是真的當(dāng)且僅當(dāng)P和Q都是真的。,日常語句中有：

16、 并且 與 和 ……,⑴“?”是一個2元邏輯聯(lián)結(jié)詞；⑵若P，Q是原子命題，則P?Q是復(fù)合命題；,合取聯(lián)結(jié)詞的例子,P: 2×2＝5 Q：雪是白的。P∧Q：2×2＝5并且雪是白的。,P: 今天刮風(fēng)。 Q：今天下雨。P∧Q：今天刮風(fēng)并且今天下雨。,注意：“小王和小李是同學(xué)”是簡單命題，這里的“和”沒有合取的意思。,3.析取聯(lián)結(jié)詞 ∨,

17、設(shè)P，Q是兩個命題，命題 “P或者Q”稱為P，Q的析取，記以P?Q，讀作P或Q。規(guī)定P?Q是真的當(dāng)且僅當(dāng)P，Q中至少有一個是真的。,⑴ “?”是一個2元邏輯聯(lián)結(jié)詞；⑵若P，Q是原子命題，則P ?Q是復(fù)合命題；,日常語言中有： 或 或者 ……,析取聯(lián)結(jié)詞的例子,P: 2×2＝5 Q：雪是白的。 P∨Q：2×2＝5或者雪是白的。

18、 P∨Q顯然是一個真命題。,P: 今天刮風(fēng)。 Q：今天下雨。P∨Q ：今天刮風(fēng)或者今天下雨。 顯然，只有在今天刮了風(fēng)，或者下了雨的情況 下， P ∨ Q這句話才算說對。,4.異或聯(lián)結(jié)詞? : p ? q,設(shè)p，q是兩個命題，命題 “p異或q”稱為p，q的異或，記以p ? q，讀作p異或q。規(guī)定p?q是真的當(dāng)且僅當(dāng)p，q中真值不同。,⑴ “?”是一個2元邏輯聯(lián)結(jié)詞；⑵若p，q是原子

19、命題，則p ? q是復(fù)合命題.,日常語言中有： 或 或者 ……,注意：自然語言中的“或”可能是“可兼或”，也可能是“不可兼或”（排斥或），而析取表達(dá)的是可兼或。,異或聯(lián)結(jié)詞的例子,P：我明天到北京出差 Q ：我明天到廣州去度假P∨ Q：我明天到北京出差或者到廣州去度假但是我們知道“我明天到北京出差或者到廣州去度假”表示的是二者只能居其一，不會同時成立。因此不用析取聯(lián)結(jié)詞

20、表示 ，而是用異或聯(lián)結(jié)詞。,5.蘊(yùn)含(條件)聯(lián)結(jié)詞?,設(shè)P，Q是兩個命題，命題 “如果P，則Q”稱為P蘊(yùn)涵Q，記以P?Q。 規(guī)定，P?Q是假的當(dāng)且僅當(dāng)P是真的而Q是假的。,日常語言中有： 如果…則… 如果…那么… ……,在P?Q中，稱P為前件，Q為后件。,蘊(yùn)含聯(lián)結(jié)詞的例子,用→表示下列命題：⑴只要天下雨，我就回家。⑵只有天下雨，我才回家。⑶除非天下雨，否則我不回家。⑷僅當(dāng)天下雨，我才回家。解

21、 設(shè)p：天下雨。 q：我回家。 則⑴符號化為 p→q。⑵符號化為 q→p，或： ﹁ p→ ﹁ q⑶符號化為 q→p，或： ﹁ p→ ﹁ q⑷符號化為 q→p，或： ﹁ p→ ﹁ q,注1. 前件為假時，命題為真,如果蘊(yùn)含前件P是假命題，那么不管Q是什么命題，命題“如果P則Q”在邏輯中都被認(rèn)為是真命題。例：“如果張三能及格，那太陽從西邊升起?！闭f話者當(dāng)然知道兩命題風(fēng)馬牛不相及，而一般人此時并沒有說謊的必要，即這是

22、真命題，它所要明確的是“張三能及格”是假命題。,注2. 前件、后件可以毫不相關(guān),在日常語言中“如果……那么（則）……”所聯(lián)結(jié)的句子之間表現(xiàn)的是一種因果關(guān)系，但在數(shù)理邏輯中，盡管說前件蘊(yùn)涵后件，但兩個命題可以是毫不相關(guān)的。 例： P：2×3＝5 Q：雪是黑色的 P→Q：如果2×3＝5，則雪是黑色的命題P→Q是真命題，這有點不符合日常生活中的直觀，但這是邏輯的需要。,注3. 充分條件、必要

23、條件,p→q為真命題的邏輯關(guān)系是： p是q的充分條件， q是p的必要條件。“q是p的必要條件”的敘述方式還有： p僅當(dāng)q（僅當(dāng)q，則p） 只有q才p 只要p就q 除非q，否則非p（非p，除非q）,例：天下大雨（p)，地一定濕了(q)。 ? p→q,6.等價（雙條件）

24、聯(lián)結(jié)詞?,設(shè)P，Q是兩個命題，命題 “P當(dāng)且僅當(dāng)Q”稱為P等價Q，記以P?Q。規(guī)定，P?Q是真的當(dāng)且僅當(dāng)P，Q或者都是真的，或者都是假的。,“p當(dāng)且僅當(dāng)q”有兩層含義：⑴“p當(dāng)q”是指q ? p. ⑵“p僅當(dāng)q”是指p ? q.,日常語言中有： 當(dāng)且僅當(dāng) 充分必要 ……,等價聯(lián)結(jié)詞的例子,P: 2×2＝4 Q：雪是白色的。 P ? Q：2&

25、#215;2＝4當(dāng)且僅當(dāng)雪是白色的。 顯然，P ? Q是真的，這符合直觀。,P: 2×2＝5 Q：雪是黑色的。 P ? Q：2×2＝5當(dāng)且僅當(dāng)雪是黑色。 顯然，P ? Q是真的，這符合直觀。,注4. 充要條件,p ? q為真命題的邏輯關(guān)系是： p是q的充分條件， q是p的必要條件。,7.與非聯(lián)結(jié)詞? : p ?

26、 q,設(shè)p，q是兩個命題，命題 “p，q相與后否定”稱為p與非q，記以p ? q。規(guī)定， p? q是假的當(dāng)且僅當(dāng)p，q同時真的。,8.或非聯(lián)結(jié)詞? : p ? q,設(shè)p，q是兩個命題，命題 “p，q相或后否定”稱為p或非q，記以p ? q。規(guī)定，p ? q是真的當(dāng)且僅當(dāng)p，q同時為假的。,判斷命題的類型,（1）Tom和John是兄弟。（2）如果x>0， 則 x2>0。（3）如果兩個三角形全等，則它們的面積相等。（4）一

27、個三角形為等腰三角形當(dāng)且僅當(dāng)三角形有兩條邊相等。,中學(xué)《數(shù)學(xué)》選修2-1：四種命題,中學(xué)《數(shù)學(xué)》選修2-1：充分、必要,命題公式（合式公式，WFF），是如下定義的一個符號串：⑴命題變元和命題常量(1和0)是命題公式；⑵若G是命題公式，則（?G）是命題公式。⑶若G和H是命題公式，則（?G）、（G?H）、（G?H）、（G→H）、（G?H）是命題公式。⑷有限次應(yīng)用⑴、⑵、⑶所得到的符號串是僅有的命題公式。,3.3 命題公式及其真值表,

28、1.命題公式定義,設(shè)P為命題公式，Q為P中的一個連續(xù)的符號串，且Q為命題公式，則稱Q為P的子公式。,子公式,試判斷命題公式Q?R是不是命題公式 P?Q?R的子公式，為什么？,嚴(yán)格按照命題公式的定義，就會出現(xiàn)很多的括號。因此作如下一些可以省略括號的約定：⑴最外層的括號可以省略；⑵聯(lián)結(jié)詞運(yùn)算的優(yōu)先順序依次為: ? 、?、?、→、?；⑶同級運(yùn)算從左至右依次進(jìn)行。,關(guān)于命題公式,命題公式不再是一個復(fù)合命題，是復(fù)合命題的抽象，這種抽象表現(xiàn)在

29、，符號串中大寫的英文字母不代表一個具體的命題，而只是一個符號，這個符號可以用一個具體的來解釋。,2.命題的符號化,所謂命題的符號化就是使用符號——命題變元、邏輯聯(lián)結(jié)詞和括號將所給出的命題表示出來。其意義在于：⒈符號體系來源于實際問題；⒉給出進(jìn)一步學(xué)習(xí)邏輯演算系統(tǒng)的語義解釋時的一種標(biāo)準(zhǔn)模型。,將命題符號化的步驟：⑴找出所給命題的所有原子命題, 并用小寫英文字母或帶下標(biāo)表示；⑵ 確定應(yīng)使用的聯(lián)結(jié)詞,進(jìn)而將原命題用符號表示出來.,命

30、題符號化實例,⑴如果你走路時看書，那么你一定會成為近視眼。解：令 P：你走路； Q：你看書； R：你是近視眼。于是，上述命題符號化為：（P?Q）?R。,⑵除非他以書面或口頭的方式正式通知我，否則我不參加明天的會議。解：令 P：他書面通知我； Q：他口頭通知我； R：我參加明天的會議。于是，上述命題符號化為：（P?Q）?R。,命題符號化

31、實例,⑸只有努力學(xué)習(xí)、認(rèn)真復(fù)習(xí)，才能取得好成績。解：令P表示“努力學(xué)習(xí)”； Q表示“認(rèn)真復(fù)習(xí)”； R表示“取得好成績”。則原句譯為R?（P?Q）。,該語句能不能譯為（P?Q）? R？,翻譯是一定要考慮條件的必要性和充分性！,命題符號化實例,將下列語句形式化⑶狗急跳墻。 可表示為p→q， 其中p：狗急了，q：狗跳墻。⑷如果他不來,那么他

32、或者是生病了,或者是不在本地。 可表示為┐p→(q∨┐r)，其中p：他來，q：他生病，r：他在本地。,命題符號化實例,提示：根據(jù)命題的實際含義，不拘泥于原句形式地確定原子命題和選用聯(lián)結(jié)詞。在語句符號化時，一定要分解至原子命題，而不能把某個復(fù)合命題直接用命題變元P來表示，如此不能完整表達(dá)語句的意思，也不便于計算機(jī)處理相關(guān)語句及其產(chǎn)生的知識。,(1)天氣很好或很熱.(2)如果張三和李四都不去,那么我就去.(3)僅當(dāng)

33、你走, 我留下.(4)我今天進(jìn)城, 除非天下雨.(5)你只有刻苦學(xué)習(xí), 才能取得好成績.,練習(xí)：將下列命題符號化.,3.命題公式的真值表——解釋,設(shè)A是命題公式，A1，…，An是在A中出現(xiàn)的所有原子。指定A1，…，An的一組真值，則這組真值稱為A的一個解釋（也稱為一種真值指派）。記作I。,設(shè)G是公式，I是G的一個解釋，顯然，G在I下有真值，通常記為TI(G)。,如，G=P?Q，設(shè)解釋I為： I： P Q

34、 1 1則TI (G)=1,對一個公式A，將A在其所有解釋下取得的真值列成一個表，稱為A的真值表。,構(gòu)造命題公式A的真值表的具體步驟為：⑴找出A中所有命題變元A1，…，An（一般按字典順序給出），列出所有可能的解釋；⑵按從低到高的順序?qū)懗龈鲗哟蔚淖庸?；⑶對?yīng)每個解釋，計算命題公式的各層次的子公式的真值，直到最后計算出命題公式A的真值。,3.命題公式的真值表——真值表,例：命

35、題公式G=(P?Q)?R的真值表,一般來說,含n個命題變元的命題公式的不同的真值指派有2n種.,練習(xí)：命題公式 的真值表,4.命題公式的類型,如果命題公式G在它的所有解釋下都是真的，則稱G為永真的(或有效的，也稱為重言式)。如果命題公式G在它的所有解釋下都是假的，則稱公式G為永假的(或不可滿足的，也稱為了矛盾式)。如果命題G不是恒假的，則稱公式G為可滿足的。如果命題G至少有一種指派使其為真同時至少有一種指

36、派使其為假，則稱G為非永真式或中性式。,判斷命題公式的類型,利用真值表可以判斷一個命題公式的類型。,判斷命題公式的類型,證明：,結(jié)論：由A =1可推出B = 1, 則A ? B永真.由B =0可推出A = 0, 則A ? B永真.,利用取值法可以判斷一個命題公式的類型。,代入定理,設(shè)命題公式G包含n個不同命題變元p1，p2，……，pn，用命題公式A1，A2，……，An同時分別取代p1，p2，……，pn的每一個出現(xiàn)，所得到的命題公式

37、稱為G的一個代入實例。代入定理：對于永真式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，得到的仍是永真式；對于永假式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，得到的仍是永假式。,證明：G1:（P?Q）??(P?Q)是永真式， G2:（P?Q) ? ?(P?Q)是永假式。,證明：用命題公式P?Q取代永真式P??P得到G1，即G1是永真式P??P的一個代入實例，因此G1是永真的。,證明：用命題公式P?

38、 Q 取代永假式P ??P得到G2，即G2是永假式P??P的一個代入實例，因此G2是永假的。,3.4 邏輯等值的命題公式,命題公式邏輯等值：給定命題公式A,B，若在任何真值指派I下，其真值相同。則稱命題公式A,B是邏輯等值的，或邏輯等價，簡稱等值或相等。記作A=B。,=和?區(qū)別?,=與?表達(dá)的含義不同。=表示兩個公式間關(guān)系的符號；?是命題聯(lián)結(jié)詞，是運(yùn)算符號；=與?表達(dá)的結(jié)果不同。=表示兩個公式有等值關(guān)系，聯(lián)結(jié)后結(jié)果不表示一個公式，即

39、不代表命題，而?聯(lián)結(jié)兩個公式的后仍是一個公式，表示某個命題；=與?有密切的聯(lián)系。,命題公式A，B是等值的當(dāng)且僅當(dāng)A?B為永真式。設(shè)A、B、C是命題公式，則有⑴自反性：A=A；⑵對稱性：若A=B，則B=A；⑶傳遞性：若A=B，B=C，則A=C。,命題公式邏輯等值定理,證明：,命題公式邏輯等值定理,定理：,,基本邏輯等值式,⑴ ? ? G=G ；

40、 (對合律)⑵ G?G=G，G?G=G ； (冪等律)⑶ G?H=H?G，G?H=H?G； (交換律)⑷G?(H?S)=(G?H)?S,G?(H?S)=(G?H)?S； (結(jié)合律)⑸G?(G?H)=G，G?(G?H)=G； (吸收律)⑹G?(H?S)=(

41、G?H)?(G?S)， G?(H?S)=(G?H)?(G?S)； (分配律)⑺ G?0=G，G?1=G； (同一律)⑻ G?0=0，G?1=1 ; (零一律)⑼ ?(G?H)=?G??H, ?

42、(G?H)=?G??H ； (De Morgan律)⑽ G? ?G =1, ?G??G=0; (互補(bǔ)律),其它邏輯等值式,⑴ (A?B)=(A?B)?(B?A)；⑵ (A?B)=(?A?B)；⑶⑷⑸⑹,等值置換：設(shè)C是命題公式A的子公式且C=D，則將A中的C部分或全部替換成D所得到的命題公式與A等值。,等值演算法

43、——等值置換定理,利用基本等值式以及等值置換定理求解問題的方法稱為“等值演算法”.,化簡下列命題公式并將最后結(jié)果用只含?和?表示.,等值演算法應(yīng)用——公式化簡,⑴,解：,設(shè)A, B, C是任意的命題公式,判斷下列命題公式的類型.,等值演算法應(yīng)用——判斷公式類型,⑴,解：,等值演算法應(yīng)用——證明兩個命題公式相等,設(shè)A, B, C是任意的命題公式,證明下列等值式.,⑴,證：,置換和代入的區(qū)別,代入是命題公式取代變元，置換是命題公式取代子公式

44、；,代入必須用同一命題公式取代同一變元的每一處出現(xiàn)，而置換不必“每一處” 取代；,代入可用任意命題公式代變元，置換只能是等價置換；,置換后得到的新命題公式與原命題公式等價，而代入后得到的新命題公式不一定與原命公式等價。,置換和代入的區(qū)別,練習(xí)——化簡命題公式,設(shè)A,B,C為任意命題公式,化簡命題公式: ? A? ? B ? （?C ? A）使其最結(jié)果只含?和?表示。,解：,?A? ?B ?（?C ? A）= （?A? ?B） ?（C

45、? A）= （?A? ?B ?C ） ? （?A? ?B ?A）= ?（A ?B ??C ）,練習(xí)——判斷公式類型,設(shè)A,B,C為任意命題公式,試判斷命題公式:（A?（B?C））?（A?B）?C）的類型。,解：（A?（B?C））= A?（?B?C）=?A?（?B?C）=（?A??B）?C=?（A?B）?C=（A?B）?C(A?(B?C))?(A?B)?C)是永真式。,練習(xí)——判斷公式等值,G=（P?Q）?（R?Q），H=

46、（P?R）? Q，試判定G和H是否等值。,（P?Q）?（R?Q）= (?P?Q) ? （?R?Q）= ((?P?Q) ? ?R )? ((?P?Q) ? Q)= (?P ? ?R ) ? (Q ? ?R) ? Q ? (?P ? Q) = ? (P ? R) ? Q= (P ? R) ?Q ∴G和H邏輯等值。,對偶原理,設(shè)命題公式G中只含有3個邏輯聯(lián)結(jié)詞?，?，?，將G中的符號?換成符號?， 符號?換成符號?，符號1換

47、成符號0，符號0換成符號1，其他符號（原子符號和否定符號）不變，所得到的命題公式稱為G的對偶式，記作G*。,對偶原理：設(shè)A和B是命題公式，若A=B，則A*=B*。,設(shè)命題公式G=?（p?q）?1，Q= p?（q?r），分別求G，Q的對偶式。,解：G=?（p?q）?1的對偶式為:G*=?（p?q）?0；Q= p?（q?r）的對偶式為:Q*= p?（q?r）。,對偶原理實例,3.5 命題公式的范式,命題公式是千變?nèi)f化的，這給研究命

48、題演算帶來困難，這里我們研究如何由一個命題公式化歸為一個標(biāo)準(zhǔn)形式的問題，這樣命題演算的研究問題就歸結(jié)為對標(biāo)準(zhǔn)形式的研究問題，這種標(biāo)準(zhǔn)形式就叫范式。,1.析取范式和合取范式,設(shè)A是命題公式, 若A = A1? A2 ? … ? An (n ?1), 其中Ai(1? i ? n)是由命題變元或其否定組成的合取式, 則稱A1? A2 ? … ? An為A的析取范式.,Ai是由命題變元或其否定組成的合取式應(yīng)滿足：⑴命題變元及其否定不同時出現(xiàn)；

49、⑵命題變元及其否定按字典順序出現(xiàn)或按下標(biāo)從小到大順序出現(xiàn)；⑶相同的合取式中不重復(fù)出現(xiàn)。n =1時由單個命題變元或其否定組成的合取式看成一個整體是析取范式。,設(shè)A是命題公式, 若A = A1? A2 ? … ? An (n ?1), 其中Ai(1? i ? n)是由命題變元或其否定組成的析取式, 則稱A1? A2? … ? An為A的合取范式.,Ai是由命題變元或其否定組成的析取式應(yīng)滿足：⑴命題變元及其否定不同時出現(xiàn)；⑵命題變元

50、及其否定按字典順序出現(xiàn)或按下標(biāo)從小到大順序出現(xiàn)；⑶相同的析取式中不重復(fù)出現(xiàn)。n =1時由單個命題變元或其否定組成的析取式看成一個整體是合取范式。,1.析取范式和合取范式,對于任意命題公式，都存在等價于它的析取范式和合取范式。,定理,證明：對于公式G，通過如下算法即可得出等價于G的范式：⑴使用基本等價式，將G中的邏輯聯(lián)結(jié)詞?，?等歸約為?，?，?。⑵利用?(?H)=H和De Morgan律，將G中所有的否定號?都放在原子之前。⑶

51、反復(fù)使用分配律，即可得到等價于G的范式。,G?(H?S)=(G?H)?(G?S)G?(H?S)=(G?H)?(G?S),證明過程給出了求析取范式和合取范式的的步驟。,求G=(P?(Q?R))?S的析取范和合取范式。,解：G=(P?(Q?R))?S =?(P?(?Q?R))?S =?P??(?Q?R)?S =?P?(Q??R)?S (析取范式)

52、 =?P?(Q??R)?(S?(Q??Q)) =?P?(Q??R)?(S?Q)?(S??Q) (析取范式) =(?P?S)?(Q??R) =(?P?S?Q)?(?P?S??R) (合取范式),根據(jù)命題公式的析取范式及合取范式可分別得出該命題公式取真、假的指派.,析取范式及合取范式的應(yīng)用,析取范式及合取范式的應(yīng)用,從p, q, r, s

53、四人中選派2人出差,求滿足下列3個條件的選派方法有哪幾種.(1)若p去,則r和s中只去1人；(2)q和r不能都去；(3)若r去, 則s不能去.,解：p: p去出差, q: q去出差, r: r去出差, s: s去出差,則,練習(xí)：求命題公式G=P?（P→Q）取真的指派。,解：P?（P→Q）=P?（?P?Q）=（P??P）? （ P?Q）使G取真的指派有（1，1）,根據(jù)命題公式的析取范式及合取范式可分別得出該命題公式取真、假的指

54、派。,對于給定的命題變元,若由命題變元或其否定組成的合取式滿足(1) 每個命題變元或其否定二者之一只出現(xiàn)一次；(2)按字典順序或按下標(biāo)從小到大順序出現(xiàn), 稱這樣的合取式為由所給命題變元產(chǎn)生的最小項.,對原子P，Q，R而言，P??Q?R， P?Q?R ，?P??Q?R都是最小項,對原子P，Q，R而言，共有多少個最小項？,對于n個原子，共有多少個最小項？,2.主析取范式和主合取范式,對于n個原子P1，…，Pn而言，其不同的解釋共有2n個，

55、對于P1，…，Pn的任一個最小項m，2n個解釋中，有且只有一個解釋使m取1值。,最小項,對P，Q，R而言，?P?Q??R是最小項，解釋{0，1，0}使該最小項取1值，其他解釋都使該最小項取0值。,假設(shè)使最小項m取1值的解釋對應(yīng)的二進(jìn)制數(shù)為i，將m記為mi。,最小項與其對應(yīng)的解釋,設(shè)命題公式G中所有不同原子為P1，…，Pn，如果G的某個析取范式G?中的每一個合取式，都是關(guān)于P1，…，Pn的一個最小項，則稱G?為G的主析取范式。恒假公式的

56、主析取范式用0表示。,主析取范式,求主析取范式的方法1—等值演算法,通過以下步驟，求命題公式G的主析取范式。⑴使用基本等價式，將G中的邏輯聯(lián)結(jié)詞?，?刪除。⑵使用?(?H)=H和De Morgan律，將G中所有的否定號?都放在原子之前。⑶反復(fù)使用分配律和同一律，即可得到等價于G的主析取范式。,求G=?(R?P)?(Q?(P?R))的主析取范式,解： G=?(R?P)?(Q?(P?R)) =?(?R?P)?(

57、Q?P)?(Q?R) =(?P?R)?(Q?P)?(Q?R) =((?P?R)?(?Q?Q))?((Q?P)?(?R?R)) ?((Q?R)?(?P?P)) =(?P?Q?R)?(?P??Q?R)?(P?Q?R) ?(P?Q??R),求主析取范式的方法2,通過真值表來求命題公式G的主析取范式。⑴寫出命題公

58、式G的真值表；⑵對于使命題公式G取1的指派，寫出對應(yīng)的最小項，使該最小項在該指派下也為1；⑶G等值于所有這樣寫出的最小項的析取。,求公式G=(P?Q)?(?P?R)?(Q?R)的主析取范式,(?P??Q?R)? (?P?Q?R)? (P?Q??R)? (P?Q?R),課堂練習(xí),求(?p? q)∧(p?r)的主析取范式。,,(?p ? q) ∧(p ? r)=(q ∧? p) ∨(p ∧ r)∨(q ∧ r) (析取范式) =(

59、(p∧r)∧(q ?q))∨((?p∧q)∧(r∨?r)) ∨(( q∧r) ∧(p∨?p ))= ……=(p∧q∧r)∨(p ∧?q ∧ r)∨(? p∧q ∧r) ∨ (?p∧q ∧?r ) (主析取范式),定理,對于任意公式G，存在唯一一個與G等價的主析取范式。,證明：對于命題公式G，存在析取范式G?，使得G=G?。 設(shè)G中所有不同原子為P1，…，Pn，對于G?中每一個合取式Gi ?進(jìn)行檢查，如果Gi ?不是

60、關(guān)于P1，…，Pn的最小項，則Gi?中必然缺少原子P j1，…，Pjk。 因為 Gi?= Gi??(Pj1?? Pj1)?…?( Pjk?? Pjk) =于是將G?中非最小項Gi?化成了一些最小項之析取。對G?中其他非最小項也做如上處理，最后得等價于G的主析取范式G*。,,自學(xué)內(nèi)容,按主析取范式順序自學(xué)主合取范式。,1.最大項定義2.主合取范式定義3.求主合取范式方法4

61、.定理,命題公式恒真恒假性的判定,利用真值表法判斷公式類型。,利弊,判斷公式G=? (P?Q) ? ? P?Q是否恒真？,基于范式的判斷方法。,命題公式恒真恒假性的判定,利弊,解：G=(P?Q)?P??Q =(?P?Q)?P??Q =(?P?P??Q)?(Q?P??Q)故公式G是恒假的。,判斷公式G=(P?Q)?P??Q是否恒假?,命題公式G是恒假的當(dāng)且僅當(dāng)在等價于它的析取范式中，每個短語均至少包含

62、一個原子及其否定。,命題公式恒真恒假性的判定,把公式化成主析取范式,公式恒假時，主析取范式?jīng)]有極小項；公式恒真時，主析取范式有全部極小項。,一種判定算法,命題公式恒真恒假性的判定,對任給要判定的命題公式G，設(shè)其中有原子P1，P2，…，Pn，令P1取1值，求G的真值，或為1，或為0，或成為新公式G1且其中只有原子P2，…，Pn，再令P1取0值，求G真值，如此繼續(xù)，到最終只含0或1為止，若最終結(jié)果全為1，則公式G恒真，若最終結(jié)果全為0，則公

63、式G恒假，若最終結(jié)果有1，有0，則是可滿足的。,設(shè)H1，…，Hn，C是公式。若 H1,…,Hn,全為真,可得出C必然真,則稱由H1,…,Hn得出C的推理形式是有效的。記為：H1,…,Hn ?C。其中 H1,…,Hn稱為前提，C稱為結(jié)論。,3.7 命題邏輯中的推理,H1,…,Hn ?C簡稱為H1,…,Hn邏輯推出或邏輯蘊(yùn)涵C。,1.推理形式有效性的定義,命題公式的蘊(yùn)含關(guān)系,?和?區(qū)別?,?與?表示的含義不同。 ?表示兩個公式間關(guān)系的符號；

64、?是命題聯(lián)結(jié)詞，是運(yùn)算符號；?與?表示的結(jié)果不同。 ?表示兩個公式有蘊(yùn)含關(guān)系，聯(lián)結(jié)后結(jié)果不表示一個公式，即不代表命題，而?聯(lián)結(jié)兩個公式的后仍是一個公式，表示某個命題；?與? 有密切的聯(lián)系。,命題公式G?H當(dāng)且僅當(dāng)命題公式G?H是恒真的。設(shè)G、H、S是命題公式，則有⑴自反性：G?G；⑵反對稱性：若G?H且H?G，則G=H；⑶傳遞性：若G?H且H?S，則G?S。設(shè)G、H、S是命題公式，G=H當(dāng)且僅當(dāng)G?H且H?G。,公式蘊(yùn)

65、含關(guān)系相關(guān)定理,⑴ P?Q?P ⑵P?Q?Q⑶P?P?Q⑷Q?P?Q⑸P，Q?P?Q⑹P，P?Q ?Q⑺?Q，P?Q ??P,⑻ ?P?(P?Q) ⑼Q?(P?Q) ⑽P?Q, Q?R ?P?R⑾?P，P?Q?Q⑿ ?(P?Q)? P⒀?(P?Q)??Q ⒁ P?Q，P?R，Q?R ?R,2.基

66、本推理規(guī)則,推理有效性證明方法,真值表法取值法等值演算法主范式法自然推理系統(tǒng)中的構(gòu)造法,公式蘊(yùn)涵的證明——構(gòu)造法,構(gòu)造法（也稱形式演繹法）：根據(jù)一些基本等價式和基本蘊(yùn)涵式，從S出發(fā)，演繹出G，在演繹過程中我們遵循以下三條規(guī)則：P規(guī)則. 所給的前提在證明過程中隨時引用。 T規(guī)則. 已經(jīng)演繹出公式在以后可的證明過程中隨時引用。CP規(guī)則. 如果需要演繹出的公式是P?Q的形式，則我們可將P做為附加前提使用，而力圖去演繹出Q。,證

67、{(P?Q)，(P?R)，(Q?S)}?S?R,構(gòu)造法證明的實例1——直接演繹,證明：⑴P?Q 規(guī)則P⑵?P?Q 規(guī)則T⑴⑶Q?S 規(guī)則P⑷?P?S 規(guī)則T⑵⑶⑸?S?P 規(guī)則T⑷⑹P?R 規(guī)則P⑺?S?R

68、 規(guī)則T⑸⑹⑻S?R 規(guī)則T⑺,構(gòu)造法證明的實例2——CP規(guī)則,證 {P?(Q?S)，?R?P，Q}?R?S,證明：⑴?R?P P⑵R P（附加）⑶P T⑴⑵⑷P?(Q?S) P⑸Q?S