Lecture 1数理逻辑

1、数理逻辑数理逻辑(1)(1)计算机学院计算机学院 姜新文姜新文1380748139213807481392，xinwenjianggfkd.mtnxinwenjianggfkd.mtnQQ: 4712810QQ: 4712810本讲内容本讲内容1.1.课程介绍课程介绍2.2.要求及注意事项要求及注意事项3.3.形式系统形式系统4.P4.P系统介绍系统介绍数理逻辑数理逻辑课程介绍课程介绍逻辑逻辑： 客观事物的规律在人的主观意客观事物的规律在人的主观意识中的反映识中的反映推理推理：就是从一个或几个：就是从一个或几个已知判断已知判断推推导出一个导出一个新的判断新的判断的思维过程。的思维过程。数理逻辑

2、数理逻辑课程介绍课程介绍逻辑学逻辑学：研究思维形式和思维规律的研究思维形式和思维规律的一门科学一门科学。任何推理都有它。任何推理都有它形式形式和和内容内容的两个方面。推理的内容是它的两个方面。推理的内容是它所施用的具体的科学理论的研究对所施用的具体的科学理论的研究对象，而象，而逻辑学研究的是推理的形式，逻辑学研究的是推理的形式， 也就是去除内容后前提判断与结论也就是去除内容后前提判断与结论的关系。的关系。 数理逻辑数理逻辑课程介绍课程介绍形式逻辑形式逻辑：以思维的形式结构及规律：以思维的形式结构及规律进行研究的逻辑学。进行研究的逻辑学。辨证逻辑辨证逻辑：以辨证法认识论来进行研：以辨证法认识论来

3、进行研究的逻辑学。究的逻辑学。数理逻辑数理逻辑课程介绍课程介绍形式逻辑主要从形式逻辑主要从形式结构上研究思维形式结构上研究思维的形式和规律的形式和规律。形式逻辑推理的每。形式逻辑推理的每一个环节都是完全确定的，界限分一个环节都是完全确定的，界限分明的，它用逻辑符号来指称对象，明的，它用逻辑符号来指称对象，有一套严密的逻辑规则，能够进行有一套严密的逻辑规则，能够进行精确的逻辑演算。精确的逻辑演算。数理逻辑数理逻辑课程介绍课程介绍归纳逻辑和演绎逻辑归纳逻辑和演绎逻辑归纳逻辑归纳逻辑研究特殊到一般、特殊到特殊的推理。研究特殊到一般、特殊到特殊的推理。它是一种或然性推理。它是一种或然性推理。例例：美国

4、加州的自然环境与我国南方地区的自：美国加州的自然环境与我国南方地区的自然环境是相似的，然环境是相似的， 我国南方地区适宜种植柑橘，我国南方地区适宜种植柑橘， 所以，美国加州也适宜种植柑橘。所以，美国加州也适宜种植柑橘。 显然，这是从显然，这是从特殊到特殊特殊到特殊的推理，通常叫做的推理，通常叫做类比推理。类比推理。数理逻辑数理逻辑课程介绍课程介绍归纳逻辑研究归纳逻辑研究特殊到一般特殊到一般、特殊到特殊的、特殊到特殊的推理。它是一种或然性推理。推理。它是一种或然性推理。例例：所有的以前发现的绿宝石都是绿的，：所有的以前发现的绿宝石都是绿的， 所以，下一个被发现的绿宝石将是绿所以，下一个被发现的绿

5、宝石将是绿的。的。 当人们把关于过去经验的概括整理起当人们把关于过去经验的概括整理起来以便做出关于即将发生的特定事件来以便做出关于即将发生的特定事件的预见时，他们常常使用这种归纳推的预见时，他们常常使用这种归纳推理。理。数理逻辑数理逻辑课程介绍课程介绍归纳逻辑研究特殊到一般、特殊到特殊的推理。归纳逻辑研究特殊到一般、特殊到特殊的推理。它是一种它是一种或然性或然性推理。推理。例例：这个班上的所有学生都是高智商的，：这个班上的所有学生都是高智商的， 这个班上的所有学生都有强烈的学习热情，这个班上的所有学生都有强烈的学习热情， 这个班上的所有学生学业负担都比较轻，这个班上的所有学生学业负担都比较轻，

