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

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