一阶逻辑课件

第二章一阶逻辑§2.1 一阶逻辑的基本概念§2.2 一阶逻辑合式公式及解释§2.3 一阶逻辑等值式§2.4 一阶逻辑推理理论§2.5 例题分析

第二章一阶逻辑§2.1 一阶逻辑的基本概念

在命题逻辑中,我们把原子命题作为基本研究单位,对原子命题不再进行分解,只有复合命题才可以分解,揭示了一些有效的推理过程.但是进一步研究发现，仅有命题逻辑是无法把一些常见的推理形式包括进去.例如

§2.1 一阶逻辑的基本概念在命题逻辑中,我们把原子命题作为基本研究单形式逻辑形式逻辑的一般格式就是三段论。例：苏格拉底三段论：所有的人都是要死的，苏格拉底是人，所以，苏格拉底是要死的。形式逻辑形式逻辑的一般格式就是三段论。（1）凡人都是要死的；（2）苏格拉底是人；（3）所以苏格拉底是要死的。P：凡人都是要死的；Q：苏格拉底是人;R：所以苏格拉底是要死的。

(P∧Q)R（前提）（前提）（结论）苏格拉底三段论这不是重言式(110),即r不是前提p,q的有效结论.这反映了命题逻辑的局限性,其原因是把本来有内在联系的命题p,q,r,视为独立的命题。（1）凡人都是要死的；（前提）（前提）（结论）苏格拉底三段论原因：命题逻辑不考虑命题之间的内在联系和数量关系。要反映这种内在联系，就要对命题逻辑进行分析,分析出其中的个体词、谓词和量词，再研究它们之间的逻辑关系，总结出正确的推理形式和规则，这就是一阶(谓词)逻辑的研究内容。办法：将命题再次细分。§2.1 一阶逻辑的基本概念原因：命题逻辑不考虑命题之间的内在联系§2.1 一阶逻辑的基解决这个问题的方法：在表示命题时，既表示出主语，也表示出谓语，就可以解决上述问题。这就提出了谓词的概念(谓词是用来刻划个体词的性质或事物之间的关系的词,谓词S(x)相当于一个函数).解决这个问题的方法：2.1.1个体、谓词和命题函数在谓词逻辑中，将原子命题分解为谓词和个体两部分。1、定义：在原子命题中，所描述的对象称为个体；用以描述个体的性质或个体间关系的部分，称为谓词。§2.1 一阶逻辑的基本概念2.1.1个体、谓词和命题函数§2.1 一阶逻辑的基本概例2.1：分析下列个命题中的个体和谓词是无理数。张三与李四同在信息技术学院。

x与y的和等于z（x，y，z是确定的数）。的平方是非负的。所有的实数的平方都是非负的。有一个比21000大的素数。例2.1：分析下列个命题中的个体和谓词是无理数。（1）是无理数。解：个体：（代表圆周率） 谓词：···是无理数，表示“”的性质。（2）张三与李四同在信息技术学院。解：个体：张三，李四 谓词：···

与···同在信息技术学院 表示“张三”与“李四”之间的关系。个体：李四谓词：张三与···

同在信息技术学院表示“李四”的性质。个体：张三谓词：···

与李四同在信息技术学院，表示“张三”的性质。（1）是无理数。个体：李四个体：张三（3）x

与y的和等于z

（x，y，z是确定的数）个体：x、y、z谓词：···与···的和等于···个体：x、

z谓词：···与y的和等于···个体：y谓词：x与···的和等于z

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

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

P(x1,x2,…,xn)是n元谓词。2.1.2谓词（1）张三是个大学生解： 个体：张三 谓词：…是个大学生。 若 用P表示谓词：“

…

是个大学生”

;

a

表示个体：“张三”。 则上述命题可表示为P（a）。同理：“李四是个大学生”，若b表示个体“李四”， 则该命题可表示为P（b）。

对于给定的命题，当用表示其个体的小写字母和表示其谓词的大写字母来表示时，规定将小写字母写在大写字母右侧的（）内。例2.2

