第一篇数理逻辑课件.ppt

,第 一 篇 数 理 逻 辑,第 一 篇,数理逻辑（mathematical logic）是用数学的方法来研究人类推理过程的一门数学学科。,又称符号逻辑、现代逻辑。,其显著特征是符号化和形式化，即把逻辑所涉及的“概念、判断、推理”用符号来表示，用公理体系来刻划,并基于符号串形式的演算来描述推理过程的一般规律。,逻辑演算四个分支：公理集合论、证明论、模型论和递归论。,数理逻辑（mathematical logic）又称符号逻,第 一 章 命题演算及其形式系统,第 一 章,1.1 命题与联结词,1.2 重 言 式,1.3 范式,*1.4 命题演算形式系统,第一章 命题演算及其形式系统,1.1 命题与联结词1.2 重 言 式1.3 范,1.1.1 命题,1.1.2 联结词,1.1.3 命题公式及其真值表,1.1.4 语句的形式化,第一章 命题演算及其形式系统,1.1 命题与联结词,1.1.1 命题1.1.2 联结词1.1.3 命题公,1.2.1 重言式概念,1.2.2 逻辑等价式和逻辑蕴涵式,1.2.3 对偶原理,第一章 命题演算及其形式系统,1.2 重 言 式,1.2.1 重言式概念1.2.2 逻辑等价式和逻辑蕴涵式,1.3.1 析取范式和合取范式,1.3.2 主析取范式与主合取范式,1.3.3 联结词的扩充与归约,第一章 命题演算及其形式系统,1.3 范式,1.3.1 析取范式和合取范式1.3.2 主析取范式与主,1.4.1 证明、演绎和推理,1.4.2 命题演算形式系统PC,1.4.3 自然推理系统ND,第一章 命题演算及其形式系统,*1.4 命题演算形式系统,1.4.1 证明、演绎和推理1.4.2 命题演算形式系,第一章 命题演算及其形式系统,1.1 命题与联结词,1.1.1 命题,我们把对确定的对象作出判断的陈述句称作命题（propositions or statements）,当判断正确或符合客观实际时，称该命题真（true），否则称该命题假（false）。,第一章 命题演算及其形式系统 1.1 命题与联结词 1.,第一章 命题演算及其形式系统,1.1 命题与联结词,1.1.1 命题,通常把不含有逻辑联结词的命题称为原子命题或原子（atoms）,把由原子命题和逻辑联结词共同组成的命题称为复合命题（compositive propositions or compound statements）,第一章 命题演算及其形式系统 1.1 命题与联结词 1.,第一章 命题演算及其形式系统,1.1 命题与联结词,1.1.2 联结词,否定词“并非”,合取词“并且”,析取词“或”,蕴涵词“如果，那么”,双向蕴涵词“当且仅当”,第一章 命题演算及其形式系统 1.1 命题与联结词1.1,第一章 命题演算及其形式系统,1.1 命题与联结词,1.1.2 联结词,否定词（negation）“并非”（not），用符号“”表示。,可用表1.1来规定否定词“”的意义:,p读作“并非p”或“非p”。,第一章 命题演算及其形式系统 1.1 命题与联结词1.1,第一章 命题演算及其形式系统,1.1 命题与联结词,1.1.2 联结词,合取词（conjunction）“并且”（and），用符号“”表示。,可用表1.2来规定合取词“”的意义：,pq读作“p并且q”或“p且q”,第一章 命题演算及其形式系统 1.1 命题与联结词1.1,第一章 命题演算及其形式系统,1.1 命题与联结词,1.1.2 联结词,析取词（disjunction）“或”（or）用符号“”表示。,可用表1.3来规定析取词“”的意义：,pq读作“p或者q”、“p或q”。,第一章 命题演算及其形式系统 1.1 命题与联结词1.1,第一章 命题演算及其形式系统,1.1 命题与联结词,1.1.2 联结词,蕴涵词（implication)“如果，那么”（ifthen），用符号“”表示。,可用表1.5来规定该蕴涵词“”的意义：,pq中的p称为蕴涵前件，q称为蕴涵后件。,第一章 命题演算及其形式系统 1.1 命题与联结词1.1,第一章 命题演算及其形式系统,1.1 命题与联结词,1.1.2 联结词,双向蕴涵词(two-way-implication)“当且仅当”（if and only if），用符号“”表示。,可用表1.6来规定该双向蕴涵词“”的意义：,pq读作“p双向蕴涵q”，“p当且仅当q”，“p等价于q”。,第一章 命题演算及其形式系统 1.1 命题与联结词1.1,第一章 命题演算及其形式系统,1.1 命题与联结词,1.1.3 命题公式及其真值表,命题常元,命题公式,指派,弄真与弄假,真值表（truth table）,命题变元,第一章 命题演算及其形式系统 1.1 命题与联结词1.1,第一章 命题演算及其形式系统,1.1 命题与联结词,1.1.3 命题公式及其真值表,我们把表示具体命题及表示常命题的p，q，r，s等与f，t统称为命题常元（proposition constants）。,命题变元（proposition variable）是以“真、假”或“1，0”为取值范围的变元，它未指出符号所表示的具体命题。,第一章 命题演算及其形式系统 1.1 命题与联结词1.1,第一章 命题演算及其形式系统,1.1 命题与联结词,1.1.3 命题公式及其真值表,以下三条款规定了命题公式（proposition formula）的意义：,（1）命题常元和命题变元是命题公式，也称为原子公式或原子。（2）如果A，B是命题公式，那么（A），（AB），（AB），（AB），（AB）也是命题公式。（3）只有有限步引用条款（1），（2）所组成的符号串 是命题公式。,定义1.1,第一章 命题演算及其形式系统 1.1 命题与联结词1.1,第一章 命题演算及其形式系统,1.1 命题与联结词,1.1.3 命题公式及其真值表,对任意给定的命题变元p1,pn的一种取值状况，称为指派或赋值（assignments），用字母，等表示,当A对取值状况 为真时，称指派弄真A或是A的成真赋值，记为(A)=1；反之称指派弄假A或是A的成假赋值，记为(A)=0。,第一章 命题演算及其形式系统 1.1 命题与联结词1.1,第一章 命题演算及其形式系统,1.1 命题与联结词,1.1.3 命题公式及其真值表,对一切可能的指派,公式A的取值可能用下表来描述，这个表称为真指表（truth table）,第一章 命题演算及其形式系统 1.1 命题与联结词1.1,第一章 命题演算及其形式系统,1.1 命题与联结词,1.1.4 语句的形式化,语句形式化主要是以下几个方面：,要准确确定原子命题，并将其形式化。,要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略），否定词的位置要放准确。,必要时可以进行改述，即改变原来的叙述方式，但要保证表达意思一致。,需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略。,要注意语句的形式化未必是唯一的。,第一章 命题演算及其形式系统 1.1 命题与联结词1.1,第一章 命题演算及其形式系统,1.2 重 言 式,1.2.1 重言式概念,定义1.2,重言式,不可满足式,可满足式,第一章 命题演算及其形式系统1.2 重 言 式1.2,第一章 命题演算及其形式系统,1.2 重 言 式,1.2.1 重言式概念,对命题公式A，如果对A中命题变元的一切指派均弄真A，则A称为重言式（tautology），又称永真式.,如果至少有一个指派弄真A，则A称为可满足式（satisfactable formula or contingency）。,第一章 命题演算及其形式系统1.2 重 言 式1.2,第一章 命题演算及其形式系统,1.2 重 言 式,1.2.1 重言式概念,如果对A中命题变元的一切指派均弄假A，则称A为不可满足式或矛盾式（contradiction or absurdity）或永假式。,第一章 命题演算及其形式系统1.2 重 言 式1.2,第一章 命题演算及其形式系统,1.2 重 言 式,1.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 重 言 式,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 重 言 式,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 重 言 式,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 重 言 式,1.2.3 对偶原理,设公式A仅含联结词，A*为将A中符号，t，f分别改换为，f，t后所得的公式，那么称A*为A的对偶（dual）。,定义1.5,第一章 命题演算及其形式系统1.2 重 言 式1.,第一章 命题演算及其形式系统,1.2 重 言 式,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.2 重 言 式1.,第一章 命题演算及其形式系统,1.3 范式,1.3.1 析取范式和合取范式,文字(letters)：指命题常元、变元及它们的否定，前者又称正文字，后者则称负文字。,析取子句(disjunctive clauses)：指文字或若干文字的析取。,合取子句(conjunctive clauses)：指文字或若干文字的合取。,互补文字对(complemental pairs of letters)：指形如L，L（L为文字）的一对字符。,第一章 命题演算及其形式系统1.3 范式1.3.1 析,第一章 命题演算及其形式系统,1.3 范式,1.3.1 析取范式和合取范式,定义1.6 命题公式A称为公式A的析取范式（disjunctive normal form），如果（1）AA（2）A为一合取子句或若干合取子句的析取。,定义1.7 命题公式A称为公式A的合取范式（conjunctive normal form）如果（1）AA（2）A为一析取子句或若干析取子句的合取。,第一章 命题演算及其形式系统1.3 范式1.3.1 析,第一章 命题演算及其形式系统,1.3 范式,1.3.2 主析取范式与主合取范式,定义1.8设A为恰含命题变元p1,pn的公式。公式A,称为A的主析（合）取范式（majordisjunctive（conjunctive）normal form），如果A,是A的析（合）取范式，并且其每个 合（析）取子句中p1,pn均恰出现一次。,第一章 命题演算及其形式系统1.3 范式1.3.2 主,第一章 命题演算及其形式系统,1.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.3,第一章 命题演算及其形式系统,1.3 范式,1.3.3 联结词的扩充与归约,定义1.10当联结词组g1,g2,.,gm可表示所有一元、二元联结词时，称其为完备联结词组（complete group of connectives）。,第一章 命题演算及其形式系统1.3 范式1.3.3,第一章 命题演算及其形式系统,*1.4 命题演算形式系统,1.4.1 证明、演绎和推理,定义1.11 公式序列A1,A2,Am称为Am的一个证明（proof），如果Ai(1 i m)或者是公理，或者由Aj1,Ajk(j1,jki)用推理规则推得。当这样的证明存在时，称Am为系统的定理（theorems），记为*Am,(为所讨论的系统名),或简记为Am。,第一章 命题演算及其形式系统*1.4 命题演算形式系统,第一章 命题演算及其形式系统,*1.4 命题演算形式系统,1.4.1 证明、演绎和推理,定义1.12 设为一公式集合。公式序列A1,A2,Am称为Am的以为前提的演绎（diduction），如果Ai(1im)或者是 中公式，或者是公理，或者由Aj1,Ajk(j1,jki)用推理规则导出。当有这样的演绎时，Am称为 的演绎结果，记为*Am,(为所讨论的系统名)，或简记为Am。称 和 的成员为Am的前提(hypothesis)。,第一章 命题演算及其形式系统*1.4 命题演算形式系统,第一章 命题演算及其形式系统,*1.4 命题演算形式系统,1.4.2 命题演算形式系统PC,定理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 命题演算形式系统PC,定理1.8（完备性，completeness）若公式A永真，则A必为PC的定理；若公式A是公式集 的逻辑结果，那么A必为 的演绎结果。即若 A，那么 PC A.若 A，那么 PC A.,第一章 命题演算及其形式系统*1.4 命题演算形式系统,第一章 命题演算及其形式系统,*1.4 命题演算形式系统,1.4.2 命题演算形式系统PC,定理1.9（演绎定理）对任意公式集 和公式A，B，AB当且仅当 A B（当=时，AB当且仅当A B，或A B）,第一章 命题演算及其形式系统*1.4 命题演算形式系统,第一章 命题演算及其形式系统,*1.4 命题演算形式系统,1.4.2 命题演算形式系统PC,定理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 自然推理系统ND,定理1.12 如果公式A是PC的定理，那么A也必定是ND的定理。即PC A蕴涵ND A。,第一章 命题演算及其形式系统*1.4 命题演算形式系统,