《逻辑与证明2.ppt》由会员分享，可在线阅读，更多相关《逻辑与证明2.ppt（18页珍藏版）》请在三一文库上搜索。
1、逻辑与证明(2),南京大学离散数学教学组,命题表达式及其真值确定,命题表达式的递归定义： 命题变元是命题表达式 若A是命题表达式，则（A）也是命题表达式。 若A和B均是命题表达式，则（AB), (AB), (AB), (AB)均是命题表达式。 只有有限次应用上述规则形成的符号串才是命题表达式。 例子： (pq)(qr), p(qr)是命题表达式 pqr, pq不是命题表达式。,命题表达式的真值确定,表达式：(pq)r,p q r,0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1,1 1 1 1 0 0 0 0,0 0 1 1 0 0 0 0,1 0
2、 1 0 1 0 1 0,(pq)r,1 1 1 0 1 1 1 1,重言式、矛盾式与可能式,所有指派均为成真指派：重言式 (pq)(qp) 对任意的p,q值均为1，为重言式。 所有指派均为成假指派：矛盾式 pp 对任意的p值均为0，为矛盾式。 同时存在成真和成假指派：可能式 (pq)(pq): 成真指派：(p,q) = (1,1) or (0,1) 成假指派：(p,q) = (1,0) or (0,0),逻辑等价,p q,0 0 0 1 1 0 1 1,pq,qp,1 1 0 1,1 0 1 1,(pq)(qp),1 0 0 1,(pq) (pq)(qp),pq,1 0 0 1,(pq) (
3、pq)(qp),1 1 1 1,双蕴含连接符连接的命题表达式，如果所有指派均成真， 称该符号连接的两个命题表达式逻辑等价，并记为： AB,(pq) (pq)(qp),常用的逻辑等价(1),名称 等价 双重否定律 A A 幂等律 AAA, AAA 交换律 ABBA, ABBA 结合律 (AB)CA(BC) (AB)CA(BC) 分配律 A(BC)(AB)(AC) A(BC)(AB)(AC) 德摩根律 (AB)AB (AB)AB 吸收律 A(AB)A A(AB)A,常用的逻辑等价(2),名称 等价 支配律 A11, A00 恒等律 A0A, A1A 排中律 AA 1 矛盾律 AA 0 ABAB A
4、B(AB)(B A) 假言易位 ABBA ABBA 归缪论 (AB)(AB)A,否定律,置换规则-等价式的应用,逻辑等价式在逻辑演算(表达式推演)和证明中起重要作用。 置换规则：设(A)是含表达式A的命题表达式，(B)是用表达式B置换了(A)中所有的A后得到的表达式。若B A, 则(B) (A)。,逻辑等价的判定,(pq)和pq是否逻辑等价？ (pq) (pq) (p) q p q,pq pq是否永真？ pq pq (pq) (pq) (p q) (pq) pp q q T,命题符号化若干例,符号化下列命题： 只有计算机系学生和老师，才能参加迎新晚会 几点提醒： 复合命题的“原子命题”及其内部
5、逻辑连接！ 自然语言有一定的歧义，注意观察和分析！,命题符号化若干例,验证下列系统规格说明是否一致： 如果文件系统未加锁，那么新消息将被排成队 如果文件系统未加锁，则系统处于正常运行，反之亦然； 如果新消息尚未入队，就应该送入缓冲区； 如果文件系统未加锁，新消息将被送入缓冲区； 新消息不应被送入缓冲区,命题符号化及其应用,We know that Bill, Jim and Sam are from Boston, Chicago and Detroit, respectively. Each of following sentence is half right and half wrong
6、: Bill is from Boston, and Jim is from Chicago. Sam is from Boston, and Bill is from Chicago. Jim is from Boston, and Bill is from Detroit. Tell the truth about their home town.,命题符号化及其应用,We set : P1 = Bill is from Boston P2 = Jim is from Chicago. P3 = Sam is from Boston P4 = Bill is from Chicago. P
7、5 = Jim is from Boston P6 = Bill is from Detroit. So, We have: (p1 p2) (p1p2) (p3 p4) (p3p4) (p5 p6) (p5p6) 应该可满足,等价替换： (p1 p2)(p1p2) (p3 p4) (p3p4) (p1 p2)(p1p2) (p3 p4)(p1 p2)(p1p2) (p3p4) (p1 p2p3 p4) (p1p2p3 p4) (p1 p2p3p4) (p1p2p3p4) F(p1p2p3 p4) FF p1p2p3 p4 继续： (p1p2p3 p4)(p5p6)(p5p6) (p1p2p3
8、 p4p5p6) 可满足 So, Jim is from Chicago, Sam is from Boston, and Bill is from Detroit.,命题符号化及其应用,由题意,析取范式,析取（合取）范式的存在性,求 (pq) r 的析取范式 (pq) r （消去） (pq) r) (pq) r ) （消去 ） (pq) r) ( (p q) r ) （否定号内移） (p r) (q r) (pqr ) （分配律、结合律）,主析取（合取）范式的唯一性,求 (pq) r 的主析取范式 (p r) (q r) (pqr ) （析取范式） (p q r) (p q r) (p q r) (p qr ) (p q r) (p q r) (pqr) (p q r) 001 011 100 111,p r p (q q) r (p q r ) (p q r ) q r ( p q r ) (p q r ),逻辑等价的判定,命题逻辑等价的可判定性 基于主析取（合取）范式的唯一性 指数级复杂性 命题表达式的可满足性 能否找到一个命题表达式的成真指派？ 第一个被证明是NP难的问题,逻辑与证明,教材：1.2；1.3；1.4 习题： P34：10,24(任选3题),34,42 P43：6(任选3题),16,44,