第二章命題邏輯等值演算(yǎnsuàn)1精品文檔本章主要(zhǔyào)內容等值式范式(fànshì)合取范式析取范式聯結詞的完備(wánbèi)集

重點內容：等值演算范式消解法2精品文檔2.1等值式

等值式基本等值式等值演算和置換(zhìhuàn)規則3精品文檔一、等值式

定義1：設A和B是兩個(liǎnɡɡè)命題公式，如果A、B在任意指派下，其真值都是相同的，則稱A和B是等值的，或邏輯相等，記作AB，稱AB為等值式。pq

q

ppq(pq)(qp)4精品文檔一、等值式5精品文檔一、等值式6精品文檔一、等值式

定義(dìngyì)2：若AB是重言式，則稱A與B等值，記作AB，并稱AB是等值式。例如(lìrú)，(pq)((pq)(rr))說明：定義中，A、B、均為元語言符號(fúhào),A或B中可能有啞元出現。r是啞元7精品文檔一、等值式

等值式的性質(xìngzhì)：自反性，即對任意公式A，有A

A。對稱性，即對任意公式A和B，若A

B，則B

A。傳遞性，即對任意公式A、B和C，若

A

B、B

C，則A

C。8精品文檔一、等值式例1：“除非(chúfēi)有時間，我才去看電影。”上面這句話的意思相當于“如果沒有時間，我就不去看電影。”令：p：我有時間(shíjiān)；q：我去看電影9精品文檔pq和q

p是等值的。

判斷兩個(liǎnɡɡè)公式是否為等值式的基本方法是：通過兩個(liǎnɡɡè)公式的真值表進行驗證。10精品文檔二、基本(jīběn)等值式

雙重(shuāngchóng)否定律

:AA冪等律：

AAA,AAA交換律:ABBA,ABBA結合律:(AB)CA(BC)(AB)CA(BC)11精品文檔二、基本(jīběn)等值式分配律:A(BC)(AB)(AC)

A(BC)(AB)(AC)德·摩根律

:(AB)AB

(AB)AB吸收(xīshōu)律:A(AB)A,A(AB)A12精品文檔零律:A11,A00同一律:A0A,

A1A排中律:AA1矛盾律:AA0蘊涵(yùnhán)等值式:ABAB二、基本(jīběn)等值式13精品文檔二、基本(jīběn)等值式等價等值式:AB(AB)(BA)假言易位:ABBA等價否定(fǒudìng)等值式:ABAB歸謬論:(AB)(AB)A14精品文檔ABAB(pq)AB等值式模式：由元語言符號(fúhào)表示的等值式稱作等值式模式。pAB(rs)ABr(pq)

rqpq(s)(rs)

(s)代入實例(shílì)每一個等值模式都可以(kěyǐ)對應于無窮多個同類型的具體等值式。15精品文檔三、等值演算與置換(zhìhuàn)規則

等值演算:由已知的等值式推演(tuīyǎn)出新的等值式的過程。例：由基本等值式可知pqpq

所以(suǒyǐ)：當用pq替換pq時，公式A公式B16精品文檔三、等值演算(yǎnsuàn)與置換規則

置換規則：設(A)是含有公式A的命題公式，用公式B置換(A)中所有(suǒyǒu)的A后得到新的命題公式(B)，若AB,則(B)(A)

。17精品文檔三、等值演算(yǎnsuàn)與置換規則

等值演算的基礎：

(1)等值關系的性質：自反、對稱、傳遞

(2)基本的等值式

(3)置換(zhìhuàn)規則18精品文檔例2

：證明(zhèngmíng)三、等值演算(yǎnsuàn)與置換規則19精品文檔三、等值演算(yǎnsuàn)與置換規則例3：證明

p(qr)(pq)r證：

p(qr)p(qr)（蘊涵(yùnhán)等值式，置換規則）

(pq)r

（結合律，置換規則）

(pq)r

（德摩根律，置換規則）

(pq)r

（蘊涵等值式，置換規則）

q(p

r)20精品文檔三、等值演算與置換(zhìhuàn)規則

例4:

和

滿足(mǎnzú)等值關系嗎？21精品文檔三、等值演算(yǎnsuàn)與置換規則蘊涵(yùnhán)等值律蘊涵(yùnhán)等值律德.摩根律分配律排中律、同一律、交換律22精品文檔三、等值演算(yǎnsuàn)與置換規則

例5：通過等值演算判斷(pànduàn)下面三個公式之間的關系23精品文檔24精品文檔三、等值演算(yǎnsuàn)與置換規則雙重(shuāngchóng)否定律

:AA德·摩根律

:(AB)AB

(AB)AB否定(fǒudìng)律25精品文檔三、等值演算與置換(zhìhuàn)規則冪等律：

AAA,AAA排中律:AA1矛盾律:AA0冪等律26精品文檔三、等值演算(yǎnsuàn)與置換規則分配律:A(BC)(AB)(AC)

A(BC)(AB)(AC)分配律27精品文檔三、等值演算(yǎnsuàn)與置換規則

例6：某勘探隊有3名隊員，有一天取得一塊礦樣，3人的判斷如下：甲說：這不是(bùshi)鐵，也不是(bùshi)銅；乙說：這不是鐵，是錫；丙說：這不是錫，是鐵。經實驗室鑒定后發現，其中有一個人的判斷完全正確，有一個人只對了一半，另一個人全錯了。根據這樣的情況判斷礦樣是什么類型？28精品文檔三、等值演算(yǎnsuàn)與置換規則解：令p：礦樣為鐵q：礦樣為銅

r：礦樣為錫29精品文檔三、等值演算與置換(zhìhuàn)規則30精品文檔三、等值演算(yǎnsuàn)與置換規則31精品文檔三、等值演算與置換(zhìhuàn)規則因為礦樣不可能(kěnéng)既是銅又是錫，即q和r不可能同時取得真值1，所以只有即q和r為假命題，p為真命題，礦樣為鐵32精品文檔三、等值演算(yǎnsuàn)與置換規則(1)q(pq)

解：q(pq)

q(pq)

q(pq)例7：用等值演算法判斷(pànduàn)下列公式的類型

p(qq)

p0

0

由最后(zuìhòu)一步可知，該式為矛盾式。33精品文檔三、等值演算與置換(zhìhuàn)規則解:(pq)(qp)

(pq)(qp)

(pq)(pq)1

該式為重言式。(2)(pq)(qp)

(3)((pq)(pq))r)解：((pq)(pq))r)

(p(qq))r

p1r

pr

可滿足(mǎnzú)式。34精品文檔(4)吸收(xīshōu)律可滿足(mǎnzú)式等值演算可以(kěyǐ)用于驗證兩個公式等值，有時也可以(kěyǐ)用于判斷一個公式的類型。35精品文檔內容摘要第二章命題邏輯等值演算。傳遞性，即對任意公式A、B和C，若。令：p：我有時間。判斷兩個公式是否(shìfǒu)為等