离散数学谓词逻辑分解课件

1、第二章 谓词逻辑杨圣洪第二章 谓词逻辑杨圣洪引言 命题逻辑好像功能强大，但还是有些问题难以解决。 如杨圣洪要喝水、刘翔要喝水、姚明要喝水、姚晨要喝水、刘德华要喝水、，可归纳为“某某要喝水”，无法表示。 所有的人都要呼吸、喝水、吃饭，“所有”如何表示呢？ 有些人要升官、有些人要失恋，“有些”又如何表示？ 所有男人都会多看几眼漂亮女人 所有女人都会多喜欢漂亮的衣服 又如有名三段论：所有人都是要变老的，杨圣洪是人，所以杨圣洪也会变老的，无法表示。 为此需要我们学习新的逻辑工具-谓词逻辑或一阶逻辑引言 2.1基本概念 1、谓词 “某某要喝水”、“喜欢漂亮衣服”、“喜欢帅哥”、“结婚生崽”都是所在句子的

2、谓语部分。 命题逻辑中用大写字母表示命题。 谓词逻辑中用大写字母表示谓语部分，如 用W表示“要喝水”， 用L表示“喜欢漂亮衣服”， 用H表示“喜欢帅哥”， 用M表示“结婚生崽”。 这些表示谓语部分的大写字母，称为“谓词”。 2.1基本概念2.1基本概念 2、个体常元 表示某种判断的语句一般都有主语。 主语是表示某个、某些客体，也称为个体。 如“刘翔”、“姚明”。 为了描述方便，常用小写字母表示这些个体。 如a表示“刘翔”， c表示“姚明”， 这些表示具体个体的小写字母，称为“个体常元”或个体常量。 其他学科中，也是用字母表中靠前的字母表示常量。2.1基本概念2.1基本概念 3、个体变元 对于不

3、针对特定个体的泛指， 如“某某”、“男人”、“女人”， 常用x,y,z,r,s,t等字母表中靠后的字母表示， 其他学科中，也是这样表示， 这些小字字母称为“个体变元”。 因此“某某要喝水”表示为W(x),x泛指所有的人， “女人喜欢漂亮衣服”表示为L(x,y)，x泛指“女人”、y泛指“衣服”， “女人喜欢帅哥”表示为H(y,z)，其中y泛指女人、z泛指帅哥。 “男人结婚生崽”表示为M(z)，z泛指男人。 2.1基本概念2.1基本概念 4、全称量词 为了表示“所有女人都喜欢漂亮的衣服”、 “所有女人都喜欢帅哥”等中 “所有”，引入符号“”，称为全称量词。 可能是“ALL”的字母A倒写，表示所有、

4、全部。 当用x泛指“人”，“所有人”表示为“x”， “所有活人都要喝水”表示为xW(x)。 当用x表示“女人”,y表示漂亮的衣服时， “所有女人”则表示为x、 “所有漂亮的衣服”则表示为“y”，因此 “所有女人都喜欢漂亮的衣服”表示为xyL(x,y)。 当用x表示“女人”,y表示帅哥时， “所有女人都喜欢帅哥”表示为xyH(x,y)。 2.1基本概念2.1基本概念 5、存在量词 为了表示“有些男人结婚生崽”中“有些”， 引入符号“”， 表示“存在，有些、有部分”等的含义。 称为存在量词。 它是Exist的首字母，左旋180度， 如用z表示“男人”，那么 “有些男人”表示为“z”， “有些男人结

5、婚生崽”表示为“zM(z)”。2.1基本概念2.1基本概念 6、谓词公式 将表示全部的符号“”，表示为部分的“”称为量词， 将单个谓词公式如W(x)，带量词的谓词如zM(z)， 统称为“谓词公式”。 谓词W(x),M(z)中只有1个个体变元, 则称为1元谓词公式， 常用来刻划对象的性质、属性。 谓词L(x,y)、H(y,z)中有2个个体变元，称为2元谓词。 常用来表示二个对象之间的关系， 如喜欢， 类似如果有n个个体变元则称为n元谓词公式。 个体变元的取值范围称为“讨论域”， 如果没有交待讨论域，表示对个体变元的取值范围，不做任何限制，泛指宇宙界的万物，称为“全总个体域”，常用大写字母U表示。

