离散数学一阶逻辑命题符号化.ppt

《离散数学一阶逻辑命题符号化.ppt》由会员分享，可在线阅读，更多相关《离散数学一阶逻辑命题符号化.ppt（26页珍藏版）》请在三一办公上搜索。

1、离散数学,数理逻辑,第四章 一阶逻辑基本概念,一阶逻辑命题符号化一阶逻辑公式及解释,一阶逻辑的引入,在命题逻辑中,命题是最基本的单位,对简单命题不再进行分解,不关心命题中个体与总体的内在联系和数量关系.这就使得它难以描述和证明一些常见的推理.因此,需要对命题进行细化,建立更为精细的逻辑推理体系.例如:逻辑学中著名的三段论:凡偶数都能被2整除.6是偶数.所以,6能被2整除.这个推理是数学中的真命题,是正确的,但在命题逻辑中却无法判断其正确性,用p,q,r分别表示以上三个命题.则得到推理的形式结构为:(pq)r由于上式不是重言式,因而不能由它判断推理的正确性.原因在于各命题的内在联系没有表示出来.

2、为了克服命题逻辑的局限性,应该将原子命题再细分,分析出个体词,谓词和量词,以便达到表达出命题的内在联系和命题之间的逻辑关系.这就是一阶逻辑所研究的内容.,4.1 一阶逻辑命题符号化,谓词逻辑命题符号化的三个基本要素:个体词,谓词,量词.1.个体词:研究对象中可以独立存在的具体的或抽象的客体.例如:小王,小张,马列主义,3,北京等都可做为个体词.注:(1)表示具体或特定客体的个体词称为个体常项,一般用小写字母 a,b,c,表示;(2)表示抽象或泛指的个体词称为个体变项,一般用小写字母 x,y,z,表示.个体变项的取值范围称为个体域(或论域).个体域可以是有限集合,如1,2,3或a,b,c,也可以

3、是无限集合,如自然数集合N或实数集合R.由宇宙间一切事物组成的个体域称为全总个体域.,谓词,2.谓词:用来刻划个体词的性质或个体词之间相互关系的词.例如:(1)在命题“是无理数”中,“是无理数”是谓词.(2)在命题“x 是有理数”中,“是有理数”是谓词.(3)在命题“小王与小李同岁”中,“与同岁”是谓词.(4)在命题“x与y具有关系L”中,“与具有关系L”是谓词.注 常用大写字母F,G,H 等来表示谓词.表示具体性质或关系的谓词称为谓词常项;表示抽象或泛指的性质或关系的谓词称为谓词变项.F(a):表示个体常项a具有性质F(F是谓词常项或变项);F(x):表示个体变项x具有性质F(F同上);F(

4、a,b):表示个体常项a,b具有关系F(同上);F(x,y):表示个体变项 x,y具有关系F(同上).一般地,用P(x1,x2,xn)表示含n(n1)个个体变项x1,x2,xn 的n元谓词.它可看成以个体域为定义域,以0,1为值域的n元函数关系.当P取常项,且(x1,x2,xn)取定常项(a1,a2,an)时,P(a1,a2,an)是一个命题.,谓词续,不含个体变项的谓词称为0元谓词.例如 F(a),G(a,b),P(a1,a2,an)等.当F,G,P等为谓词常项时,0元谓词即为命题.因此,命题可看作特殊的谓词.例 用0元谓词将下列命题符号化,并讨论它们的真值.(1)只有当2是素数时,4才是素

5、数;(2)如果5大于4,则4大于6.解(1)设一元谓词F(x):x是素数;个体常项:a:2；b:4.则命题可符号化:F(b)F(a).因为该蕴含式前件为假,故命题为真.(2)设二元谓词G(x,y):x大于y.个体常项:a:4;b:5;c:6.则命题可符号化为:G(b,a)G(a,c).由于G(b,a)为真,而G(a,c)为假,故命题为假.,量词的引入,有了个体词和谓词的概念之后,有些命题还是不能准确地符号化.以前面所讨论的三段论为例:令 P(x):x是偶数.S(x):x能被2整除.a:6.符号化为:(1)P(x)S(x)(2)P(a)(3)S(a)我们知道,“凡偶数都能被2整除.”是一个真命题

