离散数学(05).ppt

1 1 1个体 谓词在命题演算中 原子命题是演算的基本单位 不再对原子命题进行分解 故无法研究命题内部的成分 结构及其逻辑特征 例如 所有的人总是要死的 苏格拉底是人 所以苏格拉底是要死的 第一章数理逻辑1 1个体 谓词和命题函数 2 凭直觉这个苏格拉底论证是正确的 但无法用命题演算表达出来 为了深入研究形式逻辑中的推理问题 所以有必要将命题演算扩充而引入谓词演算 2 1 1谓词例1 a 5是质数x是质数 b 张明生于北京x生于y c 7 3 2x y z 3 右侧是每个例子的模式 是质数 刻画x的性质 生于 刻画x和y的关系 刻画x y z的关系 我们把 5 张明 北京 7 3 2 叫做个体 代表个体的变元叫个体变元 刻画个体的性质或几个个体间关系的模式叫谓词 是质数 生于 都是谓词 前部分讨论的是命题逻辑 后部分讨论的是谓词逻辑 4 个体 指可以独立存在的客体 它可以是一个具体的事物 也可以是一个抽象的概念 例如 1 小李 自然数 等个体常元 表示具体的或特定的个体 常用小写字母a b c 表示 个体变元 表示抽象的或泛指的个体的词 常用小写字母x y z 表示 5 谓词一般用大写字母P Q R 表示 个体用小写字母a b c 等表示 单独的个体和谓词不能构成命题 故不能将它们分开以表示命题 设F表示 是质数 则 x是质数 表示为F x G表示 生于 则 x生于y 表示为G x y H表示 则 x yz 表示为H x y z F x G x y H x y z 等叫谓词命名式 简称谓词 6 一个个体变元的谓词叫一元谓词 两个个体变元的谓词叫二元谓词 一般地 n个个体变元的谓词叫n元谓词 记为P x1 x2 xn 也称为命题函数 只有个体是变元时 谓词才能称为命题函数 它与代数中的函数具有共同的性质 y f x 只有在x取到函数定义域里具体值a时 才有函数值f a 7 命题函数本身不具有真值 只有在变量赋值后才有真值 例如 P x1 x2 xn 只有在xi取到具体值P a b c 时 才有确定的真值 一般谓词用设定的字母表示 常用的谓词则用特定的符号表示 例如 x y 可写成 x y 或L x y L表示小于 x yz 可写成 x y z 要事先说明 8 但最常用的仍写成x y x yz 称为谓词的中缀记法 将表示关系的谓词放在个体之间 方便于比较 中缀记法多出现在二元谓词中 不管怎样记法 变元的次序是重要的 例如 x y 与 y x 不一样 一个字母代表一特定谓词 例如F代表 是质数 则称此字母为谓词常元 若字母代表任意谓词 则称此字母为谓词变元 这个区分并不 9 重要 我们通常不加区分 但一般从上下文可看出它的含义 谓词命名式中个体变元的取值范围叫做论述域或个体域 容易看出 空集不能作为论述域 所以 以后谈到论述域都至少有一个个体 个体的取值区域 如同函数中变量的定义域 用于个体是变元时 10 命题函数P x1 x2 xn 中变元x1 x2 xn的取值只能在个体域中 例1 a 5是质数 的论述域是正整数 b 7 3 2 的论述域是实数 c 张明生于北京 中x的变域是人类 y的变域是地名集 所以论述域分别是人类和地名集 11 谓词命名式中 若谓词是常元 个体变元代以论述域中的某一个体 就成为一个命题 例如 F 5 5是质数 是真 F 4 4是质数 是假 G 张明 北京 是真 假定张明生于北京 所以谓词命名式是一个命题函数 12 设x y z表示为P x y z 若取定x为3 即P 3 y z 可改记为P y z 成为二元谓词 再取定y为4 即P 4 z 可改记为P z 成为一元谓词 再取定z为5 即P 5 可改记为P 而成为命题 可见命题是0元谓词 所以谓词是命题概念的扩充 命题是谓词的一种特殊情况 将命题符号化是我们经常要遇到的问题 13 例如将下列命题符号化 1 如果你不出去 我就不进来 2 123是偶数当且仅当2整除123解 1 设P 要出去 Q 要进来 a 你 b 我 则原命题可以表示为 P a Q b 2 设A 是偶数 B 整除 a 123 b 2 则原命题可以表示为 A a B b a 14 量词1 全称量词 x读做 对一切x 对任一x 或 对每一x 这里 是全称量词 x标记 所作用的个体变元 xP x 表示 对一切x P x 是真 x P x 表示 对一切x P x 是真 xP x 表示 并非对一切x P x 是真 x P x 表示 并非对一切x P x 是真 15 2 存在量词 x读做 存在一x 对某些x 或 至少有一x 这里 是存在量词 x标记 所作用的个体变元 它的意思是肯定存在一个 但不排斥多于一个 相对与两个量词的称呼 我们把没有量词的谓词P x 读着 对一确定的x 它有P这样的性质 16 xP x 表示 有一x使P x 是真 x P x 表示 有一x 使 P x 是真 xP x 表示 至少存在一x使P x 是真 并非这样 x P x 表示 至少存在一x使 P x 是真 并非这样 17 xP x 表示 对每一个x 都具有P这一特性 xP x 表示 至少有一个x 具有P这一特性 量词仅仅用于个体为变元时 加上量词后的命题函数 才能全面 完整地描述命题函数在谓词P x Q x y 等的前边加上全称量词 x或存在量词 x 说成是变元x被全称量化或存在量化 18 例2 a y y y 1 c y y y 1 b y y 3 d y y 3 如果论述域是整数 则 a 是真 b 是假 c 和 d 是真 设F x 表示 x是质数 将谓词F x 变为命题有两种方法 第一种是将x取定一个值 例如4 那么F 4 是命题 假 这种方法的本质是给变元以约束 19 第二种是将谓词量化 例如 xF x 假 xF x 真 这种方法的本质也是给变元以约束 不过约束方法不一样 以量化的作用是约束变元 量化后所得命题的真值与论述域有关 例如 y y 3 如果论述域是正整数 这一命题是真 如果论述域是负整数 则这一命题是假 论述域中没有3 20 对不同的个体变元 用不同的论述域是可以的 但有时 不同的个体变元一起讨论时 用不同的论述域甚感不便 于是我们设想有一个集合 它包括谓词中各个体变元的所有个体域 我们称它为全总个体域 类似讨论集合时的全集 用了全总个体域以后 个体变元取值范围一致了 但不同论述对象须用不同的特性谓词加以再刻画 21 有了全总个体域 为了研究命题方便 我们约定当一个命题没有指明其个体的个体域时 一般都把全总个体域作为其个体域 而对每个个体变元的真正取值域 需使用一个谓词来加以限制 这个谓词就称为特性谓词 特性谓词是被全总个体域包含 这样我们就可以都在全总个体域中讨论命题了 22 设F x 表示 x是不怕死的 D x 表示 x是要死的 M x 表示 x是人 如果论述域是全人类 则 人总是要死的 译为 xD x 有些人不怕死 译为 xF x 如果是全总个体域 则分别译为 23 x M x D x 1 x M x F x 2 1 式 x M x D x 等价于 x M x D x 所以 1 可以表达为 对一切x 如果x是人 则x是要死的 也可表达为 对一切x x不是人 或是要死的 各概念间的关系如图所示 24 特性谓词是 M x 限制个体x是 人 25 2 式 x M x F x 可表达为 存在一些x x是人并且是不怕死的 各概念间的关系如图所示 以上两式中 M x 是特性谓词 用以刻画论述对象具有 人 这一特性 26 特性谓词怎样加入到断言中去 有以下两条规则 1 对全称量词 特性谓词作为蕴含式之前件而加入之 2 对存在量词 特性谓词作为合取项而加入之 第一条规则不易理解 例如 人总是要死的 译为 x M x D x 似乎也不错 其实不对 27 这主要由于量化断言的真假与论述域有关 在全总个体域里 先要确定x是人 才会有生死之分 如果个体是石头就不会死的 例 将下列命题符合化1 人都要犯错误解 可以这样说 对于所有的x 如果x是人 则x要犯错误 28 设 M x x是人D x x要犯错误则命题可表示谓 x M x D x 其中M x 是特性谓词一般地 对全称量词 特性谓词作为限制个体属于的子域 个体域 应作为蕴涵式的前件 29 2 有些人聪明 但不是所有的人都聪明解 设M 是人B 聪明命题中的 但 是一种 并且 的关系 有些 是存在量词 所有的 是全称量词 其中M x 表示特性谓词 所以该命题可以表示成 x M x B x x M x B x 30 一般地 对存在量词 特性谓词作为限制个体属于的子域 个体域 应作为合取项 例3 a 没有不犯错误的人 解设F x 为 x犯错误 M x 为 x是人 则上句可译为 x M x F x 31 b 凡是实数 不是大于零就是等于零或小于零 解设R x 表示 x是实数 x 0 x 0 x 0 分别表示x大于 等于 小于零 则上句可译为 x R x x 0 x 0 x 0 32 例4 a 对于所有的自然数 均有x y x 设F x y 表示x y x N x 表示 x是自然数 则上句可译为 x y N x N y F x y 如果F x y 表示x y 则上句可译为 x y N x N y F x y x 33 就是说 翻译时 允许把个体和运算符组成的式子 诸如x y x 2 x2等 作为个体 因为它们代表个体 填入谓词命名式的个体位上 b 某些人对某些食物过敏 设F x y 表示 x对y过敏 M x 表示 x是人 G x 表示 x是食物 于是上句可译为 x y M x G y F x y 34 c 每个人都有些缺点 设F x y 表示 x有y M x 表示 x是人 G x 表示 x是缺点 于是上句可译为 x M x y G y F x y d 尽管有人聪明 但未必一切人都聪明 35 设F x 表示 x聪明 M x 表示 x是人 于是上句可译为 x M x F x x M x F x 1 6 3量化断言和命题的关系 1 如果论述域是有限的 不妨设论述域是 1 2 3 那么 xP x P 1 P 2 P 3 xP x P 1 P 2 P 3 36 2 如果论述域是可数无限集合 诸如自然数集合 那么 xP x xP x 不能表达为有限的合取和析取 但概念可以推广 全称量化断言可看作无限合取 存在量化断言 可看作无限析取 例如论述域是自然数时 我们理解 xP x 为P 0 P 1 P 2 xP x 为P 0 P 1 P 2 37 3 如果论述域是不可数无限集合 诸如实数集合 则无法表达 以上展开式常可帮助我们具体理解 xP x 和 xP x 38 1 6 4谓词公式不出现命题联结词和量词的谓词命名式P x1 x2 xn 称为谓词演算的原子公式 此表示法也包括n 0的情况 此时P x1 x2 xn 即为原子命题公式P 由原子公式出发 我们可定义谓词演算的合式公式 简称公式 39 在命题逻辑中我们定义过 原子命题 由原子命题通过五种连接运算和括号可以组成命题公式 现在我们定义了原子公式 用原子公式通过五种连接运算 量词和括号可以组成谓词演算合式公式 方法与命题公式的组成一样 40 1 谓词演算的原子公式是谓词演算公式 2 若A B是谓词演算公式 则 A A B A B A B A B xA 和 xA 是谓词演算公式 3 只有有限次应用步骤1和2构成的公式才是谓词演算公式 易知命题演算公式 也是谓词演算公式另外形式 在书写时 有些括号可以省略 41 1 6 5自由变元与约束变元紧接于量词之后最小的子公式叫量词的辖域 例如 1 xP x Q x 2 x P x y Q x y P y z x的辖域是P x x的辖域是 P x y Q x y 辖域就是量词的管辖范围 不是原子公式 其两侧必须有括号 否则 不应有括号 42 在量词 x x的辖域内变元x的一切出现叫约束出现 称这样的x为约束变元 在一公式中 变元的非约束出现叫变元的自由出现 称这样的变元为自由变元 在上面例1中 P x 中的x是约束出现 Q x 中的x是自由出现 在上面例2中 x是约束出现 y和z是自由出现 43 在公式 y A y xR x y 中 x和y都是约束出现 在公式 xP y 中 y是自由出现 一个公式中 一个约束变元的符号是无关紧要的 如公式 xP x 若将x改为y 得 yP y 它与原公式有相同的意义 这同定积分中积分变量可以改变类似 所以一公式中的约束变元是可以更改的 改名规则如下 44 1 若要改名 则该变元在量词及其辖域中的所有出现均须一起更改 其余部分不变 2 改名时所选用的符号 必须是量词辖域内未出现的符号 最好