全套电子课件：离散数学导论.ppt

1、离散数学离散数学是研究离散数量关系和离散结构离散数量关系和离散结构数学模型的数学分支的统称。是计算机科学与技术专业的核心基础课程。计算机求解问题的基本模式计算机求解问题的基本模式:实际问题实际问题 算法设计算法设计 编程实现编程实现 第一章第一章 命题演算及其命题演算及其 形式系统形式系统第二章第二章 谓词演算及其谓词演算及其 形式系统形式系统*第三章第三章 消消 解解 原原 理理第五章第五章 关关 系系 第六章第六章 函函 数数 第七章第七章 基基 数数第八章第八章 图图 第九章第九章 特特 殊殊 图图 第十章第十章 代数结构通论代数结构通论第十一章第十一章 群、环、域群、环、域第十二章第十

2、二章 格与布尔代数格与布尔代数第一篇 数理逻辑数理逻辑第二篇 集合论集合论 第四章第四章 集合及其运算集合及其运算第三篇 图图 论论第四篇 抽象代数抽象代数 第第 一一 篇篇 数数 理理 逻逻 辑辑（mathematical logic）是用数学的方法来研究人类推理过程的一门数学学科。是用数学的方法来研究人类推理过程的一门数学学科。又称又称符号逻辑、现代逻辑符号逻辑、现代逻辑。其显著特征是符号化和形式化，其显著特征是符号化和形式化，即把逻辑所涉及的即把逻辑所涉及的“概念、判断、推理概念、判断、推理”用符号来表用符号来表示，用公理体系来刻划示，用公理体系来刻划,并基于符号串形式的演算来描并基于符

3、号串形式的演算来描述推述推理过程的一般规律。理过程的一般规律。逻辑演算四个分支：逻辑演算四个分支：公理集合论、证明论、模型论和递归论。公理集合论、证明论、模型论和递归论。第第 一一 章章 命题演算及其形式系统命题演算及其形式系统 1.1 命题与联结词命题与联结词1.2 重重 言言 式式1.3 范式范式*1.4 命题演算形式系统命题演算形式系统第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1.1 命题命题1.1.2 联结词联结词1.1.3 命题公式及其真值表命题公式及其真值表1.1.4 语句的形式化语句的形式化 第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1

4、 命题与联结词命题与联结词1.2.1 重言式概念重言式概念1.2.2 逻辑等价式和逻辑蕴涵式逻辑等价式和逻辑蕴涵式1.2.3 对偶原理对偶原理第一章第一章 命题演算及其形式系统命题演算及其形式系统1.2 1.2 重重 言言 式式1.3.1 析取范式和合取范式析取范式和合取范式1.3.2 主析取范式与主合取范式主析取范式与主合取范式1.3.3 联结词的扩充与归约联结词的扩充与归约第一章第一章 命题演算及其形式系统命题演算及其形式系统1.3 1.3 范式范式1.4.1 证明、演绎和推理证明、演绎和推理1.4.2 命题演算形式系统命题演算形式系统PC1.4.3 自然推理系统自然推理系统ND 第一章第

5、一章 命题演算及其形式系统命题演算及其形式系统*1.4 1.4 命题演算形式系统命题演算形式系统第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词 1.1.1 1.1.1 命题命题 我们把对确定我们把对确定的对象作出判断的陈述句的对象作出判断的陈述句称作称作（propositions or statements）当判断正确或符合客观实际时，当判断正确或符合客观实际时，称该命题称该命题（true），），否则称该命题否则称该命题（false）。）。第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词 1.1.

6、1 1.1.1 命题命题 通常把不含有逻辑联结词的命题通常把不含有逻辑联结词的命题称为称为或或（atoms）把由原子命题和逻辑联结词共同组成的把由原子命题和逻辑联结词共同组成的命题称为命题称为（compositive propositions or compound statements）第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.2 1.1.2 联结词联结词否定词否定词“并非并非”合取词合取词“并且并且”析取词析取词“或或”蕴涵词蕴涵词“如果如果，那么，那么”双向蕴涵词双向蕴涵词“当且仅当当且仅当”第一章第一章 命题演算及其形式系统

