JHY-第一章命題邏輯.ppt

離 散 數(shù) 學(xué) 主講人： 姜慧研 東北大學(xué) 軟件學(xué)院 多媒體醫(yī)療信息處理研究室 E-mail : ,2,緒論,離散數(shù)學(xué)課程的性質(zhì)、內(nèi)容 課程學(xué)習(xí)目的 課程學(xué)習(xí)方法,3,一.離散數(shù)學(xué)的性質(zhì)、內(nèi)容,離散數(shù)學(xué)是研究離散對象的結(jié)構(gòu)及其相互關(guān)系的科學(xué)。 計算機不論硬件還是軟件都屬于離散結(jié)構(gòu)，所以它所應(yīng)用的數(shù)學(xué)必是離散數(shù)學(xué)。 教學(xué)目的旨在通過學(xué)習(xí)本課培養(yǎng)和提高學(xué)生的抽象思維能力和邏輯推理能力。 性質(zhì)：此課是計算機科學(xué)與技術(shù)專業(yè)的重要的理論基礎(chǔ)課，也是該專業(yè)的主干課。 內(nèi)容： 1. 數(shù)理邏輯（第1、2章） 2. 集合論 （第3、4章） 3.格與布爾代數(shù)（第6章） 4. 圖論（第7章）,4,計算機系統(tǒng),硬件,軟件,組成原理,電子技術(shù),體系結(jié)構(gòu),數(shù)字邏輯電路,電路原理,大學(xué)物理,計算機網(wǎng)絡(luò),接口與通訊技術(shù),通訊概論,安全與保密,程序設(shè)計語言,匯編語言,高級語言,編譯原理,計算理論,C、C、JAVA、PB、VB,系統(tǒng)軟件,操作系統(tǒng),DOS、Windows 、UNIX,數(shù)據(jù)庫,Access、Sybase 、Oracle,數(shù)據(jù)結(jié)構(gòu),人工智能,應(yīng)用軟件開發(fā),離散數(shù)學(xué)：,軟件工程,算法設(shè)計與分析,集合,函數(shù),代數(shù)結(jié)構(gòu),格與布爾代數(shù),圖論,形式語言與自動機,數(shù)理邏輯,二元關(guān)系,5,二.學(xué)習(xí)此課的目的,1.計算機的誕生與發(fā)展和離散數(shù)學(xué)密切相關(guān) 正如馬克思所說的：“一門科學(xué)，只有當(dāng)它能夠運用數(shù)學(xué)時，才算真正發(fā)展了?！?計算機的誕生：正是在離散數(shù)學(xué)中的圖靈機的理論指導(dǎo)下誕生的(1936提出圖靈機-1946誕生計算機)。 計算機軟件的發(fā)展： 程序設(shè)計語言的發(fā)展:從機器語言匯編語言高級面向過程語言面向?qū)ο笳Z言智能語言 系統(tǒng)軟件的發(fā)展:如操作系統(tǒng)，從單用戶 多用戶 網(wǎng)絡(luò)分布式操作系統(tǒng) 所有這些發(fā)展都依賴于離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、編譯原理、操作系統(tǒng)、數(shù)據(jù)庫原理、軟件工程、網(wǎng)絡(luò)等理論。其中,離散數(shù)學(xué)是基礎(chǔ)，其它的理論中都用到了離散數(shù)學(xué)中的基本概念、基本思想、基本方法。,6,2.此課是主干課，也是后續(xù)課的基礎(chǔ)課 計算機專業(yè)的后續(xù)課中都大量地應(yīng)用到離散數(shù)學(xué)中的基本理論，要想學(xué)好專業(yè)課，必須先學(xué)好離散數(shù)學(xué)。 3.培養(yǎng)學(xué)生抽象思維和邏輯推理能力、創(chuàng)新能力 在大學(xué)學(xué)習(xí)知識很重要，但是能力的培養(yǎng)更重要。正如著名的物理學(xué)家勞厄所說：“重要的不是獲得知識，而是發(fā)展思維能力。教育無非是一切已學(xué)過的東西都遺忘的時候，所剩下來的東西。” 剩下的就是思維能力，它可以長期起作用。,7,北京大學(xué)姜伯駒教授談到數(shù)學(xué)時說：“數(shù)學(xué)是學(xué)習(xí)科學(xué)技術(shù)的鑰匙和先決條件”. 所以必須提高學(xué)生的數(shù)學(xué)修養(yǎng)(數(shù)學(xué)素質(zhì))。 數(shù)學(xué)修養(yǎng)包括：理解、抽象、見識、體驗。 理解能力：邏輯推理能力、不同語言對應(yīng)的轉(zhuǎn)換能力、想象能力等。 抽象能力：敏銳的洞察力，靈活的聯(lián)想類比、舉一反三能力，特別是把實際問題轉(zhuǎn)化為數(shù)學(xué)問題的能力。 見識：就是讓學(xué)生見識一些重要的數(shù)學(xué)思想、數(shù)學(xué)方法以及用數(shù)學(xué)解決實際問題的著名事例。有了見識才會思路寬，辦法多，遇到問題會自覺求助于數(shù)學(xué)。 體驗:數(shù)學(xué)是一種分析問題、解決問題的實踐活動。與打獵一樣是活本領(lǐng)。像轉(zhuǎn)換觀點、選擇方法、熟悉軟件、檢驗結(jié)果、發(fā)現(xiàn)毛病、查找原因多環(huán)節(jié)只有親身經(jīng)歷才能學(xué)到手。 學(xué)到這些活本領(lǐng)，就是一些基本素質(zhì)問題。,8,三.此課的特點及學(xué)習(xí)方法：,特點：內(nèi)容較雜，概念多，定理多，比較抽象，給學(xué)習(xí)帶來一定難度。 學(xué)習(xí)方法： 1.準確掌握每個概念(包括內(nèi)涵及外延)。 2.要有刻苦鉆研精神,不斷總結(jié)經(jīng)驗。 3.在理解內(nèi)容的基礎(chǔ)上，要較多地做些習(xí)題，從而再進一步加深理解所學(xué)內(nèi)容。 4.注意培養(yǎng)分析問題和解決問題的能力,9,第一篇 數(shù)理邏輯,邏輯是研究人的思維的科學(xué)。 邏輯包含： 1.辯證邏輯：是研究人的思維中的辯證法。 例如：用全面的和發(fā)展的觀點觀察事物；具體問題具體分析；實踐是檢查事物正誤的唯一標準。 2.形式邏輯：是研究人的思維的形式和一般規(guī)律。 數(shù)理邏輯是精確化、數(shù)學(xué)化的形式邏輯,10,一 .形式邏輯,人的思維過程： 概念 判斷 推理 正確的思維： 概念清楚，判斷正確，推理合乎邏輯。 人們是通過各種各樣的學(xué)習(xí)(理論學(xué)習(xí)和從實踐中學(xué)習(xí))來掌握許多概念和判斷。 形式邏輯主要是研究推理的。 推理： 是由若干個已知的判斷(前提)，推出新的判斷(結(jié)論)的思維過程。,11,推理方法,類比推理：由個別事實推出個別結(jié)論。 如：地球上有空氣、水，地球上有生物?；鹦巧嫌锌諝狻⑺?。 火星上有生物。 歸納推理：由若干個別事實推出一般結(jié)論。 如：銅能導(dǎo)電。鐵能導(dǎo)電。錫能導(dǎo)電。鉛能導(dǎo)電。 一切金屬都導(dǎo)電。 演繹推理：由一般規(guī)律推出個別事實。 形式邏輯主要是研究演繹推理的。,12,演繹推理 舉例,演繹推理：由一般規(guī)律推出個別事實。 例1： 如果天下雨，則路上有水。(一般規(guī)律) 天下雨了。 (個別事實) 推出結(jié)論：路上有水。 (個別結(jié)論) 例2： (大前提)：所有金屬都導(dǎo)電。 (一般規(guī)律) (小前提)：銅是金屬。 (個別事實) 推出結(jié)論：銅能導(dǎo)電。 (個別結(jié)論),13,二. 數(shù)理邏輯,數(shù)理邏輯是用數(shù)學(xué)的方法研究形式邏輯。 “數(shù)學(xué)方法”：是建立一套有嚴格定義的符號，即建立一套形式語言，來研究形式邏輯。所以數(shù)理邏輯也稱為“符號邏輯”。 用數(shù)學(xué)的方法研究形式邏輯，是由萊布尼茲 (G.W.Leibniz, 1646-1716,德國)首先提出來的。所以萊布尼茲被認為是數(shù)理邏輯的創(chuàng)始人。 布爾(George Boole,1815-1864,英國) 和德.摩根(De Morgan, 1806-1876,英國)取得最初成果。,14,弗雷格 (G.Frege,1848-1925,德國) 、皮亞諾 (G.Peano, 1883-1932,意大利)和羅素(B.Russell,1870-970,英國)建立了命題演算和謂詞演算。突破了古典形式邏輯的局限性，形成了一個完整的邏輯體系。 希爾伯特(D.Hilbert,1862-1943,德國)和哥德爾(Kurt Gdel,1906-1978,美籍奧地利數(shù)學(xué)家)等人使得數(shù)理邏輯發(fā)展成為一門內(nèi)容豐富的學(xué)科。,15,數(shù)理邏輯的主要內(nèi)容： 邏輯演算 證明論 公理集合論 遞歸論 模型論 我們這里只涉及邏輯演算中“命題邏輯”和“謂詞邏輯” 。 數(shù)理邏輯與數(shù)學(xué)的其它分支、計算機科學(xué)、人 工智能、語言學(xué)等學(xué)科均有密切聯(lián)系。 下面就前面兩個例子，說明如何將推理符號化的。,16,數(shù)理邏輯把推理符號化之一,設(shè) P表示：天下雨。 設(shè)Q表示：路上有水。 設(shè)表示：如果則 例1的推理過程表示為： 前提1:PQ (如果天下雨,則路上有水。) 前提2：P (天下雨了。) 結(jié) 論：Q (路上有水。) (這就是第一章命題邏輯中要討論的問題),17,數(shù)理邏輯把推理符號化之二,設(shè)M(x): x是金屬 . 設(shè)C(x): x能導(dǎo)電. 設(shè)x 表示: 所有的x . 設(shè) a 表示銅. 例2的推理過程表示為： 前提:x(M(x)C(x) (所有金屬都導(dǎo)電.) 前提:M(a) (銅是金屬.) 結(jié)論:C(a) (銅能導(dǎo)電.) (其中符號M(x)是謂詞，所以這就是第二章“謂詞邏輯”中所討論的內(nèi)容.）,18,使用計算機必須首先學(xué)會編“程序”，那么什么 是程序？ 程序算法數(shù)據(jù) 算法邏輯控制 可見“邏輯”對于編程序是多么重要。要想學(xué) 好、使用好計算機，必須學(xué)習(xí)邏輯，此外，通過 學(xué)習(xí)邏輯，掌握邏輯推理規(guī)律和證明方法 ，會 培養(yǎng)學(xué)生的邏輯思維能力，提高證明問題的技巧。,數(shù)理邏輯與計算機,19,錢學(xué)森談“計算機與數(shù)理邏輯”,電子計算機與數(shù)理邏輯具有非常密切的關(guān)系。正是在數(shù)理邏輯中，把人類的推理過程分解成一些非常簡單原始的、非常機械的動作，才使得用機器代替人類的推理的設(shè)想有了實現(xiàn)的可能。 有了電子計算機，使用它時，必須先進行程序設(shè)計，把整個推理、計算過程，絲毫不漏地考慮到，統(tǒng)統(tǒng)編入程序，而機器則依次而運行；如稍有錯誤，將立即得到毫無意義的結(jié)果?？梢姳仨氂凶銐虻臄?shù)理邏輯的訓(xùn)練，熟悉推理過程的全部細節(jié),才能從事程序設(shè)計。 此外，程序設(shè)計是一個很細致又很麻煩的工作，如何從事程序設(shè)計，如何防止在計算過程中出錯，如何很快地發(fā)現(xiàn)這種錯誤而及時加以改正，都是程序設(shè)計理論(軟件理論)中非常根本又非常重要的內(nèi)容，大家都認為，這些內(nèi)容都與數(shù)理邏輯息息相關(guān)。,20,我現(xiàn)在年紀大了，搞了這么多年軟件，錯誤不知犯了多少，現(xiàn)在覺悟了。我想，假如我早在數(shù)理邏輯上好好下點功夫的話，我就不會犯這么多錯誤。不少東西邏輯學(xué)家早就說過了，可是我不知道。要是我能年輕20歲的話，我就會回去學(xué)邏輯。,軟件大師戴克斯特拉談“數(shù)理邏輯”,21,第一章 命題邏輯,這章是以“命題”為中心 主要討論： 命題的表示、命題的演算 命題演算中的公式，及其應(yīng)用 命題邏輯推理,22,1-1. 命題及其表示法,本節(jié)主要討論三個問題： 命題的概念 命題的真值 原子命題與復(fù)合命題,23,一. 命題的概念,命題是一個能確定是真的或是假的判斷。（判斷都是用陳述句表示） 例1-1.1 判定下面這些句子哪些是命題。 2是個素數(shù)。 雪是黑色的。 2015年人類將到達火星。 如果 ab且bc，則ac。 x+y5 請打開書！ 您去嗎？ 是命題,判斷一個語句是否為命題，首先看是否為陳述句，再看其真值是否唯一。,24,二.命題的真值,一個命題所作的判斷有兩種可能：是正確的判斷或者是錯誤的判斷。所以一個命題的真值有兩個：“真”或“假” 真值為真:一個命題所作的判斷與客觀一致,則稱該命題的真值為真,記作T (True)。 真值為假:一個命題所作的判斷與客觀不一致,則稱該命題的真值為假,記作F (False)。 例1-1.1中(1)(4)的真值為真,(2)的真值為假, (3)暫時不能定，等到2015年確定。,25,三. 原子命題與復(fù)合命題,簡單命題 (原子命題)：由最簡單的陳述句構(gòu)成的命題 (該句再不能分解成更簡單的句子了)。通常用大寫英字母表示。 例1-1.1中的(1)、(2)、(3)是原子命題。 復(fù)合命題 (分子命題)：由若干個原子命題構(gòu)成的命題。 例1-1.1中的(4)是由三個原子命題(ab、bc、ac)構(gòu)成的復(fù)合命題。,26,1-2 聯(lián)結(jié)詞,復(fù)合命題：是用“聯(lián)結(jié)詞”將原子命題聯(lián)結(jié)起來構(gòu)成的。 歸納自然語言中的聯(lián)結(jié)詞，定義了六個邏輯聯(lián)結(jié)詞： (1) 否定： (2) 合?。海⑶?(3) 析?。海杉嫒〉幕蛘?(4) 異或： ，不可兼取的或 (5) 蘊涵：，如果。，那么。 (6) 等價：,27,一. 否定“”,表示：“不成立”，“不”。 用于：對一個命題P的否定，寫成P，并 讀成“非P”。 P的真值：與P真值相反。 例1-2.1 P：2是素數(shù)。 P：2不是素數(shù)。,P P,T F,F T,28,例如： Q：今天是星期三 Q：今天不是星期三 Q不能理解為“今天是星期四”，因為“今天是星期三”的否定，并不一定必是星期四，還可能是星期五、六 例如： Q：這些都是男同學(xué)。 Q：這些不都是男同學(xué)。 (翻譯成“這些都不是男同學(xué)”是錯的。),29,二. 合取“”,表示:“并且”,“不但而且.”,“既又 .”,“盡管還 ” 例1-2.2 P：小王能唱歌，Q：小王能跳舞。 PQ：小王能歌善舞。PQ讀成P合取Q。 PQ的真值為真，當(dāng)且僅當(dāng)P和Q的真值均為真。,P Q PQ,F F F,F T F,T F F,T T T,“這臺機器質(zhì)量很好，但是很貴”， 這句話的含義是說同一臺機器質(zhì)量很好而且很貴。 若用P表示“這臺機器質(zhì)量很好”，用Q表示“這臺機器很貴”，那么這句話的邏輯表示就是P Q,30,三. 析取“”、異或“ ”,表示“或者” “或者”有二義性，看下面兩個例子： 例1-2.3. 燈泡或者線路有故障。 例1-2.4. 第一節(jié)課上數(shù)學(xué)或者上英語。 例3中的或者是可兼取的或。即析取“” 例4中的或者是不可兼取的或，也稱之為異或、排斥或。即“ ”.,31,1. 析取“”,P：燈泡有故障。 Q：線路有故障。 例3中的復(fù)合命題可表示為：PQ，讀成P析取Q，P或者Q。 PQ的真值為F，當(dāng)且僅當(dāng)P與Q均為F。,P Q PQ,F F F,F T T,T F T,T T T,例1-2.3. 燈泡或者線路有故障。,A: 2小于3 B: 雪是黑的 AB就是命題“2小于3或者雪是黑的” 由于2小于3是真的，所以AB必取值為真，盡管 “雪是黑的”這命題取假,32,2. 異或“ ”,P：第一節(jié)上數(shù)學(xué)。 Q：第一節(jié)上英語。 例4中的復(fù)合命題 可寫成P Q，讀 成P異或Q。 P Q的真值為F， 當(dāng)且僅當(dāng)P與Q的真值相同。,F F F,F T T,T F T,T T F,P Q P Q,例1-2.4. 第一節(jié)課上數(shù)學(xué)或者上英語,33,3.“異或”的另一種表示,異或是表示兩個命題不可能同時都成立。 命題“第一節(jié)課上數(shù)學(xué)或者上英語?！笨梢越忉尀椋?“第一節(jié)課上數(shù)學(xué)而沒有上英語或者第一節(jié)課上英語而沒有上數(shù)學(xué)?！?于是有 P Q 與 (PQ)(QP ) 是一樣的。 實際應(yīng)用中必須注意“或者”的二義性。,34,四. 蘊涵(條件)“”,表示“如果 則 ”， 例1-2.5： P表示：缺少水分。 Q表示：植物會死亡。 PQ：如果缺少水分，植物就會死亡。 PQ：也稱之為蘊涵式，讀成“P蘊涵Q”，“如果P則Q”。也說成P是PQ 的前件，Q是PQ的后件。 還可以說P是Q的充分條件，Q是P的必要條件。,35,關(guān)于充分條件和必要條件的說明：,充分條件：只要條件成立，結(jié)論就成立，則該條件就是充分條件。 上例中，“缺少水分”就是“植物會死亡” 的充分條件。 在自然語言中表示充分條件的詞有 ： 如果 則 ，只要 就，若則 必要條件：就是如果該條件不成立，那么結(jié)論就不成立, 則該條件就是必要條件。 上例中，“植物死亡”就是“缺少水分”的必要條件(植物未死亡，一定不缺少水分)。 在自然語言中表示必要條件的詞有 ： 只有 才 ； 僅當(dāng)， ; , 僅當(dāng)。,36,PQ的真值：,PQ的真值為假，當(dāng)且僅當(dāng)P為真，Q為假。 注意：當(dāng)前件P為假時， PQ為T。,P Q PQ 小王借錢不還 我替他還 （我給小王擔(dān)保）,F F T,F T T,T F F,T T T,37,P: n 3 (n為整數(shù)) Q: n2 9 命題PQ表示“如果n 3那么n2 9”, 分析PQ的真值 P = Q = T。這時如n = 4 3，有n2 = 16 9，這符合事實PQ = T，正是我們所期望的可以PQ表示P、Q間的因果關(guān)系，這時規(guī)定P Q是自然的 P = T, Q = F。如n 3而n2 9 由于前提條件n 3不成立，而n2 9 成立與否并不重要，都不違反對自然用語“如果n 3那么n2 9”成立的肯定。于是P= F時可規(guī)定P Q = T,PQ = PQ,38,蘊含式PQ可以用多種方式陳述,“若P, 則Q” “只要p,就q” “P是Q的充分條件” “Q是P的必要條件” “Q每當(dāng)P” “P僅當(dāng)Q” “只有Q 才P” “除非Q, 才P” “除非Q, 否則非P”,39,舉例：,令：P：天氣好。 Q：我去公園。 1.如果天氣好，我就去公園。 2.只要天氣好，我就去公園。 3.天氣好，我就去公園。 4.僅當(dāng)天氣好，我才去公園。 5.只有天氣好，我才去公園。 6.我去公園，僅當(dāng)天氣好。 命題1.、2.、3.寫成： PQ 命題4.、5.、6.寫成： QP 可見“”既表示充分條件（即前件是后件的充分條件）； 也表示必要條件（即后件是前件的必要條件）。這一點要 特別注意!它決定了哪個作為前件，哪個作為后件。,40,五.等價(雙條件）“”,表示“當(dāng)且僅當(dāng)”、“充分且必要” 例1-2.6： P：ABC是等邊三角形。 Q：ABC是等角三角形。 PQ ：ABC是等邊三角形當(dāng)且僅當(dāng) 它是等角三角形。,41,P Q PQ,F F T,F T F,T F F,T T T,PQ的真值：,PQ的真值為真，當(dāng)且僅當(dāng)P與Q的真值相同。,42,本節(jié)小結(jié)：,要熟練掌握這五個聯(lián)結(jié)詞在自然語言中 所表示的含義以及它們的真值表的定義。,43,特別要注意“或者”的二義性，即要區(qū)分給定的“或”是“可兼取的或”還是 “不可兼取的或”。 特別要注意“”的用法，它既表示“充分條件”也表示“必要條件”，即要弄清哪個作為前件，哪個作為后件。 課堂練習(xí),44,練習(xí)：填空 已知PQ為T，則P為( )，Q為( )。 已知PQ為F，則P為( )，Q為( )。 已知P為F，則PQ為( )。 已知P為T，則PQ為( )。 已知PQ為T，且P為F ，則Q為( )。 已知PQ為F，則P為( )，Q為( )。 已知P為F，則PQ為( )。 已知Q為T，則PQ為( )。 已知 PQ為F，則P為( )， Q為( )。,45,已知P為T， PQ為T，則Q為( )。 .已知Q為T, PQ為T，則P為( )。 .已知PQ為T，P為T , 則Q為( ). .已知PQ為F，P為T , 則Q為( ). .PP 的真值為( ). .PP 的真值為( )。,46,填空練習(xí) 答案： 已知PQ為T，則P為( T )，Q為( T )。 已知PQ為F，則P為( F )，Q為( F )。 已知P為F，則PQ為( F )。 已知P為T，則PQ為( T )。 已知PQ為T，且P為F ，則Q為( T )。 已知PQ為F，則P為( T )，Q為( F )。 已知P為F，則PQ為( T )。 已知Q為T，則PQ為( T )。 已知 PQ為F，則P為( F )， Q為( T )。,47,已知P為T， PQ為T，則Q為( T )。 .已知Q為T, PQ為T，則P為( F )。 .已知PQ為T，P為T , 則Q為( T ). .已知PQ為F，P為T , 則Q為( F ). .PP 的真值為( T ). .PP 的真值為( T )。,48,1-3 命題公式及命題符號化,一.常值命題與命題變元 常值命題：即是我們前面所說的命題。它有具體含義 (真值)。 例如：“3是素數(shù)?！本褪浅Ｖ得}。 命題變元：用大寫的英文字母如P、Q等表示任何命題。稱這些字母為命題變元。 對命題變元作指派(給命題變元一個解釋)：將一個常值命題賦予命題變元的過程，或者是直接賦給命題變元真值“T”或“F”的過程。 注意：命題變元本身不是命題，只有給它一個解釋，才變成命題。,49,二.合式公式 ( wff ) (well formed formulas) 對計算機而言，最方便的定義方式就是構(gòu)造性的（或遞歸性的），即用簡單的原子命題變元和聯(lián)結(jié)詞，通過有限步構(gòu)造出新的復(fù)合命題來。因此，我們給出下面的定義： 1.定義： 單個命題變元是個合式公式。 若A是合式公式，則A是合式公式。 若A和B是合式公式，則(AB)， (AB)，(AB)和(AB)都是合式公式。 當(dāng)且僅當(dāng)有限次地應(yīng)用、所得到的含有命題變元、聯(lián)結(jié)詞和括號的符號串是合式公式。 注意：這個定義是遞歸的。(1)是遞歸的基礎(chǔ)，由(1)開始，使用(2)、(3)規(guī)則，可以得到任意的合式公式。,50,這里所謂的合式公式可以解釋為合法的命題公式，也稱之為命題公式，有時也簡稱公式。 按照合式公式定義，下面的式子不是合式公式： PQ， PR， PQR 下面的式子才是合式公式： (PQ)，(PR)，(PQ)R) 按照合式公式定義最外層括號必須寫。 約定：為方便，最外層括號可以不寫， 上面的合式公式可以寫成： PQ，PR，(PQ)R,51,2.命題公式的真值表 命題公式不是復(fù)合命題，所以它沒有真值，但是給其中的所有命題變元作指派以后它就有了真值。 可以以表的形式反應(yīng)它的真值情況， 例如：命題公式(PQ)Q 的真值表如下所示： P Q P PQ (PQ)Q F F T F F F T T T T T F F T T T T F T T,52,由于對每個命題變元可以有兩個真值(T,F)被指派，所以有n個命題變元的命題公式 A(P1,P2,Pn) 的真值表有2n行。 為有序地列出A(P1,P2,Pn)的真值表，可將F看成0、T看成1，按二進制數(shù)次序列表。,如A(P,Q)的真值表可按照如下次序指派： 00(FF)，01(FT)，10(TF)，11(TT),如A(P,Q,R)的真值表可按照如下次序指派：,53,A(P1,P2,Pn)的真值表，按照二進制數(shù) 000 0001 00010 1 10 111 0 1 2 2n -2 2n -1 (即按照十進制的0,1,2,. ,2n -1的次序進行指派列真值表) 。,54,例如列出P(QR)的真值表,P Q R QR P(QR),000 F F F T T,001 F F T T T,010 F T F F T,011 F T T T T,100 T F F T T,101 T F T T T,110 T T F F F,111 T T T T T,55,三.命題符號化 命題符號化定義:用命題公式的符號串來表示給定的命題。 命題符號化的方法 1.首先要明確給定命題的含義。 2.對于復(fù)合命題，找聯(lián)結(jié)詞，用聯(lián)結(jié)詞斷句，分解出各個原子命題。 3.設(shè)原子命題符號，并用邏輯聯(lián)結(jié)詞聯(lián)結(jié)原子命題符號，構(gòu)成給定命題的符號表達式。,56,例1.說離散數(shù)學(xué)無用且枯燥無味是不對的。 P：離散數(shù)學(xué)是有用的。 Q：離散數(shù)學(xué)是枯燥無味的。 該命題可寫成： (PQ) 例2.如果小張與小王都不去，則小李去。 P：小張去。 Q：小王去。 R：小李去。 該命題可寫成： (PQ)R 如果小張與小王不都去，則小李去。 該命題可寫成： (PQ)R 也可以寫成： (PQ)R,57,例3. 僅當(dāng)天不下雨且我有時間，才上街。 P：天下雨。Q：我有時間。R：我上街。 分析：由于“僅當(dāng)”是表示“必要條件”的，即“天不下雨且我有時間”，是“我上街”的必要條件。所以 該命題可寫成： R(PQ) 例4.人不犯我，我不犯人；人若犯我，我必犯人。 P：人犯我。Q：我犯人。 該命題可寫成：(PQ)(PQ),P是Q的充分條件,P是Q的必要條件,P是Q的充分且必要條件,或?qū)懗桑?PQ,58,例5 .若天不下雨，我就上街；否則在家。 P：天下雨。Q ：我上街。R：我在家。 該命題可寫成： (PQ)(P R).,59,本節(jié)重點掌握： 列命題公式的真值表 將給定命題符號化 作業(yè)題： 第8頁：（3） 第12頁：（5）、（7） 第17頁：（1）a)、d),60,1-4 重言式與重言蘊涵式,一.重言式(永真式)與矛盾式(永假式) 1.例子： P PP PP F T F T T F 可見不論P取什么真值PP 的真值總是為真，PP的真值總是為假。故稱PP為重言式(永真式)，稱PP為矛盾式(永假式)。,61,2 .重言式(矛盾式)定義 A(P1,P2,Pn) 是含有命題變元P1,P2, Pn的命題公式，如不論對P1, P2 , , Pn作任何指派，都使得A(P1,P2, Pn) 為真(假)，則稱之為重言式(矛盾式), 也稱之為永真式 (永假式)。 3.重言式的證明方法 方法1：列真值表。 方法2：公式的等價變換，化簡成“T”。 方法3：用公式的主析取范式。,62,方法1. 列真值表。 例如，證明 (P(PQ)Q 為重言式。 P Q PQ P(PQ) (P(PQ)Q F F T F T F T T F T T F F F T T T T T T 永真式的真值表的最后一列全是“T”。,63,4. 永真式的性質(zhì) 1).如果A是永真式，則A是永假式。 2).如果A、B是永真式，則(AB)、(AB)、(AB)和(AB)也都是永真式。 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) 的置換例式。,64,例如： 公式A：P(P(PQ)R) 用(DE)替換A中P得到A的置換例式 B： (DE)(DE)(DE)Q)R) 如果A是永真式，例如A為PP，用 (DE)替換A中P，得到A的置換例式 B： (DE)(DE) ， 顯然B也是永真式。 如果可以斷定給定公式是某個永真式的置換例式的話，則這個公式也是永真式。,65,二.重言(永真)蘊涵式 有些重言(永真)式，如(P(PQ)Q， 公式中間是“”聯(lián)結(jié)詞，稱為重言蘊涵式。 1.定義：如果公式AB是重言式，則稱A重言(永真)蘊涵B，記作AB。 上式可以寫成 (P(PQ)Q 注意符號“”不是聯(lián)結(jié)詞，它是表示公式間的“永真蘊涵”關(guān)系，也可以看成是“推導(dǎo)”關(guān)系。即AB可以理解成由A可推出B，即由A為真，可以推出B也為真。,66,2.重言(永真)蘊涵式證明方法 方法1.列真值表。(即列永真式的真值表) 下面討論另外兩種方法。,先看一看AB的真值表，如果AB為永真式，則真值表的第三組指派不會出現(xiàn)。于是有下面兩種證明方法。,67,方法2.假設(shè)前件為真，推出后件也為真。 例如,求證： (AB)C)D(CD) AB 證明:設(shè)前件(AB)C)D(CD) 為真。則(AB)C)、D、(CD)均真， D為T，則D為F,得C為F,得AB為F,如果A為F，則A為T，所以AB為T。 如果B為F，則B為T，所以AB 為T。 (AB)C)D(CD) AB,(AB)C為T,CD為T,68,方法3.假設(shè)后件為假，推出前件也為假。 例如,求證： (AB)C)D(CD) AB 證明:假設(shè)后件AB為F,則A與B均為T。 1.如果C為F，則(AB)C為F，所以前件 (AB)C)D(CD) 為F 2.如果C為T，則若D為T，則D為F，所以 前件(AB)C)D(CD) 為假 若D為F，則CD為F，所以 前件(AB)C)D(CD) 為假。 (AB)C)D(CD) AB,69,3.重要的重言蘊涵式(如教材第43頁所示) I1.PQP I2. PQQ I3. PPQ I4. QPQ I5. PPQ I6. QPQ I7. (PQ)P I8. (PQ)Q I9. P,Q PQ I10. P(PQ)Q I11. P(PQ)Q I12. Q(PQ)P I13. (PQ)(QR)PR I14.(PQ)(PR)(QR)R I15. AB (AC)(BC) I16. AB (AC)(BC),上述公式的證明可以用假設(shè)前件為T，推出后件也為T的方法證明。,70,4. 性質(zhì) 1).自反性：對任何命題公式A，有AA 2).傳遞性：若AB且BC，則AC 3).反對稱性：若AB且BA，則AB 符號“”表示“等價”。 本節(jié)重點掌握：永真式及永真蘊涵式的定義、證明方法、以及常用的公式。 作業(yè)：第23頁: (2) b) 、(6)、(8) e),71,1-5 等價公式,1. 例子, 看下面三個公式的真值表 P Q PQ PQ QP F F T T T F T T T T T F F F F T T T T T 從真值表可以看出，不論對P、Q作何指派，都使得PQ、PQ和QP的真值相同，表明它們之間彼此等價。,72,2. 定義：A、B是含有命題變元P1,P2, Pn的命題公式，如不論對P1, P2 , , Pn作任何指派，都使得A和B的真值相同，則稱之為A與B等價，記作AB。 顯然 PQPQQP 3. 重要的等價公式 對合律 PP 冪等律 PPP PPP 結(jié)合律 P(QR)(PQ)R P(QR)(PQ)R 交換律 PQQP PQQP,73,分配律 P(QR)(PQ)(PR) P(QR)(PQ)(PR) 吸收律 P(PQ)P P(PQ)P 德-摩根定律 (PQ)PQ (PQ)PQ 同一律 PFP PTP 零律 PTT PFF 互補律 PPT PPF PQPQ PQQP PQ (PQ)(QP) PQ (PQ)(PQ) PQ (PQ)(PQ ),74,將等價公式(前10個)與集合論的公式比較，請看集合公式： 對合律 AA A表示A的絕對補集 冪等律 AAA AAA 結(jié)合律 A(BC)(AB)C A(BC)(AB)C 交換律 ABBA ABBA 分配律 A(BC)(AB)(AC) A(BC)(AB)(AC) 吸收律 A(AB)A A(AB)A 德-摩根定律 (AB)AB (AB)AB 同一律 AA AEA E表示全集 零律 AEE A 否定律 AAE AA,75,4. 等價公式的證明方法 方法1：用列真值表。（不再舉例） 方法2：用公式的等價變換.(用置換定律) 置換定律:A是一個命題公式，X是A中的一部分且也是合式公式，如果XY，用Y代替A中的X得到公式B，則AB。 應(yīng)用置換定律以及前面列出的等價公式可以對給定公式進行等價變換。,76,例題1. 求證吸收律 P(PQ)P 證明 P(PQ) (PF)(PQ) (同一律) P(FQ) (分配律) PF (零律) P (同一律),77,例題2. 求證 (PQ)(PQ) P 證明 (PQ)(PQ) (PQ)(PQ) (公式E16) (PQ)(PQ) (摩根定律) (PQ)(PQ) (對合律) P(QQ) (分配律) PT (互補律) P (同一律) 公式E16 ： PQPQ,78,例題3.化簡 (PQ)(P(PQ) 解 原公式 (PQ)(PP)Q) (E16,結(jié)合) (PQ)(PQ) (對合律，冪等律) (PQ)(QP) (交換律) (PQ)Q)P (結(jié)合律) QP (吸收律) 公式E16 ： PQPQ 結(jié)合律: P(QR)(PQ)R ,P(QR)(PQ)R 交換律: PQQP , PQQP 吸收律 P(PQ)P P(PQ)P,79,5. 性質(zhì) 1).自反性：任何命題公式A，有AA。 2).對稱性：若AB，則BA 3).傳遞性：若AB且BC，則AC 4).如果A(P1,P2,Pn)B(P1,P2,Pn)，則 A(P1,P2,Pn)B(P1,P2,Pn) 例: 如果 A(P,Q)PQ B(P,Q)PQ 則: A(P,Q)B(P,Q) A(P,Q)PQ B(P, Q)PQ 可見: A(P,Q)B(P, Q),80,6.等價公式的對偶性 從前面列出的等價公式看出，有很多是成對出現(xiàn)的。這就是等價公式的對偶性。 對偶式：在一個只含有聯(lián)結(jié)詞 、的公式A中，將換成，換成，T換成F，F(xiàn)換成T，其余部分不變，得到另一個公式A*，稱A與A*互為對偶式。 例如: A A* P P QR QR (PT)Q (PF)Q,81,用對偶式求公式的否定 定理1-5.1 令A(yù)(P1,P2,Pn)是一個只含有聯(lián)結(jié)詞 、的命題公式，則 A(P1,P2,Pn)A*(P1,P2,Pn) 此定理可以反復(fù)地使用德-摩根定律得以證明。 下面我們驗證一下。 令 A(P,Q)PQ A*(P,Q)PQ A(P,Q)(PQ) A*(P, Q)PQ 可見 A(P,Q)A*(P,Q) 推論:A(P1,P2,Pn)A*(P1,P2,Pn),82,例如，利用上述求公式的否定公式求 (PQ)(PQ)R) (PQ)(PQ)R,83,對偶原理(定理1-5.2)： 令A(yù)(P1,P2,Pn) 、B(P1,P2,Pn)是只含有聯(lián)結(jié)詞、的命題公式， 如果: A(P1,P2,Pn)B(P1,P2,Pn) 則: A*(P1,P2,Pn)B*(P1,P2, Pn) 證明：因為 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) B*(P1,P2,Pn) 所以 A*(P1,P2,Pn)B*(P1, P2, Pn),84,下面我們驗證一下對偶原理： 本節(jié)要求掌握等價公式的證明方法及記憶公式。 作業(yè)：第19頁 (7) f) g) , (8) c),85,1-6.范式,范式就是命題公式形式的規(guī)范形式。這里約定在范式中 只含有聯(lián)結(jié)詞、和。 一.析取范式與合取范式 1.合取式與析取式 合取式：是用“”聯(lián)結(jié)命題變元或變元的否定構(gòu)成的式子。 如 P 、P 、PQ、PQR 析取式：是用“” 聯(lián)結(jié)命題變元或變元的否定構(gòu)成的式子。 如 P 、P 、PQ、PQR 注: PPP PPP P是合(析)取式.,86,2.析取范式 公式A如果寫成如下形式： A1A2.An (n1) 其中每個Ai (i=1,2,n)是合取式，稱之為A的析取范式。 3.合取范式 公式A如果寫成如下形式： A1A2.An (n1) 其中每個Ai (i=1,2,n)是析取式，稱之為A的合取范式。 例如，PQ 的析取范式與合取范式： PQ (PQ)(PQ)-析取范式 PQ (PQ)(PQ)-合取范式,87,4.析取范式與合取范式的寫法 先用相應(yīng)的公式去掉和。 公式E16 PQPQ 公式E21 PQ (PQ)(PQ) 公式E20 PQ (PQ)(QP) 再用E16 PQ (PQ)(PQ) 用公式的否定公式或摩根定律將后移到命題變元前 A(P1,P2,Pn)A*(P1,P2,Pn) 德-摩根定律： (PQ)PQ (PQ)PQ 用分配律、冪等律等公式進行整理，使之成為所要求的形式。,88,例如，求(PQ)R的析取范式與合取范式 (PQ)R (PQ)R 公式E16：PQPQ (PQ)(PQ)R (PQ)(PQ)R -析取范式 (PQ)R (PQ)R 公式E16：PQPQ (PQ)(PQ)R E21：PQ (PQ)(PQ) (PQ)(PQ)R (PQR)(PQR) -合取范式,89,二.主析取范式與主合取范式 一個公式的析取范式與合取范式的形式是不唯一的。下面定義形式唯一的主析取范式與主合取范式。 主析取范式 1.小項 定義：在一個有n個命題變元的合取式中，每個變元必出現(xiàn)且僅出現(xiàn)一次，稱這個合取式是個小項。 例如，有兩個變元的小項： PQ、PQ、 PQ、 PQ,90,小項的性質(zhì) a).有n個變元，則有2n個小項。 b).每一組指派有且只有一個小項為T。 為了記憶方便，可將各組指派對應(yīng)的為T的小項 分別記作m0,m1,m2,m2n-1 上例中 m0PQ m1PQ m2PQ m3PQ,91,2.主析取范式定義 析取范式 A1A2.An, , 其中每個Ai (i=1,2,n)都是小項，稱之為主析取范式。 3.主析取范式的寫法 方法：列真值表 列出給定公式的真值表。 找出真值表中每個“T”對應(yīng)的小項。 (如何根據(jù)一組指派寫對應(yīng)的為“T”的項： 如果變元P被指派為T，P在小項中以P形式出現(xiàn)；如變元P被指派為F,P在小項中以P形式出現(xiàn)(要保證該小項為T)。 用“”聯(lián)結(jié)上述小項，即可。,92,例如，求 PQ和PQ的主析取范式 P Q PQ PQ F F T T F T T F T F F F T T T T PQ m0m1m3 (PQ)(PQ)(PQ) PQm0m3 (PQ)(PQ) 思考題:永真式的主析取范式是什么樣 ？,93,方法：用公式的等價變換 先寫出給定公式的析取范式 A1A2.An 。 為使每個Ai都變成小項，對缺少變元的Ai補全變元， 比如，缺變元R，就用聯(lián)結(jié)永真式(RR)形式補R。 用分配律等公式加以整理。 PQPQ (P(QQ)(P P) Q) (PQ)(PQ)(PQ)(PQ) (PQ)(PQ)(PQ),94,主合取范式 1.大項 定義:在有n個命題變元的析取式中，每個變元必出現(xiàn)且僅出現(xiàn)一次,稱之為大項。 例如，有兩個變元的大項及其真值表：,95,大項的性質(zhì) a).有n個變元，則有2n個大項。 b).每一組指派有且只有一個大項為F。 將各組指派對應(yīng)的為F的大項分別記作M0,M1,M2,M2n-1 。 上例中， M0 PQ M1 PQ M2 PQ M3 PQ,96,2.主合取范式定義 合取范式 A1A2. An, , 其中每個Ai (i=1,2,n)都是大項，稱之為主合取范式。 3.主合取范式的寫法 方法：列真值表 列出給定公式的真值表。 找出真值表中每個“F”對應(yīng)的大項。 如何根據(jù)一組指派寫對應(yīng)的為“F”的大項： 如果變元P被指派為F，P在大項中以P形式出現(xiàn)； 如變元P被指派為T，P在大項中以P形式出現(xiàn)(確保該大項為F)。 用“”聯(lián)結(jié)上述大項，即可。,97,例如,求 PQ 和 PQ 的主合取范式 P Q PQ PQ F F T T F T T F T F F F T T T T PQ M2 PQ