归结推理方法(三)

归结推理方法（三）引入新课：数理逻辑为知识的推理奠定了基础；基于一阶谓词逻辑的推理方法，是一种机械化的可在计算机上加以实现的推理方法。

一、命题逻辑✧命题逻辑和谓词逻辑是两种逻辑；对知识的形式化表示，特别是定理的自动证明发挥了重要作用。

✧谓词逻辑是在命题逻辑的基础上发展起来的。

命题逻辑可看作是谓词逻辑的一种特殊形式。

（一）命题定义1能够分辨真假的语句称作命题定义2一个语句如果不能再进一步分解成更简单的语句，并且又是一个命题，则称此命题为原子命题。

说明：（1）原子命题是命题中最基本的单位，用P,Q,R,…..大写拉丁字母表示。

而命题的真与假分别用“T”与“F”表示。

命题代表人们进行思维时的一种判断，或者是真。

或者是假，只有这两种情况。

若命题的意义为真，则记为T。

若命题的意义为假，则记为F。

（2）一般情况下，只有陈述句才可能是命题，因为只有陈述句才能分辨真假。

如“太阳从西边升起”、“雪是白色的”等等都是陈述句，而其他的一些句子如疑问句、祈使句、感叹句等均不能分辨其真假。

象这样的没有真假意义的句子就不是命题。

（3）并不是所有的陈述句都是命题；例如，“这个句子是假的”。

显然无法判断该语句的真假，这个语句不是命题。

（4）在有些情况下，要判断一个陈述句的真假，是需要一定条件的，即该陈述句在一种条件下，其逻辑值为真，但在另一种条件下，其逻辑值为假。

比如，“1+1=10”。

（5）用大写字母表示的命题既可以是一个特定的命题，也可以是一个抽象命题。

前者称为命题常量，后者称为命题变量。

对于命题变量，只有把确定的命题代入后，它才可能有明确的逻辑值（T或F）。

（二）命题公式连接词：在日常生活中，可以通过连接词将一些简单的陈述句组成较为复杂的语句，称为复合句。

较复杂的定义。

～：称为“非”或“否定”。

其作用是否定位于它后面的命题。

当命题P为真时，～P为假；当P 为假时，～P为真。

∨：称为“析取”。

它表示被它连接的两个命题具有“或”关系。

∧：称为“合取”。

它表示被它连接的两个命题具有“与”关系。

→：称为“条件”或“蕴含”。

P→Q表示“P蕴含Q”，即“如果P，则Q”，其中P称为条件的前件，Q称为条件的后件。

↔：称为“双条件”。

P↔Q表示“P当且仅当Q”。

命题公式：以递归形式给出命题公式的定义：（1）原子命题是命题公式（2）A 是命题公式，则～A 也是命题公式（3）若A 和B 是命题公式，则A ∧B 、A ∨B 、A →B 、A ↔B 也都是命题公式。

（4）只有按（1）－（3）所得的公式才是命题公式。

命题公式就是一个按照上述规则由原子命题、连接词及圆括号所组成的字符串。

～(P ∨Q), P →(Q ∨R), (P →Q) ∧(Q →R)↔(P →R)在命题演算公式中，连接词的优先级别次序是～，∧，∨，→，↔✓ 命题公式可以用来表示知识，尤其是事实性知识。

✓ 命题逻辑不能把所描述的客观事物的结构及逻辑特征反映出来，也不能把不同事物的共同特征表示出来。

例如，对于命题“张三是李四的老师”，若用英文字母P 表示，看不出张三和李四之间的师生关系。

✓ 为了消除命题逻辑的局限性，在命题逻辑的基础上发展起来了谓词逻辑。

二、谓词逻辑（一）谓词与个体✧ 在谓词逻辑中，将原子命题分解为谓词和个体两部分。

例：“贝多芬是作家”，“是作家”为谓词；“贝多芬”是个体一。

