离散数学-第四章-一阶逻辑基本概念

1漳州师范学院计算机科学与工程系第四章一阶逻辑基本概念2§4.1一阶逻辑命题符号化著名的苏格拉底三段论:所有人都是要死的苏格拉底是人所以:苏格拉底是要死的用P表示:所有人都是要死的用Q表示:苏格拉底是人用R表示:苏格拉底是要死的那么R是P,Q的逻辑结果,即{P,Q}┝R引入谓词和量词的概念，进一步描述命题的内部结构在命题逻辑中这个推理是不正确的原子命题符号化方法过于简单,忽略了原子命题的内部结构和它们之间的联系苏格拉底三段论是正确的,但在命题逻辑中却无法判断它的正确性a:苏格拉底M(x):x是人N(x):x是要死的M(a):苏格拉底是人N(a):苏格拉底是要死的M(a)N(a):如果苏格拉底是人则苏格拉底是要死的苏格拉底三段论相当于{M(a),M(a)N(a)}┝N(a),这个推理是正确的“所有人都是要死的”的逻辑结果“如果苏格拉底是人则苏格拉底是要死的”a表示特定的个体x泛指某个个体M和N表示x的某种属性在谓词逻辑中,苏格拉底三段论符号化为{M(a),(x)(M(x)N(x))}┝N(a)3第四章一阶逻辑基本概念一阶逻辑命题符号化一阶逻辑等值演算与推理知识点：谓词的概念与表示、命题函数与量词、谓词公式与解释、变量的约束教学要求：深刻理解和掌握谓词逻辑的基本概念教学重点：谓词逻辑中的基本概念学时:44§4.1一阶逻辑命题符号化命题逻辑的局限性在命题逻辑中，研究的基本单位是简单命题，对简单命题不再进行分解，并且不考虑命题之间的内在联系和数量关系。一阶逻辑所研究的内容为了克服命题逻辑的局限性，将简单命题再细分，分析出个体词、谓词和量词，以期达到表达出个体与总体的内在联系和数量关系。5§4.1一阶逻辑命题符号化一阶逻辑命题符号化的三个基本要素个体词谓词量词6个体词及相关概念个体词：指所研究对象中可以独立存在的具体的或抽象的客体。举例命题：电子计算机是科学技术的工具。个体词：电子计算机。命题：他是三好学生。个体词：他。7个体词及相关概念个体常项：表示具体或特定的客体的个体词，用小写字母a,b,c,…表示。个体变项：表示抽象或泛指的客体的个体词，用x,y,z,…表示。个体域（或称论域）：指个体变项的取值范围。可以是有穷集合，如{a,b,c},{1,2}。可以是无穷集合，如N，Z，R，…。全总个体域（universe）——宇宙间一切事物组成。本教材在论述或推理中，如果没有指明所采用的个体域，都是使用的全总个体域。说明8谓词及相关概念谓词（predicate）表示对象的性质或对象间关系的谓语,常用大写英文字母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)。9谓词及相关概念谓词常项：表示具体性质或关系的谓词。用大写字母表示。如(1)、(2)、(3)中谓词F、G、H。谓词变项：表示抽象的、泛指的性质或关系的谓词。用大写字母表示。如(4)中谓词L。n(n1)元谓词：P(x1,x2,…,xn)表示含n个命题变项的n元谓词。n=1时，一元谓词——表示x1具有性质P。n≥2时，多元谓词——表示x1,x2,…,xn具有关系P。0元谓词：不含个体变项的谓词。如F(a)、G(a,b)、P(a1,a2,…,an)。n元谓词是命题吗？不是，只有用谓词常项取代P，用个体常项取代x1,x2,…,xn时，才能使n元谓词变为命题。思考10例题®例4.1将下列命题在一阶逻辑中用0元谓词符号化，并讨论真值。(1)只有2是素数，4才是素数。(2)如果5大于4，则4大于6.解：(1)设一元谓词F(x):x是素数，命题符号化为0元谓词的蕴涵式F(4)→F(2)由于此蕴涵式前件为假，所以命题为真。(2)设二元谓词G(x,y):x大于y，命题符号化为0元谓词的蕴涵式G(5,4)→G(4,6)由于G(5,4)为真，而G(4,6)为假，所以命题为假。11量词及相关概念量词（quantifiers）是表示个体常项或个体变项之间数量关系的词。1.全称量词：符号化为“”日常生活和数学中所用的“一切的”、“所有的”、“每一个”、“任意的”、“凡”、“都”等词可统称为全称量词。x表示个体域里的所有个体，xF(x)表示个体域里所有个体都有性质F。2.存在量词：符号化为“”日常生活和数学中所用的“存在”、“有一个”、“有的”、“至少有一个”等词统称为存在量词。y表示个体域里有的个体，yG(y)表示个体域里存在个体具有性质G等。12一阶逻辑命题符号化例4.2在个体域分别限制为(a)和(b)条件时，将下面两个命题符号化:(1)凡人都呼吸。(2)有的人用左手写字。其中:(a)个体域D1为人类集合；(b)个体域D2为全总个体域。13解:(a)个体域为人类集合。令F(x):x呼吸。G(x):x用左手写字。(1)在个体域中除了人外，再无别的东西，因而“凡人都呼吸”应符号化为xF(x)(2)在个体域中除了人外，再无别的东西，因而“有的人用左手写字”符号化为xG(x)14(b)个体域为全总个体域。即除人外，还有万物，所以必须考虑将人先分离出来。令F(x):x呼吸。G(x):x用左手写字。M(x):x是人。(1)“凡人都呼吸”应符号化为x(M(x)→F(x))(2)“有的人用左手写字”符号化为x(M(x)∧G(x))在使用全总个体域时，要将人从其他事物中区别出来，为此引进了谓词M(x)，称为特性谓词。同一命题在不同的个体域中符号化的形式可能不同。思考：在全总个体域中，能否将(1)符号化为x(M(x)∧F(x))？能否将(2)符号化为x(M(x)→G(x))？结论15§4.1一阶逻辑命题符号化个体域为全总个体域令M(x):x是人,F(x):x呼吸,G(x):x用左手写字能否将”凡人都呼吸”符号化为(∀x)(M(x)∧F(x))？不可以。(∀x)(M(x)∧F(x))表示宇宙中的万物都是人并且会呼吸能否将”有的人用左手写字”符号化为(x)(M(x)→G(x))？不可以。(x)(M(x)→G(x))表示在宇宙万物中存在某个个体x,”如果x是人则x会用左手写字”®16例题例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)（假命题）(b)在D2内，(1)和(2)的符号化形式同(a)，皆为真命题。在不同个体域内，同一个命题的符号化形式可能不同，也可能相同。同一个命题，在不同个体域中的真值也可能不同。说明17例题例4.4将下列命题符号化，并讨论真值。（1）所有的人都长着黑头发。（2）有的人登上过月球。（3）没有人登上过木星。（4）在美国留学的学生未必都是亚洲人。分析：谓词逻辑中命题的符号化，主要考虑：(1)非空个体域的选取。若是为了确定命题的真值，一般约定在某个个体域上进行，否则，在由一切事物构成的全总个体域上考虑问题时，需要增加一个指出个体变量变化范围的特性谓词。(2)量词的使用及作用范围。(3)正确地语义。18例题解：没有提出个体域，所以认为是全总个体域。（1）所有的人长着黑头发。令F(x):x长着黑头发，M(x):x是人。命题符号化为x(M(x)→F(x))。命题真值为假。（2）有的人登上过月球。令G(x):x登上过月球，M(x):x是人。命题符号化为x(M(x)∧G(x))。命题真值为真。19§4.1一阶逻辑命题符号化（3）没有人登上过木星。令H(x):x登上过木星，M(x):x是人。命题符号化为┐x(M(x)∧H(x))。命题真值为真。（4）在美国留学的学生未必都是亚洲人。令F(x):x是在美国留学的学生，G(x):x是亚洲人。符号化┐x(F(x)→G(x))命题真值为真。20例题n元谓词的符号化例4.5将下列命题符号化（1）兔子比乌龟跑得快。（2）有的兔子比所有的乌龟跑得快。（3）并不是所有的兔子都比乌龟跑得快。（4）不存在跑得同样快的两只兔子。解：令F(x):x是兔子，G(y):y是乌龟，H(x,y):x比y跑得快，L(x,y):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))（4）┐xy(F(x)∧F(y)∧L(x,y))21一阶逻辑命题符号化时需要注意的事项分析命题中表示性质和关系的谓词，分别符号为一元和n（n2）元谓词。根据命题的实际意义选用全称量词或存在量词。一般说来，多个量词出现时，它们的顺序不能随意调换。例如，考虑个体域为实数集，H(x，y)表示x+y=10，则命题“对于任意的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))xy(F(x)∧G(y)∧┐H(x,y))22§4.2一阶逻辑公式及其解释同在命题逻辑中一样，为在一阶逻辑中进行演算和推理，必须给出一阶逻辑中公式的抽象定义，以及它们的分类及解释。一阶语言是用于一阶逻辑的形式语言，而一阶逻辑就是建立在一阶语言基础上的逻辑体系，一阶语言本身不具备任何意义，但可以根据需要被解释成具有某种含义。一阶语言的形式是多种多样的，本书给出的一阶语言是便于将自然语言中的命题符号化的一阶语言，记为ℒ。23一阶语言中的字母表定义4.1设L是一个非逻辑符号集合,由L生成的一阶语言ℒ的字母表包括下述符号:非逻辑符号(1)L中的个体常项符号:a,b,c,…,ai,bi,ci，…，i≥1(2)L中的函数符号:f,g,h,…,fi,gi,hi，…，i≥1(3)L中的谓词符号:F,G,H,…,Fi,Gi,Hi，…，i≥1逻辑符号(4)个体变项符号:x,y,z,…，xi,yi,zi，…，i≥1(5)量词符号:∀，∃(6)联结词符号:┐,∧,∨,→,↔(7)括号与逗号:(,),，®24一阶语言的项定义4.2ℒ的项的定义如下:⑴个体常项符号和个体变项符号是项⑵如果φ（x1,x2,…,xn)是一个n元函数符号,t1,t2,…,tn是n个项,则φ(t1,t2,…,tn)是项⑶只有由有限次使用⑴，⑵所产生的表达式才是项25项的例子例如:设D为人类集合,N为自然数集合,a:张三,b:李四f(x)=x的父亲,定义在D上的一元函数g(x)=x的年龄,定义在D上的一元函数h(x,y)=x+y,定义在N上的二元函数则a,b,x,y,f(a),f(b),g(a),g(b),f(x),g(x),h(x,y)以及h(g(a),g(b)),h(g(f(a)),g(a)),h(x,g(b))等都是项项不是谓词®26一阶语言的合式公式定义4.3如果R(x1,x2,…,xn)是ℒ的n元谓词符号,t1,t2,…,tn是ℒ的n个项，则R(t1,t2,…,tn)称为ℒ的原子公式由原子公式、逻辑联词、量词和括号按下述法则构成的表达式称为谓词合式公式,简称为谓词公式定义4.4ℒ的合式公式:⑴原子公式是合式公式⑵若A,B都是合式公式,则A,AB,AB,AB和AB也是合式公式⑶若A是合式公式,则(x)A和(x)A也是合式公式⑷只有经有限次运用⑴,⑵,⑶所得到的表达式才是合式公式27§4.2一阶逻辑公式及