命題邏輯的基本概念.ppt

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