离散数学：第二章 谓词逻辑

第二章谓词逻辑用命题逻辑表示，则有P，Q|—R。但(P∧Q)→R并不是永真式，故上述推理形式是错误的。在命题逻辑中，研究以原子命题为基本单位的复合命题之间的逻辑关系和推理。例如，著名的亚里士多德三段论苏格拉底推理：

P：所有的人都会死的，

Q：苏格拉底是人，

R：所以苏格拉底会死的。错误的原因：各命题的逻辑关系不是体现在原子命题之间，而是体现在构成原子命题的内部成分之间，即体现在命题结构的更深层次上。前一章介绍的命题与命题演算是命题逻辑的内容，其基本组成单位是原子命题。原子命题作为具有真假意义的陈述句至少是由主语和谓语两部分组成。例如，电子商务是计算机技术的一个应用系统。在这里“电子商务”是主语，而“是……”是谓语。当主语改变为“电子政务”时就得到新的原子命题：电子政务是计算机技术的一个应用系统。谓词逻辑是对原子命题作进一步分析，分析出其中个体词、谓词和量词，研究它们形式结构的逻辑关系，正确的推理形式和规则。定义2.1.1

在原子命题中，所描述的对象称为个体；用以描述个体的性质或个体间关系的部分，称为谓词。个体是指可以独立存在的事物，它可以是具体的，也可以是抽象的。个体常元表示特定的个体，以a，b，c…或带下标的ai，bi，ci…表示；个体变元表示不确定的个体，以x，y，z…或xi，yi，zi…表示。谓词，当与一个个体相联系时，它刻划了个体性质；当与两个或两个以上个体相联系时，它刻划了个体之间的关系。谓词常元表示特定谓词；谓词变元表示不确定的谓词；都用大写英文字母，如P，Q，R，…，或其带上、下标来表示。2.1谓词逻辑中基本概念与表示一、个体、谓词和命题的谓词形式例子：张三是一个大学生，李四是一个大学生。这两个命题可用不同符号P,Q表示，但P,Q的谓词有同样的属性：“是一个大学生”。因此引入一个符号表示“是一个大学生”，再引入一种方法表示客体的名称，这样就能把“是一个大学生”这个命题的本质属性刻划出来。（a）他是三好学生。谓词指明客体性质（b）7是质数。（c）每天早晨做广播操是好习惯。（d）5大于3。谓词指明客体联系（e）哥白尼指出地球绕着太阳转。命题的谓词形式定义2.1.2

一个原子命题用一个谓词(如P)和n个有次序的个体常元(如a1，a2，…，an)表示成P(a1，a2，…，an)，称它为该原子命题的谓词形式或命题的谓词形式。命题的谓词形式的约定：

(a)对给定命题，小写字母表示个体，大写字母表示谓词，规定把小写

字母写在大写字母右侧的圆括号()内。

(b)命题的谓词形式中的个体出现的次序影响命题的真值，不得随意变动，否则真值会有变化。

(c)用谓词表达命题，必须包括客体和谓词两部分。例如：

“张三是一个大学生”

表示客体的性质，可以表达为A(b)，

其中

谓词A：“是一个大学生”，b:张三。

“a是小于b”表示两个客体之间关系，表达为B(a,b),

其中谓词B:“是小于”。

“点a在b与c之间”表示两个客体之间关系，表达为L(a,b,c)，其中谓词L：“…在…和…之间”

。二、原子谓词定义2.1.3

由一个谓词(如P)和n

个个体变元(x1，x2，…，xn)组成的P(x1，x2，…，xn)，称为n元原子谓词或n元命题函数，简称n元谓词。而个体变元的论述范围，称为个体域或论域。

当n=1时，称为一元谓词；当n=2时，称为二元谓词；

…

……

…

当n=0时，称为零元谓词。零元谓词就是命题。n元谓词不是命题，只有当其中的个体变元用特定个体或个体常元替代时，才能成为一个命题。论域把一个n元谓词中的每个个体的论域综合在一起作为它的论域，称为n元谓词的全总论域。当一个命题没有指明论域时，把全总论域作为其论域。采用一个谓词如P(x)来限制个体变元x的取值范围，并把P(x)称为特性谓词。n元谓词中的每个个体变元在哪些论域取特定的值，对命题的真值极有影响。例如：S(x)：x是大学生若x的论域为某大学计算机系全体同学，则S(x)为真。若x的论域为某中学的全体同学，则S(x)为假。若x的论域为某剧场中的观众，则S(x)的真值不确定。由一个或者n个简单命题函数以及逻辑联结词组合而成的表达式称为复合命题函数。逻辑联结词┐，

∧，∨，→和的意义与命题演算中的解释类同。例2：H(x,y)：x比y长得高；l：李四；c：张三；则┐H(l,c)：李四不比张三长得高；

