第13章 命题演算

1、第第1313章章 命题演算命题演算 第三部分第三部分 知识的表示和推理知识的表示和推理对特征值加以约束对特征值加以约束 一个一个agentagent环境的某些信息是很难或者说是不可能环境的某些信息是很难或者说是不可能由图标来表述的。例如：由图标来表述的。例如： 普遍规律，如普遍规律，如“所有的蓝色盒子都是可推动所有的蓝色盒子都是可推动的的”。 否定信息，如否定信息，如“积木积木A A不在地板上不在地板上( (没有说积木没有说积木A A在哪儿在哪儿)”)”。 不确定信息，如不确定信息，如“或者积木或者积木A A在积木在积木B B上面，或上面，或者积木者积木A A在积木在积木C C上面上面”。 有

2、些这种难以表述的信息可以用公式表示为对特征有些这种难以表述的信息可以用公式表示为对特征值的约束，这些表示某个值的约束，这些表示某个agentagent所处世界的重要知识的所处世界的重要知识的约约束束常常被用来推断那些不能被直接感知的特征值。常常被用来推断那些不能被直接感知的特征值。 对特征值加以约束对特征值加以约束 使用基于特征中约束的计算推断有关一个使用基于特征中约束的计算推断有关一个agentagent当前当前(present)(present)状态的信息，可以与从一个状态的信息，可以与从一个agentagent行为的将来行为的将来(future)(future)状态的计算作对照。状态的计

3、算作对照。 第一个方法称为第一个方法称为“推理推理(reasoning)(reasoning)”，第二个称为，第二个称为“投影投影(projecting)(projecting)”。在以下几章中，先不考虑投影。在以下几章中，先不考虑投影的问题，而集中讨论推理。的问题，而集中讨论推理。 包含有关特征值的推理有几项应用。可以确信，当包含有关特征值的推理有几项应用。可以确信，当agent(agent(甚至是反应型甚至是反应型agent)agent)决定行动的时候，推理能增决定行动的时候，推理能增强它们的效力。例如，与强它们的效力。例如，与“原因原因”相联系的特征可以从相联系的特征可以从与与“症状症状

4、”相联系的特征推断出。这种方法是人工智能相联系的特征推断出。这种方法是人工智能应用中的重要一类应用中的重要一类专家系统专家系统(expert system)(expert system)的基础。的基础。 对特征值加以约束对特征值加以约束 用一个富有启发件的例子来开始推理技术的讨论。用一个富有启发件的例子来开始推理技术的讨论。设想一个能举起一块积木的机器人，假如那个木块是可设想一个能举起一块积木的机器人，假如那个木块是可举的举的( (即不是太重的即不是太重的) )，并且假设这个机器人有足够的电，并且假设这个机器人有足够的电池能源。假如以上条件都满足，那么当机器人试着举起池能源。假如以上条件都满足

5、，那么当机器人试着举起这个它所握住的木块时，它的手臂就移动。可以用二元这个它所握住的木块时，它的手臂就移动。可以用二元值特征来表述这些不同的条件：值特征来表述这些不同的条件： x x1 1 ( BAT_OK ) ( BAT_OK ) (电池能源合适电池能源合适) ) x x2 2 ( LIFTABLE ) ( ( LIFTABLE ) (可举的可举的) ) x x3 3 ( MOVES ) ( ( MOVES ) (移动移动) )对特征值加以约束对特征值加以约束 假设机器人能感知以假设机器人能感知以BAT_OK(BAT_OK(通过读量表通过读量表) )和和MOVES(MOVES(通通过联角传感

6、器过联角传感器) )，但不能感知，但不能感知LIFTABLELIFTABLE。但知道。但知道LIFTABLELIFTABLE的值对机器人完成其必须完成的任务来说是很重要的。的值对机器人完成其必须完成的任务来说是很重要的。 从上面的描述，我们知道假如从上面的描述，我们知道假如BAT_OKBAT_OK和和LIFTABLELIFTABLE的值的值都为都为1 1，那么，那么MOVESMOVES也如此。所以，假如当这个机器人试着也如此。所以，假如当这个机器人试着要移动这块积木时要移动这块积木时MOVESMOVES值为值为0 0，那么我们知道或者，那么我们知道或者BAT_OKBAT_OK或者或者LIFTA

