人工智能-谓词逻辑1课件

谓词逻辑基础一阶逻辑基本概念个体词：表示主语的词谓词：刻画个体性质或个体之间关系的词量词：表示数量的词

小王是个工程师。

8是个自然数。 我去买花。 小丽和小华是朋友。其中，“小王”、“工程师”、“我”、“花”、“8”、“小丽”、“小华”都是个体词，而“是个工程师”、“是个自然数”、“去买”、“是朋友”都是谓词。显然前两个谓词表示的是事物的性质，第三个谓词“去买”表示的一个动作也表示了主、宾两个个体词的关系，最后一个谓词“是朋友”表示两个个体词之间的关系。谓词逻辑基础谓词逻辑基础例如：（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)）,

其中，R(x)表示x是人；P(x)表示x是要死的。（2）x（R(x)∧Q(x)）， 其中，R(x)表示x是人；Q(x)表示x活到一百岁以上。

一阶逻辑公式及其解释个体常量：a,b,c个体变量：x,y,z谓词符号：P,Q,R量词符号：

,谓词逻辑基础量词否定等值式：～(x

）

P（x）<=>（

y

）～

P（y）～(x

）

P（x）<=>（

y

）～

P（y）量词分配等值式：(x

）(

P（x）∧

Q（x）)<=>(x

）

P（x）∧

(x

）

Q（x）(x

）(

P（x）∨

Q（x）)<=>(x

）

P（x）∨

(x

）

Q（x）消去量词等值式：设个体域为有穷集合（a1,a2,…an）(x

）

P（x）<=>P（a1

）∧

P（a2

）∧

…

∧

P（an

）(x

）P（x）<=>P（a1

）∨

P（a2

）∨

…

∨

P（an

）谓词逻辑基础量词辖域收缩与扩张等值式：(x

）(

P（x）∨Q)<=>(x

）

P（x）∨Q(x

）(

P（x）∧

Q)<=>(x

）

P（x）∧

Q

(x

）(

P（x）→Q)<=>(x

）

P（x）→Q

(x

）(Q

→P（x）)<=>Q

→(x

）

P（x）(x

）(

P（x）∨Q)<=>(x

）

P（x）∨Q(x

）(

P（x）∧

Q)<=>(x

）

P（x）∧

Q

(x

）(

P（x）→Q)<=>(x

）

P（x）→Q

(x

）(Q

→P（x）)<=>Q

→(x

）

P（x）谓词逻辑基础谓词逻辑基础SKOLEM标准形前束范式

定义：说公式A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。谓词逻辑归结原理即：把所有的量词都提到前面去，然后消掉所有量词

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)约束变项换名规则：(Qx

）

M（x）<=>（Qy

）

M（y）(Qx

）

M（x,z）<=>（Qy

）

M（y,z）谓词逻辑归结原理

量词消去原则： 消去存在量词“”，略去全程量词“”。 注意：左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数；如没有，改写成为常量。

谓词逻辑归结原理Skolem定理： 谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。SKOLEM标准形定义： 消去量词后的谓词公式。注意：谓词公式G的SKOLEM标准形同G并不等值。谓词逻辑归结原理例：将下式化为Skolem标准形：

～(x)(y)P(a,x,y)→(x)(～(y)Q(y,b)→R(x))解：第一步，消去→号，得：～(～(x)(y)P(a,x,y))∨(x)(～～(y)Q(y,b)∨R(x))第二步，～深入到量词内部，得：

(x)(y)P(a,x,y)∨(x)((y)Q(y,b)∨R(x))第三步，变元易名，得

(x)(y)P(a,x,y)∨(u)(v)(Q(v,b)∨R(u))第四步，存在量词左移，直至所有的量词移到前面， (x)(y)(u)(v)(P(a,x,y)∨(Q(v,b)∨R(u))由此得到前述范式第五步，消去“”（存在量词），略去“”全称量词 消去(y)，因为它左边只有(x)，所以使用x的函数f(x)代替之，这样得到：

(x)(u)(v)(P(a,x,f(x))∨Q(v,b)∨R(u))

消去(u)，同理使用g(x)代替之，这样得到：

(x)(v)(P(a,x,f(x))∨

Q(v,b)∨

R(g(x)))

则，略去全称变量，原式的Skolem标准形为：

P(a,x,f(x))∨

Q(v,b)∨

R(g(x))

子句与子句集文字：不含任何连接词的谓词公式。子句：一些文字的析取（谓词的和）。子句集S的求取：

G→SKOLEM标准形 →消去存在变量 →以“，”取代“∧”，并表示为集合形式。谓词逻辑归结原理

G是不可满足的<=>S是不可满足的G与S不等价，但在不可满足得意义下是一致的。

定理： 若G是给定的公式，而S是相应的子句集，则G是不可满足的<=>S是不可满足的。

注意：G真不一定S真，而S真必有G真。 即：S=>G谓词逻辑归结原理G=G1ΛG2ΛG3Λ…ΛGn

的子句形G的字句集可以分解成几个单独处理。

有SG=S1US2US3U…USn

则SG

与S1US2US3U…USn在不可满足得意义上是一致的。 即SG

不可满足<=>S1US2US3U…USn不可满足3.3谓词逻辑归结原理例：对所有的x,y,z来说，如果y是x的父亲，z又是y的父亲，则z是x的祖父。又知每个人都有父亲，试问对某个人来说谁是它的祖父？求：用一阶逻辑表示这个问题，并建立子句集。解：这里我们首先引入谓词：

P(x,y)表示x是y的父亲

Q(x,y)表示x是y的祖父

ANS(x)表示问题的解答谓词逻辑归结原理对于第一个条件，“如果x是y的父亲，y又是z的父亲，则x是z的祖父”，一阶逻辑表达式如下：

A1：(x)(y)(z)(P(x,y)∧P(y,z)→Q(x,z)) SA1：～P(x,y)∨～P(y,z)∨Q(x,z)对于第二个条件：“每个人都有父亲”，一阶逻辑表达式：

A2：(y)(x)P(x,y) SA2：P(f(y),y)对于结论：某个人是它的祖父

B：(x)(y)Q(x,y)

否定后得到子句：～（(x)(y)Q(x,y)）∨ANS(x) S～B：～Q(x,y)∨ANS(x)则得到的相应的子句集为：{SA1，SA2，S～B}谓词逻辑归结原理归结原理正确性的根本在于，找到矛盾可以肯定不真。方法：和命题逻辑一样。但由于有函数，所以要考虑合一和置换。

谓词逻辑归结原理置换：可以简单的理解为是在一个谓词公式中用置换项去置换变量。定义： 置换是形如{t1/x1,t2/x2,…,tn/xn}的有限集合。其中，x1,x2,…,xn是互不相同的变量，t1,t2,…,tn是不同于xi的项（常量、变量、函数）；ti/xi表示用ti置换xi，并且要求ti与xi不能相同，而且xi不能循环地出现在另一个ti中。例如

{a/x，c/y，f(b)/z}是一个置换。

{g(y)/x，f(x)/y}不是一个置换，

谓词逻辑归结原理置换置换的合成设＝{t1/x1,t2/x2,…,tn/xn}， ＝{u1/y1,u2/y2,…,un/yn}，是两个置换。 则与的合成也是一个置换，记作·。它是从集合

{t1·/x1,t2·/x2,…,tn·/xn,u1/y1,u2/y2,…,un/yn}

中删去以下两种元素：i.

当ti=xi时，删去ti/xi(i=1,2,…,n);Ii.

当yi{x1,x2,…,xn}时，删去uj/yj(j=1,2,…,m)

最后剩下的元素所构成的集合。合成即是对ti先做置换然后再做置换，置换xi谓词逻辑归结原理例：设：＝{f(y)/x,z/y}，＝{a/x,b/y,y/z}，求与的合成。解：先求出集合

{f(b/y)/x,(y/z)/y,a/x,b/y,y/z}＝{f(b)/x,y/y,a/x,b/y,y/z}

其中，f(b)/x中的f(b)是置换作用于f(y)的结果；y/y中的y是置换作用于z的结果。在该集合中，y/y满足定义中的条件i，需要删除；a/x，b/y满足定义中的条件ii，也需要删除。最后得

·＝{f(b)/x，y/z}谓词逻辑归结原理合一合一可以简单地理解为“寻找相对变量的置换，使两个谓词公式一致”。定义：设有公式集F＝{F1，F2，…，Fn}，若存在一个置换，可使F1＝F2＝…=Fn，则称是F的一个合一。同时称F1，F2，...，Fn是可合一的。

例： 设有公式集F＝{P(x,y,f(y)),P(a,g(x),z)}，则＝{a/x,g(a)/y,f(g(a))/z}是它的一个合一。注意：一般说来，一个公式集的合一不是唯一的。

谓词逻辑归结原理谓词逻辑归结原理谓词逻辑归结原理谓词逻辑归结原理归结原理归结的注意事项：谓词的一致性，P()与Q()，不可以常量的一致性，P(a,…)与P(b,….)，不可以 变量，P(a,….)与P(x,…)，可以变量与函数，P(a,x,….)与P(x,f(x),…)，不可以；是不能同时消去两个互补对，P∨Q与～P∨～Q的空，不可以先进行内部简化（置换、合并）

谓词逻辑归结原理归结的过程写出谓词关系公式→用反演法写出谓词表达式→SKOLEM标准形→子句集S→对S中可归结的子句做归结→归结式仍放入S中，反复归结过程→得到空子句

▯得证谓词逻辑归结原理例题“快乐学生”问题假设任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有的考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。

解：先将问题用谓词表示如下：R1:“任何通过计算机考试并获奖的人都是快乐的”

(x)((Pass(x,computer)∧Win(x,prize))→Happy(x))R2:“任何肯学习或幸运的人都可以通过所有考试”

(x)(y)(Study(x)∨Lucky(x)→Pass(x,y))R3:“张不肯学习但他是幸运的” ～Study(zhang)∧Lucky(zhang)R4:“任何幸运的人都能获奖”

(x)(Luck(x)→Win(x,prize))结论：“张是快乐的”的否定～Happy(zhang)例题“快乐学生”问题由R1及逻辑转换公式:P∧W→H=～（P∧W）∨H，可得

(1)～Pass(x,computer)∨～Win(x,prize)∨Happy(x)由R2：(2)～Study(y)∨Pass(y,z)(3)～Lucky(u)∨Pass(u,v)由R3：(4)～Study(zhang)(5)Lucky(zhang)由R4：(6)～Lucky(w)∨Win(w，prize)由结论：(7)～Happy(zhang) （结论的否定）(8)～Pass(w,computer)∨Happy(w)∨～Luck(w)(1)(6)，{w/x}(9)～Pass(zhang,computer)∨～Lucky(zhang)(8)(7)，{zhang/w}(10)

～Pass(zhang,computer) (9)(5)(11)

～Lucky(zhang) (10)(3)，{zhang/u,computer/v}(12)

ɓ

(11)(5)

归结法的实质：归结法是仅有一条推理规则的推理方法。归结的过程是一个语义树倒塌的过程。归结法的问题子句中有等号或不等号时，完备性不成立。※Herbrand定理的不实用性引出了可实用的归结法。谓词逻辑归结原理归结过程的控制策略要解决的问题：归结方法的知识爆炸。控制策略的目的归结点尽量少控制策略的原则给出控制策略，以使仅对选择合适的子句间方可做归结。避免多余的、不必要的归结式出现。或者说，少做些归结仍能导出空子句。谓词逻辑归结原理

删除策略 => 完备名词解释：归类：设有两个子句C和D，若有置换使得C

D成立，则称子句C把子句D归类。 由于小的可以代表大的，所以小的吃掉大的了。若对S使用归结推理过程中，当归结式Cj是重言式（永真式）和Cj被S中子句和子句集的归结式Ci(i<j)所归类时，便将Cj删除。这样的推理过程便称做使用了删除策略的归结过程。谓词逻辑归结原理主要思想：归结过程在寻找可归结子句时，子句集中的子句越多，需要付出的代价就会越大。如果在归结时能把子句集中无用的子句删除掉，就会缩小搜索范围，减少比较次数，从而提高归结效率。删除策略对阻止不必要的归结式的产生来缩短归结过程是有效的。然而要在归结式Cj产生后方能判别它是否可被删除，这部分计算量是要花费的，只是节省了被删除的子句又生成的归结式。尽管使用删除策略的归结，少做了归结但不影响产生空子句，就是说删除策略的归结推理是完备的。谓词逻辑归结原理采用支撑集 <=>完备

支撑集：设有不可满足子句集S的子集T，如果S-T是可满足的，则T是支持集。

采用支撑集策略时，从开始到得到的整个归结过程中，只选取不同时属于S-T的子句，在其间进行归结。就是说，至少有一个子句来自于支撑集T或由T导出的归结式。

谓词逻辑归结原理例如：A1ΛA2ΛA3Λ～B中的～B可以作为支撑集使用。要求每一次参加归结的亲本子句中，只要应该有一个是有目标公式的否定（～B）所得到的子句或者它们的后裔。支撑集策略的归结是完备的，同样，所有可归结的谓词公式都可以用采用支撑集策略达到加快归结速度的目的。问题是如何寻找合适的支撑集。一个最容易找到的支撑集是目标子句的非，即S～B。谓词逻辑归结原理ST可满足支撑集示意图谓词逻辑归结原理

语义归结 <=> 完备 语义归结策略是将子句S按照一定的语义分成两部分，约定每部分内的子句间不允许作归结。同时还引入了文字次序，约定归结时其中的一个子句的被归结文字只能是该子句中“最大”的文字。 语义归结策略的归结是完备的，同样，所有可归结的谓词公式都可以用采用语义归结策略达到加快归结速度的目的。问题是如何寻找合适的语义分类方法，并根据其含义将子句集两个部分中的子句进行排序。

谓词逻辑归结原理

线性归结<=>完备线性归结策略首先从子句集中选取一个称作顶子句的子句C0开始作归结。归结过程中所得到的归结式Ci立即同另一子句Bi进行归结得归结式Ci+1。而Bi属于S或是已出现的归结式Cj(j<i)。即，如下图所示归结得到的新子句立即参加归结。线性归结是完备的，同样，所有可归结的谓词公式都可以采用线性归结策略达到加快归结速度的目的。如果能搞找到一个较好的顶子句，可以式归结顺利进行。否则也可能事与愿违。

C0C1C2C3C4C5空线性归结策略示意图

单元归结 => 完备

单元归结策略要求在归结过程中，每次归结都有一个子句是单元子句（只含一个文字的子句）或单元因子。显而易见，词中方法可以简单地削去另一个非单子句中的一个因子，使其长度减少，构成简单化，归结效率较高。初始子句集中没有单元子句时，单元归结策略无效。所以说“反之不成立”，即此问题不能采用单元归结策略。

输入归结 => 完备

与单元归结策略相似，输入归结策略要求在归结过程中，每一次归结的两个子句中必须有一个是S的原始子句。这样可以避免归结出的不必要的新子句加入归结，造成恶性循环。可以减少不必要的归结次数。

如同单元归结策略，不是所有的可归结谓词公式的最后结论都是可以从原始子句集中的得到的。简单的例子，归结结束时，即最后一个归结式为空子句的条件是，参加归结的双方必须是两个单元子句。原始子句集中没有单元子句的谓词公式一定不能采用输入归结策略。

人工智能

是一门交叉学科

脑科学认知科学心理学语言学逻辑学哲学计算机科学人工智能什么是人工智能人工智能的定义可以分为两部分，即“人工”和“智能”。关于什么是“智能”？智能需要具备的特征？具有感知能力（系统输入）:

机器视觉，机器听觉，图像语音识别……具有记忆与思维能力：思维是智能的根本原因，思维是一个动态的过程。思维分为：逻辑思维，形象思维和顿悟思维。具有学习能力及自适应能力：适应环境的变换、积累经验的能力

具有行为能力（系统输出）：对外界的智能化反应早期判断是否有智能的方法———图灵测试英国数学家阿兰·图灵(AlanTuring)提出了现称为“图灵测试”(TuringTest)的方法。简单来讲,图灵测试的做法是:让一位测试者分别与一台计算机和一个人进行交谈(当时是用电传打字机),而测试者事先并不知道哪一个是人,哪一个是计算机。如果交谈后测试者分不出哪一个被测者是人,

哪一个是计算机,则可以认为这台被测的计算机具有智能。

Turing测试存在的问题“图灵测试”没有规定问题的范围和提问的标准仅反映了结果的比较，无涉及思维过程没指出是什么人争论：通过了图灵检验的电脑就具备思维能力了么？测试主持人被测机器被测人中文屋子约翰·西尔勒的中文屋子假设是说:有一台计算机阅读了一段故事并且能正确回答相关问题,这样这台计算就通过了图灵测试。而西尔勒设想将这段故事和问题改用中文描述(因为他本人不懂中文),然后将自己封闭在一个屋子里,代替计算机阅读这段故事并且回答相关问题。描述这段故事和问题的一连串中文符号只能通过一个很小的缝隙被送到屋子里。西尔勒则完全按照原先计算机程序的处理方式和过程(如符号匹配、查找、照抄等)对这些符号串进行操作,然后把得到的结果即问题答案通过小缝隙送出去。西尔勒也得到了问题的正确答案。西尔勒认为尽管计算机用这种符号处理方式也能正确回答问题,并且也可通过图灵测试,但仍然不能说计算机就有了智能。

人工智能的发展概况

1.形成期（1956--1970年）AI诞生于一次历史性的聚会(Dartmouth人工智能夏季研讨会)时间：1956年夏季地点：美国达特茅斯(Dartmouth)大学目的：为使计算机变得更“聪明”，或者说使计算机具有智能发起人：麦卡锡(J.McCarthy），Dartmouth的年轻数学家、计算机专家，后为MIT教授明斯基(M.L.Minsky），哈佛大学数学家、神经学家，后为MIT教授洛切斯特(N.Lochester)，IBM公司信息中心负责人香农(C.E.Shannon)，贝尔实验室信息部数学研究员会议结果：由麦卡锡提议正式采用了“ArtificialIntelligence”这一术语人工智能的发展概况2.形成期（1956----1970年）其他开创性贡献1958年，美籍华人数理逻辑学家王浩在IBM-740计算机上仅用了3-5分钟就证明了《数学原理》命题演算全部220条定理。1965年，费根鲍姆(E.A.Feigenbaum)开始研究化学专家系统DENDRAL，用于质谱仪分析有机化合物的分子结构。1969年召开了第一届国际人工智能联合会议（InternationalJointConferenceonAI，IJCAI），标志着人工智能作为一门独立学科登上了国际学术舞台。此后IJCAI每两年召开一次。1970年《InternationalJournalofAI》创刊。人工智能的发展概况3.暗淡期（1966----1974年）失败的预言给人工智能的声誉造成重大伤害“20年内，机器将能做人所能做的一切”---------1965在博弈方面：塞缪尔的下棋程序在与世界冠军对弈时，5局败了4局。在定理证明方面：发现鲁宾逊归结法的能力有限。当用归结原理证明两个连续函数之和还是连续函数时，推了10万步也没证出结果。在机器翻译方面：发现并不那么简单，甚至会闹出笑话。例如，把“心有余而力不足”的英语句子翻译成俄语，再翻译回来时竟变成了“酒是好的，肉变质了”在问题求解方面：对于不良结构，会产生组合爆炸问题。在神经生理学方面：研究发现人脑有1011-12以上的神经元，在现有技术条件下用机器从结构上模拟人脑是根本不可能的。在英国，剑桥大学的詹姆教授指责“人工智能研究不是骗局，也是庸人自扰”。从此，形势急转直下，在全世界范围内人工智能研究陷入困境、落入低谷。

人工智能的发展概况

4.知识应用期（1970----1988年）整个20世纪80年代，专家系统和知识工程在全世界得到了迅速发展。专家系统为企业等用户赢得了巨大的经济效益。在开发专家系统过程中，许多研究者获得共识，即人工智能系统是一个知识处理系统，而知识获取、知识表示和知识利用则成为人工智能系统的三大基本问题。同时出现新的问题：专家系统本身所存在的应用领域狭窄、缺乏常识性知识、知识获取困难、推理方法单一、没有分布式功能、不能访问现存数据库等问题被逐渐暴露出来。人工智能的发展概况

5.集成发展期（1986年以来）1997年5月11日，由IBM研制的超级计算机“深蓝”首次击败了国际象棋特级大师卡斯帕洛夫。2000年，中国科学院计算所开发出知识发现系统MSMiner。该系统是一种多策略知识发现平台，能够提供快捷有效的数据挖掘解决方案，提供多种知识发现方法。2011年，IBM超级电脑“沃森”亮相美国最受欢迎的智力竞赛节目《危险边缘》战胜该节目两位最成功的选手。人工智能研究形成了三大学派符号主义连接主义行为主义符号主义又称：逻辑主义、心理学派或计算机学派符号主义的实现基础是纽威尔和西蒙提出的物理符号系统假设。该学派认为：人类认知和思维的基本单元是符号，而认知过程就是在符号表示上的一种运算。它认为人是一个物理符号系统,计算机也是一个物理符号系统,因此,我们就能够用计算机来模拟人的智能行为,即用计算机的符号操作来模拟人的认知过程。这种方法的实质就是模拟人的左脑抽象逻辑思维，通过研究人类认知系统的功能机理，用某种符号来描述人类的认知过程，并把这种符号输入到能处理符号的计算机中，就可以模拟人类的认知过程，从而实现人工智能。可以把符号主义的思想简单的归结为“认知即计算”。连接主义又称：仿生学派或生理学派原