┐H(l,c)∧┐H(c,l)：李四不比张三长得高且张三也不比李四长得高，即张三和李四同样高；

例1：S(x)：x

学习很好；W(x)：x

工作很好；则┐S(x)：x学习不是很好；

S(x)∧

W(x)：x的学习和工作都很好；

S(x)→W(x)：若x的学习很好，则x工作得很好；三、量词利用n元谓词和它的论域概念，有时不能用符号来准确表达某些命题。为避免理解上的歧义，在谓词逻辑中，引入表示不同数量的词，即量词。量词是由逻辑学家Fray引入的，有了量词后用逻辑符号表示命题的能力大大加强。

定义2.1.4

①符号称为全称量词符，用来表达“对所有的”、“每一个”、“对任何一个”、“一切”等词语；

x称为全称量词，称

x为指导变元。②符号称为存在量词符，用来表达“存在一些”、“至少有一个”、“对于一些”、“某个”等词语；

x

称为存在量词，称

x为指导变元。③符号!

称为存在惟一量词符，用来表达“恰有一个”、“存在惟一”等词语；

!x称为存在惟一量词，称x为指导变元

。解：令M(x):x是人；H(x):x要呼吸。

(x)(M

(x)→H(x))②每个学生都要参加考试；解：令P(x):x是学生；Q(x):x要参加考试。

(x)(P

(x)→Q(x))③任何整数或是正的或是负的；解：令I(x):x是整数；R(x):x是正数；N(x):x是负数。

