《離散學(xué)命題邏輯》PPT課件.ppt

《《離散學(xué)命題邏輯》PPT課件.ppt》由會員分享，可在線閱讀，更多相關(guān)《《離散學(xué)命題邏輯》PPT課件.ppt（46頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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

2、。,說明,4是素數(shù)。 x大于y。 充分大的偶數(shù)等于兩個素數(shù)之和。 今天是星期二。 請不要吸煙！ 這朵花真美麗?。?我正在說假話。,例1.1 判斷下列句子是否為命題。,是，假命題 是，真命題 不是，無確定的真值 是，真值客觀存在 是，真值根據(jù)具體情況而定。 不是，疑問句 不是，祈使句 不是，感嘆句 不是，悖論,命題和真值的符號化,用小寫英文字母p,q,r,pi ,qi ,ri 表示命題 用“1”表示真，用“0”表示假,不能被分解成更簡單的陳述句，稱這樣的命題為簡單命題或原子命題。 由簡單陳述句通過聯(lián)結(jié)詞而成的陳述句，稱這樣的命題為復(fù)合命題。,例1.2,將下面這段陳述中所出現(xiàn)的原子命題符號化，并指

3、出它們的真值，然后再寫出這段陳述。,是有理數(shù)是不對的；2是偶素數(shù)；2或4是素數(shù)；如果2是素數(shù)，則3也是素數(shù)；2是素數(shù)當且僅當3也是素數(shù)。,p： 是有理數(shù) q：2是素數(shù)； r：2是偶數(shù) s：3是素數(shù)； t：4是素數(shù),0 1 1 1 0,非p； q并且(與)r； q或t； 如果q，則s； q當且僅當s。,例1.2的討論,半形式化形式 數(shù)理邏輯研究方法的主要特征是將論述或推理中的各種要素都符號化。即構(gòu)造各種符號語言來代替自然語言。 形式化語言：完全由符號所構(gòu)成的語言。 將聯(lián)結(jié)詞（connective）符號化，消除其二義性，對其進行嚴格定義。 例如：他是100米或400米賽跑的冠軍。 魚香肉絲或鍋包肉

4、，加一碗湯。,定義1.1否定(negation),設(shè)p為命題，復(fù)合命題“非p”(或“p的否定”)稱為p的否定式,記作p，符號稱作否定聯(lián)結(jié)詞，并規(guī)定p為真當且僅當p為假。,例如：p：哈爾濱是一個大城市。 p：哈爾濱是一個不大城市。 p：哈爾濱不是一個大城市。,定義1.2合取(conjunction),設(shè)p,q為二命題，復(fù)合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作pq，稱作合取聯(lián)結(jié)詞，并規(guī)定pq為真當且僅當p與q同時為真。,使用合取聯(lián)結(jié)詞時要注意的兩點： 描述合取式的靈活性與多樣性。自然語言中的“既又”、“不但而且”、“雖然但是”、“一面一面”等聯(lián)結(jié)詞都可以符號化為。 分清簡單命題

5、與復(fù)合命題。不要見到“與”或“和”就使用聯(lián)結(jié)詞。,例1.3 將下列命題符號化,吳穎既用功又聰明。 吳穎不僅用功而且聰明。 吳穎雖然聰明，但不用功。 張輝與王麗都是三好學(xué)生。 張輝與王麗是同學(xué)。,p: 吳穎用功。 q: 吳穎聰明。 r: 張輝是三好學(xué)生。 s: 王麗是三好學(xué)生。 t: 張輝與王麗是同學(xué)。,(1)pq (2)pq (3)qp (4)rs (5)t,解題要點： 正確理解命題含義。 找出原子命題并符號化。 選擇恰當?shù)穆?lián)結(jié)詞。,合取舉例,p：我們?nèi)タ措娪?。q：房間里有十張桌子。 pq：我們?nèi)タ措娪安⑶曳块g里有十張桌子。,在數(shù)理邏輯中，關(guān)心的只是復(fù)合命題與構(gòu)成復(fù)合命題的各原子命題之間的真值

