离散数学课件第二章一阶逻辑.ppt

刘师少,Tel：86613747（h）E-mail：,授课:51学时,教学目标:知识、能力、素质,Discrete Mathematics,第二章 一阶逻辑,2.1一阶逻辑的基本概念2.2 一阶逻辑合式公式及解释2.3 一阶逻辑等值式 2.4 一阶逻辑推理理论2.5 例题分析,在命题逻辑中,我们把原子命题作为基本研究单位,对原子命题不再进行分解,只有复合命题才可以分解,揭示了一些有效的推理过程.但是进一步研究发现，仅有命题逻辑是无法把一些常见的推理形式包括进去.例如,2.1一阶逻辑的基本概念,形式逻辑,形式逻辑的一般格式就是三段论。例：苏格拉底三段论：所有的人都是要死的，苏格拉底是人，所以，苏格拉底是要死的。,（1）凡人都是要死的；（2）苏格拉底是人；（3）所以苏格拉底是要死的。P：凡人都是要死的；Q：苏格拉底是人;R：所以苏格拉底是要死的。(PQ)R,（前提）,（前提）,（结论）,苏格拉底三段论,这不是重言式(110),即 r 不是前提p,q的有效结论.这反映了命题逻辑的局限性,其原因是把本来有内在联系的命题p,q,r,视为独立的命题。,原因：命题逻辑不考虑命题之间的内在联系 和数量关系。要反映这种内在联系，就要对命题逻辑进行分析,分析出其中的个体词、谓词和量词，再研究它们之间的逻辑关系，总结出正确的推理形式和规则，这就是一阶(谓词)逻辑的研究内容。办法：将命题再次细分。,2.1一阶逻辑的基本概念,解决这个问题的方法：在表示命题时，既表示出主语，也表示出谓语，就可以解决上述问题。这就提出了谓词的概念(谓词是用来刻划个体词的性质或事物之间的关系的词,谓词S(x)相当于一个函数).,2.1.1 个体、谓词和命题函数在谓词逻辑中，将原子命题分解为谓词和个体两部分。1、定义：在原子命题中，所描述的对象称为个体；用以描述个体的性质或个体间关系的部分，称为谓词。,2.1一阶逻辑的基本概念,例2.1：分析下列个命题中的个体和谓词,是无理数。张三与李四同在信息技术学院。x与y的和等于z（x，y，z是确定的数）。的平方是非负的。所有的实数的平方都是非负的。有一个比21000大的素数。,（1）是无理数。解：个体：（代表圆周率）谓词：是无理数，表示“”的性质。（2）张三与李四同在信息技术学院。解：个体：张三，李四 谓词：与同在信息技术学院 表示“张三”与“李四”之间的关系。,个体：李四谓词：张三与 同在信息技术学院表示“李四”的性质。,个体：张三谓词：与李四同在信息技术学院，表示“张三”的性质。,（3）x 与 y 的和等于 z（x，y，z是确定的数）个体：x、y、z谓词：与的和等于个体：x、z谓词：与y的和等于个体：y谓词：x与的和等于z,谓词可以单个个体的性质，也可以表示二个个体词之间的关系或性质，分别称为一元谓词和二元谓词。表示n个个体间的关系或性质的谓词称为n元谓词,（4）的平方是非负的。解：个体：谓词：的平方是非负的个体：的平方谓词：是非负的（5）所有的实数的平方都是非负的。个体：每一个实数谓词：的平方是非负的（6）有一个比21000大的素数。个体：一个素数谓词：比21000大,“所有”是什么？量词：所有,“有一个”是什么？量词：有一个,2.1.1 个体与个体变元基本概念,个体：能够独立存在的事物，称之为个体，也称之为客体。它可以是具体的，也可以是抽象的事物。通常用小写英文字母a、b、c、.表示。例如，小张、小李、8、a、杭州、社会主义等等都是个体。个体变项：用小写英文字母x、y、z.表示任何个体词，则称这些字母为个体变项。注意：个体变项本身不是个体。,2.1.2 谓词 定义：一个大写英文字母后边有括号，括号内是若干个个体变项，用以表示个体的属性或者个体之间的关系，称之为谓词。如果括号内有n个个体变项，称该谓词为n元谓词。一般地 P(x1,x2,xn)是n元谓词。,（1）张三是个大学生解：个体：张三谓词：是个大学生。若用 P 表示谓词：“是个大学生”;a 表示个体：“张三”。则上述命题可表示为P（a）。同理：“李四是个大学生”，若b表示个体“李四”，则该命题可表示为P（b）。,对于给定的命题，当用表示其个体的小写字母和表示其谓词的大写字母来表示时，规定将小写字母写在大写字母右侧的（）内。,例2.2 用谓词表示下列命题,（2）陈强与陈佩斯是父子解：a 表示：陈强b 表示：陈佩斯若用 Q 表示二元谓词：与 是父子则上述命题可表示为Q（a，b）。又如，若用 R 表示三元谓词“位于与之间”，则命题“杭州位于南京和上海之间”如何表示？a：杭州，b：南京，c：上海，则上述命题可表示为R（a，b，c）。,2.1.3 命题函数 谓词本身并不是命题，只有谓词的括号内填入足够的个体，才变成命题。设 H(x)是谓词 表示 x“能够到达山顶”，l 表示个体李四，t 表示老虎，c 表示汽车，那么H（l），H（t），H（c），等分别表示各个不同的命题：但它们有一个共同的形式，即 H（x）当 x 分别取 l、t、c 时就表示“李四能够到达山顶”，“老虎能够到达山顶”，“汽车能够到达山顶”。,可见,在谓词的括号内填入不同的内容,就得到不同的命题，故谓词相当于一个函数，称之为命题函数。n元谓词P(x1,x2,xn)称之为简单命题函数。规定：当命题函数P(x1,x2,xn)中 n=0 时，即0元谓词，表示不含有客体变元的谓词，它本身就是一个命题变元。将若干个简单命题函数用逻辑联结词联结起来，构成的表达式，称之为复合命题函数。简单命题函数与复合命题函数统称为命题函数。,例如:给定简单命题函数：A(x)：x身体好，B(x)：x学习好，C(x)：x工作好，复合命题函数 A(x)(B(x)C(x)表示如果x身体不好，则x的学习与工作 都不会好。,再如，若L(x,y)表示“x 小于y”，那么L(2,3)表示了一个真命题：“2小于3”而 L(5,1)表示了一个假命题：“5小于1”又如 A(x,y,z)表示一个关系“x 加上 y 等于z”则 A(3,2,5）表示了真命题“3+2=5”，而A(1,2,4）表示了一个假命题“1+2=4”。可以看出：H(x),L(x,y),A(x,y,z)本身不是一个命题，只有当变元 x，y，z等取特定的客体时，才确定了一个命题。,例2.3 用谓词(命题函数)分别表示x是负整数及x 是非负整数,设N（x）：“x是负数”,E(x)：“x是整数”则复合命题函数 N（x）E（x）表示：“x是负整数”N（x）E（x）表示：“x 是非负整数”,通常,对于一个命题函数 Q（x，y）若 Q（x，y）：表示“x 比 y 重”，当 x，y 指人或物时，它是一个命题，但若x，y 指实数时，Q（x，y）就不是一个命题。命题函数不是一个命题，只有个体变元取特定名称时，才能成为一个命题。但是个体变元在那些范围内取特定的值，对是否成为命题及命题的真值即有影响。,比如:设R（x）：“x 是大学生”，对x的取值情况:如果 x 的讨论范围为浙江中医药大学里班级中的学生，则R（x）是永真式。如果 x 的讨论范围为杭州长河高级中学里班级中的学生，则R（x）是永假式。如果 x 的讨论范围为一个剧院中的观众，观众中有大学生也有非大学生，那么对于某些观众，R（x）为真，对于另一些观众，R（x）为假。命题函数确定为命题，与个体变元的论述范围有关。,再如 令G(x，y)：“x高于y”，于是，G(x，y)是一个二元谓词。将x代以个体“张三”，y代以个体“李四”，则G(张三，李四)就是命题：“张三高于李四”。随便将x，y代以确定的个体，由G(x，y)都能得到一个命题。可见，G(x，y)不是命题，而是一个命题函数即谓词。,2.1.4 论域(个体域)定义：在命题函数中个体变项的取值范围，称之为论域，也称之为个体域。例如 S(x):x是大学生，论域是:人类。G(x,y)：xy，论域是:实数。论域是一个集合。定义：由所有个体构成的论域，称之为全总个体域。它是个“最大”的论域。约定:对于一个命题函数，如果没有给定论域，则假定该论域是全总个体域。,例2.4 用谓词(命题函数)将下列命题符号化：(1)丘华和李兵都是学生；(2)2既是偶数又是素数；(3)如果张华比黎明高，黎明比王宏高，则张华比王 宏高。解(1)设个体域是人的集合。P(x)：:x是学生。a：丘华b：黎兵该命题符号化为P(a)P(b),(2)2既是偶数又是素数；设个体域为正整数集合N。F(x)：x是偶数，G(x)：x是素数 a：2该命题符号化为F(a)G(a)(3)如果张华比黎明高，黎明比王宏高，则张 华比王宏高。设个体域是人的集合。L(x,y)：x比y高。a：张华 b：黎明 c：王宏 该命题符号化为L(a,b)L(b,c)L(a,c),2.1.5 量词例如：有些人是大学生。所有事物都是发展变化的。“有些”,“所有的”,就是对客体量化的词。量词：在命题中表示对客体数量化的词。定义了两种量词：(1).存在量词：记作，表示“有些”、“一些”、“某些”、“至少一个”等。(2).全称量词：记作，表示“每个”、“任何一个”、“一切”、“所有的”、“凡是”、“任意的”等。,考察下面两个例子(它们均以整数作为其个体域)(x+1)2=x2+2x+1 x+6=5 对于任何整数代入后等式总是成立。用符号“x”表示“对所有x”，则可表示为 x(x+1)2=x2+2x+1)但则不然，只存在一个整数（-1）代入后才使等式成立号“x”表示“存在某些x”,则 可表示为 x（x+6=5）,（1）所有大学生都热爱祖国；（2）每个自然数都是实数；解：（1）令 S（x）：x 是大学生，L（x）：x热爱祖国x（S（x）L（x）（2）令 N（x）：x 是自然数，R（x）：x 是实数 x（N（x）R（x）,例2.5 试用量词、谓词表示下列命题,（1）有些人是聪明的。（2）并非一切数都大于0。解：（1）令M（x）：x是人，N（x）：x是聪明的x（M（x）N（x）,（2）令I（x）：x 是数（实数域），R（x）：x 是大于零的数。（x（I（x）R（x）x（I（x）R（x）,例2.6 试用量词、谓词表示下列命题,特别注意：谓词前加上了量词，称为谓词的量化。若一个谓词中所有个体变元都量化了，则该谓词就变成了命题。这是因为在谓词被量化后，可以在整个个体域中考虑命题的真值了。这如同数学中的函数f(x)，的值是不确定的，但 可确定其值。,说明：（1）分析命题中表示性质和关系的谓词，要分别符号化为一元和n(n 2)元谓词。（2）根据命题的实际意义选用 或。（3）一般来说，当多个量词同时出现时，它们的顺 序不能随意调换。如：在实数域上用L(x,y)表示x+y=10命题为：对于任意的x,都存在y使得 x+y=10。可符号化为：xyL(x,y)真值为1。若调换顺序后为：yxL(x,y)真值为0。,2.1 一阶逻辑的基本概念,说明：（4）有些命题的符号化形式不止一种。至此，下列推理即可解决：凡是人都是 要死的。苏格拉底是人。苏格拉底是要死的。设：M(x):x是人。D(x):x 是要死的。a:苏格拉底。则符号化为：x(M(x)D(x)M(a)D(a),2.1 一阶逻辑的基本概念,定义2.1 一阶语言的字母表定义如下：（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 一阶逻辑公式及解释,定义2.2一阶语言项的定义如下：(1)个体常项和个体变项是项(2)若f(x1,x2,xn)是任意的n元函数,t1,t2,tn 是任意的n个项，则f(t1,t2,tn)是项。(3)所有的项都是有限次使用(1),(2)得到的。定义2.3 若R(x1,x2,xn)是任意的n元谓词,t1,t2,tn 是项，则称R(t1,t2,tn)为原子公式。,2.2 一阶逻辑公式及解释,有了项的定义，函数的概念就可用来表示个体常元和个体变元。例如，令f(x,y)表示x+y，谓词N(x)表示x是自然数，那么f(2,3)表示个体自然数5，而N(f(2,3)表示5是自然数。这里函数是就广义而言的例如P(x):x是教授，f(x):x的父亲，c:张强，那么P(f(c)便是表示“张强的父亲是教授”这一命题。,函数的使用给谓词表示带来很大方便。例如，用谓词表示命题：对任意整数 x，x2-1=(x+1)(x-1)是恒等式。令 I(x):x是整数，f(x)=x2-1，g(x)=(x+1)(x-1)，E(x,y):x=y，则该命题可表示成：(x)(I(x)E(f(x),g(x)。,定义谓词逻辑公式（简称公式）（1）原子公式是公式（2）如果A，B是公式，则（A），（AB），（AB），（AB），（AB）是公式；（3）如A为公式，x为个体变元，则（xA），（xA）为公式；（4）公式由且仅由有限次使用（1），（2），（3）而得。注：量词后面若有括号，则不能省略。,2.2 一阶逻辑公式及解释,例2.9 将下列命题表示为谓词公式（1）所有正数均可开平方（2）有些人是大学生(3)猫必捕鼠解：（1）设 P（x）：x是正数；Q（x）：x 可开平方则命题（1）可表示为：x（P（x）Q（x）（2）设 R（x）：x是人，S（x）：x是大学生，则命题（2）可表示为：x（R（x）S（x）,(3)猫必捕鼠解：(3)设 C（x）：“x是猫”，R（y）：“y是鼠”，A（x，y）：“x捕y”，则语句可表示为：xy（C（x）R（y）A（x，y）凡是与某一范围有关的对象应用量词来描述。,例2.10 用谓词表示下列语句(1)没有最大的自然数解：设N（x）：x是自然数，G（x，y）：“x大于y”，则 语句可表示为：x(N(x)y(N(y)G(y,x)另一种表示：B（x）：x是最大，则 x（N（x）B（x）可以吗？,(2)并非每个实数都是有理数。R（x）,Q（x）解：（x（R（x）Q（x）(3)没有不犯错误的人。F（x）,M（x）解：（x（F（x）M（x）(4)尽管有人聪明，但未必一切人都聪明。M（x）,x是人,P（x）,x聪明 解：x(（M(x）P(x）,一、约束变元、与自由变元与指导变元、辖域 在一个谓词公式中，形如 x A（x）或 x A（x）的那一部分称为公式的约束部分，在公式x A（x）和x A（x）中称x为指导变元 而A（x）称为量词（x或x）的作用域或辖域。在作用域中 x 的任一出现，称为 x 在公式中的约束出现，x 称为约束变元。若在公式中的出现不是约束出现，则称x的出现为自由出现，自由出现的变元称为自由变元。,2.3 约束变元与自由变元,x（P（x）y Q（x，y）x H（x）L（x，y）xy（P（x，y）Q（y，z）x R（x、y）说明：（1）若量词后有括号，则括号内的子公式就是该量词的辖域；（2）若量词后无括号，则与量词邻接的子公式为该量词的辖域；,例2.11 指出下列公式的辖域和变元约束的情况,1.x（P（x）y Q（x，y）解：x 的辖域是（P（x）y Q（x，y），对于x的辖域而言，x的所有出现均为约束出现，故它是约束变元。y 的辖域是Q（x，y），对于 y 的辖域而言，y 的出现为约束出现，故它是约束变元。,例2.11 指出下列公式的辖域和变元约束的情况,变元的辖域实际上是可嵌套的，例如：公式x（F（x）x（G（x）F（x）其中量词 x 的辖域为：（F（x）x（G（x）F（x），而量词 x 的辖域为：（G（x）F（x）。实际上在子公式（G（x）F（x）中的 x 被量词x 约束，而不是被量词 x 约束。实际上，上述公式等价于：x（F（x）y（G（y）F（y）在使用谓词逻辑公式符号化命题时，要小心地选择变元，以使得到的公式满足上述两个条件。,2.x H（x）L（x，y）解：x 的辖域是H（x）,x 是约束出现,故 x 为约束变元在L（x，y）中 x，y 均为自由出现，故对于整个公式来说，x 既为约束变元，又为自由变元，y为自由变元。,例2.11 指出下列公式的辖域和变元约束的情况,3.xy（P（x，y）Q（y，z）x R（x、y）解：xy 的辖域均为（P（x，y）Q（y，z），其中，x、y均为约束出现，故是约束变元，z是自由变元。x的辖域为R（x、y），x为约束出现，故是约束变元，y为自由出现，故是自由变元。在整个公式中，x是约束变元，y既是约束变元，又是自由变元，z是自由变元。,例2.11 指出下列公式的辖域和变元约束的情况,换名规则 设A是一公式，将A中某个辖域中约束变项的所有出现及相应的指导变元，改成该量词辖域中未曾出现的某个个体变项符号，公式中其它部分不变，设所得公式为A,则 A A。代替规则 设A是一公式，将A中某个自由出现的个体变项所有出现用A中未曾出现的个体变项符号代替，A中其它部分不变，设所得公式为A,则 A A。,2.2 一阶逻辑合式公式及解释,注意：在一公式中，有的个体变元既可以是约束出现，又可以是自由出现，这就容易产生混淆。为了避免混淆，采用下面两个规则：约束出现用换名规则，将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。例 x F(x)G(x,y)(换名规则,将约束出现 zF(z)G(x,y)的x改成z),自由变元代入规则，对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入。例 x F(x)G(x,y)(代替规则,将自由出现 x F(x)G(z,y)的x改成z),换名规则是替换约束变项及相应的指导变元。代替规则是代替自由出现的个体变项例 xy(R(x,y)L(y,z)x H(x,y)xy(R(x,y)L(y,z)tH(t,y)(换名规则t)xy(R(x,y)L(y,z)t H(t,w)(代替规则 w)该公式中，不存在既是约束出现，又是自由出现的个体变项。,换名规则与代入规则的主要区别:,公式解释 一般情况下，一阶逻辑公式含有：个体常元、个体变元（约束变元或自由变元）、函数变元、为谓词变元等，对各种变元用指定的特殊常元去代替，就构成了一个公式的解释。当然在给定的解释下，可以对多个公式进行解释。下面给出解释的一般定义。,2.2 一阶逻辑合式公式及解释,带量词的公式在论域内的展开式,例2.12 令A(x)：表示x是整数,B(x)：表示x是奇数，设论域是1,2,3,4,5，谓词公式xA(x)表示论域内所有的客体都是整数 显然公式xA(x)的真值为真，因为 A(1)、A(2)、A(3)、A(4)、A(5)都为真 于是有 xA(x)A(1)A(2)A(3)A(4)A(5),带量词的公式在论域内的展开式,例2.11 令A(x)：表示x是整数，B(x)：表示x是奇数，设论域是1,2,3,4,5，谓词公式xB(x)表示论域内有些客体是奇数，显然公式xB(x)的真值也为真，因为 B(1)、B(3)、B(5)的真值为真，于是有 xB(x)B(1)B(3)B(5)一般地，设论域为a1,a2,.,an，则 1.xA(x)A(a1)A(a2).A(an)2.xB(x)B(a1)B(a2).B(an),定义2.7 一个解释 I 由下列4部分组成：(1)非空个体域DI。(2)DI中一些特定元素的集合a1,a2,ai,.(3)DI上特定函数集合fin|i,n 1.(4)DI上特定谓词的集合Fin|i,n 1.所谓一个解释不外乎指定个体域、个体域中一些特定的元素、特定的函数和谓词等,2.2 一阶逻辑合式公式及解释,例2.12：给定解释I如下：求下列各式的真值(1)DI=2,3；(2)DI中的特定元素 a=2；(3)DI上的函数f(x)为f(2)=3,f(3)=2;(4)DI上的谓词F(x)为F(2)=0,F(3)=1;.G(x,y)为G(i,j)=1 i,j=2,3 G(2,3)=G(3,2)=G(2,2)=1,G(3,3)=1;L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0;(1)x(F(x)G(x,a)解 x(F(x)G(x,a)(F(2)G(2,2)(F(3)G(3,2)(0 1)(11)0,例2.12：给定解释I如下：求下列各式的真值(1)DI=2,3；(2)DI中的特定元素 a=2；(3)DI上的函数f(x)为f(2)=3,f(3)=2;(4)DI上的谓词F(x)为F(2)=0,F(3)=1;.G(x,y)为G(i,j)=1 i,j=2,3 G(2,3)=G(3,2)=G(2,2)=1,G(3,3)=1;L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0;(2)x(F(f(x)G(x,f(x)x(F(f(x)G(x,f(x)(F(f(2)G(2,f(2)(F(f(3)G(3,f(3)(11)(01)1,例2.12：给定解释I如下：求下列各式的真值(1)DI=2,3；(2)DI中的特定元素 a=2；(3)DI上的函数f(x)为f(2)=3,f(3)=2;(4)DI上的谓词F(x)为F(2)=0,F(3)=1;.G(x,y)为G(i,j)=1 i,j=2,3 G(2,3)=G(3,2)=1,G(3,3)=1;L(x,y)为L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0;解(3)xyL(x,y)x(L(x,2)L(x,3)(L(2,2)L(2,3)(L(3,2)L(3,3)11 1 规律：用 用,公式类型 若一公式在任何解释下都是真的，称 该公式为逻辑有效的，或永真的。若一公式在任何解释下都是假的，称 该公式为矛盾式，或永假式。若一公式至少存在一个解释使其为真，称该公式为可满足式。,与命题公式中分类一样，谓词公式也分为三种类型，即 逻辑有效式（或重言式）、矛盾式（或永假式）可满足式。,例2.13：给定解释N如下：(1)个体域为自然数集合DN；(2)DN中的特定元素 a=0；(3)DN上的函数f(x,y)=x+y,g(x,y)=xy;(4)DN上的谓词F(x,y)为x=y;在解释N下,下面哪些公式为真？哪些公式为假？(1)xF(g(x,a),x);(2)xy(F(f(x,a),y)F(f(y,a),x)；(3)xyzF(f(x,y),z);(4)xyF(f(x,y),g(x,y);(5)F(f(x,y),f(y,z);,例2.13：给定解释N如下：(1)个体域为自然数集合DN；(2)DN中的特定元素 a=0；(3)DN上的函数 f(x,y)=x+y,g(x,y)=xy;(4)DN上的谓词F(x,y)为 x=y;在解释N下,公式分别化为：(1)xF(g(x,a),x)x F(g(x,0),x)x F(x0,x)x(0=x)这是假命题,例2.13：给定解释N如下：(1)个体域为自然数集合DN；(2)DN中的特定元素 a=0；(3)DN上的函数 f(x,y)=x+y,g(x,y)=xy;(4)DN上的谓词F(x,y)为x=y;在解释N下,公式分别化为：(2)xy(F(f(x,a),y)F(f(y,a),x)xy(F(x+0,y)F(y+0,x)xy(x+0=yy+0=x)xy(x=yy=x)这是真命题,例2.13：给定解释N如下：(1)个体域为自然数集合DN；(2)DN中的特定元素 a=0；(3)DN上的函数 f(x,y)=x+y,g(x,y)=xy;(4)DN上的谓词F(x,y)为x=y;在解释N下,公式分别化为：(3)xyz(F(f(x,y),z)xyz(F(f(x,y),z)xyz(F(x+y,z)xyz(x+y=z)这是真命题,例2.13：给定解释N如下：(1)个体域为自然数集合DN；(2)DN中的特定元素 a=0；(3)DN上的函数 f(x,y)=x+y,g(x,y)=xy;(4)DN上的谓词 F(x,y)为 x=y;解(4)xyF(f(x,y),g(x,y)xyF(x+y,xy)xy(x+y=xy)这是假命题(5)F(f(x,y),f(y,z)F(x+y,y+z)它的真值不确定 x+y=y+z 因而不是命题,定义2.8 设A为一公式,若A在任何解释下均为真则称A为永真式(逻辑有效式)。若A在任何解释下均为假,则称A为矛盾式(永假式)。若至少存在一个解释使A为真，则称A为可满足式。在一阶逻辑里面，由于公式的复杂性和解释的多样性，迄今为止还没有一种能判断任意一个公式是否可满足的或不可满足的算法。,2.2 一阶逻辑合式公式及解释,定义2.9 设A0是含p1,p2,pn 命题变项的命题公式，A1,A2,An 是n个谓词公式，用Ai(1 i n)处处代替A0 中的pi，所得公式A称为A0 的代换实例。重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。如：F(x)G(x)xF(x)xG(x)等都是 p q 的代换实例,2.2 一阶逻辑合式公式及解释,例2.14 判断下列公式的类型1.(xF(x)y G(y)yG(y)xF(x)2.(xF(x)xF(x)(yG(y)yG(y)解：1.(pq)q p 永真式2.(p p)(q q)矛盾式,2.2 一阶逻辑合式公式及解释,例2.15 判断下列各公式的类型。(1)F(x,y)(G(x,y)F(x,y)代换实例 p(q p)重言式(2)x(F(x)F(x)y(G(y)G(y)代换实例(p p)(q q)矛盾式 或 蕴涵式前件x(F(x)F(x)为1，蕴涵式后件y(G(y)G(y)为0，所以为矛盾式。,2.2 一阶逻辑合式公式及解释,(3)x y(P(x,y)P(x,y)令个体域为实数集,因为对实数集中任取一组x,y公式 P(x,y)P(x,y)总是假，所以 x y(P(x,y)P(x,y)为矛盾式。(4)(x F(x)y G(y)y G(y)代换实例(p q)q 矛盾式(5)x y F(x,y)x y F(x,y)取解释I为:个体域是整数集Z，F(x,y):x=10+y 则x y F(x,y)x y F(x,y)前件x y(x=10+y)为真 后件x y(x=10+y)为假 所以蕴涵式为假，为矛盾式,(5)x y F(x,y)x y F(x,y)取解释I为:个体域是自然数N，F(x,y):x y。x y F(x,y)xyF(x,y)前件x y(x y)为真 后件x y(x y)为真 所以蕴涵式为真,为重言式(5)x y F(x,y)x y F(x,y)取解释I为:个体域是自然数N，F(x,y):x y。x y F(x,y)xyF(x,y)前件x y(x y)为假 后件xy(x y)为假 所以蕴涵式真,为重言式 综上所述(5)中公式在不同的解释下真值不同,可见 x y F(x,y)x y F(x,y)是非逻辑有效式的可满足式。见P42例2.9（5）,例2.16 给定解释I 如下:(a)个体域 D=N(b)(c)(d)谓词说明下列公式在 I 下的涵义,并讨论真值(1)xF(g(x,a),x),x(2x=x)假命题,(2)xy(F(f(x,a),y)F(f(y,a),x),xy(x+2=yy+2=x)假命题,(3)xyzF(f(x,y),z),两点说明:5个小题都是闭式,在I下全是命题(3)与(5)说明，量词顺序不能随意改变,(5)xyzF(f(y,z),x),xyz(y+z=x)假命题,(4)xF(f(x,x),g(x,x),x(2x=x2)真命题,xyz(x+y=z)真命题,(a)个体域 D=N(b)a=2(c)f(x,y)=x+y,g(x,y)=xy(d)谓词 F(x,y):x=y,一阶逻辑等值式在一阶逻辑中，有些命题可以有不同的符号化形式。如：没有不能表示为分数的有理数。令H(x):x是有理数。W(x):x能表示成分数。则：(1)x(H(x)W(x)（2）x(H(x)W(x)均正确。同命题逻辑一样,我们称(1)、(2)是等值的。,2.3 一阶逻辑等值式,定义2.10设A，B是一阶逻辑中任意两个公式，若A B为重言式，则称A与B是等值的，记作A B。称A B是等值式。已经得证的重要等值式：第一组：(1)x F(x)x F(x)(2)xy(F(x,y)G(x,y)xy(F(x,y)G(x,y)(3)F(x)G(y)F(x)G(y)(4)x(F(x)G(y)zL(z)x(F(x)G(y)zL(z),2.3 一阶逻辑等值式,第二组：1.消去量词等值式设个体域为有限集D=a1，a2，an，则(1)x A(x)A(a1)A(a2)A(an)(2)x A(x)A(a1)A(a2)A(an)定理2.1 量词否定等值式设A(x)是任意的含自由出现个体变项x的公式，则(1)x A(x)x A(x)(2)x A(x)x A(x),2.3 一阶逻辑等值式,定理2.1 量词否定等值式的证明xA(x)xA(x)xA(x)xA(x)对这两个公式可以证明如下：证明：设论域为a1,a2,.,an，则 xA(x)(A(a1)A(a2).A(an)A(a1)A(a2).A(an)xA(x)类似可以证明另一个公式。从这两个公式，可以总结出如下规律：将量词前的“”移到量词的后边，或者将量词后的“”移到量词的前边时，量词也随着改变，如果原来是全称量词改成存在量词，如果原来是存在量词改成全称量词。所以我们也把这两个公式称为量词转换公式。,定理2.2 量词辖域收缩与扩张等值式 设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则(1)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(B A(x)(B x A(x),2.3 一阶逻辑等值式,证明:x(A(x)B)x(A(x)B)证法1:右边 x A(x)B(A(a1)A(an)B(A(a1)A(an)B(A(a1)B)(A(an)B)(A(a1)B)(A(an)B)x(A(x)B),设论域为a1,a2,.,an,证法2: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.2 量词辖域收缩与扩张等值式 设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则(2)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(B A(x)B x A(x),2.3 一阶逻辑等值式,上述公式我们只证明三个。证明：设论域为a1,a2,.,an，xA(x)B(A(a1)A(a2).A(an)B(A(a1)B)(A(a2)B).(A(an)B)x(x)BxA(x)BxA(x)x(BA(x)x(BA(x)xA(x)BxA(x)BxA(x)B x(A(x)B)x(A(x)B)要特别注意,量词的辖域扩充后,量词发生了变化,定理2.3 量词分配等值式 设A(x)、B(x)是任意的含自由出现个体变项x的公式，则(1)x(A(x)B(x)x A(x)x B(x)(2)x(A(x)B(x)x A(x)x B(x)我们称(1)为对的分配；(2)为对的 分配但注意为对及为对都不存在分配等值式,2.3 一阶逻辑等值式,x(A(x)B(x)x A(x)x B(x)证明：设论域为a1,a2,.,an，x(A(x)B(x)(A(a1)B(a1)(A(a2)B(a2)(A(an)B(an)(A(a1)A(a2).A(an)(B(a1)B(a2).B(an)xA(x)xB(x),例2.16：证明：(P47 例2.10)(1)x(A(x)B(x)x A(x)x B(x)(2)x(A(x)B(x)x A(x)x B(x)证（1）只需证明 x(A(x)B(x)xA(x)xB(x)不是永真式。设个体域D为自然数，A(x):x是奇数,B(x):x是偶数。所以x(A(x)B(x)为真,xA(x)xB(x)为假 于是（1）为假。所以不是永真式（2）只需证明 x(A(x)B(x)xA(x)xB(x)不是永真式。设个体域D为自然数,A(x):x是奇数。B(x):x是偶数 此时x(A(x)B(x)为假，xA(x)xB(x)为真，于是（2）为假。所以不是永真式,例2.17：证明下列各式为等值式。(1)x(F(x)G(x)x(F(x)G(x)(2)x(F(x)G(x)x(F(x)G(x)证：(1)x(F(x)G(x)x(F(x)G(x)（量词否定等值式）x(F(x)G(x)（置换规则）x(F(x)G(x)（置换规则）注：x A(x)x A(x)x A(x)x A(x),证：(2)x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)（量词否定等值式）x(F(x)G(x)（置换规则）x(F(x)G(x)（置换规则）注：x A(x)x A(x)x A(x)x A(x),范式 与命题演算类似，在谓词演算中也有范式。范式为我们研究谓词演算公式提供了一种规范的标准形式。一个公式如果它的所有量词均非否定的出现在公式的最前面，且它们的辖域一直延伸到公式的末尾，此种形式的公式就叫前束范式。如公式 xyz(P(x)F(y,z)Q(y,z)定义2.11设A 是一个一阶逻辑公式，若A具有如下形式 Q1x1Q2x2QkxkB 则称A为前束范式,其中Qi为或,B为不含量词的公式如：xy（F(x)G(y)）H(x,y)）xy(F(x,y)G(y,z)x H(x,y,z)前束范式就是把 或 提到范式的左边(即前边）,一阶逻辑中的 任何公式都存在与之等价的前束范式。这就是说：任何公式的前束范式都是存在的，但一般不是唯一的。求法：利用前面的公式及三条变换规则（置换规则、换名规则、代替规则）即可求出与公式等值的前束范式。,2.3 一阶逻辑等值式,例2.18：求下列公式的前束范式。（1）x F(x)x G(x)解：(1)x F(x)x G(x)(量词否定等值式)x(F(x)G(x)(量词分配等值式)注意:x 在形式下可提出来,在形式下提不出来 x 在形式下可提出来,在形式下提不出来，,2.3 一阶逻辑等值式,例2.18：求下列公式的前束范式。（2）x F(x)x G(x)解(2)x F(x)y G(y)(换名规则)x F(x)y G(y)(量词否定等值式)x(F(x)y G(y)(量词辖域扩张等值式)x y(F(x)G(y)(量词辖域扩张等值式)注：x 与y的辖域不同所以可提出来,2.3 一阶逻辑等值式,例2.18：求下列公式的前束范式。（3）x F(x)x G(x)解：x F(x)y G(y)(换名规则)x y(F(x)G(y)(4)x F(x)x G(x)解：x F(x)y G(y)(换名规则)x y(F(x)G(y),2.3 一阶逻辑等值式,至此，下列推理即可解决：凡是人都是 要死的。苏格拉底是人。苏格拉底是要死的。设：M(x):x是人。D(x):x 是要死的。a:苏格拉底。则符号化为：x(M(x)D(x)M(a)D(a)只需证明当前件为真事,后件也为真 设前件为真,即x(M(x)D(x)与M(a)都为真 由于x(M(x)D(x)为真,有M(a)D(a)为真 由M(a)D(a)与M(a)为真,由假言推理(A B A B)得出D(a)为真 则 x(M(x)D(x)M(a)D(a)为逻辑有效式(重言式),例2.23 将“每一列火车都比某些汽车快”符号化（先分析题意，然后设好谓词、量词,同时分清是存在量词还是任意量词，再按题意连成一阶逻辑公式的形式）解：令 F(x)：x是火车 G(y)：y是汽车 H(x,y)：x比y快 此命题在一阶逻辑中表示为 x(F(x)y(G(y)H(x,y),2.4 例题分析,第二章 小结,本章重点掌握内容：1.各基本概念清楚。2.会命题符号化。3.熟练掌握等价公式和永真蕴涵式。4.会写前束范式。,The end of this part.Thanks!,