7、命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.2 1.1.2 联结词联结词词（词（negation）“并非并非”（not ），），用符号用符号“”表示。表示。p p 0 1 1 0可用表可用表1.1来规定否定词来规定否定词“”的意义的意义:p读作读作“并非并非p”或或“非非p”。第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.2 1.1.2 联结词联结词合取合取词（词（conjunction）“并且并且”（and ），），用用符号符号“”表示表示。可用表可用表1.2来规定合取词来规定合取词“”的意义：的意义：p q

8、 p q 0 0 1 1 0 1 0 1 0 0 0 1pq读作读作“p并且并且q”或或“p且且q”第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.2 1.1.2 联结词联结词 词（词（disjunction）“或或”（or）用符号用符号“”表示。表示。可用表可用表1.3来规定析取词来规定析取词“”的意义：的意义：pq读作读作“p或者或者q”、“p或或q”。p q p q 0 0 1 1 0 1 0 1 0 1 1 1第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.2 1.1.2 联

9、结词联结词 词（词（implication)“如果如果，那么，那么”（ifthen），用符号），用符号“”表示。表示。可用表可用表1.5来规定该蕴涵词来规定该蕴涵词“”的意义：的意义：p q p q 0 0 1 1 0 1 0 1 1 1 0 1pq中的中的p称为称为，q称为称为。第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.2 1.1.2 联结词联结词 词词(two-way-implication)“当且仅当且仅当当”（if and only if），用符号），用符号“”表示。表示。可用表可用表1.6来规定该双向蕴涵词来规定该双向蕴涵

10、词“”的意义：的意义：p q p q 0 0 1 1 0 1 0 1 1 0 0 1pq读读作作“p双向蕴涵双向蕴涵q”，“p当且仅当当且仅当q”，“p等价于等价于q”。第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.3 1.1.3 命题公式及其真值表命题公式及其真值表命题常元命题常元 命题公式命题公式 指派指派 弄真与弄假弄真与弄假真值表（真值表（truth table）命题变元命题变元第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.3 1.1.3 命题公式及其真值表命题公式及其真

11、值表 我们把表示具体命题及表示常命我们把表示具体命题及表示常命题的题的p，q，r，s等与等与f，t统称为统称为（proposition constants）。）。（proposition variable）是以是以“真、假真、假”或或“1，0”为取值范围的变元，为取值范围的变元，它未指出符号所表示的具体命题它未指出符号所表示的具体命题。第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.3 1.1.3 命题公式及其真值表命题公式及其真值表 以下三条款规定了以下三条款规定了（proposition formula）的意义：的意义：命题常元和命题

12、变元是命题公式，也称为原子公式或原子。命题常元和命题变元是命题公式，也称为原子公式或原子。如果如果A，B是命题公式，那么（是命题公式，那么（A），（），（AB），），（AB），（），（AB），（），（AB）也是命题公式。）也是命题公式。只有有限步引用条款（只有有限步引用条款（1），（），（2）所组成的符号串）所组成的符号串 是命题公式。是命题公式。定义定义1.1第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.3 1.1.3 命题公式及其真值表命题公式及其真值表 对任意给定的命题变元对任意给定的命题变元p1,pn的一种取值的一种取值状况，称

