離散數(shù)學(xué)命題邏輯1.1

1、離散數(shù)學(xué)離散數(shù)學(xué) 東北石油大學(xué)軟件學(xué)院東北石油大學(xué)軟件學(xué)院王永安王永安離散數(shù)學(xué)(Discrete Mathematics)n研究離散量的關(guān)系離散量的關(guān)系的一門科學(xué)n研究離散結(jié)構(gòu)離散結(jié)構(gòu)的數(shù)學(xué)分科（辭海）n用一組基本的指令來編制一個(gè)計(jì)算機(jī)程序，非常類似于從一組公理來構(gòu)造一個(gè)從一組公理來構(gòu)造一個(gè)數(shù)學(xué)證明數(shù)學(xué)證明。(D.E.Knuth 1974 圖靈獎得主)怎樣理解離散n什么是離散？離散就是不連續(xù)。離散就是不連續(xù)。線與點(diǎn)。人的說話聲，鳥叫聲等；計(jì)算機(jī)里儲存聲音。 生活中，人眼見到的圖像(非計(jì)算機(jī)里的)；計(jì)算機(jī)里用灰度值(從0到255)表示的圖像。計(jì)算機(jī)不能處理連續(xù)信息的，這是由計(jì)算機(jī)的本質(zhì)：0和1，

2、決定的。因此，如果要用計(jì)算機(jī)來處理連續(xù)信息，必須經(jīng)過離散化。離散數(shù)學(xué)的地位離散數(shù)學(xué)的構(gòu)成計(jì)算機(jī)與離散數(shù)學(xué)n電子數(shù)字計(jì)算機(jī)是一個(gè)離散結(jié)構(gòu)，只能處理離散的數(shù)量關(guān)系n電子數(shù)字計(jì)算機(jī)是數(shù)理邏輯與電子學(xué)結(jié)合的產(chǎn)數(shù)理邏輯與電子學(xué)結(jié)合的產(chǎn)物物n離散數(shù)學(xué)是計(jì)算機(jī)編程的內(nèi)在思維邏輯的表象內(nèi)在思維邏輯的表象離散數(shù)學(xué)的特點(diǎn)n提高抽象思維、嚴(yán)格推理以及綜合歸納分析能力n以研究離散量的結(jié)構(gòu)和相互關(guān)系為主要目標(biāo)n顯著特征是符號化和形式化符號化和形式化離散數(shù)學(xué)的用途n又稱“計(jì)算機(jī)數(shù)學(xué)計(jì)算機(jī)數(shù)學(xué)”，因?yàn)殡x散數(shù)學(xué)的主要應(yīng)用領(lǐng)域是計(jì)算機(jī)。數(shù)理邏輯數(shù)字邏輯電路、密碼學(xué)圖論(包括樹)數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng) 、編譯原理、計(jì)算機(jī)網(wǎng)絡(luò)集合論和

3、關(guān)系代數(shù)軟件工程和數(shù)據(jù)庫原理考核方式與成績評定期末采用閉卷考試形式。 總評成績： 作業(yè)、平時(shí)考勤及學(xué)習(xí)態(tài)度占 15%，曠課一次扣2分，遲到一次扣1分。 期末考試占 85%。qq群:173410467博客: http:/ 第一部分?jǐn)?shù)理邏輯什么是數(shù)理邏輯n數(shù)理邏輯(Mathematical Logic) 是研究演繹推理的一門學(xué)科。用數(shù)學(xué)方法數(shù)學(xué)方法來研究推理的規(guī)律推理的規(guī)律統(tǒng)稱為數(shù)理邏輯。例1n請看下面兩段文字請看下面兩段文字(1)你的錢在你的錢包里，你的錢包在你的口袋里，那么你的錢一定在你的口袋里。(2) 人必然會死，蘇拉格底是人，因此蘇拉格底會死。什么是數(shù)理邏輯主要研究內(nèi)容：推理 著重于推理過

