第二章 一阶逻辑

1、2.1 一阶逻辑的基本概念一阶逻辑的基本概念2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释2.3 一阶逻辑等值式一阶逻辑等值式 在命题逻辑中在命题逻辑中,我们把原子命题作为基本我们把原子命题作为基本研究单位研究单位,对原子命题不再进行分解对原子命题不再进行分解,只有复只有复合命题才可以分解合命题才可以分解,揭示了一些有效的推理揭示了一些有效的推理过程过程. 但是进一步研究发现，仅有命题逻辑但是进一步研究发现，仅有命题逻辑是无法把一些常见的推理形式包括进去是无法把一些常见的推理形式包括进去. 例如例如2.1一阶逻辑的基本概念一阶逻辑的基本概念l形式逻辑的一般格式就是三段论。l例：苏格拉底三

2、段论：所有的人都是要死的，苏格拉底是人，所以，苏格拉底是要死的。（1）凡人都是要死的；）凡人都是要死的；（2）苏格拉底是人；）苏格拉底是人；（3）所以苏格拉底是要死的。）所以苏格拉底是要死的。p：凡人都是要死的；：凡人都是要死的；q：苏格拉底是人：苏格拉底是人;r：所以苏格拉底是要死的。：所以苏格拉底是要死的。(pq)r（前提）（前提）（前提）（前提）（结论）（结论）苏格拉底三段论苏格拉底三段论这不是重言式这不是重言式(110),即即 r 不是前提不是前提p, q的有效结论的有效结论. 这反映了命题逻辑的局限性这反映了命题逻辑的局限性,其原因是把本来有内在其原因是把本来有内在联系的命题联系的命

3、题p, q, r, 视为独立的命题。视为独立的命题。原因：命题逻辑不考虑命题之间的内在联系原因：命题逻辑不考虑命题之间的内在联系 和数量关系。和数量关系。 要反映这种内在联系，就要对命题逻要反映这种内在联系，就要对命题逻辑进行分析辑进行分析, ,分析出其中的个体词、谓词和分析出其中的个体词、谓词和量词，再研究它们之间的逻辑关系，总结出量词，再研究它们之间的逻辑关系，总结出正确的推理形式和规则，这就是一阶正确的推理形式和规则，这就是一阶( (谓词谓词) )逻辑的研究内容。逻辑的研究内容。 办法：将命题再次细分。办法：将命题再次细分。2.1一阶逻辑的基本概念一阶逻辑的基本概念 解决这个问题的方法：

4、 在表示命题时，既表示出主语，也表示出谓语，就可以解决上述问题。这就提出了谓词的概念(谓词是用来刻划个体词的性质或事物之间的关系的词,谓词S(x)相当于一个函数).2.1.1 个体、谓词和命题函数在谓词逻辑中，将原子命题分解为谓词和个体两部分。1、定义：在原子命题中，所描述的对象称为个体；用以描述个体的性质或个体间关系的部分，称为谓词。2.1一阶逻辑的基本概念例例2.12.1：分析下列个命题中的个体和谓词：分析下列个命题中的个体和谓词1. 是无理数。是无理数。2.张三与李四同在信息技术学院。张三与李四同在信息技术学院。3. x与与y的和等于的和等于z（x，y，z是确定的数）。是确定的数）。4.

5、 的平方是非负的。的平方是非负的。5.所有的实数的平方都是非负的。所有的实数的平方都是非负的。6.有一个比有一个比21000大的素数。大的素数。（1）是无理数。解： 个体：（代表圆周率） 谓词：是无理数，表示“”的性质。（2）张三与李四同在信息技术学院。解：个体：张三，李四 谓词： 与同在信息技术学院 表示“张三”与“李四”之间的关系。 个体：李四谓词：张三与 同在信息技术学院表示“李四”的性质。个体：张三谓词： 与李四同在信息技术学院，表示“张三”的性质。（3 3）x x 与与 y y 的和等于的和等于 z z （x x，y y，z z是确定的数）是确定的数）个体：个体： x x、 y y、

