高等数学数学

1、第二章第二章 谓词逻辑谓词逻辑l在命题逻辑中，以原子命题为演算的最小单位，主要是研究命题之间的逻辑关系。命题是具有真假意义的一句话，而对这句话的内部结构和成分是不作分析的，不能揭示原子命题内部的特征。因此，命题推理存在着不足，有些简单的论断也不能用命题逻辑进行推论，例如著名的苏格拉底三段论l所有的人都是要死的；l苏格拉底是人。l所以，苏格拉底是要死的。l又如：l所有的无理数都是实数；l是无理数。l 所以，是实数。l按命题逻辑的方法，设P、Q、R分别表示上述三个命题，则R应该是P，Q的逻辑结果，即P,Q R，命题公式PQR应为永真公式，但根据各种赋值情况不能保证PQR是永真公式，即P,Q R不能

2、成立。所以用命题逻辑无法证明苏格拉底三段论。l原因就在于这类推理中，各命题内部成分之间是有联系的，需要分析命题结构的更深层次。应该将原子命题再细分，分析出个体词，谓词和量词，以便可表达个体与总体的内在联系和数量关系，这就是一阶逻辑所研究的基本内容。一阶逻辑也称一阶谓词逻辑或谓词逻辑。l2.1 谓词逻辑基本概念l2.1.1 个体和谓词l一、一、个体和个体域l命题是命题是具有真假意义的陈述句。从语法上分析，一个陈述句由主语和谓语两部分组成。陈述句。从语法上分析，一个陈述句由主语和谓语两部分组成。l谓词逻辑中把讨论的对象称为个体个体，它们可以是具体客体，也可以是抽象的客体，诸如数字、符号等。确定的个

3、体常用a，b，c等小写字母表示，它们被称为个体常元常元。如：张三，苹果，6等都可以作为个体词表示抽象的或泛指的个体词称为个体变量，常用字母x，y，z，u，v，w等来表示，它们被称为个体变元变元。l个体变元的取值范围称为个体域(或称论域)。个体域可以是有穷集合，例如，1，2，3，4，a，b，c，d，；也可以是无穷集合，例如，自然数集合N=0，1，2，。综合各个个体域一起作为论述范围称为全总域，用字母U表示。l二、谓词及其表示l用以刻划客体的性质或客体之间的关系（通常是谓语）即是谓词。谓词也有常项和变项之分。表示具体性质或关系的谓词称为谓词常项，表示抽象的、泛指的性质或关系的谓词称为谓词变项谓词变

4、项。l例如：l（1）“苏格拉底是人”l“苏格拉底” 是个体常量，“是人” 是谓词 。l（2）“5小于2”l“5”，“2” 是两个个体常量，“小于” 是谓词 。l（3）“直线l1 位于直线l2和直线l3之间”l“直线l1”、“直线l2”和“直线l3” 是三个个体常量，“位于和之间” 是谓词 。l谓词有可以放置个体的空位，如省略号表示的部分。当空位代之以个体后便为一个关于此个体的语句。谓词所具有的空位的数目称为谓词的元数谓词的元数。上述例子中，（1）是一元谓词，（2）是二元谓词，（3）是三元谓词。谓词也须符号化。谓词都用大写英文字母F，G，H，表示，用变元来代替空位，例如可用M（x），L（x,y）

5、，AT（x,y,z）表示上述三 个谓词，它们被称为谓词。这里，用什么变元是无关紧要的。l我们说过，当谓词的空位上填入个体后，便产生一个关于该个体的语句，这时它被称为谓词填式。例如：用M(a)表示个体常项a具有性质M ，用M(x)表示个体变项x具有性质M.而用M(a，b)表示个体常项a，b具有关系M，用M(x,y)表示个体变项x，y具有关系M.一般的，用P(x1,x2,xn)表示含n(n1)个命题变项的n元谓词。n=1时，P(x1)表示x1具有性质P；n2时，P(x1,x2,xn)表示x1,x2,xn具有关系P。 注意：本书约定命题可以看成0元谓词, 将命题看成特殊的谓词。l定义定义2.1 n元

6、谓词P(x1,x2,xn)定义为：个体变量x1,x2,xn的定义域分别为D1，D2，Dn，值域为0,1的n元命题函数（简单命题函数）。ln元谓词P(x1,x2,xn)不是命题。但当用谓词常项取代P，用个体常项a1,a2,an取代x1,x2,xn，才能确定P(x1,x2,xn)的真假值，P(a1,a2,an)成为命题。l2.1.2 量词 l一、量词l有了个体词和谓词之后，还需要表示个体常项或变项之间数量关系的词，即量词。量词可分两种: 全称量词和存在量词。全称量词全称量词和存在量词。全称量词用符号 表示，如：“一切的”，“任意的”，“所有的”，“每一个”，“凡”，“都”等词可将它们都符号化为。存

