离散数学第四章 一阶逻辑基本概念.ppt

谓词逻辑（一阶逻辑）简介谓词逻辑（一阶逻辑）简介引言引言实例：所有偶数都能被实例：所有偶数都能被2 2整除整除.6.6是偶数是偶数.所以所以,6,6能被能被2 2整除整除.这个推理是数学中的真命题，但在命题逻辑中无法这个推理是数学中的真命题，但在命题逻辑中无法判断它的正确性判断它的正确性.理由：理由：在命题逻辑中，把它可符号化为：在命题逻辑中，把它可符号化为：p p q q r.r.110 110是上式的成假赋值，所以是上式的成假赋值，所以p p q q r r不是重不是重言式言式.问题？问题？解决办法？解决办法？拆分，揭示命题内部结构及其关系拆分，揭示命题内部结构及其关系.1谓词逻辑（一阶逻辑）简介谓词逻辑（一阶逻辑）简介引言引言实例：张三是学生实例：张三是学生.李四是学生李四是学生.设设p:p:张三是学生张三是学生.q:.q:李四是学生李四是学生.二者毫无关系二者毫无关系,但事但事实并非如此实并非如此.共同的特征：共同的特征：“是学生是学生.”问题？简单命题是基本单位问题？简单命题是基本单位.解决办法？解决办法？拆分，主语拆分，主语+谓语，揭示命题内部结构及其关系谓语，揭示命题内部结构及其关系.2第四章第四章 一阶逻辑基本概念一阶逻辑基本概念l一阶逻辑命题符号化一阶逻辑命题符号化l一阶逻辑公式及其解释一阶逻辑公式及其解释第五章第五章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理l一阶逻辑等值式与基本的等值式一阶逻辑等值式与基本的等值式l置换规则、换名规则、代替规则置换规则、换名规则、代替规则l前束范式前束范式l自然推理系统自然推理系统N NL L及其推理规则及其推理规则谓词逻辑（一阶逻辑）简介谓词逻辑（一阶逻辑）简介3主要内容主要内容l一阶逻辑命题符号化一阶逻辑命题符号化 个体词、谓词、量词个体词、谓词、量词 一阶逻辑命题符号化一阶逻辑命题符号化l一阶逻辑公式及其解释一阶逻辑公式及其解释 一阶语言一阶语言 合式公式合式公式 合式公式的解释合式公式的解释 永真式、矛盾式、可满足式永真式、矛盾式、可满足式第四章第四章 一阶逻辑基本概念一阶逻辑基本概念4基本要求：基本要求：1.1.准确地将给定命题符号化准确地将给定命题符号化.分清各种符号化形式，如在符分清各种符号化形式，如在符号化形式号化形式(1)-(7)(1)-(7)中特别要注意两个基本公式中特别要注意两个基本公式(3)(3)与与(4)(4)中中量词与联结词的搭配情况，其实量词与联结词的搭配情况，其实(5)(5)、(6)(6)、(7)(7)都是两个都是两个基本公式的应用基本公式的应用2.2.深刻理解永真式、矛盾式、可满足式的概念和判别方法。深刻理解永真式、矛盾式、可满足式的概念和判别方法。3.3.深刻理解闭式的概念及性质（闭式在任何解释下都是命题）深刻理解闭式的概念及性质（闭式在任何解释下都是命题）.4.4.对于给定的解释对于给定的解释I I，会在解释，会在解释I I下解释公式，判断公式是否下解释公式，判断公式是否是命题，是真命题，还是假命题。是命题，是真命题，还是假命题。第四章第四章 一阶逻辑基本概念一阶逻辑基本概念54.1 4.1 一阶逻辑命题符号化一阶逻辑命题符号化 主要内容主要内容 一、一、一阶逻辑命题符号化一阶逻辑命题符号化3 3个基本要素个基本要素 1.1.个体词个体词 2.2.谓词谓词 3.3.量词量词 二、二、一阶逻辑命题符号化一阶逻辑命题符号化 符号化形式符号化形式(1)-(7)(1)-(7)64.1 4.1 一阶逻辑命题符号化一阶逻辑命题符号化 在谓词逻辑中，一个简单命题被分解成在谓词逻辑中，一个简单命题被分解成个体词个体词和和谓词谓词两个部分两个部分例如，考察下列句子例如，考察下列句子（1 1）北京北京是中国的首都是中国的首都.（2 2）离散数学离散数学是计算机的基础课程是计算机的基础课程.（3 3）雪雪是白的是白的.（4 4）中国人中国人是很聪明的是很聪明的.个体词个体词所研究对象中可以独立存在的具体或抽象的客体所研究对象中可以独立存在的具体或抽象的客体 个体常项个体常项：具体的事务，用：具体的事务，用a a,b b,c c表示表示 个体变项个体变项：抽象的事物，用：抽象的事物，用x x,y y,z z表示表示 个体域个体域(论域论域)个体变项的取值范围个体变项的取值范围 有限个体域，如有限个体域，如 a a,b b,c c,1,2,1,2 无限个体域，如无限个体域，如 N,Z,R,N,Z,R,全总个体域全总个体域由宇宙间一切事物组成由宇宙间一切事物组成7谓谓 词词谓词谓词表示个体词性质或相互之间关系的词表示个体词性质或相互之间关系的词.谓词常项谓词常项 如如,F F(a a)：a a是人是人谓词变项谓词变项 如如,F F(x x)：x x具有性质具有性质n n（n n 1 1）元谓词）元谓词含含n n个命题变项的谓词，个命题变项的谓词，记作记作F F(x x1 1,x x2 2 x xn n)一元谓词一元谓词(n n=1)=1)表示性质表示性质 多元谓词多元谓词(n n 2)2)表示事物之间的关系表示事物之间的关系例如例如,L L(x x,y y)：x x与与 y y 有关系有关系 L L，L L(x x,y y)：x x y y，0 0元谓词元谓词不含个体变项的谓词不含个体变项的谓词.实际上就是一般的命题实际上就是一般的命题8实实 例例1 1例例1 1 用用0 0元谓词将命题符号化元谓词将命题符号化 (1)(1)墨西哥位于南美洲墨西哥位于南美洲 (2)(2)是无理数仅当是无理数仅当 是有理数是有理数 (3)(3)如果如果2323，则，则343323，q q：34.3 y y，G G(x x,y y)：x x 323，则，则343y x(F(x)y(G(y)L(x,y)或者或者 x y(F(x)G(y)L(x,y)(2)令令F(x)：x是无理数，是无理数，G(y)：y是有理数，是有理数，L(x,y)：xy x(F(x)y(G(y)L(x,y)或者或者 x y(F(x)G(y)L(x,y)14实例实例4例例4 在一阶逻辑中将下面命题符号化在一阶逻辑中将下面命题符号化 (1)没有不呼吸的人没有不呼吸的人 (2)不是所有的人都喜欢吃糖不是所有的人都喜欢吃糖解解(1)F(x):x是人是人,G(x):x呼吸呼吸x(F(x)G(x)x(F(x)G(x)(2)F(x):x是人是人,G(x):x喜欢吃糖喜欢吃糖 x(F(x)G(x)x(F(x)G(x)15实例实例5例例5 设个体域为实数域设个体域为实数域,将下面命题符号化将下面命题符号化 (1)对每一个数对每一个数x都存在一个数都存在一个数y使得使得xy (2)存在一个数存在一个数x使得对每一个数使得对每一个数y都有都有xy解解 L(x,y):xx1010,G G(x x):):x x00 真命题真命题24解释解释定义定义4.74.7 设一阶语言设一阶语言L L 的个体常项集的个体常项集 a ai i|i i 1,1,函数符函数符号集号集 f fi i|i i 1,1,谓词符号集谓词符号集 F Fi i|i i 1,1,L L 的的解释解释I I由下由下面面4 4部分组成部分组成:(1)(1)非空个体域非空个体域D DI I(2)(2)对每一个个体常项对每一个个体常项a ai i,D DI I,称作称作a ai i在在I I中的解释中的解释(3)(3)对每一个函数符号对每一个函数符号f fi i,设其为设其为m m元的元的,是是D DI I上的上的m m元函数元函数,称作称作f fi i在在I I中的解释中的解释(4)(4)对每一个谓词符号对每一个谓词符号F Fi i,设其为设其为n n元的元的,是一个是一个n n元元谓词谓词,称作称作F Fi i在在I I中的解释中的解释25实例实例例例4.4.8 给定解释给定解释I I 如下如下:(a)个体域个体域 D=N (b)(c)(d)谓词谓词说明下列公式在说明下列公式在 I 下的含义下的含义,并讨论其真值并讨论其真值 (1)xF(g(x,a),x)x(2x=x)假命题假命题(2)x y(F(f(x,a),y)F(f(y,a),x)x y(x+2=yy+2=x)假命题假命题26实例实例(续续)(3)x y zF(f(x,y),z)(5)F(f(x,a),g(x,a)(4)xF(f(x,x),g(x,x)x(2x=x2)真命题真命题 x y z(x+y=z)真命题真命题(6)x(F(x,y)F(f(x,a),f(y,a)x(x=yx+2=y+2)真命题真命题x+2=2x 不是命题不是命题27闭式的性质闭式的性质定理4.1 闭式在任何解释下都变成命题.例8(1)(4)都是闭式,在I下全是命题.(5)和(6)不是闭式,在I下(5)不是命题,(6)是命题28一阶逻辑公式的分类一阶逻辑公式的分类永真式永真式(逻辑有效式逻辑有效式):无成假解释无成假解释矛盾式矛盾式(永假式永假式):无成真解释无成真解释可满足式可满足式:至少有一个成真解释至少有一个成真解释在一阶逻辑中在一阶逻辑中,公式的可满足性公式的可满足性(永真性永真性,永假性永假性)是不可是不可判定的判定的,即不存在算法能在有限步内判断任给的公式是否即不存在算法能在有限步内判断任给的公式是否是可满足式是可满足式(永真式永真式,矛盾式矛盾式)29代换实例代换实例定定义义4.9 4.9 设设A A0 0是是含含命命题题变变项项p p1 1,p p2 2,p pn n的的命命题题公公式式,A A1 1,A A2 2,A An n是是n n个个谓谓词词公公式式,用用A Ai i处处处处代代替替A A0 0中中的的p pi i(1(1 i i n n),),所得公式所得公式A A称为称为A A0 0的的代换实例代换实例.例如例如F F(x x)G G(x x),),xFxF(x x)yGyG(y y)等都是等都是p pq q的代换实例的代换实例 定理定理4.24.2 重言式的代换实例都是永真式，矛盾式的代换实重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式例都是矛盾式.30实例实例例例4.94.9 判断下列公式的类型判断下列公式的类型:(1)(1)x x(F F(x x)G G(x x)非永真式的可满足式非永真式的可满足式(2)(xF(x)(xF(x)这是这是 p p p p 的代换实例的代换实例,p p p p是重言式是重言式,取解释取解释I1,D1=R,:x是整数是整数,:x是有理数是有理数,真命题真命题永真式永真式(3)(xF(x)yG(y)yG(y)这这是是(pq)q的的代代换换实实例例,(pq)q是是矛矛盾盾式式矛盾式矛盾式取取解解释释I2,D2=R,:x是是整整数数,:x是是自自然然数数,假假命命题题31第四章第四章 习题课习题课主要内容主要内容l个体词、谓词、量词个体词、谓词、量词l一阶逻辑命题符号化一阶逻辑命题符号化l一一阶语言言L L 项、原子公式、原子公式、合式公式合式公式l公式的解释公式的解释 量词的辖域、指导变元、个体变项的自由出现与约束出现、量词的辖域、指导变元、个体变项的自由出现与约束出现、闭式、解释闭式、解释l公式的类型公式的类型 永真式永真式(逻辑有效式逻辑有效式)、矛盾式、矛盾式(永假式永假式)、可满足式、可满足式32基本要求基本要求l 准确地将给定命题符号化准确地将给定命题符号化l 理解一阶语言的概念理解一阶语言的概念l 深刻理解一阶语言的解释深刻理解一阶语言的解释l 熟练地给出公式的解释熟练地给出公式的解释l 记住闭式的性质并能应用它记住闭式的性质并能应用它l 深刻理解永真式、矛盾式、可满足式的概念深刻理解永真式、矛盾式、可满足式的概念,会判断简会判断简 单公式的类型单公式的类型33练习练习11.在分别取个体域在分别取个体域 2.(a)D1=N (b)D2=R (c)D3为全总个体域为全总个体域的条件下的条件下,将下面命题符号化，并讨论真值将下面命题符号化，并讨论真值 (1)对于任意的数对于任意的数x，均有，均有(b)xG(x)(c)又设又设F(x):x是实数是实数 x(F(x)G(x)真真 真真(a)xG(x)解解假假设：设：G G（x):x):34练习练习1(续续)解解 设设H(x)：x+7=5 (a)xH(x)(2)存在数存在数x，使得，使得 x+7=5(b)xH(x)(c)又设又设F(x)：x为实数为实数 x(F(x)H(x)本例说明：不同个体域内，命题符号化形式可能不同（也可本例说明：不同个体域内，命题符号化形式可能不同（也可能相同），真值可能不同（也可能相同）能相同），真值可能不同（也可能相同）.真真真真假假35练习练习22.在一阶逻辑中将下列命题符号化在一阶逻辑中将下列命题符号化 (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)36练习练习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一样高一样高 x(F(x)y(F(y)H(x,y)L(x,y)或或 x y(F(x)F(y)H(x,y)L(x,y)设设F(x):x是汽车是汽车,G(y):y是火车是火车,H(x,y):x比比y快快 x y(F(x)G(y)H(x,y)或或 x y(F(x)G(y)H(x,y)37练习练习3 x(2x=x)假假3.给定解释给定解释 I 如下如下:(a)个体域个体域D=N (b)=2 (c)(d)说明下列公式在说明下列公式在 I 下的涵义下的涵义,并讨论真值并讨论真值 (1)xF(g(x,a),x)(2)x y(F(f(x,a),y)F(f(y,a),x)x y(x+2=yy+2=x)假假38练习练习3(3)x y zF(f(x,y),z)(5)xF(f(x,x),g(x,x)(4)x y zF(f(y,z),x)x y z(y+z=x)假假 x y z(x+y=z)真真 x(x+x=x x)真真(3),(4)说明说明 与与 不能随意交换不能随意交换39练习练习44.证明下面公式既不是永真式，也不是矛盾式证明下面公式既不是永真式，也不是矛盾式:(1)x(F(x)G(x)(2)x y(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 假假40练习练习55.证明下列公式为永真式证明下列公式为永真式:(1)(xF(x)yG(y)xF(x)yG(y)(2)x(F(x)(F(x)G(x)(AB)AB的代换实例的代换实例设设I是任意的一个解释是任意的一个解释,对每一个对每一个x DI,F(x)(F(x)G(x)恒为真恒为真41