第5章 基于谓词逻辑的机器推理

2020/1/211第5章基于谓词逻辑的机器推理2020/1/212目录5.0机器推理概述5.1一阶谓词逻辑5.2归结演绎推理5.3应用归结原理求取问题答案5.4归结策略5.5归结反演程序举例*5.6Horn子句归结与逻辑程序5.7非归结演绎推理2020/1/2135.0机器推理概述（1）机器推理：就是计算机推理，也称自动推理。它是人工智能的核心课题之一。推理是人脑的一个基本功能和重要功能。几乎所有的人工智能领域都与推理有关。因此，要实现人工智能，就必须将推理的功能赋予机器，实现机器推理。自动定理证明：是机器推理的一种重要应用，它是利用计算机证明非数值性的结果，很多非数值领域的任务如医疗诊断、信息检索、规划制定和难题求解等方法都可以转化一个定理证明问题。2020/1/214自动定理证明的基本方法：5.0机器推理概述（2）定理证明器：它是研究一切可判定问题的证明方法。鲁滨逊的归结原理。人机交互进行定理证明：计算机作为数学家的辅助工具，用计算机帮助人完成手工证明中的难以完成的烦杂的大量计算推理和穷举。四色定理。判定法：该方法是对一类问题找出统一的计算机上可实现的算法。数学家吴文俊教授——吴氏方法。自然演绎法：该方法依据推理规则从前提和公理中可以推出许多定理，如果待证明的定理在其中则定理得证。LT程序、证明平面几何的程序。2020/1/215基于归结原理的自动定理证明过程：5.0机器推理概述（3）定理的自然语言描述定理的谓词公式描述子句集生成子句集定理得证应用归结规则＋归结策略自然语言处理生成谓词公式已知前提：F1：自然数都是大于零的整数。F2：所有整数不是偶数就是奇数。F3：偶数除以2是整数。结论G：所有自然数不是奇数就是一半为整数的数。定理的谓词公式描述：F1:x(N(x)GZ(x)I(x))F2:x(I(x)(E(x)O(x)))F3:x(E(x)I(s(x)))G:x(N(x)(I(s(x))O(x)))2020/1/2165.1一阶谓词逻辑5.1.1谓词、函数、量词5.1.2谓词公式5.1.3谓词逻辑中的形式演绎推理2020/1/2175.1.1谓词、函数、量词（1）命题（proposition）：是具有真假意义的语句。命题代表人们进行思维时的一种判断，或者是否定，或者是肯定。命题可以用命题符号表示。用命题符号可以表示简单的逻辑关系和推理。P:今天天气好Q:去旅游S1：我有名字S2：你有名字PQ表示：如果今天天气好，就去旅游。此时，如果P（今天天气好）成立，则可以得到结论Q（去旅游）2020/1/2185.1.1谓词、函数、量词（2）对于复杂的知识，命题符号能力不够。无法把所描述的客观事物的结构及逻辑特征反映出来。无法把不同事物间的共同特征表达出来。F：老李是小李的父亲。S1：我有名字S2：你有名字所有的人都有名字：SIS2S3…2020/1/2195.1.1谓词、函数、量词（3）谓词(predicate)：一般形式为P（x1,x2,…,xn）P为谓词名，用于刻画个体的性质、状态或个体间的关系。x1，x2，…，xn是个体，表示某个独立存在的事物或者某个抽象的概念。S(x):x是学生；P(x,y):x是y的父亲。个体变元的变化范围称为个体域。包揽一切事物的集合称为全总个体域。2020/1/21105.1.1谓词、函数、量词（4）函数：为了表达个体之间的对应关系，引入数学中函数概念和记法。用形如f(x1，x2，…，xn)来表示个体变元对应的个体y，并称之为n元个体函数，简称函数。函数father(x):值为x的父亲。谓词D(father(Li)):表示x的父亲是医生，值为真或假。符号约定：谓词－大写字母；P(x,y)函数－小写字母；f(x)变量－x、y、z、u、v……；常量－a、b、c…….。P(a,y)2020/1/21115.1.1谓词、函数、量词（5）表示“对个体域中所有的（或任一个）个体”。记为x全称量词表示“在个体域中存在个体”。记为x存在量词如：“凡是人都有名字”用M（x）表示“x是人”，N（x）表示“x有名字”x（M（x）N（x））如：“存在不是偶数的整数”用G（x）表示“x是整数”，E（x）表示“x是偶数”x（G（x）¬E（x））2020/1/21125.1.1谓词、函数、量词（6）用谓词表示命题时，一般取全总个体域，再采用使用限定谓词的方法来指出每个个体变元的个体域。(2)对存在量词，把限定词作为一个合取项加入。即x(P(x)…)例5.2：对于所有的自然数，均有x+yxxy（N（x）N（y）S(x,y,x)）例5.3：某些人对某些食物过敏xy(M(x)N(y)G（x，y））(1)对全称量词，把限定词作为蕴含式之前件加入。即x（P（x）…）例5.2：对于所有的自然数，均有x+yx也可以用函数h（x，y）来表示x与y的和xy（N（x）N（y）G(h(x,y),x)）2020/1/21135.1.1谓词、函数、量词（7）例5.1：不存在最大的整数，我们可以把它表示为：¬x(G(x)y（G（y）D（x，y））x(G(x)y（G（y）D（y，x））用谓词表示命题时，形式并不是固定的。2020/1/21145.1.1谓词、函数、量词（8）练习：用谓词公式表示下述命题。已知前提：（1）自然数都是大于零的整数。（2）所有整数不是偶数就是奇数。（3）偶数除以2是整数。结论：所有自然数不是奇数就是一半为整数的数。首先定义如下谓词：N(x):x是自然数。I(x):x是整数。E(x):x是偶数。O(x):x是奇数。GZ(x):x大于零。s(x):x除以2。2020/1/21155.1.1谓词、函数、量词（9）将上述各语句翻译成谓词公式：（1）自然数都是大于零的整数。F1:x(N(x)GZ(x)I(x))（2）所有整数不是偶数就是奇数。F2:x(I(x)(E(x)O(x)))（3）偶数除以2是整数。F3:x(E(x)I(s(x)))所有自然数不是奇数就是一半为整数的数。G:x(N(x)(I(s(x))O(x)))2020/1/21165.1.2谓词公式（1）定义1：项（1）个体常元和变元都是项。（2）f是n元函数符号，若t1，t2，…，tn是项，则f（t1，t2，…，tn）是项。（3）只有有限次使用（1），（2）得到的符号串才是项。用谓词、量词及真值连结词可以表达相当复杂的命题，我们把命题的这种符号表达式称为谓词公式。2020/1/21175.1.2谓词公式（2）定义2：原子公式设P为n元谓词符号，t1，t2，…，tn为项，P（t1，t2，…，tn）称为原子谓词公式，简称原子或原子公式。2020/1/21185.1.2谓词公式（3）定义3：谓词公式（1）原子公式是谓词公式。（2）若A、B是谓词公式，则¬A，AB，AB，AB，A←→B，xA，xA也是谓词公式。（3）只有有限步应用（1）（2）生成的公式才是谓词公式。谓词公式亦称为谓词逻辑中的合适（式）公式，记为Wff。由项的定义，当t1，t2，…，tn全为个体常元时，所得的原子谓词公式就是原子命题公式（命题符号）。所以全体命题公式也是谓词公式。2020/1/21195.1.2谓词公式（4）辖域：紧接于量词之后被量词作用（即说明）的谓词公式称为该量词的辖域。指导变元：量词后的变元为指导变元。约束变元：在一个量词辖域中与该量词的指导变元相同的变元称为约束变元。自由变元：谓词公式中除了约束变元之外的变元。（1）xP（x）（2）y（G（y）D（x，y））（3）xG(x)P（x）指导变元约束变元约束变元约束变元自由变元自由变元2020/1/21205.1.2谓词公式（5）一个变元在一个公式中既可以约束出现，也可以自由出现，为了避免混淆，通过改名规则改名：对需要改名的变元，应同时更改该变元在量词及其辖域中的所有出现。新变元符号必须是量词辖域内原先没有的，最好是公式中也未出现过的。xG(x)P（x）xG(x)P（y）2020/1/21215.1.2谓词公式（6）谓词公式与命题的区别与联系谓词公式是命题函数。一个谓词公式中所有个体变元被量化，谓词公式就变成了一个命题。从谓词公式得到命题的两种方法：给谓词中的个体变元代入个体常元；把谓词中的个体变元全部量化。例：P（x）表示“x是素数”xP（x），xP（x），P（a）都是命题2020/1/21225.1.2谓词公式（7）一阶谓词：仅个体变元被量化的谓词。二阶谓词：个体变元被量化，函数符号和谓词符号也被量化。PxP（x）全称命题：xP(x)等价于P(a1)P(a2)…P(an)特称命题xG(x)等价于P(a1)P(a2)…P(an)2020/1/21235.1.2谓词公式（8）定义4：合取范式（ConjunctiveNormalForm）设A为如下形式的谓词公式：B1B2…Bn其中Bi（i=1,2,…，n）形如L1L2…Lm，Lj（j=1，2,…，m）为原子公式或其否定，则A称为合取范式。例(P(x)Q(y))(¬P(x)Q(y)R(x,y))(¬Q(x)¬R(x,y))就是一个合取范式2020/1/21245.1.2谓词公式（9）定义5：析取范式（DisjunctiveNormalForm）设A为如下形式的谓词公式：B1B2…Bn其中Bi（i=1,2,…，n）形如L1L2…Lm，Lj（j=1，2,…，m）为原子公式或其否定，则A称为析取范式。例(P(x)¬Q(y)R(x,y))(¬P(x)Q(y))(¬P(x)R(x,y))就是一个析取范式2020/1/21255.1.2谓词公式（10）*谓词公式的解释设D为谓词公式P的个体域，若对P中的个体常量、函数和谓词按如下规定赋值：（1）为每个个体常量指派D中的一个元素；（2）为每个n元函数指派一个从Dn到D的映射，其中Dn＝{(x1,x2,…,xn)/x1,x2,…,xn∈D}（3）为每个n元谓词指派一个从Dn到{F,T}的映射。则称这些指派为公式P在D上的一个解释。2020/1/21265.1.2谓词公式（11）*例：设个体域D＝{1,2},求公式A＝xyP（x，y）在D上的解释，并指出在每一种解释下公式A的真值。解：公式里没有个体常量和函数，所以直接为谓词指派真值，设为P（1，1）＝TP（1，2）＝FP（2，1）＝TP（2，2）＝F这就是A在D上的一个解释。在此解释下：当x＝1时有y＝1使P（x，y）的真值为T；当x＝2时有y＝1使P（x，y）的真值为T；即对于D中的所有X都有y＝1使P（x，y）的真值为T，所以在此解释下公式A的真值为T。2020/1/21275.1.2谓词公式（12）*例：设个体域D＝{1,2},求公式A＝xP（x）Q（f(x),b）在D上的解释，并指出在每一种解释下公式A的真值。解：为个体常量b指派D中的值：b=1为函数f(x)指派D中的值f(1)=2,f(2)=1对谓词指派真值为：P(1)=F,P(2)=T,Q(1,1)=T,Q(2,1)=F2020/1/21285.1.2谓词公式（13）*在此解释下，当x＝1时有：P(1)=F,Q(f(1),1)=Q(2,1)=F所以P（x）Q（f(x),b）为T。当x＝2时有P(2)=T,Q(f(2),1)=Q(1,1)=T所以P（x）Q（f(x),b）为T。即对个体域D中的所有x均有P（x）Q（f(x),b），所以公式B在此解释下的真值为T。2020/1/21295.1.2谓词公式（14）定义6：谓词公式在个体域上的永真、永假、可满足设P为谓词公式，D为其个体域，对于D中的任一解释I：（1）若P恒为真，则称P在D上永真或是D上的永真式。（2）若P恒为假，则称P在D上永假或是D上的永假式。（3）若至少有一个解释，可是P为真，则称P在D上是可满足式。2020