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

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

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

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

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

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

6、 (4)r s (5)t,解題要點(diǎn)： 正確理解命題含義. 找出原子命題并符號(hào)化. 選擇恰當(dāng)?shù)穆?lián)結(jié)詞.,合取舉例,p：我們?nèi)タ措娪? q：房間里有十張桌子. p q：我們?nèi)タ措娪安⑶曳块g里有十張桌子.,在數(shù)理邏輯中, 關(guān)心的只是復(fù)合命題與構(gòu)成復(fù)合命題的各原子命題之間的真值關(guān)系, 即抽象的邏輯關(guān)系, 并不關(guān)心各語(yǔ)句的具體內(nèi)容.,說明,定義1.3析取(disjunction),設(shè)p, q為二命題, 復(fù)合命題“p或q”稱作p與q的析取式, 記作pq, 稱作析取聯(lián)結(jié)詞, 并規(guī)定p q為假當(dāng)且僅當(dāng)p與q同時(shí)為假.,自然語(yǔ)言中的“或”具有二義性, 用它聯(lián)結(jié)的命題有時(shí)具有相容性, 有時(shí)具有排斥性, 對(duì)應(yīng)的聯(lián)結(jié)

7、詞分別稱為相容或和排斥或(排異或).,說明,例1.4 將下列命題符號(hào)化,張曉靜愛唱歌或愛聽音樂. 張曉靜只能挑選202或203房間. 張曉靜是江西人或安徽人. 他昨天做了二十或三十道習(xí)題.,設(shè) p：張曉靜愛唱歌, q：張曉靜愛聽音樂. 相容或, 符號(hào)化為 pq 設(shè)t：張曉靜挑選202房間, u：張曉靜挑選203房間. 排斥或, 符號(hào)化為：(tu)(tu) 設(shè)r：張曉靜是江西人, s：張曉靜是安徽人. 排斥或, 符號(hào)化為：rs. (排斥或聯(lián)結(jié)的兩個(gè)命題事實(shí)上不可能同時(shí)為真)或符號(hào)化為：(rs)(rs) 原子命題, 因?yàn)椤盎颉敝槐硎玖肆?xí)題的近似數(shù)目.,定義1.4蘊(yùn)涵(implication),設(shè)p

8、, q為二命題, 復(fù)合命題“如果p, 則q”稱作p與q的蘊(yùn)涵式, 記作pq, 并稱p是蘊(yùn)涵式的前件, q為蘊(yùn)涵式的后件, 稱作蘊(yùn)涵聯(lián)結(jié)詞, 并規(guī)定pq為假當(dāng)且僅當(dāng)p為真q為假.,說明,pq的邏輯關(guān)系表示q是p的必要條件. q是p的必要條件有許多不同的敘述方式 只要p, 就q 因?yàn)閜, 所以q p僅當(dāng)q 只有q才p 除非q才p 除非q, 否則非p,例1.5 將下列命題符號(hào)化, 并指出其真值,如果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的邏輯關(guān)系: q為p的必要條件 (2)“如果p, 則q的不同表述法很多: 若p, 就q 只要p, 就q p僅當(dāng)q 只有q 才p 除非q, 才p或除非q, 否則非p, (3)當(dāng)p為假時(shí), pq為真, 可稱為空證明 (4) 常出現(xiàn)的錯(cuò)誤: 不分充分與必要條件,例1.5 將下列命題符號(hào)化, 并指出其真值,以下命題中出現(xiàn)的a是一個(gè)給定的正整數(shù)： (5) 只要a能被4整除, 則a一定能被2整除. (6) a能被4整除, 僅當(dāng)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)五個(gè)命題均敘述的是a能被2整除是a能被4整除的必要條件, 因而都符號(hào)化為rs. 其真值為1 在(10)中, 將a能被4整除看成了a能被2整除的必要條件, 因而應(yīng)符號(hào)化為sr. a值不定時(shí), 真值未知.,例 設(shè)p: 天冷, q: 小王穿羽絨服, 將下列命題符號(hào)化 (1)只要天冷, 小王就穿羽絨服. (2)因?yàn)樘炖? 所以小王穿羽絨服. (3)若小王不穿羽絨服, 則天不冷. (4)只有天冷, 小王才穿羽絨服. (5)除非天冷, 小王才穿羽絨服. (6)除非小王穿羽絨服,

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

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

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

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

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

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

17、言符號(hào). p, q等被稱作對(duì)象語(yǔ)言符號(hào). 所謂對(duì)象語(yǔ)言是指用來描述研究對(duì)象的語(yǔ)言, 而元語(yǔ)言是指用來描述對(duì)象的語(yǔ)言, 這兩種語(yǔ)言是不同層次的語(yǔ)言. 例如中國(guó)人學(xué)習(xí)英語(yǔ)時(shí), 英語(yǔ)為對(duì)象語(yǔ)言, 而用來學(xué)習(xí)英語(yǔ)的漢語(yǔ)則是元語(yǔ)言.,關(guān)于合式公式的說明,(A)、(AB)等公式單獨(dú)出現(xiàn)時(shí), 外層括號(hào)可以省去, 寫成A、AB等. 公式中不影響運(yùn)算次序的括號(hào)可以省去, 如公式(pq)(r)可以寫成pqr. 合式公式的例子：(pq)(q r)(pq)rp(qr) 不是合式公式的例子pqr(p(rq),定義1.7 公式層次,(1)若公式A是單個(gè)的命題變項(xiàng), 則稱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層公式,公式的解釋,在命題公式中, 由于有命題符號(hào)的出現(xiàn), 因而真值是不確定的. 當(dāng)將公式中出現(xiàn)的全部命題符號(hào)都解釋成具體的命題之后, 公式就成了真值確定的命題了. (pq)r 若p：2是素?cái)?shù), q：3是偶數(shù),

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

20、個(gè)命題變項(xiàng)的公式A的賦值情況做如下規(guī)定：(1)若A中出現(xiàn)的命題符號(hào)為p1, p2, , pn, 給定A的賦值1, 2, , n 是指p11, p22, , pnn. (2)若A中出現(xiàn)的命題符號(hào)為p, q, r., 給定A的賦值1, 2, , n是指p1, q2, , 最后一個(gè)字母賦值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)為成假賦值. 重要結(jié)論：含n(n1)個(gè)命題變項(xiàng)的公式共有2n個(gè)不同的賦值.,定義1.9 真值表,將命題公式A在所有賦值下取值情況列成表, 稱作A的真值表.,構(gòu)造真值表的具體步驟如下： (1)找出公式中所含的全體命題變項(xiàng)p1, p2, , pn (若無下角標(biāo)就按字典順序排列), 列出2n個(gè)賦值. 本書規(guī)定, 賦值從000開始, 然后按二進(jìn)制加法依次寫出各賦值, 直到111為止. (2)按從低到高的順序?qū)懗龉降母鱾€(gè)層次. (3)對(duì)應(yīng)各個(gè)賦值計(jì)算出各層次的真值, 直到最后計(jì)算出公式的真值.,公式A與B具有相同的或不同的真值表

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

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

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

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