阶逻辑基本概念.ppt

第四章 一阶逻辑基本概念 上一节的复习 自然推理系统 P n定义3.3 自然推理系统P定义如下： 1字母表 （1） 命题变项符号：p，q，r，,pi，qi，ri， （2） 联结词符号：, （3） 括号和逗号：( , )， 2合式公式 同定义1.6 上一节的复习（续） 自然推理系统 P（续） 3推理规则 （1） 前提引入规则：在证明的任何步骤上 都可以引入前提。 （2） 结论引入规则：在证明的任何步骤上所 得到的结论都可以作为后继证明的前提。 （3） 置换规则：在证明的任何步骤上，命题 公式中的子公式都可以用与之等值的公式置换 ，得到公式序列中的又一个公式。 （4） 几条重要的推理规则 上一节的复习（续） （练习） n默写下列的“置换规则”和“推理规则” (1) 德摩根律 (2) 吸收律 (3) 蕴涵等值式 (4) 归谬论 (5) 假言推理规则 (6) 附加规则 (7) 化简规则 (8) 拒取式规则 (11) 假言三段论 (12) 析取三段论规则 (13) 合取引入规则 n在P中构造下面推理的证明 如果小张守第一垒并且小李向B队投球，则A队将取胜；或者A队 未取胜，或者A队获得联赛第一名；A队没有获得联赛的第一名； 小张守第一垒。因此，小李没有向B队投球。 （不用归谬法证明。） 引言 n在命题逻辑中，命题是最基本的单位， 对简单命题不再进行分解，并且不考虑 命题之间的内在联系和数量关系。因而 命题逻辑具有局限性，甚至无法判断一 些简单而常见的推理。 引言（续） n例 凡偶数都能被2整除； 6是偶数。 所以，6能被2整除。 这个推理是我们公认的数学推理中的真命题，但是在 命题逻辑中却无法判断它的正确性。因为在命题逻辑 中只能将推理中出现的三个简单命题依次符号化为p， q，r，将推理的形式结构符号化为 (pq)r 由于上式不是重言式，所以不能由它判断推理的正确 性。 引言（续） n为了克服命题逻辑的局限性，就应该将 简单命题再细分，分析出个体词，谓词 和量词，以期达到表达出个体与总体的 内在联系和数量关系，这就是一阶逻辑 所研究的内容。 n一阶逻辑也称一阶谓词逻辑或谓词逻辑 。 4.1. 一阶逻辑命题符号化 n一阶逻辑命题符号化的三个基本要素 个体词； 谓词； 量词。 个体词 n定义 个体词是指所研究对象中可以独立存在的具体的或抽象 的客体。 例如，小王，小李，中国，3。 n个体常项 将表示具体或特定的客体的个体词称作个体常项，一 般用小写英文字母a，b，c表示。 n个体变项 而将表示抽象或泛指的个体词称为个体变项，常用x ，y，z表示。 个体词（续） n个体域 称个体变项的取值范围为个体域(或称论域)。个体域 可以是有穷集合。 例如，1，2，3，a，b，c，d，a，b，c， ，x，y，z，；也可以是无穷集合，例如，自然数 集合N=0，1，2，实数集合R=x|x是实数 。 n全总个体域 有一个特殊的个体域，它是由宇宙间一切事物组成的 ，称它为全总个体域。 本书在论述或推理中如没有指明所采用的个体域，都 是使用全总个体域。 谓词 n定义 谓词是用来刻画个体词性质及个体词之间相互 关系的词。 n谓词常项 表示具体性质或关系的谓词。 n谓词变项 表示抽象的、泛指的性质或关系的谓词。 n表示 无论是谓词常项或变项都用大写英文字母F，G ，H，表示，可根据上下文区分。 例 (1) 是无理数。 个体词: (个体常项); 谓词: “是无理数”, 记为F (谓词常项); 命题: F( ). (2) x是有理数。 个体词: x (个体变项); 谓词: “是有理数”, 记为G (谓词常项); 命题: G( x ). 例（续） (3) 小王与小李同岁。 个体词: 小王(a)、小李(b) (个体常项); 谓词: “与同岁”, 记为H (谓词常项); 命题: H(a,b). (4) x与y具有关系L. 个体词: x、y (个体变项); 谓词: “与具有关系L”, 记为L (谓词变项); 命题: L(x,y). 例（续） n一般的， 用F(a)表示个体常项a具有性质F(F是谓 词常项或谓词变项); 用F(x)表示个体变项x具有性质F; 而用F(a，b)表示个体常项a，b具有关 系F; 用F(x,y)表示个体变项x，y具有关系F. n元谓词 n用P(x1,x2,xn)表示含n(n1)个命题变项的 n元谓词。n=1时，P(x1)表示x1具有性质P； n2时，P(x1,x2,xn)表示x1,x2,xn具有 关系P. n实质上，n元谓词P(x1,x2,xn)可以看成以个 体域为定义域，以0,1为值域的n元函数或 关系。 n它不是命题。要想使它成为命题，必须用谓词 常项取代P，用个体常项a1,a2,an取代 x1,x2,xn，得P(a1,a2,an)是命题。 0元谓词 n有时候将不带个体变项的谓词称为0元谓 词，例如，F(a)，G(a,b)， P(a1,a2,an)等都是0元谓词。 n当F，G，P为谓词常项时，0元谓词为命 题。这样一来，命题逻辑中的命题均可 以表示成0元谓词，因而可以将命题看成 特殊的谓词。 例4.1. 将命题在一阶逻辑中 用0元谓词符号化，并讨论其真值 (1)只有2是素数，4才是素数。 分析： 个体词: 2, 4 (个体常项); 谓词: 是素数 (谓词常项). 解： 设一元谓词F(x): x是素数， 个体常项: a:2，b:4。 (1)中命题符号化为0元谓词的蕴涵式: F(b)F(a) 由于此蕴涵前件为假，所以(1)中命题为真。 例4.1（续，练习） (2)如果5大于4，则4大于6. 解: 设二元谓词G(x，y): x大于y， 个体词: a:4，b:5，c:6。 G(b,a)，G(a,c)是两个0元谓词，把(2)中命 题符号化为 G(b,a)G(a,c) 由于G(b,a)为真，而G(a,c)为假，所以(2)中 命题为假。 量词 n有了个体词和谓词之后，有些命题还是 不能准确的符号化，原因是还缺少表示 个体常项或变项之间数量关系的词。 n定义 称表示个体常项或变项之间数量关系的 词为量词。 (1) 全称量词; (2) 存在量词. 全称量词 n日常生活和数学中所用的“一切的”，“所 有的”，“每一个”，“任意的”，“凡”，“ 都”等词可统称为全称量词，将它们符号 化为“ ”。 n用 x， y等表示个体域里的所有个体，而 用 xF(x)， yG(y)等分别表示个体域 里所有个体都有性质F和都有性质G。 存在量词 n日常生活和数学中所用的“存在”，“有一 个”，“有的”，“至少有一个”等词统称为 存在量词，将它们都符号化为“ ”。 n 用x， y等表示个体域里有的个体，而用 xF(x)， yG(y)等分别表示个体域 里存在个体具有性质F和存在个体具有性 质G等。 一阶逻辑命题符号化 n例4.2 在个体域分别限制为(a)和(b)条 件时，将下面两个命题符号化 (1) 凡人都呼吸。 (2) 有的人用左手写字。 其中: (a)个体域D1为人类集合； (b)个体域D2为全总个体域。 例4.2（续） (1) 凡人都呼吸。 (2) 有的人用左手写字。 n解 (a) 令F(x): x呼吸。 G(x): x用左手写字。 (1) 在D1中除了人外，再无别的东西，因而“ 凡人都呼吸”应符号化为 xF(x) (2) 在D1中的有些个体(人)用左手写字，因而 “有的人用左手写字”符号化为 xG(x) 例4.2（续） (1) 凡人都呼吸。 (2) 有的人用左手写字。 分析: D2中除了有人外，还有万物，因而在(1)，(2)符号化时，必 须考虑将人分离出来。 解(b) 令M(x): x是人。 在D2中，(1)，(2)可以分别重述如下: (1)对于宇宙间一切事物而言，如果事物是人，则他要呼吸。 (2)在宇宙间存在着用左手写字的人。 于是(1)，(2)的符号化形式分别为 x(M(x)F(x) x(M(x)G(x) 其中F(x)与G(x)的含义同(a)中。 例4.2（续，分析与总结） n特性谓词的使用 (1) 由例4.2可知，命题(1)，(2)在不同的个 体域D1和D2中符号化的形式不一样。 (2) 主要区别在于，在使用个体域D2时，要将 人与其他事物区分开来。 (3) 为此引进了谓词M(x)，像这样的谓词称为 特性谓词。在命题符号化时一定要正确使用特 性谓词。 例4.2（续，分析与总结） n联结词的使用 (1) x(M(x)F(x) (2) x(M(x)F(x) n当F是谓词常项时， xF(x)和 xF(x)都是命 题。 例4.2（续，分析与总结） n全总个体域的约定 作为一种约定，今后没有特别指明个体 域，都采用全总个体域。 例4.4. 将下列命题符号化， 并讨论真值 (1)所有的人都长着黑头发。 (2)有的人登上过月球。 (3)没有人登上过木星。 (4)在美国留学的学生未必都是亚洲人。 例4.4. (1)所有的人都长着黑头发 n分析 (1) 特性谓词的使用； (2) 联结词的使用； (2) 全总个体域的约定。 例4.4. (1)所有的人都长着黑头发（续） n解 由于本题没有提出个体域，因而应该采用全总个体域 ，并令M(x): x为人。 令F(x): x长着黑头发。命题(1)符号化为 x(M(x)F(x) (4.9) 设a为某个金发姑娘，则M(a)为真，而F(a)为假，所 以M(a)F(a)为假，故(4.9)所表示的命题为假。 例4.4. (3)没有人登上过木星 n解 令H(x):x登上过木星。 命题(3)符号化形式为 x(M(x)H(x) (4.11) 到目前为止，对于任何一个人(含已经去世的 人)都还没有登上过木星，所以对任何人a， M(a)H(a)均为假，因而 x(M(x)H(x)为 假，所以(4.11)表示的命题为真。 (2)有的人登上过月球（练习） (4)在美国留学的学生未必都是亚洲人 例4.5 将下列命题符号化 n(1) 兔子比乌龟跑得快。 n(2)有的兔子比所有的乌龟跑得快。 例4.5（续） n分析 （1）本题没有指明个体域，因而采用全 总个体域。 （2）出现二元谓词，因而引入两个体 变项x与y。 例4.5（续） n解 令F(x): x是兔子，G(y): y是乌龟，H(x,y): x 比y跑得快，L(x,y): x与y跑得一样快。 这2个命题分别符号化为 x y(F(x)G(y)H(x,y) (4.13) x(F(x) y(G(y)H(x,y) (4.14) N元谓词符号化 n分析命题中表示性质和关系的谓词，分 别符号化为一元和n元谓词； n根据命题的实际意义选用全称量词或存 在量词； n注意谓词的先后顺序； n命题的符号化形式不是唯一的。 课后作业 (1) 习题四 第1(-1,-3,-5), 2, 4(-2,-4), 5(-1,- 3), 6(-2,-4,-6)题 （第65,66页）. 4.2. 一阶谓词公式及其解释 n自然推理系统P n形式语言 为在一阶逻辑中进行演算和推理，还必须给出 一阶逻辑中公式的抽象定义及其它们的解释。 n 一阶逻辑与一阶语言 一阶语言是用于一阶逻辑的形式语言，而一阶 逻辑是建立在一阶语言上的逻辑体系。 符号 n非逻辑符号 非逻辑符号更像是所描述的特定对象中的符号，包括 ：个体常项符号、函数符号、谓词符号。 n逻辑符号 逻辑符号则是逻辑系统中的符号，包括：个体变项符 号、量词符号、联结词符号、括号、逗号。 一阶语言（定义4.1-4.4） n设L是一个非逻辑符号集合，由L生成的一阶语 言的字母表包括下述符号： 非逻辑符号 (1) L中的个体常项: a, b, c,ai, bi, ci, i1. (2) L中的函数符号: f, g, h, fi, gi, hi, , i1. (3) L中的谓词符号: F, G, H, Fi, Gi, Hi, i1. 逻辑符号 (1) 个体变项: x, y, z, xi, yi, zi, i1. (2) 量词符号: , . (3) 联结词符号:, . (4) 括号与逗号: (, ), ,. 一阶语言（续） n中项项的定义义 (1) 个体常项和个体变项是项。 (2) 若f(x1,x2,xn)是任意的n元函数， t1,t2,tn是任意的n个项，则 f(t1,t2,tn)是项。 (3) 所有的项都是有限次使用(1)，(2) 得到的。 一阶语言（续） n中原子公式的定义义 设R(x1,x2,xn)是的任意n元谓词， t1,t2,tn是 的任意的n个项，则称 R(t1,t2,tn)是的原子公式。 如: 例4.5中的1元谓词F(x)，G(x)，2元谓 词H(x,y)，L(x,y)等都是原子公式。 一阶语言（续） n中合式公式/谓词谓词 公式/公式的定义义 (1) 原子公式是合式公式。 (2) 若A是合式公式，则(A)也是合式公式。 (3) 若A，B是合式公式，则(AB)， (AB)，(AB)，(A B)也是合式公式。 (4)若A是合式公式，则 xA， xA也是合式公式。 (5)只有有限次的应用(1)(4)构成的符号串 才是合式公式。 一阶语言的相关说明 n一阶语言是针对非逻辑符号集L的 不同的一阶语言使用不同的非逻辑符号 集L，但它们构成谓词公式的规则是一样 的。 nL不一定要包括全部3类非逻辑符号 自由与约束 n定义4.5 在公式 xA和 xA中，称x为指导变元 ，A为相应量词的辖域。在 x和 x的 辖域中，x的所有出现都称为约束出现。 A中不是约束出现的其他变项均称为是自 由出现的。 自由与约束（续） n指出公式中的指导变元，各量词的辖域，自由出现以 及约束出现的个体变项 闭公式 n设A是任意的公式，若A中不含有自由出 现的个体变项，则称A为封闭的公式，简 称闭式。 一阶公式的解释 n中的谓词谓词 公式是按照形成规则规则 生 成的符号串，没有实际实际 的含义义。只 有将其中的变项变项 （个体变项变项 、谓词谓词 变项变项 等）用指定的常项项代替后，所 得公式才有具体的实际实际 含义义。 一阶公式的解释（续） n将下列公式中的变项指定成常项使其成为命题 分析： （1）指定个体变项的变化范围； （2）指定谓词F，G的含义 一阶公式的解释（续） 一阶公式的解释（续） n在例4.7中所谈的对各种变项的指定也可 以称为对它们的解释。 n在本例中是给出公式后再对它们进行解 释，也可以先给出解释，再用这个解释 去解释各种公式。 n一个解释不外乎指定个体域、个体域中 一些特定的元素、特定的函数和谓词等 部分。 解释I n定义4.7 设是由L生成的一阶语阶语 言， 的解 释I由下面4部分组成： （注意对比教材中的定义） 解释I的几点说