L2命題邏輯2 離散數(shù)學(xué)

命題邏輯二LuChaojun,SJTU22主要內(nèi)容命題與命題聯(lián)結(jié)詞命題公式等值演算命題公式的范式聯(lián)結(jié)詞的功能完全集永真蘊(yùn)涵式命題邏輯推理LuChaojun,SJTU3等值關(guān)系一種重要的數(shù)學(xué)論證方法是:將一個(gè)命題用另一個(gè)等值命題替換.兩個(gè)命題公式A和B若在任一賦值下的真值都相同,則稱(chēng)A和B等值(equivalence).記作AB.例如:ab(a)b這兩個(gè)公式語(yǔ)法上是不同的,但語(yǔ)義上相同.LuChaojun,SJTU4與的關(guān)系等值定理:對(duì)公式A和B, AB

iff

AB是永真式證明:若AB永真,則在任一賦值下其真值都為1,依的定義知A和B真值相同.

若AB,則在任一賦值下A和B都有相同的真值,依的定義即AB真值為1.注:教材中干脆用此關(guān)系作為等值的定義.LuChaojun,SJTU5與的不同從形式系統(tǒng)角度看是系統(tǒng)內(nèi)的符號(hào),

AB是系統(tǒng)內(nèi)的命題公式.(語(yǔ)法)是系統(tǒng)外的符號(hào),

AB不是命題公式!在系統(tǒng)外觀察系統(tǒng)內(nèi)兩個(gè)公式是否等值.(語(yǔ)義)從真假性來(lái)看AB是表示A和B是否等值的一個(gè)命題.只有AB為真,才肯定A和B等值.但AB可為假.AB則肯定地表示A和B等值.LuChaojun,SJTU6補(bǔ)充:等值關(guān)系的性質(zhì)和數(shù)學(xué)里的等號(hào)一樣,具有下面三個(gè)性質(zhì):

1.自反性:

A

A 2.對(duì)稱(chēng)性:若A

B,

則B

A 3.傳遞性:若A

B且B

C,則A

C這三條性質(zhì)刻畫(huà)了兩事物“等同”、“同一性”概念.滿足這三條性質(zhì)的關(guān)系稱(chēng)為等價(jià)關(guān)系.在等值概念下,命題常量可看成只有兩個(gè):1,06LuChaojun,SJTU7如何證明兩公式等值?真值表技術(shù)利用等值定理利用基本等值式進(jìn)行等值演算7LuChaojun,SJTU8例:利用真值表證明等值證明(aa)b

b.證:列出真值表即可看出等式成立.abaa(aa)b0000010110001101LuChaojun,SJTU9例:利用等值定理證明等值證明(ab)

(ab).根據(jù)等值定理,可轉(zhuǎn)化為證明 (ab)(ab)是永真式.比如列出此公式的真值表.這樣本質(zhì)上還是真值表技術(shù).還可利用重言式推理系統(tǒng).9LuChaojun,SJTU10基本等值式1.結(jié)合律 (AB)C

A(BC) (AB)C

A(BC) (A

B)

C

A

(B

C)2.交換律

AB

BA

AB

BA

A

B

B

A

注意:沒(méi)有的結(jié)合律和交換律.

LuChaojun,SJTU11基本等值式(續(xù))3.分配律

A(BC)(AB)(AC)

A(BC)(AB)(AC)

A(BC)(AB)(AC)4.吸收律

A(AB)

A

A(AB)

ALuChaojun,SJTU12基本等值式(續(xù))5.關(guān)于否定詞的等值式

(A)

A (對(duì)合律) (AB)

AB (DeMorgan律)

(AB)

AB (DeMorgan律)

(AB)

A

B

(AB)

AB

AB

(AB)(AB)基本等值式(續(xù))6.相同命題變量的等值式AA

A(等冪律)AA

A(等冪律)AA

1AA

1AA

1(排中律)AA

0(矛盾律)AA

AAA

AAA

0此處的1/0代表任意真值恒為1/0的命題公式.LuChaojun,SJTU13LuChaojun,SJTU14基本等值式(續(xù))7.部分賦值的等值式 A0

A A1

A

1A

A A0

A

1A

A

0A

A

A11

A00

A11 0A

114LuChaojun,SJTU15基本等值式(續(xù))8.關(guān)于的等值式AB

(A)B

(AB)AB

BA[假言易位]A(BC)(AB)C[合取前提]A(BC)

B(AC)[交換前提](AC)(BC)(AB)C[析取前提](AB)(AB)

A[歸謬論]A(BC)(AB)(AC)A(BC)(AB)(AC)基本等值式(續(xù))9.關(guān)于的等值式AB

ABAB

(AB)(AB)[同真或同假]AB

(AB)(AB)[一真一假]AB

(AB)(BA)[充分必要]由于,,更易理解和處理,常利用8和9類(lèi)的等值式將含和的公式改寫(xiě)成僅含有,,的公式.LuChaojun,SJTU16置換規(guī)則定理:設(shè)AA,BB,則有(1)

AA(2)AB

AB(3)AB

AB(4)AB

AB(5)AB