7、BLE(LIFTABLE(或者两者或者两者) )肯定值为肯定值为0 0。如果。如果BAT_OKBAT_OK被感知被感知到值为到值为1 1，那么，那么LIFTABLELIFTABLE值一定为值一定为0 0。 既然我们能如此推理，那么机器人也可如此。所需要既然我们能如此推理，那么机器人也可如此。所需要的是一种能用于表达特征中的约束和特征值的语言的是一种能用于表达特征中的约束和特征值的语言(language)(language)和能进行必要推理的推理和能进行必要推理的推理(inference)(inference)机制。机制。而而命题演算命题演算(propositional calculus)(pr

8、opositional calculus)作为布尔代数的作为布尔代数的一种延伸，为此提供了必要的工具。一种延伸，为此提供了必要的工具。 与这种语言相联系的机制可以用来从这种与这种语言相联系的机制可以用来从这种语句语句(statement)(statement)中推出中推出结论结论(consequence)(consequence)。既然逻辑语言在。既然逻辑语言在人工智能中是如此重要，那么，必须在表述基于使用这些人工智能中是如此重要，那么，必须在表述基于使用这些语言的更复杂和更具智能的语言的更复杂和更具智能的agentagent之前，对这些语言作更之前，对这些语言作更详细的说明。详细的说明。 首

9、先是一些定义。逻辑包含首先是一些定义。逻辑包含 一种语言一种语言( (具有一个句法用以规定在这种语言中具有一个句法用以规定在这种语言中什么是合法的表达式什么是合法的表达式) )。 推理规则推理规则用以操作这种语言中的语句。用以操作这种语言中的语句。 语义语义用以把这种语言中的要素和某些主题用以把这种语言中的要素和某些主题(subject matter)(subject matter)中的要素联系起来。中的要素联系起来。 对特征值加以约束对特征值加以约束 语言语言 下面从形式上描述命题演算中的组成元素。此刻最好下面从形式上描述命题演算中的组成元素。此刻最好不要把某种意义与这种语音的组成元素联系起

10、来，把我们不要把某种意义与这种语音的组成元素联系起来，把我们现在正在做的想象为对一个无意义的游戏规则的描述，以现在正在做的想象为对一个无意义的游戏规则的描述，以后我们再谈论意义。以下是这种语言的组成元素：后我们再谈论意义。以下是这种语言的组成元素： 原子原子(atom)(atom)：两个最明显的原子是两个最明显的原子是T T和和F F，还有可数的，还有可数的以大写字母开头的那些字符串的无限集合以大写字母开头的那些字符串的无限集合，如：，如： P P，Q Q，R R，P P1 1，P P2 2，ON_A_BON_A_B，等等。，等等。 联结词联结词(connective)(connective)

11、：、 和和 ，分别称为：，分别称为：“析取析取(disjunction)”(disjunction)”、“合取合取(conjunction)(conjunction)”、“蕴含蕴含(implication)(implication)”和和“非非(negation)(negation)” ” 。 语言语言 合式公式合式公式(well-formed formulas , wff)(well-formed formulas , wff)( (也称为也称为句子句子sentencesentence) )的语法：的语法： 任何原子都是一个合式公式。任何原子都是一个合式公式。 例如：例如： P P，R R，

