《离散数学课件第二章一阶逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学课件第二章一阶逻辑.ppt（98页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、刘师少刘师少 Tel：86613747（h）E-mail：授课:51学时 教学目标:知识、能力、素质Discrete Mathematics第二章第二章 一阶逻辑一阶逻辑2.1一阶逻辑的基本概念一阶逻辑的基本概念2.2一阶逻辑合式公式及解释一阶逻辑合式公式及解释2.3一阶逻辑等值式一阶逻辑等值式2.4一阶逻辑推理理论一阶逻辑推理理论2.5 例题分析例题分析在在命命题题逻逻辑辑中中,我我们们把把原原子子命命题题作作为为基基本本研研究究单单位位,对对原原子子命命题题不不再再进进行行分分解解,只只有有复复合合命命题题才才可可以以分分解解,揭揭示示了了一一些些有有效效的的推推理理过过程程.但但是是进进
2、一一步步研研究究发发现现，仅仅有有命命题题逻逻辑辑是无法把一些常见的推理形式包括进去是无法把一些常见的推理形式包括进去.例如例如2.1一阶逻辑的基本概念一阶逻辑的基本概念形式逻辑l形式逻辑的一般格式就是三段论。l例：苏格拉底三段论：所有的人都是要死的，苏格拉底是人，所以，苏格拉底是要死的。（1）凡人都是要死的；）凡人都是要死的；（2）苏格拉底是人；）苏格拉底是人；（3）所以苏格拉底是要死的。）所以苏格拉底是要死的。P：凡人都是要死的；：凡人都是要死的；Q：苏格拉底是人：苏格拉底是人;R：所以苏格拉底是要死的。：所以苏格拉底是要死的。(PQ)R（前提）（前提）（前提）（前提）（结论）（结论）苏格
3、拉底三段论苏格拉底三段论这不是重言式这不是重言式(110),即即r不是前提不是前提p,q的有效结论的有效结论.这反映了命题逻辑的局限性这反映了命题逻辑的局限性,其原因是把本来有内其原因是把本来有内在联系的命题在联系的命题p,q,r,视为独立的命题。视为独立的命题。原因：命题逻辑不考虑命题之间的内在联系原因：命题逻辑不考虑命题之间的内在联系和数量关系。和数量关系。要要反反映映这这种种内内在在联联系系，就就要要对对命命题题逻逻辑辑进进行行分分析析,分分析析出出其其中中的的个个体体词词、谓谓词词和和量量词词，再再研研究究它它们们之之间间的的逻逻辑辑关关系系，总总结结出出正正确确的的推推理理形形式式和
4、和规规则则，这这就就是是一一阶阶(谓谓词词)逻辑的研究内容。逻辑的研究内容。办法：将命题再次细分。办法：将命题再次细分。2.1一阶逻辑的基本概念一阶逻辑的基本概念 解决这个问题的方法：在表示命题时，既表示出主语，也表示出谓语，就可以解决上述问题。这就提出了谓词的概念(谓词是用来刻划个体词的性质或事物之间的关系的词,谓词S(x)相当于一个函数).2.1.1 个体、谓词和命题函数在谓词逻辑中，将原子命题分解为谓词和个体两部分。1、定义：在原子命题中，所描述的对象称为个体；用以描述个体的性质或个体间关系的部分，称为谓词。2.1一阶逻辑的基本概念例例2.12.1：分析下列个命题中的个体和谓词：分析下列
5、个命题中的个体和谓词1.是无理数。是无理数。2.张三与李四同在信息技术学院。张三与李四同在信息技术学院。3.x与与y的和等于的和等于z（x，y，z是确定的数）。是确定的数）。4.的平方是非负的。的平方是非负的。5.所有的实数的平方都是非负的。所有的实数的平方都是非负的。6.有一个比有一个比21000大的素数。大的素数。（1）是无理数。解：个体：（代表圆周率）谓词：是无理数，表示“”的性质。（2）张三与李四同在信息技术学院。解：个体：张三，李四 谓词：与同在信息技术学院 表示“张三”与“李四”之间的关系。个体：李四谓词：张三与 同在信息技术学院表示“李四”的性质。个体：张三谓词：与李四同在信息技
6、术学院，表示“张三”的性质。（3 3）x x 与与 y y 的和等于的和等于 z z （x x，y y，z z是确定的数）是确定的数）个体：个体：x x、y y、z z谓词：谓词：与与的和等于的和等于个体：个体：x x、z z谓词：谓词：与与y y的和等于的和等于个体：个体：y y谓词：谓词：x x与与的和等于的和等于z z谓词可以单个个体的性质，也可以表示二个个体词之间的关系或性质，分别称为一元谓词和二元谓词。表示n个个体间的关系或性质的谓词称为n元谓词（4）的平方是非负的。解：个体：谓词：的平方是非负的个体：的平方谓词：是非负的（5）所有的实数的平方都是非负的。个体：每一个实数谓词：的平方
7、是非负的（6）有一个比21000大的素数。个体：一个素数谓词：比21000大“所有”是什么？量词：所有“有一个有一个”是什么是什么？量词：有一个量词：有一个2.1.1 2.1.1 个体与个体变元基本概念个体与个体变元基本概念个体：能够独立存在的事物，称之为个体，也称之为客体。它可以是具体的，也可以是抽象的事物。通常用小写英文字母a、b、c、.表示。例如，小张、小李、8、a、杭州、社会主义等等都是个体。个体变项：用小写英文字母x、y、z.表示任何个体词，则称这些字母为个体变项。注意：个体变项本身不是个体。2.1.2 谓词 定义：一个大写英文字母后边有括号，括号内是若干个个体变项，用以表示个体的属
8、性或者个体之间的关系，称之为谓词。如果括号内有n个个体变项，称该谓词为n元谓词。一般地 P(x1,x2,xn)是n元谓词。（1）张三是个大学生解：个体：张三谓词：是个大学生。若 用 P 表示谓词：“是个大学生”;a 表示个体：“张三”。则上述命题可表示为P（a）。同理：“李四是个大学生”，若b表示个体“李四”，则该命题可表示为P（b）。对于给定的命题，当用表示其个体的小写字母和表示其谓词的大写字母来表示时，规定将小写字母写在大写字母右侧的（）内。例2.2 用谓词表示下列命题（2）陈强与陈佩斯是父子解：a 表示：陈强b 表示：陈佩斯若用 Q 表示二元谓词：与 是父子则上述命题可表示为Q（a，b）
9、。又如，若用 R 表示三元谓词 “位于与之间”，则命题“杭州位于南京和上海之间”如何表示？a：杭州，b：南京，c：上海，则上述命题可表示为R（a，b，c）。2.1.3 2.1.3 命题函数命题函数 谓词本身并不是命题，只有谓词的括号内填入足够谓词本身并不是命题，只有谓词的括号内填入足够的个体，才变成命题。的个体，才变成命题。设设 H(x)H(x)是谓词是谓词 表示表示 x“x“能够到达山顶能够到达山顶”，l l 表示个体李四，表示个体李四，t t 表示老虎，表示老虎，c c 表示汽车，表示汽车，那么那么H H（l l），），H H（t t），），H H（c c），等分别表示各），等分别表示各个
10、不同的命题：但它们有一个共同的形式，个不同的命题：但它们有一个共同的形式，即即 H H（x x）当当 x x 分别取分别取 l l、t t、c c 时时就表示就表示“李四能够到达山顶李四能够到达山顶”，“老虎能够到达山顶老虎能够到达山顶”，“汽车能够到达山顶汽车能够到达山顶”。可见可见,在谓词的括号内填入不同的内容在谓词的括号内填入不同的内容,就得到不同就得到不同的命题，故谓词相当于一个函数，的命题，故谓词相当于一个函数，称之为命题函数。称之为命题函数。n n元谓词元谓词P(x1,x2,xn)P(x1,x2,xn)称之为简单命题函数。称之为简单命题函数。规定：当命题函数规定：当命题函数P(x1
11、,x2,xn)P(x1,x2,xn)中中 n=0 n=0 时，即时，即0 0元谓词，表示不含有客体变元的谓词，它本身就是元谓词，表示不含有客体变元的谓词，它本身就是一个命题变元。一个命题变元。将若干个简单命题函数用逻辑联结词联结起将若干个简单命题函数用逻辑联结词联结起来，构成的表达式，称之为复合命题函数。来，构成的表达式，称之为复合命题函数。简单命题函数与复合命题函数统称为命题函数。简单命题函数与复合命题函数统称为命题函数。例如例如:给定简单命题函数：给定简单命题函数：A(x)A(x)：x x身体好，身体好，B(x)B(x)：x x学习好，学习好，C(x)C(x)：x x工作好，工作好，复合命
12、题函数复合命题函数 A(x)(A(x)(B(x)B(x)C(x)C(x)表示如果表示如果x 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.2.
13、2.2.3 3 3 3 用谓词用谓词用谓词用谓词(命题函数命题函数命题函数命题函数)分别表示分别表示分别表示分别表示x x x x是负整数及是负整数及是负整数及是负整数及x x x x 是是是是非负整数非负整数非负整数非负整数 设设N N（x x）：）：“x x是负数是负数”,E(x)”,E(x)：“x x是整数是整数”则复合命题函数则复合命题函数 N N（x x）E E（x x）表示：）表示：“x x是负整数是负整数”N N（x x）E E（x x）表示：）表示：“x x 是非负整数是非负整数”通常通常,对于一个命题函数对于一个命题函数 Q Q（x x，y y）若若 Q Q（x x，y y）
14、：）：表示表示“x x 比比 y y 重重”，当，当 x x，y y 指人或物时，它是一个命题，但若指人或物时，它是一个命题，但若x x，y y 指指实数时，实数时，Q Q（x x，y y）就不是一个命题。）就不是一个命题。命题函数不是一个命题，只有个体变元取命题函数不是一个命题，只有个体变元取特定名称时，才能成为一个命题。但是个体变元特定名称时，才能成为一个命题。但是个体变元在那些范围内取特定的值，对是否成为命题及命在那些范围内取特定的值，对是否成为命题及命题的真值即有影响。题的真值即有影响。比如比如:设设R R（x x）：）：“x x 是大学生是大学生”，对，对x x的取值情况的取值情况:
15、l如果如果 x x 的讨论范围为浙江中医药大学里班级中的学的讨论范围为浙江中医药大学里班级中的学生，则生，则R R（x x）是永真式。）是永真式。l如果如果 x x 的讨论范围为杭州长河高级中学里班级中的的讨论范围为杭州长河高级中学里班级中的学生，则学生，则R R（x x）是永假式。）是永假式。l如果如果 x x 的讨论范围为一个剧院中的观众，观众中有的讨论范围为一个剧院中的观众，观众中有大学生也有非大学生，那么对于某些观众，大学生也有非大学生，那么对于某些观众，R R（x x）为真，对于另一些观众，为真，对于另一些观众，R R（x x）为假。）为假。命题函数确定为命题，与个体变元的论述范围有
16、命题函数确定为命题，与个体变元的论述范围有关。关。再如再如令令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
17、是大学生，论域是:人类。G(x,y)：xy，论域是:实数。论域是一个集合。l定义：由所有个体构成的论域，称之为全总个体域。它是个“最大”的论域。l约定:对于一个命题函数，如果没有给定论域，则假定该论域是全总个体域。例例2.4用谓词用谓词(命题函数命题函数)将下列命题符号化：将下列命题符号化：(1)丘华和李兵都是学生；丘华和李兵都是学生；(2)2既是偶数又是素数；既是偶数又是素数；(3)如果张华比黎明高，黎明比王宏高，则张华比王如果张华比黎明高，黎明比王宏高，则张华比王宏高。宏高。解解(1)设个体域是人的集合。设个体域是人的集合。P(x)：:x是学生。是学生。a：丘华丘华b：黎兵黎兵该命题符号化
18、为该命题符号化为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 量词例如：有些人是大学生。所有事物都是发展变化的。“有些”,“所有的”,就是对客体量化的词。量
19、词：在命题中表示对客体数量化的词。定义了两种量词：(1).存在量词：记作，表示“有些”、“一些”、“某些”、“至少一个”等。(2).全称量词：记作，表示“每个”、“任何一个”、“一切”、“所有的”、“凡是”、“任意的”等。考察下面两个例子考察下面两个例子 (它们均以整数作为其个体域它们均以整数作为其个体域)(x+1)(x+1)2 2=x=x2 2+2x+1+2x+1 x+6=5 x+6=5 对对于于任任何何整整数数代代入入后后等等式式总总是是成成立立。用用符符号号“x”x”表示表示“对所有对所有x”x”，则则可表示为可表示为 x(x(x+1)(x+1)2 2=x=x2 2+2x+1)+2x+1
20、)但但则不然，只存在一个整数（则不然，只存在一个整数（-1-1）代入后才使）代入后才使等式成立号等式成立号“x x ”表示表示“存在某些存在某些x”,x”,则则 可表示为可表示为 x x（x+6=5x+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.52.5 试用量词、谓词表示下列命题试用量词、谓词表示下列命题试用量词
21、、谓词表示下列命题试用量词、谓词表示下列命题（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.62.6试用量词、谓词表示下列命题试用量词、谓词表示下列命题试用量词、谓词表示下列命题试用量词、谓词表示下列命题特别注意：特别注意：谓词前加上了量词，称为谓词的量谓词前加上了量词，称为谓词的量化。若一个谓词中所有个体
22、变元都量化了，则化。若一个谓词中所有个体变元都量化了，则该谓词就变成了命题。这是因为在谓词被量化该谓词就变成了命题。这是因为在谓词被量化后，可以在整个个体域中考虑命题的真值了。后，可以在整个个体域中考虑命题的真值了。这如同数学中的函数这如同数学中的函数f(x)，的值是不的值是不确定的，但确定的，但可确定其值。可确定其值。说明：说明：（1）分分析析命命题题中中表表示示性性质质和和关关系系的的谓谓词词，要要分分别符号化为一元和别符号化为一元和n(n2)元谓词。元谓词。（2）根据命题的实际意义选用）根据命题的实际意义选用 或或 。（3）一一般般来来说说，当当多多个个量量词词同同时时出出现现时时，它它
23、们们的顺的顺序不能随意调换。如：序不能随意调换。如：在实数域上用在实数域上用L(x,y)表示表示x+y=10命题为：命题为：对于任意的对于任意的x,都存在都存在y使得使得x+y=10。可符号化为：可符号化为：x yL(x,y)真值为真值为1。若调换顺序后为：若调换顺序后为：y xL(x,y)真值为真值为0。2.1 一阶逻辑的基本概念一阶逻辑的基本概念说明：说明：（4）有些命题的符号化形式不止一种。）有些命题的符号化形式不止一种。至此，至此，下列推理即可解决：下列推理即可解决：凡是人都是凡是人都是要死的。要死的。苏格拉底是人。苏格拉底是人。苏格拉底是要死的。苏格拉底是要死的。设设：M(x):x是
24、是人人。D(x):x是是要要死死的的。a:苏苏格格拉拉底。则符号化为：底。则符号化为：x(M(x)x(M(x)D(x)(x)M(a)M(a)D(a)D(a)2.1 一阶逻辑的基本概念一阶逻辑的基本概念定义定义2.1一阶语言的字母表定义如下：一阶语言的字母表定义如下：（1）个体常项：表示具体的或特定的个体的词）个体常项：表示具体的或特定的个体的词常用常用a,b,c,ai,bi,ci，i1.1.（2）个体变项：表示抽象的或泛指个体的词个体变项：表示抽象的或泛指个体的词常用常用x,y,z,xi,yi,zi，i1.1.（3）函数符号：函数符号：f,g,h,fi,gi,hi，i1.1.（4）谓词符号：谓
25、词符号：F,G,H,Fi,Gi,Hi，i1.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
26、元元谓谓词词,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)便是表示便是表
27、示“张强的父亲是教授张强的父亲是教授”这一命题。这一命题。函数的使用给谓词表示带来很大方便。函数的使用给谓词表示带来很大方便。例如，用谓词表示命题：例如，用谓词表示命题：对任意整数对任意整数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 1）原子公式是公式）原子公式是公式（2 2）如果）如果A A，B B是公式，则（是公式，则（A A），（），（A
28、BAB），），（ABAB），（），（A AB B），（），（A AB B）是公式；）是公式；（3 3）如）如A A为公式，为公式，x x为个体变元，则（为个体变元，则（x xA A），），（x xA A）为公式；）为公式；（4 4）公式由且仅由有限次使用（）公式由且仅由有限次使用（1 1），（），（2 2），（），（3 3）而得。而得。注：量词后面若有括号，则不能省略。注：量词后面若有括号，则不能省略。2.2一阶逻辑公式及解释一阶逻辑公式及解释例例2.9将下列命题表示为谓词公式将下列命题表示为谓词公式（1）所有正数均可开平方）所有正数均可开平方（2）有些人是大学生）有些人是大学生(3)(3)猫
29、必捕鼠猫必捕鼠解：解：（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)猫必捕鼠猫必捕鼠解：解：(3)(3)设设 C C（x x）：）：“x x是猫是猫”，R R（y y）：）：“y y是鼠是鼠”，A A（x x，y y）：）：“x x捕捕y”y”，则语句可表示为：则语句可表示为：x x y y（C C（x x）R R（y y）A A（x x，y y）凡是与某一
30、范围有关的对象应用量词来描述。凡是与某一范围有关的对象应用量词来描述。例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)(2)并非每个实数都是有理数。并非每个实数都是有理数。R R（x x）,Q,Q（x x）解：解：（x x（R R（x x）Q Q（x x）(3)(3)没有不犯错误的人。没有不犯错误的人。F F（x x）,M,M（x x）解：解：（x x（F F（x x）M M（x x）(4)(4)尽管有人聪明，但
31、未必一切人都聪明。尽管有人聪明，但未必一切人都聪明。M M（x x）,x,x是人是人,P,P（x x）,x,x聪明聪明 解：解：x x(（M(M(x x）P(P(x x）一、约束变元、与自由变元与指导变元、辖域一、约束变元、与自由变元与指导变元、辖域在一个谓词公式中，形如在一个谓词公式中，形如 xA（x）或或 xA（x）的那一部分称为公式的约束部分，的那一部分称为公式的约束部分，在公式在公式 xA（x）和和 xA（x）中称）中称x为指导变元为指导变元而而A（x）称为量词（）称为量词（x或或 x）的作用域或辖域。）的作用域或辖域。在作用域中在作用域中x的任一出现，称为的任一出现，称为x在公式中的
32、约在公式中的约束出现，束出现，x称为约束变元。若在公式中的出现不是约称为约束变元。若在公式中的出现不是约束出现，则称束出现，则称x的出现为自由出现，自由出现的变元的出现为自由出现，自由出现的变元称为自由变元。称为自由变元。2.3 2.3 约束变元与自由变元约束变元与自由变元约束变元与自由变元约束变元与自由变元1.1.x x（P P（x x）y Qy Q（x x，y y）2.2.x Hx H（x x）L L（x x，y y）3.3.x x y y（P P（x x，y y）Q Q（y y，z z）x Rx R（x x、y y）说明：说明：（1 1）若量词后有括号，则括号内的子公式就是该量词）若量词
33、后有括号，则括号内的子公式就是该量词的辖域；的辖域；（2 2）若量词后无括号，则与量词邻接的子公式为该量）若量词后无括号，则与量词邻接的子公式为该量词的辖域；词的辖域；例例例例2.11 2.11 2.11 2.11 指出下列公式的辖域和变元约束的情况指出下列公式的辖域和变元约束的情况指出下列公式的辖域和变元约束的情况指出下列公式的辖域和变元约束的情况1.x（P（x）yQ（x，y）解：解：x的辖域是（的辖域是（P（x）yQ（x，y），对于），对于x的的辖域而言，辖域而言，x的所有出现均为约束出现，故它是约的所有出现均为约束出现，故它是约束变元。束变元。y的辖域是的辖域是Q（x，y），对于），对于
34、 y的辖域而言，的辖域而言，y的的出现为约束出现，故它是约束变元。出现为约束出现，故它是约束变元。例例例例2.11 2.11 2.11 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被量词被量
35、词 x约约束，而不是被量词束，而不是被量词 x约束。约束。实际上，上述公式等价于：实际上，上述公式等价于：x（F（x）y（G（y）F（y）在使用谓词逻辑公式符号化命题时，要小心地选择变元，在使用谓词逻辑公式符号化命题时，要小心地选择变元，以使得到的公式满足上述两个条件。以使得到的公式满足上述两个条件。2.xH（x）L（x，y）解：解：x的辖域是的辖域是H（x）,x是约束出现是约束出现,故故x为约束变元为约束变元在在L（x，y）中）中x，y均为自由出现，均为自由出现，故对于整个公式来说，故对于整个公式来说，x既为约束变元，又为既为约束变元，又为自由变元，自由变元，y为自由变元。为自由变元。例例例
36、例2.11 2.11 2.11 2.11 指出下列公式的辖域和变元约束的情况指出下列公式的辖域和变元约束的情况指出下列公式的辖域和变元约束的情况指出下列公式的辖域和变元约束的情况3.3.x x y y（P P（x x，y y）Q Q（y y，z z）x Rx R（x x、y y）解：解：x x y y 的辖域均为（的辖域均为（P P（x x，y y）Q Q（y y，z z），其中，），其中，x x、y y均为约束出现，故是约束变元，均为约束出现，故是约束变元，z z是自由变元。是自由变元。x x的辖域为的辖域为R R（x x、y y），），x x为约束出现，故是约束变元，为约束出现，故是约束变
37、元，y y为自由出现，故是自由变元。为自由出现，故是自由变元。在整个公式中，在整个公式中，x x是约束变元，是约束变元，y y既是约束变元，既是约束变元，又是自由变元，又是自由变元，z z是自由变元。是自由变元。例例例例2.11 2.11 2.11 2.11 指出下列公式的辖域和变元约束的情况指出下列公式的辖域和变元约束的情况指出下列公式的辖域和变元约束的情况指出下列公式的辖域和变元约束的情况换名规则换名规则 设设A A是一公式，将是一公式，将A A中某个辖域中中某个辖域中约束变项约束变项的的所有出现及相应的所有出现及相应的指导变元指导变元，改成该量词辖域中，改成该量词辖域中未曾出现的某个个体
38、变项符号，公式中其它部分未曾出现的某个个体变项符号，公式中其它部分不变，设所得公式为不变，设所得公式为A,A,则则 A A A A。代替规则代替规则 设设A A是一公式，将是一公式，将A A中某个中某个自由出现自由出现的个体变的个体变项所有出现用项所有出现用A A中未曾出现的个体变项符号代替中未曾出现的个体变项符号代替，A A中其它部分不变，设所得公式为中其它部分不变，设所得公式为A,A,则则 A A A A。2.2一阶逻辑合式公式及解释一阶逻辑合式公式及解释 注意：注意：在一公式中，有的个体变元既可以在一公式中，有的个体变元既可以是约束出现，又可以是自由出现，这就容易产是约束出现，又可以是自
39、由出现，这就容易产生混淆。为了避免混淆，采用下面两个规则：生混淆。为了避免混淆，采用下面两个规则：约束约束出现用换出现用换名规则，将量词辖域中某个约名规则，将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。域中未曾出现过的个体变元，其余不变。例例 x F(x)x F(x)G(x,y)(G(x,y)(换名规则换名规则,将约束出现将约束出现 z zF(F(z z)G(x,y)G(x,y)的的x x改成改成z)z)自由变元代入规则，对某自由出现的个自由变元代入规则，对某自由出现的个体变元可用个体常元或用与原子公式中所
40、有个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入。体变元不同的个体变元去代入，且处处代入。例例 xF(x)G(x,y)(代替规则代替规则,将自由出现将自由出现 x F(x)G(z,y)的的x改成改成z)换名规则换名规则是替换约束变项及相应的指导变元。是替换约束变项及相应的指导变元。代替规则代替规则是代替自由出现的个体变项是代替自由出现的个体变项例例 x x y(R(x,y)L(y,z)y(R(x,y)L(y,z)x H(x,y)x H(x,y)x x y(R(x,y)L(y,z)y(R(x,y)L(y,z)t tH(H(t t,y),y)(换名规则换名规则t)
41、t)x x y(R(x,y)L(y,z)y(R(x,y)L(y,z)t t H(H(t t,w),w)(代替规则代替规则 w)w)该公式中，该公式中，不存在既是不存在既是约束出现约束出现，又是又是自由出现自由出现的个体变项。的个体变项。换名规则换名规则换名规则换名规则代入规则代入规则代入规则代入规则对对对对象象象象约束变元约束变元约束变元约束变元自由变元自由变元自由变元自由变元范范范范围围围围一个量词及其辖域内一个量词及其辖域内一个量词及其辖域内一个量词及其辖域内整个公式整个公式整个公式整个公式结结结结果果果果只能换名为另一变元只能换名为另一变元只能换名为另一变元只能换名为另一变元,而不能换名
42、为个体常而不能换名为个体常而不能换名为个体常而不能换名为个体常元元元元,换名后公式的含换名后公式的含换名后公式的含换名后公式的含义不变。义不变。义不变。义不变。可以代以另一常元。公可以代以另一常元。公可以代以另一常元。公可以代以另一常元。公式由具有普遍意义变成式由具有普遍意义变成式由具有普遍意义变成式由具有普遍意义变成仅对该个体常元有意义。仅对该个体常元有意义。仅对该个体常元有意义。仅对该个体常元有意义。换名规则与代入规则的主要区别换名规则与代入规则的主要区别换名规则与代入规则的主要区别换名规则与代入规则的主要区别:公式解释公式解释一一般般情情况况下下，一一阶阶逻逻辑辑公公式式含含有有：个个体
43、体常常元元、个个体体变变元元（约约束束变变元元或或自自由由变变元元）、函函数数变变元元、为为谓谓词词变变元元等等，对对各各种种变变元元用用指指定定的的特特殊殊常常元元去去代代替替，就就构构成成了了一一个个公公式式的的解解释释。当当然然在在给给定定的的解解释释下下，可可以以对对多多个个公公式式进进行行解释。下面给出解释的一般定义。解释。下面给出解释的一般定义。2.2一阶逻辑合式公式及解释一阶逻辑合式公式及解释 带量词的公式在论域内的展开式带量词的公式在论域内的展开式 例例2.12 2.12 令令A(x)A(x)：表示：表示x x是整数是整数,B(x),B(x)：表示：表示x x是奇数，是奇数，设
44、论域是设论域是1,2,3,4,51,2,3,4,5，谓词公式谓词公式 xA(x)xA(x)表示论域内所有的客体都是整数表示论域内所有的客体都是整数 显然公式显然公式 xA(x)xA(x)的真值为真，因为的真值为真，因为 A(1)A(1)、A(2)A(2)、A(3)A(3)、A(4)A(4)、A(5)A(5)都为真都为真 于是有于是有 xA(x)xA(x)A(1)A(2)A(3)A(4)A(5)A(1)A(2)A(3)A(4)A(5)带量词的公式在论域内的展开式带量词的公式在论域内的展开式 例例2.11 2.11 令令A(x)A(x)：表示：表示x x是整数，是整数，B(x)B(x)：表示：表示
45、x x是奇数，是奇数，设论域是设论域是1,2,3,4,51,2,3,4,5，谓词公式谓词公式 xB(x)xB(x)表示论域内有些客体是奇数，表示论域内有些客体是奇数，显然公式显然公式 xB(x)xB(x)的真值也为真，因为的真值也为真，因为 B(1)B(1)、B(3)B(3)、B(5)B(5)的真值为真，的真值为真，于是有于是有 xB(x)xB(x)B(1)B(3)B(5)B(1)B(3)B(5)一般地，设论域为一般地，设论域为aa1 1,a,a2 2,.,a,.,an n，则，则 1.1.xA(x)xA(x)A(a1)A(a2).A(an)A(a1)A(a2).A(an)2.2.xB(x)x
46、B(x)B(a1)B(a2).B(an)B(a1)B(a2).B(an)定义定义2.7一个解释一个解释I由下列由下列4部分组成：部分组成：(1)非空个体域非空个体域DI。(2)DI中一些特定元素的集合中一些特定元素的集合a1,a2,ai,.(3)DI上特定函数集合上特定函数集合fin|i,n1.(4)DI上特定谓词的集合上特定谓词的集合Fin|i,n1.所谓一个解释不外乎指定个体域、个体域所谓一个解释不外乎指定个体域、个体域中一些特定的元素、特定的函数和谓词等中一些特定的元素、特定的函数和谓词等2.2一阶逻辑合式公式及解释一阶逻辑合式公式及解释 例例2.12：给定解释给定解释I如下：求下列各式
47、的真值如下：求下列各式的真值(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)=1i,j=2,3G(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)(01)(11)0例例2.12：给定解释给定解释I如下：求下列各式的真值如下：求下
48、列各式的真值(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)=1i,j=2,3G(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如下：求下列各式的真值
49、如下：求下列各式的真值(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)=1i,j=2,3G(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)x x yL(x,y)yL(x,y)x x(L(x,2)L(x,3)L(x,2)L(x,3)(L(2,2)L(2,3)L(2,2)L(2,3)(L(3,2)L(3,3)L(3,2)L(3,3)1
50、 111 1 1 规律：规律：用用 用用 公式类型公式类型若一公式在任何解释下都是真的，称若一公式在任何解释下都是真的，称该公式为逻辑有效的，或永真的。该公式为逻辑有效的，或永真的。若一公式在任何解释下都是假的，称若一公式在任何解释下都是假的，称该公式为矛盾式，或永假式。该公式为矛盾式，或永假式。若一公式至少存在一个解释使其为真若一公式至少存在一个解释使其为真，称该公式为可满足式。，称该公式为可满足式。与命题公式中分类一样，与命题公式中分类一样，谓词公式也分为三种类型，谓词公式也分为三种类型，即即逻辑有效式（或重言式）、逻辑有效式（或重言式）、矛盾式（或永假式）矛盾式（或永假式）可满足式。可满