交大数理逻辑课件4-2 谓词逻辑的基本概念

《交大数理逻辑课件4-2 谓词逻辑的基本概念》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第4章谓词逻辑的基本概念4.1谓词和个体词4.2函数和谓词4.3合式公式4.4自然语句的形式化4.5有限域下公式(x)P(x)、(x)P(x)的表示法4.6公式的普遍有效性和判定问题4.4自然语句的形式化“函数f(x)在[a,b]上的点x0处连续”的形式描述d-e的说法表述为----设f(x)在点x0的某一邻域[a,b]有定义，若对于任意e>0,总存在着正数d，使得对于适合

2、x-x0

3、

4、f(x)-f(x0)

5、

6、律用全总个体域形式化为：(e)(e>0(d)(d>0(x)(

7、x-x0

8、

9、f(x)-f(x0)

10、

11、x-a

12、

13、f(x)-b

14、0(d)(x)(d>0(0<

15、x-a

16、

17、f(x)-b

18、y,Q(x,y)：x

19、x-a

20、,d)∧P(

21、x-a

22、,

23、0))→Q(

24、f(x)-b

25、,e))在使用量词时，应注意以下特点个体域和谓词的含义确定之后，n元命题函数要转化为命题至少需要n个量词。当个体域为有限集时，如D={a1,a2,a3,….an}。对于任意谓词，都有xA(x)=A(a1)A(a2)……A(an)xA(x)=A(a1)A(a2)……A(an)这实际上是将一阶逻辑中命题公式转化为命题逻辑中的命题公式问题。对谓词变元多次量化的分析设P(x,y)是二元谓词，则两变元的量化形式为：(x)(y)P(x,y)=(x)((y)P(x,y))对一

26、切的x和一切的y,都有关系P，量词次序可互换(x)(y)P(x,y)=(x)((y)P(x,y))对一切的x，都有y具有关系P，量词次序不可互换(x)(y)P(x,y)=(x)((y)P(x,y))有一个x，对所有的y有关系P，量词次序不可互换(x)(y)P(x,y)=(x)((y)P(x,y))有一个x，有一个y,具有关系P，量词次序可互换4.5有限域下公式(x)P(x)、(x)P(x)的表示法设个体域为有限集，用{1,2,…,k}来代表。对于任意谓词，都有xP(x)=P(1)P

27、(2)…P(k)即全称量词是合取词的推广在任意域下，全称量词相当于无限个合取词的作用xP(x)=P(1)P(2)…P(k)即存在量词是析取词的推广在任意域下，存在量词相当于无限个析取词的作用4.5.2在域{1,2}上多次量化公式(x)(y)P(x,y)=(y)P(1,y)(y)P(2,y)=P(1,1)P(1,2)P(2,1)P(2,2)($x)($y)P(x,y)=(y)P(1,y)(y)P(2,y)=P(1,1)P(1,2)P(2,1)P(2,2)xP(x)=

28、P(1)P(2)…P(k)xP(x)=P(1)P(2)…P(k)在域{1,2}上多次量化公式($x)(y)P(x,y)=(y)P(1,y)(y)P(2,y)=(P(1,1)P(1,2))(P(2,1)P(2,2))(y)($x)P(x,y)=($x)P(x,1)($x)P(x,2)=(P(1,1)P(2,1))(P(1,2)P(2,2))=(P(1,1)P(1,2))(P(1,1)P(2,2))(P(2,1)P(1,2))(P(2,1)P(2,2))=($x)(

29、y)P(x,y)(P(1,1)P(2,2))(P(2,1)P(2,2))($x)(y)P(x,y)Þ(y)($x)P(x,y)各个量词在公式中出现的次序不能随意更换4.5.3{1,2}域上谓词公式的解释定义：解释I由下面4部分组成：(a)非空个体域D（此处D={1，2}）(b)D中一些特定元素的集合(c)D上特定函数集合(d)D上特定谓词的集合说明：在使用一个解释I解释一个公式A时，将A中的个体常项用I中特定常项代替，函数和谓词用解释I中的特定函数和谓词代替公式的解释举例对(x)($y)P(x,y

30、)一个解释I如下：D={1,2};谓词:P(1,1)=T,P(1,2)=F,P(2,1)=F;P(2,2)=T;(x)($y)P(x,y)=($y)P(1,y)($y)P(2,y)=(P(1,1)P(1,2))(P(2,1)P(2,2))=(TF)(FT)=T对xP(x)一个解释I如下：D={1,2};P(1)=T，P(2)=FxP(x)=P(1)P