第四章一阶逻辑.pptVIP

凡是偶数都能被2整除。 6是偶数。 所以，6能被2整除。 第四章 一阶逻辑基本概念 一阶逻辑命题符号化 一阶逻辑公式及解释 (1) 1/3是无理数。  (2)x是有理数。 (3)小王与小李同岁。  (4)x与y具有关系L. 例4.1 将下列命题在一阶逻辑中用0元谓词符号化，并讨论它们的真值: ????(1)只有2是素数，4才是素数。 ????(2)如果5大于4，则4大于6. 例4.2 在个体域分别为(a),(b)条件时，将下列命题符号化 (1) 凡人都呼吸。 (2) 有的人用左手写字。 （a）个体域D1为人类集合 （b）个体域D2为全总个体域 例4.3 在个体域限制为(a),(b)条件时，将下列命题符号化 （1）对于任意的x,均有x2-3x+2=(x-1)(x-2) （2）存在x，使得x+5=3 其中:(a)个体域D1=N（N为自然数集合） (b)个体域D2 =R(R为实数集合） 小结 个体词：指研究对象中可以独立存在的具体的或抽象的客体。 谓词 用来刻划个体词性质及个体词之间相互关系的词。 量词：表示个体常项或变项之间数量关系的词。 例4.4 将下列命题符号化，并讨论它们的真值. (1)所有的人都长着黑头发。 (2)有的人登上过月球。 (3)没有人登上过木星。 (4)在美国留学的学生未必是亚洲人。 例4.5将下列命题符号化 （1）兔子比乌龟跑得快。 （2）有的兔子比所有的乌龟跑得快。 （3）并不是所有的兔子都比乌龟跑得快。 （4）不存在跑得同样快的二只兔子。 注意 分析命题中表示性质和关系的谓词，分别符号化为一元和n元谓词。 根据命题的实际意义选用全称量词或存在量词。 一般说来，多个量词出现时，他们的顺序不能随意调换。 有些命题的符号化形式不仅一种。 定义4.5 在公式?xA和?xA中，称x为指导变元，A为相应量词辖域。在?xA和?xA的辖域中， x的所有出现都称为约束出现，A中不是约束出现的其它变项均称为自由出现 例4.6指出下列公式中的指导变元，各量词的辖域，自由出现和約束出现的个体变项： （1）?x(F(x,y) ?G(x,z)) （2） ? x(F(x)?G(y))??y(H(x)?L(x,y,z)) 自由变元的代入规则是： （1）对于谓词公式中的自由变元，可以代入，此时需要对公式中出现该自由变元的每一处进行代入。 （2）用以代入的变元与原公式中所有变元的名称都不能相同。 定义4.6 设A是任意的公式，若A中不含自由出现的个体变项，则称A为封闭的公式，简称闭式。 定义4.4 谓词演算的合式公式定义如下： （1）原子公式是合式公式； （2）若A是合式公式，则（﹁A）也是合式公式； （3）若A，B是合式公式，则（A∧B）、（A∨B）、（A→B）、（A?B）是合式公式； （4）若A是合式公式，则?x A、 ? x A是合式公式； （5）只有有限次地应用（1）~（4）构成的符号串才是合式公式。 一阶逻辑公式的解释 一阶逻辑公式的一个解释I，是由非空区域D和对G中常项符号、函数符号、谓词符号以下列规则进行的一组指定组成： （1）对每一个常项符号指定D中一个元素。 （2）对每一个n元函数符号，指定一个函数。 （3）对每一个n元谓词符号，指定一个谓词。 给定解释I如下 个体域D=N a=0 f(x,y)=x+y,g(x,y)=x?y F(x,y)为x=y 在I下，下列哪些公式为真？哪些公式为假？哪些公式真值不能确定？ 解释 （1）F(f(x,y),g(x,y)) （2）F(f(x,a),y)?F(g(x,y),z) （3）?F(g(x,y),g(y,z)) （4） ?xF(g(x,y),z) （5） ?xF(g(x,a),x)?F(x,y) （6） ? xF(g(x,a),x) 定义4.8 设A为一公式，若A在任何解释下均为真，则称A为永真式。若A在任何解释下均为假则称A为矛盾式。若至少存在一个解释使A为真则称A是可满足式。 判断公式的类型 判断下列公式的类型 （1）?xF(x)??xF(x) （2）?x?yF(x，y)??x?yF(x，y) （3）?x(F(x)?G(x))??yG(y) 离散数学的应用问题 设计一个为三人小组进行秘密表决的电路，要求信号指示灯在两人或两人以上按下表决开关表示同意时亮，否则不亮。 这是著名物理学家爱因斯坦出过的一道题：一个土耳其商人，想找一个十分聪明的助手协助他经商。有两个人前来应聘，这个商人为了试一试哪一个聪明些，就把两个人带进一间漆黑的屋子里。他打开电灯，并告诉他们：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的。现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在头上，在我开