数理逻辑发展教案

第一讲前言一、课程内容·数理逻辑：是计算机科学的基础，应娴熟掌握将现实生活中的条件化成逻辑公式，并能做适合的推理，这对程序设计等课程是极实用途的。·会合论：数学的基础，对于学习程序设计、数据结构、编译原理等几乎全部计算机专业课程和数学课程都很实用途。娴熟掌握相关会合、函数、关系等基本看法。·代数结构：对于抽象数据种类、形式语义的研究很实用途。培育数学思想，将以前学过的知识系统化、形式化和抽象化。娴熟掌握相关代数系统的基本看法，以及群、环、域等代数结构的基本知识。·图论：对于解决很多实质问题很实用途，对于学习数据结构、编译原理课程也很有帮助。要求掌握相关图、树的基本看法，以及如何将图论用于实质问题的解决，并培育其使用数学工具成立模型的思想方式。·授课时间为两个学期，第一学期解说数理逻辑与会合论，第二学期解说代数结构和图论。考试内容限于书中的内容和难度，但授课内容不限于书中的内容和难度。二、数理逻辑发展史目的·认识相关的背景，加深对计算机学科的全面认识，特别是理论方面的认识，而不限于将计算机当作是一门技术或工程性的学科。·经过重要的历史事件，认识计算机科学中的一些基本思想方式和一些基本问题。2.数理逻辑的发展先期·前史时期——古典形式逻辑时期：亚里斯多德的直言三段论理论·始创时期——逻辑代数时期（17世纪末）·资本主义生产力大发展，自然科学获得了长足的进步，数学在认识自然、发展技术方面起到了相当重要的作用。·人们希望使用数学的方法来研究思想，把思想过程变换为数学的计算。·莱布尼兹(Leibniz,1646~1716)完美三段论，提出了成立数理逻辑或许说理性演算的思想：·提出将推理的正确性化归于计算，这类演算能令人们的推理不依靠于对推理过程中的命题的含义内容的思虑，将推理的规则变为演算的规则。·使用一种符号语言来取代自然语言对演算进行描绘，将符号的形式和其含义分开。使得演算从很大程度上取决与符号的组合规律，而与其含义没关。·布尔(G.Boole,1815~1864)代数：将相关数学运算的研究的代数系统推行到逻辑领域，布尔代数既是一种代数系统，也是一种逻辑演算。3.数理逻辑的奠定时期·弗雷格(G.Frege,1848~1925)：《看法语言——一种按算术的公式语言构成的纯思想公式语言》版标记着数理逻辑的基础部分——命题演算和谓词演算的正式成立。

(1879)的出·皮亚诺

(GiuseppePeano,1858~1932)

：《用一种新的方法陈说的算术原理》

(1889)提出了自然数算术的一个公义系统。·罗素(BertrandRussell,1872~1970)：《数学原理》(与怀特黑合著，1910,1912,1913)从命题演算和谓词演算开始，而后经过一元和二元命题函项定义了类和关系的看法，成立了抽象的类演算和关系演算。由此出发，在类型论的基础上用连续定义和证明的方式引出了数学（主假如算术）中的主要看法和定理。·逻辑演算的发展：甘岑(G.Gentzen)的自然推理系统(NaturalDeductionSystem)，逻辑演算的元理论：公义的独立性、一致性、完好性等。·各种各种的非经典逻辑的发展：路易斯(Lewis,1883~1964)的模态逻辑，实质蕴涵怪论和严格蕴涵、相关逻辑等，卢卡西维茨的多值逻辑等。会合论的发展·对待无量会合的两种看法：实无量与潜无量·康托尔(G.Cantor,1845~1918)：以实无量的思想为指导，成立了朴实会合论·外延原则（会合由它的元素决定）和归纳原则（每一性质产生一会合）。·可数集和不行数集，确立无量会合的实质在于会合自己能与其子集一一对应。能与正整数会合对应的会合是可数的，不然是不行数的。证了然有理数集是可数的，使用对角线法证了然实数会合是不行数的。·超穷基数和超穷序数·朴实会合论的悖论：罗素悖论·公义会合论的成立：ZFC系统第三次数学危机与逻辑主义、直觉主义与形式主义·会合论的悖论使得人们感觉数学产生了第三次危机，提出了数学的基础究竟是什么这样的问题。·罗素等的逻辑主义：数学的基础是逻辑，倡议全部数学可从逻辑符号推出，《数学原理》一书是他们这一思想的表现。为解决悖论产生了逻辑种类论。·布劳维尔(Brouwer,1881~1966)的直觉主义：数学是心灵的结构，只认可同结构的数学，重申结构的能行性，与计算机科学有重要的联系。坚持潜无量，重申排中律不可以用于无量会合。海丁(Heyting)的直觉主义逻辑。·希尔伯特(D.Hilbert)的形式主义：公义化方法与形式化方法，元数学和证明论，倡议将逻辑演算和数学证明自己形式化，把用一般的语言传达的内容上的数学科学变为用数学符号和逻辑符号按必定法例摆列的一堆公式。为了除去悖论，要数学成立在公义化基础上，将各门数学形式化，构成形式系统，并证明其一致性，这是希尔伯特的数学大纲。数理逻辑的发展早期·哥德尔(Godel,1906~1978)不完好性定理：一个足够强盛的形式系统，假如是一致的则不是完好的，即有的判断在此中是不行证的，既不可以判定其为假，也不可以证明其为真。·各种计算模型：哥德尔的递归函数理论，邱吉尔的演算，图灵机模型·这些计算模型是计算机科学的理论基础，是计算机的理论模型。三、预备知识1.会合的基本看法·会合(set)：会合是数学中最基本的看法之一，不可以以更简单的看法来定义(define)，只好给出它的描绘(description)。一些对象的整体就称为一个会合，这个整体的每个对象称为该会合的一个元素(member或element)。·用大写字母A,B,C等表示会合，用小写字母a,b,c等表示会合的元素aA表示：a是会合A的元素，或说a属于会合AaA表示：a不是会合A的元素，或说a不属于会合A会合中的元素是无序的，不重复的。往常使用两种方法来给出一个会合：·列元素法：列出某会合的全部元素，如：·A={0,1,2,3,4,5,6,7,8,9}表示全部小于10的自然数所构成的会合·B={a,b,,z}表示全部小写英文字母所构成的会合·性质归纳法：使用某个性质来归纳会合中的元素，如：A={n|n是小于10的自然数}C={n|n是质数}表示全部质数所构成的会合·会合由它的元素所决定，换句话说，两个会合A和B相等，记为A=B，假如A和B拥有相同的元素，即a属于会合A当且仅当a属于会合B。·子集(subset)：说会合A是会合B的子集，记为AB，假如a属于会合A则a也属于会合B。所以A=B当且仅当AB且BA。说会合A是会合B的真子集(propersubset)，假如AB且A不等于B(AB)。·空集(emptyset)：商定存在一个没有任何元素的会合，称为空集，记为，有时也用{}来表示。按子集的定义，空集是任何会合的子集(为何？)。·幂集(powerset)：会合A的幂集，记为P(A)，是A的全部子集所构成的会合，即：·P(A)={B|BA}·比如，A={0,1}，则P(A)={{},{0},{1},{0,1}}·明显，对任意会合A，有P(A)和AP(A)·补集(complementset)：会合A的补集，记为A，是那些不属于会合A的元素所构成的会合，即A={x|xA}。往常来说，是在存在一个全集U的状况下议论会合的补集。全集U是所议论的问题域中全部元素所构成的会合。·会合的并(union)：会合A和B的并AB定义为：AB={x|xA或许xB}，会合的并可推行到多个集合，设A1,A2,,An都是会合，它们的并定义为：A1AAn={x|存在某个i，使得xA}2i·会合的交(intersection)：会合A和B的并AB定义为：AB={x|xA并且xB}，会合的交也可推行到多个会合，设A1,A2,,An都是会合，它们的交定义为：A1AAn={x|对全部的i，都有xA}2i·会合的差(difference)：会合A和B的差AB定义为：AB={x|xA并且xB}。关系和函数的基本看法·有序对(orderedpair)：设A和B是两个会合，aA,bB是两个元素，a和b的有序对，记为<a,b>，定义为会合{{a},{a,b}}。·设<a,b>和<a,b>是两个有序对，能够证明<a,b>=<a,b>当且仅当a=a且b=b。(如何证？)112211221212·有序对可推行到n个元素，设A,A,,A是会合，a1A,aA,a,nA是元素，定义有序n元12n122n组(orderedn-tuple)<a1,a2,,an>为<<a1,a2,a,n-1>,an>，注意这是一个归纳(inductive)定义，将有序n元组的定义归纳为有序n-1元组的定义。·明显有<a,a,a,>=<b,b,b,>当且仅当a=b且a=b且且a=b。12n12n1122nn·会合的笛卡尔积(cartesianproduct)：两个会合A和B的笛卡尔积AB定义为：AB={<a,b>|aA且bB}·比如，设A={a,b,c}，B={1,2}，则：AB={<a,1>,<a,2>,<b,1>,<b,2>,<c,1>,<c,2>}·笛卡尔积可推行到多个会合的状况，会合A1,A2,,An的笛卡尔积定义为：尔积关系

