离散数学谓词逻辑

1、引言引言 命题逻辑命题逻辑好像功能强大，但还是有些问题难以解决。好像功能强大，但还是有些问题难以解决。 如杨圣洪要喝水、刘翔要喝水、姚明要喝水、姚晨要如杨圣洪要喝水、刘翔要喝水、姚明要喝水、姚晨要喝水、刘德华要喝水、喝水、刘德华要喝水、，可归纳为，可归纳为“某某要喝水某某要喝水”，无法表示。无法表示。 所有的人都要呼吸、喝水、吃饭所有的人都要呼吸、喝水、吃饭，“所有所有”如何如何表示呢？表示呢？ 有些人要升官、有些人要失恋有些人要升官、有些人要失恋，“有些有些”又如何又如何表示？表示？ 所有所有男人都会多男人都会多看看几眼漂亮几眼漂亮女人女人 所有所有女人都会多女人都会多喜欢喜欢漂亮的漂亮的衣

2、服衣服 又如有名又如有名三段论三段论：所有人都是要变老的，杨圣洪是人，：所有人都是要变老的，杨圣洪是人，所以杨圣洪也会变老的，无法表示所以杨圣洪也会变老的，无法表示。 为此为此需要我们学习新的逻辑工具需要我们学习新的逻辑工具-谓词逻辑谓词逻辑或一阶逻辑或一阶逻辑2.1基本概念基本概念 1、谓词、谓词 “某某要喝水某某要喝水”、“喜欢漂亮衣服喜欢漂亮衣服”、“喜欢喜欢帅哥帅哥”、“结婚生崽结婚生崽”都是所在句子的都是所在句子的谓语部分谓语部分。 命题逻辑命题逻辑中用大写字母表示命题。中用大写字母表示命题。 谓词逻辑谓词逻辑中用大写字母表示中用大写字母表示谓语部分谓语部分，如，如 用用W表示表示“

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

4、靠前的字母表示常量。常量。2.1基本概念基本概念 3、个体变元、个体变元 如如“某某某某”、“男人男人”、“女人女人”， 常用常用x,y,z,r,s,t等字母表中靠后的字母表示，等字母表中靠后的字母表示， 其他学科中，也是这样表示，其他学科中，也是这样表示， 因此因此“某某要喝水某某要喝水”表示为表示为W(x), ,x泛指所有的人，泛指所有的人， “ “女人喜欢漂亮衣服女人喜欢漂亮衣服”表示为表示为L(x,y)，x泛指泛指“女人女人”、y泛指泛指“衣服衣服”， “ “女人喜欢帅哥女人喜欢帅哥”表示为表示为H(y,z)，其中其中y泛指女人、泛指女人、z泛指帅哥。泛指帅哥。 “ “男人结婚生崽男人

5、结婚生崽”表示为表示为M(z)，z泛指男人。泛指男人。 2.1基本概念基本概念 4、全称量词、全称量词 为了表示为了表示“所有女人都喜欢漂亮的衣服所有女人都喜欢漂亮的衣服”、 “ “所有女人都喜欢帅哥所有女人都喜欢帅哥”等中等中 可能是可能是“ALL”的字母的字母A倒写，表示倒写，表示所有、全部所有、全部。 当用当用x泛指泛指“人人”，“所有人所有人”表示为表示为“ x”， “ “所有活人都要喝水所有活人都要喝水”表示为表示为 xW(x)。 当用当用x表示表示“女人女人”, ,y表示表示漂亮的衣服漂亮的衣服时，时， “ “所有女人所有女人”则表示为则表示为 x x、 “ “所有漂亮的衣服所有漂

6、亮的衣服”则表示为则表示为“ y”，因此，因此 “ “所有女人都喜欢漂亮的衣服所有女人都喜欢漂亮的衣服”表示为表示为 x yL(x,y)。 当用当用x表示表示“女人女人”, ,y表示帅哥时，表示帅哥时， “ “所有女人都喜欢帅哥所有女人都喜欢帅哥”表示为表示为 x yH(x,y)。 2.1基本概念基本概念 5、存在量词、存在量词 为了表示为了表示“有些男人结婚生崽有些男人结婚生崽”中中“有些有些”， 引入符号引入符号“ ”， 。 称为称为存在量词存在量词。 它是它是Exist的首字母，左旋的首字母，左旋180180度，度， 如用如用z表示表示“男人男人”，那么，那么 “ “有些男人有些男人”表

