资源描述
第二章第二章 谓词逻辑谓词逻辑2.1谓词的概念与表示谓词的概念与表示(Predicate and its expression)Predicate and its expression)2.2谓词公式与翻译谓词公式与翻译(Predicate formulae)2.3谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式(Equivalences&implications of predicate calculus)2.4前束范式前束范式(Prenex normal form)2.5谓词演算的推理理论谓词演算的推理理论(Inference theory of predicate calculus)2.1 一阶逻辑命题符号化一阶逻辑命题符号化n命题逻辑的局限性命题逻辑的局限性：在命题逻辑中，命题是命题演算的基本在命题逻辑中，命题是命题演算的基本单位，不再对原子命题进行分解，因而无法单位，不再对原子命题进行分解，因而无法研究命题的内部结构、成分及命题之间的内研究命题的内部结构、成分及命题之间的内在联系，甚至无法处理一些简单而又常见的在联系，甚至无法处理一些简单而又常见的推理过程。推理过程。2.1 一阶逻辑命题符号化一阶逻辑命题符号化n例如，下列推理：例如，下列推理：所有的人都是要死的。所有的人都是要死的。苏格拉底是人。苏格拉底是人。苏格拉底是要死的。苏格拉底是要死的。众所周知众所周知,这是真命题。但在命题逻辑中这是真命题。但在命题逻辑中,如如果用果用P,Q,R表示以上三个命题，则上述推理过表示以上三个命题，则上述推理过程为：（程为：（PQ）R。借助命题演算的推理理。借助命题演算的推理理论不能论不能证明其为重言式证明其为重言式。原因：原因：命题逻辑不能将命题之间的内在联系命题逻辑不能将命题之间的内在联系和数量关系反映出来。和数量关系反映出来。解决办法：解决办法：将命题进行分解。将命题进行分解。2.1 一阶逻辑命题符号化一阶逻辑命题符号化个体词个体词和和谓词谓词 在谓词逻辑中，可将在谓词逻辑中，可将原子命题原子命题划分为划分为个体词个体词和和谓词谓词两部分。两部分。个体词个体词：可以独立存在的具体事物的或抽象的：可以独立存在的具体事物的或抽象的概念。概念。例例如，电子计算机、李明、玫瑰花、黑如，电子计算机、李明、玫瑰花、黑板、实数、中国、思想、唯物主义等，客体也板、实数、中国、思想、唯物主义等，客体也可称之为主语。可称之为主语。2.1 一阶逻辑命题符号化一阶逻辑命题符号化谓谓词词：用用来来刻刻划划个个体体词词的的性性质质或或个个体体词词之之间间的的相相互互关关系的词。系的词。例如在下面命题中：例如在下面命题中：（1）张明是个劳动模范。）张明是个劳动模范。（2）李华是个劳动模范。）李华是个劳动模范。刻划个体词的性质刻划个体词的性质 （3）王红王红是个大学生。是个大学生。（4）小李比小赵高小李比小赵高2cm。（5）点）点a在在b与与c之间。之间。刻划个体词之间的相互关系刻划个体词之间的相互关系 （6）阿杜与阿寺同岁。阿杜与阿寺同岁。“是是个个劳劳动动模模范范”、“是是个个大大学学生生”、“比比高高2cm”、“在在与与之间之间”都是都是谓词。谓词。2.1 一阶逻辑命题符号化一阶逻辑命题符号化n刻刻划划一一个个个个体体性性质质的的词词称称之之为为一一元元谓谓词词,刻刻划划n个个个个体之间关系体之间关系的词称之为的词称之为n元谓词元谓词.n一般我们用大写英文字母表示一般我们用大写英文字母表示谓词，谓词，用小写英文字用小写英文字母表示客体名称，例如，母表示客体名称，例如，将上述谓词分别记作大写将上述谓词分别记作大写字母字母F、G、H、R，S则上述命题可表示为：则上述命题可表示为：(1)F(a)a：张明张明 (2)F(b)b：李华李华 (3)G(c)c：王红王红 (4)H(s,t)s：小李小李 t：小赵：小赵 (5)R(a,b,c)(6)S(a,b)a:阿杜阿杜 b:阿寺阿寺其其中中(1)、(2)、(3)为为一一元元谓谓词词，(4)、(6)为为二二元元谓谓词词，(5)为三元谓词。为三元谓词。2.1 一阶逻辑命题符号化一阶逻辑命题符号化注注:(1)单独一个谓词并不是命题，在谓词字母后填单独一个谓词并不是命题，在谓词字母后填上个体所得到的式子称之为谓词填式。上个体所得到的式子称之为谓词填式。(2)在谓词填式中，若个体确定，则在谓词填式中，若个体确定，则A(a1，a2.an)就变成了命题就变成了命题(3)在多元谓词表达式中，个体字母出现的先后在多元谓词表达式中，个体字母出现的先后次序与事先约定有关次序与事先约定有关,一般不可以随意交换位一般不可以随意交换位置置(如如,上例中上例中H(s,t)与与H(t,s)代表两个不同的代表两个不同的命题命题)。2.1 一阶逻辑命题符号化一阶逻辑命题符号化 设谓词设谓词H表示表示“是劳动模范是劳动模范”,a表示个体名表示个体名称称张明张明,b表示个体名称表示个体名称李华李华,c表示个体名称这只老表示个体名称这只老虎，虎，那么那么H(a)、H(b)、H(c)表示三个不同的命表示三个不同的命题题,但它们有一个共同的形式但它们有一个共同的形式,即即H(x).一般地，一般地，H(x)表示客体表示客体x具有性质具有性质H。这里。这里x表示抽象的或表示抽象的或泛指的客体，称为泛指的客体，称为个体变元个体变元，常用小写英文字母，常用小写英文字母x,y,z,表示。相应地，表示具体或特定的客体表示。相应地，表示具体或特定的客体的词称为的词称为个体常项个体常项，常用小写英文字母，常用小写英文字母a,b,c,表示。表示。2.1 一阶逻辑命题符号化一阶逻辑命题符号化同理，个体变元同理，个体变元x，y具有关系具有关系L，记作，记作L(x,y);个体变元个体变元x,y,z具有关系具有关系A，记作，记作A(x,y,z).nH(x)、L(x,y)、A(x,y,z)本身并不是一个命题。本身并不是一个命题。只有用特定的个体取代客体变元只有用特定的个体取代客体变元x,y,z后，它后，它们才成为命题。我们称们才成为命题。我们称H(x)、L(x,y)、(x,y,z)为为命题函数。命题函数。2.1 一阶逻辑命题符号化一阶逻辑命题符号化2.1 一阶逻辑命题符号化一阶逻辑命题符号化vn元谓词元谓词就是有就是有n个个体变元的个个体变元的命题函数命题函数.当当n=0时时,称为称为0元谓词元谓词.因此因此,一般情况下一般情况下,命题命题函数不是命题函数不是命题;特殊情况特殊情况0元谓词就变成一个元谓词就变成一个命题命题.v复合命题函数复合命题函数:由一个或几个简单命题函数由一个或几个简单命题函数以及逻辑联结词组合而成的表达式以及逻辑联结词组合而成的表达式.2.1 一阶逻辑命题符号化一阶逻辑命题符号化例例1:若若x的学习好的学习好,则则x的工作好的工作好 设设S(x):x学习好；学习好；W(x):x工作好工作好 则有则有S(x)W(x)例例2:将下列命题用将下列命题用0元谓词符号化元谓词符号化.(1)2是素数且是偶数是素数且是偶数.(2)如果如果2大于大于3,则则2大于大于4.(3)如果如果张明比李民高张明比李民高,李民比赵亮高李民比赵亮高,则张明则张明比赵亮高比赵亮高.2.1 一阶逻辑命题符号化一阶逻辑命题符号化v解解:(1)设设F(x):x是素数是素数.G(x):x是偶数是偶数.则则命题符号化为：命题符号化为：F(2)G(2)(2)设设L(x,y)：x大于大于y.则则命题符号化为：命题符号化为：L(2,3)L(2,4)(3)设设 H(x,y):x比比y高高.a:张明张明 b:李民李民 c：赵亮：赵亮 则则命题符号化为：命题符号化为：H(a,b)H(b,c)H(a,c)注注意意:命命题题函函数数中中,个个体体变变元元在在哪哪些些范范围围内内取取特特定定的的值值,对命题的真值极有影响对命题的真值极有影响.例如例如:H(x,y)H(y,z)H(x,z)n若若H(x,y)解释为解释为:x大于大于y,当当x,y,z都在实数中取值时都在实数中取值时,则这个式子表示则这个式子表示“若若x大于大于y 且且y 大于大于z，则，则x大于大于z”。这是一个永真式。这是一个永真式。如果如果H(x,y)解释为解释为:“x是是y的儿子的儿子”,当当x,y,z都指人都指人时，则这个式子表示时，则这个式子表示“若若x为为y的儿子的儿子 且且y 是是z的儿的儿子，则子，则x是是z的儿子的儿子”。这是一个永假式。这是一个永假式。如果如果H(x,y)解释为解释为:“x距距y10米米”,当当x,y,z为平面上为平面上的点，则这个式子表示的点，则这个式子表示“若若x距距y10米且米且y距距z10米，米，则则x距距z10米米”。这个命题的真值将由。这个命题的真值将由x,y,z的具体位的具体位置而定，它可能是置而定，它可能是1，也可能是，也可能是0。2.1 一阶逻辑命题符号化一阶逻辑命题符号化n在命题函数中，个体变元的取值范围称为在命题函数中，个体变元的取值范围称为个体个体域域，又称之为论域。个体域可以是有限事物的，又称之为论域。个体域可以是有限事物的集合，也可以是无限事物的集合。集合，也可以是无限事物的集合。n全总个体域：全总个体域：宇宙间一切事物组成的个体域称宇宙间一切事物组成的个体域称为为全总个体域。全总个体域。2.1 一阶逻辑命题符号化一阶逻辑命题符号化2.1 一阶逻辑命题符号化一阶逻辑命题符号化量词量词(Quantifiers)v量词量词：分为全称量词：分为全称量词()和存在量词和存在量词()1.全称量词全称量词(The Universal Quantifiers)对日常语言中的对日常语言中的“一切一切”、“所有所有”、“凡凡”、“每一每一个个”、“任意任意”等词，等词，用符号用符号“”表示表示，表示表示对个体域里的所有个体，对个体域里的所有个体，()表示个体域表示个体域里的所有个体具有性质里的所有个体具有性质F.符号符号“”称为称为全称量全称量词词.2.1 一阶逻辑命题符号化一阶逻辑命题符号化例例3：在谓词逻辑中将下列命题符号化在谓词逻辑中将下列命题符号化.（1）凡是人都呼吸。）凡是人都呼吸。（2）每个学生都要参加考试。）每个学生都要参加考试。（3）任何整数或是正的或是负的。）任何整数或是正的或是负的。解解:(1)当个体域为当个体域为人类集合人类集合时：时：令令F(x):x呼吸。则（呼吸。则（1）符号化为）符号化为 xF(x)xF(x)当个体域为当个体域为全总个体域全总个体域时：时：令令M(x):x是人。则（是人。则（1）符号化为）符号化为 x(M(x)x(M(x)F(x).F(x).2.1 一阶逻辑命题符号化一阶逻辑命题符号化(2)当个体域为当个体域为全体学生的集合全体学生的集合时：时：令令P(x):x要参加考试。则（要参加考试。则（2）符号化为）符号化为 xP(x)xP(x)当个体域为当个体域为全总个体域全总个体域时：时：令令S(x):x是学生。则（是学生。则（2）符号化为）符号化为 x(S(x)x(S(x)P(x).P(x).2.1 一阶逻辑命题符号化一阶逻辑命题符号化(3)当个体域为当个体域为全体整数的集合全体整数的集合时：时：令令P(x):x是正的。是正的。N(x):x是负的。是负的。则（则（3）符号化为）符号化为 x(P(x)x(P(x)N(x)当个体域为当个体域为全总个体域全总个体域时：时：令令I(x):x是是整数整数。则（。则（3）符号化为）符号化为 x(I(x)x(I(x)(P(x)(P(x)N(x).).2.1 一阶逻辑命题符号化一阶逻辑命题符号化2.存在量词存在量词(The Existential Quantifiers)对日常语言中的对日常语言中的“有一个有一个”、“有的有的”、“存在存在着着”、“至少有一个至少有一个”、“存在一些存在一些”等等词，词，用符号用符号“”表示表示，表示存在个体域里的个体，表示存在个体域里的个体，()表示存在个体域里的个体具有性质表示存在个体域里的个体具有性质F.符号符号“”称为称为存在存在量词量词.2.1 一阶逻辑命题符号化一阶逻辑命题符号化“”表达式的读法：表达式的读法：x A(x)x A(x)：存在一个：存在一个x,x,使使x x是是；x xA(x)A(x)：存在一个：存在一个x,x,使使x x不是不是；x A(x)x A(x)：不存在一个：不存在一个x,x,使使x x是是；x xA(x)A(x)：不存在一个：不存在一个x,x,使使x x不是不是。2.1 一阶逻辑命题符号化一阶逻辑命题符号化v例例4 设设 P(x)表示表示x喜欢梦八队，则喜欢梦八队，则 P(x)表示表示x不不喜欢梦八队。喜欢梦八队。(个体域限定为人个体域限定为人)（1）不是所有人都喜欢梦八队：）不是所有人都喜欢梦八队：(x)P(x)（2）存在一些人不喜欢梦八队：）存在一些人不喜欢梦八队：(x)P(x)（3）不会有人喜欢梦八队：）不会有人喜欢梦八队：(x)P(x)（4）所有人都不喜欢梦八队：）所有人都不喜欢梦八队：(x)P(x)v可以看出命题可以看出命题(1)(2)意义完全相同，意义完全相同，(3)(4)意义也完全相意义也完全相同同2.1 一阶逻辑命题符号化一阶逻辑命题符号化解解:(1)令令Q(x):x是有理数。则（是有理数。则（1）符号化为）符号化为 Q(x)（2）当个体域为）当个体域为人类集合人类集合时：令时：令G(x):x活百岁以上活百岁以上 则（则（2）符号化为：）符号化为：xG(x)当个体域为当个体域为全总个体域全总个体域时：时：令令M(x):x是人。是人。则（则（2）符号化为：）符号化为：x(M(x)G(x)例例5：在谓词逻辑中将下列命题符号化在谓词逻辑中将下列命题符号化.（1）一些数是有理数。）一些数是有理数。（2）有些人活百岁以上。）有些人活百岁以上。有时需要同时使用多个量词。有时需要同时使用多个量词。例例6.命命题题“对对任任意意的的x,存存在在y,使使得得x+y=5”,取取个个体域为实数体域为实数集合集合,则该命题则该命题符号化为符号化为:x y H(x,y).其中其中H(x,y):x+y=5.这是个真命题这是个真命题.2.1 一阶逻辑命题符号化一阶逻辑命题符号化3.使用使用量词时应注意的问题量词时应注意的问题（1）在在不不同同的的个个体体域域，同同一一命命题题的的符符号号化化形形式式可能相同也可能不同。可能相同也可能不同。（2）在在不不同同的的个个体体域域，同同一一命命题题的的真真值值可可能能相相同同也也可可能能不不同同。(如如,R（x）表表示示x为为大大学学生生。如如果个体域为大学里的某个班级的学生，则果个体域为大学里的某个班级的学生，则 x R（x）为为真真；若若个个体体域域为为中中学学里里的的某某个个班班级的学生，则级的学生，则 x R（x）为假）为假.).2.1 一阶逻辑命题符号化一阶逻辑命题符号化（3）约约定定以以后后如如不不指指定定个个体体域域，默默认认为为全全总总个个体体域域。对对每每个个客客体体变变元元的的变变化化范范围围,用用特特性谓词加以限制性谓词加以限制.特特性性谓谓词词:限限定定客客体体变变元元变变化化范范围围的的谓谓词词(如如例例3中的中的M（x）).一般而言，对全称量词，特性谓词常作蕴含一般而言，对全称量词，特性谓词常作蕴含的前件，如（的前件，如（x）(M(x)F(x)；对存在；对存在量词，特性谓词常作合取项，如（量词，特性谓词常作合取项，如（x）(M(x)G(x).2.1 一阶逻辑命题符号化一阶逻辑命题符号化2.1 一阶逻辑命题符号化一阶逻辑命题符号化(4)一一般般来来说说，当当多多个个量量词词同同时时出出现现时时，它它们的顺序不能随意调换。如：们的顺序不能随意调换。如：在在实实数数域域上上用用H(x,y)表表示示x+y=5,则则命命题题“对对于于任任意意的的x,都都存存在在y使使得得x+y=5”可可符符号号化化为为：x yH(x,y),其其真真值值为为1.若若调调换换量量词顺序后为：词顺序后为：y xH(x,y),其真值为其真值为0。(5)当当个个体体域域为为有有限限集集合合时时,如如D=a1,a2,an,对任意谓词对任意谓词A(x),有有(x)A(x)A(a1)A(a2)A(an)（x）A(x)A(a1)A(a2)A(an)2.1 一阶逻辑命题符号化一阶逻辑命题符号化例例7：在谓词逻辑中将下列命题符号化：在谓词逻辑中将下列命题符号化.（1）所有的人都长头发。）所有的人都长头发。（2）有的人吸烟。）有的人吸烟。（3）没有人登上过木星。）没有人登上过木星。（4）清华大学的学生未必都是高素质的。）清华大学的学生未必都是高素质的。解：令解：令M(x):x是人。（特性谓词）是人。（特性谓词）（1）令令F(x):x长头发。则符号化为：长头发。则符号化为：（x）(M(x)F(x)2.1 一阶逻辑命题符号化一阶逻辑命题符号化（2）令）令S(x):x吸烟。则符号化为：吸烟。则符号化为：（x x）(M(x)(M(x)S(x)(x)（3）令）令D(x):x登上过木星。则符号化为：登上过木星。则符号化为：(x)(M(x)D(x)x)(M(x)D(x)（4）令）令Q(x):x是清华大学的学生。是清华大学的学生。H(x):x是高素质的。则符号化为：是高素质的。则符号化为：(x)(Q(x)x)(Q(x)H(x)(x)2.1 一阶逻辑命题符号化一阶逻辑命题符号化小结小结:本节将原子命题进行分解本节将原子命题进行分解,分为客体和分为客体和谓词两部分谓词两部分.进而介绍了客体和谓词、一元进而介绍了客体和谓词、一元谓词和谓词和n元谓词元谓词、命题函数、全称量词和、命题函数、全称量词和存在量词等概念。存在量词等概念。重点掌握：重点掌握：一元谓词和一元谓词和n元谓词的概念、元谓词的概念、全全称量词和存在量词及量化命题的符号化。称量词和存在量词及量化命题的符号化。作业作业:1.预习预习4.2 2.习题习题4、5、6上节学习了 一阶逻辑的基本概念：一阶逻辑的基本概念：个体词个体词、谓词谓词、量词量词 一阶逻辑一阶逻辑符号化符号化的有关概念和方法的有关概念和方法本节学习 一阶逻辑公式的概念：一阶逻辑公式的概念：字母表字母表、项项、原子公式原子公式、公式、指导变元、辖域、闭式公式、指导变元、辖域、闭式等等 一阶逻辑公式的一阶逻辑公式的解释解释及及公式类型的判断。公式类型的判断。2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释一阶语言一阶语言用于一阶逻辑公式的形式语言用于一阶逻辑公式的形式语言一、一阶语言一、一阶语言F与合式公式与合式公式定义定义4.1 一阶语言一阶语言F的字母表定义如下：的字母表定义如下：（1）个体常项：）个体常项：a,b,c,ai,bi,ci,i 1（2）个体变项：）个体变项：x,y,z,xi,yi,zi,i 1（3）函数符号：）函数符号：f,g,h,fi,gi,hi,i 1（4）谓词符号：）谓词符号：F,G,H,Fi,Gi,Hi,i 1（5）量词符号：）量词符号：,（6）联结词符号：）联结词符号：,（7）括号与逗号：）括号与逗号：(,),，2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释定义定义4.2 F的项的定义如下：的项的定义如下：（1）个体常项和个体变项是项）个体常项和个体变项是项.（2）若若(x1,x2,xn)是是任任意意的的n元元函函数数，t1,t2,tn是任意的是任意的n个项，则个项，则(t1,t2,tn)是项是项.（3）所所有有的的项项都都是是有有限限次次使使用用（1），（2）得得到的到的.其其实实，个个体体常常项项、变变项项是是项项，由由它它们们构构成成的的n元元函数和复合函数还是项函数和复合函数还是项.2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释例例1 1：D是个体名称的集合，是个体名称的集合，x,y（D）为个体变项，为个体变项，a：张三，张三，b：李四李四 所以所以x，y，a，b是项是项 假设假设f(x):x的父亲，的父亲，F(x,y):x是是y的父亲的父亲 f(a),f(f(a),F(a,b),F(f(f(a),b)则则f(a):张三的父亲，是项张三的父亲，是项 f(f(a):张三的祖父，是项张三的祖父，是项 在谓词逻辑中，项起的是名词的作用，不是句子在谓词逻辑中，项起的是名词的作用，不是句子2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释定定义义4.3 设设R(x1,x2,xn)是是F的的任任意意n元元谓谓词词，t1,t2,tn是是F的的任任意意的的n个个项项，则则称称R(t1,t2,tn)是是F的原子公式的原子公式.其实，原子公式是由项组成的其实，原子公式是由项组成的n元谓词元谓词.原子公式是谓词逻辑公式的最小单位，原子公式是谓词逻辑公式的最小单位，最小的句子单位最小的句子单位2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释例例1：D是个体名称的集合，是个体名称的集合，x,y（D）为个体变项，为个体变项，a：张三，张三，b：李四李四 所以所以x，y，a，b是项是项 假设假设f(x):x的父亲，的父亲，F(x,y):x是是y的父亲的父亲 F(a,b):张三是李四的父亲，是原子公式张三是李四的父亲，是原子公式 F(f(f(a),b):张三的祖父是李四的父亲，是原子公式张三的祖父是李四的父亲，是原子公式定义定义4.44.4（谓词公式）（谓词公式）谓词公式也称为合式公式，其递归定义如下：谓词公式也称为合式公式，其递归定义如下：（1 1）原子公式是合式公式。）原子公式是合式公式。（2 2）若）若A A 是合式公式，则是合式公式，则(A)A)也是合式公式。也是合式公式。（3 3）若）若A A，B B是合式公式，则是合式公式，则(A B)(A B)，(A B)(A B)，(A(A B)B)，(A(A B)B)也是合式公式。也是合式公式。（4 4）若）若A A是合式公式，是合式公式，x x是是A A中出现的任何变元中出现的任何变元,则则(x)x)A,(A,(x)x)A A，也是合式公式。，也是合式公式。(5)(5)只只有有有有限限次次应应用用(1)(4)(1)(4)得得到到的的公公式式是是合合式式公公式式.2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释二、封闭的公式（简称闭式）二、封闭的公式（简称闭式）1量词的辖域、个体变项的约束与自由出现量词的辖域、个体变项的约束与自由出现定定义义4.5 在在公公式式 xA和和 xA中中，称称x为为指指导导变变元元，A为为相相应应量量词词的的辖辖域域.在在 x和和 x的的辖辖域域中中，x的的所所有有出出现现都都称称为为约约束束出出现现，A中中不不是是约约束束出出现现的其他变项均称为是的其他变项均称为是自由出现自由出现的的.在公式在公式 x(F(x,y)G(x,z)中，设中，设 A=(F(x,y)G(x,z)（也可记为（也可记为A(x)）则则x为指导变元，为指导变元，A为为 x的辖域，的辖域，A中中x的两次的两次出现均为约束出现，出现均为约束出现，y与与z均为自由出现均为自由出现.2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释v说明说明:(1)n元谓词公式元谓词公式A(x1，x2.xn)中有中有n个自由变元个自由变元,若若对其中的对其中的k(kn)个进行约束个进行约束,则构成了则构成了n-k元谓词元谓词;如果一个公式中没有自由变元出现如果一个公式中没有自由变元出现,则该公式就则该公式就变成了一个命题变成了一个命题(2)一个公式的约束变元所使用的名称符号是无关一个公式的约束变元所使用的名称符号是无关紧要的紧要的,如如(x)M(x)与与(y)M(y)意义相同意义相同.2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释辖域辖域,自由变元与约束变元自由变元与约束变元举例举例 在在 xP(x)xP(x)Q(x)Q(x)中中,x x的辖域是的辖域是P(x)P(x);在在 y y(C(y)C(y)x x(T(x)T(x)u uQ(Q(x,u)x,u)中中,u u的辖域是的辖域是Q(Q(x,u)x,u);x x的辖域是的辖域是T(x)T(x)u uQ(Q(x,u)x,u);y y的辖域是的辖域是C(y)C(y)x x(T(x)T(x)u uQ(Q(x,u)x,u).2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释例：例：x y(P(x,y)Q(y,z)(x)p(x,y),下面的描下面的描述中错误的是（）述中错误的是（）A.(x)的辖域是（的辖域是（y）（）（P（x,y）Q(y,z)）Bz是该谓词公式的约束变元是该谓词公式的约束变元C.(x）的辖域是）的辖域是P（x,y）D.x是该谓词公式的约束变元是该谓词公式的约束变元 2闭式闭式定定义义4.6 若若公公式式A中中不不含含自自由由出出现现的的个个体体变变项，则称项，则称A为闭式为闭式.例如例如:x y(F(x)G(y)H(x,y)x(F(x)G(x,y)闭式闭式不是闭式不是闭式2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释v由闭式定义可知，闭式中所有个体变元均为约由闭式定义可知，闭式中所有个体变元均为约束出现。束出现。v例如，例如，(x)(P(x)Q(x)x)(P(x)Q(x)和和(x)(x)(y)(P(x)y)(P(x)Q(x,y)Q(x,y)是闭式，而是闭式，而(x)(P(x)Q(x,y)x)(P(x)Q(x,y)和和(y)(y)(z)L(x,y,z)z)L(x,y,z)不是闭式。不是闭式。2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释p约束变元的约束变元的换名与换名与自由变元的自由变元的代入规则代入规则一个变元在同一个公式中既是自由出现又是约束一个变元在同一个公式中既是自由出现又是约束出现出现,这样在理解上容易发生混淆这样在理解上容易发生混淆.为了避免这为了避免这种混乱种混乱,可对可对约束变元进行换名约束变元进行换名.换名规则换名规则:(对约束变元而言）对约束变元而言）对约束变元进行换名对约束变元进行换名,使得一个变元在一个公式中使得一个变元在一个公式中只呈一种形式出现只呈一种形式出现.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)2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释(1)约束变元可以换名约束变元可以换名,其更改的变元名称范其更改的变元名称范围是量词中的指导变元以及该量词作用围是量词中的指导变元以及该量词作用域中所出现的该变元域中所出现的该变元,公式的其余部分不公式的其余部分不变变.(2)换名时一定要更改为作用域中没有出现换名时一定要更改为作用域中没有出现的变元名称的变元名称.2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释v例例1:x(P(x)R(x,y)L(x,y)换名为换名为 t(P(t)R(t,y)L(x,y)v x(H(x,y)y(W(y)L(x,y,z)换名为换名为 x(H(x,y)s(W(s)L(x,s,z)2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释例：例：xP(x)xP(x)yR(x,y)yR(x,y)可改写成可改写成:xP(x)xP(x)zR(x,z)zR(x,z)，但不能改成，但不能改成:xP(x)xP(x)xR(x,x)xR(x,x)，因为因为 xR(x,x)xR(x,x)中前面的中前面的x x原为原为自由变元自由变元，现在变为，现在变为约约束变元束变元了。了。2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释v代入规则代入规则（对自由变元而言）（对自由变元而言）对公式中自由变元的更改称为代入对公式中自由变元的更改称为代入(1)对于谓词公式中的自由变元可以作代入对于谓词公式中的自由变元可以作代入,代入代入时需要对公式中出现该自由变元的时需要对公式中出现该自由变元的每一处每一处进行进行;(2)用以代入的变元与原公式中所有变元的名称用以代入的变元与原公式中所有变元的名称不能相同不能相同.例如对例例如对例1中的公式中的公式 x(P(x)R(x,y)L(x,y)自由变元自由变元y用用z来代入来代入,得得 x(P(x)R(x,z)L(x,z)2.2 一阶逻辑公式及其解释一阶逻辑公式及其解释p区别是命题还是命题函数的方法区别是命题还是命题函数的方法（a）若在谓词公式中出现有自由变元，则该公式为）若在谓词公式中出现有自由变元，则该公式为命题函数；命题函数；（b）若在谓词公式中的变元均为约束变元，则该公）若在谓词公式中的变元均为约束变元，则该公式为命题。式为命题。例：例：xP(x,y,z)是二元命题函数，是二元命题函数，y xP(x,y,z)是一元命题函数，是一元命题函数，谓词公式中如果没有自由变元出现，则该公式是一谓词公式中如果没有自由变元出现，则该公式是一个命题。个命题。根据闭式定义和命题与命题函数的区别方法可知：根据闭式定义和命题与命题函数的区别方法可知：闭式为命题，命题函数不是闭式。闭式为命题，命题函数不是闭式。三、解释与公式的分类三、解释与公式的分类1给定公式对它们进行解释：给定公式对它们进行解释：（1）给给出出公公式式 x(F(x)G(x)一一个个成成真真解解释释，一个成假解释；一个成假解释；（2）给给出出公公式式 x(F(x)G(x)一一个个成成真真解解释释，一个成假解释；一个成假解释；（3）xF(x)x F(x)有成真解释吗？有成真解释吗？（4）xF(x)x F(x)有成假解释吗？有成假解释吗？2F中的解释中的解释定义定义4.7 F的解释的解释I由下面由下面4部分组成：部分组成：(a)非空个体域非空个体域DI (b)DI中一些特定元素的集合中一些特定元素的集合 (c)DI上特定函数集合上特定函数集合 (d)DI上特定谓词的集合上特定谓词的集合例：例：给定解释给定解释I如下：如下：(a)个体域个体域D=N（N为自然数集合，即为自然数集合，即N=0,1,2,）(b)(c)(d)为为 x=y.(e)在在I下，下列哪些公式为真？哪些为假？哪些真知还不下，下列哪些公式为真？哪些为假？哪些真知还不能确定？能确定？3闭式的性质闭式的性质.定理定理4.1 闭式在任何解释下都是命题闭式在任何解释下都是命题.4公式的类型公式的类型定义定义4.8（1）永真式（逻辑有效式）永真式（逻辑有效式）（2）矛盾式（永假式）（）矛盾式（永假式）（3）可满足式）可满足式注意：不是闭式的公式在某些解释下也可能是命题注意：不是闭式的公式在某些解释下也可能是命题.说明：说明：u永真式为可满足式，但反之不真永真式为可满足式，但反之不真;u判断公式是否为永真式不是易事判断公式是否为永真式不是易事;u通过某些代换实例可判断公式类型通过某些代换实例可判断公式类型.定定义义4.9 设设A0是是含含命命题题变变项项p1,p2,pn的的命命题题公公式式，A1,A2,An是是 n个个 谓谓 词词 公公 式式，用用 Ai(1 i n)处处处处代代替替A0中中的的pi，所所得得公公式式A称称为为A0的代换实例的代换实例.例如例如定定理理4.2 重重言言式式的的代代换换实实例例都都是是永永真真式式，矛矛盾盾式的代换实例都是矛盾式式的代换实例都是矛盾式.pq的代换实例的代换实例F(x)G(x),xF(x)yG(y)例例 判判断断下下列列公公式式中中，哪哪些些是是永永真真式式，哪哪些些是是矛矛盾盾式？式？（1）x(F(x)G(x)（2）x(F(x)G(x)（3）xF(x)(x yG(x,y)xF(x)（4）(xF(x)yG(y)yG(y)解解（1），（），（2）为可满足式）为可满足式.（3）为）为p(qp)（重言式）的代换实例，为永真式（重言式）的代换实例，为永真式.（4）为）为(pq)q（矛盾式）的代换实例，为永假式（矛盾式）的代换实例，为永假式.第四章第四章 小结小结一、本章的主要内容与要求一、本章的主要内容与要求1主要内容主要内容v个体词、谓词、量词；个体词、谓词、量词；v一阶逻辑命题符号化；一阶逻辑命题符号化；vF的合式公式、闭式；的合式公式、闭式；vF的解释；的解释；v公式的类型：永真式、矛盾式、可满足式公式的类型：永真式、矛盾式、可满足式2要求要求（1）准确地将给定命题在）准确地将给定命题在F中符号化：中符号化：u当指定个体域时，就使用它；当指定个体域时，就使用它；u当没指定个体域时，就使用全总个体域；当没指定个体域时，就使用全总个体域；u在在符符号号化化时时注注意意两两个个基基本本公公式式中中量量词词与与联联结结词词的搭配。的搭配。（2）深深刻刻理理解解永永真真式式、矛矛盾盾式式、可可满满足足式式的的概概念念及相互之间的关系；及相互之间的关系；（3）记住闭式的性质并能应用它；）记住闭式的性质并能应用它；（4）对对于于给给定定的的解解释释会会判判断断公公式式的的真真值值，或或判判定定真值不确定（即仍不是命题）。真值不确定（即仍不是命题）。二、例二、例1在在一一阶阶逻逻辑辑中中将将下下面面命命题题符符号号化化，并并讨讨论论真值：真值：（1）存在）存在x，使得，使得 x+7=5 (a)D1为全总个体域为全总个体域 (b)D2=N (c)D3=R（1）(a)xH(x)，H(x)：x+7=5，为真，为真 (b)x(F(x)H(x)，H(x)同同(a)中中，F(x)：x为为自自然然数数，为假为假.(c)x(F(x)H(x)，H(x)同同(b)中中，F(x)：x为为实实数数，为真为真本本例例说说明明：不不同同个个体体域域内内，命命题题符符号号化化形形式式可可能能不不同同（也可能相同），真值可能不同（也可能相同）（也可能相同），真值可能不同（也可能相同）.2在一阶逻辑中将下列命题符号化在一阶逻辑中将下列命题符号化（1）大熊猫都可爱）大熊猫都可爱（2）有人爱发脾气）有人爱发脾气（3）说所有人都爱吃面包是不对的）说所有人都爱吃面包是不对的（4）没有不爱吃糖的人）没有不爱吃糖的人（5）一切人都不一样高）一切人都不一样高（6）并不是所有的汽车都比火车快）并不是所有的汽车都比火车快 由于没指出个体域，故用全总个体域由于没指出个体域，故用全总个体域（1）x(F(x)G(x)其中，其中，F(x):x为大熊猫，为大熊猫，G(x):x可爱可爱（2）x(F(x)G(x)其中，其中，F(x):x是人，是人，G(x):x爱发脾气爱发脾气（3）x(F(x)G(x)或或 x(F(x)G(x)其中，其中，F(x):x是人，是人，G(x):x爱吃面包爱吃面包（4）x(F(x)G(x)或或 x(F(x)G(x)其中，其中，F(x):x是人，是人，G(x):x爱吃糖爱吃糖（5）x(F(x)y(F(y)H(x,y)L(x,y),或或 x y(F(x)F(y)H(x,y)L(x,y)其中，其中，F(x):x是人是人,H(x,y),x与与y相同相同,L(x,y):x与与y一样高一样高（6）x y(F(x)G(y)H(x,y)或或 x y(F(x)G(y)H(x,y)其中其中,F(x):x是汽车是汽车,G(y):y是火车是火车,H(x,y):x比比y快快说明：说明：使用的是全总个体域使用的是全总个体域(1)与与(2)是两个基本公式的使用是两个基本公式的使用(3)与与(4)是否定式是否定式(5)与与(6)使用了二元谓词使用了二元谓词(3)-(6)的不同符号化形式是等值的的不同符号化形式是等值的 3.给定解释给定解释I如下如下:(a)个体域个体域D=N (b)=2(c)(x,y)=x+y,(x,y)=x y (d)谓词谓词 (x,y):x=y说明下列公式在说明下列公式在I下的涵义下的涵义,并讨论真值并讨论真值(1)xF(g(x,a),x)(2)x y(F(f(x,a),y)F(f(y,a),x)(3)x y zF(f(x,y),z)(4)xF(f(x,x),g(x,x)(5)x y zF(f(y,z),x)答案答案(3),(4)为真为真,其余的均为假其余的均为假说明：说明：5个小题都是闭式个小题都是闭式,在在I下全是命题；下全是命题；(3)与与(5)说明，量词顺序不能随意改变。说明，量词顺序不能随意改变。作业作业:1.预习预习5.1 2.习题习题9、11(1)(3)(5)人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。
展开阅读全文