12、P3P3 假如假如1 1和和2 2是合式公式，那么以下这些也是：是合式公式，那么以下这些也是： 1 1(1 1和和2 2的析取的析取) )； 1 12 2 ( (1 1和和2 2的合取的合取) )； 1 1 2 2 ( (蕴含蕴含) )； 1 1 ( (1 1的非的非) ) 。 不再有别的合式公式。不再有别的合式公式。 原子以及前面带有原子以及前面带有 符号的原子叫做符号的原子叫做文字文字(literal)(literal)。在在1 1 2 2中，中， 1 1被称为被称为蕴含的前项蕴含的前项(antecedent)(antecedent)，而，而2 2被称为被称为蕴含的后项蕴含的后项(cons

13、equent)(consequent)。 语言语言 注意以上例子中有语言外的分隔符注意以上例子中有语言外的分隔符“(” (” 和和 “ “)”)”的使用。它们根据递归定义把合式公式组成的使用。它们根据递归定义把合式公式组成次级次级(sub)(sub)合合式公式式公式。 有些逻辑处理把这两个分隔符公式化为语言的组成有些逻辑处理把这两个分隔符公式化为语言的组成部分，然而在此用得有点宽松并且较直观。合式公式可部分，然而在此用得有点宽松并且较直观。合式公式可以通过递归地使用它们的定义来识别。以通过递归地使用它们的定义来识别。例如：例如：是一个合式公式。首先，是一个合式公式。首先， P P和和Q Q是合

