第2章-逻辑代数(下)：谓词演算.ppt

1、离散数学,第2章 逻辑代数（下）：谓词演算,离散数学第2章 逻辑代数（下）：谓词演算,第2章 逻辑代数（下）：谓词演算,离散数学第2章 逻辑代数（下）：谓词演算,问题1：为何要讲谓词演算？ 例1：数学中的常用判断无法用命题逻辑的形式准确描述。 如： x 5 实数的平方非负 例2：无法很好地刻画推理机制。 如： 所有的人都是要死的 苏格拉底是人 苏格拉底是要死的 命题演算不足的原因忽略了命题内部的细节。,第2章 逻辑代数（下）：谓词演算,离散数学第2章 逻辑代数（下）：谓词演算,问题2：原子命题内部究竟有那些细节？ 例2： 所有的人都是要死的 苏格拉底是人 苏格拉底是要死的 三个命题涉及两个概念

2、： 1）表示事物的性质： “是人”、“是要死的” 称谓词。 2）表示主体： “所有的人”、“苏格拉底” 称个体。 “所有的人”中还使用了数量词“所有”称量词。,第2章 逻辑代数（下）：谓词演算,离散数学第2章 逻辑代数（下）：谓词演算,2.1.1 个体,2.1 谓词演算基本概念,个体：谓词演算中的一切讨论对象。 个体可以是客观世界中的具体客体，也可以是抽象的客 体，诸如数字、符号等。 确定的个体：常用a，b，c 等小写字母或字母串表示。 个体常元 不确定的个体：常用字母 x，y，z，u，v，w 等表示。 个体变元或变元,离散数学第2章 逻辑代数（下）：谓词演算,2.1.1 个体,2.1 谓词演

3、算基本概念,个体域：讨论对象（个体）的全体。 集合论中的全集（D），任何D都至少含有一个成员。 当讨论对象遍及一切客体时，个体域特称为全总域（U）。 当给定个体域时：常元表示该域中的一个确定的成员； 变元可以取该域中的任何一个成员为其值。 个体项：由D上个体间运算的运算符、常元、变元组成。 如： a2+b x2c,离散数学第2章 逻辑代数（下）：谓词演算,谓词：表示个体性质或个体之间关系。 例如：M(x)：“苏格拉底是人”中“是人” 整个语句为M(Socrates)。 D(x)：“苏格拉底是要死的”中“是要死的” 整个语句为D(Socrates)。 又如：“3是小于2”可表示为： L(3,2)

4、 （L(x,y)：x小于y） “3加2等于5”可表示为： ADD(3,2,5) （ADD(x,y,z)：x加y等于z）,2.1.2 谓词,2.1 谓词演算基本概念,离散数学第2章 逻辑代数（下）：谓词演算,“x是小于100的质数”可表示为: L(x,100)P(x) （L(x,100)：x小于100；P(x)：x是质数） “小张是教师，或者是工程师”可表示为: T(xiaozhang)E(xiaozhang) （xiaozhang：小张；T(x)：x是教师；E(x)：x是工程师） “如果一个人生于北京，那么他不生于上海”可表示为: B(x,beijing)B(x,shanghai) （B(x,

5、y)：x生于y）,2.1.2 谓词,2.1 谓词演算基本概念,离散数学第2章 逻辑代数（下）：谓词演算,2.1.3 量词,2.1 谓词演算基本概念,量词：指数量词“所有的”（“每一个”）和“有”，分别用符号 和 来表示， 称为全称量词和存在量词。 量词的表示和意义： xP(x) ：读作“所有（任意，每一个）x满足P(x)”。 表示个体域中所有的个体满足谓词P(x)。 xP(x)： 读作“有（存在，至少有一个）x满足P(x)”。 表示个体域中至少有一个体满足谓词P(x)。 x ： 量词的指导变元，填在谓词P(x) 中。,离散数学第2章 逻辑代数（下）：谓词演算,关于量词的说明： (1) x 称指

