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

第四章一阶逻辑基本概念（谓词逻辑）1本章主要内容4.1一阶逻辑命题符号化4.2一阶逻辑公式及解释24.1一阶逻辑命题符号化个体词、谓词、量词的概念一阶逻辑命题的符号化3一、个体词、谓词、量词的概念定义：个体词（个体）:可以独立存在的具体或抽象的客体。1.个体词的基本概念例：我是老师。其中“我”就是个体词。张三比李四高。其中“张三”、“李四”都是个体词。4一、个体词、谓词、量词的概念个体常项：具体的客体，用a,b,c表示。个体变项：抽象或泛指的事物，用x,y,z表示。个体域（论域）:个体变项的取值范围。例：x高于y。x，y都是个体变项。有限个体域即个体域是有限集合无限个体域即个体域是无穷集合全总个体域宇宙间一切事物组成。5一、个体词、谓词、量词的概念2.谓词的基本概念定义:表示个体词性质或相互之间关系的词。例：张华是大学生。李凯是大学生。…是大学生例：张三比李四高。…比…高6一、个体词、谓词、量词的概念谓词常项：表示具体性质或关系例：…是大学生，记为F，F(张华)表示“张华是大学生”。谓词变项：表示抽象及泛指的性质或关系例：…具有性质F，记为F，F(张华)：张华具有性质F谓词常项和变项都用大写字母表示。7一、个体词、谓词、量词的概念n元谓词(n2):含有n个个体变项的谓词。如：L(x,y)：xy，L是一个二元谓词。一元谓词:只含有一个个体变项的谓词。如：F(x)：x是女孩。0元谓词:不含个体变项的谓词。8一、个体词、谓词、量词的概念如：上例二元谓词L中的x,y代以个体“2”和“1”,则L(2,1)就是命题“21”。此时二元谓词变成0元谓词。同理：一元谓词F(x)中的x代以个体“小王”，则F(小王)就是命题“小王是女孩”。也是0元谓词。谓词逻辑包括命题逻辑。9一、个体词、谓词、量词的概念例1：用0元谓词将下述命题符号化。(1)墨西哥位于南美洲在命题逻辑中,设p:墨西哥位于南美洲符号化为p,该命题为真命题。在一阶逻辑中,设a：墨西哥；F(x)：x位于南美洲；符号化为F(a)10一、个体词、谓词、量词的概念(2)是无理数仅当是有理数23在一阶逻辑中，设F(x):x是无理数；G(x):x是有理数符号化为)3()2(GF在命题逻辑中,设p:是无理数;q:是有理数.符号化为pq,这是假命题。2311一、个体词、谓词、量词的概念（3）如果23，则34。在命题逻辑中,设p：23，q：34.符号化为pq,这是真命题。在一阶逻辑中,设F(x,y)：xy，G(x,y)：xy,符号化为：F(2,3)G(3,4)12一、个体词、谓词、量词的概念3.量词的基本概念定义：表示个体常项或变项之间数量关系的词。例：有的人喜欢喝咖啡。所有的人都喜欢喝茶。13一、个体词、谓词、量词的概念全称量词:表示任意的,所有的,一切的等。如：x表示对个体域中所有的x；xF(x)表示对个体域中所有的x都有性质F例：F(x):x喜欢喝咖啡。当x的个体域为人类集合时，“所有的人都喜欢喝咖啡”可以符号化为：xF(x)14一、个体词、谓词、量词的概念存在量词:表示存在,“有的”等。如x表示在个体域中存在x。xF(x)表示对个体域中至少有一个x具有性质F。“有的人喜欢喝咖啡”符号化为：xF(x)15二、一阶逻辑中命题符号化例2：在两种不同的个体域D1、D2中，利用一阶逻辑的思想将下面命题符号化:(1)人都爱美。(2)有人用左手写字。D1：个体域为人类集合；D2：全总个体域。16二、一阶逻辑中命题符号化当个体域为D1时：(1)设G(x)：x爱美,符号化为xG(x)(2)设G(x)：x用左手写字符号化为xG(x)17二、一阶逻辑中命题符号化当个体域为D2时：设F(x)：x为人；G(x)：同上(1)x(F(x)G(x))(2)x(F(x)G(x))18二、一阶逻辑中命题符号化例3：采用谓词逻辑将下列命题符号化（1）有的偶数大于10。设：P(x)：x是偶数；Q(x)：x10。))()((xQxPx19二、一阶逻辑中命题符号化令F(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犯错误。))()((xQxPx))()((xQxPx或21二、一阶逻辑中命题符号化令F(x):x是金属，G(x):x是液体，L(x,y):x溶解在y中（4）任何金属都可以溶解在某种溶液中。))),()(()((yxLyGyxFx22二、一阶逻辑中命题符号化（5）某些人对所有的花粉都过敏。令F(x):x是人,G(y):y是花粉,L(x,y)：x对y过敏。))),()(()((yxLyGyxFx23二、一阶逻辑中命题符号化（6）所有的学生都上课了，这是错的。令F(x):x是学生,G(x):x上课了。))()((xGxFx这句话相当于“有些学生没有上课”。))()((xGxFx24二、一阶逻辑中命题符号化（7）不存在最大的整数。令F(x):x是整数,L(x,y)：x比y大。))),()(()((yxLyFyxFx这句话相当于：“任意一个整数，都存在比它大的整数”。))),()(()((xyLyFyxFx25二、一阶逻辑中命题符号化例4：（教材例4.5）将下列命题符号化（1）兔子比乌龟跑得快。（2）有的兔子比所有的乌龟跑得快。（3）并不是所有的兔子都比乌龟跑得快。（4）不存在跑得同样快的两只兔子。26二、一阶逻辑中命题符号化例5:设A(x):x能被3整除；B(x):x能被6整除.个体域为：{1,2,6,7,12}分析如下情况的真值。)()1(xxA)()2(xxA))()(()3(xBxAx))()(()4(xBxAx真假真真27二、一阶逻辑中命题符号化例6：考虑个体域为实数域，则命题“对于任意的x，都存在y，使得xy”应该符号化为下面的哪一种形式？令：L(x,y):xy),()2(),()1(yxxLyyxyLx28二、一阶逻辑中命题符号化小结：在不同的个体域中，同一个命题的符号化有可能不同。同一个命题，在不同的个体域中的真值也可能不同。多个量词出现时，顺序不能随意调换。294.2一阶逻辑公式及解释原子公式和合式公式公式的解释公式的类型个体变项的自由出现和约束出现30(1)单个命题常项或变项p,q,r,…是合式公式；(2)若A,B是合式公式，则(A)，(AB),(AB),(AB),(AB)也是合式公式；(3)只有有限次地应用(1)~(2)形成的包含命题变元、联结词和括号的符号串才是合式公式。命题逻辑合式公式的定义：(1)原子公式是合式公式;(2)若A、B是合式公式，则(A),(AB),(AB),(AB),(AB)是合式公式;(3)若A是合式公式，则xA,xA是合式公式;(4)所有合式公式都是有限次应用1~3形成的符号串。谓词逻辑合式公式的定义：原子命题公式n元谓词31一、原子公式和项定义：设P(x1,x2,…,xn)是任意的n元谓词，t1,t2,…,tn是任意的n个项，则称P(t1,t2,…,tn)是原子公式。1.个体常项和个体变项是项.2.若(x1,x2,…,xn)是任意的n元函数，t1,t2,…,tn是任意的n个项，则(t1,t2,…,tn)是项。3.所有的项都是有限次使用1,2得到的。32F(x,y)：yxxyyxgyxyxfyxyxG2),(),(:),(22G(f(x1,x2),g(x3,x4))F(x):x是无理数。F()2一、原子公式和项项33引例x(F(x,y)G(x,z))),()),(),((yxxPyxQyxPyx考察上述两个公式中个体变项受约束的情况。34二、个体变项的自由出现与约束出现定义：在公式xA和xA中，1.称x为指导变元；2.A为相应量词的辖域；3.在x和x的辖域中，x的所有出现都称为约束出现；4.A中不是约束出现的其他变项均称为自由出现。35二、个体变项的自由出现与约束出现例1：说明以下各式量词的辖域与变元的约束情况：（1）x(F(x,y)G(x,z))A=(F(x,y)G(x,z))为的辖域，x为指导变元,A中x的两次出现均为约束出现，y与z均为自由出现。36二、个体变项的自由出现与约束出现),()),(),((2yxxPyxQyxPyx）（)),(),((yxQyxPyx的辖域是),(),(yxQyxPy的辖域是),(yxPx的辖域是的出现均为约束出现，x.出现的最后一次出现为自由y37二、个体变项的自由出现与约束出现例2：使下面的公式不出现“既是约束出现又是自由出现的个体变项”。),,(),,(1zyxyGzyxxF）（),,(),,(zyxyGzyttF换名规则换名规则),,(),,(zwxwGzyttF换名规则：将量词辖域中某个约束变项的所有出现及对应的指导变元，改成另一个在辖域中未曾出现过的个体变项符号，公式中其余部分不变，则所得公式与原来的公式等值。38二、个体变项的自由出现与约束出现),,(),,(zyxyGzyxxF),,(),,(zytyGzyxxF代替规则代替规则)),,(),((2zyxyGyxFx）（)),,(),((zyxyGwxFx换名规则)),,(),((ztxtGyxFx代替规则),,(),,(zytyGzwxxF或代替规则：对某自由出现的个体变项用与原公式中所有个体变项符号不同的符号去代替，则所得公式与原来的公式等值。39三、公式的解释引例：给定公式A=x(F(x)G(x))个体域N,F(x):x2,G(x):x1个体域N,F(x):x1,G(x):x2成真解释代入得A=x(x2x1)真命题成假解释代入得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)),,(()),,((zyxgFyaxfF例：由于公式是抽象的符号串，若不对它们给以具体解释，则公式是没有实在意义的。41三、公式的解释定义：解释I由下面4部分组成：(a)非空个体域DI(b)DI中一些特定元素的集合(c)DI上特定函数集合(d)DI上特定谓词的集合},,,{1iaa}1,|{nifni}1,|{niFni42三、公式的解释例3给定解释I如下:(a)个体域D=N（包括0）(b)(c)(d)谓词说明下列公式在I下的涵义,并讨论真值。2axyyxgyxyxf),(,),(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=yy+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(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)真命题闭式:不含自由出现的个体变项的公式。例：)),(),((zxGyxFxyz定理：闭式在任何解释下都是命题。46四、公式的类型永真式（逻辑有效式）：无成假解释矛盾式（永假式）：无成真解释可满足式：至少有一个成真解释47