控制工程课件：02知识表示-1.ppt

1、按照按照符号主义的观点，知识是一切智能符号主义的观点，知识是一切智能行为的基础，要使计算机具有智能，首行为的基础，要使计算机具有智能，首先必须使它拥有知识。先必须使它拥有知识。2.12.1 知识与知识表示知识与知识表示2.22.2 一阶谓词逻辑表示法一阶谓词逻辑表示法2.32.3 产生式表示法产生式表示法2.42.4 框架表示法框架表示法2.52.5 语义网络表示法语义网络表示法2.62.6 面向对象表示法面向对象表示法 人人之所以有智能行为是因为他们拥之所以有智能行为是因为他们拥有知识，拥有对知识的获取、表达、搜有知识，拥有对知识的获取、表达、搜索、分析、解答等智能能力。索、分析、解答等智能

2、能力。 知识表示一直是知识表示一直是AIAI研究中的一个瓶颈。研究中的一个瓶颈。其难点在于知识中隐含有不确定性，即模糊性其难点在于知识中隐含有不确定性，即模糊性和随机性。和随机性。 2.1.1 2.1.1 什么是知识？什么是知识？ 1 1、知识、知识是是人们在改造客观世界的实践中积累起来的认识和经验。人们在改造客观世界的实践中积累起来的认识和经验。是是经过削减、塑造、解释和转换的信息。知识是经过加经过削减、塑造、解释和转换的信息。知识是经过加工的信息。工的信息。 Feigenbaum 是是由特定领域的描述、关系和过程组成的。由特定领域的描述、关系和过程组成的。 Bernstein 知知识识=

3、=事实事实+ +信念信念+ +启发式规则。启发式规则。 Hayes-Roth 是是某论域中所涉及的各有关方面、状态的一种符号表示。某论域中所涉及的各有关方面、状态的一种符号表示。 从知识库观点看从知识库观点看 知识可从知识可从( (范围，目的，有效性范围，目的，有效性) )加以三维描述：加以三维描述：知识的知识的范围范围是由具体到一般，是由具体到一般，知识的知识的目的目的是由说明到指定，是由说明到指定，知识的知识的有效性有效性是由确定到不确定。是由确定到不确定。例如例如“为了证明为了证明ABAB，只需证明，只需证明AAB B是不可满足的是不可满足的”这种知识是一般性、指定性、确定的。这种知识是

4、一般性、指定性、确定的。而像而像“桌子有四条腿桌子有四条腿”这种知识是具体的、说明的、这种知识是具体的、说明的、不确定的。不确定的。例如例如“为了证明为了证明ABAB，只需证明，只需证明AAB B是不可满足的是不可满足的”这种知识是一般性、指示性、确定性的。这种知识是一般性、指示性、确定性的。而像而像“桌子有四条腿桌子有四条腿”这种知识是具体的、说明性的、这种知识是具体的、说明性的、不确定性的。不确定性的。2 2、数据、信息和知识、数据、信息和知识 数据数据是记录信息的符号，是信息的载体和表示。是记录信息的符号，是信息的载体和表示。 信息信息是对数据的解释，是数据在特定场合下的具体含义。是对数

5、据的解释，是数据在特定场合下的具体含义。 两者必须紧密结合，才能实现对现实世界中某一具体事两者必须紧密结合，才能实现对现实世界中某一具体事物的描述。物的描述。 现实生活中，信息以数据的形式来表达和传递，数据中现实生活中，信息以数据的形式来表达和传递，数据中蕴涵着信息。蕴涵着信息。 例如：例如：028-85966393028-85966393：数据，蕴涵的信息是电话号码：数据，蕴涵的信息是电话号码- -计计算机学院办公室。算机学院办公室。 只有把相关的信息关联到一起的时候形成的信息结构才只有把相关的信息关联到一起的时候形成的信息结构才形成形成知识知识。 028 028 的知识的知识 85966

6、85966 的知识的知识3 3、信息、知识和智能、信息、知识和智能信息：信息：是由数据表达的客观事实是由数据表达的客观事实知识：知识：是由智力对信息进行加工后所形成的对客观世界规律性的认识是由智力对信息进行加工后所形成的对客观世界规律性的认识智能：是指人类在认识客观世界中，由思维过程和脑力活智能：是指人类在认识客观世界中，由思维过程和脑力活动所表现出的综合能力动所表现出的综合能力三者之间的关系三者之间的关系信息：是形成知识的原料，是智能的加工对象信息：是形成知识的原料，是智能的加工对象知识：是信息的关联，是由智能加工后的产品知识：是信息的关联，是由智能加工后的产品智能：是信息到知识的一个加工器