用谓词表示下列命题（1）张三是个大学生对于给定的命题，当用表示其个（2）陈强与陈佩斯是父子解： a表示：陈强

b

表示：陈佩斯 若用Q表示二元谓词：……

与……

是父子 则上述命题可表示为Q（a，b）。又如， 若用R表示三元谓词

“……位于……与……之间”， 则命题“杭州位于南京和上海之间”如何表示？

a：杭州，b：南京，c：上海， 则上述命题可表示为R（a，b，c）。（2）陈强与陈佩斯是父子

2.1.3命题函数

谓词本身并不是命题，只有谓词的括号内填入足够的个体，才变成命题。设H(x)是谓词表示x“能够到达山顶”，

l表示个体李四，

t表示老虎，

c表示汽车，那么H（l），H（t），H（c），等分别表示各个不同的命题：但它们有一个共同的形式，即H（x）当x分别取l、t、c时就表示“李四能够到达山顶”，“老虎能够到达山顶”，“汽车能够到达山顶”。2.1.3命题函数可见,在谓词的括号内填入不同的内容,就得到不同的命题，故谓词相当于一个函数，称之为命题函数。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等取特定的客体时，才确定了一个命题。再如，若L(x,y)表示“x小于y例2.3

用谓词(命题函数)分别表示x是负整数及x是非负整数

设N（x）：“x是负数”,E(x)：“

x是整数”则复合命题函数

N（x）∧E（x）表示：

“x是负整数”

┐N（x）∧E（x）表示：

“

x是非负整数”

例2.3用谓词(命题函数)分别表示x是负整数及x是非负整

通常,对于一个命题函数Q（x，y）

若Q（x，y）：表示“

x比y重”，当x，y指人或物时，它是一个命题，但若x，y指实数时，Q（x，y）就不是一个命题。 命题函数不是一个命题，只有个体变元取特定名称时，才能成为一个命题。但是个体变元在那些范围内取特定的值，对是否成为命题及命题的真值即有影响。 通常,对于一个命题函数Q（x，y）比如:设R（x）：“

x是大学生”，对x的取值情况:如果x的讨论范围为浙江中医药大学里班级中的学生，则R（x）是永真式。如果x的讨论范围为杭州长河高级中学里班级中的学生，则R（x）是永假式。如果x的讨论范围为一个剧院中的观众，观众中有大学生也有非大学生，那么对于某些观众，R（x）为真，对于另一些观众，R（x）为假。 命题函数确定为命题，与个体变元的论述范围有关。 比如:设R（x）：“x是大学生”，对x的取值情况:再如

令G(x，y)：“x高于y”，于是，G(x，y)是一个二元谓词。将x代以个体“张三”，y代以个体“李四”，则G(张三，李四)就是命题：“张三高于李四”。随便将x，y代以确定的个体，由G(x，y)都能得到一个命题。可见，G(x，y)不是命题，而是一个命题函数即谓词。再如令G(x，y)：“x高于y”，2.1.4论域(个体域)

定义：在命题函数中个体变项的取值范围，称之为论域，也称之为个体域。例如S(x):x是大学生，论域是:人类。

G(x,y)：x>y，论域是:实数。论域是一个集合。定义：由所有个体构成的论域，称之为全总个体域。它是个“最大”的论域。约定:对于一个命题函数，如果没有给定论域，则假定该论域是全总个体域。2.1.4论域(个体域)例2.4

用谓词(命题函数)将下列命题符号化：(1)丘华和李兵都是学生；(2)2既是偶数又是素数；(3)如果张华比黎明高，黎明比王宏高，则张华比王宏高。解(1)设个体域是人的集合。

P(x)：:x是学生。

a：丘华

b：黎兵 该命题符号化为P(a)P(b)例2.4用谓词(命题函数)将下列命题符号化：(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)2既是偶数又是素数；2.1.5量词例如：有些人是大学生。所有事物都是发展变化的。“有些”,“所有的”,就是对客体量化的词。量词：在命题中表示对客体数量化的词。定义了两种量词：

