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

《《命題邏輯基本概念》PPT課件.ppt》由會員分享，可在線閱讀，更多相關《《命題邏輯基本概念》PPT課件.ppt（54頁珍藏版）》請在裝配圖網上搜索。

第1章命題邏輯基本概念,離散數(shù)學,本章說明,本章的主要內容命題、聯(lián)結詞、復合命題命題公式、賦值、命題公式的分類本章與后續(xù)各章的關系本章是后續(xù)各章的準備或前提,1.1命題與聯(lián)結詞,數(shù)理邏輯研究的中心問題是推理.推理的前提和結論都是表達判斷的陳述句.表達判斷的陳述句構成了推理的基本單位.,1.1命題與聯(lián)結詞,稱能判斷真假而不是可真可假的陳述句為命題（proposition）.作為命題的陳述句所表達得的判斷結果稱為命題的真值.真值只取兩個：真與假.真值為真的命題稱為真命題.真值為假的命題稱為假命題.,感嘆句、疑問句、祈使句都不能稱為命題.判斷結果不唯一確定的陳述句不是命題.陳述句中的悖論不是命題.,說明,4是素數(shù).21/2是無理數(shù).x大于y.充分大的偶數(shù)等于兩個素數(shù)之和.今天是星期二.?大于21/2嗎？請不要吸煙！這朵花真美麗啊！我正在說假話.,例1.1判斷下列句子是否為命題.,是,假命題是,真命題不是,無確定的真值是,真值客觀存在是,真值根據(jù)具體情況而定.不是,疑問句不是,祈使句不是,感嘆句不是,悖論,命題和真值的符號化,用小寫英文字母p,q,r…,pi,qi,ri…表示命題用“1”表示真,用“0”表示假p:4是素數(shù).r:充分大的偶數(shù)等于兩個素數(shù)之和q:21/2是無理數(shù).s:今天是星期二.,不能被分解成更簡單的陳述句,稱這樣的命題為簡單命題或原子命題.由簡單陳述句通過聯(lián)結詞而成的陳述句,稱這樣的命題為復合命題.,例1.2,將下面這段陳述中所出現(xiàn)的原子命題符號化,并指出它們的真值,然后再寫出這段陳述.,21/2是有理數(shù)是不對的；2是偶素數(shù)；2或4是素數(shù)；如果2是素數(shù),則3也是素數(shù)；2是素數(shù)當且僅當3也是素數(shù).,p：21/2是有理數(shù)q：2是素數(shù)；r：2是偶數(shù)s：3是素數(shù)；t：4是素數(shù),01110,非p；q并且(與)r；q或t；如果q,則s；q當且僅當s.,例1.2的討論,半形式化形式數(shù)理邏輯研究方法的主要特征是將論述或推理中的各種要素都符號化.即構造各種符號語言來代替自然語言.形式化語言：完全由符號所構成的語言.將聯(lián)結詞（connective）符號化,消除其二義性,對其進行嚴格定義.例如：他是100米或400米賽跑的冠軍.魚香肉絲或鍋包肉,加一碗湯.,定義1.1否定(negation),設p為命題,復合命題“非p”(或“p的否定”)稱為p的否定式,記作?p,符號?稱作否定聯(lián)結詞,并規(guī)定?p為真當且僅當p為假.,例如：p：哈爾濱是一個大城市.?p：哈爾濱是一個不大城市.?p：哈爾濱不是一個大城市.,定義1.2合取(conjunction),設p,q為二命題,復合命題“p并且q”(或“p與q”)稱為p與q的合取式,記作p?q,?稱作合取聯(lián)結詞,并規(guī)定p?q為真當且僅當p與q同時為真.,使用合取聯(lián)結詞時要注意的兩點：描述合取式的靈活性與多樣性.自然語言中的“既……又……”、“不但……而且……”、“雖然……但是……”、“一面……一面……”等聯(lián)結詞都可以符號化為?.分清簡單命題與復合命題.不要見到“與”或“和”就使用聯(lián)結詞?.,例1.3將下列命題符號化,吳穎既用功又聰明.吳穎不僅用功而且聰明.吳穎雖然聰明,但不用功.張輝與王麗都是三好學生.張輝與王麗是同學.,p:吳穎用功.q:吳穎聰明.r:張輝是三好學生.s:王麗是三好學生.t:張輝與王麗是同學.,(1)p?q(2)p?q(3)q??p(4)r?s(5)t,解題要點：正確理解命題含義.找出原子命題并符號化.選擇恰當?shù)穆?lián)結詞.,合取舉例,p：我們去看電影.q：房間里有十張桌子.p?q：我們去看電影并且房間里有十張桌子.,在數(shù)理邏輯中,關心的只是復合命題與構成復合命題的各原子命題之間的真值關系,即抽象的邏輯關系,并不關心各語句的具體內容.,說明,定義1.3析取(disjunction),設p,q為二命題,復合命題“p或q”稱作p與q的析取式,記作p?q,?稱作析取聯(lián)結詞,并規(guī)定p?q為假當且僅當p與q同時為假.,自然語言中的“或”具有二義性,用它聯(lián)結的命題有時具有相容性,有時具有排斥性,對應的聯(lián)結詞分別稱為相容或和排斥或(排異或).,說明,例1.4將下列命題符號化,張曉靜愛唱歌或愛聽音樂.張曉靜只能挑選202或203房間.張曉靜是江西人或安徽人.他昨天做了二十或三十道習題.,設p：張曉靜愛唱歌,q：張曉靜愛聽音樂.相容或,符號化為p?q設t：張曉靜挑選202房間,u：張曉靜挑選203房間.排斥或,符號化為：(t??u)?(?t?u)設r：張曉靜是江西人,s：張曉靜是安徽人.排斥或,符號化為：r?s.(排斥或聯(lián)結的兩個命題事實上不可能同時為真)或符號化為：(r??s)?(?r?s)原子命題,因為“或”只表示了習題的近似數(shù)目.,定義1.4蘊涵(implication),設p,q為二命題,復合命題“如果p,則q”稱作p與q的蘊涵式,記作p?q,并稱p是蘊涵式的前件,q為蘊涵式的后件,?稱作蘊涵聯(lián)結詞,并規(guī)定p?q為假當且僅當p為真q為假.,說明,p?q的邏輯關系表示q是p的必要條件.q是p的必要條件有許多不同的敘述方式只要p,就q因為p,所以qp僅當q只有q才p除非q才p除非q,否則非p,例1.5將下列命題符號化,并指出其真值,如果3+3＝6,則雪是白的.如果3+3≠6,則雪是白的.如果3+3＝6,則雪不是白的.如果3+3≠6,則雪不是白的.,解：令p：3+3＝6,p的真值為1.q：雪是白色的,q的真值也為1.p?q?p?qp??q?p??q,1101,說明:(1)p?q的邏輯關系:q為p的必要條件(2)“如果p,則q的不同表述法很多:若p,就q只要p,就qp僅當q只有q才p除非q,才p或除非q,否則非p,…．(3)當p為假時,p?q為真,可稱為空證明(4)常出現(xiàn)的錯誤:不分充分與必要條件,例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)只有a能被4整除,a才能被2整除.,解：令r：a能被4整除s：a能被2整除(5)至(9)五個命題均敘述的是a能被2整除是a能被4整除的必要條件,因而都符號化為r?s.其真值為1在(10)中,將a能被4整除看成了a能被2整除的必要條件,因而應符號化為s?r.a值不定時,真值未知.,例設p:天冷,q:小王穿羽絨服,將下列命題符號化(1)只要天冷,小王就穿羽絨服.(2)因為天冷,所以小王穿羽絨服.(3)若小王不穿羽絨服,則天不冷.(4)只有天冷,小王才穿羽絨服.(5)除非天冷,小王才穿羽絨服.(6)除非小王穿羽絨服,否則天不冷.(7)如果天不冷,則小王不穿羽絨服.(8)小王穿羽絨服僅當天冷的時候.注意:p?q與?q??p等值(真值相同)(1),(2),(3),(6)符號化為p?q其余的符號化為q?p,關于蘊含的進一步說明,作為一種規(guī)定,當p為假時,無論q是真是假,p→q均為真.也就是說,只有p為真q為假這一種情況使得復合命題p→q為假.稱為實質蘊含.例：如果x>5,則x>2.(1)x=6如果6>5,則6>2.(2)x=3如果3>5,則3>2.(3)x=1如果1>5,則1>2.例：如果我有車,那么我去接你常出現(xiàn)的錯誤,沒有分清充分條件與必要條件.,定義1.5等價(two-way-implication),設p,q為二命題,復合命題“p當且僅當q”稱作p與q的等價式,記作p?q,稱作等價聯(lián)結詞,并規(guī)定p?q為真當且僅當p與q同時為真或同時為假.,說明,“當且僅當”（ifandonlyif）p?q的邏輯關系為p與q互為充分必要條件.(p?q)?(q?p)與p?q的邏輯關系完全一致.,例1.6將下列命題符號化,并討論它們的真值,π是無理數(shù)當且僅當加拿大位于亞洲.2+3＝5的充要條件是π是無理數(shù).若兩圓A,B的面積相等,則它們的半徑相等；反之亦然.當王小紅心情愉快時,她就唱歌；反之,當她唱歌時,一定心情愉快.,設p：π是無理數(shù),q：加拿大位于亞洲.符號化為p?q,真值為0.設p：2+3＝5,q：π是無理數(shù).符號化為p?q,真值為1.設p：兩圓A,B的面積相等,q：兩圓A,B的半徑相等.符號化為p?q,真值為1.設p：王小紅心情愉快,q：王小紅唱歌.符號化為p?q,真值由具體情況而定.,關于基本聯(lián)結詞的說明,{?,?,?,?,?},稱為一個聯(lián)結詞集.由聯(lián)結詞集{?,?,?,?,?}中的一個聯(lián)結詞聯(lián)結一個或兩個原子命題組成的復合命題是最簡單的復合命題,可以稱它們?yōu)榛镜膹秃厦}.基本復合命題的真值見下表：,關于基本聯(lián)結詞的說明,多次使用聯(lián)結詞集中的聯(lián)結詞,可以組成更為復雜的復合命題.求復雜復合命題的真值時,除依據(jù)上表外,還要規(guī)定聯(lián)結詞的優(yōu)先順序,將括號也算在內.本書規(guī)定的聯(lián)結詞優(yōu)先順序為：(),?,?,?,?,?,對于同一優(yōu)先級的聯(lián)結詞,先出現(xiàn)者先運算.,例1.7,令p：北京比天津人口多.q：2+2＝4.r：烏鴉是白色的.求下列復合命題的真值：(1)((?p?q)?(p??q))?r(2)(q?r)?(p??r)(3)(?p?r)?(p??r),解：p、q、r的真值分別為1、1、0(1)1(2)1(3)0,我們關心的是復合命題中命題之間的真值關系,而不關心命題的內容.,說明,1.2命題公式及其賦值,簡單命題是真值唯一確定的命題邏輯中最基本的研究單位,所以也稱簡單命題為命題常項或命題常元.(propositionconstant)稱真值可以變化的陳述句為命題變項或命題變元(propositionvariable).也用p,q,r,…表示命題變項.當p,q,r,…表示命題變項時,它們就成了取值0或1的變項,因而命題變項已不是命題.這樣一來,p,q,r,…既可以表示命題常項,也可以表示命題變項.在使用中,需要由上下文確定它們表示的是常項還是變項.將命題變項用聯(lián)結詞和圓括號按一定的邏輯關系聯(lián)結起來的符號串稱為合式公式或命題公式.,定義1.6合式公式(wff),(1)單個命題變項是合式公式,并稱為原子命題公式.(2)若A是合式公式,則(?A)也是合式公式.(3)若A,B是合式公式,則(A?B),(A?B),(A?B),(A?B)也是合式公式.(4)只有有限次地應用(1)～(3)形式的符號串才是合式公式.合式公式也稱為命題公式或命題形式,并簡稱為公式.設A為合式公式,B為A中一部分,若B也是合式公式,則稱B為A的子公式.合式公式：WellFormedFormula,關于合式公式的說明,定義1.6給出的合式公式的定義方式稱為歸納定義或遞歸定義方式.定義中引進了A,B等符號,用它們表示任意的合式公式,而不是某個具體的公式,這與p,p?q,(p?q)?r等具體的公式是有所不同的.A,B等符號被稱作元語言符號.p,q等被稱作對象語言符號.所謂對象語言是指用來描述研究對象的語言,而元語言是指用來描述對象的語言,這兩種語言是不同層次的語言.例如中國人學習英語時,英語為對象語言,而用來學習英語的漢語則是元語言.,關于合式公式的說明,(?A)、(A?B)等公式單獨出現(xiàn)時,外層括號可以省去,寫成?A、A?B等.公式中不影響運算次序的括號可以省去,如公式(p?q)?(?r)可以寫成p?q??r.合式公式的例子：(p?q)?(q?r)(p?q)??rp?(q??r)不是合式公式的例子pq?r(p?(r?q),定義1.7公式層次,(1)若公式A是單個的命題變項,則稱A為0層合式.(2)稱A是n+1(n≥0)層公式是指下面情況之一：(a)A＝?B,B是n層公式；(b)A＝B?C,其中B,C分別為i層和j層公式,且n=max(i,j)；(c)A＝B?C,其中B,C的層次及n同(b)；(d)A＝B?C,其中B,C的層次及n同(b)；(e)A＝B?C,其中B,C的層次及n同(b).(3)若公式A的層次為k,則稱A是k層公式.例如：(?p?q)?r,(?(p??q))?((r?s)??p)分別為3層和4層公式,公式的解釋,在命題公式中,由于有命題符號的出現(xiàn),因而真值是不確定的.當將公式中出現(xiàn)的全部命題符號都解釋成具體的命題之后,公式就成了真值確定的命題了.(p?q)?r若p：2是素數(shù),q：3是偶數(shù),r：π是無理數(shù),則p與r被解釋成真命題,q被解釋成假命題,此時公式(p?q)?r解釋成：若2是素數(shù)或3是偶數(shù),則π是無理數(shù).（真命題）r被解釋為：π是有理數(shù),則(p?q)?r被解釋成：若2是素數(shù)或3是偶數(shù),則π是有理數(shù).（假命題）將命題變項p解釋成真命題,相當于指定p的真值為1,解釋成假命題,相當于指定p的真值為0.,定義1.8賦值或解釋,設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是指p1＝α1,p2＝α2,…,pn＝αn.(2)若A中出現(xiàn)的命題符號為p,q,r...,給定A的賦值α1,α2,…,αn是指p＝α1,q＝α2,…,最后一個字母賦值αn.上述αi取值為0或1,i＝1,2,…,n.,賦值舉例,在公式(?p1??p2??p3)?(p1?p2)中,000(p1＝0,p2＝0,p3＝0),110(p1＝1,p2＝1,p3＝0)都是成真賦值,001(p1＝0,p2＝0,p3＝1),011(p1＝0,p2＝1,p3＝1)都是成假賦值.在(p??q)?r中,011(p1＝0,p2＝1,p3＝1)為成真賦值,100(p1＝1,p2＝0,p3＝0)為成假賦值.重要結論：含n(n≥1)個命題變項的公式共有2n個不同的賦值.,定義1.9真值表,將命題公式A在所有賦值下取值情況列成表,稱作A的真值表.,構造真值表的具體步驟如下：(1)找出公式中所含的全體命題變項p1,p2,…,pn(若無下角標就按字典順序排列),列出2n個賦值.本書規(guī)定,賦值從00…0開始,然后按二進制加法依次寫出各賦值,直到11…1為止.(2)按從低到高的順序寫出公式的各個層次.(3)對應各個賦值計算出各層次的真值,直到最后計算出公式的真值.,公式A與B具有相同的或不同的真值表,是指真值表的最后一列是否相同,而不考慮構造真值表的中間過程.,說明,例1.8,求下列公式的真值表,并求成真賦值和成假賦值.(1)(?p?q)??r(2)(p??p)?(q??q)(3)?(p?q)?q?r,定義1.10重言式、永真式、可滿足式,設A為任一命題公式(1)若A在它的各種賦值下取值均為真,則稱A是重言式(tautology)或永真式.(2)若A在它的各種賦值下取值均為假,則稱A是矛盾式(contradiction)或永假式.(3)若A不是矛盾式,則稱A是可滿足式（satisfactableformula）.,定義1.10的進一步說明,A是可滿足式的等價定義是：A至少存在一個成真賦值.重言式一定是可滿足式,但反之不真.因而,若公式A是可滿足式,且它至少存在一個成假賦值,則稱A為非重言式的可滿足式.真值表可用來判斷公式的類型:若真值表最后一列全為1,則公式為重言式.若真值表最后一列全為0,則公式為矛盾式.若真值表最后一列中至少有一個1,則公式為可滿足式.,說明,n個命題變項共產生2n個不同賦值含n個命題變項的公式的真值表只有種不同情況,例題,例題1.9下列各公式均含兩個命題變項p與q,它們中哪些具有相同的真值表?(1)p?q(4)(p?q)?(q?p)(2)p?q(5)?q?p(3)?(p??q),啞元,設公式A,B中共含有命題變項p1,p2,…,pn,,而A或B不全含有這些命題變項,比如A中不含pi,pi+1,…,pn,稱這些命題變項為A的啞元,A的取值與啞元的變化無關,因而在討論A與B是否有相等的真值表時,將A,B都看成p1,p2,…,pn的命題公式.,例題,例1.10下列公式中,哪些具有相同的真值表?(1)p?q(2)?q?r(3)(?p?q)?((p?r)?p)(4)(q?r)?(p?p),本章主要內容,命題與真值（或真假值）.簡單命題與復合命題.聯(lián)結詞：?,?,?,?,?.命題公式（簡稱公式）.命題公式的層次和公式的賦值.真值表.公式的類型：重言式（永真式）,矛盾式（永假式）,可滿足式.,本章學習要求,在5種聯(lián)結詞中,要特別注意蘊涵聯(lián)結的應用,要弄清三個問題：p?q的邏輯關系p?q的真值p?q的靈活的敘述方法寫真值表要特別仔細認真,否則會出錯誤.深刻理解各聯(lián)結詞的邏輯含義.熟練地將復合命題符號化.會用真值表求公式的成真賦值和成假賦值.,本章典型習題,命題符號化求復合命題的真值與命題公式的賦值判斷公式的類型,例題：命題符號化,(1)我和他既是兄弟又是同學p：我和他是兄弟,q：我和他是同學.故命題可符號化為：p?q.(2)張三或李四都可以做這件事.p：張三可以做這件事.q：李四可以做這件事.故命題可符號化為：p?q.(3)僅當我有時間且天不下雨,我將去鎮(zhèn)上.對于“僅當”,實質上是“當”的逆命題.“當A則B”是A?B,而“僅當A則B”是B?A.p：我有時間.q：天不下雨.r：我將去鎮(zhèn)上.故命題可符號化為：r?(p?q).,例題：命題符號化,(4)張剛總是在圖書館看書,除非圖書館不開門或張剛生病.對于“除非”,只要記住,“除非”是條件.p：張剛在圖書館看書,q：圖書館不開門,r：張剛生病.故命題可符號化為：﹁(q?r)?p.(5)風雨無阻,我去上學.可理解為“不管是否刮風、是否下雨,我都去上學”.p：天刮風,q：天下雨,r：我去上學.故命題可符號化為：(p?q?r)?(p??q?r)?(?p?q?r)?(?p??q?r)或(p?q?r)?(p??q?r)?(?p?q?r)?(?p?┐q?r)理解為“四種情況必居其一,而每種情況下我都去上學”,命題符號化的要點,要準確確定原子命題,并將其形式化.要選用恰當?shù)穆?lián)結詞,尤其要善于識別自然語言中的聯(lián)結詞（有時它們被省略）.否定詞的位置要放準確.需要的括號不能省略,而可以省略的括號,在需要提高公式可讀性時亦可不省略.要注意的是,語句的形式化未必是唯一的.,例題：求公式?(p?(q?r))的真值表.,設p:2是素數(shù)q:北京比天津人口多r:美國的首都是舊金山求下面命題的真值(p?q)?r(q?r)?(p??r)(q?r)?(p??r)(q?p)?((p??r)?(?r??q)),提示:p,q為真命題,r是假命題反復用基本復合命題的真值求解(心算即可)答案:真值分別為0,1,0,0,用真值表判斷下面公式的類型p?r??(q?p)((p?q)?(?q??p))?r(p?q)?(p?r)提示:按層次寫真值表,由最后一列判類型,(1)p?r??(q?p),矛盾式,(2)((p?q)?(?q??p))?r,永真式,(3)(p?q)?(p?r),非永真式的可滿足式,本章作業(yè),習題一書上：1,2,4作業(yè)本上：9(1-4),14(1-5),18,19(1-4),