6、 这个班上的所有学生都是心理健康的，这个班上的所有学生都是心理健康的， 所以，这个班上的所有学生学习成绩都比所以，这个班上的所有学生学习成绩都比较好。较好。数理逻辑数理逻辑课程介绍课程介绍演绎逻辑演绎逻辑从从一般到特殊一般到特殊的逻辑推理方法，也常的逻辑推理方法，也常被称之谓一种被称之谓一种必然性必然性推理，或保真性推理。推理，或保真性推理。演绎主义者认为归纳不靠谱。（海城到唐山）演绎主义者认为归纳不靠谱。（海城到唐山）归纳主义者反对或贬低演绎逻辑，认为演绎逻归纳主义者反对或贬低演绎逻辑，认为演绎逻辑不是一种科学的方法，其基本理由有两个：辑不是一种科学的方法，其基本理由有两个： 1. 1. 认

7、为演绎逻辑不能给人以新知识。认为演绎逻辑不能给人以新知识。 2. 2. 认为演绎逻辑不能证明其前提的正认为演绎逻辑不能证明其前提的正确性，必然导致先验论。确性，必然导致先验论。数理逻辑数理逻辑课程介绍课程介绍数理逻辑：用数理逻辑：用数学方法和计算的方法来研究数学方法和计算的方法来研究推理的规律推理的规律，又称，又称符号逻辑符号逻辑。是一种。是一种形形式逻辑式逻辑。属于。属于演绎逻辑演绎逻辑。数理逻辑中的数理逻辑中的“数理数理”一词有两层意思：一词有两层意思： 其一是其一是 Leibniz Leibniz 的思想的思想用数学的方用数学的方法研究逻辑；法研究逻辑； 其二是主要研究数学中使用的逻辑。

8、其二是主要研究数学中使用的逻辑。 数理逻辑数理逻辑课程介绍课程介绍数理逻辑的发展：数理逻辑的发展：300年，三个阶段：年，三个阶段：1.17世纪末到世纪末到19世纪末，从莱布尼茨到布尔、世纪末，从莱布尼茨到布尔、德摩根，成果有德摩根，成果有布尔代数和关系逻辑布尔代数和关系逻辑。2.19世纪中叶以后世纪中叶以后60年，奠定自己的理论基础，年，奠定自己的理论基础，创建了特有的新方法，创建了特有的新方法，成为一门学科成为一门学科。成就。成就有四个方面：有四个方面：集合论创建，公理化方法的发集合论创建，公理化方法的发展，逻辑演算的建立，证明论的提出展，逻辑演算的建立，证明论的提出。3.1940年以后发

9、展出年以后发展出5各方面内容各方面内容，并与数学，并与数学其他分支和计算机科学有了广泛的联系。其他分支和计算机科学有了广泛的联系。数理逻辑数理逻辑课程介绍课程介绍数理逻辑的数理逻辑的5 5各方面内容各方面内容 逻辑演算逻辑演算， 递归论，递归论， 公理集合论，公理集合论， 证明论，证明论， 模型论。模型论。数理逻辑数理逻辑课程介绍课程介绍数理逻辑研究内容：我们主要介绍它的两个最基数理逻辑研究内容：我们主要介绍它的两个最基本的也是最重要的组成部分，就是本的也是最重要的组成部分，就是“命题演算命题演算”和和“谓词演算谓词演算”。命题演算命题演算是研究关于命题如何通过一些逻辑连接是研究关于命题如何通

