离散数学第二章谓词逻辑-1节.ppt

离 散 数 学,河南工业大学,信息科学与工程学院,第二章 谓词逻辑,第一章 内容回顾,1命题的概念、表示方法；联结词的逻辑意义。 2命题公式的递归定义，自然语言翻译成命题公式。 3真值表的构造、命题公式等价的概念。 4重言式与蕴含式的定义、逻辑意义，逻辑等价与逻辑蕴含的意义和证明方法。常用的逻辑等价公式和逻辑蕴含公式。 5命题公式的对偶式、合取范式、析取范式、主合取范式、主析取范式。小项、大项。任给公式化为析取范式、任给公式化为主析取范式、任给公式化为合取范式、任给公式化为主合取范式。 6命题逻辑的推理理论，主要的推理方法：真值表法、直接证明法、间接证明法。,第二章主要内容,谓词逻辑的引入 2.1 谓词的概念与表示 2.2 命题函数与量词 2.3 谓词公式与翻译 2.4 变元的约束 2.5 谓词演算的等价与蕴含式 2.6 前束范式 2.7 谓词演算的推理理论 小结 习题,本章学习要求,2.6 前束范式,2.4 变元的约束,2.5,2.7,谓词逻辑的引入,命题是具有真假意义的陈述句。 从语法上分析，这种句子一般有主语和谓语。 如：“我是大学生”，“7是质数”。 主语是句子叙述的主语，指出句子要表达、描述的人或物； 谓语是用来说明主语做了什么或处在什么状态。,谓词逻辑的引入,问题的提出： 在命题逻辑中，主要研究命题和命题演算，其基本组成单位是原子命题，一个原子命题只用一个字母表示，而且不对原子命题中的句子成分进行分解。这样有一些逻辑问题无法解决。如部分简单的论断不能用命题逻辑进行推证等。 通过例子看命题逻辑的缺点。,例子,例如.令：小张是大学生。 ：小李是大学生。 命题与中的谓语是相同的(是大学生)，只是主语不同。 从符号、中不能归纳出他们都是大学生的共性。 命题逻辑的局限性之一：无法表达原子命题之间所具有的共同特点。,命题逻辑的局限性之二: 不能反映命题的内部结构、成分和命题之间的内在联系。即不能将命题分解开。,逻辑学中著名的三段论方法，是由一个大前提，一个小前提推出结论的方法。 例如：著名的苏格拉底三段论： 显然这是正确的推理，但在命题逻辑中却无法得到证明。,所有的人都是要死的。 苏格拉底是人。 所以苏格拉底是要死的。,苏格拉底（前469-前399） 古希腊唯心主义哲学家。,P,Q,R,PQ R,判断PQR是否重言式？,谓词逻辑学习目的,命题逻辑中原子命题是最小的单位，不能够再进行分解，这给推理带来了很大局限性，本章引入谓词逻辑。学习关于谓词逻辑的相关概念和定理，解决实际问题。,2-1 谓词逻辑中的基本概念与表示,要求： 掌握的概念：谓词、谓词填式、n元谓词。,原子命题,一、客体与谓词,人总是要死的,人,是要死的,客体,谓词,客体,谓词,张三比李四高。,比高,张三、李四,能够独立存在的事物（句子中的主语、宾语等)。它可以是具体的，也可以是抽象的事物。客体一般是充当主语的名词或代词。,说明客体的性质、特征或客体之间的关系。,客体,谓词,谓词逻辑,客体和谓词的表示,在命题逻辑中， P： “张三是个大学生”， Q： “李四是个大学生”。 在谓词逻辑中， A： “是个大学生”， t： “张三”， f： “李四”，则 A(t)： “张三是个大学生”， A(f )： “李四是个大学生”。,单独谓词和客体不是完整的命题，必须在谓词字母后填以客体，称这样得到的式子为谓词填式。 格式：一个谓词（如A）和n个有次序的客体(如a1,a2,an)表示成A(a1,a2,an), 称它为该原子命题的谓词形式或命题的谓词形式。,客体：用带或不带下标的小写英文字母。 谓词：用带或不带下标的大写英文字母。,谓词,更一般地， A(x)：x是个大学生。,x：客体,A：谓词,A(x):原子命题的谓词填式,客体词的分类及表示,1.客体常量(元)：表示具体的或特定的客体， 一般用带或不带下标的小写英文字母 a,b,c,a1,b1,c1,等表示； 2.客体变量(元)：表示抽象的或泛指的客体， 一般用带或不带下标的小写英文字母 x, y, z, , x1, y1, z1, 等表示。,谓词分类与表示,用带或不带下标的大写字母来表示谓词， 如P,Q,R, 或A1,A2,A3,， 谓词常量(元) ：表示具体性质或关系的谓词。 如：P: “是大学生” 谓词常量(元)：表示抽象的、泛指的性质或关 系的谓词。 如：x与y具有关系L。 x，y都是客体变元，谓词为L。 这里仅讨论谓词常量。,n元谓词,定义4.2.3 n元谓词：含n个客体变元的谓词。 用P(x1,x2,xn)表示。 P(x1, x2, , xn)的值为0或1。 一元谓词：n=1时，表示x1具有性质P。 多元谓词：n2时，表示x1,x2,xn具有关系P。 0元谓词：不含客体变元的谓词。如F(x) 为一元谓词、P(x,y)为二元谓词，而F(a)、G(a,b)为0元谓词，即一般的命题。,元数：在谓词中所包含的客体变元的数量。,例,设有如下命题，并用谓词进行表示。 P：王童是一个三好学生； Q：李新华是李兰的父亲； R：张强与谢莉是好朋友； S：武汉位于北京和广州之间。,S(x)：x是一个三好学生 a：王童 命题P可表示为：S(a),F(x, y)：x是y的父亲 b：李新华 c：李兰 命题Q可表示为：F(b, c),T(x, y)：x与y是好朋友 d：张强 e：谢莉 命题R可表示为：T(d, e),B(x,y,z)：x位于y和z之间 w：武汉 b：北京 g：广州 命题S可表示为：B(w, b, g),结论,1.谓词中客体词的顺序十分重要，不能随意变更。 如命题F(b, c)为“真”，但命题F(c, b)为“假”； 2. S(a)与S(x)的不同： 如上例中S(x)：x是一个三好学生， a为王童。 S(a)是有真值的，但S(x)却没有真值。 具体命题的谓词表示形式和n元谓词是不同的，前者是有真值