第3章-基于谓词逻辑的知识表示与机器推理

2020/5/181第3章基于谓词逻辑的知识表示与机器推理2020/5/182内容3.1机器推理概述3.2谓词逻辑简介3.3自然演绎推理3.4归结演绎推理3.5归结原理与PROLOG程序3.6基于规则的演绎推理2020/5/1833.1机器推理概述机器推理推理是人脑的一个基本功能和重要功能，几乎所有的人工智能领域都与推理有关。因此，要实现人工智能，就必须将推理的功能赋予机器，实现机器推理。机器推理也称为是计算机推理，或自动推理，它也是人工智能的核心课题之一。自动定理证明：是机器推理的一种重要应用，它是利用计算机证明非数值性的结果，很多非数值领域的任务如医疗诊断、信息检索、规划制定和难题求解等方法都可以转化一个定理证明问题。2020/5/184基于归结原理的自动定理证明过程：3.1机器推理概述定理的自然语言描述定理的谓词公式描述子句集生成子句集定理得证应用归结规则和归结策略自然语言处理生成谓词公式已知前提：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/5/1853.2谓词逻辑简介3.2.1基于命题逻辑的知识表示3.2.2谓词逻辑3.2.3基于谓词逻辑的知识表示2020/5/1863.2.1基于命题逻辑的知识表示（1）定义3.1命题（proposition）：是具有真假意义的语句。命题代表人们进行思维时的一种判断，或否定，或肯定。命题可以用命题符号表示。用命题符号可以表示简单的逻辑关系和推理。R:今天天气好S:去旅游S1：我有名字S2：你有名字RS表示：如果今天天气好，就去旅游。此时，如果R（今天天气好）成立，则可以得到结论S（去旅游）2020/5/1873.2.1基于命题逻辑的知识表示（2）对于复杂的知识，命题符号能力不够。无法把所描述的客观事物的结构及逻辑特征反映出来。无法把不同事物间的共同特征表达出来。P：大李是小李的父亲。S1：我有名字S2：你有名字所有的人都有名字：SIS2S3…2020/5/1883.2.2谓词逻辑（1）谓词(predicate)：一般形式为P（x1,x2,…,xn）P为谓词名（谓词符号），用于刻画个体的性质、状态或个体间的关系。x1，x2，…，xn是个体，表示某个独立存在的事物或者某个抽象的概念。S(x):x是学生；P(x,y):x是y的父亲。个体变元的变化范围称为个体域。包揽一切事物的集合称为全总个体域。2020/5/1893.2.2谓词逻辑（2）函数：为了表达个体之间的对应关系，引入数学中函数概念和记法。用形如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/5/18103.2.2谓词逻辑（3）为了表示命题中出现的“全部”、“所有”、“一切”、“任一”或“凡是”等意义，引入全称量词，记为x。为了表示命题中出现的“存在”、“某些”、“有一个”等意义，引入存在量词，记为x。如：“某些学生对某些课外活动感兴趣”S(x)表示x是学生，L(y)表示y是课外活动，I(x,y)表示x对y感兴趣。(()()())xySxLyIxy，2020/5/18113.2.2谓词逻辑（4）定义3.2：项（1）个体常元和变元都是项。（2）f是n元函数符号，若t1，t2，…，tn是项，则f（t1，t2，…，tn）是项。（3）只有有限次使用（1），（2）得到的符号串才是项。2020/5/18123.2.2谓词逻辑（5）定义3.3：原子公式设P为n元谓词符号，t1，t2，…，tn为项，P（t1，t2，…，tn）称为原子谓词公式，简称原子或原子公式。2020/5/18133.2.2谓词逻辑（6）定义3.4：谓词公式（1）原子公式是谓词公式。（2）若A、B是谓词公式，则¬A，AB，AB，AB，A←→B，xA，xA也是谓词公式。（3）只有有限步应用（1）（2）生成的公式才是谓词公式。2020/5/18143.2.2谓词逻辑（7）辖域：紧接于量词之后被量词作用（即说明）的谓词公式称为该量词的辖域。指导变量：量词后的变量为量词的指导变量。约束变量：在一个量词辖域中与该量词的指导变元相同的变量称为约束变量。自由变量：谓词公式中除了约束变量之外的变量。（1）（2）（3）(,)xSxy()()yFyDy((()())(,))xyWxLxPxy2020/5/18153.2.2谓词逻辑（8）一个变元在一个公式中既可以约束出现，也可以自由出现，为了避免混淆，通过改名规则改名：对需要改名的变元，应同时更改该变元在量词及其辖域中的所有出现。新变元符号必须是量词辖域内原先没有的，最好是公式中也未出现过的。yF(y)D（y）xF(x)D（y）2020/5/18163.2.2谓词逻辑（9）谓词公式与命题的区别与联系谓词公式是命题函数。一个谓词公式中所有个体变元被量化，谓词公式就变成了一个命题。从谓词公式得到命题的两种方法：给谓词中的个体变元代入个体常元；把谓词中的个体变元全部量化。例：P（x）表示“x是素数”xP（x），xP（x），P（a）都是命题2020/5/18173.2.2谓词逻辑（10）一阶谓词：仅个体变元被量化的谓词。二阶谓词：个体变元被量化，函数符号和谓词符号也被量化。PxP（x）全称命题：xP(x)等价于P(a1)P(a2)…P(an)特称命题xG(x)等价于P(a1)P(a2)…P(an)2020/5/18183.2.2谓词逻辑（11）定义3.5：合取范式（ConjunctiveNormalForm）设A为如下形式的谓词公式：B1B2…Bn其中Bi（i=1,2,…，n）形如L1L2…Lm，Lj（j=1，2,…，m）为原子公式或其否定，则A称为合取范式。例就是一个合取范式(()())(()())(()())PxQxQyRyPzSz2020/5/18193.2.2谓词逻辑（12）定义3.6：析取范式（DisjunctiveNormalForm）设A为如下形式的谓词公式：B1B2…Bn其中Bi（i=1,2,…，n）形如L1L2…Lm，Lj（j=1，2,…，m）为原子公式或其否定，则A称为析取范式。例如(¬D(y)L(a,y))(¬P(x)C(z))(¬P(u)L(u,v))就是一个析取范式2020/5/18203.2.2谓词逻辑（13）定义3.7谓词公式的解释设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/5/18213.2.2谓词逻辑（14）例3.1：设个体域D＝{1,2},求公式在D上的解释，并指出在每一种解释下公式A的真值。解：设公式A中对个体常量b、函数f（x）指派的真值分别为：b=2，f(1)=2，f(2)=1对谓词指派的真值为：P(1，1)=T，P(1，2)=T，P(2，1)=T，P(2，2)=FQ(1，2)=F，Q(2，2)=T((,)((),))AxyPxyQfxb2020/5/18223.2.2谓词逻辑（15）在此解释下，由于当x=1时，有y=2，使得：：所以为T。当x=2时，有y=2，使得所以为T。所以公式A在此解释下真值为T。(1,2)((1),2)(2,2)PTQfQT，(,)((),2)PxyQfx(2,2)((2),2)(1,2)PFQfQF，(,)((),2)PxyQfx2020/5/18233.2.2谓词逻辑（16）定义3.8：谓词公式的永真如果谓词公式P对个体域D上的任何一个解释都取得真值T，则称P在D上是永真的；如果P在全总个体域上永真，则称P永真。定义3.9：谓词公式的可满足性对于谓词公式P，如果在个体域D上至少存在一个解释使得公式P在此解释下的真值为T，则称公式P在D上是可满足的。谓词公式的可满足性又称相容性。2020/5/18243.2.2谓词逻辑（17）定义3.9：谓词公式的永假如果谓词公式P对于个体域D上的任何一个解释都取得真值F，则称P在D上是永假的；如果P在全总个体域上永假，则称P永假。谓词公式的永假性又称不可满足性或不相容。2020/5/18253.2.3基于谓词逻辑的知识表示（1）用谓词表示命题时，一般取全总个体域，再采用使用限定谓词的方法来指出每个个体变元的个体域。(2)对存在量词，把限定词作为一个合取项加入。即x(P(x)…)(1)对全称量词，把限定词作为蕴含式之前件加入。即x（P（x）…）用谓词表示命题：•先定义谓词、函数•事实用谓词公式与或形表示•规则用蕴含式表示2020/5/18263.2.3基于谓词逻辑的知识表示（2）例3.2设有如下命题：（1）小明比他的哥哥学习努力。定义谓词：：x比y学习努力定义函数：：x的哥哥谓词公式表示为：(,)StudyHarderxybrotherx()StudyHarderabrothera(,())2020/5/18273.2.3基于谓词逻辑的知识表示（3）（2）对于所有的自然数，均有。定义谓词：：x是自然数：x大于等于y定义函数：：x与y的和谓词公式表示为：xyx()Naturex(,)GExy(,)sumxy(()()((,),))xyNaturexNatureyGEsumxyy2020/5/18283.2.3基于谓词逻辑的知识表示（4）（3）某些人对某些食物过敏。定义谓词：：x是人：x是食物：x对y过敏谓词公式表示为：()Mx()Fx(,)Sxy(()()(,))xyMxFySxy2020/5/18293.2.3基于谓词逻辑的知识表示（5）例3.3用谓词公式表示下述命题。已知前提：F1：自然数都是大于零的整数。F2：所有整数不是偶数就是奇数。F3：偶数除以2是整数。结论：所有自然数不是奇数就是一半为整数的数。首先定义如下谓词：N(x):x是自然数。I(x):x是整数。E(x):x是偶数。O(x):x是奇数。GZ(x):x大于零。定义函数s(x):x除以2。2020/5/18303.2.3基于谓词逻辑的知识表示（6）将上述各语句翻译成谓词公式：F1：自然数都是大于零的整数。x(N(x)GZ(x)I(x))F2：所有整数不是偶数就是奇数。x(I(x)(E(x)O(x)))F3：偶数除以2是整数。x(E(x)I(s(x)))所有自然数不是奇数就是一半为整数的数。G:x(N(x)(I(s(x))O(x)))2020/5/18313.2.3基于谓词逻辑的知识表示（7）例3.4设在一个房间里，a和b是两张桌子，a处桌子上放有一个盒子box，c处有一个机器人Robot，为了让机器人从c处出发把盒子从a处拿到b处的桌子上，然后再回到c处，用谓词逻辑描述从初始状态到目标状态的机器人操作过程。解：定义谓词Table(x)：表示x是桌子Empty(Robot)：表示机器人Robot手是空的At(Robot,x)：表示机器人Robot在x处Holds(Robot,Box)：机器人Robot拿着BoxOn(Box,x)：盒子在x上2020/5/18323.2.3基于谓