第一篇数理逻辑课件.ppt

1、 第第 一一 篇篇 数数 理理 逻逻 辑辑（mathematical logic）是用数学的方法来研究人类推理过程的一门数学学科。是用数学的方法来研究人类推理过程的一门数学学科。又称又称符号逻辑、现代逻辑符号逻辑、现代逻辑。其显著特征是符号化和形式化，其显著特征是符号化和形式化，即把逻辑所涉及的即把逻辑所涉及的“概念、判断、推理概念、判断、推理”用符号来表用符号来表示，用公理体系来刻划示，用公理体系来刻划,并基于符号串形式的演算来描并基于符号串形式的演算来描述推述推理过程的一般规律。理过程的一般规律。逻辑演算四个分支：逻辑演算四个分支：公理集合论、证明论、模型论和递归论。公理集合论、证明论、模

2、型论和递归论。第第 一一 章章 命题演算及其形式系统命题演算及其形式系统 1.1 命题与联结词命题与联结词1.2 重重 言言 式式1.3 范式范式*1.4 命题演算形式系统命题演算形式系统第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1.1 命题命题1.1.2 联结词联结词1.1.3 命题公式及其真值表命题公式及其真值表1.1.4 语句的形式化语句的形式化 第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.2.1 重言式概念重言式概念1.2.2 逻辑等价式和逻辑蕴涵式逻辑等价式和逻辑蕴涵式1.2.3 对偶原理对偶原理第一章第一章

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 第一章第一章 命题演算及其形式系统命题演算及其形式系统*1.4 1.4 命题演算形式系统命题演算形式系统第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.

4、1 1.1 命题与联结词命题与联结词 1.1.1 1.1.1 命题命题 我们把对确定我们把对确定的对象作出判断的陈述句的对象作出判断的陈述句称作称作（propositions or statements）当判断正确或符合客观实际时，当判断正确或符合客观实际时，称该命题称该命题（true），），否则称该命题否则称该命题（false）。）。第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词 1.1.1 1.1.1 命题命题 通常把不含有逻辑联结词的命题通常把不含有逻辑联结词的命题称为称为或或（atoms）把由原子命题和逻辑联结词共同组成的把由原子命题和

5、逻辑联结词共同组成的命题称为命题称为（compositive propositions or compound statements）第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.2 1.1.2 联结词联结词否定词否定词“并非并非”合取词合取词“并且并且”析取词析取词“或或”蕴涵词蕴涵词“如果如果，那么，那么”双向蕴涵词双向蕴涵词“当且仅当当且仅当”第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.2 1.1.2 联结词联结词词（词（negation）“并非并非”（not ），），用

6、符号用符号“”表示。表示。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 p q 0 0 1 1 0 1 0 1 0 0 0 1pq读作读作“p并且并且q”或或“p且且q”第一章第一章 命题演算及其形式系统命题演算及其形式系统

7、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 联结词联结词 词（词（implication)“如果如果，那么，那么”（ifthen），用符号），用符号“”表示。表示。可用表可用表1.5来规定该蕴涵词来规定

8、该蕴涵词“”的意义：的意义：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来规定该双向蕴涵词来规定该双向蕴涵词“”的意义：的意义：p q p q 0 0 1 1 0 1 0 1 1 0 0 1pq读读作作“p双向蕴涵双向蕴涵q”，“p当且仅当当且仅当q”，“p等价

9、于等价于q”。第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.3 1.1.3 命题公式及其真值表命题公式及其真值表命题常元命题常元 命题公式命题公式 指派指派 弄真与弄假弄真与弄假真值表（真值表（truth table）命题变元命题变元第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.3 1.1.3 命题公式及其真值表命题公式及其真值表 我们把表示具体命题及表示常命我们把表示具体命题及表示常命题的题的p，q，r，s等与等与f，t统称为统称为（proposition constants）

10、。）。（proposition variable）是以是以“真、假真、假”或或“1，0”为取值范围的变元，为取值范围的变元，它未指出符号所表示的具体命题它未指出符号所表示的具体命题。第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.3 1.1.3 命题公式及其真值表命题公式及其真值表 以下三条款规定了以下三条款规定了（proposition formula）的意义：的意义：命题常元和命题变元是命题公式，也称为原子公式或原子。命题常元和命题变元是命题公式，也称为原子公式或原子。如果如果A，B是命题公式，那么（是命题公式，那么（A），（），（A