10、过一些逻辑连接词构成更复杂的命题以及逻辑推理的方法。命词构成更复杂的命题以及逻辑推理的方法。命题是指具有具体意义的又能判断它是真还是假题是指具有具体意义的又能判断它是真还是假的句子。的句子。 谓词演算谓词演算也叫做命题涵项演算。在谓词演算里，也叫做命题涵项演算。在谓词演算里，把命题的内部结构分析成具有主词和谓词的逻把命题的内部结构分析成具有主词和谓词的逻辑形式，由命题涵项、逻辑连接词和量词构成辑形式，由命题涵项、逻辑连接词和量词构成命题，然后研究这样的命题之间的逻辑推理关命题，然后研究这样的命题之间的逻辑推理关系。系。 数理逻辑数理逻辑课程介绍课程介绍一句有真假意义的陈述句称为命题。一句有真假

11、意义的陈述句称为命题。例：例： （）（）数理逻辑数理逻辑是计算机专业的核心课是计算机专业的核心课 （）三角形之内角之和等于（）三角形之内角之和等于 （）二进制数（）二进制数 （）凡是国旗都是红色的。（）凡是国旗都是红色的。 （）（）我正在说谎。我正在说谎。 （）（）本命题是假的。本命题是假的。要求和注意事项要求和注意事项反复思考、琢磨、辨析反复思考、琢磨、辨析真正训练计算思维真正训练计算思维形式系统形式系统定义定义称五元偶称五元偶FS=为为形式系统形式系统,其中其中,1.为非空集合为非空集合,称为称为FS的符号表的符号表,其元素称为其元素称为FS的符号。的符号。2.Term*,称为称为FS的项

12、集合的项集合,其元素称为其元素称为FS的的项项。3.Formula*且且FormulaTerm=,称为称为FS的公式集的公式集合合,其元素称为其元素称为FS的的公式公式。此外，有。此外，有Formula的一个的一个子子集集Atom称为称为FS的原子公式集合，其元素称为的原子公式集合，其元素称为FS的原的原子公式。子公式。4.AxiomFormula,称为称为FS的公理集合，其元素称为的公理集合，其元素称为FS的公理。的公理。5.Rule,称为称为FS的推演规则的的推演规则的集合，其元素称为集合，其元素称为FS的推演规则。的推演规则。 2()2nnFormula 形式系统形式系统如果如果r Ru

13、ler Rule及及A A0 0,A,A1 1,A,An n,B Formula (n ,B Formula (n N)N)使得使得A r,B r，称可由推演，称可由推演规则规则r r 以及以及A A0 0,A,A1 1,A,An n重写出重写出B B，简称可由，简称可由A A0 0,A,A1 1,A,An n重写出重写出B B，记为，记为 或者或者01nA ,A ,AB01nA ,A ,ABr形式系统形式系统 ,Term,Formula ,Term,Formula为为FSFS的语言部分，的语言部分，Axiom Axiom 和和 Rule Rule为为FSFS的推演部分的推演部分Term,Fo

14、rmula,Axiom,Term,Formula,Axiom,和和RuleRule都可以是空都可以是空集集当当Term=Axiom=Rule= Term=Axiom=Rule= ，FSFS仅仅是一个仅仅是一个语言生成系统语言生成系统FSFS本身使用的语言称为本身使用的语言称为FSFS的对象语言的对象语言研究研究FSFS还要使用到元语言还要使用到元语言形式系统形式系统通常还要对通常还要对FSFS加以限制，使得加以限制，使得FSFS推演能够推演能够机械的实现机械的实现 a. a. 为有穷集或者可数集为有穷集或者可数集 b. Term, Formula, Atom, Axiom, b. Term,

15、Formula, Atom, Axiom, RuleRule都是递归的，即成员关系是可判定的都是递归的，即成员关系是可判定的初等数论形式系统初等数论形式系统FSENFSEN1.=0,2.Term=0,0,0,3.Formula=t1t2t1,t2Term=Atom4.Axiom=005.Rule=r，其中，其中，r=t1,t2Term初等代数中的群论形式系统初等代数中的群论形式系统FSGFSG1.=e,*,-1,(,),X,其中，其中，X为集合且为集合且Xe,*,-1,(,),=2.Term=，其中，其中T0=XeTi+1=(t-1),(t1*t2)t,t1,t2Tii=0,1,.3.Form