4、程是否正確 著重于語句間的關(guān)系主要研究方法：數(shù)學(xué)方法 就是引進(jìn)一套符號體系的方法,故數(shù)理邏輯也稱為符號邏輯(Symbolic Logic)。例2n已知1+1=2，1+2=3，請問你的推理結(jié)果是什么？ A. 2-1=1 B. 3-2=1 C. 3-1=2 D. 1+1+1=3誤區(qū)：條件中沒有給出“-”“-”-”是常識性臆斷是常識性臆斷結(jié)論：推理結(jié)果只有一個(gè)（推理表象松散、結(jié)論：推理結(jié)果只有一個(gè)（推理表象松散、 實(shí)質(zhì)嚴(yán)謹(jǐn)）實(shí)質(zhì)嚴(yán)謹(jǐn)）正確答案 D數(shù)理邏輯的組成命題邏輯命題邏輯命題的基本概念命題邏輯等值演算命題邏輯推理謂詞邏輯謂詞邏輯 ( (一階邏輯一階邏輯) )謂詞邏輯基本概念謂詞邏輯等值演算謂詞邏

5、輯推理總結(jié)什么是數(shù)理邏輯？用數(shù)學(xué)方法來研究推理的規(guī)律統(tǒng)稱為數(shù)理邏輯。用數(shù)學(xué)方法來研究推理的規(guī)律統(tǒng)稱為數(shù)理邏輯。數(shù)理邏輯的組成？命題邏輯和謂詞邏輯命題邏輯和謂詞邏輯為什么要研究數(shù)理邏輯？ 程序算法數(shù)據(jù)程序算法數(shù)據(jù) 算法邏輯控制算法邏輯控制 第一章命題邏輯基本概念命題邏輯基本概念n1.1 1.1 命題與聯(lián)結(jié)詞命題與聯(lián)結(jié)詞n1.2 命題公式及其賦值1.1命題與聯(lián)結(jié)詞n一、命題一、命題1.1.命題的概念命題的概念定義定義.1 非真即假非真即假 的陳述句稱作命題。命題的判斷結(jié)果判斷結(jié)果稱為命題的真值。真值只能取兩個(gè)值：真或假(0或1) 真判斷正確 假判斷錯(cuò)誤n2.2.命題的特點(diǎn)命題的特點(diǎn)

6、任何命題的真值都是唯一的。只有具有確定真值確定真值的陳述句陳述句才是命題。真值是否唯一與我們是否知道它的真值是兩回事。1.1命題與聯(lián)結(jié)詞1.1命題與聯(lián)結(jié)詞例例1.1 1.1 判斷下列語句是否是命題判斷下列語句是否是命題(1)北京是中國的首都。 (2)所有的樹木都是植物。(3)昨天大慶下雨。 (4) 請勿吸煙!(5) 這朵花多好看呀!(6)我正在說假話。悖論，不是命題悖論，不是命題真命題真命題命題命題不是命題不是命題不是命題不是命題真命題真命題1.1命題與聯(lián)結(jié)詞例例1.1 1.1 判斷下列語句是否是命題判斷下列語句是否是命題(7) x+80。(8)你出去么？(9)5或6是素?cái)?shù)。(10)如果行列式

7、的兩行對應(yīng)成比例，則行列式的值為0。(11)角A與角B相等當(dāng)且僅當(dāng)A與角B是對頂角。不是命題不是命題不是命題不是命題不是命題不是命題真命題真命題假命題假命題n2.2.命題的特點(diǎn)命題的特點(diǎn)命題一定是陳述句,但陳述句不一定是命題。命題的真值有時(shí)明確給出，有時(shí)還要依靠環(huán)境、條件、實(shí)際情況等因素環(huán)境、條件、實(shí)際情況等因素才能確定其真值。1.1命題與聯(lián)結(jié)詞1.1命題與聯(lián)結(jié)詞注意：注意：一切沒有判斷內(nèi)容的句子都不能一切沒有判斷內(nèi)容的句子都不能作為命題。作為命題。如命令句、感嘆句、如命令句、感嘆句、祈使句、疑問句、悖論（二義性祈使句、疑問句、悖論（二義性的陳述句）等。的陳述句）等。1.1命題與聯(lián)結(jié)詞例例1.

