一阶逻辑基本概念

《一阶逻辑基本概念》由会员分享，可在线阅读，更多相关《一阶逻辑基本概念（34页珍藏版）》请在金锄头文库上搜索。

1、 一阶谓词逻辑一阶谓词逻辑CH4一阶逻辑基本概念一阶逻辑基本概念CH5一阶逻辑等值演算与推理一阶逻辑等值演算与推理一一阶逻辑阶逻辑基本基本概概念念*2内容要点：内容要点：谓词和个体谓词和个体量词量词一阶逻辑公式一阶逻辑公式置换规则置换规则一阶逻辑等值式一阶逻辑等值式一阶逻辑前束范式一阶逻辑前束范式推理理论推理理论CH4CH4CH4CH4CH4CH4CH5CH5CH5CH5CH5CH5CH5CH5一一阶逻辑阶逻辑基本基本概概念念*31.命题的表达命题的表达例例1.1：凡偶数都能被：凡偶数都能被2整除，整除，6是偶数。是偶数。所以，所以，6能被能被2整除整除将它们命题符号化：将它们命题符号化： p

2、：凡偶数都能被：凡偶数都能被2整除整除q：6是偶数是偶数r：6能被能被2整除整除则推理的形式结构符号化为：则推理的形式结构符号化为：(p q)r由于上式不是重言式，由于上式不是重言式，所以不能由它判断推理所以不能由它判断推理的正确性。为了克服命的正确性。为了克服命题逻辑的局限性，就应题逻辑的局限性，就应该将简单命题再细分，该将简单命题再细分，分析出个体词、谓词和分析出个体词、谓词和量词，以期达到表达出量词，以期达到表达出个体与总体的内在联系个体与总体的内在联系和数量关系，这就是谓和数量关系，这就是谓词逻辑。词逻辑。 一一阶逻辑阶逻辑基本基本概概念念*4(1)(1)是自然数。是自然数。(2) (

3、2) 21世纪末，人类将住在月球。世纪末，人类将住在月球。 (3) x+y=y+x (4) 只有只有x能被能被2整除，整除， x才能被才能被4整除。整除。A.个体词个体词x,y的取值范围：复数域的取值范围：复数域a的取值范围：整数域的取值范围：整数域是指所研究对象中可以是指所研究对象中可以独立存在的具体的或抽独立存在的具体的或抽象的客体。象的客体。表示具体或特定的客体表示具体或特定的客体的个体词称作个体常项；的个体词称作个体常项；常用常用a,b,c,表示。表示。表示抽象或泛指的客体表示抽象或泛指的客体的个体词称作个体变项；的个体词称作个体变项；常用常用x,y,z,表示。表示。个体变项的取值范围

4、为个个体变项的取值范围为个体域，个体域可以是有穷体域，个体域可以是有穷集合，也可以是无穷集合。集合，也可以是无穷集合。全总个体域：由宇宙间一切事物组成的域为全总个体域。全总个体域：由宇宙间一切事物组成的域为全总个体域。 一一阶逻辑阶逻辑基本基本概概念念*5a.a.小陈是大学生小陈是大学生 b.b.小张生于苏州小张生于苏州 c. 8=3*2 c. 8=3*2 x x是大学生是大学生 小陈小陈-个体；是大学生个体；是大学生-谓词：谓词： 是大学生刻划了是大学生刻划了x x 的性质的性质x x生于生于y y 生于生于-谓词：刻划了谓词：刻划了x x和和y y的关系的关系x=y*z x=y*z .=.

5、=.-.-谓词：刻划了谓词：刻划了x x，y y，z z三三 元的关系元的关系 一、谓词和个体一、谓词和个体B.谓词谓词一一阶逻辑阶逻辑基本基本概概念念*6B. 谓词谓词(1)(1)是自然数。是自然数。(2) (2) 21世纪末，人类将住在月球。世纪末，人类将住在月球。 (3) x 与与y 具有关系具有关系L (4) 只有只有x能被能被2整除，整除， x才能被才能被4整除。整除。谓词：谓词：用来刻划个体用来刻划个体词性质及个体词之间词性质及个体词之间相互关系的词相互关系的词 表示具体性质表示具体性质或关系的谓词或关系的谓词称为谓词常项称为谓词常项谓词变项：表示谓词变项：表示抽抽象的或泛指的象的

