离散数学第4章-高等教育出版社-屈婉玲-

1第四章一阶逻辑基本概念命题逻辑具有一定的局限性，例如：凡偶数都能被2整除.6是偶数.所以，6能被2整除.问：如何符号化？解决方法：引入量词2第四章一阶逻辑基本概念引入量词，以期达到表达出个体与总体之间的内在联系和数量关系，这是一阶逻辑所研究的内容。34.1一阶逻辑命题符号化一阶逻辑命题符号化的3个要素：1.个体词：指研究对象中可以独立存在的具体的或抽象的客体，一般用小写字母表示。例如：小王，小李，中国，3等。特别地，将表示具体或特定的客体的个体词称作个体常项，抽象或泛指的个体词称为个体变项。并称个体变项的取值范围为个体域。如N，R等。特别地，宇宙间一切事物组成的个体域称为全总个体域。44.1一阶逻辑命题符号化一阶逻辑命题符号化的3个要素：2.谓词：用来刻画个体词性质及个体词之间相互关系的词，常用大写字母表示。例如：x是有理数。x是个体变项，“…是有理数”是谓词，记为G。这个命题可表成G(x).小王与小李同岁。小王，小李都是个体常项，“…与…同岁”是谓词，记为H，这个命题可以符号化为H(a,b)。54.1一阶逻辑命题符号化同个体词一样，谓词也有常项和变项之分。表示具体性质或关系的谓词称为谓词常项，表示抽象或泛指的性质或关系的谓词称为谓词变项。一般地，含n个命题变项的谓词P称作n元谓词，将不带个体变项的谓词称为0元谓词。例4.1将下列命题在一阶逻辑中用0元谓词符号化，并讨论他们的真值：只有2是素数，4才是素数。64.1一阶逻辑命题符号化只有2是素数，4才是素数。解：设1元谓词F(x)：x是素数，命题可以符号化为F(4)→F(2)由于此蕴含式前件为假，所以命题为真。74.1一阶逻辑命题符号化3.量词：表示个体常项或变项之间数量关系的词称为量词。有两种量词：（1）全称量词：“一切的”，“所有的”，“每一个”，“任意的”，“凡”，“都”等词统称为全称量词，用符号∀表示，∀x表示个体域里的所有个体x，其中个体域是事先约定的。例如：∀xF(x)表示个体域里所有个体x都有性质F，∀x∀yG(x,y)表示个体域里所有的个体x和y有关系G，其中F和G是谓词。84.1一阶逻辑命题符号化（2）存在量词：日常生活和数学中常用的“存在”，“有一个”,“有的”，“至少有一个”等词统称为存在量词，用符号∃表示。∃x表示个体域里有一个个体x。例如，用∃xF(x)表示在个体域里存在个体x具有性质F，∃x∃yG(x,y)表示在个体域里存在个体x和y有关系G。注：全称量词和存在量词可以联合使用，如∀x∃yG(x,y)表示对个体域里所有个体x，存在y使得x和y有关系G；94.1一阶逻辑命题符号化而，∃x∀yG(x,y)表示对个体域里存在个体x使得所有的个体y有关系G。例：4.2P57——4.5104.1一阶逻辑命题符号化例：4.2在个体域分别限制为(a)和(b)条件时，将下面两个命题符号化：(1)凡人都呼吸(2)有的人用左手写字其中(a)个体域D1为人类集合；(b)个体域D2为全总个体域解114.1一阶逻辑命题符号化例：4.2在个体域分别限制为(a)和(b)条件时，将下面两个命题符号化：(1)凡人都呼吸(2)有的人用左手写字其中(a)个体域D1为人类集合；(b)个体域D2为全总个体域解（a）令F(x):x呼吸。G(x):x用左手写字。在D1中除人外，再无别的东西，因而(1)符号化为124.1一阶逻辑命题符号化(1)符号化为∀xF(x)(2)符号化为∃xG(x)134.1一阶逻辑命题符号化例：4.2在个体域分别限制为(a)和(b)条件时，将下面两个命题符号化：(1)凡人都呼吸(2)有的人用左手写字其中(a)个体域D1为人类集合；(b)个体域D2为全总个体域解（b）D2中除有人外，还有万物，因而在符号化时必须考虑将人先分离出来。为此引入谓词M(x):x是人。令F(x):x呼吸。G(x):x用左手写字。(1)符号化为∀x（M(x)→F(x)）(2)符号化为∃x（M(x)G(x)）注：常见错误P5714类似的，请看课本例4.3P57，及例4.4-4.5154.1一阶逻辑命题符号化对于含n元谓词的命题，在符号化时应注意以下几点：（1）分析命题中表示性质和关系的谓词，分别符号化为一元和n元谓词。（2）根据命题的实际意义选用全称量词或存在量词。（3）一般来说，多个量词同时出现时，他们的次序不能随意调换。例如：考虑个体域为实数集，H(x,y)表示x+y=10，则命题“对于任意的x，都存在y，使得x+y=10”的符号化形式为∀x∃yH(x,y)此命题显然为真命题。但是改变两个量词的顺序，得∃y∀xH(x,y)意思是“存在y使得对所有x都有x+y=10”，假命题164.1一阶逻辑命题符号化对于含n元谓词的命题，在符号化时应注意以下几点：（4）命题的符号化形式不惟一。例4.5（3）17第四章一阶逻辑基本概念凡偶数都能被2整除.6是偶数.所以，6能被2整除.问：如何符号化？(∀x（M(x)→F(x)）)M(6)→F(6)184.2一阶逻辑公式及其解释首先给出一阶语言的概念。所谓一阶语言是用于一阶逻辑的形式语言，而一阶逻辑是建立在一阶语言上的逻辑体系。一阶语言本身是由抽象符号构成的，可以根据需要被解释成各种具体的含义。我们称个体常项符号、函数符号和谓词符号为非逻辑符号，称个体变项符号、量词符号、联接词符号和括号与逗号为逻辑符号。定义4.1设L是一个非逻辑符号集合，由L生成的一阶语言Ｌ的字母表包括下述符号：194.2一阶逻辑公式及其解释定义4.1设L是一个非逻辑符号集合，由L生成的一阶语言Ｌ的字母表包括下述符号：非逻辑符号：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.括号与逗号：（,）,,.204.2一阶逻辑公式及其解释定义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)是Ｌ的原子公式：214.2一阶逻辑公式及其解释定义4.4Ｌ的合式公式定义如下：1.原子公式是合式公式2.若A是合式公式，则A是合式公式3.若A,B是合式公式，则AB,AB,AB,AB也是合式公式。4.若A是合式公式，则∀xA，∃xA也是合式公式。5.只有有限次地应用（1）~（4）构成的符号串才是合式公式注：A，B是元语言符号，表示任意的合式公式。同时，不同的一阶语言使用不同的非逻辑集合L，但他们构造合式公式的规则是一样的。一阶逻辑研究一阶语言的一般性质，而不是针对某个特定的一阶语言。224.2一阶逻辑公式及其解释定义4.5在公式∀xA和∃xA中，称x为指导变元，A为量词的辖域。在∀x和∃x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其他变项均称为自由出现。见例4.6234.2一阶逻辑公式及其解释为方便起见，用A(x1,x2,…,xn)表示含x1,x2,…,xn自由出现的公式，并用△表示任意的量词。例如：△x1A(x1,x2,…,xn)是含x2,…,xn自由出现的公式，可记为A1(x2,…,xn)。类似的，△x2△x1A(x1,x2,…,xn)可记为A2(x3,…,xn)244.2一阶逻辑公式及其解释定义4.6假设A是任意的公式，若A中不含自由出现的个体变项，则称A为封闭的公式，简称闭式。例4.7（1）（2）254.2一阶逻辑公式及其解释在例4.7中队公式中的变项的指定称为解释，解释的定义如下：定义4.7假设Ｌ是由L生成的一阶语言，Ｌ的解释I由下面4部分组成：1.非空个体域D12.对每一个个体常项符号a∈L，有一个a’∈DI,称a’为a在I中的解释。3.对每一个n元函数符号f∈L，有一个DI上的n元函数f’：DI^n→DI,称f’为f在I中的解释。4.对每一个n元谓词符号F∈L，有一个DI上的n元谓词常项F’，称F’为F在I中的解释。264.2一阶逻辑公式及其解释设公式A，规定：在解释I下，1.取个体域DI2.若A中含个体常项符号a就将它替换成a’3.若A中含函数符号f就将它替换成f’4.若A中含谓词符号F就将它替换成F’把这样所得到的公式记作A’，称A’为A在I下的解释，或A在I下被解释称A’。见例4.8274.2一阶逻辑公式及其解释定理4.1封闭的公式在任何解释下都变成命题。注：不是闭式的公式在某些解释下也可能变成命题。例4.8中的（5）。284.2一阶逻辑公式及其解释为了区别不同的公式类型，定义如下：定义4.8设A为一公式，若A在任何解释下均为真，则称A为永真式（或称逻辑有效式）。若A在任何解释下均为假，则称A为矛盾式（或永假式）。若至少存在一个解释使A为真，则称A为可满足式。