7、示为表示为“ z”， “ “有些男人结婚生崽有些男人结婚生崽”表示为表示为“ zM(z)”。2.1基本概念基本概念 6、谓词公式、谓词公式 将表示将表示全部全部的符号的符号“ ”，表示为，表示为部分部分的的“ ”称为称为量量词词， 将将单个谓词单个谓词公式如公式如W(x)，带，带量词量词的谓词如的谓词如 zM(z)， 谓词谓词W(x),M(z)中只有中只有1 1个个体变元个个体变元, , 常用来刻划对象的常用来刻划对象的。 谓词谓词L(x,y)、H(y,z)中有中有2 2个个体变元，称为个个体变元，称为2 2元元谓词。谓词。， 如喜欢，如喜欢， 类似如果有类似如果有n n个个体变个个体变元则称

8、为元则称为n n元元谓词公式。谓词公式。 个体变元的个体变元的取值取值范围称为范围称为“讨论域讨论域”， 如果如果没有交待没有交待讨论域，表示对个体变元的讨论域，表示对个体变元的取值范围取值范围，不做不做任何任何限制，泛指限制，泛指宇宙界宇宙界的万物，称为的万物，称为“全总个体全总个体域域”，常用大写，常用大写字母字母U表示。表示。 利用量词、谓词将自然语言转换为谓词公式利用量词、谓词将自然语言转换为谓词公式 例例1：(1)凡人都要呼吸凡人都要呼吸 (2)有的人用左手写字。有的人用左手写字。 解解：当个体域为：当个体域为“人类人类”时时 xB(x),其中其中B(x)表示表示x人呼吸人呼吸bre

9、ath. 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=3 当当x的

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