7、智能：是信息到知识的一个加工器 4 4、智能知识的表现方式、智能知识的表现方式1 1）知识的获取能力：通过感知器官，在观察、测量、）知识的获取能力：通过感知器官，在观察、测量、训练、操作等实践中，获取直接经验的积累或感性训练、操作等实践中，获取直接经验的积累或感性知识，以及在学习、阅读、交谈等过程中，获取间知识，以及在学习、阅读、交谈等过程中，获取间接经验知识或理性知识。接经验知识或理性知识。2 2）知识的处理能力：将感性知识上升为理性知识，）知识的处理能力：将感性知识上升为理性知识，进行演绎推理与归纳推理，通过知识的积累、存储、进行演绎推理与归纳推理，通过知识的积累、存储、联想、类比、分析、

8、计算、论证、比较、探索、择联想、类比、分析、计算、论证、比较、探索、择优等信息处理过程，求得问题的解答，制定规划与优等信息处理过程，求得问题的解答，制定规划与决策。决策。3 3）知识的运用能力：运用所获得的知识，通过）知识的运用能力：运用所获得的知识，通过知识信息处理，根据所求得的问题解答或所制知识信息处理，根据所求得的问题解答或所制定的规划决策作出反应，采取行动，发挥知识定的规划决策作出反应，采取行动，发挥知识的效用，如回答咨询、诊断疾病、操纵机器等。的效用，如回答咨询、诊断疾病、操纵机器等。5 5、知识的特性知识的特性1 1）知识的相对正确性）知识的相对正确性 任何知识都是在一定环境下相对

9、正确的，而非绝对任何知识都是在一定环境下相对正确的，而非绝对正确。正确。2 2）知识的不确定性）知识的不确定性 知识可能是确定的，也可能是不确定的。知识可能是确定的，也可能是不确定的。3 3）知识的可表示性）知识的可表示性 知识是可以用形式化的东西表示的，如语言、文字、知识是可以用形式化的东西表示的，如语言、文字、图表、公式、数字等。图表、公式、数字等。4 4）知识的可利用性）知识的可利用性 可以利用知识解决各种问题。可以利用知识解决各种问题。 6 6、知识的分类、知识的分类（1 1）以知识的作用范围来划分）以知识的作用范围来划分: : 常识性知识常识性知识 领域性知识领域性知识（2 2）按知

10、识的作用及表示来划分）按知识的作用及表示来划分: : 事实性知识事实性知识 规则性知识规则性知识 控制性知识控制性知识 元知识元知识 事实性（叙述性）知识事实性（叙述性）知识：有关系统状态、环境和条件，问题的：有关系统状态、环境和条件，问题的概念、定义和事实的知识；常以概念、定义和事实的知识；常以“是是”的形式出现。的形式出现。 如：雪是白色的、鸟有翅膀、张三李四是好朋友、这辆车是如：雪是白色的、鸟有翅膀、张三李四是好朋友、这辆车是张三的。张三的。规则性（过程型）知识：规则性（过程型）知识：是有关问题中与事物的行动、动作相是有关问题中与事物的行动、动作相联系的因果关系、系统状态变化、问题求解过

11、程的操作、演联系的因果关系、系统状态变化、问题求解过程的操作、演算和行动的知识，是动态的，常以算和行动的知识，是动态的，常以“如果如果那么那么”形式出现。形式出现。特别是启发式规则是专家提供的专门经验知识，这种知识虽无特别是启发式规则是专家提供的专门经验知识，这种知识虽无严格解释但很有用处。严格解释但很有用处。控制（过程）性知识控制（过程）性知识是有关问题的求解步骤、技巧性知识，告是有关问题的求解步骤、技巧性知识，告诉怎么做一件事。也包括当有多个动作同时被激活时应选哪诉怎么做一件事。也包括当有多个动作同时被激活时应选哪一个动作来执行的知识。一个动作来执行的知识。它常与程序结合在一起出现。它常与

12、程序结合在一起出现。元知识元知识是有关知识的知识，是知识中的高层知识。包括怎样使是有关知识的知识，是知识中的高层知识。包括怎样使用规则、解释规则、校验规则，解释程序结构等知识。用规则、解释规则、校验规则，解释程序结构等知识。它存它存在于知识库中。在于知识库中。说明：说明：元知识与控制知识是有重迭的，对一个大的程序来说，以元知元知识与控制知识是有重迭的，对一个大的程序来说，以元知识或元规则形式体现控制知识更为方便，因为元知识存于知识或元规则形式体现控制知识更为方便，因为元知识存于知识库中，而控制知识常与程序结合在一起出现，从而不容易识库中，而控制知识常与程序结合在一起出现，从而不容易修改。修改。

