第二章-命題邏輯等值演算課件

第二章命題邏輯等值演算第二章命題邏輯等值演算1本章內(nèi)容等值式基本等值式等值演算置換規(guī)則析取范式和合取范式析取范式與合取范式主析取范式與主合取范式本章內(nèi)容等值式22.1等值式兩公式什么時候代表了同一個命題呢？抽象地看，它們的真假取值完全相同時即代表了相同的命題。設(shè)公式A,B共同含有n個命題變項，可能A或B有啞元，若A與B有相同的真值表，則說明在2n個賦值的每個賦值下，A與B的真值都相同。于是等價式A?B應(yīng)為重言式。2.1等值式兩公式什么時候代表了同一個命題呢？32.1等值式2.1等值式42.1等值式(p∨q)?(┐p∧┐q)的真值表2.1等值式(p∨q)?(┐p∧┐q)的真值表52.1等值式例、判斷下列各組公式是否等值：（1）p→(q→r)與(p∧q)→r（2）(p→q)→r與(p∧q)→r2.1等值式例、判斷下列各組公式是否等值：62.1等值式基本等值式2.1等值式基本等值式72.1等值式基本等值式（續(xù)）2.1等值式基本等值式（續(xù)）82.1等值式基本等值式（續(xù)）2.1等值式基本等值式（續(xù)）92.1等值式等值演算與置換規(guī)則2.1等值式等值演算與置換規(guī)則102.1等值式應(yīng)用舉例——證明兩個公式等值2.1等值式應(yīng)用舉例——證明兩個公式等值112.1等值式例、證明兩個公式不等值2.1等值式例、證明兩個公式不等值122.1等值式應(yīng)用舉例---判斷公式類型2.1等值式應(yīng)用舉例---判斷公式類型132.1等值式應(yīng)用舉例---判斷公式類型2.1等值式應(yīng)用舉例---判斷公式類型142.1等值式應(yīng)用舉例---判斷公式類型2.1等值式應(yīng)用舉例---判斷公式類型152.2析取范式與合取范式2.2析取范式與合取范式162.2析取范式與合取范式2.2析取范式與合取范式172.2析取范式與合取范式2.2析取范式與合取范式182.2析取范式與合取范式2.2析取范式與合取范式192.2析取范式與合取范式命題公式的方式2.2析取范式與合取范式命題公式的方式202.2析取范式與合取范式求公式的范式舉例2.2析取范式與合取范式求公式的范式舉例212.2析取范式與合取范式求公式的范式舉例2.2析取范式與合取范式求公式的范式舉例222.2析取范式與合取范式極大項與極小項2.2析取范式與合取范式極大項與極小項232.2析取范式與合取范式極大項與極小項2.2析取范式與合取范式極大項與極小項242.2析取范式與合取范式2.2析取范式與合取范式252.2析取范式與合取范式主析取范式與主合取范式2.2析取范式與合取范式主析取范式與主合取范式262.2析取范式與合取范式主析取范式與主合取范式2.2析取范式與合取范式主析取范式與主合取范式272.2析取范式與合取范式主析取范式與主合取范式求公式的主范式2.2析取范式與合取范式主析取范式與主合取范式282.2析取范式與合取范式主析取范式與主合取范式求公式的主范式2.2析取范式與合取范式主析取范式與主合取范式292.2析取范式與合取范式主析取范式與主合取范式求公式的主范式2.2析取范式與合取范式主析取范式與主合取范式302.2析取范式與合取范式主析取范式與主合取范式求公式的主范式2.2析取范式與合取范式主析取范式與主合取范式312.2析取范式與合取范式主范式的用途——與真值表相同2.2析取范式與合取范式主范式的用途——與真值表相同322.2析取范式與合取范式主范式的用途2.2析取范式與合取范式主范式的用途332.2析取范式與合取范式主范式的用途2.2析取范式與合取范式主范式的用途342.3聯(lián)接詞的完備集N元真值函數(shù)定義：就是有n個自變量的函數(shù)，其自變量和函數(shù)值都是真值為0或者1。一元真值函數(shù)有4個2.3聯(lián)接詞的完備集N元真值函數(shù)352.3聯(lián)接詞的完備集N元真值函數(shù)二元真值函數(shù)有16個2.3聯(lián)接詞的完備集N元真值函數(shù)362.3聯(lián)接詞的完備集N元真值函數(shù)一般地，n元真值函數(shù)共有多少個呢？每個自變量有2個取值方式，n個自變量共有2n個不同取值方式。對n個自變量的每個取值方式，函數(shù)值有2個取值方式，即為0或1，故n元真值函數(shù)共有個。例如，3元真值函數(shù)共有=256個。