11、T(y)H(x,y) x y(R(x) T(y)H(x,y) (4) x y(R(x) R(y) L(x,y) x y(R(x) R(y) L(x,y)例例4任意两个不相等实数，其平方和大于积的二倍。任意两个不相等实数，其平方和大于积的二倍。 解解：个体域为：个体域为全总个体域全总个体域即不对个体变元的取值做任即不对个体变元的取值做任何限制。何限制。 F(x)表示表示x是实数，是实数， G(x,y)表示表示x y， H(x,y)表示表示xy，则原话表示为，则原话表示为 x y (F(x) F(y) G(x,y)H(x2+y2,2xy)。 若用若用f(x,y)表示表示x2+y2，g(x,y)表示

12、表示2xy，则原话表示为，则原话表示为 (F(x) F(y) G(x,y)H(f(x,y),g(x,y) 因为对于实数因为对于实数x，y，(x2-2xy+y2)=(x-y)2， 当当x y时，有时，有(x-y)20， 故故(x2-2xy+y2)0， 故故x2+y22xy， 故故H(x2+y2,2xy) 为真为真 故原话正确，故以上公式的真值为故原话正确，故以上公式的真值为1 1。 故谓词公式可出现个体变元故谓词公式可出现个体变元,平方平方,乘、倍数、函数等乘、倍数、函数等。例例5表示表示“所有人都要变老的，杨圣洪是人，所所有人都要变老的，杨圣洪是人，所以杨圣洪也会变老的以杨圣洪也会变老的”。

13、解解：个体域为全总个体域，即对个体变元的取：个体域为全总个体域，即对个体变元的取值不做任何限。值不做任何限。 H(x)表示对象表示对象x是人类，是人类， O(x)表示对象表示对象x变老，变老， c表示个体常元表示个体常元“杨圣洪杨圣洪”，则，则 H(c)表示个体常元杨圣洪是人类，表示个体常元杨圣洪是人类， O(c)表示个体常元杨圣洪要变老，原句表示表示个体常元杨圣洪要变老，原句表示 ( x(H(x)O(x) H(c)O(c)。 该公式不仅有个体变元，还有个体常元该公式不仅有个体变元，还有个体常元 例例6表示表示“所有人都要死的，苏格拉底是人，所所有人都要死的，苏格拉底是人，所以苏格拉底也会死以

14、苏格拉底也会死”。 解解：个体域为全总个体域，即对个体变元的取：个体域为全总个体域，即对个体变元的取值不做任何限制。值不做任何限制。 H(x)表示对象表示对象x是人类，是人类， O(x)表示对象表示对象x要死的，要死的， c表示个体常元表示个体常元“苏格拉底苏格拉底”，则，则 H(c)表示个体常元苏格拉底是人类，表示个体常元苏格拉底是人类， O(c)表示个体常元苏格拉底要死，原句表示表示个体常元苏格拉底要死，原句表示 ( x(H(x)O(x) H(c)O(c)。 这两个例题，语句不同，但是最后的谓词公式这两个例题，语句不同，但是最后的谓词公式相同。相同。2.2、谓词公式及解释、谓词公式及解释

15、上节上节得到一些谓词公式，得到一些谓词公式，获得一些结论，也有获得一些结论，也有存在一些存在一些疑惑疑惑？ (1)谓词公式有个体谓词公式有个体常元常元、个体、个体变元变元，还可以有，还可以有个体变元的个体变元的表达式表达式，那么谓词公式究竟，那么谓词公式究竟还有还有哪些哪些形式，究竟什么的字符串是形式，究竟什么的字符串是合法的合法的谓词公式？谓词公式？ (2)同一句话有同一句话有二个不同二个不同的公式，那么这二个公的公式，那么这二个公式式等值等值吗？吗？ (3)不同的话拥有不同的话拥有同样同样的的谓词公式谓词公式，到底这二句，到底这二句话话有何共性有何共性？ (4)同一样公式在同一样公式在不同

16、的论域不同的论域下真值不同，究竟下真值不同，究竟如何确定一个公式的真值呢？如何确定一个公式的真值呢？ 2.2、谓词公式及解释、谓词公式及解释非逻辑符号非逻辑符号:个体常元、函数符号、谓词符号个体常元、函数符号、谓词符号逻辑符号逻辑符号:个体变元、量词符号、联结词、逗号、个体变元、量词符号、联结词、逗号、括号。括号。项的定义项的定义：个体常元与变元及其函数式为项。：个体常元与变元及其函数式为项。(1)个体常元和个体变元是项。个体常元和个体变元是项。(2)若若 (x1,x2, xn)是是n元函数元函数,t1,t2,tn是是n个项，个项，则则 (t1,t2, tn)是项。是项。(3)有限次使用有限次

17、使用(2)得到的表达式是项。得到的表达式是项。原子公式原子公式： 设设R(x1,x2,xn)是是n元谓词，元谓词，t1,t2,tn是项，则是项，则R(t1,t2, tn)是原子公式。是原子公式。2.2、谓词公式及解释、谓词公式及解释项的定义项的定义：个体常元与变元及其函数式为项。：个体常元与变元及其函数式为项。原子公式原子公式： 设设R(x1,x2,xn)是是n元谓词元谓词，t1,t2,tn是项，则是项，则R(t1,t2, tn)是原子公式。是原子公式。合式谓词公式合式谓词公式： (1)原子公式是合式公式；原子公式是合式公式； (2)若若A是合式公式，则是合式公式，则( A)也是合式公式；也是

18、合式公式； (3)若若A,B合式，则合式，则A B, A B, AB , AB 合式合式 (4)若若A合式，则合式，则 xA、 xA合式合式 (5)有限次使用有限次使用(2)(4)得到的式子是合式。得到的式子是合式。2.2、谓词公式及解释、谓词公式及解释 (F(x) F(y) G(x,y)H(f(x,y),g(x,y)、 x y(R(x) T(y)H(x,y)、 x y(R(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)

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

20、次出现：指导变元的每次出现(称约束变元称约束变元)。变元的自由出现变元的自由出现：不是约束出现的变元：不是约束出现的变元(称自由变元称自由变元) 。例题例题 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、谓词公式及解释、谓词公式及解释-个体变元的身份个体变元的身份量词指导变元量词指导变元： xA和和 xA中的中的x量词辖域量词辖域： x

21、A和和 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)是量词是量词 的辖域，其中的辖域，其中x是约束出现，是约束出现，y是是自由出现。自由出现。 量词量词 的指导变元的指导变元y, H(x) L(x,y,z)是量词是量词 的辖域，其中的辖域，其中x是自

22、由是自由2次，次，y是是约束出现。整个公式中是约束约束出现。整个公式中是约束1自由自由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次自由出现。次自由出现。 尽管尽

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

24、管：尽管x在公式在公式 x(F(x)G(y)出现，又在出现，又在 y(H(x) L(x,y,z)出现，但两个出现，但两个x不是一回事，不是一回事， 只是恰巧二个名字相同而矣，只是恰巧二个名字相同而矣， 为避免这种为避免这种“误会误会”出现要对出现要对“约束变元约束变元”改改名。名。 将量词将量词 x的指导变元的指导变元x，x的每次约束出现换成的每次约束出现换成公式中未出现的公式中未出现的r。 将量词将量词 y指导变元指导变元y、约束变元、约束变元y的每次出现换的每次出现换成公式中未出现的成公式中未出现的s，则原式为，则原式为 r(F(r)G(y)s(H(x) L(x,s,z)， 所有约束变元与

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

26、份 例题例题 x(P(x)xQ(x,z)yR(x,y) Q(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、谓词公式及解释、谓词公式及解释-个体变元的身份个体

27、变元的身份 闭公式闭公式：不含自由变元的谓词公式不含自由变元的谓词公式 。 x(F(x,y)G(x,z)因y,z是自由变元，故不是。 r(F(r)G(y)s(H(x) L(x,s,z) 因为y,x,z自由故不是 x r(P(x,r) Q(r,z)sP(s,y) 因z与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自由故不是以下公式均没有自由变元，均为闭公式： x y(R(x) T(y)H(x,y)、 x y(R(x) T(y)H(x,y)、x y(R(x) T(y)H(x,y)、 x y

28、(R(x) T(y) H(x,y)、x y(R(x) R(y) L(x,y)、 x y(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.22.2、谓词公式及解释、谓词公式及解释- -谓词公式的真值谓词公式的真值 前面我们学习前面我们学习“合式公式合式公式”时，说过不再拘泥于某个时，说过不再拘泥于某个具体的自然语句，从形式上研究合式公式的性质。具体的自然语句，从形式上研究合式公式的性质。 但谓词公式是逻辑公式，它总得有一个真假呀？但谓词公式是逻辑公式，它总得有一个真假呀？ 如何确定其真假呢？如何确定其真假呢？ 神

29、马不能总是浮云？神马不能总是浮云？ 总得落地。总得落地。 确定真值的方法：确定真值的方法： (1)(1)确定个体域，即个体的取值范围，确定个体域，即个体的取值范围，哪个范围哪个范围？ (2)(2)将个体常元指定为个体域的具体值。将个体常元指定为个体域的具体值。哪个对象哪个对象？ (3)(3)函数常元表示指定个体域中个体变元的项。函数常元表示指定个体域中个体变元的项。 (4)(4)用指定个体域中的对象来解释各个原子公式。用指定个体域中的对象来解释各个原子公式。 (5)(5)用原子公式的解释来描述整个公式的含义。用原子公式的解释来描述整个公式的含义。原义？原义？ 根据个体域中知识，判断整个公式的含

30、义是否正确，根据个体域中知识，判断整个公式的含义是否正确，若对则公式的真值为若对则公式的真值为1 1，否则为，否则为0 02.2、谓词公式的解释、谓词公式的解释-谓词公式的真值谓词公式的真值例题例题： x(F(x)G(x) 其中其中x的的取值范围取值范围是什么？是什么？ F(x)的的含义含义是什么？是什么？G(x)的的含义含义是什么？是什么？ 将这些问题确定后，表达式将这些问题确定后，表达式 x(F(x)G(x)的真值就确的真值就确定了，这就是公式的定了，这就是公式的解释解释。 dom(x)=D1=全总个体域全总个体域 F(x)表示表示x是人，是人，G(x)表示表示x是是黄种黄种人。人。 x(

31、F(x)G(x)：所有的人都是：所有的人都是黄种黄种人，人，值为值为F. dom(x)=D2=实数集实数集R F(x)表示表示x是自然数，是自然数，G(x)表示表示x是是整数整数。 x(F(x)G(x)：所有的自然数都是：所有的自然数都是整数整数，值为值为T.例例： x y (F(x) F(y) G(x,y)H(f(x,y),g(x,y) f(x,y),g(x,y)是函数变元，一元谓词公式是函数变元，一元谓词公式F(x),二二元谓词元谓词G与与H。 x与与y的的个体域个体域：全总个体域全总个体域。 F(x):x是是实数实数 G(x,y):x y H(x,y):xy f(x,y)=x2+y2 g

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

33、的值域、确定函数确定函数、谓谓词公式词公式的含义。的含义。例例4：个体变元的值域：个体变元的值域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,真假

34、难定真假难定,不是命题不是命题. 个体常元的值个体常元的值、个体变元个体变元的值域、的值域、确定函数确定函数、谓词公式谓词公式的含义。的含义。例例：个体变元的值域：个体变元的值域D=N, 常元的常元的a=0,函数函数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)

35、 确定谓词后确定谓词后: 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则则例例：个体变元的值域：个体变元的值域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)确定函数后确定函数后: x

36、F(x*0,x)F(x,y)确定谓词后确定谓词后: x(0=x) (x=y) 条件式的前式为假条件式的前式为假,无论后件为何无论后件为何,均为真均为真 因为因为全称量词全称量词 x是指个体域中是指个体域中所有对象所有对象具有某具有某性质、或具有某相互关系性质、或具有某相互关系。 存在量词存在量词 x是指个体域中部分是指个体域中部分对象具有对象具有某性质、某性质、或具有某相互关系或具有某相互关系 故故当个体域当个体域dom(X)=a1,a2,an有限有限,即即n有限有限, xA(x)即为即为A(a1) A(a2) A(an)。 xA(x)即即为为A(a1) A(a2) A(an)。 利用这两个展

37、开式，在解释公式的含义时，可利用这两个展开式，在解释公式的含义时，可能会带来某种便利能会带来某种便利！ 例题：例题：个体域个体域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)，代入代入谓词的值谓词的值得得(0

38、 1) (1 1)，即为，即为0。 例题：例题：个体域个体域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)，代入代入谓词谓词的值的值(1 1) (0 1)，即为，即为1

39、。 例题：例题：个体域个体域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， 求下列谓词公式的值求下列谓词公式的值:(3) x yL(x,y)解：解：展开展开 y y得得 x(L(x,2) L(x,3)，展开展开 x x得得(L(2,2) L(2,3) (L(3,2) L(3,3)，代入代入谓词的值谓词的值得得(1 0) (0 1)，即为，即为1。 例题：例题：个体域个体域D=2,3，常元常元a=2，f(2)=3，f(3)=

40、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) x yL(x,y)代入代入谓词的值谓词的值得得(1 0) (0 1)，即为，即为1。(4) y x L(x,y)展开展开 x x得得： y(L(2,y) L(3,y)，展展 y y得得：(L(2,2) L(3,2) ( L(2,3) L(3,3)，代入代入谓词值谓词值得得(1 0) (0 1)，即为，即为0。说明说明： x与与 y次序次序很重要！很重要！ 2.2 谓词公式的类型谓词公

41、式的类型 正如命题公式有永真正如命题公式有永真/永假永假/可满足一样，谓词公式也可满足一样，谓词公式也有这有这3种类型。种类型。 永真式永真式(逻辑有效式逻辑有效式):在任何解释下均为真。在任何解释下均为真。 永假式永假式(矛盾式矛盾式):在任何解释下均为假。在任何解释下均为假。 可满足式可满足式:至少存在一种至少存在一种解释下为真。解释下为真。说明说明： (1)命题逻辑命题逻辑,使用真值表可以判断一个公式的类型。使用真值表可以判断一个公式的类型。 (2)在一阶逻辑即谓词逻辑中，不存在一个算法，在有在一阶逻辑即谓词逻辑中，不存在一个算法，在有限步内判断任意一个公式的类型。限步内判断任意一个公式

42、的类型。 (3)不可判定的！不可判定的！ (4)“任何解释任何解释”如何穷尽？不可能，因此只能根据如何穷尽？不可能，因此只能根据某些某些原则如原则如“代换实例代换实例”，即，即“类比类比命题逻辑原则命题逻辑原则”。谓词公式的类型谓词公式的类型永真式永真式(逻辑有效式逻辑有效式):在任何解释下均为真。在任何解释下均为真。永假式永假式(矛盾式矛盾式):在任何解释下均为假。在任何解释下均为假。可满足式可满足式:至少存在一种至少存在一种解释下为真。解释下为真。代换实例代换实例： 设设A0是含命题变元是含命题变元p1,p2,.,pn的命题公式，的命题公式，A1,A2,.,An是是n个谓词公式个谓词公式(

43、其中个体常元其中个体常元/变元变元/函函数数/谓词公式都未确定含义谓词公式都未确定含义)，将，将A0中中pi的每次出的每次出现都换成现都换成Ai，所得公式，所得公式A称为称为A0的代换实例。的代换实例。A(x)A(x), 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的每次

44、出现都换成的每次出现都换成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 ( q p)p pq1，即为重言式，即为重言式, , 故其代换实例故其代换实例F(x,y)(G(x,y)F(x,y)是永真式。是永

45、真式。 称称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)( x yG(x,y)

46、 xF(x)，是，是 p(q p) 的代换实例，的代换实例， 而而p(q p) p ( q p) 1 故故永真式永真式(3) ( xF(x) yG(y) yG(y) 是是 (pq) q的的代换实例代换实例， 而而 (pq) q pq q0 永假，永假，故为永假故为永假2.3谓词公式等值演算谓词公式等值演算：定义定义1 设设A、B是两个是两个合法的谓词合法的谓词公式公式,如果在任何解释下如果在任何解释下两个公式的两个公式的真值真值都相等，则称都相等，则称A与与B等值等值记为记为AB。 因因AB时在任何解释下，公式时在任何解释下，公式A与公式与公式B的真值都相的真值都相同，故同，故AB为永真式，故

47、有定义为永真式，故有定义2。定义定义2 设设A、B是两个合法谓词公式，如果在任何解释下，是两个合法谓词公式，如果在任何解释下，AB为永真式，则为永真式，则A与与B等值，记为等值，记为AB。 等值等值问题，转换为问题，转换为永真永真问题，问题， 通过通过代换实例代换实例原则找原则找原型原型 并不是所有的谓词公式有对应的原型，并不是所有的谓词公式有对应的原型， 因此有些结论是无法证明，只能当作显然成立的公理。因此有些结论是无法证明，只能当作显然成立的公理。谓词逻辑推理的公理：谓词逻辑推理的公理：1、个体域为个体域为有限集有限集D=a1,a2,.,an,则有则有 xA(x) A(a1) A(a2)

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

49、有这个特性所有的没有这个特性如：如： 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) x y(F(x) M(x)H(x,y) x x (F(x) M(x)H(x,y)1、个体域为个体域为有限集有限集D=a1,a2,.,an,则有则有 xA(x) A(a1) A(a2) A(an) xA(x) A(a1) A(a2) A(an) 无法证明，只能理解！无法证明，只能理解！2.量词的德摩律量词的德摩律 xA(x)x A(x) x A(x)x A(x) 3、量词分配律量词分配律 x(A(x) B(x)xA(x)xB(x) x(

50、A(x) B(x)xA(x) xB(x) 无法证明，只能理解！无法证明，只能理解！1、个体域为个体域为有限集有限集D=a1,a2,.,an,则有则有 xA(x) A(a1) A(a2) A(an) xA(x) A(a1) A(a2) A(an)2.量词的德摩律量词的德摩律 xA(x)x A(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)

51、/ xA(x) B (2) / x(A(x) B)/ xA(x) B1、 xA(x) A(a1) A(a2) A(an) 个体域为个体域为有限有限 xA(x) A(a1) A(a2) A(an)2.量词的德摩律量词的德摩律 xA(x)x A(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、量词作用域的收缩与扩张律量词作用域的收缩与扩张律 (1) / x(A(x) B)/ xA(x) B A(x)含含自由自由x (2) / x(A(x) B)/ xA(x) B B不含有自由不含有自由x5 、约束

52、变元改名规则约束变元改名规则将将A中某量词辖域中变元的中某量词辖域中变元的每次约束每次约束出现，全部换成公出现，全部换成公式中式中未出现未出现的字母，所得到的公式记为的字母，所得到的公式记为B，则，则AB 6 、置换规则：公式局部等值变换后置换规则：公式局部等值变换后,仍与原公式等值。仍与原公式等值。例题、例题、 x(A(x)B)xA(x)B x(A(x)B)x( A(x) B)pqpq的代换实例x A(x) B量词作用域的收缩与扩张律xA(x) B德摩律xA(x)B pqpq的代换实例例题例题、 x(B A(x)BxA(x) x(BA(x)x( B A(x)pqpq的代换实例BxA(x)量词

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

54、x)德摩律德摩律x(M(x)F(x) pqp q的代换实例的代换实例例题例题、 x(M(x)F(x)x(M(x)F(x)x(M(x)F(x)x( M(x) F(x) pqp q的的代换实例代换实例x ( M(x) F(x) 德摩律德摩律x (M(x)F(x) 德摩律德摩律x (M(x)F(x) pp的的代换实例代换实例例题例题、 x y(F(x) G(y)H(x,y) x y(F(x) G(y)H(x,y) x y(F(x) G(y)H(x,y)x y (F(x) G(y)H(x,y) 德摩律德摩律x y ( (F(x) G(y) H(x,y) pqp q x y( (F(x) G(y)H(x

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

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

57、前件中是约束变元，在后件是自由变元, y在前件中是自由变元，在后件是约束变元，在前件中是自由变元，在后件是约束变元， 约束变元约束变元改名：改名： tF(t,y,z)sG(x,s,z)对对自由变元自由变元改名：改名： xF(x,s,z)yG(t,y,z) x(F(x,y)yG(x,y,z)解：解：y在前件是自由，在后件是约束，有歧义！在前件是自由，在后件是约束，有歧义！ x(F(x,y)sG(x,s,z)2.4 谓词公式范式谓词公式范式 定义定义：一个谓词公式，如果量词均在全式的开：一个谓词公式，如果量词均在全式的开头，它们的作用域延伸到整个公式的末尾，则该头，它们的作用域延伸到整个公式的末尾

58、，则该公式称为公式称为前束范式前束范式，形如形如Q1x1Q2x2QkxkB，其，其中中Qi为为 或或 ，B中不含有中不含有数量词数量词。 如如 x y(F(x) G(y)H(x,y) 是前束范式是前束范式 x(F(x)y(G(y) H(x,y)不是！因不是！因B有量词有量词 定理定理1：任何逻辑公式可转换为前束范式。：任何逻辑公式可转换为前束范式。 说明说明：利用代换实例，将：利用代换实例，将、转换为转换为 2.4 谓词公式范式谓词公式范式定理定理1：任何逻辑公式可转换为前束范式。：任何逻辑公式可转换为前束范式。 步骤步骤： 2.4 谓词公式范式谓词公式范式例例 公式公式 xP(x)xQ(x)

59、转换为前束范式转换为前束范式 后方约束变元改名条件式的代换实例否定到底量词辖域的扩张条件式的代换实例德摩律量词的分配律2.4 谓词公式范式谓词公式范式例例 2.5 谓词推理谓词推理 引言引言：推理推理是永恒的是永恒的话题话题，谓词逻辑同样要进，谓词逻辑同样要进行推理，只是比命题逻辑行推理，只是比命题逻辑更加复杂更加复杂。 谓词逻辑中谓词逻辑中不能不能使用使用真值表真值表。 谓词逻辑的谓词逻辑的等值式等值式，其判断也只能根据，其判断也只能根据代换实代换实例规则例规则，沿用沿用命题逻辑中的等值式。命题逻辑中的等值式。 因此只能使用因此只能使用自然推理自然推理的方法，即的方法，即直接直接从从前提前提出发，利用出发，利用基本原则基本原则，不断，不断推出结论推出结论 谓词逻辑谓词逻辑自有自有的等值式并不多，即使有的等值式并不多，即使有 也是也是只能只能理解而理解而无法无法证明的规律，如证明的规律，如德摩律德摩律、分配律等。分配律等。2.5 谓词推理谓词推理 定义定义1 若在若在各种解释各种解释下下A1 A2 A3 AnB只只能为真能为真,则称为前提则称为前提A1,A2,An可推出结论可推出结论B。 定义定义2 当当A1 A2 A3 An为真时为真时B为真，即为真，即 当当A1,A2,A3,An为真时为真时B为真。为真。 方法方法： 当前提条件当前提条件A1,A2,An为真时，为真时，利用利