《命題邏輯基本概念》PPT課件.ppt

1、第1章 命題邏輯基本概念,離散數學,本章說明,本章的主要內容 命題、聯結詞、復合命題 命題公式、賦值、命題公式的分類 本章與后續(xù)各章的關系 本章是后續(xù)各章的準備或前提,1.1 命題與聯結詞,數理邏輯研究的中心問題是推理. 推理的前提和結論都是表達判斷的陳述句. 表達判斷的陳述句構成了推理的基本單位.,1.1 命題與聯結詞,稱能判斷真假而不是可真可假的陳述句為命題（proposition）. 作為命題的陳述句所表達得的判斷結果稱為命題的真值. 真值只取兩個：真與假. 真值為真的命題稱為真命題. 真值為假的命題稱為假命題.,感嘆句、疑問句、祈使句都不能稱為命題. 判斷結果不唯一確定的陳述句不是命題

2、. 陳述句中的悖論不是命題.,說明,4是素數. 21/2是無理數. x大于y. 充分大的偶數等于兩個素數之和. 今天是星期二. 大于21/2嗎？ 請不要吸煙！ 這朵花真美麗??！ 我正在說假話.,例1.1 判斷下列句子是否為命題.,是, 假命題 是, 真命題 不是, 無確定的真值 是, 真值客觀存在 是, 真值根據具體情況而定. 不是, 疑問句 不是, 祈使句 不是, 感嘆句 不是, 悖論,命題和真值的符號化,用小寫英文字母p, q, r, pi , qi , ri 表示命題 用“1”表示真, 用“0”表示假 p: 4是素數. r: 充分大的偶數等于兩個素數之和 q: 21/2是無理數. s:

3、今天是星期二.,不能被分解成更簡單的陳述句, 稱這樣的命題為簡單命題或原子命題. 由簡單陳述句通過聯結詞而成的陳述句, 稱這樣的命題為復合命題.,例1.2,將下面這段陳述中所出現的原子命題符號化, 并指出它們的真值, 然后再寫出這段陳述.,21/2是有理數是不對的；2是偶素數；2或4是素數；如果2是素數, 則3也是素數；2是素數當且僅當3也是素數.,p：21/2是有理數 q：2是素數； r：2是偶數 s：3是素數； t：4是素數,0 1 1 1 0,非p； q并且(與)r； q或t； 如果q, 則s； q當且僅當s.,例1.2的討論,半形式化形式 數理邏輯研究方法的主要特征是將論述或推理中的各

4、種要素都符號化. 即構造各種符號語言來代替自然語言. 形式化語言：完全由符號所構成的語言. 將聯結詞（connective）符號化, 消除其二義性, 對其進行嚴格定義. 例如：他是100米或400米賽跑的冠軍. 魚香肉絲或鍋包肉, 加一碗湯.,定義1.1否定(negation),設p為命題, 復合命題“非p”(或“p的否定”)稱為p的否定式, 記作p, 符號稱作否定聯結詞, 并規(guī)定p為真當且僅當p為假.,例如：p：哈爾濱是一個大城市. p：哈爾濱是一個不大城市. p：哈爾濱不是一個大城市.,定義1.2合取(conjunction),設p, q為二命題, 復合命題“p并且q”(或“p與q”)稱為

5、p與q的合取式, 記作pq, 稱作合取聯結詞, 并規(guī)定p q為真當且僅當p與q同時為真.,使用合取聯結詞時要注意的兩點： 描述合取式的靈活性與多樣性. 自然語言中的“既又”、“不但而且”、“雖然但是”、“一面一面”等聯結詞都可以符號化為. 分清簡單命題與復合命題. 不要見到“與”或“和”就使用聯結詞.,例1.3 將下列命題符號化,吳穎既用功又聰明. 吳穎不僅用功而且聰明. 吳穎雖然聰明, 但不用功. 張輝與王麗都是三好學生. 張輝與王麗是同學.,p: 吳穎用功. q: 吳穎聰明. r: 張輝是三好學生. s: 王麗是三好學生. t: 張輝與王麗是同學.,(1)p q (2)p q (3)q p

