《《谓词逻辑集合》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《谓词逻辑集合》PPT课件.ppt（53页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第2 2章章 谓词演算及其形式系统谓词演算及其形式系统 在研究命题逻辑中，原子命题是命题演算中最基本的单位，但是不再对原子命题进行分解，会产生二大缺点：（1）不能研究命题的结构，成分和内部逻辑的特征；（2）也不可能表达二个原子命题所具有的共同特征，甚至在命题逻辑中无法推理一些简单又常见的结论。谓词演算及其形式系统例：苏格拉底论证是正确的，但不能用命题逻辑的例：苏格拉底论证是正确的，但不能用命题逻辑的推理规则推导出来。推理规则推导出来。P P：所有的人总是要死的。：所有的人总是要死的。Q Q：苏格拉底是人。：苏格拉底是人。R R：所以苏格拉底是要死的。：所以苏格拉底是要死的。命题演算无法反映上
2、述推理，因为前提和结论命题演算无法反映上述推理，因为前提和结论都只能表示为原子命题，在命题演算系统中，无都只能表示为原子命题，在命题演算系统中，无法由前提法由前提P,QP,Q推出结论推出结论R R，结论，结论R R也根本不是前提也根本不是前提P,QP,Q的逻辑结果。的逻辑结果。所以我们必须对原子命题进行分解，研究它的所以我们必须对原子命题进行分解，研究它的内部结构，并用相应的手段去刻划它们，这正是内部结构，并用相应的手段去刻划它们，这正是谓词逻辑所要研究的问题。谓词逻辑所要研究的问题。2.1 2.1 个体个体 谓词谓词 量词量词 2.1.1 2.1.1 2.1.1 2.1.1 个体个体个体个体
3、 谓词演算中把一切讨论对象都称为个体，它们谓词演算中把一切讨论对象都称为个体，它们可以是客观世界中具体的客体，也可以是抽象的客可以是客观世界中具体的客体，也可以是抽象的客体，例如数字，符号等。确定的个体常用体，例如数字，符号等。确定的个体常用a a，b b，c c等小写字母表示，并被称为常元。不确定的个体常等小写字母表示，并被称为常元。不确定的个体常用字母用字母x x，y y，z z等表示，并被称为变元。等表示，并被称为变元。谓词演算中把讨论对象，即个体的全体称为个体谓词演算中把讨论对象，即个体的全体称为个体域，常用字母域，常用字母D D表示，并约定任何表示，并约定任何D D都至少含有一个都至
4、少含有一个成员。当讨论对象遍及一切客体时，个体域特称为成员。当讨论对象遍及一切客体时，个体域特称为全总域，用字母全总域，用字母U U表示。表示。当给定个体域时，常元表示该域中的一个确定的成当给定个体域时，常元表示该域中的一个确定的成员，而变元则可以取该域中的任何一个成员为其值。员，而变元则可以取该域中的任何一个成员为其值。个体2.1.2 2.1.2 2.1.2 2.1.2 谓词谓词谓词谓词 我们把语句中表示个体性质或关系的语言成分（通我们把语句中表示个体性质或关系的语言成分（通常是谓语）称为谓词。常是谓语）称为谓词。例例：（：（1 1）“苏格拉底是人苏格拉底是人”中的中的“是人是人”（2 2）
5、“苏格拉底是要死的苏格拉底是要死的”中的中的“是要死的是要死的”（3 3）“实数的平方是非负的实数的平方是非负的”中的中的“是非负的是非负的”（4 4）“张三生于北京张三生于北京”中的中的“生于生于”（5 5）“3“3小于小于2”2”中的中的“小于小于”（6 6）“3“32 25”5”中的中的“”其中：其中：（1 1），（），（2 2），（），（3 3）表示个体性质；（）表示个体性质；（4 4），（），（5 5）表示两个个体间的关系；（表示两个个体间的关系；（6 6）表示）表示3 3个个体间的关个个体间的关系。系。谓词我们可把陈述句分解为二部分：我们可把陈述句分解为二部分：主语（名词，代词）和
6、谓语（动词）。主语（名词，代词）和谓语（动词）。谓词演算中用携有空位的大写字母表示谓词，例如：谓词演算中用携有空位的大写字母表示谓词，例如：M M（）表示（）表示“是人是人”B B（，）表示）表示“生于生于”A A（，）表示，）表示“”上述表示法可读性差，因此常用变元来代替空位，上述表示法可读性差，因此常用变元来代替空位，例如：例如：M(x),B(x,y),A(x,y,z)M(x),B(x,y),A(x,y,z)，它们被称为谓词，它们被称为谓词命名式，简称谓词。命名式，简称谓词。若谓词字母联系着一个个体，则称作若谓词字母联系着一个个体，则称作一元谓词一元谓词一元谓词一元谓词；若谓词字母联系着二
7、个个体，则称作若谓词字母联系着二个个体，则称作二元谓词二元谓词二元谓词二元谓词；若谓词字母联系着若谓词字母联系着n n个个体，则称作个个体，则称作n n n n元谓词元谓词元谓词元谓词。谓词填式谓词填式谓词填式谓词填式：谓词字母后填以个体所得的式子。例如：谓词字母后填以个体所得的式子。例如:R R（x x）表示）表示“x“x是实数是实数”（这里（这里x x表示个体）表示个体）L L（3 3，2 2）表示）表示“3 3小于小于2 2”注意：注意：个体的次序必须是有规定的。个体的次序必须是有规定的。例：河南省例：河南省北接北接河北省。河北省。n L b n L b用用L(x,y)L(x,y)表示表
8、示x x北接北接y y；n n：河南省；：河南省；b b：河北省：河北省 写成二元谓词为：写成二元谓词为：L(n,b)L(n,b)，但不能写成，但不能写成L(b,n)L(b,n)。一般的，谓词填式一般的，谓词填式P P（t1,tn）表示个体项）表示个体项t1,，tn所代表的个体满足所代表的个体满足n n元谓词元谓词P P（t1,tn）注意：注意：当空位处填入变元时，谓词命题式与谓词填当空位处填入变元时，谓词命题式与谓词填式同形，但它们表示不同的意义。例如，式同形，但它们表示不同的意义。例如，R R（x x）作为命名式时，它只是作为命名式时，它只是R R（）的另一写法，与（）的另一写法，与x x
9、无无关，改为关，改为R R（y y）意义照旧；但）意义照旧；但R R（x x）作为填式时，）作为填式时，它表示它表示“x“x所取值为实数所取值为实数”，改为，改为R R（y y）后其意义）后其意义变为变为“y“y所取值为实数所取值为实数”。当谓词填式中所填个体都是常元时，它是一个命当谓词填式中所填个体都是常元时，它是一个命题，因而有确定的真值，例如题，因而有确定的真值，例如 L L（3 3，2 2）为假，）为假，A A（3 3，2 2，5 5）为真。）为真。从这个意义上，谓词是以个体域为定义域，以真值从这个意义上，谓词是以个体域为定义域，以真值集为值域的映射。集为值域的映射。2.1.3 2.1
10、.3 命题函数与量词命题函数与量词定义定义 由一个谓词字母和一个非空的个体变元的集合由一个谓词字母和一个非空的个体变元的集合所组成的表达式，称为简单所组成的表达式，称为简单命题函数命题函数。个体在谓词表达式中可以是任意的名词。个体在谓词表达式中可以是任意的名词。例：例：C“C“总是要死的。总是要死的。”j j：张三；：张三；t t：老虎；：老虎；e e：桌子。：桌子。则则C(j),C(t),C(e)C(j),C(t),C(e)均表达了命题。均表达了命题。C C：表示：表示“总是总是要死的要死的”；x x：表示变元（个体变元），则：表示变元（个体变元），则C(C(x x)表示表示“x x总是要死
11、的总是要死的”，则称，则称C(C(x x)为命题函数。为命题函数。讨论：（讨论：（a a）当简单命题函数仅有一个个体变元时，）当简单命题函数仅有一个个体变元时，称为一元简单命题函数；称为一元简单命题函数；（b b）若用任何个体去取代个体变元之后，则）若用任何个体去取代个体变元之后，则命题函数就变为命题。命题函数就变为命题。命题函数量词量词（1 1 1 1）全称量词全称量词“”为全称量词符号，读作为全称量词符号，读作“对于所有的对于所有的”，“对任一个对任一个”，“对一切对一切”。“”表达式的读法表达式的读法 xP(x)xP(x)：“对所有的对所有的x x，x x满足满足P(x)”P(x)”；x
12、P(x)xP(x)：“对所有对所有x x，x x不满足不满足P(x)”P(x)”；xP(x)xP(x)：“并不是对所有的并不是对所有的x x，x x都满足都满足 P(x)”P(x)”；xP(x)xP(x)：“并不是对所有的并不是对所有的x x，x x都不满足都不满足 P(x)”P(x)”。例：例：“这里所有的都是苹果这里所有的都是苹果”可写成：可写成：xA(x)xA(x)或或(x)A(x)x)A(x)量词 全称量词例：将例：将“对于所有的对于所有的x x和所有的和所有的y y，如果，如果x x高于高于y y，那，那么么y y不高于不高于x”x”写成命题表达形式。写成命题表达形式。解：解：G(x
13、,y)G(x,y)：x x高于高于y y x x y(G(x,y)y(G(x,y)G(y,x)G(y,x)（2 2 2 2）存在量词存在量词“”为存在量词符号，读作为存在量词符号，读作“存在一个存在一个”，“对于一些对于一些”，“对于某些对于某些”，“至少存在一个至少存在一个”。“”表达式的读法：表达式的读法：x A(x)x A(x)：“存在一个存在一个x,x,使使x x满足满足A(x)”A(x)”；xA(x)xA(x)：“存在一个存在一个x,x,使使x x不满足不满足A(x)”A(x)”；x A(x)x A(x)：“不存在一个不存在一个x,x,使使x x满足满足A(x)”A(x)”；xA(x
14、)xA(x)：“不存在一个不存在一个x,x,使使x x不满足不满足A(x)”A(x)”。存在量词例：（例：（a a）存在一个人；）存在一个人；（b b）某个人很聪明；）某个人很聪明；（c c）某些实数是有理数）某些实数是有理数 将（将（a a）,（b b）,（c c）写成命题。）写成命题。解：规定解：规定M(x)M(x)：x x是人；是人；C(x)C(x)：x x很聪明；很聪明；R R1 1(x)(x)：x x是实数是实数 R R2 2(x)(x)：x x是有理数。是有理数。则（则（a a）x M(x)x M(x)；（b b）x(M(x)x(M(x)C(x)C(x)；（c c）x(R x(R1
15、 1(x)(x)R R2 2(x)(x)。（3 3 3 3）量化命题的真值：取决于给定的个体域量化命题的真值：取决于给定的个体域 给定个体域：给定个体域：aa1 1，a an n，则有：，则有：xP(x)xP(x)P(aP(a1 1)P(aP(an n)xQ(x)xQ(x)Q(aQ(a1 1)Q(aQ(an n)2.1.4 2.1.4 谓词公式和语句的形式化谓词公式和语句的形式化原子谓词公式：不出现命题联结词和量词的谓词命名原子谓词公式：不出现命题联结词和量词的谓词命名式称为原子谓词公式，并用式称为原子谓词公式，并用P(xP(x1 1xxn n)来表示。来表示。（P P称为称为n n元谓词，元
16、谓词，x x1 1xxn n称为个体变元），当称为个体变元），当n=0n=0时时称为零元谓词公式。称为零元谓词公式。定义定义（谓词公式的归纳法定义）（谓词公式的归纳法定义）原子谓词公式是谓词公式；原子谓词公式是谓词公式；若若A A是谓词公式，则是谓词公式，则AA也是谓词公式；也是谓词公式；若若A,BA,B都是谓词公式，则都是谓词公式，则(A(A B),(AB),(A B),(AB),(AB),(AB),(AB)B)都是谓词公式；都是谓词公式；若若A A是谓词公式，是谓词公式，x x是任何变元，则是任何变元，则 xA,xA,xAxA也都也都是谓词公式；是谓词公式；谓词公式只有有限次利用只有有限次
17、利用-所产生的符号串才是谓词公所产生的符号串才是谓词公式（谓词公式又称合式公式，简称公式）。式（谓词公式又称合式公式，简称公式）。从以上谓词公式的生成法则可见，命题公式是从以上谓词公式的生成法则可见，命题公式是谓词公式的特例。事实上，命题逻辑是谓词逻辑谓词公式的特例。事实上，命题逻辑是谓词逻辑系统的一个子系统，命题逻辑所使用的方法和所系统的一个子系统，命题逻辑所使用的方法和所获得的结论，在谓词逻辑中是作为不证自明的正获得的结论，在谓词逻辑中是作为不证自明的正确形式而直接使用的。确形式而直接使用的。谓词公式中括号的省略方法与命题公式相同。谓词公式中括号的省略方法与命题公式相同。例：任何整数或是正
18、的，或是负的。例：任何整数或是正的，或是负的。解：设解：设I(x):xI(x):x是整数；是整数；R R1 1(x)(x)：x x是正数；是正数；R R2 2(x)(x)：x x是负数。是负数。此句可写成：此句可写成：x(I(x)x(I(x)(R R1 1(x)(x)R R2 2(x)(x)例：设个体域是人类，将下列语句形式化为谓词公式。1.有人勇敢，但不是所有的人都勇敢。设：B(x)：x勇敢则形式化为：x B(x)x B(x)x x B(x)B(x)2.我为人人，人人为我。设i表示“我”；S（x,y）：x为y服务则形式化为：x x S（i,x）x Sx S（x x，i)i)辖域：紧接在量词后
19、面括号内的谓词公式。例：xP(x)Q Q（x x），量词），量词x的辖域为P(x)x(P(x)Q(x)，量词x的辖域为P(x)Q(x)若量词后括号内为原子谓词公式，则括号可以省去。例如 x（P(x)）可写成 xP(x)辖域约束变元：在量词x或x的辖域内，且与量词下标相同的变元。自由变元：当且仅当不受量词的约束。例：xP(x)Q Q（x x）P(x)中的x是约束变元，Q（x）中的x是自由变元 x（P(x，y)Q Q（x x，y y）R(x，z)，P(x，y)Q Q（x x，y y）中的x是约束变元，R(x，z)中的x是自由变元，y,z都是自由变元约束变元的改名规则 任何谓词公式，对约束变元可以改
20、名。我们认为xP(x,y)和zP(z,y)是一等价的谓词公式，但是需注意，不能用同一变元去表示同一谓词公式中的二个变元。例如：yP(y,y)是不正确的。约束变元 自由变元 改名规则改名规则：（1）在改名中要把公式中所有相同的约束变元全部同时改掉；（2）改名时所用的变元符号在量词辖域内未出现的。例：xP(x)yR(x,y)可改写成xP(x)zR(x,z)，但不能改成xP(x)xR(x,x)，xR(x,x)中前面的x原为自由变元，现在变为约束变元了。语句形式化应注意：（1）准确从语句中提取谓词，表示性质的谓语用一元谓词，表示关系的谓语用二元或多元数谓词表示。（2）准确使用量词的辖域，当辖域中多于一
21、个谓语时必须注意括号的使用。多个量词使用时其次序应与原语句意义一致。改名规则2.2 谓词演算永真式2.2.1 2.2.1 谓词公式的真值谓词公式的真值 在谓词公式中，包含有命题变元和个体变元，当在谓词公式中，包含有命题变元和个体变元，当个体变元由确定的个体来取代，命题变元用确定个体变元由确定的个体来取代，命题变元用确定的命题所取代时，就称对谓词公式赋值。一个谓的命题所取代时，就称对谓词公式赋值。一个谓词公式经过赋值后，就成为有确定真值的命题。词公式经过赋值后，就成为有确定真值的命题。例例:给下列谓词公式一组赋值，以得到一个命题公式给下列谓词公式一组赋值，以得到一个命题公式(1)(1)x x（E
22、(x)E(x)D(x D(x，6)6)解解：令：令E(x)E(x)为为x x是偶数是偶数 D D（x x，6 6）为）为x x大于大于6 6；x x8 8。则谓词公式代表命题：则谓词公式代表命题：8 8是偶数并且是偶数并且8 8大于大于6 6。谓词公式的真值(2)(2)x(B(x)x(B(x)M M（x x）)解：令解：令B(x)B(x)为为x x早餐吃面包早餐吃面包 M(x)M(x)为为x x早餐吃馒头：早餐吃馒头：x x为李明为李明则谓词公式代表命题：李明早餐吃面包或吃馒头。则谓词公式代表命题：李明早餐吃面包或吃馒头。2.2.2 2.2.2 谓词演算永真式谓词演算永真式定义定义 给定谓词公
23、式给定谓词公式A A，若对于，若对于A A的所有赋值，公式的所有赋值，公式对应的真值总为对应的真值总为T T，则称该谓词公式为，则称该谓词公式为永真式永真式。定义定义 给定谓词公式给定谓词公式A A，若对于，若对于A A的所有赋值，公式的所有赋值，公式对应的真值总为对应的真值总为F F，则称该谓词公式为，则称该谓词公式为永假式永假式。定义定义 给定谓词公式给定谓词公式A A，若对于，若对于A A至少存在一组赋值，至少存在一组赋值，公式对应的真值总为公式对应的真值总为T T，则称该谓词公式为，则称该谓词公式为可满足可满足式式。谓词演算永真式关于永真式的几个基本原理：关于永真式的几个基本原理：关于
24、永真式的几个基本原理：关于永真式的几个基本原理：代入规则：代入规则：对公式中的自由变元的更改叫做代入。对公式中的自由变元的更改叫做代入。(1)(1)对公式中出现该自由变元的每一处进行代入。对公式中出现该自由变元的每一处进行代入。(2)(2)用以代入的变元与原公式中所有变元的名称不用以代入的变元与原公式中所有变元的名称不能相同。能相同。代入原理：代入原理：若若A A是永真式，则对是永真式，则对A A中变元可代入的代中变元可代入的代入实例都是永真式。入实例都是永真式。替换原理：替换原理：设设A,DA,D为谓词公式，为谓词公式，C C为为A A的子公式，且的子公式，且C CD D。若。若B B为将为
25、将A A中子公式中子公式C C的某些出现（未必全部）的某些出现（未必全部）替换为替换为D D后所得到的公式，则后所得到的公式，则C CD D。改名原理：改名原理：若公式若公式A A中无自由变元中无自由变元y y，则，则 xA(x)xA(x)yA(y)yA(y)xA(x)xA(x)yA(y)yA(y)永真式的基本原理注意：注意：定理中对定理中对A A的限制是不可忽略的。例如的限制是不可忽略的。例如 x(xx(xy)y)与改名后的与改名后的 y y(y(yy)y)显然不等价。显然不等价。谓词公式的对偶式谓词公式的对偶式谓词公式的对偶式谓词公式的对偶式定义定义 在一个谓词公式在一个谓词公式A A中（
26、其中不出现中（其中不出现,词）词）把公式把公式A A中中 ,F,T,F,T,变为变为,T,T,F,F,后得到公式后得到公式A A*，则称，则称A A*是是A A的对偶式。的对偶式。定理定理 若谓词公式若谓词公式A A B B，则，则A A*B B*；若谓词公；若谓词公式式A A B B，则，则B B*A A*（这里（这里A,BA,B有同样的个体域）。例如：有同样的个体域）。例如：xA(x)xA(x)xB(x)xB(x)x(A(x)x(A(x)B(x)B(x)xA(x)xA(x)xB(x)xB(x)x(A(x)x(A(x)B(x)B(x)对偶式 定理2.2.3 2.2.3 谓词演算等价式与蕴含式
27、谓词演算等价式与蕴含式定义定义 设设A A和和B B是两个谓词公式，是两个谓词公式，E E为它们共同个体为它们共同个体域，域，如果对如果对A A和和B B的任何一组赋值，两者的真值都的任何一组赋值，两者的真值都相同，则称相同，则称A A和和B B遍及遍及E E是等价的。记作是等价的。记作。定义定义 设设A A和和B B是两个谓词公式，是两个谓词公式，E E为它们共同个体为它们共同个体域，域，当且仅当当且仅当是一个永真式时，称永真是一个永真式时，称永真蕴涵。记作蕴涵。记作。1.1.1.1.不含量词的谓词公式的永真式不含量词的谓词公式的永真式不含量词的谓词公式的永真式不含量词的谓词公式的永真式 只
28、只要要用用原原子子谓谓词词公公式式去去替替代代命命题题公公式式的的永永真真式式中中的的原原子子命命题题变变元元，则则在在第第一一章章中中永永真真蕴蕴含含式式和和等价公式均可变成谓词演算中的永真式：等价公式均可变成谓词演算中的永真式：谓词演算等价式与蕴含式 命题逻辑命题逻辑 谓词逻辑谓词逻辑 (x)(x)(x)(x)(x)(x)(x)(x)(x)(x).(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)(x)(x).2.2.2.2.含有量词的等价式和永真蕴含式含有量词的等价式和永真蕴含式含有量词的等价式和永真蕴含式含有量词的等价式和永真蕴
29、含式（1 1 1 1）量词转换律：量词转换律：xP(x)xP(x)xP(x)xP(x)xP(x)xP(x)xP(x)xP(x)结论：对于非量化命题的否定只需将动词否定，而结论：对于非量化命题的否定只需将动词否定，而对于量化命题的否定不但需对动词进行否定，同对于量化命题的否定不但需对动词进行否定，同时对量词也要进行否定。其方法是：时对量词也要进行否定。其方法是：x x的否定的否定变为变为 x x ，x x的否定变为的否定变为 x x 。（2 2 2 2）量词分配律量词分配律 x(A(x)x(A(x)B(x)B(x)xA(x)xA(x)x xB(x)B(x)x(A(x)x(A(x)B(x)B(x)
30、xA(x)xA(x)x xB(x)B(x)量词转换率 量词分配率 x(A(x)x(A(x)B(x)B(x)xA(x)xA(x)x xB(x)B(x)xA(x)xA(x)x xB(x)B(x)x(A(x)x(A(x)B(x)B(x)x(A(x)x(A(x)B(x)B(x)xA(x)xA(x)x xB(x)B(x)xA(x)xA(x)x xB(x)B(x)x(A(x)x(A(x)B(x)B(x)（3 3 3 3）量词辖域的扩张及其收缩律量词辖域的扩张及其收缩律 x(Ax(A B(x)B(x)A A xB(x)xB(x)x(Ax(A B(x)B(x)A A xB(x)xB(x)x(Ax(A B(x)
31、B(x)A A xB(x)xB(x)x(Ax(A B(x)B(x)A A xB(x)xB(x)xA(x)xA(x)B B x(A(x)x(A(x)B)B)xA(x)xA(x)B B x(A(x)x(A(x)B)B)A AxB(x)xB(x)x(Ax(AB(x)B(x)A AxB(x)xB(x)x(Ax(AB(x)B(x)量词辖域的扩张与收缩率结论：在某个量词的辖域中若存在着不含有被此量结论：在某个量词的辖域中若存在着不含有被此量词所约束的个体变元的子公式，则可将这个子公词所约束的个体变元的子公式，则可将这个子公式从量词的辖域中提出来。式从量词的辖域中提出来。xA xA A A xA xA A
32、A(A(A为不含有变元为不含有变元x x的任何谓词公式的任何谓词公式）2.3 2.3 谓词公式的前束范式谓词公式的前束范式定义定义 一个公式，如果量词均非否定地在公式的开一个公式，如果量词均非否定地在公式的开头，它们的辖域一直延伸到整个公式的末尾，则头，它们的辖域一直延伸到整个公式的末尾，则称此公式叫前束范式。称此公式叫前束范式。形如形如 ，其中，其中 ,QnQn为量词为量词 或或，B B称为母式，称为母式，B B中无量词。中无量词。例：例：x x y y z(Q(x,y)z(Q(x,y)R(z)R(z)前束范式任何一个谓词公式均可转化为与其等价的前束范式，任何一个谓词公式均可转化为与其等价的
33、前束范式，转化步骤如下：转化步骤如下：（1 1）将公式中的联结词）将公式中的联结词和和化化为为，（2 2）利用量词转换把）利用量词转换把 深入到原子谓词公式前深入到原子谓词公式前（3 3）利用改名规则使得所有约束变元，自由变元的）利用改名规则使得所有约束变元，自由变元的名字均不相同名字均不相同（4 4）扩大量词辖域至整个公式。）扩大量词辖域至整个公式。例：把例：把 xP(x)xP(x)xQ(x)xQ(x)变成前束范式。变成前束范式。xP(x)xP(x)xQ(x)xQ(x)xP(x)xP(x)xQ(x)xQ(x)xP(x)xP(x)xQ(x)xQ(x)x(P(x)x(P(x)Q(x)Q(x)2.
34、4 谓词演算的推理理论常用推理规则：常用推理规则：常用推理规则：常用推理规则：（1 1 1 1）全称指定规则（全称指定规则（USUS规则）。规则）。如果对个体域中所有个体如果对个体域中所有个体x,A(x)x,A(x)成立，则对个体域成立，则对个体域中某个任意个体中某个任意个体c c，A(c)A(c)成立。该规则表示成：成立。该规则表示成：xA(x)xA(x)A(c)(x,c A(c)(x,c 个体域个体域)（2 2 2 2）全称推广规则（全称推广规则（UGUG规则）规则）如果能够证明对个体域中每一个个体如果能够证明对个体域中每一个个体c c，命题，命题A(c)A(c)都成立，则可得到结论都成立
35、，则可得到结论 xA(x)xA(x)成立。该规则表示成：成立。该规则表示成：A(x)A(x)xA(x)xA(x)谓词演算的推理理论（3 3 3 3）存在指定规则（存在指定规则（ESES规则）规则）如果对于个体域中某些个体如果对于个体域中某些个体A(x)A(x)成立，则必成立，则必有某个特定的个体有某个特定的个体c c，使，使A(c)A(c)成立。该规则表示成：成立。该规则表示成：xA(x)xA(x)A(c)A(c)（4 4 4 4）存在推广规则（存在推广规则（EGEG规则）规则）如果对个体域中某个特定个体如果对个体域中某个特定个体c c，有，有A(c)A(c)成成立，则在个体域中，必存在立，则
36、在个体域中，必存在x x，使，使A(x)A(x)成立。该规成立。该规则表示成：则表示成：A(c)A(c)xA(x)xA(x)推论规则：推论规则：推论规则：推论规则：命题逻辑中的命题逻辑中的P P规则规则,T,T规则和间接证明法，都可规则和间接证明法，都可以引用到谓词逻辑的推论规则中来，不过要注意以引用到谓词逻辑的推论规则中来，不过要注意对量词做适当处理，其方法是：用对量词做适当处理，其方法是：用US,ESUS,ES在推导中在推导中去掉量词，用去掉量词，用UG,EGUG,EG使结论量化。使结论量化。规则使用说明：规则使用说明：规则使用说明：规则使用说明：（1 1 1 1）在使用在使用ES,USE
37、S,US时一定要是前束范式时一定要是前束范式（2 2 2 2）推导中连续使用推导中连续使用USUS规则可用相同变元规则可用相同变元 xP(x)xP(x)P(y),P(y),xQ(x)xQ(x)Q(y),Q(y),（3 3 3 3）推导中连续使用推导中连续使用ESES规则时，使用一次更改一规则时，使用一次更改一个变元。个变元。（4 4 4 4）推导中既用推导中既用ESES，又用，又用USUS时，时，则必须先用则必须先用ESES，后用，后用USUS方可取相同变元，反之不行。方可取相同变元，反之不行。xP(x)xP(x)P(y)P(y)xQ(x)xQ(x)Q(y)Q(y)推论规则使用说明 xA(x)
38、xA(x)A(c)(US)A(c)(US)A(x)A(x)xA(x)(UG)xA(x)(UG)xA(x)xA(x)A(c)(ES)A(c)A(c)(ES)A(c)xA(x)(EG)xA(x)(EG)例：证明苏格拉底论证例：证明苏格拉底论证 x(M(x)x(M(x)D(x)D(x)M(s)M(s)D(s)D(s)证明：证明：前提：前提：x(M(x)x(M(x)D(x)D(x)，M(s)M(s)结论：结论：D(s)D(s)M(s)P M(s)P x(M(x)x(M(x)D(x)PD(x)P M(s)M(s)D(s)USD(s)US D(s)D(s)假言推理假言推理小结小结学习第一章要注意以下几点：
39、学习第一章要注意以下几点：（1 1）清楚命题与陈述句的关系。）清楚命题与陈述句的关系。（2 2）清楚由）清楚由5 5种基本联结词联结的复合命题的逻辑种基本联结词联结的复合命题的逻辑关系及其真值。特别是要弄清蕴含式关系及其真值。特别是要弄清蕴含式“P“PQ”Q”的的逻辑关系及其真值。逻辑关系及其真值。（3 3）记住常用的蕴含式和等价式，这是学好命题逻）记住常用的蕴含式和等价式，这是学好命题逻辑的关键。辑的关键。（4 4）会准确地求出给定公式的主析取范式和主合取）会准确地求出给定公式的主析取范式和主合取范式。范式。（5 5）会用多种方法判断公式的类型及判断两个公式）会用多种方法判断公式的类型及判断
40、两个公式是否等价。是否等价。（6 6）掌握推理和判断推理是否有效的方法。）掌握推理和判断推理是否有效的方法。小结学习第二章要注意以下几点：学习第二章要注意以下几点：(1)(1)同一个命题在不同个体域内可能有不同的符号化同一个命题在不同个体域内可能有不同的符号化形式，同时也可能有不同的真值，因而在将一个形式，同时也可能有不同的真值，因而在将一个命题符号化之前，必须弄清个体域。命题符号化之前，必须弄清个体域。(2)(2)在将命题符号化时，要特别注意量词与联结词的在将命题符号化时，要特别注意量词与联结词的搭配。经常的情况是全称量词搭配。经常的情况是全称量词 与蕴含词与蕴含词搭配，搭配，存在量词存在量
41、词 与合取词与合取词 搭配搭配。(3)(3)记住主要的等价式。会用约束变元和自由变元换记住主要的等价式。会用约束变元和自由变元换名规则进行等价演算，求出给定公式的前束范式。名规则进行等价演算，求出给定公式的前束范式。(4)(4)在谓词演算的推理证明中，要特别注意在谓词演算的推理证明中，要特别注意USUS，UGUG，ESES，EGEG规则成立的条件。规则成立的条件。第二部分第二部分 集合论集合论 集合论是计算机科学领域不可缺少的数学工具集合论是计算机科学领域不可缺少的数学工具,它是研究集合的一般性质的数学分支。它是研究集合的一般性质的数学分支。在现代数学中，每个对象（如数、函数等）本在现代数学中
42、，每个对象（如数、函数等）本质上都是集合，都可以用某种集合来定义。数学质上都是集合，都可以用某种集合来定义。数学的各个分支，本质上都是在研究这种或那种对象的各个分支，本质上都是在研究这种或那种对象的集合的性质。集合论已成为全部现代数学的理的集合的性质。集合论已成为全部现代数学的理论基础。论基础。集合论的特点是研究对象的广泛性。它总结出集合论的特点是研究对象的广泛性。它总结出由各种对象构成的集合的共同性质，并用统一的由各种对象构成的集合的共同性质，并用统一的方法来处理。因此，集合论被广泛地应用于各种方法来处理。因此，集合论被广泛地应用于各种科学和技术领域。科学和技术领域。第二部分 集合论 由于集
43、合论的语言适合于描述和研究离散对象由于集合论的语言适合于描述和研究离散对象及其关系及其关系，因此，集合论在计算机程序设计语言，因此，集合论在计算机程序设计语言,数据结构数据结构,形式语言形式语言,开关理论开关理论,人工智能人工智能,数据库数据库等领域都有着重要的应用。对于计算机科学工作等领域都有着重要的应用。对于计算机科学工作者来说者来说,集合论是不可缺少的理论基础知识。集合论是不可缺少的理论基础知识。本部分介绍集合论的基础知识本部分介绍集合论的基础知识,如集合的概念如集合的概念,运算和性质运算和性质,序偶序偶,关系关系,函数函数,基数等内容基数等内容.第第3 3章章 集合集合3.1 集合的基
44、本概念与表示3.1.1 3.1.1 集合的基本概念集合的基本概念集合是数学中最基本的概念，它是一个不定义概念。集合是数学中最基本的概念，它是一个不定义概念。一般来说，把具有确定的共同性质的一些事物，一般来说，把具有确定的共同性质的一些事物，汇集成一个整体，就形成一个集合，即集合的元汇集成一个整体，就形成一个集合，即集合的元素具有无序性。素具有无序性。讨论：讨论：1.1.元素（成员）：一个集合中的每个事物元素（成员）：一个集合中的每个事物2.2.符号：通常用大写英文字母符号：通常用大写英文字母,如如A,B,C,A,B,C,表示集合，表示集合，用小写英文字母用小写英文字母a,b,c,a,b,c,表
45、示元素。表示元素。集合的基本概念3.元素与集合间的关系：若a是集合A中的元素，则称“a属于A”，记作：aA；若a不是集合A中的元素，则称“a不属于A”，并记作：aA。4.有限集合：集合的元素个数是有限个的。无限集合：集合的元素个数是无限个的。5.集合基数：有限集A中元素的个数称为A的基，记作|A|。例如：A1，3，5，7，9，则|A|56.性质：a.集合具有无序性由于集合是由一些事物组成的整体，因此不计较这些事物的排列次序。例如,由1，2，3组成的集合与由2，3，1组成的集合是同一个集合。b.b.集合具有互异性集合具有互异性 集合中的元素是互不相同的，如果同一个元素在集集合中的元素是互不相同的
46、，如果同一个元素在集合中多次出现，则认为是一个元素。例如，由合中多次出现，则认为是一个元素。例如，由1 1，1 1，2 2，3 3，3 3组成的集合与由组成的集合与由1 1，2 2，3 3组成的集合是同组成的集合是同一个集合。一个集合。3.1.2 3.1.2 集合的表示集合的表示 表示一个集合，一般常用下列三种方法：表示一个集合，一般常用下列三种方法：1.1.列举法列举法 又称穷举法，是把集合的所有元素一一列举出来又称穷举法，是把集合的所有元素一一列举出来放在大括号内，元素之间用逗号分开。例如：放在大括号内，元素之间用逗号分开。例如：A=1,3,5,7,9,A=1,3,5,7,9,这表示集合这
47、表示集合A A由由5 5个元素组成个元素组成,它们它们分别是分别是1,3,5,7,91,3,5,7,9。显然。显然3 3 A,10A,10 A A。集合的表示 列举法 当一个集合的元素较多，或者它有无穷多个元当一个集合的元素较多，或者它有无穷多个元素时，可以只写出几个元素，其他元素用省略号素时，可以只写出几个元素，其他元素用省略号表示并且把它们放在一个大括号内。要注意写出表示并且把它们放在一个大括号内。要注意写出的元素必须让人明白省略了哪些元素。的元素必须让人明白省略了哪些元素。如：小于如：小于100100的自然数组成的集合可以表示为的自然数组成的集合可以表示为 0 0，1,21,2，9999
48、 2.2.描述法描述法 就是指出一个集合中所有元素共同具有的性质，就是指出一个集合中所有元素共同具有的性质，而不属于这个集合的元素都不具有该性质。它的而不属于这个集合的元素都不具有该性质。它的一般表示方法是：一般表示方法是：S=x|x S=x|x具有性质具有性质PP 描述法 例例:A=x|x:A=x|x是是2424的约束且的约束且x x003.3.文氏图法文氏图法 用一个矩形表示全集，在矩形内画一些圆，用用一个矩形表示全集，在矩形内画一些圆，用圆的内部表示集合。圆的内部表示集合。以下是一些常用的集合，用固定的符号表示：以下是一些常用的集合，用固定的符号表示：N N 自然数集合自然数集合 0,1
49、,2 0,1,2 Z Z 整数集合整数集合 -1,0,1,2 -1,0,1,2 Z Z 正整数集合正整数集合 1,2 1,2，3 3，Q Q 有理数集合有理数集合 R R 实数集合实数集合 C C 复数集合复数集合文氏图法三个特殊集合：全集合、空集、集合族三个特殊集合：全集合、空集、集合族定义定义 如果一个集合包含了所要讨论的每一个集合，如果一个集合包含了所要讨论的每一个集合，则称该集合为全集合，简称全集，用则称该集合为全集合，简称全集，用U U表示。表示。集合中的元素可以是多种多样的，一个集合也可集合中的元素可以是多种多样的，一个集合也可作为另一集合的元素。例：作为另一集合的元素。例：S=a
50、,1,2,p,q S=a,1,2,p,q 定义定义 不含有任何元素的集合称为空集，用不含有任何元素的集合称为空集，用表示。表示。例如，例如，A=x|xA=x|x是大于是大于2 2且小于且小于3 3的自然数的自然数 注意：注意：前者是空集，是没有元素的集前者是空集，是没有元素的集合；后者是以合；后者是以作为元素的集合。作为元素的集合。定义定义 集合中的元素均为集合，称这样的集合为集集合中的元素均为集合，称这样的集合为集合族。合族。例如，例如，A=a A=a，bb，cc、dd三个特殊集合3.2 集合之间的关系定义定义 设设A A、B B是任意二个集合，如果集合是任意二个集合，如果集合A A的每一个