离散数学-谓词逻辑

《离散数学-谓词逻辑》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章谓词逻辑2-1.1客体与客体变元•定义：能够独立存在的事物，称之为客体，也称之为个体。它可以是具体的，也以是抽象的事物。通常用小写英文字母a、b、c、...表示。例如，小张、小李、8、a、沈阳、社会主义等等都是客体。•定义：用小写英文字母x、y、z...表示任何客体，则称这些字母为客体变元。注意：客体变元本身不是客体2-1.2谓词•定义：一个大写英文字母后边有括号，括号内是若干个客体变元，用以表示客体的属性或者客体之间的关系，称之为谓词。如果括号内有n个客体变元，称该谓词为n元谓词。例如：S(x):表示x是大学生。一元谓词G(x,y)：表示x>y。二元谓词B(x,y,z)

2、：表示x在y与z之间。三元谓词一般地P(x1,x2,…,xn)是n元谓词。2-1.3命题函数•谓词本身并不是命题，只有谓词的括号内填入足够的客体，才变成命题。•例如，a表示小张，b表示小李，则S(a):小张是大学生。S(b):小李是大学生。Ｇ(7,3)表示:７>３。如果c表示锦州，d表示沈阳，e表示山海关，则B(c,d,e)表示：锦州在沈阳与山海关之间。这时S(a)、S(b)、G(7,3)、B(c,d,e)才是命题令谓词S(x):x是大学生，括号内填入不同的人名，就得到不同的命题，故谓词S(x)相当于一个函数，称之为命题函数。定义：n元谓词P(x1,x2,…,xn)称之为简单命

3、题函数。规定：当命题函数P(x1,x2,…,xn)中n=0时，即0元谓词，表示不含有客体变元的谓词，它本身就是一个命题变元。定义：将若干个简单命题函数用逻辑联结词联结起来，构成的表达式，称之为复合命题函数。简单命题函数与复合命题函数统称为命题函数。Eg：给定简单命题函数：A(x)：x身体好，B(x)：x学习好，C(x)：x工作好，复合命题函数A(x)→(B(x)∧C(x))表示：如果x身体不好，则x的学习与工作都不好。2-1.4论域(个体域)定义：在命题函数中客体变元的取值范围，称为论域，也称为个体域。例如S(x):x是大学生，论域是:人类。G(x,y)：x>y，论域是:

4、实数。论域是一个集合。1定义：由所有客体构成的论域，称之为全总个体域。它是个“最大”的论域。约定:对于一个命题函数，如果没有给定论域，则假定该论域是全总个体域。2-1.5量词例如：有些人是大学生。所有事物都是发展变化的。“有些”,“所有的”,就是对客体量化的词。定义：在命题中表示对客体数量化的词，称之为量词。•定义了两种量词：(1).存在量词：记作，表示“有些”、“一些”、“某些”、“至少一个”等。(2).全称量词：记作，表示“每个”、“任何一个”、“一切”、“所有的”、“凡是”、“任意的等。量词后的指导变元：量词后边要有一个客体变元，用以指明对哪个客体变元量化，称此客体变

5、元是量词后的指导变元。例如,x(读作“任意x”)，x(读作“存在x”)，其中的x就是量词后的指导变元。例题１.所有的自然数都是整数。设N(x)：x是自然数。I(x)：x是整数。此命题可以写成x(N(x)→I(x))例题２.有些自然数是偶数。设N(x)：x是自然数,E(x)：x是偶数。此命题可以写成x(N(x)∧E(x))2-2谓词公式及命题符号化2-2.1客体函数有些命题中，可能有若干个客体，其中有些客体之间有函数关系，例如例题1.如果x是奇数，则2x是偶数。其中客体x与客体2x之间就有函数关系，可以设客体函数g(x)=2x，谓词O(x)：x是奇数，E(x)：x是偶数，

6、则此命题可以表示为：x(O(x)→E(g(x)))例题2小王的父亲是个医生。设函数f(x)=x的父亲，谓词D(x):x是个医生,a:小王，此命题可以表示为D(f(a)).例题3如果x和y都是奇数，则x+y是偶数。设h(x,y)=x+y,谓词O(x):x是奇数,E(x):x是偶数，此命题可以表示为:xy((O(x)∧O(y))→E(h(x,y))•像上述的g(x)、f(x)、h(x,y)就是客体函数，一般地用小写的英文字母f,g,h….表示客体函数。注意:客体函数与谓词是不同的，不可混淆。要注意区分客体函数与谓词间的区别：•设例题1的论域是自然数集合N.(例题1.如果x是奇

7、数,则2x是偶数.客体函数g(x)=2x,谓词O(x):x是奇数,E(x):x是偶数)•客体函数中的客体变元用客体带入后的结果依然是个客体(3∈N,g(3)=6，所以g(3)∈N)。•谓词中的客体变元用确定的客体带入后就变成了命题，其真值为Ｔ或者为Ｆ.(3∈N,O(3)是个命题,真值为T)•把它们都看成“映射”的话，则:客体函数是论域到论域的映射，g:N→N，如果指定的客体a∈N，则g(a)∈N。谓词是从论域到{T,F}的映射，即谓词E(x)可以看成映射E:N→{T,F}，如果指定客体a∈N