6、 (4)r s (5)t,解題要點： 正確理解命題含義. 找出原子命題并符號化. 選擇恰當的聯結詞.,合取舉例,p：我們去看電影. q：房間里有十張桌子. p q：我們去看電影并且房間里有十張桌子.,在數理邏輯中, 關心的只是復合命題與構成復合命題的各原子命題之間的真值關系, 即抽象的邏輯關系, 并不關心各語句的具體內容.,說明,定義1.3析取(disjunction),設p, q為二命題, 復合命題“p或q”稱作p與q的析取式, 記作pq, 稱作析取聯結詞, 并規(guī)定p q為假當且僅當p與q同時為假.,自然語言中的“或”具有二義性, 用它聯結的命題有時具有相容性, 有時具有排斥性, 對應的聯結

7、詞分別稱為相容或和排斥或(排異或).,說明,例1.4 將下列命題符號化,張曉靜愛唱歌或愛聽音樂. 張曉靜只能挑選202或203房間. 張曉靜是江西人或安徽人. 他昨天做了二十或三十道習題.,設 p：張曉靜愛唱歌, q：張曉靜愛聽音樂. 相容或, 符號化為 pq 設t：張曉靜挑選202房間, u：張曉靜挑選203房間. 排斥或, 符號化為：(tu)(tu) 設r：張曉靜是江西人, s：張曉靜是安徽人. 排斥或, 符號化為：rs. (排斥或聯結的兩個命題事實上不可能同時為真)或符號化為：(rs)(rs) 原子命題, 因為“或”只表示了習題的近似數目.,定義1.4蘊涵(implication),設p

8、, q為二命題, 復合命題“如果p, 則q”稱作p與q的蘊涵式, 記作pq, 并稱p是蘊涵式的前件, q為蘊涵式的后件, 稱作蘊涵聯結詞, 并規(guī)定pq為假當且僅當p為真q為假.,說明,pq的邏輯關系表示q是p的必要條件. q是p的必要條件有許多不同的敘述方式 只要p, 就q 因為p, 所以q p僅當q 只有q才p 除非q才p 除非q, 否則非p,例1.5 將下列命題符號化, 并指出其真值,如果3+36, 則雪是白的. 如果3+36, 則雪是白的. 如果3+36, 則雪不是白的. 如果3+36, 則雪不是白的.,解：令p：3+36, p的真值為1. q：雪是白色的, q的真值也為1. pq pq

9、 pq pq,1 1 0 1,說明: (1)pq的邏輯關系: q為p的必要條件 (2)“如果p, 則q的不同表述法很多: 若p, 就q 只要p, 就q p僅當q 只有q 才p 除非q, 才p或除非q, 否則非p, (3)當p為假時, pq為真, 可稱為空證明 (4) 常出現的錯誤: 不分充分與必要條件,例1.5 將下列命題符號化, 并指出其真值,以下命題中出現的a是一個給定的正整數： (5) 只要a能被4整除, 則a一定能被2整除. (6) a能被4整除, 僅當a能被2整除. (7) 除非a能被2整除, a才能被4整除. (8) 除非a能被2整除, 否則a不能被4整除. (9)只有a能被2整除

10、, a才能被4整除. (10)只有a能被4整除, a才能被2整除.,解：令r： a能被4整除 s： a能被2整除 (5)至(9)五個命題均敘述的是a能被2整除是a能被4整除的必要條件, 因而都符號化為rs. 其真值為1 在(10)中, 將a能被4整除看成了a能被2整除的必要條件, 因而應符號化為sr. a值不定時, 真值未知.,例 設p: 天冷, q: 小王穿羽絨服, 將下列命題符號化 (1)只要天冷, 小王就穿羽絨服. (2)因為天冷, 所以小王穿羽絨服. (3)若小王不穿羽絨服, 則天不冷. (4)只有天冷, 小王才穿羽絨服. (5)除非天冷, 小王才穿羽絨服. (6)除非小王穿羽絨服,