个体：是指独立存在的物体；它可以是抽象的、具体的。

如，鲜花、电视、代表团、自然数、唯物主义等。

谓词：则用于刻画个体的性质、状态或个体间关系的；例：“李白是诗人”，若用poet 表示“是诗人”；用LiBei 表示个体，则得到谓词是poet(LiBei)；其中poet 是谓词，LiBei 是个体。

“5＞3”，可用谓词表示为Greater(5,3)，Greater 刻画了5与3之间的“大于”关系。

✧ 一个谓词可以与一个个体相关联，此种谓词称为一元谓词，它刻画了个体的性质；一个谓词也可以与多个个体相关联，此种谓词称为多元谓词，它刻画了个体间的“关系”。

例如：“张三是李四的老师”，在命题逻辑中无法刻画张三与李四的关系，而在谓词逻辑中可以用二元谓词teacher(x,y)表示“x 是y 的老师”。

而teacher （张三，李四）即刻画了张三是李四之间的关系✧ 谓词的一般形式为：),,,(21n x x x P其中，P 是谓词，而n x x x ,,,21 是个体；谓词通常用大写字母表示，个体通常用小写字母表示。

✧ 个体可以是常量、也可以是变量、还可以是函数。

例如，“小刘的哥哥是个工人”，可以表示为worker(brother(Liu))，其中(brother(Liu)是一个函数。

常量、变量、函数统称为项。

✧ 谓词的语义都是使用者根据需要人为定义的。

（当谓词的变化用特定的个体取代时，谓词就具有一个确定的逻辑值T 或F ）✧ 谓词中包含的个体数目称为谓词的元数（),,,(21n x x x P 是n 元谓词）在谓词),,,(21n x x x P 中，如果i x 是常量、变元或函数，则它称为一阶谓词，如果某个i x 本身又是一个一阶谓词，则它称为二阶谓词。

说明：谓词和函数形式上相似，是两个完全不同的概念。

谓词具有逻辑值：“真”或“假”；函数是某个个体到另一个个体的映射。

（二）谓词公式✧ 连接词：在谓词逻辑中，可以通过与命题逻辑中相同的连接词，将一些原子谓词公式连接起来，构成一～↔→∧∨,,,,✧ 量词：全称量词，x ∀（表示对个体域中所有个体x ）存在量词x ∃（表示个体域中存在个体x ）F(x,y)表示x 与y 是朋友，则(x ∀)(y ∃)F(x,y)就表示个体域中的任何个体x ，都存在一个个体y ，x 与y 是朋友。

(x ∀)(y ∀)F(x,y)则表示对个体域中的任何两个个体x 和y ，x 与y 是朋友。

✧ 谓词演算公式：谓词演算中，由单个谓词构成的不含任何连接词的公式，叫做原子谓词公式。

形式),,,(21n x x x F ，简称原子，其中F 是n 元谓词，n x x x ,,,21 则为个体变元。

按下述规则得到谓词演算的合式公式：（1）原子公式是合式公式（2）若A 是合式公式，则～A 也是合式公式（3）若A 和B 都是合式公式，则A ∧B 、A ∨B 、A →B 、A ↔B 也都是合式公式（4）若A 是合式公式，x 是任一个体变元，则A x )(∀和A x )(∃也都是合式公式。

说明：（1）谓词演算公式是一个按照上述规则由原子公式、连接词、量词及圆括号所组成的字符串。

例：),()(y x P x ∃ ))()()((y R x P x ∨∃（2）命题演算公式是谓词演算公式的一种特殊情况。

（3）在谓词演算的合式公式中，连接词的优先级别次序是～↔→∧∨,,,,✧ 量词辖域与约束变元在一个公式中，如果有量词出现，位于量词后面的单个谓词或者用括弧括起来的合式公式称为量词的辖域。

在辖域内与量词中同名的变元称为约束变元，不受约束的变元称为自由变元。

)),()()()((y x R y x P x ∃→∀其中，)(x ∀的辖域是)),()()((y x R y x P ∃→，辖域内的x 是受)(x ∀约束的变元；)(y ∃的辖域是),(y x R ，),(y x R 中的y 是受)(y ∃约束的变元。

在这个公式中没有自由变元。

✧ 说明：在谓词公式中，变元的名字是无关紧要的。

可以把一个变元名字换成另一个名字。

当对量词辖域内的约束变元更名时，必须把同名的约束变元都统一改成相同的名字，且还能与辖域内的自由变元同名。

同样，对辖域内的自由变元改名时，也不能改成与约束变元相同的名字。

例如，对于公式),()(z y Q y ∀，可将其改名为),()(u t Q t ∀。

（三）谓词公式的永真性和可满足性1、谓词公式的解释✧ 命题公式直接通过真值指派给出解释；✧ 谓词公式必须考虑个体常量和函数在个体域中的取值，然后才能针对常量和函数的具体取值为谓词分别指派真值。

由于存在多种组合情况，所以一个谓词公式的解释可能有多个。

对于每一个解释，谓词公式都可求出一个真值（T 或F ）。

定义：设D 为谓词公式P 的个体域，若对P 中的个体常量、函数和谓词按照如下规定赋值：（1）为每个个体常量指派D 中的一个元素；（2）为每个n 元函数指派一个从D n 到D 的映射，其中},,,|),,,{(2121D x x x x x x D n n n ∈=（3）为每个n 元谓词指派一个D n 到｛F,T ｝的映射。

则称这种指派为公式P 在D 上的一个解释。

例：设个体域}2,1{=D ，求公式))),(()()((b x f Q x P x A →∀=在D 上的某个解释，并指出在此解释下公式A 的真值。

解：由于在该公式中包含有个体常量b 、函数f(x)和两个谓词P 和Q ，所以首先设个体常量b 及函数f(x)的指派分别为b=1，f(1)=2，f(2)=1对谓词指派的真值为P(1)=F ，P(2)=T ，Q(1,1)=T ，Q(2,1)=F这里，由于已指派b=1，所以Q(2,2)与Q(1,2)不可能出现，故没有给它们指派真值。

x=1时有P(1)=F ，Q(f(1),1)-Q(2,1)=F所以，P(1)→Q(f(1),1)的真值为T 。

当x=2时，P(2)=T ，Q(f(2),1)=Q(1,1)=T所以，P(2) →Q(f(2),1)的真值为T 。

因为对个体域D={1,2}上的所有x 均有)),(()(b x f Q x P →的真值为T ，所以公式A 在此解释下的真值为T 。

说明：(1)谓词公式的真值都是针对某一解释而言的。

（2）同一个公式可能在一种解释下其真值为T ，而在另一种解释下，其真值为F 。

2、谓词公式的永真性定义：如果谓词公式P ，对个体域D 上的任何一个解释都取得真值T ，则称P 在D 上是永真的；如果P 在每个非空个体域上均永真，则称P 永真。

定义：如果谓词公式P ，对个体域D 上的所有解释都取得真值F ，则称P 在D 上是永假的；如果P 在每个非空个体域上均永假，则称P 永假。

谓词公式的永假性又称为不可满足性或不相容性。

当要判断某个公式的永真性（永真或永假时），必须对每个个体域上的每个解释进行判断。

当解释的个数有限时，这种判断尚可进行，若解释的个数无限时，公式的永真或永假就很难判断了。

3、谓词公式的可满足性定义：对于谓词公式P ，如果至少存在一个解释使得公式P 在此解释下的真值为T ，则称公式P是可满足的。

说明：谓词公式永假与不可满足是等价的。

（四）谓词公式的等价性与永真蕴含定义：设P 与Q 是两外谓词公式，D 是它们共同的个体域。

若对D 上的任何一个解释，P 与Q 的取值都相同，则公式P 和Q 在域D 上是等价的。