6、,而“P(x)S(x)”不是一个命题.原因是“P(x)S(x)”没有把命题 中“凡”的意思表示出来.即缺少表示个体常项或变项的数量关系的词.所以还要引入量词的概念.,量词,量词:表示个体常项或变项之间数量关系的词.量词只有两个:全称量词,存在量词.(1)全称量词:表示“全部”含义的词.全称量词符号化为“”.a.常用语中“全部”,“所有的”,“一切”,“每一个”,“任何”,“任意的”,“凡”,“都”等词都是全称量词.b.x F(x)表示个体域里所有个体都有性质F.(2)存在量词:表示“存在”含义的词.存在量词符号化为“”.a.常用词中“存在”,“有一个”,“有的”,“至少有一个”等词都是存在量词

7、.b.x F(x)表示个体域中存在个体具有性质 F.例:凡偶数都能被2整除.可符号化为:x(P(x)S(x)是真命题,其中x不再起变元的作用,它被全称量词 限制住了,这时我们称 x 被量化了.,一阶逻辑中命题符号化,例 个体域为人类集合,将下面两个命题符号化:(1)凡是人都要呼吸;(2)有的人用左手写字.解令 F(x):x 呼吸;G(x):x 用左手写字.则(1)x F(x);(2)x G(x)。例 上例中,将个体域改为全总个体域,两命题的符号化形式如何?解令 F(x):x呼吸;G(x):x用左手写字；M(x):x是人.则:(1)x(M(x)F(x);(2)x(M(x)G(x).特性谓词:从全

8、总个体域中分离出一个集合,定义的谓词.在不同个体域中,同一个命题的符号化形式可能不同.一般地,对全称量词,特性谓词应作为蕴含式的前件.一般地,对存在量词,特性谓词应作为合取式的一项.同一个命题,在不同个体域中的真值也可能不同.如果问题中没有指明个体域时,默认为全总体域.,一阶逻辑中命题符号化续,当F是谓词常项时,xF(x)是个命题,如果把个体域中的任何一个个体a代入,F(a)都为真,则xF(x)为真;否则xF(x)为假.当F是谓词常项时,xF(x)是个命题,如果个体域中存在一个个体a使F(a)为真,则 xF(x)为真;否则 xF(x)为假.例在个体域限制为(a)和(b)条件时,将下列命题符号化

9、,并给出它们的真值.(1)对于任意的x,均有x2-3x+2=(x-1)(x-2)(2)存在x,使得x+5=3其中(a)个体域为D1=N(b)个体域为D2=R解令F(x):x2-3x+2=(x-1)(x-2),G(x):x+5=3.则可符号化为(1)xF(x),(2)xG(x).个体域为(a)时,(1)是真命题,(2)是假命题;个体域为(b)时,(1)与(2)都是真命题.,一阶逻辑中命题符号化续,例将下列命题符号化,并讨论其真值.(1)实数都能写成整数之比;(2)有的素数是偶数;(3)没有人登上过木星;(4)在美国留学的学生未必都是亚洲人.解(1)令M(x):x 为实数;F(x):x能写成整数之

10、比.则x(M(x)F(x)不是 x(M(x)F(x)假命题(2)令M(x):x 为素数;G(x):x为偶数.则 x(M(x)G(x)不是 x(M(x)G(x)真命题(3)令M(x):x 是人;H(x):x登上过木星.则x(M(x)H(x)真命题(4)令F(x):x是在美国留学的学生;G(x):x是亚洲人.则x(F(x)G(x)真命题,n 元谓词的符号化(n 2),例将下列命题符号化(1)兔子比乌龟跑得快;(2)有的兔子比所有的乌龟跑得快;(3)并不是所有的兔子都比乌龟跑得快;(4)不存在跑得同样快的两只兔子.解令F(x):x是兔子;G(y):y是乌龟;H(x,y):x比y跑得快;L(x,y):

11、x与 y跑得同样快.则:(1)任意一个兔子x:x 比任意一个乌龟跑得快x(F(x)y(G(y)H(x,y);(2)存在一个兔子 x:x 比任意一个乌龟跑得快x(F(x)y(G(y)H(x,y);(3)(1)的否定 存在一个兔子 x:存在一个乌龟 y:x不比y跑得快 x(F(x)y(F(y)L(x,y).;(4)“存在一个兔子 x:存在另一个兔子 y:x与y跑得同样快”的否定x(F(x)y(F(y)L(x,y).,注,1.分析命题中表示性质和关系的谓词,分别符号化为一元和n元谓词(n2).2.根据命题的实际意义选用全称量词或存在量词.3.一般来说,多个量词在一起时,其顺序不能随意调换.例如:“对

12、任意x,都存在y,使x+y=10”这一命题,可符号化为 xy(x+y=10),它不能改写为 yx(x+y=10).练习 函数f(x)在x=a处极限为b任给小正数,则存在正数,使得当00,存在0,使得当00(0 x(|x-a|f(x)-b|),4.2一阶逻辑公式及解释,非逻辑符号:个体词常项符号,函数符号和谓词符号逻辑符号:个体词变项符号,量词符号,联结词符号和括号与逗号定义 设L是一个非逻辑符号,由L生成的一阶语言L的字母表包括下述符号如下:非逻辑符号(1)L中的个体常项符号:a,b,c,;ai,bi,ci,i1(2)L中的函词符号:f,g,h,;fi,gi,hi,i1(3)L中的谓词符号:F

13、,G,H,;Fi,Gi,Hi,i1逻辑符号(4)个体变项符号:x,y,z,;xi,yi,zi,i1(5)量词符号:,.(6)联结词符号:,.(7)逗号与括号:,().,项与原子公式,定义 一阶语言L 的项定义如下:(1)个体常项符号和个体变项符号是项;(2)若(x1,x2,xn)是n元函词符号,t1,t2,tn 是n个项,则(t1,t2,tn)是项.(3)所有的项都是有限次使用(1),(2)得到的定义 设R(x1,x2,xn)是一阶语言L中的n元谓词符号.t1,t2,tn 是L 的n个项,则称 R(t1,t2,tn)是F 的原子公式,合式公式,定义 一阶语言L 中的合式公式(也称为谓词公式或公

14、式)定义如下:(1)原子公式是合式公式;(2)若A是合式公式,则(A)也是合式公式;(3)若A,B 是合式公式,则(AB),(AB),(AB),(AB)也是合式公式;(4)若A是合式公式,则 xA,xA也是合式公式;(5)只有有限次应用(1)(4)构成的符号串才是合式公式.定义 在公式 xA 和 xA中,称 x 为指导变元,A为相应量词的辖域.在x 和 x 的辖域中,x的所有出现都称为约束出现,A中不是约束出现的其它变项都称为自由出现.,辖域,例 指出下列公式中的指导变元,各量词的辖域,自由出现和约束出现的个体变项:(1)x(F(x,y)G(x,z);(2)x(F(x)G(y)y(H(x)L(

15、x,y,z).解(1)指导变元:x;量词的辖域:A=(F(x,y)G(x,z);在A 中,x是约束出现;y,z是自由出现.(2)前件量词的指导变元:x;后件量词的指导变元:y.量词的辖域:(F(x)G(y),其中x是约束出现,y 是自由出现.量词的辖域:(H(x)L(x,y,z),其中 y是约束出现,而x,z 是自由出现.,闭式,定义 设A是任意的公式,若A中不含自由出现的个体变项,则称A为封闭的公式,简称闭式.例如 xy H(x,y),xy(F(x)F(y)L(x,y),x(F(x)G(x)F(a)G(a)例 将下列两个公式中的变项指定为常项使其成为命题:(1)x(F(x)G(x)(2)xy

16、(F(x)F(y)G(x,y)H(f(x,y),g(x,y)解(1)个体域 F(x)G(x)命题 真值 全总 x是人 x是黄种人 所有人都是黄种人0 实数 x是自然数 x是整数 所有自然数都是整数1(2)两个2元函词变项,一个1元谓词变项,两个2元谓词变项.个体域 F(x)G(x,y)H(x,y)f(x,y)g(x,y)全总 x是实数 xy xy x2+y2 2xy命题:对于任意的x,y,若x与y都是实数且xy,则x2+y22xy.真值为真.,解释,在前面例子中对各种变项的指定也称为对它们的解释,是先给出公式再对它们进行解释,也可以先给出解释,再去解释各种公式.定义 对公式A指定其中个体域的范

17、围,并指定其中谓词的具体含义使其成为命题,称为对公式A的一个解释.定义 设L是由L生成的一阶语言,L的的解释I 由下面4部分组成:非空个体域DI.对每一个个体常项符号aL,有一个aDI,称a为a在I中的解释.对每一个n元函词符号fL,有一个DI上的n元函数f:DIn DI,称f为f在I中的解释.对每一个n元谓词符号FL,有一个DI上的n元谓词常项F,称F为F在I中的解释.,例,例 给定解释I如下:个体域D=N.a=0.f(x,y)=x+y,g(x,y)=xy.F(x,y):x=y.写出下列公式在I下的解释,并指出哪些公式为真?哪些为假?哪些真值不能确定?(1)F(f(x,y),g(x,y);解

18、:公式解释为:“x+y=xy”不是命题;真值不确定(2)F(f(x,a),y)F(g(x,y),z);解:公式解释为:“(x+0=y)(xy=z)”不是命题;真值不确定(3)F(g(x,y),g(y,z);解:公式解释为:“xyyz”不是命题;真值不确定,例续,(4)xF(g(x,y),z);解:公式解释为:“x(xy=yz)”不是命题;真值不确定(5)x F(g(x,a),x);解:公式解释为:“x(x0=x)”假命题(6)x F(g(x,a),x)F(x,y);解:公式解释为:“x(x0=x)(x=y)”真命题(前件为假),例续,(7)xy(F(f(x,a),y)F(f(y,a),x);解

19、:公式解释为:“xy(x+0=y)(y+0=x)”真命题(8)xyz F(f(x,y),z);解:公式解释为:“xyz(x+y=z)”真命题(9)x F(f(x,x),g(x,x);解:公式解释为:“x(x+x=xx)真命题,公式类型,定理 闭式在任何解释下都可变成命题.定义 设A为一个公式,若A在任何解释下均为真,则称A为永真式(或逻辑有效式);若A在任何解释下均为假,则称A为永假式(或逻辑矛盾式);若至少存在一个解释使A为真,则称A为可满足式.定义 设A0 是含命题变项p1,p2,pn 的命题公式,A1,A2,An 是n个谓词公式.用Ai(1in)处处代替A0 中的pi,所得公式A 称为A

20、0 的代换实例.例如 F(x)G(x),x F(x)y G(y)等都是pq的代换实例.定理 重言式的代换实例都是永真式,矛盾式的代换实例都是矛盾式.,公式类型示例,例 判断下列公式中,哪些是永真式,哪些是永假式?(1)x(F(x)G(x);(3)x F(x)(x y G(x,y)x F(x);(2)x(F(x)G(x);(4)(x F(x)y G(y)y G(y).解 用A,B,C,D分别代表(1),(2),(3),(4)中的公式.(1)取解释I1:个体域为实数域;F(x):x是实数;G(x):x是有理数.在I1下A为假,故A不是永真式.再取解释I2:个体域为实数域;F(x):x是有理数;G(

21、x):x 能表示成分数.在I2下A为真.故公式A是可满足式但不是永真式.(2)公式B是非永真的可满足式.(3)易知C是命题公式p(qp)的代换实例,而该命题公式是重言式,故公式C 是永真式.(4)D是命题公式(pq)q的代换实例,而该命题公式为矛盾式,故公式D是矛盾式.,公式类型示例,例 判断下列公式的类型:(1)x F(x)x F(x);(2)xyF(x,y)xy F(x,y);(3)x(F(x)G(x)y G(y).解 记三个公式分别为A,B,C.(1)设I为任一解释,个体域为D.若存在x0D,使F(x0)为假,则xF(x)为假,所以A的前件为假,A为真;若D中每个个体都具有性质F,即A的前件为真,后件显然也为真,从而A为真.由 I 的任意性知,A是永真式.(2)取解释I,个体域为自然数集合N,F(x,y)为xy,在 I 下 B的前件与后件均为真,故B为真,这说明 B不是矛盾式.另取解释 I1,个体域为自然数集合N,F(x,y)为 x=y,在 I1下,B的前件真而后件假,故B为假.这又说明 B不是永真式.从而 B是非永真的可满足式.(3)C也是非永真的可满足式.,该休息啦,