当前位置： >>
交大数理逻辑课件2-1 命题逻辑的等值和推理演算
请交作业1第2章 命题逻辑的等值和推理演算2.1 等值定理 2.2 等值公式 2.3 命题公式与真值表的关系 2.4 联结词的完备集 2.5 对偶式讨论等值演算2.6 范式2.7 推理形式 2.8 基本的推理公式 2.9 推理演算 2.10 归结推理法 讨论推理演算公式的类型定义 设A为一个合式公式 (1) 若A无成假赋值，则称A为重言式(也称永真式) (2) 若A无成真赋值，则称A为矛盾式(也称永假式) (3) 若A不是矛盾式，则称A为可满足式P Q 0 0 1 1 0 1 0 1P ?Q (P ?Q)? (?P ? Q) 1 1 0 1 1 1 1 1? (?P ? Q) ? Q0 0 0 0可满足式永真式矛盾式2.1 等值定理? 等价的定义? 设A和B是两个命题公式，对A和B的任一赋值，A和 B的真值都相同，则称A和B是等值的（或等价的）， 记为A = B 或A?B? 注意：?是关系符， ?是联结词?显然，根据真值表可判明任何两个公式是否等值? 如 ?(P?Q) 与 ?P ? ?Q 和 ?P ? ?Q P Q ? P ? Q P ? Q ?(P ? Q) ?P ? ? Q ?P ?? Q0 0 1 10 1 0 11 1 0 01 0 1 00 1 1 11 0 0 01 1 1 01 0 0 0等值定理? 等值定理对公式A和B， A=B的充分必要条件是A?B是重言式? 即若A?B是重言式，则在任一解释下，A和B都 只能有相同的真值A B A ?B? 命题公式的等值关系“=”有下面的性 质：0 0 1 10 1 0 11 0 0 11. 自反性―― ? A=A 对任意命题公式A， 2. 对称性―― B和C ? 若A = B，则B = A 3. 传递性―― ? 若A = B，B = C，则A = C2.2 等值公式1. 基本的等值公式（命题定律）A,B,C代表任意的 命题公式双重否定律 : ? ?A = A等幂律： 交换律:A?A = A,A?A = T，A?A = AA?A = TA?B = B?A,A?B = B?A A?B = B?A， A?B ≠ B?A2.2 等值公式1. 基本的等值公式（命题定律）结合律:(A?B)?C = A?(B?C) ,(A?B)?C = A?(B?C) (A?B)?C = A?(B?C), (A?B)?C ≠ A?(B?C)A,B,C代表任意的 命题公式分配律:A?(B?C) = (A?B)?(A?C),A?(B?C) = (A?B)?(A?C)A?(B?C) = (A?B) ?(A?C)A ?(B ? C) ≠ (A ? B) ? (A ? C)等值公式1. 基本的等值公式（命题定律）摩根律 : 吸收律: 零律: 同一律: 补余律: ?(A?B) = ?A??B，A,B代表任意 的命题公式?(A?B) = ?A??BA?(A?B) = A, A?T = T, A?F = A, A?(A?B) = A A?F = F A?T = AT?A = A， T ? A = A， A??A = T， A??A = F，等值公式2. 常用等值公式? A?B = ?A?B （由联结词的真值表得） ? A?(B?C) = (A∧B) ?CA,B代表任意 的命题公式? A?B = ?B??A （由逆否命题=原命题得） ? A?B = (A∧B)?(?A∧?B) （由联结词的真值表得）? A?B = (A∨?B)?(?A∨B)? A?B = (A?B)?(B?A) (由联结词的定义得)? A?(B?C) = B?(A?C) （前提条件可交换次序） ? (A?C)?(B?C) = (A?B) ?C基本等值公式的证明举例? 原则上说，上面的公式均可用真值表证明。下面 仅验证摩根律。?(A∨B) = ?A∧?BA 0 0 1 1 B 0 1 0 1 ?A 1 1 0 0 ?B 1 0 1 0 ?A∧?B 1 0 0 0 A∨B 0 1 1 1 ? (A∨B) 1 0 0 0等值演算与置换规则? 置换――对公式A的子公式，用与之等值的公式代换。? 置换规则公式A的子公式置换后，A化为公式B，必有A = B? 等值演算? 由已知的等值公式推演出新的等值公式的过程 ? 如已知: A?A = A 则: B?A?A = B?A? 等值演算的基础： (1) 等值关系的性质：自反、对称、传递(2) 基本的等值式(3) 置换规则三个重要的等值式P ?Q = ?P ? Q P ? Q = (P ? Q) ? (? P ? ? Q )P?Q = (P?Q)?(Q?P)等值演算举例1例1 证明 P?(Q?R) = (P?Q)?R 证: P?(Q?R) = ?P?(?Q?R) （蕴涵等值式，置换规则） = (?P??Q)?R = ?(P?Q)?R = (P?Q) ?R （结合律，置换规则） （德摩根律，置换规则） (蕴涵等值式，置换规则）也可以从右边开始演算应用举例――证明两个公式等值例2 证明： P?Q = (P∧Q)∨(?P∧?Q) 证: P?Q= (P→Q)∧(Q→P) = (?P∨Q)∧(?Q∨P) =(?P∧?Q)∨(?P∧P)∨(Q∧?Q)∨(Q∧P) (分配律) = (?P∧?Q)∨F∨F∨(Q∧P) = (?P∧?Q)∨(Q∧P) = (P∧Q)∨(?P∧?Q) (矛盾律) (同一律) (交换律)P ? Q = (P∧Q)∨(?P∧?Q)等值演算举例3?证明：(?P?(?Q?R))?(Q?R)?(P?R) = R 分配律A?(B?C) = (A?B)?(A?C) ?证： 结合律：(A?B)?C = A?(B?C) 左边= (?P??Q?R)?((Q?P)?R)摩根律：?(A?B) = ?A??B= (?(P?Q)?R)?((P?Q)?R)=(?(P?Q)?(Q?P))?R)= T ?R = R = 右边分配律A?(B?C) = (A?B)?(A?C)补余律：A??A = T等值演算举例4：证明((P?Q)??(?P?(?Q??R)))?(?P??Q)?(?P??R)= T证：左边= ((P?Q)?(P?(Q?R)))??(P?Q)??(P?R)= ((P?Q)?(P?(Q?R)))??((P?Q)?(P?R))= ((P?Q)?((P?Q)?(P?R)))??((P?Q)?(P?R))= ((P?Q)?(P?R))??((P?Q)?(P?R))=T可见，能用等值演算证明公式的类型，此例说明它为重言式用等值演算法判断下列公式的类型(1) Q??(P?Q) 解 Q??(P?Q) = Q??(?P?Q) （蕴涵等值式） = Q?(P??Q) （德摩根律） = P?(Q??Q) （交换律，结合律） = P?F （矛盾律） =F （零律） 由最后一步可知，该式为矛盾式.用等值演算法判断下列公式的类型(2) ((P?Q)?(P??Q))?R) 解: ((P?Q)?(P??Q))?R) = (P?(Q??Q))?R （分配律） = P?T?R （排中律） = P?R （同一律）这不是矛盾式，也不是重言式，而是非重言式的可 满足式.如101是它的成真赋值,000是它的成假赋值. 总结：A为矛盾式当且仅当A = F A为重言式当且仅当A = T命题公式等值演算的应用? 化简下面程序段if A if B X else Y elseif B X else YT B FX X T T A B F F B YT Y FIf BX elseY? 执行X的条件为： (A?B) ?(?A?B) =B ? 执行Y的条件为： (A??B) ?(?A??B) =?B2.3 命题公式与真值表的关系? 按真值表列出命题公式的方法? 从T来列出? 如下表中A为T有三种可能 所以，A的命题公式形式为：□∨ □ ∨□而取T相应的P、Q解释分别为： ?P∧?Q、?P∧Q、 P∧Q? 所以，A=(?P∧?Q) ∨(?P∧Q) ∨(P∧Q)? 同理，可列出 B =(?P∧?Q) ∨(?P∧Q) = ?P ?A= P∧?QC= ?Q ?P∧?QP Q F F T T F T F TA T T F TB T T F F?A F F T FC T F T 任意?P∧QP∧Q命题公式与真值表的关系? 按真值表列出命题公式的方法? 从F来列出? 如下表中B为F有二种可能 所以，B的命题公式形式为：□ ∧ □ 而取F相应的P、Q解释分别为： ?P∨Q 、 ?P∨? Q?所以，B=(?P∨Q)∧(?P∨?Q ) = ?P ?同理，A= ? P∨Q P Q?P∨Q?P∨? QA T T F TB T T F F?A F F T FC T F T 任意F F T TF T F T命题逻辑的应用举例“三人表决器” 设计步骤―― ? 画出真值表 ? 写出逻辑表达式 ? 化简逻辑表达式 ? Y=AB+BC+CA ? 画出逻辑电路图 A B C 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 1 0 1 0 1 0 1 Y 0 0 0 1 0 1 1 12.4 联结词的完备集? 复合联结词如:P:他在家里. Q:他在做作业. P ? Q: 并非他在家里或在做作业.? 排斥或: P?Q = (P??Q)?(?P?Q) (异或) ? 与非式: P?Q = ?(P?Q) ? 或非式: P?Q = ?(P?Q)P 0 0 1 1 Q 0 1 0 1 P?Q 0 1 1 0 P?Q 1 1 1 0 P ?Q 1 0 0 0联结词“↑”的性质?定义： P↑Q = ?(P∧Q) ?性质―― ⑴ P↑P = ?(P∧P) = ?P ⑵ (P↑Q)↑(P↑Q) = ?(P↑Q) = ??(P∧Q) =P∧Q ⑶ (P↑P)↑(Q↑Q) = (?P)↑(?Q) = ?(?P∧?Q) = P∨Q类似地，可用“↓”表示 命题公式间的“与”、 “或”和“非”关系真值函数问题：两个命题变项可构成多少个不等价的合式公式？? 即两个命题变项构成的合式公式有多少个不同的真值表？真值表中每个公式的真值都有1、0两种可能，所以命题公 式的真值有24=2 2 2 =16种可能，既有2 2 2 个不同的真值表。故 有 2 2 2 种不等价的公式。 P Q 公式?结论： 含n个命题变项的所有公 式共产生 22n 个互不相同的 真值表00 101 01或01或0 1或0111或02元真值函数对应的真值表P Q 0 0 1 1 P 0 0 1 1 0 1 0 1 Q 0 1 0 1F0( 2) F1( 2) F2( 2) F3( 2) F4( 2) F5( 2) F6( 2) F7( 2)0 0 0 0F8( 2)0 0 0 1F9( 2)0 0 1 0( F102)0 0 1 1( F112)0 1 0 0( F122)0 1 0 1( F132)0 1 1 0( F142)0 1 1 1( F152)1 0 0 01 0 0 11 0 1 01 0 1 11 1 0 01 1 0 11 1 1 01 1 1 1作业2P37: 1 (1)(3) P37: 2 P37: 3
赞助商链接
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...第二章 命题逻辑等值演算一、用等值演算法判断下列...数理逻辑的的主要任务是 推理是指 是 2.推理正确...建立数理逻辑或者说理性演算的思想: ?提出将推理的...2 三、预备知识 1. 集合的基本概念?集合(set):...而且对于命题逻辑的等值演算、推理理论 在一阶逻辑中...数理逻辑小结 概念 命题逻辑 命题: 谓词: 谓词逻辑...等值演算 原子命题、复合命题 命题公式 真值指派与...方法推理 代入规则 置换规则 主析取范式: 主析取...数理逻辑考试题及答案_研究生入学考试_高等教育_教育专区。“离散数学”数理逻辑...计算推理公式真值为真,由此,本题推理正确。 二、命题逻辑等值演算(5 分) 1...数理逻辑大纲1611016_教育学_高等教育_教育专区。《数理...第二章 命题逻辑等值演算(6 学时) 教学目的:通过...第五章 一阶逻辑等值演算与推理(6 学时) 教学...搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...重点: 重点: 数理逻辑的命题逻辑的基本概念、命题...逻辑基本概念 一阶逻辑等值演算与 推理 3 2 2 ...复习(数理逻辑部分)_法学_高等教育_教育专区。第 1...第 2 章 命题逻辑等值演算一:验证两个公式是否等值...M2 q 1 1 0 1 第 3 章 命题逻辑的推理理论一...等值 永真蕴含 极小项 主析取范式 有效结论 推理规则 数理逻辑习题课 在一定...1 为其变化域 真值已确定的命题,即是 0,或 1 命题与命题演算中的运算符 ...数理逻辑的应用_理学_高等教育_教育专区。高数1 逻辑运算 逻辑运算又称布尔运算...进行推理、 演算,等值演算的目的在于化简复杂的命题公式,从而提取出于命题等价的...14页 1下载券 北邮高级数理逻辑课件 15页 免费高...命题逻辑与命题演算 Leibniz 提出逻辑推理变成符号演算...合取式、析取式、蕴涵式、等值式等不同类型的概念...
All rights reserved Powered by
www.tceic.com
copyright &copyright 。文档资料库内容来自网络，如有侵犯请联系客服。1.3 等值演算_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
1.3 等值演算
阅读已结束，下载本文需要
想免费下载更多文档？
定制HR最喜欢的简历
下载文档到电脑，同时保存到云知识，更方便管理
加入VIP
还剩1页未读，
定制HR最喜欢的简历
你可能喜欢【图文】第一章 命题逻辑等值演算_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
第一章 命题逻辑等值演算
&&离散数学
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢高手帮我指点一下，离散数学，等价公式中吸收律的含义是什么？_百度知道
高手帮我指点一下，离散数学，等价公式中吸收律的含义是什么？
补充：命题逻辑中的等价公式，其中有吸收律P∧(P∨Q)=P，P∨(P∧Q)=P，这个吸收律是什么含义？
用真值表可以证明同时你可以参考一下图片&方便理解
采纳率：39%
为您推荐：
其他类似问题
您可能关注的内容
离散数学的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。【图文】命题逻辑等值演算_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
命题逻辑等值演算
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