一阶逻辑基本概念

1.一阶逻辑命题符号化2.一阶逻辑公式及其解释第四章一阶逻辑基本概念命题逻辑的局限性:在命题逻辑中，研究的基本单位是简单命题，对简单命题不再进行分解，并且不考虑命题之间的内在联系和数量关系。例如:凡偶数都能被2整除，6是偶数，所以6能被2整除。将出现的3个命题依次符号化为p,q,r，将推理的形式结构p∧qr4.1一阶逻辑命题符号化为了克服命题逻辑的局限性，将简单命题再细分，分析出个体词、谓词和量词，以期达到表达出个体与总体的内在联系和数量关系。这就是一阶逻辑所研究的内容。4.1一阶逻辑命题符号化一阶逻辑命题符号化的三个基本要素:(1)个体词(2)谓词(3)量词(1)个体词个体词：指所研究对象中可以独立存在的具体或抽象的客体。说明：个体词一般是充当主语的名词或代词举例命题：电子计算机是科学技术的工具。个体词：电子计算机。命题：他是三好学生。个体词：他。个体常项：表示具体或特定的客体的个体词，用小写字母a,b,c，…表示。个体变项：表示抽象或泛指的客体的个体词，用x,y,z,…表示。个体域(或称论域):指个体变项取值范围。可以是有穷集合，如{a,b,c},{1,2}。可以是无穷集合，如N,Z,R,…。全总个体域——宇宙间一切事物组成。说明：本教材在论述或推理中，如果没有指明所采用的个体域，都是使用的全总个体域。(2)谓词谓词：谓词是用来刻画个体词性质及个体词之间相互关系的词,常用F,G,H表示。举例例题1：是无理数。是个体常项，“是无理数”是谓词，记为F，命题符号化为F()。例题2：x是有理数。x是个体变项，“是有理数”是谓词，记为G，命题符号化为G(x)。例题3：小王与小李同岁。小王、小李都是个体常项，“与同岁”是谓词，记为H，命题符号化为H(a,b)，其中a：小王，b：小李。例题4：x与y具有关系L。x，y都是个体变项，谓词为L，命题符号化为L(x,y)。谓词常项：表示具体性质或关系的谓词。用大写字母表示。如①、②、③中谓词F、G、H。谓词变项：表示抽象的、泛指的性质或关系的谓词。用大写字母表示。如④中谓词L。例x与y具有关系L。x，y都是个体变项，谓词为L，命题符号化为L(x,y)n(n1)元谓词：P(x1,x2,…,xn)表示含n个命题变项的n元谓词。n=1时,一元谓词—表示x1具有性质P。n≥2时,多元谓词—表示x1,x2,…,xn具有关系P0元谓词：不含个体变项的谓词。如F(a)、G(a,b)、P(a1,a2,…,an)。例4.1将下列命题在一阶逻辑中用0元谓词符号化，并讨论真值。(1)只有2是素数，4才是素数。(2)如果5大于4，则4大于6.解：(1)设一元谓词F(x):x是素数,a:2,b:4。命题符号化为0元谓词的蕴涵式F(b)→F(a)由于此蕴涵前件为假，所以命题为真。(2)如果5大于4，则4大于6.解：设二元谓词G(x,y):x大于y，a:4，b:5，c:6。命题符号化为0元谓词的蕴涵式G(b,a)→G(a,c)由于G(b,a)为真，而G(a,c)为假，所以命题为假。(3)量词量词：是表示个体常项或个体变项之间数量关系的词。全称量词：符号化为“”日常生活和数学中所用的“一切的”、“所有的”、“每一个”、“任意的”、“凡”、“都”等词可统称为全称量词。x表示个体域里的所有个体，xF(x)表示个体域里所有个体都有性质F。xyG(x,y)表示个体域里的所有个体x和y有关系G。存在量词：符号化为“”日常生活和数学中所用的“存在”、“有一个”、“有的”、“至少有一个”等词统称为存在量词。yG(y)表示个体域里存在个体具有性质G等。xyG(x,y)表示个体域里存在个体x和个体y有关系G。xyG(x,y)表示个体域里所有个体x，存在y，使得x和y有关系G。xyG(x,y)表示个体域里存在个体x，使得和所有的个体y有关系G。例4.2在个体域分别限制为(a)和(b)条件时，将下面两个命题符号化:(1)凡人都呼吸。(2)有的人用左手写字。其中:(a)个体域D1为人类集合；(b)个体域D2为全总个体域。解:(a)个体域为人类集合。令F(x):x呼吸。G(x):x用左手写字。(1)在个体域中除了人外，再无别的东西，因而“凡人都呼吸”应符号化为xF(x)(2)在个体域中除了人外，再无别的东西，因而“有的人用左手写字”符号化为xG(x)(b)个体域为全总个体域。即除人外,还有万物,所以必须考虑将人先分离出来。所以引入谓词M(x):x是人。令F(x):x呼吸。G(x):x用左手写字。(1)“凡人都呼吸”应符号化为x(M(x)→F(x))(2)“有的人用左手写字”符号化为x(M(x)∧G(x))注意：1.在使用全总个体域时，要将人从其他事物中区别出来，为此引进了谓词M(x)，称为特性谓词。2.正确使用→与∧3.在不同个体域内，同一个命题的符号化形式可能不同，也可能相同。当F是谓词常项时，xF(x)是一个命题，如果把个体域中的任何一个个体a带入，F(a)都是真，则xF(x)为真；否则xF(x)为假。xF(x)也是一个命题，如果个体域中存在一个个体a，使得F(a)为真，则xF(x)为真；否则xF(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)在D1内令F(x):x2-3x+2=(x-1)(x-2)，G(x):x+5=3。命题(1)的符号化形式为xF(x)（真命题）命题(2)的符号化形式为xG(x)（假命题）解(a)在D2内令F(x):x2-3x+2=(x-1)(x-2)，G(x):x+5=3。命题(1)的符号化形式为xF(x)（真命题）命题(2)的符号化形式为xG(x)（真命题）例4.4将下列命题符号化，并讨论真值(1)所有人都长着黑头发。(2)有的人登上过月球。(3)没有人登上过木星。(4)在美国留学的学生未必都是亚洲人。解：由于没有指明个体域，因为采用全总个体域，M(x):x是人(1)所有人都长着黑头发。令F(x):x长着黑头发命题(1)的符号化形式为x(M(x)F(x))命题为假(2)有的人登上过月球。令F(x):x登上过月球命题(2)的符号化形式为x(M(x)∧F(x))命题为真(3)没有人登上过木星。令F(x):x登上过木星命题(3)的符号化形式为┐x(M(x)∧F(x))真值为真(4)在美国留学的学生未必都是亚洲人。令F(x):x是在美国留学的学生G(x):x是亚洲人命题(4)的符号化形式为┐x(F(x)G(x))命题为真例4.5将下列命题符号化(1)兔子比乌龟跑得快。(2)有的兔子比所有的乌龟跑得快。(3)并不是所有的兔子都比乌龟跑得快。(4)不存在跑得同样快的两只兔子。(1)兔子比乌龟跑得快。解：令F(x):x是兔子，G(y):y是乌龟，H(x,y):x比y跑得快命题(1)的符号化形式为xy(F(x)∧G(y)H(x,y))(2)有的兔子比所有的乌龟跑得快。解：令F(x):x是兔子，G(y):y是乌龟，H(x,y):x比y跑得快命题符号化形式为x(F(x)∧y(G(y)H(x,y)))(3)并不是所有的兔子都比乌龟跑得快。解：令F(x):x是兔子，G(y):y是乌龟，H(x,y):x比y跑得快命题符号化形式为┐xy(F(x)∧G(y)H(x,y))思考：命题符号化形式为xy(F(x)∧G(y)∧┐H(x,y))可以么？(4)不存在跑得同样快的两只兔子解：令F(x):x是兔子，L(x,y):x与y跑得同样快命题符号化形式为┐zy(F(z)∧F(y)∧L(z,y))思考：命题符号化形式为xy(F(x)∧F(y)┐L(x,y))可以么？一阶逻辑命题符号化时需要注意的事项:(1)分析命题中表示性质和关系的谓词，分别符号为一元和n（n2）元谓词。(2)根据命题的实际意义选用全称量词或存在量词。(3)有些命题的符号化形式可不止一种。（例4.5之(3)）(4)一般说来，多个量词出现时，它们的顺序不能随意调换。例如，考虑个体域为实数集，H(x，y)表示x+y=10，则命题“对于任意的x，都存在y，使得x+y=10”的符号化形式为xyH(x,y)如果改变两个量词的顺序，得yxH(x,y)真命题假命题同在命题逻辑中一样,为在一阶逻辑中进行演算和推理,必须给出一阶逻辑中公式的抽象定义,以及它们的分类及解释。一阶语言是用于一阶逻辑的形式语言,而一阶逻辑就是建立在一阶语言基础上的逻辑体系,一阶语言本身不具备任何意义,但可以根据需要被解释成具有某种含义.一阶语言的形式是多种多样的，本书给出的一阶语言是便于将自然语言中的命题符号化的一阶语言，记为F。4.2一阶逻辑命题符号化定义4.1一阶语言F的字母表定义如下:(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一阶语言F的项的定义如下:(1)个体常项和个体变项是项。(2)若(x1,x2,…,xn)是任意的n元函数，t1,t2,…,tn是任意的n个项，则(t1,t2,…,tn)是项。(3)所有的项都是有限次使用(1),(2)得到的。定义4.3设R(x1,x2,…,xn)是一阶语言F的任意n元谓词，t1,t2,…,tn是一阶语言F的任意的n个项，则称R(t1,t2,…,tn)是一阶语言F的原子公式。例如：1元谓词F(x)，G(x)，2元谓词H(x,y)，L(x,y)等都是原子公式。定义4.4一阶语言F的合式公式定义如下:(1)原子公式是合式公式。(2)若A是合式公式，则(┐A)也是合式公式。(3)若A，B是合式公式，则(A∧B)，(A∨B)，(A→B)，(AB)也是合式公式。(4)若A是合式公式,则xA,xA也是合式公式(5)只有有限次的应用(1)～(4)构成的符号串才是合式公式.一阶语言F的合式公式也称为谓词公式，简称公式。定义4.5指导变元、辖域、约束出现、自由出现在公式xA和xA中，称x为指导变元。在公式xA和xA中，A为相应量词的辖域。在x和x的辖域中，x的所有出现都称为约束出现。A中不是约束出现的其他变项均称为是自由出现的。例4.6指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项。(1)x(F(x,y)→G(x,z))x是指导变元。量词的辖域A=(F(x,y)→G(x,z))。在A中，x的两次出现均是约束出现。y和z均为自由出现。例4.6指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项。(2)x(F(x)→G(y))→y(H(x)∧L(x,y,z))解：前件上量词的指导变元为x量词的辖域A=(F(x)→G(y))，x在A中是约束出现的，y在A中是自由出现的。后件中量词的指导变元为y，量词的辖域为B=(H(x)∧L(x,y,z))，y在B中是约束出现的，x、z在B中均为自由出现的。例题1.指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项。a)x(P(x)Q(y))b)x(P(x)(y)(R(x,y))c)xy(P(x,y)Q(y,z))xP(x,y)例题1.指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项。a)x(P(x)Q(y))量词的指导变元为x的辖域是P(x)Q(y)x是约束出现的，y是自由出现的。b)x(P(x)y(R(x,y))解：量词的指导变元为x，量词的辖域