离散数学谓词逻辑

《离散数学谓词逻辑》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章谓词逻辑1在命题逻辑中,原子命题是进行演算的基本单位,不研究命题的内部结构以及命题之间的内在联系,因而,命题逻辑中的推理有很大的局限性。例如,著名的苏格拉底三段论：所有的人都是要死的,苏格拉底是人,所以苏格拉底是要死的。符号化：分别用P、Q、R表示以上三个命题,则P∧Q→R表示这一推理过程。蕴含式P∧Q→R不是重言式,虽然凭我们的直觉这个论断正确,在内部逻辑中却无法证明。谓词逻辑的任务就是对原子命题作进一步的分析,研究其内部的逻辑结构,并在此基础上更深入地刻画推理。2谓词逻辑：原子命题＝客体词＋谓词命题所陈述的对象称为客体词。它可

2、以是一个具体的事物,也可以是一个抽象的概念。例如,李明、自然数、思想等都可以作为客体词。定义用来刻画客体词的性质或客体词之间的关系的词称为谓词。例如：π是无理数。小李是计算机系的学生。李明比王宏高2厘米。“π”、“小李”、“李明”、“王宏”都是客体词；“……是无理数”“……是计算机系的学生”“……高2厘米”都是谓词。前两个谓词表示客体词的性质,而后一个谓词描述客体词之间的关系。2.1谓词的概念与表示3谓词的表示客体词有两种：客体常元和客体变元。客体常元表示具体的或特定的客体,一般用小写字母a、b、c等表示；表示抽象的或泛指的客体的词称为

3、客体变元,常用小写字母x、y、z等表示。谓词,通常用大写的字母A、B、C等表示。谓词填式：单独一个谓词不是完整的命题,把谓词字母后填以客体所得的式子。4例子［例2-1.1］张明是位大学生。解：设S(x)：x是大学生,c：张明,则原句的谓词形式为S(c)。［例2-1.2］我坐在张三和李四中间。解：设S(x,y,z)：x坐在y和z之间,i：我,z：张三,l：李四,则原句的谓词形式为S(i,z,l)。一元谓词：表示客体性质多元谓词：表示客体间关系5一般来说,谓词P(x1,…,xn)不是命题,真值无法确定,只有当n个客体常元代替x1,x2,…,

4、xn这n个客体变元之后,才有了确定的真值,因而也就成了命题。例如,L(x,y)是表示x小于y的二元谓词,它的真值不能确定,当以2(用a表示)、3(用b表示)替换x和y之后,L(a,b)成为真命题。62.2命题函数与量词例子：假设谓词H表示“能够到达山顶”,客体p表示李四,q表示老虎,r表示汽车。那么H(p),H(q),H(r)表示三个不同的命题相同点：H(x)定义由一个谓词,一些客体变元组成的表达式称为简单命题函数。由一个或者n个简单命题函数以及逻辑联结词组合而成的表达式称为复合命题函数。7客体变元的取值范围称为个体域(或论述域)。个体

5、域可以是有限客体的集合,如：{a、b、c}、{计算机系的学生}；也可以是无限客体的集合,如实数几何、自然数集合等。特别是,当没有特别声明时,可以将宇宙间的一切事物和概念构成的集合作为个体域,称为全总个体域。8量词1.所有的人都是要死的。2.有些人是要死的。这两个命题中的客体词和谓语均相同,区别在于“所有的”和“有些”这两个表示数量的词。表示数量的词在谓词逻辑中称为量词,量词包括全称量词和存在量词两种。全称量词对应日常语言中的“一切”、“所有的”、“任意的”等词,表示对个体域的所有客体,用符号“∀”表示。存在量词对应对应日常语言中的“存在

6、着”、“至少有一个”、“有些”等词,表示存在着个体域的客体,用符号“∃”表示.9例如：∀xF(x)表示个体域中的所有客体都有性质F；∃xF(x)表示存在着个体域中的客体具有性质F。当个体域有限时,设个体域为{a1,a2,…,an},则∀xF(x)⇔F(a1)∧F(a2)∧…∧F(an)∃xF(x)⇔F(a1)∨F(a2)∨…∨F(an)10符号化:谓词F(x)表示是要死的。当个体域为人类集合时,上述两命题可分别符号化为①∀xF(x)②∃xF(x)。(所有的人都是要死的。有些人是要死的。)引入新的谓词M(x),将人类分离出来。在全总个体域

7、下,以上两命题可分别叙述为：∀x(M(x)→F(x))∃x(M(x)∧F(x))★从以上两命题的符号化可以看出,同一命题在不同个体域下符号化的形式可能不同。11这里,M(x)称为特性谓词。应该注意的是,全称量词和存在量词符号化时,引入特性谓词时的形式是不同的。用全称量词符号化时,特性谓词作为条件式的前件；用存在量词符号化时则作为合取式的一项。12对于任一给定的实数x,都存在着一个实数y,使得x+y=0。如果取个体域为实数集合∀x∃yH(x,y)然而∃y∀xH(x,y)：存在着一个少数y,对于任一实数x,使得x+y=0由此可见,量词出现的

8、不同顺序表达了不同的含义,量词的顺序不能随意颠倒。我们约定,量词按从左到右的顺序读出。13练习Page59(1)c.g.Page60(2)a.i.142.3谓词公式与翻译1.谓词公式为了使命题的符号化更准确