AB置換:將公式的一部分用等值公式替換.定理(置換規(guī)則):設(shè)BC.若將A中出現(xiàn)的一個(gè)或幾個(gè)B換成C后得到公式A,則有AA.LuChaojun,SJTU17LuChaojun,SJTU18等值演算等值演算:利用等值定律,基本等值式以及替換規(guī)則進(jìn)行公式推演.一般是將兩邊的公式推演成相同形狀的公式,從而證明等值式成立.例:等值演算證明(a(bc))(bc)(ac)

c.證明:左端(a(bc))((ba)c) (分配律)

((ab)c)((ba)c)

(結(jié)合律)

((ab)c)((ba)c) (德摩根律)

((ab)(ba))c

(分配律)

((ab)(ab))c

(交換律)

1c (置換)

cLuChaojun,SJTU19LuChaojun,SJTU20對(duì)偶式和內(nèi)否式觀察下面兩個(gè)等值式(分配律):A(BC)(AB)(AC)A(BC)(AB)(AC)可見(jiàn),命題邏輯公式存在“對(duì)偶”規(guī)律.限制性公式:公式中只用到聯(lián)結(jié)詞,,.將限制性公式A中的,,1,0分別以,,0,1替換,所得公式稱(chēng)為A的對(duì)偶式A*.

將限制性公式A中所有肯定形式出現(xiàn)的變?cè)獂換成x,所有否定形式出現(xiàn)的變?cè)獂換成x,所得公式稱(chēng)為A的內(nèi)否式A－.其實(shí),求A－時(shí)A不必是限制性公式,即可包含和.LuChaojun,SJTU21A*和A－的性質(zhì)定理(1)(A*)*

A (A－)－

A(2)(AB)*A*B* (AB)－A－B－(3)(AB)*A*B* (AB)－A－B－定理(1)(A)*(A*) (A)－

(A－)(2)A

(A*)－(DeMorgan律的一般形式)(3)(A*)－(A－)*LuChaojun,SJTU22命題公式的對(duì)偶性質(zhì)推論:若AB,則(A*)－(B*)－.推論:若AB,則

A*B*.一旦證明了兩公式等值,則同時(shí)證明了它們的對(duì)偶式也等值.LuChaojun,SJTU2323主要內(nèi)容命題與命題聯(lián)結(jié)詞命題公式等值演算命題公式的范式聯(lián)結(jié)詞的功能完全集永真蘊(yùn)涵式命題邏輯推理LuChaojun,SJTU24公式有沒(méi)有標(biāo)準(zhǔn)形式?命題公式的數(shù)量是無(wú)窮多的.即便只有一個(gè)命題變量x,也可以寫(xiě)出x,xx,xxx,x

xxx,……但若按等值關(guān)系對(duì)全體公式進(jìn)行劃分,n個(gè)命題變量所能形成的不同公式僅有22n個(gè).(Why?)問(wèn)題:與命題公式A等值的公式能否都化為某種標(biāo)準(zhǔn)形式?借助于標(biāo)準(zhǔn)形容易判斷兩個(gè)公式是否等值.借助于標(biāo)準(zhǔn)形容易判斷公式是否永真式或永假式.LuChaojun,SJTU25簡(jiǎn)單析(合)取式一個(gè)命題符號(hào)a及其否定a統(tǒng)稱(chēng)為文字.由文字利用()聯(lián)結(jié)而成的公式稱(chēng)為簡(jiǎn)單析(合)取式.簡(jiǎn)單析取式例:x,x,xy,xyx簡(jiǎn)單合取式例:x,x,xy,xyx定理(1)一個(gè)簡(jiǎn)單析取式是永真式iff它同時(shí)包含一個(gè)命題符號(hào)及其否定.(2)一個(gè)簡(jiǎn)單合取式是矛盾式iff它同時(shí)包含一個(gè)命題符號(hào)及其否定.析(合)取范式由若干個(gè)簡(jiǎn)單合取式利用聯(lián)結(jié)而成的公式稱(chēng)為析取范式.形如:

A1

A2

…An(諸Ai是簡(jiǎn)單合取式)由若干個(gè)簡(jiǎn)單析取式利用聯(lián)結(jié)而成的公式稱(chēng)為合取范式.形如:A1

A2

…An(諸Ai是簡(jiǎn)單析取式)定理(1)一個(gè)析取范式是矛盾式iff它的每個(gè)簡(jiǎn)單合取式都是矛盾式.(2)一個(gè)合取范式是永真式iff它的每個(gè)簡(jiǎn)單析取式都是永真式.LuChaojun,SJTU26LuChaojun,SJTU27范式存在定理及求法范式定理:對(duì)任一命題公式都存在與之等值的析取范式和合取范式.等值變換法求范式(1)消去,(2)深入到命題符號(hào)之前(3)()深入至此已是范式.(4)

(可選)化簡(jiǎn)27LuChaojun,SJTU28求范式(1):消去,方法:利用下列等值式AB

AB

AB

(AB

)(AB

) [用于求析取范式]AB

