第三章一阶谓词逻辑

第三章一阶谓词逻辑表示知识§3.1一阶谓词逻辑形式§3.2谓词公式、永真性、可满足性、不可满足性§3.3谓词公式的等价性与永真蕴含§3.4自然演绎推理§3.5归结演绎推理§3.6归结策略讨论3.1一阶谓词逻辑形式前面离散数学课程已经讲述过谓词逻辑，在这里简要回顾如下：1.命题逻辑定义具有确定真值的陈述句，称为命题。例：(1)2是素数。(2)雪是黑的。(3)今年的十二月一号是个晴天。(4)X+Y5命题若是简单的陈述句，不能分解成更简单的句子，我们称这样的命题为简单命题或原子命题。可以用英文字母P，Q，R，…或是带有下标的大写英文字母Pi等表示简单命题，将命题用合适的符号表示，称为命题符号化。命题逻辑的局限性：例如：命题:焦作是一个漂亮的城市P郑州是一个漂亮的城市Q晋城是一个漂亮的城市R新乡是一个漂亮的城市S安阳是一个漂亮的城市T要表达这样一个类别的知识时，命题逻辑表达起来，不方便。用谓词结构的形式最方便定义谓词：BeautifulCity(x);x是一个漂亮的城市像这样表达知识的形式就是谓词表达知识的形式2、一阶谓词逻辑谓词的一般形式是:P(x1,x2,…xn)其中P是谓词，通常才用首字母大写开头的字母字符串表示。x1,x2,x3………是个体,通常用小写字母来表示。在谓词逻辑中，命题被细分为谓词和个体两个部分。n元谓词：含有n个个体符号的谓词P(x1,x2,…xn)，表示一个映射：P：Dn→{T，F}或是(D1×D2×D3…Dn)→{T，F}谓词：用于刻画个体的性质、状态或个体之间的关系，称为谓词。谓词一般也用P,Q,R等大写字母表示。例1：x是一个美丽的城市可以写成：BeautifulCity(x)其中：BeautifulCity是谓词；x是个体例2：xy可定义成：Greater(x,y)这里：x、y是个体，Greater是谓词谓词的一般形式是:P(x1,x2,…xn)其中P是谓词，通常首字母用大写字母表示。x1,x2,x3………是个体,通常用小写字母来表示。在谓词逻辑中，命题被细分为谓词和个体两个部分。n元谓词：含有n个个体符号的谓词P(x1,x2,…xn)，表示一个映射：P：Dn→{T，F}或是(D1×D2×D3…Dn)→{T，F}谓词的语义是由使用者根据需要人为定义的。如：S（x）可以定义成x是船也可定义成x是学生谓词中包含的个体数目称为谓词的元数.如：Q(x)是一元谓词，P(x,y)是二元谓词，A(x1,x2,…,xn)是n元谓词。若Xi是个体常元、变元或函数，谓词称为一阶谓词；如果某个Xi本身又是一个一阶谓词，则谓词称为二阶谓词，依次类推。个体变元的取值范围称为个体域（或称论域），个体域可以是有限的也可以是无限的。例I（x）x是整数，则个体域是所有整数，它是无限的。函数符号：是从若干个研究对象到某个研究对象的映射的符号。•n元函数f(x1,x2,…,xn)规定为一个映射：f:Dn→D谓词与函数的区别：1.谓词的真值是真和假，而函数无真值可言，其值是个体域中的某个个体。2.谓词描述的是个体域中的个体之间的关系或性质。而函数实现的是一个个体的出现依赖于个体中中的其他个体，他是一个个体在个体域中的映射。3.在谓词逻辑中，函数本身不能单独使用，它必须嵌入到谓词中。注意：有人讲命题逻辑是0元谓词逻辑3.2谓词公式、永真性、可满足性、不可满足性3.2.1谓词公式1、联接词：用于联接两谓词公式，组成一个复杂的复合命题：：“否定”联接按词，当命题P为真时，则﹁P为假，反之为真∨：“析取”联接词，它表示两个命题存在“或”者的关系。∧：“合取”联接词，两个命题之间具有“与”关系。→“蕴含”、“条件命题”P→Q表示“如果P，则Q”。P为条件，Q为条件的后件：（）“等价”“双条件”表示“P当且仅当P”上述联结词构成谓词公式其定义如下：PQPP∨QP∧QP→QPQTTFTTTTTFFTFFFFTTTFTFFFTFFTT；联接词的优先级：，∧，∨，→，2、量词：用于刻划谓词与个体之间关系的词，在谓词逻辑中引入了两个量词，全称量词符号（x）及存在量词符号（x）。全称量词符号+变元=全称量词，如（x）；存在量词符号+变元=存在量词，如（x）；(x)：它表示对个体域中所有个体x(x)：表示在个体域中存在某个个体x例：设谓词P(x)表示x是正数，F(x,y)表示x与y是好朋友，则：(x)P(x)：表示个体域中所有个体x都是正数。(x)(y)F(x,y)：表示在个体域中对任何个体x,都存在个体y，x与y是好朋友。(x)(y)F(x,y)：表示在个体域中存在个体x，它与个体域中的任何个体y都是朋友。(y)(x)F(x,y)：表示在个体域中存在个体x与个体y，x与y是朋友。(x)(y)F(x,y)：表示对于个体域中的任何两个个体x和y，x与y都是朋友。3、量词辖域与约束变元在一个谓词公式中，如果有量词出现，位于量词后面的单个谓词或者用括弧扩起来的合式公式称为量词的辖域。在辖域内与量词同名的变元称谓约束变元，不受约束的变元称谓自由变元，例如（x）(P（x）→(y)R(x,y))其中（x）的辖域是(P（x）→(y)R(x,y))，辖域内的x是受（x）的约束的变元；而(y)的辖域是R(x,y)，R(x,y)的y是受(y)约束的变元。在这个公式中没有自由变元。在谓词公式中，变元的名字是无关紧要的，可以把一个变元的名字换成另一个变元的名字。但是，必须注意，当对量词辖域内的约束变元更名时，必须把同名的约束变元都统一改成相同的名字，且不能与辖域内的自由变元同名。同样，对辖域内的自由变元改名时，也不能改成与约束变元相同的名字。例如，对于公式（x）R(x,y)，可以改名为（t）R(t,u),这里将约束变元x改成了t,把自由变元y改成了u。4、谓词公式：按下述规则得到谓词演算的合式公式：(1)单个谓词和单个谓词的否定，称为原子谓词公式，原子谓词公式是合式公式；(2)若A是合式公式，则¬A也是合式公式；(3)若A，B都是合式公式，则A∨B，A∧B，A→B，AB也都是合式公式；(4)若A是合式公式，x是任一个体变元，则(x)A，(x)A也都是合式公式。5、谓词公式的解释在谓词逻辑中，对谓词公式中各个个体变元的一次真值指派称为谓词公式的一个解释。也即蜕化成命题逻辑，一旦解释确定，根据各联接词的定义就可求出谓词公式中真值（T或F）。定义：谓词公式G的论域为D，根据D和G中的常量符号，函数符号和谓词符号按下列规则作的一组指派成为G的一个解释I（或赋值）解释I：三个赋值规定：（1）对公式G，为每个常量指派D中的一个元素；解释I：三个赋值规定：（2）对公式G，为每个n元函数指派一个Dn→D的映射，其中Dn={（x1,x2,…xn）/x1,x2,…xn∈D}（3）对公式G，为每个n元谓词指派一个Dn→{T，F}的映射；则称这些指派为公式G在D上的一个解释。；公式只有经过指派才与现实联系起来，才有意义。；解释I称为公式G在论域D上的一个解释。；对应每个解释，公式G都有一个真值{T，F}。；一阶谓词的公式解释数目：一阶谓词的公式解释数通常是相当可观的，是一种排列组合。设个体域有m个元素，则：每个常量有m个取值，n个常量有mn种取值的可能性，一个n元函数一般有种指派，一个n元谓词有种指派。整个公式在给定域上的解释数目将达到该公式所包含的所有函数和谓词指派数目的连乘积。nmmnm2；由于存在多种组合情况，所以一个谓词公式的解释可能有很多个。对于每个解释，谓词公式都可求出一个真值（T或F）。(需要注意：（x）P（x）的真值为1当且仅当对论域D的每一个元素x，P（x）都取值为1，（x）P（x）的真值为0当且仅当对D的每个元素x，P（x）都取值为0)例3.2.1：设谓词公式A=y（P（y）∧Q(y,a)）,B=x(P(f(x))∧Q(x,f(a))(它们不含自由变元),解释给定为:D={2,3}a=2，f函数和谓词P、Q的解释如下表所示。f(2)f(3)3201P(2)P(3)1111Q(2,2)Q(2,3)Q(3,2)Q(3,3)求A、B的值。则A=(P(2)∧Q(2,2))∧(P(3)∧Q(3,2))=(0∧1)∧(1∧1)=0B=(P(f(2))∧Q(2,f(2)))∨(P(f(3))∧Q(3,f(2)))=(P(3)∧Q(2,3))∨(P(2)∧Q(3,3))=(1∧1)∨(0∧1)=1例：设变元x和y的个体域是D={1，2}，谓词P（x，y）表示x大于等于y，给出公式A=(x)(y)P(x,y)在D上的解释，并指出在每一种解释下公式A的真值。解：由于在公式A中没有包括个体常量和函数，所以可由谓词P（x,y）的定义得出谓词的真值指派。设对谓词P（x,y）在个体域D上的真值指派为：P(1,1)=T，P(1,2)=F，P(2,1)=T，P(2,2)=T这就是公式A在D上的一个解释。在此解释下，因为x=1时有y=1使P(x,y)的真值为T，x=2时也有y=1使P(x,y)的真值为T，即x对于D中的所有取值，都存在y=1，使P(x,y)的真值为T，所以在此解释下公式A的真值为T。例：设个体域D={1，2}，谓词公式B=(x)P(f(x),a)，已知a=1。若指派f(1)=1，f(2)=2指派P(1,1)=T，P(2,1)=T则上述各个指派就确定了谓词公式B的一个解释即对x在D上的任意取值，都使B为T3.2.2.谓词公式的永真性、可满足性和永假性•永真性–若谓词公式P对非空个体域D上的任一解释都有真值T，则称P在D上是永真的即：若P在任何非空个体域上均永真，则称P永真•可满足性–对谓词公式P，若至少存在D上的一个解释，使P在此解释下真值为T，则称P在D上是可满足的•永假性（不可满足性、不相容性）–若谓词公式P对非空个体域D上的任一解释都有真值F，则称P在D上是永假的即：P在任何非空个体域上均永假，则称P永假当个体域个数少，每个域自身又小时，易于判断或当解释的个数有限，也总是可判定的但若解释的个数无限时，就不能确保可以判定或者不能确保在有限的时间内判定3.3谓词公式的等价性与永真蕴含3.3.1等价性含义定义：设Ｐ与Ｑ是两个谓词公式，Ｄ是它们共同的个体域，若对于Ｄ上的任何解释，Ｐ和Ｑ都有相同的真值，则称Ｐ与Ｑ在个体域D上是等价的，如果D是任意个体域，则称P和Q是等价的，记作：PQ以下公式是等价式，推理时常用到：–(1)双重否定¬(¬P)P–(2)交换律P∨QQ∨PP∧QQ∧P–(3)结合律(P∧Q)∧RP∧(Q∧R)(P∨Q)∨RP∨(Q∨R)–(4)分配律P∧(Q∨R)(P∧Q)∨(P∧R)P∨(Q∧R)(P∨Q)∧(P∨R)–(5)狄·摩根定律¬(P∨Q)¬P∧¬Q¬(P∧Q)¬P∨¬–(6)吸收律P∨(P∧Q)PP∧(P∨Q)P–(7)补余律P∨﹁PTP∧﹁PF–(8)联词化归律P→Q¬P∨Q蕴涵式转化–PQ(P→Q)∧(P→Q)–PQ(P∧Q)∨(¬P∧¬Q)–(9)量词否定¬(x)P(x)(x)(¬P(x))¬(x)P(x)(x)(¬P(x))–(10)量词分配(x)[P(x)∧Q(x)](x)P(x)∧(x)Q(x)(x)[P(x)∨Q(x)](x)P(x)∨(x)Q(x3.3.2谓词公式的永真蕴涵性•永真蕴涵性含义–如果P→Q永真，则称P永真蕴涵Q–且称Q为P的逻辑结论，称P为Q的前提–记作PQ，这就是知识的一种表达形式。•永真蕴涵式(推理规则)–(1)化简式P∧QPP∧QQ–(2)附加式PP∨QQP∨Q–(3)析取三段论﹁P，P∨QQ（“，”表示∧）–(4)假言推理P，P→QQ–(5)拒取式¬Q，P→Q¬P–(6)假言三段论P→Q，Q→RP→R–(7)二难推理P∨Q，P→R，Q→RR–(8)全称固化(x)P(x)P(y)作用：y是任一个体，消去全称量词–(9)存在固化(x)P(x)P(y)作用：y是某一个体，使