(x)(I(x)→(R

(x)∨N(x))例1：试用量词、谓词表示命题：①所有的人都是要呼吸的；例2：试用量词、谓词表示命题：①存在一个数是质数；解令P(x):x是质数；

(

x)(P

(x))②一些人是聪明的。解令M(x):x是人；R(x):x是聪明的。

(

x)(M

(x)∧R(x))③有些人早饭吃面包。解令M(x):x是人；E(x):x早饭吃面包。

(x)(M

(x)∧E(x))例3：试用量词、谓词表示命题：①所有大学生都热爱祖国；解令S(x):x是大学生；L(x):x热爱祖国。

(x)(S

(x)→L(x))②每个自然数都是实数解令N(x):x是自然数；R(x):x是实数。

(x)(N

(x)→R(x))③一些大学生有远大理想；解令S(x):x是大学生；I(x):x有远大理想。

(x)(S

(x)∧I(x))④有的自然数是素数解令N(x):x是自然数；P(x):x是素数。

(x)(N

(x)∧P(x))规律全称量词后跟一个条件式，特性谓词作为其前件出现；存在量词后跟一个合取式，特性谓词作为一个合取项出现。若指明了论域，则不需要特性谓词。(x)L

(x)，(x)R

(x)(x)I

(x)，(x)P

(x)谓词前加上了量词，称为谓词的量化。若一个谓词中所有个体变元都量化了，则该谓词就变成了命题。在谓词被量化后，可以在整个个体域中考虑命题的真值。一、谓词公式定义2.2.1

项由下列规则形成：①个体常元和个体变元是项；②若f

是n元函数，且t1，t2，…，tn

是项，则f(t1，t2，…，tn)是项；③所有项都是有限次的使用①和②生成。2.2谓词公式与翻译为了方便处理数学和计算机科学的逻辑问题及谓词表示的直觉清晰性，引进项的概念。例1：令f(x,y)表示x+y,谓词N(x)表示x是自然数。则f(2,3)表示个体自然数5，N(f(2,3))表示5是自然数。有了项的定义、函数的概念就可用来表示个体常元和变元。

函数的使用给谓词表示带来很大方便。例2：P(x):x是教授；f(x):x的父亲；c:张强那么P(f(c))表示“张强的父亲是教授”这一命题。例3：用谓词表示命题：对任意整数x,x2-1=(x+1)(x-1)。解：令I(x)是整数，f(x)=x2-1,g(x)=(x+1)(x-1),E(x,y):x=y。则该命题可表示成：(

x)(I(x)→

E(f(x),g(x)))定义2.2.2

若P(x1，x2，…，xn)是n元谓词，t1，t2，…，tn是项，则称P(t1，t2，…，tn)为原子谓词公式，简称原子公式。定义2.2.3

合式谓词公式当且仅当由下列规则形成的符号串：①原子公式是合式谓词公式；②若A是合式谓词公式，则(┐A)是合式谓词公式；③若A，B是合式谓词公式，则(A∧B)，(A∨B)，(A→B)和(A

B)都是合式谓词公式；④若A是合式谓词公式，x是个体变元，则(x)A、(x)A都是合式谓词公式；⑤仅有有限项次使用①、②、③和④形成的才是合式谓词公式。合式谓词公式是按上述规则由原子公式、联结词、量词、圆括号和逗号组成的符号串，而且命题公式是它的一个特例。例如：(x)P(x)，(x)(P(x)∨R(x))，(x)(y)(P(x,y)→R(y))都是合式谓词公式；而(x)(P(x)→R(x)，(x)(y)(∧P(x,y))都不是合式谓词公式。称合式谓词公式为谓词公式；可将合式谓词公式最外层括号省略，但量词后括号不可省略。二、谓词逻辑的翻译把一个文字叙述的命题，用谓词公式表示出来，称为谓词逻辑的翻译或符号化；①正确理解给定命题。必要时把命题改叙，使其中每个原子命题及原子命题之间的关系能明显表达出来。②把每个原子命题分解成个体、谓词和量词；在全总论域中讨论时，要给出特性谓词。③找出恰当量词。应注意全称量词(x)后跟条件式，存在量词

(x)后跟合取式。④用恰当的联结词把给定命题表示出来。一般说，符号化的步骤如下：例1：把下列命题符号化：①张强和李林都是足球运动员。

②赵越是象棋迷或围棋迷。

③李林比张强高。

F(x):x是足球运动员；a:张强；b:李林；

F(a)∧F(b)C(x):x是象棋迷；G(x)：x是围棋迷；a：赵越

C(a)∨G(a)P(x,y)：x比y高；

a：李林；b：张强；

P(a，b)例2.将命题“没有最大的自然数”符号化解：改叙为：“对所有的自然数x，如果x是自然数，则一定存在y,y也是自然数，并且y比x大。”令N(x):x是自然数；G(x，y)：x比y大；则原命题表示为：(x)(N(x)→(y)(N

(y)∧G(y，x)))例3.将“今天有雨雪，有些人会跌跤”符号化解：改叙“若今天下雨又下雪，则存在x,x是人且x会跌跤”

令

R:今天有雨；S:今天有雪；

M(x):x是人；F(x):x会摔跤；则本语句可表示为：R∧S→(x)(M

(x)∧F(x))例4.用谓词表示命题“张强把一本新买到的离散数学书送给了李林。”解：令N(x):x是新的；B(x):x是买的；

G(x，y，z):x把y给了z；

a:张强；b：李林；c:离散数学书则原命题可表示成：

G(a，c，b)∧N(c)

∧B(c)若令P(x):x是新买到的；则原命题可表示成：G(a，c，b)∧P(c)这里给出了两种不完全相同的符号化形式，表示了对命题描述的深刻程度不同，前者细微一些，后者粗糙一些。例5.人都要犯错误。例6.李涛无书不读。解：该命题可说成“对所有的x,如果x是人,则x要犯错误”。设

H(x):x是人。

Q(x):x犯错误。则命题可表示为(x)

(H(x)→Q(x))。此命题等价于“没有不犯错误的人”

则命题还可表示为┐(x)

(H(x)∧┐Q(x))解：该命题即是说“李涛所有的书都读”。设P(x):x是书。Q(x,y):x读y。a:李涛。则命题可表示为：(x)(P(x)→Q

(a,x))。例8.如果b2－4ac≥0,则实系数一元二次方程

ax2＋bx＋c＝0有实数解。例7.有些人聪明，但不是所有的人都聪明。解设H(x):x是人；B(x):x聪明。则命题可表示为：

(x)(H(x)∧B(x))∧┐((x

)(H(x)→B(x)))。解：设R(x):x是实数,并将数学中的运算符“＝”、“≠”、“＞”、“≥”等作谓词使用,则命题可表示为：

R(a)∧R(b)∧R(c)∧(b2－4ac≥0)→(x)(R(x)∧(ax2＋bx＋c＝0))一、约束变元与自由变元定义2.3.1

给定一个谓词公式A，其中有一部分公式形如(x)B

(x)或(x)B

(x)，则称它为A的x约束部分，称B(x)为相应量词的作用域或辖域。辖域中，x的所有出现称为约束出现，x称为约束变元；B中不是约束出现的其它个体变元的出现称为自由出现，这些个体变元称为自由变元。2.3、约束变元与自由变元①若量词后有括号，则括号内的子公式就是该量词的辖域；②若量词后无括号，则与量词邻接的子公式为该量词的辖域。确定量词的辖域:例1指出下列各合式公式中的量词辖域、个体变元的约束出现和自由出现。①(x)(P(x)(y)Q(x，y))②(x)H(x)∧L(x，y)③(x)(y)(P(x，y)∨Q(y，z))∧(x)R(x，y)解：①(x)的辖域是(P(x)(y)Q(x,y))；(y)的辖域是Q(x,y)；

对于(y)的辖域而言，y为约束出现，x为自由出现；

对于(x)的辖域而言，x和y均为约束出现，x约束出现2次，

y约束出现1次。②(x)的辖域是H(x)，x为约束出现，L(x，y)中的x和y都是自由出现；

对于整个公式，x约束出现一次，自由出现一次，y自由出现一次。解：(x)的辖域为(y)(P(x,y)∨Q(y,z))；(y)的辖域为P(x,y)∨Q(y,z)；

(x)的辖域为R(x，y);

在(x)的辖域中，x和y为约束出现，z为自由出现；在(y)的辖域中，y为约束出现，x,z为自由出现；在(x)的辖域中，x为约束出现，y为自由出现；整个公式，

x为约束出现，y为约束出现又为自由出现，z为自由出现③(x)(y)(P(x，y)∨Q(y，z))∧(x)R(x，y)定义2.3.2设A为任意一个公式，若A中无自由出现的个体变元，则称A为封闭的合式公式，简称闭式。若A中无约束变元出现，则称A为开放公式，简称开式。由闭式定义可知，闭式中所有个体变元均为约束出现。例如：(x)(P(x)Q(x))和(x)(y)(P(x)∨Q(x，y))是闭式，P(x)Q(x，y)和L(x，y，z)是开式，(x)(P(x)Q(x，y))和(y)(z)L(x，y，z)既不是闭式，也不是开式。

在一个公式中，有的个体变元既可以是约束出现，又可以是自由出现，容易产生混淆。为了避免混淆，采用下面两个规则：约束变元改名规则，将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。自由变元代入规则，对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入。例1.

将公式(x)(P

(x)Q

(x，y))∧R

(x，y)中的约束变元改名。解：(z)(P

(z)Q

(z，y))∧R

(x，y)(y)(P

(y)Q

(y，y))∧R

(x，y)(z)(P

(z)Q

(x，y))∧R

(x，y)(z)(P

(z)Q

(z，y))∧R

(z，y)xxx例2.

对公式(x)(P

(y)Q

(x，y))∧R

(x，y)中的自由变元代入。(x)(P

(z)Q

(x，z))∧R

(u

，z)(x)(P

(z)Q

(x，z))∧R

(x，y)(x)(P

(x)Q

(x，z))∧R

(x，x)xx解：在(x)的辖域中，y是自由变元,

而在整个公式中，x与y都是自由变元，正确的代入是把z代入自由变元y，得：改名规则与代入规则的不同点：①施行的对象不同。改名是对约束变元施行，代入是对自由变元施行。②施行的范围不同。改名可以只对公式中一个量词及其辖域内施行，即只对公式的一个子公式施行；而代入必须对整个公式同一个自由变元的所有自由出现同时施行，即必须对整个公式施行。③施行后的结果不同。改名后，公式含义不变，因为约束变元只改名为另一个个体变元，约束关系不改变。约束变元不能改名为个体常元；代入，不仅可用另一个个体变元进行代入，并且也可用个体常元去代入，从而使公式由具有普遍意义变成为仅对该个体常元有意义，即公式的含义改变了。定义2.3.3

若x1，x2，…，xn是不同个体变元，t1，t2，…，tn是项，则称{x1/t1，x2/t2，…，xn/tn}是代换。

若

t是项，{x1/t1，x2/t2，…，xn/tn}是代换，则t{x1/t1，x2/t2，…，xn/tn}是t1，t2，…，tn分别代替t中x1，x2

，…，xn

的所有出现而得到的项，记为若A为公式，{x1/t1，x2/t2，…，xn/tn}是代换，则A{x1/t1，x2/t2，…，xn/tn}是用t1，t2，…，tn分别代替A中的x1，x2，…，xn的所有自由出现而得到的公式，记为

例3.

设t是，A是(x)P(x，y)Q(x，y，z)，则是；

而是(x)P(x，z)Q(a，z，x)。定义2.3.4

令A是任意的合式公式，x为自由出现。如果

x不出现在项t所含的任意个体变元y

的量词(y)或(y)

的辖域内，则称项t

对A中的x是自由的或可代入的。解：项f(x,w)对A中的y不是自由的：y出现在了项f(x,w)中的个体变元x的量词(x)的辖域内.

例1.设

A为(x)P

(x，y)(z)Q

(x，z)，考察项f(x,w)对A中的y，项g(y,z)对A中的y，项h(x,z)对A中的x，项y对A中的x是否是自由的？项g(y,z)对A中的y是自由的：y不出现在项g(y,z)中的个体变元z的量词(z)的辖域内。项h(x,z)对A中的x不是自由的：x出现在了项h(x,z)的个体变元x的量词(x)和个体变元z的量词(z)的辖域内。项y对A中的x是自由的：在公式A中没有量词(y)和(y)。解：项g(y,z)对A中的y是自由的：y不出现在项g(y,z)中的个体变元z的量词(z)的辖域内。因此，=(x)P

(x，g(y，z))(z)Q

(x，z)项y对A中的x是自由的：在公式A中没有量词(y)和(y)。因此，=(x)P

(x，y)(z)Q

(y，z)

例1.A为(x)P

(x，y)(z)Q

(x，z)，考察项f(x,w)对A中的y，项g(y,z)对A中的y，项h(x,z)对A中的x，项y对A中的x是否是自由的？从约束变元的概念可以看出，P(x1,x2,……xn)是n元谓词，它有n个互相独立的自由变元。若对其中k个变元进行约束，则成为n-k元谓词。因此，谓词公式中如果没有自由变元出现，则该式就成为一个命题。例如，(x)P(x,y,z)是二元谓词

(z)(x)P(x,y,z)是一元谓词一个公式的约束变元所使用的名称符号是无关紧要的。故(x)P(x)和(y)P(y)具有相同的意义。设A(x)表示x不小于0,那么,

(x)A(x)表示一切x都使得x不小于0;(y)A(y)表示一切y都使得y不小于0;(t)A(t)表示一切t都使得t不小于0;

这三个命题在实数域中都表示假命题：“一切实数均不小于0”。量词作用域中的约束变元，当论域的元素是有限时，个体变元的所有可能的取代是可枚举的。设论域元素为a1,a2,……an，则：

(x)A(x)A(a1)

∧

A(a2)∧……

∧

A(an)(x)A(x)A(a1)∨A(a2)∨……

∨

A(an)例.求下列公式的真值：

(1)(x)(P(x)∨Q(x))，其中P(x)

:x=1,Q(x)

:x=2而且论域是{1,2}。

(2)(x)(P(x)∧Q(x))，其中P(x)

:x=1,Q(x)

:x=2而且论域是{1,2}。

(3)(x)(P→Q(x))∨R(a)，其中

P

:2>1,Q(x)：x<=3,R(x)：x>5,

a:5,

论域是{-2,3,6}。解：

(1)(x)(P(x)∨Q(x))(P(1)∨Q(1))∧(P(2)∨Q(2))

(T∨F)∧(F∨T)T(3)(x)(P→Q(x))∨R(a)(x)(T→Q(x))∨F

(x)(T→Q(x))

(x)(F∨

Q(x))

(x)

Q(x)

Q(-2)∧Q(3)

∧Q(6)

T

∧T

∧F

F(2)(x)(P(x)∧Q(x))

(P(1)∧

Q(1))∨

(P(2)∧

Q(2))

(T∧

F)∨

(F∧

T)F定义2.4.1

谓词逻辑的一个解释I

由下面四部分组成：①非空个体域DI；②DI

中部分特定元素a′，b′，…；③DI上的一些特定函数f′，g′，…；④DI上特定谓词P′，Q′，…。2.4谓词逻辑的解释与其赋值

给定一个文字叙述的命题，可以符号化为谓词公式。反之，给定一个谓词公式，它表达怎样的意义？这涉及谓词逻辑的语义问题。只有对谓词公式中的抽象符号给出解释和赋值后，公式才有意义，公式可能真或假。解释是针对谓词逻辑中的符号，其对应关系如下：①个体变元x，y，…在DI

内取值；②个体常元a，b，…被解释成a′，b′，…；③函数符号f，g，…被解释成f′，g′，…；④谓词符号P，Q，…被解释成P′，Q′，…。

在一个具体解释中，个体常元、函数符号和谓词符号的数量一般是有限的，并且其解释一旦确定就不再改变，只是个体变元的值在个体域DI内变化，量词符或仅作用于DI中的元素。例1设公式为(x)(y)(z)E

(f(x，z)，y)，试说明它在下面解释中的具体含义。②解释Q：DQ为正有理数全体，a

ʹ=1，fʹ(p,q)=p*q，gʹ(p,q)=p/

q，Eʹ(p，q):p=q，其中p，q是DQ中的元素。①解释N：DN为含有0在内的全体自然数，a

ʹ=0,fʹ(i，j)=i+j，

gʹ(i，j)=i*j，hʹ(i)=i+1，Eʹ(i，j)：i=j，其中i，j是DN中的元素。在此解释下公式的含义为：对DN中的任意i，j，存在DN中的k，使得i+k=j。真值为F。在此解释下公式的含义为：对DQ中的任意i，j，存在DQ中的k，使得i*k=j。

真值为T。赋值定义2.4.2

解释I中的一个赋值是一个从项的全体到DI

的具有下列性质的函数v，使得：①对任意个体常元a，有v(a)=a′。②v(f(t1，t2，…，tn))=fʹ(v(t1)，v(t2)，…，v(tn))，其中f为n元函数，t1，t2，…，tn为任意项。赋值提供了对每个项指派D中元素作为它的解释的一个规则。在给定解释中存在不同的赋值，并且当一个赋值v对所有个体变元的值确定后，则任意项的值也就确定了。例2.

在例1的解释N中，设公式为(x)(y)(z)E

(f(x，z)，y)解释N：DN为含有0在内的全体自然数，a

ʹ=0,

fʹ(i，j)=i+j，gʹ(i，j)=i*j，hʹ(i)=i+1，

Eʹ(i，j)：i=j，其中i，j是DN中的元素。令赋值v

是：v(x)=i,v(y)=j,v(z)=k,……,

其中i,j,k,…是DN中的元素。于是

v(f(x,y))=fʹ(v(x)，v(y))=i+j，

v(g(x,y))=gʹ(v(x)，v(y))=i*j，

v(h(x))=hʹ(v(x))=i+1，

……….

以此类推，可以得到在解释I中各项在赋值下的值。定义2.4.3

在一个解释I中，称v和v′是几乎等同赋值或者

x-等同赋值，如果对任意元素y,

有v(y)=vʹ(y)，其中y≠x.由定义可知，若v和vʹ

是x-等同赋值，那么它们除了在x处可能不等，对其余个体变元都有相同的值。对于x,它们的赋值也是可以相同的，因此一个赋值v总是与自己是x-等同赋值。如果一个赋值使某公式为真，则称该赋值满足本公式。例如，在解释N中，令v(x)=i,v(y)=j，其中i,j为DN中元素，则有：公式E(f(x,y),f(x,y))的意义是：i+j=i+j,这是真命题，也即是说赋值v满足本公式;

公式E(f(x,y),g(x,y))的意义是：i+j=i*j,这是假命题，也即是说赋值v不满足本公式。解释N：DN为含有0在内的全体自然数，a

ʹ=0,

fʹ(i，j)=i+j，gʹ(i，j)=i*j，hʹ(i)=i+1，

Eʹ(i，j)：i=j，其中i，j是DN中的元素。①v满足原子公式P(t1,t2,…,tn),如果Pʹ(v(t1),v(t2),…,v(tn))在I

中为真；②v满足┐B，如果v不满足B；③v满足B∧C，如果v满足B也满足C；④v满足B∨C，如果或者v满足B或者v满足C；⑤v满足B→C，如果或者v满足┐B或者满足C；⑥v满足BC，如果v满足B→C且也满足C→B；

⑦v满足(x)A，如果对于任意与v是x-等同赋值的vʹ,均有vʹ满足A；

⑧v满足(x)A，如果存在一个与v是x-等同赋值的vʹ，有vʹ满足A；定义2.4.4

令A是谓词逻辑的公式，I是谓词逻辑的一个解释，称I中的赋值v满足A，是指以下八条归纳地成立：在解释I中，对任何公式A，赋值v或者满足A或者不满足A，二者必居其一。①E(g(x,y),g(z,w))；②(x)(E(x,y)→E(y,x))；③(x)E(x,a)；④(x)

E(x,y).例2.4.2

在解释N中，讨论赋值是否满足下列公式：解释N：DN为含有0在内的全体自然数，aʹ=0,fʹ(i,j)=i+j,gʹ(i,j)=i*j，hʹ(i)=i+1，Eʹ(i,j)：i=j，其中i，j是DN中的元素。解：①在解释N中，凡是使v(x)*v(y)=v(z)*v(w)成立的赋值v

都满足公式E(g(x,y),g(z,w)),否则不满足。例如，令v1(x)=1,v1(y)=2,v1(z)=2,v1(w)=1,1*2=2*1成立，

则v1满足公式

E(g(x,y),g(z,w))；令v2(x)=1,v2(y)=2,v2(z)=2,v2(w)=2,由于1*2≠2*2,

则v2不满足公式E(g(x,y),g(z,w))。解：②

(x)(E(x,y)→E(y,x))(x)(┐E(x,y)∨E(y,x))

.

在解释N中，令赋值v1为v1(x)=1,v1(y)=2，则由于1≠2，即v1不满足E(x,y),

于是v1满足┐E(x,y)，即v1满足┐E(x,y)∨E(y,x)

故v1满足E(x,y)→E(y,x)。

所有与v1是x-等同赋值的v1ʹ仅在x处和v1的赋值可能有所不同。而这些v1ʹ或者满足┐E(x,y)(当v1ʹ(x)≠2，v1ʹ(y)=2时)，或者满足E(y,x)(当v1ʹ(x)=2，v1ʹ(y)=2时)。所以v1ʹ满足┐E(x,y)∨E(y,x)

，即

v1ʹ满足E(x,y)→E(y,x)。依定义知，v1满足公式(x)(E(x,y)→E(y,x))。进一步分析，可得N中每个赋值v都满足这个公式。例2.4.2

在解释N中，讨论赋值是否满足下列公式：解释N：DN为含有0在内的全体自然数，aʹ=0,fʹ(i,j)=i+j,gʹ(i,j)=i*j，hʹ(i)=i+1，Eʹ(i,j)：i=j，其中i，j是DN中的元素。解：③(x)E(x,a).

在解释N中，令赋值v1,v1(x)=0,而v(a)=0，则v1满足E(x,a)。取与v1是x-等同赋值的v1ʹ,v1ʹ(x)=1,则v1ʹ不满足E(x,a)。可见v1不满足公式(x)E(x,a).

进一步分析，可得N中任何赋值v都不满足该公式。④(x)E(x,y).

在解释N中，令赋值v1,v1(x)=1,v1(y)=2,知v1不满足E(x,y)。若取与v1是x-等同赋值的v1ʹ,使v1ʹ(x)=2,v1ʹ(y)=2,则v1ʹ满足E(x,y)。根据定义知，v1满足公式(x)E(x,y)。因此，N中任何赋值v都满足本公式。例2.4.2

在解释N中，讨论赋值是否满足下列公式：解释N：DN为含有0在内的全体自然数，aʹ=0,fʹ(i,j)=i+j,gʹ(i,j)=i*j，hʹ(i)=i+1，Eʹ(i,j)：i=j，其中i，j是DN中的元素。定义2.5.1如果在解释I中每个赋值v都满足公式A，则A在解释I中称为真；如果不存在在I中满足A的任何赋值，则A在解释I中称为假。前者记作I|=A，后者记作I|=┐A。2.5真与逻辑有效由定义知，对一个特殊公式A，若I中有些赋值满足A，有些赋值不满足A，则该公式在I中既不永真也不永假。根据赋值和真的定义，可以推知：在给定解释中，一个公式A是假，当且仅当┐A是真。故不存在公式A，使得A和┐A在I中都真。证明：令v是I

中任意赋值。由已知条件知，v满足A和(A→B)。再由满足定义，v或者满足┐A或者满足B；又知v满足A，也即v不满足┐A。因此，v必须满足B.

由于v的任意性，则有I|=B。定理2.5.1

若I|=A∧(A→B)，则I|=B。定理2.5.2

I|=┐(A→B)当且仅当I|=A且I|=┐B。证明：必要性：设I|=┐(A→B)

A∧┐B

。

v是I

中任意赋值，于是v不满足A→B。根据满足定义，可知v既不满足┐A也不满足B。可见v满足A且不满足B。由v的任意性，则I|=A且I|=┐B。充分性：由I|=A且I|=┐B知，在I中每个赋值都满足A且满足┐B。即满足A∧┐B

┐(A→B)。定理2.5.3

I|=A当且仅当I|=(x)A，其中x为任意个体变元。证明：必要性：设I|=A。

v是I

中任意赋值，于是v满足A。

由于所有赋值都满足A，因此与v是x-等同赋值的v’也满足A。根据满足定义知，v满足(x)A。

由v的任意性，可知

I|=(x)A。充分性：设I|=(x)A。

v是I中任意赋值，v满足(x)A

。由于v与v自己是x-等同赋值以及满足定义，可知v满足A。由v的任意性，有I|=A。推论2.5.1

I|=A当且仅当I|=(x1)(x2)…(xn)A，其中

x1，x2，…，xn是任意n个个体变元。由定理2.5.3得知，在解释I中，A(x)为真当且仅当(x)A

为真。这表明，当考察有自由变元出现的公式真或假时，就有一种表示全称量词在此被省略了的意义。

在命题逻辑中有永真式，在谓词逻辑中也有类似概念，而且两者之间还有密切的关系。定义2.5.2

令A为命题逻辑中的公式，其中出现的命题变元为P1，P2，…，Pn。B1，B2，…，Bn是谓词逻辑中的公式，用Bi(1≤i≤n)处处代入A中的Pi而得到谓词逻辑中公式Aʹ

，记为，称Aʹ为A在谓词逻辑中的代入实例。若A为永真式，则称Aʹ为谓词逻辑的永真式。

例如，(x)A(x)→(x)A(x)是P→P

的代入实例，并且是谓词逻辑中的永真式。谓词逻辑中永真式的性质定理2.5.4

谓词逻辑的永真式在谓词逻辑的任何解释I中都为真。定理2.5.5

令I是谓词逻辑的一个解释，A是谓词逻辑的公式。如果v和w都是赋值，并且对A中的每个自由变元x，有v(x)＝w(x)。那么v满足A当且仅当w满足A。推论2.5.2

如果A是谓词逻辑中闭式，且I是谓词逻辑的一个解释，则或者I|=A或者I|=┐A。定义2.5.3

谓词逻辑的一个公式A称为逻辑有效的，如果公式A在谓词逻辑的每个解释下都是真；称A是矛盾的，如果它在每个解释下都是假的。前者记为|=A，后者记为|=┐A。

推论由定义2.5.3及定理2.5.4知，谓词逻辑的永真式都是逻辑有效的。作为定理2.5.1的推论，有：若|=A∧(A→B)，则|=B。即，若公式A和A→B是逻辑有效的，则B也是逻辑有效的。作为定理2.5.3的推论，有：|=A当且仅当|=(x)A。即，A是逻辑有效的当且仅当(x)A是逻辑有效的。例1.判断下列公式是否为逻辑有效：①(x)A→(x)A，其中A为任何公式，x为任意个体变元。②(x)(y)G(x，y)→(y)(x)G(x，y)解：①本公式是逻辑有效的。令I是谓词逻辑的任意解释，v是I中任意赋值。由于(x)A

→(x)A

┐(x)A

∨

(x)A

，

则考虑以下两种情况：

a.若v不满足(x)A,则v满足┐(x)A，即v满足┐(x)A∨(x)A；b.若v满足(x)A，则每个与v是x-等同赋值的v’满足A。显然，存在一个与v是x-等同赋值的v’满足A，于是v满足(x)A。故v满足┐(x)A

∨

(x)A。由I和v的任意性可知，公式┐(x)A

∨

(x)A是逻辑有效的。也即,公式(x)A→(x)A是逻辑有效的。例1.判断下列公式是否为逻辑有效：②(x)(y)G(x，y)→(y)(x)G(x，y)解：

②(x)(y)G(x，y)→(y)(x)G(x，y)

本公式不是逻辑有效的。只需构造一个解释及其不满足此公式的赋值即可。令DI为整数全体，G(x,y)：x>y。显然不管是哪个赋值，闭式(x)(y)G(x,y)在这一解释下都是真的，而(y)(x)G(x,y)是假的。即：每个赋值满足公式前件，不满足后件。因此不存在赋值满足给定公式。故它在这个解释I下不是真的，从而它不是逻辑有效的。2.6谓词逻辑中的等价式定义2.6.1

令A和B是谓词逻辑中的公式，若|=A

B，则称A和B是等价的，也记为AB。由于永真式都是逻辑有效的，故命题逻辑中的等价式(即命题定律)在谓词逻辑中都成立。定理2.6.1

有关量词否定的两个等价式：

①┐(x)A(x)┐A②┐(x)A(x)┐A证明①┐(x)A(x)┐A。令I为任意解释，v为I中任意赋值。再证v满足(x)┐A→┐(x)A

┐(x)

┐A∨┐(x)A.分两种情况讨论:

a.若v满足┐(x)┐A,

则v满足┐(x)┐A∨┐(x)A，即v满足(x)┐A→┐(x)A;

先证v满足┐(x)A→(x)┐A

(x)A∨(x)┐A.分两种情况讨论:

a.若v满足(x)A,则v满足(x)A∨(x)┐A，即v满足┐(x)A→(x)┐A;

根据满足的定义知，v满足公式┐(x)A(x)┐A

。由I和v的任意性知，┐(x)A(x)┐A是逻辑有效的，即┐(x)A(x)┐A。b.若v满足┐(x)A,则v不满足(x)A，即存在与v是x-等同赋值的vʹ不满足A,

于是vʹ满足┐A，也即是存在与v是x-等同赋值的vʹ满足┐A，即v满足(x)┐A.

则v满足(x)A∨(x)┐A，即v

满足┐(x)A→(x)┐A。

b.若v不满足┐(x)┐A,则v满足(x)┐A,则存在与v是x-等同赋值的vʹ满足┐A，

即vʹ不满足A,

于是v不满足(x)A,即v满足┐(x)A,则v满足(x)┐A→┐(x)A.

对于多重量词前置┐，可反复应用该定理，将逐次右移。

例如：┐(x)(y)(z)P(x，y，z)(x)(y)(z)┐P(x，y，z)定理2.6.2

有关量词辖域缩小或扩大的两组八个等价式。令B为没有x出现的公式，A(x)为有x自由出现的公式，则有：

①(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)(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)⑤(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.6.3

有关量词分配律的两个等价式：①(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)②(x)(A(x)∨B(x))(x)A(x)∨(x)B(x)注意：(x)对∨和(x)对∧都不满足分配律，即以下公式不成立：①(x)(A(x)∨B(x))(x)A(x)∨(x)B(x)②(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)令解释P，Dp为全体素数；E(x):x为偶数O(x):x为奇数①(x)(E(x)∨O(x))：对于任意素数x,x是偶数或者x是奇数，这个语句为真；

(x)E(x)∨(x)O(x)：对所有素数x都是偶数，或者所有素数x都是奇数，这是假语句。在解释P中(x)(A(x)∨B(x))(x)A(x)∨(x)B(x)为假，故它不是逻辑有效的。注意：(x)对∨和(x)对∧都不满足分配律，即公式不成立：①(x)(A(x)∨B(x))(x)A(x)∨(x)B(x)②(x)(A(x)∧B(x))(x)A(x)∧(x)B(x)令解释N，DN为全体自然数；E(x):x为偶数O(x):x为奇数②(x)(E(x)∧O(x))：存在自然数x,它既是偶数又是奇数,这是假语句；

(x)E(x)∧(x)O(x)：有些自然数x是偶数，并且有些自然数x是奇数，这是真语句。在解释N中(x)(A(x)∧B(x))(x)A(x)∧(x)B(x