离散数学]离散数学.ppt

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

1、第二章谓词逻辑问题的提出：(即命题逻辑的局限性)在第一章,一个原子命题只用一个字母表示，而不再对命题中的句子成分细分。这样有一些逻辑问题无法解决。请看下面的例子。例1.令Ｐ：小张是大学生。Ｑ：小李是大学生。从符号Ｐ、Ｑ中不能归纳出他们都是大学生的共性。我们希望从所使用的符号那里带给我们更多的信息，比如可以看出他们的共性。这种想法在第一章是无法实现的。例2.令Ａ：所有自然数都是整数。Ｂ：８是自然数。Ｃ：８是整数。这是著名的三段论推理，A是大前提，B是小前提，C是结论。显然，由Ａ和Ｂ可以推出结论Ｃ。这个推理是有效的，但是这个推理在第一章也是无法实现的。分析：命

2、题Ｐ与Ｑ中的谓语是相同的(是大学生),只是主语不同。命题Ａ、Ｂ、Ｃ之间在主语谓语方面也是有联系的，靠这种联系才能由Ａ、Ｂ推出Ｃ。而从这三个符号上看不出此种联系。所以就要另外考虑表示命题的方法。解决这个问题的方法：在表示命题时，既表示出主语，也表示出谓语，就可以解决上述问题。这就提出了谓词的概念。令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:

3、N(8)C:I(8)N(8)→I(8)N(8)I(8)符号S(x)、N(x)、I(x)就是所谓的谓词。推理如此实现：2-1基本概念2-1.1客体与客体变元定义：能够独立存在的事物，称之为客体，也称之为个体。它可以是具体的，也可以是抽象的事物。通常用小写英文字母a、b、c、...表示。例如，小张、小李、8、a、沈阳、社会主义等等都是客体。定义：用小写英文字母x、y、z...表示任何客体，则称这些字母为客体变元。注意：客体变元本身不是客体。2-1.2谓词定义：一个大写英文字母后边有括号，括号内是若干个客体变元，用以表示客体的属性或者客体之间的关系，称之为谓词

4、。如果括号内有n个客体变元，称该谓词为n元谓词。例如S(x):表示x是大学生。一元谓词G(x,y)：表示x>y。二元谓词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(

5、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的

6、学习与工作都不会好。2-1.4论域(个体域)定义：在命题函数中命题变元的取值范围，称之为论域，也称之为个体域。例如S(x):x是大学生，论域是:人类。G(x,y)：x>y，论域是:实数。论域是一个集合。定义：由所有客体构成的论域，称之为全总个体域。它是个“最大”的论域。约定:对于一个命题函数，如果没有给定论域，则假定该论域是全总个体域。2-1.5量词例如：有些人是大学生。所有事物都是发展变化的。“有些”,“所有的”,就是对客体量化的词。定义：在命题中表示对客体数量化的词，称之为量词。定义了两种量词：(1).存在量词：记作，表示“有些”、“一些”、“某些”

7、、“至少一个”等。(2).全称量词：记作，表示“每个”、“任何一个”、“一切”、“所有的”、“凡是”、“任意的”等。定义：量词后边要有一个客体变元，指明对哪个客体变元量化，称此客体变元是量词后的指导变元。例如x(读作“任意x”)，x(读作“存在x”)，其中的x就是量词后的指导变元。例题１.所有的自然数都是整数。设N(x)：x是自然数。I(x)：x是整数。此命题可以写成x(N(x)→I(x))例题２.有些自然数是偶数。设E(x)：x是偶数。此命题可以写成x(N(x)∧E(x))例题3.每个人都有一个生母。设P(x):x是个人。M(x,y):y是x的

8、生母。此命题可以写成x(P(x)→y(P(y)∧M(x,y))