11、否則天不冷. (7)如果天不冷, 則小王不穿羽絨服. (8)小王穿羽絨服僅當天冷的時候. 注意: pq與qp等值(真值相同) (1), (2), (3), (6)符號化為pq 其余的符號化為qp,關于蘊含的進一步說明,作為一種規(guī)定, 當p為假時, 無論q是真是假, pq均為真. 也就是說, 只有p為真q為假這一種情況使得復合命題pq為假. 稱為實質蘊含. 例：如果x5, 則x2. (1) x=6如果65, 則62. (2) x=3 如果35, 則32. (3) x=1 如果15, 則12. 例：如果我有車, 那么我去接你 常出現的錯誤, 沒有分清充分條件與必要條件.,定義1.5等價(two-w

12、ay-implication),設p, q為二命題, 復合命題“p當且僅當q”稱作p與q的等價式, 記作pq, 稱作等價聯結詞, 并規(guī)定pq為真當且僅當p與q同時為真或同時為假.,說明,“當且僅當”（if and only if） pq的邏輯關系為p與q互為充分必要條件. (pq)(qp)與pq的邏輯關系完全一致.,例1.6 將下列命題符號化, 并討論它們的真值,是無理數當且僅當加拿大位于亞洲. 2+35的充要條件是是無理數. 若兩圓A, B的面積相等, 則它們的半徑相等；反之亦然. 當王小紅心情愉快時, 她就唱歌；反之, 當她唱歌時, 一定心情愉快.,設 p：是無理數, q：加拿大位于亞洲.

13、 符號化為 pq, 真值為0. 設 p：2+35, q：是無理數. 符號化為 pq, 真值為1. 設 p：兩圓A, B的面積相等, q：兩圓A, B的半徑相等. 符號化為 pq, 真值為1. 設 p：王小紅心情愉快, q：王小紅唱歌. 符號化為 pq, 真值由具體情況而定.,關于基本聯結詞的說明, , , , , 稱為一個聯結詞集. 由聯結詞集, , , , 中的一個聯結詞聯結一個或兩個原子命題組成的復合命題是最簡單的復合命題, 可以稱它們?yōu)榛镜膹秃厦}. 基本復合命題的真值見下表：,關于基本聯結詞的說明,多次使用聯結詞集中的聯結詞, 可以組成更為復雜的復合命題. 求復雜復合命題的真值時,

14、除依據上表外, 還要規(guī)定聯結詞的優(yōu)先順序, 將括號也算在內. 本書規(guī)定的聯結詞優(yōu)先順序為：( ), , , , , , 對于同一優(yōu)先級的聯結詞, 先出現者先運算.,例1.7,令 p：北京比天津人口多. q：2+24. r：烏鴉是白色的. 求下列復合命題的真值：(1)(pq)(pq)r (2)(qr)(pr) (3)(pr)(pr),解：p、q、r的真值分別為 1、1、0 (1) 1(2) 1(3) 0,我們關心的是復合命題中命題之間的真值關系, 而不關心命題的內容.,說明,1.2 命題公式及其賦值,簡單命題是真值唯一確定的命題邏輯中最基本的研究單位, 所以也稱簡單命題為命題常項或命題常元. (

15、proposition constant) 稱真值可以變化的陳述句為命題變項或命題變元 (proposition variable). 也用p, q, r, 表示命題變項. 當p, q, r, 表示命題變項時, 它們就成了取值0或1的變項, 因而命題變項已不是命題. 這樣一來, p, q, r, 既可以表示命題常項, 也可以表示命題變項. 在使用中, 需要由上下文確定它們表示的是常項還是變項. 將命題變項用聯結詞和圓括號按一定的邏輯關系聯結起來的符號串稱為合式公式或命題公式.,定義1.6 合式公式( wff ),(1)單個命題變項是合式公式, 并稱為原子命題公式. (2)若A是合式公式, 則(

16、A)也是合式公式. (3)若A, B是合式公式, 則(AB), (AB), (AB), (AB)也是合式公式. (4)只有有限次地應用(1)(3)形式的符號串才是合式公式. 合式公式也稱為命題公式或命題形式, 并簡稱為公式. 設A為合式公式, B為A中一部分, 若B也是合式公式, 則稱B為A的子公式. 合式公式：Well Formed Formula,關于合式公式的說明,定義1.6給出的合式公式的定義方式稱為歸納定義或遞歸定義方式. 定義中引進了A, B等符號, 用它們表示任意的合式公式, 而不是某個具體的公式, 這與p, pq, (pq)r等具體的公式是有所不同的. A, B等符號被稱作元語

