L2命題邏輯2 離散數學

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

iff

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

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

AB是系統(tǒng)內的命題公式.(語法)是系統(tǒng)外的符號,

AB不是命題公式!在系統(tǒng)外觀察系統(tǒng)內兩個公式是否等值.(語義)從真假性來看AB是表示A和B是否等值的一個命題.只有AB為真,才肯定A和B等值.但AB可為假.AB則肯定地表示A和B等值.LuChaojun,SJTU6補充:等值關系的性質和數學里的等號一樣,具有下面三個性質:

1.自反性:

A

A 2.對稱性:若A

B,

則B

A 3.傳遞性:若A

B且B

C,則A

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

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

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

A(BC) (AB)C

A(BC) (A

B)

C

A

(B

C)2.交換律

AB

BA

AB

BA

A

B

B

A

注意:沒有的結合律和交換律.

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.關于否定詞的等值式

(A)

A (對合律) (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.關于的等值式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.關于的等值式AB

ABAB

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

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

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

AA(2)AB

AB(3)AB

AB(4)AB

AB(5)AB

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

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

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

(結合律)

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

((ab)(ba))c

(分配律)

((ab)(ab))c

(交換律)

1c (置換)

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

將限制性公式A中所有肯定形式出現的變元x換成x,所有否定形式出現的變元x換成x,所得公式稱為A的內否式A－.其實,求A－時A不必是限制性公式,即可包含和.LuChaojun,SJTU21A*和A－的性質定理(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命題公式的對偶性質推論:若AB,則(A*)－(B*)－.推論:若AB,則

A*B*.一旦證明了兩公式等值,則同時證明了它們的對偶式也等值.LuChaojun,SJTU2323主要內容命題與命題聯結詞命題公式等值演算命題公式的范式聯結詞的功能完全集永真蘊涵式命題邏輯推理LuChaojun,SJTU24公式有沒有標準形式?命題公式的數量是無窮多的.即便只有一個命題變量x,也可以寫出x,xx,xxx,x

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

A1

A2

…An(諸Ai是簡單合取式)由若干個簡單析取式利用聯結而成的公式稱為合取范式.形如:A1

A2

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

(可選)化簡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):(可選)化簡方法:利用下列等值式消去矛盾式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的合取范式,若每個簡單析取式都含有某個變元及其否定(如x和x),則A是永真式.判斷A是否矛盾式求A的析取范式,若每個簡單合取式都含有某個變元及其否定(如x和x),則A是矛盾式.判斷A

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

xn.極小項:n個文字的簡單合取式,諸xi以xi或xi形式出現且只出現一次,且xi出現在左起第i個位置.極小項有2n個:根據對應的成真賦值,可記為m0…00=x1

…xn1

xnm0…01=x1

…xn1

xnm0…10=x1

…xn1

xn…m1…11=x1

…xn1

xn設公式只涉及n個命題變量x1,…,

xn.極大項:n個文字的簡單析取式,諸xi以xi或xi形式出現且只出現一次,且xi出現在左起第i個位置.極大項有2n個:根據對應的成假賦值,可記為M0…00=x1

…

xn1

xnM0…01=x1

…

xn1xnM0…10=x1

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

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

(Ax)(Ax)來補足x.(3)消去重復出現的變量,矛盾式及重復出現的極小項.利用基本等值式(1)先求一個合取范式.(2)若簡單析取式A中未出現命題變量x,則通過AA(xx)

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

x

(yy)(xy)(xy)y

y(xx)

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

m00

m01m11例:求(xy)的主合取