离散数学2(精品·公开课件).ppt

第二章 谓词逻辑 问题的提出：(即命题逻辑的局限性) 在第一章, 一个原子命题只用一个字母表示， 而不再对命题中的句子成分细分。这样有一些逻 辑问题无法解决。请看下面的例子。 例1.令Ｐ：小张是大学生。 Ｑ：小李是大学生。 从符号Ｐ、Ｑ中不能归纳出他们都是大学生的共 性。我们希望从所使用的符号那里带给我们更多 的信息，比如可以看出他们的共性。这种想法在 第一章是无法实现的。 例2.令 Ａ：所有自然数都是整数。 Ｂ：８是自然数。 Ｃ：８是整数。 这是著名的三段论推理，A是大前提，B是小前提， C是结论。显然，由Ａ和Ｂ可以推出结论Ｃ。这 个推理是有效的，但是这个推理在第一章也是无 法实现的。 分析：命题Ｐ与Ｑ中的谓语是相同的(是大学生), 只是主语不同。命题Ａ、Ｂ、Ｃ之间在主语谓语 方面也是有联系的，靠这种联系才能由Ａ、Ｂ推 出Ｃ。而从这三个符号上看不出此种联系。 所以就要另外考虑表示命题的方法。 解决这个问题的方法： 在表示命题时，既表示出主语，也表示出谓语， 就可以解决上述问题。这就提出了谓词的概念。 令S(x)表示x是大学生，a:小张，b:小李 命题P表示成S(a):小张是大学生。 命题Q表示成S(b):小李是大学生。 从符号S(a)、S(b)可看出小张和小李都是大学生的共性. 令N(x):x是自然数。I(x):x是整数。 ?表示所有的。 A: ?x(N(x)→I(x)) B :N(8) C :I(8) 2-1 基本概念 2-1.1 客体与客体变元 定义：能够独立存在的事物，称之为客体，也 称之为个体。它可以是具体的，也可以是抽象的 事物。通常用小写英文字母a、b、c、...表示。 例如，小张、小李、8、a、沈阳、社会主义等等 都是客体。 定义：用小写英文字母x、y、z...表示任何客 体，则称这些字母为客体变元。 注意：客体变元本身不是客体。 2-1.2 谓词 定义：一个大写英文字母后边有括号，括号内是若干个客体变元，用以表示客体的属性或者客体之间的关系，称之为谓词。如果括号内有n个客体变元，称该谓词为n元谓词。 例如 S(x):表示x是大学生。 一元谓词 G(x,y)：表示 xy。 二元谓词 B(x,y,z)：表示x在y与z之间。三元谓词 一般地 P(x1,x2,…,xn) 是n元谓词。 2-1.3 命题函数 谓词本身并不是命题，只有谓词的括号内填入足够的客体，才变成命题。 例如， a表示小张，b表示小李，则 S(a):小张是大学生。 S(b):小李是大学生。 Ｇ(7,3)表示:７３。 如果c表示锦州，d表示沈阳，e表示山海关，则B(c,d,e)表示：锦州在沈阳与山海关之间。 这时S(a)、S(b)、G(7,3)、B(c,d,e)才是命题。 令谓词S(x):x是大学生，括号内填入不同的人名， 就得到不同的命题，故谓词S(x)相当于一个函数， 称之为命题函数。 定义：n元谓词P(x1,x2,…,xn)称之为简单命题函数。 规定：当命题函数P(x1,x2,…,xn)中 n=0 时，即0 元谓词，表示不含有客体变元的谓词，它本身就是 一个命题变元。 定义：将若干个简单命题函数用逻辑联结词联结起 来，构成的表达式，称之为复合命题函数。简单命 题函数与复合命题函数统称为命题函数。 例如 给定简单命题函数： A(x)：x身体好， B(x)：x学习好， C(x)：x工作好， 复合命题函数 ?A(x)→(?B(x)∧?C(x)) 表示如果x身体不好，则x的学习与工作都不会好。 2-1.4 论域(个体域) 定义：在命题函数中客体变元的取值范围，称之为论域，也称之为个体域。 例如 S(x):x是大学生，论域是:人类。 G(x,y)：xy， 论域是:实数。 论域是一个集合。 定义：由所有客体构成的论域，称之为全总个体域。它是个“最大”的论域。 约定:对于一个命题函数，如果没有给定论域，则假定该论域是全总个体域。 2-1.5 量词 例如：有些人是大学生。 所有事物都是发展变化的。 “有些”,“所有的”,就是对客体量化的词。 定义：在命题中表示对客体数量化的词，称之为量词。 定义了两种量词： (1).存在量词：记作?，表示“有些”、“一些”、 “某些”、“至少一个”等。 (2).全称量词：记作?，表示“每个”、“任何 一个”、“一切”、“所有的”、“凡是”、“任意 的”等。 定义：量词后边要有一个客体变元，指明对哪个客体变元量化，称此客体变元是量词后的指导变元。 例如 ?x(读作“任意x”)，?x