简单数理逻辑及其应用.pptx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《简单数理逻辑及其应用.pptx》由会员分享,可在线阅读,更多相关《简单数理逻辑及其应用.pptx(40页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、简单数理逻辑及其应用清华大学 计算机科学与技术系李恺威概述数理逻辑命题联结词合式公式等值公式、定理范式SAT问题2-SATDPLL算法SMT问题分类应用命题命题变项简单命题和复合命题P:雪是白的且“1+1=2”可分割为R:雪是白的S:1+1=2命题联结词非与 合取或 析取 p p0110 p q pqpq0000010110011111推断推断因果关因果关系系等价等价 PQPQP QFFTTFTTFTFFFTTTT合式公式Well-formed formula命题变项和连接词的组合定义1.简单命题是合式公式2.如果A是合式公式,那么A也是合式公式3.如果A,B是合式公式,那么(A B),(A
2、B),(A B)和(A B)是合式公式4.当且仅当经过有限次地使用1,2,3所组成的符号串才是合式公式合式公式合式公式简称公式例子p(pq)qIf A then B else C 能用合式公式表示吗?合式公式分类永真式:在任何解释I下都为真(T)可满足式:在某个解释I0下为真(T)矛盾式:在任何解释I下都为假(F)例1.P P I0=(T)I1=(F)2.P QI0=(T,F)3.P P矛盾三种公式关系A永真,当且仅当A永假A可满足,当且仅当A非永真A不可满足,当且仅当A永假等值公式两个公式A和B,P1,Pn是所有A和B中的命题变项A和B有2n个不同的解释在任何解释下,A和B的真值都相等称A和
3、B等值,记A=B等值定理对公式A和B,A=B的充分必要条件是AB是永真式不要将“=”视作连结词A=B表示公式A与B的一种关系1.自反性:A=A2.对称性:若A=B,则B=A3.传递性:若A=B,B=C,则A=C等值公式1.1.双重双重否定否定律律 P=P2.2.结合律结合律 (P Q)R=P (Q R)(P Q)R=P (Q R)(P Q)R=P (Q R)3.3.交换律交换律 P Q=Q P P Q=Q P P Q=Q P4.分配律分配律P (Q R)=(P Q)(P R)P (Q R)=(P Q)(P R)P (Q R)=(P Q)(P R)5.等等幂幂律律P P=P P P=PP P=T
4、 P P=T6.吸收律吸收律P (P Q)=P P (P Q)=P7.摩根摩根(De Morgan)律:)律:(P Q)=P Q (P Q)=P Q 命题公式与真值表给出公式,列写真值表很容易反过来呢?尝试写出A,B由P,Q表达的公式PQABFFTTFTTTTFFFTTTF从T列写A=(PQ)(PQ)(PQ)B=(PQ)(PQ)PQABFFTTFTTTTFFFTTTF从F列写A=(PQ)B=(PQ)(PQ)PQABFFTTFTTTTFFFTTTF范式列写方法多样,是否有标准形式?定义:文字:简单命题P及其否定式P合取式:一些文字的合取析取式:一些文字的析取析取范式:形如A1A2An(其中Ai为
5、合取式)合取范式:形如A1A2An(其中Ai为析取式)范式范式定理:任意命题公式都存在有与其等值的合取范式和析取范式求范式AB=ABA B=(AB)(AB)=(AB)(AB)小结命题联结词合式公式等值公式、定理范式SAT问题Boolean satisfiability problem给出一个合式公式,判断其是否可满足将合式公式化成合取范式A1A2AnAi=(Pi1Pi2Pim)求解办法?2-SAT特殊情况合取式的每一项Ai最多只有2个变量析取(m=2)(X0X2)(X0X3)(X1X3)T T T T T T构图法N个变项,2N个节点(Ai与 Ai为对偶点)AB=A B对每一项(AB)从A向B
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 简单 数理逻辑 及其 应用
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内