第3 章 谓词逻辑 原子命题是命题逻辑中最基本的组成单元,不能对它再作进一步的分解,但同时也无 法反映出某些原子命题的共同特征和相互关系。 例如,用p 表示命题“小李是大学生”,用q 表示命题“小王是大学生”,在命题逻辑的 范畴中它们是两个独立的原子命题,p 和q 之间没有任何关系。但是,命题“小李是大学 生”和“小王是大学生”之间有相同的结构和内在的联系,它们都具有相同的谓语(及宾语) “是大学生”,不同的只是主语,它们都描述了“是大学生”这样一个共同的特性,而使用原 子命题表示时并没有能将这一共性刻画出来。 再如著名的苏格拉底三段论: 凡是人都是要死的。 苏格拉底是人。 所以苏格拉底是要死的。 这个推理显然是正确的。但是,如用p、q、r 分别表示上面3个命题,由于p∧q.r 不是 重言式,因此它不是正确的推理。也就是说,当p 和q 都为真时,得不出r 一定为真。其 80 离散数学及应用(第 3 版) 根本原因在于命题逻辑不能将命题p、q、 r 之间的内在联系反映出来。 为了克服命题逻辑的局限性,引入了谓词和量词对原子命题和命题间的相互关系做 进一步的剖析,从而产生了谓词逻辑。谓词逻辑也称一阶逻辑(first-orderlogic),它同命 题逻辑一样,是数理逻辑中最基础的内容。 从历史上讲,德国数学家、逻辑学家和哲学家弗雷格(FriedrichLudwigGotlob Frege,1848—1925)于1879年出版了著作《概念文字:一种模仿算术语言构造的纯思维 的形式语言》(Begriffschrift,aFormalLanguageofPureThoughtModeledupon thatofArithmetic),提出了一整套相对完备的谓词逻辑演算与推理理论,奠定了谓词逻 辑的基础。该著作在当时被誉为“可能是有史以来最重要的一部逻辑著作(pmostimportantsingleworkeverwriteninlogic)”。 erhapsthe 谓词逻辑可用于软件系统的建模和程序正确性及可终止性的证明。 3.谓词与量词 1 3.1.1 谓词 在谓词逻辑中,一般将原子命题分解为个体词和谓词两个部分。 定义3.个体词(l)是一个命题里表示思维对象的词,表示独立存在的具体或抽象的客体。简单地讲,(v) (n) 个体词表示各种事物,相当于汉语中的名词。具体的、确定 的个体词称为个体常项,一般用a、b、 c 表示;抽象的、不确定的个体词称为个体变项,一 般用x、y、 z 表示。个体变项的取值范围称作个体域或论域(difthediscourse,有 时也简写为domain),宇宙间一切事物组成的个体域称为全总个体(o) 域(u(no) (a) (m) niversaldomainof indiidl)。 注(v) :(u) 本(a) 书在提及论域时,(s) 如未特别说明,指的都是全总个体域。 定义3.在命题中,表示个体词性质或相互关系的词称作谓词()。 1 idiidua 2 predicate 可以这样来理解谓词: 如果命题里只有一个个体词,这时表示该个体词性质或属性的词便称为谓词。这是 一元(目)谓词,以P(x)、Q(x)等表示。 如果在命题里的个体词多于一个,那么表示这几个个体词间关系的词称为谓词。这 是多元(目)谓词,有 n 个个体的谓词P(x1,x2,…,xn )称 n 元(目)谓词,以P(x,y)、 Q (x,R(y,等表示。 y)、x,z) 用谓词表示命题,必须包括个体词和谓词两个部分。例如,在“小李是大学生”中,小(“) 李”和“大学生”都是个体词,“是大学生”是谓词;在“9大于4中,(”) “9”和“4都(”) 是个体词, “大于”是谓词。 准确地讲,谓词P(x)、Q(x,y)等是命题形式而不是命题。因为不仅没有指定谓词 符号P、 Q 的含义,而且个体词x、 y 也是个体变项,而不代表某个具体的事物,从而无法 第 3 章　谓词逻辑 81 确定P(x)、Q(x,y)的真值①。仅当赋予谓词确定含义,并且个体词取定为个体常项时, 命题形式才化为命题。如P(x)表示“ x 是素数”,那么P(7)是命题,真值为T;Q(x,y) 表示“ x 等于y”,那么 Q (4,5)是命题,取值为F。因此有时谓词也称为命题函数 (propositionalfunction)。 有时将P(3)、Q(2,3)这样不包含个体变项的谓词称为零元谓词。当赋予谓词确定 含义时,零元谓词为命题。因而可将命题看成特殊的谓词。 【例3.将下列命题在一阶逻辑中用零元谓词符号化, a) b) 1】并讨论(和(的真值。 (a)8是素数。 (b)如果3大于4,则2大于6。 (c)小明共修了21 个学分,而小红共修了15 个学分 。 解 : (a)设一元谓词P(x)为“ x 是素数”,则“8是素数”可符号化为零元谓词P(8), 真值 为假。 y) (b)设二元谓词G(x,为“ x 大于y”,那么“如果3大于4,则2大于6”符号化为零 元谓词G(3,4).G(2,6), 由于G(3,4)为假,所以该命题为真。 (c)设二元谓词S(y) x 共修了 y 个学分”则“ 而小红 x,为“ 21)∧S, ( 小明共修了21 个学分, 共修了15 个学分”符号化为零元谓词S(小明,小红,15 )。 3.1.2 量词 用来表示个体数量的词是量词(quantification), 给谓词加上量词称作谓词的量化。 量词可看作对个体词所加的限制、约束的词,但不是对数量(一个、二个、三个等)的具体描 述,而是讨论两个最通用的数量限制词。 定义3.符号.称作全称量词(nvrauniiain), 所有的 x ”任意 x ” 3 uieslqatfcto读作““ 或“一切 x ”,含义相当于自然语言中的“任意的”“所有的”“一切的”“每一个”“凡”等。 (.x)P(x)意指对论域 D 中的所有个体都具有性质P。命题(.x)P(x)当且仅当对论 域中的所有 x 来说P(x)均为真时方为真,此时称P(x)被全称量化。 定义3.符号.称作存在量词(n), 读作“存在 x ”,含义相当 于自然语言中的“某个”“存在”“有的”“至少有一个”“有些”等(o) 。(.x)P(x)意指论域 D 中至少有一个个体具有性质P,此时称P(x)被存在量化。 【例3.假设个体 x 的论域是全总个体域,一切事物都是运动的”可以形式化描 4 existentialquantificati 2】“ 述为(.x)( x 是运动的)。若以P(x)表示“ x 是运动的”,那么这句话可以写成(.x) (P(x)), 或者简写成(.x)P(x)或.xP(x)。 【例3.假设个体 x 的论域是全总个体域,有的事物是水果”可以形式化描述为 3】“ (.x)( x 是水果)。若以Q(x)表示“ x 是水果”,那么这句话就可写成(.x)(Q(x)), 或 者简写成(.x)Q(x)或.xQ(x)。 假设 D 为论域,则有:(.x)P(x)为真当且仅当{x|x∈D,P(x)为真}=D;(.x) ① 类似于函数形式f(y) x,并不是任何一个确定的值。 82 离散数学及应用(第 3 版) P(x)为真当且仅当{x|x∈D,P(x)为真}≠. 。 习题3. 1 3. ( 将下列命题用零元谓词表示。 1 a)天安门位于北京。 (b)小李不是教师,而是运动员。 (c)苗苗非常聪明和美丽。 (d)π和e都是无理数。 (e)俞伯牙和钟子期是好朋友 。 ( f) α 属于集合 A 或者集合B。 (g)乐乐既熟悉C++语言,又熟悉Java语言。 (h)鱼我所欲也,熊掌亦我所欲也 。 ( i)若3大于2且4大于3,则4大于2。 3.2 令论域为正整数集合,谓词Odd(x)表示“ x 是奇数”,Even(x)表示“ x 是偶数”, Prime(x)表示“ x 是素数”,Equal(x,y)表示“ x=y”,Greater(x,y)表示“ x>y”。 将以下各式译为汉语,并判断其真值。 (a)Prime(6)。 (b)(.x)~Odd(x)。 (c)(.x)rae5,)。 Getr( x (d)(.x)(.y)(Graer(x)∧Piy)) 。 ety,rme( (e)(.x)(.y)(ul(y+2)∧Pix)∧Pime())。 ( Eqax, l( rme(ryy)).En())。 f)(.x)(.y)(.z)((Equaz,x+y)∧Odd(x)∧Odd(vez 3.谓词公式及分类 2 与命题逻辑类似,可以对谓词逻辑中的公式进行定义和分类。 定义3.谓词逻辑中的谓词公式(dfa,递归地定义为: 5 lflf) (1)个体常项、个体变项、不含联结词的谓词)是谓词 公式。个体词的函数(w) 和原(o) 子(m) 谓词(o) (e) 公式((w) (mu) (r) (r) (e) (2)如果 A 是谓词公式,则~ A 也是谓词公式。 (3)如果 A 和 B 是谓词公式,则由逻辑联结词联结 A 和 B 构成的符号串也是谓词 公式,如(A∧B)、(A∨B)、(A.B)、(A.B)等。 (4)若 A 是谓词公式,且 A 中无. x 及. x 出现,则(.x)A(x)、(.x) A (x)也是 谓词公式。 (5)只有有限次地应用(1)~(4)构成的符号串才是谓词公式。 在不引起混淆的情况下,谓词公式也称为合式公式,简称公式。 【例3.~ p ~x,xF(.G())、(.x)(x).(.y)F 4】、P(y)∧Q()、(.x)(x)xA( 第 3 章　谓词逻辑 83 (x,都是合式公式, F(不是合式公式。 y)) 而(.x)(.x)x) 类似于命题逻辑中对命题公式进行的真值指派,可以对谓词公式赋予不同的解释。 定义3.谓词公式的一个解释(n)由下面4部分组成: 6 interpretatio (1)非空的论域D 。 (2) D 中一部分特定元素的具体取值 。 (3) D 上一些特定的函数的具体含义 。 (4) D 上一些特定的谓词的具体含义 。 注 : (a)解释规定了相应的个体常项、个体变项、函数符号及谓词符号的具体意义以及个 体变项的取值范围。 (b)如果两个解释的4个组成部分中至少有一部分不同,则这两个解释是不同的。 (c)一个公式可以用不同的解释给定含义,一个解释也可以对应多个不同的公式。 【例3.谓词公式(.x)f(2) 2是一个 5】P(x),的解释1为:论域 D 是正整数集合, 特定的整数,函数f(x)=4x,谓词 P (x,y)表示xy” (a)这句话可以形式化为(.x)(S(x).P(x))。 需注意的是这句话不能形式化为(.x)(S(x)∧P(x)), 这个公式的意思是说,对宇 宙间所有的事物 x 而言, x 既是素数又是整数。 一般地讲,“所有的 A 是B”“是 A 的都是B”“一切 A 都是B”这类语句的形式描述只 能使用.而不能使用∧。 (b)这句话的形式化描述应为(.x)(S(x)∧Q(x))。 需注意的是这句话不能形式化为(.x)(S(x).Q(x))。一般地讲,“有的 A 是B” 这类语句的形式化描述只能使用∧而不能使用.。 (c)这句话可以形式化为~(.x)(P(x).S(x)); 也可以把这句话理解为“有的整 数不是素数”,这时应形式化为(.x)(P(x)∧~S(x))。它们都是正确的,其理由将在 4节中阐述。 3. (d)这句话可以形式化为~(.x)(Q(x)∧R(x)); 也可以把这句话理解为“所有的 奇数都不是偶数”或者“所有的偶数都不是奇数”,这时应形式化为(.x)( Q (x). ~R(x)) 或者(.x)(R(x).~Q(x)), 它们都是正确的。 (e)这句话可以形式化为(.x)(S(x).(E(x,2)∨Q(x)))。 (存在个体x, 而且,对于任意个体y,如果它是整数, f)这句话的含义是“ 它是奇数; y)x,那么一定有y< x ”,因此可以形式化为(.x)(Q(x)∧(.y)(P(.G(y)))。 (g)这句话的含义是“存在个体x,它既是偶数又是素数;而且,如果还有个体 y 也是 既是偶数又是素数,那么一定有x=y”,因此可以形式化为(.x)(S(x)∧ R (x)∧ (.y)(S(y)∧R(y)x,)))。 .E( y (h)这句话和(g)的区别在于允许不存在偶素数,因此在形式化后也是不同的,应该 第 3 章　谓词逻辑 87 表示为(.x)(S(x)∧R(x).(.y)(S(y).E(x,)))。这句话也可以理解为 y)∧R( y “不存在不相等的两个个体,它们都既是偶数又是素数”,可形式化为~(.x)(.y)(S(x)∧ R(x)∧S(y)∧~E(y))。 ( y)∧R( R( x, x,.(.y)(.z)(y)∧S(x,)))。 i)形式化为(.x)(x)∧G(2)S(z)∧E(y+ z 【例3.假设论域是整数集, 并判断其真值。 11 】将下列语句翻译为谓词公式, (a)至少存在一个偶数,且至少存在一个奇数。 (b)至少有一个整数既是偶数又是奇数。 (c)对于任一个整数而言,它或者是偶数,或者是奇数。 (d)或者所有整数都是偶数,或者所有整数都是奇数。 (e)对于任一整数而言,都存在比它小的整数 。 (满足任何整数都大于它 。 f)存在一个整数, 解:令谓词P(表示“,Q(表示“,G(y) x>y”。 x) x 是奇数”x) x 是偶数”x,表示“ (a)这句话可以形式化为(.x)P(x)∧(.x)Q(x), 是真命题。 (b)这句话可以形式化为(.x)(P(x)∧Q(x)), 是假命题。 (c)这句话可以形式化为(.x)(P(x)∨Q(x)), 是真命题。 (d)这句话可以形式化为(.x)P(x)∨(.x)Q(x), 是假命题。 G(y), (e)这句话可以形式化为(.x)(.y)x,是真命题。 (f)这句话可以形式化为(.y)(.x)G(y), x,是假命题。 上述例子说明(.x)P(x)∧(.x)Q(x)和(.x)(P(x)∧Q(x))、(.x)(P(x)∨ Q(x)) P(Q(xG(y) G(y) 和(.x)x)∨(.x))、(.x)(.y)x,和(.y)(.x)x,含义不 同。这些都是容易混淆的,应注意加以区别。 【例3.假设论域是全总个体域, 12 】将下列语句翻译为谓词公式。 (a)没有人可以永生不死。 (b)天下乌鸦一般黑。 (c)金子一定闪光,但闪光的不一定是金子。 (d)所有的大学生都会说英语,有一些大学生会说法语 。 解 : (a)设P(x)表示“ x 是人”,Q(x)表示“ x 会死”。原语句可表示成~(.x)(P(x)∧ ~Q())。(b(x) )设F(x)表示“ x 是乌鸦”, G (x,y)表示“ x 与 y 一般黑”。原语句可表示成 (.x)(.y)(F(y)x,或者~(.x)(.y)(x)∧F(x,后 x)∧F(.G(y)) F(y)∧~G(y)), 者意为不存在个体x、 y 都是乌鸦但不一般黑,这两句话含义是相同的。 x) x 是金子”表示“ G(. (c)设G(表示“,L(x) x 会闪光”,原语句可表示成(.x)(x) L(x))∧(.x)(L(x)∧~G())。 (d)设S(x)表示“ x 是生”,E(x)表示“ x 会说英语”,F(x)表示“ x 会说法语”,大学(x) 原语句可表示成(.x)(S(x).E(x))∧(.x)(S(x)∧F(x))。 如果引入二元谓词C(x,表示“ 言”,那么原句子也可以表示为 y) x 可以说 y 这种语 (.x)(S(x).C(x,英语))∧(.x)(S(x)∧C(x,法语))。 88 离散数学及应用(第 3 版) 【13 】 例3.假设论域是实数集,将下列语句翻译为谓词公式。 (a)函数f(x)趋近 a 时的极限值是b。 (b)函数f(x)在点 a 处不存在极限值。 (c)函数f(x)在点 a 处连续。 (d)任意两个实数之间都存在一个有理数 。 解 : (a)原语句可表示 成 (.ε)(δ>0∧(.x)(|a|<δ.|b|<ε)) ) ε>0.(.δ)(x-f(x) (b)原语句可表示成 (.L)(.ε)(δ>0.(.x)(|a|<δ∧|f(x)L|≥ε))) ε>0∧(.δ)(x- (c)原语句可表示成 x-f(a)|<ε))) (.ε)(ε>0.(.δ)(δ>0∧(.x)(|a|<δ.|x)-f( (d)设P(x)表示“ x 是有理数”,则原语句可表示 成 (.x)(.y)((.(.z)(z)∧(z>y)) ) x>y)P(x>z)∧ ( 此例中采用了易于理解的谓词表示形式 。 总结上述各例,可以得到以下规律 : (a)“ 所有的 A 是B”“是 A 的都是B”“一切 A 都是B”应形式化为(.x)(A(x). B(x))。 (b)“ 有的 A 是B”应形式化为(.x)(A(x)∧B(x))。 (c)“ 所有的 A 都不是B”“是 A 的都不是B”“一切 A 都不是B”应形式化为(.x) (A(x).~B(x)) 或者~(.x)(A(x)∧B(x))。 (d)“ 有的 A 不是B”应形式化为(.x)( A (x)∧~B(x)) 或者~(.x)( A (x). B(x))。 y).Eqax, (e)“ 只有一个A”应形式化为(.x)(A(x)∧(.y)(A(ul(y)))。 (若存在 A 则唯一” A(.(.y)(y).Eqax,有 f)“ 应形式化为(.x)(x)A(ul(y))); 时也使用符号.! 表示量词“存在且唯一”。 (g)“ 所有的 A 和 B 都具有关系C”应形式化为(.x)(.y)( A (x)∧ B (y). C(x,))。 y (h)“ 任何一个 A 都存在一个 B 与之对应满足性质C”应形式化为(.x)(A(x). (.y)(B(x, y)∧C(y)))。 习题3. 3 3.令论域为正整数集合,谓词Odd(x)表示“ x 是奇数”,Een(x)表示“ x 是偶数”, 7 vPrime(x)表示“ x 是素数”,Equal(x,y)表示“ x=y”,Greater(x,y)表示“ x>y”。 利用谓词公式翻译下列命题。 (a)有不是奇数的素数。 (b)存在奇数x、 y 和偶数 z 使得 x 与 y 的和大于 x 与 z 的和。 第 3 章　谓词逻辑 89 (c)对于任意的正整数x、y,存在正整数 z 使得x+z=y。 (d)存在大于10000 的偶数。 (e)存在介于2和6之间的正整数 。 ( f)只存在唯一的奇数1。 (g)没有最大的素数。 3.8 将下列命题用谓词表示出来,使用全总个体域。 (a)人都生活在地球上。 (b)有的人长着金色头发。 (c)并不是所有的实数都能表示成分数。 (d)没有能表示成分数的无理数。 (e)任意的偶数 x 与 y 都有大于1的公因子 。 (它们没有大于1的公因子 。 f)存在奇数 x 与y, (g)只有一个北京。 (h)任何金属都可以溶解在某种液体中 。 ( i)有一种液体可以溶解任何金属。 (j)尽管有些人是勤奋的,但并非所有人都勤奋。 3.谓词逻辑的等值演算 4 如例3.b)所示,有些语句的形式化表述可能不止一种,但它们的含义都是相同 的。因此需在谓词逻辑中也引入“等值”的概念。 12( 定义3.设 A 和 B 是两个谓词公式, 则称 A 与 B 等值, 11 若A. B 是逻辑有效式, 记作A≡B。 注:类似于命题逻辑,两个谓词公式 A 和 B 等值当且仅当在任何解释下 A 和 B 的 真值都相同。 相比命题逻辑,量词和谓词的引入使得谓词演算应用广泛。特别是在计算机科学、人 工智能等领域,谓词逻辑是表示知识、实现推理的有力工具。 类似于命题逻辑,谓词逻辑的等值演算仍是以基本等值式为基础,应用等值演算规则 逐步推演。 谓词逻辑中的基本等值式主要分为两类:其一是从命题公式移植来的等值式,即命 题逻辑中基本等值式的代换实例,如(.x)F(x).(.y)G(y)≡~(.x)F(x)∨(.y) G(y)和~((.x)F(x)∨(.y)G(y))≡~(.x)F(x)∧~(.y)G(y)等;另一类是谓 词逻辑特有的等值式,与量词有关。 定理3.( 设论域D={a2,…,} 则有 3 消去量词等值式) a1,am 是有限集合 , (a)(.x)A(x)≡A(a2)∧…∧A() 。 a1)∧A(am A(a1)∨A( (b)(.x)x)≡A(a2)∨…∨A(am )。 注:这一组等值式表明,对于有限论域而言,全称量词与合取式相对应,存在量词则 对应于析取式。 90 离散数学及应用(第 3 版) 【14 】a,c}, 消去下面公式中的量词。 例3.设论域D={b, (a)(.x)(P(x)∨Q(x)) 。 (b)(.x)(P(x).(.y)Q(y)) 。 (c)(.x)(.y)R(x,) 。 y 解: (a)(.x)(x))≡(P(a))∧(P(b))∧(P(c)) P(x)∨Q(a)∨Q(b)∨Q(c)∨Q( (b)(.x)(P(x).(.y)Q(y)) ≡(.x)(~P(x)∨(.y)Q(y)) ≡(~a)∨(.y)y))∧(P(Q(~c)∨(.y)Q(y)) P(Q(~b)∨(.y)y))∧(P( ~a)∧~P( ≡(P(c))∨(.y)Q(y)(分配律) ≡(~a)∧~P(Q(b)∨Q( b)∧~P( c))∨(c) ) (c)(.x)(.y)x, P(b)∧~P(a)∨Q( R(y) ≡(.x)(R(a)∧R(b)∧R(x,c) ) x,x, ≡(R(a)∧R(b)∧R(c))∨(R(a)∧R(b)∧R(c))∨(R(a)∧ a,a,a,b,b,b,c, R(b)∧R(c)) c,c, 或者 (.x)(.y)R(y) x, ≡((.y)R(y))∨((.y)b,R(y) ) a,R(y))∨((.y)c,, ≡(R(a)∧R(b)∧R(c))∨(R(a)∧R(b)∧R(c))∨(R(a)∧ a,a,a,b,b,b,c, R(b)∧R(c)) c,c, 定理3.(量词否定等值式/德摩根律)设A(x)是含 x 自由出现的公式,则有 4 (a)~(.x)A(x)≡(.x)~A(x)。 (b)~(.x)A(x)≡(.x)~A(x)。 即,“不是论域中所有个体都具有性质A”和“论域中至少存在一个个体不具有性质 A”二者含义是完全相同的,“论域中不存在具有性质 A 的个体”和“论域中所有个体都不 具有性质A”二者含义也是完全相同的。 当论域D={am 有 a2,…, } ~(A(a2)∧…∧A(A(~A( a1,是有限集合时, a1)∧A(am ))≡~(.x)x)≡(.x)x) ≡~A(a2)∨…∨~A() a1)∨~A(am ~(A(a2)∨…∨A())≡~(.x)x)≡(.x)x) a1)∨A(am A(~A( ≡~A(a2)∧…∧~A() 即是命题逻辑中德摩根律的表现形式。 a1)∧~A(am 定理3.5 (量词辖域收缩与扩张等值式)设A(x)是含 x 自由出现的公式,谓词公式 B 中不含 x 的出现,则有 (a)(.x)(A(x)∨B)≡(.x)A(x)∨B。 (b)(.x)(A(x)∨B)≡(.x)A(x)∨B。 (c)(.x)(A(x)∧B)≡(.x)A(x)∧B。 (d)(.x)(A(x)∧B)≡(.x)A(x)∧B。 第 3 章　谓词逻辑 91 证明:仅证明(a), 余者类似。 假设在某一解释 I 下,(.x)( A (x)∨B)为真,于是对任一x∈ D 有 A (x)∨ B 为真。如 果 B 为真,则(.x)A(x)∨ B 为真 x) 。 于是(.x)x) 从而(.x)x)∨B如果 B 为假,则对于任一x∈ D 有A(为真, A(为真, A( 为真。假 设在某一解释 I 下,(.x)( A (x)∨B)为假,于是存在x∈ D 使得 A (x)∨ B 为 假,则 B 和A(x)取值都为假。这表明 B 和(.x)A(x)都为假,即(.x)A(x)∨ B 为假。 □ 定理3.6 (量词分配等值式)设A(x)和B(x)是含 x 自由出现的谓词公式,则有 (a)(.x)(A(x)∧B(x))≡(.x)A(x)∧(.x)B(x)。 (b)(.x)(A(x)∨B(x))≡(.x)A(x)∨(.x)B()。 证明:仅证明(a), 即.对∧的分配律。假设在某一解释(x) I 下(.x)(A(x)∧B(x)) 为真。于是对任一x∈ D 有 A (x)∧ B (x)为真,即 A (x)为真且 B (x)也为真,从而 (.x)A(x)∧(.x)B(x)为真。 反过来,如果(.x) A (x)∧(.x) B (x)在一某解释 I 下为真,则(.x) A (x)和 (.x)B(x)均为真,于是对任一x∈ D 有A(x)和B(x)均为真,即(.x)(A(x)∧B(x)) 为真。 .对∨的分配律可类似地证明。□ 注: (a)以上两等值式的成立,实际上也反映了全称量词.与合取∧的对应,存在量词. 与析取∨的对应,以及合取∧、析取∨这两种运算都满足交换律和结合律。 (b).对∨不满足分配律,.对∧不满足分配律。即(.x) A (x)∨(.x)B(x)与 (.x)(A(x)∨B(x)) 不等值,(.x)A(x)∧(.x)B(x)与(.x)(A(x)∧B(x)) 不等 值(可参看例 7 3. y) 11 ) 。 定理3.设A(x,是含x、 y 自由出现的谓词公式,则 有 A(y)≡(.y)(.x) y (a)(.x)(.y)x,A(x,) 。 (b)(.x)(.y)x,A(x,) 。 A(y)≡(.y)(.x) y 24 ) 。 这组等值式的证明将在3.6节中作为例题给出(例3. 注:这组等值式表明,相同量词与排列的次序无关,但是不同量词不能随意更换次 序,即(.x)(.y)x,与(.y)(.x)x,不等值( 11 )。 A(y) A(y) 可参看例3. 定义3.在仅含有联结词~、∧、∨的谓词公式 A 中,将∨换成∧,将∧换成∨,将 全称量词.换成存在量词.,将存在量词.换成全称量词.,若包含F和T也相互取代, 所得谓词公式称为 A 的对偶式(dual), 记作A*。 谓词逻辑中的对偶可看作命题逻辑中对偶的扩展,依然满足如下结论。 定理3.8 (对偶原理)设 A 和 B 为两个仅含有联结词~、∧、∨的谓词公式,若A≡ B,则A*≡B*。 例如,由(.x)(A(x)∧ B (x))≡(.x) A (x)∧(.x) B (x)可得(.x)( A (x)∨ 12 92 离散数学及应用(第 3 版) x))≡(.x)x)∨(.x)x), 由~(.x)x)≡(.x)A(可得~(.x)x)≡B(A(B(A(~x) P( (.x)~P(x)。 11 给出的3条等值演算规则。 谓词逻辑包括定理3.9~定理3. 定理3.9 (置换规则)设Φ(A)是含谓词公式 A 的公式,Φ(B)是用谓词公式 B 取代 Φ(A)中的A(不一定是每一处)之后得到的谓词公式,若A≡B,则Φ(A)≡Φ(B)。 谓词逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同,只是在这里 A 和 B 是谓词公式。 9(的公式(.x)x)∨Q(y)同一个个体变项符号,在例3.b) P(x,中的符号 x 既有约 束出现又有自由出现,而在例3.d) L(y) H (y)) 9(的公式(.x)((.y)x,.(.y)x,中的 符号 y 被不同的量词所约束,这就容易引起概念上的混淆。为避免这种情况,引入了下 面的代替规则和换名规则,使得同一个个体变项符号在一个公式中只呈现一种形式,要么 为约束出现,要么为自由出现;同时使不同的量词所约束的个体变项不同名,便于计算机 处理。 定理3.(代替规则)将谓词公式 A 中某个自由出现的个体变项的所有自由出现 10 改成 A 中未曾出现的某个个体变项符号,其余部分不变,记所得谓词公式为A' ,则 A≡A'。 11 换名规则) 定理3.( 将谓词公式 A 中某量词的指导变项及其在辖域内的所有约 束出现改成该量词辖域内未曾出现的某个个体变项符号,其余部分不变,记所得谓词公式 为A' ,则A≡A'。 定理3.11 即(.x)x)≡(.y)y),(.x)x)≡(.y)y)。这 10 和定理3.A(A(A(A( 是不难理解的,因为在同一论域 D 上,对(“) 一切个体x,同“ y x 具有性质P” 对一切个体y, 具有性质P”这两者除变项 x 和 y 的区别外并无差异,从而(.x)A(x)与(.y)A(y)有 相同的真值。 表3. 1对代替规则和换名规则进行了比较。 表3.代替规则和换名规则的比较 1 比较项代替规则换名规则 使用对象任一谓词公式任一谓词公式 改名对象自由变项指导变项及其在辖域内的所有约束出现 改名方式 对公式中出现的所有同名的自由变项 进行改名 对指导变项及其量词辖域中出现的约束变项 处处进行改名 改名限制公式中未曾出现的某个个体变项符号新的变项符号应是该量词辖域内未曾出现的 改名结果与原公式等值与原公式等值 【例3.将公式(.x)F(x,z)G(x,z) 使其 15 】y,.(.y)y,化为与之等值的公式, 没有既是约束出现又是自由出现的个体变项符号。 解:(.x)F(x,z).(.y)G(x,z) ≡(.u)F( y, z)G( y, z)(换名规则) u,.(.y)x, y,y, 第 3 章　谓词逻辑 93 ≡(.u)F(y,G(v,( u,z).(.v)x,z) 换名规则) 或者 (.x)F(y,.(.y)x,z) x,z)G(y, ≡(.x)F(u,.(.y)x,z) 代替规则 ) x,z)G(y, ( ≡(.x)F(u,.(.y)v,z) 代替规则 ) x,z)G(y, ( 使用这两类基本等值式和上述3条规则,可以进行谓词逻辑的等值演算 。 【例3.证明以下等值式成立 。 16 】 A(x)∨B(A(x)∨(.x)B( x (a)(.x)(.y)(y))≡(.x)) 。 (b)(.x)(A(x).B(x))≡(.x)A(x).(.x)B(x) 。 (c)(.x)(.y)(y))≡(.y)(.x)()) 。 P(x).Q(P(x).Q( y 解 : (a)(.x)(.y)(x)∨B( A(y) ) x)∨(.y)y) ) ≡(.x)(A(B((量词辖域收缩等值式) x)∨(.y)y) ≡(.x)A(B((量词辖域收缩等值式) ≡(.x)A(x)∨(.x)B(x)(换名规则) (b)(.x)(A(x).B(x) ) ≡(.x)(~A(x)∨B(x)) (置换规则 ) ≡(.x)~A(x)∨(.x)B(x)(量词分配等值式 ) ≡~(.x)A(x)∨(.x)B(x)(德摩根律 ) ≡(.x)A(x).(.x)B(x)(置换规则 ) (c)(.x)(.y)(y))≡(.x)(.y)(y)) P(x).Q(~P(x)∨Q( ≡(.x)~x)∨(.y)y) P(Q( (.y)(.x)(P(.Q(~x)∨Q( x)y))≡(.y)(.x)(P(y)) ≡(.x)~x)∨(.y)y) P(Q( 即(.x)(.y)(P(x).Q(y)) 和(.y)(.x)(P(x).Q(y)) 都与同一个谓词公式 等值。下 面证明例3.12(b)的两种形式化描述等值。 【例3.设F(表示“,x,y) x 与 y 一般黑” 天下乌鸦一 17 】x) x 是乌鸦”G(表示“ 。“ 般黑”可表示成(.x)(.y)( F (x)∧ F (y). G (x,y)) 或者~(.x)(.y)( F (x)∧ F(y)∧~G(x,后一种形式意为不存在个体 x 和 y 都是乌鸦但不一般黑,下面证明 y)), 这两个命题公式是等值的: ~(.x)(.y)(F(y)∧~G(y)) x)∧F(x, ≡(.x)~(.y)(x)∧F(x, F(y)∧~G(y)) ≡(.x)(.y)~(x)∧F(x, F(y)∧~G(y)) ≡(.x)(.y)(~(x)∧F(x, F(y))∨G(y)) ≡(.x)(.y)(F(x)∧F(.G(y)) y)x, 94 离散数学及应用(第 3 版) 习题4 3. 3.9 判断下列公式的类型,若是逻辑有效式,则给出证明,否则举出反例。 (a)(.x)P(x).((.x)P(x)∨(.y)G(y))。 (b)(.x)P(x).((.x)(.y)x,.(.x)P(x))。 H (y) (c)~((.x)A(x).(.x)B(x))∧(.x)B(x) 。 (d)(.x)(.y)P(x,.(.x)(.y)P(y) 。 y)x, 3.设论域为{b,试消去下列谓词公式中的量词。 10 a,c} , (a)(.x)P(x).(.x)Q(x) 。 (b)(.x)(P(x)∨(.y)y)) 。 (c)(.y)(.x) H (x,)。 Q( y 3.将下列公式化为与之等值的公式,使其没有既是约束出现又是自由出现的个体变 11 项符号。 PP( (xy,y)∨ )∨ (. (. yy) )Qx(x, ,yz , z (a)(.x)x,Q(y,) 。 (b)(.x)()) 。 (c)(.x)(.y)(x)x,.L(y) 。 P(.R(y))x, (d)((.x)x,.(.y)x,.(.x)(.y)x, P(y)Q(y))R(y)。 3.设A(x)是含 x 自由出现的公式,谓词公式 B 中不含 x 的出现,证明下列等值式。 12 (a)(.x)(A(x).B)≡(.x)A(x).B 。 (b)(.x)(A(x).B)≡(.x)A(x).B 。 (c)(.x)(B.A(x))≡B.(.x)A(x) 。 (d)(.x)(B.A(x))≡B.(.x)A(x) 。 3.证明下列等值式。 13 (a)(.x)(.y)(A(x)∧B(y))≡(.x)A(x)∧(.x)B(x)。 (b)~(.x)( M (x)∧F(x))≡(.x)( M (x).~F()) 。 (c)(.x)(.y)(P(x).Q(y))≡(.x)P(x).(.yy) 。)(x) Q( (d)((.x)P(x)∧(.x)Q(x)∧(.x)R(x))∨((.x)P(x)∧(.x)Q(x)∧ (.x)S(x))≡(.x)(P(x)∧Q(x))∧(.x)(R(x)∨S(x))。 3.前束范式 5 在命题逻辑中,讨论过命题公式的规范的、标准的形式,即范式。在谓词逻辑中,谓词 公式也有与之相对应的范式。 定义3.13 设 A 为谓词公式,如果满足以下条件: (1)所有量词都位于该公式的最左边。 (2)所有量词前都不含否定词。 (3)量词的辖域都延伸到整个公式的末端。 95 第 3 章　谓词逻辑 则称 A 为前束范式(prenexformalform)。 前束范式的一般形式为 x2,…,) 其中,Qi(1≤i≤n)为.或.,Q1x1Q2x2…Qnxn 称为前束(prenex); M 为不含量词的公 式,称作公式的基式或母式(trix)。 例3.~(x)yx,S(y) Q1x1Q2x2…QnxnM (x1,xn 【18 】(.x)(.y)(ma) P(.Q())、(.x)(.y)R(y)、x,都是前束 范式,而~(.x)x,和(.x)x)∨(.x)x) R(y) P(Q(都不是前束范式 。 下面给出求前束范式的基本方法 。 (1)消去谓词公式中的联结词.和.。 (2)将谓词公式中的否定词~右移。 (3)将谓词公式中的量词左移(使用量词分配等值式、量词辖域收缩与扩张等值式), 必要时将变项改名。 【例3.求(.x)x,x, 19 】P(y).~(.y)Q(y)的前束范式 。 解:(.x)P( xy, ) .~(.yQ) ( xy, ) ~(.y)x,.(.x) x,.~(.y)x, ≡((.x)P(y)Q(y))∧(Q(y)P(x,y)) (消去联结词.) ≡(~(.x)x,Q(y))∧(Q(y)∨(.x)x, P(y)∨~(.y)x,~~(.y)x,P(y)) (消去联结词.) ≡(~(.z)z,Q(u))∧(~~(.v)x,P(y)) P(y)∨~(.u)x,Q(v)∨(.w)w, (换名规则) ≡((.z)P(Q(u))∧((.v)x,P(y)) z,x,Q(v)∨(.w)w,~y)∨(.u)~ (~右移) ≡(.z)(~P(y)∨~Q(x,Q(v)∨(.w)w, z,z))∧((.v)x,P(y)) (量词分配等值式) ≡(.z)(~z,x,Q(v)∨P(y)) P(y)∨~Q(z))∧(.v)(.w)(x,w, (量词左移) ≡(.z)(.v)(.w)((~P(y)∨~Q(z))∧(Q(v)∨P(y))) z,x,x,w, ≡(.z)(.v)(.w)S(x,z,w) (量词左移) y,v, 注:使用以上步骤,可求得任一公式的前束范式。由于每一步变换都保持等值性,所 以得到的前束形式与原公式是等值的。这里的S(x,z,w)便是原公式的母式。 y,v, 由于前束中对量词的次序排列没有约束,如(.v)(.w)也可以写成(.w)(.v), 并 且对母式没有明确的限制,自然其前束范式并不唯一。例如, 19 的前束范式也可 例3. 以是 (.z)(.w)(.v)(S(y,v, 其中 P 可以是任一不含量词的逻辑有效式。 x,z,w)∧P) 事实上,有如下结论。 定理3.12 (前束范式存在定理)任一谓词公式都存在与之等值的前束范式,但其前 96 离散数学及应用(第 3 版) ≡~(.x)P(y)∨(~(.y)Q(y)∨(.z)R(z)) 束范式并不唯一。 【例3.20 】求下列公式的前束范式。 (a)(.x)F(x)∧~(.x)G(x) 。 (b)(.x)F(x)∧~(.x)G(x) 。 (c)(.x)y).((.y)Q(y)z)) 。P(x,x,.(.z)R(x, 解: (a)(.x)F(x)∧~(.x)G(x) ≡(.x)F(x)∧(.x)~G(x) ≡(.x)(F(x)∧~G(x)) (b)(.x)F(x)∧~(.x)G(x) ≡(.x)F(x)∧(.x)~G(x) ≡(.x)F(~y)x)∧(.y)G( ≡(.x)(.y)(F(x)∧~G(y)) (c)(.x)x,Q(R(z)) P(.((.y)x,x,y)y).(.z) (量词分配等值式) (换名规则) (量词辖域扩张等值式) x,x,x, ≡(.x)~x,x,R( y)∨((.y)~z)) P(Q(y)∨(.z)x, ≡(.x)~x,~x,x,量词辖域扩张等值式) P(y)∨(.y)(.z)(Q(y)∨R(z))( ≡(.u)~u,Q(y)∨R( v)∨(.y)(.z)(z))( 代替规则、换名规则) ≡(.u)(.y)(.z)(~u,x,x,量词辖域扩张等值式) P(~x,x, P(v)∨~Q(y)∨R(z))( 习题3. 5 3.将下列公式化为等值的前束范式。 14 (a)(.x)F(x).(.x)G(x)。 (b)(.x)F(x).(.x)G(x)。 (c)(.x)(P(x)Q(y))。 .(.y)x, (d)((.x)x,.(.y)y)) H (y)。 F(y)G(.(.x)x, 3.谓词逻辑的推理 6 与命题逻辑的推理相同,谓词逻辑的推理也是从某些给定的前提出发,根据一些基本 的推理规则推导出相应结论的过程。因而,谓词逻辑推理的形式与命题逻辑推理的形式 是一致的。 在谓词逻辑中,从前提H1,H2,…,Hn 出发推出结论 C 的推理形式结构,依然采用 如下的蕴涵式形式: (H1∧H2∧…∧Hn ). C 若上式为逻辑有效式,则称推理正确,称 C 为前提H1,H2,…,Hn 的逻辑结论或有效结 论;否则称推理不正确。于是,在谓词逻辑中判断推理是否正确便归结为判断蕴涵式是否 第 3 章　谓词逻辑 97 为逻辑有效式的问题。 由于在谓词逻辑中不能使用真值表法,又不存在判别A. B 是否逻辑有效的一般方 法,从而使用基本推理公式及推理规则是谓词逻辑的基本推理演算方法。 除命题逻辑中基本推理公式的代换实例外,还有一些谓词逻辑特有的、与量词相关的 推理公式。 定理3.(基本推理公式)以下蕴涵式都是逻辑有效式。 13 (a)(.x)P(x)∨(.x)Q(x).(.x)(P(x)∨Q(x))。 (b)(.x)(P(x)∧Q(x)).(.x)P(x)∧(.x)Q(x)。 (c)(.x)(P(x).Q(x)).((.x)P(x).(.x)Q(x))。 (d)(.x)(P(x).Q(x)).((.x)P(x).(.x)Q(x))。 (e)((.x)P(x).(.x)Q(x)).(.x)(P(x).Q(x))。 (f)(.x)(P(x).Q(x)).((.x)P(x).(.x)Q(x))。 (g)(.x)(P(x).Q(x)).((.x)P(x).(.x)Q(x))。 (h)(.x)(P(x).Q(x))∧(.x)(Q(x).R(x)).(.x)(P(x).R(x))。 (P(.Q(a)a)。 i)(.x)(x)x))∧P(.Q( 至此,可以总结一下。两个量词的公式有下列8种情况:(.x)(.y) P (x,y)、 (.y)(.x)P(x,)、(.x)(.y)P(y)、(.y)(.x)x,)、(.x)(.y)P(y)、 yx,P(yx, (.y)(.x)P(x,)、(.x)(.y)P(x,)、(.y)(.x)P(x,)。 yyy 它们之间的等价关系与蕴涵关系如下(可参看图3. 1)。 图3.14 用图 1 定理3. 定理3.以下谓词公式都是逻辑有效式。 14 (a)(.x)(.y)x,.(.y)(.x)P(x, P(y)y)。 (b)(.x)(.y)P(x, y) .(.x)(.y)P( yy)。 y)x, (c)(.y)(.x)P(x,.(.y)(.x)P(x,)。 (d)(.x)(.y)x,.(.y)(.x)P(x, P(y)y)。 (e)(.y)(.x)P(x,.(.x)(.y)P(y)。 y)x, (P(y)P(y)。 f)(.y)(.x)x,.(.y)(.x)x, x,.(.x)(.y)y (g)(.x)(.y)P(y)P(x,)。 (h)(.y)(.x)P(x,.(.x)(.y)P(y)。 在图3. y)x, 1中未出现的有向边表示两者之间没有必然联系。 98 离散数学及应用(第 3 版) 例如,假设论域 D 限定为正整数集合,解释1中谓词P(x,y)表示x=y,解释2中 谓词P(x,表示xy, x,表示x≥y, x,表示 x≤y。 y) y=解释3中谓词P(y) 解释4中谓词P(y) 在解释1下命题(.x)(.y) P (x,y)为真,命题(.x)(.y) P (x,y)为假,命题 (.y)(.x)P(y) x,为真。 在解释2下命题(.x)(.y) P (x,y)为假,命题(.x)(.y) P (x,y)为真,命题 x,为真。(.y)(.x)P(y) x,为真, P(y) 在解释3下命题(.y)(.x)P(y) 命题(.x)(.y)x,为假。 在解释4下命题(.y)(.x)P(y) 命题(.x)(.y)x,为真。 x,为假, P(y) 而谓词逻辑使用的推理规则除命题逻辑的推理演算中用到的6条基本推理规则外, 还包括4条有关量词的消去和引入规则。 (a)全称量词消去规则,也称作全称举例规则(UniversalSpecification,US): (.x)P(.P(或(.x)P(x)a) x)y).P( 其中 y 是论域中任一个体。该规则意为,如果所有的x∈ D 都具有性质P,那么 D 中任 一个体 y 或特定个体 a 必定具有性质P。 使用该规则的条件如下: (1)第一式中,取代 x 的 y 应为任意的不在P(x)中约束出现的个体变项。 (2)第二式中, a 为任意个体常项。 (3)用 y 或 a 取代P(x)中自由出现的 x 时,必须对 x 的所有自由出现进行取代。 (b)全称量词引入规则,也称作全称推广规则(UiversalGeneralization,UG): P(.(.x)x)(n) y)P( 其中 y 是论域中任一个体。该规则意为,如果任一个体y∈ D 都具有性质P,那么 D 中 所有个体 x 都具有性质P。 使用该规则的条件如下: (1)无论P(中自由出现的个体变项 y 取何值,y)应该均为真。 y) P( (2)取代自由出现的 y 的 x 不能在P(y)中约束出现。 (c)存在量词消去规则,也称作存在举例规则(ExistentialSpecification,ES): (.x)P(.P( x)a) 其中 a 是论域中的一个个体常项。该规则意为,如果论域 D 中存在某个体具有性质P, 那么必有特定个体 a 具有该性质P。 使用该规则的条件如下 : (1) a 是使 P 为真的特定的个体常项 。 (2) a 不在P(x)中出现 。 (3)P(x)中没有其他自由出现的个体变项 。 (4) a 是在推导过程中未曾使用过的 。 (d)存在量词引入规则,也称作存在推广规则(ExistentialGeneralization,EG): P(.(.x)x) a)P( 其中 a 是论域中一个体常项。该规则意为,如果有个体常项 a 具有性质P, P( 必为真。 那么(.x)x)