chpt3-人工智能原理-逻辑系统

人工智能原理第3章逻辑系统本章内容3.1命题逻辑和一阶谓词逻辑3.2逻辑系统的语法和语义3.3逻辑推理举例3.4逻辑智能体的推理策略参考书目附录形式系统简介第3章逻辑系统3经典数理逻辑•AI研究内容之一是推理，即研究怎样使计算机获得自动推理的能力•数理逻辑用数学方法研究各种推理中的逻辑问题，以推理本身作为研究对象•AI要使用逻辑推理，就必然涉及数理逻辑/数理逻辑的经典部分—经典的命题逻辑和一阶谓词逻辑，同时作为人工智能的知识表示方法和推理方法而存在；因此数理逻辑是人工智能的一个基础第3章逻辑系统4逻辑智能体•基于知识的智能体的核心部件是知识库，当这些知识以逻辑形式表示并进行相应的推理时，就是逻辑智能体•知识表示：命题逻辑、一阶谓词逻辑•推理(一阶谓词逻辑)—主要有3类推理算法：前向链接和演绎系统、反向链接和逻辑程序设计(本章)、归结反演和定理证明系统(第4章)•采用命题和谓词演算进行推理的系统(如演绎系统)是一种典型的逻辑智能体第3章逻辑系统3.1命题逻辑和一阶谓词逻辑命题、真值、原子公式、合式公式谓词、论域、个体量词、变量、函数一阶语言、一阶语言的项第3章逻辑系统6命题•命题：描述客观世界的可区分真假的陈述句,即判断（经典二值逻辑：非真即假）•是命题的例子：•2+2=4/二月份有30天/2002年哈尔滨有地震/人类能够证明数论中所有论断非真即假（有待时间）•不是命题的例子：•张三比李四聪明/公共汽车内非常拥挤（各人认识不同）第3章逻辑系统7命题变量与真值•命题变量（变元）：一个命题用符号表示，称为命题符号•当命题符号代表任一个命题时，即为命题变量•真值：真或假–一个命题或命题变量具有真值•真值连接词（5个）：否定/合取/析取/蕴涵/等价第3章逻辑系统8简单命题与复合命题•真值函数：真值联结词可以视为一元或二元映射(真值函数)，￢是从{T,F}到{T,F}，其余是{T,F}2到{T,F}的映射/其函数定义由真值表确定•简单命题：一个被视为整体的、具有真或假的命题是简单命题；•复合命题：使用联结词将简单命题联结起来的命题是复合命题第3章逻辑系统9命题语言与原子公式•命题逻辑：研究复合命题之间的推导关系•命题语言：是命题逻辑使用的形式语言，是符号的集合,用Lp表示/包括：命题符号、连接词、左右括号•原子公式：命题语言中的一个表达式是原子公式，当且仅当它是一个命题符号/原子公式也称为文字(包括正文字和负文字)第3章逻辑系统10命题逻辑的合式公式•合式公式(well-formedformula)，简称公式，记作wff：一个表达式是一个公式，当且仅当它能通过有限次地使用下述步骤生成：(1)原子公式是公式；(2)如果A是公式，则(￢A)是公式；(3)如果A、B均为公式，则A*B是公式，其中*表示∧∨→≡中的任意一个/公式的形成规则/命题逻辑的主要研究对象是公式第3章逻辑系统11谓词•从命题到一阶谓词：命题内部逻辑结构的分解对判断的分解，把判断中的具体内容抽出，称为个体；剩下的判断即为谓词•谓词可看作是从个体域或个体域的笛卡儿乘积到真值集合{T/F}的映射•典型的推理例子：(1)凡人皆有死；(2)苏格拉底是人；(3)苏格拉底有死。（三段论式）M(x)D(x),M(s)├D(s)第3章逻辑系统12论域与个体•论域和个体：在一阶逻辑中，被研究对象构成的非空集称为论域；论域中的每个元素称为个体•论域例子：前面例子中的论域是“人”/所有的有理数都是实数：其论域为有理数•一阶逻辑还研究个体之间的关系（或个体的性质）及作用于个体的函数•论域/个体/个体间关系/作用于个体函数这4个成分构成了一阶逻辑的结构第3章逻辑系统13谓词•谓词（关系）：一阶形式语言中用于指称论域中个体的性质或者个体之间关系的形式符号（大写字母表示）•给定了论域，就确定了谓词的真假值•一元谓词：个体的性质；二元谓词(多元谓词)：个体的关系•个体的位置—空位，具体化—构成意义完整的语句•空位的数目—谓词的元数→几元谓词第3章逻辑系统14量词与变量•变量(变元)：表示论域内的任意一个个体/常量(常元)，表示确定的个体•量词与变量：量词用来表示谓词的判断特性•全称量词：对所有的xxP(x)•存在量词：存在xxP(x)•约束变量：、中x的变量，量词所管辖的公式如P(x)称为量词辖域•自由变量：不在量词辖域内的变量为自由变量第3章逻辑系统15约束变量和自由变量•区别：自由变量可代入常量，约束变量不行，因为aP(a)无意义；约束变量可改名，自由变量不行•带有全称变量x的命题表示为一阶公式时，其表示形式为x(P(x)→…)，带有存在变量x的命题则表示形式为x(P(x)∧…)•例子：所有有理数都是实数x(P(x)→R(x))，有些人身高超过2米x(M(x)∧G(x))•上述使用方式不可改变，否则造成逻辑错误第3章逻辑系统16函数•函数：表示个体之间的运算，可作用于一个或数个个体（用小写字母）•给定一个或若干个体（对象），产生一个新的个体（对象）/函数的元数•例子：x的父亲father(张三)•两数之和仍是一个数add(e1,e2)第3章逻辑系统17函数与谓词的区别•谓词和函数的区别：谓词代表语句，结果是关系（具有真假值）；函数代表关系运算，结果是一个新个体•例子：谓词SUM(e1,e2,e3)说明e1、e2、e3之间的关系是e1与e2的和是e3，•函数add(e1,e2)说明e1与e2相加的结果仍是一个数第3章逻辑系统18一阶语言(1)•一阶语言L：是一阶逻辑使用的形式语言，可以和任何结构（论域）没有联系，也可以与某个结构有联系•与结构没有联系的一阶语言由8类符号组成：(1)无限序列的个体符号（个体常量）(2)无限序列的谓词符号，有确定的元数n≥1有一个特殊的谓词符号称为相等符号（等式），记为=。L可含或不含=，如果含有，即称为含=的一阶逻辑第3章逻辑系统19一阶语言(2)(3)无限序列的函数符号，有确定的元数m≥1(4)无限序列的自由变量：用u/v/w等表示自由变量(5)无限序列的约束变量：用x/y/z等表示约束变量(6)联结词：￢∧∨→≡(7)量词：、(8)标点：左右括号、逗号(),第3章逻辑系统20一阶语言的项和公式•L的项：一阶语言中的一个符号是项t，当且仅当它能通过有限次使用下述步骤生成：(1)个体常量、自由变量是项；(2)如果t1…tn是项，且f是n元函数，则f(t1…tn)是项•L的原子公式：一阶语言中的一个表达式是一个原子公式，当且仅当它有如下2种形式：(1)F(t1…tn)，F是n元谓词，t1…tn是项；(2)=(t1,t2)或t1=t2，t1、t2是项第3章逻辑系统21一阶语言的公式(1)•L的公式：一阶语言中的一个表达式是一个公式，当且仅当它能通过有限次使用下述步骤生成：(1)原子公式是公式；(2)如果A是公式，则(￢A)是公式；(3)如果A、B均为公式，则A*B是公式，其中*表示∧∨→≡中的任意一个(4)如果A(u)是公式，且x不在A(u)中出现，则xA(x)、xA(x)都是公式第3章逻辑系统22一阶语言的公式(2)•一阶谓词公式的例子•数学命题的表示：5只被1和5整除•设Q(x,y)表示x被y整除，N(x)表示x是自然数x(Q(5,x)→N(5)∨N(1))•自然语言语句的表示：他不能在所有时刻欺骗所有人•设F(x)表示“x是人”/G(x)“x是一个时刻”/H(x,y)“他能在y时刻欺骗x”¬xy(F(x)∧G(y)→H(x,y))或者xy(¬H(x,y)∧F(x)∧G(y))第3章逻辑系统3.2逻辑系统的语法和语义逻辑系统的语法逻辑系统的语义语法和语义之间的关系第3章逻辑系统24逻辑系统•逻辑系统(亦称形式系统FormalSystem)由5个部分组成：•符号表—非空集合，即逻辑(形式)语言—如一阶语言•上全体符号的集合*的子集—项和变量•*的子集—公式|公式和项的交集为空•公式FORMULA上的子集—公理AXIOM•公式上的n元关系集合—推理规则RULE•、项TERM、FORMULA称为FS的组成部分/AXIOM、RULE称为FS的推演部分第3章逻辑系统25语法和形式推演•逻辑系统除符号表以外的部分构成了逻辑系统的语法•形式推演：定义了公式之间的形式可推演性关系，它涉及公式的语法结构，其正确性能够机械地证明•用记号├表示形式可推演关系，读作“推出”•用├A表示A是由形式可推演的（或形式可证明的），其中是前提，A是结论第3章逻辑系统26推演规则举例•形式推演由形式推演规则定义，举例如下：•自反A├A(Ref)•传递if├‘├Athen├A()•￢消去(反证律)if,￢A├B&,￢A├￢Bthen├A(￢–)•公式变换A→BAB第3章逻辑系统27形式可推演性•形式可推演性：在命题/一阶逻辑系统中，A是由可形式推演的(或形式可证明的)，记为├A，当且仅当├A能通过有限次应用相应逻辑的形式推演规则生成•即├A成立，当且仅当存在有限序列使得1├A1，2├A2，…，n├An中的每一项均由某个形式推导规则生成,且n├An就是├A即n=,An=A•建立在上述形式推演规则基础上的形式推演系统称为自然推演(演绎)系统第3章逻辑系统28逻辑系统的语义•语义即对形式语言进行解释•研究可推导性即形式推演(├)时不考虑作为前提和结论的命题的内容，只考虑命题真假并由此确定前提的真是否蕴涵结论的真，即前提和结论之间是否有可推导关系(语法)•研究形式系统的语义时，对逻辑系统赋予研究对象的集合即论域；用论域中的个体对象、对象之上的运算(函数)、对象之间的关系(谓词)去解释逻辑系统中的符号，称作指称denote指称语义学•赋予形式系统的论域及解释称为形式系统的语义结构，简称结构(structure)第3章逻辑系统29命题逻辑的语义与可满足性•研究命题逻辑的语义，即研究公式(公式集)的真假赋值问题•真假赋值：真假赋值是以所有命题符号的集合为定义域、以真假值{1,0}为值域的函数。真假赋值v给公式A指派的值记作Av•可满足性：是可满足的，当且仅当有真假赋值v，使得v=1。此时称v满足。第3章逻辑系统30可满足性•的可满足性蕴涵了中所有公式的可满足性，但反过来不成立。因为这要求同一个真假赋值满足所有的公式(并非所有可满足的公式使用同一个赋值)•重言式和矛盾式•A是重言式(永真式)，当且仅当对于任意的真假赋值v，Av=1•A是矛盾式(永假式)，当且仅当对于任意的真假赋值v，Av=0第3章逻辑系统31真假判断与逻辑推论•一个命题公式是重言式或者是矛盾式或者两者都不是，需要进行判定。判定方法可通过构造真假值表方法或采用树形分支的方法来判定•可推导关系：研究前提的真是否蕴涵结论的真，引入语义以后对公式进行真假赋值；如果对任意的真假赋值，都有上述关系，则说明前提和结论之间存在一种逻辑推论关系(或称逻辑蕴涵)第3章逻辑系统32命题逻辑的逻辑推论•逻辑推论：设、A分别是命题逻辑中的公式集合和公式,A是的逻辑推论，记为A，当且仅当对于任意真假赋值v，v=1蕴涵Av=1。•|=可读作“逻辑地蕴涵”，|=是前提和结论A之间的关系•逻辑推论的证明•要证明|=A时，即要证明对于任何真假赋值v，如果v=1则Av=1(通常使用反证法)第3章逻辑系统33一阶语言的语义•一阶语言的语义：一阶语言的解释包括一个论域和一个函数•函数把一阶语言中的个体符号映射到论域中的个体•n元关系符号(即谓词)映射到论域上的n元关系•m元函数符号映射到论域上的m元全函数•以上组成了该论域中对一阶语言的解释第3章逻辑系统34一阶语言的赋值•赋值：一阶语言L的赋值v包括一个论域D和一个函数(记作v)•L中所有个体符号a为定义域，其赋值v(a)或av•关系符号F的赋值v(F)或Fv•函数符号f的赋值v(f)或fv•自由变量符号u的赋值v(u)或uv•则有(1)av,uv∈D(2)FvDn(3)fv:Dm→D第3章逻辑系