离散数学命题逻辑续

1、命题逻辑（续）离散数学逻辑和证明大学计算机科学与技术系内容提要式命题等价命题的范式命题等价的判定命题的可满足性推理规则及论证命题表达式的真值表(pq) (pq)(qp)(pq) (pq)(qp)pp(pq)(qp)pqpq1001100111110011010111011011式、式与可能式式（重言式）：总是真的，无论其中出现如何取值。比如：pp题变元式：总是比如： pp可能式：既不是，无论其中出现题变元如何取值。式又不是式。比如： pp ppppp10011100逻辑等价p和q逻辑等价：在所有可能情况下p和q都有相同的真值。也就是说，pq是式。记法：p q，或者p qpq (pq)(qp)p

2、q (pq)(qp)pp Tpp F常用的逻辑等价(1)名称等价双重否定律交换律分配律德律吸收律A AAB BA, AB BAA(BC) (AB)(AC)A(BC) (AB)(AC)(AB) AB(AB) AB A(AB) A A(AB) A结合律(AB)C A(BC)(AB)C A(BC)幂等律A AA, A AA常用的逻辑等价(2)否定律名称等价支配律恒等律排中律律假言易位AT T, AF F AF A, AT A AA TAA F AB ABAB BAAB BA归缪论(AB)(AB) AAB (AB)(B A)逻辑等价的判定(pq)和pq是否逻辑等价？(pq) (pq) (p) q p

3、qpq pq是否？pq pq (pq) (pq) (p q) (pq) pp q q T通过逻辑等价进行推理（续）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.通过逻辑等价进行推理（续）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通过逻辑等价进行推理（续）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 )（消去）（消去 ）（否定号内移）（分配律、结

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逻辑等价的判定命题逻辑等价的可判定性基于主析取（合取）范式的唯一性还没有（在情况下）时间复杂性为多项式的算法命题表达式的可满足性转化为命题的逻辑等价问题p T ?Sudoku谜题（九宫格数独3232的网格，32个33的子网格。每行、每列及

7、每宫填入数字1-9且不能重复。）4 294541442675735196Sudoku谜题（命题可满足问题）p(i, j, n): 第i行第j列的格子里填上数字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设计Sudoku谜题，使得它有唯一解。命题逻辑的推理规则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用推理规则建立论证“今天下午出并且比昨天冷”，“只有今天下午出太阳，才去游泳”，“若不去游泳，则乘独在黄昏时回木舟游览”，“若家”，结论“乘独木舟游览，则在黄昏时回家”。，q: 今天比昨天冷，r:p: 今天下午出去游泳，s:p qr p乘独木舟游览，t:在黄昏时回家r ss tp化简r取拒式假言推理假言推理用推理规则建立论证已知(pq)r和 r sps 是否为真？(pq)r (p