6、關(guān)系，即抽象的邏輯關(guān)系，并不關(guān)心各語句的具體內(nèi)容。,說明,定義1.3析取(disjunction),設(shè)p，q為二命題，復(fù)合命題“p或q”稱作p與q的析取式，記作pq，稱作析取聯(lián)結(jié)詞，并規(guī)定pq為假當且僅當p與q同時為假。,自然語言中的“或”具有二義性，用它聯(lián)結(jié)的命題有時具有相容性，有時具有排斥性，對應(yīng)的聯(lián)結(jié)詞分別稱為相容或和排斥或(排異或)。,說明,例1.4 將下列命題符號化,張曉靜愛唱歌或愛聽音樂。 張曉靜只能挑選202或203房間。 張曉靜是江西人或安徽人。 他昨天做了二十或三十道習題。,設(shè) p：張曉靜愛唱歌，q：張曉靜愛聽音樂。相容或，符號化為 pq 設(shè)t：張曉靜挑選202房間，u：張曉

7、靜挑選203房間。排斥或，符號化為：(tu)(tu) 設(shè)r：張曉靜是江西人，s：張曉靜是安徽人。排斥或，符號化為：rs。(排斥或聯(lián)結(jié)的兩個命題事實上不可能同時為真)或符號化為：(rs)(rs) 原子命題，因為“或”只表示了習題的近似數(shù)目。,定義1.4蘊涵(implication),設(shè)p，q為二命題，復(fù)合命題“如果p，則q”稱作p與q的蘊涵式，記作pq，并稱p是蘊涵式的前件，q為蘊涵式的后件，稱作蘊涵聯(lián)結(jié)詞,并規(guī)定pq為假當且僅當p為真q為假。,說明,pq的邏輯關(guān)系表示q是p的必要條件。 q是p的必要條件有許多不同的敘述方式 只要p，就q 因為p，所以q p僅當q 只有q才p 除非q才p 除非q

8、，否則非p,例1.5 將下列命題符號化，并指出其真值,如果3+36，則雪是白的。 如果3+36，則雪是白的。 如果3+36，則雪不是白的。 如果3+36，則雪不是白的。,解：令p：3+36，p的真值為1。 q：雪是白色的，q的真值也為1。 pq pq pq pq,1 1 0 1,例1.5 將下列命題符號化，并指出其真值,以下命題中出現(xiàn)的a是一個給定的正整數(shù)： (5) 只要a能被4整除，則a一定能被2整除。 (6) a能被4整除，僅當a能被2整除。 (7) 除非a能被2整除， a才能被4整除。 (8) 除非a能被2整除，否則a不能被4整除。 (9)只有a能被2整除， a才能被4整除。 (10)只

9、有a能被4整除， a才能被2整除。,解：令r： a能被4整除 s： a能被2整除 (5)至(9)五個命題均敘述的是a能被2整除是a能被4整除的必要條件，因而都符號化為rs。其真值為1 在(10)中，將a能被4整除看成了a能被2整除的必要條件，因而應(yīng)符號化為sr。 a值不定時，真值未知。,關(guān)于蘊含的進一步說明,作為一種規(guī)定，當p為假時，無論q是真是假，pq均為真。也就是說，只有p為真q為假這一種情況使得復(fù)合命題pq為假。稱為實質(zhì)蘊含。 例：如果x5，則x2。(1) x=6如果65，則62。(2) x=3 如果35，則32。(3) x=1 如果15，則12。 例：如果我有車，那么我去接你 常出現(xiàn)的

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

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