16、ula=t1t2t1,t2Term=Atom4.Axiom=aaaX eett,t-1*te,(t1*t2)*t3t1*(t2*t3)t1,t2,t3Term0nnT初等代数中的群论形式系统初等代数中的群论形式系统FSGFSG5.Rule=r1,r2,r3,r4，其中其中，r1=t1,t2Termr2=t1,t2Termr3=t1,t2,t3Termr4=t1,t2,t3,t4Term形式系统形式系统（可证可证）定义）定义1.2设设AFormula，若有，若有A0,A1,A2,AmFormula满足：满足：Am=A当当0jm时，以下两个条件至少一个成立：时，以下两个条件至少一个成立：1.AjA

17、xiom2.有有rRule以及以及j0,j1,jn(nN,0j0,j1,jnj)使得使得r形式系统形式系统就称就称A A为为FSFS的一个定理，或者称的一个定理，或者称A A为可为可证的证的，记为，记为FSFSA A，并称，并称A A0 0,A,A1 1,A,A2 2,A,Am m 为为A A的一个证明。的一个证明。 FSFSA A在不引起混淆时简写为在不引起混淆时简写为A A。形式系统形式系统（从前提出发可证从前提出发可证）定义定义 设设A FormulaA Formula， Formula Formula，若有若有A A0 0,A,A1 1,A,A2 2,A,Am m Formula Fo

18、rmula 满满足：足：A Am m=A=A当当0jm0jm时，以下三个条件至少一时，以下三个条件至少一个成立：个成立： 1. A1. Aj j 2. A 2. Aj j Axiom Axiom 形式系统形式系统 3. 3. 有有r Ruler Rule以及以及j j0 0,j,j1 1,j,jn n (n N, (n N, 0j0j0 0,j,j1 1,j,jn nj )j )使得使得 A r r就称就称A A由由可证的可证的，记为，记为FSFSA A，并称，并称A A0 0,A,A1 1,A,A2 2,A,Am m 为为A A的从的从出发一个证明。出发一个证明。 FSFSA A在不引起混淆

19、时简写为在不引起混淆时简写为AA。形式系统形式系统定义定义Th(FS)=AFormulaFSA不引起混淆时，不引起混淆时，Th(FS)=Th()显然，显然，若若为空，为空，Th(FS)=Th(FS)形式系统形式系统若干性质若干性质性质性质1 1AxiomTh(FS)Th()性质性质2 2Th()性质性质3 3Th()=Th(FS)性质性质4 4Th(Th()=Th()形式系统形式系统定义定义设设FSi=(i=1,2)为形式系统。若为形式系统。若FS1和和FS2满足：满足：12,Term1Term2,Formula1Formula2,Axiom1Th(FS2)且且Rule1Rule2，就称，就称

20、FS2为为FS1的一个的一个扩张扩张，记为，记为FS1FS2。当还有。当还有FS1FS2时，又记为时，又记为FS1FS2 P P 系统、系统、P P 的定理及导出规则的定理及导出规则1.1.P P 的的符号表符号表 通用符号通用符号 命题联接词：，命题联接词：， 括号：（，）括号：（，） 特殊符号特殊符号 可数个命题变元：可数个命题变元：p p，q q，r r，p pi i，q qi i，r ri i，（i i0 0，1 1，）2.2.P P 的的项集项集TermTerm，即，即P P 无项无项命题逻辑命题逻辑3. P P 的的公式集公式集Formula Formula * *为满为满足以下条

21、件的集合足以下条件的集合F F * *的最的最小集合：小集合：若若pp为命题变元，则为命题变元，则p Fp F；若若AFAF，则，则AFAF若若A A，BFBF，则（，则（ABAB）F F命题逻辑命题逻辑 定理定理2.1.12.1.1 （公式结构归纳法公式结构归纳法）若）若F FormulaF Formula满足以下条件：满足以下条件： 若若pp为命题变元，则为命题变元，则pFpF； 若若AFAF，则，则AFAF； 若若A A，BFBF，则（，则（ABAB）F F则则 F F FormulaFormula 命题逻辑命题逻辑证明证明： 由由F F 也满足产生公式的条件也满足产生公式的条件)及及F

