离散数学-命题逻辑教学课程

离散数学命题逻辑(Proposition),主讲教师：吴旭,第一章命题逻辑数理逻辑是用数学方法研究思维规律的一门学科。所谓数学方法是指:用一套数学的符号系统来描述和处理思维的形式与规律。因此,数理逻辑又称为符号逻辑。本章介绍数理逻辑中最基本的内容命题逻辑。首先引入命题、命题公式等概念。然后,在此基础上研究命题公式间的等值关系和蕴含关系,并给出推理规则,进行命题演绎。主要内容如下：命题和命题联结词命题公式与翻译命题公式的等值关系和蕴含关系对偶与范式命题演算的推理理论,例1判断下列语句是否是命题。（1）空气是人生存所必需的。（2）请把门关上。（3）南京是中国的首都。（4）你吃饭了吗？（5）x=3。（6）啊，真美呀！(7)明年春节是个大晴天。,解语句（1）,（3）,（5），(7)是陈述句（1）、（3）、(7)是命题,用真值来描述命题是“真”还是“假”。分别用“1”和“0”表示,命题用大写的拉丁字母A、B、C、P、Q、或者带下标的大写的字母来表示。,例2判断下列陈述句是否是命题。P：地球外的星球上也有人；Q：小王是我的好朋友；,解P、Q是命题,二、命题联结词,原子命题：由简单句形成的命题。,复合命题：由一个或几个原子命题通过联结词的联接而构成的命题。,例3A：李明既是三好学生又是足球队员。B：张平或者正在钓鱼或者正在睡觉。C：如果明天天气晴朗，那么我们举行运动会。,定义五种联结词（或称命题的五种运算）。,1.否定“”,定义1-1设P是一个命题，利用“”和P组成的复合命题称为P的否命题，记作“P”(读作“非P”)。命题P取值为真时，命题P取值为假；命题P取值为假时，命题P取值为真。,例4设P：上海是一个城市；Q：每个自然数都是偶数。则有P：上海不是一个城市;Q：并非每个自然数都是偶数。,2合取“”定义1-2设P和Q是两个命题，由P、Q利用“”组成的复合命题，称为合取式复合命题，记作“PQ”（读作“P且Q”）。,当且仅当命题P和Q均取值为真时，PQ才取值为真。,例5设P：我们去看电影。Q：房间里有十张桌子。则PQ表示“我们去看电影并且房间里有十张桌子。”,3.析取“”定义1-3由命题P和Q利用“”组成的复合命题，称为析取式复合命题，记作“PQ”（读作“P或Q”）。,当且仅当P和Q至少有一个取值为真时，PQ取值为真。,例6将命题“他可能是100米或400米赛跑的冠军。”符号化。,解令P：他可能是100米赛跑冠军；Q：他可能是400米赛跑冠军。,则命题可表示为PQ。,设P、Q是两个命题，P异或Q是一个复合命题，记作PQ。,4.蕴含“”定义1-4由命题P和Q利用“”组成的复合命题，称为蕴含式复合命题，记作“PQ”（读作“如果P，则Q”）。,当P为真，Q为假时，PQ为假，否则PQ为真。,例8将命题“如果我得到这本小说，那么我今夜就读完它。”符号化。,解令P：我得到这本小说；Q：我今夜就读完它。于是上述命题可表示为PQ。,例9若P：雪是黑色的；Q：太阳从西边升起；R：太阳从东边升起。则PQ和PR所表示的命题都是真的.,5等值“”定义1-5由命题P和Q，利用“”组成的复合命题，称为等值式复合命题，记作“PQ”（读作“P当且仅当Q”）。,当P和Q的真值相同时,PQ取真,否则取假。,例10非本仓库工作人员，一律不得入内。,解令P：某人是仓库工作人员；Q：某人可以进入仓库。,则上述命题可表示为PQ。,例11黄山比喜马拉雅山高，当且仅当3是素数令P：黄山比喜马拉雅山高；Q：3是素数本例可符号化为PQ,从汉语的语义看，P与Q之间并无联系，但就联结词的定义来看，因为P的真值为假，Q的真值为真，所以PQ的真值为假。,对于上述五种联结词，应注意到：复合命题的真值只取决于构成它的各原子命题的真值，而与这些原子命题的内容含义无关。,三、命题符号化利用联结词可以把许多日常语句符号化。基本步骤如下：,（1）从语句中分析出各原子命题，将它们符号化；,（2）使用合适的命题联结词，把原子命题逐个联结起来，组成复合命题的符号化表示。,例12用符号形式表示下列命题。（1）如果明天早上下雨或下雪，那么我不去学校（2）如果明天早上不下雨且不下雪，那么我去学校。（3）如果明天早上不是雨夹雪，那么我去学校。（4）只有当明天早上不下雨且不下雪时，我才去学校。,解令P：明天早上下雨；Q：明天早上下雪；R：我去学校。,（2）（PQ）R；,（1）（PQ）R；,（4）R（PQ）,（3）(PQ）R；,例13将下列命题符号化（1）派小王或小李出差；（2）我们不能既划船又跑步；（3）如果你来了，那么他唱不唱歌将看你是否伴奏而定；（4）如果李明是体育爱好者，但不是文艺爱好者，那么李明不是文体爱好者；（5）假如上午不下雨，我去看电影，否则就在家里看书。,解（1）令P：派小王出差；Q：派小李出差。命题符号化为PQ。,（2）令P：我们划船；Q：我们跑步。则命题可表示为(PQ）。,（3）令P：你来了；Q：他唱歌；R：你伴奏。则命题可表示为P（QR）,（4）令P：李明是体育爱好者；Q：李明是文艺爱好者。则命题可表示为（PQ）（PQ）,（5）令P：上午下雨；Q：我去看电影；R：我在家读书。则命题可表示为（PQ）（PR）。,练习1-11.判断下列语句哪些是命题，若是命题，则指出其真值。（1）只有小孩才爱哭。（2）X+6=Y（3）银是白的。（4）起来吧，我的朋友。,(是假),(不是),(是真),(不是),2将下列命题符号化（1）我看见的既不是小张也不是老李。,解令P：我看见的是小张；Q：我看见的是老李。,则该命题可表示为PQ,（2）如果晚上做完了作业并且没有其它的事，他就会看电视或听音乐。,解令P：他晚上做完了作业；Q：他晚上有其它的事；R：他看电视；S：他听音乐。则该命题可表示为（PQ）（RS）,卡盟卡盟,MicrosoftOfficePowerPoint，是微软公司的演示文稿软件。用户可以在投影仪或者计算机上进行演示，也可以将演示文稿打印出来，制作成胶片，以便应用到更广泛的领域中。利用MicrosoftOfficePowerPoint不仅可以创建演示文稿，还可以在互联网上召开面对面会议、远程会议或在网上给观众展示演示文稿。MicrosoftOfficePowerPoint做出来的东西叫演示文稿，其格式后缀名为：ppt、pptx；或者也可以保存为：pdf、图片格式等,命题公式一、命题公式的概念1.命题常元一个表示确定命题的大写字母或T和F。,2命题变元一个没有指定具体内容的命题符号。,一个命题变元当没有对其赋予内容时，它的真值不能确定，一旦用一个具体的命题代入，它的真值就确定了。,3.命题公式命题公式(或简称公式)是由0(F)、1(T)和命题变元以及命题联结词按一定的规则产生的符号串。,定义1-6(命题公式的递归定义。)0(F)，1(T)是命题公式；命题变元是命题公式；如果A是命题公式，则A是命题公式；如果A和B是命题公式，则(AB),(AB),(AB),(AB)也是命题公式；有限次地利用上述而产生的符号串是命题公式。,例1下列符号串是否为命题公式。P(QPR)；(PQ)(QR),解不是命题公式。是命题公式。,二、真值指派命题公式代表一个命题，但只有当公式中的每一个命题变元都用一个确定的命题代入时，命题公式才有确定的真值，成为命题。,定义17设F为含有命题变元P1，P2，,Pn的命题公式，对P1，P2，,Pn分别指定一个真值,称为对公式F的一组真值指派。,公式与其命题变元之间的真值关系，可以用真值表的方法表示出来。,例2给出公式F=(（PQ）（QR）)(PR）的真值表。,解公式F的真值表如下：,三、公式类型定义1-8如果对于命题公式F所包含的命题变元的任何一组真值指派，F的真值恒为真，则称公式F为重言式(或永真公式)，常用“1”(T)表示。相反地，若对于F所包含的命题变元的任何一组真值指派，F的真值恒为假，则称公式F为矛盾式(或永假公式)，常用“0”(F)表示。如果至少有一组真值指派使公式F的真值为真，则称F为可满足公式。,例3构造下列命题公式的真值表，并判断它们是何种类型的公式(PQ)(PQ)；(QP)(PQ)；(PQ)(QR)(PR)。,由上可知：F1是重言式,F2是矛盾式。,(3)的真值表自己做一下，它是可满足公式。,命题公式的等值关系和蕴含关系,一、命题公式的等值关系定义1-9设A和B是两个命题公式,P1,P2,Pn是所有出现于A和B中的命题变元，如果对于P1,P2,Pn的任一组真值指派，A和B的真值都相同,则称公式A和B等值，记为AB,称AB为等值式。,注意：（1）符号“”与“”的区别与联系。,“”不是联结词，AB不表示一个公式，它表示两个公式间的一种关系，即等值关系。,“”是联结词，AB是一个公式。,AB当且仅当AB是永真公式。,（2）可以验证等值关系是等价关系。即自反性：对任意公式A，有AA。对称性：对任意公式A，B，若AB，则BA。可传递性：对任意公式A、B、C，若AB，BC，则AC。,（3）当A是重言式时，A1；当A是矛盾式时，则A0。,二、基本的等值式设P、Q、R是命题变元，下表中列出了24个最基本的等值式:,三、等值式的判别有两种方法：真值表方法，命题演算方法1、真值表方法,例1用真值表方法证明E10：(PQ)PQ,解令：A=(PQ)，B=PQ，构造A，B以及AB的真值表如下：,由于公式AB所标记的列全为1，因此AB。,0,例2用真值表方法证明E11：PQPQ,解令A=PQ，B=PQ构造A，B以及AB的真值表如下：,由于公式AB所标记的列全为1，因此AB.,例3用真值表方法判断PQPQ是否成立.,解令A=PQ，B=PQ构造A，B以及AB的真值表,由于公式AB所标记的列不全为1，AB不是永真公式，因此AB不成立。,(1)代入规则代入规则对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。,2等值演算方法,例如F=(PQ)(QP)是重言式，若用公式AB代换命题变元P得公式F1=(AB)Q)(Q(AB)，F1仍是重言式。,注意：因为AB当且仅当AB是重言式。所以，若对于等值式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等值式。,(2)置换规则定义1-10设C是命题公式A的一部分(即C是公式A中连续的几个符号)，且C本身也是一个命题公式，则称C为公式A的子公式。,例如设公式A=(PQ)(PQ)(RS)。,则PQ，PQ，(PQ)(RS)等均是A的子公式，,但P，P和Q等均不是A的子公式，,置换规则设C是公式A的子公式，CD。如果将公式A中的子公式C置换成公式D之后，得到的公式是B，则AB。,(3)等值演算等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。,由代入规则知前述的基本等值式，不仅对任意的命题变元P，Q，R是成立的，而且当P，Q，R分别为命题公式时，这些等值式也成立,例2证明命题公式的等值关系：(PQ)(RQ)(PR)Q；,证明(PQ)(RQ)(PQ)(RQ)E11(PR)QE3(分配律)(PR)QE10(德.摩根定律)(PR)QE11所以(PQ)(RQ)(PR)Q,例3证明下列命题公式的等值关系(PQ)(P(PQ)PQ,证明(PQ)(P(PQ)(PQ)(PP)Q)E2(结合律),(PQ)(PQ)E7(等幂律),(PQ)(PQ)E1(交换律),P(Q(PQ)E2(结合律),PQE1，E9(交换律，吸收律),例4判别下列公式的类型。（1）Q(P(PQ)（2）(PQ)P,解（1）Q(P(PQ)Q(P(PQ)E11,E6Q(PP)(PQ)E3Q(1(PQ)E5Q(PQ)E4QPQE10(QQ)PE1,E20E5,E8所以Q(P(PQ)是矛盾式。（2）(PQ)P(PQ)PE11PE9于是该公式是可满足式。,三、命题公式的蕴含关系定义1-11设A，B是两个公式，若公式AB是重言式，即AB1，则称公式A蕴含公式B，记作AB。称“AB”为蕴含式。,注意：符号“”和“”的区别和联系与符号“”与“”的区别和联系类似。,“”不是联结词，“AB”不是公式，它表示公式A与B之间存在蕴含关系。,“”是联系词，AB是一个公式。,AB当且仅当AB是永真公式。,AB是偏序关系,即自反性：AA。反对称：若AB，BA，则AB。传递性：若AB，BC，则AC。,反对称性的证明：设AB且BA，,由定义7-11AB1且BA1,于是AB(AB)(BA)E14111因此AB,传递性的证明：设AB，BC，,则AB1，BC1,(ABC)(ABC),(AB)C)(A(BC),(1C)(A1),111,因此AC.,于是ACAC,(AC)(BB),四、基本的蕴含式,五、蕴含式的判别判定“AB”是否成立的问题可转化为判定AB是否为重言式，有下述判定方法：,（1）真值表；（2）等值演算；（3）假定前件A为真；（4）假定后件B为假。,1.真值表方法,例4证明I14：(PQ)(PR)(QR)R,证明令公式F=(PQ)(PR)(QR)R，其真值表如下：,公式F对任意的一组真值指派取值均为1，故F是重言式。,2.等值演算方法例5证明I11：P（PQ）Q,证明(P(PQ)Q,(P(PQ)QE11,(P(PQ)QE10,(PQ)(PQ)E2,1代入规则,E5因此P（PQ）Q,3.假定前件A真假定前件A为真，检查在此情况下，其后件B是否也为真。,例6证明I12:Q（PQ）P,证明令前件Q（PQ）为真，,则Q为真,且PQ为真。,于是Q为假，因而P也为假。由此P为真。,故蕴含式I12成立。,4、假定后件B假假定后件B为假，检查在此情况下，其前件A是否也为假.,例7证明蕴含式(PQ)(RS)(PR)(QS),证明令后件(PR)(QS)为假，则PR为真，QS为假,于是P、R均为真，而Q和S至少一个为假。,由此可知PQ与RS中至少一个为假,因此(PQ)(RS)为假.,故上述蕴含式成立。,练习1-31判断下列等值式是否成立（1）(PQ)(RQ)(PR)Q（2）(PQ)(PQ)(PQ),解（1）(PQ)(RQ),(PQ)(RQ)E11,(PR)QE3,(PR)QE10,（2）(PQ)(PQ),(PQ)(QP)E6，E10,(PQ)(QP)E11,(PQ)E14,(PR)QE11,2判定蕴含式P(QR)(PQ)(PR)是否成立,解假定后件(PQ)(PR)为假，,则PQ为真，PR为假。,由PR为假,得P为真，R为假。,又PQ为真，故得Q为真。,于是P为真，QR为假。,从而P(QR)为假。,因此蕴含式成立。,范式一、析取范式和合取范式,定义1-12一个命题公式若它具有P1*P2*Pn*的形式（n1），其中Pi*是命题变元Pi或其否定Pi，则称其为质合取式(基本积)。例如,PQRS是由命题变元P、Q、R、S组成的一质合取式(基本积)。,定义1-13一个命题公式若具有P1*P2*Pn*（n1）的形式，其中P*i是命题变元Pi或是其否定Pi，则称其为质析取式(基本和)。例如,QPR是由命题变元P、Q、R组成的一质析取式(基本和)。,定理1-4(1)一质合取式为永假式的充分必要条件是，它同时包含某个命题变元P及其否定P。(2)一质析取式为永真式的充分必要条件是，它同时包含某个命题变元P及其否定P。,证明（2）必要性：假设A=P1*P2*Pn*为一质析取式，且A为一永真式。,(反证法)假设A式中不同时包含任一命题变元及其否定，,则在A中，当Pi*为Pi时指派Pi取0，当Pi*为Pi时，指派Pi取1。(i=1,2,n).这样的一组真值指派使A的真值取0，这与A为永真式矛盾。,例如A=P1P2P3.则(P1,P2,P3)=(0,1,0)的指派，使A的真值为0.,充分性：设A含命题变元Pi和Pi，而PiPi是永真式，由结合律和零一律，A的真值必为1，故A也是永真式。,定义1-14质合取式的析取称为析取范式。即具有A1A2An(n1)的形式的公式，其中Ai是质合取式。,例如，F1=P(PQ)R(PQR)是一析取范式。,定义1-15质析取式的合取称为合取范式。即具有A1A2An(n1)的形式的公式，其中Ai是质析取式。,例如，F2=P(PQ)R(PQR)是一合取范式。F3=(PRQ)(PQ)R(PR)也是一合取范式。,二、求公式的析取范式和合取范式,任何一个命题公式都可以变换为与它等值的析取范式或合取范式。按下列步骤进行：,（1）利用E11，E12和E14消去公式中的运算符“”和“”；,(2)利用德摩根定律将否定符号“”向内深入，使之只作用于命题变元；,（3）利用双重否定律E6将(P)置换成P；,（4）利用分配律、结合律将公式归约为合取范式或析取范式。,例1求F1=(P(QR)S的合取范式和析取范式,解F1(P(QR)SE11,P(QR)SE10,P(QR)S(析取范式)E10,E6,又F1P(QR)S,(PS)(QR)E1,E2,(PSQ)(PSR)（合取范式）E3,另外由F1(PSQ)(PSR),(P(PSR)(S(PSR)(Q(PSR)E3,PS(QP)(QS)(QR)（析取范式）E9,E13,例2求F2=(PQ)(PQ)的析取范式、合取范式。,解F2(PQ)(PQ)(PQ)(PQ)E14,(PQ)(PQ)(PQ)(PQ)E11,E6,(P(Q(PQ)(PQ(PQ)E2,E10,E10,(PQ)(PQ)（合取范式）E2,E9,(P(PQ)(Q(PQ)E3,(PP)(PQ)(PQ)(QQ)（析取范式）E3,定理1-5（1）公式A为永真式的充分必要条件是，A的合取范式中每一质析取式至少包含一对互为否定的析取项。,三、利用范式判定公式类型,证明（2）必要性（用反证法）：假设AA1A2An中某个Ai不包含一对互为否定的合取项，,（2）公式A为永假式的充分必要条件是，A的析取范式中每一质合取式至少包含一对互为否定的合取项。,则由定理7-4知，Ai不是矛盾式。,于是存在一组真值指派使Ai取值为真。,对同一组真值指派，A的取值也必为真，这与A是矛盾式不符，假设不成立。,充分性：假设任一Ai(1in)中含有形如PP合取式，其中P为命题变元。于是由定理7-4知，每一Ai(1in)都为矛盾式，因此A1A2An必为矛盾式，即A为矛盾式。,因此A的析取范式中每一质合取式至少包含一对互为否定的合取项。,例3判别公式A=P(P(QP)是否为重言式或矛盾式。,解AP(P(QP)E11,P(PQ)(PP)(析取范式)E3,根据定理7-5，A不是矛盾式。,又AP(P(QP),（PP）（PQP)（合取范式）E3,由定理1-5知，A是重言式。,例4利用范式判断公式P(PQ)的类型。,解P(PQ)(P(PQ)(P(PQ)E12,(PQ)(P(PQ)E10,(PQ)P(析取范式)E9,由定理1-5，该公式不是永假公式。,(PP)(PQ)（合取范式）E1，E3,由定理7-5，该公式也不是永真公式。,由上可知，该公式是一可满足公式。,又P(PQ)(PQ)P,四、主析取范式和主合取范式定义1-16设有命题变元P1，P2，,Pn，形如的命题公式称为是由命题变元P1，P2，Pn所产生的最小项。而形如的命题公式称为是由命题变元P1，P2，Pn所产生的最大项。其中Pi*为Pi或为Pi(i=1,2,n).,例如,P1P2P3，P1P2P3均是由P1，P2，P3所产生的最小项。P1P2P3是由P1，P2，P3产生的一个最大项。,定义1-17由不同最小项所组成的析取式，称为主析取范式。,定义1-18由不同最大项所组成的合取式，称为主合取范式。,例如(P1P2P3)(P1P2P3)(P1P2P3)是一个主析取范式。,(P1P2P3)(P1P2P3)(P1P2P3)(P1P2P3)是一个主合取范式。,例4求公式F1=P(P(QP)和公式F2=(PQ)(PQ)的主析取范式.,解F1P(P(QP)E11,P(PQ)(PP)E3,(P(QQ)(PQ)(P(QQ)E7,E4,E5,(PQ)(PQ)(PQ)(PQ)(PQ)E3,(PQ)(PQ)(PQ)(PQ)E1,E7,五、求公式的主析取范式和主合取范式对任一给定的公式除了用求范式时的四个步骤外，还要利用同一律、等幂律、互否律、分配律等进一步将质合取式（质析取式）变换为最小项（最大项）的形式。,F2(PQ)(PQ),(PQ)(PQ)E11,(PPQ)(QPQ)E3,定理1-6每一个不为永假的命题公式F（P1,P2,Pn）必与一个由P1，P2，Pn所产生的主析取范式等值。,永真公式的主析取范式包含所有2n个最小项。,永假公式的主析取范式是一个空公式。用0表示。,例5求公式F1=(PQ)(PQ)和公式F2=P(P(QP)的主合取范式,F1(PQ)(PQ)E11,(PQ)(P(QQ)(Q(PP)E5,E4,(PQ)(PQ)(PQ)(PQ)(PQ)E3,(PQ)(PQ)(PQ)(PQ)E7,解F2P(P(QP)E11,(PP)(PQP)E3,11E5,E1,1,定理1-7每一个不为永真的公式F(P1,P2,Pn)必与一个由P1,P2,Pn所产生的主合取范式等值。,永假公式的主合取范式包含所有2n个最大项。,永真公式的主合取范式是一空公式，用1表示。,六、利用主范式判定公式类型1.利用主析取范式判定,(1)若公式F(P1,P2，Pn)的主析取范式包含所有2n个最小项，则F是永真公式。例如，例4中的F1。,(2)若F的主析取范式是一空公式且为0，则F是永假公式。例如，例4中的F2。,(3)否则，F为可满足的公式。,2利用主合取范式判定,(1)若公式F（P1,P2,Pn）的主合取范式包含所有2n个最大项，则F是永假公式。例如，例5中的F1。,(2)若F的主合取范式是一空公式且为1，则F是永真公式。例如，例5中的F2。,(3)否则，F为可满足公式,例6求公式F=(Q(PQ)P的主范式并判定公式的类型.,解(1)求F的主析取范式,F(Q(PQ)P,Q(PQ)P,(Q(PP)(PQ)(P(QQ),（PQ)(PQ)(PQ)(PQ)(PQ),(PQ)(PQ)(PQ),由此可知F是可满足公式。,(2)求F的主合取范式,F（Q(PQ)P,PQ,由前分析和举例可知：仅需求出公式F的任一种主范式即可判定F的类型。,练习1-41判断公式F=(PQ)(PQ)是否为重言式或矛盾式？,解F(PQ)(PQ)(QP)E11,(PQ)(PQ)(QP)E10,E6,E11,(PQ)(P(QP)(Q(QP)E3,(PQ)(PQ)(PP)(QQ)(QP)E3,(PQ)(PQ)(QP)E5,E8,F的主析取范式既非空公式，又未包含22=4个项，故F不是重言式和矛盾式，只是可满足式。,命题演算的推理理论一、推理推理是由已知的命题得到新命题的思维过程。,定义1-19设A和B是两个命题公式，如果AB，即如果命题公式AB为重言式，则称B是前提A的结论或从A推出结论B。一般地设H1，H2，,Hn和C是一些命题公式,若蕴含式H1H2HnC(*)成立，则称C是前提集合H1，H2，,Hn的结论，或称从前提H1，H2，,Hn能推出结论C。有时也记作H1，H2，,HnC,1、真值表法对于命题公式中所有命题变元的每一组真值指派作出该公式的真值表，看是否为永真。,例1考察结论C是否是下列前提H1，H2的结论。（1）H1：PQ，H2：P，C：Q,二、如何判断由一个前提集合能否推出某个结论,（2）H1：PQ，H2：P，C：Q,在这里，我们不关心结论是真还是假，而主要关心由给定的前提是否能推出这个结论来。,2、等值演算方法例证明,分析根据题意，需证明,证明,3、“形式证明”方法（1）基本述语形式证明：一个描述推理过程的命题序列，其中每个命题或者是已知的命题，或者是由某些前提所推得的结论，序列中最后一个命题就是所要求的结论，这样的命题序列称为形式证明。,有效的证明：如果证明过程中的每一步所得到的结论都是根据推理规则得到的，则这样的证明称作是有效的。有效的结论：通过有效的证明而得到结论，称作是有效的结论。,合理的证明：一个证明是否有效与前提的真假没有关系。如果所有的前提都是真的，那么通过有效的证明所得到的结论也是真的。这样的证明称作是合理的。合理的结论：一个结论是否有效与它自身的真假没有关系。通过合理证明而得到的结论称作合理的结论。,(2)推理规则前提引用规则：在证明的任何步骤上都可以引用前提。结论引用规则：在证明的任何步骤上所得到的结论都可以在其后的证明中引用。,置换规则：在证明的任何步骤上，命题公式的子公式都可以用与它等值的其它命题公式置换。代入规则：在证明的任何步骤上，重言式中的任一命题变元都可以