第四部分一阶逻辑基本概念教学课件.ppt

第四章:一阶逻辑基本概念,本章的主要内容一阶逻辑命题符号化一阶逻辑公式、解释及分类本章与其他章的联系克服命题逻辑的局限性是第五章的先行准备,第一节：一阶逻辑命题符号化,4.1 一阶逻辑命题符号化,例子凡是人都要死 pq苏格拉底是人 r推出：苏格拉底要死？命题逻辑的表示能力缺陷命题演算的基本单元为简单命题不能研究命题的结构、成分和内部逻辑的特征不能表达二个原子命题所具有的共同特征，无法处理一些简单又常见的推理,命题之间的联系无法刻画,4.1 一阶逻辑命题符号化,一阶逻辑对命题做进一步分解揭示命题的内部结构以及命题间的内在联系命题分解个体词（名词、代词）谓词量词例：南京是城市个体词：南京谓词：是城市,4.1 一阶逻辑命题符号化,个体词：研究对象中独立存在的具体或抽象的个体个体常项：具体或特定的个体词南京，东南大学，1，2个体变项：抽象或泛指的个体词x,y,z 取值范围称为个体域或论域空集不能作为论域全总个体域：宇宙间一切事物,4.1 一阶逻辑命题符号化,谓词：刻画个体词性质及个体词之间的关系的词谓词常项：具体性质或关系的谓词F(a,b)：小王和小李是同学G(x)：x是有理数谓词变项：抽象或泛指的性质或关系的谓词L(x,y)：x,y具有关系Ln元谓词P(x1,xn)P(x1,xn):DnF,T，D为个体域不带个体变项的谓词为0元谓词，当为谓词常项时，即命题,4.1 一阶逻辑命题符号化,例:将下列命题用0元谓词符号化2既是素数又是偶数F(x)：x是素数G(x)：x是偶数a:2F(a)G(a)例:将下列命题用0元谓词符号化如果35，则23F(x,y):xya:3,b:5,c:2F(a,b)F(c,a),4.1 一阶逻辑命题符号化,量词：表示个体常项或变项之间数量关系的词全称量词：x表示个体域里的所有个体x对应日常语言中的“一切的”、“所有的”等一元谓词F(x)个体域为D，xF(x)真值xF(x)为真：F(a)为真，对所有aDxF(x)为假：F(a)为假，对某个aDxyG(x,y)：个体域里所有个体x,y有关系GxyG(x,y)为真：G(a,b)为真，对所有a,bDxyG(x,y)为假：G(a,b)为假，对某对a,bD,4.1 一阶逻辑命题符号化,存在量词：x表示个体域里有一个个体x对应日常语言中的“存在”、“有一个”等一元谓词F(x)个体域为D，xF(x)真值xF(x)为真：F(a)为真，存在某个aDxF(x)为假：F(a)为假，对任意aDxyG(x,y)：个体域里存在个体x,y有关系G全称量词与存在量词联合xyG(x,y)：个体域里任意x,存在个体y,x,y有关系GxyG(x,y)：个体域里存在x和所有个体y都有关系G,4.1 一阶逻辑命题符号化,讨论：xF(x),xF(x),F(x)的联系、区别F(x)是不能确定真值的谓词xF(x),xF(x)都是命题x称为约束变元,4.1 一阶逻辑命题符号化,例：将下列命题符号化凡是人都呼吸（个体域为人类集合）F(x):x呼吸xF(x)有的人用左手写字（个体域为人类集合）G(x):x用左手写字xG(x)凡是人都呼吸（个体域为全总个体域）F(x):x呼吸,M(x):x是人x（M(x)F(x)有的人用左手写字（个体域为全总个体域）G(x):x用左手写字,M(x):x是人x(M(x)G(x),4.1 一阶逻辑命题符号化,例：将下列命题符号化并判断真假值所有有理数都是整数（个体域为有理数集合）F(x):x是整数xF(x)所有有理数都是整数（个体域为实数集合）F(x):x是整数,Q(x):x是有理数x（Q(x)F(x),4.1 一阶逻辑命题符号化,例：将下列命题符号化并判断真假值任意x，x2-3x+2=(x-1)(x-2)（个体域为自然数集合）F(x):x2-3x+2=(x-1)(x-2)xF(x)存在x,x+5=3（个体域为自然数集合）G(x):x+5=3xG(x)任意x，x2-3x+2=(x-1)(x-2)（个体域为实数集合）存在x,x+5=3（个体域为实数集合）,4.1 一阶逻辑命题符号化,谓词逻辑符号化几点说明不同的个体域，符号化形式可能不一样，命题真值也可能不同一般默认是全总个体域，即包含一切个体特性谓词：描述个体变元取值范围的谓词全称量化中，特性谓词常作为蕴涵式的前件x（M(x)F(x)存在量化中，特性谓词常作为合取项之一x(M(x)G(x),4.1 一阶逻辑命题符号化,例：将下列命题符号化并判断真假值凡是学生都需要学习和考试在北京工作的人未必是北京人没有人登上过木星,4.1 一阶逻辑命题符号化,例：将下列命题符号化并判断真假值凡是学生都需要学习和考试F(x):x是学生；G(x)：x学习；H(x)：x考试x(F(x)G(x)H(x)在北京工作的人未必是北京人F(x):x在北京工作；G(x)：x是北京人 x(F(x)G(x)x(F(x)G(x)没有人登上过木星M(x):x是人；H(x)：x登上过木星 x(M(x)H(x),4.1 一阶逻辑命题符号化,例：将下列命题符号化不存在跑得同样快的两只兔子有的兔子比所有的乌龟跑得快尽管有些人聪明，未必所有人都聪明,4.1 一阶逻辑命题符号化,例：将下列命题符号化不存在跑得同样快的两只兔子F(x)：x是兔子，L(x,y):x和y跑得同样快 xy(F(x)F(y)L(x,y)有的兔子比所有的乌龟跑得快F(x)：x是兔子，G(y)：y是乌龟，H(x,y):x比y跑得快 x(F(x)y(G(y)H(x,y)尽管有些人聪明，未必所有人都聪明F(x):x是人；G(x)：x聪明x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)x(F(x)G(x),4.1 一阶逻辑命题符号化,注意事项根据命题的实际意义选取全称量词或存在量词多个量词同时出现时，不能随意颠倒顺序符号化：对任意的x，存在着y，使得x+y=5给定实数域F(x,y)：x+y=5xyF(x,y)不同于yxF(x,y),T,F,4.1 一阶逻辑命题符号化,例子凡是人都要死 苏格拉底是人 推出：苏格拉底要死？F(x):x是人；G(x):x要死a:苏格拉底x(F(x)G(x)F(a)G(a),第二节：一阶逻辑公式及其解释,4.2一阶逻辑公式及其解释,一阶谓词语言的字母表非逻辑符号个体常项符号：a,b,c,函数符号：f,g,h,谓词符号：F,G,H,逻辑符号个体变项符号：x,y,z,量词符号：，联结词符号：，括号与逗号：(，)，函数符号不同于谓词符号,一阶谓词语言的项：个体常项符号和个体变项符号是项若f(x1,xn)是n元函数符号，t1,tn是n个项，则f(t1,tn)是项有限次使用，生成的符号串才是项例：下列符号串是否为项？a,bx,yf(x,y)：x+y;f(a,y):a-yf(f(a,b),b)：f(a,b)+b,4.2一阶逻辑公式及其解释,一阶谓词语言的原子公式：F(x1,xn)为n元谓词符号t1,tn为n个项F(t1,tn)为的原子公式例：下列符号串为原子公式F(a,b)F(x,y)F(f(x,y),a),4.2一阶逻辑公式及其解释,一阶谓词语言的合式公式（谓词公式）：原子公式是合式公式 A为合式公式，则A是合式公式 A，B为合式公式,则(AB),(AB),(AB),(AB)为合式公式如A是合式公式，则xA,xA也是合式公式只有有限次应用1-4构成的符号串才是合式公式,4.2一阶逻辑公式及其解释,例子F(a,b)F(a,b)G(x,y)F(a,b)xG(x,y)x(F(a,b)G(x,y)(y)(x)(G(x,y),4.2一阶逻辑公式及其解释,4.2一阶逻辑公式及其解释,辖域：紧接在量词后面括号内的合式公式x P(x)，x(P(x)Q(x)x M(x)D(x)自由变元与指导变元指导变元：出现在量词x,x辖域内的变元xx M(x)D(x)自由变元：非约束出现的变元x M(x)D(x)闭式（封闭公式）：不含自由出现的个体变项的公式,4.2一阶逻辑公式及其解释,例：指出下列公式中的指导变元，各量词的辖域，自由出现和约束出现的个体变项F(a,b)xG(x,y)x(F(a,b)G(x,y)x(F(a,x)y(G(x,y)H(z),4.2一阶逻辑公式及其解释,如何赋予合式公式含义？定义域函数变项需要指定具体函数谓词变项需要指定具体谓词,4.2一阶逻辑公式及其解释,例：xy(F(x)F(y)G(f(x,y),g(x,y)定义域：全总个体域函数变项需要指定具体函数f(x,y)：x+yg(x,y)：xy谓词变项需要指定具体谓词F(x)：x是实数G(x,y)：x=y,任意x,y，如果x,y是实数，则x+y=xy,4.2一阶逻辑公式及其解释,解释：非逻辑符号集L生成的一阶语言，的解释I由4部分组成非空个体域DII将任意一个个体常项符号aL映射到DI上的个体a*I将任意一个n元函数fL映射到DI上的n元函数f*:(DI)n DII将任意一个n元谓词FL映射到DI上的n元关系RF,4.2一阶逻辑公式及其解释,公式A在I下的解释AI：取个体域DIA中个体常项符号aL替换为DI上的个体a*A中的n元函数fL替换为DI上的n元函数f*:(DI)n DIA中n元谓词FL替换为DI上的n元关系RF,4.2一阶逻辑公式及其解释,给定解释I个体域为自然数集Na*=2f*=x+y,g*=xyF*：x=y给出下列公式在I下的解释，讨论真假值x F(g(x,y),z)x(F(g(x,a),x)F(x,f(x,a)x F(g(x,a),x)F(x,y),4.2一阶逻辑公式及其解释,给定解释I个体域为自然数集Na*=2f*=x+y,g*=xyF*：x=y给出下列公式在I下的解释，讨论真假值x F(g(x,y),z)x(xy=z)x(F(g(x,a),x)F(x,f(x,a)x(2x=x)(x=x+2)x F(g(x,a),x)F(x,y)x(2x=x)x=y,4.2一阶逻辑公式及其解释,合式公式分类：公式A重言式(永真式)：A在任意的解释下为真矛盾式(永假式)：A在任意的解释下为假可满足式：A在某个解释下为真,4.2一阶逻辑公式及其解释,代换实例给定命题公式A0，含命题变项p1,pnA1,An是n个谓词公式A称为A0的代换实例,如果A通过用Ai代替A0中的pi得到,4.2一阶逻辑公式及其解释,定理：重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式 证明思路：给定重言式A0，对于命题变项p1,pn的任意赋值，A0都为真例：已知p(qp)为重言式，那么 F(x)(G(x)F(x)是否是重言式？x(F(x)(G(x)F(x)呢？,4.2一阶逻辑公式及其解释,例：判断下列公式类型x F(x)x F(x)x(F(x)G(x)(xF(x)yG(y)yG(y),4.2一阶逻辑公式及其解释,例：判断下列公式类型x F(x)x F(x)对任意解释I，如果I使得x F(x)为真，对任意xDI，F(x)为真，I必使得x F(x)为真x(F(x)G(x)解释I：DI 为实数集RF(x):x是整数；G(x):x是有理数(xF(x)yG(y)yG(y)是(p q)q 的代换实例,永真式,矛盾式,可满足式,4.2一阶逻辑公式及其解释,第四章 习题课,主要内容个体词、谓词、量词一阶逻辑命题符号化一阶语言L 项、原子公式、合式公式公式的解释 量词的辖域、指导变元、个体变项的自由出现与约束出现、闭式、解释公式的类型 永真式(逻辑有效式)、矛盾式(永假式)、可满足式,基本要求,准确地将给定命题符号化 理解一阶语言的概念 深刻理解一阶语言的解释 熟练地给出公式的解释深刻理解永真式、矛盾式、可满足式的概念,会判断简 单公式的类型,练习1,1.在分别取个体域为(a)D1=N(b)D2=R(c)D3为全总个体域的条件下,将下面命题符号化，并讨论真值:对于任意的数x，均有,解 设G(x):(a)xG(x),(b)xG(x),(c)又设F(x):x是实数 x(F(x)G(x),真,真,假,练习2,2.在一阶逻辑中将下列命题符号化(1)大熊猫都可爱,(2)有人爱发脾气,(3)说所有人都爱吃面包是不对的,(4)没有不爱吃糖的人,(5)任何两个不同的人都不一样高,(6)不是所有的汽车都比所有的火车快,练习2,2.在一阶逻辑中将下列命题符号化(1)大熊猫都可爱,(2)有人爱发脾气,(3)说所有人都爱吃面包是不对的,设F(x):x为大熊猫，G(x):x可爱 x(F(x)G(x),设F(x):x是人，G(x):x爱发脾气 x(F(x)G(x),设F(x):x是人，G(x):x爱吃面包 x(F(x)G(x)或 x(F(x)G(x),练习2,(4)没有不爱吃糖的人,(5)任何两个不同的人都不一样高,(6)不是所有的汽车都比所有的火车快,设F(x):x是人，G(x):x爱吃糖x(F(x)G(x)或 x(F(x)G(x),设F(x):x是人,H(x,y):x与y相同,L(x,y):x与y一样高 xy(F(x)F(y)H(x,y)L(x,y),设F(x):x是汽车,G(y):y是火车,H(x,y):x比y快 xy(F(x)G(y)H(x,y)或 xy(F(x)G(y)H(x,y),练习3,3.给定解释 I 如下:(a)个体域D=N(b)=2(c)(d)说明下列公式在 I 下的涵义,并讨论真值(1)xF(g(x,a),x),(2)xy(F(f(x,a),y)F(f(y,a),x),(3)xyzF(f(x,y),z),(4)xyzF(f(y,z),x),(5)xF(f(x,x),g(x,x),练习3,x(2x=x)假,3.给定解释 I 如下:(a)个体域D=N(b)=2(c)(d)说明下列公式在 I 下的涵义,并讨论真值(1)xF(g(x,a),x),(2)xy(F(f(x,a),y)F(f(y,a),x),xy(x+2=yy+2=x)假,练习3,(3)xyzF(f(x,y),z),(5)xF(f(x,x),g(x,x),(4)xyzF(f(y,z),x),xyz(y+z=x)假,xyz(x+y=z)真,x(x+x=xx)真,(3),(4)说明与不能随意交换,练习4,4.证明下面公式既不是永真式，也不是矛盾式:,(1)x(F(x)G(x),(2)xy(F(x)G(y)H(x,y),练习4,4.证明下面公式既不是永真式，也不是矛盾式:,(1)x(F(x)G(x),(2)xy(F(x)G(y)H(x,y),解释1:D1=N,F(x):x是偶数,G(x):x是素数,真,解释2:D2=N,F(x):x是偶数,G(x):x是奇数,假,解释1:D1=Z,F(x):x是正数,G(x):x是负数,H(x,y):xy 真,解释2:D2=Z,F(x):x是偶数,G(x):x是奇数,H(x,y):xy 假,练习5,5.证明下列公式为永真式:(1)(xF(x)yG(y)xF(x)yG(y),(2)x(F(x)(F(x)G(x),练习5,5.证明下列公式为永真式:(1)(xF(x)yG(y)xF(x)yG(y),(2)x(F(x)(F(x)G(x),(AB)AB的代换实例,设I是任意的一个解释,对每一个xDI,F(x)(F(x)G(x)恒为真,作业,1451011,