14、式公式，所以是合式公式，所以(PQ)(PQ)是合式公式；是合式公式；并且由于并且由于R R是一个合式公式，是一个合式公式， R R也是一个合式公式，因也是一个合式公式，因而，而， 是一个合式公式。是一个合式公式。 RQP )(RQP )(推理规则推理规则 从一些合式公式推出另一些合式公式可以有许多方法，称它们为从一些合式公式推出另一些合式公式可以有许多方法，称它们为推理规则推理规则(rule of inference)(rule of inference)。一条推理规则的典型形式是：。一条推理规则的典型形式是：可以可以从从( (或从或从和和) )推出。下面是一些通用的推理规则：推出。下面是一些

15、通用的推理规则： 合式公式合式公式2 2可以根据合式公式可以根据合式公式1 1和和1 1 2 2推出推出( (称之为称之为假言假言推理或演绎推理推理或演绎推理(modus ponens)(modus ponens) )。 合式公式合式公式1 12 2可以根据两个合式公式可以根据两个合式公式1 1和和2 2推出推出( (引入引入) ) 合式公式合式公式2 21 1可以根据合式公式可以根据合式公式1 12 2推出推出( (交换交换) ) 合式公式合式公式1 1可以根据合式公式可以根据合式公式1 12 2推出推出( (消除消除) ) 合式公式合式公式1 12 2可以根据单个合式公式可以根据单个合式公

16、式1 1或单个合式公式或单个合式公式2 2推出推出( (引入引入) ) 合式公式合式公式1 1可以根据合式公式可以根据合式公式（1 1）推出）推出( (消除消除) ) 验证定义验证定义 合式公式序列合式公式序列1 1 ，2 2 ，n n 被称为是从被称为是从一个合式公式集合一个合式公式集合得出的得出的验证验证(proof)(proof)( (或或演绎，演绎，deductiondeduction) )，当且仅当在序列中的每个当且仅当在序列中的每个i i或者是在或者是在中，或者可以从处于这个序列中的较前的一个中，或者可以从处于这个序列中的较前的一个( (或多个或多个) )合式公式运用若干推理规则中

17、的一条推出合式公式运用若干推理规则中的一条推出。假如有一个。假如有一个从从推出推出n n的验证，就说的验证，就说n n是集合是集合的一个的一个定理定理(theorem)(theorem)。用下面的标记来表示。用下面的标记来表示n n可以从可以从得到验证：得到验证： n n 验证和定理的概念是与一个所使用的特定推理规则验证和定理的概念是与一个所使用的特定推理规则集合相关的。如果我们用字母集合相关的。如果我们用字母R R来表示推理规则集合，来表示推理规则集合，那么我们可以用如下符号写出这样的事实：那么我们可以用如下符号写出这样的事实： n n可以用可以用R R中的推理规则从中得到验证：中的推理规则

18、从中得到验证： R R n n 例如：给定一个合式公式的集合例如：给定一个合式公式的集合：P,R,PP,R,P Q Q，下面，下面的序列是一个的序列是一个QRQR验证它表达了上面所述的推理规则：验证它表达了上面所述的推理规则：P,P P,P Q,Q,R,Q Q,Q,R,Q R R 验证的概念可以基于一个偏序，也可以基于一个序列。验证的概念可以基于一个偏序，也可以基于一个序列。这种偏序可以由一个树结构来表示。验证树中的每个节点这种偏序可以由一个树结构来表示。验证树中的每个节点都标上一个合式公式，并且必须或者与都标上一个合式公式，并且必须或者与中的一个合式公中的一个合式公式对应，或者用若干推理规则

19、中的一条从树的父节点推出。式对应，或者用若干推理规则中的一条从树的父节点推出。被标记的树是一个根节点标记的验证。图下是一个验证树被标记的树是一个根节点标记的验证。图下是一个验证树的例子。的例子。 验证定义验证定义 语义语义 解释解释 语义语义(semantics)(semantics)必须把逻辑语言的要素与必须把逻辑语言的要素与论域论域(domain of discourse )(domain of discourse )的要素联系起来。这种联系的要素联系起来。这种联系就是我们用就是我们用“意义意义”(meaning)(meaning)这一词所指的。就命题这一词所指的。就命题逻辑来说，我们把原

20、子与关于这个世界的逻辑来说，我们把原子与关于这个世界的命题命题(proposition)(proposition)联系起来联系起来( (因而有命题逻辑的称谓因而有命题逻辑的称谓) )。 举例说，我们可以把原子举例说，我们可以把原子BAT_OKBAT_OK与命题与命题“电池是电池是充了电的充了电的”联系起来联系起来( (我们并没有被迫要用助记原子串我们并没有被迫要用助记原子串来做出这种联系，也可以用另外的代替来做出这种联系，也可以用另外的代替) )。 原子与命题的联系被称为原子与命题的联系被称为解释解释(interpretation)(interpretation)。在给定的解释中，与一个原子相

21、联系的命题被称为这在给定的解释中，与一个原子相联系的命题被称为这个原子的个原子的指称指称(denotation)(denotation)。语义语义 给定一个解释，原子为真或假值。假如原子给定一个解释，原子为真或假值。假如原子与命与命题题P P相联系，那么对这个世界来说，只有相联系，那么对这个世界来说，只有P P为真时我们才为真时我们才说说为真；反之它就为假。特殊原子为真；反之它就为假。特殊原子T T总是为真，而特殊总是为真，而特殊原子原子F F总是为假。总是为假。 假如一个假如一个agentagent有传感装置，这个装置可以用来决定有传感装置，这个装置可以用来决定各种有关这个世界的命题的真假，

22、那么当感觉特征各种有关这个世界的命题的真假，那么当感觉特征x1x1值值为为1 1时，与此相应的有关这个世界的命题也为真，并且与时，与此相应的有关这个世界的命题也为真，并且与此相联系的命题逻辑原子此相联系的命题逻辑原子( (也许是也许是x1x1) )也为真。因此，我也为真。因此，我们不用通过在某种输入们不用通过在某种输入“线线”上的一个值上的一个值l l或或0 0来为来为agentagent表述感觉到的信息，而是能用一个在表述感觉到的信息，而是能用一个在agentagent的记忆结构的记忆结构( (称为称为知识库，知识库，knowledge baseknowledge base) )中的命题演算

23、原子来表中的命题演算原子来表述它。述它。 一个原子一个原子x1x1在在agentagent的知识库中出现就意味着这个的知识库中出现就意味着这个agentagent把与此相联系的命题在它的世界中当作真。把与此相联系的命题在它的世界中当作真。 解解释释 命题真值表命题真值表 语义语义 在某种解释下给定原子的值，我们可以用一个在某种解释下给定原子的值，我们可以用一个真真值表值表(truth table)(truth table)来计算在同样解释下的任何合式公来计算在同样解释下的任何合式公式的值。这个真值表建立了命题联结词的语义式的值。这个真值表建立了命题联结词的语义( (意义意义) )。设设1 1

24、和和2 2是合式公式，那么真值表规则就是：是合式公式，那么真值表规则就是： 假如假如1 1 为真并且为真并且2 2也为真，那么也为真，那么(1 12 2) )就为真；否则，它就为假。就为真；否则，它就为假。 假如假如1 1 为真或者为真或者2 2为真，或两者都为真，为真，或两者都为真，那么那么(1 12 2) )就为真；否则，它就为假。就为真；否则，它就为假。 假如假如1 1 为假，那么为假，那么1 1 就为真；否则，就为真；否则，它就为假。它就为假。 的语义是以的语义是以和和来定义的。具体地说，来定义的。具体地说，(1 1 2 2) )是是( (1 12 2) )的替换形式和等价形式。的替换

