逻辑与证明2.ppt
《逻辑与证明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,命题符号化若干例,符号化下列命题: 只有计算机系学生和老师,才能参加迎新晚会 几点提醒: 复合命题的“原子命题”及其内部
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 逻辑 证明
链接地址:https://www.31doc.com/p-2618216.html