13、为状况，称为或或（assignments），用字母用字母，等表示等表示 当当A对取值状况对取值状况 为真时，称指派为真时，称指派 A或或 是是A的成真赋值，记为的成真赋值，记为(A)=1；反之称指派反之称指派 A或或 是是A的成假赋值，记为的成假赋值，记为 (A)=0。第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.3 1.1.3 命题公式及其真值表命题公式及其真值表 对一切可能的指派对一切可能的指派,公式公式A的取值可能用下表来描述，这个表的取值可能用下表来描述，这个表称为称为（truth table）p q r qr p (qr)(p

14、(qr)0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 11111000100001110第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.4 1.1.4 语句的形式化语句的形式化 语句形式化语句形式化主要是以下几个方面：主要是以下几个方面：要准确确定原子命题，并将其形式化。要准确确定原子命题，并将其形式化。要选用恰当的联结词，尤其要善于识别自然语言中的要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略），否定词的位置要放准确。联结词（有时它们被省

15、略），否定词的位置要放准确。必要必要时可以进行改述，即改变原来的叙述方式，时可以进行改述，即改变原来的叙述方式，但要保证表达意思一致但要保证表达意思一致。需要的括号不能省略，而可以省略的括号，需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略。在需要提高公式可读性时亦可不省略。要注意语句的形式化未必是唯一的。要注意语句的形式化未必是唯一的。第一章第一章 命题演算及其形式系统命题演算及其形式系统1.2 1.2 重重 言言 式式1.2.1 1.2.1 重言式概念重言式概念定义定义1.2重言式重言式 不可满足式不可满足式 可满足式可满足式 第一章第一章 命题演算及其形式系统命题演

16、算及其形式系统1.2 1.2 重重 言言 式式1.2.1 1.2.1 重言式概念重言式概念 对命题公式对命题公式A，如果对，如果对A中命题变元的一切指派均中命题变元的一切指派均弄真弄真A，则，则A称为称为（tautology），），又称又称.如果至少有一个指派弄真如果至少有一个指派弄真A，则，则A称为称为（satisfactable formula or contingency）。）。第一章第一章 命题演算及其形式系统命题演算及其形式系统1.2 1.2 重重 言言 式式1.2.1 1.2.1 重言式概念重言式概念 如果对如果对A中命题变元的一切指派均中命题变元的一切指派均弄假弄假A，则称，则称

17、A为为或或（contradiction or absurdity）或或。第一章第一章 命题演算及其形式系统命题演算及其形式系统1.2 1.2 重重 言言 式式1.2.2 .2.2 逻辑等价式和逻辑蕴涵式逻辑等价式和逻辑蕴涵式 当命题公式当命题公式AB为重言式时，称为重言式时，称A逻辑等价于逻辑等价于B，记为记为A B，它又称为，它又称为（logically equivalent or equivalent）。定义定义1.3当命题公式当命题公式AB为重言式时，称为重言式时，称A逻辑蕴涵逻辑蕴涵B，记为记为A B，它又称为，它又称为(logically implication)。定义定义1.4第一

18、章第一章 命题演算及其形式系统命题演算及其形式系统1.2 1.2 重重 言言 式式1.2.2 1.2.2 逻辑等价式和逻辑蕴涵式逻辑等价式和逻辑蕴涵式性质：性质：定理定理1.1 （1）AB当且仅当当且仅当 AB （2）A B当且仅当当且仅当 AB （3）若）若AB，则，则BA （4）若）若AB，BC，则，则AC （5）若）若A B，则，则B A （6）若）若A B，B C，则，则A C （7）若）若A B，AA，BB，则，则A B第一章第一章 命题演算及其形式系统命题演算及其形式系统1.2 1.2 重重 言言 式式1.2.2 1.2.2 逻辑等价式和逻辑蕴涵逻辑等价式和逻辑蕴涵式式 设设A为永

19、真式，为永真式，p为为A中命题变元，中命题变元，A(B/p)表示将表示将A中中p的的出现出现代换为公式代换为公式B后后所得的命题公式（称为所得的命题公式（称为A的一个代入实例），的一个代入实例），那么那么A(B/p)亦为永真式。亦为永真式。定理定理1.2-（rule of substitution），简记为），简记为RS第一章第一章 命题演算及其形式系统命题演算及其形式系统1.2 1.2 重重 言言 式式1.2.2 1.2.2 逻辑等价式和逻辑蕴涵式逻辑等价式和逻辑蕴涵式 设设A为一命题公式，为一命题公式，C为为A的子公式的子公式（A的一部分，且自身为一公式），的一部分，且自身为一公式），且且

20、CD。若将。若将A中子公式中子公式C的的（未必全部）出现替换为（未必全部）出现替换为D后得到公式后得到公式B，那么那么A B。定理定理1.3-（rule of replacement），简记为），简记为RR第一章第一章 命题演算及其形式系统命题演算及其形式系统1.2 1.2 重重 言言 式式1.2.3 1.2.3 对偶原理对偶原理 设公式设公式A仅含联结词仅含联结词，A*为为将将A中符号中符号，t，f分别改换为分别改换为，f，t后所得的公式，那么称后所得的公式，那么称A*为为A的的（dual）。）。定义定义1.5第一章第一章 命题演算及其形式系统命题演算及其形式系统1.2 1.2 重重 言言

21、式式1.2.3 1.2.3 对偶原理对偶原理 定理定理1.4 设公式设公式A中仅含命题变元中仅含命题变元p1,pn，及联结词，及联结词，那么，那么 AA*(p1/p1,pn/pn)定理定理1.5设设A，B为仅含联结词为仅含联结词，和命题变元和命题变元p1,pn的命的命题公式，且满足题公式，且满足A B，那么有，那么有B*A*。进而当。进而当A B时有时有A*B*。常把常把B*A*，A*B*称为称为A B和和A B的的。第一章第一章 命题演算及其形式系统命题演算及其形式系统1.3 1.3 范式范式1.3.1 1.3.1 析取范式和合取范式析取范式和合取范式(letters)：指命题常元、变元及它

22、们的否定，：指命题常元、变元及它们的否定，前者又称前者又称，后者则称，后者则称。(disjunctive clauses)：指文字或若干文字：指文字或若干文字的析取。的析取。(conjunctive clauses)：指文字或若干文字：指文字或若干文字的合取。的合取。(complemental pairs of letters)：指形如指形如L，L（L为文字）的一对字符。为文字）的一对字符。第一章第一章 命题演算及其形式系统命题演算及其形式系统1.3 1.3 范式范式1.3.1 1.3.1 析取范式和合取范式析取范式和合取范式 定义定义1.6 命题公式命题公式A称为公式称为公式A的的（disj

23、unctive normal form），如果，如果 AA A为一合取子句或若干合取子句的析取为一合取子句或若干合取子句的析取。定义定义1.7 命题公式命题公式A称为公式称为公式A的的（conjunctive normal form）如果如果 AA A为一析取子句或若干析取子句的合取。为一析取子句或若干析取子句的合取。第一章第一章 命题演算及其形式系统命题演算及其形式系统1.3 1.3 范式范式1.3.2 1.3.2 主析取范式与主合取范式主析取范式与主合取范式 定义定义1.8设设A为恰含命题变元为恰含命题变元p1,pn的公式。的公式。公式公式A,称为称为A的的（majordisjunctiv

24、e（conjunctive）normal form），），如果如果A,是是A的析（合）取范式，并且其每个的析（合）取范式，并且其每个 合（析）取子句中合（析）取子句中p1,pn均恰出现一次。均恰出现一次。第一章第一章 命题演算及其形式系统命题演算及其形式系统1.3 1.3 范式范式1.3.3 1.3.3 联结词的扩充与归约联结词的扩充与归约 定义定义1.9 称称n元联结词元联结词h是用是用m 个联结词个联结词g1,g2,gm 的，如果的，如果 h(p1,p2,.,pn)A而而A中所含联结词仅取自中所含联结词仅取自g1,g2,.,gm。第一章第一章 命题演算及其形式系统命题演算及其形式系统1.3

25、 1.3 范式范式1.3.3 1.3.3 联结词的扩充与归约联结词的扩充与归约 定义定义1.10当联结词组当联结词组g1,g2,.,gm可表示所有可表示所有一元、二元联结词时，称其为一元、二元联结词时，称其为（complete group of connectives）。）。第一章第一章 命题演算及其形式系统命题演算及其形式系统*1.4 1.4 命题演算形式系统命题演算形式系统1.4.1 1.4.1 证明、演绎和推理证明、演绎和推理 定义定义1.11 公式序列公式序列A1,A2,Am称为称为Am的一个的一个（proof），），如果如果Ai(1 i m)或者是公理，或者由或者是公理，或者由Aj1

26、,Ajk(j1,jk i)用推理规则推得。当这样的证明存在时，用推理规则推得。当这样的证明存在时，称称Am为系统的为系统的（theorems），），记为记为*Am,(为所讨论的系统名为所讨论的系统名),或简记为或简记为Am。第一章第一章 命题演算及其形式系统命题演算及其形式系统*1.4 1.4 命题演算形式系统命题演算形式系统1.4.1 1.4.1 证明、演绎和推理证明、演绎和推理 定义定义1.12 设设 为一公式集合。公式序列为一公式集合。公式序列A1,A2,Am称为称为Am的的以以 为前提的为前提的（diduction），如果），如果Ai(1im)或者是或者是 中公式，或者是公理，或者由中

27、公式，或者是公理，或者由Aj1,Ajk(j1,jk i)用推理规则导出。当有这样的用推理规则导出。当有这样的演绎时，演绎时，Am称为称为 的的，记为，记为 *Am,(为所讨论的系统名为所讨论的系统名)，或简记为，或简记为 Am。称称 和和 的成员为的成员为Am的的(hypothesis)。第一章第一章 命题演算及其形式系统命题演算及其形式系统*1.4 1.4 命题演算形式系统命题演算形式系统1.4.2 1.4.2 命题演算形式系统命题演算形式系统PCPC定理定理1.6（，sondness）若公式若公式A是系统是系统PC的定理，则的定理，则A为永真式。为永真式。若若A是公式集是公式集 的演绎结果

28、，那么的演绎结果，那么A是是 的逻辑结的逻辑结果。即果。即 若若PC A，则，则 A.若若 PC A，则，则 A.定理定理1.7 PC是一致的，即没有公式是一致的，即没有公式A使得使得PC A与与PCA同时成立。同时成立。第一章第一章 命题演算及其形式系统命题演算及其形式系统*1.4 1.4 命题演算形式系统命题演算形式系统1.4.2 1.4.2 命题演算形式系统命题演算形式系统PCPC定理定理1.8（，completeness）若公式若公式A永真，则永真，则A必为必为PC的定理；若公式的定理；若公式A是公是公式集式集 的逻辑结果，那么的逻辑结果，那么A必为必为 的演绎结果。即的演绎结果。即若

29、若 A，那么，那么 PC A.若若 A，那么，那么 PC A.第一章第一章 命题演算及其形式系统命题演算及其形式系统*1.4 1.4 命题演算形式系统命题演算形式系统1.4.2 1.4.2 命题演算形式系统命题演算形式系统PCPC定理定理1.9（）对任意公式集对任意公式集 和公式和公式A，B，AB A B（当（当 =时，时，AB A B，或，或A B）第一章第一章 命题演算及其形式系统命题演算及其形式系统*1.4 1.4 命题演算形式系统命题演算形式系统1.4.2 1.4.2 命题演算形式系统命题演算形式系统PCPC定理定理1.10（）对任何公式集对任何公式集 和公式和公式A，B,若若 A B

30、，A B，那么，那么 A。定理定理1.11（）对任何公式集，公式对任何公式集，公式A，B，若，若 A B，A B，则，则 B。第一章第一章 命题演算及其形式系统命题演算及其形式系统*1.4 1.4 命题演算形式系统命题演算形式系统1.4.3 4.3 自然推理系统自然推理系统ND ND 定理定理1.12 如果公式如果公式A是是PC的定理，那么的定理，那么A也必定是也必定是ND的定理。的定理。即即PC A蕴涵蕴涵ND A。第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.1 个体、谓词和量词个体、谓词和量词2.2 谓词演算永真式谓词演算永真式2.3 谓词公式的前束范式谓词公式的前束范式 2

31、.4 一阶谓词演算形式系统一阶谓词演算形式系统 第二章第二章 谓词演算及其形式系统谓词演算及其形式系统 2.1.1 个体个体2.1.2 谓词谓词2.1.3 量词量词2.1.4 谓词公式及语句的形式化谓词公式及语句的形式化 第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.1 2.1 个体、谓词和量词个体、谓词和量词2.2.3 两个原理与两个规则两个原理与两个规则2.2.1 谓词公式的真值规定谓词公式的真值规定 第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.2 2.2 谓词演算永真式谓词演算永真式 2.4.1 一阶谓词演算形式系统一阶谓词演算形式系统FPC 2.4.2 一阶谓

32、词演算的自然推理系统一阶谓词演算的自然推理系统 FND2.4.3 含等词的一阶谓词演算自然推含等词的一阶谓词演算自然推 理系统理系统 第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.4 2.4 一阶谓词演算形式系统一阶谓词演算形式系统 第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.1 2.1 个体、谓词和量词个体、谓词和量词2.1.1 2.1.1 个体个体常元常元 个体个体 个体域个体域 全总域全总域 变元变元 第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.1 2.1 个体、谓词和量词个体、谓词和量词2.1.1 2.1.1 个体个体 确定的个体常用确定的个体常

33、用a，b，c等到小写字母或字等到小写字母或字母串表示。母串表示。a，b，c等称为等称为（constants）。）。不确定的个体常用字母不确定的个体常用字母x，y，z，u，v，w等等来表示。它们被称为来表示。它们被称为（variables）。）。第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.1 2.1 个体、谓词和量词个体、谓词和量词2.1.1 2.1.1 个体个体 谓词演算中把一切讨论对象都称为谓词演算中把一切讨论对象都称为，它们可以是客观世界中的具体，它们可以是客观世界中的具体客体，也可以是抽象的客体，诸如数字、客体，也可以是抽象的客体，诸如数字、符号等。符号等。第二章第二章 谓

34、词演算及其形式系统谓词演算及其形式系统2.1 2.1 个体、谓词和量词个体、谓词和量词2.1.1 2.1.1 个体个体 谓词演算中把讨论对象谓词演算中把讨论对象个体的全体称为个体的全体称为（domain of individuals），），常用字常用字母母D表示，并约定任何表示，并约定任何D都至少含有一个成员都至少含有一个成员。当讨论对象遍及一切客体时，个体域特称为当讨论对象遍及一切客体时，个体域特称为（universe），），用字母用字母U表示。表示。第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.1 2.1 个体、谓词和量词个体、谓词和量词2.1.2 2.1.2 谓词谓词谓词的元

35、数谓词的元数 谓词命名式谓词命名式 谓词填式谓词填式 第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.1 2.1 个体、谓词和量词个体、谓词和量词2.1.2 2.1.2 谓词谓词 通常把谓词所携空位的数目称为谓词的通常把谓词所携空位的数目称为谓词的。含空位的写法有一个明显的缺点，可读性差。因此常用含空位的写法有一个明显的缺点，可读性差。因此常用变元来代替空位，它们被称为变元来代替空位，它们被称为，简称简称。当谓词的空位上填入个体后，便产生一个关于该个体的当谓词的空位上填入个体后，便产生一个关于该个体的语句，这时它被称为语句，这时它被称为。第二章第二章 谓词演算及其形式系统谓词演算及其

36、形式系统2.1 2.1 个体、谓词和量词个体、谓词和量词2.1.3 2.1.3 量词量词（quantifiers）指数量词指数量词“所有所有”和和“有有”，分别用，分别用符号符号（)和和（)来表示。来表示。第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.1 2.1 个体、谓词和量词个体、谓词和量词2.1.3 2.1.3 量词量词约束变元约束变元 自由变元自由变元 辖域辖域 一阶谓词演算一阶谓词演算 第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.1 2.1 个体、谓词和量词个体、谓词和量词2.1.3 2.1.3 量词量词 可以取值代入的变元则称为可以取值代入的变元则称为（f

