离散数学]离散数学.ppt

《离散数学]离散数学.ppt》由会员分享，可在线阅读，更多相关《离散数学]离散数学.ppt（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)、N(x)、I(x)就是所谓的谓词。,推理

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

4、：表示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)称之为简单命题函数。规定：当命题函数

5、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是大学生，论域是:人类。G(x,y)：xy，论域是:实数。论域是一个集合。定义：由所有客体构成

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

7、中的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 客体函数 有些命题中，可能有若干个客体，其中有些客体之间有函数关系，例如例题1.如果x是奇数，则2x是偶数。其中客体x与客体2x之间就有函数

8、关系，可以设客体函数 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)就是客体函数，一般地用小写的英文字母f,g,h.表示客体函数。注意:客体函数与谓词是不同的，不可混淆.,要注意区分客体函数与谓词间的区别：设例题1的论域是自然数集合N。客体函数中的客体

9、变元用客体带入后的结果依然是个客体(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 原子谓词公式定义：称n元谓词P(x1,x2,.,xn)为原子谓词公式。例如 P、Q(x)、A(x,f(x)、B(x,y,a)都是原子谓词公式。,2-2.3 谓词合式公式(WFF)(Well Forme

10、d formulas)定义：谓词合式公式递归定义如下：1.原子谓词公式是合式公式。2.如果A是合式公式，则A也是合式公式。3.如果A、B是合式公式，则(AB)、(AB)、(AB)、(AB)都是合式公式。4.如果A是合式公式，x是中的任何客体变元，则x和x也是合式公式。5.只有有限次地按规则(1)至(4)求得的公式才是合式公式。谓词合式公式也叫谓词公式，简称公式。,下面都是合式公式：P、(PQ)、(Q(x)P)、x(A(x)B(x)、xC(x)而下面都不是合式公式：xyP(x)、P(x)Q(x)x为了方便，最外层括号可以省略，但是若量词后边有括号，则此括号不能省。注意：公式x(A(x)B(x)中

11、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),一般地，如果量词后边只是一个原子谓词公式时，该量词的辖域就是此原子谓词公式。如果量词后边是括号，则此括号所表示的区域就是该量词的辖域。如果多个量词紧挨着出现，则后边的量词及其辖域就是前边量词的辖域。,2-2.5 自由变元与约束变元在谓词公式中的客体变元可以分成两种

12、，一种是受到量词约束的，一种是不受量词约束的。请看下面公式：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在此辖域内是约束变元。否则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

13、(y)是一样的。这类似于计算积分与积分变元无关，即积分f(x)dx 与f(y)dy 相同。(2).一个谓词公式如果无自由变元，它就表示一个命题。例如 A(x)表示x是个大学生。xA(x)或者xA(x)就是个命题了，因为它们分别表示命题“有些人是大学生”和“所有人都是大学生”。,(3).一个n元谓词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)就变成了命题

14、“任意给定的整数x，都可以找到整数y，使得x+y=1”,。可见每当给z指定个整数a后，xyP(x,y,a)就变成了一个命题。所以谓词公式xyP(x,y,z)就相当于只含有客体变元 z的一元谓词了。,在一个谓词公式中，如果某个客体变元既以约束变元形式出现，又以自由变元形式出现，就容易产生混淆。为了避免此现象发生，可以对客体变元更改名称。如 x(F(x,y)yP(y)Q(z)约束变元的改名规则：(1).对约束变元可以更改名称，改名的范围是：量词后的指导变元以及该量词的辖域内此客体变元出现的各处同时换名。(2).改名后用的客体变元名称，不能与该量词的辖域内的其它变元名称相同。,例如x(P(x)Q(x

15、,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).如果论域是自然数集合N，令 I(x)：x是整数，则命题的表达式为 xI(x)

16、(2).如果论域扩大为全总个体域时，上述表达式xI(x)表示“所有客体都是整数”，显然这是假的命题，此表达式已经不能表达原命题了。因此需要添加谓词N(x)：x是自然数，用于表明x的特性，于是命题的符号表达式为 x(N(x)I(x),2.有些大学生吸烟。(1).如果论域是大学生集合S，令A(x)：x吸烟，则命题的表达式为 xA(x)(2).如果论域扩大为全总个体域时，上述表达式xA(x)表示“有些客体吸烟”，就不是表示此命题了，故需要添加谓词 S(x)：x是大学生，用于表明x的特性，于是命题的表达式为 x(S(x)A(x),从上述两个例子可以看出，命题的符号表达式与论域有关。当论域扩大时，需要添

17、加用来表示客体特性的谓词，称此谓词为特性谓词。特性谓词往往就是给定命题中量词后边的那个名词。如上面两个例子中的“所有自然数”、“有些大学生”。如何添加特性谓词，这是个十分重要的问题，这与前边的量词有关。特性谓词的添加方法如下：如果前边是全称量词，特性谓词后边是蕴含联结词“”；如果前边是存在量词，特性谓词后边是合取联结词“”。,为什么必须这样添加特性谓词？分析一下特性谓词和原谓词所表示的概念之间的关系，得出下面的图，从此图可以得出如此添加特性谓词的正确性。令N:自然数集合，I:整数集合，S:大学生集合，A:烟民的集合。,I包含Nx(N(x)I(x),吸烟大学生是S与A的交集 x(S(x)A(x)

18、,3.所有大学生都喜欢一些歌星。令S(x)：x是大学生，X(x)：x是歌星，L(x,y)：x喜欢y。则命题的表达式为 x(S(x)y(X(y)L(x,y)4.没有不犯错误的人。此话就是“没有人不犯错误”，“没有”就是“不存在”之意。令P(x)：x是人，F(x)：x犯错误，此命题的表达式为 x(P(x)F(x)或者 x(P(x)F(x)5.不是所有的自然数都是偶数。令N(x)：x是自然数，E(x)：x是偶数，命题的表达式为:x(N(x)E(x)或者x(N(x)E(x),6.如果一个人只是说谎话，那么他所说的每句话没有一句是可以相信的。令A(x)：x是人，B(x,y)：y是x说的话，C(x):x是

19、谎话，D(x)：x是可以相信的 命题的表达式为:x(A(x)(y(B(x,y)C(y)z(B(x,z)D(z)或者 x(A(x)y(B(x,y)C(y)D(y)7.每个自然数都有唯一的后继数。令N(x)：x是自然数，A(x,y)：y是x的后继数，E(x,y)：x=y 则命题的表达式为 x(N(x)y(N(y)A(x,y)z(N(z)A(x,z)E(y,z),有一个后继数,后继数的唯一性,下面请同学们自己做练习第60页(2),练习P60(2),a)x(J(x)L(x)b)x(L(x)S(x)c)x(J(x)O(x)V(x)d)J(j)O(j)V(j)e)x(L(x)J(x)或者 x(L(x)J(

20、x)f)x(S(x)L(x)C(x)g)x(C(x)V(x)或者 x(C(x)V(x)h)x(C(x)O(x)L(x)i)x(W(x)C(x)H(x)j)x(W(x)J(x)C(x)k)x(L(x)y(J(y)A(x,y)l)x(S(x)y(L(y)A(x,y),小结1.命题的符号表达式形式与论域有关系。论域扩大需要用特性谓词对客体进行说明.注意如何添加特性谓词(即要注意特性谓词后边是什么联结词)。2.如果量词前有否定符号，如“没有.”“不是所有的.”等，可以按照字面直译。如“x”“x.”3.命题的符号表达式中所有客体变元必须都是约束变元，才表示命题。有时给定命题中有些量词没有明确给出，要仔细

21、分析并写出这隐含的量词。例如 a)金子闪光，但闪光的不一定都是金子。G(x),F(x)x(G(x)F(x)x(F(x)G(x)b)没有大学生不懂外语。S(x),K(x,y),F(x)x(S(x)y(F(y)K(x,y),作业60页(2)62页(2),(3)b),c),(5)b)(6)65页(4)b)(5)a),2-3谓词演算的等价式与蕴涵式,在命题逻辑中，我们是通过对公式的命题变元赋值来讨论永真式、永真蕴含式及等价公式的。在谓词演算中，也要讨论一些重要的谓词公式。但是由于谓词公式中可能有命题变元、客体变元。对命题变元赋值比较容易，因为只有两个值可赋。而对客体变元作指派却不那么简单，因为论域中的

22、客体可能有无限个。另外谓词公式的真值还与论域有关。,2-3.1 对谓词公式赋值,定义：若将给定的谓词公式中的命题变元，用确定的命题代替，对公式中的客体变元用论域中的客体代替，这个过程就称之为对谓词公式作指派，或者称之 为对谓词公式赋值。例如公式 PN(x)，N(x)：x是自然数，论域为实数集合R，令P：21，x=4 时，此公式变成PN(4)，它的真值就是“真”。,2-3.2 谓词公式的永真式定义,定义：给定谓词公式A，E是其论域，如果不论对公式A作任何赋值，都使得A的真值为真，则称公式A在论域E上是永真式。如果不论对什么论域E，都使得公式A为永真式，则称A为永真式。例如，I(x)：x是整数，论

23、域E为自然数集合，公式I(x)在E上就是永真式。而公式 I(x)I(x)就是与论域无关的永真式。,2-3.3 谓词公式的等价公式定义,定义：给定谓词公式A、B，E是它们的论域，如果不论对公式A、B作任何赋值，都使得A与B的真值相同(或者说AB是永真式)，则称公式A与B在论域E上是等价的。如果不论对什么论域E，都使得公式A与B等价，则称A与B等价，记作AB。例如，I(x)：表示x是整数，N(x)：表示x是自然数，假设论域E是自然数集合，公式I(x)与N(x)在E上是等价的。而公式N(x)I(x)与N(x)I(x)就是与论域无关的等价的公式，即 N(x)I(x)N(x)I(x)。,2-3.4 谓词

24、公式的永真蕴含式定义,定义：给定谓词公式A、B，E是它们的论域，如果不论对公式A、B作任何赋值，都使得AB为永真式，则称在论域E上公式A永真蕴含B。如果不论对什么论域E，都使得公式AB为永真式，则称A永真蕴含B，记作AB。例如，G(x)：表示x大于5，N(x)：表示x是自然数，论域E=-1,-2,6,7,8,9,.，在E上公式G(x)N(x)是永真式。而公式(G(x)N(x)N(x)就是与论域无关的永真式，所以(G(x)N(x)N(x)。,2-3.5.重要公式,下面讨论重要的谓词等价公式和永真蕴含式。一.由命题公式推广出的公式因一个不含自由变元的谓词公式本身如xA(x)、xB(x)就是命题。一

25、个含有n个自由变元的谓词公式，赋予论域中的n个指定客体后就变成命题(例如S(a)、G(3,1)等)。因此可以把此公式看成一个命题变元。所以在命题演算的永真式中，将其中的同一个命题变元，用同一个谓词公式代替，所得到的公式也是永真式。这样就可以将命题演算中的等价公式和永真蕴含式推广到谓词演算中使用。例如A(x)A(x)B(x)PPQx(A(x)B(x)x(A(x)B(x)PQPQ(xA(x)xB(x)xA(x)xB(x)摩根定律,二.带量词的公式在论域内的展开式,先看一个例子，令A(x)：表示x是整数，B(x)：表示x是奇数，设论域是1,2,3,4,5，谓词公式xA(x)表示论域内所有的客体都是整

26、数，显然公式xA(x)的真值为真，因为A(1)、A(2)、A(3)、A(4)、A(5)都为真，于是有 xA(x)A(1)A(2)A(3)A(4)A(5)类似地，谓词公式xB(x)表示论域内有些客体是奇数，显然公式xB(x)的真值也为真，因为B(1)、B(3)、B(5)的真值为真，于是有 xB(x)B(1)B(2)B(3)B(4)B(5)一般地，设论域为a1,a2,.,an，则 1.xA(x)A(a1)A(a2).A(an)2.xB(x)B(a1)B(a2).B(an),三.量词否定公式,我们还是先用一个例子说明这个问题。令(x)表示x是优等生，论域是某班级的学生集合。xA(x)表示：不是所有人

27、都是优等生。xA(x)表示：有些人不是优等生。xA(x)表示：没有人是优等生。xA(x)表示：所有人都不是优等生。从这个例子可以看出“不是所有人都是优等生。”与“有些人不是优等生。”是等价的。“没有人是优等生。”与“所有人都不是优等生。”是等价的。于是有：,1.xA(x)xA(x)2.xA(x)xA(x)对这两个公式可以证明如下：证明：设论域为a1,a2,.,an，则 xA(x)(A(a1)A(a2).A(an)A(a1)A(a2).A(an)xA(x)类似可以证明另一个公式。从这两个公式，可以总结出如下规律：将量词前的“”移到量词的后边，或者将量词后的“”移到量词的前边时，量词也随着改变，如

28、果原来是全称量词改成存在量词，如果原来是存在量词改成全称量词。所以我们也把这两个公式称为量词转换公式。,四.量词辖域的扩充公式,如果是个不含客体变元x的谓词公式，且不在x和x的辖域内，可以将放入x和x的辖域内。即得如下公式：1.xA(x)Bx(A(x)B)2.xA(x)Bx(A(x)B)3.xA(x)Bx(A(x)B)4.xA(x)Bx(x)B)5.BxA(x)x(BA(x)6.BxA(x)x(BA(x)7.xA(x)Bx(A(x)B)8.xA(x)Bx(A(x)B),上述公式我们只证明三个。证明：设论域为a1,a2,.,an，xA(x)B(A(a1)A(a2).A(an)B(A(a1)B)(

29、A(a2)B).(A(an)B)x(x)BxA(x)BxA(x)x(BA(x)x(BA(x)xA(x)BxA(x)BxA(x)B x(A(x)B)x(A(x)B)在使用公式7.、8.时，要特别注意，量词的辖域扩充后，量词发生了变化。,五.量词分配公式,1.x(A(x)B(x)xA(x)xB(x)2.x(A(x)B(x)xA(x)xB(x)3.x(A(x)B(x)xA(x)xB(x)4.xA(x)xB(x)x(A(x)B(x)证明：设论域为a1,a2,.,an，x(A(x)B(x)(A(a1)B(a1)(A(a2)B(a2)(A(an)B(an)(A(a1)A(a2).A(an)(B(a1)B(

30、a2).B(an)xA(x)xB(x),注意公式3.和4.不是等价公式，而是永真蕴含式。例如公式3.由xA(x)xB(x)不能推出x(A(x)B(x)，我们可以举一个反例，设A(x)和B(x)分别表示“x是奇数”和“x是偶数”，显然命题xA(x)xB(x)为真。而x(A(x)B(x)是表示命题“存在一些数既是奇数，也是偶数”，显然不为真。所以说由xA(x)xB(x)不能推出 x(A(x)B(x).,证明公式3.x(A(x)B(x)xA(x)xB(x)证明：假设前件x(A(x)B(x)为真，则论域中至少有一个客体a，使得 A(a)B(a)为真，于是A(a)和B(a)都为 真，所以有xA(x)以及

31、xB(x)为真，进而得xA(x)xB(x)为真。于是有 x(A(x)B(x)xA(x)xB(x),下面利用公式3.证明公式4.。证明：因为公式3.中的A(x)和B(x)是任意的谓词公式，不妨用A(x)和B(x)分别代替公式3.中的A(x)和B(x)得 x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)(xA(x)xB(x)应用公式 PQQP 得 xA(x)xB(x)x(A(x)B(x)公式4.得证。在使用公式4.的时候，特别要注意蕴含式的方向，不要搞错。,六其它公式,1.x(A(x)B(x)xA(x)xB(x)2.xA(x)xB(x)x(A(x

32、)B(x)证明1.xA(x)xB(x)xA(x)xB(x)xA(x)xB(x)x(A(x)B(x)x(A(x)B(x)证明2.xA(x)xB(x)xA(x)xB(x)xA(x)xB(x)x(A(x)B(x)x(A(x)B(x),七两个量词的公式,在A(x,y)前有两个量词，如果两个量词是相同的，它们的次序是无关紧要，但是如果是不同的，它们的次序就不可以随便交换。例如设A(x,y)表示“x+y=0”,论域为：实数集合，xyA(x,y)表示“对于任意给定的一个实数x,可以找到一个y,使得x+y=0”,这是一个为“真”的命题。而交换量词后yxA(x,y)表示“存在一个实数y,与任意给定的一个实数x之

33、和都等于0”,这是一个为“假”的命题。,有如下一些公式：1.xyA(x,y)yxA(x,y)2.xyA(x,y)yxA(x,y)3.yxA(x,y)xyA(x,y)4.xyA(x,y)xyA(x,y)5.yxA(x,y)xyA(x,y)6.xyA(x,y)yxA(x,y)7.yxA(x,y)xyA(x,y)8.xyA(x,y)yxA(x,y)注意：下面式子不成立xyA(x,y)yxA(x,y),为了便于记忆，用下面图形表示上面八个公式。,实际上，根据具有传递性，还可以派生出一些公式。下面我们只证明一个等价公式。用谓词逻辑推理方法很容易证明上面那些永真蕴涵式，在此就不证明了。下面证明公式1.。证

34、明：设论域为a1,a2,.,an，则 xyA(x,y)yA(a1,y)yA(a2,y)yA(an,y)(A(a1,a1)A(a1,a2)A(a1,an)(A(a2,a1)A(a2,a2)A(a2,an)(A(an,a1)A(an,a2)A(an,an)(A(a1,a1)A(a2,a1)A(an,a1)(A(a1,a2)A(a2,a2)A(an,a2)(A(a1,an)(A(a2,an)A(an,an)xA(x,a1)xA(x,a2)xA(x,an)yxA(x,y),本节小结：熟练掌握谓词等价公式和永真蕴涵式的证明方法及应用。作业题：P66(3)b)P71(2)d),(6)面作做个练习P71(1

35、)c),练习P71(1)c).论域D=1,2 a=1 b=2 f(1)=2 f(2)=1 P(1,1)=T P(1,2)=T P(2,1)=F P(2,2)=F求xy(P(x,y)P(f(x),f(y)y(P(1,y)P(f(1),f(y)y(P(2,y)P(f(2),f(y)(P(1,1)P(f(1),f(1)(P(1,2)P(f(1),f(2)(P(2,1)P(f(2),f(1)(P(2,2)P(f(2),f(2)(P(1,1)P(2,2)(P(1,2)P(2,1)(P(2,1)P(1,2)(P(2,2)P(1,1)(T F)(T F)(F T)(F T)(F F)(T T)FT F,2-

36、4前束范式,与命题公式的范式类似，谓词公式也有规范形式。这里主要介绍前束范式-所有量词都在公式前边约束变元。1.前束范式定义：如果一个谓词公式符合下面条件，它就是前束范式：所有量词前面都没有联接词；所有量词都在公式的左面；所有量词的辖域都延伸到公式的末尾。例如 yxz(A(x)(B(x,y)C(x,y,z)x(x)B(x)就是前束范式，而 xA(x)yB(y)xy(A(x)(B(x,y)zC(z)xA(x)B(x)这三个就不是前束范式。,2.前束范式的写法给定一个带有量词的谓词公式，1)消去公式中的联接词和(为了便于量词辖域的扩充)；2)如果量词前有“”，则用量词否定公式将“”后移。再用摩根定

37、律或求公式的否定公式，将“”后移到原子谓词公式之前。3)用约束变元的改名规则或自由变元的代入规则对变元换名(为量词辖域扩充作准备)4)用量词辖域扩充公式提取量词，使之成为前束范式形式。,例1.xA(x)xB(x)xA(x)xB(x)xA(x)xB(x)xA(x)yB(y)(换元)x(A(x)yB(y)(量词辖域扩充)xy(A(x)B(y)另一个方法：xA(x)xB(x)xA(x)xB(x)xA(x)xB(x)x(A(x)B(x)(量词分配公式),例2.x(P(x)R(x)(xP(x)Q(x)x(P(x)R(x)(xP(x)Q(x)(去)x(P(x)R(x)(xP(x)Q(x)(量词转换)x(P

38、(x)R(x)(xP(x)Q(x)(后移)x(P(x)R(x)(yP(y)Q(z)(换变元)x(P(x)R(x)y(P(y)Q(z)(扩量词辖域)xy(P(x)R(x)(P(y)Q(z)(扩量词辖域)3.前束析取范式与前束合取范式：前束析取范式:前束范式中量词后的括号内是析取范式形式。前束合取范式:前束范式中量词后的括号内是合取范式形式。上例的前束析取范式为:xy(P(x)R(x)(P(y)Q(z)上例的前束合取范式为:xy(P(x)R(x)P(y)(P(x)R(x)Q(z),本节掌握前束范式的写法。作业P75(1)b)(2)c),2-5 谓词演算的推理理论,推理方法：直接推理、条件论证、反证

39、法所用公式：43页和70页的I1I19，E1E33推理规则：P、T、CP、US、ES、EG、UG后四个规则，是处理量词的，因为推理时要使用不含量词的命题公式，所以要去掉量词，如果结论有量词，还要添加量词。下面介绍四个新规则：,一.全称特指规则 US(Universal Specialization)形式：xA(x)A(c)(其中c是论域内指定客体)含义：如果xA(x)为真，则在论域内任 何指定客体c，都使得A(c)为真。作用：去掉全称量词。要求：c不是A(x)中的符号。,二.存在特指规则ES(Existential Specialization)形式：xA(x)A(c)(其中c是论域内指定客体

40、)含义：如果xA(x)为真，则在论域内指定客体c，都使得A(c)为真。作用：去掉存在量词。要求：c不是A(x)中的符号。用ES指定的客体c不应该是在此之前用US规则或者用ES规则所指定的客体c(即本次用ES特指客体c，不应该是以前特指的客体)。请看下面两个例子：,例1.令A(x)表示x是自然数，B(x)表示x是整数。x(A(x)B(x)P A(c)B(c)US 如c=0.1 xA(x)P A(c)ES A(0.1)为F xB(x)P B(c)ES 如c=-1 xA(x)P A(c)ES A(-1)为F,三.存在推广规则 EG(Existential Generalization)形式：A(c)

41、xA(x)(其中c是论域内指定客体)含义：如果在论域内指定客体c使得 A(c)为真，则xA(x)为真。作用：添加存在量词。要求：x不是A(c)中的符号。,四.全称推广规则UG(Universal Generalization)形式：A(c)xA(x)(其中c是论域内任何指定客体)含义：如果在论域内任何指定客体c都使 得A(c)为真，则xA(x)为真。作用：添加全称量词。要求：x不是A(c)中的符号。c一定是任意的客体，否则不可全 称推广。,例1 所有金属都导电。铜是金属。故铜导电。令 M(x):x是金属。C(x):x导电。a:铜。符号化为：x(M(x)C(x),M(a)C(a)x(M(x)C(

42、x)P M(a)C(a)US M(a)P C(a)T I11,例2.所有自然数都是整数。有些数是自然数。因此有些数是整数。令A(x)表示x是自然数，B(x)表示x是整数。x(A(x)B(x)，xA(x)xB(x)xA(x)P A(c)ES x(A(x)B(x)P A(c)B(c)US B(C)T I11 xB(x)EG,例2中，如果按下面方法推理，是否正确？x(A(x)B(x)，xA(x)xB(x)x(A(x)B(x)P A(c)B(c)US xA(x)P A(c)ES B(C)T I11 xB(x)EG 问题在哪里？,例3 不认识错误的人，也不能改正错误。有些诚实的人改正了错误。所以有些诚实

43、的人是认识了错误的人。设A(x):x是认识错误的人。B(x):x改正了错误。C(x):x是诚实的人。符号化为：x(A(x)B(x)，x(C(x)B(x),x(C(x)A(x),x(A(x)B(x)，x(C(x)B(x),x(C(x)A(x)x(C(x)B(x)P C(c)B(c)ES C(c)T I1 B(c)T I2 x(A(x)B(x)P A(c)B(c)US A(c)T I12 A(c)T E1 C(c)A(c)T I9 x(C(x)A(x)EG,例4 一些病人喜欢所有医生。任何病人都不喜欢庸医。所以没有医生是庸医。设:P(x):x是病人,D(x):x是医生,Q(x):x是庸医,L(x,

44、y):x喜欢y.符号化为：x(P(x)y(D(y)L(x,y)，x(P(x)y(Q(y)L(x,y)y(D(y)Q(y),x(P(x)y(D(y)L(x,y)，x(P(x)y(Q(y)L(x,y)y(D(y)Q(y)x(P(x)y(D(y)L(x,y)P P(a)y(D(y)L(a,y)ES P(a)T I1 y(D(y)L(a,y)T I2 x(P(x)y(Q(y)L(x,y)P P(a)y(Q(y)L(a,y)US y(Q(y)L(a,y)T I11 D(b)L(a,b)US Q(b)L(a,b)US L(a,b)Q(b)T E18 D(b)Q(b)T I13 D(b)Q(b)T E16(

45、D(b)Q(b)T E8 y(D(y)Q(y)UG y(D(y)Q(y)T E25,课堂练习P79(1)d)改成：x(A(x)B(x),x(B(x)C(x),xC(x)x(A(x)(1)x(A(x)B(x)P(2)A(a)B(a)ES(1)(3)x(B(x)C(x)P(4)B(a)C(a)US(3)(5)xC(x)P(6)C(a)US(5)(7)B(a)T(4)(6)I12(8)A(a)T(2)(7)I10(9)x(A(x)EG(8),例5 x(P(x)Q(x)xP(x)xQ(x)用条件论证证明：xP(x)P(附加前提)x(P(x)Q(x)P P(a)Q(a)ES P(a)US Q(a)T I

46、11 xQ(x)EG xP(x)xQ(x)CP,用反证法证明例5：x(P(x)Q(x)xP(x)xQ(x)(xP(x)xQ(x)P(假设前提)(xP(x)xQ(x)T E16 xP(x)xQ(x)T E9 xP(x)T I1 xQ(x)T I2 x(P(x)Q(x)P P(a)Q(a)ES P(a)US Q(a)T I11 xQ(x)EG xQ(x)xQ(x)T I9,用推理证明公式：yxA(x,y)xyA(x,y)yxA(x,y)P xA(x,b)ES A(a,b)US yA(a,y)EG xyA(x,y)UG 作业：79页 c)d)、推理时的注意事项：,推理时注意事项：,1.注意使用ES、

47、US、EG、UG的限制条件。2.对于同一个客体变元，既有带也有带的前提，去量词时，应先去后去，这样才可以特指同一个客体 c.3.去量词时，该量词必须是公式的最左边的量词，且此量词的前边无任何符号，它的辖域作用到公式末尾。下面的作法是错误的：正确作法是：xP(x)yQ(y)P xP(x)yQ(y)P xP(x)Q(b)ES(2)xP(x)yQ(y)T(1)E(3)P(a)Q(b)US(2)(3)xP(x)yQ(y)T(2)E(4)xy(P(x)Q(y)T(3)E(5)y(P(a)Q(y)ES(4)实际上x的辖域扩(6)P(a)Q(b)ES(4)充后量词改成为x(7)P(a)Q(b)T(5)E,下

48、面的作法是错误的：正确作法是：xP(x)P xP(x)P P(c)US(2)xP(x)T(1)E 实际上中不是x而是x(3)P(c)ES(2)xyP(x,y)P xyP(x,y)P xP(x,c)ES(2)yP(a,y)US(1)令P(x,y):y是x的生母，显然是个假命题.另外X是公式A的子公式，且XY,如果用Y替换A中X而得到B，那么不一定有AB。例如PQP,而(PQ)P是不成立的。US和ES规则都是蕴涵式，所以不可对一个子公式用这些规则。4.添加量词时，也要加在公式的最左边，(即新加的量词前也无任何符号！)且其辖域作用到公式的末尾。,第二章 小结,本章重点掌握内容：1.各基本概念清楚。2

49、.会命题符号化。3.熟练掌握等价公式和永真蕴涵式。4.会写前束范式。5.熟练掌握谓词逻辑的三种推理方法。,第二章 习题课,一.命题符号化 60页(2)a)x(J(x)L(x)b)x(L(x)S(x)c)x(J(x)O(x)V(x)d)J(j)O(j)V(j)e)x(L(x)J(x)或者 x(L(x)J(x)f)x(S(x)L(x)C(x)g)x(C(x)V(x)或者 x(C(x)V(x)h)x(C(x)O(x)L(x)i)x(W(x)C(x)H(x)j)x(W(x)J(x)C(x)k)x(L(x)y(J(y)A(x,y)l)x(S(x)y(L(y)A(x,y),62页(2)xy(P(x)P(y

50、)E(x,y)z(L(z)R(x,y,z)t(L(t)R(x,y,t)E(t,z)(3)b)设R(x):x是实数，G(x,y):xy x(R(x)y(R(y)G(y,x)c)设R(x):x是实数，G(x,y):xy f(x,y)=x+y g(x,y)=xy xyz(R(x)R(y)R(z)G(f(x,y),g(x,z)或者 xyz(R(x)R(y)R(z)G(x+y,xz)(5)b)设N(x):x是数，A(x,y):y是x的后继数 x(N(x)A(x,1)(6)设A(x):x是戴眼镜的,B(x):x是用功的,C(x):x是大学生,D(x):x是大的,E(x):x是厚的，F(x):x是巨著,A(