6、 z z谓词：谓词： 与与的和等于的和等于个体：个体： x x、 z z谓词：谓词： 与与y y的和等于的和等于个体：个体： y y谓词：谓词： x x与与的和等于的和等于z z 谓词可以单个个体的性质，也可以表示二个个体词之间的关系或性质，分别称为一元谓词和二元谓词。表示n个个体间的关系或性质的谓词称为n元谓词 （4） 的平方是非负的。 解：个体： 谓词： 的平方是非负的个体： 的平方谓词： 是非负的（5）所有的实数的平方都是非负的。个体：每一个实数谓词： 的平方是非负的（6）有一个比21000大的素数。个体：一个素数谓词： 比21000大“所有”是什么？量词：所有“有一个有一个”是什么？是

7、什么？ 量词：有一个量词：有一个2.1.1 2.1.1 个体与个体变元基本概念个体与个体变元基本概念个体：能够独立存在的事物，称之为个体，也称之为客体。它可以是具体的，也可以是抽象的事物。通常用小写英文字母a、b、c、.表示。例如，小张、小李、8、a、杭州、社会主义等等都是个体。个体变项：用小写英文字母x、y、z.表示任何个体词，则称这些字母为个体变项。注意：个体变项本身不是个体。2.1.2 谓词 定义：一个大写英文字母后边有括号，括号内是若干个个体变项，用以表示个体的属性或者个体之间的关系，称之为谓词。如果括号内有n个个体变项，称该谓词为n元谓词。 一般地 P(x1,x2,xn) 是n元谓词

8、。（1）张三是个大学生解： 个体：张三谓词：是个大学生。若 用 P 表示谓词： “ 是个大学生 ” ; a 表示个体： “ 张三 ” 。则上述命题可表示为P（a）。同理：“李四是个大学生”， 若b表示个体“李四”，则该命题可表示为P（b）。 对于给定的命题，当用表示其个体的小写字母和表示其谓词的大写字母来表示时，规定将小写字母写在大写字母右侧的（ ）内。例2.2 用谓词表示下列命题（2）陈强与陈佩斯是父子解：a 表示：陈强b 表示：陈佩斯若用 Q 表示二元谓词： 与 是父子则上述命题可表示为Q（a，b）。又如，若用 R 表示三元谓词 “位于与之间”，则命题 “杭州位于南京和上海之间” 如何表示

9、？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,P(x1,x2,xn),xn)称之为称之为简单命题函数简单命题函数。规定：当命题函数规定：当命题函数P(x1,x2,P(x1,x2,xn),xn)中中 n=0

