资源描述
1第第2章章 一阶逻辑一阶逻辑 2.1 一阶逻辑基本概念一阶逻辑基本概念2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释2.3 一阶逻辑等值式与前束范式一阶逻辑等值式与前束范式 22.1 一阶逻辑基本概念一阶逻辑基本概念 个体词个体词 谓词谓词 量词量词 一阶逻辑中命题符号化一阶逻辑中命题符号化 命题逻辑的局限性命题逻辑的局限性苏格拉底三段论：苏格拉底三段论：凡是人都要死的凡是人都要死的.苏格拉底是人苏格拉底是人.所以苏格拉底是要死的所以苏格拉底是要死的.在命题逻辑中，只能用在命题逻辑中，只能用p、q、r表示以上表示以上3个命题，个命题，上述推理可表成上述推理可表成 (pq)r这不是重言式这不是重言式34基本概念基本概念个体词、谓词、量词个体词、谓词、量词 个体词（个体）个体词（个体）:所研究对象中可以独立存在的具所研究对象中可以独立存在的具体或抽象的客体体或抽象的客体 个体常项个体常项：具体的事物，用：具体的事物，用a,b,c表示表示 个体变项个体变项：抽象的事物，用：抽象的事物，用x,y,z表示表示 个体域个体域:个体变项的取值范围个体变项的取值范围 有限个体域有限个体域，如，如a,b,c,1,2 无限个体域无限个体域，如，如N,Z,R,全总个体域全总个体域:宇宙间一切事物组成宇宙间一切事物组成 5基本概念基本概念(续续)谓词谓词:表示个体词性质或相互之间关系的词表示个体词性质或相互之间关系的词 谓词常项谓词常项：F(a)：a是人是人 谓词变项谓词变项：F(x)：x具有性质具有性质F 一元谓词一元谓词:表示事物的性质表示事物的性质 多元谓词多元谓词(n元谓词元谓词,n 2):表示事物之间的关系表示事物之间的关系 如如 L(x,y)：x与与y有关系有关系L，L(x,y)：x y，0元谓词元谓词:不含个体变项的谓词不含个体变项的谓词,即命题常项或命即命题常项或命题变项题变项 6基本概念基本概念(续续)量词量词:表示数量的词表示数量的词 全称量词全称量词:表示任意的表示任意的,所有的所有的,一切的等一切的等 如如 x 表示对个体域中所有的表示对个体域中所有的x 存在量词存在量词:表示存在表示存在,有的有的,至少有一个等至少有一个等 如如 x 表示在个体域中存在表示在个体域中存在x7一阶逻辑中命题符号化一阶逻辑中命题符号化 例例 用用0元谓词将命题符号化元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶要求：先将它们在命题逻辑中符号化，再在一阶 逻辑中符号化逻辑中符号化 (1)墨西哥位于南美洲墨西哥位于南美洲在命题逻辑中在命题逻辑中,设设 p:墨西哥位于南美洲墨西哥位于南美洲 符号化为符号化为 p 在一阶逻辑中在一阶逻辑中,设设a：墨西哥，：墨西哥，F(x)：x位于位于南美洲南美洲,符号化为符号化为F(a)8例例(续续)23 (2)是无理数仅当是无理数仅当 是有理数是有理数 2323在命题逻辑中在命题逻辑中,设设 p：是无理数，是无理数，q：是有理数是有理数.符号化为符号化为 p q)3()2(GF在一阶逻辑中在一阶逻辑中,设设F(x):x是无理数是无理数,G(x):x是有理数是有理数 符号化为符号化为在命题逻辑中在命题逻辑中,设设 p：23，q：3y，G(x,y)：x3，则，则3y 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)两者等值两者等值11一阶逻辑中命题符号化一阶逻辑中命题符号化(续续)几点注意：几点注意：1 1元谓词与多元谓词的区分元谓词与多元谓词的区分 无特别要求无特别要求,应使用全总个体域应使用全总个体域,引入特性谓词引入特性谓词 量词顺序一般不能随便颠倒量词顺序一般不能随便颠倒 两个基本形式两个基本形式 x(F(x)G(x)和和 x(F(x)G(x)的使用的使用 否定的表示，否定的表示，如如“没有不呼吸的人没有不呼吸的人”等同于等同于“所有的人都呼吸所有的人都呼吸”“不是所有的人都喜欢吃糖不是所有的人都喜欢吃糖”等同于等同于“存在不喜存在不喜欢吃糖的人欢吃糖的人”122.2 一阶逻辑公式及解释一阶逻辑公式及解释合式公式合式公式(简称公式简称公式)个体变项的自由出现和约束出现个体变项的自由出现和约束出现解释与赋值解释与赋值公式分类公式分类 永真式，矛盾式永真式，矛盾式,可满足式可满足式 13字母表字母表 定义定义 字母表字母表包含下述符号：包含下述符号：(1)个体常项：个体常项：a,b,c,ai,bi,ci,i 1 (2)个体变项：个体变项：x,y,z,xi,yi,zi,i 1 (3)函数符号：函数符号：f,g,h,fi,gi,hi,i 1 (4)谓词符号：谓词符号：F,G,H,Fi,Gi,Hi,i 1 (5)量词符号：量词符号：,(6)联结词符号：联结词符号：,(7)括号与逗号：括号与逗号：(,),，14项项 定义定义 项项的定义如下：的定义如下：(1)个体常项和个体变项是项个体常项和个体变项是项.(2)若若(x1,x2,xn)是任意的是任意的n元函数，元函数，t1,t2,tn是任意的是任意的n个项，则个项，则(t1,t2,tn)是项是项.(3)所有的项都是有限次使用所有的项都是有限次使用(1),(2)得到的得到的.个体常项、变项是项，由它们构成的个体常项、变项是项，由它们构成的n元函数和复元函数和复合函数还是项合函数还是项15原子公式原子公式 定义定义 设设R(x1,x2,xn)是任意的是任意的n元谓词，元谓词，t1,t2,tn是任意的是任意的n个项，则称个项，则称R(t1,t2,tn)是是原子公式原子公式.原子公式是由项组成的原子公式是由项组成的n元谓词元谓词.例如，例如，F(x,y),F(f(x1,x2),g(x3,x4)等均为原子公式等均为原子公式 16合式公式合式公式 定义定义 合式公式合式公式（简称（简称公式公式）定义如下：）定义如下：(1)原子公式是合式公式原子公式是合式公式.(2)若若A是合式公式，则是合式公式，则(A)也是合式公式也是合式公式 (3)若若A,B是合式公式，则是合式公式，则(A B),(A B),(AB),(AB)也是合式公式也是合式公式 (4)若若A是合式公式，则是合式公式，则 xA,xA也是合式公式也是合式公式 (5)只有有限次地应用只有有限次地应用(1)(4)形成的符号串是合形成的符号串是合 式公式式公式.如如 x 0,x(F(x)G(x),x y(x+y=1)17个体变项的自由出现与约束出现个体变项的自由出现与约束出现 定义定义 在公式在公式 xA和和 xA中，称中，称x为为指导变元指导变元，A为相为相应量词的应量词的辖域辖域.在在 x和和 x的的辖域辖域中，中，x的所有出现都的所有出现都称为称为约束出现约束出现，A中不是约束出现的其他变项均称中不是约束出现的其他变项均称为是为是自由出现自由出现.例如例如,在公式在公式 x(F(x,y)G(x,z)中中,A=(F(x,y)G(x,z)为为 x的辖域，的辖域，x为指导变元为指导变元,A中中x的两次出现均为约束出现，的两次出现均为约束出现，y与与z均为自由出现均为自由出现.闭式闭式:不含自由出现的个体变项的公式不含自由出现的个体变项的公式.18公式的解释与分类公式的解释与分类 给定闭式给定闭式 A=x(F(x)G(x)取个体域取个体域N,F(x):x2,G(x):x1 代入得代入得A=x(x2x1)真命题真命题给定非闭式给定非闭式 B=xF(x,y)取个体域取个体域N,F(x,y):x y 代入得代入得B=x(x y)不是命题不是命题令令y=1,B=x(x 1)假命题假命题19解释和赋值解释和赋值 定义定义 解释解释I由下面由下面4部分组成：部分组成：(a)非空个体域非空个体域DI (b)对每一个命题常项对每一个命题常项a 指定一个指定一个 DI (c)对每一个函数符号对每一个函数符号f指定一个指定一个DI上的函数上的函数 (d)对每一个谓词符号对每一个谓词符号F指定一个指定一个DI上的谓词上的谓词赋值赋值：对每一个命题变项：对每一个命题变项x指定一个值指定一个值(x)DI 公式公式A在解释在解释I和赋值和赋值 下的含义下的含义：取个体域取个体域DI,并将公式中出现的并将公式中出现的a、f、F 分别解释成分别解释成 、,把自由出现的把自由出现的x换成换成(x)后所得到的命题后所得到的命题.在给定的解释和赋值下在给定的解释和赋值下,任何公式都成为命题任何公式都成为命题.afFafF20实例实例例例 给定解释给定解释I I 如下如下:(a)个体域个体域 D=N (b)(c)(d)谓词谓词以及赋值以及赋值：(x)=0,(y)=1,(z)=2.说明下列公式在说明下列公式在 I 与与 下的涵义下的涵义,并讨论真值并讨论真值 (1)xF(g(x,a),y)2 axyyxgyxyxf ),(,),(yxyxF:),(x(2x=1)假命题假命题21例例(续续)(2)xF(f(x,a),y)yF(x,f(y,a)x(x+2=1)y(0=y+2)真命题真命题 x y z(x+y=z)真命题真命题(3)xF(f(x,y),g(x,z)x(x+1=2x)真命题真命题(5)x y zF(f(y,z),x)x y z(y+z=x)假命题假命题(4)x y zF(f(x,y),z)闭式只需要解释闭式只需要解释,如如(4),(5)22公式的分类公式的分类 永真式永真式(逻辑有效式逻辑有效式):在任何解释和赋值下为真命题在任何解释和赋值下为真命题矛盾式矛盾式(永假式永假式):在任何解释和赋值下为假命题在任何解释和赋值下为假命题可满足式可满足式：存在成真的解释和赋值：存在成真的解释和赋值说明：说明：永真式为可满足式，但反之不真永真式为可满足式，但反之不真谓词公式的可满足性（永真性谓词公式的可满足性（永真性,永假性永假性)是不可判是不可判定的定的23代换代换 定义定义 设设A0是含命题变项是含命题变项p1,p2,pn的命题公式，的命题公式，A1,A2,An是是n个谓词公式，用个谓词公式，用Ai处处代替处处代替A0中的中的pi (1 i n)，所得公式，所得公式A称为称为A0的的代换实例代换实例.如如 F(x)G(x),xF(x)yG(y)是是pq的代换实例的代换实例定理定理 重言式的代换实例都是永真式，矛盾式的代重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式换实例都是矛盾式.实例实例例例 判断下列公式的类型判断下列公式的类型(1)xF(x)xF(x)；24 设设I为任意的解释，若为任意的解释，若xF(x)为假，则为假，则xF(x)xF(x)为真为真.若若xF(x)为真，则为真，则xF(x)也为真，所以也为真，所以xF(x)xF(x)也为真也为真.是逻辑有效式是逻辑有效式.(2)xF(x)(xyG(x,y)xF(x)；重言式重言式p(qp)的代换实例，是逻辑有效式的代换实例，是逻辑有效式.例例(续续)(3)xF(x)(xF(x)yG(y)；25重言式重言式p(pq)的代换实例的代换实例,是逻辑有效式是逻辑有效式.(4)(F(x,y)R(x,y)R(x,y)；矛盾式矛盾式(pq)q的代换实例的代换实例,是矛盾式是矛盾式.例例(续续)(5)xyF(x,y)xyF(x,y).26取解释取解释I：个体域：个体域N,F(x,y)为为x=y.公式被解释为公式被解释为xy(x=y)xy(x=y)，其值为假，其值为假.解释解释I:个体域个体域N,F(x,y)为为x y,得到一个新的得到一个新的 在在I下下,公式被解释为公式被解释为xy(x y)xy(x y)，其值为真，其值为真.是非逻辑有效式的可满足式是非逻辑有效式的可满足式.例例(续续)(6)xF(x,y)27取解释取解释I：个体域：个体域N,F(x,y)为为xy.赋值赋值 1：1(y)=1.在在I和和 1下下,x(x1)，真命题，真命题.取解释取解释I:个体域个体域N,F(x,y)为为xy.赋值赋值 2：2(y)=0.在在I和和 2下下,x(x0)，假命题假命题是非逻辑有效式的可满足式是非逻辑有效式的可满足式.
展开阅读全文