第四章命题逻辑

《第四章命题逻辑》由会员分享，可在线阅读，更多相关《第四章命题逻辑（37页珍藏版）》请在金锄头文库上搜索。

1、因而命题逻辑具有局限性，甚至无法判断一些简单而常见的推理。如：命题演算的基本单位是命题不再对简单命题进行分解不考虑命题之间的内在联系和数量关系命题逻辑p:凡人必死。q:苏格拉底是人。r:所以苏格拉底必死。显然是一个有效推理，但按命题逻辑中的推理：pqrr不是一个重言式，是一个非有效的推理。问题出在命题中所包含的成分，若改成：所有A是BC是A所以C是B从而符合了有效推理。这在命题逻辑中是无法描述的。鉴于此，德国的数学家弗雷格引入了谓词，量词，个体词，对命题逻辑进行了扩充。研究它们的形式结构及逻辑关系。总结出正确的推理形式和规则，即一阶逻辑，又称谓词逻辑。4.1一阶逻辑的符号化个体词谓词独立存在的

2、客体刻画个体词的性质或个体词之间关系的词。简单命题分解成如：李明是个大学生。个体词个体词谓词谓词张明与李亮是兄弟。个体词个体词是指所研究对象中可以独立存在的具体的或抽象的客体。例如，小王，桌子，中国，3，3等本书在论述或推理中如没有指明所采用的个体域，都是使用全总个体域。个体常项个体常项表示具体或特定的客体的个体词。一般用小写英文字母a，b，c，ai，bi，ci表示个体变项个体变项表示抽象或泛指的个体词。常用x，y，z，xi，yi，zi表示。个体域个体域(或称论域或称论域)个体变项的取值范围。个体域可以是有穷集合，例如，1，2，3，a，b，c，d，a，b，c，x，y，z，；也可以是无穷集合，例

3、如，自然数集合N=0，1，2，实数集合R=x|x是实数。全总个体域全总个体域是由宇宙间一切事物组成的。谓词谓词刻画个体词性质及个体词之间相互关系的词。(1)2是无理数。(2)x是有理数。(3)小王与小李同岁。(4)x与y具有关系L。谓词常项谓词常项表示具体性质或关系的谓词谓词变项谓词变项表示抽象的、泛指的性质或关系的谓词无论是谓词常项或变项都用大写英文字母F，G，H，表示，可根据上下文区分一般的，用F(a)表示个体常项a具有性质F，用F(x)表示个体变项x具有性质F.而用F(a，b)表示个体常项a，b具有关系F，用F(x,y)表示个体变项x，y具有关系F.(F是谓词常项或谓词变项)实质上，n元

4、谓词P(x1,x2,xn)可以看成以个体域为定义域，以0,1为值域的n元函数或关系。它不是命题。要想使它成为命题，必须用谓词常项取代P，用个体常项a1,a2,an取代x1,x2,xn，得P(a1,a2,an)是命题。更一般的用P(x1,x2,xn)表示含n(n1)个命题变项的n元谓词。n=1时，P(x1)表示x1具有性质P；n2时，P(x1,x2,xn)表示x1,x2,xn具有关系P。0元谓词不带个体变项的谓词。例如，F(a)，G(a,b)，P(a1,a2,an)等都是0元谓词元谓词。当F，G，P为谓词常项时，0元谓词为命题。命题逻辑中的命题均可以表示成0元谓词，因而可以将命题看成特殊的谓词。

5、判断：0元谓词都是命题。例例4.1将下列命题在一阶逻辑中用0元谓词符号化，并讨论它们的真值:(1)只有2是素数，4才是素数。(2)如果5大于4，则4大于6.。解：解：(1)设一元谓词F(x):x是素数，a:2，b:4。(1)中命题符号化为0元谓词的蕴涵式:F(b)F(a)由于此蕴涵前件为假，所以(1)中命题为真。（2）设二元谓词G(x，y):x大于y，a:4，b:5，c:6。G(b,a)，G(a,c)是两个0元谓词，把(2)中命题符号化为G(b,a)G(a,c)由于G(b,a)为真，而G(a,c)为假，所以(2)中命题为假。有了个体词和谓词之后，有些命题还是不能准确的符号化，原因是还缺少表示个