22、ormulaFormula的最小性，知的最小性，知Formula F Formula F ，所以再由，所以再由题设题设F FormulaF Formula即得即得F = FormulaF = Formula一种证明方法一种证明方法： 根据上面证明的公式结构归纳法，要想证明根据上面证明的公式结构归纳法，要想证明FormulaFormula中的每个公式都具有某种性质中的每个公式都具有某种性质时，可时，可先令先令 F F =A=AFormula Formula A A具有性质具有性质 然后再验证然后再验证F F满足定理满足定理2.1.12.1.1中的条件中的条件) ) ) )即可。即可。 命题逻辑命

23、题逻辑派生命题联结词：派生命题联结词： ：（：（ABAB）代表（）代表（AAB B） ：（：（A BA B）代表（）代表（ABAB） ：（：（ABAB）代表）代表 （A BA B）（B AB A）命题逻辑命题逻辑符号，符号， 和和称为命题联称为命题联结词，其直观意义分别为：结词，其直观意义分别为： A A 意指意指 非非A A（ABAB） 意指意指 A A或或B B（ABAB） 意指意指 A A且且B B（A BA B） 意指意指 A A蕴含蕴含B B（ABAB） 意指意指 A A当且仅当当且仅当B B命题逻辑命题逻辑（pq）r）（p（qr）表示表示（【（pq）（pq）】r）（【（pq）（pq

24、）】r）（p(qr)(qr)）（p（qr）（qr）命题逻辑命题逻辑约定：约定：公式最外层括号可以省略；公式最外层括号可以省略；同一命题联结词的多次出现按从左到右的同一命题联结词的多次出现按从左到右的顺序依次处理；顺序依次处理；不同的命题联结词按，不同的命题联结词按， ，的优先次序处理的优先次序处理 用用“”代表一个左括号，而代表一个左括号，而与此与此“左括左括号号”相匹配的右括号，在不改变已有括号相匹配的右括号，在不改变已有括号匹配关系的条件下，要尽可能地远匹配关系的条件下，要尽可能地远；命题逻辑命题逻辑p q p q r s r r s r P (P ( r r q q r s) p r s

25、) p ASAS3 3:A B :A B CA BCCA BCASAS3 3: (A B) : (A B) ( (CA) (BC) ( (CA) (BC) 命题逻辑命题逻辑4.P P 的的公理集公理集AxiomAS1AS2AS3，其中其中AS1:AAAAS2:ABAA，B，CFormulaAS3:ABCABC亦即亦即AS1AAA|AFormulaAS2ABA|A，BFormulaAS3ABCABC|A，B，CFormula 命题逻辑命题逻辑5. P 5. P 的的推演规则集推演规则集RuleRuleMPMP，其中，其中 ，或者说，或者说“若若A A且且A BA B，则则B”B”。这里，。这里，

26、A A，BFormulaBFormula亦即亦即 M PM P A | AB | A ，BFormula BFormula 通 常 ， 把通 常 ， 把 M PM P 称 为称 为 假 言 推 理假 言 推 理 （ m o d u s m o d u s ponensponens）BBAAMP ，:命题逻辑命题逻辑综合以上所述，我们获得了一个命题综合以上所述，我们获得了一个命题逻辑形式系统如下：逻辑形式系统如下：P PRule MP命题逻辑命题逻辑代入运算及其性质代入运算及其性质 定义定义2.1.1 2.1.1 如果函数如果函数：* * *满足满足以下条件：以下条件： i i）()()； （表

27、示空符号表示空符号串）串） iiii）若若xx，则，则(x)(x)； iii)iii)若若X X，YY* *，则，则(XY)(XY)(X)(Y)(X)(Y)就称就称为一个为一个代入代入。命题逻辑命题逻辑 定义定义2.1.2 2.1.2 设设为一个为一个代入代入。i i）若若x|(x)xx|(x)x为有穷集，则称为有穷集，则称为一个为一个有穷代入有穷代入。iiii）若）若满足以下条件：满足以下条件： ( () )，()()，(（）（, , 且且（）) )就称就称为一个为一个变元代入变元代入。命题逻辑命题逻辑iii） 若有命题变元若有命题变元p p1 1，p pn n及公式及公式A A1 1，A