13、例：对于从北京到上海，是乘飞机还是火车的问题，其知识例：对于从北京到上海，是乘飞机还是火车的问题，其知识可归纳为：可归纳为：* * 事实性（叙述性）知识事实性（叙述性）知识：北京、上海、飞机、火车、时间、：北京、上海、飞机、火车、时间、费用等；费用等；* * 规则性（过程型）知识规则性（过程型）知识：乘飞机、坐火车等；：乘飞机、坐火车等；* * 控制性知识控制性知识：乘飞机较快、较贵；坐火车较慢、较便宜。：乘飞机较快、较贵；坐火车较慢、较便宜。（3 3）知识的确定性来划分：）知识的确定性来划分： 确定性知识确定性知识 不确定性知识不确定性知识（4 4）按人类的思维及认识方法来划分：）按人类的思

14、维及认识方法来划分： 逻辑性知识逻辑性知识 形象性知识形象性知识 2.1.2 2.1.2 知识表示的概念知识表示的概念 1 1、什么是知识的表示？什么是知识的表示？知识的表示知识的表示可以看成是一组描述事物的约定，以把人类知识可以看成是一组描述事物的约定，以把人类知识表示成机器能处理的表示成机器能处理的数据结构数据结构。即用一组符号把知识编码。即用一组符号把知识编码成计算机可以接受的某种结构。成计算机可以接受的某种结构。 知识的表示知识的表示是研究用机器表示知识的可行性、有效性的一般是研究用机器表示知识的可行性、有效性的一般方法，是一种数据结构与控制结构的统一体，既考虑知识方法，是一种数据结构

15、与控制结构的统一体，既考虑知识的存储又考虑知识的使用。的存储又考虑知识的使用。表示表示能力能力能否正确、有效地表示问题。包括：能否正确、有效地表示问题。包括：表示范围的广泛性表示范围的广泛性领域知识表示的高效性领域知识表示的高效性对非确定性知识表示的支持程度对非确定性知识表示的支持程度可可利用性利用性可利用这些知识进行有效推理。包括：可利用这些知识进行有效推理。包括： 对对推理的适应性：推理是根据已知事实利用知识导出结果的推理的适应性：推理是根据已知事实利用知识导出结果的过程。过程。 对对高效算法的支持程度：知识表示要有较高的处理效率。高效算法的支持程度：知识表示要有较高的处理效率。可实现性可

16、实现性要便于计算机直接对其进行处理要便于计算机直接对其进行处理可组织性可组织性可以按某种方式把知识组织成某种知识结构可以按某种方式把知识组织成某种知识结构可维护性可维护性便于对知识的增、删、改等操作便于对知识的增、删、改等操作自然性自然性符合人们的日常习惯符合人们的日常习惯可理解性可理解性知识应易读、易懂、易获取等知识应易读、易懂、易获取等 2、知识表示的要求知识表示的要求3 3、知识表示的观点、知识表示的观点陈述性观点：知识的存储与知识的使用相分离。陈述性观点：知识的存储与知识的使用相分离。优点：灵活、简洁，演绎过程完整、确定，知识维护方便缺点：推理效率低、推理过程不透明过程性观点：知识寓于

17、使用过程性观点：知识寓于使用它它的过程中。的过程中。优点：推理效率高、过程清晰 缺点：灵活性差、知识维护不便 4 4、知识表示的方法、知识表示的方法 逻辑表示法逻辑表示法：一阶谓词逻辑一阶谓词逻辑- - 基于语法的策略，目标应用通用广泛基于语法的策略，目标应用通用广泛 产生式表示法产生式表示法：产生式规则产生式规则 大量使用特定问题域的经验大量使用特定问题域的经验结构表示法结构表示法：语义网络、框架语义网络、框架 对象及其之间的关系（概念关联，层次分类）对象及其之间的关系（概念关联，层次分类）过程表示法过程表示法 显示表示问题域的基础理论、功能及求解过程显示表示问题域的基础理论、功能及求解过程

18、 5 5、知识表示的具体形式、知识表示的具体形式知识外部表示模式：是与软件开发与运行的软件工具与平台知识外部表示模式：是与软件开发与运行的软件工具与平台无关的知识表示的形式化描述。无关的知识表示的形式化描述。 知识内部表示模式：是与开发软件工具与平台有关的知识知识内部表示模式：是与开发软件工具与平台有关的知识表示的存储结构。表示的存储结构。从实用观点看，从实用观点看，AIAI是一门是一门知识工程学知识工程学：以知识为对象，研究：以知识为对象，研究知识的表示方法、知识的运用和知识的获取。知识的表示方法、知识的运用和知识的获取。知识可以用模式知识可以用模式 K=F+R+C K=F+R+C 来表达来

19、表达其中：其中： K K知识项（知识项（Knowledge itemsKnowledge items） F F事实（事实（FactsFacts） 表示人类对客观世界，客观事物的状态、属性、特征的表示人类对客观世界，客观事物的状态、属性、特征的描述，以及对事物之间关系的描述。描述，以及对事物之间关系的描述。 R R规则（规则（RulesRules） 表示能表达在前提与结论之间的因果关系的一种形式。表示能表达在前提与结论之间的因果关系的一种形式。 C C概念（概念（ConceptsConcepts） 表示事实的含义规则、语义说明等。表示事实的含义规则、语义说明等。6 6、知识模型的变换、知识模型的