A1A2An={<a1,a2,a,n>|a1A1且a2A2且且anAn}·会合之间的关系(relation)：定义n个会合A1,A2,,An之间的一个n元关系R为会合A1,A2,,An的笛卡A1A2An的一个子集。设<a1,a2,a,n>A1A2An，若<a1,a2,a,n>R，则称a1,a2,a,n间拥有R，不然称它们不具相关系R。特别地：·当A1=A2==A=A时，称R为A上的n元关系。n·当n=2时，有RA1A2，称R为A1与A2间的一个二元关系(binaryrelation)。这时若<a,a>R则12简记为a1Ra2，不然（即<a1,a2>R）记为a1Ra2。往常研究得最多的是二元关系，n元关系的很多性质可从二元关系的性质扩大而获得。假如没有特别指明的话，说R是一个关系则是指R是一个二元关系。·当n=1时，这时可认为R是会合A上知足某种性质的子集。·关系的一些性质：设R是A上的二元关系：·说R是自反的(reflexive)，假如对任意的aA有aRa。·说R是反自反的(irreflexive)，假如对任意的aA有aRa。·说R是对称的(symmetric)，假如对任意的a,bA有若aRb则bRa。·说R是反对称的(antisymmetric)，假如对任意的a,bA有若aRb且bRa则a=b。·说R是传达的(transitive)，假如对任意的a,b,cA有若aRb且bRc则aRc。·说R是等价关系(equivalence)，假如R是自反的、对称的和传达的。·会合之间的函数(function，或说映照mapping)：定义会合A到B的函数f是A和B的笛卡尔积AB的一个子集，且知足若<x,y>f及<x,z>f则y=z。所以函数是A和B之间的一个特别的二元关系。往常记会合A到B的函数f为f:AB。·函数f:AB的定义域(domain)dom(f)定义为：dom(f)={x|存在某个yB使得<x,y>f}·函数f:AB的值域(range)ran(f)定义为：ran(f)={y|存在某个xA使得<x,y>f}·若<x,y>f，往常记y为f(x)，并称y为x在函数f下的像(image)，x为y在函数f下的原像。·函数也可推行到n元的情况：f:A1A2AnB，意味着：·f是A1A2AnB的一个子集，且·<x1,x2,x,n,y>f且<x1,x2,x,n,z>f则y=z。·函数的一些性质：设f:AB是会合A到B的函数：·说f是全函数(totalfunction)，若dom(f)=A，不然称f是偏函数(partialfunction)。下边假如没有特别指明的话，都是指全函数。·说f是满射(surjection,或说fmapsAontoB)，假如ran(f)=B，即对任意的yB都有原像。·说f是单射(injection，或说fisone-one)，假如有f(x)=f(x)则x=x，即对任意的yB，假如它有原1212像的话，则有独一的原像。·说f是双射(bijection，或说f是一一对应)，假如f既是满射，又是单射，即对任意的yB，都有独一的原像，相同依据全函数的定义，对于任意xA都有独一的像。这时能够定义f的逆函数(inversefunction)，记为f-1:BA，f-1(y)=x当且仅当f(x)=y。明显f-1也是双射。·会合的基数(cardinalnumber)或说势：会合A的基数记为|A|，且有：·对于有限会合A，令A的基数为A中元素的个数。·定义无穷会合，不直接定义基数，而是经过定义两个会合之间的等势关系来刻划会合的基数或势，说会合A和会合B是等势的(equipotent)，假如存在一个从A到B的双射。依据双射的性质，能够证明等势是会合上的一个等价关系。·称与自然数集等势的会合为可列集(enumerable)，有限集和可列集统称为可数集(countable)。·设A和B是有限会合，有|P(A)|=2|A|，|AB|=|A||B|。小结·下边以树的形式给出了以上主要看法之间的关系：会合子集幂集

会合的补、并、交、差

有序对笛卡尔积关系关系的自反、对称、传达性

函数单射、满射、双射归纳定义和归纳证明·一个会合的归纳定义(inductivedefinition)往常分为三步：·归纳基：一些基本的元素属于该会合；·归纳步：定义一些规则（或许说操作），从该会合中已有的元向来生成该会合的新的元素；·最小化：该会合中的全部元素都是经过基本元素以及所定义的规则生成的，换句话说，该会合是由基本元素及规则所生成的最小的会合。·自然数集N的归纳定义：归纳基：0是一个自然数，即0N。[2].归纳步：若n是自然数，则n的后继也是自然数。记n的后继为succ(n)，即若nN，则succ(n)N。为方便起见，后边也记n的后继为n+1。[3].最小化：全部的自然都经过步骤[1]和[2]获得，或许说自然数集是经过步骤[1]和[2]获得的最小会合。·这类定义方式可推行到对其余一些看法的定义，比如上述多个会合的并、交、笛卡尔积以及多个元素的有序n元组都可经过递归的方式定义。比如，对于多个会合的并可定义为：·归纳基：A1A2={x|xA1或许xA2}·归纳步：A1AAn=(A1AAn-1)An22·这里不需要最小化，因为这里不是定义会合。·数学归纳法：对于自然数的很多性质都可经过数学归纳法来证明，对于性质R，假如它对0成立，并且如果对于n成立的话，能够获得它对于n+1也成立，那么性质R对全部的自然数成立。这类证明方法的正确性本身可经过自然数的归纳定义来获得证明：·定义会合S={nN|性质R对n成立}·归纳基：依据上边的定义有0S·归纳步：依据上边的定义有假如nS，则n+1S，所以S是知足上边自然数集的归纳定义中的1、2点的一个会合，而自然数集N是知足这两点的最小会合，所以有NS，而明显有SN，所以S=N。·数学归纳法举例：使用数学归纳法证明1+2+n+=(n*(n+1))/2·归纳基：当n=0时明显成立。·归纳步：假如对于n成立，则有1+2+n+=(n*(n+1))/2（这称为归纳假定），此刻要证对于n+1也成立。明显有：1+2+n++(n+1)=(n*(n+1))/2+(n+1)//依据归纳假定=(n*(n+1)+2*(n+1))/2=((n+1)*((n+1)+1))/2所以要证的公式对于n+1成立，所以对于全部的自然数成立。·明显在数学归纳法中，对于归纳基改为R对于自然数k成立，归纳步不变的话，则可证明R对于全部大于k的自然数都成立。·在数学归纳法中，也可将归纳步改为假如R对于全部小于n的自然数成立，则推出R对于n也成立，即归纳步是假定对于全部小于n的自然数性质R成立来导出性质R对于自然数n成立。这类形式的数学归纳法通常称为第二数学归纳法。形式系统·形式系统的定义：一个形式系统S由以下4个会合构成：·一个非空会合S，称为形式系统S的字母表或说符号(Symbol)表；·一个由S中字母的有限序列（字符串）所构成的会合FS，称为形式系统S的公式(Formula)集；·从FS中选用一个子集A，称为形式系统S的公义(Axiom)集；S·F上有一个部分函数集R={R|R:FSFSFSF,n=1,2,}称为形式系统，S的规则(Rule)SSnnS集，此中Rn:FSFSFSFS是n元的部分函数，我们称其为n元规则。统

