一阶逻辑基本概念 谓词逻辑课件(离散数学)

1、 第四章第四章 一阶逻辑基本概念 （谓词逻辑）（谓词逻辑） 1 本章主要内容本章主要内容 4.1 一阶逻辑命题符号化一阶逻辑命题符号化 4.2 一阶逻辑公式及解释一阶逻辑公式及解释 2 4.1 一阶逻辑命题符号化一阶逻辑命题符号化 n个体词、谓词、量词的概念个体词、谓词、量词的概念 n一阶逻辑命题的符号化一阶逻辑命题的符号化 3 一、个体词、谓词、量词的概念一、个体词、谓词、量词的概念 定义：定义：个体词（个体）个体词（个体）: 可以独立存在的具可以独立存在的具 体或抽象的客体。体或抽象的客体。 个体词的基本概念个体词的基本概念 例：我是老师。其中例：我是老师。其中“我我”就是个体词。就是个体

2、词。 张三比李四高。其中张三比李四高。其中“张三张三”、 “李四李四”都是个体词。都是个体词。 4 一、个体词、谓词、量词的概念一、个体词、谓词、量词的概念 n个体常项个体常项：具体的客体，用：具体的客体，用a, b, c表示。表示。 n个体变项个体变项：抽象或泛指的事物，用：抽象或泛指的事物，用x, y, z表示。表示。 n 个体域（论域）个体域（论域）: 个体变项的取值范围。个体变项的取值范围。 例：例：x高于高于y。x，y都是个体变项。都是个体变项。 有限个体域有限个体域 即个体域是即个体域是 有限集合有限集合 无限个体域无限个体域 即个体域是即个体域是 无穷集合无穷集合 全总个体域全总

3、个体域 宇宙间一切宇宙间一切 事物组成。事物组成。 5 一、个体词、谓词、量词的概念一、个体词、谓词、量词的概念 n谓词的基本概念谓词的基本概念 定义定义: 表示个体词表示个体词性质性质或相互之间或相互之间关系关系的词。的词。 例：张华是大学生。例：张华是大学生。 李凯是大学生。李凯是大学生。 是大学生是大学生 例：张三比李四高。例：张三比李四高。比比高高 6 一、个体词、谓词、量词的概念一、个体词、谓词、量词的概念 n谓词常项：表示具体性质或关系谓词常项：表示具体性质或关系 例：例：是大学生，记为是大学生，记为F，F(张华张华)表示表示“张华是张华是 大学生大学生”。 n谓词变项：表示抽象及

4、泛指的性质或关系谓词变项：表示抽象及泛指的性质或关系 例：例：具有性质具有性质F，记为，记为F， F(张华张华)：张华具有：张华具有 性质性质F 谓词常项和变项都用大写字母表示。谓词常项和变项都用大写字母表示。 7 一、个体词、谓词、量词的概念一、个体词、谓词、量词的概念 nn元谓词元谓词(n 2): 含有含有n个个个体变项个体变项的谓词。的谓词。 如：如：L(x,y)：x y，L是一个二元谓词。是一个二元谓词。 n一元谓词一元谓词: 只含有一个只含有一个个体变项个体变项的谓词。的谓词。 如：如：F(x)：x是女孩。是女孩。 n0元谓词元谓词: 不含不含个体变项个体变项的谓词。的谓词。 8 一

5、、个体词、谓词、量词的概念一、个体词、谓词、量词的概念 如：上例二元谓词如：上例二元谓词L中的中的x,y代以个体代以个体“2”和和 “1”,则则L(2,1)就是命题就是命题“2 1”。此时二元谓。此时二元谓 词变成词变成0元谓词。元谓词。 同理：一元谓词同理：一元谓词F(x)中的中的x代以个体代以个体“小小 王王”，则，则F(小王小王)就是命题就是命题“小王是女孩小王是女孩”。 也是也是0元谓词。元谓词。 谓词逻辑包括命题逻辑。谓词逻辑包括命题逻辑。 9 一、个体词、谓词、量词的概念一、个体词、谓词、量词的概念 例例1：用：用0元谓词将下述命题符号化。元谓词将下述命题符号化。 (1) 墨西哥位

