离散数学(第7讲)谓词逻辑2.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《离散数学(第7讲)谓词逻辑2.ppt》由会员分享,可在线阅读,更多相关《离散数学(第7讲)谓词逻辑2.ppt(34页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、栾新成栾新成 四川大学软件学院四川大学软件学院85997822 13808024081第第2章章 一阶谓词逻辑一阶谓词逻辑(2)主要内容主要内容v谓词公式与解释谓词公式与解释v 1.谓词的合适公式谓词的合适公式v 2.谓词公式的解释谓词公式的解释v 3.几个特殊的公式几个特殊的公式v谓词公式的等价与范式表示谓词公式的等价与范式表示v 1.谓词公式的等价谓词公式的等价v 2.基本等价式基本等价式v 3.前束范式前束范式v 4.斯柯林范式斯柯林范式2022年年12月月31日日2谓词公式谓词公式v同命题演算一样,在谓词逻辑中也同样包含命题变元和命同命题演算一样,在谓词逻辑中也同样包含命题变元和命题联
2、结词,为了能够进行演绎和推理,为了对谓词逻辑中题联结词,为了能够进行演绎和推理,为了对谓词逻辑中关于谓词的表达式加以形式化,利用联结词、谓词与量词关于谓词的表达式加以形式化,利用联结词、谓词与量词构成构成命题函数命题函数,我们必须引入公式的概念。,我们必须引入公式的概念。2022年年12月月31日日3谓词公式谓词公式v四类符号四类符号:v常量符号常量符号:一般用:一般用a,b,c,a1,b1,c1,来表示,它可以是来表示,它可以是D中的中的某个某个元素元素;v变量符号变量符号:一般用:一般用x,y,z,x1,y1,z1,来表示来表示.它可以取它可以取值于值于D中的中的任意任意元素;元素;v函数
3、符号函数符号:一般用:一般用f,g,h,f1,g1,h1,来表示。来表示。n元函数元函数符号符号f(x1,x2,.xn)可以是可以是DnD的任意一个函数;的任意一个函数;v谓词符号谓词符号:一般用:一般用P,Q,R,.,P1,Q1,R1,.来表示。来表示。n元元谓词符号谓词符号P(x1,x2,.xn)可以是可以是Dn0,1的任意一个谓词。的任意一个谓词。v注:不含变元的函数是注:不含变元的函数是常量常量;不含客体变元的谓词是;不含客体变元的谓词是命题命题。2022年年12月月31日日4谓词公式谓词公式vn元函数符号元函数符号f(x1,x2,.xn)与与n元谓词符号元谓词符号P(x1,x2,.x
4、n)v1)两个)两个n元相同吗?元相同吗?v2)函数符号)函数符号f(x1,x2,.xn)中的中的f 可以用可以用P代换吗?如果能,代换吗?如果能,则代换结果为则代换结果为P(x1,x2,.xn),与谓词符号,与谓词符号P(x1,x2,.xn)的的区别是什么?区别是什么?2022年年12月月31日日值域不同5谓词公式谓词公式定义定义2-2.1 2-2.1 谓词逻辑中的谓词逻辑中的项项被被递归地定义为:递归地定义为:v1 1)任意的常量符号是项;)任意的常量符号是项;v2 2)任意的变量符号是项;)任意的变量符号是项;v3 3)若)若f(xf(x1 1,x,x2 2,x,x3 3,x,xn n)
5、是是n n元元函数符号,函数符号,t t1 1,t,t2 2,t,t3 3,t,tn n是项,是项,则则f(tf(t1 1,t,t2 2,t,t3 3,t,tn n)是项;是项;v4 4)只有有限次使用)只有有限次使用1)-3)1)-3)产生产生的符号串才是项。的符号串才是项。例例2.12.1复合函数复合函数f(g(f(a),g(a,x)f(g(f(a),g(a,x)是是一个项一个项2022年12月31日6谓词公式谓词公式v定义定义2-2.2 设设P(x1,x2,x3,.xn)是是n元谓词,元谓词,t1,t2,t3,.tn是项是项,则则P(t1,t2,t3,.tn)是原子谓词公式,简是原子谓词
6、公式,简称原子公式。称原子公式。v定义定义2-2.3 满足下列条件的表达式,称为合适公式满足下列条件的表达式,称为合适公式,简简称公式。称公式。v1)原子公式是合适公式;)原子公式是合适公式;v2)若)若G,H是合适公式,则是合适公式,则(G)、(H)、(GH)、(GH)、(GH)、(GH)也是合适公式;也是合适公式;v3)若)若G是合适公式,是合适公式,x是个体变量,则是个体变量,则(x)G、(x)G也是合适公式;也是合适公式;v4)仅仅由)仅仅由1)-3)产生的表达式才是合适公式。产生的表达式才是合适公式。2022年年12月月31日日G G的区别的区别:G:G与与(x)Gx)G(x)x)7
7、谓词公式谓词公式v例例2.2(P(x)(Q(x,y)R(x,a,f(z)v(P(x)R(y)v(x)(P(x)v 等都是公式。等都是公式。v 而而v(x)(P(x)R(x)v(x)P(x)(y)v 等则不是公式,前者括号不匹配,后者量词无辖域。等则不是公式,前者括号不匹配,后者量词无辖域。2022年年12月月31日日8谓词公式的谓词公式的翻译翻译v例例1 1 并非并非每个每个实数都是有理数实数都是有理数v解:设解:设R(x):xR(x):x是实数是实数,Q(x):x,Q(x):x是有理数是有理数v原命题为:原命题为:x x(R(x)Q(x)R(x)Q(x)v例例2 2 没有没有不犯错误的人不犯
8、错误的人v解:设解:设M(x)M(x):x x是人是人,F(x):x,F(x):x犯错犯错v原命题为:原命题为:x((M(x)(M(x)F(x)F(x)v例例3 3 尽管尽管有人聪明有人聪明,但,但未必一切人未必一切人都都聪明聪明。v解:设解:设M(x):xM(x):x是人是人,P(x):x,P(x):x聪明聪明v原题为:原题为:x(M(x)P(x)x(M(x)P(x)x(M(x)x(M(x)P(xP(x)2022年年12月月31日日9谓词公式的谓词公式的翻译翻译v多元谓词可以多重量化多元谓词可以多重量化v例例4 4 翻译翻译每个人都有缺点每个人都有缺点。v解:设解:设F F(x,yx,y):
9、x:x有有y,M(x):xy,M(x):x是人是人 G(y):yG(y):y有缺点有缺点v原命题为原命题为:x(M(x)y(G(y)F(x,y)F(x,y)v例例5:5:翻译翻译某些人对某些食物过敏某些人对某些食物过敏。v解:设解:设F F(x,yx,y):x:x对对y y过敏过敏,M(x):x,M(x):x是人是人 v G(y):yG(y):y是食物。是食物。v原命题为原命题为:x y(M(x)G(y)F(x,y)F(x,y)2022年年12月月31日日10谓词公式的谓词公式的翻译翻译v谓词对于个体刻划的深度的谓词对于个体刻划的深度的机动灵活性机动灵活性v例例6 翻译翻译那只小花猫逮住这只大
10、老鼠那只小花猫逮住这只大老鼠。v解:设解:设v a:F(x,y):x逮住逮住y,P(x):x是小花猫是小花猫,Q(y):y是大老鼠是大老鼠,S(a):a是那只是那只,R(b):b是这只是这只v原命题为:原命题为:a b(P(a)Q(b)F(a,b)S(a)R(b)vb A(x):x是猫是猫,B(x):x是小的是小的,C(x):x是花的是花的,D(y):y是的是的,E(y):y是老鼠是老鼠,F(x,y),S(a),R(b)同上。同上。v原命题为:原命题为:a b(A(a)B(a)C(a)D(b)E(b)F(a,b)S(a)R(b)v。2022年年12月月31日日11谓词公式的解释谓词公式的解释v
11、定义定义2-2.4 一个定义在论域一个定义在论域D上的公式上的公式G的每一个的每一个解释解释(指(指派)由如下四部分组成:派)由如下四部分组成:v1、非空的个体域集合、非空的个体域集合D;v2、G中的每个常量符号中的每个常量符号,指定指定D中的一个元素;中的一个元素;v3、G中的每个中的每个n元函数符号元函数符号,指定指定Dn到到D的一个函数;的一个函数;v4、G中的每个中的每个n元谓词符号元谓词符号,指定指定Gn到到0,1的一个谓词。的一个谓词。v注:定义中所谓指定一个注:定义中所谓指定一个具体函数具体函数,即是对每组可能的变量,即是对每组可能的变量值给出值给出函数的对应值函数的对应值;(值
12、域?)(值域?)v所谓指定一个具体所谓指定一个具体命题函数命题函数,就是对每组可能的客体变元取,就是对每组可能的客体变元取值给出谓词的对应值,值给出谓词的对应值,1表示逻辑真,表示逻辑真,0表示逻辑假。表示逻辑假。2022年年12月月31日日12谓词公式的解释谓词公式的解释v含有量词的公式的解释含有量词的公式的解释v 对于含有量词的公式的解释,需要根据量词的逻辑意对于含有量词的公式的解释,需要根据量词的逻辑意义来决定公式的值。义来决定公式的值。v设论域设论域 D=a1,a2,,anv1)()(x)P(x)P(a1)P(a2)P(an)v 表示公式(表示公式(x)P(x)值为值为1“当且仅当当且
13、仅当”对论域对论域D中每个中每个元素元素a,P(a)的值为的值为1。v2)()(x)P(x)P(a1)P(a2)P(an)v 表示公式(表示公式(x)P(x)值为值为0“当且仅当当且仅当”对论域对论域D中每个中每个元素元素a,P(a)的值为的值为0。2022年年12月月31日日13谓词公式的解释谓词公式的解释v例例2.3 设公式:设公式:(x)(y)(P(x,y)Q(x,y)。在如下给定的解释下在如下给定的解释下,判断该公式的真值。判断该公式的真值。v1)、解释、解释I为:为:v .个体域为个体域为N+(严格大于严格大于0的整数的整数);v .P(x,y)指定为:指定为:“yx”;v .Q(x
14、,y)指定为:指定为:“y1”。v则原公式的真值为则原公式的真值为“真真”。因确能找到一个。因确能找到一个xN+,使得,使得对任意对任意y,都有都有yx和和y1。v此时蕴涵公式的前件为真,后件也为真。所以,整个公式此时蕴涵公式的前件为真,后件也为真。所以,整个公式为真。为真。2022年年12月月31日日14谓词公式的解释谓词公式的解释v2)、解释、解释I为:为:(x)(y)(P(x,y)Q(x,y)。v.个体域为个体域为N;v.P(x,y)指定为:指定为:“xy0”;v.Q(x,y)指定为:指定为:“xy”;则原公式的真值;则原公式的真值为为“假假”。v因对任意的因对任意的x0,当当y0时,有
15、时,有P(x,y)Q(x,y)为为“假假”,即有:即有:(y)(P(x,y)Q(x,y)为为“假假”。v而对而对x0,当,当y1时,有时,有P(x,y)Q(x,y)为为“假假”。即有:。即有:(y)(p(x,y)Q(x,y)为为“假假”。v所以,对任意所以,对任意xN,都有:都有:(y)(P(x,y)Q(x,y)为为“假假”。v即有:即有:(x)(y)(P(x,y)Q(x,y)为为“假假”。2022年年12月月31日日15谓词公式的解释谓词公式的解释v3)、解释、解释I为:为:(x)(y)(P(x,y)Q(x,y)。v.个体域为个体域为N;v.P(x,y)指定为:指定为:“x+y0”;v.Q(
16、x,y)指定为:指定为:“xy”。v则原公式的真值为则原公式的真值为“真真”。v因对任意的因对任意的x0,任意任意yN,有,有x+y0为为“假假”,所以,所以无论后件如何,都有无论后件如何,都有 P(x,y)Q(x,y)为为“真真”,v即有:即有:(y)(P(x,y)Q(x,y)为为“真真”。v所以:所以:(x)(y)(P(x,y)Q(x,y)为为“真真”。2022年年12月月31日日16几个特殊公式几个特殊公式v定义定义2-2.5:1、设、设A是以是以D为论域的谓词公式,如果在关于为论域的谓词公式,如果在关于D的任一解释的任一解释之下,之下,A的值都为真(或的值都为真(或1)时,称公式)时,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 谓词 逻辑
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内