37、ree variables）。）。不可以取值代入的变元则称为不可以取值代入的变元则称为（free variables）。）。当量词用于一谓词或复合的谓词表达式式，当量词用于一谓词或复合的谓词表达式式，该谓词或复合的谓词表达式称为该谓词或复合的谓词表达式称为（domains of quantifiers）第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.1 2.1 个体、谓词和量词个体、谓词和量词2.1.3 2.1.3 量词量词 当限定量词的指导变元为个体变元当限定量词的指导变元为个体变元（不用命题变元、谓词、函数变元（不用命题变元、谓词、函数变元-分别以命题、谓词、函数为值的变元）分别

38、以命题、谓词、函数为值的变元）时，谓词演算又称为时，谓词演算又称为（first order predicate calculus）。）。第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.1 2.1 个体、谓词和量词个体、谓词和量词2.1.4 2.1.4 谓词公式及语句的形式化谓词公式及语句的形式化 定义定义2.1 以下条款规定的符号串称为以下条款规定的符号串称为（predicate forrmula），），简称简称。谓词填式是公式，命题常元是公式谓词填式是公式，命题常元是公式 （看作零元谓词）。（看作零元谓词）。如果如果A，B是公式，是公式，x为任一变元，为任一变元，那么那么(A)，(

39、AB)，(xA)，(x A)（当使用五个联结词时（当使用五个联结词时 还有还有(AB)，(AB)，(AB)）都是公式。）都是公式。只有有限步使用（只有有限步使用（1），（），（2）条款）条款 所形成的符号串是公式。所形成的符号串是公式。第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.2 2.2 谓词演算永真式谓词演算永真式2.2.1 2.2.1 谓词公式的真值规定谓词公式的真值规定 定义定义2.2给定给定个体个体域域D及公式及公式A中各谓词符号的解释中各谓词符号的解释I，如果如果A中个体变元中个体变元x1,xn分别取值分别取值u1,un时时A真，则称真，则称；当当x1,xn无论取无论

