第四章-一阶逻辑基本概念

1、2021/3/261第四章第四章 一阶逻辑基本概念一阶逻辑基本概念 本章的主要内容本章的主要内容p 一阶逻辑基本概念、命题符号化一阶逻辑基本概念、命题符号化p 一阶逻辑公式、解释及分类一阶逻辑公式、解释及分类2021/3/2624.1 一阶逻辑命题符号化一阶逻辑命题符号化一、基本概念一、基本概念个体词、谓词、量词个体词、谓词、量词（1）个体常项）个体常项:具体的事务具体的事务,用用a, b, c表示表示（2）个体变项）个体变项:抽象的事物抽象的事物,用用x, y, z表示表示（3）个体域）个体域个体变项的取值范围个体变项的取值范围 有限个体域有限个体域,如如a, b, c, 1, 2 无限个体

2、域无限个体域,如如N, Z, R, 全总个体域全总个体域宇宙间一切事物组成宇宙间一切事物组成1个体（个体词）个体（个体词）所研究对象中可以独立存所研究对象中可以独立存在的具体或抽象的客体（名词或代词充当）在的具体或抽象的客体（名词或代词充当）2021/3/2632.谓词谓词表示个体词性质或相互之间关系的词表示个体词性质或相互之间关系的词（1）谓词常项）谓词常项:F: 是人是人,F(a):a是人是人（2）谓词变项）谓词变项:F: 具有性质具有性质F,F(x):x具有性质具有性质F（3）n（n 1）元谓词）元谓词 n=1,一元谓词一元谓词表示性质表示性质 n 2,多元谓词多元谓词表示事物之间的关系

3、表示事物之间的关系L(x,y):x与与y有关系有关系L,L(x,y):x y,(4) 0元谓词元谓词不含个体变项的谓词不含个体变项的谓词(命题常项命题常项或变项或变项)2021/3/2643量词量词表示数量的词表示数量的词（1）全称量词）全称量词:“ ”, x（2）存在量词）存在量词:“ ”, x 2021/3/265例例 用用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)

4、（以后讨论）（以后讨论）（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) （以后讨论）（以后讨论） 2021/3/2611注意否定式的使用注意否定式的使用: 没有不呼吸的人没有不呼吸的人 不是所有的人都喜欢吃糖不是所有的人都喜欢吃糖 不是所有的火车都比所有的汽车快不是所有的火车都比所有的汽车快以上命题应如何符号化以上命题应如何符号化?2021/3/26124.2 一阶逻辑公式及解释一阶逻辑公式及解释一阶语言一阶语言用于一阶逻辑公式的形式语言用于一阶逻辑公式的形式语言一、

5、一阶语言一、一阶语言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）括号与逗号）括号与逗号:(, ), ,2021/3/

6、26132F的项的项定义定义4.2 F的项的定义如下的项的定义如下:（1）个体常项和个体变项是项）个体常项和个体变项是项.（2）若）若 (x1, x2, , xn)是任意的是任意的n元函数元函数,t1, t2, , tn是任意的是任意的n个项个项,则则 (t1, t2, , tn) 是项是项.（3）所有的项都是有限次使用（）所有的项都是有限次使用（1）,（2）得）得到的到的.其实其实,个体常项、变项是项个体常项、变项是项,由它们构成的由它们构成的n元函元函数和复合函数还是项数和复合函数还是项.2021/3/26143F的原子公式的原子公式定义定义4.3 设设R(x1, x2, , xn)是是F

