《命題邏輯的基本概念.ppt》由會員分享，可在線閱讀，更多相關《命題邏輯的基本概念.ppt（55頁珍藏版）》請在裝配圖網上搜索。

1 鳴謝黃林鵬教授 2 第1章命題邏輯的基本概念 命題邏輯研究的是命題的推理演算 命題邏輯的基本概念命題聯(lián)結詞合式公式 重言式自然語句的形式化 3 命題邏輯的基本概念 命題是一個非真即假 不可兼 的陳述句 有兩層意思 首先命題是一個陳述句 而命令句 疑問句和感嘆句都不是命題 其次是說這個陳述句所表達的內容可決定是真還是假 而且不是真的就是假的 不能不真又不假 也不能又真又假 凡與事實相符的陳述句為真浯句 而與事實不符的陳述句為假語句 這說是說 一個命題具有兩種可能的取值 又稱真值 為真或為假 并且只能取其一 通常用大寫字母T表示真值為真 用F表示真值為假 因為只有兩種取值 所以這樣的命題邏輯稱為二值邏輯 4 舉例說明 1 雪是白的 命題 2 雪是黑的 命題 3 好大的雪啊 不是陳述句 不是命題 4 一個偶數(shù)可表示成兩個素數(shù)之和 是命題 或為真或為假 只不過當今尚不知其是真命題還是假命題 5 1 10l 110 這是一個數(shù)學表達式 相當于一個陳述句 可以敘述為 1加101等于110 這個句子所表達的內容在十進制范圍中真值為假 而在二進制范圍中真值為真 可見 這個命題的真值與所討論問題的范圍有關 5 命題變項 為了對命題作邏輯演算 采用數(shù)學手法將命題符號化 形式化 是十分重要的 約定用大寫字母表示命題 如以戶表示 雪是白的 Q表示 北京是中國的首都 等 當P表示任一命題時 P就稱為命題變項 變元 命題與命題變項含義是不同的 命題指具體的陳述句 是有確定的真值 而命題變項的真值不定 只當將某個具體命題代入命題變項時 命題變項化為命題 方可確定其真值 命題與命題變項像初等數(shù)學中常量與變量的關系一樣 如5是一個常量 是一個確定的數(shù)字 而x是一個變量 賦給它一個什么值它就代表什么值 即x的值是不定的 6 簡單命題和復合命題 簡單命題又稱原子命題 它是不包含任何的與 或 非一類聯(lián)結詞的命題 如1 1 1中所舉的命題例子都是簡單命題 這樣的命題不可再分割 如再分割就不是命題了 而像命題 雪是白的而且l l 2 就不是簡單命題 它可以分割為 雪是白的 以及 1十1 2 兩個簡單命題 聯(lián)結詞是 而且 在簡單命題中 盡管常有主語和謂語 但我們不去加以分割 是將簡單命題作為一個不可分的整體來看待 進而作命題演算 在謂詞邏輯里 才對命題中的主謂結構進行深入分析 7 復合命題 把一個或幾個簡單命題用聯(lián)結詞 如與 或 非 聯(lián)結所構成的新的命題稱為復合命題 復合命題自然也是陳述句 其真值依賴于構成該復合命題的各簡單命題的真值以及聯(lián)結詞 從而復合命題有確定的真值 如 張三學英語和李四學日語 就是一個復合命題 由簡單命題 張三學英語 李四學日語 經聯(lián)結詞 和 聯(lián)結而成 這兩個簡單命題真值均為真時 該復合命題方為真 命題邏輯所討論的是多個命題聯(lián)結而成的復合命題的規(guī)律性 8 內容 形式 在數(shù)理邏輯里 僅僅把命題看成是一個可取真或可取假的陳述句 所關心的并不是這些具體的陳述句的真值究竟為什么或在什么環(huán)境下是真還是假 這是有關學科本身研究的問題 而邏輯關心的僅是命題可以被賦予真或假這樣的可能性 以及規(guī)定了真值后怎樣與其他命題發(fā)生聯(lián)系 9 命題聯(lián)結詞及真值表 聯(lián)結詞可將命題聯(lián)結起來構成復雜的命題 命題邏輯聯(lián)結詞的引入是十分重要的 其作用相當于初等數(shù)學里在實數(shù)集上定義的十 一 等運算符 通過聯(lián)結詞便可定義新的命題 從而使命題邏輯的內容變得豐富起來 復合命題的真值可由組成它的簡單命題的真值所確定 值得注意的是邏輯聯(lián)結詞與日常自然用語中的有關聯(lián)結詞的共同點和不同點 10 常用的邏輯聯(lián)結詞 否定詞 是個一元聯(lián)結詞 亦稱否定符號 一個命題P加上否定詞就形成了一個新的命題 記作 P 這個新命題是命題的否定 讀作非P否定詞的真值規(guī)定如下 若命題P的真值為真 那么 P的真值就為假 若P的真值為假 那么 P的真值就為真 P與P間的真值關系 常常使用稱作真值表的一種表格來表示 11 P的定義 真值表 真值表表明了 P的真值如何依賴于P的真值 真值表描述了命題之間的真值關系 很直觀 真值表是命題邏輯里研究真值關系的重要工具 12 例1 昨天張三去看球賽了 該命題以P表示 于是 昨天張三沒有去看球賽 該新命題便可用 P表示 若昨天張三去看球賽了 命題P是真的 那么新命題 P必然是假的 反之 若命題P是假的 那么 P就是真的 13 例2 Q 今天是星期三 Q 今天不是星期三 然而 Q不能理解為 今天是星期四 因為 今天是星期三 的否定 并不一定必是星期四 還可能是星期五 星期六 14 合取詞 合取詞 是個二元命題聯(lián)結詞 亦稱合取符號 將兩個命題P Q聯(lián)結起來 構成一個新的命題P Q 讀作P Q的合取 也可讀作P與Q 這個新命題的真值與構成它的命題P Q的真值間的關系 由合取詞真值表來規(guī)定 15 合取詞真值表 只有當兩個命題變項P T Q T時方有P Q T 而P Q只要有一為F 則P Q F P Q可用來表示日常用語P與Q 或P并且Q 16 例3 P 教室里有10名女同學 Q 教室里有15名男同學 不難看出 命題P Q 教室里有10名女同學與15名男同學 17 例4 A 今天下雨了 B 教室里有100張桌子 可知A B就是命題 今天下雨了并且教室里有100張桌子 18 注意 日常自然用語里的聯(lián)結詞 和 與 并且 一般是表示兩種同類有關事物的并列關系 而在邏輯語言中僅考慮命題與命題之間的形式關系并不顧及日常自然用語中是否有此說法 這樣 同 與 并且 又不能等同視之 日常自然用語中說 這臺機器質量很好 但是很貴 這句話的含義是說同一臺機器質量很好而且很貴 若用P表示 這臺機器質量很好 用Q表示 這臺機器很貴 那么這句話的邏輯表示就是P Q 盡管這句話里出現(xiàn)的聯(lián)結詞是 但是 總之 合取詞有 與 并且 的含義 邏輯聯(lián)結詞是自然用語中聯(lián)結詞的抽象 兩者并不等同 這是需注意的 19 析取詞 析取詞 是個二元命題聯(lián)結詞 將兩個命題P Q聯(lián)結起來 構成一個新的命題P Q 讀作P Q的析取 也讀作P或Q 這個新命題的真值與構成它的命題P Q的真值間的關系 20 析取詞真值表 當P Q有一取值為T時 P Q便為T 僅當P Q均取F值時 P Q方為F 這就是析取詞的定義 P Q可用來表示自然用語P或Q 21 例 例5 P 今天刮風 Q 今天下雨 命題 今天刮風或者下雨 便可由P Q來描述了 例6 A 2小于3 B 雪是黑的 A B就是命題 2小于3或者雪是黑的 由于2小于3是真的 所以A B必取值為真 盡管 雪是黑的 這命題取假 22 蘊涵詞 蘊涵詞 也是個二元命題聯(lián)結詞 將兩個命題P Q聯(lián)結起來 構成一個新的命題P Q 讀作如果P則Q 或讀作P蘊涵Q 如果P那么Q 其中P稱前件 前項 條件 Q稱后件 后項 結論 規(guī)定只有當P為T而Q為F時 P Q F 而P F Q任意 或P T Q T時P Q均取值為T 23 真值表 P Q T下 若P T必有Q T 而不會出現(xiàn)Q F 這表明P Q體現(xiàn)了P是Q成立的充分條件 P Q T下 若P F可有Q T 這表明P Q體現(xiàn)了P不必是Q成立的必要條件 24 因果關系 引入 的目的是希望用來描述命題間的推理 表示因果關系 使用P Q能描述推理 即P Q為真時 只要P為真必有Q真 而不能出現(xiàn)P真而Q假就夠了 至于P為假時 Q取真取假 并不違背P為真時Q必真 從而仍可規(guī)定P為假時 P Q取真 當P F時對P Q真值的不同定義方式將給推理的討論帶來不同的表示形式 也是允許的 25 P Q P Q 在P Q的所有取值下 P Q同 P Q都有相同的真值 P Q P Q 真值相同的等值命題以等號聯(lián)結 這也說明 可由 來表示 從邏輯上看 如果P則Q 同 非P或Q 是等同的兩個命題 26 如果 那么 蘊涵詞 與自然用語 如果 那么 有一致的一面 可表示因果關系 然而P Q是無關的命題時 邏輯上允許討論P Q 并且P F則P Q T 這在自然用語中是不大使用的 27 例7 P n 3 n為整數(shù) Q n2 9命題P Q表示 如果n 3那么n2 9 分析P Q的真值 1 P Q T 這時如n 4 3 有n2 16 9 這符合事實P Q T 正是我們所期望的可以P Q表示P Q間的因果關系 這時規(guī)定P T是自然的 2 P T Q F 如n 3而n29由于前提條件n 3不成立 而n2 9成立與否并不重要 都不違反對自然用語 如果n 3那么n2 9 成立的肯定 于是P F時可規(guī)定P Q T 當然在肯定了1 2的情況下 對P F時P Q的值另作規(guī)定也是可以的 同樣不違反自然語句 如果 那么 可以用P Q來描述 總之 對P Q的這種說明是可接受的 但也不是說僅只有這樣的解釋才是合理的 28 例8 P 2 2 5Q 雪是黑的P Q就是命題 如果2 2 5 那么雪是黑的 從蘊涵詞的定義看 由2 2 5是不成立的或說P取F值 不管Q取真取假都有P Q T 29 雙條件詞 30 P Q Q P P Q 只有當兩個命題P Q的真值相同或說P Q時 P Q的真值方為T 而當P Q的真值不同時 P Q F 若建立 P Q Q P 的真值表 就可發(fā)現(xiàn) P Q Q P 和P Q有相同的真值 于是 P Q Q P P Q 31 例9 P ABC是等腰三角形Q ABC中有兩個角相等命題P Q就是 ABC是等腰三角形當且僅當 ABC中有兩個角相等 顯然就這個例子而言P Q T 32 總結 定義的五個聯(lián)結詞是數(shù)理邏輯中最基本最常用的邏輯運算 一元二元聯(lián)結詞還有多個 此外還有三元以至更多元的聯(lián)結詞 因其極少使用 況且又都可由這五個基本聯(lián)結詞表示出來 所以無需一一定義了 聯(lián)結詞是由命題定義新命題的基本方法 命題邏輯的許多問題都可化成是計算復合命題的真假值問題 真值表方法是極為有力的工具 是應十分重視和經常使用的 33 總結 由聯(lián)結詞構成新命題的真值表中 對僅由兩個變元P Q構成的新命題A而言 每個變元有T F兩種取值 從而P Q共有四種可能的取值 對應于真值表中的四行 每一行下命題A都有確定的真值 對P Q的每組真值組合 如P T Q F 或說真值指派 都稱作命題A的一個解釋 一般地說 當命題A依賴于命題P1 Pn到A的真值表就有2n行 每一行對應著P1 Pn的每組真值都稱作命題A的一個解釋 A有2n個解釋 命題的解釋用符號I表示 34 總結 由于數(shù)理邏輯是采用數(shù)學的符號化的方法來研究命題間最一般的真值規(guī)律的 而不涉及判斷一個命題本身如何取真取假 拋開命題的具體含義 而是抽象形式地討論邏輯關系 這就導致了數(shù)理邏輯中所討論的命題與自然用語的差異 聯(lián)結詞 同構成計算機的與門 或門和非門電路是相對應的 從而命題邏輯是計算機硬件電路的表示 分析和設計的重要工具 也正是數(shù)理邏輯應用于實際特別是應用于計算機學科推動了數(shù)理邏輯的發(fā)展 35 不同的符號 五個聯(lián)結詞在不同的書中會采用不同的符號 如 P可以以 P表示 P Q以P Q表示 P Q以P Q表示 P Q以P Q表示 P Q以P Q表示 閱讀時應注意不同的表示方式 36 1 3合式公式 命題公式是命題邏輯討論的對象 而由命題變項使用聯(lián)結詞可構成任意多的復合命題 如 P Q P Q R P Q等 問題是它們是否都有意義呢 只有一個聯(lián)結詞的命題 P P Q P Q當然是有意義的 由兩個聯(lián)結詞構成的命題P Q R至少意義不明確 是先作P Q再對R做 還是先作Q R再對P作 呢 P Q也有同樣的問題 解決運算次序是容易的 可象初等代數(shù)那樣使用括號的辦法 在邏輯運算中也常使用圓括號來區(qū)分運算的先后次序 這樣由命題變項 命題聯(lián)結詞和圓括號便組成了命題邏輯的全部符號 進一步的問題是建立一個一般的原則以便生成所有的合法的命題公式 并能識別什么樣的符號串是合法的 有意義的 37 合式公式 簡記為Wff 的定義 1 簡單命題是合式公式 2 如果A是合式公式 那么 A也是合式公式 3 如果A B是合式公式 那么 A B A B A B 和 A B 是合式公式 4 當且僅當經過有限次地使用1 2 3所組成的符號串才是合式公式 這個定義給出了建立合式公式的一般原則 也給出了識別一個符號串是否是合式公式的原則 這是遞歸 歸納 的定義 在定義中使用了所要定義的概念 如在2和3中都出現(xiàn)了所要定義的合式公式字樣 其次是定義中規(guī)定了初始情形 如1中指明了已知的簡單命題是合式公式 條件4說明了哪些不是合式公式 而1 2和3說明不了這一點 38 判斷一個公式是否為合式公式 依定義 若判斷一個公式是否為合式公式 必然要層層解脫回歸到簡單命題方可判定 P Q P P Q P Q Q R P R 是合式公式 而 P Q P Q Q P Q都不是合式公式 39 約定 為了減少圓括號的數(shù)量 可以引入一些約定 如規(guī)定聯(lián)結詞優(yōu)先級的辦法 可按 的排列次序安排優(yōu)先的級別 多個同一聯(lián)結詞按從左到右的優(yōu)先次序 這樣 在書寫合式公式時 可以省去部分或全部圓括號 通常采用省略一部分又保留一部分括號的辦法 這樣選擇就給公式的閱讀帶來方便 如 P Q R 可寫成P Q R 或P Q R P P R 可寫成P P R 命題演算中只討論合式公式 將合式公式就稱作公式 40 1 4重言式 可滿足式 矛盾式 如果一個公式 對于任一解釋I其值都為真 就稱為重言式 永真式 如P P是一個重言式 由 和 聯(lián)結的重言式仍是重言式 一個公式 如在某個解釋I0下值為真 則稱它是可滿足的 如P Q 當取I0 T F 即P T Q F時便有P Q T 所以是可滿足的 重言式當然是可滿足的 矛盾式 永假式或不可滿足式 如果一個公式 對于任一解釋I值都是假的 便稱是矛盾式 如P P就是矛盾式 41 三類公式間關系 1 公式A永真 當且僅當 永假 2 公式A可滿足 當且僅當 A非永真 3 不是可滿足的公式必永假 4 不是永假的公式必可滿足 42 1 4 2代入規(guī)則 A是一個公式 對A使用代入規(guī)則得公式B 若A是重言式 則B也是重言式 為保證重言式經代入規(guī)則仍得到保持 要求 43 1 公式中被代換的只能是命題變元 原子命題 而不能是復合命題 如可用 R S 來代換某公式中的P 而不能反過來將公式中的 R S 以P代之 這一要求可以以代數(shù)的例子來說明 如對 a b 2 a2 2ab b2可以a cd代入 仍會保持等式成立 而若將a b以cd代入 結果左端得 cd 2 而右端無法代入cd 不能保持等式成立了 44 2 對公式中某命題變項施以代入 必須對該公式中出現(xiàn)的所有同一命題變項代換以同一公式 如A P P P以 Q代之得B Q Q仍是重言式 若將 P以Q代替得B P Q不是重言式了 45 使用代入規(guī)則證明重言式 例1 判斷 R S R S 為重言式 因P P為重言式 P以 R S 代入得 R S R S 依據代入規(guī)則 這公式必是重言式 例2 判斷 R S R S P Q P Q 為重言式 不難驗證 A A B B是重言式 A以R S代入 B以P Q代入得 R S R S P Q P Q 是重言式 46 1 5命題形式化 一些推理問題的描述 常是以自然語句來表示的 需首先把自然語句形式化成邏輯語言 即以符號表示的邏輯公式 然后根據邏輯演算規(guī)律進行推理演算 先要引入一些命題符號P Q 用來表示自然語句中所出現(xiàn)的簡單命題 進而依自然語句通過聯(lián)結詞將這些命題符號聯(lián)結起來 以形成表示自然語句的合式公式 47 1 5 1簡單自然語句的形式化 1 北京不是村莊 令P表示 北京是村莊 于是1可表示為 P 2 李明既聰明又用功 令P表示 李明聰明 Q表示 李明用功 于是2可表示為P Q 3 2是有理數(shù)的話 2 2也是有理數(shù) 令P表示 2是有理數(shù) Q表示 2 2是有理數(shù) 于是3可表示為P Q 48 1 5 2較復雜自然語句的形式化 需注意的是邏輯聯(lián)結詞是從自然語句中提煉抽象出來的 它僅保留了邏輯內容 而把自然語句所表達的主觀因素 心理因素以及文藝修辭方面的因素全部撇開了 從而命題聯(lián)結詞只表達了自然語句的一種客觀性質 又由于自然語句本身并不嚴謹 常有二義性 自然會出現(xiàn)同一自然語句的不等價的邏輯描述 其根由在于人們對同一自然語句的不同理解 49 例1 張三與李四是表兄弟 這是普通的自然用語 它是一個命題 令以R表示 若形式地規(guī)定 P 張三是表兄弟 Q 李四是表兄弟 那么R P Q 顯然 這樣的形式化是錯誤的 原因很簡單 張三是表兄弟 李四是表兄弟 都不是命題 實際上 張三與李四是表兄弟 才是一個命題 而且是一個簡單命題 這例子說明自然語句中的 與 不一定都能用合取詞來表達 50 例2 張三或李四都能做這件事 這句話中的 或 不一定就用析取詞來表示 應允許有的人把這命題的內容理解為 張三能做這件事而且李四也能做這件事 這樣 這句話便可以P Q的形式表示了 51 例3 給了三個命題 A 今晚我在家里看電視 B 今晚我去體育場看球賽 C 今晚我在家里看電視或去體育場看球賽 問題是C與A B是否表達的是同一命題呢 52 否 因為C同A B的真值關系為 53 異或 不可兼或 這表的前三行很容易理解 而第四行是說今晚我在家看電視 又去體育場看球賽 顯然對同一個人來說這是不可能的 從而這時C的真值為F 這就說明了C與A B邏輯上是并不相等的 即C中出現(xiàn)的 或 不能以 來表示 C同A B的邏輯關系 常稱為異或 不可兼或 以表示 有C AB不難驗證C A B A B 54 例4 今天我上班 除非今天我病了 以P表示今天我病了 Q表示今天我上班 例4是個因果關系 意思是如果今天我不病 那么我上班 所以可描述成 P Q 55 作業(yè) P121 2 4 6 8 4 2 4 6 5 2 4 6 8 6 2