第四章一阶逻辑命题符号化.

第四章一阶逻辑基本概念第1节一阶逻辑的符号化第2节一阶逻辑公式及解释在命题逻辑中，命题是最基本的单位，对简单命题不再进行分解，并且不考虑命题之间的内在联系和数量关系.因而命题逻辑具有局限性，甚至无法判断一些简单而常见的推理.考虑下面的推理:凡偶数都能被2整除；6是偶数.所以，6能被2整除.这个推理是我们公认的数学推理中的真命题，但是在命题逻辑中却无法判断它的正确性.因为在命题逻辑中只能将推理中出现的三个简单命题依次符号化为p，q，r，将推理的形式结构符号化为(p∧q)→r由于上式不是重言式，所以不能由它判断推理的正确性.为了克服命题逻辑的局限性，就应该将简单命题再细分，分析出个体词，谓词和量词，以期达到表达出个体与总体的内在联系和数量关系，这就是一阶逻辑所研究的内容.一阶逻辑也称一阶谓词逻辑或谓词逻辑.一、个体词二、谓词第1节一阶逻辑的符号化三、量词四、一阶逻辑命题符号化个体词、谓词和量词是一阶逻辑命题符号化的三个基本要素.下面讨论这三个要素.一、个体词个体词是指所研究对象中可以独立存在的具体的或抽象的客体.（1）将表示具体或特定的客体的个体词称作个体常项，一般用小写英文字母a，b，c…表示；（2）而将表示抽象或泛指的个体词称为个体变项，常用x，y，z,…表示.（3）称个体变项的取值范围为个体域(或称论域).个体域可以是有穷集合，也可以是无穷集合.有一个特殊的个体域，它是由宇宙间一切事物组成的，称它为全总个体域.本书在论述或推理中如没有指明所采用的个体域，都是使用全总个体域.同个体词一样，谓词也有常项和变项之分.（1）表示具体性质或关系的谓词称为谓词常项;谓词是用来刻画个体词性质及个体词之间相互关系的词.(见P55例题）1定义2分类（2）表示抽象的、泛指的性质或关系的谓词称为谓词变项.二、谓词无论是谓词常项或变项都用大写英文字母F,G,H,…表示，可根据上下文区分.一般的：用F(a)表示个体常项a具有性质F(F是谓词常项或谓词变项);用F(x)表示个体变项x具有性质F;用F(a，b)表示个体常项a，b具有关系F;用F(x,y)表示个体变项x，y具有关系F.更一般的,用P(x1,x2,…,xn)表示含n(n≥1)个命题变项的n元谓词.1）n=1时，P(x1)表示x1具有性质P；2）n≥2时，P(x1,x2,…,xn)表示x1,x2,…,xn具有关系P.实质上，n元谓词P(x1,x2,…,xn)可以看成以个体域为定义域，以{0,1}为值域的n元函数或关系.它不是命题.要想使它成为命题，必须用谓词常项取代P，用个体常项a1,a2,…,an取代x1,x2,…,xn，得P(a1,a2,…,an)是命题.3）有时候将不带个体变项的谓词称为0元谓词，例如,F(a),G(a,b),P(a1,a2,…,an)等都是0元谓词.当F,G,P为谓词常项时，0元谓词为命题.例4.1将下列命题在一阶逻辑中用0元谓词符号化，并讨论它们的真值:(1)只有2是素数，4才是素数。(2)如果5大于4，则4大于6.这样一来，命题逻辑中的命题均可以表示成0元谓词，因而可以将命题看成特殊的谓词.解:(1)设一元谓词F(x):x是素数，a:2，b:4。(1)中命题符号化为0元谓词的蕴涵式:F(b)→F(a)(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)为假，所以(2)中命题为假.由于此蕴涵前件为假，所以(1)中命题为真.G(b,a)→G(a,c)三、量词有了个体词和谓词之后,有些命题还是不能准确的符号化，原因是还缺少表示个体常项或变项之间数量关系的词.称表示个体常项或变项之间数量关系的词为量词.量词可分两种:全称量词存在量词1全称量词日常生活和数学中所用的“一切的”，“所有的”,“每一个”，“任意的”，“凡”，“都”等词可统称为全称量词，将它们符号化为“”.,xy(),()xFxyGy用等表示个体域里的所有个体;用等分别表示个体域里所有个体都有性质F和都有性质G.2存在量词日常生活和数学中所用的“存在”，“有一个”，“有的”，“至少有一个”等词统称为存在量词，将它们都符号化为“”.,xy(),()xFxyGy用等表示个体域里有的个体;用等分别表示个体域里存在个体具有性质F和存在个体具有性质G等.例4.2在个体域分别限制为(a)和(b)条件时，将下面两个命题符号化:(1)凡人都呼吸.(2)有的人用左手写字.其中:(a)个体域D1为人类集合；(b)个体域D2为全总个体域.四、一阶逻辑命题符号化解:(a)令F(x):x呼吸.G(x):x用左手写字.(2)在宇宙间存在着用左手写字的人.(b)D2中除了有人外，还有万物，因而在符号化时，必须考虑将人分离出来.(1)对于宇宙间一切事物而言，如果事物是人，则他要呼吸.令M(x):是人.在D2中，(1),(2)可以分别重述如下:(1)xF(x)(4.1)(2)xG(x)(4.2)于是(1)，(2)的符号化形式分别为其中F(x)与G(x)的含义同(a)中.(M(x)→F(x))(4.3)x(M(x)∧F(x))(4.4)x由例4.2可知，命题(1)，(2)在不同的个体域D1和D2中符号化的形式不一样.主要区别在于，在使用个体域D2时，要将人与其他事物区分开来.为此引进了谓词M(x)，像这样的谓词称为特性谓词.注在命题符号化时一定要正确使用特性谓词.(1)对于任意的x，均有x2-3x+2=(x-1)(x-2).(2)存在x，使得x+5=3.例4.3在个体域限制为(a)和(b)条件时，将下列命题符号化:其中:(a)个体域D1=N(N为自然数集合)(b)个体域D2=R(R为实数集合)解:(a)令F(x):x2-3x+2=(x-1)(x-2)，G(x):x+5=3.命题(1)的符号化形式为命题(2)的符号化形式为(b)在D2内，(1)和(2)的符号化形式还是(4.7)式和(4.8)式，(1)依然是真命题，而此时(2)也是真命题.xG(x)(4.8)xF(x)(4.7)显然(1)为真命题；而(2)为假命题，因为N不含负数.从例4.2和例4.3可以看出以下两点:1）在不同个体域内，同一个命题的符号化形式可能不同，也可能相同.2）同一个命题，在不同个体域中的真值也可能不同.例4.4将下列命题符号化，并讨论真值.(1)所有的人都长着黑头发.(2)有的人登上过月球.(3)没有人登上过木星.(4)在美国留学的学生未必都是亚洲人.解:由于本题没有提出个体域，因而应该采用全总个体域.(1)令F(x):x长着黑头发.设a为某个金发姑娘，则M(a)为真，而F(a)为假，所以M(a)→F(a)为假，故(4.9)所表示的命题为假.x(M(x)→F(x))(4.9)令M(x):x为人.命题(1)符号化为(2)令G(x):x登上过月球.设a是1969年登上月球完成阿波罗计划的一个美国人，x(M(x)∧G(x))(4.10)命题(2)的符号化形式为所以(4.10)表示的命题为真.则M(a)∧G(a)为真.(3)令H(x):x登上过木星.命题(3)符号化形式为到目前为止，对于任何一个人(含已经去世的人)都还没有登上过木星，┐x(M(x)∧H(x))(4.11)因而x(M(x)∧H(x))为假，所以对任何人a，M(a)∧H(a)均为假，所以(4.11)表示的命题为真.(4)令F(x):x是在美国留学的学生，G(x):x是亚洲人.┐x(F(x)→G(x))(4.12)命题(4)符号化形式为这个命题也为真.P654、解：（1）F(x):x是有理数；G(x)：x能表示成分数(()())xFxGx（2）F(x):x是在北京卖菜的人；G(x)：x是外地人(()())xFxGx(()())xFxGx或(()())xFxGx或（3）F(x):x是乌鸦；G(x)：x是黑色的(()())xFxGx（4）F(x):x是人；G(x)：x天天锻炼身体(()())xFxGx例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.13)(4.14)(4.15)(4.16))),()()((yxHyGxFyx))),()(()((yxHyGyxFx)),()()((yxHyGxFyx)),()()((yxLyFxFyx1.一般说来，多个量词出现时，它们的顺序不能随意调换.2.有些命题的符号化形式可不止一种.注意例如：个体域为实数集合，F(x,y):xy),()1(yxyFx),()2(yxxFy对每一个数x，都存在一个y满足F(x,y)存在一个数y，对所有的x满足F(x,y)其中，F(x):x是偶数.G(x):x能被2整除.a:6.(4.21)由于引进了个体词，谓词和量词的概念，现在可以将本章开始时讨论的推理在一阶逻辑中符号化为如下形式:下一章可以证明(4.21)是永真式.(4.21))()()))()(((aGaFxGxFx作业：P655.一、一阶语言二、自由与约束第2节一阶逻辑公式及解释三、闭公式四、一阶公式的解释五、一阶公式的分类一阶语言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.1一、一阶语言定义4.2L的项的定义如下:(1)个体常项和个体变项是项.(2)若f(x1,x2,…,xn)是任意的n元函数,t1,t2,…,tn是任意的n个项，则f(t1,t2,…,tn)是项.(3)所有的项都是有限次使用(1)，(2)得到的.例4.5中的1元谓词F(x)，G(x)，2元谓词H(x,y)，L(x,y)等都是原子公式．设R(x1,x2,…,xn)是的任意n元谓词,t1,t2,…,tn是L的任意的n个项，则称R(t1,t2,…,tn)是L的原子公式.定义4.3定义4.4L的合式公式定义如下:(1)原子公式是合式公式.(2)若A是合式公式，则(┐A)也是合式公式.(3)若A，B是合式公式，则(A∧B)，(A∨B)，(A→B)，(A↔B)也是合式公式.(5)只有有限次的应用(1)～(4)构成的符号串才是合式公式.(4)若A是合式公式，则也是合式公式.,xAxA合式公式也称为谓词公式，简称公式.在定义4.4中出现的字母A,B是代表任意公式的元语言符号.为方便起见,公式(┐A),(A∧B),…中的最外层括号可以省去，使其变成┐A,A∧B，….(4.1)～(4.21)都是L中的公式.因为本书只引进一种一阶语言L，下文的讨论都是在L中，因而一般不再提及L.下面讨论一阶公式的一些性质.在公式xA和xA中，称x为指导变元，A为相应量词的辖域.在x和x的辖域中,x的所有出现都称为约束出现.A中不是约束出现的其他变项均称为是自由出现的.定义4.5二、自由与约束例4.6指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项:x是指导变元.量词的辖域A=(F(x,y)→G(x,z))，在A中，x是约束出现的.而且约束出现两次，y和z均为自由出现的，而且各自由出现一次.(1)x(F(x,y)G(x,z))(4.22)(2)x(F(x)G(y))y(H(x)L(x,y,z))(4.23)公式中含有两个量词，前件上的量词的指导变元为x，的辖域