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

离散数学数理逻辑2/26第四章一阶逻辑基本概念一阶逻辑命题符号化一阶逻辑公式及解释3/26一阶逻辑的引入在命题逻辑中,命题是最基本的单位,对简单命题不再进行分解,不关心命题中个体与总体的内在联系和数量关系.这就使得它难以描述和证明一些常见的推理.因此,需要对命题进行细化,建立更为精细的逻辑推理体系.例如:逻辑学中著名的三段论:凡偶数都能被2整除.6是偶数.所以,6能被2整除.这个推理是数学中的真命题,是正确的,但在命题逻辑中却无法判断其正确性,用p,q,r分别表示以上三个命题.则得到推理的形式结构为:(p∧q)→r由于上式不是重言式,因而不能由它判断推理的正确性.原因在于各命题的内在联系没有表示出来.为了克服命题逻辑的局限性,应该将原子命题再细分,分析出个体词,谓词和量词,以便达到表达出命题的内在联系和命题之间的逻辑关系.这就是一阶逻辑所研究的内容.4/26§4.1一阶逻辑命题符号化谓词逻辑命题符号化的三个基本要素:个体词,谓词,量词.1.个体词:研究对象中可以独立存在的具体的或抽象的客体.例如:小王,小张,马列主义,3,北京等都可做为个体词.注:(1)表示具体或特定客体的个体词称为个体常项,一般用小写字母a,b,c,…表示;(2)表示抽象或泛指的个体词称为个体变项,一般用小写字母x,y,z,…表示.个体变项的取值范围称为个体域(或论域).个体域可以是有限集合,如{1,2,3}或{a,b,c},也可以是无限集合,如自然数集合N或实数集合R.由宇宙间一切事物组成的个体域称为全总个体域.5/26谓词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(x1,x2,…,xn)表示含n(n≥1)个个体变项x1,x2,…,xn的n元谓词.它可看成以个体域为定义域,以{0,1}为值域的n元函数关系.当P取常项,且(x1,x2,…,xn)取定常项(a1,a2,…,an)时,P(a1,a2,…,an)是一个命题.6/26谓词续④不含个体变项的谓词称为0元谓词.例如F(a),G(a,b),P(a1,a2,…,an)等.当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)为假,故命题为假.7/26量词的引入有了个体词和谓词的概念之后,有些命题还是不能准确地符号化.以前面所讨论的三段论为例:令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)”没有把命题中“凡”的意思表示出来.即缺少表示个体常项或变项的数量关系的词.所以还要引入量词的概念.8/26量词量词:表示个体常项或变项之间数量关系的词.量词只有两个:全称量词,存在量词.(1)全称量词:表示“全部”含义的词.全称量词符号化为“”.a.常用语中“全部”,“所有的”,“一切”,“每一个”,“任何”,“任意的”,“凡”,“都”等词都是全称量词.b.xF(x)表示个体域里所有个体都有性质F.(2)存在量词:表示“存在”含义的词.存在量词符号化为“”.a.常用词中“存在”,“有一个”,“有的”,“至少有一个”等词都是存在量词.b.xF(x)表示个体域中存在个体具有性质F.例:凡偶数都能被2整除.可符号化为:x(P(x)→S(x))是真命题,其中x不再起变元的作用,它被全称量词限制住了,这时我们称x被量化了.9/26一阶逻辑中命题符号化例个体域为人类集合,将下面两个命题符号化:(1)凡是人都要呼吸;(2)有的人用左手写字.解令F(x):x呼吸;G(x):x用左手写字.则(1)xF(x);(2)xG(x)。例上例中,将个体域改为全总个体域,两命题的符号化形式如何?解令F(x):x呼吸;G(x):x用左手写字；M(x):x是人.则:(1)x(M(x)→F(x));(2)x(M(x)∧G(x)).①特性谓词:从全总个体域中分离出一个集合,定义的谓词.②在不同个体域中,同一个命题的符号化形式可能不同.一般地,对全称量词,特性谓词应作为蕴含式的前件.一般地,对存在量词,特性谓词应作为合取式的一项.③同一个命题,在不同个体域中的真值也可能不同.如果问题中没有指明个体域时,默认为全总体域.10/26一阶逻辑中命题符号化续④当F是谓词常项时,xF(x)是个命题,如果把个体域中的任何一个个体a代入,F(a)都为真,则xF(x)为真;否则xF(x)为假.⑤当F是谓词常项时,xF(x)是个命题,如果个体域中存在一个个体a使F(a)为真,则xF(x)为真;否则xF(x)为假.例在个体域限制为(a)和(b)条件时,将下列命题符号化,并给出它们的真值.(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)都是真命题.11/26一阶逻辑中命题符号化续例将下列命题符号化,并讨论其真值.(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))真命题12/26n元谓词的符号化(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))).13/26注1.分析命题中表示性质和关系的谓词,分别符号化为一元和n元谓词(n≥2).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|ε)))14/26§4.2一阶逻辑公式及解释非逻辑符号:个体词常项符号,函数符号和谓词符号逻辑符号:个体词变项符号,量词符号,联结词符号和括号与逗号定义设L是一个非逻辑符号,由L生成的一阶语言L的字母表包括下述符号如下:非逻辑符号(1)L中的个体常项符号:a,b,c,…;ai,bi,ci,…,i≥1(2)L中的函词符号:f,g,h,…;fi,gi,hi,…,i≥1(3)L中的谓词符号:F,G,H,…;Fi,Gi,Hi,…,i≥1逻辑符号(4)个体变项符号:x,y,z,…;xi,yi,zi,…,i≥1(5)量词符号:,.(6)联结词符号:┐,∧,∨,→,↔.(7)逗号与括号:,,().15/26项与原子公式定义一阶语言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的原子公式16/26合式公式定义一阶语言L中的合式公式(也称为谓词公式或公式)定义如下:(1)原子公式是合式公式;(2)若A是合式公式,则(┐A)也是合式公式;(3)若A,B是合式公式,则(A∧B),(A∨B),(A→B),(A↔B)也是合式公式;(4)若A是合式公式,则xA,xA也是合式公式;(5)只有有限次应用(1)~(4)构成的符号串才是合式公式.定义在公式xA和xA中,称x为指导变元,A为相应量词的辖域.在x和x的辖域中,x的所有出现都称为约束出现,A中不是约束出现的其它变项都称为自由出现.17/26辖域例指出下列公式中的指导变元,各量词的辖域,自由出现和约束出现的个体变项:(1)x(F(x,y)→G(x,z));(2)x(F(x)→G(y))→y(H(x)∧L(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是自由出现.18/26闭式定义设A是任意的公式,若A中不含自由出现的个体变项,则称A为封闭的公式,简称闭式.例如xyH(x,y),xy(F(x)∧F(y)→┑L(x,y)),x(F(x)→G(x))∧F(a)→G(a)例将下列两个公式中的变项指定为常项使其成为命题:(1)x(F(x)→G(x))(2)xy(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是实数x≠yx＞yx2+y22xy命题:对于任意的x,y,若x与y都是实数且x≠y,则x2+y2＞2xy.真值为真.19/26解释在前面例子中对各种变项的指