math-chap1-1.離散數(shù)學(xué)-命題邏輯

莊伯金bjzhuang@1第一章命題邏輯課件下載地址：/Lecture.php莊伯金bjzhuang@2主要內(nèi)容命題的基本概念等值演算范式推理理論莊伯金bjzhuang@3命題的基本概念命題的定義能判斷真假的陳述句命題的兩個關(guān)鍵要素必須是陳述句能明確地判斷真假命題的真值判斷為正確的命題，其真值為真（1）；判斷為錯誤的命題，其真值為假（0）。莊伯金bjzhuang@4命題的例4是素數(shù)。x大于y。充分大的偶數(shù)等于兩個素數(shù)之和。(歌德巴赫猜想)2020年5月1日北京的天氣是雨天。請不要吸煙！這朵花真美麗啊！我正在說假話。你現(xiàn)在好嗎？莊伯金bjzhuang@5命題符號化命題常用小寫字母表示，如p：4是素數(shù)命題的真值表示：1表示真0表示假簡單命題不能被分解為更簡單的陳述句的命題也稱為原子命題命題常項與命題變項命題常項：真值可以確定；命題變項：真值可以變化。本質(zhì)不是命題。莊伯金bjzhuang@6復(fù)合命題及聯(lián)結(jié)復(fù)合命題：由簡單命題通過聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。常見聯(lián)結(jié)詞否定聯(lián)結(jié)詞合取聯(lián)結(jié)詞析取聯(lián)結(jié)詞蘊涵聯(lián)結(jié)詞等價聯(lián)結(jié)詞莊伯金bjzhuang@7例P：今天是星期二。?p：今天不是星期二。q：所有人都來上課了。?q：不是所有人來上課了。有人沒來上課。否定式定義：復(fù)合命題“非p”稱為p的否定式，記作?p。?為否定聯(lián)結(jié)詞。?p為真當(dāng)且僅當(dāng)p為假。即?p表示對p的真值取反。p?p1001莊伯金bjzhuang@8例小李既勤奮又聰明。小李不僅勤奮而且聰明。小李雖然聰明，但是不勤奮。小李和小王都很勤奮。小李和小王是同學(xué)。注：并不是所有的“和”、“與”都表示合取關(guān)系。合取式定義：復(fù)合命題“p并且q”稱為p與q的合取式，記作p∧q?！臑楹先÷?lián)結(jié)詞。p∧q為真當(dāng)前僅當(dāng)p與q同時為真。其他情況時p∧q為假。pqp∧q111100010000莊伯金bjzhuang@9例小李愛唱歌或者愛打籃球。小李在打籃球或者在踢足球。小李可以坐火車或者乘飛機回家。析取式定義：復(fù)合命題“p或者q”稱為p與q的析取式，記作p∨q?！艦槲鋈÷?lián)結(jié)詞。p∨q為假當(dāng)且僅當(dāng)p與q同時為假。其他情況p∨q為真。pqp∨q111101011000莊伯金bjzhuang@10析取式自然語言中的“或”具有二義性，與析取式中的“或”含義不完全相同。析取式可表示“相容或”和“不同時為真排斥或”；“能同時為真的排斥或”可用“異或”關(guān)系表示。莊伯金bjzhuang@11蘊涵式定義：復(fù)合命題“如果p，則q”稱為p與q的蘊涵式，記作p→q。p→q為假當(dāng)前僅當(dāng)p為真且q為假。其他情況時，p→q為真。pqp→q111100011001自然語言中p與q具有聯(lián)系，而數(shù)理邏輯中p與q可以沒有聯(lián)系。例如果3＋3＝6，則雪是黑的。如果3+36，則雪是黑的。莊伯金bjzhuang@12蘊涵式p→q在邏輯上表明p為q的充分條件，q為p的必要條件。例只要a能被4整除，則a一定能被2整除。a能被4整除，僅當(dāng)a能被2整除。除非a能被2整除，a才能被4整除。只有a能被2整除，a才能被4整除。只有a能被4整除，a才能被2整除。莊伯金bjzhuang@13等價式定義：復(fù)合命題“p當(dāng)且僅當(dāng)q”稱為p與q的等價式，記作p?q。?稱作等價聯(lián)結(jié)詞。p?q為真當(dāng)且僅當(dāng)p與q真值相同。其他情況時，p?q為假。pqp?q111100010001p?q在邏輯上表明p與q互為充要條件。例：若今天為1號，則明天是2號，反之亦然。今天是雨天當(dāng)且僅當(dāng)雪是黑的。莊伯金bjzhuang@14基本復(fù)合命題真值表pq?pp∧qp∨qp→qp?q0010011011011010001001101111莊伯金bjzhuang@15聯(lián)結(jié)詞的優(yōu)先順序()?∧∨→?莊伯金bjzhuang@16練習(xí)判斷下列命題的真值若2＋2＝4，則3＋3＝6若2＋2＝4，則3＋3≠6若2＋2≠4，則3＋3＝6若2＋2≠4，則3＋3≠62＋2＝4當(dāng)且僅當(dāng)3＋3＝62＋2＝4當(dāng)且僅當(dāng)3＋3≠62＋2≠4當(dāng)且僅當(dāng)3＋3＝62＋2≠4當(dāng)且僅當(dāng)3＋3≠6莊伯金bjzhuang@17練習(xí)將下列命題符號化2是偶數(shù)又是素數(shù)他一邊吃飯一邊看電視如果天下雨，他就乘公共汽車上班只有天下雨，他才乘公共汽車上班不經(jīng)一事，不長一智莊伯金bjzhuang@18練習(xí)設(shè)p、q的真值為0，r、s的真值為1，求下列命題公式的真值p∨(q∧r)(p?r)∧(?q∨s)莊伯金bjzhuang@19命題公式命題常項（命題常元）：簡單命題，真值唯一確定。命題變項（命題變元）：真值可以變化的陳述句。命題常項和命題變元都用小寫字母表示。合式公式（命題公式）：將命題變項用聯(lián)結(jié)詞和圓括號按一定的邏輯關(guān)系聯(lián)結(jié)起來的符號串。莊伯金bjzhuang@20合式公式的定義遞歸定義1.單個命題變項是合式公式，并稱為原子命題公式；2.若A是合式公式，則(?A)也是合式公式；3.若A，B是合式公式，則(A∧B)，(A∨B)，(A→B)，(A?B)也是合式公式；4.只有有限次地應(yīng)用1－3形式的符號串才是合式公式。子公式定義若A為合式公式，B為A的一部分，且B也是合式公式，則稱B為A的子公式。莊伯金bjzhuang@21公式的賦值定義設(shè)A為一命題公式，p1,p2,…,pn,為所有在A中出現(xiàn)的命題變項。給p1,p2,…,pn指定一組真值，稱其為A的一個賦值或解釋。若指定的一組賦值使A的真值為真，則稱這組值為A的成真賦值。若指定的一組賦值使A的真值為假，則稱這組值為A的成假賦值。將一個命題公式在所有賦值下的情況列成表，稱為這個公式的真值表。n個命題變項共有2n組賦值。莊伯金bjzhuang@22例p∨(q∧r)的真值表pqrq∧rp∨(q∧r)0000000100010000111110001101011100111111莊伯金bjzhuang@23例p∨(?p∨q)的真值表pq?p?p∨qp∨(?p∨q)00111011111000111011莊伯金bjzhuang@24例p∧(?p∧q)的真值表pq?p?p∧qp∧(?p∧q)00100011101000011000莊伯金bjzhuang@25重言式（永真式）：所有的賦值都是A的成真賦值。矛盾式（永假式）：所有的賦值都是A的成假賦值。可滿足式：至少存在一組賦值使A為真。莊伯金bjzhuang@26等值演算等值式（等價式）設(shè)A，B為兩命題公式，若A?B為重言式，則稱A與B為等值式，記為AB。不是邏輯聯(lián)結(jié)詞，表示對任意的賦值，A與B的值相同。?是等價聯(lián)結(jié)詞，它與不能混為一談。等值式的性質(zhì)（等價關(guān)系的通性）自反性：AA；對稱性：若AB，則BA；傳遞性：若AB和BC，則AC。莊伯金bjzhuang@27例p→q與?p∨q是否等值？莊伯金bjzhuang@28基本等值規(guī)律(1)雙重否定律A??A等冪律AA∨AAA∧A交換律A∨BB∨AA∧BB∧A結(jié)合律A∨(B∨C)(A∨B)∨CA∧(B∧C)(A∧B)∧C莊伯金bjzhuang@29基本等值規(guī)律(2)分配律A∨(B∧C)(A∨B)∧(A∨C)A∧(B∨C)(A∧B)∨(A∧C)德.摩根律?(A∨B)?A∧?B?(A∧B)?A∨?B吸收律A∨(A∧B)AA∧(A∨B)A莊伯金bjzhuang@30基本等值規(guī)律(3)零律A∨11A∧00同一律A∨0AA∧1A排中律A∨?A1矛盾律A∧?A0莊伯金bjzhuang@31基本等值規(guī)律(4)蘊涵等值式A→B?A∨B等價等值式A?B(A→B)∧(B→A)(?A∨B)∧(?B∨A)假言易位A→B?B→?A等價否定等值式A?B?A??B歸謬論(A→B)∧(A→?B)?A莊伯金bjzhuang@32置換規(guī)則設(shè)Φ(A)為含公式A的命題公式，Φ(B)為用公式B置換了A的命題公式，若AB，則Φ(A)Φ(B)。利用等值規(guī)律及置換規(guī)則可以進行等值演算。例(p→q)→(?q→?p)?(q→p)∧p(?p→q)→(q→?p)(p∨q)→r?(p→(p∨q))∧r莊伯金bjzhuang@33聯(lián)結(jié)詞的完備集問題：含n個命題變項的命題公式其真值表的可能性有多少種？n元真值函數(shù)：F：{0,1}n→{0,1}為n元真值函數(shù)。聯(lián)結(jié)詞完備集：設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞完備集。{?,∧,∨}{?,∧}{?,∨}{?,→}莊伯金bjzhuang@34對偶對偶的定義：在僅含有?,∧,∨的命題公式A中，將∧換成∨，∨換成∧，若A中含0或1，將0換成1，1換成0，所得的命題公式稱為A的對偶式，記為A*。定理：設(shè)A和A*互為對偶式，p1,p2,…,pn是出現(xiàn)在A和A*中的全部命題變項，若將A和A*寫成n元函數(shù)形式，則：(1)?A(p1,p2,…,pn)A*(?p1,?p2,…,?pn)(2)A(?p1,?p2,…,?pn)?A*(p1,p2,…,pn)對偶原理：設(shè)A、B為兩命題公式，若AB，則A*B*。莊伯金bjzhuang@35范式的概念命題公式的規(guī)范表示方法析取范式合取范式文字：命題變項及其否定式統(tǒng)稱文字簡單析取式僅有有限個文字構(gòu)成的析取式簡單合取式僅有有限個文字構(gòu)成的合取式定理：一個簡單析取式是重言式當(dāng)且僅當(dāng)它同時含某個命題變項及其否定式一個簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時含某個命題變項及其否定式莊伯金bjzhuang@36析取范式定義由有限個簡單合取式構(gòu)成的析取式例p∨q(?p∧q)∨r析取范式性質(zhì)析取范式是矛盾式當(dāng)且僅當(dāng)它的每個簡單合取式是矛盾式莊伯金bjzhuang@37合取范式定義:由有限個簡單析取式構(gòu)成的合取式例p∧q(p∨?q)∧r合取范式性質(zhì)合取范式是重言式，當(dāng)且僅當(dāng)它的每個簡單析取式是重言式莊伯金bjzhuang@38范式存在定理定理：任一命題公式都存在與之等值的析取范式（合取范式）。求范式的步驟利用蘊涵等值式和等價等值式消去聯(lián)結(jié)詞→、?。用雙重否定律消去否定聯(lián)結(jié)詞，利用德.摩根律將否定聯(lián)結(jié)詞內(nèi)移。利用分配律求析取范式或合取范式。例：(p→q)?r范式的求解例：(p→q)?r莊伯金bjzhuang@39莊伯金bjzhuang@40極小項與極大項極小項的定義在含n個命題變項的簡單合取式中，如果每個變項與其否定式不同時存在，但兩者之一恰出現(xiàn)1次，且第i個命題變項或否定式出現(xiàn)在從左起的第i位上。極大項的定義在含n個命題變項的簡單析取式中，如果每個變項與其否定式不同時存在，但兩者之一恰出現(xiàn)1次，且第i個命題變項或否定式出現(xiàn)在從左起的第i位上。n個命題變項共可形成2n個極小項和2n個極大項。莊伯金bjzhuang@41極小項的成真賦值每個極小項僅有一個成真賦值每個極小項的成真賦值均不相同可以利用不同的成真賦值區(qū)別每個極小項，給予標(biāo)記二元極小項取值成真賦值簡記名稱?p∧?q100m0?p∧q101m1p∧?q110m2p∧q111m3莊伯金bjzhuang@42極大項的成假賦值每個極大項僅有一個成假賦值每個極大項的成假賦值均不相同可以利用不同的成假賦值區(qū)別每個極大項，給予標(biāo)記二元極大項取值成假賦值簡記名稱p∨q000M0p∨?q001M1?p∨q010M2?p∨?q011M3莊伯金bjzhuang@43主析取范式與主合取范式主析取范式的定義若A的命題公式由若干個極小項進行析取構(gòu)成，則稱該析取范式為A的主析取范式從主析取范式中很容易得到成真賦值主合取范式的定義若A的命題公式由若干個極大項進行合取構(gòu)成，則稱該合取范式為A的主合取范式從主合取范式中很容易得到成假賦值定理：任何命題公式都存在與之等值的主析?。ê先。┓妒?，且唯一。莊伯金bjzhuang@44主析取范式的求解方法(1)用等值演算求得析取范式依次掃描析取范式中的每個簡單合取式B若B為極小項，則繼續(xù)掃描下一個若B不為極小項，將不含的命題變項p及其否定式?p用等值變換添入BB∧(p∨?p)(B∧p)∨(B∧?p)