6、导变元，其名字不重要 量词的指导变元和量词“管辖” 的谓词填式中的变元是可以改名的。 (2) 量词不仅可用于谓词填式之前，还可用于复合的谓词表达式 之前，这时应对该表达式使用括号。 如： x(M(x)B(x) （有的个体是人且是勇敢的） x(M(x)D(x) （所有个体中凡人者是要死的） x(L(x,2)L(x,2) （所有个体或者小于2或者不小于2） xyz (ADD(x,y,z)ADD(y,x,z) （数的加运算满足交换律）,2.1.3 量词,2.1 谓词演算基本概念,离散数学第2章 逻辑代数（下）：谓词演算,量词的辖域： 当量词用于谓词填式或复合的谓词表达式时，该谓词或复合 的谓词表达式

7、称为量词的辖域。 量词的辖域或者是紧邻其右侧的那个谓词；或者是其右侧第 一对括号内的表达式。 (3) 约束变元和自由变元： xP(x) 和 xP(x)中的变元 x 可以改名却不能取值代入。 通常谓词填式中的个体变元可以取值代入。 xP(x) 和 xP(x) 中变元称为约束变元 可以取值代入的变元则称为自由变元。,2.1.3 量词,2.1 谓词演算基本概念,离散数学第2章 逻辑代数（下）：谓词演算,(4) xP(x)是一命题，断言所有个体满足性质P(x)，其真值确定。 xP(x) 也是命题。 当个体域中个体有穷时，例如D = a1, ,an， xP(x) 的意义与命题 P(a1)P(an) 等同

8、 xP(x) 的意义与命题P(a1)P(an) 等同。,2.1.3 量词,2.1 谓词演算基本概念,离散数学第2章 逻辑代数（下）：谓词演算,例2.1： (1) x(A(x)B(x)C(x) x的辖域是A(x)B(x)，其中的x是约束变元； C(x) 不在的辖域内，其中的x是自由变元； (2) x A(x)B(x) x的辖域是A(x)，其中x是约束变元， B(x)中x为自由变元。 可改为： y(A(y)B(y)C(x) y A(y)B(x) (3) 约定个体域为 0，1，2 y(y2=y) 等价于 02=012=122=2 ，此为假。 y(y2=y) 等价于 02=012=122=2 ，此为真

9、。,2.1.3 量词,2.1 谓词演算基本概念,离散数学第2章 逻辑代数（下）：谓词演算,2.1.4 谓词公式及语句的形式化,2.1 谓词演算基本概念,定义2.1 归纳定义谓词公式（又称合式公式，简称公式）。 （1）谓词填式是公式，命题常元是公式（看作零元谓词），常称 原子公式。 （2）如果A，B是公式，x为任一变元，那么(A)，(AB)，(xA)， (xA)（当使用五个联结词时还有(AB)，(AB)，(AB)） 都是公式。 （3）终极条款，略。 （括号省略原则同命题公式， (xA)、(xA)的最外层括号可省）,离散数学第2章 逻辑代数（下）：谓词演算,2.1.4 谓词公式及语句的形式化,2.

10、1 谓词演算基本概念,例2.2 以下均为公式 ADD(x,y,z) x(M(x)D(x) x(A(x)B(x) xy( B(x,y)M(y) yL(3,2)x L(x,2) 其中xy(B(x,y)M(y)是x (y( B(x,y) M(y)的简写。 注意：yL(3,2)也是公式，尽管L(3,2)中没有变元y。 yL(3,2)被理解为L(3,2)。 一般地，当A中无变元x时，xA，xA，均被看作与A相同。,离散数学第2章 逻辑代数（下）：谓词演算,2.1.4 谓词公式及语句的形式化,例2.3 设D为实数域， D上关系E(x,y)为 “x = y”，L(x,y) 为xy (1) xL(0，x2+1

11、) 真 (2) xE(x2-2x-1，0) 真 (3) xE(x2+x+1，0) 假 (4) xE(x2,y) 当y取非负实数时真，否则假 (5) xy(xy=yx) 真 (6) xy(x+y=xy ) 真 (7) xy(x+y=0) 真 (8) yx(x+y=0) 假 (9) yx(xy=0) 真 (10) xy(xy=0) 真,离散数学第2章 逻辑代数（下）：谓词演算,2.1.4 谓词公式及语句的形式化,2.1 谓词演算基本概念,关于语句形式化: 例2.4 设个体域是人类，试将下列语句译为谓词公式。 (1) 有人勇敢，但不是所有的人都勇敢。 B(x)：x勇敢 译为： xB(x) xB(x)

12、 (2) 大家都不相互依靠，确要互相帮助。 R(x,y)：x依靠y，H(x,y)：x帮助y 译为： xyR(x,y)xyH(x,y),离散数学第2章 逻辑代数（下）：谓词演算,2.1.4 谓词公式及语句的形式化,2.1 谓词演算基本概念,例2.4(续) (3) 每个人都有人爱，但没有人为所有人爱。 L(x,y)：x爱y 译为： xyL(y,x) yxL(x,y) (4) 勇敢者未必都是成功者。 B(x)：x是勇敢者， W(x)：x是成功者 译为：x(B(x)W(x) 或 x(B(x)W(x),离散数学第2章 逻辑代数（下）：谓词演算,语句形式化过程的关键步骤： 准确地从语句中提取谓词。表示性质

13、的谓语用一元谓词表示， 表示关系的谓语用二元或更多元数的谓词来表示。 准确地使用量词和确定量词的辖域，当辖域中多于一个谓词时必须注意括号的使用。 准确地使用谓词之间的真值联结词，正确地反映谓词之间的逻辑关系。 准确地使用多个重叠的量词，其排列次序应与原语句意义一致。,2.1.4 谓词公式及语句的形式化,2.1 谓词演算基本概念,离散数学第2章 逻辑代数（下）：谓词演算,限定谓词的使用方法: 讨论个体域的某个局部的所有个体或某些个体时，要使用把量词限于该局部的“限定谓词” 。 限定谓词与其它谓词之间应使用适当的联结词。 当限定谓词用于限定全称量词时，它必须作为蕴涵词的前件加入；当限定谓词用于限定

14、存在量词时，它必须作为合取词的合取项加入，即用 x(A(x) 和 x(A(x) 表示“所有满足 A(x)的东西都 ”和“在满足A(x)的东西中有满足 的个体”。这里A(x)是限定谓词，将个体域暂时限定在满足A(x)的那些个体上。,2.1.4 谓词公式及语句的形式化,2.1 谓词演算基本概念,离散数学第2章 逻辑代数（下）：谓词演算,例2.5 将下列语句用谓词公式形式化： (1) 凡是实数，或者大于零，或者等于零，或者小于零。 R(x)：“x是实数” x(R(x)x0) (2) 一个数是偶数当且仅当它可被2整除。 E(x)：“x是偶数”，D(x,y)：“x整除y” x(E(x) D(2,x) (

15、3) 没有不犯错误的人。 F(x)：“x犯错误”， M(x)：“x是人” x(M(x)F(x) 或 x(M(x)F(x),2.1.4 谓词公式及语句的形式化,2.1 谓词演算基本概念,离散数学第2章 逻辑代数（下）：谓词演算,(4) 每人都有自己喜欢的水果，有人喜欢所有的水果。 F(x)：“x是水果”，M(x)，L(x,y)同前 x(M(x)y (F(y)L(x,y)x (M(x)y(F(y) L(x,y) (5) 并不是火车都比汽车跑得快，有的汽车比有的火车跑得快。 A(x)：“x是汽车”， T(x)：“x是火车”， F(x,y)：“x比y跑得快” xy(T(x)A(y)F(x,y)xy (

16、A(x)T(y)F(x,y) (6) 有位妇女已搭乘过世界上每一条航线上的航班。 W(x)：x是妇女， L(x)：x是航线， F(x)：x是航班； Q(x, y)：x是y航线上的航班， P(x, y)：x搭乘过y航班 x(W(x)y(L(y)z(F(z)Q(z,y)P(x, z),2.1.4 谓词公式及语句的形式化,2.1 谓词演算基本概念,离散数学第2章 逻辑代数（下）：谓词演算,2.2.1 谓词公式的真值规定,2.2 谓词演算永真式,问题：谓词公式的真值如何确定? 例如： 1) x(M(x)D(y) 2) x(f(x)=0) 3) x(ax2+bx+c=0)y=1,与谓词公式的值有关的因素

17、： (1) 个体域； (2) 对符号所作的解释； (3) 个体变元的取值。,离散数学第2章 逻辑代数（下）：谓词演算,2.2.1 谓词公式的真值规定,2.2 谓词演算永真式,例2.6 分别给定个体域D1=3，4，D2=3，5， 解释I1：P(x) 表示“x是质数” 解释I2：P(x) 表示“x是合数”,离散数学第2章 逻辑代数（下）：谓词演算,2.2.1 谓词公式的真值规定,2.2 谓词演算永真式,定义2.2 给定个体域D及公式A中各谓词符号的解释I，如果A中个体 变元x1 ,xn分别取值u1 ,un时A真，则称 A在u1 ,un处真； 当x1 ,xn无论取D中怎样的个体u1 ,un, A在u

18、1 ,un处均真， 则称A在解释I下真。,例如：例2.6中取个体域D2 =3，5,离散数学第2章 逻辑代数（下）：谓词演算,2.2.1 谓词公式的真值规定,2.2 谓词演算永真式,定义2.3 给定个体域D，若公式A在每一解释 I 下均真，那么称 A在D上永真。若公式A对任何个体域 D 均有D上永真， 则称A为永真式，或称A永真。A永真仍记为 A。 永真式的表示： AB 表示“AB永真” AB 表示“AB永真” 例2.7 xP(x) xP(x) 在只有一个元素的个体域D上永真 x(P(x)P(x) 永真式 xP(x) xP(x) 永真式,离散数学第2章 逻辑代数（下）：谓词演算,2.2.1 谓词

19、公式的真值规定,2.2 谓词演算永真式,A(x1,xn)在x1=u1,xn=un处真,A在解释I下均真,在D上永真,A永真,谓词公式的语义小结：,沿用命题演算中引入的一些符号和称谓： A B表示“AB”永真，称A逻辑蕴涵B 。 AB表示“AB”永真，称A逻辑等价B 。,离散数学第2章 逻辑代数（下）：谓词演算,2.2.1 谓词公式的真值规定,2.2 谓词演算永真式,定义2.4 公式A称为可满足的，如果有某一个体域、某一解释使得 变元在某一取值状况下，A取值真。否则，称公式A不可满 足。公式A不可满足时也称A为永假式。,例如：例2.6中公式都是可满足的， yP(y)P(x) 是永真式。 显然，当

20、公式A永真时，A必定是永假式。,离散数学第2章 逻辑代数（下）：谓词演算,2.2.2 谓词演算永真式,2.2 谓词演算永真式,第一组 所有重言式。 例2.8 以下为永真式（这里A，B为任意谓词公式）： A(x)A(x)、 A(x)(xB(x)A(x)、 (A(x)B(x) (B(x)A(x),离散数学第2章 逻辑代数（下）：谓词演算,2.2.2 谓词演算永真式,2.2 谓词演算永真式,第二组 当A不含自由变元x时， xAA , xAA 第三组 对任意含有自由变元x的公式A(x)，有 xA(x) A(x) A(x) xA(x) xA(x) xA(x),离散数学第2章 逻辑代数（下）：谓词演算,2

21、.2.2 谓词演算永真式,2.2 谓词演算永真式,第四组 对任意含有自由变元x的公式A(x)，有 xA(x)xA(x) xA(x)xA(x) xA(x)xA(x) xA(x)xA(x) 例2.9 xyz(x=y+z) xyz (x=y+z) x yz(x=y+z) x yz(xy+z),离散数学第2章 逻辑代数（下）：谓词演算,2.2.2 谓词演算永真式,2.2 谓词演算永真式,第五组 当公式B中不含自由变元 x 时，对任意含有自由变元x的 公式A(x) 有: xA(x)Bx(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(A(x)B) 例2.10 x

22、A(x)yB(y) x (A(x)yB(y) xy (A(x)B(y) x (x040)(40),离散数学第2章 逻辑代数（下）：谓词演算,2.2.2 谓词演算永真式,2.2 谓词演算永真式,第六组 对任意含有自由变元x的公式A(x)，B(x)，有: x(A(x)B(x)xA(x)x B(x) xA(x)xB(x) x(A(x)B(x) x(A(x)B(x) xA(x)xB(x) x(A(x)B(x)xA(x)xB(x),离散数学第2章 逻辑代数（下）：谓词演算,2.2.2 谓词演算永真式,2.2 谓词演算永真式,第二式证明： xA(x)xB(x) x(A(x)B(x) 证明：对任一个体域D和

23、解释I 。 若xA(x)xB(x)真，那么有以下两种情况： (a) xA(x)真，即对一切个体dD，A(d)真， 从而A(d)B(d)真,故有x(A(x)B(x)真。 (b) x B(x)真，同理可证x(A(x)B(x)亦真。 相反的逻辑蕴涵却是不成立的。 令D为整数集，A(x)表示“x是偶数”，B(x)表示“x是奇数”。 则 x (A(x)B(x) 真，但 x A(x)x B(x)假。,离散数学第2章 逻辑代数（下）：谓词演算,2.2.2 谓词演算永真式,2.2 谓词演算永真式,第七组 对任意含有自由变元x,y的公式A(x,y)，有: xyA(x,y)yxA(x,y) xyA(x,y) yx

24、A(x,y) yxA(x,y) xyA(x,y) xyA(x,y) yxA(x,y) xyA(x,y)yxA(x,y) 注意：相邻的同名量词的次序无关紧要； 相邻的不同名量词的次序不可随意改变！,离散数学第2章 逻辑代数（下）：谓词演算,2.2.2 谓词演算永真式,2.2 谓词演算永真式,第八组 当C中无自由变元x时，对任意含有自由变元x的公式A(x)，B(x)，有 x(CA(x)CxA(x) x(CA(x)CxA(x) x(A(x)B(x) xA(x)xB(x) 证明第一式： x(CA(x)x(CA(x) Cx A(x) Cx A(x),离散数学第2章 逻辑代数（下）：谓词演算,证明第三式：

25、 x(A(x)B(x)xA(x)xB(x) 证明：设个体域D和解释I下x (A(x)B(x)真。 （即对任意dD，A(d)B(d)真） (1) 证xA(x)xB(x)在个体域D和解释I下真： 设xA(x) 在域D和解释I下真，从而对任意dD，A(d)均真。 由A(d)B(d) 真及A(d) 真，可知对任意dD，B(d)真， 此即表明xB(x)在域D解释I下真。第三式得证。 (2) 证该式之逆不成立： 令D为整数集，A(x)，B(x)解释为“x是偶数”和“x是奇数”， 这时xA(x)假，故xA(x)xB(x)真，但x(A(x)B(x)假。 （因为“所有的偶数都是奇数”显然是荒谬的。）,2.2.2

26、 谓词演算永真式,2.2 谓词演算永真式,离散数学第2章 逻辑代数（下）：谓词演算,2.2.3 谓词公式等价变换的几个基本原理,定义2.5 设谓词公式A中含自由变元x，设t为一个体项，且t中无自 由变元为A中的约束变元，那么称t是在A中对x可代入的， 其代入实例记为A(t/x) 。,2.2 谓词演算永真式,例2.11 A=y(x y)，对多于一个元素的任何个体域均为真。 对x作代入，代入的个体项t中不含y， t都是对x可代入的。否则不然。,离散数学第2章 逻辑代数（下）：谓词演算,2.2.3 谓词公式等价变换的几个基本原理,定理2.2（替换原理）设A，D为谓词公式，C为A的子公式，且 CD。若

27、B为将A中子公式C的某些出现（未 必全部）替换为D后所得的公式，那么AB 。,2.2 谓词演算永真式,定理2.1（代入原理）若A是永真式，那么对A中变元可代入的代入 实例都是永真式。,离散数学第2章 逻辑代数（下）：谓词演算,2.2.3 谓词公式等价变换的几个基本原理,2.2 谓词演算永真式,例2.12 （1）由2.2.2节第六组第一式导出第四式。 第一式: x(A(x)B(x)xA(x)x B(x) 第四式: x(A(x)B(x)xA(x)xB(x) 证 x (A(x)B(x)x(A(x)B(x) (x(A(x)B(x) (xA(x)xB(x) xA(x)xB(x) xA(x)x B(x),

28、离散数学第2章 逻辑代数（下）：谓词演算,2.2.3 谓词公式等价变换的几个基本原理,2.2 谓词演算永真式,例2.12 （2）对任意A(x)，B(x) ， x (A(x)B(x)xA(x)xB(x) 证 x (A(x)B(x) x(A(x)B(x) xA(x)xB(x) xA(x)x B(x) xA(x)xB(x),离散数学第2章 逻辑代数（下）：谓词演算,2.2.3 谓词公式等价变换的几个基本原理,定义2.6 设A为仅含联结词，的谓词公式，A*为将A中符号 ，t，f， , 分别换为，f，t, ， 后所得的公式， 那么称A*为A的对偶式。,2.2 谓词演算永真式,例2.13 由对偶原理AA*

29、( p1/p1, , pn/pn)导出 xp(x)x p(x)x p(x) 由“若A B则B* A*”、x A(x)x B(x) x (A(x)B(x)导出 x (A(x)B(x) x A(x)x B(x)（或反之）。 由“若 AB则A*B*”、xyA(x,y)yx A(x,y)导出 x y A(x,y)y x A(x,y)（或反之）。,离散数学第2章 逻辑代数（下）：谓词演算,2.2.3 谓词公式等价变换的几个基本原理,定理2.3 （改名原理）若公式A(x)中无自由变元y，那么， xA(x)yA(y) , xA(x)yA(y) 例2.14 求证：对任意公式A(x,y)，xyA(x,y)yxA

30、(y,x) 证 xyA(x,y) xzA(x,z) yzA(y,z) yxA(y,x),2.2 谓词演算永真式,离散数学第2章 逻辑代数（下）：谓词演算,2.3.1 前束化和消去量词,定义2.7 公式A称为公式A的前束范式，如果AA ，且A形如 Q1x1QnxnB 其中Q1,Qn为量词 或 , B称为母式，B中无量词。当B为 合取（析取）范式时，A称为A的前束合取（析取）范式。,前束化步骤: （1）利用逻辑等价式将公式中联结词, 消除。 （2）利用逻辑等价式将否定词深入到各原子公式之前。 （3）利用2.2.2节的第五组和第六组永真式将量词逐个移至公式前部。,2.3 谓词演算消解原理,离散数学第

31、2章 逻辑代数（下）：谓词演算,2.3.1 前束化和消去量词,例2.15 求以下两式的前束范式： （1）xA(x)x B(x) 解 xA(x)x B(x) xA(x)x B(x) xA(x)x B(x) x(A(x)B(x) (或将母式表示为非范式的前束型 x(A(x)B(x),2.3 谓词演算消解原理,离散数学第2章 逻辑代数（下）：谓词演算,2.3.1 前束化和消去量词,例2.15 求以下两式的前束范式： （2）xy (z(P(x,z)P(y,z)z Q(x,y,z) 解 xy (z(P(x,z)P(y,z)z Q(x,y,z) xy (z(P(x,z)P(y,z)z Q(x,y,z) x

32、y (z(P(x,z)P(y,z)z Q(x,y,z) xy (z(P(x,z)P(y,z)u Q(x,y,u) xy zu (P(x,z)P(y,z)Q(x,y,u) （或xy zu (P(x,z)P(y,z)Q(x,y,u),2.3 谓词演算消解原理,离散数学第2章 逻辑代数（下）：谓词演算,2.3.1 前束化和消去量词,定理2.4 （前束范式定理） 对任意谓词公式均可作出其前束范式， 进而作出其前束合取范式或前束析取范式。,定理2.5（Skolem 定理） 公式A(v)与A(e)，公式u A(u,v)与 uA(u,f(u)同可满足性。这里e是A中未出现的新常元， f是A中未出现的新n元函

33、数符号，它们被分别称为斯柯伦 常元和斯柯伦函词。,2.3 谓词演算消解原理,离散数学第2章 逻辑代数（下）：谓词演算,2.3.1 前束化和消去量词,证明 uA(u,v)和u A(u,f(u)同可满足性，并只对n =1的情况立论。 证 设有个体域U，解释I使得uA(u,v)成立， 从而对每一dU均有dU，使得 A(d d)。 作U上函数f，使得对每一dU，f(d)为使A(d,d)成立的d中的一个。 考虑个体域U，解释I ，其中I把f解释为上面定义函数。 显然，个体域U，解释I使得u A(u,f(u)成立。 这就是说，如果uA(u,v)可满足，那么u A(u,f(u)也可满足。 反之，设有个体域U

34、，解释I使得u A(u,f(u)成立，f被解释为U上函数。那么对每一dU，A(d,f(d)真。即对每一dU，A(d,v)真，从而在个体域U，解释I下有u A(u,v)真。即，u A(u,f(u)可满足，uA(u,v)也可满足。,2.3 谓词演算消解原理,离散数学第2章 逻辑代数（下）：谓词演算,2.3.2 谓词演算消解原理,2.3 谓词演算消解原理,例2.16 证明y(A(y)C(y) x(y(A(y)B(x,y)z(C(z)B(x,z) 证 对应于前提的子句集为： A(y)C(y) 结论的否定化为前束合取范式： x(y(A(y)B(x,y)z(C(z)B(x,z) x(y(A(y)B(x,y)z(C(z)B(x,z) x(y(A(y)B(x,y)z(C(z)B(x,z) xy(A(y)B(x,y)