資源描述：
《《離散數(shù)學》PPT課件》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第七章謂詞邏輯廣東工業(yè)大學計算機學院7.3謂詞演算的推理理論7.2等價式與永真蘊含式主要內(nèi)容等價式與永真蘊含式謂詞推理理論2謂詞公式的等價給定兩個謂詞公式A和B，設(shè)它們有共同的個體域E，如果對A和B的任一組變元（個體詞）進行賦值，所得命題的真值相同，則稱謂詞公式A和B在E上等價記做A?B3謂詞公式的等價與命題公式的等價舉例PQP?Q?P?QTTTTTFFFFTTTFFTTP?Q??P?QF(x)?W(x)??F(x)?W(x)X的范圍是：所有正整數(shù)xF(x)?W(x)?F(x)?W(x)1T/F?T/F?2T/F？T/F?………4命題演算中等價公式的推廣應
2、用用同一謂詞公式代替兩個等價命題公式中的同一命題變元，所得到的謂詞公式也等價。例如：(?x)F(x)W(x)?(?x)F(x)W(x)???PQPQ(?x)F(x)?G(x)???QPQ(?x)F(x)G(x)?P?()5等價變換基本規(guī)則1．置換規(guī)則2．約束元的換名規(guī)則3．自由元的代入規(guī)則6等價演算的基本規(guī)則(1)1.置換規(guī)則：設(shè)P(A)是含公式A的公式，若A?B,則用公式B取代P(A)中所有的A之后的公式P(B)與P(A)等價。例：(?x)(A(x)→B)?(?x)(?A(x)∨B)7等價替換基本規(guī)則(2)2．約束元的換名規(guī)則設(shè)A為一公式，將A中某量詞轄
3、域中某約束變量的指導變元及相應的約束變元改成該量詞轄域中未曾出現(xiàn)過的某個體變量符號，公式的其余部分不變，所得公式與A等價.例：?(?x)(P(x,y)?Q(x))??xR(x)??(?z)(P(z,y)?Q(z))??xR(x)8等價替換基本規(guī)則(3)3．自由元的代入規(guī)則設(shè)A為一公式，將A中某個自由出現(xiàn)的個體變元的所有出現(xiàn)用A中未曾出現(xiàn)過的個體變元符號代替，A中其余部分不變，所得公式與A等價.例：?(?x)(P(x,y)?Q(x))??xR(x)??(?x)(P(x,w)?Q(x))??xR(x)9常用等價式1：否定與量詞量詞與否定聯(lián)結(jié)詞┐的關(guān)系：(1)┐
4、(?x)P(x)?(?x)┐P(x)(2)┐(?x)P(x)?(?x)┐P(x)證法一:(1)“并非對任意x，P(X)是真”等價于“至少存在一個x，使P(X)為假”。(2)“并非存在一個x，使P(X)為真”等價于“對所有的x，P(X)為假”。注意：出現(xiàn)在量詞前面的否定，不是否定該量詞本身，而是否定被量化了的整個公式。10證法2：設(shè)個體域為{a1，a2，……………，an}┐(?x)P(x)?┐(P(a1)?P(a2)?……………?P(an))?┐P(a1)?┐P(a2)?……………?┐P(an)?(?x)┐P(x)11常用等價式2：量詞的分配公式（1）1)?
5、對∧可分配：?x(A(x)∧B(x))??xA(x)∧?xB(x)設(shè)x的個體域為{a1，a2，…，an}?x(A(x)∧B(x))?(A(a1)∧B(a1))∧(A(a2)∧B(a2))∧…∧(A(an)∧B(an))?(A(a1)∧A(a2)∧…∧A(an))∧(B(a1)∧B(a2)∧…∧B(an))??xA(x)∧?xB(x)12量詞的分配公式?x(A(x)∨B(x))??xA(x)∨?xB(x)？舉例：令x的個體域為正整數(shù)。A(x)：x是奇數(shù)B(x)：x是偶數(shù)?x(A(x)∨B(x))?所有正整數(shù)是奇數(shù)或者偶數(shù)。?xA(x)∨?xB(x)?所有正整
6、數(shù)都是奇數(shù)或者所有正整數(shù)都是偶數(shù)。13常用等價式2：量詞的分配公式（2）2)?對∨可分配：?x(A(x)∨B(x))??xA(x)∨?xB(x)設(shè)x的個體域為{a1，a2，…，an}?x(A(x)∨B(x))?(A(a1)∨B(a1))∨(A(a2)∨B(a2))∨…∨(A(an)∨B(an))?(A(a1)∨A(a2)∨…∨A(an))∨(B(a1)∨B(a2)∨…∨B(an))??xA(x)∨?xB(x)14析取、合取與量詞(?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)？舉例：令x的個體域為正整數(shù)。A(x)：x是奇數(shù)B(x)：x是偶
7、數(shù)?x(A(x)?B(x))?存在既是奇數(shù)又是偶數(shù)的正整數(shù)。?xA(x)??xB(x)?存在為奇數(shù)的正整數(shù)且存在為偶數(shù)的正整數(shù)。15常用等價式2：析取、合取與量詞量詞與聯(lián)結(jié)詞∧，∨的關(guān)系總結(jié)：1)?x(A(x)∧B(x))??xA(x)∧?xB(x)?x(A(x)∨B(x))??xA(x)∨?xB(x)2)?x(A(x)∨B(x))??xA(x)∨?xB(x)?x(A(x)∧B(x))??xA(x)∧?xB(x)16常用等價式3：量詞轄域收縮與擴張設(shè)A(x)是任意一個含個體變量x的公式，B中不含x，(P:288)1.(?x)A(x)∨B?(?x)(A(x)
8、∨B)(?x)A(x)∧B?(?x)(A(x)∧B)(補充)2.(
