离散数学教学课件-ch4.pptVIP

第四章 一阶逻辑基本概念 主要内容 一阶逻辑命题符号化 一阶逻辑公式及其解释 苏格拉底三段论： “所有人都是要死的.” “苏格拉底是人.” “所以，苏格拉底是要死的.” 苏格拉底三段论应该是正确的，但在命题逻辑中无法判断. 为了克服命题逻辑的局限性，要将命题再细分，分离出个体词、谓词和量词. 这就是一阶逻辑的研究内容. 4.1 一阶逻辑命题符号化 1. 个体词 定义: 个体词是指研究对象中可以独立存在的客体 注：个体词可以是具体的事物，也可以是抽象的概念. 例如：曹操是个体词（具体）， x也是个体词（抽象） (1) 将表示具体或特定的客体的个体词称为个体常项，一般用a, b, c表示 (2) 将表示抽象或泛指的客体的个体词称为个体变项，一般用x, y, z表示 个体变项的取值范围称为个体域(论域). 注: (1) 只有个体变项才有个体域. (2) 个体域可以是有穷集合，也可以是无穷集合. 例如：生物信息12级的全体学生 有穷 自然数集合 无穷 (3) 由宇宙间一切事物组成的个体域称为全总个体域. 谓词 2. 谓词 定义：谓词是用来刻画个体词性质及个体词之间相互关系的词，常用F,G,H,? 表示. 一般地，用F(x)表示“x具有性质F ” 用G(x,y)表示“x与 y 有关系G ” 用F(x1, x2,?, xn)表示x1, x2,?, xn之间有关系F 不含个体变项的谓词称为0元谓词. (1)表示具体性质或关系的谓词称为谓词常项. (2)表示抽象性质或关系的谓词称为谓词变项. 谓词 例: (1) e是无理数. (2) x是有理数. (3) 冯绍峰与孙老师同岁. (4) x与y具有关系L. 量词 3. 量词 定义：表示个体常项或变项之间数量关系的词称为量词. (1) 全称量词，表示“每一个”，“所有的”，“任意的”，“凡”等，用?表示. ?xF(x)表示个体域中所有个体x具有性质F 注: ?xF(x)为真当且仅当个体域中每一个个体a都有F(a)为真; 量词 3. 量词 定义：表示个体常项或变项之间数量关系的词称为量词. (2)存在量词，表示“存在着”，“有一个”，“有的”，“至少有一个”等，用?表示. ?xF(x)表示个体域中存在个体x具有性质F 注: ?xF(x)为真当且仅当个体域中存在一个个体a有F(a)为真. 在谓词逻辑中，将命题符号化，要分析到个体词、谓词和量词，并要注意以下3点： (1) 明确个体域. 若预先指定个体域，就要在给定个体域中将命题符号化. 若预先未指定个体域，使用全总个体域. (2) 正确使用全称量词与存在量词，多个量词出现时，顺序不能随意调换. (3) 正确使用一元谓词与n(n≥2)元谓词. 例1. 在个体域分别限制为(a)和(b)条件时，将下面命题符号化. (1) 实数不是有理数就是无理数. (2) 有的实数是有理数. 其中(a) 个体域D1=R; (b) 个体域D2为全总个体域. 例2. 将下列命题符号化，并讨论真值. (1) 所有的人都长着黑头发. (2) 有的人登上过月球. (3) 没有人登上过木星. (4) 在美国留学的学生未必都是亚洲人. 例3. 将下列命题符号化. (1) 兔子比乌龟跑得快. (2) 有的兔子比所有的乌龟跑得快. (3) 并不是所有的兔子都比乌龟跑得快. (4) 不存在跑得同样快的两只兔子. 4.2 一阶逻辑公式及解释 一阶语言L 的项与原子公式 定义 L 的项定义如下： (1) 个体常项和个体变项是项. (2) 设? (x1, x2, …, xn)是任意n元函数, t1, t2, …, tn是项，则? (t1, t2, …, tn) 是项. (3) 有限次地使用(1)(2)形成的符号串是项. 一阶语言L 的公式 定义 合式公式定义如下： (1) 原子公式是合式公式. (2) 若A是合式公式，则 (?A)也是合式公式 (3) 若A, B是合式公式，则(A?B), (A?B), (A?B), (A?B)也是合式公式 (4) 若A是合式公式，则?xA, ?xA也是合式公式 (5) 有限次地应用(1)—(4)形成的符号串是合式公式. L 的合式公式也称为谓词公式，简称公式. 定义 在公式 ?xA 和 ?xA 中，称x为指导变元，A为量词的辖域. 在?x和 ?x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其他变项均称为自由出现. 例如：在公式?xF(x,y,z)? ?yG(x,y,z)中，