8、2 1.2 判斷下列語句是否是命題，判斷下列語句是否是命題，并判斷其真值。并判斷其真值。(1) 黑龍江不是一個(gè)國家。(2) 3既是素?cái)?shù)又是奇數(shù)。(3) 劉翔是大學(xué)生或是運(yùn)動員。(4) 如果周末天氣晴，則我們?nèi)ソ纪饴糜巍?5) 2+2=4當(dāng)且僅當(dāng)雪是白的。1.1命題與聯(lián)結(jié)詞3 3. .命題的分類命題的分類 命題定義定義1.1.2 1.1.2 簡單命題(原子命題)：由簡簡單的陳述句單的陳述句構(gòu)成的命題。(不能再分解為更簡單命題的命題)定義定義1.1.3 1.1.3 復(fù)合命題：由簡單命題簡單命題用聯(lián)聯(lián)結(jié)詞聯(lián)結(jié)結(jié)詞聯(lián)結(jié)而成的命題。復(fù)合命題簡單命題1.1命題與聯(lián)結(jié)詞n4.4.命題符號化命題符號化簡單命題

9、用p,q,r等表示。約定：約定：在數(shù)理邏輯中像 “x x”、“y y”、“z z”等字母等字母總是表示變量。命題的真值符號化為用“1” 或“T” 表示“真”；用“0” 或“F” 表示“假”。1.1命題與聯(lián)結(jié)詞n4.4.命題符號化命題符號化復(fù)合命題的符號化用p，q，r，等表示簡單命題（通常稱p，q，r，為命題常項(xiàng)或命題常元），將p，q，r， 用某些聯(lián)結(jié)詞符聯(lián)結(jié)詞符按一定的邏輯關(guān)系聯(lián)結(jié)起來就是復(fù)合命題的符號化形式。1.1命題與聯(lián)結(jié)詞n二、聯(lián)結(jié)詞二、聯(lián)結(jié)詞否定聯(lián)結(jié)詞 合取聯(lián)結(jié)詞 析取聯(lián)結(jié)詞 蘊(yùn)涵聯(lián)結(jié)詞 等價(jià)聯(lián)結(jié)詞 1.1命題與聯(lián)結(jié)詞n1.1.否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞是一個(gè)一元運(yùn)算一元運(yùn)算。例例

10、1.31.3 將下列命題符號化將下列命題符號化 p ：上海是一個(gè)大城市。p ：上海不是不是一個(gè)大城市。 q ：5能被2整除。q ：5不能不能被2整除。1.1命題與聯(lián)結(jié)詞n1.1.否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞定義定義.4設(shè)p為一命題，復(fù)合命題 “非p”（或“p的否定”）稱為p的否定式，記作p ，稱 為為否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞。p為真當(dāng)且僅當(dāng)p為假。p的真值表為 p p 0 1 1 01.1命題與聯(lián)結(jié)詞n2.2.合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞例例1.41.4 將下列命題符號化將下列命題符號化 (1) p：22=5， q：雪是黑的。 pq：22=5并且并且雪是黑的。(2) r：2是偶數(shù)，s：6是偶數(shù)。

11、rs：2和和6都是偶數(shù)。1.1命題與聯(lián)結(jié)詞n2.2.合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞定義定義.5設(shè)p，q為二命題，復(fù)合命題 “p并且q”（或“p與q”）稱為p與q的合取式，記作pq，稱 為為合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞。pq為真當(dāng)且僅當(dāng)p與q同時(shí)為真。合取聯(lián)結(jié)詞是一個(gè)二元運(yùn)算。1.1命題與聯(lián)結(jié)詞n2.2.合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞pq的真值表為 p q pq 0 0 1 1 0 1 0 1 0 0 0 11.1命題與聯(lián)結(jié)詞n2.2.合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞自然語句中的“既又”，“不但而且”，“不僅而且”， “一邊一邊”，“雖然但”，等都可符號化為pq 的形式。注意注意: :并非所有的“和”“與”都可符號化為