40、取D中怎样的个体中怎样的个体u1,un,A在在u1,un处均真，则称处均真，则称。第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.2 2.2 谓词演算永真式谓词演算永真式2.2.1 2.2.1 谓词公式的真值规定谓词公式的真值规定 定义定义2.3给定个体域给定个体域D，若公式，若公式A在每一解释在每一解释I下均真，下均真，那么称那么称。若公式若公式A对任何个体域对任何个体域D均有均有D上永真，则称上永真，则称A为为，或称，或称A（valid）。）。定义定义2.4公式公式A称为称为的，如果对某一个体的，如果对某一个体域、某一解释和变元域、某一解释和变元的某一取值状况，的某一取值状况，A

41、在此处取值真。在此处取值真。公式公式A不可满足时也不可满足时也称称A为为。第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.2 2.2 谓词演算永真式谓词演算永真式2.2.3 2.2.3 两个原理与两个规则两个原理与两个规则 定义定义2.5设谓词公式设谓词公式A中含自由变元中含自由变元x，设，设t为一个为一个体项，且体项，且t中无自由变元为中无自由变元为A中的约束变元，中的约束变元，那么称那么称t是是的的。第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.2 2.2 谓词演算永真式谓词演算永真式2.2.3 .2.3 两个原理与两个规则两个原理与两个规则 定理定理2.1（）若若A