(AB

)(AB

) [用于求合取范式]例:求(xy)(xy)的析取范式(xy)(xy)((xy)(xy))((xy)(xy))28LuChaojun,SJTU29求范式(2):否定詞深入方法:利用下列等值式(A

B

)

A

B

(A

B

)

A

BA

A例 (xy)(xy)((xy)(xy))((xy)(xy))

(xy

xy)((xy)(xy))29LuChaojun,SJTU30求范式(3):合(析)取詞深入方法:利用分配律A(BC)(AB)(AC)[用于求析取范式]A(BC)(AB)(AC)[用于求合取范式]例 (xy)(xy)((xy)(xy))((xy)(xy))

(xyxy)((xy)(xy))(xy

xy)

(xx)(xy)(yx)(yy)30LuChaojun,SJTU31求范式(4):(可選)化簡(jiǎn)方法:利用下列等值式消去矛盾式A

0

0A

0

A例 (xy)(xy)((xy)(xy))((xy)(xy))

(xyxy)((xy)(xy))(xy

xy)(xx)(xy)(yx)(yy)(xy)(xy)31LuChaojun,SJTU32范式的用途判斷A是否永真式求A的合取范式,若每個(gè)簡(jiǎn)單析取式都含有某個(gè)變?cè)捌浞穸?如x和x),則A是永真式.判斷A是否矛盾式求A的析取范式,若每個(gè)簡(jiǎn)單合取式都含有某個(gè)變?cè)捌浞穸?如x和x),則A是矛盾式.判斷A

B?求A和B的同一種范式,看是否相同.這里有問(wèn)題:范式唯一嗎?32LuChaojun,SJTU33極小項(xiàng)與極大項(xiàng)設(shè)公式只涉及n個(gè)命題變量x1,…,

xn.極小項(xiàng):n個(gè)文字的簡(jiǎn)單合取式,諸xi以xi或xi形式出現(xiàn)且只出現(xiàn)一次,且xi出現(xiàn)在左起第i個(gè)位置.極小項(xiàng)有2n個(gè):根據(jù)對(duì)應(yīng)的成真賦值,可記為m0…00=x1

…xn1

xnm0…01=x1

…xn1

xnm0…10=x1

…xn1

xn…m1…11=x1

…xn1

xn設(shè)公式只涉及n個(gè)命題變量x1,…,

xn.極大項(xiàng):n個(gè)文字的簡(jiǎn)單析取式,諸xi以xi或xi形式出現(xiàn)且只出現(xiàn)一次,且xi出現(xiàn)在左起第i個(gè)位置.極大項(xiàng)有2n個(gè):根據(jù)對(duì)應(yīng)的成假賦值,可記為M0…00=x1

…

xn1

xnM0…01=x1

…

xn1xnM0…10=x1

…xn1xn…M1…11=x1…xn1xnLuChaojun,SJTU34極小/大項(xiàng)的性質(zhì)每個(gè)極小項(xiàng)只在一個(gè)賦值下為真.一個(gè)賦值不能使兩個(gè)極小項(xiàng)都為真.兩個(gè)極小項(xiàng)的合取為0極小項(xiàng)兩兩不等值.若A由k個(gè)極小項(xiàng)的析取組成,則其余2nk個(gè)極小項(xiàng)的析取就是A.若k=2n,則A是重言式.每個(gè)極大項(xiàng)只在一個(gè)賦值下為假.一個(gè)賦值不能使兩個(gè)極小項(xiàng)都為假.兩個(gè)極大項(xiàng)的析取為1極大項(xiàng)兩兩不等值.若A由k個(gè)極大項(xiàng)的合取組成,則其余2n

k個(gè)極大項(xiàng)的合取就是A.若k=2n,則A是矛盾式.34LuChaojun,SJTU35主范式主析取范式:僅由極小項(xiàng)構(gòu)成的析取范式.定理:任何非永假的命題公式都存在唯一與之等值的主析取范式.主合取范式:僅由極大項(xiàng)構(gòu)成的合取范式.定理:任何非永真的命題公式都存在唯一與之等值的主合取范式.LuChaojun,SJTU36主范式的求法(1)利用基本等值式(1)先求一個(gè)析取范式.(2)若簡(jiǎn)單合取式A中未出現(xiàn)命題變量x,則通過(guò)AA(xx)

(Ax)(Ax)來(lái)補(bǔ)足x.(3)消去重復(fù)出現(xiàn)的變量,矛盾式及重復(fù)出現(xiàn)的極小項(xiàng).利用基本等值式(1)先求一個(gè)合取范式.(2)若簡(jiǎn)單析取式A中未出現(xiàn)命題變量x,則通過(guò)AA(xx)

(Ax)(Ax)來(lái)補(bǔ)足x.(3)消去重復(fù)出現(xiàn)的變量,永真式及重復(fù)出現(xiàn)的極大項(xiàng).36LuChaojun,SJTU37例:基本等值式方法例:求xy的主析取范式(1)xyxy(2)x

x

(yy)(xy)(xy)y

y(xx)

(xy)(xy)(3)消去一個(gè)(xy)于是:xy

m00

m01m11例:求(xy)的主合取