·形式系统中的定理(Theorem)：·归纳基：tAS是形式系统S中的定理。·归纳步：t1,t2,t,n是形式系统S中的定理，而Rn是S中的规则，那么S中的定理。·对于形式系统中的规则Rn:FSFSFSFS，往常表示成下边的形式：t1,t2,t,nRn(t1,t2,t,n)

Rn(t1,t2,

t,n)也是形式系·形式系统拥有两个特色：·形式化其实是一个可机械实现的过程，在它里面，符号、规则和演算等被表示得严实、精准。在形式系统S中，只好使用字母表S中的符号，只认可公式集FS中的符号串的合理性，只好由公义集，依据规则推出存心义的东西来。·形式系一致旦达成，就成了符号串及依据规则进行的符号串的改写，系统与一确实质意义就绝不相关，或许说已经经过这类符号，从实质问题中抽象出了我们所需要研究的内容。在形式系统内部，所能认识的只好是符号串及其改写，只好在形式系统外对这类符号串及规则给予意义。·对象语言(Objectlanguage)与元语言(Metalanguage)：·数理逻辑所研究的是“数学推理”，而使用的方法也是数学推理，所以有必需区分这两个层次的推理。·把作为研究对象的“推理”形式化，使用形式语言来表示作为研究对象的“推理”的前提、结论和规则等，这类形式语言是我们所研究的对象语言。·另一方面，对于形式系统的性质、规律的表达和作为研究方面的推理方式使用另一种语言来表达，这个语言称为研究的元语言，往常使用多半学化的自然语言。·形式语言的语法(Syntax)与语义(Semantic)：·形式语言的语法是构成形式系统的公式集、公义集和规则集的法例。·形式语言的语义是对于形式系统的解说和意思。·形式语言自己没有含义，但我们在结构它们时是设想它们能代表某种意义的，特其余当我们在选择形式系统的公义时，老是选择所研究的问题域中那些最为明显或最简单公认为正确的性质。习题1.令会合A={n|n10且n是奇数}，B={n|n10且n是素数}，请回答以下问题：请用列元素的方法列出会合A和会合B，请问会合B是不是会合A的子集？b)请计算AB、AB、AB、AB以及P(A)(即A的幂集)。设关系R={<a,b>|a和b是互质的自然数}，请问R是自反的吗？对称的吗？传达的吗？为何？3.设f:AB是函数，R是价关系。

A上的以下二元关系：R={<a,b>|a,bA,f(a)=f(b)}，证明R是A上的一个等使用数学归纳法证明：12+22+32++n2=(n*(n+1)*(2n+1))/65.设有函数f:NNN，f(n)=<n,n+1>，请问f是不是单射、满射或双射？*6.设R1和R2都是A上的等价关系，请问R1R2和R1R2能否仍是A上的等价关系？假如是请证明，不然请举一反例。*7.设R是会合A上的等价关系，aA，可定义：a)[a]={bA|aRb}，称[a]为a对于R的等价类；A/R={[a]|aA}，称A对于R的商集。*8

设函数f:AA/R定义为对任意aA有f(a)=[a]，请问R知足如何的条件时f是单射？请给出<x,y,z>的会合方式的定义。若定义：[x,y,z]={{x},{x,y},{x,y,z}}，则假如有[x1,y1,z1]=[x2,y2,z2]能否意味着有x1=x2且y1=y2且z1=z2？第二讲数理逻辑一、命题逻辑(PropositionalLogic)内容概括·简单命题与复合命题：什么是命题？命题联络词及其含义。·命题公式与赋值：命题逻辑公式的归纳定义，命题公式的真值表。·等值演算：命题公式的等值赋值，重要的等值式。·命题联络词的齐备集：经过等值演算获得命题联络词的齐备集和极小齐备集。·命题公式的范式：析取范式与合取范式。·命题演算系统：使用命题逻辑公式进行推理的形式系统。·命题演算系统的语义与命题演算系统的元性质：注意差别形式系统的语法和语义。简单命题与复合命题·命题(proposition)：经典命题逻辑中，称能判断真假但不可以既真又假的陈说句为命题。·命题对于命题逻辑来说是一个原始的看法，不可以在命题逻辑的范围内给出它的精准定义，只好描绘它的性质。·命题一定为陈说句，不可认为疑问句、祈使句、叹息句等，比以下述句子为命题：1.3是有理数2.8小于103.2是素数4.乌鸦是黑色的以下句子不是命题：1.这个小男孩多英勇啊！2.乌鸦是黑色的吗？3.希望中国队能取胜。4.请把门开一开！以下句子不行能判断其为真或为假，所以也不是命题：1.x+y>102.我正在说谎·命题一定拥有真假值，从某种意义上来说，疑问句、祈使句、叹息句没有真假之分。但能判断真假，其实不意味着此刻就能确立其是真仍是假，只需它拥有能够独一确立的真假值即可，比以下述陈说句是命题：1.明年的中秋节的夜晚是晴日3.21世纪末，人类将居住在太空

2.地球外的星球上存在生物4.哥德巴赫猜想是正确的·经典命题逻辑不区分此刻已确立为真，仍是未来可能确立为真这类状况，办理与时间相关的真值问题是时态逻辑的任务。经典命题逻辑也不区分是在技术上能够确立为真，仍是此刻的技术条件下不可以够确立为真的这类状况，只认可在技术上，或许说能给出某种方法确立为真的那些东西才为真是直觉逻辑的看法。·真命题和假命题：命题是为真或为假的陈说句，称这类真假的结果为命题的真值。如果命题的真值为真，则称为真命题，不然称为假命题。·命题常量与命题变量：使用符号来表示命题，往常用p,q或带下标来表示命题常量或者变量。假如命题符号p代表命题常量则意味它是某个详细命题的符号化，假如p代表命题变量则意味着它可指代任何详细命题。假如没有特别指明，往常来说命题符号p等是命题变量，即可指代任何命题。·简单命题与复合命题：不可以分红更简单的陈说句的命题为简单命题或原子命题，不然称为复合命题，复合命题使用命题联络词联络简单命题而获得。·复合命题的联络词往常包含：·设p是任意命题，复合命题“非p”称为p的否认（非），记为p。·设p和q是任意命题，复合命题“p且q”称为p和q的合取（与），记为pq。·设p和q是任意命题，复合命题“p或q”称为p和q的析取（或），记为pq。·设p和q是任意命题，复合命题“假如p则q”称为p蕴涵q，记为pq。·设p和q是任意命题，复合命题“p当且仅当q”称为p与q等价，记为pq。·上述定义中的非(negation)、合取(conjunction)、析取(disjunction)、蕴涵(implication)和等价(equivalence)是在命题逻辑中的术语，而引号中给出的复合命题是自然语言中的典型用法。自然，命题逻辑中符号化形式的复合命题在自然语言中有许很多多的表达方法，这也是为何自然语言有歧义的原由，参赐教材中的各例题，并注意以下几点：·pq的逻辑关系是pq为真当且仅当p和q中起码有一个为真。但自然语言中的“或”既可能拥有相容性，也可能拥有排挤性。命题逻辑中采纳了“或”的相容性。·pq的逻辑关系是pq为假当且仅当p为真，而q为假，称p为蕴涵式的前件，q为蕴涵式的后件。现实世界中的“假如则”与这类蕴涵有比较大的差别。简单命题逻辑中的这类蕴涵经常称为“实质蕴涵”，相对应地有“严格蕴涵（p严格蕴涵q，意味着p为真，则q不行能为假）”、“相关蕴涵”等。实质蕴涵意味着可从假的前提推出任何命题来，或两个不没有内在联系的命题之间存在蕴涵关系。·将平时生活中的陈说句符号化为命题逻辑中的公式是在此后的程序编写等课程中应用数理逻辑知识的重要基础。但就数理逻辑这门课程自己而言，我们只关怀公式之间的真值关系，而不关怀公式所详细指代的命题。·复合命题与简单命题之间的真值关系可用下表给出，此中0代表假，1代表真：pqppqpqpqpq0010011011011010001001101111命题逻辑公式【定义1.1】命题逻辑公式(propositionallogicformula)由以下子句归纳定义：归纳基：命题常量或命题变量是命题逻辑公式，称为命题逻辑公式的原子项。[2].归纳步：假如A,B是逻辑公式，则(A)、(AB)、(AB)、(AB)和(AB)也是命题逻辑公式。[3].最小化：全部的命题逻辑公式都经过1和2获得。□在这里我们隐含地使用的字母表是大小写的英文字母、命题联络符和园括号。英文字母还可带下标。其余的符号都不属于我们的符号表，即在命题逻辑公式中不可以出现这些符号。后边我们将命题逻辑公式简称为命题公式，或在没有二义的状况下进一步简称为公式。【例子1.1】((pq)((p)(qr)))是命题公式，它经过以下步骤生成：1.p是公式；//依据定义1.1的[1]2.q是公式；//依据定义1.1的[1]3.(pq)是公式；//依据定义1.1的[2]4.(p)是公式；//依据定义1.1的[2]5.r是公式；//依据定义1.1的[1]6.(qr)是公式；//依据定义1.1的[2]7.((p)(qr))是公式；//依据定义1.1的[2]，以及4,68.((pq)((p)(qr)))是公式。//依据定义1.1的[2]，以及3,7这类生成过程，能够形象地用下边的一棵树来表示：((p

