2.2 基于逻辑的知识表示

2.2.1 逻辑的基本概念

1．常用逻辑术语

一种知识表示语言的语法指的是这种语言句子（Sentence）的一般合理结构。逻辑的语法（Syntax）指的是逻辑表达式的合理结构。同时，逻辑表达式还具有与其相关联的事实意义。这种意义被称为语义（Semantics）。语义定义了在可能情况（Possible World）下每个逻辑表达式的真值表（Truth Table）^[12]。由于本书并没有涉及具体的逻辑层面，所以此处以一个数学表达式为例与逻辑表达式进行类比。数学表达式x+y=4是符合数学表达式语法的，而xy+=4不符合数学表达式语法。其中，x+y=4表达了“两个变量相加等于4”这个语义。在这种语义下，x=y=2是真的（True），而x=y=1是假的（False）。

在逻辑研究中，通常使用模型（Model）这一术语指代上述可能情况。如果一个语言的句子α在模型m的取值下是真的，那么模型m满足（Satisfy）句子α。如果满足α的模型都满足β，那么句子α蕴含句子β。这是一种蕴含关系（Entailment），记为α⇒β^[12]。举一个例子，句子x=0蕴含句子xy=0，其语义是“只要x=0，那么xy=0”。

2．三种基本逻辑

逻辑的功能丰富程度有三个层次：命题逻辑（Propositional Logic）、一阶谓词逻辑（First-Order Logic）和高阶谓词逻辑（Higher-Order Logic）。

命题逻辑是语法最简单的逻辑表达语言之一。命题逻辑定义了具有真假两种取值的变量，被称为原子命题（Atom Proposition），并通过基本逻辑运算连接原子命题构成复合命题（Complex Proposition）。其中，基本逻辑运算包括与（∧）、或（∨）、非、蕴含（⇒）、当且仅当（⇐⇒）。命题逻辑的推理过程主要有前向过程（Forward Chaining）、反向过程（Backward Chaining）和归结算法（Resolution）。

一阶谓词逻辑指的是在命题逻辑的基础上引入谓词（Predicate）。通俗地说，命题逻辑好比汇编，所有语句都是原子级的；而谓词逻辑就好比高级编程语言，在命题逻辑（汇编）的基础上引入谓词（函数），使表达能力更加丰富。除了谓词，一阶谓词逻辑的一个特点就是引入了两种量词（Qualifier）：全称量词（Universal Quantifier，∀）和存在量词（Existential Quantifier，∃）。之所以称之为一阶，主要是一阶谓词逻辑的量词不能作用到谓词上，其表达能力受到限制，于是需要设计高阶谓词逻辑。

高阶谓词逻辑在一阶谓词逻辑的基础上引入了可以作用在谓词上的量词语法，可解决一阶谓词逻辑不能量化谓词或集合的问题，从编程语言的类比中，进一步增强了表达能力。

2.2.2 命题逻辑

原子级句子包含简单的命题符号。每个命题符号均代表可以取真或取假的命题。复合命题是由原子级句子、括号和逻辑运算（Logical Connectives）组成的。其中，五种逻辑运算为：

① 否定（Negation，）：一个如A的句子被称为A的否定。一个命题逻辑的基本形式或者是一个原子级句子（A），或者是一个否定原子级句子（A），比如North代表向北，那么North就代表不向北。

② 且（And，∧）：一个用“且”连接的句子被称为合取形式（Conjunction），如North ∧On代表机器人面朝北正在运行。符号∧来自字母A，意思为And（且）。

③ 或（Or，∨）：一个用“或”连接的句子被称为析取形式（Disjunction），如North∨East代表机器人或向北或向东。符号∨来自字母V，意思为Vel（或）。

④ 蕴含（Imply，⇒）：一个用“蕴含”连接的句子被称为一个推断（Implication），如A∧B⇒C。其中，A∧B被称为前件（Premise），C被称为结论（Conclusion）。蕴含也被视为用“如果-那么”表示的规则。

⑤ 当且仅当（If and Only If，⇐⇒）。顾名思义，如果A⇒B且B⇒A，那么A⇐⇒B。注意，这是一个双向（Biconditional）关系，也即如果A ⇐⇒B，那么B⇐⇒A，意为命题A与命题B等价。

2.2.3 谓词逻辑

如前所述，谓词逻辑在命题逻辑的基础上引入了谓词和量词^[12]。其中，一阶谓词逻辑的基本元素是符号（Symbol）、关系（Relation）和函数（Function）。符号有三种：常量符号（Constant Symbol）、谓词符号（Predicate Symbol）和函数符号（Function Symbol），如

其中，Misa和John代指两个人物是常量符号；Couple是代指夫妻关系的谓词；Queen和King分别是皇后和国王的谓词。

一旦逻辑表达式可以表示规则，很自然的事情就是表示同一类事物的规则，也就是对集合有效的规则。这就是量词产生的原因。

① 全称量词（Universal Quantifier，∀）代表了对于集合中每个元素的语义，如

表示“任何一个君王，都是一个人”。也就是说，对于任意一个元素x，只要“君王”这个谓词成立，那么“人”这个谓词一定成立。其中，x被称为变量（Variable）。

② 存在量词（Existential Quantifier，∃）代表至少存在一个例子满足逻辑表达式，如

表示“约翰（John）头上戴着一顶王冠”。也就是说，至少存在一个元素x是一顶王冠Crown（x），并且戴在约翰头上OnHead（x，John）。当然，也可以写成蕴含的形式

③ 嵌套量词（Nested Quantifier）就是通过嵌套和组合量词表达复杂的语义，如

表达“任何兄弟，都是同辈直系亲属”。当然，这种嵌套可能会很复杂，如

表示“在所有王冠中，存在一顶王冠，戴在理查德（Richard）头上”。

2.2.4 归结原理

1965年，美国人Robinson提出的一种证明一阶谓词演算中定理的方法就是归结原理^[13]。

用归结原理证明定理有些类似于反证法的思想。在反证法中，首先假定要证明的结论不成立，然后通过推导出存在矛盾的方法，反证出结论成立。在归结法中，首先对结论求反，然后将已知条件和结论的否定合在一起用子句集表达。如果该子句集存在矛盾，那么可证明结论的正确性。具体来说，对任一要证明的永真公式取非后，只要证明它不可满足即可。为了完成算法，必须先把逻辑表达式转化成一种标准型，然后对这种标准型不断使用单一的推理规则，即执行归结直到导出矛盾。注意，子句集中的子句之间是合取关系，只要有一个子句不可满足，子句集就不可满足。另外，空子句是不可满足的。因此，若一个子句集中包含空子句，则这个子句集一定是不可满足的。这就是归结原理的基本思想。简单说，检查子句集中是否包含空子句，就是只要包含空子句，子句集就不可满足；若不包含空子句，则在子句集中选择合适的子句进行归结，一旦通过归结，就能推出空子句，说明子句集是不可满足的。

1930年，Herbrand提出了相应的定理：在一阶谓词逻辑中，如果一个定理是正确的，就有一个机械方法能够在有限步内证明它^[14]。Herbrand定理为归结原理提供了理论支持，使归结原理具备良好的完备性质。据此，归结原理在逻辑推理范畴内有不可忽视的历史地位。