6、于南美洲墨西哥位于南美洲 在在命题逻辑命题逻辑中中, 设设 p: 墨西哥位于南美洲墨西哥位于南美洲 符号化为符号化为 p, 该命题为真命题。该命题为真命题。 在在一阶逻辑一阶逻辑中中, 设设 a：墨西哥；：墨西哥； F(x)：x位于南美洲；位于南美洲； 符号化为符号化为F(a) 10 一、个体词、谓词、量词的概念一、个体词、谓词、量词的概念 (2) 是无理数仅当是无理数仅当 是有理数是有理数23 在在一阶逻辑一阶逻辑中，中， 设设F(x): x是无理数；是无理数；G(x): x是有理数是有理数 符号化为符号化为)3()2(GF 在在命题逻辑命题逻辑中中,设设 p: 是无理数是无理数;q: 是有

7、理数是有理数. 符号化为符号化为 p q, 这是假命题。这是假命题。 2 3 11 一、个体词、谓词、量词的概念一、个体词、谓词、量词的概念 （3） 如果如果23，则，则33，q：3y，G(x,y)：x10 。 )()(x xQ Qx xP Px x 19 二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化 令令 F(x): x是无理数是无理数, G(y): y是有理数是有理数, L(x,y)：xy x (F(x) y(G(y) L(x,y) （2）有的无理数大于有的有理数）有的无理数大于有的有理数 20 二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化 （3）没有不犯错的人。）没有不犯错的人。

8、 设：设：P(x)：x是人；是人； Q(x)：x犯错误。犯错误。 )()(x xQ Qx xP Px x )()(x xQ Qx xP Px x 或或 21 二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化 令令 F(x): x是金属，是金属，G(x): x是液体，是液体， L(x,y): x溶解在溶解在y中中 （4）任何金属都可以溶解在某种溶液中。）任何金属都可以溶解在某种溶液中。 ),()()(y yx xL Ly yG Gy yx xF Fx x 22 二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化 （5）某些人对所有的花粉都过敏。）某些人对所有的花粉都过敏。 令令 F(x): x是人

9、是人, G(y): y是花粉是花粉, L(x,y)：x对对y过敏。过敏。 ),()()(y yx xL Ly yG Gy yx xF Fx x 23 二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化 （6）所有的学生都上课了，这是错的。）所有的学生都上课了，这是错的。 令令 F(x): x是学生是学生, G(x): x上课了。上课了。 )()(x xG Gx xF Fx x 这句话相当于这句话相当于“有些学生没有上课有些学生没有上课”。 )()(x xG Gx xF Fx x 24 二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化 （7）不存在最大的整数。）不存在最大的整数。 令令 F(x):

10、 x是整数是整数, L(x,y)：x比比y大大。 ),()()(yxLyFyxFx 这句话相当于：这句话相当于：“任意一个整数，都存在比任意一个整数，都存在比 它大的整数它大的整数”。 ),()()(x xy yL Ly yF Fy yx xF Fx x 25 二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化 例例4：（教材例：（教材例4.5）将下列命题符号化）将下列命题符号化 （1）兔子比乌龟跑得快。）兔子比乌龟跑得快。 （2）有的兔子比所有的乌龟跑得快。）有的兔子比所有的乌龟跑得快。 （3）并不是所有的兔子都比乌龟跑得快。）并不是所有的兔子都比乌龟跑得快。 （4）不存在跑得同样快的两只兔子

11、。）不存在跑得同样快的两只兔子。 26 二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化 例例5:设设A(x):x能被能被3整除；整除； B(x):x能被能被6整除整除. 个体域为：个体域为：1,2,6,7,12 分析如下情况的真值。分析如下情况的真值。 )()1(x xx xA A )()2(x xxAxA )()()3(x xB Bx xA Ax x )()()4(x xB Bx xA Ax x 真真 假假真真 真真 27 二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化 例例6：考虑个体域为实数域，则命题：考虑个体域为实数域，则命题“对于对于 任意的任意的x，都存在，都存在y，使得，使得

12、xy”应该符号化应该符号化 为下面的哪一种形式？为下面的哪一种形式？ 令：令：L(x,y): x2, G(x): x1 个体域个体域N, F(x): x1, G(x): x2 成真解释成真解释 代入得代入得A = x(x2x1) 真命题真命题 成假解释成假解释 代入得代入得A= x(x1 x2)假命题假命题 40 三、公式的解释三、公式的解释 对公式中的各个抽象符号给出如下解释：对公式中的各个抽象符号给出如下解释： （1）个体域）个体域D=N；（；（2）a=0 （3）f(x,y)=x+y，g(x,y)=xy （4）F(x,y)：x=y ),(),(z zy yx xg gF Fy ya ax

13、xf fF F例：例： 由于公式是抽象的符号串，若不对它们给以由于公式是抽象的符号串，若不对它们给以 具体解释，则公式是没有实在意义的。具体解释，则公式是没有实在意义的。 41 三、公式的解释三、公式的解释 定义定义：解释：解释I由下面由下面4部分组成：部分组成： (a) 非空个体域非空个体域DI (b) DI中一些特定元素的集合中一些特定元素的集合 (c) DI上特定函数集合上特定函数集合 (d) DI上特定谓词的集合上特定谓词的集合 , 1 i aa 1,| nif n i 1,| niF n i 42 三、公式的解释三、公式的解释 例例3 3 给定解释给定解释I I 如下如下: : (a

14、) 个体域个体域 D=N（包括（包括0） (b) (c) (d) 谓词谓词 说明下列公式在说明下列公式在 I 下的涵义下的涵义,并讨论真值。并讨论真值。 2 a xyyxgyxyxf ),(,),( yxyxF :),( 43 三、公式的解释三、公式的解释 (1) xF( g(x,a), x) x(2x=x) (2) x y(F(f (x,a), y)F(f(y,a), x) x y(x+2=yy+2=x) (3) xF(f(x,x),g(x,x) x(2x=x2) 假命题假命题 假命题假命题 真命题真命题 44 三、公式的解释三、公式的解释 (5) x y zF(f(y,z),x) x y

15、z (y+z=x) (4) x y zF(f(x,y),z) x y z (x+y=z)真命题真命题 假命题假命题 (6) x F(g(x,y),z) xy=z不是命题不是命题 45 三、公式的解释三、公式的解释 小结小结： (1)(5)中的公式中的公式都是都是闭式闭式,在在I下全是命题。下全是命题。 (6)与与(7)中的公式中的公式都不是闭式都不是闭式,但但(6)在该解释在该解释 下没有确定的真值，而下没有确定的真值，而(7)的真值为真的真值为真 。 (7) xF(g (x,a), x)F(x,y) x(2x= x)(x=y)真命题真命题 闭式闭式: 不含自由出现的个体变项的公式。不含自由出

16、现的个体变项的公式。 例：例： ),(),(z zx xG Gy yx xF Fx xy yz z 定理：定理：闭式在任何解释下都是命题。闭式在任何解释下都是命题。 46 四、公式的类型四、公式的类型 n永真式（逻辑有效式）永真式（逻辑有效式）：无成假解释：无成假解释 n矛盾式（永假式）矛盾式（永假式）：无成真解释：无成真解释 n可满足式可满足式：至少有一个成真解释：至少有一个成真解释 47 例例5：证明下面公式不是永真式。：证明下面公式不是永真式。 ),(),(y yx xy yF Fx xy yx xy yF Fx x 只要找到一个使公式成假的解释就可以证明该公只要找到一个使公式成假的解释就可以证明该公 式不是永真式。式不是永真式。 设论域为整数集合，设论域为整数集合，F(x,y):xy n前件为：对任意整数前件为：对任意整数x，存在整数，存在整数y，使得，使得xy。其。其 真值为真值为真真。 n后件为：存在整数后件为：存在整数x，对任意的整数，对任意的整数y都有都有xy。其。其 真值为真值为假假。 所以在这样的解释下，公式为假，即不是永真式。所以在这样的解释下，公式为假，即不是永真式。 48 四、公式的类型四、公式的类型 例：判断公式例：判断公式 的类型的类型),(),(),(y yx xF Fy yx xG Gy yx xF F 真真式式。的的代代换换实实例例，所所以