2-1-aolm-离散数学

《2-1-aolm-离散数学》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第二章谓词逻辑历史使人聪明，诗歌使人机智，数学使人精细，哲学使人深邃，道德使人严肃，逻辑与修辞使人善辩。BaconFrancis命题逻辑研究的基本单位是原子命题，不再对原子命题进行分解，也不再对原子命题的内部结构作进一步的分析，故其应用具有一定的局限性。解决问题：引入了谓词和量词等概念，形成数理逻辑另外一个重要的基础部分——一阶谓词逻辑。一阶谓词逻辑：称为一阶谓词演算、狭谓词逻辑、初等逻辑、量词理论等，一般简称为谓词逻辑。主要内容：基本概念：谓词、量词、谓词公式、命题符号化。量词的个体变元的出现形式：自由出

2、现和约束出现。谓词公式之间的等价和蕴涵关系；谓词公式的标准形式——前缀范式，即谓词演算推理中的规范形式。2.1谓词和量词2.1.1谓词的概念命题逻辑的特点：在命题逻辑中，基本组成单位是原子命题，并把它看作不可再分解的，而不涉及其内部的逻辑结构。命题逻辑的缺点：（1）它不能揭示某些有效的论证；（2）无法将具有某种共同属性的命题显示出来。（1）它不能揭示某些有效的论证；【例2.1】所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。这是简单而有名的苏格拉底三段论，直观地，这是一个有效的论证，但它却无法用命题

3、逻辑予以推证。（2）无法将具有某种共同属性的命题显示出来。【例2.2】设P表示命题：张辉是工人Q表示命题：李明是工人仅仅从命题符号P和Q看不出张辉和李明都是工人这一特性。定义2.1一个原子命题用一个谓词和n个有次序的个体常元a1,a2,…,an表示成P(a1,a2,…,an)的形式，称为该原子命题的谓词形式。在定义2.1中，若n＝0，则P称为零元谓词，即P本身就是一个命题，若n＝1，则称P是一元谓词，若n＝2，则称P是二元谓词，以此类推。显然，单独一个谓词不是完整的命题。且P(a1,a2,…,ai,…,aj

4、,…,an)(1≤i＜j≤n)与P(a1,a2,…,aj,…,ai,…,an)是不同的命题。定义2.2若表达式P(a1,a2,…,an)中，P是某个命题，a1,a2,…,an是个体变元，则P(a1,a2,…,an)称为简单命题函数。定义2.3由一个或多个简单命题函数以及逻辑联结词组合而成的表达式称为复合命题函数。命题函数：简单命题函数、复合命题函数。命题函数不是命题！只有当其中的个体变元都用具体的个体取代后才成为命题。并且个体变元在哪些范围内取特定的值，对是否成为命题及命题的真值极有影响。个体域：个体变元的

5、取值范围，又称为论域。个体域可以是有限的，也可以是无限的，全总个体域：把各种个体域综合在一起作为论述范围内的域。全总个体域是无限的。【例2.3】试将下列命题符号化：2是质数平方为1的数不是实数6能被2整除解：(1)用a表示2，A表示“是质数”，则命题“2是质数”，符号化为：A(a)。(2)用a表示平方为1的数，A表示“不是实数”，则命题“平方为1的数不是实数”，符号化为：A(a)。(3)用a,b分别表示6,2，A表示“整除”，则命题“6能被2整除”符号化为：A(6,2)。【例2.4】若R(x)表示“a

6、是大学生”，如果x的讨论范围为某大学里的所有在校学生，则R(x)是永真式。若x的讨论范围为某中学里的所有在校学生，则R(x)是永假式。若x的讨论范围为一个剧场中的观众，观众中有大学生也有非大学生，那么，对某些观众而言，R(x)为真，对另一些观众而言，R(x)为假。【例2.5】试将“所有的人都是要死的”这一命题符号化。在此例中，怎么表达“所有的”这一概念呢？显然，仅仅用目前所讨论的知识是不行的，在此引入量词来刻划“所有的”这一概念。2.1.2全称量词和存在量词“对一切x”称为全称量词，记为(x)（是All

7、中第一个字母的倒写）。[例2.5]若用A表示“是人”、用B表示“要死的”，则中的命题可符号化为:(x)(A(x)B(x))“(x)”还可表示日常语言中的“凡x”、“对每一个x”、“对所有的x”等用语。另外还有一类量词，用来表达“有x”、“至少有一个x”、“存在x”等概念，这类量词称为存在量词，记为(x)（是Exist中第一个字母的反写）。【例2.6】试将命题“存在一个数满足要求”符号化。解：若A(x)表示“x是一个数”，B(x)表示“x满足要求”，则命题“存在一个数满足要求”符号化为：(x)(A

8、(x)∧B(x))。在命题符号化的过程中需要注意以下三点：（1）“所有的…是…”应表示为：(x)(A(x)B(x))，而不是：(x)(A(x)∧B(x))。这是因为量化断言的真假与个体域有关。这里事先并未规定个体域是什么，因此可以认为x的取值范围是一切事物，所以要表达“所有的…是…”，必先假设x具有性质A，这就是(x)(A(x)B(x))的形式，不然就不能忠实于原命题。例：“每一个有理数均是实数”是真命