《一阶逻辑基本概念谓词逻辑(离散数学)课件》由会员分享，可在线阅读，更多相关《一阶逻辑基本概念谓词逻辑(离散数学)课件（49页珍藏版）》请在金锄头文库上搜索。
1、 第四章第四章一阶逻辑基本概念（谓词逻辑）（谓词逻辑）1本章主要内容本章主要内容4.1一阶逻辑命题符号化一阶逻辑命题符号化4.2一阶逻辑公式及解释一阶逻辑公式及解释24.1 一阶逻辑命题符号化一阶逻辑命题符号化n个体词、谓词、量词的概念个体词、谓词、量词的概念n一阶逻辑命题的符号化一阶逻辑命题的符号化3一、个体词、谓词、量词的概念一、个体词、谓词、量词的概念定义：定义：个体词（个体）个体词（个体）:可以独立存在的具可以独立存在的具体或抽象的客体。体或抽象的客体。1.个体词的基本概念个体词的基本概念例：我是老师。其中例：我是老师。其中“我我”就是个体词。就是个体词。张三比李四高。其中张三比李四高
2、。其中“张三张三”、“李四李四”都是个体词。都是个体词。4一、个体词、谓词、量词的概念一、个体词、谓词、量词的概念n个体常项个体常项：具体的客体，用：具体的客体，用a,b,c表示。表示。n个体变项个体变项：抽象或泛指的事物，用：抽象或泛指的事物，用x,y,z表示。表示。n个体域（论域）个体域（论域）:个体变项的取值范围。个体变项的取值范围。例：例：x高于高于y。x，y都是个体变项。都是个体变项。有限个体域有限个体域即个体域是即个体域是有限集合有限集合无限个体域无限个体域即个体域是无即个体域是无穷集合穷集合全总个体域全总个体域宇宙间一切事宇宙间一切事物组成。物组成。5一、个体词、谓词、量词的概念
3、一、个体词、谓词、量词的概念2.谓词的基本概念谓词的基本概念定义定义:表示个体词表示个体词性质性质或相互之间或相互之间关系关系的词。的词。例：张华是大学生。例：张华是大学生。李凯是大学生。李凯是大学生。是大学生是大学生例：张三比李四高。例：张三比李四高。比比高高6一、个体词、谓词、量词的概念一、个体词、谓词、量词的概念n谓词常项：表示具体性质或关系谓词常项：表示具体性质或关系例：例：是大学生，记为是大学生，记为F，F(张华张华)表示表示“张华是张华是大学生大学生”。n谓词变项：表示抽象及泛指的性质或关系谓词变项：表示抽象及泛指的性质或关系例：例：具有性质具有性质F，记为，记为F，F(张华张华)
4、：张华具有：张华具有性质性质F谓词常项和变项都用大写字母表示。谓词常项和变项都用大写字母表示。7一、个体词、谓词、量词的概念一、个体词、谓词、量词的概念nn元元谓谓词词(n 2):含含有有n个个个个体体变变项项的的谓谓词词。如：如：L(x,y)：x y，L是一个二元谓词。是一个二元谓词。n一元谓词一元谓词:只含有一个只含有一个个体变项个体变项的谓词。的谓词。如：如：F(x)：x是女孩。是女孩。n0元谓词元谓词:不含不含个体变项个体变项的谓词。的谓词。8一、个体词、谓词、量词的概念一、个体词、谓词、量词的概念如如：上上例例二二元元谓谓词词L中中的的x,y代代以以个个体体“2”和和“1”,则则L(
5、2,1)就就是是命命题题“2 1”。此此时时二二元元谓词变成谓词变成0元谓词。元谓词。同同理理：一一元元谓谓词词F(x)中中的的x代代以以个个体体“小小王王”，则则F(小小王王)就就是是命命题题“小小王王是是女女孩孩”。也也是是0元谓词。元谓词。谓词逻辑包括命题逻辑。谓词逻辑包括命题逻辑。9一、个体词、谓词、量词的概念一、个体词、谓词、量词的概念例例1：用：用0元谓词将下述命题符号化。元谓词将下述命题符号化。(1)墨西哥位于南美洲墨西哥位于南美洲在在命题逻辑命题逻辑中中,设设p:墨西哥位于南美洲墨西哥位于南美洲符号化为符号化为p,该命题为真命题。该命题为真命题。在在一阶逻辑一阶逻辑中中,设设a
6、：墨西哥；：墨西哥；F(x)：x位于南美洲；位于南美洲；符号化为符号化为F(a)10一、个体词、谓词、量词的概念一、个体词、谓词、量词的概念(2)是无理数仅当是无理数仅当是有理数是有理数在在一阶逻辑一阶逻辑中，中，设设F(x):x是无理数；是无理数；G(x):x是有理数是有理数符号化为符号化为在在命题逻辑命题逻辑中中,设设p: 是无理数是无理数;q:是有理数是有理数.符号化为符号化为p q,这是假命题。这是假命题。11一、个体词、谓词、量词的概念一、个体词、谓词、量词的概念（3）如果如果23，则，则33，q：3y，G(x,y)：x10。19二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化令令F
7、(x):x是无理数是无理数,G(y):y是有理数是有理数, L(x,y)：xy x (F(x) y(G(y) L(x,y)（2）有的无理数大于有的有理数）有的无理数大于有的有理数20二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化（3）没有不犯错的人。）没有不犯错的人。设：设：P(x)：x是人；是人；Q(x)：x犯错误。犯错误。21二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化令令F(x):x是金属，是金属，G(x):x是液体，是液体， L(x,y):x溶解在溶解在y中中（4）任何金属都可以溶解在某种溶液中。）任何金属都可以溶解在某种溶液中。22二、一阶逻辑中命题符号化二、一阶逻辑中命题符号
8、化（5）某些人对所有的花粉都过敏。）某些人对所有的花粉都过敏。令令F(x):x是人是人,G(y):y是花粉是花粉, L(x,y)：x对对y过敏。过敏。23二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化（6）所有的学生都上课了，这是错的。）所有的学生都上课了，这是错的。令令F(x):x是学生是学生,G(x):x上课了。上课了。这句话相当于这句话相当于“有些学生没有上课有些学生没有上课”。24二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化（7）不存在最大的整数。）不存在最大的整数。令令F(x):x是整数是整数,L(x,y)：x比比y大大。这句话相当于：这句话相当于：“任意一个整数，都存在比任意
9、一个整数，都存在比它大的整数它大的整数”。25二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化例例4：（教材例：（教材例4.5）将下列命题符号化）将下列命题符号化（1）兔子比乌龟跑得快。）兔子比乌龟跑得快。（2）有的兔子比所有的乌龟跑得快。）有的兔子比所有的乌龟跑得快。（3）并不是所有的兔子都比乌龟跑得快。）并不是所有的兔子都比乌龟跑得快。（4）不存在跑得同样快的两只兔子。）不存在跑得同样快的两只兔子。26二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化例例5:设设A(x):x能被能被3整除；整除；B(x):x能被能被6整除整除.个体域为：个体域为：1,2,6,7,12分析如下情况的真值。分析
10、如下情况的真值。真真假假真真真真27二、一阶逻辑中命题符号化二、一阶逻辑中命题符号化例例6：考虑个体域为实数域，则命题：考虑个体域为实数域，则命题“对于对于任意的任意的x，都存在，都存在y，使得，使得xy”应该符号化应该符号化为下面的哪一种形式？为下面的哪一种形式？令：令：L(x,y):x2,G(x):x1个体域个体域N,F(x):x1,G(x):x2成真解释成真解释代入得代入得A= x(x2x1) 真命题真命题成假解释成假解释代入得代入得A= x(x1x2) 假命题假命题40三、公式的解释三、公式的解释对公式中的各个抽象符号给出如下解释：对公式中的各个抽象符号给出如下解释：（1）个体域）个体
11、域D=N；（；（2）a=0（3）f(x,y)=x+y，g(x,y)=xy（4）F(x,y)：x=y例：例：由于公式是抽象的符号串，若不对它们给以由于公式是抽象的符号串，若不对它们给以具体解释，则公式是没有实在意义的。具体解释，则公式是没有实在意义的。41三、公式的解释三、公式的解释定义定义：解释：解释I由下面由下面4部分组成：部分组成：(a)非空个体域非空个体域DI(b)DI中一些特定元素的集合中一些特定元素的集合(c)DI上特定函数集合上特定函数集合(d)DI上特定谓词的集合上特定谓词的集合42三、公式的解释三、公式的解释 例例3 3 给定解释给定解释I I 如下如下: : (a)个体域个体
12、域D=N（包括（包括0）(b)(c)(d)谓词谓词说明下列公式在说明下列公式在I下的涵义下的涵义,并讨论真值。并讨论真值。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 z (y+z=x)(4) x y zF(f(x,y),z) x y z (x+y=z)真命题真命题假命题假命题(6) xF(g(
13、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)真命题真命题闭式闭式:不含自由出现的个体变项的公式。不含自由出现的个体变项的公式。例：例：定理：定理：闭式在任何解释下都是命题。闭式在任何解释下都是命题。46四、公式的类型四、公式的类型n永真式（逻辑有效式）永真式（逻辑有效
14、式）：无成假解释：无成假解释n矛盾式（永假式）矛盾式（永假式）：无成真解释：无成真解释n可满足式可满足式：至少有一个成真解释：至少有一个成真解释47例例5：证明下面公式不是永真式。：证明下面公式不是永真式。只要找到一个使公式成假的解释就可以证明该公只要找到一个使公式成假的解释就可以证明该公式不是永真式。式不是永真式。设论域为整数集合，设论域为整数集合，F(x,y):xyn前件为：对任意整数前件为：对任意整数x，存在整数，存在整数y，使得，使得xy。其。其真值为真值为真真。n后件为：存在整数后件为：存在整数x，对任意的整数，对任意的整数y都有都有xy。其。其真值为真值为假假。 所以在这样的解释下，公式为假，即不是永真式。所以在这样的解释下，公式为假，即不是永真式。48四、公式的类型四、公式的类型例：判断公式例：判断公式的类型的类型定定义义：设设A0是是含含命命题题变变项项p1,p2,pn的的命命题题公公式式，A1,A2,An是是n个个谓谓词词公公式式，用用Ai代代替替A0中中所所有有的的pi (1 i n) ，得到的公式，得到的公式A称为称为A0的的代换实例。代换实例。定理：定理：重言式的代换实例都是永真式，矛盾式的重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。代换实例都是矛盾式。49
