计算机数学基础-第9章.pptVIP

第9章 谓词逻辑基础 9.1 谓词逻辑的基本概念 9.2 谓词逻辑的等价式和蕴涵式 *9.3 谓词公式的前束范式 9.1 谓词逻辑的基本概念 9.1.1 个体、谓词与谓词表达式 9.1.2 命题函数与个体域 9.1.3 量词与辖域 9.1.4 谓词公式与语句的形式化 9.1.1 个体、谓词与谓词表达式 比较 命题逻辑 一个完整的语句为研究对象 谓词逻辑 将语句细分为“个体” 和“谓词”。 个体一般是语句的主语，谓词一般是语句的谓语。 9.1.2 命题函数与个体域 9.1.3 量词与辖域 9.1.4 谓词公式与语句的形式化 9.2 谓词逻辑的等价式和蕴涵式 9.2.1 谓词公式的永真、永假与可满足式 9.2.2 谓词逻辑的等价式与蕴涵式 9.2.1 谓词公式的永真、永假与可满足式 9.2.2 谓词逻辑的等价式与蕴涵式 * 个体：谓词演算中把要讨论对象称为个体，它们可以是客观世界中的具体客体，也可以是抽象的客体，诸如数字、符号等。 表示法： 个体常元：确定的个体常用a，b，c等小写字母或字母串表示。 个体变元: 不确定的个体常用字母x，y，z，u，v，w等来表示。 谓词：用来指明对象的性质或对象间关系的词。 表示法：用大写字母或者大写字母串表示谓词。 注意： （1）单独一个谓词不是完整的命题； （2）用谓词表达命题，必须包括个体和谓词两个部分，成为谓词表达式。 谓词的元数：通常把谓词所含个体的数目称为谓词的元数。 表示单个个体性质的谓词是一元谓词，例如P(x)。表示两个个体之间关系的谓词是二元谓词，例如Q（x,y）;依此类推得n元谓词。N=0时，称为0元谓词，它本身就是一个命题。故命题就是n元谓词的特殊情况 注意: 命题的谓词形式中的个体出现的次序影响命题的真值, 不能随意变动, 否则真值会有变化. 例如： P: …位于…和…之间; a: 天津, b: 沈阳, c: 广州. 则P(a, b, c)表示“天津位于沈阳和广州之间”是真命题。但是 P(b, a, c)表示“沈阳位于天津和广州之间”是假命题. 例 将下列语句写成谓词表达式形式: (1) 苏格拉底是要死的; (2) - 5的平方非负; (3) 董旎生于青岛; (4) 3+ 5 = 8. 解: (1) 设D表示“…是要死的”, s: 苏格拉底,原语句写成谓词表达式为: D(s) (2) 设NN表示“…是非负的”, 语句写成谓词表达式为: NN((-5)2). (3) 设B表示“…生于…”, a: 董旎, b: 青岛, 语句写成谓词表达式为: 或D(socrates). B(a, b)或B(Dongni, qingdao). ADD(3, 5, 8). (4) 设ADD表示“…+…=…”, 语句写成谓词表达式为: 定义9.1 由一个特定的谓词P和n个个体变元x1, x2, …, xn组成的形如P(x1, x2, …, xn)的表达式称为简单命题函数. 简单命题函数可用所有命题联接词联接组成复合命题函数. 若x 学习好, 则x工作好. 例如: A(x): x 学习好; B(x): x 工作好. 则A(x)∧B(x)表示: x 学习好并且工作好. A(x)→B(x)表示: 个体变元变化的范围即—个体的全体称为个体域, 当讨论对象遍及一切客体时, 个体域称为全总域. (4) “y是非负实数当且仅当y大于等于零” 可表示为: NN(y) ? 0 ≤ y, 其中 例 (1) “x是小于100的质数”可表示为: L(x, 100)∧P(x), 其中 L(x, 100): x小于100; P(x): x是质数. (2) “y小于等于3”可表示为 L(y, 3)∨E(y, 3), 其中 L(y, 3): y小于3; E(y, 3): y等于3. (3) “如果一个人生于北京, 那么他不生于上海”可表示为: B(x, beijing)→ ┐B(x, shanghai), 其中 B(x, beijing): x生于beijing. NN(y): y是非负的实数. 例如: ?y表示个体域内有的y. 量词分为两种： 1) 全称量词: “一切”, “所有”, “凡”, “每一个”, “任意”等等, 都是全称量词, 用符号?表示. 例如: ?x 表示个体域内所有的x. 2) 存在量词: “有一个”, “有的”, “存在”, “至少有一个”等等, 都是存在量词, 用符号?表示. ?xP(x)表示个体域中所有个体x都满足谓词P. ?xP(x)表示个体域中存在个体x满足谓词P. 例 将下列命题符号化. (1)?每个母亲都爱自己的孩子； (2) 所有的人都呼吸； (3) 某