阶逻辑基本概念(调整).ppt

1、第4章 一阶逻辑基本概念,离 散 数 学,1.1阶逻辑的基本概念 2.1阶逻辑命题符号化 3.1阶逻辑的公式、解释、分类,1.明确一阶逻辑的相关概念 2.熟练将一阶逻辑命题符号化 3.掌握1阶逻辑公式的解释,一阶逻辑命题的符号化,1阶逻辑公式的解释,基本问题：,基本要求：,教学重点：,教学重点：,第4章 一阶逻辑基本概念,本章说明,本章与后续各章的关系 克服命题逻辑的局限性 是第五章的先行准备,引言,问题：命题逻辑的局限性 在命题逻辑中，研究的基本单位是简单命题， 对简单命题不再进行分解，并且不考虑命题 之间的内在联系和数量关系。 例如：所有的人都是要死的，苏格拉底是人，所以 苏格拉底是要死的

2、。 这是著名的苏格拉底三段论，但却无法用命题逻辑予以证明。,苏格拉底；著名的古希腊的思想家、哲 学家、教育家.学生柏拉图柏、拉图的学 生亚里士多德-“古希腊三贤”，更被后人 广泛认为是西方哲学的奠基者。,引言,一阶逻辑所研究的内容： 为了克服命题逻辑的局限性，将简单命题再细分，分析出个体词、谓词和量词，以期达到表达出个体与总体的内在联系和数量关系。,第一节 一阶逻辑命题符号化,一阶逻辑命题符号化的三个基本要素,谓词 谓词 谓词常项 谓词变项 特性谓词,量词 存在量词 全称量词,个体词 个体词 个体常项 个体变项 个体域（论域） 全总个体域,基本概念,1.个体词（个体）：指所研究对象中可以独立存

3、在的具 体或抽象的客体（名词或代词充当） 例如： 命题：电子计算机是科学技术的工具。个体词：电子计算机。 命题：他是三好学生。个体词：他。,（1）个体常项：具体的事物，用a, b,c，表示 （2）个体变项：抽象的事物，用x,y,z,表示。 （3）个体域（或称论域）：个体变项的取值范围。 有限个体域，如a, b, c, 1, 2。 无限个体域，如N,Z,R,。 全总个体域，宇宙间一切事物组成 。,基本概念,本教材在论述或推理中，如果没有指明所采用的个体域，都是使用的全总个体域。,说明,基本概念,2.谓词：表示个体词性质或相互之间关系的词 例如：(1) 是无理数 是个体常项，“是无理数”是谓词，记

4、为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)。,（1）谓词常项：表示具体的性质或关系的谓词。 F：。是人，F（a）:a是人 （2）谓词变项：表示抽象的、泛指的性质或关系的谓词。 F：。具有性质F，F（x）: x具有性质F （3）n(n1)元谓词： n=1时，一元谓词表示事物的性质。 n2时，多元谓词表示事物之间的

5、。 L(x，y)：x和y具有性质L （4）0元谓词：不含个体变项的谓词。 如F(a)、G(a,b)、P(a1,a2,an)。,基本概念,n元谓词是命题吗？ 0元谓词是命题吗？ 两者有什么区别？,思考,3.量词：是表示个体常项或个体变项之间数量关系的词。 （1）全称量词：符号化为“”， x 日常生活和数学中所用的“一切的”、“所有的”、“每一个”、“任意的”、“凡”、“都”等词可统称为全称量词。 x表示个体域里的所有个体，xF(x)表示个体域里所有个体都有性质F。 （2）存在量词：符号化为“” ，y 日常生活和数学中所用的“存在”、“有一个”、“有的”、“至少有一个”等词统称为存在量词。 y表示

