命題邏輯的基本概念ppt課件

1、命題邏輯的根本概念Lu Chaojun, SJTU 2 2主要內(nèi)容 命題 命題結(jié)合詞 合式公式 重言式Lu Chaojun, SJTU 3 3什么是命題? 命題命題(proposition):是一個(gè)非真即假的陳說句是一個(gè)非真即假的陳說句. 是陳說句是陳說句,而非命令句、疑問句或感慨句等而非命令句、疑問句或感慨句等. 表達(dá)的內(nèi)容可判別真假表達(dá)的內(nèi)容可判別真假,而且非真即假而且非真即假. 真假的斷定真假的斷定:與現(xiàn)實(shí)能否相符與現(xiàn)實(shí)能否相符. 不能不真又不假，也不能又真又假不能不真又不假，也不能又真又假. 真值真值(truth value):命題具有兩種能夠的取值命題具有兩種能夠的取值,即即真真(t

2、rue)和假和假(false). 常寫做常寫做T和和F. 稱為二值邏輯稱為二值邏輯.Lu Chaojun, SJTU 4 4例子:命題(1)雪是白的.是命題,真值為T.(2)雪是黑的.是命題,真值為F.(3)好大的雪啊!不是命題(4)偶數(shù)可表示成兩個(gè)素?cái)?shù)之和.(Goldbach猜測) 是命題,目前不知其真假.(5)1+10l110.相當(dāng)于陳說句“1加101等于110. 在十進(jìn)制范圍中真值為F,在二進(jìn)制范圍中真值為T.并不意味著同一命題有兩個(gè)真值!在不同數(shù)制中是不同的命題.Lu Chaojun, SJTU 5 5命題的符號(hào)化表示 為了對(duì)命題進(jìn)展邏輯演算,利用數(shù)學(xué)手段將命題符號(hào)化(方式化). 用字

3、母表示命題 命題常項(xiàng):例如用P表示“雪是白的. 命題變項(xiàng):例如用P表示恣意命題. 命題vs.命題變項(xiàng) 命題指詳細(xì)的陳說句,有確定的真值 命題變項(xiàng)不特指某個(gè)命題,真值不確定 將某個(gè)命題代入命題變項(xiàng)時(shí),命題變項(xiàng)方可確定真值. 但在命題邏輯演算中,兩者處置原那么是一樣的,可不做區(qū)分.Lu Chaojun, SJTU 6 6簡單命題和復(fù)合命題 簡單命題簡單命題: :簡單句簡單句, ,不包含任何不包含任何“并且并且, , “或者或者之類的結(jié)合詞之類的結(jié)合詞. . 例如例如: :雪是白的雪是白的. . 又叫原子命題又叫原子命題: :不可分割不可分割. . 假設(shè)按主語謂語分析假設(shè)按主語謂語分析, ,那么是謂

4、詞邏輯的做法那么是謂詞邏輯的做法. . 復(fù)合命題復(fù)合命題: :成分命題經(jīng)結(jié)合詞結(jié)合而成成分命題經(jīng)結(jié)合詞結(jié)合而成. . 例如例如: :張三是教師并且雪是白的張三是教師并且雪是白的. . 又叫分子命題又叫分子命題: :可以分割可以分割. . 結(jié)合詞例子結(jié)合詞例子: :并且并且, ,或者或者, ,非非, ,假設(shè)假設(shè)那么那么Lu Chaojun, SJTU 7 7復(fù)合命題的真值 復(fù)合命題的真值是成分命題的真值的函數(shù). 當(dāng)成分命題被賦予任一真值組合時(shí),結(jié)合詞完全決議了復(fù)合命題的真值. 例如: “張三學(xué)英語且李四學(xué)日語由簡單命題“張三學(xué)英語, “李四學(xué)日語經(jīng)結(jié)合詞“且結(jié)合而成.當(dāng)這兩個(gè)簡單命題真值均為T時(shí)

5、,該復(fù)合命題真值才為T.Lu Chaojun, SJTU 8 8命題內(nèi)容vs.方式 方式邏輯并不關(guān)懷命題內(nèi)容為真為假的條件和環(huán)境等,只關(guān)懷命題有真假的能夠性,以及復(fù)合命題的真假規(guī)律性. 風(fēng)馬牛不相及的內(nèi)容也可以組成復(fù)合命題. 例如:張三學(xué)英語或者熊貓是珍稀動(dòng)物.Lu Chaojun, SJTU 9 9命題結(jié)合詞 命題結(jié)合詞命題結(jié)合詞(propositional (propositional connective):connective):將命題結(jié)合起來構(gòu)成新命將命題結(jié)合起來構(gòu)成新命題題. . 將命題視為運(yùn)算對(duì)象將命題視為運(yùn)算對(duì)象, , 命題結(jié)合詞視為命題結(jié)合詞視為運(yùn)算符運(yùn)算符, ,從而構(gòu)成運(yùn)算

