第一命題邏輯等值演算

1第1頁，共19頁，2023年，2月20日，星期一等值式

定義若等價式AB是重言式，則稱A與B等值，記作AB，并稱AB是等值式說明：定義中，A,B,均為元語言符號,A或B中可能有啞元出現(xiàn).例如，在(pq)((pq)(rr))中，r為左邊公式的啞元.

用真值表可驗證兩個公式是否等值請驗證：p(qr)(pq)rp(qr)(pq)r

第2頁，共19頁，2023年，2月20日，星期一基本等值式

雙重否定律

:AA等冪律：

AAA,AAA交換律:ABBA,ABBA結(jié)合律:(AB)CA(BC)(AB)CA(BC)分配律:A(BC)(AB)(AC)

A(BC)(AB)(AC)第3頁，共19頁，2023年，2月20日，星期一基本等值式(續(xù))德·摩根律:(AB)AB

(AB)AB吸收律:A(AB)A,A(AB)A零律:A11,A00同一律:A0A,

A1A排中律:AA1矛盾律:AA0第4頁，共19頁，2023年，2月20日，星期一基本等值式(續(xù))蘊涵等值式:ABAB等價等值式:AB(AB)(BA)假言易位:ABBA等價否定等值式:ABAB歸謬論:(AB)(AB)A注意:A,B,C代表任意的命題公式牢記這些等值式是繼續(xù)學(xué)習(xí)的基礎(chǔ)第5頁，共19頁，2023年，2月20日，星期一等值演算與置換規(guī)則

等值演算:

由已知的等值式推演出新的等值式的過程置換規(guī)則：若AB,則(B)(A)

等值演算的基礎(chǔ)：

(1)等值關(guān)系的性質(zhì)：自反、對稱、傳遞

(2)基本的等值式

(3)置換規(guī)則第6頁，共19頁，2023年，2月20日，星期一應(yīng)用舉例——證明兩個公式等值

例1證明

p(qr)(pq)r證

p(qr)p(qr)（蘊涵等值式，置換規(guī)則）(pq)r

（結(jié)合律，置換規(guī)則）(pq)r

（德摩根律，置換規(guī)則）(pq)r

（蘊涵等值式，置換規(guī)則）

說明:也可以從右邊開始演算（請做一遍）因為每一步都用置換規(guī)則，故可不寫出熟練后，基本等值式也可以不寫出

第7頁，共19頁，2023年，2月20日，星期一應(yīng)用舉例——證明兩個公式不等值例2證明:p(qr)(pq)r

用等值演算不能直接證明兩個公式不等值,證明兩個公式不等值的基本思想是找到一個賦值使一個成真,另一個成假.

方法一真值表法（自己證）方法二觀察賦值法.容易看出000,010等是左邊的的成真賦值，是右邊的成假賦值.

方法三用等值演算先化簡兩個公式，再觀察.第8頁，共19頁，2023年，2月20日，星期一應(yīng)用舉例——判斷公式類型

例3

用等值演算法判斷下列公式的類型(1)q(pq)

解q(pq)

q(pq)（蘊涵等值式）

q(pq)（德摩根律）

p(qq)（交換律，結(jié)合律）

p0（矛盾律）

0（零律）由最后一步可知，該式為矛盾式.

第9頁，共19頁，2023年，2月20日，星期一例3(續(xù))(2)(pq)(qp)解

(pq)(qp)

(pq)(qp)（蘊涵等值式）

(pq)(pq)（交換律）

1由最后一步可知，該式為重言式.問：最后一步為什么等值于1？

第10頁，共19頁，2023年，2月20日，星期一例3(續(xù))(3)((pq)(pq))r)解((pq)(pq))r)

(p(qq))r

（分配律）

p1r

（排中律）

pr

（同一律）這不是矛盾式，也不是重言式，而是非重言式的可滿足式.如101是它的成真賦值,000是它的成假賦值.總結(jié)：A為矛盾式當(dāng)且僅當(dāng)A0A為重言式當(dāng)且僅當(dāng)A1說明：演算步驟不惟一,應(yīng)盡量使演算短些第11頁，共19頁，2023年，2月20日，星期一1.4聯(lián)結(jié)詞全功能集

復(fù)合聯(lián)結(jié)詞排斥或與非式或非式真值函數(shù)聯(lián)結(jié)詞全功能集第12頁，共19頁，2023年，2月20日，星期一復(fù)合聯(lián)結(jié)詞

排斥或:pq(pq)(pq)與非式:pq(pq)或非式:pq(pq)

第13頁，共19頁，2023年，2月20日，星期一真值函數(shù)

問題：含n個命題變項的所有公式共產(chǎn)生多少個互不相同的真值表？答案為個，為什么？定義

稱定義域為{00…0,00…1,…,11…1}，值域為{0,1}的函數(shù)是n元真值函數(shù)，定義域中的元素是長為n的0,1串.常用F:{0,1}n{0,1}表示F是n元真值函數(shù).

共有個n元真值函數(shù).例如F:{0,1}2{0,1}，且F(00)=F(01)=F(11)=0，F(xiàn)(01)=1，則F為一個確定的2元真值函數(shù).第14頁，共19頁，2023年，2月20日，星期一命題公式與真值函數(shù)

對于任何一個含n個命題變項的命題公式A，都存在惟一的一個n元真值函數(shù)F為A的真值表.等值的公式對應(yīng)的真值函數(shù)相同.下表給出所有2元真值函數(shù)對應(yīng)的真值表,每一個含2個命題變項的公式的真值表都可以在下表中找到.

例如：pq,pq,(pq)((pq)q)等都對應(yīng)表中的第15頁，共19頁，2023年，2月20日，星期一2元真值函數(shù)對應(yīng)的真值表pq00010111

00000000000011110011001101010101

pq00010111

11111111000011110011001101010101

第16頁，共19頁，2023年，2月20日，星期一聯(lián)結(jié)詞的全功能集

定義

在一個聯(lián)結(jié)詞的集合中，如果一個聯(lián)結(jié)詞可由集合中的其他聯(lián)結(jié)詞定義，則稱此聯(lián)結(jié)詞為冗余的聯(lián)結(jié)詞，否則稱為獨立的聯(lián)結(jié)詞.例如,在聯(lián)結(jié)詞集{,,,,}中，由于

pqpq,所以，為冗余的聯(lián)結(jié)詞;類似地，也是冗余的聯(lián)結(jié)詞.又在{,,}中，由于

pq(pq)，所以，是冗余的聯(lián)結(jié)詞.類似地，也是冗余的聯(lián)結(jié)詞.

第17頁，共19頁，2023年，2月20日，星期一聯(lián)結(jié)詞的全功能集(續(xù))定義

設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n(n1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞全功能集.說明：若S是聯(lián)結(jié)詞全功能集，則任何命題公式都可用S中的聯(lián)結(jié)詞表示.

若S1,S2是兩個聯(lián)結(jié)詞集合，且S1

S2.若S1是全功能集，則S2也是全功能集.

第18頁，共19頁，2023