20、变换 对于不同的知识表达方法，有各种不同的形式化知识模型。对于不同的知识表达方法，有各种不同的形式化知识模型。通过通过同构同构和和同态同态的概念可以对知识模型进行变换和简化，以便的概念可以对知识模型进行变换和简化，以便更简洁地表达知识，易于问题的求解。更简洁地表达知识，易于问题的求解。 其变换方式如下：其变换方式如下： 原始问题原始问题 难求解难求解 原始解答原始解答 同构变换同构变换 等价等价 （明确）（明确） 同构问题同构问题 便于求解便于求解 同构解答同构解答 同态变换同态变换 蕴含蕴含 （简化）（简化） 同态问题同态问题 易求解易求解 同态解答同态解答 同构变换与同态变换图同构变换与同

21、态变换图例：方格棋盘分割问题例：方格棋盘分割问题： 2n 初始状态初始状态 2n (a) 原始问题原始问题 (b)同构问题同构问题 (c)同态问题同态问题 方格棋盘的分割问题方格棋盘的分割问题第一次分割第一次分割 2，00，02n2n2 22 2次操作次操作 原始问题：原始问题： 在在2n2n2n2n的方格棋盘中，去掉对顶角上两个小方格后，的方格棋盘中，去掉对顶角上两个小方格后，问能否将它分割为若干问能否将它分割为若干1 12 2的小长方块？的小长方块？ 求解原始问题是很困难的，由于对求解原始问题是很困难的，由于对n n的数值未加限制，可的数值未加限制，可以是任意大的正整数。直接求解要考察以是

22、任意大的正整数。直接求解要考察2(2n)22(2n)2种可能的分种可能的分割方案，而且随着割方案，而且随着n n的增大，还会出现的增大，还会出现“组合爆炸组合爆炸”问题。问题。 解解: :（1 1）将原始问题化为同构问题：）将原始问题化为同构问题：将棋盘中的小方格相间地作以不同的颜色，将其化为将棋盘中的小方格相间地作以不同的颜色，将其化为同构问题同构问题： 无论无论n n为何值，对顶的两个小方格的颜色都是同色的。为何值，对顶的两个小方格的颜色都是同色的。 由于每个由于每个1 12 2长方块只能包括一个小白格和一个小红格，长方块只能包括一个小白格和一个小红格，因此，无论如何分割，最后剩下的必定是

23、同色的两个小方格，因此，无论如何分割，最后剩下的必定是同色的两个小方格，无法分割成原始问题要求的小长方块。无法分割成原始问题要求的小长方块。 由于同构问题无解，所以原始问题无解。由于同构问题无解，所以原始问题无解。 （2 2）将同构问题化为同态问题：）将同构问题化为同态问题： 为了简化原始问题，引入同态变换：引入序对，为了简化原始问题，引入同态变换：引入序对， ，用以表示待分割的棋盘，用以表示待分割的棋盘状态，化为状态，化为同态问题同态问题。 初始状态：初始状态： 2n-2； 目标状态：目标状态： ; 分割操作：每次操作，分割出一个小长方块。分割操作：每次操作，分割出一个小长方块。割去一个小白

24、格和一个小红格，使状态变量都减割去一个小白格和一个小红格，使状态变量都减去去1 1，如第一次分割后，使初始状态变为：，如第一次分割后，使初始状态变为： 2n-3； 经过经过2n2n2 2-2-2次操作，使状态变为次操作，使状态变为，不可，不可能达到目标状态能达到目标状态。所以同样无解。所以同样无解。一些常用的知识表示形式：一些常用的知识表示形式： 一阶谓词逻辑、产生式规则、框架、语义网络、一阶谓词逻辑、产生式规则、框架、语义网络、类和对象、模糊集合、贝叶斯网络、脚本、过程等。类和对象、模糊集合、贝叶斯网络、脚本、过程等。 机器推理机器推理 演绎推理、归纳推理和类比推理演绎推理、归纳推理和类比推

25、理 不确定性推理和不确切性推理不确定性推理和不确切性推理 约束推理、定性推理、范例推理、非单调推理约束推理、定性推理、范例推理、非单调推理 2.2 2.2 一阶谓词逻辑表示法一阶谓词逻辑表示法基于谓词逻辑的机器推理也称自动推理。它是人工智能早基于谓词逻辑的机器推理也称自动推理。它是人工智能早期的主要研究内容之一。期的主要研究内容之一。一阶谓词逻辑是一种表达力很强的形式语言，是知识表示一阶谓词逻辑是一种表达力很强的形式语言，是知识表示的首选。的首选。基于这种语言，不仅可以实现类似于人推理的自然演绎法基于这种语言，不仅可以实现类似于人推理的自然演绎法自动推理，而且也可实现不同于人的归结法（或称消解