6、 2.1基本概念利用量词、谓词将自然语言转换为谓词公式 例1：(1)凡人都要呼吸 (2)有的人用左手写字。 解：当个体域为“人类”时 xB(x),其中B(x)表示x人呼吸breath. xWL(x)，其中WL(x)表示x用左边写字。 当个体域为全总个体域(宇宙万物组成) x(H(x)B(x) H(x)表示个体x是人类 x(H(x) WL(x)，WL(x)表示x用左边写字。 个体域不同，谓词公式不同。例2 (1)任意x,x2-2x+1=(x-1)2. 有x,使得x*5=3解：当x的取值范围即个体域为自然数N时 xE(x) E(x)表示x2-2x+1=(x-1)2 xF(x) F(x)表示x*5=

7、3 当x的个体域为实数R时，谓词公式相同但真值不同！利用量词、谓词将自然语言转换为谓词公式 例3 (1)兔子比乌龟跑得快 (2)有的兔子比所有的乌龟跑得快 (3)并不是所有的兔子都比乌龟跑得快 (4)不存在跑得同样快的两只兔子. 解：H(x,y)表示x比y跑得快. L(x,y)表示x与y一样快 R(x)表示x是兔子 T(x)表示x是乌龟 (1) xy(R(x)T(y)H(x,y) (2) xy(R(x)T(y) H(x,y) (3) xy(R(x)T(y)H(x,y) xy(R(x)T(y)H(x,y) (4) xy(R(x)R(y)L(x,y) xy(R(x)R(y) L(x,y)例3 (1

8、)兔子比乌龟跑得快例4任意两个不相等实数，其平方和大于积的二倍。 解：个体域为全总个体域即不对个体变元的取值做任何限制。 F(x)表示x是实数， G(x,y)表示xy， H(x,y)表示xy，则原话表示为 xy (F(x)F(y)G(x,y)H(x2+y2,2xy)。 若用f(x,y)表示x2+y2，g(x,y)表示2xy，则原话表示为 (F(x)F(y)G(x,y)H(f(x,y),g(x,y) 因为对于实数x，y，(x2-2xy+y2)=(x-y)2， 当xy时，有(x-y)20， 故(x2-2xy+y2)0， 故x2+y22xy， 故H(x2+y2,2xy) 为真 故原话正确，故以上公式

9、的真值为1。 故谓词公式可出现个体变元,平方,乘、倍数、函数等。例4任意两个不相等实数，其平方和大于积的二倍。例5表示“所有人都要变老的，杨圣洪是人，所以杨圣洪也会变老的”。 解：个体域为全总个体域，即对个体变元的取值不做任何限。 H(x)表示对象x是人类， O(x)表示对象x变老， c表示个体常元“杨圣洪”，则 H(c)表示个体常元杨圣洪是人类， O(c)表示个体常元杨圣洪要变老，原句表示 (x(H(x)O(x)H(c)O(c)。 该公式不仅有个体变元，还有个体常元 例5表示“所有人都要变老的，杨圣洪是人，所以杨圣洪也会变老的例6表示“所有人都要死的，苏格拉底是人，所以苏格拉底也会死”。 解

10、：个体域为全总个体域，即对个体变元的取值不做任何限制。 H(x)表示对象x是人类， O(x)表示对象x要死的， c表示个体常元“苏格拉底”，则 H(c)表示个体常元苏格拉底是人类， O(c)表示个体常元苏格拉底要死，原句表示 (x(H(x)O(x)H(c)O(c)。 这两个例题，语句不同，但是最后的谓词公式相同。例6表示“所有人都要死的，苏格拉底是人，所以苏格拉底也会死”2.2、谓词公式及解释 上节得到一些谓词公式，获得一些结论，也有存在一些疑惑？ (1)谓词公式有个体常元、个体变元，还可以有个体变元的表达式，那么谓词公式究竟还有哪些形式，究竟什么的字符串是合法的谓词公式？ (2)同一句话有二

11、个不同的公式，那么这二个公式等值吗？ (3)不同的话拥有同样的谓词公式，到底这二句话有何共性？ (4)同一样公式在不同的论域下真值不同，究竟如何确定一个公式的真值呢？ 2.2、谓词公式及解释2.2、谓词公式及解释非逻辑符号:个体常元、函数符号、谓词符号逻辑符号:个体变元、量词符号、联结词、逗号、括号。项的定义：个体常元与变元及其函数式为项。(1)个体常元和个体变元是项。(2)若(x1,x2, xn)是n元函数,t1,t2,tn是n个项，则(t1,t2, tn)是项。(3)有限次使用(2)得到的表达式是项。原子公式： 设R(x1,x2,xn)是n元谓词，t1,t2,tn是项，则R(t1,t2,

12、tn)是原子公式。2.2、谓词公式及解释2.2、谓词公式及解释项的定义：个体常元与变元及其函数式为项。原子公式： 设R(x1,x2,xn)是n元谓词，t1,t2,tn是项，则R(t1,t2, tn)是原子公式。合式谓词公式： (1)原子公式是合式公式； (2)若A是合式公式，则(A)也是合式公式； (3)若A,B合式，则AB, AB, AB , AB 合式 (4)若A合式，则xA、 xA合式 (5)有限次使用(2)(4)得到的式子是合式。2.2、谓词公式及解释2.2、谓词公式及解释 (F(x)F(y)G(x,y)H(f(x,y),g(x,y)、 xy(R(x)T(y)H(x,y)、 xy(R(

13、x)T(y)H(x,y)、x(H(x)WL(x)、(x(H(x)O(x) H(c) )O(c)， 因此以上公式均是合法的公式，而 F(x)F(y)G(x,y)、F(y)G(x,y)不是合法的公式。 凡按照以上5条规则写出的表达式，就是合法谓词公式(也称为合式公式)。 不再拘泥于某个具体的自然语句。 直接研究含义不确定或泛指的谓词公式。 从形式上研究合式公式的性质。2.2、谓词公式及解释2.2、谓词公式及解释-个体变元的身份量词指导变元：xA和xA中的x量词辖域：xA和xA中的A为量词/辖域变元的约束出现：指导变元的每次出现(称约束变元)。变元的自由出现：不是约束出现的变元(称自由变元) 。例题

14、 x(F(x,y)G(x,z)解： x是量词的指导变元。 (F(x,y)G(x,z)是量词的辖域 在 (F(x,y)G(x,z)中x是约束出现，出现2次。 在(F(x,y)G(x,z)自由出现的变元y/z，各一次。 2.2、谓词公式及解释-个体变元的身份2.2、谓词公式及解释-个体变元的身份量词指导变元：xA和xA中的x量词辖域：xA和xA中的A为量词/辖域变元的约束出现：指导变元的每次出现(称约束变元)。变元的自由出现：不是约束出现的变元(称自由变元) 。 例题 x(F(x,y)G(x,z)例题 x(F(x)G(y)y(H(x)L(x,y,z)解： 量词的指导变元x, (F(x)G(y)是量

15、词的辖域，其中x是约束出现，y是自由出现。 量词的指导变元y, H(x)L(x,y,z)是量词的辖域，其中x是自由2次，y是约束出现。整个公式中是约束1自由2次。2.2、谓词公式及解释-个体变元的身份2.2、谓词公式及解释-个体变元的身份 例题 分析x(F(x)G(y)y(H(x)L(x,y,z)变元身份解： x的辖域是：(F(x)G(y)，约束变元是x，x有1次约束出现，y是自由变元，有1次自由出现。 y的辖域是：H(x)L(x,y,z)，约束变元是y，y有1次约束出现，x与z是自由变元，各有1次自由出现。 尽管x在公式x(F(x)G(y)出现，又在 y(H(x)L(x,y,z)出现，但两个

16、x不是一回事， 只是恰巧二个名字相同而矣， 好比有2个李勇，一个是正坐在家里看电视的“李勇”，一个是在马路上散步的“李勇”， 为了避免这种“误会”出现，要对“约束变元”改名。2.2、谓词公式及解释-个体变元的身份2.2、谓词公式及解释-个体变元的身份 例题 分析x(F(x)G(y)y(H(x)L(x,y,z)变元身份解：尽管x在公式x(F(x)G(y)出现，又在 y(H(x)L(x,y,z)出现，但两个x不是一回事， 只是恰巧二个名字相同而矣， 为避免这种“误会”出现要对“约束变元”改名。 将量词x的指导变元x，x的每次约束出现换成公式中未出现的r。 将量词y指导变元y、约束变元y的每次出现换

17、成公式中未出现的s，则原式为 r(F(r)G(y)s(H(x)L(x,s,z)， 所有约束变元与自由变元均不重名，无误会。 2.2、谓词公式及解释-个体变元的身份2.2、谓词公式及解释-个体变元的身份 例题 分析xy(P(x,y)Q(y,z)xP(x,y)作用域与变元约束情况 解：x、y的作用域是(P(x,y)Q(y,z)， x的作用域是P(x,y)。 将与自由变元同名约束变元yr， 将与前一个同名约束变元xs，则原公式 xr(P(x,r)Q(r,z)sP(s,y) 2.2、谓词公式及解释-个体变元的身份2.2、谓词公式及解释-个体变元的身份 例题 x(P(x)xQ(x,z)yR(x,y)Q(

18、x,y) 解：x的辖域是P(x)xQ(x,z)yR(x,y)，。 x的辖域是Q(x,z) y的辖域是R(x,y) s(P(s)rQ(r,z)tR(s,t)Q(x,y) 改名规则：一般仅对约束变元改名 后出现者约束变元也要改名。 方法：将量词的指导变元，及辖域中约束变元每次约束出现，全部换成公式中未出现的字母。2.2、谓词公式及解释-个体变元的身份2.2、谓词公式及解释-个体变元的身份 闭公式：不含自由变元的谓词公式 。x(F(x,y)G(x,z)因y,z是自由变元，故不是。r(F(r)G(y)s(H(x)L(x,s,z)因为y,x,z自由故不是xr(P(x,r)Q(r,z)sP(s,y) 因z

19、与y自由，故不是。s(P(s)rQ(r,z)tR(s,t) 因z自由故不是(F(x)F(y)G(x,y)H(f(x,y),g(x,y) 因x/y自由故不是以下公式均没有自由变元，均为闭公式：xy(R(x)T(y)H(x,y)、xy(R(x)T(y)H(x,y)、xy(R(x)T(y)H(x,y)、xy(R(x)T(y) H(x,y)、xy(R(x)R(y)L(x,y)、xy(R(x)R(y) L(x,y)、x(H(x)B(x)、x(H(x)WL(x)、(x(H(x)O(x)H(c)O(c)2.2、谓词公式及解释-个体变元的身份2.2、谓词公式及解释-谓词公式的真值 前面我们学习“合式公式”时，

20、说过不再拘泥于某个具体的自然语句，从形式上研究合式公式的性质。 但谓词公式是逻辑公式，它总得有一个真假呀？ 如何确定其真假呢？ 神马不能总是浮云？ 总得落地。 确定真值的方法： (1)确定个体域，即个体的取值范围，哪个范围？ (2)将个体常元指定为个体域的具体值。哪个对象？ (3)函数常元表示指定个体域中个体变元的项。 (4)用指定个体域中的对象来解释各个原子公式。 (5)用原子公式的解释来描述整个公式的含义。原义？ 根据个体域中知识，判断整个公式的含义是否正确，若对则公式的真值为1，否则为02.2、谓词公式及解释-谓词公式的真值2.2、谓词公式的解释-谓词公式的真值例题：x(F(x)G(x)

21、 其中x的取值范围是什么？ F(x)的含义是什么？G(x)的含义是什么？ 将这些问题确定后，表达式x(F(x)G(x)的真值就确定了，这就是公式的解释。 dom(x)=D1=全总个体域 F(x)表示x是人，G(x)表示x是黄种人。 x(F(x)G(x)：所有的人都是黄种人，值为F. dom(x)=D2=实数集R F(x)表示x是自然数，G(x)表示x是整数。 x(F(x)G(x)：所有的自然数都是整数，值为T.2.2、谓词公式的解释-谓词公式的真值例：xy (F(x)F(y)G(x,y)H(f(x,y),g(x,y) f(x,y),g(x,y)是函数变元，一元谓词公式F(x),二元谓词G与H。

22、 x与y的个体域：全总个体域。 F(x):x是实数 G(x,y):xy H(x,y):xy f(x,y)=x2+y2 g(x,y)=2xy 这时整个公式的含义： 对于任意的x和y，若x与y是实数且xy，那么x2+y2 2xy ，其真值为1. 如果H(x,y): xy f(x,y)=x2+y2 g(x,y)=2xy 这时整个公式的含义： 对于任意的x和y，若x与y是实数且xy，那么x2+y2 2xy ，其真值为1. 总结： 个体常元的值、个体变元的值域、确定函数、谓词公式的含义。例题：xy (F(x)F(y)G(x,y)H(f( 个体常元的值、个体变元的值域、确定函数、谓词公式的含义。例4：个体

23、变元的值域D=N, 常元的a=0,函数f(x,y)=x+y ,g(x,y)=x*y 谓词F(x,y):x=y解释下列各公式的含义： (1) F(f(x,y),g(x,y)原式=F(x+y,x*y)，x+y=x*y，对于自然数x/y，此式真假不确定，故不是命题。 (2) F(f(x,a),y)F(g(x,y),z)代入各式= F(x+0,y)F(x*y,z)=F(x,y)F(x*y,z)确定F后: x=yx*y=z,真假难定,不是命题. 个体常元的值、个体变元的值域、确定函数、谓词公式的含义。 个体常元的值、个体变元的值域、确定函数、谓词公式的含义。例：个体变元的值域D=N, 常元的a=0,函数

24、f(x,y)=x+y ,g(x,y)=x*y 谓词F(x,y):x=y解释下列各公式的含义： (3) F(g(x,y),g(y,z)将函数确定后:F(x*y,y*z)将谓词确定后: x*y=y*z, 是否成立要看x,y,z的值,非命题! (4) xF(g(x,y),z)确定函数后:xF(x*y,z) 确定谓词后:x(x*y=z)为0, 当x=y=z1时(x*y=z)为0 xF(x)F(x0)F(x1). F(xk).(*) (*)式为0则左=0 xF(x)=1F(x0)=1, F(x1)=1. F(xk)=1.,若F(xi0)=0则 个体常元的值、个体变元的值域、确定函数、谓词公式的含义。例：

25、个体变元的值域D=N, 常元的a=0,函数f(x,y)=x+y ,g(x,y)=x*y 谓词F(x,y):x=y解释下列各公式的含义： (5) xF(g(x,a),x)F(x,y)确定个体常量xF(g(x,0),x)F(x,y)确定函数后:xF(x*0,x)F(x,y)确定谓词后:x(0=x) (x=y) 条件式的前式为假,无论后件为何,均为真 例：个体变元的值域D=N, 常元的a=0, 因为全称量词x是指个体域中所有对象具有某性质、或具有某相互关系。 存在量词x是指个体域中部分对象具有某性质、或具有某相互关系 故当个体域dom(X)=a1,a2,an有限,即n有限, xA(x)即为A(a1)

26、A(a2)A(an)。 xA(x)即为A(a1)A(a2)A(an)。 利用这两个展开式，在解释公式的含义时，可能会带来某种便利！ 因为全称量词x是指个体域中所有对象具有某性质、或具有 例题：个体域D=2,3，常元a=2，f(2)=3，f(3)=2 ，F(2)=0,F(3)=1,G(2,2)=G(2,3)=G(3,2)=1、G(3,3)=0、 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,2)，展开全称量词得(F(2)G(2,2)(F(3)G(3,2)，代入谓词的值得(01)(11)

27、，即为0。 例题：个体域D=2,3，常元a=2， 例题：个体域D=2,3，常元a=2，f(2)=3，f(3)=2 ，F(2)=0,F(3)=1,G(2,2)=G(2,3)=G(3,2)=1、G(3,3)=0、 L(2,2)=L(3,3)=1, L(2,3)=L(3,2)=0， 求下列谓词公式的值:(2) x(F(f(x)G(x,f(x)解：展开存在量词得(F(f(2)G(2,f(2)(F(f(3)G(3,f(3)，代入函数值 (F(3)G(2,3)(F(2)G(3,2)，代入谓词的值(11)(01)，即为1。 例题：个体域D=2,3，常元a=2， 例题：个体域D=2,3，常元a=2，f(2)=

28、3，f(3)=2 ，F(2)=0,F(3)=1,G(2,2)=G(2,3)=G(3,2)=1、G(3,3)=0、 L(2,2)=L(3,3)=1, L(2,3)=L(3,2)=0， 求下列谓词公式的值:(3) xyL(x,y)解：展开y得x(L(x,2)L(x,3)，展开x得(L(2,2)L(2,3)(L(3,2) L(3,3)，代入谓词的值得(10)(01)，即为1。 例题：个体域D=2,3，常元a=2， 例题：个体域D=2,3，常元a=2，f(2)=3，f(3)=2 ，F(2)=0,F(3)=1,G(2,2)=G(2,3)=G(3,2)=1、G(3,3)=0、 L(2,2)=L(3,3)=

29、1, L(2,3)=L(3,2)=0， 求下列谓词公式的值:(3) xyL(x,y)代入谓词的值得(10)(01)，即为1。(4) yx L(x,y)展开x得：y(L(2,y)L(3,y)，展y得：(L(2,2)L(3,2)( L(2,3)L(3,3)，代入谓词值得(10)(01)，即为0。说明： x与y次序很重要！ 例题：个体域D=2,3，常元a=2，2.2 谓词公式的类型 正如命题公式有永真/永假/可满足一样，谓词公式也有这3种类型。 永真式(逻辑有效式):在任何解释下均为真。 永假式(矛盾式):在任何解释下均为假。 可满足式:至少存在一种解释下为真。说明： (1)命题逻辑,使用真值表可以

30、判断一个公式的类型。 (2)在一阶逻辑即谓词逻辑中，不存在一个算法，在有限步内判断任意一个公式的类型。 (3)不可判定的！ (4)“任何解释”如何穷尽？不可能，因此只能根据某些原则如“代换实例”，即“类比命题逻辑原则”。2.2 谓词公式的类型谓词公式的类型永真式(逻辑有效式):在任何解释下均为真。永假式(矛盾式):在任何解释下均为假。可满足式:至少存在一种解释下为真。代换实例： 设A0是含命题变元p1,p2,.,pn的命题公式，A1,A2,.,An是n个谓词公式(其中个体常元/变元/函数/谓词公式都未确定含义)，将A0中pi的每次出现都换成Ai，所得公式A称为A0的代换实例。A(x)A(x),

31、xA(x)xA(x)是pp代换实例.A(x)A(x),xA(x) x A(x)是pp的代换实例 谓词公式的类型代换实例： 设A0是含命题变元p1,p2,.,pn的命题公式，A1,A2,.,An是n个谓词公式(其中个体常元/变元/函数/谓词公式都未确定含义)，将A0中pi的每次出现都换成Ai，所得公式A称为A0的代换实例。定理：命题重言式的代换实例都是永真式， 矛盾式的代换实例都是矛盾式。例题判断公式F(x,y)(G(x,y)F(x,y)的类型。解：F(x,y)p, G(x,y)q， 得命题公式p(qp)， F(x,y)(G(x,y)F(x,y)是p(qp)的代换实例。 p(qp)p(qp)pp

32、q1，即为重言式, 故其代换实例F(x,y)(G(x,y)F(x,y)是永真式。 称p(qp)为F(x,y)(G(x,y)F(x,y)的原型代换实例：2.2 谓词公式： 设A0是含命题变元p1,p2,.,pn的命题公式，A1,A2,.,An是n个谓词公式，用Ai处处代替A0中pi的每次出现，所得公式A称为A0的代换实例。 定理：命题重言式的代换实例都是永真式， 矛盾式的代换实例都是矛盾式。(1) x(F(x)G(x) 不是永真/永假/可满足 实-整(2) xF(x)(xyG(x,y)xF(x)，是 p(q p) 的代换实例， 而p(q p)p(q p) 1 故永真式(3)(xF(x)yG(y)

33、yG(y) 是(pq)q的代换实例， 而(pq)q pqq0 永假，故为永假2.2 谓词公式：2.3谓词公式等值演算：定义1 设A、B是两个合法的谓词公式,如果在任何解释下两个公式的真值都相等，则称A与B等值记为AB。 因AB时在任何解释下，公式A与公式B的真值都相同，故AB为永真式，故有定义2。定义2 设A、B是两个合法谓词公式，如果在任何解释下，AB为永真式，则A与B等值，记为AB。 等值问题，转换为永真问题， 通过代换实例原则找原型 并不是所有的谓词公式有对应的原型， 因此有些结论是无法证明，只能当作显然成立的公理。2.3谓词公式等值演算：谓词逻辑推理的公理：1、个体域为有限集D=a1,

34、a2,.,an,则有 xA(x) A(a1)A(a2) A(an) xA(x) A(a1)A(a2) A(an) 无法证明，只能理解！2.量词的德摩律 xA(x)xA(x) x A(x)x A(x) 当否定符“”移过时，变成、变成、变成、变成。谓词逻辑推理的公理：2、量词否定等值式-对于量词的德摩律 设公式A(x)含自由出现的个体变项x,则 (1) xA(x) xA(x) 不是所有的个体有某性=有些个体没有该特性 (2) xA(x) xA(x) 没有x有某些特性=所有的没有这个特性如： x(M(x)F(x) x(M(x)F(x) x(M(x)F(x) x(M(x)F(x) x(M(x)F(x)

35、 xy(F(x)M(x)H(x,y) xx(F(x)M(x)H(x,y)2、量词否定等值式-对于量词的德摩律1、个体域为有限集D=a1,a2,.,an,则有 xA(x) A(a1)A(a2) A(an) xA(x) A(a1)A(a2) A(an) 无法证明，只能理解！2.量词的德摩律 xA(x)xA(x) x A(x)x A(x) 3、量词分配律x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x) xB(x) 无法证明，只能理解！1、个体域为有限集D=a1,a2,.,an,则有1、个体域为有限集D=a1,a2,.,an,则有 xA(x) A(a1)A(a2) A(an) x

36、A(x) A(a1)A(a2) A(an)2.量词的德摩律 xA(x)xA(x) x A(x)x A(x) 3、量词分配律x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x) xB(x)4、量词作用域的收缩与扩张律 A(x)含自由x，B不含有自由出现的x，则有： (1)/x(A(x)B)/xA(x)B (2)/x(A(x)B)/xA(x)B1、个体域为有限集D=a1,a2,.,an,则有1、 xA(x) A(a1)A(a2) A(an) 个体域为有限 xA(x) A(a1)A(a2) A(an)2.量词的德摩律 xA(x)xA(x) x A(x)x A(x) 3、量词分配律

37、x(A(x)B(x)xA(x)xB(x) x(A(x)B(x)xA(x) xB(x)4、量词作用域的收缩与扩张律 (1)/x(A(x)B)/xA(x)B A(x)含自由x (2)/x(A(x)B)/xA(x)B B不含有自由x5 、约束变元改名规则将A中某量词辖域中变元的每次约束出现，全部换成公式中未出现的字母，所得到的公式记为B，则AB 6 、置换规则：公式局部等值变换后,仍与原公式等值。1、 xA(x) A(a1)A(a2) A(an例题、x(A(x)B)xA(x)B x(A(x)B)x(A(x)B)pqpq的代换实例xA(x)B量词作用域的收缩与扩张律xA(x)B德摩律xA(x)B pq

38、pq的代换实例例题、x(A(x)B)xA(x)B 例题、 x(B A(x)BxA(x) x(BA(x)x(BA(x)pqpq的代换实例BxA(x)量词作用域的收缩与扩张律 BxA(x) pqpq的代换实例例题、 x(A(x)B) xA(x)Bx(A(x)B)x(A(x)B) pqpq的代换实例xA(x)B 量词作用域的收缩与扩张律xA(x)B 德摩律xA(x)B pqpq的代换实例例题、 x(B A(x)BxA(x) 例题、 x(B A(x)BxA(x) x(B A(x)x(B A(x)pqpq的代换实例BxA(x)量词作用域的收缩与扩张律BxA(x) pqpq的代换实例例题、 x(M(x)F

39、(x)x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)德摩律x (M(x)F(x)德摩律x(M(x)F(x) pqpq的代换实例例题、 x(B A(x)BxA(x) 例题、 x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)x(M(x)F(x) pqpq的代换实例x(M(x)F(x) 德摩律x (M(x)F(x) 德摩律x (M(x)F(x) pp的代换实例例题、 x(M(x)F(x)x(M(x)F例题、 xy(F(x)G(y)H(x,y) xy(F(x)G(y)H(x,y) xy(F(x)G(y)H(x,y)xy(F(x)G(y)H(x,y) 德摩律xy(F(x)G(y

40、)H(x,y) pqpq xy( (F(x)G(y)H(x,y)德摩律xy(F(x)G(y)H(x,y) ppxy(F(x)G(y)H(x,y) 结合律 例题、 xy(F(x)G(y)H(x,y)例题、 xy (F(x)G(y) L(x,y) xy (F(x)G(y)L(x,y) xy (F(x)G(y) L(x,y)xy(F(x)G(y) L(x,y)德摩律xy(F(x)G(y)L(x,y)德摩律xy(F(x)G(y)L(x,y) pqpq 例题、 xy (F(x)G(y) L(x,y)例1 将下面公式化成等值的公式,使其不含有既是约束出现又是自由出现的个体变项。 xF(x,y,z)yG(x

41、,y,z)解：x在前件中是约束变元，在后件是自由变元, y在前件中是自由变元，在后件是约束变元，容易产生歧义，故要改名！ 约束变元改名： tF(t,y,z)sG(x,s,z)也可以对自由变元改名： xF(x,s,z)yG(t,y,z)例1 将下面公式化成等值的公式,使其不含有既是约束出现又是自例 将下面公式化成等值的公式,使其不含有既是约束出现又是自由出现的个体变项。 xF(x,y,z)yG(x,y,z)解：x在前件中是约束变元，在后件是自由变元, y在前件中是自由变元，在后件是约束变元， 约束变元改名： tF(t,y,z)sG(x,s,z)对自由变元改名： xF(x,s,z)yG(t,y,z

42、) x(F(x,y)yG(x,y,z)解：y在前件是自由，在后件是约束，有歧义！ x(F(x,y)sG(x,s,z)例 将下面公式化成等值的公式,使其不含有既是约束出现又是自2.4 谓词公式范式 定义：一个谓词公式，如果量词均在全式的开头，它们的作用域延伸到整个公式的末尾，则该公式称为前束范式，形如Q1x1Q2x2QkxkB，其中Qi为或，B中不含有数量词。 如 xy(F(x)G(y)H(x,y) 是前束范式 x(F(x)y(G(y)H(x,y)不是！因B有量词 定理1：任何逻辑公式可转换为前束范式。 说明：利用代换实例，将、转换为 用德摩律将否定深入到原子公式前面 用量词辖域的扩张与收缩律，

43、将量词的前面，左移到最前面，可能还要对约束变元换名。2.4 谓词公式范式2.4 谓词公式范式定理1：任何逻辑公式可转换为前束范式。 步骤： (1)剔除不起作用的量词；(2)若约束变元与自由变元同名则约束变元改名；(3)如果与前面的约束变元同名，则后者改名；(4)利用代换实例，将、转换表示；(5) 将否定深入到原子公式的前面；(6)利用量词辖域的扩张与收缩规律或利用量词的分配律，将量词移到最左边 。2.4 谓词公式范式2.4 谓词公式范式例 公式xP(x)xQ(x)转换为前束范式 xP(x)xQ(x)xP(x)yQ(y)后方约束变元改名xP(x) yQ(y)条件式的代换实例xP(x)yQ(y)否

44、定到底xy(P(x)yQ(y)量词辖域的扩张或，显然不唯一xP(x)xQ(x)xP(x)xQ(x)条件式的代换实例xP(x)xQ(x)德摩律x(P(x)Q(x)量词的分配律2.4 谓词公式范式2.4 谓词公式范式例 xP(x,y) yQ(x,y)转换为前束范式 xP(x,y) yQ(x,y)rP(r,y) sQ(x,s)约束变元改名rP(r,y) sQ(x,s)转换条件式rP(r,y) sQ(x,s)德摩律rs(P(r,y)Q(x,s)量词辖域的扩张2.4 谓词公式范式例x(yA(x,y)xy(B(x,y)y(A(y,x)B(x,y)为前范式x(yA(x,y)xy(B(x,y)y(A(y,x)

45、B(x,y)x(yA(x,y)xy(B(x,y)r(A(r,x)B(x,r) 改名x(yA(x,y)xs(B(x,s)r(A(r,x)B(x,r) 改名x(yA(x,y)ts(B(t,s)r(A(r,t)B(t,r) 改名 书上错了x(yA(x,y)ts(B(t,s)r(A(r,t)B(t,r) 条件式x (yA(x,y)ts(B(t,s)r(A(r,t)B(t,r) 德摩律x (yA(x,y)ts(B(t,s)r(A(r,t)B(t,r) 同上x (yA(x,y)ts(B(t,s)r(A(r,t)B(t,r) x (yA(x,y)ts (B(t,s)r(A(r,t)B(t,r) x (yA(

46、x,y)ts (B(t,s)r(A(r,t)B(t,r) x (yA(x,y)ts (B(t,s)r (A(r,t)B(t,r) x (yA(x,y)ts (B(t,s)r (A(r,t)B(t,r)xytsr(A(x,y) (B(t,s) (A(r,t)B(t,r)例x(yA(x,y)xy(B(x,y)y(A2.5 谓词推理 引言：推理是永恒的话题，谓词逻辑同样要进行推理，只是比命题逻辑更加复杂。 谓词逻辑中不能使用真值表。 谓词逻辑的等值式，其判断也只能根据代换实例规则，沿用命题逻辑中的等值式。 因此只能使用自然推理的方法，即直接从前提出发，利用基本原则，不断推出结论 谓词逻辑自有的等值式

47、并不多，即使有 也是只能理解而无法证明的规律，如德摩律、分配律等。2.5 谓词推理2.5 谓词推理 定义1 若在各种解释下A1A2A3AnB只能为真,则称为前提A1,A2,An可推出结论B。 定义2 当A1A2A3An为真时B为真，即 当A1,A2,A3,An为真时B为真。 方法： 当前提条件A1,A2,An为真时，利用等值式推出其他公式也为真，或利用谓词推理规律，推出其他公式为真， 最终推出结论也为真。2.5 谓词推理 常见的推理方法 一、谓词逻辑的等值演算原则、规律： 命逻的代换实例、量词德摩律、量词分配律、量词辖域的扩张与收缩、约束变元改名。二、命题逻辑的推理规则的代换实例。 如假言推理

48、规则、传递律、合取与析取的性质律、CP规则、反证法等。三、谓词逻辑的推理公理xA(x)xB(x)x(A(x)B(x) x(A(x)B(x)xA(x)xB(x) 别反了 四条推理铁律 常见的推理方法 三、谓词逻辑推理公理:仅能理解左真时右真xA(x)xB(x)x(A(x)B(x) x(A(x)B(x)xA(x)xB(x) 别反了 四条推理铁律全称量词的指定US或-：xA(x)A(x0) x0是论域中的任意个体 存在量词的指定ES或-：xA(x)A(c) c为某个特定的个体，不是任意的个体全称量词的推广UG或+：A(x0) xA(x) x0是论域中的任意个体 存在量词的推广EG或+：A(c) xA

49、(x) c为某个体 三、谓词逻辑推理公理:仅能理解左真时右真例题 (x(H(x)O(x)H(c)O(c)， 亚里斯多德的三段论(1) x(H(x)O(x)为真(前提)(2) H(c)O(c) 为真(全称指定x=c时为真)(3) H(c) 为真(前提)(4) O(c) 为真(2)(3)与假言推理代换实例) 通过“指定规则”将量词去掉, 通过代换实例沿用命题逻辑的方法. 例题 (x(H(x)O(x)H(c)O(c)，例题 (x(H(x)O(x)H(c)O(c)， 亚里斯多德的三段论(1) x(H(x)O(x)为真(前提)(2) H(c)O(c) 为真(全称指定x=c时为真)(3) H(c) 为真(前提)(4) O(c) 为真(2)(3)与假言推理代换实例) 通过“指定规则”将量词去掉, 通过代换实例沿用命题逻辑的方法. 例题 (x(H(x)O(x)H(c)O(c)，例题 x(F(x)G(x),xF(x)xG(x)证明:(1)xF(x)为真 (前提)(2) F(c)为真 (存在指定,至少存在c使F(c)为真)(3) x(F(x)G(x)为真 (前提)(4) F(c)G(c)为真 (全称指定,尤其x=c时为真)(5) G(c)为真 ( (2)