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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,/26,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,*,/26,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,/29,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,/29,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,/29,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,/29,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,/29,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,/29,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,/29,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,/29,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,*,/29,离散数学,数理逻辑,第四章 一阶逻辑基本概念,一阶逻辑命题符号化,一阶逻辑公式及解释,一阶逻辑的引入,在命题逻辑中,命题是最基本的单位,对简单命题不再进行分解,不关心命题中个体与总体的内在联系和数量关系,.,这就使得它难以描述和证明一些常见的推理,.,因此,需要对命题进行细化,建立更为精细的逻辑推理体系,.,例如,:,逻辑学中著名的三段论,:,凡偶数都能被,2,整除,.6,是偶数,.,所以,6,能被,2,整除,.,这个推理是数学中的真命题,是正确的,但在命题逻辑中却无法判断其正确性,用,p,q,r,分别表示以上三个命题,.,则得到推理的形式结构为,:,(pq)r,由于上式不是重言式,因而不能由它判断推理的正确性,.,原因在于各命题的,内在联系,没有表示出来,.,为了克服命题逻辑的局限性,应该将原子命题再细分,分析出,个体词,谓词和量词,以便达到表达出命题的内在联系和命题之间的逻辑关系,.,这就是一阶逻辑所研究的内容,.,4.1,一阶逻辑命题符号化,谓词逻辑命题符号化的三个基本要素,:,个体词,谓词,量词,.,1.,个体词,:,研究对象中可以独立存在的,具体的或抽象的,客体,.,例如,:,小王,小张,马列主义,3,北京等都可做为个体词,.,注,:(,1),表示,具体或特定,客体的个体词称为,个体常项,一般用小写字母,a,b,c,表示,;,(2),表示,抽象或泛指,的个体词称为,个体变项,一般用小写字母,x,y,z,表示,.,个体变项的,取值范围,称为,个体域,(,或论域,).,个体域可以是有限集合,如,1,2,3,或,a,b,c,也可以是无限集合,如自然数集合,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,(,a,b,):,表示个体常项,a,b,具有关系,F,(,同上,);,F,(,x,y,):,表示个体变项,x,y,具有关系,F,(,同上,).,一般地,用,P,(,x,1,x,2,x,n,),表示含,n,(,n,1),个个体变项,x,1,x,2,x,n,的,n,元谓词,.,它可看成以个体域为定义域,以,0,1,为值域的,n,元函数关系,.,当,P,取常项,且,(,x,1,x,2,x,n,),取定常项,(,a,1,a,2,a,n,),时,P(,a,1,a,2,a,n,),是一个命题,.,谓词续,不含,个体变项的谓词称为,0,元谓词,.,例如,F,(,a,),G,(,a,b,),P,(,a,1,a,2,a,n,),等,.,当,F,G,P,等为谓词常项时,0,元谓词即为命题,.,因此,命题可看作特殊的谓词,.,例,用,0,元谓词将下列命题符号化,并讨论它们的真值,.(1),只有当,2,是素数时,4,才是素数,;(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,整除,.”,是一个真命题,而“,P,(,x,),S,(,x,)”,不是一个命题,.,原因是“,P,(,x,),S,(,x,)”,没有把命题 中“凡”的意思表示出来,.,即缺少表示个体常项或变项的数量关系的词,.,所以还要引入量词的概念,.,量词,量词,:,表示个体常项或变项之间数量关系的词,.,量词只有两个,:,全称量词,存在量词,.,(1),全称量词,:,表示“全部”含义的词,.,全称量词符号化为“,”,.,a,.,常用语中“全部”,“,所有的”,“,一切”,“,每一个”,“,任何”,“,任意的”,“,凡”,“,都”等词都是全称量词,.,b,.,x F,(,x,),表示个体域里所有个体都有性质,F,.,(2),存在量词,:,表示“存在”含义的词,.,存在量词符号化为“,”,.,a,.,常用词中“存在”,“,有一个”,“,有的”,“,至少有一个”等词都是存在量词,.,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).,特性谓词,:,从全总个体域中分离出一个集合,定义的谓词,.,在不同个体域中,同一个命题的符号化形式可能不同,.,一般地,对全称量词,特性谓词应作为蕴含式的前件,.,一般地,对存在量词,特性谓词应作为合取式的一项,.,同一个命题,在不同个体域中的真值也可能不同,.,如果问题中没有指明个体域时,默认为,全总体域,.,一阶逻辑中命题符号化续,当,F,是谓词常项时,xF,(,x,),是个命题,如果把个体域中的任何一个个体,a,代入,F,(,a,),都为真,则,xF,(,x,),为真,;,否则,xF,(,x,),为假,.,当,F,是谓词常项时,xF,(,x,),是个命题,如果个体域中存在一个个体,a,使,F,(,a,),为真,则,xF,(,x,),为真,;,否则,xF,(,x,),为假,.,例,在个体域限制为,(a),和,(b),条件时,将下列命题符号化,并给出它们的真值,.(1),对于任意的,x,均有,x,2,-3x+2=(x-1)(x-2)(2),存在,x,使得,x+5=3,其中,(a),个体域为,D,1,=N (b),个体域为,D,2,=R,解令,F(x):x,2,-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,能写成整数之比,.,则,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):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.,一般来说,多个量词在一起时,其顺序不能随意调换,.,例如,:“,对任意,x,都存在,y,使,x+y=10”,这一命题,可符号化为,x,y(x+y=10),它不能改写为,y,x(x+y=10).,练习,函数,f(x),在,x=a,处极限为,b,任给小正数,则存在正数,使得,当,0|x-a|,时,|f(x)-b|0,存在,0,使得,当,0|x-a|,时,|f(x)-b|0 ,(,0,x(|x-a|,|f(x)-b|,),4.2,一阶逻辑公式及解释,非逻辑符号,:,个体词常项符号,函数符号和谓词符号,逻辑符号,:,个体词变项符号,量词符号,联结词符号和括号与逗号,定义,设,L,是一个非逻辑符号,由,L,生成的,一阶语言,L,的字母表,包括下述符号如下,:,非逻辑符号,(1),L,中的,个体常项符号,:,a,b,c,;a,i,b,i,c,i,i,1,(2),L,中的,函词符号,:f,g,h,;f,i,g,i,h,i,i,1,(3),L,中的,谓词符号,:F,G,H,;F,i,G,i,H,i,i,1,逻辑符号,(4),个体变项符号,:,x,y,z,;x,i,y,i,z,i,i,1,(5),量词符号,:,.,(6),联