《离散数学导论(盘) 教学课件 ppt 作者 王元元 张桂芸 第二章演示文稿》由会员分享，可在线阅读，更多相关《离散数学导论(盘) 教学课件 ppt 作者 王元元 张桂芸 第二章演示文稿（29页珍藏版）》请在金锄头文库上搜索。
1、第二章 谓词演算及其形式系统,2.1 个体、谓词和量词,2.2 谓词演算永真式,2.3 谓词公式的前束范式,2.4 一阶谓词演算形式系统,第二章 谓词演算及其形式系统,2.1.1 个体,2.1.2 谓词,2.1.3 量词,2.1.4 谓词公式及语句的形式化,第二章 谓词演算及其形式系统,2.1 个体、谓词和量词,2.2.3 两个原理与两个规则,2.2.1 谓词公式的真值规定,第二章 谓词演算及其形式系统,2.2 谓词演算永真式,2.4.1 一阶谓词演算形式系统FPC,2.4.2 一阶谓词演算的自然推理系统 FND,2.4.3 含等词的一阶谓词演算自然推 理系统,第二章 谓词演算及其形式系统,2
2、.4 一阶谓词演算形式系统,第二章 谓词演算及其形式系统,2.1 个体、谓词和量词,2.1.1 个体,常元,个体,个体域,全总域,变元,第二章 谓词演算及其形式系统,2.1 个体、谓词和量词,2.1.1 个体,确定的个体常用a，b，c等到小写字母或字 母串表示。a，b，c等称为常元（constants）。,不确定的个体常用字母x，y，z，u，v，w等来表示。它们被称为变元（variables）。,第二章 谓词演算及其形式系统,2.1 个体、谓词和量词,2.1.1 个体,谓词演算中把一切讨论对象都称为 个体，它们可以是客观世界中的具体 客体，也可以是抽象的客体，诸如数字、 符号等。,第二章 谓词
3、演算及其形式系统,2.1 个体、谓词和量词,2.1.1 个体,谓词演算中把讨论对象个体的全体称为 个体域（domain of individuals），常用字 母D表示，并约定任何D都至少含有一个成员。,当讨论对象遍及一切客体时，个体域特称为 全总域（universe），用字母U表示。,第二章 谓词演算及其形式系统,2.1 个体、谓词和量词,2.1.2 谓词,谓词的元数,谓词命名式,谓词填式,第二章 谓词演算及其形式系统,2.1 个体、谓词和量词,2.1.2 谓词,通常把谓词所携空位的数目称为谓词的元数。,含空位的写法有一个明显的缺点，可读性差。因此常用 变元来代替空位，它们被称为谓词命名式，
4、 简称谓词。,当谓词的空位上填入个体后，便产生一个关于该个体的语句，这时它被称为谓词填式 。,第二章 谓词演算及其形式系统,2.1 个体、谓词和量词,2.1.3 量词,量词（quantifiers） 指数量词“所有”和“有”，分别用 符号 （全称量词) 和 （存在量词)来表示。,第二章 谓词演算及其形式系统,2.1 个体、谓词和量词,2.1.3 量词,约束变元,自由变元,辖域,一阶谓词演算,第二章 谓词演算及其形式系统,2.1 个体、谓词和量词,2.1.3 量词,可以取值代入的变元则称为 自由变元（free variables）。,不可以取值代入的变元则称为 约束变元（free variabl
5、es）。,当量词用于一谓词或复合的谓词表达式式， 该谓词或复合的谓词表达式称为 量词的辖域（domains of quantifiers）,第二章 谓词演算及其形式系统,2.1 个体、谓词和量词,2.1.3 量词,当限定量词的指导变元为个体变元 （不用命题变元、谓词、函数变元 - 分别以命题、谓词、函数为值的变元） 时，谓词演算又称为一阶谓词演算 （first order predicate calculus）。,第二章 谓词演算及其形式系统,2.1 个体、谓词和量词,2.1.4 谓词公式及语句的形式化,定义2.1 以下条款规定的符号串称为谓词公式（ predicate forrmula），简
6、称公式。 （1）谓词填式是公式，命题常元是公式 （看作零元谓词）。 （2）如果A，B是公式，x为任一变元， 那么(A)， (AB)，(xA)，(x A)（当使用五个联结词时 还有(AB)，(AB)，(AB)）都是公式。 （3）只有有限步使用（1），（2）条款 所形成的符号串是公式。,第二章 谓词演算及其形式系统,2.2 谓词演算永真式,2.2.1 谓词公式的真值规定,定义2.2 给定个体域D及公式A中各谓词符号的解释I， 如果A中个体变元x1 ,xn分别取值u1 ,un 时A真，则称A在u1 ,un处真；当x1 ,xn 无论取D中怎样的个体u1 ,un, A 在u1 ,un处均真，则称A在解释
7、I下真。,第二章 谓词演算及其形式系统,2.2 谓词演算永真式,2.2.1 谓词公式的真值规定,定义2.3 给定个体域D，若公式A在每一解释I下均真，那么称A在D上永真。 若公式A对任何个体域D均有D上永真，则称A为永真式，或称A 永真（valid）。,定义2.4 公式A称为可满足的，如果对某一个体域、某一解释和变元的某一取值状况，A在此处取值真。 公式A不可满足时也称A为永假式。,第二章 谓词演算及其形式系统,2.2 谓词演算永真式,2.2.3 两个原理与两个规则,定义2.5 设谓词公式A中含自由变元x，设t为一个 体项，且t中无自由变元为A中的约束变元， 那么称t是在A中对x可代入的。,第
8、二章 谓词演算及其形式系统,2.2 谓词演算永真式,2.2.3 两个原理与两个规则,定理2.1（代入原理） 若A是永真式，那么对A中变元可代入的代入实例都是永真式。,定理2.2（替换原理） 设A，D为谓词公式，C为A的子公式， 且CD。 若B为将A中子公式C的某些出现（未必全部）替换为 D后所得的公式，那么AB。,第二章 谓词演算及其形式系统,2.2 谓词演算永真式,2.2.3 两个原理与两个规则, 定义2.6 设A为仅含联结词 ，的谓词公式， A*为将A中符号，t，f， , 分别换 为，f，t, ， 后所得的公式，那么 称A*为A的对偶式。,第二章 谓词演算及其形式系统,2.2 谓词演算永真
9、式,2.2.3 两个原理与两个规则,定理2.3（改名原理） 若公式A中无自由变元y，那么， xA(x) yA(y) , xA(x) yA(y),第二章 谓词演算及其形式系统,2.3 谓词公式的前束范式,定义2.7 公式A称为公式A的前束范式（prenex normal forms），如果AA，且A形如 Q1x1QnxnB其中Q1，Qn为量词 或 ，B中无量词，且仅含联结词，B称为母式。当B为合取（析取）范式时，A称为A的前束合取（析取）范式。,第二章 谓词演算及其形式系统,定理2.4 （前束范式定理） 对任意谓词公式均可作出其前束范式，进而作出其前束合取范式或前束析取范式。,2.3 谓词公式的
10、前束范式,第二章 谓词演算及其形式系统,2.4 一阶谓词演算形式系统,2.4.1 一阶谓词演算形式系统FPC,定义2.8 设x1,xn是公式A中的所有自由变元，那么公式x1xnA(或x1xnA(x1,xn)称为A的全称封闭式（generalization clusure）。,第二章 谓词演算及其形式系统,2.4 一阶谓词演算形式系统,2.4.1 一阶谓词演算形式系统FPC,定理2.5 对任意公式A，变元x，若 A，则 x A 。,全称推广规则,定理2.6 对任何公式集 ，公式A和变元x，x不是 中任一公式的自由变元，那么，若 A，则 x A。,第二章 谓词演算及其形式系统,2.4 一阶谓词演算
11、形式系统,2.4.1 一阶谓词演算形式系统FPC,定理2.7（存在消除定理） 设A，B为任意公式，变元x是公式A、但不是公式B的自由变元，那么当， x A(x) , A(x) B同时成立时，应有 B 。,定理2.6（推广的存在消除定理） 设 为一公式集，A，B为任意公式，变元x是A的自由变元，但不是 中任一公式的自由变元那么当 x A(x) ， A(x) B同时成立时，应有 B 。,第二章 谓词演算及其形式系统,2.4 一阶谓词演算形式系统,2.4.2 一阶谓词演算的自然推理系统FND,-消除规则,-消除规则,-引入规则,-引入规则,第二章 谓词演算及其形式系统,2.4 一阶谓词演算形式系统,2.4.3 含等词的一阶谓词演算自然推理系统,定理2.9 对任意项t1，t2，t3，有（ 表示FNDE ）。 （a） t1 = t2 t2 = t1 （b） t1 = t2 t2 = t3 t1 = t3,