26、）自动推理，而且也可实现不同于人的归结法（或称消解）自动推理。自动推理。 1 1、谓词逻辑、谓词逻辑 命题：命题：具有真假意义的句子。命题代表人们进行思维时的一具有真假意义的句子。命题代表人们进行思维时的一种判断，或者是肯定，或者是否定。种判断，或者是肯定，或者是否定。命题的意义为真命题的意义为真真值为真，记为真值为真，记为T T；否则记为；否则记为F F。 今天下雨了。今天下雨了。 F F 1815 1815 F F 1+1=2 1+1=2 T T 1+1=10 1+1=10 T T 加拿大是一个国家。加拿大是一个国家。T T 是偶数而是奇数。是偶数而是奇数。 T T 孔莹是护士。孔莹是护士

27、。 F F 没有真假意义的句子不是命题。没有真假意义的句子不是命题。例如：命令句，感叹句，疑问句均不是命题。例如：命令句，感叹句，疑问句均不是命题。 （1 1）把门关上！）把门关上！ （2 2）你到哪里去？）你到哪里去？ 语句既为真，同时又包含假的不是命题，这样的句子称为语句既为真，同时又包含假的不是命题，这样的句子称为“悖论悖论”。 （3 3）他正在说谎。）他正在说谎。 （在命题逻辑中不讨论这类问题）（在命题逻辑中不讨论这类问题）命题的局限命题的局限无法描述客观事物的结构及逻辑特征，不能把不同事物间的共无法描述客观事物的结构及逻辑特征，不能把不同事物间的共同特征表述出来。同特征表述出来。谓词