17、言符號. p, q等被稱作對象語言符號. 所謂對象語言是指用來描述研究對象的語言, 而元語言是指用來描述對象的語言, 這兩種語言是不同層次的語言. 例如中國人學習英語時, 英語為對象語言, 而用來學習英語的漢語則是元語言.,關于合式公式的說明,(A)、(AB)等公式單獨出現時, 外層括號可以省去, 寫成A、AB等. 公式中不影響運算次序的括號可以省去, 如公式(pq)(r)可以寫成pqr. 合式公式的例子：(pq)(q r)(pq)rp(qr) 不是合式公式的例子pqr(p(rq),定義1.7 公式層次,(1)若公式A是單個的命題變項, 則稱A為0層合式. (2)稱A是n+1(n0)層公式是指

18、下面情況之一： (a) AB, B是n層公式； (b) ABC, 其中B, C分別為i層和j層公式, 且n=max(i, j)； (c) ABC, 其中B, C的層次及n同(b)； (d) ABC, 其中B, C的層次及n同(b)； (e) ABC, 其中B, C的層次及n同(b). (3)若公式A的層次為k, 則稱A是k層公式. 例如：(pq)r, (pq)(rs)p) 分別為3層和4層公式,公式的解釋,在命題公式中, 由于有命題符號的出現, 因而真值是不確定的. 當將公式中出現的全部命題符號都解釋成具體的命題之后, 公式就成了真值確定的命題了. (pq)r 若p：2是素數, q：3是偶數,

19、 r：是無理數, 則p與r被解釋成真命題, q被解釋成假命題, 此時公式(pq)r解釋成：若2是素數或3是偶數, 則是無理數. （真命題） r被解釋為：是有理數, 則(pq)r被解釋成：若2是素數或3是偶數, 則是有理數. （假命題） 將命題變項p解釋成真命題, 相當于指定p的真值為1, 解釋成假命題, 相當于指定p的真值為0.,定義1.8 賦值或解釋,設p1, p2, , pn是出現在公式A中的全部命題變項, 給p1, p2, , pn各指定一個真值, 稱為對A的一個賦值或解釋. 若指定的一組值使A的真值為1, 則稱這組值為A的成真賦值；若使A的真值為0, 則稱這組值為A的成假賦值. 對含n