11、B），），（AB），（），（AB），（），（AB）也是命题公式。）也是命题公式。只有有限步引用条款（只有有限步引用条款（1），（），（2）所组成的符号串）所组成的符号串 是命题公式。是命题公式。定义定义1.1第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.3 1.1.3 命题公式及其真值表命题公式及其真值表 对任意给定的命题变元对任意给定的命题变元p1,pn的一种取值的一种取值状况，称为状况，称为或或（assignments），用字母用字母，等表示等表示 当当A对取值状况对取值状况 为真时，称指派为真时，称指派 A或或 是是A的成真赋值，

12、记为的成真赋值，记为(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(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 111110001000

13、01110第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.4 1.1.4 语句的形式化语句的形式化 语句形式化语句形式化主要是以下几个方面：主要是以下几个方面：要准确确定原子命题，并将其形式化。要准确确定原子命题，并将其形式化。要选用恰当的联结词，尤其要善于识别自然语言中的要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略），否定词的位置要放准确。联结词（有时它们被省略），否定词的位置要放准确。必要必要时可以进行改述，即改变原来的叙述方式，时可以进行改述，即改变原来的叙述方式，但要保证表达意思一致但要保证表达意思一致。需

14、要的括号不能省略，而可以省略的括号，需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略。在需要提高公式可读性时亦可不省略。要注意语句的形式化未必是唯一的。要注意语句的形式化未必是唯一的。第一章第一章 命题演算及其形式系统命题演算及其形式系统1.2 1.2 重重 言言 式式1.2.1 1.2.1 重言式概念重言式概念定义定义1.2重言式重言式 不可满足式不可满足式 可满足式可满足式 第一章第一章 命题演算及其形式系统命题演算及其形式系统1.2 1.2 重重 言言 式式1.2.1 1.2.1 重言式概念重言式概念 对命题公式对命题公式A，如果对，如果对A中命题变元的一切指派均中

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

16、式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第一章第一章 命题演算及其形式系统命题演算及其形式系统1.2 1.2 重重 言言 式式1.2.2 1.2.2 逻辑等价式和逻辑蕴涵式逻辑等价式和逻辑蕴涵式性质：

17、性质：定理定理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为永真式，为永真式，p为为A中命题变元，中命题变元，A(B/p)表示将表示将A中中p的的出现出现代换为公式代换为公式B后后所得的命题公式（称为所得的命题公式（称

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

19、f 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 重重 言言 式式1.2.3 1.2.3 对偶原理对偶原理 定理定理1.4 设公式设公式A中仅含命题变元中仅含命题变元p1,pn，及联结词，及联结词，那么，那么 AA*(

20、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)：指命题常元、变元及它们的否定，：指命题常元、变元及它们的否定，前者又称前者又称，后者则称，后者则称。(disjunctive clauses)：指文字或若干文字：指文字或若干文

21、字的析取。的析取。(conjunctive clauses)：指文字或若干文字：指文字或若干文字的合取。的合取。(complemental pairs of letters)：指形如指形如L，L（L为文字）的一对字符。为文字）的一对字符。第一章第一章 命题演算及其形式系统命题演算及其形式系统1.3 1.3 范式范式1.3.1 1.3.1 析取范式和合取范式析取范式和合取范式 定义定义1.6 命题公式命题公式A称为公式称为公式A的的（disjunctive normal form），如果，如果 AA A为一合取子句或若干合取子句的析取为一合取子句或若干合取子句的析取。定义定义1.7 命题公式命题

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

23、）取子句中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 1.3 范式范式1.3.3 1.3.3 联结词的扩充与归约联结词的扩充与归约 定义定义1.10当联结词组当联结词组g1,g2,.,gm可表示所有可表示所有

24、一元、二元联结词时，称其为一元、二元联结词时，称其为（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,Ajk(j1,jk i)用推理规则推得。当这样的证明存在时，用推理规则推得。当这样的证明存在时，称称Am为系统的为系统的（theorems），），记为记为

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

26、*Am,(为所讨论的系统名为所讨论的系统名)，或简记为，或简记为 Am。称称 和和 的成员为的成员为Am的的(hypothesis)。第一章第一章 命题演算及其形式系统命题演算及其形式系统*1.4 1.4 命题演算形式系统命题演算形式系统1.4.2 1.4.2 命题演算形式系统命题演算形式系统PCPC定理定理1.6（，sondness）若公式若公式A是系统是系统PC的定理，则的定理，则A为永真式。为永真式。若若A是公式集是公式集 的演绎结果，那么的演绎结果，那么A是是 的逻辑结的逻辑结果。即果。即 若若PC A，则，则 A.若若 PC A，则，则 A.定理定理1.7 PC是一致的，即没有公式是

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

28、算形式系统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，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。