第一命題邏輯等值演算

第一命題邏輯等值演算演示文稿1當(dāng)前1頁(yè)，總共17頁(yè)。2（優(yōu)選）第一命題邏輯等值演算當(dāng)前2頁(yè)，總共17頁(yè)?；镜戎凳?/p>

雙重否定律

:AA等冪律：

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

A(BC)(AB)(AC)當(dāng)前3頁(yè)，總共17頁(yè)?；镜戎凳?續(xù))德·摩根律:(AB)AB

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

A1A排中律:AA1矛盾律:AA0當(dāng)前4頁(yè)，總共17頁(yè)?；镜戎凳?續(xù))蘊(yùn)涵等值式:ABAB等價(jià)等值式:AB(AB)(BA)假言易位:ABBA等價(jià)否定等值式:ABAB歸謬論:(AB)(AB)A注意:A,B,C代表任意的命題公式牢記這些等值式是繼續(xù)學(xué)習(xí)的基礎(chǔ)當(dāng)前5頁(yè)，總共17頁(yè)。等值演算與置換規(guī)則

等值演算:

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

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

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

(2)基本的等值式

(3)置換規(guī)則當(dāng)前6頁(yè)，總共17頁(yè)。應(yīng)用舉例——證明兩個(gè)公式等值

例1證明

p(qr)(pq)r證

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

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

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

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

說(shuō)明:也可以從右邊開(kāi)始演算（請(qǐng)做一遍）因?yàn)槊恳徊蕉加弥脫Q規(guī)則，故可不寫(xiě)出熟練后，基本等值式也可以不寫(xiě)出

當(dāng)前7頁(yè)，總共17頁(yè)。應(yīng)用舉例——證明兩個(gè)公式不等值例2證明:p(qr)(pq)r

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

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

方法三用等值演算先化簡(jiǎn)兩個(gè)公式，再觀察.當(dāng)前8頁(yè)，總共17頁(yè)。應(yīng)用舉例——判斷公式類(lèi)型

例3

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

解q(pq)

q(pq)（蘊(yùn)涵等值式）

q(pq)（德摩根律）

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

p0（矛盾律）

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

當(dāng)前9頁(yè)，總共17頁(yè)。例3(續(xù))(2)(pq)(qp)解

(pq)(qp)

(pq)(qp)（蘊(yùn)涵等值式）

(pq)(pq)（交換律）

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

當(dāng)前10頁(yè)，總共17頁(yè)。例3(續(xù))(3)((pq)(pq))r)解((pq)(pq))r)

(p(qq))r

（分配律）

p1r

（排中律）

pr

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

復(fù)合聯(lián)結(jié)詞排斥或與非式或非式真值函數(shù)聯(lián)結(jié)詞全功能集當(dāng)前12頁(yè)，總共17頁(yè)。復(fù)合聯(lián)結(jié)詞

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

當(dāng)前13頁(yè)，總共17頁(yè)。真值函數(shù)

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

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

共有個(gè)n元真值函數(shù).例如F:{0,1}2{0,1}，且F(00)=F(01)=F(11)=0，F(xiàn)(01)=1，則F為一個(gè)確定的2元真值函數(shù).當(dāng)前14頁(yè)，總共17頁(yè)。命題公式與真值函數(shù)

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

例如：pq,pq,(pq)((pq)q)等都對(duì)應(yīng)表中的當(dāng)前15頁(yè)，總共17頁(yè)。2元真值函數(shù)對(duì)應(yīng)的真值表pq00010111

00000000000011110011001101010101

pq00010111

11111111000011110011001101010101

當(dāng)前16頁(yè)，總共17頁(yè)。聯(lián)結(jié)詞的全功能集

定義

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