42、是永真式，那么是永真式，那么对对A中变元可代入的代入实例都中变元可代入的代入实例都是永真是永真式。式。定理定理2.2（）设设A，D为谓词公式，为谓词公式，C为为A的子公式，的子公式，且且CD。若若B为将为将A中子公式中子公式C的某些出现（未必全部）替换为的某些出现（未必全部）替换为D后所得的公式，那么后所得的公式，那么AB。第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.2 2.2 谓词演算永真式谓词演算永真式2.2.3 2.2.3 两个原理与两个规则两个原理与两个规则 定义定义2.6设设A为为联结词联结词，的谓词公式，的谓词公式，A*为将为将A中符号中符号，t，f，,分别换分别换为

43、为，f，t,，后所得的公式，那么后所得的公式，那么称称A*为为A的的。第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.2 2.2 谓词演算永真式谓词演算永真式2.2.3 2.2.3 两个原理与两个规则两个原理与两个规则 定理定理2.3（）若公式若公式A中无自由变元中无自由变元y，那么，那么，xA(x)yA(y),xA(x)yA(y)第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.3 2.3 谓词公式的前束范式谓词公式的前束范式 定义定义2.7公式公式A称为称为公式公式A的的（prenex normal forms），如果），如果AA，且，且A形如形如 Q1x1QnxnB其中