6、个体域里有的个体，yG(y)表示个体域里存在个体具有性质G等。,基本概念,例4.1： 在个体域分别限制为(a)和(b)条件时，将下面两 个命题符号化: (1) 凡人都呼吸。 (2) 有的人用左手写字。 其中:(a)个体域D1为人类集合； (b)个体域D2为全总个体域。,一阶逻辑命题符号化,x,x,解：(a)个体域为人类集合,令F(x):x呼吸。G(x):x用左手写字,(1)在个体域中除了人外，再无别的东西，因而“凡人都呼吸” 应符号化为,F(x),(2)在个体域中除了人外，再无别的东西，因而“有的人用左 手写字”符号化为：,G(x),一阶逻辑命题符号化,(b)个体域为全总个体域,即除人外，还有

7、万物，所以必须考虑将人先分离出来,令F(x):x呼吸。 G(x):x用左手写字。 M(x):x是人,(1) “凡人都呼吸”应符号化为,(M(x)F(x),x,(2) “有的人用左手写字”符号化为,(M(x)G(x),x,2.同一命题在不同的个体域中符号化的形式可能不同。,思考：在全总个体域中， 能否将(1)符号化为x(M(x)F(x)？ 能否将(2)符号化为x(M(x)G(x)？,注意：,1.在使用全总个体域时，要将人从其他事物中区别出来， 为此引进了谓词M(x)，称为特性谓词,例4.2： 在个体域限制为(a)和(b)条件时，将下列命题符号化: (1) 对于任意的x，均有x2-3x+2=(x-

8、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)的符号化形式为x F(x) （真命题） 命题(2)的符号化形式为x G(x) （假命题） (b)在D2内，(1)和(2)的符号化形式同(a)，皆为真命题。,一阶逻辑命题符号化,说明,1.在不同个体域内，同一个命题的符号化形式可能不同，也可能相同。,2.同一个命题，在不同个体域中的真值也可能不同。,例4.3 ：将下列命题符号化，并讨论真值。 （1）所有的人长着黑头发。

9、 （2）有的人登上过月球。 （3）没有人登上过木星。 （4）在美国留学的学生未必都是亚洲人。,例题,谓词逻辑中命题的符号化，主要考虑以下问题： 非空个体域的选取 量词的使用及作用范围 正确地语义,1.全称量词的选取注 意和蕴含式的结合。 2.存在量词的选取注意 和合取式的结合。,1.若是为了确定命题的真值，一 般约定在某个个体域上进行。 2.在由一切事物构成的全总个体 域上考虑问题时，需要增加一 个指出个体变量变化范围的特 性谓词。,特别提醒,解：没有提出个体域，所以认为是全总个体域,（1）所有的人长着黑头发。,令F(x):x长着黑头发， M(x):x是人。 命题符号化为,M(x),F(x),

10、),(,x,命题真值为假,（2）有的人登上过月球。,令G(x):x登上过月球， M(x):x是人。 命题符号化为：,(M(x)G(x)。,x,命题真值为真。,例题,（3）没有人登上过木星,令H(x):x登上过木星， M(x):x是人,命题符号化为：,(M(x)H(x),x,命题真值为真,（4）在美国留学的学生未必都是亚洲人,令F(x):x是在美国留学的学生，G(x):x是亚洲人,命题符号化为：,(F(x)G(x),x,命题真值为真,例题,一阶逻辑命题符号化时需要注意的事项,1.分析命题中表示性质和关系的谓词， 分别符号为一元和n（ n2）元谓词。 2.根据命题的实际意义选用全称量词或存在量词。

11、 3.一般说来，多个量词出现时，它们的顺序不能随意调换。 例如：考虑个体域为实数集，H(x，y)表示x+y=10， 则命题“对于任意的x，都存在y，使得x+y=10”的符号化 形式为xyH(x,y) 真命题。 如果改变两个量词的顺序，得yxH(x,y) 假命题。,第二节 一阶逻辑公式及解释,同在命题逻辑中一样，为在一阶逻辑中进行演算和推理，必须给出一阶逻辑中公式的抽象定义，以及它们的分类及解释。,一阶语言F的字母表,定义4.1 ：一阶语言F的字母表定义如下: (1)个体常项：a , b , c , , ai , bi , ci , , i 1 (2)个体变项：x , y , z, , xi ,

12、 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)括号与逗号:(,),，,一阶语言：是用于一阶逻辑的形式语言。,一阶语言F的项,定义4.2： 一阶语言F的项的定义如下: (1) 个体常项和个体变项是项。 (2) 若(x1,x2,xn)是任意的n元函数，t1,t2,tn是任意的n个项，则(t1,t2,tn)是项。 (3) 所有的项都是有限次使用(1)，(2)得到的。,一阶语言F的原子公式,定义

13、4.3:(一阶语言F的原子公式) 设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)等都 是原子公式。,一阶语言F的合式公式,定义4.4 一阶语言F的合式公式定义如下: (1) 原子公式是合式公式。 (2) 若A是合式公式，则(A)也是合式公式。 (3) 若A，B是合式公式，则(AB)，(AB)，(AB)，(AB) 也是合式公式。 (4) 若A是合式公式，则xA，xA也是合式公式。 (5) 只有有限次

14、的应用(1)(4)构成的符号串才是合式公式。 一阶语言F的合式公式也称为谓词公式，简称公式。,A，B代表任意公式，是元语言符号。 下文的讨论都是在一阶语言F中，因而不再提及。,说明,自由出现与约束出现,定义4.5： 指导变元-在公式xA和xA中，称x为指导变元。 辖域-在公式xA和xA中，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

15、,y,z),例题,解答,(1) x是指导变元。量词的辖域A=(F(x,y)G(x,z)。在A中，x的两次出现均是约束出现。y和z均为自由出现。 (2) 前件上量词的指导变元为x，量词的辖域A=(F(x)G(y)，x在A中是约束出现的，y在A中是自由出现的。后件中量词的指导变元为y， 量词的辖域为B=(H(x)L(x,y,z)，y在B中是约束出现的，x、z在B中均为自由出现的。,闭式,定义4.6： 设A是任意的公式，若A中不含有自由出现的个体 变项，则称A为封闭的公式，简称闭式。 例如： xy(F(x)G(y)H(x , y) 为闭式， x(F(x)G(x , y) 不是闭式 。,一阶公式的解释

16、 一阶公式没有确定的意义，一旦将其中的变项（项的变项、谓词变项）用指定的常项代替后，所得公式就具备一定的意义，有时就变成命题了。,例题4.7,例4.7： 将下列两个公式中的变项指定成常项使其成为命题: (1)x(F(x)G(x)(2)xy(F(x)F(y)G(x,y)H(f(x,y),g(x,y) (1)指定个体变项的变化范围，并且指定谓词F，G的含义， 下面给出两种指定法: (a)令个体域D1为全总个体域，F(x)为x是人，G(x)为x是黄种人， 则命题为“所有人都是黄种人”，这是假命题。 (b)令个体域D2为实数集合R，F(x)为x是自然数，G(x)为x是整数， 则命题为“自然数都是整数”

17、，这是真命题。,例题4.7,(2)xy(F(x)F(y)G(x,y)H(f(x,y),g(x,y) 含有两个2元函数变项，两个1元谓词变项，两个2元谓词变项。 指定个体域为全总个体域，F(x)为x是实数，G(x,y)为xy，H(x,y)为xy，f(x,y)=x2+y2，g(x,y)=2xy， 则表达的命题为“对于任意的x，y，若x与y都是实数，且xy，则x2+y22xy”，这是真命题。 如果H(x,y)改为xy， 则所得命题为假命题。,例4.8 给定解释I如下: (a) 个体域D=N(N为自然数集合，即 N=0,1,2,),(b) =0,(c) (x,y)=x+y, (x,y)=xy。,(d)

18、 (x,y)为x=y。,在I下，下列哪些公式为真?哪些为假?哪些的真值还不能确定?,例题4.8,例题4.8,(1) F(f(x,y),g(x,y) (2) F(f(x,a),y)F(g(x,y),z) (3) F(g(x,y),g(y,z) (4) x F(g(x,y),z) (5) x F(g(x,a),x)F(x,y) (6) x F(g(x,a),x) (7) xy(F(f(x,a),y)F(f(y,a),x) (8) xyz F(f(x,y),z) (9) x F(f(x,x),g(x,x),例题4.8,(1) F(f(x,y),g(x,y) 公式被解释成“x+y=xy”，这不是命题。

19、 (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) x F(g(x,y),z) 公式被解释成“x(xy=z)”，不是命题。,例题4.8,(5) x F(g(x,a),x)F(x,y) 公式被解释成“x(x0=x)(x=y)”，由于前件为假，所以被 解释的公式为真。 (6) x F(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

20、=x)”，为真命题。,(8) xyz F(f(x,y),z) 公式被解释成“xyz(x+y=z)”，这也为真命题。 (9) x F(f(x,x),g(x,x) 公式被解释成“x(x+x=xx)”，为真命题。,例题4.8,定理4.1 封闭的公式在任何解释下都变成命题。,一阶公式的分类,定义4.8： 、 永真式：设A为一个公式，若A在任何解释下均为真，则称A为 永真式(或称逻辑有效式)。 永假式：设A为一个公式，若A在任何解释下均为假，则称A为 矛盾式(或永假式)。 可满足式：设A为一个公式，若至少存在一个解释使A为真， 则称A为可满足式。,永真式一定是可满足式，但可满足式不一定是永真式。 在一阶

21、逻辑中，到目前为止，还没有找到一种可行的算法，用来判断任意一个公式是否是可满足的，这与命题逻辑的情况是完全不同的。 但对某些特殊的公式还是可以判断的。,说明,代换实例,定义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.9 判断下列公式中，哪些是永真式，哪些是矛盾式？ （1）x(F(x)G(

22、x) （2）x(F(x)G(x) （3）xF(x)(xyG(x,y)xF(x) （4）(xF(x)yG(y)yG(y) 解: (1) x(F(x)G(x) 解释1：个体域为实数集合R，F(x)：x是整数，G(x)：x是有理数，因此公式真值为真。 解释2：个体域为实数集合R，F(x)：x是无理数，G(x)：x能表示成分数，因此公式真值为假。 所以公式为非永真式的可满足式。,例题4.9,例题4.9,（2）x(F(x)G(x) 公式为非永真式的可满足式。 （3）xF(x)(xyG(x,y)xF(x) 为p(qp)（重言式）的代换实例，故为永真式。 （4）(xF(x)yG(y)yG(y) 为(pq)q

23、（矛盾式）的代换实例，故为永假式。,例题,例4.10 判断下列公式的类型。(1) xF(x) xF(x)(2) xyF(x,y) xyF(x,y)(3) x(F(x)G(x) yG(y) 解 记(1)，(2)，(3)中的公式分别为A,B,C。 (1)设I为任意一个解释，个体域为D。 若存在x0D，使得F(x0)为假，则xF(x)为假，所以A的前件为假，故A为真。 若对于任意xD，F(x)均为真，则xF(x)，xF(x)都为真，从而A为真。 所以在I下A为真。由I的任意性可知，A是永真式。,例题,(2) xyF(x,y) xyF(x,y) 取解释I：个体域为自然数集合N，F(x,y)为xy。 在I下B的前件与后件均为真，所以B为真。这说明B不是矛盾式。（ 在xyF(x,y)中，x0 ） 再取I：个体域仍然为N，F(x,y)为x=y。 在I下，B的前件真而后件假，所以B为假。这说明B不是永真式。 故B是非永真式的可满足式。 (3) x(F(x)G(x) yG(y) C也是非永真式的可满足式。,小节结束,本章主要内容,个体词个体常项个体变项个体域全总个体域 谓词谓词常项谓词变项n(n1)元谓词特性谓词 量词全称量词存在量词,本章主要内容,一阶逻辑中命题符号化 一阶逻辑公式原子公