12、1.1命題與聯(lián)結(jié)詞 例例1.51.5 將下列命題符號化將下列命題符號化（1）小李既既是100米冠軍，又又是400米冠軍。 （2）他一邊一邊吃飯，一邊一邊看電視。（3）他不僅不僅聰明，而且而且用功。（4）他雖然雖然不太聰明，但但他很用功。（5）他不是不是不聰明，而是而是不用功。解解 （1）設(shè)p ：小李是100米冠軍, q ：小李是400米冠軍。pq （2） s：他吃飯，t ：他看電視。 st （3）設(shè)p：他聰明， q： 他用功。 pq （4） pq （5） (p)qn3.3.析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞例例1.61.6 將下列命題符號化將下列命題符號化(1)“(1)“王燕學(xué)過英語王燕學(xué)過英語或或法語法語

13、”符號化為符號化為pqpq，其中，其中p p：王燕學(xué)過英語，：王燕學(xué)過英語，q q：王燕學(xué)過法語。：王燕學(xué)過法語。但自然語言中，有時(shí)但自然語言中，有時(shí)“或或”表示排斥性或。表示排斥性或。(2)(2)派小王派小王或者或者小李中的一個(gè)人去開會小李中的一個(gè)人去開會pq正確答案正確答案 (pq)(pq)1.1命題與聯(lián)結(jié)詞1.1命題與聯(lián)結(jié)詞n3.3.析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞定義定義.6設(shè)p，q為二命題，復(fù)合命題 “p或q”稱為p與q的析取式，記作 pq ，稱 為為析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞。pq為真當(dāng)且僅當(dāng)p與q中至少一個(gè)為真。析取聯(lián)結(jié)詞是一個(gè)二元運(yùn)算。注意注意: :析取式析取式pqpq表示的是一

14、種表示的是一種相容或相容或，即允許即允許p p與與q q同時(shí)為真。同時(shí)為真。1.1命題與聯(lián)結(jié)詞n3.3.析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞pq的真值表為 p q pq 0 0 1 1 0 1 0 1 0 1 1 11.1命題與聯(lián)結(jié)詞4.4.蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵聯(lián)結(jié)詞例例1.71.7 將下列命題符號化將下列命題符號化(1)p：f(x)是可微的，q：f(x)是連續(xù)的。 pq：若f(x)是可微的，則f(x)是連續(xù)的。(2)p：經(jīng)一事， q：長一智。 pq：不經(jīng)一事，不長一智。1.1命題與聯(lián)結(jié)詞n4.4.蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵聯(lián)結(jié)詞定義定義.7設(shè)p，q是二命題，復(fù)合命題 “如果p，則q”稱為p與q的蘊(yùn)涵式，記作

15、pq。稱p為蘊(yùn)涵式的前件，q為蘊(yùn)涵式的后件，稱為為蘊(yùn)涵蘊(yùn)涵聯(lián)結(jié)詞聯(lián)結(jié)詞。 pq為假當(dāng)且僅當(dāng)p為真q為假。蘊(yùn)涵聯(lián)結(jié)詞是一個(gè)二元運(yùn)算。1.1命題與聯(lián)結(jié)詞n4.4.蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵聯(lián)結(jié)詞pq的真值表為 p q pq 0 0 1 1 0 1 0 1 1 1 0 11.1命題與聯(lián)結(jié)詞例例1.8 1.8 將下列命題符號化并判斷其真值將下列命題符號化并判斷其真值（1）若2+2=4，則地球是運(yùn)動的。（2）若2+24，則地球是運(yùn)動的。（3）若2+2=4，則地球是靜止的。（4）若2+24，則地球是靜止的。解解 p：2+2=4 ，q：地球是運(yùn)動的：地球是運(yùn)動的，（1）符號化為）符號化為 pq ,真值真值為為1。（2）