11、n=0 时，即时，即0 0元谓词，表示不含有客体变元的谓词，它本身就是元谓词，表示不含有客体变元的谓词，它本身就是一个命题变元。一个命题变元。将若干个简单命题函数用逻辑联结词联结起将若干个简单命题函数用逻辑联结词联结起来，构成的表达式，称之为复合命题函数。来，构成的表达式，称之为复合命题函数。简单命题函数与复合命题函数统称为命题函数。简单命题函数与复合命题函数统称为命题函数。例如例如: : 给定简单命题函数：给定简单命题函数： A(x)A(x)：x x身体好，身体好， B(x)B(x)：x x学习好，学习好， C(x)C(x)：x x工作好，工作好， 复合命题函数复合命题函数 A(x)(A(x

12、)( 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等取特定的客体时， 才确定了一个命题。 设设N N（x

13、 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）：）：表示表示“ x x 比比 y y 重重 ”，当，当 x x ，y y 指人或物时，它是一个命题，但若指人或物时，它是一个命题，但若x x ，y y 指指实数时，实数时， Q Q（x x，y y）就不是一个命题。）

14、就不是一个命题。 命题函数不是一个命题，只有个体变元取命题函数不是一个命题，只有个体变元取特定名称时，才能成为一个命题。但是个体变特定名称时，才能成为一个命题。但是个体变元在那些范围内取特定的值，对是否成为命题元在那些范围内取特定的值，对是否成为命题及命题的真值即有影响。及命题的真值即有影响。 比如比如: :设设R R（x x）：）：“ x x 是大学生是大学生”，对，对x x的取值情的取值情况况: :l如果如果 x x 的讨论范围为浙江中医药大学里班级中的的讨论范围为浙江中医药大学里班级中的学生，则学生，则R R（x x）是永真式。）是永真式。l如果如果 x x 的讨论范围为杭州长河高级中学

15、里班级中的讨论范围为杭州长河高级中学里班级中的学生，则的学生，则R R（x x）是永假式。）是永假式。l如果如果 x x 的讨论范围为一个剧院中的观众，观众中的讨论范围为一个剧院中的观众，观众中有大学生也有非大学生，那么对于某些观众，有大学生也有非大学生，那么对于某些观众，R R（x x）为真，对于另一些观众，为真，对于另一些观众，R R（x x）为假。）为假。命题函数确定为命题，与个体变元的论述范围命题函数确定为命题，与个体变元的论述范围有关。有关。 再如再如 令令G(x，y)： “x高于高于y”，于是，于是，G(x，y)是一个二元谓词是一个二元谓词。将将x代以个体代以个体 “张三张三”，y

16、代以个体代以个体 “李四李四”，则则G(张三，李四张三，李四)就是命题就是命题： “张三高于李张三高于李四四”。随便将。随便将x，y代以确定的个体，由代以确定的个体，由G(x，y)都能得到一个命题。都能得到一个命题。可见，可见，G(x，y)不是命题，而是一个命题函数不是命题，而是一个命题函数即谓词即谓词。2.1.4 论域(个体域) 定义：在命题函数中个体变项的取值范围，称之为论域，也称之为个体域。 例如 S(x):x是大学生，论域是:人类。 G(x,y)：xy， 论域是:实数。 论域是一个集合。l定义：由所有个体构成的论域，称之为全总个体域。它是个“最大”的论域。l约定:对于一个命题函数，如果

17、没有给定论域，则假定该论域是全总个体域。例例2.4 用谓词用谓词(命题函数命题函数)将下列命题符号化：将下列命题符号化：(1) 丘华和李兵都是学生；丘华和李兵都是学生；(2) 2既是偶数又是素数；既是偶数又是素数；(3) 如果张华比黎明高，黎明比王宏高，则张华比王如果张华比黎明高，黎明比王宏高，则张华比王 宏高。宏高。解解 (1) 设个体域是人的集合。设个体域是人的集合。 P(x)：:x是学生。是学生。a：丘华丘华b：黎兵黎兵该命题符号化为该命题符号化为P(a) P(b)(2) 2既是偶数又是素数；既是偶数又是素数； 设个体域为正整数集合设个体域为正整数集合N。F(x)：x是偶数，是偶数，G(

18、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).存在量词：记作，表示“有些”、“一些”、“某些”、“至少一个”等。

19、(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)但但则不然，只存在一个整数（则不然，只存在一个整数（-1-1）代入后才使）代入后才使等式成立号等式成立号

20、“ 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）（1）有些人是聪明的。）有些人是聪明的。（2）并非一切数都大于）并非一切数都大于0。解：解：（1）令）令M（x）：）：x是人，是人， N（x）：）：x是聪明的是

21、聪明的 x（M（ x ） N（ x ） （2）令）令I（x） ：x 是数（实数域），是数（实数域）， R（x）：）：x 是大于零的数。是大于零的数。 （ x （ I（x） R （x） x（I（x） R （x）dx)x(fbadx)x(f特别注意：特别注意：谓词前加上了量词，称为谓词的量谓词前加上了量词，称为谓词的量化。化。若一个谓词中所有个体变元都量化了，则若一个谓词中所有个体变元都量化了，则该谓词就变成了命题。该谓词就变成了命题。这是因为在谓词被量化这是因为在谓词被量化后，可以在整个个体域中考虑命题的真值了。后，可以在整个个体域中考虑命题的真值了。这如同数学中的函数这如同数学中的函数f(x)

22、，的值是不的值是不确定的，但确定的，但 可确定其值。可确定其值。（1）分析命题中表示性质和关系的谓词，要分）分析命题中表示性质和关系的谓词，要分别符号化为一元和别符号化为一元和n(n 2)元谓词。元谓词。（2）根据命题的实际意义选用）根据命题的实际意义选用 或或 。（3）一般来说，当多个量词同时出现时，它们）一般来说，当多个量词同时出现时，它们的顺的顺 序不能随意调换。如：序不能随意调换。如： 在实数域上用在实数域上用L(x, y)表示表示x+y=10命题为：命题为： 对于任意的对于任意的x, 都存在都存在y使得使得 x+y=10。 可符号化为：可符号化为： x yL(x,y) 真值为真值为1

23、。 若调换顺序后为：若调换顺序后为： y xL(x,y) 真值为真值为0。（4）有些命题的符号化形式不止一种。）有些命题的符号化形式不止一种。至此，至此，下列推理即可解决：下列推理即可解决： 凡是人都是凡是人都是 要死的。要死的。 苏格拉底是人。苏格拉底是人。 苏格拉底是要死的。苏格拉底是要死的。设：设：M(x):x是人。是人。D(x):x 是要死的。是要死的。a:苏格拉苏格拉底。则符号化为：底。则符号化为： x(M(x)x(M(x)D(x)(x) M(a) M(a) D(a) D(a)定义定义2.1 一阶语言的字母表定义如下：一阶语言的字母表定义如下：（1）个体常项：表示具体的或特定的个体的

24、词）个体常项：表示具体的或特定的个体的词 常用常用a , b , c , ai , bi , ci，i 1.1.（2）个体变项：表示抽象的或泛指个体的词个体变项：表示抽象的或泛指个体的词 常用常用x , y , z , xi , yi , zi，i 1.1.（3）函数符号：函数符号：f , g , h , fi , gi , hi，i 1.1.（4）谓词符号：谓词符号：F, G , H,Fi , Gi , Hi，i 1.1.（5）量词符号：量词符号： ， . .（6）联结词符号：）联结词符号： ，. .（7）括号与逗号：）括号与逗号： （，），（，），. .定义定义2.2一阶语言一阶语言项项的

25、定义如下：的定义如下：(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 ) 为为原子公式原子公式。 有了项的定义，函数的概念就可用来表示个有了项的定义，函数的概念

26、就可用来表示个体常元和个体变元。体常元和个体变元。例如，令例如，令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

27、，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），（），（ABAB），）， （ABAB），（），（A AB B），（），（A AB B）是公式；）是公式；（3 3）如）如A A为公式，为公式，x x为个体变元，则（为个体变元，则（ x xA

28、A），）， （ x xA A）为公式；）为公式；（4 4）公式由且仅由有限次使用（）公式由且仅由有限次使用（1 1），（），（2 2），（），（3 3） 而得。而得。注：量词后面若有括号，则不能省略。注：量词后面若有括号，则不能省略。例例2.9 将下列命题表示为谓词公式将下列命题表示为谓词公式（1）所有正数均可开平方）所有正数均可开平方 （2）有些人是大学生）有些人是大学生 ( 3) ( 3)猫必捕鼠猫必捕鼠解：解：（1） 设设 P（x）：）： x是正数；是正数； Q（x）：）： x 可开平方可开平方则命题（则命题（1）可表示为：）可表示为： x（P（x） Q（x）（2） 设设 R（x）：）：

29、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）凡是与某一范围有关的对象应用量词来描述。凡是与某一范围有关的对象应用量词来描述。 例2.10 用谓词表示下列语句(1) 没有最大的自然数解：设N（x）：x是自

30、然数，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)尽管有人聪明，但未必一切人都聪明。尽管有人聪明，但未必一切人都聪明。 M M（x x）,x,x是人是人, P, P（

31、x x）,x,x聪明聪明 解：解： x x( (（M(M(x x）P(P(x x）一、约束变元、与自由变元与指导变元、辖域一、约束变元、与自由变元与指导变元、辖域 在一个谓词公式中，形如在一个谓词公式中，形如 x A（x） 或或 x A（x） 的那一部分称为公式的约束部分，的那一部分称为公式的约束部分， 在公式在公式 x A（x） 和和 x A（x）中称）中称x为指导变元为指导变元 而而A（x）称为量词（）称为量词（ x或或 x）的作用域或辖域。）的作用域或辖域。 在作用域中在作用域中 x 的任一出现，称为的任一出现，称为 x 在公式中的约在公式中的约束出现，束出现，x 称为约束变元。若在公式

32、中的出现不是约称为约束变元。若在公式中的出现不是约束出现，则称束出现，则称x的出现为自由出现，自由出现的变元的出现为自由出现，自由出现的变元称为自由变元。称为自由变元。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）若量词后有括号，则括号内的子公式就是该量词）若量词后有括号，则括号内的子公式就是该量词的辖域；的辖域；（2 2）若量词后无括号，则与量词邻接的子公式为该量）若量词后无括号，则与量词邻

33、接的子公式为该量词的辖域；词的辖域；例例2.11 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 2.11 指出下列公式的辖域和变元约束的情况指出下列公式的辖域和变元约束的情况 变元的辖域

34、实际上是可嵌套的，例如：公式变元的辖域实际上是可嵌套的，例如：公式 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）在使用谓词逻辑公式符号化命题时，要小心地选择变元，在使用谓词逻辑公式符号化命题时，要小心地选择变元，以使得到的公式满足上述两个条件。以使得

35、到的公式满足上述两个条件。2. x H（x）L（x，y）解：解： x 的辖域是的辖域是H（x）,x 是约束出现是约束出现,故故 x 为约束变元为约束变元在在L（x，y）中）中 x，y 均为自由出现，均为自由出现，故对于整个公式来说，故对于整个公式来说，x 既为约束变元，又为既为约束变元，又为自由变元，自由变元，y为自由变元。为自由变元。 例例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

36、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为约束出现，故是约束变元，为约束出现，故是约束变元，y y为自由出现，故是自由变元。为自由出现，故是自由变元。在整个公式中，在整个公式中，x x是约束变元，是约束变元，y y既是约束变元，既是约束变元，又是自由变元，又是自由变元，z z是自由变元。是自由变元。例例2.11 2.11 指出下列公式的辖域和变元约束的情况指出下列公式的辖域和变元约束的情况换名规则换名规则 设设A A是一公

37、式，将是一公式，将A A中某个辖域中中某个辖域中约束变项约束变项的的所有出现及相应的所有出现及相应的指导变元指导变元，改成该量词辖域中，改成该量词辖域中未曾出现的某个个体变项符号，公式中其它部分未曾出现的某个个体变项符号，公式中其它部分不变，设所得公式为不变，设所得公式为A,A,则则 A A A A。代替规则代替规则 设设A A是一公式，将是一公式，将A A中某个中某个自由出现自由出现的个体变的个体变项所有出现用项所有出现用A A中未曾出现的个体变项符号代替中未曾出现的个体变项符号代替，A A中其它部分不变，设所得公式为中其它部分不变，设所得公式为A,A,则则 A A A A。 注意：注意：在

38、一公式中，有的个体变元既可以在一公式中，有的个体变元既可以是约束出现，又可以是自由出现，这就容易产是约束出现，又可以是自由出现，这就容易产生混淆。为了避免混淆，采用下面两个规则：生混淆。为了避免混淆，采用下面两个规则：约束约束出现用换出现用换名规则，将量词辖域中某个约名规则，将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。域中未曾出现过的个体变元，其余不变。例例 x F(x)x F(x)G(x,y) (G(x,y) (换名规则换名规则, ,将约束出现将约束出现 z zF(F(z z)G(x,y) )G(x,y

39、) 的的x x改成改成z)z) 自由变元代入规则，对某自由出现的个自由变元代入规则，对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入。体变元不同的个体变元去代入，且处处代入。例例 x F(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

40、(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)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) 该公式中，该公式中， 不存在既是不存在既是约束出现约束出现， 又是又是自由出现自由出现的个体变项。的个体变项。公式解释公式解释 一般情况下，一阶逻辑公式含有：一般情况下，一阶逻辑公式含有：个体常元、个体常元、个体变元（约束变元或自由变元）、函数变个体变元（约束变元或自由变元）、函数变元、谓词变元等

41、，元、谓词变元等，对各种变元用指定的特殊对各种变元用指定的特殊常元去代替，就构成了一个公式的解释。当常元去代替，就构成了一个公式的解释。当然在给定的解释下，可以对多个公式进行解然在给定的解释下，可以对多个公式进行解释。下面给出解释的一般定义。释。下面给出解释的一般定义。带量词的公式在论域内的展开式带量词的公式在论域内的展开式 例例2.12 2.12 令令A(x)A(x)：表示：表示x x是整数是整数,B(x),B(x)：表示：表示x x是奇数，是奇数， 设论域是设论域是1,2,3,4,51,2,3,4,5， 谓词公式谓词公式 xA(x)xA(x) 表示论域内所有的客体都是整数表示论域内所有的客

42、体都是整数 显然公式显然公式 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)：表示：表示x x是奇数，是奇数， 设论域是设论域是1,2,3,4,51,2,3,4,5， 谓词公式谓词公式 xB(x)xB(x) 表示论域内有

43、些客体是奇数，表示论域内有些客体是奇数， 显然公式显然公式 xB(x)xB(x)的真值也为真，因为的真值也为真，因为 B(1)B(1)、B(3)B(3)、B(5)B(5)的真值为真，的真值为真， 于是有于是有 xB(x)xB(x)B(1)B(1)B(2)B(2)B(3)B(3)B(4)B(4)B(5)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)xB(x)B(a1)B(a2).B(an)B(a1)B(a2).B(an)定义

44、定义2.7 一个解释一个解释 I 由下列由下列4部分组成：部分组成：(1) 非空个体域非空个体域DI。( 2 ) DI中 一 些 特 定 元 素 的 集 合中 一 些 特 定 元 素 的 集 合a1,a2,ai,.(3) DI上特定函数集合上特定函数集合fin|i,n 1.(4) DI上特定谓词的集合上特定谓词的集合Fin|i,n 1.所谓一个解释不外乎指定个体域、个体域所谓一个解释不外乎指定个体域、个体域中一些特定的元素、特定的函数和谓词等中一些特定的元素、特定的函数和谓词等例例2.12：给定解释给定解释I如下：求下列各式的真值如下：求下列各式的真值(1) DI=2,3；(2) DI中的特定

45、元素中的特定元素 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如下：求下列各式的真值

46、如下：求下列各式的真值(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) ( 1

47、1)(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) x x yL(x,y)yL(x,y) ( ( y(L(2 ,y) (y(L(2 ,y)

48、 ( yL(3,y)yL(3,y) ( (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 111 1 1 规律：规律： 用用 用用 公式类型公式类型 若一公式在任何解释下都是真的，称若一公式在任何解释下都是真的，称 该公式为逻辑有效的，或永真的。该公式为逻辑有效的，或永真的。 若一公式在任何解释下都是假的，称若一公式在任何解释下都是假的，称 该公式为矛盾式，或永假式。该公式为矛盾式，或永假式。 若一公式至少存在一个解释使其为真若一公式至少存在一个解释使其为真 ，称该公式为可满足式。，称该公式为可满足式。 与命题公式中分类一样，与命题公

49、式中分类一样， 谓词公式也分为三种类型，谓词公式也分为三种类型， 即即 逻辑有效式（或重言式）、逻辑有效式（或重言式）、 矛盾式（或永假式）矛盾式（或永假式） 可满足式。可满足式。例例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);xF(g(x,a),x);(2) x

50、x y(F(f(x,a),y)y(F(f(x,a),y)F(f(y,a),x)F(f(y,a),x) ；(3) x x y y zF(f(x,y),z)zF(f(x,y),z);(4) x x yF(f(x,y),g(x,y)yF(f(x,y),g(x,y);(5) F(f(x,y),f(y,z)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)为为

51、 x=y;在解释在解释N下下,公式分别化为：公式分别化为：(1) xF(g(x,a),x) xF(g(x,a),x) x F(g(x,0),x)x F(g(x,0),x) x F(xx F(x 0,x)0,x) x(0=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) x x y(

52、F(f(x,a),y)y(F(f(x,a),y)F(f(y,a),x)F(f(y,a),x) x x y(F(x+0,y)y(F(x+0,y)F(y+0,x)F(y+0,x) x x y(x+0=yy(x+0=yy+0=x)y+0=x) x x y(x=yy(x=yy=x) y=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下下,公式分

53、别化为：公式分别化为：(3) x y z(F(f(x,y),z) x y z(F(f(x,y),z) x y z(F(x+y,z) x y z(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) x x yF(f(x,y),g(x,y)yF(f(x,y),g(x,y) x x yF(x+y,xyF(x+y,x y)y) x

54、x y(x+y=xy(x+y=x y) y) 这是假命题这是假命题(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为可满为可满足式。足式。 在一阶逻辑里面，由于公式的复杂性和解在一阶逻辑里面，由于公式的复杂性和解释的多样性，

55、迄今为止还没有一种能判断任释的多样性，迄今为止还没有一种能判断任意一个公式是否可满足的或不可满足的算法。意一个公式是否可满足的或不可满足的算法。定义定义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 的代换实

56、例的代换实例例例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.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) ) 蕴涵式前件蕴涵式前件 x (F(x) F(x) 为为1， 蕴涵式后件蕴涵式后件 y(G(y) G(y) )为为0， 所

57、以为矛盾式。所以为矛盾式。(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 Gy G(y) y Gy 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 y F(x,y) x y y F(x,y) 前件

58、前件 x y y (x=10+y) 为真为真 后件后件 x y y(x=10+y) 为假为假 所以蕴涵式为假，为矛盾式所以蕴涵式为假，为矛盾式(5) x y y F(x,y) x y y F(x,y) 取解释取解释I为为: 个体域是自然数个体域是自然数N， F(x,y):x y。 x y y F(x,y) x y yF(x,y) 前件前件 x y y (x y ) 为真为真 后件后件 x y y(x y ) 为真为真 所以蕴涵式为真所以蕴涵式为真, 为重言式为重言式(5) x y y F(x,y) x y y F(x,y) 取解释取解释I为为: 个体域是自然数个体域是自然数N， F(x,y):

59、 x y 。 x y y F(x,y) x y yF(x,y) 前件前件 x y y ( x y ) 为假为假 后件后件 x y y(x y ) 为假为假 所以蕴涵式真所以蕴涵式真, 为重言式为重言式 综上所述综上所述 (5)中公式在不同的解释下真值不同中公式在不同的解释下真值不同, 可见可见 x y y F(x,y) x y y F(x,y) 是非逻辑有效式的可满足式。见是非逻辑有效式的可满足式。见P45例例2.9（5）例例2.16 2.16 给定解释给定解释I I 如下如下: : (a) 个体域个体域 D=N (b) (c) (d) 谓词谓词说明下列公式在说明下列公式在 I 下的涵义下的涵

60、义,并讨论真值并讨论真值 (1) xF(g(x,a),x)2axyyxgyxyxf),(,),(yxyxF: ),( x(2x=x) 假命题假命题(2) x y(F(f(x,a),y)F(f(y,a),x) x y(x+2=yy+2=x) 假命题假命题(3) x y zF(f(x,y),z)两点说明两点说明:5个小题都是闭式个小题都是闭式,在在I下全是命题下全是命题(3)与与(5)说明，量词顺序不能随意改变说明，量词顺序不能随意改变 (5) x y zF(f(y,z),x) x y z (y+z=x) 假命题假命题(4) xF(f(x,x),g(x,x) x(2x=x2) 真命题真命题 x y