20、個命題變項的公式A的賦值情況做如下規(guī)定：(1)若A中出現的命題符號為p1, p2, , pn, 給定A的賦值1, 2, , n 是指p11, p22, , pnn. (2)若A中出現的命題符號為p, q, r., 給定A的賦值1, 2, , n是指p1, q2, , 最后一個字母賦值n. 上述i取值為0或1, i1, 2, , n.,賦值舉例,在公式(p1p2p3)(p1p2)中, 000(p10, p20, p30), 110(p11, p21, p30)都是成真賦值, 001(p10, p20, p31), 011(p10, p21, p31)都是成假賦值. 在(pq)r中, 011(p1

21、0, p21, p31)為成真賦值, 100(p11, p20, p30)為成假賦值. 重要結論：含n(n1)個命題變項的公式共有2n個不同的賦值.,定義1.9 真值表,將命題公式A在所有賦值下取值情況列成表, 稱作A的真值表.,構造真值表的具體步驟如下： (1)找出公式中所含的全體命題變項p1, p2, , pn (若無下角標就按字典順序排列), 列出2n個賦值. 本書規(guī)定, 賦值從000開始, 然后按二進制加法依次寫出各賦值, 直到111為止. (2)按從低到高的順序寫出公式的各個層次. (3)對應各個賦值計算出各層次的真值, 直到最后計算出公式的真值.,公式A與B具有相同的或不同的真值表

22、, 是指真值表的最后一列是否相同, 而不考慮構造真值表的中間過程.,說明,例1.8,求下列公式的真值表, 并求成真賦值和成假賦值. (1)(pq)r (2)(pp)(qq) (3)(pq)qr,定義1.10 重言式、永真式、可滿足式,設A為任一命題公式 (1)若A在它的各種賦值下取值均為真, 則稱A是重言式(tautology)或永真式. (2)若A在它的各種賦值下取值均為假, 則稱A是矛盾式(contradiction)或永假式. (3)若A不是矛盾式, 則稱A是可滿足式（satisfactable formula）.,定義1.10的進一步說明,A是可滿足式的等價定義是：A至少存在一個成真賦

23、值. 重言式一定是可滿足式, 但反之不真. 因而, 若公式A是可滿足式, 且它至少存在一個成假賦值, 則稱A為非重言式的可滿足式. 真值表可用來判斷公式的類型: 若真值表最后一列全為1, 則公式為重言式. 若真值表最后一列全為0, 則公式為矛盾式. 若真值表最后一列中至少有一個1, 則公式為可滿足式.,說明,n個命題變項共產生2n個不同賦值 含n個命題變項的公式的真值表只有 種不同情況,例題,例題1.9 下列各公式均含兩個命題變項p與q, 它們中哪些具有相同的真值表? (1) pq(4) (pq)(qp)(2) pq(5) qp(3) (pq),啞元,設公式A, B中共含有命題變項p1, p2

24、, , pn, , 而A或B不全含有這些命題變項, 比如A中不含pi, pi+1, , pn , 稱這些命題變項為A的啞元, A的取值與啞元的變化無關, 因而在討論A與B是否有相等的真值表時, 將A, B都看成p1, p2, , pn的命題公式.,例題,例1.10 下列公式中, 哪些具有相同的真值表?(1)pq (2)qr (3)(pq)(pr)p) (4)(qr)(pp),本章主要內容,命題與真值（或真假值）. 簡單命題與復合命題. 聯結詞：, , , , . 命題公式（簡稱公式）. 命題公式的層次和公式的賦值. 真值表. 公式的類型：重言式（永真式）, 矛盾式（永假式）, 可滿足式.,本章

25、學習要求,在5種聯結詞中, 要特別注意蘊涵聯結的應用, 要弄清三個問題： pq 的邏輯關系 pq 的真值 pq 的靈活的敘述方法 寫真值表要特別仔細認真, 否則會出錯誤. 深刻理解各聯結詞的邏輯含義. 熟練地將復合命題符號化. 會用真值表求公式的成真賦值和成假賦值.,本章典型習題,命題符號化 求復合命題的真值與命題公式的賦值 判斷公式的類型,例題：命題符號化,(1)我和他既是兄弟又是同學 p：我和他是兄弟, q：我和他是同學. 故命題可符號化為： pq. (2)張三或李四都可以做這件事. p：張三可以做這件事. q：李四可以做這件事. 故命題可符號化為：pq. (3)僅當我有時間且天不下雨, 我將去鎮(zhèn)上. 對于