离散数学是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。 本课程介绍计算机科学和信息技术理论基础的概念和思想方法，介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念，介绍离散数学基本概念和空间信息技术之间的联系与结合，培养学生理解和掌握离散数学基本概念，采用形式化方法分析问题，并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。
28-数理逻辑-谓词公式永真式
Loading...
来自 Peking University 的课程
离散数学概论 Discrete Mathematics Generality
155 个评分
从本节课中
数理逻辑：谓词逻辑及形式系统
与讲师见面
陈斌副教授
北京大学
[音乐]
好，欢迎回来，下面我们来看看这个谓词公式当中的永真式，首先呢，
我们分析一下谓词公式成为命题，有确定条件，真值的这个条件，
我们上次实际上提到过，就是首先呢，要给定一个个体域，
然后呢对公式当中所有的谓词都有 明确的意义，也就是说都有一个解释，有一个解释，
第三呢，就是公式当中所有的这个自由变元都要取定一个个体，
那么永真式呢是，因为它是逻辑当中很重要的概念，所以呢，
我们来看看谓词公式，它成为，成真，或者说成为永真式
是有什么样的一个概念，那么我们说它有 四个层次，因为它具有确定真值的条件
有三个，所以呢我们来看看是哪四个层次。
像这样的一个层次就是包括了个体域 包括了谓词的解释，包括了这个个体变元x，
那么第一个层次就是说如果我给定一个个体域D，
然后公式A当中的每一个谓词符号的解释I也都给定了，
而且呢如果说A当中的每一个自由 变元x1到xn都分别取值u1到un，
如果在这样的一个确定条件下A为真的话，那么我们就把
这个谓词公式A就称作为在u1到un处为真， 这是它的第一个成真。
第二个层次呢如果说 A它在任何自由变元的任何取值下 都为真，那么就说A在
解释I的情况下为真，就是有一个固定的解释的情况下它是一个永真式。
那么如果说A在每一个解释，就是说你对于
谓词公式里头的每一个谓词可以进行任意的解释， 那么不管你是什么样的解释这个谓词
那么它都为真的话，那么就称为这个A在这个个体域D上是永真的，
最后如果说这个A呢强大到对于任何的这个个体域而言
D都永真，那么就简称为A是一个永真式， 也就是说它是一个无条件成立的一个式子。
那么反过来， 那么就是有可满足式以及永假式的这个定义，
我们说如果对于某一个个体域， 谓词的某一个解释你可以找到某一个解释
和自由变元的某一个取值，公式A 都在公式A在这个取值处
为真的话，那么就称之为公式A呢它是一个可满足式，
就是我不管说怎么找，我只要能够找到某一个特定条件下这个公式A能够成真，
那么它就是一个可满足式，当然如果说它不可满足，也就说我对于任何的个体域
任何的对谓词的任何的解释以及自由变元的任何取值都不能够使公式A为真，
那么这个时候就称A是一个永假式。
那么当然相应的， 谓词公式呢也有它们之间呢也有逻辑等价和逻辑蕴含的关系，
那所谓的逻辑等价呢，A和B，谓词公式A和B逻辑等价，它是
当且仅当说对于一切的个体域，一切的解释和一切的这个变元取值状况而言
A和B都拥有相同的真值的情况下，那么就才能够称A和B是逻辑等价的，
那么相应逻辑蕴含呢也是一样的，A逻辑蕴含B当且仅当是说对于一切的个体域，
一切的解释，对于一切使得A成真的这个变元取值状况
都能够使B为真，这个时候才能够称A是逻辑蕴含B的。
那么我们来看看一些重要的这个谓词演算的这个永真式，永真式。
那么首先呢，这个所有命题逻辑当中的重言式，
都是这个谓词逻辑里边的永真式，那么这个呢是可以确定的， 然后接下来呢，我们看这个带量词和谓词，
当A不含有变元x的时候， 那么任意xA和A呢是等价的，
存在xA和A也是等价，这就说明这个量词实际上 它并不起作用。
下面这三个式子，就是任意xA(x)，
它是逻辑蕴涵A(x)的，还有呢，A(x)呢是逻辑蕴涵存在xA(x)，
也就是说它这个，当你有 变元有量词进行约束的时候，那么
任意x，全称量词是最强的，那么有自由变元，那是中间，那么存在x，A(x)
呢，就是一个存在量词它是最弱的，所以呢，按照逻辑蕴涵的这个递推的，就是它是
可以传递的这么一个概念呢，当然也有 任意xA(x)是逻辑蕴涵存在xA(x)的。
接下来呢是关于这个量词之间相互变换的一个
永真式，那么它是说，非
存在x，然后非A，它是等价于任意xA(x)的，
所以也就是说全称量词和这个
存在量词之间有这样的一个转换关系，它可以互相表示， 那当然即使这样，反过来也是一样的，
非任意x非A，也就是说并不是所有的x
都会让A不成立，那么也就是说会有一些x 让A会成立的，所以它们是等价的。
当然如果少一些这个非，它们之间也可以相互地转换，
非存在xA(x)，也就是说不存在
x使得A成立，那么也就是说任何的x都会让A不成立，
接下来也是一样，如果并不是所有的x都让x
都让A成立，那么也就是说会有一些x，会让A不成立，是这样的。
第二组呢，当公式B，它是涉及到这个量词的辖域的问题，
当公式B不含有自由变元x的时候，它会有
像任意xA(x)这个全称量词的约束的情况下，那么这个B呢，
不管是跟前面的这个谓词公式是合取还是析取，
它都可以自由地进入和挪出这个 谓词公式，就挪出这个全称量词的这个辖域的，
那么对于存在量词，相应地，也是一样的。
那也就是说只要B当中不包含有这个自由变元x的时候，
它可以自由地进出这个两个量词的这个辖域，
而不会使得这个谓词公式呢会有任何的这个变化。
当然，如果你这个公式B当中包含了自由变元x的时候，
那么这个时候呢，情况就比较复杂一些， 当然对于全称量词和这个合取来说，它是没有变化的，
也就是说，所有的x，能够同时使得A和B都为真的话，那么也就是意味着
A，所有的x使得A成立，所有的 x使得B成立，那么这两者其实上是等价的。
但是这个就不一样，也就是说所有的x使得A成立，
析取上所有的x属于，让B成立， 它是会逻辑蕴涵这个任意的x，
要么呢A成立，要么B成立，这个从左到右是容易理解的，
那么为什么没有从右到左呢？那我们可以实际上可以这么样地来理解， 就是说，如果说是右边成立，
也就是说，它所有的x，要么是A成立，要么是B成立，
那么实际上它并不能够保证说所有的x都会让 A，全部都让A成立，或者呢，让B成立，
因为呢使得这个A成立和B成立的情况， 它这个x呢，它可能是错开的，有一部分x呢，
会让A成立，有一部分x让B成立而A不成立，如果这样的话，它就不能够再
用上这个全称量词，所以呢从右到左，是不能够有逻辑蕴涵关系的。
那么接下来第三个也是这样，就是有某些x，
让A和B同时成立的话，那么实际上就是意味着，
说A呢，它会在某些x的情况下成立， B呢，同时也会在某一些x成立的情况下成立，但是
反过来是不一样的，因为使得A成立和使得B成立的 这个x，这个个体，它可能会错开，它可能会错开，
它会没有交集，如果像这种状况，那么从右到左，它就不能够成立了。
接下来呢，是对于说存在量词的这个析取，
这个情况下呢，它是可以自由的这个组合，它们是逻辑等价的。
接下来这个第四组呢，它是关于
到，关系到量词的组合，两个量词的组合和顺序的问题，
如果是同名的量词，比如说是全称量词，两个全称量词， 那么你是可以自由地交换它们的次序的，但是如果涉及到
不同名的，一个是全称，一个是存在的话，那么就不行。
那么第二个呢，是说任意的x任意y， 都会使得这个A(x,y)成立，都会使得A成立，
那么它是蕴涵着，某一些y，会对所有的x
成立，某一些y，会对所有的x，让这个A成立，但是反过来是不显然是
不会成立的，那么第三个呢，这是最重要的，
是说这个存在量词和全称量词，它们之间的这个次序不能够随意交换， 因为它们所代表的含义是不一样的。
存在y，任意x使得A成立，是说 会有一些y，会有一些y，那么这些y呢，
对于每一个的x来说，都会让A成立，
那么如果是任意x，存在y呢，使得A成立，那个的意思呢是说，
每一个x，它都，它都会对应某一些y，让这个A成立， 所以呢从左到右它是可以成立的，
但是从右到左，并不是这样，从右到左呢，它是不能够逻辑蕴涵。
举一个例子，比如说，这个把这个A呢变成是x加y等于0，
那么右边这个式子就是说， 每一个x，它都会有一些y，使得说x加y等于0，
那当然，我们知道，只要是x的相反数，那么都会使得这个x加y等于0，
那这个是没错的，但是如果反过来说，到左边这个，
也就是说存在一个，存在y，对于任意的x来说，它都会有x加y等于0，那这个显然是- 不对的，
所以从右到左它是没有逻辑蕴涵关系的。
第四个式子呢，是说，全称 任意x存在y，它就蕴涵着存在y，存在x，
因为存在y，存在x，或者是说是存在x，存在 y，这个呢是，实际上是最弱的这个条件，那么
对于存在量词来说，两个你是可以自由地 交换次序的，而不会影响这个谓词公式的含义，所以它们是逻辑等价的。
最后一组呢，是关于蕴涵的，蕴涵。
当这个C当中没有自由变元x，这个公式， 那么我们可以看到，这个C它是可以自由地进出
这个蕴涵式的这个 量词的这个辖域的，所以呢任意x，C蕴涵A(x)，
那么是等价于C蕴涵着任意xA(x)， 那么存在量词，也是一样的。
第三个呢，是说明，说任意的就是全称量词，对于这个蕴涵而言，
任意x，A(x)蕴涵B(x)的话，它是蕴涵着，逻辑蕴涵任意xA(x)，蕴涵
任意xB(x)。
