离散数学讲义(第2章)

《离散数学讲义(第2章)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、天津财经大学信息科学与技术系王宁ninglw@163.comDiscreteMathematics离散数学讲义（电子版）1第二章谓词逻辑2第二章谓词逻辑谓词演算(一阶谓词演算）是命题演算的扩充和发展,其本质同命题演算，是把数学中的逻辑论证加以符号化，可以刻划命题内部的逻辑结构。从而推动了这个数学分支的发展。苏格拉底（Socrates）三段论：.所有的人都是要死的。.苏格拉底是人。.所以苏格拉底是要死的。3本章包括以下内容：2-1谓词的概念与表示2-2命题函数与量词2-3谓词公式与翻译2-4变元的约束2-5谓词演算的等价式与蕴含式2-6前

2、束范式2-7谓词演算的推理理论第二章谓词逻辑4在谓词演算中，将原子命题分解为谓词和客体两部分。客体：可以独立存在的东西,它可以是一个具体的事物，也可以是一个抽象的概念。主语一般为客体。2-1谓词的概念与表示例如：谓词指明客体性质谓词指明客体间关系谓词：用于刻划客体的性质或客体与客体之间的关系。(a)他是三好学生。(b)7是质数。(c)每天早晨做广播操是好习惯。(d)5大于3。(e)哥白尼指出地球绕着太阳转。5记号：例如：2-1谓词的概念与表示（续）大写字母：表示谓词。小写字母：表示客体（个体）。（1）用A表示“是个大学生”，c表示“张三

3、”，d表示“李四”，则：A(c)：张三是个大学生。A(d)：李四是个大学生。（2）用B表示“大于”，e代表“5”，f代表“3”，则：B(e,f)：5大于3。（3）用L表示“…在…和…之间”，a表示“点a”，b表示“点b”，c表示“点c”，则：L(a,b,c)表示“a在b和c之间”。6记号：一元谓词：A(b)。二元谓词：B(a，b)。三元谓词：L(a，b，c)。……n元谓词：A(c1，c2，…，cn)。代表客体名称的字母，它在多元谓词表示式中出现的次序与事先约定有关。2-1谓词的概念与表示（续）72-1谓词的概念与表示（续）通常，一元谓词

4、表达了客体的“性质”，多元谓词表达了客体之间的“关系”。定义：单独一个谓词不是完整的命题，把谓词字母后填以客体所得的式子称为谓词填式。谓词和谓词填式是两个不同的概念。82-2命题函数与量词例：H：“能够到达山顶”，l：“李四”，t：“老虎”，c：“汽车”。则H(x)当x分别取l，t，c时表示“李四能够到达山顶”，“老虎能够到达山顶”，“汽车能够到达山顶”。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)表

5、示“1加2等于4”。9定义：由一个谓词和一些客体变元所组成的表达式称为简单命题函数。2-2命题函数与量词（续）例如：对于谓词P，P(x)是变元x的函数。N元谓词是有n个客体变元的命题函数，n=0时，称为0元谓词，其本身是一个命题。定义：由一个或多个简单命题函数以及逻辑联结词组合而成的表达式称为复合命题函数。102-2命题函数与量词（续）例1：设S(x)：“x学习很好”，W(x)：“x工作很好”，例2：H(x,y)：“x比y长得高”，l：“李四”，c：“张三”则S(x)：“x学习不是很好”；S(x)W(x)：“x学习工作都很好”；则

6、H(l,c)：“李四不比张三长得高”；H(l,c)H(c,l)：“李四不比张三长得高且张三不比李四长得高”，即“李四与张三一样高”。112-2命题函数与量词（续）注：例3：Q(x,y)：“x比y重”当x，y指人或物时，它是一个命题，若x，y为实数时，Q(x,y)不是命题。（1）命题函数不是命题，只有客体变元取特定名称时才能成为一个命题。（2）客体变元在哪些范围内取特定的值对是否成为命题及命题的真值有影响。122-2命题函数与量词（续）例4：R(x)：“x是大学生”，考虑x的讨论范围：例5：(P(x,y)P(y,z))P(x,z

7、)。考虑P(x,y)的解释：（1）某大学里班级中的学生，则R(x)永真。（2）某中学里班级中的学生，则R(x)永假。（3）某剧场中的观众，则R(x)对某些观众为真，对某些为假。（1）“x小于y”，则P(x,y)永真。（2）“x为y的儿子”，则P(x,y)永假。（3）“x距离y10米”，则P(x,y)可能为真或假。13个体变元：函数P(x)中的x。2-2命题函数与量词（续）说明：逻辑联结词的意义与命题演算中的解释相同。个体域（论域）：个体变元的取值（论述）范围。全总个体域：各种个体域综合在一起作为论述范围的域。14量词：2-2命

8、题函数与量词（续）注意：每个由量词确定的表达式都与个体域有关，因此在讨论带有量词的命题函数时，必须确定其个体域。全称量词：“”——表示“对所有的”，“对每一个”，“对任意一个”，等等。存在量词：“”——