離散數(shù)學第二章命題邏輯等值演算.pptx

《離散數(shù)學第二章命題邏輯等值演算.pptx》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、第二章命題邏輯等值演算公式的賦值定義：將給定公式A中所含命題變元指定具體的一組真值，稱這組真值為給公式A的賦值（或解釋）。公式A在此組賦值（解釋）下就具有確定的真值。1）公式A的所有賦值組數(shù)與公式所含變元有關（共有2n組）2）若公式A在此組解釋下的真值為真(1,T），則稱此組賦值為成真賦值。3）若公式A在此組解釋下的真值為假(0,F），則稱此組賦值為成假賦值。pq(p→q)∧(q→p)(p∧q)∨(┓p∧┓q)001101001000111（0,0）與（1,1）為公式的成真賦值。（0,1）與（1,0）為公式的成假賦值命題公式的分類（根據(jù)公式在賦值下的真值情況進行分類）1）若

2、命題公式在它的各種賦值下取值均為真,則稱命題公式是重言式或永真式。2）若命題公式在它的各種賦值下取值均為假,則稱命題公式是矛盾式或永假式。3）若命題公式不是矛盾式,則稱命題公式是可滿足式。(或公式至少有一組成真賦值）例：判斷公式的類型（現(xiàn)在只能用真值表方法）┓(p→q)∧qp→（p∨q∨r)(┓p→q)→(q→┓p)┓(（p∧q)→q）后一頁pq┓(p→q)∧q000010100110┓((p∧q)→q）0000(┓p→q)→(q→┓p)1110pqrp→(p∨q∨r)00010011010101111001101111011111返回對于形似于條件命題的構(gòu)成形式即A→B而

3、且要說明是重言式如：┐Q∧（Ｐ→Q）→┐P可利用條件聯(lián)結(jié)詞的性質(zhì)來給予證明分析1：若要得出：當設A為真，B為假的情況不會出現(xiàn)，那么A→B為永真式?？勺C明：設前件為真分析2：還可以從設B為假，推出A為真的情況不會出現(xiàn)（A為假），那么A→B為永真式。證明：設后件為假(（Ｐ→Q）∧(Q→R))→(Ｐ→R)不同真值表的公式1）當命題變元確定后，通過五個連接詞及其命題變元可以構(gòu)成無數(shù)個不同表現(xiàn)形式的命題公式。問題：這些不同形式的命題公式的真值表是否都不相同？先看變元僅有兩個p,q那么關于這兩個變元的公式的賦值僅有4組任何關于這兩個變元的公式的所有真值表只能是一組4位二進制數(shù)4位二進制

4、數(shù)的不同狀態(tài)共有16＝24關于2個變元的不同真值表的公式僅有16種。以此推斷：2）當命題變元確定后，由于其公式的賦值組數(shù)是確定的（共2n組）公式在一組賦值下是一個真值（一位二進制）在2n組賦值下對應為2n位二進制n個變元的不同真值表的公式僅有（2）（2n）種例：2個變元的16種不同真值表Pq(p∧┑p)∨(q∧┑q)P∧qP∧┑qP┑P∧qq┑(P?q)P∨q000000000001000011110001100111101010101Pq┑(P∨q)P?q┑qq→P┑PP→q┑(P∧q)(P∨┑p)∧(q∨┑q)001111111101000011110001100111

5、101010101例：看幾個公式的真值表：pqp→q┓p∨q0011011110001111pqp?q(p→q)∧(q→p)(p∧q)∨(┓p∧┓q)00111010001000011111公式的表現(xiàn)形式不同但具有相同的真值表也可以說：對所含變元的所有賦值下，其公式的真值均相同我們把這類公式定義為“是邏輯等值的”為了更方便地對命題公式進行討論（確定其真值、公式的分類及其推理），象代數(shù)式那樣進行演算（化簡），有必要引入一些化簡原則。代數(shù)式的化簡原則是等值（不論變量的取值如何，代數(shù)式的值是相等的），對于命題公式來說化簡的原則是邏輯等值。返回第二章命題邏輯等值演算一、邏輯等值定義

6、給定兩個命題公式A和B，設A和B含有共同的n個命題變元。若對于這n個命題變元的所有可能的賦值，命題公式A與B的真值均相同，則稱命題公式A邏輯等值于命題公式B。并記作A?B。邏輯等值的另外的形式定義：給定兩個命題公式A和B，若由A和B構(gòu)成的等價式A?B為重言式（永真式），則稱命題公式A邏輯等值于命題公式B。兩個定義可相互證明注：1、“?”不是連接詞，僅表示兩個公式具有等值關系（不能用等號），所構(gòu)成的式子不是命題公式2、等值的性質(zhì)：對任意公式A，Ｂ，Ｃ(進行演算的理論基礎)１）自反性：A?A；２）對稱性：若A?Ｂ，則Ｂ?A；３）傳遞性：若A?Ｂ，Ｂ?Ｃ，則A?Ｃ3、判斷兩個

7、公式是否等值的方法真值表方法：列出兩個公式的真值表，看其真值是否相同（最基礎的方法）驗證公式p→q與公式┑p∨q等值┐(A∧B)?┐A∨┐B代數(shù)式的演算無法采用此種方法演算法：以經(jīng)過驗算的等值式為基礎（乘法公式－等值定律）利用置換規(guī)則（等值代換）及其等值的性質(zhì)得到其他的等值式（與代數(shù)式的演算類似）下面引入經(jīng)過驗算得出的等值定律為使定律使用的更廣泛，定律中使用元語言的表示方法二、等值定律1．雙重否定律A?┐┐A2.冪等律A∨A?AA∧A?A3.結(jié)合律(A∨B)∨C?A∨(B∨C)(A∧B)∧C?A∧(B∧C)4.交換