離散數(shù)學(xué)：第一章1-3 等值演算

1第一章命題邏輯

1.1命題符號(hào)化及聯(lián)結(jié)詞1.2命題公式及分類(lèi)1.3等值演算1.4聯(lián)結(jié)詞全功能集1.5對(duì)偶與范式1.6推理理論2§3等值演算

一、等值式二、基本等值式三、等值演算與置換規(guī)則四、應(yīng)用舉例3一、等值式

定義若等價(jià)式A

B是重言式，則稱(chēng)A與B等值，記作A

B，并稱(chēng)A

B是等值式。┐(pVq)與┐pV┐q┐(pVq)與┐p∧┐q注:不是邏輯聯(lián)結(jié)詞，表示對(duì)任意的賦值，A與B的值相同。?是等價(jià)聯(lián)結(jié)詞，它與不能混為一談。4真值表法（1）pq┐p┐qpVq┐(pVq)┐pV┐q0011011011010110011011100100┐(pVq)與┐pV┐q不等值5真值表法（2）pq┐p┐ppVq┐(pVq)┐p∧┐q0011011011010010011001100100┐(pVq)與┐p∧┐q等值6二、基本等值式序號(hào)等值式定律1A

┐┐A雙重否定2AAVA等冪律3A

A∧A4AVB

BVA交換律5A∧BB∧A6(AVB)VCA(VBVC)結(jié)合律7(A∧B)∧CA∧(B∧C)8AV(B∧C)(AVB)∧(AVC)分配律9A∧(BVC)(A∧B)V(A∧C)7基本等值式（2）序號(hào)等值式定律10┐(AVB)

┐A∧┐B德.摩根律11┐(A∧B)

┐AV

┐B12AV(A∧B)A吸收律13A∧(AVB)A14AV11零律15A∧0016AV0A同一律17A∧1A18AV

┐A1排中律19A∧┐A0矛盾律8基本等值式（3）序號(hào)等值式定律20A→B┐AVB蘊(yùn)涵等值式(真值表)21A?B(A→B)∧(B→A)等價(jià)等值式22A→B

┐B→┐A假言易位(逆否命題)23A?B┐A?

┐B等價(jià)否定等值式24(A→B)∧(A→┐B)┐A歸繆論9三、等值演算與置換規(guī)則

等值演算:

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

B,則

(A)

(B)

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

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

(2)基本的等值式

(3)置換規(guī)則

10四、應(yīng)用舉例——驗(yàn)證等值式驗(yàn)證下列等值式:p→(q→r)

(p∧q)→r（P10例1.9(1))

p→(q→r)┐p∨(q→r)（蘊(yùn)涵等值式)

┐p∨(┐q∨r)（蘊(yùn)涵等值式)

(┐p∨┐q)∨r（結(jié)合律）┐(p∧q)∨r（德

摩根律）(p∧q)→r（蘊(yùn)涵等值式)

(p∧q)→r

┐(p∧q)∨r

(┐p∨┐q)∨r

┐p∨(┐q∨r)

┐p∨(q→r)p→(q→r)11驗(yàn)證等值式（續(xù)）驗(yàn)證下列等式:

p

(p∧q)∨(p∧┐q)（P10例1.9(2))

p

p∧1（同一律）

p∧(q∨┐q)（排中律）

(p∧q)∨(p∧┐q)（分配律）12四、應(yīng)用舉例——判斷公式類(lèi)型

例3

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

(p

q)

解q

(p

q)

q

(

p

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

q

(p

q)（德

摩根律）

p

(q

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

p

0（矛盾律）

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

13例3(續(xù))(2)(p

q)

(

q

p)解

(p

q)

(

q

p)

(

p

q)

(q

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

(

p

q)

(

p

q)（交換律）

1由最后一步可知，該式為重言式.14例3(續(xù))(3)((p

q)

(p

q))

r)解((p

q)

(p

q))

r)

(p

(q

q))

r

（分配律）

p

1

r

（排中律）

p

r

（同一律）這不是矛盾式，也不是重言式，而是非重言式的可滿足式.如101是它的成真賦值,000是它的成假賦值.總結(jié)：A為矛盾式當(dāng)且僅當(dāng)A

0A為重言式當(dāng)且僅當(dāng)A

1說(shuō)明：演算步驟不惟一,應(yīng)盡量使演算短些例用等值演算法解決下面問(wèn)題。