谓词逻辑 谓词逻辑.ppt

第二章第二章 谓词逻辑谓词逻辑v问题的提出问题的提出：一个原子命题只用一个字母表示，一个原子命题只用一个字母表示，而不再对命题中的句子成分细分。而不再对命题中的句子成分细分。v所有的人都是要死的；所有的人都是要死的；苏格拉底是人；苏格拉底是人；所以，苏格拉底是要死的。所以，苏格拉底是要死的。v令令P：所有的人都是要死的；：所有的人都是要死的；Q：苏格拉底是人；：苏格拉底是人；R：苏格拉底是要死的。：苏格拉底是要死的。则原问题符号化为：则原问题符号化为：PQR。2-1 2-1 基本概念基本概念2-1.1 2-1.1 个体与个体变元个体与个体变元v定义定义：能够独立存在的事物，称之为：能够独立存在的事物，称之为个体个体，也，也称之为称之为客体客体。它可以是具体的，也可以是抽象的。它可以是具体的，也可以是抽象的事物。通常用小写英文字母事物。通常用小写英文字母a、b、c、.表示。表示。v定义定义：用小写英文字母：用小写英文字母x、y、z.表示任何个表示任何个体，则称这些字母为体，则称这些字母为个体变元个体变元。2-1.2 2-1.2 谓词谓词v定义定义：用以刻画个体的性质或者个体之间关系的即：用以刻画个体的性质或者个体之间关系的即是是谓词谓词。v例如例如 S(x):表示表示x x是大学生。是大学生。一元谓词一元谓词 G(x,y)：表示表示 xy。二元谓词二元谓词 B(x,y,z)：表示表示x在在y与与z之间。三元谓词之间。三元谓词一般地一般地 P(P(x1 1,x2 2,xn)是是n元谓词。元谓词。2-1.3 2-1.3 命题函数命题函数谓词相当于一个函数，称之为谓词相当于一个函数，称之为命题函数命题函数。定义定义：n元谓词元谓词P(P(x1 1,x2 2,xn)称之为称之为简单命题简单命题函数函数。规定：规定：当命题函数当命题函数P(P(x1 1,x2 2,xn)中中 n=0=0 时，时，即即0 0元谓词，表示不含有客体变元的谓词，它元谓词，表示不含有客体变元的谓词，它本身就是一个命题变元。本身就是一个命题变元。复合命题函数复合命题函数定义定义：将若干个简单命题函数用逻辑联结词联结起来，：将若干个简单命题函数用逻辑联结词联结起来，构成的表达式，称之为构成的表达式，称之为复合命题函数复合命题函数。简单命题函数。简单命题函数与复合命题函数统称为与复合命题函数统称为命题函数命题函数。例：给定简单命题函数：例：给定简单命题函数：A(A(x)：x身体好，身体好，B(B(x)：x学习好，学习好，C(C(x)：x工作好，工作好，则复合命题函数则复合命题函数 A(x)()(B(B(x)C(C(x)表示表示2-1.4 2-1.4 论域论域(个体域个体域)v设设N(N(x)表示表示“x是负数是负数”，I(I(x)表示表示“x是整数是整数”，则，则N(N(x)I()I(x)表示表示v设设P(x)表示表示“x是大学生是大学生”。论域论域(个体域个体域)v定义定义：在：在命题函数命题函数中命题变元的取值范围，称之为中命题变元的取值范围，称之为论域论域，也称之为，也称之为个体域个体域。例如例如 S(S(x):):x是大学生，个体域是是大学生，个体域是:人类。人类。G(x,y)：x y，个体域是个体域是:实数。实数。v定义定义：由所有论域构成的论域，称之为：由所有论域构成的论域，称之为全总个体域全总个体域。v约定约定:对于一个命题函数，如果没有给定个体域，则对于一个命题函数，如果没有给定个体域，则假定该个体域是全总个体域假定该个体域是全总个体域。个体函数个体函数v例：张华的父亲是教师。例：张华的父亲是教师。v设设P(x)：表示表示x是教师。是教师。a：表示张华的父亲。表示张华的父亲。则原命题符号化为：则原命题符号化为：设设f(x):表示表示x的的父亲。父亲。a：表示张华。表示张华。则原命题符号化为：则原命题符号化为：f(x)称为称为个体函数（或函词）。个体函数（或函词）。注意区分个体函数与谓词间的区别：注意区分个体函数与谓词间的区别：v个体函数是论域到论域的映射个体函数是论域到论域的映射，g:NN:NN，如果指定的个体如果指定的个体aNN，则，则g(a)N)N。谓词是从个体域到谓词是从个体域到T,FT,F的映射的映射，即谓词，即谓词E(E(x)可以看成映射可以看成映射E:NT,FE:NT,F，如果指如果指定个体定个体aNN，则则E(E(a)的真值的真值T,FT,F。2-1.5 2-1.5 量词量词v例如：例如：v有些人是大学生。有些人是大学生。v 所有事物都是发展变化的。所有事物都是发展变化的。v 任何一个有理数都可以用分数形式表示。任何一个有理数都可以用分数形式表示。定义定义：在命题中表示对个体数量化的词，称之：在命题中表示对个体数量化的词，称之为为量词量词。存在量词与全称量词存在量词与全称量词 (1).(1).存在量词存在量词：记作：记作，表示，表示“有些有些”、“有一个有一个”、“某些某些”、“至少一个至少一个”等。等。xF(F(x):):表示存在着客体域中的客体具有性质表示存在着客体域中的客体具有性质F F。当且仅当论域中至少有一个当且仅当论域中至少有一个x0 0使得使得F(F(x0 0)为为T T时，时，xF(F(x)为为真。真。(2).(2).全称量词全称量词：记作：记作，表示，表示“每个每个”、“任何一个任何一个”、“一一切切”、“所有的所有的”、“凡是凡是”、“任意的任意的”等。等。xF(F(x):):表示客体域里所有的客体都有性质表示客体域里所有的客体都有性质F F。当且仅当对论域中所有的当且仅当对论域中所有的x x来说，来说，F(F(x)均为均为T T时，时，xF(F(x)为为真。真。v定义定义：量词后边要有一个个体变元，指明对哪个个体：量词后边要有一个个体变元，指明对哪个个体变元量化，称此客体变元是变元量化，称此客体变元是量词后的指导变元量词后的指导变元。2-2 2-2 谓词公式及命题符号谓词公式及命题符号化化 原子谓词公式原子谓词公式v定义定义：称：称n元谓词元谓词P(P(x1 1,x2 2,.,.,xn)为原子为原子谓词公式。谓词公式。v例如例如 P P、Q(Q(x)、A(A(x,f(x)、B(B(x,y,a)都是原子谓词公式。都是原子谓词公式。2-2.3 2-2.3 谓词合式公式谓词合式公式(WFF)(WFF)(Well Formed formulas)(Well Formed formulas)v定义定义：谓词合式公式递归定义如下：谓词合式公式递归定义如下：1.1.原子谓词公式是合式公式。原子谓词公式是合式公式。2.2.如果如果A A是合式公式，则是合式公式，则 A A也是合式公式。也是合式公式。3.3.如果如果A A、B B是合式公式，则是合式公式，则(AB)(AB)、(AB)(AB)、(AB)(AB)、(A(AB)B)都是合式公式。都是合式公式。4.4.如果如果A A是合式公式是合式公式，x是中的任何个体变元，是中的任何个体变元，则则 x和和 x也是合式公式。也是合式公式。5.5.只有有限次地按规则只有有限次地按规则(1)(1)至至(4)(4)求得的公式才求得的公式才是合式公式。是合式公式。v谓词合式公式谓词合式公式也叫也叫谓词公式谓词公式，简称，简称公式公式。v判断下面哪些符号串是合式公式：判断下面哪些符号串是合式公式：P P、(PQ)(PQ)、(Q(Q(x)P)P)、x(A(A(x)B()B(x)、xC(C(x)、x y P(P(x)、P P(x)Q()Q(x)xv为了方便，最外层括号可以省略，但是为了方便，最外层括号可以省略，但是若量词后边有括号，则此括号不能省。若量词后边有括号，则此括号不能省。2-2.4 2-2.4 量词的作用域量词的作用域(辖域辖域)v定义定义：在谓词公式中，量词的作用范围称之为：在谓词公式中，量词的作用范围称之为量词的量词的作用域作用域，也叫量词的，也叫量词的辖域辖域。v例如例如 xA(A(x)中中 x的作用域为的作用域为A(A(x).).v x(P(P(x)Q()Q(x)yR(R(x,y)中中 x x的作用域是的作用域是(P(P(x)Q(Q(x)yR(R(x,y)y y的作用域为的作用域为R(R(x,y)。v x y z(A(x,y)B()B(x,y,z)C()C(t)x x的辖域的辖域 z z的辖域的辖域 y y的辖域的辖域2-2.5 2-2.5 自由变元与约束变元自由变元与约束变元v定义定义：如果个体变元：如果个体变元x在在 x或者或者 x的作用域内，的作用域内，则称则称x在此作用域内约束出现，并称在此作用域内约束出现，并称x在此作用在此作用域内是域内是约束变元约束变元。否则。否则x是自由出现，并称是自由出现，并称x是是自自由变元由变元。v x(F(F(x,y)yP(P(y)Q()Q(z)对约束变元和自由变元有如下几点说明：对约束变元和自由变元有如下几点说明：(1).(1).对约束变元用什么符号表示无关紧要。对约束变元用什么符号表示无关紧要。(2).(2).一个谓词公式如果无自由变元，它就表示一个一个谓词公式如果无自由变元，它就表示一个命题命题。3).3).一个一个n元谓词元谓词P(P(x1 1,x2 2,xn)，若在前边添加，若在前边添加k个个量词，使其中的量词，使其中的 k个个体变元变成约束变元，则个个体变元变成约束变元，则此此 n元谓词就变成了元谓词就变成了n-k元谓词。元谓词。v约束变元的改名规则约束变元的改名规则：(1).(1).对约束变元可以更改名称，改名的对约束变元可以更改名称，改名的范围是：量词后的指导变元以及该量范围是：量词后的指导变元以及该量词的作用域内此个体变元出现的各处词的作用域内此个体变元出现的各处同时换名。同时换名。(2).(2).改名后用的个体变元名称，不能与改名后用的个体变元名称，不能与该量词的作用域内的其它变元名称相该量词的作用域内的其它变元名称相同。同。例如例如 x(P(P(x)Q()Q(x,y)(R()(R(x)A()A(x)可以可以对对x改名改名成成 z(P(P(z)Q()Q(z,y)(R()(R(x)A()A(x)对自由变元也可以换名字，此换名叫代入。对自由变元也可以换名字，此换名叫代入。对对自由变元的代入规则自由变元的代入规则：(1).(1).对谓词公式中的自由变元可以作代入。对谓词公式中的自由变元可以作代入。代入时需要对公式中出现该变元的每一处，代入时需要对公式中出现该变元的每一处，同时作代入。同时作代入。(2).(2).代入后的变元名称要与公式中的其它变代入后的变元名称要与公式中的其它变元名称不同元名称不同2-2.6 2-2.6 命题的符号化命题的符号化在谓词演算中，在谓词演算中，命题的符号表达式与论域有关命题的符号表达式与论域有关系系。1.1.每个自然数都是整数。每个自然数都是整数。(1).(1).如果论域是自然数集合如果论域是自然数集合N N，令，令 I(I(x)：x是整是整数，则命题的表达式为数，则命题的表达式为 xI(I(x)。(2).(2).如果论域扩大为如果论域扩大为全总个体域全总个体域时，上述表达式时，上述表达式 xI(I(x)表示表示“所有个体都是整数所有个体都是整数”，显然这是，显然这是假的命题，此表达式已经不能表达原命题了。假的命题，此表达式已经不能表达原命题了。因此需要添加谓词因此需要添加谓词N(N(x)：x是自然数，是自然数，用于表用于表明明x的特性的特性，于是命题的符号表达式为，于是命题的符号表达式为 x(N(N(x)I()I(x)2.2.有些大学生吸烟有些大学生吸烟。(1).(1).如果论域是大学生集合如果论域是大学生集合S S，令，令A(A(x)：x吸烟，吸烟，则命题的表达式为则命题的表达式为 xA(A(x)(2).(2).如果论域扩大为如果论域扩大为全总个体域全总个体域时，上述表达式时，上述表达式 xA(A(x)表示表示“有些客体吸烟有些客体吸烟”，就不是表示此，就不是表示此命题了，故需要添加谓词命题了，故需要添加谓词 S(S(x)：x是大学生，是大学生，用于表明用于表明x的特性的特性，于是命题的表达式为，于是命题的表达式为 x(S(S(x)A()A(x)v为什么必须这样添加特性谓词？为什么必须这样添加特性谓词？1.1.每个自然数都是整数。每个自然数都是整数。2.2.有些大学生吸烟。有些大学生吸烟。v令令N:N:自然数集合，自然数集合，I:I:整数集合，整数集合，S:S:大学生集合大学生集合，A:A:烟民的集合。烟民的集合。INSA吸烟大学生吸烟大学生 I I包含包含N N x(N(N(x)I()I(x)吸烟大学生是吸烟大学生是S S与与A A的交集的交集 x(S(S(x)A()A(x)3.3.所有大学生都喜欢一些歌星。所有大学生都喜欢一些歌星。令令S(S(x)：x是大学生是大学生，X(X(x)：x是歌星，是歌星，L(L(x,y)：x喜欢喜欢y。则命题的表达式为则命题的表达式为 x(S(S(x)y(X(X(y)L()L(x,y)4.4.没有不犯错误的人。没有不犯错误的人。令令P(P(x)：x是人，是人，F(F(x)：x犯错误，犯错误，此命题的表达式为此命题的表达式为5.5.不是所有的自然数都是偶数。不是所有的自然数都是偶数。令令N(N(x)：x是自然数是自然数，E(E(x)：x是偶数，是偶数，命题的表达式为命题的表达式为:6.6.如果一个人只是说谎话，那么他所说的每句话没有一句如果一个人只是说谎话，那么他所说的每句话没有一句是可以相信的。是可以相信的。令令A(A(x)：x是人，是人，B(B(x,y)：y是是x说的话，说的话，C(C(x):):x是谎话，是谎话，D(D(x)：x是可以相信的是可以相信的 命题的表达式为命题的表达式为:x(A(A(x)()(y(B(B(x,y)C()C(y)z(B(B(x,z)D()D(z)7.7.每个人都有一个生母。每个人都有一个生母。设设 P(P(x):):x是个人。是个人。M(M(x,y):):y是是x的生母。此命题可以写的生母。此命题可以写成成 x(P(P(x)y(P(P(y)M()M(x,y)8.8.不管白猫黑猫，抓到老鼠就是好猫。不管白猫黑猫，抓到老鼠就是好猫。设设C C（x）：）：x是猫是猫 B B（x）：）：x是黑的是黑的 W W（x）：）：x是白的是白的 G G（x）：）：x是好的是好的 M M（y）：）：y是老鼠是老鼠 K K（x，y）：）：x抓住抓住y命题的表达式为命题的表达式为:x(C(x)(W(W(x)B(B(x)()(y(M(M(y)K()K(x,y)G()G(x)对对平面上任意两个不同的点，有且仅有一条直平面上任意两个不同的点，有且仅有一条直线通过这两点。线通过这两点。vP(x)：x是是一个点一个点vL(x)：x是是一条直线一条直线vR(x,y,z)：z通过通过x和和yvE(x,y)：x=yv(x)(y)(P(x)P(y)E(x,y)(z)(L(z)R(x,y,z)(u)(L(u)R(x,y,u)E(z,u)v取个体域为实数集，函数取个体域为实数集，函数f在在a点连续的定义是：点连续的定义是：f在点在点a连续，当且仅当对每个连续，当且仅当对每个 0，存在一个，存在一个 0，使得对所有的，使得对所有的x，若若|x-a|,则则|f(x)-f(a)|yv则该定义可符号化为：则该定义可符号化为：P(f,a)v(Q(,o)(Q(,0)x(Q(,|x-a|)Q(,|f(x)-f(a)|)这只大红书柜摆满了那些古书。这只大红书柜摆满了那些古书。vF(x,y):x摆满了摆满了y R(x):x是是大红书柜大红书柜vQ(y):y是是古书古书 a:这只这只 b:那些那些v则则 R(a)Q(b)F(a,b)vA(x):x是是书柜书柜 B(x):x是大是大的的 C(x):x是红是红的的 D(y):y是是古老的古老的 E(y):y是是图书图书 v F(x,y):x摆满摆满y a:这只这只 b:那些那些v则则A(a)B(a)C(a)D(b)E(b)F(a,b)v练习：练习：v金子发光，但发光的不一定都是金子。金子发光，但发光的不一定都是金子。v没有大学生不懂外语。没有大学生不懂外语。v任何金属都可以溶解在某种液体里任何金属都可以溶解在某种液体里v如果明天天气好，有些学生将去香山如果明天天气好，有些学生将去香山v在北京工作的人未必都是北京人在北京工作的人未必都是北京人有限域下公式有限域下公式(x)P(x)、(x)P(x)的表示法的表示法v设设论域为论域为a1，a2，an，则有则有v(x)P(x)=P(a1)P(a2)P(an)v(x)P(x)=P(a1)P(a2)P(an)在域在域a1，a2上多次量化公式上多次量化公式(x)(y)F(x,y)=(x)(y)F(x,y)=(y)F(a1,y)(y)F(a2,y)=F(a1,a1)F(a1,a2)F(a2,a1)F(a2,a2)=F(a1,a1)F(a2,a1)F(a1,a2)F(a2,a2)=(x)F(x,a1)(x)F(x,a2)=(y)(x)F(x,y)(x)(y)F(x,y)=F(a1,a1)F(a1,a2)F(a2,a1)F(a2,a2)=(y)(x)F(x,y)在在域域a1，a2上多次量化公式上多次量化公式(x)(y)F(x,y)=(x)(y)F(x,y)=(y)F(a1,y)(y)F(a2,y)=(F(a1,a1)F(a1,a2)(F(a2,a1)F(a2,a2)(y)(x)F(x,y)=(y)(x)F(x,y)=(x)F(x,a1)(x)F(x,a2)=(F(a1,a1)F(a2,a1)(F(a1,a2)F(a2,a2)(x)(y)F(x,y)(y)(x)F(x,y)2-3.1 2-3.1 对谓词公式赋值对谓词公式赋值v对谓词公式对谓词公式G G的赋值的赋值I I包括以下几点：包括以下几点：（1 1）指定一个个体域）指定一个个体域D D；（2 2）对公式中出现的每个函词，指定对公式中出现的每个函词，指定D D上的个体上的个体函数；函数；（3 3）对公式中出现的每个谓词，指定）对公式中出现的每个谓词，指定D D上的谓词；上的谓词；（4 4）对公式中出现的每个个体常量和自由变元，）对公式中出现的每个个体常量和自由变元，指定指定D D中的一个个体；中的一个个体；（5 5）对公式中出现的每个命题变元，指定一个真）对公式中出现的每个命题变元，指定一个真值（值（T T或或F F）。）。v这样可以得到一个命题这样可以得到一个命题G G1 1，称，称G G1 1的真值为的真值为G G在在I I下下的真值。的真值。谓词公式的分类谓词公式的分类v定义：设定义：设G为一个公式，如果为一个公式，如果G在任何赋值下在任何赋值下都是真的，则称都是真的，则称G为普遍有效式（或永真式）为普遍有效式（或永真式）；如果；如果G在任何赋值下都是假的，在任何赋值下都是假的，则称则称G为不为不可满足式（矛盾式）；若至少存在一个赋值可满足式（矛盾式）；若至少存在一个赋值使使G为真，则称为真，则称G是可满足式。是可满足式。普遍有限式（永真式）普遍有限式（永真式）v(x)F(x)(x)F(x)v(x)F(x)(x)(y)G(x,y)(x)F(x)v(x)F(x)(x)F(x)(y)G(y)可满足式可满足式v(x)P()P(x)v(x)P()P(x)v(x)()(y)F()F(x,y)()(x)()(y)F()F(x,y)2-3.3 2-3.3 谓词公式的等价公式谓词公式的等价公式定义定义v定义定义：给定谓词公式：给定谓词公式A A、B B，若对若对A A和和B B的任一的任一组变元进行赋值，所得命题的真值相同（即组变元进行赋值，所得命题的真值相同（即 A AB B为永真式）为永真式），则称，则称A A与与B B等价，记作等价，记作A A=B B。v2-3.4 2-3.4 谓词公式的永真蕴含式谓词公式的永真蕴含式定义定义v定义定义：给定谓词公式：给定谓词公式A A、B B，如果，如果ABAB为永真为永真式，则称式，则称A A永真蕴含永真蕴含B B，记作，记作A AB B。2-3.5.2-3.5.重要的谓词等价公式和永真蕴含式重要的谓词等价公式和永真蕴含式一一.由命题公式推广出的公式由命题公式推广出的公式 命题公式中常常用到的等价式及永真蕴含式也可以命题公式中常常用到的等价式及永真蕴含式也可以看作是谓词演算中的等价式及永真蕴含式，其中每一命看作是谓词演算中的等价式及永真蕴含式，其中每一命题变元用谓词演算公式代入后仍保持其等价关系及永真题变元用谓词演算公式代入后仍保持其等价关系及永真蕴含关系。蕴含关系。例如例如A(A(x)A(A(x)B()B(x)P PPQPQ x(A(A(x)B()B(x)=x(A(A(x)B()B(x)PQPQ=P PQ Q(xA(A(x)xB(B(x)=xA(A(x)xB(B(x)摩根摩根定律定律量词转换公式量词转换公式1.1.xA(A(x)=x A(A(x)2.2.xA(A(x)=x A(A(x)证明：证明：设论域为设论域为 a1 1,a2 2,.,.,an，则则 xA(A(x)=(A(A(a1 1)A()A(a2 2).A().A(an)=A(A(a1 1)A(A(a2 2).).A(A(an)=x A(A(x)类似可以证明另一个公式。类似可以证明另一个公式。1.1.xA(A(x)=x A(A(x)2.2.xA(A(x)=x A(A(x)v证明：从语义上证明证明：从语义上证明2。对任意赋值对任意赋值I(D)，设，设xA(A(x)为为真，则真，则 xA(A(x)为为假，即对任意的假，即对任意的xDD，A(A(x)为假，所以，对为假，所以，对任意的任意的xDD，A(A(x)为真，即为真，即 x A(A(x)为为真，因真，因此此xA(A(x)x A(A(x)。对任意赋值对任意赋值I(D)，设，设 x A(A(x)为真，则对任意为真，则对任意的的xDD，A(A(x)为真，即对任意的为真，即对任意的xDD，A(A(x)为假，所以为假，所以 xA(A(x)为假，为假，xA(x)为真，因此为真，因此 x A(A(x)xA(A(x)。三三.量词作用域的扩张公式量词作用域的扩张公式 1.1.xA(A(x)B)B=x(A(A(x)B)B)2.2.xA(A(x)B)B=x(A(A(x)B)B)3.3.xA(A(x)B)B=x(A(A(x)B)B)4.4.xA(A(x)B)B=x(x)B)B)5.5.BB xA(A(x)=x(BA(BA(x)6.6.BB xA(A(x)=x(BA(BA(x)7 7.xA(A(x)B)B=x(A(A(x)B)B)8 8.xA(A(x)B)B=x(A(A(x)B)B)xA(A(x)B)B=x(A(A(x)B)B)v证明：设证明：设I(D)是使是使 xA(A(x)B)B为为T T的个体域和解的个体域和解释，则释，则I(D)I(D)时时B B为为T T且且 xA(A(x)为为T T，所以所以 I(D)I(D)使使A(A(x)对对一切一切x为为T T，即即 I(D)I(D)使使A(A(x)B)B对对一切一切x为为T T，即即 I(D)I(D)使使 x(A(A(x)B)B)为为T.T.反之，上述证明可逆。反之，上述证明可逆。所以所以 xA(A(x)B)B =x(A(A(x)B)B)。vBB xA(A(x)=x(BA(BA(x)v证明：证明：BB xA(A(x)=BB xA(A(x)v =x(BA(BA(x)=x(BA(BA(x)v xA(A(x)B)B=x(A(A(x)B)B)v证明：证明：xA(A(x)B)B=xA(A(x)B)Bv =x A(A(x)B)B =x(A(A(x)B)B)=x(A(A(x)B)B)四四.量词分配公式量词分配公式1.1.x(A(A(x)B()B(x)=xA(A(x)xB(B(x)2.2.x(A(A(x)B()B(x)=xA(A(x)xB(B(x)v个体域：个体域：某班学生某班学生vA(x)：x是高才生。是高才生。vB(x)：x是运动健将。是运动健将。证明证明：设论域为：设论域为 a1 1,a2 2,.,.,an，x(A(A(x)B()B(x)=(A(A(a1 1)B()B(a1 1)(A()(A(a2 2)B()B(a2 2)(A()(A(an)B()B(an)=(A(A(a1 1)A()A(a2 2).A().A(an)(B(B(a1 1)B()B(a2 2).B().B(an)=xA(A(x)xB(B(x)五五.带有量词的蕴含带有量词的蕴含式式1.1.x(A(A(x)B()B(x)xA(A(x)xB(B(x)2.2.xA(A(x)xB(B(x)x(A(A(x)B()B(x)v证明证明：假设在论域：假设在论域D D和赋值和赋值I I下前件下前件 x(A(A(x)B()B(x)为为真，真，则论域中至少有一个客体则论域中至少有一个客体a，使得，使得 A(A(a)B()B(a)为为真，于是真，于是A(A(a)和和B(B(a)都为都为 真，所以有真，所以有 xA(A(x)以及以及 xB(B(x)为真，进而得为真，进而得 xA(A(x)xB(B(x)为真。于是有为真。于是有 x(A(A(x)B()B(x)xA(A(x)xB(B(x)3.3.x(A(A(x)B()B(x)xA(A(x)xB(x)v用用解释法证明：解释法证明：v设在一赋值设在一赋值I(D)下，有下，有 x(A(A(x)B()B(x)为为T T，则对则对D D中的任何中的任何一个客体一个客体x，有，有A(A(x)B()B(x)为为T T，这这必能保证必能保证 xA(A(x)为为T T时，时，xB(B(x)为为T T，从而从而 xA(A(x)xB(x)为为T。六两个量词的公式六两个量词的公式v对于二元谓词，如果不考虑自由变元，可以有以下对于二元谓词，如果不考虑自由变元，可以有以下几种情况：几种情况：v x yA(A(x,y)，y xA(A(x,y)v x yA(x,y)，y xA(A(x,y)v x yA(x,y)，y xA(A(x,y)v y xA(A(x,y)，x yA(A(x,y)vA(A(x,y)：x与与y同姓。同姓。vx的论域：的论域：甲村的人甲村的人 y的论域：的论域：乙村的人乙村的人 2-42-4前束范式前束范式1.1.前束范式定义：前束范式定义：如果一个谓词公式符合下面条件，它就是如果一个谓词公式符合下面条件，它就是前束范式前束范式：所有量词前面都没有联接词；所有量词前面都没有联接词；所有量词都在公式的左面；所有量词都在公式的左面；所有量词的辖域都延伸到公式的末尾。所有量词的辖域都延伸到公式的末尾。判断下列公式哪些是前束范式：判断下列公式哪些是前束范式：y x z(A(A(x)(B()(B(x,y)C()C(x,y,z)，xA(A(x)yB(B(y)x(x)B()B(x)，x y(A(A(x)(B()(B(x,y)zC(C(z)xA(A(x)B()B(x)。结论：任意一个谓词公式均和一个前束范式等值。结论：任意一个谓词公式均和一个前束范式等值。2.2.前束范式的写法前束范式的写法1)1)消去公式中的联接词消去公式中的联接词和和(为了便于量词辖域的为了便于量词辖域的扩充扩充)；2)2)如果量词前有如果量词前有“”，则用量词否定公式将，则用量词否定公式将“”后后移。再用摩根定律或求公式的否定公式，将移。再用摩根定律或求公式的否定公式，将“”后移到原子谓词公式之前。后移到原子谓词公式之前。3)3)用约束变元的改名规则或自由变元的代入规则对变用约束变元的改名规则或自由变元的代入规则对变元换名元换名(为量词辖域扩充作准备为量词辖域扩充作准备)4)4)用量词辖域扩充公式提取量词，使之成为前束范式用量词辖域扩充公式提取量词，使之成为前束范式形式。形式。v例例1.xA(A(x)xB(B(x)=xA(A(x)xB(B(x)=x A(A(x)xB(B(x)=x A(A(x)yB(B(y)()(换元换元)=x(A(A(x)yB(B(y)()(量词辖域扩充量词辖域扩充)=x y(A(A(x)B()B(y)v另一个方法：另一个方法：xA(A(x)xB(x)=xA(A(x)xB(B(x)=x A(A(x)xB(B(x)=x(A(A(x)B()B(x)()(量词分配公式量词分配公式)v例例2.2.x(P(P(x)R()R(x)()(xP(P(x)Q()Q(x)=x(P(P(x)R()R(x)()(xP(P(x)Q()Q(x)(去去)=x(P(P(x)R()R(x)()(x P(P(x)Q()Q(x)(量词转换量词转换)=x(P(P(x)R(R(x)()(x P(P(x)Q()Q(x)(后移后移)=x(P(P(x)R(R(x)()(y P(P(y)Q()Q(z)(换变元换变元)=x(P(P(x)R(R(x)y(P(P(y)Q()Q(z)(扩量词辖域扩量词辖域)=x y(P(P(x)R(R(x)()(P(P(y)Q()Q(z)(扩量词辖域扩量词辖域)注意：前束范式不唯一。注意：前束范式不唯一。3.3.前束析取范式与前束合取范式前束析取范式与前束合取范式：前束析取范式前束析取范式:前束范式中量词后的括号内是析前束范式中量词后的括号内是析取范式形式。取范式形式。前束合取范式前束合取范式:前束范式中量词后的括号内是合前束范式中量词后的括号内是合取范式形式。取范式形式。上例的前束析取范式为上例的前束析取范式为:x y(P(P(x)R(R(x)()(P(P(y)Q()Q(z)上例的前束合取范式为上例的前束合取范式为:x y(P(P(x)R(R(x)P(P(y)(P(P(x)R(R(x)Q()Q(z)Skolem标准形标准形v如果对前束范式进而要求所有存在量词都在如果对前束范式进而要求所有存在量词都在前称量词的左边，或是只保留全称量词而消前称量词的左边，或是只保留全称量词而消去存在量词，则得到去存在量词，则得到Skolem标准形。标准形。v注意：一个谓词公式与它的注意：一个谓词公式与它的Skolem标准形一标准形一般只能保持在某种意义下的等值关系。般只能保持在某种意义下的等值关系。仅仅介绍只保留全称量词而消去存介绍只保留全称量词而消去存在量词的在量词的Skolem标准形。标准形。v定理：谓词逻辑的任一个公式定理：谓词逻辑的任一个公式A，都可以化都可以化成相应的成相应的Skolem标准形（只保留全称量词而标准形（只保留全称量词而消去存在量词），并且消去存在量词），并且A是不可满足的当且仅是不可满足的当且仅当其当其Skolem标准形是不可满足的。标准形是不可满足的。求求xyzu(F(a,x,y)G(u,b)H(z)的的Skolem标准形标准形v化为前束范式；化为前束范式；v消去存在量词消去存在量词vxyzu(F(F(a,x,y)G(G(u,b)H(H(z)消去消去y，得到，得到 xzu(F(F(a,x,f(x)G(G(u,b)H(H(z)消去消去z，得到原公式的，得到原公式的SkolemSkolem标准形：标准形：xz(F(F(a,x,f(x)G(G(g(x,z),),b)H(H(z)其中，其中，f、g是不曾在原公式中出现的符号。是不曾在原公式中出现的符号。xyF(F(x,y)的的SkolemSkolem标准形为标准形为yF(F(a,y)。2-5 2-5 谓词演算的推理理论谓词演算的推理理论推理方法：推理方法：直接推理、条件论证、反证法、归结法直接推理、条件论证、反证法、归结法所用公式：等价式、蕴含式所用公式：等价式、蕴含式推理规则推理规则：P、T、CP、US、ES、EG、UGv下面介绍四个新规则：下面介绍四个新规则：一一.全称特指规则全称特指规则 US(Universal Specialization)形式：形式：xA(A(x)A(A(c)(其中其中c是论域内是论域内指定个体指定个体)含义：如果含义：如果 xA(A(x)为真，则在论域内为真，则在论域内任何指定任何指定个体个体 c，都使得都使得A(A(c)为真。为真。作用：去掉全称量词。作用：去掉全称量词。要求要求：c不是不是A(A(x)中的符号。中的符号。v例子：例子：x y(P(P(x，z)Q(Q(x，y)y(y(P(P(c，z)Q(Q(c，y)x y(P(P(x，z)Q(Q(x，y)y(P(P(y，z)Q(Q(y，y)二二.存在特指规则存在特指规则ES(Existential Specialization)形式：形式：xA(A(x)A(A(c)(其中其中c是论域内是论域内指定个体指定个体)含义：如果含义：如果 xA(A(x)为真，则在论域内为真，则在论域内指定指定个体个体c，都使得都使得A(A(c)为真。为真。作用：去掉存在量词。作用：去掉存在量词。要求：要求：c不是不是A(A(x)中的符号。中的符号。用用ESES指定的客体指定的客体c不应该是不应该是在此之前在此之前用用USUS规则或者用规则或者用ESES规则所指定的规则所指定的个个体体c。(3)A(3)A（x）中除中除x外还有其他自由出现的个外还有其他自由出现的个体变元时，不能用此规则。体变元时，不能用此规则。例例1.令令A(x)表示表示x是自然数，是自然数，B(x)表示表示x是整是整数。数。x(A(A(x)B()B(x)P)P A(A(c)B()B(c)US )US 如如c=0.1=0.1 xA(A(x)P)P A(A(c)ES ES A(0.1)A(0.1)为为F F xB(B(x)P)P B(B(c)ES )ES 如如c=-1=-1 xA(A(x)P)P A(A(c)ES ES A(-1)A(-1)为为F F三三.存在推广规则存在推广规则 EGEG (Existential Generalization)(Existential Generalization)形式：形式：A(A(c)xA(x)(其中其中c是论域内是论域内指定个体指定个体)含义：如果含义：如果在论域内在论域内指定指定个体个体c使得使得 A(A(c)为真，则为真，则 xA(A(x)为真。为真。作用：添加存在量词。作用：添加存在量词。要求要求：x不是不是A(A(c)中的符号。中的符号。v例子：例子：x z(P(P(x,c)Q(Q(c,z)x(x z(P(P(x,x)Q(Q(x,z)y(x z(P(P(x,y)Q(Q(y,z)四四.全称推广规则全称推广规则UGUG (Universal Generalization)(Universal Generalization)形式：形式：A(A(c)xA(A(x)(其中其中c是论域内是论域内任何任何指定个体指定个体)含义：如果含义：如果在论域内在论域内任何指定任何指定个体个体c c都都使使 得得A(A(c)为真，为真，则则 xA(A(x)为真。为真。作用：添加作用：添加全称全称量词。量词。要求：要求：x不是不是A(A(c)中的符号。中的符号。c一定是任意一定是任意的的个个体，否则不可体，否则不可全全 称推广称推广。例：实数集中，例：实数集中，(x)(y)(xy)是真是真命命题，但题，但(y)(x)(xy)是是假假命题命题。v(1)(x)(y)(xy)Pv(2)(y)(zy)USv(3)zc ESv(4)(x)(xc)UGv(5)(y)(x)(xy)EGv例子：例子：下列推导是否有错误？下列推导是否有错误？1.(1)1.(1)y(P(P(y)Q(Q(y)P)P (2)P(2)P(a)Q Q(b)US)US（1 1）2.(1)2.(1)xP(P(x)Q()Q(x)P)P (2)P(2)P(x)Q()Q(x)US)US（1 1）3.(1)3.(1)xR(R(x)x(Q(Q(x)R(R(x)P)P (2)(2)R(R(a)x(Q(Q(x)R(R(x)ES)ES（1 1）与与量词有关的重要等价式量词有关的重要等价式v x(A(x)B(x)xA(x)xB(x)v x(A(x)B(x)xA(x)xB(x)vxA(x)x A(x)vxA(x)x A(x)v x(A B(x)AxB(x)v x(A B