离散数学之谓词逻辑.ppt

2.1谓词的概念与表示,命题逻辑的局限性：下列推理：凡是人都是要死的。苏格拉底是人。苏格拉底是要死的。众所周知，这是真命题。但在命题逻辑中(P Q)R，难证其为重言式。,原因：命题逻辑不考虑命题之间的内在联系和数量关系。办法：将命题再次细分。,2.1谓词的概念与表示,谓词在反映判断的句子中，用以刻划客体的性质或关系的即是谓词。例：(1)3是有理数。(2)x是无理数。(3)阿杜与阿寺同岁。(4)x与y有关系L。其中，“是有理数”、“是无理数”、“与同岁”、“与有关系L”均为谓词。前两个是指明客体性质的谓词，后两个是指明两个客体之间关系的谓词。,2.1谓词的概念与表示,将上述谓词分别记作大写字母F、G、H、L，用小写字母表示客体名称，则上述可表示为：(1)F(3)(2)G(x)(3)H(a,b)a:阿杜b:阿寺(4)L(x,y)谓词填式单独一个谓词不是完整的命题，把谓词字母后填以客体所得的式子称为谓词填式。,2.1谓词的概念与表示,n元谓词由n个客体插入到固定位置上的谓词填式。例如：A(b)称作一元谓词，B(a,b)称作二元谓词，L(a,b,c)称作三元谓词，P(x1,x2,xn)称作n元谓词。注意：代表客体名称的字母，它在多元谓词中出现的次序是固定的，与事先约定的次序有关，如L(a,b,c)和L(b,c,a)代表两个不同的命题。,2.2命题函数与量词,例：H是谓词“能够到达山顶”，t表示老虎，c表示汽车，z表示张三，那么H(t),H(c),H(z)表示三个不同的命题，但它们有一个共同的形式H(x)，当x分别取t,c,z 时。L(x,y)表示“x小于y”，那么L(2,3)表示了一个真命题“2小于3”，而L(5,1)表示假命题“5小于1”。可以看出，L(x,y)本身不是一个命题，只有当变元x,y取特定的客体时，才是一个命题。,2.2命题函数与量词,简单命题函数由一个谓词，一些客体变元组成的表达式称为简单命题函数。n元谓词就是有n个客体变元的命题函数。不带任何客体变元的谓词称为0元谓词。复合命题函数由一个或n个简单命题函数以及逻辑联结词组合而成的表达式称复合命题函数。,2.2命题函数与量词,命题函数不是一个命题，只有客体变元取特定名称时，才能成为一个命题。但客体变元在哪些范围内取特定的值，对是否成为命题及命题的真值极有影响。例：R(x)表示“x是大学生”，如果x的讨论范围是某大学里班级中的学生，则R(x)是永真式。如果x的讨论范围是某中学里班级中的学生，则R(x)是永假式。如果x的讨论范围为一剧场中的观众，那么对某些观众，R(x)为真，对另一些观众，R(x)为假。,2.2命题函数与量词,个体可以独立存在的具体的或抽象的客体。个体常量：具体的或特定的，一般用a,b,c,表示。个体变元：抽象的或泛指的，一般用x,y,z,表示。个体域个体变元的论述范围。全总个体域把各种个体域综合在一起作为论述范围的域。,2.2命题函数与量词,量词用来表示个体常量或变元之间数量关系的词。量词分为两种：全称量词表示“一切”,“所有”,“凡”,“每一个”,“任意”等意的词称为全称量词，记作。如：x 表示个体域内所有的x。存在量词表示“某个”,“对于一些”,“存在一些”,“至少有一个”等意的词称为存在量词，记作。如：y 表示个体域内存在一些y。,2.2命题函数与量词,例：用谓词表达式写出下列命题。(1)凡是人都呼吸。(2)有的人是左撇子。解：令F(x)：x 呼吸。G(x)：x 是左撇子。当个体域为人类集合时：(1)xF(x)(2)xG(x)当个体域为全总个体域时：令M(x)：x 是人。(1)x(M(x)F(x)(2)x(M(x)G(x),2.2命题函数与量词,约定：以后如不指定个体域，默认为全总个体域。特性谓词在讨论带有量词的命题函数时，必须确定其个体域。当使用全总个体域时，对客体变元的变化范围限制的词，称作特性谓词。如上例中，M(x)为F(x)和G(x)的特性谓词，它限定了变元x的范围。一般，对全称量词，特性谓词常作条件的前件；对存在量词，特性谓词常作合取项。,2.2命题函数与量词,例：将下列命题符号化，并讨论其真值。(1)所有的人都长头发。解:令M(x):x是人。F(x):x 长头发。则 x(M(x)F(x)真值为0(2)有的人吸烟。解:令M(x):x是人。S(x):x 吸烟。则 x(M(x)S(x)真值为1,2.2命题函数与量词,(3)没有人登上过木星。解:令M(x):x是人。D(x):x 登上过木星。则 x(M(x)D(x)真值为1(4)清华大学的学生未必都是高素质的。解:令Q(x):x 是清华大学的学生。H(x):x 是高素质的。则 x(Q(x)H(x)真值为1 或 x(Q(x)H(x)可见，有些命题的符号化形式不止一种。,2.2命题函数与量词,至此，下列推理即可解决：凡是人都是要死的。苏格拉底是人。苏格拉底是要死的。令M(x):x 是人。D(x):x 是要死的。s:苏格拉底。则谓词表达式为：(x)(M(x)D(x)M(s)D(s),2.3 谓词公式与翻译,一阶语言一阶语言F 的字母表定义如下:(1)个体常项：a,b,c,ai,bi,ci,i1.(2)个体变项：x,y,z,xi,yi,zi,i1.(3)函数符号：f,g,h,fi,gi,hi,i1.(4)谓词符号：F,G,H,Fi,Gi,Hi,i1.(5)量词符号：，.(6)联结词符号：，.(7)括号与逗号：(,),.,2.3 谓词公式与翻译,F 的项：(1)个体常项和个体变项都是项。(2)若f(x1,x2,xn)是任意的n元函数，t1,t2,tn是任意的n个项，则f(t1,t2,tn)是项。(3)所有的项都是有限次使用(1),(2)得到的。原子公式若A(x1,x2,xn)是F 的任意n元谓词，t1,t2,tn是F 的任意n个项，则称A(t1,t2,tn)为谓词演算的原子公式。,2.3 谓词公式与翻译,谓词演算的合式公式/谓词公式(1)原子公式是合式公式。(2)若A 是合式公式，则(A)也是合式公式。(3)若A和B是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式。(4)若A是合式公式，x是A中出现的任何变元，则xA和xA，也是合式公式。(5)只有有限次应用规则(1)(4)构成的符号串才是合式公式。,2.3 谓词公式与翻译,约定：最外层的圆括号可以省略。但量词后面若有括号则不能省略。例：将下列命题符号化。(1)没有不能表示为分数的有理数。解:令Q(x):x是有理数。W(x):x能表示成分数。则x(Q(x)W(x)或 x(Q(x)W(x),2.3 谓词公式与翻译,(2)在北京买菜的人不全是外地人。解:令B(x):x在北京买菜的人。F(x):x是外地人。则 x(B(x)F(x)或 x(B(x)F(x)例：将下列命题符号化。(1)火车都比轮船快。解:令T(x):x是火车。S(x):x是轮船。F(x,y):x 比y 跑得快。则 xy(T(x)S(y)F(x,y),2.3 谓词公式与翻译,(2)有的火车比有的汽车快。解:令T(x):x是火车。C(x):x是汽车。F(x,y):x 比y 跑得快。则 xy(T(x)C(y)F(x,y)(3)不存在比所有火车都快的汽车。解:令T(x):x是火车。C(x):x是汽车。F(x,y):x 比y 跑得快。则 x(C(x)y(T(y)F(x,y)或 x(C(x)y(T(y)F(y,x),2.4 变元的约束,给定A为一谓词公式，其中有一部分公式形为xP(x)或xP(x)。和后面所跟的x，称为相应量词的指导变元。P(x)称为相应量词的作用域/辖域。在x和x的辖域中，x的所有出现都称为x在公式A中的约束出现，所有约束出现的变元，叫做约束变元。A中不是约束出现的变元均称作自由变元。,2.4 变元的约束,(1)x(F(x)G(x,y)x是指导变元，量词的辖域为(F(x)G(x,y)，其中，x是约束出现两次，y是自由出现一次。(2)x F(x,y)y G(x,y)x是指导变元，量词的辖域是F(x,y)，其中，x是约束出现一次，y是自由出现一次；同时，y也是指导变元，量词 的辖域是G(x,y)，其中，y是约束出现一次，x是自由出现一次。,2.4 变元的约束,(3)x y(F(x,y)G(y,z)x H(x,y,z)x、y是指导变元，对应量词、的辖域为y(F(x,y)G(y,z)和(F(x,y)G(y,z)，其中x是约束出现一次，y是约束出现两次，z是自由出现一次；后一个x也是指导变元，量词的辖域为H(x,y,z)，其中x是约束出现一次，y、z是自由出现一次。,2.4 变元的约束,例:(1)x(H(x,y)y(W(y)L(x,y,z)(2)x(H(x)W(y)y(F(x)L(x,y,z)为了避免由于变元的约束与自由同时出现，引起概念上的混乱，故可对约束变元进行换名。使得一个变元在一个公式中只呈一种形式出现，即呈自由出现或呈约束出现。一个公式的约束变元所使用的名称符号是无关紧要的，即xP(x)与yP(y)具有相同的意义，xP(x)与yP(y)意义也相同。,2.4 变元的约束,约束变元的换名规则：对于约束变元可以换名，其更改的变元名称范围是量词中的指导变元，以及该量词作用域中所出现的该变元，公式的其余部分不变。换名时一定要更改为作用域中没有出现的变元名称。例:对x(H(x,y)y(W(y)L(x,y,z)换名。解:可换名为x(H(x,y)u(W(u)L(x,u,z),2.4 变元的约束,对于公式中的自由变元，也允许更改，这种更改叫做代入/代替。自由变元的代入规则：对于谓词公式中的自由变元，可以作代入，代入时需对公式中出现该自由变元的每一处进行。用以代入的变元与原公式中所有变元的名称不能相同。,2.4 变元的约束,例:对x(H(x)W(y)y(F(x)L(x,y,z)代入。解:经代入后公式为 x(H(x)W(v)y(F(u)L(u,y,z),2.4 变元的约束,A(x1,x2,xn)是n元谓词，它有n个相互独立的自由变元。若对其中k个变元进行约束则成n-k元谓词。若谓词公式中没有自由变元出现，则该式就成为一个命题。当论域的元素有限时，可以消去公式中的量词。设论域元素为a1,a2,an。则(x)A(x)A(a1)A(a2)A(an)(x)A(x)A(a1)A(a2)A(an),2.4 变元的约束,量词对变元的约束，往往与量词的次序有关。命题中的多个量词，我们约定从左到右的次序读出。注意:量词的次序不能颠倒，否则将与原命题不符。,2.5 谓词演算的等价式与蕴含式,赋值/解释在谓词公式中常包含命题变元和客体变元，当客体变元由确定的客体所取代，命题变元用确定的命题所取代时，就称作对谓词公式赋值。一个谓词公式经过赋值以后，就成为命题。等价给定任何两个谓词公式wff A和wff B，设它们有共同的个体域E，若对A和B的变元的任一组真值指派，所得真值均相同，则称谓词公式A和B在E上是等价的，并记作AB。,永真式/逻辑有效式给定任意谓词公式wff A，其个体域为E，对于A的任一组真值指派，wff A皆为1，则称公式A在E上是有效的/永真的。不可满足式/永假式一个谓词公式wff A，如果在所有赋值下都为0，则称该wff A是不可满足的/永假的。可满足式一个谓词公式wff A，如果至少在一种赋值下为T，则称该wff A是可满足的。,2.5 谓词演算的等价式与蕴含式,谓词演算中的等价式和蕴涵式命题演算中的等价公式表和蕴含公式表都可推广到谓词演算中使用。消去量词的等价式量词否定的等价式（量词的转化律）(x)P(x)(x)P(x)，(x)P(x)(x)P(x)证明：(可在有限个体域上证明),2.5 谓词演算的等价式与蕴含式,设个体域中的客体变元为a1,a2,an，则(x)A(x)(A(a1)A(a2)A(an)A(a1)A(a2)A(an)(x)A(x)(x)A(x)(A(a1)A(a2)A(an)A(a1)A(a2)A(an)(x)A(x),2.5 谓词演算的等价式与蕴含式,量词作用域的扩张与收缩的等价式 x(A(x)B)x A(x)B x(A(x)B)x A(x)B x(A(x)B)x A(x)B x(BA(x)Bx A(x)x(A(x)B)x A(x)B x(A(x)B)x A(x)B x(A(x)B)x A(x)B x(BA(x)Bx A(x),2.5 谓词演算的等价式与蕴含式,以上各等价式中的B不含客体变元x;或含有与量词指导变元x 不同的变元,如y,z 等。试证明 x(A(x)B)x A(x)B 证：左x(A(x)B)x A(x)B x A(x)B x A(x)B（右）,2.5 谓词演算的等价式与蕴含式,量词分配的等价式 x(A(x)B(x)x A(x)x B(x)x(A(x)B(x)x A(x)x B(x)量词与命题联结词间的一些蕴含式 x A(x)x B(x)x(A(x)B(x)x(A(x)B(x)x A(x)x B(x)x(A(x)B(x)x A(x)x B(x)x(A(x)B(x)x A(x)x B(x)x A(x)x B(x)x(A(x)B(x),2.5 谓词演算的等价式与蕴含式,具有两个量词的二元谓词公式（共八种）x y A(x,y)y x A(x,y)x y A(x,y)y x A(x,y)x y A(x,y)y x A(x,y)y x A(x,y)x y A(x,y)其中：x y A(x,y)y x A(x,y)x y A(x,y)y x A(x,y)后四种均不等价，故全称量词和存在量词在公式中出现的次序，不能随意更换。,2.5 谓词演算的等价式与蕴含式,2.6 前束范式,前束范式一个公式如果量词均包含在全式的开头，它们的作用域延伸到整个公式的末尾，则该公式叫做前束范式。其形式为(v1)(v2)(vn)A，其中是量词或，vi(i=1,2,n)是客体变元，A 是没有量词的谓词公式。如：x y(F(x)G(y)H(x,y)x y(F(x,y)G(y,z)x H(x,y,z),2.6 前束范式,Th1(前束范式存在定理)任意一个谓词公式，均和一个前束范式等价。本定理说明任何公式的前束范式都是存在的，但一般不是唯一的。求法：利用对合律、德摩根律、量词转化律把否定深入到命题变元和谓词填式的前面；利用换名和代入规则，量词作用域的扩张和收缩等价式，把量词提到前面。,2.6 前束范式,例:求下列公式的前束范式。(1)x F(x)x G(x)解：xF(x)xG(x)xF(x)xG(x)(量词否定等价式)x(F(x)G(x)(量词分配等价式)或xF(x)yG(y)(换名规则)xF(x)yG(y)(量词否定等价式)x(F(x)yG(y)(量词辖域扩张等价式)xy(F(x)G(y)(量词辖域扩张等价式),2.6 前束范式,(2)x F(x)x G(x)解：原式xF(x)yG(y)(换名规则)xF(x)yG(y)(量词否定等价式)x(F(x)yG(y)(量词辖域扩张等价式)xy(F(x)G(y)(量词辖域扩张等价式)(3)x F(x)x G(x)解：原式 xF(x)yG(y)(换名规则)xy(F(x)G(y)(量词辖域扩张等价式),2.6 前束范式,(4)x F(x,y)y G(x,y)解：xF(x,y)yG(x,y)t F(t,y)w G(x,w)(换名规则)tw(F(t,y)G(x,w)(量词辖域扩张等价式)或x F(x,t)y G(w,y)(代入规则)xy(F(x,t)G(w,y)(量词辖域扩张等价式)(5)x F(x)x G(x)解：原式xF(x)yG(y)(换名规则)x y(F(x)G(y)(量词辖域扩张等价式),2.6 前束范式,(6)(x F(x,y)y G(y)x H(x,y,z)解：原式(x F(x,y)b G(b)c H(c,y,z)x b(F(x,y)G(b)c H(c,y,z)x b c(F(x,y)G(b)H(c,y,z),2.6 前束范式,前束合取范式一个wff A如果具有如下形式，则称为前束合取范式。(v1)(v2)(vn)(A11A12A1k1)(A21A22A2k2)(Am1Am2Amkm)，其中是量词或，vi(i=1,2,n)是客体变元，Ai j是原子公式或其否定。Th2(前束合取范式存在定理)每一个wff A都可转化为与其等价的前束合取范式。,2.6 前束范式,前束析取范式一个wff A如果具有如下形式，则称为前束析取范式。(v1)(v2)(vn)(A11A12A1k1)(A21A22A2k2)(Am1Am2Amkm)，其中是量词或，vi(i=1,2,n)是客体变元，Ai j是原子公式或其否定。Th3(前束析取范式存在定理)每一个wff A都可转化为与其等价的前束析取范式。,2.6 前束范式,任一个wff A转换为等价的前束合(析)取范式的步骤：消去公式中出现的多余量词；利用换名、代入规则使所有约束变元均不相同，并且使约束变元和自由变元不同；将谓词公式中出现的联结词均转化成,；,2.6 前束范式,利用对合律，德摩根律及量词转化律，将谓词公式中的 深入到命题变元和谓词填式的前面；利用量词作用域的扩张和收缩等价式，将量词推到左边，扩大量词作用域至整个公式。,2.7 谓词演算的推理理论,命题演算中的推理规则，如P、T和CP规则等也可在谓词演算的推理理论中应用。但在谓词推理中，某些前提与结论可能受量词限制，为了能使用命题演算中的等价式和蕴含式，必须在推理过程中有消去和添加量词的规则。,2.7 谓词演算的推理理论,(1)全称指定规则（简记为US）(x)P(x)P(c)如果对论域中所有客体x，P(x)成立，则对论域中某个任意客体c，P(c)成立。,2.7 谓词演算的推理理论,(2)全称推广规则（简记为UG）P(x)(x)P(x)如果能够证明对论域中每一个客体c断言P(c)都成立，则可得到结论(x)P(x)成立。,2.7 谓词演算的推理理论,(3)存在指定规则（简记为ES）(x)P(x)P(c)如果对于论域中某些客体P(x)成立，则必有某个特定客体c，使P(c)成立。应注意，指定的客体c不是任意的。,2.7 谓词演算的推理理论,(4)存在推广规则（简记为EG）P(c)x P(x)如果对论域中某个特定客体c，有P(c)成立，则在论域中，必存在x 使得P(x)成立。,2.7 谓词演算的推理理论,例：构造下列推理的证明。前提：x(A(x)B(x)，x A(x)结论：x B(x)证明：(1)x A(x)P(2)A(c)(1)ES(3)x(A(x)B(x)P(4)A(c)B(c)(3)US(5)B(c)(2)(4)假言推理(6)x B(x)(5)EG注意：(1)(3)引入的顺序不可更改!,2.7 谓词演算的推理理论,例：证明凡是人都是要死的。苏格拉底是人。苏格拉底是要死的。解:令M(x):x是人。D(x):x是要死的。a:苏格拉底。即要证 x(M(x)D(x),M(a)D(a)证明(1)x(M(x)D(x)P(2)M(a)D(a)(1)US(3)M(a)P(4)D(a)(2)(3)I,2.7 谓词演算的推理理论,例：学术委员会的每个成员都是博士并且是教授。有些成员是青年人。因而有的成员是青年博士。解：先将命题符号化.A(x):x是学术委员会成员。B(x):x是博士。J(x):x是教授。H(x):x是青年人。前提:x(A(x)B(x)J(x),x(A(x)H(x)结论:x(A(x)H(x)B(x),2.7 谓词演算的推理理论,证明(1)x(A(x)H(x)P(2)A(c)H(c)(1)ES(3)x(A(x)B(x)J(x)P(4)A(c)B(c)J(c)(3)US(5)A(c)(2)化简(6)H(c)(2)化简(7)B(c)J(c)(4)(5)假言推理(8)B(c)(7)化简(9)A(c)H(c)B(c)(5)(6)(8)合取(10)x(A(x)H(x)B(x)(9)EG,2.7 谓词演算的推理理论,例：有些病人相信所有的医生。但是病人都不相信骗子。所以，医生都不是骗子。解：先将简单命题符号化A(x):x是病人。B(x):x是医生。J(x):x是骗子。H(x,y):x相信y。前提:x(A(x)y(B(y)H(x,y),x(A(x)y(J(y)H(x,y)结论:x(B(x)J(x)证明(1)x(A(x)y(B(y)H(x,y)P(2)A(c)y(B(y)H(c,y)(1)ES,2.7 谓词演算的推理理论,(3)A(c)(2)化简(4)y(B(y)H(c,y)(2)化简(5)x(A(x)y(J(y)H(x,y)P(6)A(c)y(J(y)H(c,y)(5)US(7)y(J(y)H(c,y)(3)(6)假言推理(8)y(H(c,y)J(y)(7)置换(9)B(z)H(c,z)(4)US(10)H(c,z)J(z)(8)US(11)B(z)J(z)(9)(10)假言三段论(12)x(B(x)J(x)(11)UG,