第四章一阶逻辑基本概念.ppt

第四章第四章 一一阶逻辑阶逻辑基本概念基本概念 本章的主要内容本章的主要内容p 一一阶逻辑阶逻辑基本概念、命基本概念、命题题符号化符号化p 一一阶逻辑阶逻辑公式、解公式、解释释及分及分类类1.4.1 一一阶逻辑阶逻辑命命题题符号化符号化一、基本概念一、基本概念个体个体词词、谓词谓词、量、量词词（1）个体常）个体常项项：具体的事：具体的事务务，用，用a,b,c表示表示（2）个体）个体变项变项：抽象的事物，用：抽象的事物，用x,y,z表示表示（3）个体域）个体域个体个体变项变项的取的取值值范范围围 有限个体域，如有限个体域，如a,b,c,1,2 无限个体域，如无限个体域，如N,Z,R,全全总总个体域个体域宇宙宇宙间间一切事物一切事物组组成成1个个体体（个个体体词词）所所研研究究对对象象中中可可以以独独立立存存在的具体或抽象的客体（名在的具体或抽象的客体（名词词或代或代词词充当）充当）2.2.谓词谓词表示个体表示个体词词性性质质或相互之或相互之间间关系的关系的词词（1）谓词谓词常常项项：F:是人，是人，F(a)：a是人是人（2）谓词变项谓词变项：F:具有性具有性质质F，F(x)：x具有性具有性质质F（3）n（n 1）元）元谓词谓词 n=1，一元，一元谓词谓词表示性表示性质质 n 2，多元，多元谓词谓词表示事物之表示事物之间间的关系的关系L(x,y)：x与与y有关系有关系L，L(x,y)：x y，(4)0元元谓谓词词不不含含个个体体变变项项的的谓谓词词(命命题题常常项项或或变项变项)3.3量量词词表示数量的表示数量的词词（1）全称量）全称量词词：“”，x（2）存在量）存在量词词：“”，x 4.例例 用用0元元谓词谓词将命将命题题符号化：符号化：（1）墨西哥位于南美洲）墨西哥位于南美洲（2）是无理数是无理数仅仅当当 是有理数是有理数（3）如果）如果23，则则33，q：3y，G(x,y)：xy 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)（以后（以后讨论讨论）10.注意否定式的使用：注意否定式的使用：没有不呼吸的人没有不呼吸的人 不是所有的人都喜不是所有的人都喜欢欢吃糖吃糖 不是所有的火不是所有的火车车都比所有的汽都比所有的汽车车快快以上命以上命题应题应如何符号化？如何符号化？11.4.2 一一阶逻辑阶逻辑公式及解公式及解释释一一阶语阶语言言用于一用于一阶逻辑阶逻辑公式的形式公式的形式语语言言一、一一、一阶语阶语言言F与合式公式与合式公式1F的字母表，的字母表，定定义义4.1 一一阶语阶语言言F的字母表定的字母表定义义如下：如下：（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）括号与逗号：）括号与逗号：(,),，12.2F的的项项定定义义4.2 F的的项项的定的定义义如下：如下：（1）个体常）个体常项项和个体和个体变项变项是是项项.（2）若若(x1,x2,xn)是是任任意意的的n元元函函数数，t1,t2,tn是任意的是任意的n个个项项，则则(t1,t2,tn)是是项项.（3）所所有有的的项项都都是是有有限限次次使使用用（1），（2）得得到的到的.其其实实，个个体体常常项项、变变项项是是项项，由由它它们们构构成成的的n元元函数和复合函数函数和复合函数还还是是项项.13.3F的原子公式的原子公式定定义义4.3 设设R(x1,x2,xn)是是F的的任任意意n元元谓谓词词，t1,t2,tn是是F的的任任意意的的n个个项项，则则称称R(t1,t2,tn)是是F的原子公式的原子公式.其其实实，原子公式是由，原子公式是由项组项组成的成的n元元谓词谓词.例如，例如，F(x,y),F(f(x1,x2),g(x3,x4)等均等均为为原子公式原子公式14.4F的合式公式的合式公式定定义义44.F的合式公式定的合式公式定义义如下：如下：（1）原子公式是合式公式）原子公式是合式公式.（2）若）若A是合式公式，是合式公式，则则(A)也是合式公式也是合式公式（3）若若A,B是是合合式式公公式式，则则(A B),(A B),(AB),(AB)也是合式公式也是合式公式.（4）若）若A是合式公式，是合式公式，则则 xA,xA也是合式公式也是合式公式.（5）只只有有有有限限次次地地应应用用（1）（4）形形成成的的符符号号串串才是合式公式才是合式公式.15.二、封二、封闭闭的公式（的公式（简简称称闭闭式）式）1量量词词的的辖辖域、个体域、个体变项变项的的约约束与自由出束与自由出现现定定义义4.5 在在公公式式 xA和和 xA中中，称称x为为指指导导变变元元，A为为相相应应量量词词的的辖辖域域.在在 x和和 x的的辖辖域域中中，x的的所所有有出出现现都都称称为为约约束束出出现现，A中中不不是是约约束束出出现现的的其其他他变变项项均称均称为为是自由出是自由出现现的的.在公式在公式 x(F(x,y)G(x,z)中，中，设设 A=(F(x,y)G(x,z)（也可（也可记为记为A(x)）则则x为为指指导变导变元，元，A为为 x的的辖辖域，域，A中中x的两次出的两次出现现均均为约为约束出束出现现，y与与z均均为为自由出自由出现现.16.2闭闭式式定定义义4.6 若若公公式式A中中不不含含自自由由出出现现的的个个体体变变项项，则则称称A为闭为闭式式.例如例如:x y(F(x)G(y)H(x,y)x(F(x)G(x,y)闭闭式式不是不是闭闭式式17.三、解三、解释释与公式的分与公式的分类类1给给定公式定公式对对它它们进们进行解行解释释：（1）给给出出公公式式 x(F(x)G(x)一一个个成成真真解解释释，一一个成假解个成假解释释；（2）给给出出公公式式 x(F(x)G(x)一一个个成成真真解解释释，一一个成假解个成假解释释；（3）xF(x)x F(x)有成真解有成真解释吗释吗？（4）xF(x)x F(x)有成假解有成假解释吗释吗？18.2F中的解中的解释释定定义义4.7 F的解的解释释I由下面由下面4部分部分组组成：成：(a)非空个体域非空个体域DI (b)DI中一些特定元素的集合中一些特定元素的集合 (c)DI上特定函数集合上特定函数集合 (d)DI上特定上特定谓词谓词的集合的集合19.例：例：给给定解定解释释I如下：如下：(a)个体域个体域D=N（N为为自然数集合，即自然数集合，即N=0,1,2,）(b)(c)(d)为为 x=y.在在I下，下列哪些公式下，下列哪些公式为为真？哪些真？哪些为为假？哪些真知假？哪些真知还还不不能确定？能确定？20.3闭闭式的性式的性质质.定理定理4.1 闭闭式在任何解式在任何解释释下都是命下都是命题题.4公式的公式的类类型型定定义义4.8（1）永真式（）永真式（逻辑逻辑有效式）有效式）（2）矛盾式（永假式）（）矛盾式（永假式）（3）可）可满满足式足式注意：不是注意：不是闭闭式的公式在某些解式的公式在某些解释释下也可能是命下也可能是命题题.说说明：明：u永真式永真式为为可可满满足式，但反之不真足式，但反之不真;u判断公式是否判断公式是否为为永真式不是易事永真式不是易事;u通通过过某些代某些代换实换实例可判断公式例可判断公式类类型型.21.定定义义4.9 设设A0是是含含命命题题变变项项p1,p2,pn的的命命题题公公式式，A1,A2,An是是n个个谓谓词词公公式式，用用Ai(1 i n)处处处处代代替替A0中的中的pi，所得公式，所得公式A称称为为A0的代的代换实换实例例.例如例如定定理理4.2 重重言言式式的的代代换换实实例例都都是是永永真真式式，矛矛盾盾式式的代的代换实换实例都是矛盾式例都是矛盾式.pq的代的代换实换实例例非非pq的代的代换实换实例例 x(F(x)G(x)F(x)G(x),xF(x)yG(y)22.例例 判断下列公式中，哪些是永真式，哪些是矛盾式？判断下列公式中，哪些是永真式，哪些是矛盾式？（1）x(F(x)G(x)（2）x(F(x)G(x)（3）xF(x)(x yG(x,y)xF(x)（4）(xF(x)yG(y)yG(y)解解（1），（），（2）为为可可满满足式足式.（3）为为p(qp)（重言式）的代（重言式）的代换实换实例，例，为为永真式永真式.（4）为为(pq)q（矛盾式）的代（矛盾式）的代换实换实例，例，为为永假式永假式.23.第四章第四章 小小结结一、本章的主要内容与要求一、本章的主要内容与要求1主要内容主要内容n个体个体词词、谓词谓词、量、量词词；n一一阶逻辑阶逻辑命命题题符号化；符号化；nF的合式公式、的合式公式、闭闭式；式；nF的解的解释释；n公式的公式的类类型：永真式、矛盾式、可型：永真式、矛盾式、可满满足式足式24.2要求要求（1）准确地将）准确地将给给定命定命题题在在F中符号化：中符号化：u当指定个体域当指定个体域时时，就使用它；，就使用它；u当没指定个体域当没指定个体域时时，就使用全，就使用全总总个体域；个体域；u在在符符号号化化时时注注意意两两个个基基本本公公式式中中量量词词与与联联结结词词的的搭配。搭配。（2）深深刻刻理理解解永永真真式式、矛矛盾盾式式、可可满满足足式式的的概概念念及及相相互之互之间间的关系；的关系；（3）记记住住闭闭式的性式的性质质并能并能应应用它；用它；（4）对对于于给给定定的的解解释释会会判判断断公公式式的的真真值值，或或判判定定真真值值不确定（即仍不是命不确定（即仍不是命题题）。）。25.二、二、练习练习1在在一一阶阶逻逻辑辑中中将将下下面面命命题题符符号号化化，并并讨讨论论真真值值：（1）对对于于任任意意x，可可进进行行因因式式分分解解，即即 （2）存在）存在x，使得，使得 x+7=5 (a)D1为为全全总总个体域个体域 (b)D2=N (c)D3=R26.（1）(a)xG(x)，G(x)：,为为真真(b)x(F(x)G(x)，其其中中G(x)同同(a)中中，F(x)：x是是自自然然数，数，为为假（会出假（会出现现前件真，后件假）前件真，后件假）(c)x(F(x)G(x)，F(x)：x是是实实数数,G(x)同同(b)中中，为为真真（2）(a)xH(x)，H(x)：x+7=5，为为真真 (b)x(F(x)H(x)，H(x)同同(a)中中，F(x)：x为为自自然然数数，为为假假.(c)x(F(x)H(x)，H(x)同同(b)中中，F(x)：x为为实实数数，为为真真本本例例说说明明：不不同同个个体体域域内内，命命题题符符号号化化形形式式可可能能不不同同（也可能相同），真（也可能相同），真值值可能不同（也可能相同）可能不同（也可能相同）.27.2在一在一阶逻辑阶逻辑中将下列命中将下列命题题符号化符号化（1）大熊猫都可）大熊猫都可爱爱（2）有人）有人爱发爱发脾气脾气（3）说说所有人都所有人都爱爱吃面包是不吃面包是不对对的的（4）没有不）没有不爱爱吃糖的人吃糖的人（5）一切人都不一）一切人都不一样样高高（6）并不是所有的汽）并不是所有的汽车车都比火都比火车车快快 28.由于没指出个体域，故用全由于没指出个体域，故用全总总个体域个体域（1）x(F(x)G(x)其其中中，F(x):x为为大大熊熊猫猫，G(x):x可可爱爱（2）x(F(x)G(x)其其中中，F(x):x是是人人，G(x):x爱爱发发脾气脾气（3）x(F(x)G(x)或或 x(F(x)G(x)其中，其中，F(x):x是人，是人，G(x):x爱爱吃面包吃面包（4）x(F(x)G(x)或或 x(F(x)G(x)其中，其中，F(x):x是人，是人，G(x):x爱爱吃糖吃糖（5）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是人是人,H(x,y),x与与y相同相同,Lx,y):x与与y一一样样高高（6）x y(F(x)G(y)H(x,y)或或 x y(F(x)G(y)H(x,y)其中其中,F(x):x是汽是汽车车,G(y):y是火是火车车,H(x,y):x比比y快快29.说说明：明：使用的是全使用的是全总总个体域个体域(1)与与(2)是两个基本公式的使用是两个基本公式的使用(3)与与(4)是否定式是否定式(5)与与(6)使用了二元使用了二元谓词谓词(3)-(6)的不同符号化形式是等的不同符号化形式是等值值的的30.3.给给定解定解释释I如下如下:(a)个体域个体域D=N (b)=2(c)(x,y)=x+y,(x,y)=x y (d)谓词谓词 (x,y):x=y说说明下列公式在明下列公式在I下的涵下的涵义义,并并讨论讨论真真值值(1)xF(g(x,a),x)(2)x y(F(f(x,a),y)F(f(y,a),x)(3)x y zF(f(x,y),z)(4)xF(f(x,x),g(x,x)(5)x y zF(f(y,z),x)答案答案(3),(4)为为真真,其余的均其余的均为为假假说说明：明：5个小个小题题都是都是闭闭式式,在在I下全是命下全是命题题；(3)与与(5)说说明，量明，量词顺词顺序不能随意改序不能随意改变变。31.作作业业：习题习题四：四：1，2，4，5，6，8，9，11（1，2，3）32.