《谓词逻辑及演算》PPT课件.ppt

2020 3 27 1 第四章谓词逻辑及演算 4 1谓词与个体4 2量词4 3函词 函数 4 4自由变元与约束变元习题及参考答案 2020 3 27 2 4 1谓词与个体我们知道 命题演算的基本研究单位是原子命题 在命题演算中 原子命题是不能再分割的了 这对研究命题间的关系是比较合适的 但是 在进一步研究时就会发现 仅仅命题演算对我们是很不够的并且也不充分 比如 三段论在命题演算系统中是无法完成的 例如 所有的科学是有用的 数理逻辑是科学 所以 数理逻辑是有用的 又例如 凡人必死 张三是人故张三必死 2020 3 27 3 上述两个例子的主要原因就是在于这种推理中需要对原子命题作进一步分解 在上述两个例子中 每个例子三个命题间 具有必然的内在逻辑关系 只有对这种内存逻辑联系深入研究后 才能解决形式逻辑中的一些推理问题 谓词演算正是为了这样的目的 换言之也就是对原子命题进行进一步的分解 在谓词演算中 将原子命题分解为谓词与个体两部分 在上例中 数理逻辑是科学 即主语 数理逻辑 与谓语 是科学 张三是人 中的 张三 是主语 是人 为谓语 换言之在数理逻辑中将主语称为个体 将谓语称为谓词 所谓个体既是可以独立存在的物体 它可以是抽象的 也可以是具体的 如 鲜花代表团 自行车 自然数 唯物主义等等都是个体 谓词是用来刻划个体的性质或关系 如 3整除6 这里3与6是个体 关系 整除 是谓词 一个谓词可以与某个个体相联 此种谓词称为一元谓词 上例中张三 3 6等也可以是抽象的 比如x y 由个体组成的集合称为个体域 或论述域 以某个个体域I为变域的变元叫做个体变元 2020 3 27 4 一个单独的谓词是没有含义的 如 是大学生 这个谓词必须跟随一定数量的个体后才有明确的含义 最重要的是能分别其真假 个体谓词中的次序有时也是很重要的 如 上海位于南京与杭州之间 此命题为真 其中 上海 南京 杭州 三个个体间次序不能随便颠倒 如果写成 杭州位于南京和上海之间 则此时命为假 所以 由谓词以及跟随它的若干个有一定次序的个体便可构成一个完整的命题 下面我们一般用大写拉丁字母A B E表示谓词 用小写拉丁字母a b c z表示个体 或叫个体变元 这样x y间具有关系B可记作B x y x y z具有关系C 记作C x y z 上述是二元谓词和三元谓词 当然也可以表示为n元谓词就是有n个个体变元的谓词 并约定0元谓词是命题 并记为P Q R n元谓词当然需要赋于n个个体变元才有意义 我们把谓词后填以个体称为谓词填式 有了谓词的概念后我们可以将一些日常用语及命题更深刻地刻划出来 下面我们以几个例子说明 2020 3 27 5 例1 王强是大学生李华也是大学生 解 F表示大学生 F x 表示x是大学生 a表示 王强 b表示 李华 则此式可表示为 F a F b 例2 我国领导人访问美国 解 F x y 表示x访问y a表示我国领导人 b表示美国 则此式可表示为 F a b 2020 3 27 6 例3 这座大楼建成了 解 F x 表示 x建成了 G x 表示 x是大的 H x 表示 x是大楼 则此式可表示为 F a G a H a 例4 这个人正在看那本红皮面的书 解 F x y 表示 x正在看y G x 表示 x是人 H y 表示 y是红皮面的 U y 表示 y是书 a表示 这个 b表示 那本 则此式可表示为 F a b G a H b U b 2020 3 27 7 一般地讲 对日常的语句 我们可给出一个大体的准则 根据这些准则可写出其逻辑表达式来 名词 专用名词 如王强 美国等 为个体用名词 如楼房 人等 一般可为谓词代名词 人称代词 如 你 我 他 指示代词 如这个 那个 为个体 不定代词 如任何 每个 有些 一些等 为量词 形容词 一般为谓词数词 一般为量词动词 一般为谓词副词 与所修饰的动词合并为一谓词 不在分解 前置词 与其它有关字合并为一 本身不独立表示 连接词 一般为命题联结词 以上准则只供参考 在具体应用时常常也有许多例外 2020 3 27 8 4 2量词在数学上或日常生活中经常碰到 对一切 所有的 存在一个 至少有一个 等的概念 我们以上学过的方法与技巧是无法表达清楚的 一个谓词演算中的表达不一定是确定的 个体域中不同而个体代入后可得到不同的真假值 如我们考察下面两个式子 它们均以整数作为其个体域 1 X 1 2 X2 2X 1 2 X 6 5对于 1 我们发现任何整数代入后等式总是正确 但是对 2 分析则不然 它只存在一个整数即 1 代入后使得等式成立 又如 q或者大于0 或者等于0 或者小于0 当然该句可写成 q 0 q 0 q0 a 0 a 0 a表示 每一数 这样的结果为 每一数大于0或每一数等于0或每一数小于0 显然这与原意不同 2020 3 27 9 通过上述例子说明 任一谓词演算与其个体间存在着一些关系 例如 1 对个体域中 所有个体 式子均为真2 对个体域中 一些个体 式子均为真那么如何在谓词演算中刻划谓词与个体间的关系呢 只有一个办法来引进一些新的符号 它们叫做量词 量词有两种 一种叫做全称量词 一种叫做存在量词 它的定义如下 2020 3 27 10 定义1 凡表示 任意一个 一切 每个 任何 等词时 均为全称量词 全称变元 记作x 定义2 某个 一个 一些 等词时均可用存在性变元翻译 记为 x 凡表示确定的但目前尚未知道的或不必明白指出的个体变元称之为存在量词 2020 3 27 11 对于个体域中所有个体x其谓词F x 均为真时 可用符号 x 表示 对所有x 此时它可以表示成如上例中 当个体域为实数时下面的表示为真 即 x x 1 2 x2 2x 1 符号 x 称为全称量词 它后面紧跟着括号内的式子称作全程量词的辖域 对于个体域中个体x 存在某些个体谓词 x 为真时用符号 x 表示 存在某些x 此时表示为 x F x 如 x 6 5当个体域为实数时此时表示式为真 x x 6 5 符号 x 存在变量 同理 它后面紧跟着括号内的式子称作存在量词的辖域 2020 3 27 12 一个不确定的公式的公式只要对其所有变元均施加量词后则均为确定的了 如 x 6 5因为当x 1时它为真 T 当x 3时它为假 F 但是当使用量词后 x x 3 5 则是确定的 因为它总是为真 T 这个论点一般而言是正确的 但是它是有前提的 也就是所在确定的个体域条件下 一公式所有个体变元均施加量词后 它就是确定的了 2020 3 27 13 通过例子我们发现 1 量词所确定的公式与个体域有关 2 对不同的个体域表达式可有不同的值 也就是说 各变元的变域 个体域 须做临时约定 各变元的性质 全称或存在性 须做临时约定 因此在谓词演算中 每个个体变元的个体域必需是确定的 因此可见 量词所确定的公式与个体域有关 对不同的个体域表达式的值不同 例如 x x 6 5 中 当个体域为实数时它为T 但当个体域为自然数时它为F 2020 3 27 14 因此 在谓词演算中 每个个体变元的个体域必需是确定的 但有时为了讨论方便起见 我们干脆将谓词演算中所有个体域统一 一律用全总个体域 用了全总个体域后 对每个个体变元的变化范围用一定特性谓词去刻划 对全称量词 此特性谓词可作为蕴含前件而加入 对存在量词 此特性谓词可作为合取式的合取项加入 例如 上二式中设R x 表示x为实数 它刻划了式中个体变元的特性故是特性谓词 此时 x 1 2 x2 2x 1可写为 x R x x 1 2 x2 2x 1 而x 6 5可写为 x R x x 6 5 有了量词的概念后 谓词演算表达能力就广泛的多了 它所能刻划的语句也普遍 深入 2020 3 27 15 下面我们举例说明 例1 没有不犯错误的人解 设F x 为 x犯错误 其特性谓词为M x 表示x为人 此句可译为 x M x F x 例2 凡是实数不是大于零就是等于零或者小于零 解 我们将x大于零 x等于零 x小于零分别用 x 0 x 0 x 0 x 0 x 0 2020 3 27 16 4 3函词 函数 为了说明命题函词 函数 的概念 下面先举例解释命题与谓词的关系 例 H为谓词 能够到达山顶 L表示个体名称李四 T表示个体名称老虎 C表示个体名称汽车 那么H L H T H C 等分别表示各种不同的命题 但它们都有一个共同的形式 即H X 当X取L T C时就表示了 李四能够到达山顶 老虎能够到达到山顶 汽车能够到达山顶 2020 3 27 17 同理 若L x y 表示 x小于y 那么L 2 3 表示了一个真命题 2小于3 而L 5 1 表示一个假命题 5小于1 又如A x y z 表示一个关系 x y z 则A 3 2 5 表示了真命题 3 2 5 而A 1 2 4 表示了一个假命题 1 2 4 总之从上述三个例子可以看到H x L x y A x y z 本身不是一个命题 只有当x y z等取特定的个体时 才确定了一个命题 即给出如下定义 2020 3 27 18 定义 由一个谓词及一些个体变元组成的表达式称为命题函词 函数 根据这个定义可以看到 n元谓词是有n个个体变元函词 函数 当n 0时称为0元函词 它本身就是一个命题 记为a b c 通常称它为常量 故命题是n元谓词的一个特殊情况 由一个或n个简单函词 函数 以及逻辑联结词组合而成的表达式称为复合命题函词 函数 逻辑联结词 例如 R x 表示 x是大学生 如果x的讨论范围为某大学班级里的学生 则R x 是永真式 如果x的讨论范围为某中学班级里的学生 则R x 是永假式 2020 3 27 19 4 4自由变元与约束变元在阐述自由变元与约束变元之前首先要给出谓词演算公式的概念 定义 由命题变元和谓词填式利用真值联结词和量词如下作成的式子称为谓词演算公式 简称式 1 命题变元是公式 2 填以个体变元的谓词变元填式是公式 3 如果A是公式 则 A也是公式 4 如果A和B是公式 则 A B A B A B A B 也是公式 5 如果A是公式 x是个体变元则x A x A 也都是公式 6 公式仅限于此 2020 3 27 20 定义 那么一个公式中如果其中有一部分公式形式如 x A 或 x A 则凡在这部分中的变元x的一切出现都叫做在此公式中的约束出现 而变元x叫做此公式中的约束变元 例如 x P x F x 中的变元x的二次出现均是约束出现 2020 3 27 21 定义 一公式中如果其中有一部分公式内变元X不呈约束出现 则称X在此公式中自由出现 而此变元X称此公式的自由变元 例如 x P x y F x 中的变元y是自由出现 所以y是自由变元 每个量词都有个辖域 除原子公式外 量词的辖域既是出现在它后面的括号内的公式 2020 3 27 22 关于约束变元与自由变元我们在举一些例子 例1 x P x yR x y 此公式变元x y均为约束出现 无自由出现 例2 uP x z 此公式中变元x z为自由出现 例3 xP x Q x 此公式中变元x即约束出现 又自由出现 例子中 我们要作一些说明 我们认为在一个公式中允许一个变元即使自由出现又为约束出现 但为了避免概念上的混肴起见 我们有时住住通过改名规则 使得一个变元在一个公式中只有一中形式出现 即或者自由出现或者约束出现 这样就避免了二义性 2020 3 27 23 一个公式的约束变元的符号是无关紧要的 如公式xP x 中如将约束变元x改为y 则公式yP y 与公式xP x 具有相同的意义 所以一公式中约束变元是可以更改的 但是在更改时必须要遵守一定的规则 即约束变元的改名规则 第一 改名是对约束变元而言 不是对自由变元而言 也就是说可以对约束变施行改名 不能对自由变元施行改名 为什么呢 2020 3 27 24 我们举例说明 例如 x x y x y 该式中的约束变元X可以改名为u v w等结果为 u u y u y v v y v y w w y w y 等 显然经过改名后的这些式子与原式意义相同 都表示 任何个体都或者等于y或者不等于y 若将原式的自由变元改名为z这时所得到的式子就与原式的意义不同了 2020 3 27 25 第二 改名必须 处处 进行 处处 进行的含义是当对公式中受某个量词约束出现均改名时 必须对原式中该变元的一切受该量词约束来出现均改名 否则改名后将改变原式的约束关系 即 改变了原式的意义 例如 将x x y x y 中x的第一第二出现改为u第三出现不改则有 u u y x y 其意思是 任何个体u都或者等于y或者x不等于y 结果与原意不同 其错误的根源在于改名后结果式的约束关系不同了 2020 3 27 26 第三 对受某个量词约束的变元改名时新名决不能与该量词的作用域中的其它自由变元同名 否则改名后将改变元式的约束关系 改变了原式的意义 例如 将x x y x y 中X改名为y则有 y y y y y 其意思是 任何个体都或者与自己相等或者与自己不等 这与原意不同 2020 3 27 27 第四 对受某个量词约束的变元改名时新名能否与该量词的作用域中的约束变元同名呢 回答是有时行有时不行 这是为什么呢 我们举例说明 例如 将x x2 0 y x y z z y 该式中的约束变元x不能改名y y是作用域中的约束变元 但可改名为z z也是作用域中的约束变元 因为该公式x x2 0 y x y z z y 的意思是 对于任何个体 其平方必 0 并且对于任何新个体 原个体都于新个体相等 并且存在一个个体 它大于该新个体 而改名为y后的结果式为 y y2 0 y y y z z y 2020 3 27 28 其意思是 对于任何个体 其平方必 0 并且对于任何新个体 新个体必与自己相等并且存在一个个体 它大于该新个体 显然它们的意思不相同 从约束关系看 结果式的约束关系显然与原来的约束关系不相同 但是 z z2 0 y z y z z y 意思与原式相同 从约束关系看 结果式的约束关系与原式一样 例如 上面这个例子中 如果将原式的约束变元y改名为其它变元 如改名为t 再将约束变元x改名为y结果式为 y y2 0 t y t x z t 显然与原来的约束关系完全相同 所以说这是正确的改名 是否不改变原约束关系的改名都是正确的改名呢 确实如此 2020 3 27 29 总之改名规则用更加简单的途述为 1 改名时需要更改的变元符号范围是量词中的变元以及该量词辖域中此变元所有约束出现处 而在公式之其余部分不变 2 改名时所更改的符号一定不能出现在量词的辖域内 2020 3 27 30 接下来我们在讨论代入问题 第一 代入是对自由变元而言 也就是说对自由变元可施行代入 第二 特别注意代入是有条件的 不能盲目代入 不则将发生错误 2020 3 27 31 例如 x x y z 该公式中的自由变元y可以代以2 z y z sint等因为代入后的结果式x x 2 z x x z z x x y z z x x sint z 均是原式的特例 也就是说约束变原没有变化 所以是正确的 又例如 x x y z 由自由变元y代以x或者代以含x的式子就错了 如 自由变元y决不能代以x 假如x t sinx等等 代如后的结果式为 x x x z x x x t z x x sinx z 均不是原式的特例 也就是说这时的约束关系与原式不同 2020 3 27 32 再例如 如果一定要代以x或代以含x的项 则必须先把原式中的约束变元改名 使得与代入项无关 比如将上式改为u 而后施行代入 这时结果式为 u u x z u u x t z u u sinx z 显然这是原式的特例 约束关系与原式一致 第三 代入必须 处处 进行 所谓 处处 进行是指当对某由自由变元施行代入时 必须对该公式中该变元的一切自由出现均施行代入 否则将是错误的 2020 3 27 33 第四 为了确保对自由个体变元的正确代入 我们规定 代入前先对原式施行改名 使得原式中所有约束变元名代入式中所有变元名互不相同 然后再施行代入 第五 对于命题变元和谓词变元也可施行代入 而且代入也就是有条件的 其条件仍就是代入前后约束关系必须保持不变 下面我们举例说明对命题变元和谓词变元的代入 2020 3 27 34 例一 试在y p A y p xA x 中把p代入以 yB x y 和把p代以 xB x y 注意 yB x y xB x y 也可以写为 yBxy xBxy 解 因为对p用 yB x y 代以后约束关系不发生变化 所以可立即施行代入得y yB x y A y yB x y xA x 反之对于 yB x y 代p的情形 如盲目代入的话 约束关系就将发生变化 从而出现错误 所以必须先将原式中的约束变元y改名 使之与代入式中的变元无关 如将y改为t得t xB x y A t xA x 这个结果显然是原式的特例 故代入正确 2020 3 27 35 经过分析为了确保对命题变元的代入正确我们规定 代入前先对原式施行改名 然后施行代入 显然 按此规定施行代入 结果一定正确 而且一切正确的关与命题变元的代入均可按此规定得到 谓词变元的代入比较复杂 因为在公式中为此变元均是以谓词填式的形式出现 因此在代入前应先将代入的谓词变成相应的填式 然后在把代入好的填式代到原式中去 因此要使个代入正确 必须保证二次代入均正确 即二次代入过程中的约束关系均不应发生变化 我们举例说明这一过程 2020 3 27 36 例2 试在x x x y y x yX t y 中 把x e1 e2 代以tA e1 e2 x t 解 因为代入式tA e1 e2 x t 中x是自由变元 t是约束变元 而原式中谓词填式X x y 中x是约束变元 所以若盲目代入的话 必须发生变元混乱 产生错误 为此必须先对原式及代入式进行改名 使之相互间的变元均不同名 然后施行代入 1 先把代入式改名为uA e1 e2 x u 2 再把原式改名为z X z y Y z yX t y 3 再作关于X z y 的代入式的填式uA z y x u 4 再作关于X t y 的代入式的填式uA t y x y 5 最后将这两个填式3 4 代入到原式即可z uA z y x y Y z yuA t y x y 同理 为了确保对谓词变元的代入正确 我们仍然规定同命题变元的代入规定类同 2020 3 27 37 习题及参考答案 一 将下列句子用谓词填式表示1 1小赵是优秀学生且书是红的 解 设A表示 是优秀学生 i表示小赵 则 小赵是优秀学生 表示为A i 又若以B表示谓词 是红的 j表示书 则 书是红的 表示为B j 所以 小赵是优秀学生且书是红的 整个句子表示为A i B j 1 2张三高于李四 则张三高于王五 解 用A表示 高于 a表示 张三 b表示 李四 c表示 王五 则语句表示为A a b A a c 2020 3 27 38 二 将下列句子写成谓词公式2 1小张学习很好工作也很好 解 用S x 表示 x学习很好 W x 表示 工作很好 x表示 小张 则该语句表示为 S x W x 2 2小李学习不很好但工作很好 解 用S x 表示 x学习很好 W x 表示 工作很好 x表示 小李 则该语句表示为 S x W x 2 3小王如果学习很好工作也很好 解 用S x 表示 x学习很好 W x 表示 工作很好 x表示 小张 则该语句表示为 S x W x 2020 3 27 39 三 将下列谓词译成句子 3 1用H x y 表示 x比y长得高 设L表示李四 c表示张三 解 H l c 表示 李四不比张三长得高 H l c H c l 表示 李四不比张三长得高 且 张三与李四同样高 3 2 P x y P y z P x z 若P x y 解释为 若x小于y 当x y z都在实数域中取值 则这个式子表示为 x小于y且y小于z 则x小于z 这是永真公式 如果P x y 解释为 x为y的儿子 当x y z都指人 则 若x为y的儿子且y是z的儿子则x是z的儿子 这个公式表达的是一个永假公式 如果P x y 解释为 x距离y10米 若x y z表示地面上的房子 那么 x距离y1