离散数学自考第二章

第二章谓词逻辑1谓词的概念与表示法2量词与合式公式3谓词演算的等价式与蕴含式4前束范式5谓词演算的推理理论2.1谓词的概念与表示法在研究命题逻辑中，原子命题是命题演算中最基本的单位，不再对原子命题进行分解，但原子命题可进一步用客体和谓词两个部分刻画。定义：可以独立存在的对象称为客体，客体亦称个体，可以是具体事务也可以是抽象的事务。定义：用以刻划客体的性质或关系的即是谓词。例：张华是学生，李明是学生。则可把它表示成：H:表示“是学生”，j:表示“张华”，m:表示“李明”，则可用下列符号表示上述二个命题：H(j)，H(m)。1.命题函数客体在谓词表达式中可以是任意的名词。例：C—“总是要死的。”j：张三；t：老虎；e：桌子。则C(j),C(t),C(e)均表达了命题。在上面的例子中，C：表示“总是要死的”；x：表示变元（客体变元），则C(x)表示“x总是要死的”，则称C(x)为命题函数。《定义》由一个谓词字母和一个非空的客体变元的集合所组成的表达式，称为命题函数。讨论定义：（a）若用任何客体去取代客体变元之后，则命题函数就变为命题；（b）命题函数中客体变元的取值范围称为个体域（论述域）。例：P(x)表示x是质数。这是一个命题函数。其值取决于个体域。可以将命题函数命题，有两种方法：a)将x取定一个值。如：P(4)，P(5)b)将谓词量化。如：xP(x)，xP(x)个体域的给定形式有二种：①具体给定。如：｛j,e,t｝②全总个体域任意域：所有的个体从该域中取得。作业：P281a、c1.2.1量词（1）全称量词“”为全称量词符号，读作“对于所有的”，“对任一个”，“对一切”。例：“这里所有的都是苹果”，可写成：xA(x)或(x)A(x)几种形式的读法：·xP(x)：“对所有的x，x是…”；·x¬P(x)：“对所有x，x不是…”；·¬xP(x)：“并不是对所有的x，x是…”；·¬x¬P(x)：“并不是所有的x，x不是…”。例：将“对于所有的x和任何的y，如果x高于y，那么y不高于x”写成命题表达形式。解：xy(G(x,y)¬G(y,x))G(x,y)：x高于y（2）存在量词“”为存在量词符号，读作“存在一个”，“对于一些”，“对于某些”，“至少存在一个”，“这里存在着这样的”等等。例：（a）存在一个人；将（a）,（b）,（c）写成命题。规定：M(x)：x是人；则（a）xM(x)；“”表达式的读法：·xA(x)：存在一个x,使x是…；·x¬A(x)：存在一个x,使x不是…；·¬xA(x)：不存在一个x,使x是…；·¬x¬A(x)：不存在一个x,使x不是…。著名的苏格拉底三段论可论述如下：a.所有人都是要死的；b.因为苏格拉底是人；c.所以苏格拉底总是要死的；试讲其符号化为谓词公式。解M（x）：表示x是人，D（x）：x是要死的；a：苏格拉底。上述三段论可符号化为：a.（x）（M(x)→D（x））b.M（a）c.D（a）该三段论可用推理描述为：前提：（x）（M(x)→D（x）），M(a)，结论：D（a）1.2.2合式公式定义：原子谓词公式：不出现命题联结词和量词的谓词命名式称为原子谓词公式，并用P(x1…xn)来表示。（P称为n元谓词，x1…xn称为客体变元），当n=0时称为零元谓词公式。定义：由一个或几个原子命题函数以及逻辑联结词组合而成的表达式称为复合命题函数。定义：谓词演算的合式公式（合式公式记为WffA）⑴原子谓词公式是合式公式；⑵若A是合式公式，则¬A也是合式公式；⑶若A,B都是合式公式，则(AB)，(AB),(AB),(AB)都是合式公式；⑷若A是合式公式，x是任何变元，则xA,xA也都是合式公式；⑸只有按⑴-⑷有限次所求得的那些公式才是合式公式（谓词公式又简称“公式”）。定义1.辖域（作用域）：紧接在量词后面括号内的谓词公式。例：xP(x),x(P(x)Q(x))。若量词后括号内为原子谓词公式，则括号可以省去。2.指导变元（作用变元）：紧接在量词后面括号内的X。3.约束变元：在量词的辖域内，且与量词下标相同的变元。4.自由变元：当且仅当不受量词的约束。例：（x）（P（x）（x）P（x，y））（x）的指导变元为x，作用域为P（x）（x）P（x，y），（x）的指导变元为x，作用域为P（x，y），x为约束变元，y为自由变元。约定：最外层的括号可以省略，但需注意，量词后面若有括号则不能省略。例2.(x)(y)(P(x,y)Q(x,z))(x)P(x，y)(x)(y)的作用域为P(x,y)Q(x,z)，x，y为约束变元，z为自由变元。(x)为作用域为P(x，y)，x为约束变元，y为自由变元。在上述的谓词合式公式中，有的个体变元既可以是约束出现，也可以是自由出现，为了避免混淆采用以下两个规则。1.下面介绍约束变元的改名规则：（a）在改名中要把公式中所有相同的约束变元全部同时改掉；（b）改名时所用的变元符号在量词辖域内未出现的。例：xP(x)yR(x,y)可改写成xP(x)zR(x,z)，但不能改成xP(x)xR(x,x)，xR(x,x)中前面的x原为自由变元，现在变为约束变元了。2.区别是命题还是命题函数的方法（a）若谓词公式中出现自由变元，则该公式为命题函数；（b）若谓词公式中的变元均为约束出现，则该公式为命题。例：xP(x,y,z)是二元谓词，yxP(x,y,z)是一元谓词，而谓词公式中如果没有自由变元出现，则该公式是一个命题。3.代入规则：对公式中的自由变元的更改叫做代入。(a)对公式中出现该自由变元的每一处进行代入，(b)用以代入的变元与原公式中所有变元的名称不能相同。例：对公式(x)(P(x)Q(x，y))R(x，y)中的自由变元带入。解：把z代入自由变元y得：(x)(P(x)Q(x，z))R(x，z)作业P321.a、c2.b、d62.3谓词演算的等价与蕴含式个体域（论述域，客体域）:用特定的集合表示的被约束变元的取值范围。(1)个体域不同，则表示同一命题的谓词公式的形式不同。例：“所有的人必死。”令D(x)，x是要死的。下面给出不同的个体域来讨论：(ⅰ)个体域为：{人类}，则可写成xD(x)；(ⅱ)个体域为任意域（全总个体域），则人必须首先从任意域中分离出来，设M(x)，x是人，称M(x)为特性谓词。命题可写成x(M(x)D(x))例：xP(x)，表示x是个大学生，若x的论域为{a,b,c}，则：xP(x)即是P(a)P(b)P(c)；x(P(x即是P(a)P(b)P(c)；定义：在谓词公式中，常包含命题变元和个体变元，当个体变元有确定的个体取代，命题变元用确定的命题所取代时，就称作对谓词公式赋值。亦可以通过对谓词公式的赋值消去量词来确定谓词公式的真值。定义：A，B为二个谓词公式，E为它们共同个体域，若对A和B的任一组变元进行赋值，使得A和B的值相同，则称A和B遍及E是互为等价的，记为AB。定义：给定任意谓词公式WffA，其个体域为E，对于A的所有赋值WffA都为真，则称WffA在E上有效的（或永真的）。定义：一个谓词公式WffA，如果在所有赋值下WffA都为假，则称WffA为不可满足的。定义：一个谓词公式WffA，如果至少在一种赋值下WffA都为真，则称WffA为可满足的。1.不含量词的谓词公式的永真式:只要用原子谓词公式去代命题公式的永真式中的原子命题变元，则在第一章中永真蕴含式和等价公式均可变成谓词演算中的永真式：命题逻辑谓词逻辑¬¬ＰＰ¬¬Ｐ(x)Ｐ(x)Ｐ∨ＰＰＰ(x)∨Ｐ(x)Ｐ(x)....Ｐ→Ｑ¬Ｑ→¬ＰＰ(x)→Ｑ(x)¬Ｑ(x)→¬Ｐ(x)ＰＰ∨ＱＰ(x)Ｐ(x)∨Ｑ(x)ＰΛＱＰＰ(x)ΛＱ(x)Ｐ(x)......下面分类介绍在谓词公式中含有量词的等价式和永真蕴含式。（1）量词转换律：E25¬xP(x)x¬P(x)E26¬xP(x)x¬P(x)下面证明：设个体域为：S={a1,a2,…an}¬xP(x)¬(P(a1)P(a2)…P(an))¬P(a1)¬P(a2)…¬P(an)x¬P(x)下面举例说明量化命题和非量化命题的差别:否定形式不同例：否定下列命题：(a)上海是一个小城镇A(s)(b)每一个自然数都是偶数x(N(x)E(x))上述二命题的否定为：(a)上海不是一个小城镇¬A(s)(b)有一些自然数不是偶数¬x(N(x)E(x))x¬(N(x)E(x))x¬(N(x)E(x))x(N(x)¬E(x))结论：对于非量化命题的否定只需将动词否定，而对于量化命题的否定不但对动词进行否定而且对量词同时进行否定，其方法是：x的否定变为x，x的否定变为x。（2）量词辖域的扩张及其收缩律E27xA(x)Px(A(x)P)xA(x)Px(A(x)P)E28xA(x)Px(A(x)P)xA(x)Px(A(x)P)P，A，B为不含有变元Ｘ的任何谓词公式E30xA(x)Bx(A(x)B)E31xA(x)Bx(A(x)B)E32AxB(x)x(AB(x))E33AxB(x)x(AB(x))（3）量词分配率E23x(A(x)B(x))xA(x)xB(x)E24x(A(x)B(x))xA(x)xB(x)E29(x(A(x)B(x))xA(x)xB(x)I17xA(x)xB(x)x(A(x)B(x))I18x(A(x)B(x))x（A(x)B(x)）I19xA(x)xB(x)x(A(x)B(x))（4）量词的添加和除去的永真蕴含式Q1xP(x)P(y)Q2P(y)xP(x)（Y是ｘ个体域中任一元素）Q5xP(x)xP(x)xPPxPP(P为不含x变元）（5）含有多个量词的永真式：（ⅰ）量词出现的次序直接关系到命题的含义：“xy”表示：“无论选定一个什么样的x值总能找到一个y能使x和y…”“yx”表示：“只选取一个y值，以致无论怎样选定一个x，能够使y和x…”下面列出对应的表达式可以看出其不同处：设x的个体域为：{a1,a2,…an}，y的个体域为：b1,b2,…bn}，则：xyP(x,y)yP(a1,y)…yP(an,y)(P(a1,b1)…P(a1,bn))…(P(an,b1)…P(an,bn))yxP(x,y)xP(x,b1)…xP(x,bn)(P(a1,b1)…P(an,b1))…(P(a1,bn)…P(an,bn))（ⅱ）在含有多个量词的谓词公式中,xy,xy的位置是可以改变的,且不影响命题的真值（ⅲ）量词转换律的推广应用:把¬深入到谓词公式前面去的方法。¬xyzP(x,y,z)x¬yzP(x,y,z)xy¬zP(x,y,z)xyz¬P(x,y,z)ⅳ）两个量词,所组成的谓词公式的等价式和永真蕴含式（8个）xyP(x,y)yxP(x,y)xyP(x,y)yxP(x,y)yxP(x,y)xyP(x,y)yxP(x,y)xyP(x,y)xyP(x,y)yxP(x,y)xyP(x,y)yxP(x,y)yxP(x,y)xyP(x,y)xyP(x,y)yxP(x,y)作业：P351a、c6，7，82.4前束范式定义一个公式，如果量词均非否定地在全式的开头，它们的作用域延伸到整个公式的末尾，则称此公式叫前束范式。例：xyz(¬Q(x,y)R(z))(前束范式)定理：任何一个谓词公式均和一个前束范式等价。证明：①利用量词转换把¬深入到原子谓词公式前,②利用约束变元的改名规则，③利用量词辖域的扩张收缩律,把量词移到全式的