7、在量词存在量词用符号 表示，如“存在”，“至少有一个”“有一个”，“有的”等词可将它们都符号化为。l我们用 P(x) 表示“x满足P(x)”，则xP(x) 表示：“所有（任意,每一个）x满足P(x)”，即个体域中所有的个体具有性质P。而x P(x) 表示：“有（存在,至少有一个）x满足P(x)”，即个体域中至少有一个体具有性质P。其中的x称为作用变量（指导变元）。此时，P(x)称为全称量词和存在量词的辖域。量词的辖域或者是紧邻其右侧的那个谓词;或者是其右侧第一对括号内的表达式。l二、约束变元和约束变元和自由变元。l量词辖域内与该量词指导变元同一的变元都是约束变元约束变元。l例如lx(A(x)B

8、(x) x C(x)l中x的辖域是A(x)B(x)，其中的x是约束变元； x辖域是C(x)，x是约束变元。 x C(x)不在x辖域内。l在x A(x)B(x) 中x的辖域是A(x)，其中x是约束变元，而B(x)中x不是约束变元称为自由变元自由变元。l在x和x的辖域中，x的所有出现都称为约束出现约束出现。不是约束出现的其他变项均称为是自由出现自由出现的。l三、变元改名与代入l在一公式中，有的个体变元既是约束出现，又是自由出现，这就容易产生混淆。为了避免混淆，可对约束变元换名或自由变元代入。l对于xF(x) ，zH(z)，我们可以对指导变元改名，比如改为yF(y) ，xH(x)。其含义不变。l（1

9、）改名规则，即将量词某个指导变元及相应辖域中约束出现的个体变元，改成本辖域中未曾出现过的个体变元，其余不变。l2.1.3 谓词公式及语句的符号化l一、谓词公式l当限定量词的指导变元为个体变元（不用命题变元、谓词、函数变元 - 分别以命题、谓词、函数为值的变元）时，谓词演算又称为一阶谓词演算一阶谓词演算。我们只讨论一阶谓词演算。l一阶谓词演算使用如下符号：l（1）个体常量符号：a,b,c,a1,b1,c1,。是个体域D中的某个元素。l（2）个体变量符号：x,y,z,x1,y1,z1, 。是个体域D中的任意元素。l（3）函数符号：f,g,h,f1,g1,h1,。当个体域为D，n元函数符号f(x1,

10、x2,xn)可以是DnD的任意一个函数。l（4）谓词符号： P,Q,R,P1,Q1,R1。当个体域为D，n元谓词符号P(x1,x2,xn)可以是Dn0,1的任意一个谓词。l定义定义2.2 谓词逻辑中的项 ，被递归地定义为：l（1）任意的个体常量符号或任意的个体变量符号是项；l（2）若f（x1,x2,xn）是n 元函数符号，t1,t2, ,tn是项，则f(t1,t2, tn）是项；l（3）仅仅由有限次使用（1），（2）产生的表达式才是项。l定义定义2. 3 若P(x1,x2,xn)是n元谓词，t1,t2,tn是项，则称P(t1,t2,tn)为原子谓词公式，简称原子公式。l由原子公式及逻辑符号出发

11、，可给出谓词逻辑中的谓词的合适公式的递归定义。l定义定义2.4 满足下列条件的表达式，称为合适公式（Well-Formed Formulae/Wff）,简称公式。l(1)原子公式是合式公式。 l(2)若A是合式公式，则(A)也是合式公式。 l(3)若A，B是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式。l (4)若A是合式公式，则xA，xA也是合式公式。l (5)只有有限次的应用(1)(4)构成的符号串才是合式公式。l由上述定义可知，合适公式是按上述规则由原子公式、联结词、量词、圆括号和逗号所组成的符号串。括号省略方式如同命题公式。但量词辖域中仅出现一个原子公式，则此辖域的括

12、号可省略，否则不能省略其括号。l定义定义2.5 设A是任意的公式，若A中不含有自由出现的个体变元，则称A为封闭的公式封闭的公式，简称闭闭公式公式。l由闭式定义可知，闭式中所有个体变元均为约束出现。l例如x (P(x) R(x)是闭公式。l二、语句的符号化l把一个文字叙述的命题，用谓词公式表示出来，称为谓词逻辑的翻译或符号化或形式化；反之亦然。l例2.7 在个体域分别为(a) 个体域D1为人类集合；(b) 个体域D2为全总个体域时，l将下面两个命题符号化:l(1) 每一个人都会犯错误。l(2) 有的人会打篮球。l解：(a)令A(x):x会犯错误；B(x):x会打篮球。 l由于所有 x D1，有A

13、(x)，(1)符号化为 xA(x) l由于存在 x D1，有B(x) (2)符号化为 xB(x) l(b) D2为全总个体域,人类是其子集，如果（1）翻译为 xA(x)，(2) 翻译为 xB(x)，意义就不一样了。l在D2情况下，需限定范围 ，即指D2 中的人类子集。所以，引入谓词M(x) ：x是人。这时l(1) 符号化为 x(M(x)A(x) l(2) 符号化为 x(M(x)B(x)l谓词M(x)称为特性谓词。一般情况，总是使用全总个体域。所以，要用特性谓词限定范围。l特性谓词在加入到公式中时遵循如下原则：l（1）对于全称量词x， 特性谓词作为前件加入条件式。l（2）对于存在量词x， 特性谓

14、词作为合取项加入合取式。l2.2 谓词逻辑永真式l2.2.1公式的解释l谓词公式是由一些抽象的符号构成的，是由原子谓词公式 、逻辑联结词、量词、括号连接起来的抽象表达式。给定一个谓词公式，它的实际意义是什么？这涉及到谓词逻辑的语义问题。若对它们（常量符号、变量符号、函数符号、谓词符号）给以具体的解释，则公式就有实际的意义，才可能有真或假。l由此，谓词逻辑中公式G的每一个解释I 由如下四部分组成：l（1）非空的个体域集合D；l（2）对G 中的每个常量符号，指定D中的某个特定的元素；l（3）对G 中的每个n元函数符号，指定Dn到D中的某个特定的函数；l（4）对G 中的每个n元谓词符号，指定Dn到0

15、,1中的某个特定的谓词。lx G(x)是这样的一个命题：“对任意属于个体域D中的x，G(x)都为真”。故对命题的真值如下规定：lx G(x)=lxG(x)是命题“存在一个个体域D中的a，使得G(a)为真”，其真值为lxG(x)=l按照上述定义，给定有限个体域集D=a1,a2,an时，lxA(x)=A(a1)A(a2)A(an)；lxA(x)=A(a1)A(a2)A(an)。l2.2.2谓词演算永真式l一、谓词公式分类l从上述例题可以看到，同一个公式在不同解释下真值可能不同。l定义定义2.6 设A为一个公式，若A在任何解释下均为真，则称A为永真式永真式(或称逻辑有效式或称逻辑有效式)。若A在任何

16、解释下均为假，则称A为矛盾式矛盾式(或永假式或永假式)。若至少存在一个解释使A为真，则称A为可满足式可满足式。l从上述定义可知：l（1）永真式的否定为矛盾式；矛盾公式的否定为有效公式。l（2）永真式一定为可满足式。l谓词演算中允许使用命题常元，谓词公式中仍包含命题公式，其中的重言式在谓词演算中仍然是永真式。当把命题演算中的重言式中的命题变元，代入任意的谓词公式，都不会影响原式的永真性，从而它们也是谓词公式中的重言式，是永真式。这种通过代入得到的公式称为原公式的代入实例代入实例。永真公式的任意一个代入实例必为永真式。l如 PP 是重言式，用A(x)代入P得到代入实例A(x) A(x)也是重言式；

17、用x A(x) 代入P得到代入实例x A(x) x A(x)也是重言式。l需要指出的是：谓词逻辑是不可判定的。即对任一谓词公式而言，没有能行的方法判明它是否是有普遍有效性的。但是，类似命题逻辑可用真值表法判明任一命题公式的永真性，个体域有穷时的谓词公式是可判定的。l 二、谓词演算的等价式和蕴含式l定义定义2.7 设A，B是谓词逻辑中任意两个公式，若AB是永真式，则称A与B是等价的等价的。记做AB，称AB是等价式等价式； 若 AB是永真式，则称A 蕴含蕴含B。记做AB，称AB是蕴含式蕴含式。l定义定义2. 8 设谓词公式A中含自由变元x，设t为一个项，称t关于A对x可代入，如果t中无自由变元为A

18、中的约束变元。l关于谓词逻辑的替换原理，同命题逻辑。 l定义定义2.9 设A为仅含联结词 ，的谓词公式，A*为将A中符号，T，F， , 分别换为，F，T, ， 后所得的公式，那么称A*为A的对偶式。l第一章中关于对偶式的一切讨论，现在对于谓词演算都仍然成立。l 下面讨论谓词逻辑等价式。l(1)命题永真式代入实例l由于命题逻辑中的重言式的代换实例都是谓词逻辑中的重言式，因而第一章的等值式给出的代换实例都是谓词逻辑中的等价式。例如：l xA(x) xA(x) l A(x)B(y) A(x)B(y) l(2) 量词否定等价式lx A(x) xA(x)； lx A(x) xA(x)；l这表明两个量词可

19、相互表示。l当个体域为有限集a1,an时,可以简单证明：l x A(x) (A(a1)A(an) A(a1)A(an) xA(x);l（3）量词辖域的扩张与收缩lA(x)是任意的含自由出现个体变项x的公式，B中不含x的出现,则lx (A(x)B) x A(x)B； lx (A(x)B) x A(x)B；lx (A(x)B) x A(x)B；l x (A(x)B) x A(x)B；l由上经证明可得到：lx (A(x)B) xA(x)B x (BA(x) Bx A(x) lx(A(x)B) x A(x)B x(BA(x) BxA(x) lx A(x) x B(x) x y(A(x)B(y)；l x

20、 A(x) x B(x) x y(A(x)B(y)；l（4）量词分配律l A(x)，B(x)是任意的含自由出现个体变元x的公式，l x(A(x)B(x) xA(x)xB(x) x(A(x)B(x) xA(x)xB(x) l（5） 量词与命题联结词之间的一些蕴含式l x A(x) x A(x)；l x A(x)x B(x) x (A(x)B(x)；l x (A(x)B(x) x A(x)x B(x)；l x (A(x)B(x) x A(x)x B(x)；l x (A(x)B(x) x A(x)x B(x)。l（6）多个量词的基本等价公式和蕴涵公式,设A(x,y)是含有自由变元x,y的谓词公式，则

21、有l ( x ) ( y )A(x,y) ( y ) ( x )A(x,y)；l (x) (y)A(x,y) (y) (x)A(x,y)；l (x) ( y )A(x,y) ( y ) (x)A(x,y)；l ( x ) ( y )A(x,y) (y) ( x )A(x,y)；l ( y ) ( x )A(x,y) (x) ( y )A(x,y)；l (y) ( x )A(x,y) ( x ) (y)A(x,y)；l ( x ) (y)A(x,y) (y) (x)A(x,y)；l ( y ) (x)A(x,y) (x) (y)A(x,y)。l全称量词与存在量词在公式中出现的次序，不能随意更换。

22、l2.3 谓词公式的前束范式l在命题逻辑里，每一公式都有与之等价的范式，在判定一个公式特性（如永真、永假）时，范式起着重要作用，而对谓词逻辑的公式来讲，我们学习前束范式与原公式是等值的，而其他范式与原公式只有较弱的关系。l定义定义2. 10 称公式A是一个前束范式，如果A中的一切量词都位于该公式的最前端（不含否定词）且这些量词的辖域都延伸到公式的末端。其标准形式如下：l(Q1x1)(Q2x2)(Qnxn)B(x1,x2,xn)l其中，Qi为量词或（i=1,n），M称作公式B的母式（基式），B中不再有量词。特别地，若中无量词，则也看作是前束范式。当B为合取（析取）范式时，称为A的前束合取（析取）

23、范式。l定理定理2.1 前束范式存在定理前束范式存在定理l谓词逻辑中的任一公式都可化为与之等价的前束范式，但其前束范式并不惟一。l证明 设G是任一公式，可通过下述步骤将其转化为与之等价的前束范式：l（1）将谓词谓词公式等价转换为仅含联结词为仅含联结词 ，的谓词公式的谓词公式；l（2）反复运用德摩根定律，直接将“”内移到原子谓词公式的前端；l（3）使用谓词的等价公式（主要是量词辖域的扩张与收缩）将所有量词提到公式的最前端。l经过这几步，可求得任一公式的与原公式是等价的前束范式。l定义定义2. 11 设公式A是一个前束范式，如消去A中所有的存在量词和全称量词，所得到的公式称为Skolem标准形。l

24、定理定理2. 2 任意一个公式A都存在相应的Skolem标准形，但此Skolem标准形不一定与原公式等价。l证明 由定理2.3.1知公式A必有与之等价的前束范式，设A的前束范式为lA=(Q1x1)(Q2x2)(Qnxn)B(x1,x2,xn)l（1）如果Qi是存在量词，且Qi的左边没有全称量词，则用一个不出现在B中的的常量符号a来代替xi在B中一切出现。l（2）如果Qi是存在量词，且Qi的左边有全称量词(xj),(xl),(xk)，则直接用一个不出现在B中的函数f(xj,xl,xk)来取代xi在B中一切出现。l（3）如果Qi是全称量词，则直接用一个新的变量符号x来取代xi在M中一切出现。 l反复使用上述（1）（3），消去前束范式中的所有存在量词和全称量词，此时得到的公式为该公式的Skolem标准形，该标准形显然不与原公式等价。l例如 例1的Skolem标准形为 A(v,a) (B(f(v,x)C(x) l2.4 谓词演算推理理论l命题逻辑的永真式在谓词逻辑仍然成立，因此完全可以使用与命题演算时相同的术语和符号，也可以使用命题演算系统中的证明方法和推理规则（规则P,规则T,规则CP）。在推导的过