6、表達(dá)式從而構(gòu)成運(yùn)算表達(dá)式. . 比較比較: :初等代數(shù)中運(yùn)算對(duì)象是初等代數(shù)中運(yùn)算對(duì)象是a,b,ca,b,c等等, ,運(yùn)運(yùn)算符有算符有 等等 常用命題結(jié)合詞常用命題結(jié)合詞: : , , , , ,Lu Chaojun, SJTU 1010否認(rèn)詞“ 否認(rèn)否認(rèn)(negation):(negation):命題命題P P加上否認(rèn)詞就構(gòu)加上否認(rèn)詞就構(gòu)成一個(gè)新命題成一個(gè)新命題P,P,表達(dá)的是對(duì)表達(dá)的是對(duì)P P的否認(rèn)的否認(rèn). . 讀作讀作: :非非P P的定義可用真值關(guān)系準(zhǔn)確給出的定義可用真值關(guān)系準(zhǔn)確給出: :P P為真為真 iff P iff P為假為假. . 這種真值關(guān)系經(jīng)常用真值表這種真值關(guān)系經(jīng)常用真值

7、表(truth (truth table)table)來表示來表示. .Lu Chaojun, SJTU 1111的真值表 真值表描畫了P的真值如何依賴于P的真值. 當(dāng)命題變項(xiàng)不多時(shí),真值表是研討真值關(guān)系的重要工具.PPTFFTLu Chaojun, SJTU 1212的例子1.令P:張三去看球賽了. 那么P:張三沒有去看球賽. 2.令Q:今天是星期三. 那么Q:今天不是星期三.Lu Chaojun, SJTU 1313合取詞“ 合取合取(conjunction):(conjunction):結(jié)合兩個(gè)命題結(jié)合兩個(gè)命題P P和和Q Q構(gòu)成一個(gè)新命題構(gòu)成一個(gè)新命題P PQ,Q,表達(dá)表達(dá)“P P并且

8、并且Q Q. . 讀作讀作:P:P與與Q, PQ, P、Q Q的合取的合取. . 的定義可用真值關(guān)系準(zhǔn)確給出的定義可用真值關(guān)系準(zhǔn)確給出: : P PQ Q為真為真 iff P iff P和和Q Q都為真都為真Lu Chaojun, SJTU 1414的真值表 的真值表描畫了PQ的真值如何依賴于P和Q的真值.PQP QFFFFTFTFFTTTLu Chaojun, SJTU 1515的例子1.令P:教室里有10名女同窗. Q:教室里有15名男同窗. 那么P Q:教室里有10名女同窗并且有15名男同窗.2.令A(yù):今天下雨了. B:教室里有100張桌子. 那么A B:今天下雨了并且教室里有100張桌

9、子.Lu Chaojun, SJTU 1616與日常用語的差別 日常用語里的“和、“與、“并且普通表示同類事物的并列;而方式邏輯中的只關(guān)懷命題與命題之間的真值關(guān)系,并不思索兩命題能否有意義上的聯(lián)絡(luò). 例如:“張三18歲并且今天天氣晴朗 日常用語中的某些意義用表達(dá)不出來 例如:“這臺(tái)機(jī)器質(zhì)量很好,但是很貴用表達(dá)時(shí)并無“ 轉(zhuǎn)機(jī)的語氣.Lu Chaojun, SJTU 1717析取詞“ 析取析取(disjunction):(disjunction):結(jié)合兩個(gè)命題結(jié)合兩個(gè)命題P P、Q Q構(gòu)成新命題構(gòu)成新命題P P Q, Q,表達(dá)表達(dá)“P P或者或者Q Q. . 讀作讀作: P: P或或Q, PQ,

10、P、Q Q的析取的析取. . 的定義可用真值關(guān)系準(zhǔn)確給出的定義可用真值關(guān)系準(zhǔn)確給出: : P PQ Q為假為假 iff P iff P和和Q Q都為假都為假Lu Chaojun, SJTU 1818的真值表 的真值表描畫了PQ的真值如何依賴于P和Q的真值.PQP QFFFFTTTFTTTTLu Chaojun, SJTU 19的例子1.令P:今天刮風(fēng) Q:今天下雨 那么PQ:今天刮風(fēng)或者下雨.2.令A(yù):2小于3 B:雪是黑的 那么AB: 2小于3或者雪是黑的由于2小于3是真的,所以AB必為真,雖然“雪是黑的為假.19Lu Chaojun, SJTU 20與日常用語的差別 日常用語中的“或往往具

