《离散数学第4章_高等教育出版社_屈婉玲_ (2)》由会员分享，可在线阅读，更多相关《离散数学第4章_高等教育出版社_屈婉玲_ (2)（28页珍藏版）》请在金锄头文库上搜索。
1、第四章第四章 一阶逻辑基本概念一阶逻辑基本概念 命题逻辑具有一定的局限性，例如：命题逻辑具有一定的局限性，例如：凡偶数都能被凡偶数都能被2整除整除. 6是偶数是偶数. 所以，所以，6能被能被2整除整除.问：如何符号化？问：如何符号化？解决方法：引入量词解决方法：引入量词1第四章第四章 一阶逻辑基本概念一阶逻辑基本概念引入量词，以期达到表达出个体与总体之间的内在联系和数引入量词，以期达到表达出个体与总体之间的内在联系和数量关系，这是量关系，这是 一阶逻辑一阶逻辑 所研究的内容。所研究的内容。24.1 一阶逻辑命题符号化一阶逻辑命题符号化一阶逻辑命题符号化的一阶逻辑命题符号化的3个要素：个要素：1
2、.个体词：指研究对象中可以独立存在的具体的或抽象的个体词：指研究对象中可以独立存在的具体的或抽象的客体，一般用小写字母表示。例如：小王，小李，中国，客体，一般用小写字母表示。例如：小王，小李，中国，3 等。特别地，将表示具体或特定的客体的个体词称作个等。特别地，将表示具体或特定的客体的个体词称作个体常项，抽象或泛指的个体词称为个体变项。体常项，抽象或泛指的个体词称为个体变项。2. 并称个体变项的取值范围为并称个体变项的取值范围为 个体域。如个体域。如N，R等。等。 特特别地，宇宙间一切事物组成的个体域称为别地，宇宙间一切事物组成的个体域称为 全总个体域。全总个体域。34.1 一阶逻辑命题符号化
3、一阶逻辑命题符号化一阶逻辑命题符号化的一阶逻辑命题符号化的3个要素：个要素：2.谓词：用来刻画个体词性质及个体词之间相互关系的词，谓词：用来刻画个体词性质及个体词之间相互关系的词，常用大写字母表示。常用大写字母表示。3. 例如：例如： x是有理数。是有理数。4. x是个体变项，是个体变项，“是有理数是有理数”是谓词，记为是谓词，记为G。5. 这个命题可表成这个命题可表成G(x).6. 小王与小李同岁。小王与小李同岁。7. 小王，小李都是个体常项，小王，小李都是个体常项，“与与同岁同岁”是谓是谓8. 词，记为词，记为H，这个命题可以符号化为，这个命题可以符号化为H(a,b)。44.1 一阶逻辑命
4、题符号化一阶逻辑命题符号化同个体词一样，谓词也有常项和变项之分。表示具体性质或同个体词一样，谓词也有常项和变项之分。表示具体性质或关系的谓词称为谓词常项，表示抽象或泛指的性质或关关系的谓词称为谓词常项，表示抽象或泛指的性质或关系的谓词称为谓词变项。系的谓词称为谓词变项。一般地，含一般地，含n个命题变项的谓词个命题变项的谓词P称作称作n元谓词，将不带个体元谓词，将不带个体变项的谓词称为变项的谓词称为0元谓词。元谓词。例例4.1 将下列命题在一阶逻辑中用将下列命题在一阶逻辑中用0元谓词符号化，并讨论他元谓词符号化，并讨论他们的真值：们的真值： 只有只有2是素数，是素数，4才是素数。才是素数。54.
5、1 一阶逻辑命题符号化一阶逻辑命题符号化 只有只有2是素数，是素数，4才是素数。才是素数。解：设解：设1元谓词元谓词F(x)：x是素数，命题可以符号化为是素数，命题可以符号化为 F(4) F(2) 由于此蕴含式前件为假，所以命题为真。由于此蕴含式前件为假，所以命题为真。64.1 一阶逻辑命题符号化一阶逻辑命题符号化3. 量词：表示个体常项或变项之间数量关系的词称为量词。量词：表示个体常项或变项之间数量关系的词称为量词。有两种量词：有两种量词：（1）全称量词：）全称量词：“一切的一切的”，“所有的所有的”，“每一个每一个”，“任意的任意的”，“凡凡”，“都都”等词统称为全称量词，用等词统称为全称
6、量词，用符号符号 表示，表示，x表示个体域里的所有个体表示个体域里的所有个体x，其中个体，其中个体域是事先约定的。例如：域是事先约定的。例如：xF(x)表示个体域里所有个体表示个体域里所有个体x都有性质都有性质F， x yG(x,y)表示个体域里所有的个体表示个体域里所有的个体x和和y有关系有关系G，其中，其中F和和G是谓词。是谓词。74.1 一阶逻辑命题符号化一阶逻辑命题符号化 （2）存在量词：日常生活和数学中常用的）存在量词：日常生活和数学中常用的“存在存在”，“有一个有一个”,“有的有的”，“至少至少 有一个有一个”等词统称为等词统称为 存在存在量词，用符号量词，用符号 表示。表示。x表
7、示个体域里有一个个体表示个体域里有一个个体x。例如，用。例如，用xF(x)表示在个表示在个体域里存在个体体域里存在个体x具有性质具有性质F， x yG(x,y)表示在个体表示在个体域里存在个体域里存在个体x和和y有关系有关系G。注：全称量词和存在量词可以联合使用，如注：全称量词和存在量词可以联合使用，如xyG(x,y)表表示对个体域里所有个体示对个体域里所有个体x，存在，存在y使得使得x和和y有关系有关系G；84.1 一阶逻辑命题符号化一阶逻辑命题符号化而，而，x y G(x,y)表示对个体域里存在个体表示对个体域里存在个体x使得所有的个使得所有的个体体y有关系有关系G。例：例：4.2 P57
8、4.594.1 一阶逻辑命题符号化一阶逻辑命题符号化例：例：4.2 在个体域分别限制为在个体域分别限制为(a)和和(b)条件时，将下面两个条件时，将下面两个命题符号化：命题符号化：(1)凡人都呼吸凡人都呼吸(2)有的人用左手写字有的人用左手写字(3)其中其中 (a) 个体域个体域D1为人类集合；为人类集合；(4) (b) 个体域个体域D2为全总个体域为全总个体域(5)解解104.1 一阶逻辑命题符号化一阶逻辑命题符号化例：例：4.2 在个体域分别限制为在个体域分别限制为(a)和和(b)条件时，将下面两个条件时，将下面两个命题符号化：命题符号化：(1)凡人都呼吸凡人都呼吸(2)有的人用左手写字有
9、的人用左手写字(3)其中其中 (a) 个体域个体域D1为人类集合；为人类集合；(4) (b) 个体域个体域D2为全总个体域为全总个体域(5)解解 （a）令）令 F(x):x呼吸。呼吸。G(x):x用左手写字。用左手写字。(6) 在在D1中除人外，再无别的东西，因而中除人外，再无别的东西，因而(7)(1)符号化为符号化为 114.1 一阶逻辑命题符号化一阶逻辑命题符号化(1)符号化为符号化为x F(x) (2)符号化为符号化为 x G(x)124.1 一阶逻辑命题符号化一阶逻辑命题符号化例：例：4.2 在个体域分别限制为在个体域分别限制为(a)和和(b)条件时，将下面两个命题符号化：条件时，将下
10、面两个命题符号化：(1)凡人都呼吸凡人都呼吸(2)有的人用左手写字有的人用左手写字(3)其中其中 (a) 个体域个体域D1为人类集合；为人类集合；(4) (b) 个体域个体域D2为全总个体域为全总个体域(5)解解 （b）D2中除有人外，还有万物，因而在符号化时必须考虑将人中除有人外，还有万物，因而在符号化时必须考虑将人先分离出来。为此引入谓词先分离出来。为此引入谓词 M(x):x是人。是人。(6)令令 F(x):x呼吸。呼吸。G(x):x用左手写字。用左手写字。(7) (1)符号化为符号化为 x （M(x) F(x)）(8) (2)符号化为符号化为 x （M(x) G(x)）(9)注：常见错误
11、注：常见错误 P5713类似的，请看课本类似的，请看课本 例例4.3 P57，及，及 例例4.4-4.5144.1 一阶逻辑命题符号化一阶逻辑命题符号化对于含对于含n元谓词的命题，在符号化时应注意以下几点：元谓词的命题，在符号化时应注意以下几点：（1）分析命题中表示性质和关系的谓词，分别符号化为一元）分析命题中表示性质和关系的谓词，分别符号化为一元和和n元谓词。元谓词。（2）根据命题的实际意义选用全称量词或存在量词。）根据命题的实际意义选用全称量词或存在量词。（3）一般来说，多个量词同时出现时，他们的次序不能随意）一般来说，多个量词同时出现时，他们的次序不能随意调换。调换。 例如：考虑个体域为
12、实数集，例如：考虑个体域为实数集，H(x,y)表示表示x+y=10，则命，则命题题“对于任意的对于任意的x，都存在，都存在y，使得，使得x+y=10”的符号化形式的符号化形式为为 x y H(x,y) 此命题显然为真命题。但是改变两个量词的顺序，得此命题显然为真命题。但是改变两个量词的顺序，得 y x H(x,y) 意思是意思是“存在存在y使得对所有使得对所有x都有都有x+y=10”，假命题，假命题154.1 一阶逻辑命题符号化一阶逻辑命题符号化对于含对于含n元谓词的命题，在符号化时应注意以下几点：元谓词的命题，在符号化时应注意以下几点：（4）命题的符号化形式不惟一。）命题的符号化形式不惟一。
13、 例例4.5（3）16第四章第四章 一阶逻辑基本概念一阶逻辑基本概念凡偶数都能被凡偶数都能被2整除整除. 6是偶数是偶数. 所以，所以，6能被能被2整除整除.问：如何符号化？问：如何符号化？(x （M(x) F(x)）) M(6) F(6)174.2 一阶逻辑公式及其解释一阶逻辑公式及其解释首先给出首先给出 一阶语言一阶语言 的概念。所谓一阶语言是用于一阶逻辑的的概念。所谓一阶语言是用于一阶逻辑的形式语言，而一阶逻辑是建立在一阶语言上的逻辑体系。形式语言，而一阶逻辑是建立在一阶语言上的逻辑体系。一阶语言本身是由抽象符号构成的，可以根据需要被解释成一阶语言本身是由抽象符号构成的，可以根据需要被解
14、释成各种具体的含义。各种具体的含义。 我们称个体常项符号、函数符号和谓词符号为我们称个体常项符号、函数符号和谓词符号为 非逻辑符非逻辑符号号，称个体变项符号、量词符号、联接词符号和括号与逗，称个体变项符号、量词符号、联接词符号和括号与逗号为号为 逻辑符号逻辑符号。定义定义4.1 设设L是一个非逻辑符号集合，由是一个非逻辑符号集合，由L生成的一阶语言生成的一阶语言的字母表包括下述符号：的字母表包括下述符号：184.2 一阶逻辑公式及其解释一阶逻辑公式及其解释 定义定义4.1 设设L是一个非逻辑符号集合，由是一个非逻辑符号集合，由L生成的一阶语言生成的一阶语言的的字母表字母表包括下述符号：包括下述
15、符号： 非逻辑符号：非逻辑符号： 1. L中的个体常项符号，常用中的个体常项符号，常用a,b,c或或ai，bi，ci 表示表示 2. L中的函数符号，常用中的函数符号，常用 f, g, h或或fi,gi,hi表示表示 3. L中的谓词符号，常用中的谓词符号，常用 F, G, H或或Fi,Gi,Hi表示表示 逻辑符号：逻辑符号： 4. 个体变项符号：个体变项符号：x,y,z或或xi，yi，zi 5. 量词符号：量词符号： 6. 联接词符号：常用的联接词符号：常用的 5种（合取、析取等）种（合取、析取等） 7. 括号与逗号：括号与逗号： （,）,.194.2 一阶逻辑公式及其解释一阶逻辑公式及其解
16、释 定义定义4.2 一阶语言一阶语言的的项项定义如下：定义如下： 1. 个体常项符号和个体变项符号是个体常项符号和个体变项符号是 项项 2. 若若(x1,x2,xn)是是n元函数符号，元函数符号， t1,t2,tn 是是n个个项，则项，则(t1,t2,tn )是项是项 3. 所有的项都是有限次使用所有的项都是有限次使用1.2. 得到的。得到的。定义定义4.3 设设R(x1,x2,xn)是是的的n元谓词符号，元谓词符号， t1,t2,tn 是是的的n个项，则称个项，则称(t1,t2,tn )是是的的原子公式原子公式： 204.2 一阶逻辑公式及其解释一阶逻辑公式及其解释 定义定义4.4 的的合式
17、公式合式公式 定义如下：定义如下： 1.原子公式是合式公式原子公式是合式公式 2. 若若A是合式公式，则是合式公式，则 A是合式公式是合式公式 3. 若若A,B是合式公式，则是合式公式，则A B, A B, AB, AB也是也是合合 式公式。式公式。 4. 若若A 是合式公式，则是合式公式，则 xA，x A也是合式公式。也是合式公式。 5. 只有有限次地应用（只有有限次地应用（1）（4）构成的符号串才是合式）构成的符号串才是合式公式公式 注：注：A，B是元语言符号，表示任意的合式公式。同时，不同的一阶语言使用不同的非逻辑集合是元语言符号，表示任意的合式公式。同时，不同的一阶语言使用不同的非逻辑
18、集合L，但他们，但他们构造合式公式的规则是一样的。一阶逻辑研究一阶语言的一般性质，而不是针对某个特定的一阶语构造合式公式的规则是一样的。一阶逻辑研究一阶语言的一般性质，而不是针对某个特定的一阶语言。言。214.2 一阶逻辑公式及其解释一阶逻辑公式及其解释 定义定义4.5 在公式在公式 xA和和x A中，称中，称x为为 指导变元指导变元，A为量词的为量词的辖域辖域。在。在 x和和x 的辖域中，的辖域中，x的所有出现都称为的所有出现都称为 约束出约束出现现，A中不是约束出现的其他变项均称为中不是约束出现的其他变项均称为 自由出现自由出现。 见见 例例4.6 224.2 一阶逻辑公式及其解释一阶逻辑
19、公式及其解释 为方便起见，用为方便起见，用A(x1,x2,xn)表示含表示含x1,x2,xn 自由出现自由出现的公式，的公式， 并用并用 表示表示任意的量词。任意的量词。例如：例如： x1A(x1,x2,xn) 是含是含x2,xn自由出现的公式，可自由出现的公式，可记为记为A1(x2,xn) 。类似的，。类似的， x2 x1A(x1,x2,xn) 可可记为记为A2(x3,xn) 234.2 一阶逻辑公式及其解释一阶逻辑公式及其解释 定义定义4.6 假设假设A是任意的公式，若是任意的公式，若A中不含自由出现的个体变中不含自由出现的个体变项，则称项，则称A为为 封闭的公式封闭的公式，简称，简称 闭
20、式闭式。例例4.7 （1）（）（2） 244.2 一阶逻辑公式及其解释一阶逻辑公式及其解释 在例在例4.7 中队公式中的变项的指定称为解释，解释的定义如下中队公式中的变项的指定称为解释，解释的定义如下：定义定义4.7 假设假设是由是由L生成的一阶语言，生成的一阶语言，的的解释解释I由下面由下面4部分组成：部分组成：1.非空个体域非空个体域D12.对每一个个体常项符号对每一个个体常项符号a L，有一个，有一个a DI,称称a为为a在在I中的解释中的解释。3.对每一个对每一个n元函数符号元函数符号f L，有一个，有一个DI上的上的n元函数元函数f： DIn DI,称称f为为f在在I中的解释。中的解
21、释。4.对每一个对每一个n元谓词符号元谓词符号F L，有一个，有一个DI上的上的n元谓词常项元谓词常项F，称，称F为为F在在I中的解释。中的解释。 254.2 一阶逻辑公式及其解释一阶逻辑公式及其解释设公式设公式A，规定：在解释，规定：在解释I下，下，1.取个体域取个体域 DI2.若若A中含个体常项符号中含个体常项符号a就将它替换成就将它替换成a3.若若A中含函数符号中含函数符号f就将它替换成就将它替换成f4.若若A中含谓词符号中含谓词符号F就将它替换成就将它替换成F5.把这样所得到的公式记作把这样所得到的公式记作A，称，称A为为A在在I下的解释，或下的解释，或A在在I下被解释称下被解释称A。
22、6.见例见例 4.8264.2 一阶逻辑公式及其解释一阶逻辑公式及其解释定理定理4.1 封闭的公式在任何解释下都变成命题。封闭的公式在任何解释下都变成命题。注：不是闭式的公式在某些解释下也可能变成命题。例注：不是闭式的公式在某些解释下也可能变成命题。例4.8中中的（的（5）。）。274.2 一阶逻辑公式及其解释一阶逻辑公式及其解释为了区别不同的公式类型，定义如下：为了区别不同的公式类型，定义如下：定义定义 4.8 设设A为一公式，若为一公式，若A在任何解释下均为真，则称在任何解释下均为真，则称A 为为 永真式（或称逻辑有效式）。若永真式（或称逻辑有效式）。若A在任何解释下均为假，在任何解释下均为假，则称则称A为矛盾式（或永假式）。若至少存在一个解释使为矛盾式（或永假式）。若至少存在一个解释使A为为真，则称真，则称A为可满足式。为可满足式。28