6、或泛指的性质性质或关系的谓词或关系的谓词两者都用大写两者都用大写英文字母表示英文字母表示一一阶逻辑阶逻辑基本基本概概念念*7一般的一般的用用F(a)表示个体常项表示个体常项a具有性质具有性质F（F是谓词常项或谓词变项），是谓词常项或谓词变项），用用F(x)表示个体变项表示个体变项x具有性质具有性质F。而用而用F(a,b)表示个体常项表示个体常项a,b具有关系具有关系F，用用F(x,y)表示个体变项表示个体变项x,y具有关系具有关系F。定义定义：一个大写英文字母后边有括号，括号内是若干个客体变元，用以表示客体的属性或者客体之间的关系，称之为谓词。如果括号内有n个客体变元客体变元，称该谓词为n元谓

7、词。一一阶逻辑阶逻辑基本基本概概念念*8例如 S(x):表示x是大学生。 一元谓词 G(x,y)：表示 xy。 二元谓词 B(x,y,z)：表示x在y与z之间。三元谓词一般地 P(x1,x2,xn) 是n元谓词。0元谓词：有时将不带个体变项的谓词称为元谓词：有时将不带个体变项的谓词称为0元谓词，例如上面元谓词，例如上面提到的提到的F(a)，H(a,b)，P(a1,a2,an )等都是等都是0元谓词，当元谓词，当F,H,P为谓词常项时，为谓词常项时，0元谓词为命题。这样，命题逻辑中的命题均元谓词为命题。这样，命题逻辑中的命题均可表示成可表示成0元谓词，因而可以将命题看成是特殊的谓词。元谓词，因而

8、可以将命题看成是特殊的谓词。一一阶逻辑阶逻辑基本基本概概念念*9(1)2是素数且是偶数是素数且是偶数(2)如果如果2大于大于3，则，则2大于大于4解：解：(1)设一元谓词设一元谓词F(x)：x是素数；一元谓词是素数；一元谓词G(x)：x是偶数；是偶数；a：2。则则(1)中命题符号化为中命题符号化为0元谓词的合取式：元谓词的合取式：F(a) G(a)。(2)设二元谓词设二元谓词L(x,y)：x大于大于y；a：2；b：3；c：4.L(a,b),L(a,c)是两个是两个0元谓词，把元谓词，把(2)中命题符号化为中命题符号化为L(a,b)L(a,c)例题：将下列命题用例题：将下列命题用0元谓词符号化，

9、并讨论它们的真值。元谓词符号化，并讨论它们的真值。一一阶逻辑阶逻辑基本基本概概念念*10 x x读作读作对任意对任意x x xP(x)xP(x)表示表示对一切对一切x,P(x)x,P(x)为真为真 xP(x)xP(x)表示表示 并非对任意并非对任意x, P(x)x, P(x)是真是真(1)(1)全称量词全称量词 x xC.量词量词一一阶逻辑阶逻辑基本基本概概念念*11 x x读作读作至少有一至少有一x x，存在一存在一x x x P(x)x P(x)表示表示 存在一存在一x x，使，使P(x) P(x) 为真为真 x P(x)x P(x)表示表示 并非存在一个并非存在一个x x，使，使P(x)