25、形式和等价形式。 语义语义 命命题题真真值值表表 例：假设例：假设P P为假，为假， Q Q为假，为假， R R为真。为真。 ？PRQP)( 假如一个假如一个agentagent使用使用n n种特征种特征( (与命题相对应与命题相对应) )来描述它来描述它的世界，并且这些特征是用一个相应的的世界，并且这些特征是用一个相应的n n个原子的集合表个原子的集合表述在这个述在这个agentagent世界模型中，那么它的世界就会有世界模型中，那么它的世界就会有2 2n n种不种不同的情形同的情形只要这个只要这个agentagent能辨别，因为能辨别，因为n n个原子都可以个原子都可以有真值或假值，故存在

26、着有真值或假值，故存在着2 2n n种不同的情形。这个世界所能种不同的情形。这个世界所能有的每一种情形都对应于一个解释。给定有的每一种情形都对应于一个解释。给定n n个原子的值个原子的值( (解解释释) )，那么这个，那么这个agentagent就可以用真值表找到任何合式公式的就可以用真值表找到任何合式公式的值。值。相反的过程又是怎样的呢相反的过程又是怎样的呢? ? 语义语义 可满足性与模型可满足性与模型 一个合式公式在一种解释下被指派为真值，那么这一个合式公式在一种解释下被指派为真值，那么这种解释满足这个合式公式。一种满足一个合式公式的解种解释满足这个合式公式。一种满足一个合式公式的解释被称

27、为这个释被称为这个合式公式的一个模型合式公式的一个模型。一种解释满足在一。一种解释满足在一个合式公式集合中的每一个合式公式被称为这个个合式公式集合中的每一个合式公式被称为这个合式公合式公式集合的模型式集合的模型。因为一种解释给每一个原子指派一个值，。因为一种解释给每一个原子指派一个值，所以我们可以判定一种解释是否满足任何一个原子。我所以我们可以判定一种解释是否满足任何一个原子。我们可以用真值表来判定一种解释是否满足一个包含原子们可以用真值表来判定一种解释是否满足一个包含原子的合式公式。的合式公式。 假如合式公式如我们所期望的那样值为真，那么我假如合式公式如我们所期望的那样值为真，那么我们必须排

28、除所有这样的解释，在这些解释中们必须排除所有这样的解释，在这些解释中BAT_OKBAT_OK和和LIFTABLELIFTABLE为真，而为真，而MOVESMOVES为假。每个为假。每个“约束合式公式约束合式公式”都告诉我们一些有关这个世界可能的情形，并且排除一都告诉我们一些有关这个世界可能的情形，并且排除一些可能的模型些可能的模型( (每个模型都与这个世界的一种可能情形每个模型都与这个世界的一种可能情形相对应相对应) )。一般说来，描述这个世界的合式公式越多，一般说来，描述这个世界的合式公式越多，模型就越少模型就越少! ! 语义语义 可能没有任何解释可以满足一个合式公式可能没有任何解释可以满足

29、一个合式公式( (或或一个合式公式的集合一个合式公式的集合) )，在这种情况下，这个合式，在这种情况下，这个合式公式公式( (或合式公式的集合或合式公式的集合) )被说成是被说成是不一致的不一致的(inconsistent)(inconsistent)或或不可满足的不可满足的(unsatisfiable)(unsatisfiable)。 不可满足的合式公式的例子如不可满足的合式公式的例子如F F和和PPP (P (没没有一种解释可以使这些合式公式为真有一种解释可以使这些合式公式为真) )。 一个不可满足的合式公式集合的例子是一个不可满足的合式公式集合的例子是P P Q Q， P P Q Q，

30、P QP Q， P P Q(Q(用真用真值表可证实没有一种解释可以使所有这些合式公值表可证实没有一种解释可以使所有这些合式公式为真式为真) )。 可可满满足足性性与与模模型型 语义语义 永永真真性性 假如一个合式公式在它的组成原子的所有解释下都假如一个合式公式在它的组成原子的所有解释下都为真，那么它是永真的为真，那么它是永真的( (因而，因而，一个永真的合式公式是空一个永真的合式公式是空的的，它没有告诉我们任何有关这个世界可以是怎样的情，它没有告诉我们任何有关这个世界可以是怎样的情形形) )。下面是一些永真的合式公式的例子：。下面是一些永真的合式公式的例子： P P P ( P (这与这与PP

31、PP相同相同) ) T T (P (P P)P) Q T Q T ( P ( P Q ) Q ) P P P P P P ( Q ( Q P ) P ) 用真值表来确定一个合式公式的永真性要化费大量用真值表来确定一个合式公式的永真性要化费大量的时间，因为这个合式公式必须要针对所有原子值的组的时间，因为这个合式公式必须要针对所有原子值的组合来计算。合来计算。 语义语义 等价等价 当且仅当两个合式公式的真假值在所有的解释当且仅当两个合式公式的真假值在所有的解释中都是相同的，那么我们可以说它们是中都是相同的，那么我们可以说它们是等价的等价的。用。用符号符号“”表示等价。可以用真值表来验证下面的表示等

32、价。可以用真值表来验证下面的等价：等价： 德德. .摩根定律：摩根定律： 换质换位定律：换质换位定律： 假如假如1 1和和2 2是等价的，那么下面的公式是是等价的，那么下面的公式是永真的：永真的： 由于这个事实，由于这个事实，1 12 2这个标记常常被用作这个标记常常被用作为为(1 1 2 2) () (2 2 1 1) )的缩写。的缩写。 2 21 12 21 1) )( ( 2 21 12 21 1) )( ( ) )( () )( (1 12 22 21 1 )()(1221 语义语义 涵蕴涵蕴 如果在集合如果在集合中，每一个合式公式都为真的所有中，每一个合式公式都为真的所有解释下合式公

33、式解释下合式公式值为真值为真，那么我们说，那么我们说逻辑涵蕴逻辑涵蕴(logically entail)(logically entail) ，并且，并且从从中中逻辑地派生逻辑地派生(logical follow)(logical follow)， 是是的一个的一个逻辑推论逻辑推论(logical (logical consequence)consequence)。用符号。用符号 来指称逻辑涵蕴来指称逻辑涵蕴，并且写为，并且写为。下面是一些例子。下面是一些例子。 P P P P P P，P P Q Q Q Q F F ( (是任何合式公式是任何合式公式!)!) PQ PQ P P在最后的两个例

34、子中，把标记稍微作了简缩。在最后的两个例子中，把标记稍微作了简缩。当当为为单个时，常常这么做单个时，常常这么做。 语义语义 逻辑涵蕴在人工智能中是很重要的，因为它提供了逻辑涵蕴在人工智能中是很重要的，因为它提供了一种强有力的方法来说明一种强有力的方法来说明: : 如果有关一个世界的命题是如果有关一个世界的命题是真的，那么另一些所关注的命题真的，那么另一些所关注的命题( (也许是不能被感觉到的也许是不能被感觉到的) )也必须是真的。也必须是真的。 例如，假设我们感觉一些特征，把它们与公式例如，假设我们感觉一些特征，把它们与公式BAT_OKBAT_OK和和MOVESMOVES相联系，并且用公式相联

35、系，并且用公式BAT_OK BAT_OK LIFTABLE LIFTABLE MOVESMOVES来表述有关这个世界的知识。就是说，来表述有关这个世界的知识。就是说，我们有三个公式，其中两个描述一个特定的世界的情景，我们有三个公式，其中两个描述一个特定的世界的情景，其中另一个描述有关这个世界的一般知识。其中另一个描述有关这个世界的一般知识。 根据真值表知道根据真值表知道LIFTABLELIFTABLE由这三个公式逻辑涵蕴。由这三个公式逻辑涵蕴。既然根据这种涵蕴，既然根据这种涵蕴，LIFTABLELIFTABLE在所有这三个公式都为在所有这三个公式都为真的解释中为真，那么它在我们预期的解释真的解

36、释中为真，那么它在我们预期的解释(intended (intended interpretation)(interpretation)(即我们把它与机器人世界相联系的即我们把它与机器人世界相联系的) )中中一定为真。所以，这个作为我们预期的解释的一部分命一定为真。所以，这个作为我们预期的解释的一部分命题，即题，即“积木是不可举的积木是不可举的”必须是真的必须是真的! ! 涵涵蕴蕴 语义语义 涵涵蕴蕴 因为涵蕴对于决定有关这个世界的命题是真还因为涵蕴对于决定有关这个世界的命题是真还是假是一个强劲的工具，所以对我们来说，研究怎是假是一个强劲的工具，所以对我们来说，研究怎样把信息表述为合式公式，并且

37、怎样有效地产生出样把信息表述为合式公式，并且怎样有效地产生出涵蕴的合式公式是至关重要的。涵蕴的合式公式是至关重要的。 可以总用真值表来做这件事，但是我们要寻求可以总用真值表来做这件事，但是我们要寻求更简便的方法。一个富有吸引力的可以替代涵蕴的更简便的方法。一个富有吸引力的可以替代涵蕴的是是推理推理(inference)(inference)。虽然它们是根本不同的概念，。虽然它们是根本不同的概念，但是它们可以由但是它们可以由合理性合理性(soundness)(soundness)和和完备性完备性(completeness)(completeness)的概念联结起来。的概念联结起来。 语义语义 合

38、理性和完备性合理性和完备性 把推理与涵蕴联系起来有两个重要的定义：把推理与涵蕴联系起来有两个重要的定义： 1)1)假如对任意合式公式的集合假如对任意合式公式的集合和合式公式和合式公式，R R 蕴含着蕴含着 ，那么我们说推理规则集合，那么我们说推理规则集合R R是是合理的合理的(sound)(sound)。 2)2)假如对任意合式公式的集合假如对任意合式公式的集合和合式公式和合式公式，当有当有 时，存在用推理规则集合时，存在用推理规则集合R R从从推出推出的验证（的验证（ R R ），那么就说），那么就说R R是是完备的完备的(complete)(complete)。 当推理规则是合理和完备的时