28、谓词 谓词包括谓词名和个体。谓词包括谓词名和个体。谓词名：刻画个体的性质、状态或个体间的关系。谓词名：刻画个体的性质、状态或个体间的关系。个体：表示独立存在的事物或某个抽象的概念。个体：表示独立存在的事物或某个抽象的概念。 可以是常量、变量或函数。可以是常量、变量或函数。谓词的一般形式：谓词的一般形式： P(xP(x1 1, x, x2 2, x, x3 3x xn n) ) P(x P(x1 1) ) 谓词谓词 Teacher(Zhang) Teacher(Zhang) Teacher(father(Wang) Teacher(father(Wang) P(x P(x1 1, x, x2 2

29、) ) 谓词谓词 Less(x,5)Less(x,5) P(x P(x1 1,x,x2 2,x,x3 3, ,x xn n) ) 谓词谓词2 2、谓词与函数的区别谓词与函数的区别 Teacher( Teacher( ) ) 函数：值为个体域中的某个体，常小写；函数：值为个体域中的某个体，常小写； Teacher( Teacher( ) ) 谓词谓词 ：值为真或假，常大写；：值为真或假，常大写； 个体常量、个体变元、函数统称为个体常量、个体变元、函数统称为“”。在谓词在谓词P(xP(x1 1, x, x2 2, x, x3 3x xn n) )中，中， 若若 x xi i（i=1,2,i=1,2

30、,.n.n）都是个体常量、个体变元或函数，则）都是个体常量、个体变元或函数，则为一阶谓词。为一阶谓词。 若若 x xi i本身又是一个一阶谓词，则本身又是一个一阶谓词，则P P为二阶谓词。为二阶谓词。 余类推。余类推。 3 3、谓词公式、谓词公式 用连词连接若干谓词组成谓词公式。用连词连接若干谓词组成谓词公式。 表达比较复杂的含义。谓词公式中可以用量词来表达比较复杂的含义。谓词公式中可以用量词来刻画谓词与个体间的关系。刻画谓词与个体间的关系。 ： ( (有优先级有优先级) )P QP QP P PQPQPQPQPQPQT TT TF FT TT TT TT FT FF FT TF FF FF

31、TF TT TT TF FT TF FF FT TF FF FT T谓谓词词逻逻辑辑真真值值表表 全称量词全称量词( (x)x)：表示对个体域中的所有个体：表示对个体域中的所有个体x x。 存在量词存在量词( (x)x)：表示在个体域中存在个体：表示在个体域中存在个体x x。例子：例子： 若谓词若谓词F(F(x,yx,y) )表示表示x x与与y y是好朋友，则：是好朋友，则：( (x)(x)(y)F(y)F(x,yx,y) )表示表示对于个体域中的任何个体对于个体域中的任何个体x x，都存在个体，都存在个体y y，x x与与y y是朋友。是朋友。 （班里每个女同学都有一个男同学是好朋友）（班

32、里每个女同学都有一个男同学是好朋友）( (x)(x)(y)F(y)F(x,yx,y) )表示表示在个体域存在个体在个体域存在个体x x，他与个体域中的任何，他与个体域中的任何个体个体y y都是朋友。都是朋友。 （班里女同学小菲（班里女同学小菲, ,她与班里每个男同学都是她与班里每个男同学都是好朋友）好朋友）( (x)(x)(y)F(y)F(x,yx,y) )表示表示在个体域中存在个体在个体域中存在个体x x和个体和个体y y，x x与与y y是朋是朋友。友。（班里有女同学小菲和男同学小雷他们两个是朋友）（班里有女同学小菲和男同学小雷他们两个是朋友）由下述规则得到的谓词公式称为由下述规则得到的谓

33、词公式称为合式公式合式公式。1 1）单个谓词是合式公式。）单个谓词是合式公式。2 2）若）若A A是合式公式，则是合式公式，则A A也是合式公式。也是合式公式。3 3）若）若A A、B B都是合式公式，则都是合式公式，则ABAB，ABAB，ABAB都是合式公式。都是合式公式。4 4）若）若A A是合式公式，是合式公式，x x是任一个体变元，则是任一个体变元，则( (x)Ax)A和和( (x)Ax)A也是也是合式公式。合式公式。 在合式公式中，连词的优先级别依序为：在合式公式中，连词的优先级别依序为： ， 位于量词后的单个谓词或用括弧括起来的合式公式称为该量位于量词后的单个谓词或用括弧括起来的合

34、式公式称为该量词的词的。 辖域内与量词变元同名的变元称为辖域内与量词变元同名的变元称为， 不受约束的变元称为不受约束的变元称为。变元的换名变元的换名 当对量词辖域内的约束变元更名时，必须把辖域内当对量词辖域内的约束变元更名时，必须把辖域内同名同名的约束变元都统一改成的约束变元都统一改成相同相同的名字，且的名字，且不能不能与辖域与辖域内的自由变元同名。内的自由变元同名。 当对量词辖域内的自由变元更名时，不能改成与约当对量词辖域内的自由变元更名时，不能改成与约束变元同名。束变元同名。例如：例如： ( (x)x)(P(P(x x,y)Q(,y)Q(x x,y),y)R(x,y)R(x,y) 前面前面

35、2 2个个x x是受限的，是受限的，y y都是自由的。都是自由的。可以这样修改：可以这样修改：( (k)k)(P(P(k k,y)Q(,y)Q(k k,y),y)R(x,y)R(x,y)谓词公式的解释谓词公式的解释 在命题逻辑中，对命题公式中各个命题的一次在命题逻辑中，对命题公式中各个命题的一次真值真值指派指派称为命题的一个解释。称为命题的一个解释。定义：定义：设设D D为谓词公式为谓词公式P P的个体域，若对的个体域，若对P P中的个体常量、中的个体常量、函数和谓词按如下规定赋值函数和谓词按如下规定赋值: :1 1）为每个个体常量指派）为每个个体常量指派D D中的一个元素中的一个元素2 2）

36、为每个）为每个n n元函数指派一个从元函数指派一个从D Dn n到到D D的映射，其中的映射，其中 D Dn n=(x=(x1 1, x, x2 2, ,x xn n)/ x)/ x1 1, x, x2 2, ,x,xn nDD3 3）为每个）为每个n n元谓词指派一个从元谓词指派一个从D Dn n到到F,TF,T的映射。的映射。则称这些指派为公式则称这些指派为公式P P在在D D上的一个解释。上的一个解释。 例子：个体域例子：个体域D=1,2D=1,2， 求公式求公式A=(A=(x)(x)(y)P(x,y)y)P(x,y)在在D D上的解释，上的解释， 并指出在每一种解释下公式并指出在每一种

37、解释下公式A A的真值。的真值。谓词在谓词在D D上的真值指派上的真值指派 形成一种解释形成一种解释A A的真值的真值P(1,1)=FP(1,1)=FP(1,2)=FP(1,2)=FP(2,1)=FP(2,1)=FP(2,2)=FP(2,2)=FF FP(1,1)=FP(1,1)=FP(1,2)=FP(1,2)=FP(2,1)=FP(2,1)=FP(2,2)=TP(2,2)=TF FP(1,1)=FP(1,1)=FP(1,2)=FP(1,2)=FP(2,1)=TP(2,1)=TP(2,2)=FP(2,2)=FF FP(1,1)=FP(1,1)=FP(1,2)=FP(1,2)=FP(2,1)=T

38、P(2,1)=TP(2,2)=TP(2,2)=TF FP(1,1)=FP(1,1)=FP(1,2)=TP(1,2)=TP(2,1)=FP(2,1)=FP(2,2)=FP(2,2)=FF FP(1,1)=FP(1,1)=FP(1,2)=TP(1,2)=TP(2,1)=FP(2,1)=FP(2,2)=TP(2,2)=TT TP(1,1)=FP(1,1)=FP(1,2)=TP(1,2)=TP(2,1)=TP(2,1)=TP(2,2)=FP(2,2)=FT TP(1,1)=FP(1,1)=FP(1,2)=TP(1,2)=TP(2,1)=TP(2,1)=TP(2,2)=TP(2,2)=TT T谓词在谓词

39、在D D上的真值指派上的真值指派 形成一种解释形成一种解释A A的真值的真值P(1,1)=TP(1,1)=TP(1,2)=FP(1,2)=FP(2,1)=FP(2,1)=FP(2,2)=FP(2,2)=FF FP(1,1)=TP(1,1)=TP(1,2)=FP(1,2)=FP(2,1)=FP(2,1)=FP(2,2)=TP(2,2)=TT TP(1,1)=TP(1,1)=TP(1,2)=FP(1,2)=FP(2,1)=TP(2,1)=TP(2,2)=FP(2,2)=FT TP(1,1)=TP(1,1)=TP(1,2)=FP(1,2)=FP(2,1)=TP(2,1)=TP(2,2)=TP(2,2

40、)=TT TP(1,1)=TP(1,1)=TP(1,2)=TP(1,2)=TP(2,1)=FP(2,1)=FP(2,2)=FP(2,2)=FF FP(1,1)=TP(1,1)=TP(1,2)=TP(1,2)=TP(2,1)=FP(2,1)=FP(2,2)=TP(2,2)=TT TP(1,1)=TP(1,1)=TP(1,2)=TP(1,2)=TP(2,1)=TP(2,1)=TP(2,2)=FP(2,2)=FT TP(1,1)=TP(1,1)=TP(1,2)=TP(1,2)=TP(2,1)=TP(2,1)=TP(2,2)=TP(2,2)=TT T 续续- - 例子：例子： 个体域个体域D=1,2,

41、D=1,2, 求公式求公式A=(A=(x)(x)(y)P(x,y)y)P(x,y)在在D D上的解，上的解， 并指出在每一种解释下公式并指出在每一种解释下公式A A的真值的真值。可见：谓词公式的真值是针对某一个解释可见：谓词公式的真值是针对某一个解释而言的，它可能在某一个解释下的真值为而言的，它可能在某一个解释下的真值为T T，在另一个解释下的真值为，在另一个解释下的真值为F F。：若谓词公式若谓词公式P P对个体域对个体域D D上的任何一个解释都取得上的任何一个解释都取得真值真值T T，则称，则称公式公式P P在在D D上上是永真的。是永真的。如果如果P P在在每个每个非空个体域上均永真，则

42、称非空个体域上均永真，则称P P是永真的。是永真的。可见：为了判定某个公式永真，必须对每个个体域上的每一可见：为了判定某个公式永真，必须对每个个体域上的每一个解释逐一判定公式的真值。个解释逐一判定公式的真值。：对于谓词公式对于谓词公式P P，如果至少存在一个解释使得，如果至少存在一个解释使得公式公式P P在此解释下的真值为在此解释下的真值为T T，则称公式，则称公式P P是可满足的。又称为是可满足的。又称为。：如果谓词公式如果谓词公式P P对于个体域对于个体域D D上任何一个解上任何一个解释都取得真值释都取得真值F F，则称公式，则称公式P P在在D D上是永假的。上是永假的。 谓词公式的永假

43、性谓词公式的永假性又称为不可满足性。又称为不可满足性。 谓词公式的永真、可满足性、不可满足性谓词公式的永真、可满足性、不可满足性 谓词公式的等价性谓词公式的等价性：设设P P与与Q Q是两个谓词公式，是两个谓词公式，D D是它们共同的个体域，是它们共同的个体域，若对若对D D上的任何一个解释，上的任何一个解释，P P与与Q Q都有相同的真值，则称都有相同的真值，则称公式公式P P和和Q Q在在D D上是等价的。如果上是等价的。如果D D是任意的个体域，则称是任意的个体域，则称P P和和Q Q是等价的。记为是等价的。记为P QP Q一些常用等式：一些常用等式：（1 1）交换率）交换率 PQ QP

44、PQ QP PQ QP PQ QP（2 2）结合率）结合率 （PQ)R P(QR)PQ)R P(QR) （PQ)R P(QR)PQ)R P(QR)（3 3）分配率）分配率 PP（QR) QR) （PQPQ）（PR)PR) P P（QR) QR) （PQPQ）（PR) PR) （4 4）狄）狄. .摩根率摩根率 (PQ) (PQ) PPQ Q (PQ) (PQ) PPQ Q（5 5）双重否定率）双重否定率P PP P（6 6）吸收率）吸收率 PP（PQ) PPQ) P P P（PQ) P PQ) P （7 7）补余率）补余率 PPP TP T P PP F P F （8 8）连词化归率）连词化归

