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

《04一阶逻辑基本概念(调整).ppt》由会员分享，可在线阅读，更多相关《04一阶逻辑基本概念(调整).ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第第第4 4 4 4章章章章 一阶逻辑基本概念一阶逻辑基本概念一阶逻辑基本概念一阶逻辑基本概念离离 散散 数数 学学 1.11.1阶逻辑的基本概念阶逻辑的基本概念 2.12.1阶逻辑命题符号化阶逻辑命题符号化 3.1 3.1阶逻辑的公式、解释、分类阶逻辑的公式、解释、分类 1.1.明确一阶逻辑的相关概念明确一阶逻辑的相关概念 2.2.熟练将一阶逻辑命题符号化熟练将一阶逻辑命题符号化 3.3.掌握掌握1 1阶逻辑公式的解释阶逻辑公式的解释一阶逻辑命题的符号化一阶逻辑命题的符号化1 1阶逻辑公式的解释阶逻辑公式的解释基本问题：基本问题：基本要求：基本要求：教学重点：教学重点：教学重点：教学重点：

2、第第4 4章章 一阶逻辑基本概念一阶逻辑基本概念本章说明本章说明本章说明本章说明本章与后续各章的关系本章与后续各章的关系克服命题逻辑的局限性克服命题逻辑的局限性是第五章的先行准备是第五章的先行准备 引言引言引言引言问题：命题逻辑的局限性问题：命题逻辑的局限性 在命题逻辑中，研究的基本单位是简单命题，在命题逻辑中，研究的基本单位是简单命题，对简单命题不再进行分解，并且不考虑命题对简单命题不再进行分解，并且不考虑命题 之间的内在联系和数量关系。之间的内在联系和数量关系。例如：例如：所有的人都是要死的，苏格拉底是人，所以所有的人都是要死的，苏格拉底是人，所以 苏格拉底是要死的。苏格拉底是要死的。这是

3、著名的苏格拉底三段论，但却无法用命题逻辑予以证明。这是著名的苏格拉底三段论，但却无法用命题逻辑予以证明。苏格拉底；著名的古希腊的思想家、哲苏格拉底；著名的古希腊的思想家、哲学家、教育家学家、教育家.学生学生柏拉柏拉图柏、拉图的学图柏、拉图的学生亚里士多德生亚里士多德-“古希腊三贤古希腊三贤”，更被后，更被后人人广泛认为是西方哲学的奠基者。广泛认为是西方哲学的奠基者。引言引言引言引言一阶逻辑所研究的内容：一阶逻辑所研究的内容：为了克服命题逻辑的局为了克服命题逻辑的局限性，将简单命题再细分，限性，将简单命题再细分，分析出个体词、谓词和量词，分析出个体词、谓词和量词，以期达到表达出个体与总体以期达到

4、表达出个体与总体的内在联系和数量关系。的内在联系和数量关系。第一节第一节 一阶逻辑命题符号化一阶逻辑命题符号化一阶逻辑命题符号化一阶逻辑命题符号化一阶逻辑命题符号化的三个基本要素一阶逻辑命题符号化的三个基本要素谓词谓词 谓词谓词 谓词常项谓词常项 谓词变项谓词变项 特性谓词特性谓词量词量词 存在量词存在量词 全称量词全称量词个体词个体词个体词个体词个体常项个体常项个体变项个体变项个体域（论域）个体域（论域）全总个体域全总个体域基本概念基本概念基本概念基本概念1.1.个体词（个体）：个体词（个体）：指所研究对象中可以独立存在的具指所研究对象中可以独立存在的具 体或抽象的客体（名词或代词充当）体或

5、抽象的客体（名词或代词充当）例如：例如：命题：电子计算机是科学技术的工具。命题：电子计算机是科学技术的工具。个体词：电子计算机。个体词：电子计算机。命题：他是三好学生命题：他是三好学生。个体词：他。个体词：他。（1 1）个体常项：个体常项：具体的事物，用具体的事物，用a,b,c，表示表示（2 2）个体变项：个体变项：抽象的事物，用抽象的事物，用x,y,z,表示。表示。（3 3）个体域（或称论域）：个体域（或称论域）：个体变项的取值范围。个体变项的取值范围。有限个体域，如有限个体域，如 a a,b b,c c,1,2,1,2。无限个体域，如无限个体域，如N N,Z Z,R R,。全总个体域，宇宙

