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

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

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

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