6、体常项或变项之间数量关系的词。称表示个体常项或变项之间数量关系的词为量词量词量词可分两种:(1)全称量词全称量词表示个体域里所有个体(2)存在量词存在量词日常生活和数学中所用的“一切的”，“所有的”，“每一个”，“任意的”，“凡”，“都”等词可统称为全称量词，将它们符号化为“ ”。并用x，y等表示个体域里的所有个体。表示个体域里有的个体日常生活和数学中所用的“存在”，“有一个”，“有的”，“至少有一个”等词统称为存在量词，将它们都符号化为“”。并用x，y等表示个体域里有的个体例例4.2在个体域分别限制为(a)和(b)条件时，将下面两个命题符号化:(1)凡人都呼吸。(2)有的人用左手写字。其中:

7、(a)个体域D1为人类集合；(b)个体域D2为全总个体域。解解：(a)令F(x):x呼吸。G(x):x用左手写字。(1)在D1中除了人外，再无别的东西，因而符号化为xF(x)(2)在D1中的有些个体(人)用左手写字，因而符号化为xG(x)(b)D2中除了有人外，还有万物，因而在(1)，(2)符号化时，必须考虑将人分离出来。令M(x):x是人。在D2中，(1)，(2)可以分别重述如下:(1)对于宇宙间一切事物而言，如果事物是人，则他要呼吸。(2)在宇宙间存在着用左手写字的人。于是(1)，(2)的符号化形式分别为（1）x(M(x)F(x)（2）x(M(x)G(x)可知，命题(1)，(2)在不同的个

8、体域D1和D2中符号化的形式不一样。主要区别在于，在使用个体域D2时，要将人与其他事物区分开来。为此引进了谓词M(x)，像这样的谓词称为特性谓词特性谓词。在命题符号化时一定要正确使用特性谓词。问问: :(a)能否将(1)符号化为x(M(x)F(x)？(b)能否将(2)符号化为x(M(x)G(x)？例例4.3在个体域限制为(a)和(b)条件时，将下列命题符号化:(1)对于任意的x，均有x2-3x+2=(x-1)(x-2).(2)存在x，使得x+5=3。其中:(a)个体域D1=N(N为自然数集合)(b)个体域D2=R(R为实数集合)解：解：(a)令F(x):x2-3x+2=(x-1)(x-2)，G

9、(x):x+5=3。命题(1)的符号化形式为xF(x)命题(2)的符号化形式为xG(x)显然(1)为真命题；而(2)为假命题，因为N不含负数。(b)在D2内，(1)和(2)的符号化形式同在D1中的形式，(1)依然是真命题，而此时(2)也是真命题。1.在不同个体域内，同一个命题的符号化形式可能不同，也可能相同。由上例我们可以看出：2.同一个命题，在不同个体域中的真值也可能不同。例例4.4将下列命题符号化，并讨论真值。(1)所有的人都长着黑头发。(2)有的人登上过月球。(3)没有人登上过木星。(4)在美国留学的学生未必都是亚洲人。解：解：由于本题没有提出个体域，因而应该采用全总个体域，令M(x):

10、x为人。1)令F(x):x长着黑头发。命题符号化为x(M(x)F(x)2)令G(x):x登上过月球。命题符号为x(M(x)G(x)3)令H(x):x登上过木星。命题符号为x(M(x)H(x)4)令F(x):x是在美国留学的学生，G(x):x是亚洲人。命题符号化为x(F(x)G(x)0111例例4.5将下列命题符号化:(1)兔子比乌龟跑得快。(2)有的兔子比所有的乌龟跑得快。(3)并不是所有的兔子都比乌龟跑得快。(4)不存在跑得同样快的两只兔子。解：解：本题没有指明个体域，因而采用全总个体域。因为本例中出现二元谓词，因而引入两个个体变项x与y.令F(x):x是兔子，G(y):y是乌龟，H(x,y

11、):x比y跑得快，L(x,y):x与y跑得一样快。这4个命题分别符号化为4）xy(F(x)F(y)L(x,y)1）xy(F(x)G(y)H(x,y)2）x(F(x)y(G(y)H(x,y)3）xy(F(x)G(y)H(x,y)注意：1.多个量词出现时，顺序不能随意调换。2.有些命题的符号化形式可不止一种。例如，考虑个体域为实数集，H(x,y):x+y=10,则xyH(x,y)与yxH(x,y)不同例如，在例4.5中，3)还可以符号化为xy(F(x)G(y)H(x,y)4)还可以符号化为xy(F(x)F(y)L(x,y)一、讨论下列各式的真值：1）取个体域为整数集Z，xy（xy=1）A.0B.1

12、C.不定2）取个体域为整数集Z，xyz（x-y=z）A.0B.1C.不定3）取个体域为整数集Z，x-y=-y+xA.0B.1C.不定4）取个体域为整数集Z，xy(xy)=yA.0B.1C.不定5）取个体域为整数集Z，x(xy=x)A.0B.1C.不定6）取个体域为整数集Z，xy(x+y=2y)A.0B.1C.不定ABBACA二、将下列命题符号化。(1)每个人恰有一个最好的朋友。(2)如果某人是女性而且有子女，那么此人一定是某人的母亲。(3)有位妇女已搭乘过世界上每一条航线上的航班。(4)定义是：对每个实数0，使得对每一个x，只要0|x-a|，就有|f(x)-L|。4） x(0 |x-a| |f

13、(x)-L|y，f(x,y)=2x+2y，g(x,y)=2xy，则表达的命题为则表达的命题为“对于任意的对于任意的x，y，若，若x与与y都是实数，都是实数，且且xy，则，则2x+2y2xy”，这是真命题。，这是真命题。如果如果H(x,y)改为改为xy，则所得命题就为假命题了。，则所得命题就为假命题了。(2) x y(F(x)F(y)G(x,y)H(f(x,y),g(x,y)在上例中，对各种变项的指定也可以称为对它们的解释。在本例中是给出公式后再对它们进行解释，也可以先给出解释，再用这个解释去解释各种公式。由以上的讨论不难看出，一个解释不外乎指定个体域、个体域中一些特定的元素、特定的函数和谓词等

14、部分。定义定义4.74.7F 的解释的解释I I由下面由下面4 4部分组成部分组成: :(a)非空个体域非空个体域DI( (b)Db)DI I中一些特定元素的集合中一些特定元素的集合( (c)Dc)DI I上特定函数集合上特定函数集合|i,n1|i,n1( (d)Dd)DI I上特定谓词的集合上特定谓词的集合|i,n1|i,n1下面对解释I做几点说明:2.被解释的公式A中的个体变项均取值于DI。1.在解释的定义中引进了几个元语言符号，如,。3.若A中含有个体常项ai，就解释成。4.为第i个n元函数。例如，i=1，n=2时，表示第一个二元函数，它出现在解释中，可能是(x,y)=x2+y2,(x,

15、y)=2xy等，一旦公式中出现f1(x,y)就解释成(x,y)，出现g1(x,y)就解释成(x,y)=2xy。5.为第i个n元谓词，如i=2，n=3时，表示第2个3元谓词，它可能以(x,y,z)的形式出现在解释中，公式A若出现F2(x,y,z)就解释成(x,y,z)。6.被解释的公式不一定全部包含解释中的四部分。例例4.84.8给定解释I I如下:(a)个体域D=NN(N N为自然数集合)(b)=0(c)(x,y)=x+y,(x,y)=xy(d)(x,y)为x=y在I下，下列哪些公式为真?哪些为假?哪些的真值还不能确定?(1)F(f(x,y),g(x,y)公式被解释成“x+y=xy”，这不是命

16、题。(2)F(f(x,a),y)F(g(x,y),z)公式被解释成“(x+0=y)(xy=z)”，这也不是命题。(3)F(g(x,y),g(y，z)公式被解释成“xyyz”，同样不是命题。(4)xF(g(x,y),z)公式被解释成“x(xy=z)”，不是命题。(5)xF(g(x,a),x)F(x,y)公式被解释成“x(x0=x)(x=y)”，由于蕴涵式的前件为假，所以被解释的公式为真。(6)xF(g(x,a),x)公式被解释成“x(x0=x)”，为假命题。(7)xy(F(f(x,a),y)F(f(y,a),x)公式被解释成“xy(x+0=y)(y+0=x)”，为真命题。(8)xyzF(f(x,

17、y),z)公式被解释成“xyz(x+y=z)”，这也为真命题。(9)xF(f(x,x),g(x,x)公式被解释成“x(x+x=xx)”，为真命题。定理定理4.1封闭的公式在任何解释下都变成命题。对闭式来说，由于每个个体变项都受量词的约束，因而具体解释中总表示一个意义确定的语句，即一个真（假）命题。不是闭式的公式在某些解释下也可能成为命题。定义定义4.8设A为一个公式，若A在任何解释下均为真，则称A为永真式永真式(或称或称逻辑有效式逻辑有效式)。若A在任何解释下均为假，则称A为矛盾式矛盾式(或或永假式永假式)。若至少存在一个解释使A为真，则称A为可满足式可满足式。很难判断任意一公式是否可满足。定

18、义定义4.9设A0是含有命题变项p1,p2,pn的命题公式，A1,A2,An是n个谓词公式，用Ai(1in)处处代替A0中的pi，所得公式A称为A0的代换实例代换实例。例如，F(x)G(x)，xF(x)yG(y)等都是pq的代换实例，而x(F(x)G(x)等不是pq的代换实例。定理定理4.2重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。例例4.94.9判断下列公式中，哪些是永真式，哪些是矛盾式?(1)x(F(x)G(x)取解释I1:个体域为实数集合R，F(x):x是整数，G(x):x是有理数。在I1下A为真，因而A不是矛盾式。取解释I2:个体域仍然为R，F(x):x是无理数，G(x)

19、:x能表示成分数。在I2下A为假，所以A不是永真式。故A是非永真式的可满足式。(2)xF(x)(xyG(x，y)xF(x)(3)(xF(x)yG(y)yG(y)易知是命题公式p(qp)的代换实例，而该命题公式是重言式，所以B是永真式。易知是命题公式(pq)q的代换实例，而该命题公式是矛盾式，所以C是矛盾式。有些公式即使是重言式或矛盾式的代换实例，也不容易一眼就能看出来，特别是有些公式，它们不是重言式和矛盾式的代换实例，判断它们是否为永真式或矛盾式更不容易，但有些简单的公式还是可以根据定义判断的。(1)(1) xF(x)xF(x) xF(xxF(x) )设I I为任意一个解释，个体域为D.若存在

20、x0D，使得F(x0)为假，则xF(x)为假，所以公式的前件为假，故公式为真。若对于任意xD，F(x)均为真，则xF(x)，xF(x)都为真，从而公式为真。所以在I I下公式为真。由I I的任意性可知，公式是永真式。例例4.10判断下列公式的类型。取解释取解释I1：个体域为自然数集合：个体域为自然数集合N，F(x,y)为为xy。在在I1下公式的前件与后件均为真，这说明公式不是下公式的前件与后件均为真，这说明公式不是矛盾式。矛盾式。再取再取I2：个体域仍然为：个体域仍然为N，F(x,y)为为x=y。在在I2下，公式的前件真而后件假，这又说明公式不下，公式的前件真而后件假，这又说明公式不是永真式，

21、是永真式，故是非永真式的可满足式。故是非永真式的可满足式。(2)(2) xx yF(xyF(x，y)y) xx yF(x,yyF(x,y) )(3)(3) x(F(x)G(x)x(F(x)G(x) yG(yyG(y)取解释取解释I1：个体域为自然数集合：个体域为自然数集合N，F（x）:x为奇数，为奇数，G(x):x为偶数。为偶数。在在I1下公式前件为假，所以公式为真，这说明不是矛下公式前件为假，所以公式为真，这说明不是矛盾式。盾式。再取再取I2：个体域仍然为：个体域仍然为N，F（x）:x为奇数，为奇数，G(x):x为素数，为素数，在在I2下，公式的前件真而后件假，所以公式为假。这下，公式的前件真而后件假，所以公式为假。这又说明公式不是永真式，又说明公式不是永真式，故公式是非永真式的可满足式。故公式是非永真式的可满足式。