44、其中Q1，Qn为量词为量词 或或 ，B中无量词，中无量词，联结词联结词，B称为称为。当。当B为合取（析取）范式时，为合取（析取）范式时，A称为称为A的的。第二章第二章 谓词演算及其形式系统谓词演算及其形式系统 定理定理2.4（）对对任意任意谓词公式均可作出其前束范式，进而作出其前谓词公式均可作出其前束范式，进而作出其前束合取范式或前束析取范式。束合取范式或前束析取范式。2.3 2.3 谓词公式的前束范式谓词公式的前束范式 第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.4 2.4 一阶谓词演算形式系统一阶谓词演算形式系统 2.4.1 2.4.1 一阶谓词演算形式系统一阶谓词演算形式系

45、统FPCFPC 定义定义2.8设设x1,xn是公式是公式A中的所有自由变元，那么公式中的所有自由变元，那么公式 x1 xnA(或或 x1 xnA(x1,xn)称为称为A的的（generalization clusure）。）。第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.4 2.4 一阶谓词演算形式系统一阶谓词演算形式系统 2.4.1 2.4.1 一阶谓词演算形式系统一阶谓词演算形式系统FPCFPC 定理定理2.5对对任意任意公式公式A，变元，变元x，若，若 A，则，则 x A。定理定理2.6对对任何任何公式集公式集 ，公式，公式A和变元和变元x，x不是不是 中任中任一公式的自由变

46、元，那么，若一公式的自由变元，那么，若 A，则，则 x A。第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.4 2.4 一阶谓词演算形式系统一阶谓词演算形式系统 2.4.1 2.4.1 一阶谓词演算形式系统一阶谓词演算形式系统FPCFPC 定理定理2.7（）设设A，B为为公式，变元公式，变元x是公式是公式A、但不是公式、但不是公式B的自由变元，那么当，的自由变元，那么当，x A(x),A(x)B同时成立时，同时成立时，应有应有 B。定理定理2.6 第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.4 2.4 一阶谓词演算形式系统一阶谓词演算形式系统2.4.2 2.4.2 一阶

47、谓词演算的自然推理系统一阶谓词演算的自然推理系统FNDFND )()/()(可代入对xtxtAxxA)/(xeA)()()(设中自由出现不在前提和未消除的假xxxAxA)/(,)()/()(xtAtxxtAtxxAtA代换为所有表示将中无自由变元 第二章第二章 谓词演算及其形式系统谓词演算及其形式系统2.4 2.4 一阶谓词演算形式系统一阶谓词演算形式系统2.4.3 2.4.3 含等词的一阶谓词演算自然推理系统含等词的一阶谓词演算自然推理系统 定理定理2.9对任意项对任意项t1，t2，t3，有（，有（表示表示FNDE）。）。（a）t1=t2 t2=t1 （b）t1=t2 t2=t3 t1=t3

48、 *第第 三三 章章 消消 解解 原原 理理3.1 斯柯伦标准形斯柯伦标准形3.2 命题演算消解原理命题演算消解原理3.3 谓词演算消解原理谓词演算消解原理*第三章第三章 消消 解解 原原 理理3.1.1 斯柯伦标准形斯柯伦标准形3.1.2 子句集及其可满足性子句集及其可满足性*第三章第三章 消消 解解 原原 理理3.1 3.1 斯柯伦标准形斯柯伦标准形3.3.1 代换及一致化代换及一致化3.3.2 谓词演算消解原理谓词演算消解原理*第三章第三章 消消 解解 原原 理理3.3 3.3 谓词演算消解原理谓词演算消解原理*第三章第三章 消消 解解 原原 理理3.1 3.1 斯柯伦标准形斯柯伦标准形

49、3.1.1 斯柯伦标准形斯柯伦标准形对任意只含自由变元对任意只含自由变元x,y1,yn的公式的公式A(x,y1,yn)，xA(x,y1,yn)可满足，可满足，当且仅当当且仅当A(f(y1,yn),y1,yn)可满足。可满足。这里这里f为一新函数符号；当为一新函数符号；当n=0时，时，f 为为新常元。新常元。定理定理3.1（斯柯伦定理斯柯伦定理）*第三章第三章 消消 解解 原原 理理3.1 3.1 斯柯伦标准形斯柯伦标准形3.1.1 斯柯伦标准形斯柯伦标准形 设公式设公式A的前束范式为的前束范式为B。C是利用是利用 斯柯伦常元和斯柯伦函数消去斯柯伦常元和斯柯伦函数消去B中量词中量词 （称斯柯伦化

50、）后所得的合取范式，那么称（称斯柯伦化）后所得的合取范式，那么称 C为为A的的斯柯伦标准形斯柯伦标准形 （Skolem normal form）。定义定义3.1*第三章第三章 消消 解解 原原 理理3.1 3.1 斯柯伦标准形斯柯伦标准形3.1.2 子句集及其可满足性子句集及其可满足性定义定义3.2 子句集子句集S称为称为可满足可满足的，如果存在一个的，如果存在一个个体域和一种解释，使个体域和一种解释，使S中的每一个子中的每一个子句均为真，或使得句均为真，或使得S中的每一个子句中的每一个子句至少有一个文字为真。否则称至少有一个文字为真。否则称S为为不可满足不可满足的。的。*第三章第三章 消消