7、的任意的任意n元谓词元谓词,t1, t2, , tn是是F的任意的的任意的n个项个项,则称则称R(t1, t2, , tn)是是F的原子公式的原子公式. 其实其实,原子公式是由项组成的原子公式是由项组成的n元谓词元谓词. 例如例如,F(x,y), F(f(x1,x2),g(x3,x4)等均为原子公式等均为原子公式2021/3/26154F的合式公式的合式公式定义定义4.4 . F的合式公式定义如下的合式公式定义如下:（1）原子公式是合式公式）原子公式是合式公式. （2）若）若A是合式公式是合式公式,则则 ( A)也是合式公式也是合式公式（3）若）若A, B是合式公式是合式公式,则则(A B),

8、 (A B), (AB), (AB)也是合式公式也是合式公式.（4）若）若A是合式公式是合式公式,则则 xA, xA也是合式公式也是合式公式.（5）只有有限次地应用（）只有有限次地应用（1）（4）形成的符号串）形成的符号串才是合式公式才是合式公式.2021/3/2616二、封闭的公式（简称闭式）二、封闭的公式（简称闭式）1量词的辖域、个体变项的约束与自由出现量词的辖域、个体变项的约束与自由出现定义定义4.5 在公式在公式 xA和和 xA中中,称称x为指导变元为指导变元,A为为相应量词的辖域相应量词的辖域. 在在 x和和 x的辖域中的辖域中,x的所有出的所有出现都称为约束出现现都称为约束出现,A

9、中不是约束出现的其他变项中不是约束出现的其他变项均称为是自由出现的均称为是自由出现的. 在公式在公式 x (F(x,y)G(x,z) 中中,设设 A= (F(x,y)G(x,z) （也可记为（也可记为A(x)）则则x为指导变元为指导变元,A为为 x的辖域的辖域,A中中x的两次出现的两次出现均为约束出现均为约束出现,y与与z均为自由出现均为自由出现. 2021/3/26172闭式闭式定义定义4.6 若公式若公式A中不含自由出现的个体变项中不含自由出现的个体变项,则称则称A为闭式为闭式.例如例如: x y(F(x) G(y)H(x,y) x(F(x) G(x,y)闭式闭式不是闭式不是闭式2021/

10、3/2618三、解释与公式的分类三、解释与公式的分类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) 有成假解释吗有成假解释吗?2021/3/26192F中的解释中的解释定义定义4.7 F的解释的解释I由下面由下面4部分组成部分组成: (a) 非空个体域非空个体域DI (b) DI中一些特定元素的集合中一些特定元

11、素的集合 (c) DI上特定函数集合上特定函数集合 (d) DI上特定谓词的集合上特定谓词的集合,.,.,21iaaa1,|nifni1,|niFni2021/3/2620例例:给定解释给定解释I如下如下:(a)个体域个体域D=N（N为自然数集合为自然数集合,即即N=0,1,2,）(b) (c)(d) 为为 x=y.0ayxyxgyxyxf),(,),(),(yxF在在I下下,下列哪些公式为真下列哪些公式为真?哪些为假哪些为假?哪些真知还不能确哪些真知还不能确定定?),(),()9(),()8(),(),()7(),()6(),(),()5(),()4(),(),() 3(),(),()2()

12、,(),() 1 (xxgxxfxFzyxfzFyxxayfFyaxfFyxxaxgxFyxFxaxgxFzyxgxFzygyxgFzyxgFyaxfFyxgyxfF2021/3/26213闭式的性质闭式的性质.定理定理4.1 闭式在任何解释下都是命题闭式在任何解释下都是命题.4公式的类型公式的类型定义定义4.8 （1）永真式（逻辑有效式）永真式（逻辑有效式）（2）矛盾式（永假式）（）矛盾式（永假式）（3）可满足式）可满足式注意注意:不是闭式的公式在某些解释下也可能是命题不是闭式的公式在某些解释下也可能是命题. 说明说明:u永真式为可满足式永真式为可满足式,但反之不真但反之不真;u判断公式是否

13、为永真式不是易事判断公式是否为永真式不是易事;u通过某些代换实例可判断公式类型通过某些代换实例可判断公式类型.2021/3/2622定义定义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

14、)G(x), xF(x)yG(y)2021/3/2623例例 判断下列公式中判断下列公式中,哪些是永真式哪些是永真式,哪些是矛盾式哪些是矛盾式?（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（矛盾式）的代换实例（矛盾式）的代换实例,为永假式为永假式. 2021/3/2624第四章第四章 小结小结一、本章的主要内容与要求一、本章的主要内容与

15、要求1主要内容主要内容n个体词、谓词、量词个体词、谓词、量词;n一阶逻辑命题符号化一阶逻辑命题符号化;nF的合式公式、闭式的合式公式、闭式;nF的解释的解释;n公式的类型公式的类型:永真式、矛盾式、可满足式永真式、矛盾式、可满足式2021/3/26252要求要求（1）准确地将给定命题在）准确地将给定命题在F中符号化中符号化:u当指定个体域时当指定个体域时,就使用它就使用它;u当没指定个体域时当没指定个体域时,就使用全总个体域就使用全总个体域;u在符号化时注意两个基本公式中量词与联结词的在符号化时注意两个基本公式中量词与联结词的搭配。搭配。（2）深刻理解永真式、矛盾式、可满足式的概念及相）深刻理

16、解永真式、矛盾式、可满足式的概念及相互之间的关系互之间的关系;（3）记住闭式的性质并能应用它）记住闭式的性质并能应用它;（4）对于给定的解释会判断公式的真值）对于给定的解释会判断公式的真值,或判定真值或判定真值不确定（即仍不是命题）。不确定（即仍不是命题）。2021/3/2626二、练习二、练习1在一阶逻辑中将下面命题符号化在一阶逻辑中将下面命题符号化,并讨论真并讨论真值值:（1）对于任意）对于任意x, 可进行因式分解可进行因式分解,即即 （2）存在）存在x,使得使得 x+7=5 (a) D1为全总个体域为全总个体域 (b) D2=N (c) D3=R)2)(2(22xxx22x2021/3/

17、2627（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为实数为实数,为真为真本例说明本例说明:不同个体域内不同个体域内,命题符

18、号化形式可能不同（也命题符号化形式可能不同（也可能相同）可能相同）,真值可能不同（也可能相同）真值可能不同（也可能相同）.)2)(2(22xxx可分解为2021/3/26282在一阶逻辑中将下列命题符号化在一阶逻辑中将下列命题符号化（1）大熊猫都可爱）大熊猫都可爱（2）有人爱发脾气）有人爱发脾气（3）说所有人都爱吃面包是不对的）说所有人都爱吃面包是不对的（4）没有不爱吃糖的人）没有不爱吃糖的人（5）一切人都不一样高）一切人都不一样高（6）并不是所有的汽车都比火车快）并不是所有的汽车都比火车快 2021/3/2629由于没指出个体域由于没指出个体域,故用全总个体域故用全总个体域（1） x(F(x

19、)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相同相同, L(x,y): x与与y一样高一样高（ 6 ）