11、有“不可兼的涵義,即二選一. 例如:他去或者我去. 也可定義“不可兼或,也叫“異或.20Lu Chaojun, SJTU 21蘊(yùn)涵詞“ 蘊(yùn)涵蘊(yùn)涵(implication):(implication):將兩個(gè)命題將兩個(gè)命題P P、Q Q結(jié)結(jié)合起來合起來, ,構(gòu)成一個(gè)新的命題構(gòu)成一個(gè)新的命題P PQ,Q,表達(dá)表達(dá)“假假設(shè)設(shè)P P成立那么成立那么Q Q成立成立. . 讀作讀作:P:P蘊(yùn)涵蘊(yùn)涵Q Q P P稱前件稱前件(antecedent),Q(antecedent),Q稱后件稱后件(consequent). (consequent). 的定義可用真值關(guān)系準(zhǔn)確給出的定義可用真值關(guān)系準(zhǔn)確給出: : P

12、 PQ Q為假為假 iff P iff P真而真而Q Q假假21Lu Chaojun, SJTU 2222的真值表 的真值表描畫了PQ的真值如何依賴于P和Q的真值.PQPQFFTFTTTFFTTTLu Chaojun, SJTU 23與推理 的最重要用途是進(jìn)展命題間的推理. 假設(shè)知PQ為真,那么只需P為真,必能推知Q為真. 絕不能夠P真而Q假. 此即傳統(tǒng)邏輯所稱modus ponens推理規(guī)那么. 一定前件式,或稱分別規(guī)那么 PQ 假設(shè)P那么Q P P Q Q23Lu Chaojun, SJTU 24與日常用語的差別 稱為本質(zhì)蘊(yùn)涵(material implication),與日常用語“假設(shè)那

13、么有不同. 因果聯(lián)絡(luò)? 日常用語的“假設(shè)P那么Q僅用于P和Q有內(nèi)容上的因果聯(lián)絡(luò). 只反映P和Q的真值間的關(guān)系:不能P真而Q假,與命題內(nèi)容無關(guān). P為假時(shí),不論Q的真假,PQ都為真. 存在不同的蘊(yùn)涵定義.24Lu Chaojun, SJTU 25的例子 令P:224; P :225. Q:雪是白的; Q :雪是黑的.那么 P Q為真 P Q為真 P Q 為真 P Q 為假25Lu Chaojun, SJTU 26雙條件詞“ 雙條件雙條件/ /等價(jià)等價(jià)(biconditional (biconditional /equivalence):/equivalence):將兩個(gè)命題將兩個(gè)命題P P、Q

14、Q結(jié)合起結(jié)合起來來, ,構(gòu)成一個(gè)新的命題構(gòu)成一個(gè)新的命題P PQ,Q,表達(dá)表達(dá)“等價(jià)于等價(jià)于 “當(dāng)且僅當(dāng)?shù)犬?dāng)且僅當(dāng)?shù)? . 讀作讀作: P: P等價(jià)等價(jià)Q, PQ, P當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)Q Q 的定義可用真值關(guān)系準(zhǔn)確給的定義可用真值關(guān)系準(zhǔn)確給/ /出出: : P PQ Q為真為真 iff P iff P和和Q Q真值一樣真值一樣26Lu Chaojun, SJTU 2727的真值表 的真值表描畫了PQ的真值如何依賴于P和Q的真值. 驗(yàn)證: PQ和(PQ)(QP)真值表一樣PQPQFFTFTFTFFTTTLu Chaojun, SJTU 28的例子令P: ABC是等腰三角形. Q: ABC中有兩個(gè)

15、角相等. 那么PQ表達(dá)了“ABC是等腰三角形當(dāng)且僅當(dāng)ABC中有兩個(gè)角相等.就此例而言: PQ為真.假設(shè)把“等腰換成“直角,那么PQ為假.28Lu Chaojun, SJTU 29關(guān)于結(jié)合詞 結(jié)合詞是由命題定義新命題的根本方法. ,是最常用的. 其他符號(hào): , , +, , 還可定義其他結(jié)合詞,但既不常用,又都可由這五個(gè)結(jié)合詞表示出來. 現(xiàn)實(shí)上,只需兩個(gè)根本結(jié)合詞:,或者, 結(jié)合詞,對(duì)應(yīng)著數(shù)字電路的與門,或門和非門電路.可見命題邏輯(布爾邏輯)是數(shù)字電路分析和設(shè)計(jì)的實(shí)際根底和工具.29小結(jié) 數(shù)理邏輯的簡明歷史 命題 命題銜接詞 , , , , 真值表 每個(gè)命題可以看作取值為0,1的變量 命題銜接

