第四章命题逻辑

因而命题逻辑具有局限性，甚至无法判断一些简单而常见的推理。如：命题演算的基本单位是命题不再对简单命题进行分解不考虑命题之间的内在联系和数量关系命题逻辑p:凡人必死。q:苏格拉底是人。r:所以苏格拉底必死。显然是一个有效推理，但按命题逻辑中的推理：pq∴rr不是一个重言式，是一个非有效的推理。问题出在命题中所包含的成分，若改成：所有A是BC是A所以C是B从而符合了有效推理。这在命题逻辑中是无法描述的。鉴于此，德国的数学家弗雷格引入了谓词，量词，个体词，对命题逻辑进行了扩充。研究它们的形式结构及逻辑关系。总结出正确的推理形式和规则，即一阶逻辑，又称谓词逻辑。4.1一阶逻辑的符号化个体词谓词独立存在的客体刻画个体词的性质或个体词之间关系的词。简单命题分解成如：李明是个大学生。个体词谓词张明与李亮是兄弟。个体词是指所研究对象中可以独立存在的具体的或抽象的客体。例如，小王，桌子，中国，√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}，…；也可以是无穷集合，例如，自然数集合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元谓词P(x1,x2,…,xn)可以看成以个体域为定义域，以{0,1}为值域的n元函数或关系。它不是命题。要想使它成为命题，必须用谓词常项取代P，用个体常项a1,a2,…,an取代x1,x2,…,xn，得P(a1,a2,…,an)是命题。更一般的用P(x1,x2,…,xn)表示含n(n≥1)个命题变项的n元谓词。n=1时，P(x1)表示x1具有性质P；n≥2时，P(x1,x2,…,xn)表示x1,x2,…,xn具有关系P。0元谓词不带个体变项的谓词。例如，F(a)，G(a,b)，P(a1,a2,…,an)等都是0元谓词。当F，G，P为谓词常项时，0元谓词为命题。命题逻辑中的命题均可以表示成0元谓词，因而可以将命题看成特殊的谓词。判断：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)中命题为假。有了个体词和谓词之后，有些命题还是不能准确的符号化，原因是还缺少表示个体常项或变项之间数量关系的词。称表示个体常项或变项之间数量关系的词为量词量词可分两种:(1)全称量词表示个体域里所有个体(2)存在量词日常生活和数学中所用的“一切的”，“所有的”，“每一个”，“任意的”，“凡”，“都”等词可统称为全称量词，将它们符号化为“”。并用x，y等表示个体域里的所有个体。表示个体域里有的个体日常生活和数学中所用的“存在”，“有一个”，“有的”，“至少有一个”等词统称为存在量词，将它们都符号化为“”。并用x，y等表示个体域里有的个体例4.2在个体域分别限制为(a)和(b)条件时，将下面两个命题符号化:(1)凡人都呼吸。(2)有的人用左手写字。其中:(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)在不同的个体域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(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):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):x比y跑得快，L(x,y):x与y跑得一样快。这4个命题分别符号化为4）┐xy(F(x)∧F(y)∧L(x,y))1）xy(F(x)∧G(y)→H(x,y))2）x(F(x)∧y(G(y)→H(x,y))3）┐xy(F(x)∧G(y)→H(x,y))注意：1.多个量词出现时，顺序不能随意调换。2.有些命题的符号化形式可不止一种。例如，考虑个体域为实数集，H(x,y):x+y=10,则xyH(x,y)与yxH(x,y)不同例如，在例4.5中，3)还可以符号化为xy(F(x)∧G(y)∧┐H(x,y))4)还可以符号化为xy(F(x)∧F(y)→┐L(x,y))一、讨论下列各式的真值：1）取个体域为整数集Z，xy（x·y=1）A.0B.1C.不定2）取个体域为整数集Z，xyz（x-y=z）A.0B.1C.不定3）取个体域为整数集Z，x-y=-y+xA.0B.1C.不定4）取个体域为整数集Z，xy(x·y)=yA.0B.1C.不定5）取个体域为整数集Z，x(x·y=x)A.0B.1C.不定6）取个体域为整数集Z，xy(x+y=2y)A.0B.1C.不定ABBACA二、将下列命题符号化。(1)每个人恰有一个最好的朋友。(2)如果某人是女性而且有子女，那么此人一定是某人的母亲。(3)有位妇女已搭乘过世界上每一条航线上的航班。(4)定义是：对每个实数0，使得对每一个x，只要0|x-a|，就有|f(x)-L|。Lxfax)(lim4）x(0|x-a||f(x)-L|）3）令：P(w,f):w搭乘过f。Q(f,a):f是a上的航班。则命题可表示为waf(P(w,f)Q(f,a))其中w,a,f代表世界上所有的妇女，所有的空中航班和所有的航线。2）令：M(x):x是女性。P(x):x有子女。M(x,y):x是y的母亲。则命题可表示为x(M(x)P(x))yM(x,y)1）令：B(x,y):x与y是最好的朋友。则命题可表示为xyz(B(x,y)((zy)B(x,y)))三、把下列语句解释为文字。1、x(C(x)y(C(y)F(x,y)))，其中C(x)表示x有台计算机，F(x,y)表示x和y是朋友；论域为学校全体学生。2、xyz((F(x,y)F(x,z)(yz))F(y,z))，其中F(x,y)表示x和y是朋友；论域为学校全体学生。4.2一阶逻辑公式及解释同命题逻辑一样，给出谓词公式定义：定义4.1一阶语言L的字母表定义如下:(1)个体常项:a,b,c,…,ai,bi,，ci，…，i≥1(2)个体变项:x,y,z,…，xi,yi,zi，…，i≥1(3)函数符号:f,g,h,…,fi,gi,hi，…，i≥1(4)谓词符号:F,G,H,…,Fi,Gi,Hi，…，i≥1(5)量词符号:，(6)联结词符号:┐,∧,∨,→,(7)括号与逗号:(,),，4.2一阶逻辑公式及解释定义4.2L的项的定义如下:(1)个体常项和个体变项是项。(2)若f(x1,x2,…,xn)是任意的n元函数，t1,t2,…,tn是任意的n个项，则f(t1,t2,…,tn)是项。(3)所有的项都是有限次使用(1)，(2)得到的。如：a,b,x,y;f(x,y)=x+y,g(x,y)=x-y,h(x,y)=x*y;g(h(x,y),f(a,b))=x*y-(a+b)定义4.3设R(x1,x2,…,xn)是L的任意n元谓词,t1,t2,…,tn是F的任意的n个项，则称R(t1,t2,…,tn)是L的原子公式。例4.5中的1元谓词F(x)，G(x)，2元谓词H(x,y)，L(x,y)等都是原子公式。定义4.4L的合式公式定义如下:(1)原子公式是合式公式。(2)若A是合式公式，则(┐A)也是合式公式。(3)若A，B是合式公式，则(A∧B)，(A∨B)，(A→B)，(AB)也是合式公式。(4)若A是合式公式，则xA，xA也是合式公式(5)只有有限次的应用(1)～(4)构成的符号串才是合式公式。L的合式公式也称为谓词公式，简称公式在定义中出现的字母A，B是代表任意公式的元语言符号。为方便起见，公式(┐A)，(A∧B)，…中的最外层括号可以省去。定义4.5在公式xA和xA中，称x为指导变元，A为相应量词的辖域。在x和x的辖域中，x的所有出现都称为约束出现。A中不是约束出现的其他变项均称为是自由出现的。例4.6指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项:1)x(F(x,y)→G(x,z))2)x(F(x)→G(y))→y(H(x)∧L(x,y,z))解:(1)x是指导变元。