《应用离散数学第2章--谓词逻辑.pptx》由会员分享，可在线阅读，更多相关《应用离散数学第2章--谓词逻辑.pptx（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、谓 词 逻 辑应用离散数学（第2版）第2章21世纪高等教育计算机规划教材方景龙方景龙 周丽周丽 编著编著目录2.1 个体词、谓词与量词2.2 谓词公式及其解释2.3 谓词公式的等价演算2.4 谓词公式的推理演算 在命题逻辑中，命题是最基本的单位，对原子命题不再进行分解，并且不考虑命题之间的内在联系和数量关系。因而命题逻辑具有局限性，甚至无法判断一些简单而常见的推理。例如，考虑下面著名的苏格拉底三段论：所有的人都是要死的。苏格拉底是人。所以，苏格拉底是要死的。这个推理是公认的真理，但在命题逻辑中却无法判断它的正确性。因为在命题逻辑中只能将推理中出现的三个原子命题依次符号化为p，q，r，将推理的形
2、式结构符号化为 由于上式不是永真式，所以不能由它判断推理的正确性。命题逻辑无法准确描述这个推理过程，原因在于命题逻辑本身未对各原子命题之间的内部成分的逻辑关系加以研究。为了更准确地对命题进行符号化，我们需要把一个逻辑判断的对象和谓语分离并细化，分析出其中的个体词、谓词和量词，研究它们的形式结构和逻辑关系、推理规则和推理形式，这就是本章的基本内容。2.1.1 个体词与谓词定义2.1 在原子命题中，表示对象的词称为个体词；表示对象所具有的性质或多个对象之间关系的词称为谓词。个体词一般是原子命题中的主语或宾语。个体词可以是具体事物，也可以是抽象的概念，例如，小王，夏天，偶数，思想等都可以作为个体词。
3、特定的个体词称为个体常元，用小写字母 a，b，c，L 或 表示；不确定的个体词称为个体变元，用小写字母 x，y，z，L或 表示。谓词一般是原子命题中的谓语，通常用大写字母 或 表示。含有n 个 个体变元的谓词称为n元谓词，也称为n元简单命题函数，通常记为 。它实际上是 到0，1的一个函数，其中Di是个体变元xi的个体域。所谓个体域就是个体变元遍历的非空集合。一般地，个体域应事先给定，如果没有给定，则约定个体域是全体事物构成的集合，称为全总个体域。另外，以后除非特别声明，否则认为一个n元谓词的所有个体变元的个体域是一样的。由简单命题函数和命题连接词构成的表达式称为复合命题函数。n元谓词 不是命题
4、，只有当n 元谓词中的全部个体变元在个体域中取定个体常元后它才成为命题，此时，谓词已经不含个体变元而只含个体常元。通常，我们将不含个体变元的谓词称为0元谓词，比如 ，等都是0元谓词。0元谓词是命题，命题逻辑中的命题都可表示为0元谓词，因此可将命题看成特殊的谓词。例2.1 分析下列语句的个体词和谓词。（1）计算机是现代科学技术的工具。（2）x 是偶数；2是偶数。（3）x 整除y；2整除3。解（1）“计算机”是个体常元，“是现代科学技术的工具”是谓词，表示个体的性质。（2）x 是个体变元，2是个体常元，“是偶数”是谓词，表示个体的性质。（3）x 和 y 是个体变元，2和3是个体常元，“整除”是谓词
5、，表示个体之间的关系。例2.2 用0元谓词符号化下列命题。（1）只有2是质数，4才是质数。（2）如果地球重于月亮，则太阳重于地球。（3）小王热爱自己的母亲。解（1）设一元谓词 是质数，个体常元 ，。命题符号化为0元谓词的蕴涵式：。（2）设二元谓词 x 重于y，个体常元 a：地球，b：月亮，c:太阳。命题符号化为0元谓词的蕴涵式：。（3）设二元谓词 x 热爱 y，一元函数 的母亲，个体常元 a：小王。则 表示个体常元“小王的母亲”，命题仍符号化为 。2.1.2 量词 在谓词逻辑中描述个体的性质或个体之间的关系，有时需要区分“全体个体”和“有些个体”等数量，因此有必要引进量词。因此，对于一元谓词
6、，和 都是命题，就好像由函数 构成的定积分 不再为 x 的函数一样。有了个体词、个体域、谓词、量词等概念后，我们就可以对命题进行更精细的符号化了。由例2.3可知，命题（1），（2）在不同的个体域 D1 和D2 中符号化的形式不一样，主要区别在于，在使用个体域 D2时，要将人从其他事物中区别开来，为此引进了谓词 ，像这样的谓词称为特性谓词。在命题符号化时一定要正确使用特性谓词。在例2.3中要注意的是，有些初学者在个体域为D2时将命题（1）符号化为 这是错误的，因为它对应的自然语言是“宇宙间的任何事物都是人并且都呼吸”，这显然与命题（1）的原意不符，事实上，任何非人的个体a 带入后，为假，所以 为
7、假，因而命题（1）不能符号化为 。同样，在 D2中将命题（2）符号化为 这也是错误的。因为它在个体域中有不是人的东西时总是成真，所以 成真，即使所有的人都用右手写字也是如此，这显然与命题（2）的原意不符。例2.4 将下列命题符号化。（1）所有的人都长着黑头发。（2）有的人登上过月球。（3）没有人登上过火星。（4）在美国留学的学生未必都是华人。例2.5 将下列命题符号化。（1）兔子比乌龟跑得快。（2）有的兔子比所有的乌龟跑得快。（3）并不是所有的兔子都比乌龟跑得快。（4）不存在跑得同样快的两只兔子。下面对微积分中函数连续的定义进行符号化。2.2 谓词公式及其解释2.2.1 谓词公式 下面我们定义
8、谓词逻辑中的公式谓词公式，而为了定义它，首先要定义其他两个概念项和原子公式。谓词公式是由原子公式、逻辑连接词、量词和圆括号等组成的符号串，命题逻辑中的命题公式仅是它的特例，所以命题逻辑包含于谓词逻辑之中。定义2.6 在谓词公式 和 中，称 x 为指导变元，称 A为相应量词的辖域或作用域，辖域中凡与指导变元相同的个体变元称为约束变元，不是约束变元的个体变元称为自由变元。定理2.1（换名规则）（1）在谓词公式中，将某量词辖域中出现的某个约束变元以及对应的指导变元改成本辖域中未曾出现过的个体变元符号，其余部分保持不变，公式的等价性不变。（2）在谓词公式中，将某个自由变元的所有出现用其中未曾出现过的某
9、个体变元符号代替，其余部分保持不变，公式的等价性不变。2.2.2 谓词公式的解释 同命题公式一样，谓词公式仅仅是一个符号串，并不具有任何实际意义，只有对谓词公式给出解释后，它才具有一定的意义，甚至有时就变成命题了。定义2.7 谓词公式 A 的一个解释 I 由下面四个部分组成：（1）非空个体域D。（2）对 A中每个个体常元符号，指定 D 中一个固定元素。（3）对A 中每个函数符号，指定一个具体的函数。（4）对 A中每个谓词符号，指定一个具体的谓词。在定义2.7中，所谓指定一个 n元函数和n 元谓词就是分别给出 和 的一个映射。例2.9的三个公式在上面的解释下都是命题，现在我们要问，是不是谓词公式
10、在任何解释下都可以成为命题？答案是否定的。只有封闭的谓词公式（简称闭式），它才在任何解释下都成为命题，而所谓封闭的谓词公式是指只有约束变元而没有自由变元的谓词公式。例如，例2.9中的公式（1）、（2）和（3）是闭式，所以它们在任何解释下都是命题。但如果一个公式不是闭式，则它在有的解释下可以成为命题，而在另一些解释下可能就不成为命题，下面再给出一个例子。定义2.8 设 是一个谓词公式，若A 在任何解释下均为真，则称 A为永真式（有效式）。若A 在任何解释下均为假，则称A 为永假式（矛盾式）。若存在解释使A 为真，则称A 为可满足式。在命题逻辑中，确定一个公式是永真式、永假式，还是可满足式，我们可
11、用通过该公式在所有解释下的取值情况，即真值表来进行判定。在谓词逻辑中，虽然无法使用真值表，但我们也可以类似地从谓词公式在所有解释下的取值情况来进行判断，并把这种方法称为解释法。对某些特殊的谓词公式，可以借助于命题逻辑中的永真式和永假式进行判断。为此我们回顾一下命题逻辑中的代替规则（定理1.1），这个规则指出，对于永真式（永假式），当其中的命题变元用任意的命题公式处处代入后所得到的新的命题公式仍然是永真式（永假式）。我们要问，对于命题逻辑中的永真式（永假式），其中的命题变元能否用谓词逻辑中的谓词公式代入呢？代入后所得到的谓词公式还是永真式（永假式）吗？回答是肯定的。2.3 谓词公式的等价演算 同
12、命题逻辑一样，在谓词逻辑中，一个命题同样可能有多种谓词公式表示。本节讨论谓词公式之间的等价关系。定义2.10 设 A 和 B 是两个谓词公式，如果在任何解释下，A 和B 都有相同的真值，则称A 和B等价，记为 。依据等值运算“”和谓词公式等价关系“”的定义不难证明如下定理，它与命题逻辑中的定理1.2相对应。定理2.3 设A 和B 是两个谓词公式，则 的充要条件是 是永真式。另外，同命题逻辑一样，谓词逻辑中也有一些重要的等价公式，由这些重要的等价公式可以推演出更多的等价公式来，下面我们来讨论这些公式。由于命题逻辑中的永真式的代替实例都是谓词逻辑中的永真式，因而我们有与命题逻辑中定理1.3相对的等
13、价公式，只不过这里的 A，B，C 已不再仅仅是命题公式，而是谓词公式，里面可以包含个体变元、项、原子公式、量词等。除了与命题逻辑中对应的等价公式外，在谓词逻辑中人们还证明了下面重要的等价公式。定理2.42.7的证明都是用解释法进行证明的，即说明在任何解释下，“左边取1时右边也取1，左边取0时右边也取0”或“左边取1时右边也取1，右边取1时左边也取1”。这种方法是证明谓词公式等价的基本方法，但有局限性，下面我们来讲谓词公式的等价演算方法。同命题公式的等价演算一样，要进行谓词公式的等价演算，除要使用上节介绍的重要等价公式外，有时还要用到下面的置换规则。2.4 谓词公式的推理演算2.4.1 基本概念
14、 定理2.7和例2.16的结果可以用图2.1形象地表示。图图2.1 量词的交换规律量词的交换规律2.4.2 演绎推理方法 前面我们说过，判断一个谓词公式是否为已知前提的逻辑结论可以使用解释法和等价演算法，但这些方法的缺陷在于不能清晰地表达其推理过程。同命题逻辑一样，下面介绍运用等价公式、推理公式和推理规则的谓词逻辑演绎推理方法。由于命题逻辑中的永真式的代替实例都是谓词逻辑中的永真式，因而有与命题逻辑中定理1.17相对的推理公式，只不过这里的A，B，C 已不再仅仅是命题公式，而是谓词公式，里面可以包含个体变元、项、原子公式、量词等。谓词公式中含有量词使得谓词逻辑的演绎推理变得比命题逻辑的演绎推理
15、要复杂。在谓词公式的演绎推理中，为了便于推理，有时需要引进或消去量词。因此在谓词公式的演绎推理中，除了要用到P规则（前提引入规则）、E规则（置换规则）和T规则（结论引入规则）外，还要用到四条与量词有关的推理规则，它们在谓词公式的演绎推理方法中起着重要作用。量词消去和引入的上述四条规则的使用都有一些前提条件，违反这些条件使用与量词相关的推理规则，都可能导致错误的结果。例2.23 证明下列论断的正确性：“所有的哺乳动物都是脊椎动物；并非所有的哺乳动物都是胎生动物；故有些脊椎动物不是胎生的。”解 先进行符号化。设个体域是全总个体域，是哺乳动物，是脊椎动物，是胎生动物。则即要证明 另外，同命题逻辑的演绎推理一样，在谓词逻辑的演绎推理中也可以使用附加前提法。谢 谢!应用离散数学（第2版）海量图书方便查询免费申请样书下载配套资源优惠购书成为作者更多样书申请和资源下载需求，请登录人邮教育社区（)囊括各大品类，您想要的应有尽有教师免费申请样书，我们将安排快递迅速送达教学视频、PPT课件、教学案例、习题答案、模拟试卷等丰富资源免费下载教师可以申请最低折扣学生直接优惠购买图书欢迎写文章投稿，我们强大的编辑团队将为您提供专业和高效的编辑出版服务