一般地，函數(shù)F:{0,1}n→{0,1}稱為n元真值函數(shù)，其中：{0,1}n為{0，1}的卡氏積。

2.3聯(lián)接詞的完備集N元真值函數(shù)372.3聯(lián)接詞的完備集真值函數(shù)與命題公式的關(guān)系對于每個真值函數(shù)，都可以找到許多與之等值的命題公式。以2元真值函數(shù)為例，所有矛盾式都與F0等值，所有的重言式都與F15等值。又如F13?(p→q)?(┐p∨q)?┐(p∧┐q)?(┐p∧┐q)∨(┐p∧q)∨(p∧q)。更重要的是，每個真值函數(shù)與唯一的一個主析取范式（主合取范式）等值。還以2元真值函數(shù)為例，0（矛盾式），（p∧q）m1，（p∧┐q）m2，（p∧┐q）∨（p∧q）m2∨m3,…反過來，每個主析取范式對應(yīng)無窮多個與之等值的公式，所以每個真值函數(shù)對應(yīng)無窮多個與之等值的命題公式。由定理2.5可知，每個命題公式對應(yīng)唯一的與之等值的真值函數(shù)。2.3聯(lián)接詞的完備集真值函數(shù)與命題公式的關(guān)系382.3聯(lián)接詞的完備集聯(lián)結(jié)詞完備集定義：設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n(n≥1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞完備集。定理：S={┐,∧,∨}是聯(lián)結(jié)詞完備集。因為任何n(n≥1)元真值函數(shù)都與唯一的一個主析取范式等值，而在主析取范式中僅含聯(lián)結(jié)詞┐,∧,∨，所以S={┐,∧,∨}是聯(lián)結(jié)詞完備集。2.3聯(lián)接詞的完備集聯(lián)結(jié)詞完備集392.3聯(lián)接詞的完備集聯(lián)結(jié)詞完備集以下聯(lián)結(jié)詞集都是完備集：(1)S1={┐,∧,∨,→}(2)S2={┐,∧,∨,→,}(3)S3={┐,∧}(4)S4={┐,∨}(5)S5={┐,→}解答：(1)，(2)的成立是顯然的。(3)由于S={┐,∧,∨}是聯(lián)結(jié)詞完備集，因而任何真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞的公式表示。同時對于任意公式A,B,A∨B┐┐(A∨B)┐(┐A∧┐B),因而任意真值函數(shù)都可以由僅含S3={┐,∧}中的聯(lián)結(jié)詞的公式表示，所以S3是聯(lián)結(jié)詞完備集。(4)A∧B┐(┐A∨┐B)。(5）A∨B┐A→B。2.3聯(lián)接詞的完備集聯(lián)結(jié)詞完備集402.3聯(lián)接詞的完備集單元素聯(lián)結(jié)詞構(gòu)成的聯(lián)結(jié)詞完備集設(shè)p、q為兩個命題，復(fù)合命題“p與q的否定式”（“p或q的否定式”）稱作p,q的與非式（或非式），記作p↑q(p↓q)。符號↑(↓)稱作與非聯(lián)結(jié)詞（或非聯(lián)結(jié)詞）。p↑q為真當(dāng)且僅當(dāng)p與q不同時為真（p↓q為真當(dāng)且僅當(dāng)p與q同時為假）。

p↑q?┐(p∧q）p↓q?┐(p∨q）2.3聯(lián)接詞的完備集單元素聯(lián)結(jié)詞構(gòu)成的聯(lián)結(jié)詞完備集412.3聯(lián)接詞的完備集單元素聯(lián)結(jié)詞構(gòu)成的聯(lián)結(jié)詞完備集{↑}，{↓}都是聯(lián)結(jié)詞完備集。證已知{┐,∧,∨}為聯(lián)結(jié)詞完備集，因而只需證明其中的每個聯(lián)結(jié)詞都可以由↑定義即可。而

┐p?┐(p∧p）?p↑p；p∧q?┐┐(p∧q)?┐(p↑q)?(p↑q