45、率 PQ PQ PQPQ（9 9）量词转换率）量词转换率 ( (x)P (x)P (x)x)P P ( (x)P (x)P (x)x)P P （1010）量词分配率）量词分配率 ( (x)(PQ) (x)(PQ) (x)P(x)P(x)Q x)Q ( (x)(PQ) (x)(PQ) (x)P(x)P(x)Qx)Q 谓词公式的永真蕴含谓词公式的永真蕴含：对于谓词公式：对于谓词公式P P和和Q Q，如果，如果PQPQ永真，则称永真，则称P P永真永真蕴含蕴含Q Q，且称，且称Q Q为为P P的逻辑结论，称的逻辑结论，称P P为为Q Q的前提。的前提。记为记为P QP Q。常用的永真蕴含等式：常用的

46、永真蕴含等式：（1 1）化简式）化简式 PQ PPQ P PQ Q PQ Q（2 2）附加式）附加式 P PQP PQ Q PQ Q PQ（3 3）析取三段论）析取三段论 P P，PQ QPQ Q（4 4）假言推理假言推理 P P，PQ QPQ Q（5 5）拒取式推理）拒取式推理 Q Q，PQ PQ P P （6 6）假言三段论）假言三段论 PQPQ，QR PRQR PR（7 7）二难推理）二难推理 PQPQ，PRPR，QR RQR R（8 8）全称固化）全称固化 ( (x)P(x) P(y)x)P(x) P(y) 其中其中y y是个体域中的任意一个体，利用此永真蕴含式可是个体域中的任意一个体