16、詞可以看作定義在命題上的函數(shù) 真值表的各項(xiàng)就是函數(shù)值0,130Lu Chaojun, SJTU 31命題公式 在由命題變項(xiàng)經(jīng)過結(jié)合詞構(gòu)成復(fù)雜命題時(shí),如何才是有意義的命題? 例如: PQR.(意義明確嗎?) 定義(命題公式):(1)命題變元(原子命題)是命題公式.(2)假設(shè)、是公式,那么(), ( ), ( ), ( )和( )是命題公式.(3)命題公式僅限于此. 上面這種定義方式是方式系統(tǒng)常用的合式定義,所定義的公式稱為合式公式(well-formed formula,簡記為wff).311+2;2+4/5; 31+2;2+4/5; 3* *3+13+11+2-; 1-/31+2-; 1-/3

17、Lu Chaojun, SJTU 32判別符號(hào)串能否wff 根據(jù)公式的合式定義,層層歸約,直到原子命題即可判別. 例子 (PQ) (P(PQ)(PQ)(QR)(PR)(P) 這個(gè)公式是wff ?(PQ)(Q)(PQ32Lu Chaojun, SJTU 33簡寫商定 為了減少括號(hào)的數(shù)量,可以引入優(yōu)先級(jí)的商定. 例如按,的次序安排優(yōu)先級(jí). 一樣結(jié)合詞按從左到右的優(yōu)先次序. 例: (P(QR)可寫成P(QR),進(jìn)而寫成PQR. (P(PR)可寫成P(PR),但不能寫成PPR.33Lu Chaojun, SJTU 34無括號(hào)表示法 前面的wff定義采用結(jié)合詞中綴表示法,需求用括號(hào)區(qū)分運(yùn)算次序. 波蘭表

18、示法(前綴): A B 表示為 AB 逆波蘭表示法(后綴): A B 表示為 AB (逆)波蘭式無需括號(hào),便于計(jì)算機(jī)處置. 例: (P(QR) 波蘭式: PQR 逆波蘭式: PQR34Lu Chaojun, SJTU 35命題公式的真值(語義) 命題公式的真值由其成員命題的真值決議.常用真值表方法計(jì)算. 設(shè)公式由成分命題P1, , Pn結(jié)合而成. 對(duì)P1, , Pn的真值指派(assignment)決議了 的真值,稱為 的解釋(interpretation),可表示為真值表的一行: P1 Pn T F T 總共有2n個(gè)解釋,構(gòu)成的真值表(2n行).35Lu Chaojun, SJTU 36重言

19、式 假設(shè)公式在任一解釋I 下值都為T,就稱為重言式(或永真式,tautology). 例如: PP是重言式. 重言式由,結(jié)合所得公式仍是重言式. 重言式反映了邏輯規(guī)律. 假設(shè)公式在某個(gè)解釋I0下值為T,那么稱是可滿足的(satisfiable). 例如:PQ在I0 = (T, F)下值為T,所以是可滿足的. 假設(shè)公式在任一解釋I 下值都為F,就稱為矛盾式(永假式或不可滿足式,contradiction). 例如:P P36Lu Chaojun, SJTU 37三類公式間關(guān)系定理: (練習(xí))1. 永真 iff 永假.2. 可滿足 iff 非永真.3. 非永假 iff 可滿足.37Lu Chaoj

20、un, SJTU 38代入堅(jiān)持重言式 代入規(guī)那么代入規(guī)那么: :將公式將公式 中的命題變元中的命題變元P P的的一切出現(xiàn)都交換成公式一切出現(xiàn)都交換成公式. . 記為記為 P/P/ . . 針對(duì)命題變項(xiàng)代入針對(duì)命題變項(xiàng)代入. . 處處代入處處代入. . 定理定理: :假設(shè)假設(shè)是重言式是重言式, ,那么那么 P/ P/ 也是重言式也是重言式. .38Lu Chaojun, SJTU 39例:代入 代入時(shí)被交換的是命題變元(原子命題),而不能是復(fù)合命題. 例如:可用(RS)來交換(PP)中的P,結(jié)果仍是重言式;但假設(shè)用Q交換(PP),那么不能堅(jiān)持重言式. 代入時(shí)必需對(duì)同一命題變項(xiàng)處處交換以同一公式. 例如:上例中用Q只交換一處P得到的QP不是重言式. 39為什么?Lu Chaojun, SJTU 40利用代入規(guī)那么證明重言式例1: 證明(RS)(RS)為重言式。因PP是重言式, 以(RS)代入P,得(RS)(RS).必是重言式.例2:證明(RS)(RS)(PQ)(PQ)為重言式.易驗(yàn)證:(A(AB)B是重言式(此公式表達(dá)的正是modus ponens推理規(guī)那么), A以RS代入,B以PQ代入即可證明.40Lu Chaojun, SJTU 41自然語句的方式