《[离散数学]离散数学2》由会员分享,可在线阅读,更多相关《[离散数学]离散数学2(99页珍藏版)》请在金锄头文库上搜索。
1、 第二章 谓词逻辑问题的提出:(即命题逻辑的局限性)在第一章, 一个原子命题只用一个字母表示, 而不再对命题中的句子成分细分。这样有一些逻 辑问题无法解决。请看下面的例子。 例1.令:小张是大学生。:小李是大学生。 从符号、中不能归纳出他们都是大学生的共 性。我们希望从所使用的符号那里带给我们更多 的信息,比如可以看出他们的共性。这种想法在 第一章是无法实现的。例2.令 :所有自然数都是整数。:是自然数。:是整数。这是著名的三段论推理,A是大前提,B是小前提 , C是结论。显然,由和可以推出结论。这 个推理是有效的,但是这个推理在第一章也是无 法实现的。 分析:命题与中的谓语是相同的(是大学生
2、), 只是主语不同。命题、之间在主语谓语 方面也是有联系的,靠这种联系才能由、推 出。而从这三个符号上看不出此种联系。所以就要另外考虑表示命题的方法。解决这个问题的方法: 在表示命题时,既表示出主语,也表示出谓语, 就可以解决上述问题。这就提出了谓词的概念。 令S(x)表示x是大学生,a:小张,b:小李命题P表示成S(a):小张是大学生。命题Q表示成S(b):小李是大学生。 从符号S(a)、S(b)可看出小张和小李都是大学生的共性. 令N(x):x是自然数。I(x):x是整数。表示所有的。A: x(N(x)I(x)B :N(8) C :I(8)N(8)I(8) N(8) I(8)符号 S(x)
3、、N(x)、I(x)就是所谓的谓词。推理如此实现:2-1 基本概念2-1.1 客体与客体变元 定义:能够独立存在的事物,称之为客体,也 称之为个体。它可以是具体的,也可以是抽象的 事物。通常用小写英文字母a、b、c、.表示。 例如,小张、小李、8、a、沈阳、社会主义等等 都是客体。 定义:用小写英文字母x、y、z.表示任何客 体,则称这些字母为客体变元。 注意:客体变元本身不是客体。2-1.2 谓词 定义:一个大写英文字母后边有括号,括号内 是若干个客体变元,用以表示客体的属性或者 客体之间的关系,称之为谓词。如果括号内有 n个客体变元,称该谓词为n元谓词。 例如 S(x):表示x是大学生。
4、一元谓词G(x,y):表示 xy。 二元谓词B(x,y,z):表示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)相当于一个函数, 称之为命题函数。
5、定义:n元谓词P(x1,x2,xn)称之为简单命题函数 。 规定:当命题函数P(x1,x2,xn)中 n=0 时,即0 元谓词,表示不含有客体变元的谓词,它本身就是 一个命题变元。 定义:将若干个简单命题函数用逻辑联结词联结起 来,构成的表达式,称之为复合命题函数。简单命 题函数与复合命题函数统称为命题函数。 例如 给定简单命题函数:A(x):x身体好,B(x):x学习好,C(x):x工作好, 复合命题函数 A(x)(B(x)C(x)表示如果x身体不好,则x的学习与工作 都不会好。2-1.4 论域(个体域) 定义:在命题函数中命题变元的取值范 围,称之为论域,也称之为个体域。例如 S(x):x
6、是大学生,论域是:人类。G(x,y):xy, 论域是:实数。论域是一个集合。 定义:由所有客体构成的论域,称之为 全总个体域。它是个“最大”的论域。 约定:对于一个命题函数,如果没有给定 论域,则假定该论域是全总个体域。2-1.5 量词 例如:有些人是大学生。所有事物都是发展变化的。 “有些”,“所有的”,就是对客体量化的词。 定义:在命题中表示对客体数量化的词,称之 为量词。 定义了两种量词:(1).存在量词:记作,表示“有些”、“一些 ”、 “某些”、“至少一个”等。(2).全称量词:记作,表示“每个”、“任 何 一个”、“一切”、“所有的”、“凡是”、“ 任意 的”等。 定义:量词后边要
7、有一个客体变元,指明对哪 个客体变元量化,称此客体变元是量词后的指 导变元。 例如 x(读作“任意x”),x(读作“存在x”) ,其中的x就是量词后的指导变元。 例题.所有的自然数都是整数。设 N(x):x是自然数。I(x):x是整数。此命 题可以写成 x(N(x)I(x) 例题.有些自然数是偶数。设 E(x):x是偶数。此命题可以写成 x(N(x)E(x) 例题3. 每个人都有一个生母。设 P(x):x是个人。M(x,y):y是x的生母 。此命题可以写成x(P(x)y(P(y)M(x,y)2-2 谓词公式及命题符号化命题逻辑中有命题公式,类似地,在谓词逻辑 中,要研究谓词公式。 2-2.1
8、客体函数有些命题中,可能有若干个客体,其中有些客体 之间有函数关系,例如 例题1. 如果x是奇数,则2x是偶数。 其中客体x与客体2x之间就有函数关系,可以设 客体函数 g(x)=2x, 谓词 O(x):x是奇数, E(x):x是偶数, 则此命题可以表示为: 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 ,此命题可以表示为:xy(O(x)O(y)E(h(x,y) 像上述的g(x)、f(x)、h(x,y)就是客体函 数,一
9、般地用小写的英文字母f,g,h.表 示客体函数。 注意:客体函数与谓词是不同的,不可混 淆.要注意区分客体函数与谓词间的区别: 设例题1的论域是自然数集合N。 客体函数中的客体变元用客体带入后的结果依 然是个客体(3N,g(3)=6,所以g(3)N)。 谓词中的客体变元用确定的客体带入后就变成 了命题,其真值为或者为(3N, O()是 个命题,真值为T)。 把它们都看成“映射”的话,则客体函数是论域到论域的映射,g:NN,如果 指定的客体aN,则g(a)N。而谓词是从论域到T,F的映射,即谓词E(x)可 以看成映射E:NT,F,如果指定客体aN,则 E(a)的真值T,F。2-2.2 原子谓词公
10、式 定义:称n元谓词P(x1,x2,.,xn)为原子 谓词公式。 例如 P、Q(x) 、 A(x,f(x)、B(x,y,a) 都是原子谓词公式。2-2.3 谓词合式公式(WFF)(Well Formed formulas) 定义:谓词合式公式递归定义如下:1.原子谓词公式是合式公式。2.如果A是合式公式,则A也是合式公式。3.如果A、B是合式公式,则(AB)、(AB)、 (AB)、(AB)都是合式公式。4.如果A是合式公式,x是中的任何客体变元 ,则x和x也是合式公式。5.只有有限次地按规则(1)至(4)求得的公式才 是合式公式。 谓词合式公式也叫谓词公式,简称公式。 下面都是合式公式:P、(
11、PQ)、(Q(x)P)、 x(A(x)B(x)、xC(x) 而下面都不是合式公式:xyP(x) 、P(x)Q(x)x 为了方便,最外层括号可以省略,但是 若量词后边有括号,则此括号不能省。 注意:公式x(A(x)B(x)中x后边的 括号不是最外层括号,所以不可以省略 。2-2.4 量词的作用域(辖域) 定义:在谓词公式中,量词的作用范围称之为 量词的作用域,也叫量词的辖域。 例如 xA(x)中x的辖域为A(x). x(P(x)Q(x)yR(x,y)中 x的辖域是(P(x)Q(x)yR(x,y)y的辖域为R(x,y)。 xyz(A(x,y)B(x,y,z)C(t) x的辖域z的辖域 y的辖域一般
12、地, 如果量词后边只是一个原子谓词公式时 ,该量词的辖域就是此原子谓词公式。 如果量词后边是括号,则此括号所表示 的区域就是该量词的辖域。 如果多个量词紧挨着出现,则后边的量 词及其辖域就是前边量词的辖域。2-2.5 自由变元与约束变元 在谓词公式中的客体变元可以分成两种 , 一种是受到量词约束的,一种是不受量词 约束的。请看下面公式: x(F(x,y)yP(y)Q(z)(x,y)中的x在x的辖域内,受到x的 约束,而其中的y不受x的约束。P(y)中的y在y的辖域内,受y的约束。Q(z)中的z不受量词约束。 定义:如果客体变元x在x或者x的辖域 内,则称x在此辖域内约束出现,并称x 在此辖域内
13、是约束变元。否则x是自由出 现,并称x是自由变元。 上例中x(F(x,y)yP(y)Q(z)F(x,y)中的x和P(y)中的y是约束变元。 而F(x,y)中的y和Q(z)中的z是自由变元。 对约束变元和自由变元有如下几点说明 : (1).对约束变元用什么符号表示无关紧要 。就是说xA(x)与yA(y)是一样的。这 类似于计算积分与积分变元无关,即积 分f(x)dx 与f(y)dy 相同。 (2).一个谓词公式如果无自由变元,它就 表示一个命题。例如 A(x)表示x是个大学生。xA(x)或 者xA(x)就是个命题了,因为它们分别 表示命题“有些人是大学生”和“所有 人都是大学生”。(3).一个n
14、元谓词P(x1,x2,xn),若在前边添加 k个量词,使其中的 k个客体变元变成约束变 元,则此 n元谓词就变成了n-k元谓词。 例如P(x,y,z)表示x+y=z,假设论域是整数集 。xyP(x,y,z)表示“任意给定的整数x,都 可以找到整数y,使得x+y=z” 。 如果令 z=1,则xyP(x,y,1)就变成了命题“ 任意给定的整数x,都可以找到整数y,使得 x+y=1”,。 可见每当给z指定个整数a后,xyP(x,y,a)就 变成了一个命题。所以谓词公式xyP(x,y,z) 就相当于只含有客体变元 z的一元谓词了。 在一个谓词公式中,如果某个客体变元 既以约束变元形式出现,又以自由变元
15、 形式出现,就容易产生混淆。为了避免 此现象发生,可以对客体变元更改名称 。如 x(F(x,y)yP(y)Q(z) 约束变元的改名规则: (1).对约束变元可以更改名称,改名的范 围是:量词后的指导变元以及该量词的 辖域内此客体变元出现的各处同时换名 。 (2).改名后用的客体变元名称,不能与该 量词的辖域内的其它变元名称相同。 例如x(P(x)Q(x,y)(R(x)A(x) 此式中的x 就是以两种形式出现。可以对x改名成z(P(z)Q(z,y)(R(x)A(x) 对自由变元也可以换名字,此换名叫代入。 对自由变元的代入规则: (1).对谓词公式中的自由变元可以作代入。代入 时需要对公式中出现该变元的每一处,同时作代 入。 (2).代入后的变元名称要与公式中的其它变元名 称不同 上例也可以对自由变元x作代入,改成x(P(x)Q(x,y)(R(z)A(z) 2-2.6 命题的符号化 在谓词演算中,命题的符号化比较复杂,命题的 符号表达式与论域有关系。例如 1.每个自然数都是整数。(1).如果论域是自