16、符號化為）符號化為 pq ,真值真值為為1。（3）符號化為）符號化為 pq ,真值真值為為0 。（4）符號化為）符號化為 pq ,真值真值為為1。1.1命題與聯(lián)結(jié)詞n使用蘊(yùn)涵聯(lián)結(jié)詞時(shí)應(yīng)注意的問題使用蘊(yùn)涵聯(lián)結(jié)詞時(shí)應(yīng)注意的問題在自然語句中“如果p ，則q”中的p與q往往有某種內(nèi)在的聯(lián)系，否則無意義。而在數(shù)理邏輯中p與與q不一定有什么內(nèi)在聯(lián)系不一定有什么內(nèi)在聯(lián)系。只要p，q能夠分別確定真值， pq即成為命題。在自然科學(xué)中， “如果p ，則q”往往表示前件p為真， 后件q也為真的推理關(guān)系。而在數(shù)理邏輯中， 當(dāng)p為真， q也為真時(shí)，命題pq為真，這與自然語言是一致的；但當(dāng)當(dāng)p為假時(shí)，則不為假時(shí)，則不管管

17、q是什么命題，命題是什么命題，命題 pq都是真命題都是真命題，這與自然語言是不一致的。1.1命題與聯(lián)結(jié)詞n4.4.蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵聯(lián)結(jié)詞自然語句中的“只要p就q”，“p僅當(dāng)q”，“只有q才p”，“除非q才p”等都可符號化為pq 的形式。只要明天晴天只要明天晴天,我們就去郊游。我們就去郊游。p：明天晴天明天晴天，q：我們?nèi)ソ加危覀內(nèi)ソ加?，pq：只要明天晴天只要明天晴天,我們就去郊游。我們就去郊游。1.1命題與聯(lián)結(jié)詞例例1.9 1.9 將下列命題符號化將下列命題符號化(1)只有2是偶數(shù)，3才能被2整除(2)除非6能被4整除，6才能被2整除(3)只有天下雨，他才乘公共汽車上班(4)除非天下雨，否則他

18、不乘公共汽車上班解(1) p：2是偶數(shù)， q：3能被2整除， qp (2) r： 6能被4整除， s： 6能被2整除, sr (3) u：天下雨, v：他才乘公共汽車上班, vu (4) vu (uv )1.1命題與聯(lián)結(jié)詞例例1.10 1.10 將下列命題符號化將下列命題符號化(1) p：a2+b2=a2，q： b=0。 pq：a2+b2=a2當(dāng)且僅當(dāng)b=0。 (2) s：1+2=3， r： 雪是黑的。 sr：1+2=3當(dāng)且僅當(dāng)雪是黑的。 (3) u：燕子飛回北方， v：春天來了。 uv：燕子飛回北方，春天來了。1.1命題與聯(lián)結(jié)詞n5.5.等價(jià)聯(lián)結(jié)詞等價(jià)聯(lián)結(jié)詞定義定義.8 設(shè)p

19、，q為二命題，復(fù)合命題 “p當(dāng)且僅當(dāng)q”稱為p與q的等價(jià)式，記作 pq，稱為為等價(jià)聯(lián)結(jié)詞等價(jià)聯(lián)結(jié)詞。pq為真當(dāng)且僅當(dāng)p與q的真值相同。等價(jià)聯(lián)結(jié)詞是一個(gè)二元運(yùn)算。1.1命題與聯(lián)結(jié)詞n5.5.等價(jià)聯(lián)結(jié)詞等價(jià)聯(lián)結(jié)詞pq的真值表為 p q pq 0 0 1 1 0 1 0 1 1 0 0 11.1命題與聯(lián)結(jié)詞例例1.11 1.11 將下列命題符號化并判斷其真值將下列命題符號化并判斷其真值（1）若2+2=4當(dāng)且僅當(dāng)3+3=6。（2）若2+24當(dāng)且僅當(dāng)3+3=6。（3）若2+2=4當(dāng)且僅當(dāng)3+36。（4）若2+2 4當(dāng)且僅當(dāng)3+36。解解 p：2+2=4，q： 3+3=6。（1）符號化為）符號化為 pq，真值真值為為1。 （2）符號化為）符號化為 pq，真值真值為為0。（3）符號化為）符號化為 pq，真值真值為為0。（4）符號化為）符號化為 pq，真值真值為為1。1.1命題與聯(lián)結(jié)詞n6.6.聯(lián)結(jié)詞的優(yōu)先級順序聯(lián)結(jié)詞的優(yōu)先級順序以上五種聯(lián)結(jié)詞，構(gòu)成一個(gè)聯(lián)結(jié)詞集，