离散数学是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。 本课程介绍计算机科学和信息技术理论基础的概念和思想方法，介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念，介绍离散数学基本概念和空间信息技术之间的联系与结合，培养学生理解和掌握离散数学基本概念，采用形式化方法分析问题，并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。
26-数理逻辑-个体、谓词和量词
Loading...
来自 Peking University 的课程
离散数学概论 Discrete Mathematics Generality
150 个评分
从本节课中
数理逻辑：谓词逻辑及形式系统
与讲师见面
陈斌副教授
北京大学
[音乐] 嗨，你好，欢迎回来。
我们下面呢，就进入谓词逻辑的环节。
那么在谈谓词逻辑之前，我们先来看看命题逻辑的 有什么限制。
首先我们说， 命题逻辑中最小的研究单位，它是原子命题。
那么它既然叫做原子，那么就是说我们并不研究， 进一步研究它内部的结构了。
那么我们来看看这个定义。
命题呢，是对确定的对象作出判断的一个陈述句。
那么，我们要问。
如果对那些不确定的对象怎么样？比如说， x>5。
那x呢，它是在一定范围内取值的，不确定的一些变量。
那么这样的判断，我们来怎么表示。
以及呢，对于不同的条件下的判断会怎么样。
比如说，我们说所有的x都具有某一些性质，或者说只是有一些x，它具有这样的性质。
那么另外呢，在命题逻辑当中，
它里边的推理，它主要是关注这个真值的推演。
比如说，像假言推理、 归谬推理和穷举推理。
那么它们呢，都是建立在重言式以及代入和替换的原理 基础上的。
在命题逻辑当中， 命题之间，它相互是独立的，并没有内在的联系。
那么，这样呢就造成即便是我们很经典，
很简单的这个三段论的推理当中， 用命题逻辑表达都会有一些力不从心。
我们来看看有个例子。
那么一个呢，大前提说， 所有的学校都有学生。
那当然这个可以用一个形式话，命题p来表示它， 小前提，北京大学是学校。
那么最后得出结论，北京大学有学生。
那么这样一个大前提、 小前提再加上结论的 这么一个三段论。
显然它是正确的。
我们来 把它变成命题逻辑当中的形式化的结果来看一看。
那么显然就是， p合取上q，然后能够蕴含r。
当然我们也看出来了， 这样的一个正确的推理，三段论的推理。
它在命题逻辑当中，并不是永真式。
那这是为什么呢。
当然一个常识能告诉我们说，在命题逻辑当中， 它并没有把p、
q、 r看作是有联系的事情。
但是我们常识说，这三个命题实际上包含了有一些 有关联的概念，它并非是相互独立的。
比如说，这三个命题它们都谈到了学生和学校。
以及有一个具体的学校。
谈论了这些，使得它们命题之间是有关联的。
那么我们再回过头来， 对这个命题进行一个结构的分析。
那么，命题呢， 是对于确定的对象作出判断的陈述句。
那么在这儿呢，我们把这个被作判断的这些对象就称之为个体，
把这个作出的判断就称之为谓词。
那么还有呢，会涉及到对于个体的数量的 一个衡量。
比如说，那么就这些呢就称之为量词。
量词包括了对于所有的个体，或者说有些个体，或者说
没有任何的个体，这些。
那么谓词逻辑呢，它是把我们刚才所说的这个量词作用在个体上。
同时呢，引入个体变元，来讨论不确定的对象。
所以我们一般呢，把这个谓词逻辑也称作一阶逻辑。
当然如果再进一步，把这个量词作用于谓词，
引入谓词变元的话，那么这个呢，是属于二阶逻辑的研究范围。
这个不在我们本课的讨论范围之内。
下面我们来看看个体， 谓词，量词这三个概念它的具体的定义。
那么在谓词逻辑中，我们把一切被讨论的这些对象都 称之为个体。
那么，确定的个体呢，经常会用a，b，c这些字母来 表示。
这个就称之为个体的常元。
那么不确定的这些个体， 就可以经常用x，y，z或者u，v，w这样的字母来
表示它，称之为个体的变元。
那么我们 还会讨论个体的这个汇集。
就是被讨论对象的全体就称作为个体域，经常呢记作叫D，大写的D。
有一个特殊的个体域，就是包含一切对象的所有的个体域。
统称为，特称为全总域，叫做universe。
就是这个宇宙当中所包含的所有东西都在这了。
那这个呢记作为U，这个在特殊的时候会有特殊的用途。
第二个概念是谓词。
谓词呢它表示在 个体的，讨论个体的性质或者说个体之间的关系的时候
的一个语言的成分，因为它通常是在自然语言当中是以 谓语的形式出现的，所以就称之为谓词。
比如说，"北京大学是学校"，这当中的 "是学校"，"...是学校"，这个呢就是一个谓词。
那么还有呢，"张三和李四是朋友"，当中的"...和...是朋友" 那么这也是一个谓词。
那么当然也可以进一步的把 这个朋友抽掉，这叫"...和...是..."。
比如说朋友关系，或者说亲戚关系，或者说同学关系。
那么，在一个谓词当中可以放置个体 的空位的个数就称之为谓词的元数。
那么这样呢，就会有单元谓词。
比如说，"...是学校"，这是一个单元谓词。
有二元谓词， 比如说，"...和...是朋友"，这是一个二元谓词。
当然也有三元，比如说，"...和...是..."，那么这就是一个三元谓词。
那么，把这个谓词当中的个体的空位 因为我们不能老用这个空白来表示。
我们会把空位用变元的字母来代替它。
这个时候就称之为谓词的命名式。
这看起来就会像一个式子了。
我们通常呢，会用P，Q，R，大写的P，Q，R来表示谓词。
那么这样呢，谓词的命名式就像这样，P(x)，Q(x,y)， 或者R(x,y,z)这样的。
那么命名式当中的， 这些变元的字母并没有独立的含义，只是仅仅是占位符而已。
比如说，"...是学校"，我们会记作为SCHL(x)，
比如说，"...和...是朋友"，记作为FRD(x,y)， 那么，"...和...是..."，就可以记作为REL(x,y,r)，
这样，分别是单元，二元，三元谓词的 这个命名式。
当然，如果我们具体的在用的时候，
把这个谓词当中个体的空位，用具体的个体的变元或者常元来放进去的话，
那么这个时候就称作为谓词的填式了。
谓词的填式，它在形式上和命名式是相同的，但它是属于不同的概念。
需要根据上下文来加以区分。
这个有点类似于我们在c语言编程当中的函数说明。
函数在说明的时候，它是描述空位的，调用的形参，形式参数。
那么你在进行函数调用的时候，形式也差不多，但是， 这时候呢，你会用一个变量或是一个常量放进去。
那么这叫做实在参数，叫实参。
这样一个区分，这就容易理解了。
那么，像谓词的填式。
于是我们把具体的一个个体放进去.比如说SCHL(北京大学)，那么就是表述说， 北京大学是学校，当然如果说是，
SCHL(清华大学)，那么就表示清华大学是学校。
这样的概念。
比如说，FRD(张三,李四)，就表示张三和李四是朋友。
比如说把李四和王五放进去，那么就表示李四和王五是朋友。
比如说还有，R(x)， 这就表示说x是实数，那这个x呢
它可以是一个变元。
那么， 当一个谓词填式当中的个体全都是常元的时候，
它就不包含任何变元的时候，那么它就会变成一个命题。
从而呢，具有确定的真值，比如说像R(x)， 我们如果把这个x呢，用一个常元，用1代进去。
那么， 1是实数，那么它就是一个确定的一个命题，它就真值为真。
第三个呢是量词。
量词呢，就是指这个数量词"所有"或者说"有"的。
那么我们把这个"所有"就称之为全称量词 记做为一个这样的一个符号
它实际上呢是用英文来表示，是说Any或者All。
那我们也可以看出来了 这一个符号呢，它跟这个Any/All的这个词头A是有关系的，它是把A
颠倒过来，倒过来写，所以这样一个符号就好理解了 那么有的呢就称为存在量词。
记做为 反写的E，Exist，反写的一个E
所以我们说很多数学符号，它其实设计得也是非常巧妙的。
那么量词如果作用于谓词的话，那么它不能够直接写在谓词的前面。
那么它需要引入一个指导变元， 同时放在量词后边和谓词的填式中间。
比如说应该写成这样，就是∀xP(x)，或者说∃xP(x)这样的形式，
那么这个指导变元呢是不可以用 再取值代入的。
因为它虽然是一个变元，但是它已经被约束了，它被量词所约束 那么而且呢这个约束变元它是可以改名。
比如说 像下面的∀xP(x)，你可以改成∀yP(y)，
从而不会改变这个语句本身的含义。
那么 对于那些可以取值代入的个体变元，也就是没有被 量词所约束的那些个体变元呢就称为自由变元
那么量词所作用的 这个谓词或者复合的谓词表达式
就称之为量词的辖域，也就是说它这个量词会作用到哪 个谓词以及哪些谓词。
那么对于 一元谓词来说，像∀xP(x)或者说∃xP(x)
那么实际上都是命题，因为它已经被约束了，它不可以再取值代入
那么而且呢特别的，对于有穷的个体域而言 那么像∀xP(x)呢就等价于
P(a1)∧P(a2)……∧P(aN)。
那么 (a1)到(aN)呢就是x的取值范围，就是x的所取的那个个体域
那么∃xP(x)呢就等价于P(a1)然后∨
P(a2)∨P(a3)……∨P(aN)这么一个 所以呢它是有做为一个等价的命题是这样的
我们来看看用量词的一些例子 比如说我们把这个个体域取做是全体的人类
那么∃x然后FRD(x,张三)
那这个呢就表示说，张三呢在这个世界上还是有一些人是他的朋友的
就不至于说那么特别的悲惨，谁都没有朋友
那么第二个呢如果我们把个体域取值为(1,2)，就这两个自然数 这就是一个个体域，那么∀x(x＞0)
那它就等价于(1＞0)∧(2＞0) 这样的一个。
第三呢，这个体域如果取值为所有的正整数的话
那我们可以试图来表示一个这个哥德巴赫猜想 那哥德巴赫猜想是怎么说的呢？是说所有大于2的
偶数，都可以表示成为两个素数之和 好，我们展现一下这个公式。
那么它从 左到右是这样的∀x然后∃p∃q
那么x是一个偶数，并且x大于2，那么就蕴含着 x呢会等于p+q，是p和q的和
并且呢，p是素数，q是素数 那这样呢，实际上就用一个短短的一个公式，
实际上就可以把哥德巴赫猜想的这个内容就可以表达出来了。
那么到这儿为止，你是不是认为说我们终于有一个
谓词逻辑，它好像大概功能还是比较强大的，是吧？