(1).存在量词：记作，表示“有些”、“一些”、“某些”、“至少一个”等。

(2).全称量词：记作，表示“每个”、“任何一个”、“一切”、“所有的”、“凡是”、“任意的”等。2.1.5量词

考察下面两个例子(它们均以整数作为其个体域)①(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.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试用量词、谓词表示下列命题（1）有些人是聪明的。（2）令I（x）：x是数（实数域特别注意：谓词前加上了量词，称为谓词的量化。若一个谓词中所有个体变元都量化了，则该谓词就变成了命题。这是因为在谓词被量化后，可以在整个个体域中考虑命题的真值了。这如同数学中的函数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一阶逻辑的基本概念说明：§2.1一阶逻辑的基本概念说明：（4）有些命题的符号化形式不止一种。至此，下列推理即可解决：

凡是人都是要死的。苏格拉底是人。苏格拉底是要死的。设：M(x):x是人。D(x):x是要死的。a:苏格拉底。则符号化为：

x(M(x)D(x))

∧M(a)D(a)§2.1一阶逻辑的基本概念说明：§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.1一阶语言的字母表定义如下：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一阶逻辑公式及解释定义2.22.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），（A∨B），（A∧B），（AB），（AB）是公式；（3）如A为公式，x为个体变元，则（xA），（xA）为公式；（4）公式由且仅由有限次使用（1），（2），（3）而得。注：量词后面若有括号，则不能省略。2.2一阶逻辑公式及解释定义谓词逻辑公式（简称公式）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））例2.9将下列命题表示为谓词公式(3)猫必捕鼠解：(3) 设C（x）：“x是猫”，

R（y）：“y是鼠”，

A（x，y）：“

x捕y”，则语句可表示为：

xy（（C（x）∧R（y））A（x，y））凡是与某一范围有关的对象应用量词来描述。(3)猫必捕鼠例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.10用谓词表示下列语句(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））(2)并非每个实数都是有理数。{R（x）,Q（x）}一、约束变元、与自由变元与指导变元、辖域 在一个谓词公式中，形如xA（x）或

xA（x）的那一部分称为公式的约束部分，在公式xA（x）和xA（x）中称x为指导变元而A（x）称为量词（x或x）的作用域或辖域。 在作用域中x的任一出现，称为x在公式中的约束出现，x称为约束变元。若在公式中的出现不是约束出现，则称x的出现为自由出现，自由出现的变元称为自由变元。§2.3约束变元与自由变元一、约束变元、与自由变元与指导变元、辖域§2.3约束变元x（P（x）yQ（x，y））xH（x）∧L（x，y）xy（P（x，y）∨Q（y，z））∧xR（x、y）说明：（1）若量词后有括号，则括号内的子公式就是该量词的辖域；（2）若量词后无括号，则与量词邻接的子公式为该量词的辖域；例2.11指出下列公式的辖域和变元约束的情况x（P（x）yQ（x，y））例2.11指出下列公1.x（P（x）yQ（x，y））解：x的辖域是（P（x）yQ（x，y）），对于x的辖域而言，x的所有出现均为约束出现，故它是约束变元。y的辖域是Q（x，y），对于y的辖域而言，y的出现为约束出现，故它是约束变元。例2.11指出下列公式的辖域和变元约束的情况1.x（P（x）yQ（x，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.xH（x）∧L（x，y）解：x的辖域是H（x）,x是约束出现,故x为约束变元在L（x，y）中x，y均为自由出现， 故对于整个公式来说，x既为约束变元，又为自由变元，y为自由变元。例2.11指出下列公式的辖域和变元约束的情况2.xH（x）∧L（x，y）例2.11指出下列公式3.xy（P（x，y）∨Q（y，z））∧xR（x、y）解：xy的辖域均为（P（x，y）∨Q（y，z）），其中，x、y均为约束出现，故是约束变元，z是自由变元。x的辖域为R（x、y），x为约束出现，故是约束变元，y为自由出现，故是自由变元。 在整个公式中，x是约束变元，y既是约束变元，又是自由变元，z是自由变元。例2.11指出下列公式的辖域和变元约束的情况3.xy（P（x，y）∨Q（y，z））∧xR（x、y换名规则设A是一公式，将A中某个辖域中约束变项的所有出现及相应的指导变元，改成该量词辖域中未曾出现的某个个体变项符号，公式中其它部分不变，设所得公式为A`,则AA`。代替规则设A是一公式，将A中某个自由出现的个体变项所有出现用A中未曾出现的个体变项符号代替，A中其它部分不变，设所得公式为A`,则AA`。§2.2一阶逻辑合式公式及解释

换名规则§2.2一阶逻辑合式公式及解释

注意：在一公式中，有的个体变元既可以是约束出现，又可以是自由出现，这就容易产生混淆。为了避免混淆，采用下面两个规则：①约束出现用换名规则，将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。例xF(x)∧G(x,y)(换名规则,将约束出现zF(z)∧G(x,y)的x改成z)注意：在一公式中，有的个体变元既可以是约束出现②自由变元代入规则，对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入。例xF(x)∧G(x,y)(代替规则,将自由出现x

F(x)∧G(z,y)的x改成z)②自由变元代入规则，对某自由出现的个体变元可用换名规则是替换约束变项及相应的指导变元。代替规则是代替自由出现的个体变项例xy(R(x,y)∨L(y,z))∧xH(x,y)xy(R(x,y)∨L(y,z))∧tH(t,y)(换名规则t)xy(R(x,y)∨L(y,z))∧tH(t,w)(代替规则w)该公式中，不存在既是约束出现，又是自由出现的个体变项。换名规则是替换约束变项及相应的指导变元。换名规则代入规则对象约束变元自由变元范围一个量词及其辖域内整个公式结果只能换名为另一变元,而不能换名为个体常元,换名后公式的含义不变。可以代以另一常元。公式由具有普遍意义变成仅对该个体常元有意义。换名规则与代入规则的主要区别:换名规则代入规则对象约束变元自由变元范围一个量词及其辖域内整公式解释一般情况下，一阶逻辑公式含有：个体常元、个体变元（约束变元或自由变元）、函数变元、为谓词变元等，对各种变元用指定的特殊常元去代替，就构成了一个公式的解释。当然在给定的解释下，可以对多个公式进行解释。下面给出解释的一般定义。§2.2一阶逻辑合式公式及解释

公式解释§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.12令A(x)：表示带量词的公式在论域内的展开式

例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.11令A(x)：表示定义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.7一个解释I由下列4部分组成：§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)=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))(0∧1)∧(1∧1)