q)

((p)

(q

r)))(p

q)

((p)

(q

r))p

q

(p)

(q

r)p

q

r这类树在形式语言与自动机中就称为语法剖析树。【反例1.2】·依据定义1.1，p·依据定义1.1，(p联络符都会对应一对园括号。·明显(pqr)、(q

q不是公式，因为两边没有园括号qr)不是公式，实质上，由定义(rp)等都不是公式。

1.1生成的公式，每个命题【定理1.2】设R是某个性质，假如有：[1].对于全部的原子项p，都知足性质R；[2].假如对任意的公式A和B都知足性质R，就有(A)、(AB)、(AB)、(AB)和(AB)也知足性质R。那么，全部的公式A就都知足性质R。□该定理的证明近似数学归纳法的证明，很简单依据定义1.1获得。【定义1.3】命题公式A的复杂程度deg(A)定义为：[1].假如A是原子项，则deg(A)=0；[2].deg(A)=deg(A)+1;[3].deg(A*B)=max(deg(A),deg(B))+1，此中*代表、、、之一。□此定义等价于教材p11的定义1.7。只可是我们在这里给出的是递归定义。使用归纳法，我们可证明下边定理：【定理1.4】deg(A)小于等于命题公式A中的命题联络符号的数目。【证明】依据命题公式A的结构进行归纳证明：1.归纳基：假如A是原子项，则依据定义

1.3有deg(A)=0，明显定理成立。归纳步：假定定理对于命题公式A和B成立（归纳假定），记命题公式A中的命题联络符号数为Sym(A)，即有deg(A)Sym(A)和deg(B)Sym(B)。那么因为deg(A)=deg(A)+1，而Sym(A)=Sym(A)+1，所以定理对于A也成立。相同因为deg(A*B)=max(deg(A),deg(B))+1，而Sym(A*B)=Sym(A)+Sym(B)+1，因此有deg(A*B)Sym(A*B)，进而定理对全部的命题公式都成立。□【定理1.5】任意命题逻辑公式A中出现相等数目的左右园括号，实质上，左右园括号的个数都等于A中的命题联络符号数。□【定理1.6】任意命题逻辑公式A拥有以下6种形式之一，且只拥有此中一种形式：[1].A为原子项；[2].(A)[3].(AB)[4].(AB)[5].(AB)[6].(AB)□定理1.6确实切含义包含以下几点：1.任意命题公式必定拥有上述6中形式之一；2.这6中形式都互不相同；3.假如(A)与(A1)相同，则必有A与A1相同；4.假如(A*B)与(A1*B)相同，则必有A与A相同，且B与B相同。111依据定理1.5和定理1.6，我们不难理解例子1.1是如何获得该此中命题公式的语法剖析树的。实质上每个命题公式的最左侧都是左园括号，假如从第二个符号不是左园括号，那么这个公式只有一个命题联络符。不然找与第二个左园括号配对的右园括号，进而将命题公式区分为这样的形式：(()*(，))假如本来的命题公式为根的话，那么左右两边的两个命题公式分别为它的左右子树了，并且对这两个公式可作近似的剖析，最后到原子项。在后边，为了书写方便起见，我们省略最外边的括号，并规定各个命题联络符的优先级别为大于，大于，大于，大于，进而可省略命题公式中一些不用要的园括号，比如例子1.1中的公式可写为：pqpqr。可是在后边我们书写公式的原则是尽量简易，但又能让读者简单理解。而相关命题公式的性质的议论，则只针对可由上边定义所能生成的公式形式。

1.1上边议论的命题公式的语法结构，下边议论命题公式的赋值。【定义1.7】对命题公式的一次真值赋值t是从全部命题变量所构成的会合到会合{0,1}的函数。实质上，对于某个命题公式A来说，我们只关怀t在A中的命题变量上的值。这里我们假定存在一个全部命题变量所构成的会合U，或许说我们全部命题公式中的变量都取之于会合U，我们记命题公式A中的全部命题变量所构成的会合为Var(A)。设有一个真值赋值t:U{0,1}，而对于命题公式A的真值赋值来说，我们只关怀t在Var(A)上的值。【例子1.3】对于命题公式A=((pq)((p)(qr)))，有：Var(A)={p,q,r}这里不如假定U=Var(A)，真值赋值就是一个函数t:{p,q,r}{0,1}，比如可令：t(p)=0,t(q)=1,t(r)=0【定义1.8】命题公式A在真值赋值t:U{0,1}下的真值t(A)递归定义以下：[1].假如命题公式A是一个命题常量p，则假如p为真，t(A)=1，不然t(A)=0；[2].假如命题公式A是一个命题变量p，则t(A)=t(p)[3].若t(A)=0则t(A)=1，不然t(A)=0。[4].若t(A)=t(B)=1，则t(AB)=1，不然t(AB)=0。[5].若t(A)=t(B)=0，则t(AB)=0，不然t(AB)=1。[6].若t(A)=0或许t(B)=1，则t(AB)=1，不然t(AB)=0。[7].若t(A)=t(B)，则t(AB)=1，不然t(AB)=0。【例子1.3，续】对于命题公式A=((pq)((p)(qr)))，及真值赋值函数t：t(p)=0,t(q)=1,t(r)=0有：1.t(p)=0,t(q)=1;2.t(pq)=1;//依据定义1.8的[5]4.t(p)=1;//依据定义1.8的[3]5.t(r)=0;6.t(qr)=0;//依据定义1.8的[4]7.t((p)(qr))=0;//依据定义1.8的[7]8.t((pq)((p)(qr)))=0;//依据定义1.8的[6]所以命题公式A在上述真值赋值下的真值t(A)是0。不难看出，定义1.8与上一节中给出的复合命题与简单命题之间的真值关系表是一致的。并且从上边的例子与例1.1的比较也可看出，对于命题公式的真值，可依据该命题公式的生成步骤来获得。命题公式的真值只与命题公式中所出现的命题变量的真值赋值相关，假如命题公式中含有n个命题变量，则对这些命题变量的真值赋值共有2n种不同状况，可经过一个表，列出在这全部状况下命题公式的真值，这类表称为该命题公式的真值表，比如上述命题公式的真值表为：

Ap

q

r

(pq)

(p)

(qr)

((p)

(qr))

((pq)

((p)

(qr)))0

00

0

1

0

0

10

01

0

1

0

0

1010110000111111110010011101100111101001111110100【定义1.9】假如命题公式A在任意的真值赋值函数t:U{0,1}下的真值t(A)都为1,则称命题公式A为永真式(tautology)（或称重言式）；假如命题共A在任意的真值赋值函数下的真值都为0，则称A为矛盾式(contradiction)；假如A不是矛盾式，则称为可知足式。【例子1.4】依据命题公式A=((pq)((p)(qr)))的真值表，我们知该命题公式是可知足式，但不是永真式。而公式B=((p(qp))r)是永真式，其真值表为：pqr(qp)(p(qp))((p(qp))r)000011001011010111011111100111101111110111111111而公式((((pq))q)r)（教材14页简写为(pq)qr）是矛盾式，其真值表为：pqr(pq)((pq))(((pq))q)((((pq))q)r)00010000011000010100001110001000100101010011010001111000【定义1.10】我们使用符号来表示一组命题公式所构成的会合。定义在真值赋值函数t:U{0,1}下的真值t()为：t()=1当且仅当对中任意公式A有t(A)=1，不然定义t()=0(注意只需中存在某个公式A使得t(A)=0，就有t()=0)。说是可知足的，假如存在某个真值赋值函数t使得t()=1，这时称t知足。【定义1.11】设是一组命题公式的会合，说命题公式A是认为前提的永真式，假如知足对任意知足的真值赋值函数t都有t(A)=1，这时我们记为╞A。注意在定义1.11中，假如为空集，则╞A表示A为永真式，因为对于空集来说，明显任意的真值赋值函数t都知足它（因为中没有命题公式），进而╞A意味着对任意的真值赋值函数t都有t(A)=1，即A为永真式。4.等值演算【定义1.12】当={A1,A2,,An}时，我们也记╞A为A1,A2,,An╞A。假如有A╞B且B╞A，则称命题公式A与B等值，记为AB。实质上公式A与B等值记为A╞╡B会更正确些，但教材采纳了符号AB，为了不会过于混杂，我们也使用这类记号。实质上，依据定义1.11，AB就意味着对任意的真值赋值函数t有t(A)=1当且仅当t(B)=1，也就是说对任意的t有t(A)=t(B)。进而定义1.12与教材中对于命题公式等值的定义是等价的，即有下述定理：【定理1.13】AB当且仅当A

B是永真式。

□使用真值表，不难证明下边的定理：【定理1.14】设A,B,C是任意的命题公式，有：两重否认律：A((A))[2].等幂律：A(AA)A(AA)[3].互换律：(AB)(BA)(AB)(BA)[4].联合律：((AB)B)(A(BB))((AB)B)(A(BB))[5].分派律：(A(BC))((AB)(AC))(A(BC))((AB)(AC))[6].德摩根律：((AB))((A)(B))((AB))((A)(B))[7].汲取律：(A(AB))A(A(AB))A[8].零律：(A1)1(A0)0[9].同一律：(A0)A(A1)A[10].排中律：(A(A))1[11].矛盾律：(A(A))0蕴涵等值式：(AB)((A)B)等价等值式：(AB)((AB)(BA))[14].假言易位：(AB)((B)(A))[15].等价否认等值式：(AB)((A)(B))[16].归谬论：((AB)(A(B)))(A)□要注意的是，上述定理中的0代表真值为0的任意命题常量，而1代表真值为1的任意命题常量。因为命题联络符号和都知足联合律，所以我们可有以下的简写：A1A2An依据以上简写，我们可推行定理1.13为以下定理1.15：【定理1.15】[1].A1,A2,,An╞A当且仅当╞((A1A2An)A)。[2].A1,A2,,An╞A当且仅当╞((A1(A2((AnA)))。□【引理1.16】设有AA'和BB'，则有：[1].(A)(A')[2].(AB)(A'B')[3].(AB)(A'B')[4].(AB)(A'B')[5].(AB)(A'B')□依据引理1.16，不难证明下边的置换规则：【定理1.17】设有BC，而A'是命题公式A经过使用C替代A中出现的某些B（不需假如替代全部的B）而获得的命题公式，则有AA'。【证明】对命题公式A的结构进行归纳。第一假如B=A，则有C=A'，进而有AA'。归纳基：假如A是命题变量和命题常量，那么必有B=A，所以定理成立。归纳步：依据定理1.6，命题公式A必为以下5种形式之一：A1,A1A,A1A,22A1A2,A1A2。设A的形式为A1，假如B=A则定理成立，不然必有B出现A1中，将A1中的B用C替代后获得的为A1'，按归纳假定有A=A'，再依据引理1.15有A=A'。1111定理成立。若A的形式为A1*A2，则假如B=A则定理成立，不然必有B出此刻A1或A2中，或同时出此刻这二者中。设将A1中的B用C替代后获得的为A1'，而将A2中的B用C替代后获得的为A2'，按归纳假定有A1A1'和A2A2'，再依据引理1.15有A1*A2A1*A2，即定理成立。□【定义1.18】假如命题公式A中只出现命题变量、命题常量、命题联络符号、和则称为限制性（命题）公式。定义：[1].对于限制性公式A，将此中的命题联络符号换成，命题联络符号换成得到的公式称为A的对偶公式(dualformula)，记为Aop。[2].对于限制性公式A，将此中出现的全部原子项（命题变量或命题常量）p换成p获得的公式称为A的内否式，记为A。【例子1.5】设公式A=((pq)(r))，则：(1).A的对偶式Aop=((pq)(r))(2).A的内否式A=(((p)(q))r)【引理1.19】设公式A、B都是限制性公式，有：[1].(Aop)opA(A)A[2].(AB)opAopBop(AB)AB[3].(AB)opAopBop(AB)AB[4].(Aop)(A)op□引理1.19中的(恒等号)表示两边的公式在（语法）形式上完好相同，比如(Aop)opA表示对A的对偶公式Aop再做一次对偶操作获得的就是A自己。而(Aop)(A)op表示对A做一次对偶操作获得Aop，而后再求Aop的内否式，获得的公式与先求A的内否式，而后再做对偶操作获得的公式完好相同，用代数学的术语来说，就是这两种操作可互换。引理1.19很简单依据定义1.18证明，也可直观理解引理1.19所代表的含义。读者可通过对一些公式求它的对偶式和内否式来考证引理1.19的每个恒等式，比如：【例子1.5，续】设公式A=((pq)(r))，则：(1).Aop=((pq)(r)),(Aop)=(((p)(q))r)(2).A=(((p)(q))r),(A)op=(((p)(q))r)明显有(Aop)(A)op。【定理1.20】设公式A是任意的限制性公式，有：[1].(A)op(Aop)(A)(A)[2].(Aop)A【证明】略□【推论1.21】设公式A和B都是限制性公式，有AB则(Aop)(Bop)【证明】依据引理1.16及(A)A不难获得AB当且仅当AB。则：(Aop)AB(Bop)□在定理1.14中已经看到了推论1.21的很多旁证，比如对于汲取律(A(AB))A，其中(A(AB))的对偶公式是(A(AB))，进而有(A(AB))A，这与第二个吸收律公式(A(AB))A是相同的，因为A、B代表任意命题公式。【例子1.6】考证以下等值式(1).((pq)r)((qp)r)(2).(p(qr))((pq)r)(3).((pq)r)((pr)(qr))(4).((pq)r)((pr)(qr))(5).(p(qr))((pq)(pr))(6).(p(qr))((pq)(pr))【证明】证明的思路有两种，第一种思路是经过列真值表，可看到上述等值式的两边在任何真值赋值下都有相同的真值，进而达成上述等值式的考证。读者不如自己依照这类思路进行证明。第二种思路是利用定理1.14中的基本等值式来证明。能够看到上述等值式主假如对于蕴涵的等值式，证明对于蕴涵的等值式的方法是利用定理1.14中的[12]将蕴涵化成只出现与、或、非的公式，再来考证它们的相等。(1).((pq)r)((pq)r)//定理1.14中的[12]：蕴涵等值式((pq))r//定理1.14中的[12]：蕴涵等值式(p(q))r//德摩尔根律((qp)r)//的互换律(2).(p(qr))(p(qr))//蕴涵等值式(p(qr))//蕴涵等值式((pq)r)//的联合律((pq)r)//德摩尔根律，反向运用((pq)r)//蕴涵等值式，反向运用(3).((pq)r)((pq)r)//蕴涵等值式((pq)r)//德摩尔根律((pr)(qr))//分派律与互换律((pr)(qr))//蕴涵等值式(5).(p(qr))(p)(qr)//蕴涵等值式(p)(p)(qr)//的幂等律(pq)(pr)//的互换律和联合律(pq)(pr)//蕴涵等值式(4)(6)留作练习□【例子1.7】德摩尔根律的推行：(1).(A1A2An)(A1)(A2)(An)(2).(A1A2A)(A)(A)(A)n12n【证明】对n实行数学归纳法，或直接从定理1.20[2]获得。□联络词的完好集【定义1.22】{0,1}上的n元函数f:{0,1}n{0,1}就称为一个n元真值函数。联络词实质上一个一元真值函数：f(0)=1,f(1)=0而联络词、、和则都是二元真值函数：f(0,0)=0,f(0,1)=0,f(1,0)=0,f(1,1)=1f(0,0)=0,f(0,1)=1,f(1,0)=1,f(1,1)=1f(0,0)=1,f(0,1)=1,f(1,0)=0,f(1,1)=1f(0,0)=1,f(0,1)=0,f(1,0)=0,f(1,1)=1反过来，一个真值函数便可当作一个真值联络词。设f:{0,1}n{0,1}是一个n元真值函数，则可以下定义一个n元真值联络词Nf:对于n个命题变元p1,p2,p,n，命题公式Nf(p1,p2,p,n)在真值赋值函数<t1,t2,t,n>下的真值为f(t12,n,tt,)。明显互不相同的n元真值函数的个数为2n，所以可定义2n个n元真值联络词，比如122元真值函数有四个：f1:00,10f:00,11f:01,10f:01,11234而2元真值函数有16个，可定义16个真值联络词，而我们常用的只可是是此中的4个。此刻的问题是，能否全部的真值函数都可使用常用的这5个真值联络词来表示呢？【定义1.23】设是联络词的一个会合，称为联络词的一个完好集，假如任意真值函数f都可用仅含中联络词的命题公式A来表示，即对A中命题变元的任意一个真值赋值<t1,t2,t,n>，A在<t1,t2,t,n>下的真值为f(t1,t2,t,n)。【定理1.24】{,,,}是联络词的一个完好集。【证明】依据定义1.23只需证明对任意n元真值函数都可由只含、、和的n元命题公式来表示即可。对真值函数的元数n进行归纳证明。归纳基：当n=1时，一元真值函数只有4个，可分别用p(p)、p、p和p(p)来表示，所以定理成立。归纳步：假定当n=k时定理成立，要证n=k+1定理也成立。设f(x,x,x,,xk+1)是12k一个k+1元真值函数，定义以下两个k元真值函数：f1(x12k12x,k,0)f2(x12,k12k,x,x,)=f(x,x,,xx,)=f(x,x,x,,1)由归纳假定知f1和f2都可由只含、、和的k元命题公式来表示，设它们分别可由A1和A2表示，且假定A1和A2中的k个命题变元为p1,p2,,pk。此刻我们证f可由A=((pk+1)A1)(pk+1A2)表示，此中pk+1是不同于p1,p2,p,k的一个命题变元。即要证对命题变元p12kk+1的一个真值赋值12,kk+112kk+1)。,p,p,,p<t,tt,,t>时，A的真值是f(t,t,t,,t当tk+1=0时，即p被赋值为0，这时((pk+1)A)与A等值，而(pA2)的真值为1，所k+111k+1以A与A1等值，而按归纳假定有A1的真值为f1(t12k12k,t,t,)，即为f(x,x,x,,0)。同理可证当tk+1=1时A的真值是12,k,1)，进而A的真值是f(t12kk+1)。f(x,xx,,t,t,,t□【推论1.25】{,},{,}和{,}都是联络词的完好集。【证明】1.要证{,}是联络词的一个完好集，只需证任一命题公式可与一个只含和的命题公式等值，事实上有：(AB)((A)B)(AB)(((A)(B))){,}是联络词的一个完好集，因为：(AB)(((A)(B)))(AB)((A)B){,}是联络词的一个完好集，因为：(AB)

(((A)(B)))

(A

B)((A)B)事实上，上述每个会合都是极小的完好集，保持是完好集。

即不可以再从会合中去掉任意一个联络词还可以□【定理

1.26】{

,,,

}不是联络词的完好集。【证明】总取0值的真值函数不可以由只含此联络词集中的联络词的命题公式来表达，

因为这样的命题公式当全部命题变元都真值赋值为1时真值为1，不行能为0。

□命题公式的范式【定义1.27】将命题符号（代表命题变元或命题常量）或命题符号的否认统称为文字(literal)。仅由有限个文字构成的析取式称为简单析取式。仅由有限个文字构成的合取式称为简单合取式。【例子1.8】文字、简单析取式与简单合取式：p,q等为文字，也是一个文字的简单析取式和简单合取式(2)pq,p(q)等为两个文字的简单析取式，pq(r)为三个文字的简单析取式(3)pq,p(q)等为两个文字的简单合取式，pq(r)为三个文字的简单合取式【定理1.28】一个简单析取式是永真式当且仅当它同时含一个命题符号及其否认，一个简单合取式是矛盾式当且仅当它同时含一个命题符号及其否认。□【定义1.29】由有限个简单合取式构成的析取式称为析取范式(disjunctivenormalform)，由有限个简单析取式构成的合取式称为合取范式(conjunctivenormalform)。析取范式和合取范式统称为范式(normalform)。【例子1.9】析取范式和合取范式：(1)(pq)(pq),(pr)(qrp)(rp)等是析取范式(2)(pq)(pq),(pr)(qrp)(rp)等是合取范式依据定义1.18知，一个析取范式的对偶式是合取范式，一个合取范式的对偶式是析取范式。【定理1.30】一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式。一个合取范式是永真式当且仅当它的每个简单析取式都是永真式。【定理1.31】（范式存在定理）任意命题公式都存在与之等值的析取范式与合取范式。求一个公式的范式的步骤以下：[1].利用蕴涵等值式(AB)(AB)和等价等值式(AB)(AB)(AB)除去公式中的联络词和，使得公式中只含有联络词、和。利用两重否认律AA和德摩尔根律将否认放到命题符号前。[3].利用分派律，求析取范式利用对的分派律，求合取范式则利用对的分派律。【例子1.9】求命题公式的析取范式和合取范式(1).求(pq)(pr)的析取范式和合取范式(2).求(pq)(pr)的析取范式和合取范式【解答】(1)求(pq)(pr)的析取范式：(pq)(pr)(pq)(pr)//蕴涵等值式(pq)(pr)(pp)(pr)(qp)(qr)//两重否认律和分派律(pr)(qp)(qr)//(pp)是矛盾式明显(pq)(pr)的合取范式为(pq)(pr)。(2)求(pq)(pr)的合取范式：(pq)(pr)(pq)(pr)(pqp)(pqr)明显(pq)(pr)的析取范式为(p)q(pr)。注意：一个命题公式的合取范式和析取范式不拥有独一性。【定义1.32】在含有n个文字的简单合取式中，若每个命题符号和其否认不同时存在，而二者之一一定出现且只出现一次，且第i个命题变元或许否认出此刻从左侧算起的第i个地点上（若命题变元无下标，则按词典次序摆列），这样的简单合取式称为极小项。极小项是特别的简单合取式。含n个文字的极小项中，因为每个命题变元以原形或否认出现且仅出现一次，所以n个命题变元共可产生2n个不同的极小项。若在极小项中，将命题变元的原形对应1，否认对应0，则每个极小项独一地对应一个二进制数，该二进制数的每一位正是使该极小项的真值为1的真值赋值。【例子1.10】两个命题变元p,q生成的pq对应00，记为m0pq对应10，记为m2由三个命题变元p,q,r生成的8个极小项为：pqr对应000，记为m0pqr对应010，记为m2pqr对应100，记为m4pqr对应110，记为m6

个极小项为：q对应01，记为m1q对应11，记为m2pqr对应001，记为m1pqr对应011，记为m3pqr对应101，记为m5pqr对应111，记为m7【定义1.33】若析取范式中的简单合取式都是极小项，则称该析取范式为主析取范式。【定理1.34】任何命题公式存在独一的主析取范式。求一个公式的主析取范式是：先求该公式的一个析取范式。假如该析取范式的某个简单合取式A中既不含某个命题变元p，也不含它的否认p，则该简单合取式变为以下形式：(Ap)(Ap)。[3]除去重复出现的命题变元或命题变元的否认，矛盾式及重复出现的极小项，并将每个极小项的命题变元或其否认按下标次序或词典次序摆列。【例子1.11】求命题公式的主析取范式(1).求(pq)(pr)的主析取范式(2).求(pq)(pr)的主析取范式【解答】(1)依据例子1.9知(pq)(p

r)的一个析取范式是

(pr)(q

p)(qr)，我们将此中的每个简单合取式睁开为含有全部命题变元的极小项的析取：(pr)睁开为(pqr)(pqr)(qp)睁开为(pqr)(pqr)(qr)睁开为(pqr)(pqr)所以(pq)(pr)的主析取范式为(pqr)(pqr)(pqr)(pqr)，按极小项所对应的二进制数的大小从头摆列为(pqr)(pqr)(pqr)(pqr)。(2)依据例子1.9知(pq)(pr)的一个析取范式为(p)q(pr)，将此中每个简单合取式睁开为含有全部命题变元的极小项的析取：(p)睁开为(pqr)(pqr)(pqr)(pqr)q睁开为(pqr)(pqr)(pqr)(pqr)(pr)睁开为(pqr)(p所以(pq)(pr)的主析取范式为：(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)

qr)主析取范式也可从命题公式的真值表更简单地获得，对应地，依据命题公式的主析取范式也可简单地结构其真值表、判断其种类（矛盾式、可知足式仍是永真式）等。对于极大项、主合取范式等相关内容学生依据教材自学。作业：教材p60的9,10,11,15,17。命题演算系统命题演算系统是研究利用命题逻辑公式进行推理的形式系统。这里的推理指的是前提和结论之间的逻辑关系，所以这类形式系统自己不着重前提自己的正确性，而关怀的是能否能以前提有效地推出结论，议论什么是结论的有效证明。前提自己的正确性要在给予形式系统必定的解说的基础上才能确立，这类解说能够说是形式系统的语义。命题演算系统作为一个形式系统研究如何从公义，经过有限的规则来结构有效的证明，这类证明不过是符号的改写，自己没有什么含义。一个形式系统包含符号表、公式、公义及规则，符号表定义形式系统所使用的全部符号，公式是符号表上字符串，公式定义哪些字符串是形式系统所研究的合法对象。公义是结构一切证明的前提，公义自己的正确性在形式系统中不关怀，认为是不证自明的公式。自然在结构形式系统的时候，公义的选择是必定的外在依照的。规则是从公义出发结构形式系统中定理的方法。定理就是从公义出发，使用规则能够结构出有效证明的公式，形式系统就是研究能够获得什么定理。【定义1.35】命题演算系统P定义为：P的符号表包含：命题变元：小写英文字母并可加下标联络词：、协助符号：(,)（园括号）P的公式归纳定义为：命题变元是公式若A是公式，则(A)也是公式[3].若A和B是公式，则(AB)也是公式[4].全部公式都是经过有限次使用[1]、[2]和[3]获得。P的公义有以下三类：[A1].(A(BA))[A2].((A(BC))((AB)(AC))[A3].(((A)(B))(BA))P的规则只有一条：分别规则：由A和(AB)可获得B□【讲解】对于以上定义，需要注意以下几点：1.在系统P中只使用联络词和，这使得系统P比较简单，但也失掉了使用此外三个联络词、和的方便之处，为此可作以下商定，对于P中公式A和B：(AB)代表((A)B)(AB)代表(((A)(B)))(AB)代表((AB)(BA))注意，、和不是系统P的符号，只可是是为了使用方便而引入的符号。2.上述给出的公义是一种模式，此中每一条公义实质上代表了无穷多个公式，因为其中的A,B,C是一个符号，实质上可代表任意的公式，比如对于[A2]，此中A可代表BC获得：(((BC)(BC))(((BC)B)((BC)C))注意在使用公式A替代公式B的符号C时，要将公式A替代B中全部的C。相同分别规则也是一个模式。【定义1.36】命题演算系统P中的证明是由P中公式构成的一个序列：A1,A2,,An使得对每个i(1in)，以下两个条件之一成立：(1).Ai是公义，或许(2).Ai是由上述序列中Ai以前的某两个公式Aj,Ak(1j,kn)应用分别规则(M)获得。此时A12,nnnn,A,A称为A的一个证明，而A称为P的一个内定理，记为├A。□【讲解】对于以上定义，需要注意以下几点：├也不是P中的符号，不过用├An来表示An是一个内定理。2.所谓的用两个公式A,A应用分别规则(M)获得，是指{A,A}={Aj,AjA}或{A,jkjkijA}={A,AkA}。kki3.若A1,A2,,An是An的一个证明，则对每个Ai(1in)都有├Ai。P的每个公义都是P中的内定理。5.要证明一个公式【例子1.12】设A,B

A为P的内定理，只需给出是P中的公式，证明：├(A

A的证明序列即可。B)(AA)【证明】(1).├A(2).├(A(3).├(A【例子1.13】设

(BA)(BA))((AB)(AB)(AA)A是P中的公式，证明：

A))├(A

A)

//公义[A1]//公义[A2]//分别规则

，此中C用A(M)及(1)和(2)

取代【证明】(1).├A((BA)A)//公义[A1](2).├(A((BA)A))((A(BA))(AA))//公义[A2](3).├((A(BA))(AA))//分别规则(M)及(1)和(2)(4).├(A(BA)//公义[A1](5).├(AA)//分别规则(M)及(3)和(4)【定理1.37】设A,B,C是P中的三个公式：若├A，且├AB，则├B[2].若├AB，且├BC，则├AC【证明】[1]就是分别规则。对于[2]，证明以下：(1).├(BC)(A(BC))//[A1](2).├(BC)//前提(3).├(A(BC))//分别规则(4).├(A(BC))((AB)(AC))//[A2](5).├(AB)(AC)//分别规则(6).├(AB)//前提(7).├(AC)//分别规则□此后称此定理的[2]为传达规则(Tr)。【例子1.15】证明：├(A)(AB)【证明】(1).(2).(3).

├(A)├((B)├(A)

((B)(A))(AB)

(A))(A

B)

//[A1]//[A3]//传达规则【例子1.16】证明：├(A)A├A(A)证明】[1]的证明以下：(1).├(A)(AA)//例子1.15(2).├(AA)(AA)//[A3](3).├(A)(AA)//传达规则(4).├(A(AA))((AA)(AA))//[A2](5).├(AA)(AA)//分别规则(6).├(AA)//例子1.13(7).├(AA)//分别规则的证明以下：(1).├(A)(A)//[1](2).├(AA)(AA)//[A3](3).├AA//分别规则【讲解】经过以上例子，我们可发此刻结构公式的证明中可使用以下方法：1.可灵巧地使用公义，公义中的每个符号代表的是无穷多的公式，公义中某个符号的全部出现可用某个公式替代。但这与教材p43页的置换规则不同，教材没有为命题逻辑公式的推理成立形式系统，而是依据命题逻辑公式的真值来议论推理，所以有所谓的等值公式的置换，而我们这里所定义的形式系统还没有波及到真值赋值，这里的证明不过是符号的改写。成立形式系统的方法更切共计算机的思想方式，因为程序从实质来说也是个形式系统，计算机将输入变换到输出也不过符号的改写，至于程序员所认为的程序功能，是程序员给予程序的解说，这类解说计算机其实不理解。也就是说，对于计算机学科，形式系统的推导和形式系统的含义是分开的，正是这类分别，才使得形式系统的推导可由计算机来机械地达成，而人们又能够给予形式系统各种各种的解说来达成人们所需要的功能。可使用分别规则和传达规则来结构证明。3.可使用已经证明过的内定理作为前提，这相当于教材p43页的结论引入规则。4.教材中所议论的推理是在某种前提下的推理，下边我们在命题演算系统P中来定义这类推理。【定义1.38】设是P中的一个公式集，称P中的公式序列：A,A,,A12n为前提下推出An的一个证明，假如对每个i(1in)，以下三个条件之一成立：(1).Ai是公义，或许(2).Ai，或许(3).Ai是由上述序列中Ai以前的某两个公式Aj,Ak(1j,kn)应用分别规则(M)获得。此时记为├An。□【讲解】对于上述定义，我们需要注意以下几点：1.中的公式不必定是P中的公义或内定理，也不必定是有限会合。能够说是假定的前提，在前提下的证明其实是将中的公式看作“暂时公义”的一个证明。易证：当=时，├A当且仅当├A，或许说├A就是没有前提的证明。3.易证：对P中的任意公式A及公式集和'，若'，且'├A，则有├A。易证，若A，则有├A。【例子1.17】证明：{A,B(AC)}├(BC)【证明】(1).A//前提(2).A(BA)//公义[A1](3).(BA)//分别规则:(1)和(2)(4).(B(AC))//前提(5).(B(AC))((BA)(BC))//公义[A2](6).(BA)(BC)//分别规则:(4)和(5)(7).(BC)//分别规则:(3)和(6)下边利用上述定义和定理来形式化地议论教材p42中给出的推理定律的正确性。这里形式化的含义是不经过对公式的真值议论，而不过依据P系统的公义和分别规则来证明那些推理定律，自然证明时同意使用我们已经证明过的内定理。为此，我们第一给出命题演算系统中最重要的一条定理，即演绎定理，经过演绎定理可将在某个前提下的证明与P系统中的内定理相联系起来，并简化内定理的证明。【定理1.39（演绎定理）】设是P中的公式集，A和B是P中的两个公式，若{A}├B，则├AB。【证明】略。□【定理1.40（演绎定理的逆定理）】设是P中的公式集，A和B是P中的两个公式，若├AB，则{A}├B。【证明】略。□由以上两个定理，我们获得：【推论1.41】{A1,A2,,A}├A当且仅当├(A1(A2(AnA)))□n当={A1,A2,,An}时，我们往常将├A写为A1,A2,,An├A。依据演绎定理，分别规则可表示为A,AB├B，或用内定理表示为├A((AB)B)。对于传达规则，可推行为：【定理1.42】设是P中的公式集，A1,A2,,An为P中的公式，如有├A1,├A2,,├An，且A1,A2,,An├A则├A。【证明】略。□对于上述定理1.39,1.40,1.42的证明可参照王悍贫编著的《失散数学第一分册——数理逻辑》（北京大学第一版社，1997）的p70-75。我们可将├A1,├A2,,├An简记为├A1,A,,A。2n【例子1.18】证明：{AB,A}├(B)【证明】(1).(A)A//例1.16(2).A//前提(3).A//(1)使用演绎定理，而后使用分别规则(4).AB//前提(5).B//分别规则(6).B(B)//例1.16(7).B//演绎定理及分别规则由此可得：├(AB)(AB)，又因为├(AB)(BA)（公义[A3]）获得├(AB)(BA)。【例子1.19】证明：├A(B(AB))【证明】(1).├A((AB)B)//分别规则的内定理形式(2).├((AB)B)(B(AB))//例子1.18(3).├(B(AB))//传达规则【定理1.43】合取的引入和除去：[1].A,B├AB//合取的引入[2].AB├A,B（这代表AB├A及AB├B）。//合取的除去【证明】第一注意到AB是(AB)的简写，即(AB)的简写。要证明[1]，依据演绎定理知就是要证明├A(B(AB))，这由例子1.19可得（将此中的B换成B即可）。要证明[2]，只需证明AB├A即可，因为AB├B可同理得证。要证明AB├A，按演绎定理，即要证├((AB))A，而依据例子1.15有├(A)(AB)，而依据公义[A3]有├(A)(AB)(((AB))A)，依据传达规则有├((AB))A，再依据例子1.16有├(AA)，再依据传达规则得├((AB))A。□实质上教材中的符号就是这里的├，再依据定理1.43就有教材p42的假言推理就是分别规则，合取的化简就是定理1.43，拒取式就是例子1.18，假言三段论就是传达规则。下边给出对于析取的规则的证明，为此我们先给出下边几个例子：【例子1.20】证明：AB,AB,A├C【证明】(1).A//前提(2).AB//前提(3).B//分别规则(4).AB//前提(5).B//分别规则:(1)和(4)(6).B(BC)//例子1.15(7).BC//分别规则:(5)和(6)(8).C//分别规则:(7)和(3)该例子的直观含义是，假如从命题A能推出B及B的否认，那么A能推出任何公式。由此可获得├(AB)((AB)(AC))。【例子1.21】证明：AB,AB├B【证明】(1).(AB)(BA)//例子1.18(2).AB//前提(3).BA//分别规则(4).(AB)(BA)//公义[A3](5).AB//前提(6).BA//分别规则:(4)和(5)(7).(BA)((BA)(B(AB)))//例子1.20(8).(BA)(B(AB))//分别规则:(3)和(7)(9).B(AB)//分别规则:(6)和(8)(10).(B(AB))((AB)B))//公义[A3](11).(AB)B//分别规则:(9)和(10)(12).B//分别规则:(2)和(11)该例子的直观含义是，假如命题B既能从A推出，又能从A推出，那么B就是永真的。由此可获得├(AB)((AB)B)。这样我们可证明对于析取的重要定理：【定理1.44】析取的引入和除去：[1].A├AB,A├BA//析取的引入，教材p42中的附带定律[2].AB,CB,AC├B//析取的除去【证明】注意AC是(AC)的简写，那么依据演绎定理，[1]的前一个式子就是例子1.15，后一个式子则是公义[A1]。而[2]的证明以下：(1).AC//前提AC(2).CB//前提(3).AB//分别规则(4).AB//前提(5).B//例子1.21□依据演绎定理，定理1.44的[2]也可陈说为，如有A├B，且C├B，那么有AC├B。依据该定理，我们可获得教材p42中对于析取的其余定律：【例子1.22】证明：[1].AB,B├A//析取三段论[2].AB,CD,AC├BD//结构性二难推理【证明】[1]的形式是AB,B├A，这可证明以下：(1).(AB)(BA)//公义[A3](2).AB//前提(3).BA//分别规则(4).B//前提(5).A//分别规则(6).AA//例子1.16(7).A//分别规则的证明以下：(1).AB//前提(2).BBD//定理1.44，析取的引入(3).ABD//分别规则(4).CBD//与(1)~(3)近似(5).AC//前提(6).BD//定理1.44，析取的除去【例子1.23】证明：├(AA)A【证明】只需证(AA)├A(1).A(A(AA))//例子1.15(2).(A(A(AA)))((AA)(A(AA)))//公义[A2](3).((AA)(A(AA)))//分别规则(4).AA//前提(5).A(AA)//分别规则:(3)和(4)(6).(A(AA))((AA)A)//公义[A3](7).(AA)A//分别规则:(5)和(6)(8).A//分别规则:(4)和(7)【例子1.24】证明：AB,AB├A【证明】(1).(AB)((AB)(AA))//例子1.20(2).(AB)//前提(3).(AB)(AA)//分别规则(4).AB//前提(5).(AA)//分别规则:(3)和(4)(6).(AA)A//例子1.23(7).A//分别规则:(5)和(6)读者可很简单地看出，教材p46的附带前提证明法就是演绎定理的特别形式，而归谬法则相当于例子1.24.最后我们来议论命题演算系统的元问题，即该形式系统的靠谱性、一致性和齐备性。可靠性是指命题演算系统P中的内定理能否都是永真式，一致性是指P能否存在公式A，使得├A和├(A)都成立，假如存在这样的公式，则由例子1.20知P可推出任何公式，这时P便没有任何意义。齐备性是指P能否能推出命题逻辑公式的全部永真