第2章一阶逻辑离散数学ppt课件.ppt

《第2章一阶逻辑离散数学ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章一阶逻辑（PredicateLogic）一阶逻辑基本概念一阶逻辑公式及解释一阶逻辑等值式123前两节介绍的命题与命题演算是命题逻辑的内容，其基本组成单位是原子命题。一般地，原子命题作为具有真假意义的句子至少由主语和谓语两部分组成。例如，电子商务是计算机技术的一个应用系统，这里“电子商务”是主语，而“是……”是谓语。当主语改变为“电子政务”时就得到新的原子命题：电子政务是计算机技术的一个应用系统。一阶逻辑一阶逻辑基本概念12由此可知，主语是独立存在的个体，而谓语用来描述该个体的性质或个体间的关系，这里我们称其为谓词。用P表示谓词“是……”。则P（电子商务）或P（电子政务）分

2、别等值于前述两个命题的表达。将个体用变量（称为个体变量）x推广，则P(x)表示：x是计算机技术的一个新的应用系统。这时该语句就不是一个命题，而是一个命题函数。一阶逻辑基本概念3一个谓词P连同相关的n(n≥0)个个体变量组成的表达式称为n元谓词(n-predicate)，记P(x1,x2,…,xn)，其中n是该表达式中不同个体变量的数目。DEFINITION1.一阶逻辑基本概念4设P(x)表示语句“x>3.”，则P(4)和P(2)的真值是多少?P(4)=1P(2)=0EXAMPLE1一阶逻辑基本概念5设Q(x,y)表示语句“x=y+3.”，则Q(1,2)和Q(3,0)的真值是多少

3、?Q(1,2)=0Q(3,0)=1EXAMPLE2一阶逻辑基本概念6设R(x,y,z)表示语句“x+y=z.”，则R(1,2,3)和R(0,0,1)的真值是多少?R(1,2,3)=1R(0,0,1)=0EXAMPLE3一阶逻辑基本概念7当n>1时，通常P给出了xi(i=1,2,…,n)之间的关系。例如，P(x,y,z)表示x位于y与z之间，是一个三元谓词。当x,y,z分别用赤道、南半球、北半球代入时，得到命题：赤道位于南半球与北半球之间，其真值为1。再如，将杭州、南京、北京代入，则得到：杭州位于南京和北京之间，真值为0。当n=0时（即0元谓词），该谓词对应一个命题。一阶逻辑基本

4、概念8为了进一步讨论命题函数P(x)的真值情况，首先需要指定个体变量x的取值范围，即个体域(universeofdiscourse,ordomain)。每一个个体变量x都有自己的个体域。如果没有特别指定的个体域，则缺省为一个全个体域(totaluniverseofdiscourse)即任意个体均可以作为常量对x代入。一阶逻辑基本概念9在指定个体变量x的个体域后，该个体域中的每个个体a代入到P(x)中的所有x，就对应一个可以判定真假意义的命题P(a)。不同的个体代入后所对应的命题真值可能不同，也可能相同。一阶逻辑基本概念10例如，P(x)表示为：x2–1=(x–1)(x+1)（x

5、指定的个体域为全体整数）则对任意整数i，i2–1=(i–1)(i+1)恒成立。也就是说，该谓词的真值无论用什么个体代入总是对应为1。此类谓词的真值描述通过一个称为全称量词()的特殊符号来量化。一阶逻辑基本概念11DEFINITION2.谓词P(x)的全称量化(universalquantifi-cation)是一个按如下规则确定真值的命题：如果对每一个个体a代入得到的P(a)均为1，则该命题为1。记为xP(x)。这里是全称量词(universalquantifier)，表示为“任意的”、“所有的”、“一切”等等。一阶逻辑基本概念12符号化下列命题：“这班的所有同学都学微积

6、分。”符号化为：xP(x)或x(S(x)→P(x))P(x)=“x学微积分。”S(x)=“x是这班的学生。”EXAMPLE4一阶逻辑基本概念13xP(x)=P(1)∧P(2)∧P(3)∧P(4)=0EXAMPLE5设P(x)表示语句“x2<10.”，个体域为不大于4的所有正整数。则xP(x)的真值是多少?一阶逻辑基本概念14谓词P(x)的存在量化(existentialquantifi-cation)是一个按如下规则确定真值的命题：如果个体域中存在一个个体a代入得到的P(a)为1，则该命题为1，否则为0。记为xP(x)。这里称为存在量词(existentialqua

7、ntifier)。表示为“有一个”、“某些”、“某个”、“至少有一个”等等。DEFINITION3.一阶逻辑基本概念15因为若以x=4为例，“x>3”是正确的，说明存在x，使得P(x)为真，所以xP(x)的真值为1。EXAMPLE6设P(x)表示语句“x>3.”，个体域为实数集合。则xP(x)的真值是多少?一阶逻辑基本概念16EXAMPLE7设Q(x)表示语句“x=x+1.”，个体域为实数集合。则xQ(x)的真值是多少?因为不存在这样的x，使得“x=x+1”为真，所以xQ(x)的真值