離散數(shù)學(xué)命題邏輯續(xù)

1、命題邏輯（續(xù)）離散數(shù)學(xué)邏輯和證明大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系內(nèi)容提要式命題等價(jià)命題的范式命題等價(jià)的判定命題的可滿足性推理規(guī)則及論證命題表達(dá)式的真值表(pq) (pq)(qp)(pq) (pq)(qp)pp(pq)(qp)pqpq1001100111110011010111011011式、式與可能式式（重言式）：總是真的，無論其中出現(xiàn)如何取值。比如：pp題變元式：總是比如： pp可能式：既不是，無論其中出現(xiàn)題變元如何取值。式又不是式。比如： pp ppppp10011100邏輯等價(jià)p和q邏輯等價(jià)：在所有可能情況下p和q都有相同的真值。也就是說，pq是式。記法：p q，或者p qpq (pq)(qp)p

2、q (pq)(qp)pp Tpp F常用的邏輯等價(jià)(1)名稱等價(jià)雙重否定律交換律分配律德律吸收律A AAB BA, AB BAA(BC) (AB)(AC)A(BC) (AB)(AC)(AB) AB(AB) AB A(AB) A A(AB) A結(jié)合律(AB)C A(BC)(AB)C A(BC)冪等律A AA, A AA常用的邏輯等價(jià)(2)否定律名稱等價(jià)支配律恒等律排中律律假言易位AT T, AF F AF A, AT A AA TAA F AB ABAB BAAB BA歸繆論(AB)(AB) AAB (AB)(B A)邏輯等價(jià)的判定(pq)和pq是否邏輯等價(jià)？(pq) (pq) (p) q p

3、qpq pq是否？pq pq (pq) (pq) (p q) (pq) pp q q T通過邏輯等價(jià)進(jìn)行推理（續(xù)）We knowt Bill, Jim and Sam are fromton, Chicagoand Detroit, respectively. Each of following sentence is half right and half wrong:Bill is from Sam is from Jim is froml the truton, and Jim is from Chicago. ton, and Bill is from Chicago. ton, an

4、d Bill is from Detroit.bout their home town.通過邏輯等價(jià)進(jìn)行推理（續(xù)）We set :P1 = Bill is fromtonP2 = Jim is from Chicago.P3 = Sam is fromtonP4 = Bill is from Chicago.P5 = Jim is fromtonP6 = Bill is from Detroit.So, We have:(p1 p2) (p1p2) (p3 p4) (p3p4) (p5p6) (p5p6) True通過邏輯等價(jià)進(jìn)行推理（續(xù)）We have: (p1p2)(p1p2)(p3p4)

5、(p3p4)(p5p6)(p5p6) Note: (p1 p2)(p1p2) (p3 p4) (p3p4) (p1p2p3 p4)And (p1p2p3 p4)(p5p6)(p5p6) (p1p2p3 p4p5p6) TSo, Jim is from Chicago, Sam is from Detroit.Note: Normal Formton, and Bill is from析?。ê先。┓妒降拇嬖谛郧?(pq) r 的析取范式(pq) r(pq) r) (pq) r )(pq) r) ( (p q) r )(p r) (q r) (pqr )（消去）（消去 ）（否定號內(nèi)移）（分配律、結(jié)

6、合律）主析?。ê先。┓妒降奈ㄒ恍郧?(pq) r 的主析取范式(p r) (q r) (pqr ) （析取范式）p r p (q q) r (p q r ) (p q r )q r ( p q r ) (p q r )(p q r) (p q r) (p q r) (p qr )(p q r) (p q r) (pqr) (p q r)001011100111邏輯等價(jià)的判定命題邏輯等價(jià)的可判定性基于主析?。ê先。┓妒降奈ㄒ恍赃€沒有（在情況下）時(shí)間復(fù)雜性為多項(xiàng)式的算法命題表達(dá)式的可滿足性轉(zhuǎn)化為命題的邏輯等價(jià)問題p T ?Sudoku謎題（九宮格數(shù)獨(dú)3232的網(wǎng)格，32個(gè)33的子網(wǎng)格。每行、每列及

7、每宮填入數(shù)字1-9且不能重復(fù)。）4 294541442675735196Sudoku謎題（命題可滿足問題）p(i, j, n): 第i行第j列的格子里填上數(shù)字n.i=19 n=19j=19j=19 n=19i=19p(i, j, n) Tp(i, j, n) Tr=02 s=02n=19i=13j=13i =19j =19n =19n =19, nnp(3r+i, 3s+j, n) T(p(i, j, n)p(i, j, n) F設(shè)計(jì)Sudoku謎題，使得它有唯一解。命題邏輯的推理規(guī)則1. A ( A B)2. ( A B) A附加化簡4. A B,B A5. A B,B A取拒式析取7. A B,A C B C消解假言6. A B, B C A C假言推理3. A B, A B用推理規(guī)則建立論證“今天下午出并且比昨天冷”，“只有今天下午出太陽，才去游泳”，“若不去游泳，則乘獨(dú)在黃昏時(shí)回木舟游覽”，“若家”，結(jié)論“乘獨(dú)木舟游覽，則在黃昏時(shí)回家”。，q: 今天比昨天冷，r:p: 今天下午出去游泳，s:p qr p乘獨(dú)木舟游覽，t:在黃昏時(shí)回家r ss tp化簡r取拒式假言推理假言推理用推理規(guī)則建立論證已知(pq)r和 r sps 是否為真？(pq)r (p