47、，利用此永真蕴含式可以消去公式中的全称量词。以消去公式中的全称量词。（9 9）存在固化）存在固化 ( (x)P(x) P(y) x)P(x) P(y) 其中其中y y是个体域中某一可使是个体域中某一可使P(y)P(y)为真的个体。为真的个体。利用此利用此永真蕴含式可以消去公式中的存在量词。永真蕴含式可以消去公式中的存在量词。 等价式、永真蕴含式等公式称为等价式、永真蕴含式等公式称为；用推理规则推导出的新的合式公式称为用推理规则推导出的新的合式公式称为；使用推理规则的序列构成定理的一个使用推理规则的序列构成定理的一个。规则规则( (引用前提规则引用前提规则) )：在任何推理步骤上都可以在任何推理

48、步骤上都可以引入前提。引入前提。2 2）T T规则规则( (逻辑结果引用规则逻辑结果引用规则) ) ：在推理时，若前面在推理时，若前面步骤中有一个或多个公式永真蕴含公式步骤中有一个或多个公式永真蕴含公式S S，则可把，则可把S S引入推理过程中。引入推理过程中。 推理规则、定理与证明推理规则、定理与证明3 3）CPCP规则规则( (附加前提规则附加前提规则) )： 如果能从如果能从R R和给定的前提集合和给定的前提集合P P中推导出中推导出S S来，则就能来，则就能从前提集合从前提集合P P中推导出（中推导出（RSRS）来。）来。 即：即： 若若 (PRS) (PRS) 则：则：P(RS) P

49、(RS) 4 4）反证法规则：反证法规则： Q Q为为P P1 1,P,P2 2, ,P,Pn n的逻辑结论，当且仅当：的逻辑结论，当且仅当：P P1 1PP2 2PPn nQ Q是不可满足的。是不可满足的。将将P P1 1PP2 2PPn n 简约记为简约记为 ，有：，有： P PQ Q 是可满足的是可满足的等价于等价于 P PQ Q 是可满足的是可满足的等价于等价于 ( (P PQ) Q) P PQ Q 是是不不可满足的可满足的 是永真的是永真的是永真的是永真的是不可满足的是不可满足的 例子：有例子：有假言推理假言推理： 如果下雨，停止足球赛如果下雨，停止足球赛 天在下雨天在下雨 所以停止

50、足球赛所以停止足球赛 用命题表示：用命题表示： P P：下雨：下雨 Q Q：停止足球赛：停止足球赛 PQPQ：如果下雨，停止足球赛：如果下雨，停止足球赛即，证明：即，证明：Q Q为为P P和和PQPQ的有效结论的有效结论证明：证明： P P P P规则规则 PQ PQ P P规则规则 Q Q T T规则规则 命题逻辑的表达能力是有限的：命题逻辑的表达能力是有限的： 例如：例如： 张三是人张三是人 李四是人李四是人 缺陷：命题逻辑不能表达他们之间的共同性质。缺陷：命题逻辑不能表达他们之间的共同性质。再例如，有三段论：再例如，有三段论： 所有的人都是会死的所有的人都是会死的 因为诸葛亮是人因为诸葛