10、P(x)为真为真(2)(2)存在量词存在量词 x xC.量词量词一一阶逻辑阶逻辑基本基本概概念念*12 在P(x)，P(x,y)前加上x或x，称变元x被存在量化或全称量化。 将谓词F(x)变成命题有两种方法。a.将x取定值 例：F(x)表示x是质数，那么F(4)是命题（假）b.将谓词量化 例：1). xF(x) F(x)：任意的x是质数 2). y(yy+1) 3). y(y0 ，存，存在在dd 0,使得当使得当|x-x0|d d 时，均有时，均有|f(x)-f(x0)|0dd0(|x-x0|d d |f(x)-f(x0)|ZZ)一一阶逻辑阶逻辑基本基本概概念念*29谓词公式的解释：谓词公式的

11、解释：定义定义 一个解释一个解释I I由下面由下面4 4部分组成：部分组成：（1 1）非空个体域）非空个体域D D；（2 2）D D中一些特定元素的集合中一些特定元素的集合（3 3）D D上特定函数集合上特定函数集合（4 4）D D上特定谓词的集合上特定谓词的集合一一阶逻辑阶逻辑基本基本概概念念在I 下，下列哪些公式为真？哪些为假？哪些的真值还不能确定？(1)F(f(x,y),g(x,y)在在I下，被解释成下，被解释成“x+y=xy”,这不是命题这不是命题(2)F(f(x,a),y)F(g(x,y),z)在在I下，被解释成下，被解释成“(x+0=y)(xy=z)”,这不是命题这不是命题(3)F

12、(g(x,y),g(y,z)在在I下，被解释成下，被解释成“xyyz”,这不是命题这不是命题(4)xF(g(x,y),z)在在I下，被解释成下，被解释成“x(xyz)”,这不是命题这不是命题(5)xF(g(x,a),x)F(x,y)在在I下，被解释成下，被解释成“x(x0=x)(x=y)”,由于蕴含式前件为假，由于蕴含式前件为假，所以被解释的公式为真。所以被解释的公式为真。(6)xF(g(x,a),x)在在I下，被解释成下，被解释成“x(x0=x)”,这不是命题这不是命题(7)xyF(f(x,a),y)F(f(y,a),x)在在I下，被解释成下，被解释成“xy(x+0=y)(y+0=x)”,这

13、是真命题这是真命题(8)xyzF(f(x,y),z)在在I下，被解释成下，被解释成“xyz(x+y=z)”,这是真命题这是真命题(9)xF(f(x,x),g(x,x)在在I下，被解释成下，被解释成“x(x+x=xx)”,这是真命题这是真命题一一阶逻辑阶逻辑基本基本概概念念解解 为方便起见，用为方便起见，用A，B，C分别记分别记(1)，(2)，(3)中的公式。中的公式。 (1)取解释取解释I1:个体域为实数集合个体域为实数集合R，F(x):x是整数，是整数，G(x):x是有是有理数。在理数。在I1下下A为真，因而为真，因而A不是矛盾式。取解释不是矛盾式。取解释I2:个体域仍然个体域仍然为为R，F

14、(x):x是无理数，是无理数，G(x):x能表示成分数。在能表示成分数。在I2下下A为假，为假，所以所以A不是永真式。故不是永真式。故A是非永真式的可满足式。是非永真式的可满足式。 (2)易知易知B是命题公式是命题公式p(qp)的代换实例，而该命题公式是的代换实例，而该命题公式是重言式，所以重言式，所以B是永真式。是永真式。 (3)C是命题公式是命题公式(pq)q的代换实例，而该命题公式是矛的代换实例，而该命题公式是矛盾式，所以盾式，所以C是矛盾式。是矛盾式。一一阶逻辑阶逻辑基本基本概概念念*32注：注：在证明一个谓词公式既不是永真式也不是矛盾式时，可以为在证明一个谓词公式既不是永真式也不是矛

15、盾式时，可以为公式分别找一个成真的解释和一个成假的解释。公式分别找一个成真的解释和一个成假的解释。当证明一个谓词公式是永真式或矛盾式时，可以使用相应的当证明一个谓词公式是永真式或矛盾式时，可以使用相应的命题公式进行代换。若命题公式为永真式，则原谓词公式也命题公式进行代换。若命题公式为永真式，则原谓词公式也是永真式；若命题公式为矛盾式，则原谓词公式也是矛盾式。是永真式；若命题公式为矛盾式，则原谓词公式也是矛盾式。一一阶逻辑阶逻辑基本基本概概念念*33内容小结：内容小结：谓词和个体谓词和个体量词量词一阶逻辑公式一阶逻辑公式置换规则置换规则一阶逻辑等值式一阶逻辑等值式一阶逻辑前束范式一阶逻辑前束范式推理理论推理理论CH4CH4CH4CH4CH4CH4CH5CH5CH5CH5CH5CH5CH5CH5一一阶逻辑阶逻辑基本基本概概念念*34CH4基本要求基本要求准确的将给定命题符号化准确的将给定命题符号化掌握永真式、矛盾式和可满足式的概念及判断方法掌握永真式、矛盾式和可满足式的概念及判断方法深刻理解闭式的概念及闭式的性质（闭式在任何解释深刻理解闭式的概念及闭式的性质（闭式在任何解释下都是命题）下都是命题）对于给定的解释会判断给定公式是否成为命题，对是对于给定的解释会判断给定公式是否成为命题，对是命题的能够判断出真假命题的能够判断出真假一一阶逻辑阶逻辑基本基本概概念念