6、间一切事物组成全总个体域，宇宙间一切事物组成 。基本概念基本概念基本概念基本概念本教材在论述或推理中，如果没有指明所采用的个体本教材在论述或推理中，如果没有指明所采用的个体域，都是使用的全总个体域。域，都是使用的全总个体域。说说明明基本概念基本概念基本概念基本概念2.2.谓词：谓词：表示个体词性质表示个体词性质或相互之间关系的词或相互之间关系的词例如：例如：(1)(1)是无理数是无理数 是个体常项，是个体常项，“是无理数是无理数”是谓词，记为是谓词，记为F F，命题符号化命题符号化 为为F(F()。(2)(2)x x是有理数是有理数 x x是个体变项，是个体变项，“是有理数是有理数”是谓词，记

7、为是谓词，记为G G，命题符号化命题符号化 为为G(G(x x)。(3)(3)小王与小李同岁小王与小李同岁 小王、小李都是个体常项，小王、小李都是个体常项，“与与同岁同岁”是谓词，记为是谓词，记为H H，命题符号化为命题符号化为H(H(a,ba,b)，其中，其中a a：小王，小王，b b：小李：小李。(4)(4)x x与与y y具有关系具有关系L L x x，y y都是个体变项，谓词为都是个体变项，谓词为L L，命题符号化为命题符号化为L(x,yL(x,y)。（1 1）谓词常项）谓词常项：表示具体的性质或关系的谓词。：表示具体的性质或关系的谓词。F F：。是人，：。是人，F F（a a）:a:

8、a是人是人（2 2）谓词变项）谓词变项：表示抽象的、泛指的性质或关系的谓词。：表示抽象的、泛指的性质或关系的谓词。F F：。具有性质：。具有性质F F，F F（x）:x具有性质具有性质F F（3 3）n n(n n 1)1)元谓词元谓词：n=1n=1时，一元谓词时，一元谓词表示事物的性质表示事物的性质。n2n2时，多元谓词时，多元谓词表示事物之间的表示事物之间的。L(L(x，y)：x和和y具有性质具有性质L（4 4）0 0元谓词元谓词：不含个体变项的谓词。：不含个体变项的谓词。如如F(a)F(a)、G(a,b)G(a,b)、P(aP(a1 1,a,a2 2,a,an n)。基本概念基本概念基本

9、概念基本概念qn n元谓词是命题吗？元谓词是命题吗？q0 0元谓词是命题吗？元谓词是命题吗？q两者有什么区别？两者有什么区别？思思考考3.3.量词：量词：是表示个体常项或个体变项之间数量关系的词。是表示个体常项或个体变项之间数量关系的词。（1 1）全称量词全称量词：符号化为符号化为“”，x x日日常常生生活活和和数数学学中中所所用用的的“一一切切的的”、“所所有有的的”、“每每一一个个”、“任意的任意的”、“凡凡”、“都都”等词可统称为全称量词。等词可统称为全称量词。x x表表示示个个体体域域里里的的所所有有个个体体，xF(xxF(x)表表示示个个体体域域里里所所有有个个体体都有性质都有性质F

10、 F。（2 2）存在量词存在量词：符号化为：符号化为“”，y y日日常常生生活活和和数数学学中中所所用用的的“存存在在”、“有有一一个个”、“有有的的”、“至少有一个至少有一个”等词统称为存在量词。等词统称为存在量词。y y表表示示个个体体域域里里有有的的个个体体，yG(yyG(y)表表示示个个体体域域里里存存在在个个体体具具有有性质性质G G等。等。基本概念基本概念基本概念基本概念例例4.4.1 1：在个体域分别限制为在个体域分别限制为(a)a)和和(b)b)条件时，将下面两条件时，将下面两 个命题符号化个命题符号化:(1)(1)凡人都呼吸。凡人都呼吸。(2)(2)有的人用左手写字。有的人用

11、左手写字。其中其中:(:(a)a)个体域个体域D D1 1为人类集合；为人类集合；(b)b)个体域个体域D D2 2为全总个体域。为全总个体域。一阶逻辑命题符号化一阶逻辑命题符号化一阶逻辑命题符号化一阶逻辑命题符号化 x x x x 解：解：(a)a)个体域为人类集合个体域为人类集合令令F(x):xF(x):x呼吸。呼吸。G(x):xG(x):x用左手写字用左手写字(1)(1)在个体域中除了人外，再无别的东西，因而在个体域中除了人外，再无别的东西，因而“凡人都呼吸凡人都呼吸”应符号化为应符号化为 F(xF(x)(2)(2)在个体域中除了人外，再无别的东西，因而在个体域中除了人外，再无别的东西，

12、因而“有的人用左有的人用左 手写字手写字”符号化为：符号化为：G(xG(x)一阶逻辑命题符号化一阶逻辑命题符号化(b)b)个体域为全总个体域个体域为全总个体域即除人外，还有万物，所以必须考虑将人先分离出来即除人外，还有万物，所以必须考虑将人先分离出来令令F(x):xF(x):x呼吸。呼吸。G(x):xG(x):x用左手写字。用左手写字。M(x):xM(x):x是人是人(1)(1)“凡人都呼吸凡人都呼吸”应符号化为应符号化为(M(x)F(xM(x)F(x)x x(2)(2)“有的人用左手写字有的人用左手写字”符号化为符号化为(M(x)G(xM(x)G(x)x x2.同一命题在不同的个体域中符号化

13、的形式可能不同。同一命题在不同的个体域中符号化的形式可能不同。思考：思考：在全总个体域中，在全总个体域中，能否将能否将(1)(1)符号化为符号化为 x(M(x)F(xx(M(x)F(x)？能否将能否将(2)(2)符号化为符号化为 x(M(x)G(xx(M(x)G(x)？注意：注意：1.1.在使用全总个体域时，要将人从其他事物中区别出来，在使用全总个体域时，要将人从其他事物中区别出来，为此引进了谓词为此引进了谓词M(xM(x)，称为特性谓词称为特性谓词例例4.2：在个体域限制为在个体域限制为(a)a)和和(b)b)条件时，将下列命题符号化条件时，将下列命题符号化:(1)(1)对于任意的对于任意的

14、x x，均有均有x x2 2-3x+2=(x-1)(x-2)-3x+2=(x-1)(x-2)。(2)(2)存在存在x x，使得使得x+5=3x+5=3。其中其中:(:(a)a)个体域个体域D D1 1=N(N=N(N为自然数集合为自然数集合)(b)b)个体域个体域D D2 2=R(R=R(R为实数集合为实数集合)(a)a)令令F(xF(x):x):x2 2-3x+2=(x-1)(x-2)-3x+2=(x-1)(x-2)，G(x):x+5=3G(x):x+5=3。命题命题(1)(1)的符号化形式为的符号化形式为 x x F(xF(x)（真命题）真命题）命题命题(2)(2)的符号化形式为的符号化形

15、式为 x x G(xG(x)（假命题）假命题）(b)b)在在D D2 2内，内，(1)(1)和和(2)(2)的符号化形式同的符号化形式同(a)a)，皆为真命题。皆为真命题。一阶逻辑命题符号化一阶逻辑命题符号化一阶逻辑命题符号化一阶逻辑命题符号化说明说明1.在不同个体域内，同一个命题的在不同个体域内，同一个命题的符号化形式可能不同，也可能相符号化形式可能不同，也可能相同。同。2.同一个命题，在不同个体域中的真值同一个命题，在不同个体域中的真值也可能不同。也可能不同。例例4.4.3 3 ：将下列命题符号化，并讨论真值。将下列命题符号化，并讨论真值。（1 1）所有的人长着黑头发。）所有的人长着黑头发

16、。（2 2）有的人登上过月球。）有的人登上过月球。（3 3）没有人登上过木星。）没有人登上过木星。（4 4）在美国留学的学生未必都是亚洲人。）在美国留学的学生未必都是亚洲人。例题例题例题例题谓词逻辑中命题的符号化，主要考虑以下问题：谓词逻辑中命题的符号化，主要考虑以下问题：非空个体域的选取非空个体域的选取量词的使用及作用范围量词的使用及作用范围正确地语义正确地语义1.1.全称量词的选取注全称量词的选取注 意和蕴含式的结合。意和蕴含式的结合。2.2.存在量词的选取注意存在量词的选取注意 和合取式的结合。和合取式的结合。1.1.若是为了确定命题的真值，一若是为了确定命题的真值，一 般约定在某个个体

17、域上进行。般约定在某个个体域上进行。2.2.在由一切事物构成的全总个体在由一切事物构成的全总个体 域上考虑问题时，需要增加一域上考虑问题时，需要增加一 个指出个体变量变化范围的特个指出个体变量变化范围的特 性谓词。性谓词。特别提醒特别提醒特别提醒特别提醒解：没有提出个体域，所以认为是全总个体域解：没有提出个体域，所以认为是全总个体域（1 1）所有的人长着黑头发。）所有的人长着黑头发。令令F(x):xF(x):x长着黑头发，长着黑头发，M(x):xM(x):x是人。是人。命题符号化为命题符号化为M(xM(x)F(xF(x)(x x命题真值为假命题真值为假（2 2）有的人登上过月球。）有的人登上过

18、月球。令令G(x):xG(x):x登上过月球登上过月球，M(x):xM(x):x是人。是人。命题符号化为：命题符号化为：(M(x)G(xM(x)G(x)。x x命题真值为真。命题真值为真。例题例题（3 3）没有人登上过木星）没有人登上过木星令令H(x):xH(x):x登上过木星登上过木星，M(x):xM(x):x是人是人命题符号化为：命题符号化为：(M(x)H(xM(x)H(x)x x命题真值为真命题真值为真（4 4）在美国留学的学生未必都是亚洲人在美国留学的学生未必都是亚洲人令令F(x):xF(x):x是在美国留学的学生，是在美国留学的学生，G(x):xG(x):x是亚洲人是亚洲人命题符号化

19、为：命题符号化为：(F(x)G(x)x命题真值为真命题真值为真例题例题一阶逻辑命题符号化时需要注意的事项一阶逻辑命题符号化时需要注意的事项一阶逻辑命题符号化时需要注意的事项一阶逻辑命题符号化时需要注意的事项1 1.分析命题中表示性质和关系的谓词，分析命题中表示性质和关系的谓词，分别符号为一元和分别符号为一元和n n（n n 2 2）元谓词。元谓词。2.2.根据命题的实际意义选用全称量词或存在量词。根据命题的实际意义选用全称量词或存在量词。3.3.一般说来，多个一般说来，多个量词量词出现时，它们的顺序不能随意调换。出现时，它们的顺序不能随意调换。例如：例如：考虑个体域为实数集，考虑个体域为实数集

20、，H(xH(x，y y)表示表示x+yx+y=10=10，则命题则命题“对于任意的对于任意的x x，都存在都存在y y，使得使得x+yx+y=10=10”的符号化的符号化形式为形式为 x x y yH(x,yH(x,y)真命题。真命题。如果改变两个量词的顺序，得如果改变两个量词的顺序，得 y y x xH(x,yH(x,y)假命题。假命题。第二节第二节第二节第二节 一阶逻辑公式及解释一阶逻辑公式及解释一阶逻辑公式及解释一阶逻辑公式及解释 同在命题逻辑中一样，为在一阶逻辑中同在命题逻辑中一样，为在一阶逻辑中进行演算和推理，必须给出一阶逻辑进行演算和推理，必须给出一阶逻辑中公式的抽象定义，以及它们

21、的分类中公式的抽象定义，以及它们的分类及解释。及解释。一阶语言一阶语言一阶语言一阶语言F F F F的字母表的字母表的字母表的字母表定义定义4.1 4.1：一阶语言一阶语言F F的的字母表字母表定义如下定义如下:(1)(1)个体常项：个体常项：a a,b b,c c,a ai i ,b bi i ,c ci i ,i i 1 1(2)(2)个体变项：个体变项：x x,y y,z z,x xi i ,y yi i ,z zi i ,i i 1 1(3)(3)函数符号：函数符号：f f,g g,h h,f fi i ,g gi i ,h hi i ,i i 1 1(4)(4)谓词符号：谓词符号：F

22、 F,G G,H H,F Fi i ,G Gi i ,H Hi i ,i i 1 1(5)(5)量词符号量词符号:，(6)(6)联结词符号联结词符号:,:,(7)(7)括号与逗号括号与逗号:(,),:(,),，一阶语言：一阶语言：是用于一阶逻辑的形式语言。是用于一阶逻辑的形式语言。一阶语言一阶语言一阶语言一阶语言F F的项的项的项的项定义定义4.24.2：一阶语言一阶语言F F的的项项的定义如下的定义如下:(1)(1)个体常项和个体变项是个体常项和个体变项是项项。(2)(2)若若(x(x1 1,x,x2 2,x xn n)是任意的是任意的n n元函数，元函数，t t1 1,t,t2 2,t t

23、n n是任是任意的意的n n个项，则个项，则(t(t1 1,t,t2 2,t tn n)是是项项。(3)(3)所有的项都是有限次使用所有的项都是有限次使用(1)(1)，(2)(2)得到的。得到的。一阶语言一阶语言一阶语言一阶语言F F的原子公式的原子公式的原子公式的原子公式定义定义4.34.3:(一阶语言一阶语言F F的原子公式的原子公式)设设R(xR(x1 1,x,x2,2,x xn n)是一阶语言是一阶语言F F的的任意任意n n元谓元谓 词，词，t t1 1,t,t2 2,t tn n是一阶语言是一阶语言F F的任意的的任意的n n个个 项，则称项，则称R(tR(t1 1,t,t2 2,

24、t tn n)是一阶语言是一阶语言F F的的原子公式。原子公式。例如例如：1 1元谓词元谓词F(x)F(x)，G(x)G(x)，2 2元谓词元谓词H(x,y)H(x,y)，L(x,y)L(x,y)等都等都 是原子公式。是原子公式。一阶语言一阶语言一阶语言一阶语言F F F F的合式公式的合式公式的合式公式的合式公式定义定义4.4 4.4 一阶语言一阶语言F F的的合式公式合式公式定义如下定义如下:(1)(1)原子公式是合式公式。原子公式是合式公式。(2)(2)若若A A是合式公式，则是合式公式，则(A)A)也是合式公式。也是合式公式。(3)(3)若若A A，B B是合式公式，则是合式公式，则(

25、A AB)B)，(A(AB)B)，(A(AB)B)，(A(AB)B)也是合式公式。也是合式公式。(4)(4)若若A A是合式公式，则是合式公式，则 xAxA，xAxA也是合式公式。也是合式公式。(5)(5)只有有限次的应用只有有限次的应用(1)(1)(4)(4)构成的符号串才是合式公式。构成的符号串才是合式公式。一阶语言一阶语言F F的合式公式也称为的合式公式也称为谓词公式谓词公式，简称，简称公式公式。qA A，B B代表任意公式，是元语言符号。代表任意公式，是元语言符号。q下文的讨论都是在一阶语言下文的讨论都是在一阶语言F F中，因而不再提及中，因而不再提及。说说明明自由出现与约束出现自由出

26、现与约束出现自由出现与约束出现自由出现与约束出现定义定义4.54.5：指导变元指导变元-在公式在公式 xAxA和和 xAxA中，称中，称x x为为指导变元指导变元。辖域辖域-在公式在公式 xAxA和和 xAxA中，中，A A为相应量词的为相应量词的辖域辖域。约束出现约束出现-在在 x x和和 x x的辖域中，的辖域中，x x的所有出现都称为的所有出现都称为约束出现约束出现。自由出现自由出现-A A中不是约束出现的其他变项均称为是中不是约束出现的其他变项均称为是自由出现自由出现的。的。例例4.64.6 指出下列各公式中的指导变元，各指出下列各公式中的指导变元，各量词的辖域，自由出量词的辖域，自由

27、出 现以及约束出现的个体变项现以及约束出现的个体变项。(1)(1)x x(F(F(x x,y)G(,y)G(x x,z,z)(2)(2)x x(F(F(x x)G(y)G(y)y y(H(x)L(x,(H(x)L(x,y y,z,z)例题例题例题例题解答解答(1)(1)x x是指导变元。量词是指导变元。量词 的辖域的辖域A=(F(x,y)G(x,z)A=(F(x,y)G(x,z)。在在A A中，中，x x的两次出现均是约束出现。的两次出现均是约束出现。y y和和z z均为自由出现。均为自由出现。(2)(2)前件上量词前件上量词 的指导变元为的指导变元为x x，量词量词 的辖域的辖域A=(F(x

28、)G(y)A=(F(x)G(y)，x x在在A A中是约束出现的，中是约束出现的，y y在在A A中是自由出中是自由出现的。后件中量词现的。后件中量词 的指导变元为的指导变元为y y，量词量词 的辖域为的辖域为B=(H(x)L(x,y,z)B=(H(x)L(x,y,z)，y y在在B B中是约束出现的，中是约束出现的，x x、z z在在B B中中均为自由出现的。均为自由出现的。闭式闭式闭式闭式定义定义4.64.6：设设A A是任意的公式，若是任意的公式，若A A中不含有自由出现的个体中不含有自由出现的个体 变项，则称变项，则称A A为为封闭的公式封闭的公式，简称，简称闭式闭式。例如：例如：x

29、y(F(x)G(y)H(x,y)为闭式，为闭式，x(F(x)G(x,y)不是闭式不是闭式。一阶公式的解释一阶公式的解释一一阶阶公公式式没没有有确确定定的的意意义义，一一旦旦将将其其中中的的变变项项（项项的的变变项项、谓谓词词变变项项）用用指指定定的的常常项项代代替替后后，所所得得公公式式就就具具备备一一定定的的意义，有时就变成命题了。意义，有时就变成命题了。例题例题例题例题4.74.74.74.7例例4.74.7：将下列两个公式中的变项指定成常项使其成为命题将下列两个公式中的变项指定成常项使其成为命题:(1)(1)x(F(x)x(F(x)G(xG(x)(2)(2)x x y(F(x)y(F(x

30、)F(y)F(y)G(x,y)G(x,y)H(f(x,y),g(x,yH(f(x,y),g(x,y)(1)(1)指定个体变项的变化范围，并且指定谓词指定个体变项的变化范围，并且指定谓词F F，G G的含义，的含义，下面给出两种指定法下面给出两种指定法:(a)a)令个体域令个体域D D1 1为全总个体域，为全总个体域，F(xF(x)为为x x是人，是人，G(xG(x)为为x x是黄种人，是黄种人，则命题为则命题为“所有人都是黄种人所有人都是黄种人”，这是假命题。，这是假命题。(b)b)令个体域令个体域D D2 2为实数集合为实数集合R R，F(xF(x)为为x x是自然数，是自然数，G(xG(x

31、)为为x x是整数，是整数，则命题为则命题为“自然数都是整数自然数都是整数”，这是真命题。，这是真命题。例题例题例题例题4.74.74.74.7(2)(2)x x y(F(x)y(F(x)F(y)F(y)G(x,y)G(x,y)H(f(x,y),g(x,yH(f(x,y),g(x,y)含有两个含有两个2 2元函数变项，两个元函数变项，两个1 1元谓词变项，两个元谓词变项，两个2 2元谓词变元谓词变项。项。指定个体域为全总个体域，指定个体域为全总个体域，F(xF(x)为为x x是实数，是实数，G(x,yG(x,y)为为xyxy，H(x,yH(x,y)为为xyxy，f(x,yf(x,y)=x)=x

32、2 2+y+y2 2，g(x,yg(x,y)=2xy)=2xy，则表达的命题为则表达的命题为“对于任意的对于任意的x x，y y，若若x x与与y y都是实数，且都是实数，且xyxy，则则x x2 2+y+y2 22xy”2xy”，这是真命题。这是真命题。如果如果H(x,yH(x,y)改为改为xyxy，则所得命题为假命题。则所得命题为假命题。例例4.84.8 给定解释给定解释I I如下如下:(a)a)个体域个体域D=N(ND=N(N为自然数集合，即为自然数集合，即 N=0,1,2,N=0,1,2,)(b)=0(c)(x,y)=x+y,(x,y)=xy。(d)(x,y)为为x=y。在在I下，下列

33、哪些公式为真下，下列哪些公式为真?哪些为假哪些为假?哪些的真值还不能确定哪些的真值还不能确定?例题例题例题例题4.84.8例题例题例题例题4.84.84.84.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)xF(g(x,y),z)(5)xF(g(x,a),x)F(x,y)(6)xF(g(x,a),x)(7)x y(F(f(x,a),y)F(f(y,a),x)(8)x y zF(f(x,y),z)(9)xF(f(x,x),g(x,x)例题例题例题例题4.84.84.84.8(1)(1)F(f(x,y),g(x,y

34、F(f(x,y),g(x,y)公式被解释成公式被解释成“x+yx+y=x xy y”，这不是命题。这不是命题。(2)(2)F(f(x,a),y)F(g(x,y),zF(f(x,a),y)F(g(x,y),z)公式被解释成公式被解释成“(x+0=x+0=y)y)(x(xy y=z)=z)”，这也不是命题。这也不是命题。(3)(3)F(g(x,y),g(y,zF(g(x,y),g(y,z)公式被解释成公式被解释成“x xy yy yz z”，同样不是命题。同样不是命题。(4)(4)x x F(g(x,y),zF(g(x,y),z)公式被解释成公式被解释成“x(xx(xy y=z)=z)”，不是命题

35、。不是命题。例题例题例题例题4.84.84.84.8(5)(5)x x F(g(x,a),x)F(x,yF(g(x,a),x)F(x,y)公式被解释成公式被解释成“x(xx(x0=0=x)x)(x(x=y)=y)”，由于前件为假，所由于前件为假，所以被以被 解释的公式为真。解释的公式为真。(6)(6)x x F(g(x,a),xF(g(x,a),x)公式被解释成公式被解释成“x(xx(x0=x)0=x)”，为假命题。为假命题。(7)(7)x x y(F(f(x,a),y)F(f(y,a),xy(F(f(x,a),y)F(f(y,a),x)公式被解释成公式被解释成“x x y(x+0=y)y(x

36、+0=y)(y+0=x)(y+0=x)”，为真命题。为真命题。(8)(8)x x y y z z F(f(x,y),zF(f(x,y),z)公式被解释成公式被解释成“x x y y z(x+yz(x+y=z)=z)”，这也为真命题。这也为真命题。(9)(9)x x F(f(x,x),g(x,xF(f(x,x),g(x,x)公式被解释成公式被解释成“x(x+xx(x+x=x xx x)”，为真命题。为真命题。例题例题例题例题4.84.84.84.8定理定理4.14.1 封闭的公式在任何解释下都变成命题。封闭的公式在任何解释下都变成命题。一阶公式的分类一阶公式的分类一阶公式的分类一阶公式的分类定义

37、定义4.84.8：、永真式：永真式：设设A A为一个公式，若为一个公式，若A A在任何解释下均为真，则称在任何解释下均为真，则称A A为为 永真式永真式(或称或称逻辑有效式逻辑有效式)。永假式：永假式：设设A A为一个公式，若为一个公式，若A A在任何解释下均为假，则称在任何解释下均为假，则称A A为为 矛盾式矛盾式(或或永假式永假式)。可满足式：可满足式：设设A A为一个公式，若至少存在一个解释使为一个公式，若至少存在一个解释使A A为真，为真，则称则称A A为为可满足式可满足式。q永真式一定是可满足式，但可满足式不一定是永真式。永真式一定是可满足式，但可满足式不一定是永真式。q在一阶逻辑中

38、，到目前为止，还没有找到一种可行的算在一阶逻辑中，到目前为止，还没有找到一种可行的算法，用来判断任意一个公式是否是可满足的，这与命题法，用来判断任意一个公式是否是可满足的，这与命题逻辑的情况是完全不同的。逻辑的情况是完全不同的。q但对某些特殊的公式还是可以判断的。但对某些特殊的公式还是可以判断的。说说明明代换实例代换实例代换实例代换实例定义定义4.94.9：设设A A0 0是含有命题变项是含有命题变项p p1 1,p,p2 2,p pn n的命题公式，的命题公式，A A1 1,A,A2 2,A,An n是是n n个谓词公式，用个谓词公式，用A Ai i(1(1i in)n)处处处处 代替代替A

39、 A0 0中的中的p pi i，所得公式所得公式A A称为称为A A0 0的的代换实例代换实例。例如例如，F(x)F(x)G(x),G(x),xF(x)xF(x)yG(yyG(y)等都是等都是p pq q的代换实的代换实例，而例，而 x(F(x)x(F(x)G(x)G(x)等不是等不是p pq q的代换实例。的代换实例。定理定理4.24.2：重言式的代换实例都是永真式，矛盾式的代换重言式的代换实例都是永真式，矛盾式的代换 实例都是矛盾式。实例都是矛盾式。例例4.9 4.9 判断下列公式中，哪些是永真式，哪些是矛盾式？判断下列公式中，哪些是永真式，哪些是矛盾式？（1 1）x x(F F(x x)

40、G G(x x)（2 2）x x(F F(x x)G G(x x)（3 3）xFxF(x x)(x x yGyG(x x,y y)xFxF(x x)（4 4）(xFxF(x x)yGyG(y y)yGyG(y y)解解:(1):(1)x x(F F(x x)G G(x x)解释解释1 1：个体域为实数集合：个体域为实数集合R R，F(x)F(x)：x x是整数，是整数，G(x)G(x)：x x是有理是有理数，因此公式真值为真。数，因此公式真值为真。解释解释2 2：个体域为实数集合：个体域为实数集合R R，F(x)F(x)：x x是无理数，是无理数，G(x)G(x)：x x能表能表示成分数，因此

41、公式真值为假。示成分数，因此公式真值为假。所以公式为非永真式的可满足式。所以公式为非永真式的可满足式。例题例题例题例题4.94.94.94.9例题例题例题例题4.94.94.94.9（2 2）x x(F F(x x)G G(x x)公式为非永真式的可满足式。公式为非永真式的可满足式。（3 3）xFxF(x x)(x x yGyG(x x,y y)xFxF(x x)为为p p(q qp p)（重言式）的代换实例，故为永真式。重言式）的代换实例，故为永真式。（4 4）(xFxF(x x)yGyG(y y)yGyG(y y)为为(p pq q)q q（矛盾式）的代换实例，故为永假式。矛盾式）的代换实

42、例，故为永假式。例题例题例题例题例例4.104.10 判断下列公式的类型。判断下列公式的类型。(1)(1)xF(xxF(x)xF(xxF(x)(2)(2)x x yF(x,yyF(x,y)x x yF(x,yyF(x,y)(3)(3)x(F(x)G(xx(F(x)G(x)yG(yyG(y)解解 记记(1)(1)，(2)(2)，(3)(3)中的公式分别为中的公式分别为A,B,CA,B,C。(1)(1)设设I I为任意一个解释，个体域为为任意一个解释，个体域为D D。若存在若存在x x0 0D D，使得使得F(xF(x0 0)为假，则为假，则 xF(xxF(x)为假，所以为假，所以A A的前的前件

43、为假，故件为假，故A A为真。为真。若对于任意若对于任意x xD D，F(xF(x)均为真，则均为真，则 xF(x)xF(x)，xF(xxF(x)都为真，都为真，从而从而A A为真。为真。所以在所以在I I下下A A为真。由为真。由I I的任意性可知，的任意性可知，A A是永真式。是永真式。例题例题例题例题(2)(2)x x yF(x,yyF(x,y)x x yF(x,yyF(x,y)取解释取解释I I：个体域为自然数集合个体域为自然数集合N N，F(x,yF(x,y)为为x xy y。在在I I下下B B的前件与后件均为真，所以的前件与后件均为真，所以B B为真。这说明为真。这说明B B不是

44、矛盾不是矛盾式。（式。（在在 x x yF(x,yyF(x,y)中，中，x x0 0）再取再取II：个体域仍然为个体域仍然为N N，F(x,yF(x,y)为为x=yx=y。在在II下，下，B B的前件真而后件假，所以的前件真而后件假，所以B B为假。这说明为假。这说明B B不是永不是永真式。真式。故故B B是非永真式的可满足式。是非永真式的可满足式。(3)(3)x(F(x)G(xx(F(x)G(x)yG(yyG(y)C C也是非永真式的可满足式。也是非永真式的可满足式。小节结束小节结束本章主要内容本章主要内容本章主要内容本章主要内容q个体词个体词个体常项个体常项个体变项个体变项个体域个体域全总

45、个体域全总个体域q谓词谓词谓词常项谓词常项谓词变项谓词变项n(n1)n(n1)元谓词元谓词特性谓词特性谓词q量词量词全称量词全称量词存在量词存在量词本章主要内容本章主要内容本章主要内容本章主要内容q一阶逻辑中命题符号化一阶逻辑中命题符号化q一阶逻辑公式一阶逻辑公式原子公式原子公式合式公式（或公式）合式公式（或公式）闭式闭式q解释解释q一阶逻辑公式的分类一阶逻辑公式的分类逻辑有效式（或永真式）逻辑有效式（或永真式）矛盾式（或永假式）矛盾式（或永假式）可满足式可满足式本章学习要求本章学习要求本章学习要求本章学习要求q要求准确地将给出的命题符号化：要求准确地将给出的命题符号化：当给定个体域时，在给定

46、个体域内将命题符号化。当给定个体域时，在给定个体域内将命题符号化。当没给定个体域时，应在全总个体域内符号化。当没给定个体域时，应在全总个体域内符号化。在符号化时，当引入特性时，注意全称量词与蕴含联结词的在符号化时，当引入特性时，注意全称量词与蕴含联结词的搭配，存在量词与合取联结词的搭配。搭配，存在量词与合取联结词的搭配。q深刻理解逻辑有效式、矛盾式、可满足式的概念。深刻理解逻辑有效式、矛盾式、可满足式的概念。q记住闭式的性质：在任何解释下均为命题。记住闭式的性质：在任何解释下均为命题。q对给定的解释，会判别公式的真值或不能确定真值。对给定的解释，会判别公式的真值或不能确定真值。小节结束小节结束

47、习题选讲习题选讲习题选讲习题选讲命命命命题符号化题符号化题符号化题符号化 在一阶逻辑中将下列命题符号化。在一阶逻辑中将下列命题符号化。（1 1）每个人都有心脏。每个人都有心脏。（2 2）有的狗会飞。有的狗会飞。（3 3）没有不犯错误的人。没有不犯错误的人。（4 4）发光的不都是金子。发光的不都是金子。习题选讲习题选讲习题选讲习题选讲命命命命题符号化题符号化题符号化题符号化解：由于没指出个体域，故用全总个体域解：由于没指出个体域，故用全总个体域（1 1）每个人都有心脏。）每个人都有心脏。本命题的含义：对于每一个本命题的含义：对于每一个x x，如果如果x x是人，则是人，则x x有心脏。有心脏。因

48、因而而应应首首先先从从宇宇宙宙间间的的一一切切事事物物中中，将将人人分分离离出出来来，这这就就必必须须引入特性谓词。引入特性谓词。令令M(x):xM(x):x是人，是人，H(x):xH(x):x有心脏。有心脏。命题符号化为：命题符号化为：x(M(x)x(M(x)H(xH(x)习题选讲习题选讲习题选讲习题选讲命命命命题符号化题符号化题符号化题符号化（2 2）有的狗会飞。）有的狗会飞。命题的意思是：存在一个命题的意思是：存在一个x x，x x是狗，并且是狗，并且x x会飞。会飞。设设D(x)D(x)：x x是狗，是狗，F(x)F(x)：x x会飞。会飞。命题符号化为：命题符号化为：x(D(x)x(

49、D(x)F(xF(x)习题选讲习题选讲习题选讲习题选讲命命命命题符号化题符号化题符号化题符号化（3 3）没有不犯错误的人。）没有不犯错误的人。命题的意思是：命题的意思是：存在存在(有有)不犯错误的人是不可能的不犯错误的人是不可能的设设 M(xM(x):x):x是人，是人，F(x):xF(x):x犯错误犯错误命题符号化为命题符号化为：x(M(x)F(xx(M(x)F(x)只要是人，必然犯错误只要是人，必然犯错误命题符号化为：命题符号化为：x(M(xx(M(x)F(xF(x)习题选讲习题选讲习题选讲习题选讲命命命命题符号化题符号化题符号化题符号化（4 4）发光的不都是金子。）发光的不都是金子。命题的意思是：命题的意思是：不是发光的东西都是金子。不是发光的东西都是金子。存在着发光的东西不是金子。存在着发光的东西不是金子。设设 L(x)L(x)：x x是发光的东西，是发光的东西，G(x)G(x)：x x是金子。是金子。命题符号化为命题符号化为 x x(L(x)G(xL(x)G(x)x(L(x)x(L(x)G(xG(x)作业作业作业作业习题四习题四：2、3、4、5、9、10、14结束结束