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

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

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