28、An nFormulaFormula使使 则把则把记为记为 ppxxni1pxA)x(niii，若且若n21n21PPPAAAS，x命题逻辑命题逻辑定义函数定义函数VarVar：FormulaFormula2 2如下：如下：若若pp为命题变元为命题变元, ,则则Var(p)=pVar(p)=p；若若AFormula,AFormula,则则Var(Var(A)=Var(A);A)=Var(A);若若A A，BFormulaBFormula，则，则Var(AB)= Var(AB)= Var(A) Var(B)Var(A) Var(B)命题逻辑命题逻辑 定义定义2.1.3 2.1.3 设设AForm

29、ulaAFormula，且，且pp为命题变元。若为命题变元。若pVar(A)pVar(A)，则称，则称p p在在A A中出现中出现，否则称，否则称p p不在不在A A中出现中出现。 导出规则导出规则派生规则派生规则（）：若）：若A A ，则，则 A A派生规则派生规则（+ +）：若）：若 1 1AA且且 1 1 2 2，则，则 2 2AA派生规则派生规则（ ）：若）：若 1 1AA且且 2 2A BA B， 1 1 且且 2 2 ，则，则 B BMP 导出规则导出规则(代入代入)代代入入规规则则 sub：设设A 且且 A1，AnFormula若若命命题题变变元元 p p1 1，p pn n均均

30、不不在在 的的公公式式中中出出现现，则则n21n21PPPAAAS，A A 导出规则导出规则证证明明： 我我们们把把n21n21PPPAAAS，记记为为因因为为A，所所以以有有从从出出发发的的 A A 之之证证明明存存在在，设设此此证证明明为为 C0，Cm （CmA） 要要证证明明( (A A) )， 显显然然只只须须用用关关于于 j j( (0 0j jm m) )的的第第二二归归纳纳法法证证明明 ( (C Cj j) ) j j0 0，1 1，m m 当当 0 0j jm m 时时，C Cj j只只有有以以下下三三种种可可能能： 导出规则导出规则i）C Cj j 由于由于 p p1 1，p

31、 pn n均不在均不在 C Cj j中出现，所以中出现，所以(C Cj j)=C)=Cj j，从而得，从而得(C Cj j) ) ii）C Cj j为公理为公理 这里这里(C Cj j) )显然为公理，因此有显然为公理，因此有(C(Cj j) )，从而由（从而由（+）得）得(C Cj j) ) iii）有有 i i， k,0k,0i i， k kj j, ,使使 C Ck k为为 C Ci iC Cj j 根据归纳假设及根据归纳假设及 i i，k kjj 知道，知道，(C Ci i) )且且(C Ck k) )，即，即， 导出规则导出规则(C Ci i) )( (C Cj j) )从从而而由由

32、MP得得(C Cj j) ) 导出规则（导出规则（Dr1,1,2,3,4,5,6）派派生生规规则则 DR1： 若若1AB，2CA，1 且且2 ，则则BC 10 AA 20 AA 30 AA 40 AA 50 AA 60 ABBA There are three suspects for a murder. Admas, Brown, and Clark. Admas says “I did not do it.The victim was an old acquaintance of Browns. But Clark hated him.” Brown states “I did not d

33、o it. I did not even know the guy. Besides I was out of town all that week.” Clark says “I did not do it. I saw both Admas and Brown downtown with the victim that day; one of them must have done it.” Assume that the two innocent men are telling truth, but that the guilty man might not be. Who did it?导出规则导出规则酿酒坛