39、候，可以通过寻找一当推理规则是合理和完备的时候，可以通过寻找一个验证而不是用真值表来确定一个合式公式是否由一个个验证而不是用真值表来确定一个合式公式是否由一个合式公式的集合导出。合式公式的集合导出。 当推理规则合理时，假如找到了一个当推理规则合理时，假如找到了一个从从导出的导出的验证，那么我们知道验证，那么我们知道是从是从逻辑地导出的。逻辑地导出的。 当推理规则完备时，我们知道最终能够通过一个完当推理规则完备时，我们知道最终能够通过一个完备的搜索过程搜寻一个验证来确定备的搜索过程搜寻一个验证来确定从从导出导出( (当它如此当它如此做的时候做的时候) )。 不管是在命题演算还是在谓词演算不管是在

40、命题演算还是在谓词演算( (将在后面研究将在后面研究) )中，用验证的方法来替换真值表法通常节省了巨大的计中，用验证的方法来替换真值表法通常节省了巨大的计算量。算量。 语义语义 合合理理性性和和完完备备性性 命题可满足性问题命题可满足性问题 为一个公式找一个模型的问题是一个命题为一个公式找一个模型的问题是一个命题可满足性可满足性问题问题(propositional satisfiability , PSAT)(propositional satisfiability , PSAT)。 在下一章中要说明任何公式可以被写为一些文字析在下一章中要说明任何公式可以被写为一些文字析取的合取。一些文字的析取被称为一个子句，一个写成取的合取。一些文字的析取被称为一个子句，一个写成子句合取的公式叫做子句合取的公式叫做合取范式合取范式(conjuncti