离散数学----第二章-谓词逻辑(很清晰).pptVIP

离散数学;第一章内容回忆?;第二章主要内容;本章学习要求;谓词逻辑的引入;谓词逻辑的引入;例子;命题逻辑的局限性之二:不能反映命题的内部结构、成分和命题之间的内在联系。即不能将命题分解开。;《谓词逻辑》学习目的;2-1谓词逻辑中的根本概念与表示;原子命题;客体和谓词的表示;谓词;客体词的分类及表示;谓词分类与表示;n元谓词;例;结论;2-2命题函数与量词;命题函数;将命题函数→命题的两种方法;命题函数举例;2、个体域(论域);个体域(论域);3、量词：在命题中表示客体数量的词，称之为量词。;〔1〕所有的老虎都要吃人；

〔2〕每一个大学生都会说英语；

〔3〕所有的人都长着黑头发；

〔4〕有一些人登上过月球；

〔5〕有一些自然数是素数。;不便之处;不便之处(续);不便之处的根源;特性谓词;特性谓词的例子;特性谓词的例子〔续〕;〔2〕每一个大学生都会说英语；

无特性谓词：Q(x):x会说英语。(?x)Q(x)x∈{大学生}

〔3〕有一些自然数是素数。

无特性谓词：T(x)：x是素数。(?x)T(x)x∈{自然数};谓词逻辑符号化的两条规那么;带量词的公式在个体域内的展开式;作业;2-3谓词公式及命题符号化;谓词公式涉及的符号〔共七种〕：;谓词公式涉及的符号〔共七种〕：;为何需要客体函数符号？;客体函数与谓词的区别

客体函数中的客体变元用客体带入后的结果依然是客体。

f(a)=小王的父亲

谓词中的个体变元用确定的个体带入后就变成了命题。其真值为Ｔ或者为Ｆ。

M(x)：x是人

M(a)：小王是人

函词是个体域到个体域的映射

f:D→D

谓词是从个体域到{T,F}的映射

M:D→{T,F};例，用谓词表示命题：;合式公式;合式公式判断;谓词逻辑的翻译;例谓词逻辑符号化;例谓词逻辑符号化;例谓词逻辑符号化;例谓词逻辑符号化;例谓词逻辑符号化;例谓词逻辑符号化;思考;例谓词逻辑符号化;例将以下命题符号化

〔1〕兔子比乌龟跑得快。

〔2〕有的兔子比所有的乌龟跑得快。

〔3〕并不是所有的兔子都比乌龟跑得快。

〔4〕不存在跑得同样快的两只兔子。;谓词翻译难点;谓词翻译难点〔续〕;(?x)(S(x)→O(x));注意;作业;2-4变元的约束;;例;对约束变元和???由变元的说明;对约束变元和自由变元的说明〔续〕;变元混淆;二、约束变元换名和自由变元代入;;改名规那么和代入规那么的关系;例对以下公式分别利用换名和代入规那么改写;小结;2-5谓词演算的等价式和蕴含式;一、对谓词公式赋值;带量词的公式在个体域内的展开式;例;二、谓词合式公式的分类;例;三、谓词公式的等价公式定义;四、谓词公式的蕴含式定义;五、对偶定理;六、重要公式;〔一〕由命题公式推广出的公式;〔一〕由命题公式推广出的公式-例;〔二〕量词否认公式;证明;〔三〕量词辖域的扩充公式(空间规那么〕;;;;例?好好看看这个例子;〔四〕量词分配公式(等价式和蕴含式);例;例;注意公式3.和4.不是等价公式，是重言蕴含式。;公式4;公式1的证明(自学);公式3的证明〔自学〕;公式4的证明〔自学〕;〔四〕量词分配公式(等价式和蕴含式);量词分配公式总结;〔五〕其它公式;〔五〕其它公式;〔五〕其它公式;(?x)(?y)A(x,y);(?x)(?y)A(x,y)?(?y)(?x)A(x,y)证明;演算;(?y)(?x)P(x，y)?(?x)(?y)P(x，y)证明;例;本节小结;2-6 前束范式;一、前束范式定义;前束范式存在定理;二、前束范式的写法;例求(?x)A(x)→(?x)B(x)的前束范式;三、前束析取范式与前束合取范式;;;;作业;2-7谓词演算的推理理论;谓词演算的推理理论;命题演算的所有推理规那么:

P规那么、T规那么、CP规那么

量词相关的规那么:

全称量词消去规那么：US

全称量词引入规那么：UG

存在量词消去规那么：ES

存在量词引入规那么：EG;一、全称指定规那么US(UniversalSpecialization);US成立条件;二、全称推广规那么UG(UniversalGeneralization);三、存在推广规那么EG(ExistentialGeneralization);作用：去掉存在量词。

形式：

(?x)A(x)?A(c)

其中c是使A成立的特定客体常量。

含义：(?x)A(x)成立，即可推出有某个确定的c，使A(c)成立。

要求：

(1)c不是A(x)中的符号。

(2)c不应是在此之前用US规那么或者用ES规那么所指定的客体c(即本次用ES特指客体c，不应该是以前特指的客体)。

(3)如果A(x)中除x外有其他自由变元出现，且x