0例2.12：给定解释I如下：求下列各式的真值例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)=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))(1∧1)∨(0∧1)1例2.12：给定解释I如下：求下列各式的真值例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)=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)xyL(x,y)x(L(x,2)∨L(x,3))

(L(2,2)∨L(2,3))∧(L(3,2)∨L(3,3))1∧11规律：用∨

用∧

例2.12：给定解释I如下：求下列各式的真值公式类型①若一公式在任何解释下都是真的，称该公式为逻辑有效的，或永真的。②若一公式在任何解释下都是假的，称该公式为矛盾式，或永假式。③若一公式至少存在一个解释使其为真，称该公式为可满足式。公式类型与命题公式中分类一样，谓词公式也分为三种类型，即逻辑有效式（或重言式）、矛盾式（或永假式）可满足式。与命题公式中分类一样，例2.13：给定解释N如下：(1)个体域为自然数集合DN；(2)DN中的特定元素a=0；(3)DN上的函数f(x,y)=x+y,g(x,y)=x·y;(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如下：例2.13：给定解释N如下：(1)个体域为自然数集合DN；(2)DN中的特定元素a=0；(3)DN上的函数f(x,y)=x+y,g(x,y)=x·y;(4)DN上的谓词F(x,y)为x=y;在解释N下,公式分别化为：(1)xF(g(x,a),x)xF(g(x,0),x)xF(x0,x)x(0=x)这是假命题例2.13：给定解释N如下：例2.13：给定解释N如下：(1)个体域为自然数集合DN；(2)DN中的特定元素a=0；(3)DN上的函数f(x,y)=x+y,g(x,y)=x·y;(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如下：例2.13：给定解释N如下：(1)个体域为自然数集合DN；(2)DN中的特定元素a=0；(3)DN上的函数f(x,y)=x+y,g(x,y)=x·y;(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如下：例2.13：给定解释N如下：(1)个体域为自然数集合DN；(2)DN中的特定元素a=0；(3)DN上的函数f(x,y)=x+y,g(x,y)=x·y;(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.13：给定解释N如下：

定义2.8设A为一公式,若A在任何解释下均为真则称A为永真式(逻辑有效式)。若A在任何解释下均为假,则称A为矛盾式(永假式)。若至少存在一个解释使A为真，则称A为可满足式。在一阶逻辑里面，由于公式的复杂性和解释的多样性，迄今为止还没有一种能判断任意一个公式是否可满足的或不可满足的算法。§2.2一阶逻辑合式公式及解释

定义2.8设A为一公式,若A在任何解释下均为真则称A为永定义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)等都是pq的代换实例§2.2一阶逻辑合式公式及解释

定义2.9设A0是含p1,p2,…,pn命题变项的命例2.14判断下列公式的类型1.((xF(x)∨yG(y))∧¬yG(y)xF(x)2.(xF(x)∨¬xF(x))(yG(y)∧¬yG(y))解：1.(p∨q)∧¬qp永真式2.(p∨¬p)(q∧¬q)矛盾式§2.2一阶逻辑合式公式及解释

例2.14判断下列公式的类型§2.2一阶逻辑合式公式例2.15判断下列各公式的类型。(1)F(x,y)(G(x,y)F(x,y))

代换实例p(qp)重言式(2)x(F(x)F(x))y(G(y)∧¬G(y))

代换实例(pp)(q∧¬q)矛盾式或蕴涵式前件x(F(x)F(x))为1，蕴涵式后件y(G(y)∧¬G(y))为0，所以为矛盾式。§2.2一阶逻辑合式公式及解释

例2.15判断下列各公式的类型。§2.2一阶逻辑合式公(3)xy(P(x,y)∧¬P(x,y))令个体域为实数集,因为对实数集中任取一组x,y公式P(x,y)∧¬P(x,y)总是假，所以xy(P(x,y)∧¬P(x,y))为矛盾式。(4)¬

(xF(x)yG(y))∧

yG(y)

代换实例¬(pq)∧q矛盾式(5)xyF(x,y)xyF(x,y)①取解释I为:个体域是整数集Z，F(x,y):x=10+y则xyF(x,y)xyF(x,y)前件xy(x=10+y)为真后件xy(x=10+y)为假所以蕴涵式为假，为矛盾式(3)xy(P(x,y)∧¬P(x,y))(5)xyF(x,y)xyF(x,y)

②取解释I为:个体域是自然数N，

F(x,y):x≤y。xyF(x,y)xyF(x,y)前件xy(x≤y)为真后件xy(x≤y)为真所以蕴涵式为真,为重言式(5)xyF(x,y)xyF(x,y)

③

取解释I为:个体域是自然数N，

F(x,y):x>y。xyF(x,y)xyF(x,y)前件xy(x>y)为假后件xy(x>y)为假所以蕴涵式真,为重言式综上所述(5)中公式在不同的解释下真值不同,可见xyF(x,y)xyF(x,y)

是非逻辑有效式的可满足式。见P42例2.9（5）(5)xyF(x,y)xyF(x例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)假命题例2.16给定解释I如下:x(2x=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(3)xyzF(f(x,y),z)两点说明:(5)

一阶逻辑等值式在一阶逻辑中，有些命题可以有不同的符号化形式。如：

没有不能表示为分数的有理数。令H(x):x是有理数。W(x):x能表示成分数。则：(1)x(H(x)W(x))（2）¬

x(H(x)∧¬W(x))均正确。同命题逻辑一样,我们称(1)、(2)是等值的。§2.3一阶逻辑等值式

一阶逻辑等值式§2.3一阶逻辑等值式定义2.10设A，B是一阶逻辑中任意两个公式，若AB为重言式，则称A与B是等值的，记作AB。称AB是等值式。已经得证的重要等值式：第一组：(1)xF(x)¬

¬xF(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一阶逻辑等值式

定义2.10§2.3一阶逻辑等值式第二组：1.消去量词等值式设个体域为有限集D={a1，a2，…，an}，则(1)xA(x)A(a1)∧A(a2)∧…∧A(an)(2)xA(x)A(a1)∨A(a2)∨…∨

A(an)定理2.1量词否定等值式设A(x)是任意的含自由出现个体变项x的公式，则(1)¬

xA(x)x¬A(x)(2)¬

xA(x)x¬A(x)§2.3一阶逻辑等值式

第二组：§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.1量词否定等值式的证明定理2.2量词辖域收缩与扩张等值式设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则(1)x(A(x)∨B)

xA(x)∨B

x(A(x)∧B)

xA(x)∧B

x(A(x)B)

x(A(x)B)

x(BA(x))(

B

xA(x))§2.3一阶逻辑等值式

定理2.2量词辖域收缩与扩张等值式§2.3一阶逻辑等

证明:x(A(x)B)

x(A(x)B)

证法1:右边

xA(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)xA(x)B

(

xA(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)

xA(x)∨Bx(A(x)∧B)

xA(x)∧Bx(A(x)B)

xA(x)Bx(BA(x))B

xA(x)§2.3一阶逻辑等值式

定理2.2量词辖域收缩与扩张等值式§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)∨Ｂ)B→xA(x)B∨xA(x)x(B∨A(x))x(B→A(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))xA(x)∧xB(x)(2)x(A(x)∨B(x))

xA(x)∨

xB(x)

我们称(1)为对∧的分配；(2)为对∨的分配但注意为对∨及为对∧都不存在分配等值式§2.3一阶逻辑等值式

定理2.3量词分配等值式§2.3一阶逻辑等值式

x(A(x)∨B(x))

xA(x)∨

xB(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)x(A(x)∨B(x))xA(x)∨x例2.16：证明：(P47

例2.10)(1)x(A(x)∨B(x))xA(x)∨xB(x)(2)

x(A(x)∧B(x))xA(x)∧xB(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.16：证明：(P47例2.10)例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))（置换规则）注：¬xA(x)x¬A(x)

¬xA(x)x¬A(x)例2.17：证明下列各式为等值式。证：(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))（置换规则）注：¬xA(x)x¬A(x)

¬xA(x)x¬A(x)证：(2)¬x(F(x)G(x))x(F(x)∧¬

范式与命题演算类似，在谓词演算中也有范式。范式为我们研究谓词演算公式提供了一种规范的标准形式。一个公式如果它的所有量词均非否定的出现在公式的最前面，且它们的辖域一直延伸到公式的末尾，此种形式的公式就叫前束范式。如公式xyz(P(x)∧F(y,z)∧Q(y,z))定义2.11设A是一个一阶逻辑公式，若A具有如下形式

Q1x1Q2x2…QkxkB则称A为前束范式,其中Qi为或,B为不含量词的公式如：xy（（F(x)∧G(y)）∧¬H(x,y)）√xy(F(x,y)∧G(y,z))∨xH(x,y,z)×前束范式就是把或提到范式的左边(即前边）范式

一阶逻辑中的任何公式都存在与之等价的前束范式。这就是说：任何公式的前束范式都是存在的，但一般不是唯一的。求法：利用前面的公式及三条变换规则（置换规则、换名规则、代替规则）即可求出与公式等值的前束范式。§2.3一阶逻辑等值式

一阶逻辑中的任何公式都存在与之§2.例2.18：求下列公式的前束范式。（1）xF(x)∧¬xG(x)解：(1)xF(x)∧x¬G(x)(量词否定等值式)x(F(x)∧¬G(x))(量词分配等值式)注意:

x在∧形式下可提出来,在∨形式下提不出来x在∨形式下可提出来,在∧形式下提不出来，§2.3一阶逻辑等值式

例2.18：求下列公式的前束范式。§2.3一阶逻辑等值式例2.18：求下列公式的前束范式。（2）xF(x)∨¬xG(x)解(2)xF(x)∨¬yG(y)(换名规则)

xF(x)∨y¬G(y)(量词否定等值式)

x(F(x)∨y

¬G(y))(量词辖域扩张等值式)xy

(F(x)∨¬G(y))(量词辖域扩张等值式)注：x与y的辖域不同所以可提出来§2.3一阶逻辑等值式

例2.18：求下列公式的前束范式。§2.3一阶逻辑等值式例2.18：求下列公式的前束范式。（3）

xF(x)∧xG(x)解：

xF(x)∧yG(y)(换名规则)

xy(F(x)∧G(y))

(4)xF(x)xG(x)解：xF(x)yG(y)(换名规则)

xy(F(x)

G(y))§2.3一阶逻辑等值式

例2.18：求下列公式的前束范式。§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)为真,由假言推理(AB∧AB)得出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例题分析例2.23将“每一列火车都比某些汽车快”符号化2.第二章小结本章重点掌握内容：1.各基本概念清楚。2.会命题符号化。3.熟练掌握等价公式和永真蕴涵式。4.会写前束范式。第二章小结本章重点掌握内容：Theendofthispart.Thanks!Theendofthispart.第二章一阶逻辑§2.1 一阶逻辑的基本概念§2.2 一阶逻辑合式公式及解释§2.3 一阶逻辑等值式§2.4 一阶逻辑推理理论§2.5 例题分析

第二章一阶逻辑§2.1 一阶逻辑的基本概念

在命题逻辑中,我们把原子命题作为基本研究单位,对原子命题不再进行分解,只有复合命题才可以分解,揭示了一些有效的推理过程.但是进一步研究发现，仅有命题逻辑是无法把一些常见的推理形式包括进去.例如

§2.1 一阶逻辑的基本概念在命题逻辑中,我们把原子命题作为基本研究单形式逻辑形式逻辑的一般格式就是三段论。例：苏格拉底三段论：所有的人都是要死的，苏格拉底是人，所以，苏格拉底是要死的。形式逻辑形式逻辑的一般格式就是三段论。（1）凡人都是要死的；（2）苏格拉底是人；（3）所以苏格拉底是要死的。P：凡人都是要死的；Q：苏格拉底是人;R：所以苏格拉底是要死的。

(P∧Q)R（前提）（前提）（结论）苏格拉底三段论这不是重言式(110),即r不是前提p,q的有效结论.这反映了命题逻辑的局限性,其原因是把本来有内在联系的命题p,q,r,视为独立的命题。（1）凡人都是要死的；（前提）（前提）（结论）苏格拉底三段论原因：命题逻辑不考虑命题之间的内在联系和数量关系。要反映这种内在联系，就要对命题逻辑进行分析,分析出其中的个体词、谓词和量词，再研究它们之间的逻辑关系，总结出正确的推理形式和规则，这就是一阶(谓词)逻辑的研究内容。办法：将命题再次细分。§2.1 一阶逻辑的基本概念原因：命题逻辑不考虑命题之间的内在联系§2.1 一阶逻辑的基解决这个问题的方法：在表示命题时，既表示出主语，也表示出谓语，就可以解决上述问题。这就提出了谓词的概念(谓词是用来刻划个体词的性质或事物之间的关系的词,谓词S(x)相当于一个函数).解决这个问题的方法：2.1.1个体、谓词和命题函数在谓词逻辑中，将原子命题分解为谓词和个体两部分。1、定义：在原子命题中，所描述的对象称为个体；用以描述个体的性质或个体间关系的部分，称为谓词。§2.1 一阶逻辑的基本概念2.1.1个体、谓词和命题函数§2.1 一阶逻辑的基本概例2.1：分析下列个命题中的个体和谓词是无理数。张三与李四同在信息技术学院。

x与y