12、據(jù)上表外，還要規(guī)定聯(lián)結(jié)詞的優(yōu)先順序，將括號也算在內(nèi)。 本書規(guī)定的聯(lián)結(jié)詞優(yōu)先順序為：( )，，，，， ，對于同一優(yōu)先級的聯(lián)結(jié)詞，先出現(xià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 命題公式及其賦值,簡單命題是真值唯一確定的命題邏輯中最基本的研究單位，所以也稱簡單命題為命題常項或命題常元。(proposition

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

14、(AB)，(AB)，(AB)也是合式公式。 (4)只有有限次地應(yīng)用(1)(3)形式的符號串才是合式公式。 合式公式也稱為命題公式或命題形式，并簡稱為公式。 設(shè)A為合式公式，B為A中一部分，若B也是合式公式，則稱B為A的子公式。 合式公式：Well Formed Formula,關(guān)于合式公式的說明,定義1.6給出的合式公式的定義方式稱為歸納定義或遞歸定義方式。 定義中引進了A,B等符號，用它們表示任意的合式公式，而不是某個具體的公式，這與p, pq, (pq)r等具體的公式是有所不同的。 A,B等符號被稱作元語言符號。p,q等被稱作對象語言符號。 所謂對象語言是指用來描述研究對象的語言，而元語言

15、是指用來描述對象的語言，這兩種語言是不同層次的語言。 例如中國人學(xué)習英語時，英語為對象語言，而用來學(xué)習英語的漢語則是元語言。,關(guān)于合式公式的說明,(A)、(AB)等公式單獨出現(xiàn)時，外層括號可以省去，寫成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)層公式是指下面情況之一： (a) AB，B是n層公式； (b) ABC，其中B,C分別為i層和j層公式，且n=max

16、(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層公式,公式的解釋,在命題公式中，由于有命題符號的出現(xiàn)，因而真值是不確定的。當將公式中出現(xiàn)的全部命題符號都解釋成具體的命題之后，公式就成了真值確定的命題了。 (pq)r 若p：2是素數(shù)，q：3是偶數(shù)，r：是無理數(shù)，則p與r被解釋成真命題，q被解釋成假命題，此時公式(pq)r被解釋成：若2是素數(shù)或3是偶數(shù)，則是無理數(shù)。（真命題） r被解

17、釋為：是有理數(shù)，則(pq)r被解釋成：若2是素數(shù)或3是偶數(shù)，則是有理數(shù)。（假命題） 將命題變項p解釋成真命題，相當于指定p的真值為1，解釋成假命題，相當于指定p的真值為0。,定義1.8 賦值或解釋,設(shè)p1,p2,,pn是出現(xiàn)在公式A中的全部命題變項，給p1,p2,,pn各指定一個真值，稱為對A的一個賦值或解釋。若指定的一組值使A的真值為1，則稱這組值為A的成真賦值；若使A的真值為0，則稱這組值為A的成假賦值。 對含n個命題變項的公式A的賦值情況做如下規(guī)定：(1)若A中出現(xiàn)的命題符號為p1,p2,,pn，給定A的賦值1,2,,n 是指p11，p22,，pnn。 (2)若A中出現(xiàn)的命題符號為p，q

18、，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(p10，p21，p31)為成真賦值，100(p11，p20，p30)為成假賦值。 重要結(jié)論：含n(n1)個命題變項的公式共有2n個不同的賦值。,定義1.9 真值表,將命題公式A在所有賦值下取值情況列成表，稱作A的真值表。,構(gòu)造真值表的具體步驟如下： (

19、1)找出公式中所含的全體命題變項p1,p2,,pn (若無下角標就按字典順序排列)，列出2n個賦值。本書規(guī)定，賦值從000開始，然后按二進制加法依次寫出各賦值，直到111為止。 (2)按從低到高的順序?qū)懗龉降母鱾€層次。 (3)對應(yīng)各個賦值計算出各層次的真值，直到最后計算出公式的真值。,公式A與B具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考慮構(gòu)造真值表的中間過程。,說明,例1.8,求下列公式的真值表，并求成真賦值和成假賦值。 (1)(pq)r (2)(pp)(qq) (3)(pq)qr,定義1.10 重言式、永真式、可滿足式,設(shè)A為任一命題公式 (1)若A在它的各種賦值下取值

20、均為真,則稱A是重言式(tautology)或永真式。 (2)若A在它的各種賦值下取值均為假,則稱A是矛盾式(contradiction)或永假式。 (3)若A不是矛盾式,則稱A是可滿足式（satisfactable formula）。,定義1.10的進一步說明,A是可滿足式的等價定義是：A至少存在一個成真賦值。 重言式一定是可滿足式，但反之不真。因而，若公式A是可滿足式，且它至少存在一個成假賦值，則稱A為非重言式的可滿足式。 真值表可用來判斷公式的類型: 若真值表最后一列全為1，則公式為重言式。 若真值表最后一列全為0，則公式為矛盾式。 若真值表最后一列中至少有一個1，則公式為可滿足式。,說

21、明,n個命題變項共產(chǎn)生2n個不同賦值 含n個命題變項的公式的真值表只有 種不同情況,例題,例題1.9 下列各公式均含兩個命題變項p與q，它們中哪些具有相同的真值表? (1) pq(4) (pq)(qp)(2) pq(5) qp(3) (pq),啞元,設(shè)公式A,B中共含有命題變項p1,p2,,pn，，而A或B不全含有這些命題變項，比如A中不含pi,pi+1,,pn ,稱這些命題變項為A的啞元，A的取值與啞元的變化無關(guān)，因而在討論A與B是否有相等的真值表時，將A,B都看成p1,p2,,pn的命題公式。,例題,例1.10 下列公式中,哪些具有相同的真值表?(1)pq (2)qr (3)(pq)((

22、pr)p) (4)(qr)(pp),主要內(nèi)容,命題與真值（或真假值）。 簡單命題與復(fù)合命題。 聯(lián)結(jié)詞：，，，，。 命題公式（簡稱公式）。 命題公式的層次和公式的賦值。 真值表。 公式的類型：重言式（永真式），矛盾式（永假式），可滿足式。,學(xué)習要求,在5種聯(lián)結(jié)詞中，要特別注意蘊涵聯(lián)結(jié)的應(yīng)用，要弄清三個問題： pq 的邏輯關(guān)系 pq 的真值 pq 的靈活的敘述方法 寫真值表要特別仔細認真，否則會出錯誤。 深刻理解各聯(lián)結(jié)詞的邏輯含義。 熟練地將復(fù)合命題符號化。 會用真值表求公式的成真賦值和成假賦值。,典型習題,命題符號化 求復(fù)合命題的真值與命題公式的賦值 判斷公式的類型,例題：命題符號化,(1)我和

23、他既是兄弟又是同學(xué) p：我和他是兄弟，q：我和他是同學(xué)。 故命題可符號化為： pq。 (2)張三或李四都可以做這件事。 p：張三可以做這件事。 q：李四可以做這件事。 故命題可符號化為：pq。 (3)僅當我有時間且天不下雨，我將去鎮(zhèn)上。 對于“僅當”，實質(zhì)上是“當”的逆命題?！爱擜則B”是AB，而“僅當A則B”是BA。 p：我有時間。 q：天不下雨。 r：我將去鎮(zhèn)上。 故命題可符號化為：r(pq)。,例題：命題符號化,(4)張剛總是在圖書館看書，除非圖書館不開門或張剛生病。 對于“除非”，只要記住，“除非”是條件。 p：張剛在圖書館看書，q：圖書館不開門，r：張剛生病。 故命題可符號化為：(q

24、r)p。 (5)風雨無阻，我去上學(xué)。 可理解為“不管是否刮風、是否下雨，我都去上學(xué)”。 p：天刮風，q：天下雨，r：我去上學(xué)。 故命題可符號化為：(pqr)(pqr)(pqr)(pqr) 或(pqr)(pqr)(pqr)(pqr) 理解為“四種情況必居其一,而每種情況下我都去上學(xué)”,命題符號化的要點,要準確確定原子命題，并將其形式化。 要選用恰當?shù)穆?lián)結(jié)詞，尤其要善于識別自然語言中的聯(lián)結(jié)詞（有時它們被省略）。 否定詞的位置要放準確。 需要的括號不能省略，而可以省略的括號，在需要提高公式可讀性時亦可不省略。 要注意的是,語句的形式化未必是唯一的。,例題：求公式(p(qr))的真值表。,本章作業(yè),