一阶逻辑基本概念

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

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

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

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

5、 生于生于-谓词：刻划了谓词：刻划了x x和和y y的关系的关系 x=yx=y* *z z .=.=.-.-谓词：刻划了谓词：刻划了x x，y y，z z三三 元的关系元的关系 一、谓词和个体一、谓词和个体 B. 谓词谓词 一阶逻辑阶逻辑基本概概念*6 B. 谓词谓词 (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。 定义定义：一个大写英文

7、字母后边有括号，括号内是若 干个客体变元，用以表示客体的属性或者客体之间 的关系，称之为谓词。如果括号内有n个客体变元客体变元， 称该谓词为n元谓词。 一阶逻辑阶逻辑基本概概念*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为谓词常项时，

8、为谓词常项时，0元谓词为命题。这样，命题逻辑中的命题均元谓词为命题。这样，命题逻辑中的命题均 可表示成可表示成0元谓词，因而可以将命题看成是特殊的谓词。元谓词，因而可以将命题看成是特殊的谓词。 一阶逻辑阶逻辑基本概概念*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；

9、c：4. L(a,b), L(a,c)是两个是两个0元谓词，把元谓词，把(2)中命题符号化为中命题符号化为L(a,b) L(a,c) 例题：将下列命题用例题：将下列命题用0元谓词符号化，并讨论它们的真值。元谓词符号化，并讨论它们的真值。 一阶逻辑阶逻辑基本概概念*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 x C.量词量词 一阶逻辑阶逻辑基本概概念*11 x x读作读作至少有一至少有一x x，存在一存在一

10、x x x P(x)x P(x)表示表示 存在一存在一x x，使，使P(x) P(x) 为真为真 x P(x)x P(x)表示表示 并非存在一个并非存在一个x x，使，使 P(x)P(x)为真为真 (2)(2)存在量词存在量词 x x C.量词量词 一阶逻辑阶逻辑基本概概念*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 ，存在，存在d d 0,使得当使得

11、当|x-x0| d d 时，均有时，均有|f(x)-f(x0)|0d d0(|x-x0| d d |f(x)-f(x0)|Z) 一阶逻辑阶逻辑基本概概念*29 谓词公式的解释：谓词公式的解释： 定义定义 一个解释一个解释I I由下面由下面4 4部分组成：部分组成： （1 1）非空个体域）非空个体域D D； （2 2）D D中一些特定元素的集合中一些特定元素的集合 （3 3）D D上特定函数集合上特定函数集合 （4 4）D D上特定谓词的集合上特定谓词的集合 12 ,.,. i a aa | ,1 n i fi n | ,1 n i Fi n NNN 0 ( , ),( , ) , I D a

12、f x yxy g x yx y F x yxy 给定解释 如下： (a) 个体域 （ 为自然数集合，即 0,1,2,.）. (b) (c) (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(g(x,y), g(y,z) 在在I下，被解释成下，被解释成 “xyyz”, 这不是命题这不是命题 (

13、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) xy F(f(x,a),y) F(f(y,a),x) 在在I下，被解释成下，被解释成 “xy( x+0=y) (y+0=x)”, 这是真命这是真命 题题 (8) xyzF

14、(f(x,y),z) 在在I下，被解释成下，被解释成 “xyz(x+y=z)”, 这是真命题这是真命题 (9) xF(f(x,x),g(x,x) 在在I下，被解释成下，被解释成 “x(x+x=xx)”, 这是真命题这是真命题 (1)( ( )( ) ( )( , )( ) ( )( )( ) x F xG x xF xx yG x yxF x xF xyG yyG y 例例题题： 判断下列公式中，哪些是永真式，哪些是矛盾式？ (2) (3) 解解 为方便起见，用为方便起见，用A，B，C分别记分别记(1)，(2)，(3)中的公式。中的公式。 (1)取解释取解释I1:个体域为实数集合个体域为实数集

15、合R，F(x):x是整数，是整数，G(x):x是有是有 理数。在理数。在I1下下A为真，因而为真，因而A不是矛盾式。取解释不是矛盾式。取解释I2:个体域仍然个体域仍然 为为R，F(x):x是无理数，是无理数，G(x):x能表示成分数。在能表示成分数。在I2下下A为假，为假， 所以所以A不是永真式。故不是永真式。故A是非永真式的可满足式。是非永真式的可满足式。 (2)易知易知B是命题公式是命题公式p(qp)的代换实例，而该命题公式是的代换实例，而该命题公式是 重言式，所以重言式，所以B是永真式。是永真式。 (3)C是命题公式是命题公式(pq)q的代换实例，而该命题公式是矛的代换实例，而该命题公式

16、是矛 盾式，所以盾式，所以C是矛盾式。是矛盾式。 一阶逻辑阶逻辑基本概概念*32 注：注： 在证明一个谓词公式既不是永真式也不是矛盾式时，可以为在证明一个谓词公式既不是永真式也不是矛盾式时，可以为 公式分别找一个成真的解释和一个成假的解释。公式分别找一个成真的解释和一个成假的解释。 当证明一个谓词公式是永真式或矛盾式时，可以使用相应的当证明一个谓词公式是永真式或矛盾式时，可以使用相应的 命题公式进行代换。若命题公式为永真式，则原谓词公式也命题公式进行代换。若命题公式为永真式，则原谓词公式也 是永真式；若命题公式为矛盾式，则原谓词公式也是矛盾式。是永真式；若命题公式为矛盾式，则原谓词公式也是矛盾式。 一阶逻辑阶逻辑基本概概念*33 内容小结：内容小结： 谓词和个体谓词和个体量词量词 一阶逻辑公式一阶逻辑公式 置换规则置换规则 一阶逻辑等值式一阶逻辑等值式 一阶逻辑前束范式一阶逻辑前束范式 推理理论推理理论 CH4CH4 CH4CH4