第一篇数理逻辑课件

第第 一一 篇篇 数数 理理 逻逻 辑辑数理逻辑数理逻辑（mathematical logic）是用数学的方法来研究人类推理过程的一门数学学科。是用数学的方法来研究人类推理过程的一门数学学科。又称又称符号逻辑、现代逻辑符号逻辑、现代逻辑。其显著特征是符号化和形式化，其显著特征是符号化和形式化，即把逻辑所涉及的即把逻辑所涉及的“概念、判断、推理概念、判断、推理”用符号来表示，用符号来表示，用公理体系来刻划用公理体系来刻划,并基于符号串形式的演算来描述推并基于符号串形式的演算来描述推理过程的一般规律。理过程的一般规律。逻辑演算四个分支：逻辑演算四个分支：公理集合论、证明论、模型论和递归论。公理集合论、证明论、模型论和递归论。第第 一一 章章 命题演算及其形式系统命题演算及其形式系统 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 对偶原理对偶原理第一章第一章 命题演算及其形式系统命题演算及其形式系统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.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）把由原子命题和逻辑联结词共同组成的把由原子命题和逻辑联结词共同组成的命题称为命题称为复合命题复合命题（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 ），），用符号用符号“”表示。表示。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”第一章第一章 命题演算及其形式系统命题演算及其形式系统 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来规定该蕴涵词来规定该蕴涵词“”的意义：的意义：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等价于等价于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）。）。命题变元命题变元（proposition variable）是以是以“真、假真、假”或或“1，0”为取值范围的变元，为取值范围的变元，它未指出符号所表示的具体命题它未指出符号所表示的具体命题。第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.3 1.1.3 命题公式及其真值表命题公式及其真值表 以下三条款规定了以下三条款规定了命题公式命题公式（proposition formula）的意义：的意义：（1 1）命题常元和命题变元是命题公式，也称为原子公式或原子。命题常元和命题变元是命题公式，也称为原子公式或原子。（2 2）如果如果A，B是命题公式，那么（是命题公式，那么（A），（），（AB），），（AB），（），（AB），（），（AB）也是命题公式。也是命题公式。（3 3）只有有限步引用条款（只有有限步引用条款（1），（），（2）所组成的符号串）所组成的符号串 是命题公式。是命题公式。定义定义1.1第一章第一章 命题演算及其形式系统命题演算及其形式系统 1.1 1.1 命题与联结词命题与联结词1.1.3 1.1.3 命题公式及其真值表命题公式及其真值表 对任意给定的命题变元对任意给定的命题变元p1,pn的一种取值的一种取值状况，称为状况，称为指派指派或或赋值赋值（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(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 语句的形式化语句的形式化 语句形式化语句形式化主要是以下几个方面：主要是以下几个方面：要准确确定原子命题，并将其形式化。要准确确定原子命题，并将其形式化。要选用恰当的联结词，尤其要善于识别自然语言中的要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略），否定词的位置要放准确。联结词（有时它们被省略），否定词的位置要放准确。必要必要时可以进行改述，即改变原来的叙述方式，时可以进行改述，即改变原来的叙述方式，但要保证表达意思一致但要保证表达意思一致。需要的括号不能省略，而可以省略的括号，需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略。在需要提高公式可读性时亦可不省略。要注意语句的形式化未必是唯一的。要注意语句的形式化未必是唯一的。第一章第一章 命题演算及其形式系统命题演算及其形式系统1.2 1.2 重重 言言 式式1.2.1 1.2.1 重言式概念重言式概念定义定义1.2重言式重言式 不可满足式不可满足式 可满足式可满足式 第一章第一章 命题演算及其形式系统命题演算及其形式系统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，则称则称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第一章第一章 命题演算及其形式系统命题演算及其形式系统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为永真式，为永真式，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的一部分，且自身为一公式），的一部分，且自身为一公式），且且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 重重 言言 式式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)：指命题常元、变元及它们的否定，指命题常元、变元及它们的否定，前者又称前者又称正文字正文字，后者则称，后者则称负文字负文字。析取子句析取子句(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的的析取范式析取范式（disjunctive normal form），如果如果 （1 1）AA （2 2）A为一合取子句或若干合取子句的析取为一合取子句或若干合取子句的析取。定义定义1.7 命题公式命题公式A称为公式称为公式A的的合取范式合取范式（conjunctive normal form）如果如果 （1 1）AA （2 2）A为一析取子句或若干析取子句的合取。为一析取子句或若干析取子句的合取。第一章第一章 命题演算及其形式系统命题演算及其形式系统1.3 1.3 范式范式1.3.2 1.3.2 主析取范式与主合取范式主析取范式与主合取范式 定义定义1.8设设A为恰含命题变元为恰含命题变元p1,pn的公式。的公式。公式公式A,称为称为A的的主析（合）取范式主析（合）取范式（majordisjunctive（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 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,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)或者是或者是 中公式，或者是公理，或者由中公式，或者是公理，或者由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是公式集是公式集 的演绎结果，那么的演绎结果，那么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必为必为 的演绎结果。即的演绎结果。即若若 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，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。