消去重復(fù)出現(xiàn)的命題變項、極小項和矛盾式。莊伯金bjzhuang@45主析取范式的求解方法(2)根據(jù)公式構(gòu)造真值表寫出每個公式成真賦值對應(yīng)的極小項將極小項進行析取，即得主析取范式莊伯金bjzhuang@46主析取范式例：求(p→(q∧r))∧(?p→(?q∧?r))莊伯金bjzhuang@47主合取范式的求解方法(1)用等值演算求得合取范式依次掃描合取范式中的每個簡單析取式B若B為極大項，則繼續(xù)掃描下一個若B不為極大項，將不含的命題變項p及其否定式?p用等值變換添入BB∨(p∧?p)(B∨p)∧(B∨?p)

消去重復(fù)出現(xiàn)的命題變項、極大項和重言式。莊伯金bjzhuang@48主合取范式的求解方法(2)根據(jù)公式構(gòu)造真值表寫出每個公式成假賦值對應(yīng)的極大項將極大項進行合取，即得主合取范式莊伯金bjzhuang@49主合取范式例：求(p→(q∧r))∧(?p→(?q∧?r))莊伯金bjzhuang@50主析取范式與主合取范式主析取范式與主合取范式之間的關(guān)系？莊伯金bjzhuang@51推理的形式結(jié)構(gòu)設(shè)兩命題公式A、B，若A→B為重言式，則稱A蘊涵B，記為AB。設(shè)A1、A2、...、An、B為命題公式，若A1∧A2∧...∧AnB，則稱B為A1、A2、...、An的邏輯結(jié)論或有效結(jié)論，也稱B可由一組前提A1、A2、...、An邏輯推出。記為A1，A2，...，AnB。正確推理的本質(zhì)是A1∧A2∧...∧An→B為重言式。當(dāng)A1∧A2∧...∧An為假時，不論B是真是假，A1∧A2∧...∧An→B均為真。所以B為有效結(jié)論并不意味B為真。莊伯金bjzhuang@52推理的基本方法簡單證明法：證明A1∧A2∧...∧An→B是重言式，即A1∧A2∧...∧An→B1。真值表法等值演算法主析取范式法例：若a能被4整除，則a能被2整除。因為a能被2整除，所以a能被4整除。莊伯金bjzhuang@53推理的基本方法(2)直接構(gòu)造證明法由給定的一組前提出發(fā)，利用推理規(guī)則逐步演算得到結(jié)論。常用推理規(guī)則前提引入規(guī)則：在證明過程的任何步驟都可以將前提引入使用結(jié)論引入規(guī)則：在推理中，若已證出結(jié)論B，則B可以引入到以后的推理中作為前提使用置換規(guī)則：命題公式中任何