《离散数学第四章》由会员分享，可在线阅读，更多相关《离散数学第四章（48页珍藏版）》请在金锄头文库上搜索。
1、2018/9/18,曲阜师范大学计算机科学学院,1,离散数学,数理逻辑,2018/9/18,曲阜师范大学计算机科学学院,2,命题逻辑的局限,命题逻辑的特点：在命题逻辑中，基本组成单位是原子命题，并把它看作不可再分解的，而不涉及其内部的逻辑结构。命题逻辑的缺点： （1） 它不能揭示某些有效的论证； （2） 无法将具有某种共同属性的命题显示出来。,2018/9/18,曲阜师范大学计算机科学学院,3,命题逻辑的局限,（1） 它不能揭示某些有效的论证；【例】所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。 这是简单而有名的苏格拉底三段论，直观地，这是一个有效的论证，但它却无法用命题逻辑予以推证
2、。（2）无法将具有某种共同属性的命题显示出来。【例】设 P 表示命题：张辉是工人Q 表示命题：李明是工人仅仅从命题符号 P 和 Q 看不出张辉和李明都是工人这一特性。,2018/9/18,曲阜师范大学计算机科学学院,4,一阶逻辑命题符号化 个体词、谓词、量词 一阶逻辑命题符号化 一阶逻辑公式及其解释 一阶语言 合式公式 合式公式的解释 永真式、矛盾式、可满足式,第四章 一阶逻辑基本概念,2018/9/18,曲阜师范大学计算机科学学院,5,4.1 一阶逻辑命题符号化,个体词所研究对象中可以独立存在的具体或抽象的客体 个体常项：具体的事务，用a, b, c表示 个体变项：抽象的事物，用x, y,
3、z表示 个体域(论域)个体变项的取值范围有限个体域，如 a, b, c, 1, 2无限个体域，如 N, Z, R, 全总个体域由宇宙间一切事物组成,2018/9/18,曲阜师范大学计算机科学学院,6,谓词,谓词表示个体词性质或相互之间关系的词 谓词常项 如, F(a)：a是人 谓词变项 如, F(x)：x具有性质F n（n1）元谓词 一元谓词(n=1)表示性质 多元谓词(n2)表示事物之间的关系如, L(x,y)：x与 y 有关系 L，L(x,y)：xy，0元谓词不含个体变项的谓词, 即命题常项或命题变项,2018/9/18,曲阜师范大学计算机科学学院,7,例1 用0元谓词将命题符号化(1)
4、墨西哥位于南美洲(2) 是无理数仅当 是有理数(3) 如果23，则33，q：3y，G(x, y)：xy,x(F(x)y(G(y)L(x,y) 或者 xy(F(x)G(y)L(x,y),(2) 令F(x)：x是无理数，G(y)：y是有理数，L(x,y)：xy,x(F(x)y(G(y)L(x,y) 或者 xy(F(x)G(y)L(x,y),2018/9/18,曲阜师范大学计算机科学学院,21,实例7,例7 在一阶逻辑中将下面命题符号化(1) 没有不呼吸的人(2) 不是所有的人都喜欢吃糖,解 (1) F(x): x是人, G(x): x呼吸,x(F(x)G(x),x(F(x)G(x),(2) F(x
5、): x是人, G(x): x喜欢吃糖,x(F(x)G(x),x(F(x)G(x),2018/9/18,曲阜师范大学计算机科学学院,22,实例8,例8 设个体域为实数域, 将下面命题符号化(1) 对每一个数x都存在一个数y使得xy(2) 存在一个数x使得对每一个数y都有xy,解 L(x,y):xy,(1) xyL(x,y),注意: 与不能随意交换 显然(1)是真命题, (2)是假命题,(2) xyL(x,y),2018/9/18,曲阜师范大学计算机科学学院,23,例9 设 A (x,y) 表示 x 和 y 同姓，x 的个体域是甲村村民，y 的个体域是乙村村民， 则：（1） (x)(y)A(x,
6、y)表示命题：甲村所有的村民和乙村所有的村民都同姓；（2） (y)(x)A(x,y)表示命题：乙村所有的村民和甲村所有的村民都同姓；（3） (x)(y)A(x,y)表示命题：对甲村的任何一个村民都有乙村的村民和他同姓；（4） (y)(x)A(x,y)表示命题：乙村有村民和甲村的所有村民都同姓；,实例9,2018/9/18,曲阜师范大学计算机科学学院,24,例9 设 A (x,y) 表示 x 和 y 同姓，x 的个体域是甲村村民，y 的个体域是乙村村民，则：（5） (x)(y)A(x,y)表示命题：甲村与乙村有人同姓；（6）(y)(x)A(x,y)表示命题：乙村与甲村有人同姓；（7）(y)(x)
7、A(x,y)表示命题：对于乙村的所有人，甲村都有人与他同姓；（8）(x)(y)A(x,y) 表示命题：甲村有人和乙村的所有人同姓。,实例9,2018/9/18,曲阜师范大学计算机科学学院,25,*说明： （1）分析命题中表示性质和关系的谓词，要分别符号化为一元和n(n 2)元谓词。 （2）根据命题的实际意义选用 或 。 （3）一般来说，当多个量词同时出现时，它们的顺序不能随意调换。 （4）有些命题的符号化形式不止一种。,2018/9/18,曲阜师范大学计算机科学学院,26,量词顺序不可随意更换。如：,在实数域上用L(x,y)表示x+y=10命题为：对于任意的x,都存在y使得x+y=10。可符号
8、化为： xyL(x,y) 真值为1。若调换顺序后为： yxL(x,y) 真值为0。,2018/9/18,曲阜师范大学计算机科学学院,27,至此，下列推理即可解决： 【例】所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。,设：M(x):x是人。D(x):x 是要死的。a:苏格拉底。则符号化为：x(M(x)D(x) M(a) D(a),2018/9/18,曲阜师范大学计算机科学学院,28,4.2 一阶逻辑公式及解释,定义4.1 设L是一个非逻辑符号集合, 由L生成的一阶语言L 的字母表包括下述符号： 非逻辑符号(1) 个体常项符号：a, b, c, , ai, bi, ci, , i 1(2) 函数符号：f, g, h, , fi, gi, hi, , i 1(3) 谓词符号：F, G, H, , Fi, Gi, Hi, , i 1 逻辑符号 (4) 个体变项符号：x, y, z, , xi, yi, zi, , i 1 (5) 量词符号：, (6) 联结词符号：, , , , (7) 括号与逗号：(, ), ，,
