哈工大人工智能课件chpt3124

人工智能原理第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个）：否定/合取/析取/蕴涵/等价•真值函数：真值联结词可以视为一元或二元映射(真值函数)，￢是从{T,F}到{T,F}，其余是{T,F}2到{T,F}的映射/其函数定义由真值表确定第3章逻辑系统8简单命题与复合命题•简单命题：一个被视为整体的、具有真或假的命题是简单命题•复合命题：使用联结词将简单命题联结起来的命题是复合命题第3章逻辑系统9命题逻辑基础•定义：•合取式：p与q，记做p∧q•析取式：p或q，记做p∨q•蕴含式：如果p则q，记做p→q•等价式：p当且仅当q，记做pq第3章逻辑系统10命题逻辑基础•定义：•若A无成假赋值，则称A为重言式或永真式；•若A无成真赋值，则称A为矛盾式或永假式；•若A至少有一个成真赋值，则称A为可满足的；•…………•析取范式：仅由有限个简单合取式组成的析取式•合取范式：仅由有限个简单析取式组成的合取式第3章逻辑系统11命题逻辑基础•基本等值式（24个）•交换律：p∨qq∨pp∧qq∧p•结合律：(p∨q)∨rp∨(q∨r);(p∧q)∧rp∧(q∧r)•分配律：p∨(q∧r)(p∨q)∧(p∨r)；p∧(q∨r)(p∧q)∨(p∧r)第3章逻辑系统12命题逻辑基础•基本等值式（24个）•摩根律:～(p∨q)～p∧～q；～(p∧q)～p∨～q•吸收律:p∨(p∧q)p；p∧(p∨q)p•同一律:p∨0p；p∧1p•蕴含等值式：p→q～p∨q•假言易位式:p→q～p→～q第3章逻辑系统13命题语言与原子公式•命题逻辑：研究复合命题之间的推导关系•命题语言：是命题逻辑使用的形式语言，是符号的集合,用Lp表示•包括：命题符号、连接词、左右括号•原子公式：命题语言中的一个表达式是原子公式，当且仅当它是一个命题符号/原子公式也称为文字(包括正文字和负文字)第3章逻辑系统14命题逻辑的合式公式•合式公式(well-formedformula)，简称公式，记作wff：一个表达式是一个公式，当且仅当它能通过有限次地使用下述步骤生成：(1)原子公式是公式；(2)如果A是公式，则(￢A)是公式；(3)如果A、B均为公式，则A*B是公式，其中*表示∧∨→≡中的任意一个•公式的形成规则•命题逻辑的主要研究对象是公式第3章逻辑系统15例子•将陈述句转化成命题公式。•如：设“下雨”为p，“骑车上班”为q•1“只要不下雨，我就骑车上班”。~p是q的充分条件，因而可得命题公式：~pq•2“只有不下雨，我才骑车上班”。~p是q的必要条件，因而可得命题公式：q~p16例子•1“如果我进城我就去看你，除非我很累”设：p,我进城，q，去看你，r，我很累，则有命题公式：~r(pq)•2”应届高中生，得过数学或物理竞赛的一等奖，保送上大学“设：p，应届高中生；q,保送上大学；r,得过数学竞赛的一等奖；t,得过物理竞赛的一等奖。则有命题公式：p∧(r∨t)q17命题逻辑的特点•命题逻辑：使用陈述性、上下文无关、无歧义性、合成性的形式语言•陈述性—使用符号描述(语句形式)显式地表示知识(相对于过程性—将需要的知识直接编写为程序代码)•上下文无关—其含义不因环境而改变•无歧义性—含义唯一•合成性—语句的含义是其各部分含义的一个函数(也是一种唯一性)第3章逻辑系统18一阶谓词逻辑•从命题到一阶谓词：命题内部逻辑结构的分解对判断的分解，把判断中的具体内容抽出，称为个体；剩下的判断即为谓词•谓词可看作是从个体域或个体域的笛卡儿乘积到真值集合{T/F}的映射•典型的推理例子：(1)凡人皆有死；(2)苏格拉底是人；(3)苏格拉底有死。（三段论式）M(x)D(x),M(s)├D(s)第3章逻辑系统19例子•小王是个工程师•8是个自然数•我去买花•小丽和小华是朋友•其中，“小王”、“工程师”、“8”、“我”、“花”、“小丽”、“小华”都是个体，而“是个工程师”、“是个自然数”、“去买花”、“是朋友”都是谓词。显然前两个谓词表示的是事物的性质，第三个谓词表示的是一个动作，也表示了主、宾两个个体的关系，最后一个谓词“是朋友”表示两个个体之间的关系。20论域与个体•论域和个体：在一阶逻辑中，被研究对象构成的非空集称为论域；论域中的每个元素称为个体•论域例子：前面例子中的论域是“人”/所有的有理数都是实数：其论域为有理数•一阶逻辑还研究个体之间的关系（或个体的性质）及作用于个体的函数•论域/个体/个体间关系/作用于个体函数这4个成分构成了一阶逻辑的结构第3章逻辑系统21谓词•谓词（关系）：一阶形式语言中用于指称论域中个体的性质或者个体之间关系的形式符号（大写字母表示）•给定了论域，就确定了谓词的真假值•一元谓词：个体的性质；二元谓词(多元谓词)：个体的关系•个体的位置—空位，具体化—构成意义完整的语句•空位的数目—谓词的元数→几元谓词第3章逻辑系统22变量与量词•变量(变元)：表示论域内的任意一个个体/常量(常元)，表示确定的个体•量词与变量：量词用来表示谓词的判断特性•全称量词：对所有的xxP(x)•存在量词：存在xxP(x)•约束变量：、中x的变量，量词所管辖的公式如P(x)称为量词辖域•自由变量：不在量词辖域内的变量为自由变量第3章逻辑系统23约束变量和自由变量•区别：自由变量可代入常量，约束变量不行，因为aP(a)无意义；约束变量可改名，自由变量不行•带有全称变量x的命题表示为一阶公式时，其表示形式为x(P(x)→…)，带有存在变量x的命题则表示形式为x(P(x)∧…)•例子：所有有理数都是实数x(P(x)→R(x))，有些人身高超过2米x(M(x)∧G(x))•上述使用方式不可改变，否则造成逻辑错误第3章逻辑系统24函数•函数：表示个体之间的运算，可作用于一个或数个个体（用小写字母）•给定一个或若干个体（对象），产生一个新的个体（对象）/函数的元数•例子：x的父亲father(张三)•两数之和仍是一个数add(e1,e2)第3章逻辑系统25函数与谓词的区别•谓词和函数的区别：谓词代表语句，结果是关系（具有真假值）；函数代表关系运算，结果是一个新个体•例子：谓词SUM(e1,e2,e3)说明e1、e2、e3之间的关系是e1与e2的和是e3，•函数add(e1,e2)说明e1与e2相加的结果仍是一个数第3章逻辑系统26一阶语言(1)•一阶语言L：是一阶逻辑使用的形式语言，可以和任何结构（论域）没有联系，也可以与某个结构有联系•与结构没有联系的一阶语言由8类符号组成：(1)无限序列的个体符号（个体常量）(2)无限序列的谓词符号，有确定的元数n≥1有一个特殊的谓词符号称为相等符号（等式），记为=。L可含或不含=，如果含有，即称为含=的一阶逻辑第3章逻辑系统27一阶语言(2)(3)无限序列的函数符号，有确定的元数m≥1(4)无限序列的自由变量：用u/v/w等表示自由变量(5)无限序列的约束变量：用x/y/z等表示约束变量(6)联结词：￢∧∨→≡(7)量词：、(8)标点：左右括号、逗号(),•一阶逻辑：描述对象和关系的陈述性、合成性的形式语言第3章逻辑系统28一阶语言的项和公式•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章逻辑系统29一阶语言的公式(1)•L的公式：一阶语言中的一个表达式是一个公式，当且仅当它能通过有限次使用下述步骤生成：(1)原子公式是公式；(2)如果A是公式，则(￢A)是公式；(3)如果A、B均为公式，则A*B是公式，其中*表示∧∨→≡中的任意一个(4)如果A(u)是公式，且x不在A(u)中出现，则xA(x)、xA(x)都是公式第3章逻辑系统30一阶语言的公式(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章逻辑系统31一阶语言的公式(3)•一阶谓词公式的例子•1所有人都是要死的•2有的人活到一百岁以上•在个体域D为人类集合时，可符号化为：1xP(x),其中P(x)表示x是要死的2xQ(x),其中Q(x)表示x活到一百岁以上•在个体域D是全总个体域时，引入特殊谓词R(x)表示x是人，可符号化为1x（R(x)P(x))2x(R(x)∧Q(x))第3章逻辑系统3.3逻辑推理举例wumpus世界第3章逻辑系统33wumpus世界(1)•Wumpus是一个早期电脑游戏中的怪物•Agent感知：•陷阱旁边有微风breeze•怪兽旁边有恶臭stench•金子闪闪发光glitter•感觉墙的反弹•陷阱和怪物的位置随机生成第3章逻辑系统stenchBreezePitWumpus(Monster)BreezeStenchGoldPitBreezestenchBreezeAgentBreezePitBreeze34wumpus世界(2)•Wumpus世界搜索图示—感知用5元组表示[感知wumpus,感知微风,感知金光,感知墙,感知wumpus被杀死]A=AgentB=BreezeG=Glitter,GoldOK=safesquareP=PitS=StenchV=visitedW=wumpusN=None1,42,43,44,41,32,33,34,31,2OK2,23,24,21,1AOK2,1OK3,14,1第3章逻辑系统1,42,43,44,41,32,33,34,31,2OK2,2P?3,24,21,1VOK2,1ABOK3,1P?4,1(a)[N,N,N,N,N](b)[N,B,N,N,N]35wumpus世界(3)1,42,43,44,41,3W!2,33,34,31,2ASOK2,2O