人工智能逻辑

人工智能逻辑2020/4/1史忠植逻辑基础1史忠植中国科学院计算技术研究所高级人工智能第二章主要内容逻辑简介逻辑程序设计非单调逻辑默认逻辑限定逻辑真值维护系统情景演算动态描述逻辑2020/4/1史忠植逻辑基础2逻辑简介逻辑的历史逻辑系统命题逻辑谓词逻辑2020/4/1史忠植逻辑基础3逻辑的历史Aristotle——逻辑学Leibnitz——数理逻辑GottlobFrege(1848-1925)——一阶谓词演算系统,《符号论》20世纪30年代，数理逻辑广泛发展2020/4/1史忠植逻辑基础4逻辑系统一个逻辑系统是定义语言和它的含义的方法。逻辑系统中的一个逻辑理论是该逻辑的语言的一个语句集合，它包括：逻辑符号集合：在所有该逻辑的逻辑理论中均出现的符号；非逻辑符号集合：不同的逻辑理论中出现的不同的符号；语句规则：定义什么样的符号串是有意义的；证明：什么样的符号串是一个合理的证明；语义规则：定义符号串的语义。2020/4/1史忠植逻辑基础52020/4/1史忠植逻辑基础6逻辑程序语言逻辑符号保留字或者符号非逻辑符号用户自定义的符号(变量名，函数名等)语句规则构造一个程序的语句规则语义规则定义程序做什么的语句规则推理规则、公理和证明没有逻辑与程序语言的对比2020/4/1史忠植逻辑基础7一个证明是一个语法结构，它由符号串根据一定的规则组成。它包括假设和结论。在公理化逻辑中，逻辑给出一个逻辑公理和推理规则的集合。推理规则是可以从一个语句的集合得到另一语句的集合。公理化逻辑中的证明就是一个语句序列，使得其中的每个语句要么是逻辑公理，要么是一个假设，要么是由前面的语句通过推理规则得到的。证明2020/4/1史忠植逻辑基础8在语法上，如果存在一个从假设到的证明，则记为⊢，称由可推导出的，或可证明的。是可推导出的，则记为⊢，称为可证明的。称一个假设是不协调的，如果存在一个语句使得和的否定均可由推导得出。称一个逻辑系统是一致的，或相容的(consistent)，如果不存在逻辑系统的公式A，使得⊢A与⊢¬A同时成立。证明(语法)2020/4/1史忠植逻辑基础9语言的解释是在某个论域(domain)中定义非逻辑符号。语句的语义是在解释下定义出语言L的真假值。I是L的一个解释，且在I中为真，则记为I⊨，称作I满足，或者I是的一个模型。类似地，给定一个语句和一个语句，如果对每个解释I，有I⊨蕴含I⊨，换言之，如果I是的一个模型则I也是的一个模型，则记为⊨，我们称为的一个逻辑结果。解释(语义)2020/4/1史忠植逻辑基础10可靠性(reliable)一个逻辑是可靠的，如果它的证明保持真假值，即在任何解释I下，如果I是的模型，且可由推导出，则I也是的一个模型。即，一个逻辑是可靠的，如果对任何语句集合和语句，⊢蕴涵⊨。可靠性和完备性完备性(complete)一个逻辑是完备的，如果任何永真语句是可证的。即，对任何语句集合和语句，⊨蕴涵⊢。如果一个逻辑是完备的，则该逻辑的证明系统已强到可以推出任何永真式。Gődel完备性定理：一阶逻辑是完备的2020/4/1史忠植逻辑基础11可判定的一个逻辑称为是可判定的(decidable)，如果存在一个算法对逻辑中的任一公式A，可确定⊢A是否成立。否则，称为是不可判定的(undecidable)。如果上述算法虽不一定存在，却有一个过程，可对该系统的定理做出肯定的判断，但对非定理的公式过程未必终止，因而未必能作出判断。这时称逻辑是半可判定的。可判定性一阶逻辑是不可判定的，但它是半可判定的。现代逻辑学与计算机科学、计算语言学和人工智能的关系表逻辑自然语程序人工逻辑指令与直数据库复杂性智能体未来展望言处理控制智能编程陈式语言理论理论理论时序逻辑√√√√√√√√广泛应用模态逻辑√√√√√√√√非常活跃算法证明√√√√√√√√非单调推理√√√√√√√意义重大概率和模糊√√√√√√√目前主流直觉主义逻辑√√√√√√√√主要替代者高阶逻辑，λ-演算√√√√√√更具中心作用经典逻辑片断√√√√√√前景诱人资源和子结构逻辑√√√√纤维化和组合逻辑√√√√√√可自我指称谬误理论在适当语境逻辑动力学√√动态逻辑观论辩理论游戏√前景光明对象层次/元层次√√总起中心作用机制:溯因缺省相干√√逻辑的一部分与神经网络的联系极重要，刚开始时间-行动-修正模型√√一类新模型加标演绎系统√√√√√逻辑学的统一框架2020/4/1史忠植逻辑基础12命题逻辑命题是可以确定其真假的陈述句。Bolle提出了布尔代数。语言:¬，；公式，原子公式公理模式:◆(A(BA))◆((A(BC))((AB)(AC)))◆(((¬A))(¬B)(BA))推理规则:分离规则(modusponens，MP规则)2020/4/1史忠植逻辑基础13BBAA,谓词逻辑(一阶逻辑)Frege谓词演算语言:¬，，，，(，)；常元，变元，函词，谓词；公式公理模式:◆(A(BA))◆((A(BC))((AB)(AC)))◆(((¬A)(¬B))(BA))◆vAAtv(t对A中变元v可代入)◆v(AB)(vAvB)◆AvA(v在A中无自由出现)推理规则:分离规则2020/4/1史忠植逻辑基础14BBAA,谓词逻辑与命题逻辑的区别2020/4/1史忠植逻辑基础15谓词逻辑给出了原子语句的内部结构，将原子公式看作是事物直接的关系；它引入了“推广”(泛化)，加强了逻辑的表示能力和推理能力。这样，我们可以说某种性质对某个对象是成立的，或对所有的对象成立，或不对任何对象成立。逻辑程序设计归结原理(消解原理)Horn逻辑Prolog逻辑程序设计语言2020/4/1史忠植逻辑基础16归结原理例：C1=¬P∨Q∨RC2=P∨Q则C1与C2归结后的结果为：Q∨R若子句集S能导出空子句⊓(有否证)，则称S是不可满足的。S⊢AiffS¬A⊢⊓2020/4/1史忠植逻辑基础17QQP,PQQP,PHorn逻辑文字：原子公式(正文字)或原子公式的否定(负文字)。P,Q,¬R子句：若干文字的析取。¬P∨Q∨RHorn子句：L1∨L2∨…∨Ln中如果至多只含一个正文字，那么该子句称为Horn子句。Horn子句P∨¬Q1∨¬Q2∨…∨¬Qn通常表示为：PQ1,Q2,…,Qn2020/4/1史忠植逻辑基础18Horn子句的类型2020/4/1史忠植逻辑基础19◆过程：PQ1,Q2,…,Qn◆事实：P◆目标：Q1,Q2,…,Qn◆空子句：⊓例:◆过程：AT(dog,x)AT(Zhang,x)◆事实：AT(Zhang,train)◆目标：AT(dog,train)首先目标中过程调用AT(dog,train)与过程名AT(dog,x)匹配，合一为{train/x}，调用过程AT(Zhang,x)，从而产生新目标AT(Zhang,train)，与事实匹配，产生目标⊓。因而调用成功，输出“是”。PrologProlog(Programminginlogic)语言是以Horn子句逻辑为基础的高级程序设计语言。1972年，法国马赛大学的Alain.Colmerauer提出了Prolog的雏型。1975年，Prolog被用于问题求解系统。此后，它在许多领域获得了应用，如关系数据库、定理证明、智能问题求解、计算机辅助设计、规划生成等领域。2020/4/1史忠植逻辑基础20Prolog的构成事实：关于对象性质和关系的事实语句；student(john)，married(tom,mary)规则：关于对象性质和关系的定义规则语句；它与事实的不同在于，规则所定义的性质、关系依赖与其它的性质和关系，因此规则呈蕴涵语句形式。B:—A“如果A则B”bird(x):—animal(x)，has(x,feather)问题：关于对象性质或关系的询问。?—student(john)?—married(mary，x)2020/4/1史忠植逻辑基础212020/4/1史忠植逻辑基础22Prolog的执行方式搜索：在程序中自上而下地搜索事实和规则；匹配：将目标中的项与事实和规则进行匹配；回溯：当目标中一项失败时，如果目标中有已经成功的的项(应在失败项的左边)，那末就重新调用这些成功项中最右边的一个，谋求新的成功。2020/4/1史忠植逻辑基础23Prolog语言的基本文法Prolog语言的最基本语言成分是项(term)，一个项或者是常量，或者是变量，或者是一个结构。•常量：是指对象和对象之间的特定关系的名；整数，如0，22，1586等；原子，如John，student，likes，sister-of•变量：表示任意的对象，它与FOL中的变元相同；Prolog中变量可以用大写字母，下划线，以及由它们开头的字母串。如X,Y,Answer,_value等。•结构：是常量和变量的序列，它由一个函子(函词或谓词)和该函子的自变量所组成。如：likes(john,X)married(mary,jack)例子2020/4/1史忠植逻辑基础24(1)likes(bell,sports)(2)likes(mary,smith)(3)likes(mary,sports)(4)likes(jones,smith)(5)friend(john,X):—likes(X,sports),likes(X,smith)(规则)(6)?—friends(john,Y)(问题)(事实)(7)?—likes(X,sports),likes(X,smith)(8)?—likes(bell,smith)(bell/X)(7)?—likes(X,sports),likes(X,smith)(8)?—likes(mary,smith)(mary/X)Y=mary，John与Mary是朋友2020/4/1史忠植逻辑基础25Prolog的基本特点Horn子句逻辑是Prolog的基础。•Prolog既是一种逻辑程序设计语言，又是一个逻辑系统。•Prolog是一种描述性语言，它是一种面向问题的语言，你只需要告诉它要做什么，即给出问题的形式描述，而不需要知道应该如何做。•Prolog完全依靠匹配、回溯来进行搜索。Prolog的求解过程是一个寻求否证的消解过程。•Prolog也使用元语言种的谓词，有很强的描述能力。•Prolog采用统一的数据结构——项，它包含控制成分，且有专门进行数值计算和符号处理的模块。非单调逻辑单调逻辑非单调逻辑区别2020/4/1史忠植逻辑基础26单调逻辑在现有知识的基础上，通过严密的逻辑论证和推理获得的新知识必须与已有的知识相一致。A，ABB推理系统的定理集合随着推理过程的进行而单调地增大。单调性：(1)∈Th()(2)若1⊆2，则Th(1)⊆Th(2)(3)Th(Th())＝Th()(不动点)2020/4/1史忠植逻辑基础272020/4/1史忠植逻辑基础28非单调逻辑推理系统的定理集合并不随着推理过程的进行而单调地增大，新推出的定理很可能会否定、改变原来的一些定理，使得原来能够解释的某些现象变得不能解释了。新规则：(4)⊬¬P(不动点)默认逻辑1980年，Reiter提出了默认逻辑(DefaultLogic)。“一般情况下鸟是会飞的”“鸵鸟不会飞”“企鹅不会飞”2020/4/1史忠植逻辑基础29)()(:)(xflyxMflyxBird会飞会飞”与系统不矛盾“是鸟xxx:2020/4/1史忠植逻辑基础30默认规则一个默认规则是如下形式的规则：)x()x(M,),x(M:)x(n1(x):称为前提条件i(x):称为默认条件，或检验条件(x):称为结论为简便，通常情况下可以省略检验条件中的M。规则的使用：出检验条件的否定¬i(x)，则可以得出结论成立。2020/4/1史忠植逻辑基础31