离散数学讲义第二章命题逻辑.ppt

第二章 命题逻辑 数理逻辑是用数学方法研究思维规律的一门学科。所谓数学方法是指:用一套数学的符号系统来描述和 处理思维的形式与规律。因此,数理逻辑又称为符号逻辑。本章介绍数理逻辑中最基本的内容命题逻辑。首先引入命题、命题公式等概念。然后,在此基础上研究命题公式间的等值关系和蕴含关系,并给出推理规则,进行命题演绎。主要内容如下：2.1 命题的概念和表示 2.2 逻辑联结词 2.3 命题演算的合适公式 2.4 等价与蕴含 2.5 对偶与范式 2.6 命题演算的推理理论,例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是命题,原子命题：由简单句形成的命题。,复合命题：由一个或几个原子命题通过联结词的联接而构成的命题。,例3 A：李明是三好学生。B：李明既是三好学生又是足球队员 C:明天天气晴朗.D：张平或者正在钓鱼或者正在睡觉。E：如果明天天气晴朗，那么我们举行运动会。,解 A、C是原子命题 B、D、E是复合命题,2.2 逻辑联结词,1.否定“”,设P是一个命题，则P的否定是一个复合命题，称为P的否命题，记作“P”(读作“非P”)。,例4 设P：上海是一个城市；Q：每个自然数都是偶数。则有 P：上海不是一个城市;Q：并非每个自然数都是偶数。,命题P取值为真时，命题P取值为假；命题P取值为假时，命题P取值为真。,2合取“”定义2.2.2 设P和Q是两个命题，则P和Q的合取是一个复合命题，记作“P Q”（读作“P且Q”）。,例5 设P：我们去看电影。Q：房间里有十张桌子。则P Q表示“我们去看电影并且房间里有十张桌子。”,当且仅当命题P和Q均取值为真时，P Q才取值为真。,3.析取“”定义2.2.3 设P和Q是两个命题，则P和Q的析取是一个复合命题，记作“PQ”（读作“P或Q”）。,例6 设命题P：他可能是100米赛跑冠军；Q：他可能是400米赛跑冠军。,则命题PQ表示：他可能是100米或400米赛跑的冠军。,当且仅当P和Q至少有一个取值为真时，PQ取值为真。,4.蕴含“”定义2.2.4 设P和Q是两个命题，则它们的条件命题是一个复合命题，记作“PQ”（读作“如果P，则Q”）。,例9 将命题“如果我得到这本小说，那么我今夜就读完它。”符号化。,解 令P：我得到这本小说；Q：我今夜就读完它。于是上述命题可表示为PQ。,例8 若P：雪是黑色的；Q：太阳从西边升起；R：太阳从东边升起。则PQ和PR所表示的命题都是真的.,当P为真，Q为假时，PQ为假，否则 PQ为真。,5等值“”定义2.2.5 设P和Q是两个命题，则它们的等值命题是一个复合命题，称为等值式复合命题，记作“P Q”（读作“P当且仅当Q”）。,当P和Q的真值相同时,PQ取真,否则取假。,例10 非本仓库工作人员，一律不得入内。,解 令P：某人是仓库工作人员；Q：某人可以进入仓库。,则上述命题可表示为P Q。,例11 黄山比喜马拉雅山高，当且仅当3是素数 令P：黄山比喜马拉雅山高；Q：3是素数 本例可符号化为PQ,从汉语的语义看，P与Q之间并无联系，但就联结词的定义来看，因为P的真值为假，Q的真值为真，所以PQ的真值为假。,对于上述五种联结词，应注意到：复合命题的真值只取决于构成它的各原子命题的真值，而与这些原子命题的内容含义无关。,命题符号化 利用联结词可以把许多日常语句符号化。基本步骤如下：,（1）从语句中分析出各原子命题，将它们符号化（2）使用合适的命题联结词，把原子命题逐个联结起来，组成复合命题的符号化表示。,例12 用符号形式表示下列命题。（1）如果明天早上下雨或下雪，那么我不去学校（2）如果明天早上不下雨且不下雪，那么我去学校。（3）如果明天早上不是雨夹雪，那么我去学校。（4）只有当明天早上不下雨且不下雪时，我才去学校。,解 令P：明天早上下雨；Q：明天早上下雪；R：我去学校。,（1）（PQ）R；（2）（P Q）R；（3）(PQ）R（4）R（P Q）,例13将下列命题符号化（1）派小王或小李出差；（2）我们不能既划船又跑步；（3）如果你来了，那么他唱不唱歌将看你是否伴奏而定；（4）如果李明是体育爱好者，但不是文艺爱好者，那么 李明不是文体爱好者；（5）假如上午不下雨，我去看电影，否则就在家里看书。,解（1）令P：派小王出差；Q：派小李出差。命题符号化为PQ。,（2）令P：我们划船；Q：我们跑步。则命题可 表示为(PQ）。,（3）令P：你来了；Q：他唱歌；R：你伴奏。则命题可表示为 P（Q R）,（4）令P：李明是体育爱好者；Q：李明是文艺爱好者。则命题可表示为（P Q）（P Q）,（5）令P：上午下雨；Q：我去看电影；R：我在家读书。则命题可表示为（P Q）（PR）。,练习2-2 1.判断下列语句哪些是命题，若是命题，则指出其真值。（1）只有小孩才爱哭。（2）X+6=Y（3）银是白的。（4）起来吧，我的朋友。,(是 假),(不是),(是 真),(不是),2 将下列命题符号化（1）我看见的既不是小张也不是老李。,解 令P：我看见的是小张；Q：我看见的是老李。,则该命题可表示为PQ,（2）如果晚上做完了作业并且没有其它的事，他就会看电视或听音乐。,解 令 P：他晚上做完了作业；Q：他晚上有其它的事；R：他看电视；S：他听音乐。则该命题可表示为（PQ）（RS）,2.3 命题演算的合适公式 一、命题公式的概念 1.命题常元 一个表示确定命题的大写字母。,2命题变元 一个没有指定具体内容的命题符号。,一个命题变元当没有对其赋予内容时，它的真值不能确定，一旦用一个具体的命题代入，它的真值就确定了。,3.命题公式 命题公式（或简称公式）是由0、1和命题变元以及命题联结词按一定的规则产生的符号串。,（命题公式的递归定义。）（1）0，1是命题公式；（2）命题变元是命题公式；（3）如果A是命题公式，则A是命题公式；（4）如果A和B是命题公式，则（AB），（AB）,(AB）,(A B）也是命题公式；有限次地利用上述（1）（4）而产生的符号串是命题公式。,例1 判断下列符号串是否为命题公式。（1）P(QPR）；（2）（PQ）（QR）,解（1）不是命题公式。（2）是命题公式。,4.代入实例 定义2.3.2 设A和B是两个命题公式，如果将A中的某些命题变元用命题公式进行代换便可得到B，并且此种代换满足：（1）被代换的是命题变元；（2）如果要代换某个命题变元，则要将该命题变元在A中的一切出现进行代换（3）代换必须同时独立地进行 则称B是A的一个代入实例,例2 设A=P(Q P）,判断下列命题公式是否是A的代入实例：B=SR(Q(SR)）C=SR(Q P）,解 B是；C不是,二、真值指派 命题公式代表一个命题，但只有当公式中的每一个命题变元都用一个确定的命题代入时，命题公式才有确定的真值，成为命题。,定义2.3.3 设A(P1，P2，,Pn)是一个命题公式，P1，P2，,Pn是出现于其中的全部命题变元，对P1，P2，,Pn分别指定一个真值,称为对P1，P2，,Pn公式A的一组真值指派。,列出命题公式A在P1，P2，,Pn的所有2n种真值指派下对应的真值，这样的表称为A的真值表。,例3 给出公式 F=(（PQ）（QR）)(PR）的真值表。,解 公式F的真值表如下：,三、公式类型 定义2.3.5 如果对于命题公式F所包含的命题变元的任何一组真值指派，F的真值恒为真，则称公式F为重言式（或永真公式），常用“1”表示。相反地，若对于F所包含的命题变元的任何一组真值指派，F的真值恒为假，则称公式F为矛盾式（或永假公式），常用“0”表示。如果至少有一组真值指派使公式F的真值为真，则称F为可满足公式。,例4 构造下列命题公式的真值表，并判断它们是何种类型的公式（1）（P Q）（P Q）；（2）（QP）（PQ）；（3）（PQ）（QR）（PR）。,由上可知：F1是重言式,F2是矛盾式。,2.4 等价与蕴含,一、命题公式的等价关系 定义2.4.1 设A和B是两个命题公式,P1,P2,Pn 是所有出现于A和B中的命题变元，如果对于P1,P2,Pn 的任一组真值指派，A和B的真值都相同,则称公式A和B等价，记为A B,称 AB为等价式。,注意：（1）符号“”与“”的区别与联系。,（2）可以验证等价关系满足：自反性：对任意公式A，有AA。对称性：对任意公式A，B，若AB，则BA。可传递性：对任意公式A、B、C，若AB，BC，则AC。,（3）当A是重言式时，A1；当A是矛盾式时，则A0。,定理2.4.1 A B当且仅当A B是永真公式。,二、基本的等价式 设P、Q、R是命题变元，下表中列出了24个最基本的等价式:,三、等价式的判别 有两种方法：真值表方法，命题演算方法1、真值表方法,例1 用真值表方法证明 E10：(PQ)PQ,解 令：A=(PQ)，B=PQ，构造A，B 以及A B的真值表如下：,由于公式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仍是重言式。,注意：因为A B当且仅当A B是重言式。所以，若对于等价式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等价式。,(2)置换规则 设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（P R）Q E3(分配律)(PR)Q E10(德.摩根定律)(PR)Q E11 所以（PQ）（RQ）（PR）Q,例3 证明下列命题公式的等价关系(P Q)(P(P Q)P Q,证明(PQ)(P(PQ)(PQ)(P P)Q)E2(结合律),(PQ)(PQ)E7(等幂律),(P Q)(PQ)E1(交换律),P(Q(PQ)E2(结合律),PQ E1，E9(交换律，吸收律),例4 判别下列公式的类型。（1）Q(P（PQ）)（2）（PQ）P,解（1）Q（P（PQ）Q（P（PQ）E11,E6 Q（PP）（PQ）E3 Q（1（PQ）E5 Q（PQ）E4 QPQ E10（QQ）P E1,E2 0 E5,E8 所以Q(P(PQ)是矛盾式。（2）（PQ）P（PQ）P E11 P E9 于是该公式是可满足式。,三、命题公式的蕴含关系 设A，B是两个公式，若公式AB是重言式，即AB1，则称公式A蕴含公式B，记作AB。称“AB”为蕴含式。,注意：（1）符号“”和“”的区别和联系,（2）AB是偏序关系,即 自反性：AA 反对称：若AB，BA，则AB 传递性：若AB，BC，则 AC,（3）若A、B和C是三个命题公式，且AB，A C，则ABC,（4）若A、B和C是三个命题公式，且A C，B C，则A B C,定理2.4.2 A B当且仅当A B是永真公式。,四、基本的蕴含式,五、蕴含式的判别 判定“A B”是否成立的问题可转化为判定A B是否为重言式，有下述判定方法：,（1）真值表；（2）等价演算；（3）假定前件A为真；（4）假定后件B为假。,1.真值表方法,例4 证明I14：(（PQ）（P R）（Q R）)R,证明 令公式 F=（PQ）（PR）（QR）R，其真值表如下：,公式F对任意的一组真值指派取值均为1，故F是重言式。,2.等价演算方法 例5 证明 I11：P（PQ）Q,证明（P（PQ）Q,（P（PQ）Q E11,（P（PQ）E10,（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)为假.,故上述蕴含式成立。,练习 2-41判断下列等值式是否成立（1）（PQ）（R Q）（PR）Q（2）（PQ）（P Q）（PQ）,解（1）（PQ）（RQ）,（PQ）（RQ）E11,（PR）Q E3,（PR）Q E10,（2）（PQ）（PQ）,(（PQ）（QP）)E6，E10,(（PQ）（QP）)E11,（PQ）E14,（PR）Q E11,2判定蕴含式P（QR）（PQ）（PR）是否成立,解假定后件（PQ）（PR）为假，,则PQ为真，PR为假。,由PR为假,得P为真，R为假。,又PQ为真，故得Q为真。,于是P为真，QR为假。,从而 P（QR）为假。,因此蕴含式成立。,2.5功能完备集、其他联结词,问题：为了能构造任何意义的命题公式，究竟需要定义多少逻辑联结词？,A0=F A1=PQ A2=P Q A3=P A4=PQA5=Q A6=（P Q）（P Q）A7=P Q,定义2.5.1 设S是一个由一些逻辑联结词组成的集合，若对于任意给定的命题公式，总可以找到一个仅含有S中的逻辑联结词的命题公式与之等价，则称S是一个联结词功能完备集。,定义2.5.2 设S是一个联结词功能完备集，若S中的任一联结词都不能用S中的其他联结词等价表达，则称S是一个极小的联结词功能完备集。,例，,，是极小的联结词功能完备集,2.6对偶与范式一、对偶,定义2.6.1 设A是一个仅含有联结词、和的命题公式，在A中用代替，用代替，用T代替F,用F代替T，所得的命题公式称为A的对偶式，记为A*。,例如：PQ R和（P Q）R互为对偶式,PQR的对偶式是,(P Q)R,定理2.6.1 设A是一个仅含有联结词、和的命题公式，P1，P2.Pn是出现于其中的全部命题变元，则 A(P1，P2.Pn)A*(P1，P2.Pn)A(P1，P2.Pn)A*(P1，P2.Pn),定理2.6.2 设A和B是两个仅含有联结词、和的命题公式，如果A B，则A*B*。,二、范式1、析取范式和合取范式,一个命题公式若具有P1*P2*Pn*的形式（n1），其中Pi*是命题变元Pi或其否定Pi，则称其为质合取式。例如,PQRS是由命题变元P、Q、R、S组成的一质合取式。,定义2.6.3 一个命题公式若具有P1*P2*Pn*（n1）的形式，其中P*i是命题变元Pi或是其否定Pi，则称其为质析取式。例如,QPR是由命题变元P、Q、R组成的一质析取式。,（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含命题变元Pi和Pi，而PiPi是永真式，由结合律和零一律，A的真值必为1，故A也是永真式。,质合取式的析取称为析取范式。即具有A1A2An(n1)的形式的公式，其中Ai是质合取式。,例如，F1=P(PQ)R(PQR)是一析取范式。,定义 质析取式的合取称为合取范式。即具有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)S E11,P(QR)S E10,P(QR)S(析取范式)E10,E6,又 F1 P(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）公式A为永真式的充分必要条件是，A的合取范式中每一质析取式至少包含一对互为否定的析取项。,三、利用范式判定公式类型,证明（2）必要性（用反证法）：假设AA1A2An中某个Ai不包含一对互为否定的合取项，,（2）公式A为永假式的充分必要条件是，A的析取范式中每一质合取式至少包含一对互为否定的合取项。,则由定理知，Ai不是矛盾式。,于是存在一组真值指派使Ai取值为真。,对同一组真值指派，A的取值也必为真，这与A是矛盾式不符，假设不成立。,充分性：假设任一Ai(1in)中含有形如PP合取式，其中P为命题变元。于是由定理知，每一Ai(1in)都为矛盾式，因此A1A2An必为矛盾式，即A为矛盾式。,因此A的析取范式中每一质合取式至少包含一对互为否定的合取项。,例3 判别公式A=P(P(QP)是否为重言式或矛盾式。,解 A P(P(QP)E11,P(PQ)(PP)(析取范式)E3,根据定理2.6.4，A不是矛盾式。,又AP(P(QP),（PP）（PQP)（合取范式）E3,由定理2.6.4知，A是重言式。,例4 利用范式判断公式P(PQ)的类型。,解 P(PQ)(P(PQ)(P(PQ)E12,(PQ)(P(PQ)E10,(PQ)P(析取范式)E9,由定理，该公式不是永假公式。,(PP)(PQ)（合取范式）E1，E3,由定理，该公式也不是永真公式。,由上可知，该公式是一可满足公式。,又 P(PQ)(PQ)P,四、主析取范式和主合取范式（一）极小项、极大项 设有命题变元P1，P2，,Pn，形如 的命题公式称为是由命题变元P 1，P2，Pn所产生的极小项。而形如 的命题公式称为是由命题变元P1，P2，Pn所产生的极大项。其中Pi*为Pi或为Pi(i=1,2,n).,例如,P1P2P3，P1P2P3均是由P1，P2，P3所产生的极小项。P1P2P3是由P1，P2，P3产生的一个极大项,常用mk(0k2n-1)表示极小项，其中k为二进制t1t2.tn对应的十进制。且若Pi*为Pi,ti=0.否则Pi*为1。,例如，三个命题变元P,Q,R共形成八个极小项 m0=PQR，m1=PQR，m2=PQR m3=PQR，m4=PQR，m5=PQR m6=PQR，m7=PQR,常用Mk(0k2n-1)表示极大项，其中k为二进制t1t2.tn对应的十进制。且若Pi*为Pi,ti=1.否则Pi*为0。,M0=PQ R，M1=P Q R，M2=P Q R M3=PQ R，M4=PQR，M5=PQ R M6=PQR，M7=PQR,极小项、极小项的简记：,极小项的性质：,1）每一个极小项mk在与其下标相对应的真值指派下真值为真，而在其余2n-1种真值指派下真值为假。,2）任意两个不同的极小项的合取式是一个永假式。,3）全部2n个极小项的析取式是一个重言式,极大项的性质：,1）每一个极大项Mk在与其下标相对应的真值指派下真值为假，而在其余2n-1种真值指派下真值为真。2）任意两个不同的极大项的析取式是一个永真式3）全部2n个极大项的合取式是一个矛盾式,由不同极小项所组成的析取式，称为主析取范式。,定义7-18由不同极大项所组成的合取式，称为主合取范式。,例如(P1P2P3)(P1P2P3)(P1P2P3)是一个主析取范式。,(P1P2P3)(P1P2P3)(P1P2P3)(P1P2P3)是一个主合取范式。,五、求公式的主析取范式和主合取范式(一）真值表法,例：(PQ)(P R)(PQ R)(PQ R)(P Q R)(P Q R)m2 m3 m5 m7(P Q R)(P Q R)(P Q R)(P Q R)M0 M1 M4 M6,每一个不为永假的命题公式F（P1,P2,Pn）必与一个由P1，P2，Pn所产生的主析取范式等价。,永真公式的主析取范式包含所有2n个最小项。,永假公式的主析取范式是一个空公式。用0表示。,每一个不为永真的公式 F(P1,P2,Pn）必与一个由P1,P2,Pn所产生的主合取范式等价。,永假公式的主合取范式包含所有 2n个最大项。,永真公式的主合取范式是一空公式，用1表示。,例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,例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,解 F2 P(P(QP)E11,(PP)(PQP)E3,11 E5,E1,1,六、利用主范式判定公式类型 1.利用主析取范式判定,(1)若公式 F(P1,P2，Pn)的主析取范式包含所有2n个最小项，则 F是永真公式。,(2)若 F的主析取范式是一空公式且为0，则 F是永假公式。,(3)否则，F为可满足的公式。,2 利用主合取范式判定,(1)若公式F（P1,P2,Pn）的主合取范式包含所有2n个最大项，则F是永假公式。,(2)若F的主合取范式是一空公式且为1，则F是永真公式。,(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的类型。,练习 2-6 1判断公式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不是重言式和矛盾式，只是可满足式。,2.7 命题演算的推理理论,3、如果甲是冠军，则乙或丙将得亚军；如果乙得亚军，则甲不能得冠军；如果丁得亚军，丙不能得亚军；事实是甲已得冠军，可知_不能得亚军。,例 1、如果天不下雨，我就去看电影；我没有去看电影，说明_,2、如果李敏出差到学校，若王军不生病，则王军一定去看望李敏。如果李敏出差到长沙，那么李敏一定来学校。王军没有生病。所以，_,一、推理 推理是由已知的命题得到新命题的思维过程。,设A和B是两个命题公式，如果AB，即如果命题公式AB为重言式，则称B是前提A的结论或从A推出结论B。一般地设H1，H2，,Hn和C是一些命题公式,若蕴含式H1H2Hn C(*)成立，则称C是前提集合 H1，H2，,Hn的结论，或称从前提H1，H2，,Hn能推出结论C。有时也记作H1，H2，,Hn C,1、真值表法 对于命题公式 中所有命题变元的每一组真值指派作出该公式的真值表，看是否为永真。,例1 考察结论C是否是下列前提H1，H2的结论。（1）H1：PQ，H2：P，C：Q,二、如何判断由一个前提集合能否推出某个结论?,（2）H1：PQ，H2：P，C：Q,2、真值演算方法例 证明,分析根据题意，需证明,证明,3、“形式证明”方法（1）基本述语 形式证明：一个描述推理过程的命题序列，其中每个命题或者是已知的命题，或者是由某些前提所推得的结论，序列中最后一个命题就是所要求的结论，这样的命题序列称为形式证明。,有效的证明：如果证明过程中的每一步所得到的结论都是根据推理规则得到的，则这样的证明称作是有效的。有效的结论：通过有效的证明而得到结论，称作是有效的结论。,合理的证明：一个证明是否有效与前提的真假没有关系。如果所有的前提都是真的，那么通过有效的证明所得到的结论也是真的。这样的证明称作是合理的。合理的结论：一个结论是否有效与它自身的真假没有关系。通过合理证明而得到的结论称作合理的结论。,(2)推理规则 前提引用规则(P规则）：在证明的任何步骤上都可以引用前提。结论引用规则（T规则）：在证明的任何步骤上所得到的结论都可以在其后的证明中引用。,置换规则：在证明的任何步骤上，命题公式的子公式都可以用与它等价的其它命题公式置换。代入规则：在证明的任何步骤上，重言式中的任一命题变元都可以用一命题公式代入，得到的仍是重言式。,例2 证明 R（PQ）是前提PQ，QR，PS，S的结论。,所以PQ，QR，PS，S R（PQ),例3 证明RS是前提P（QS），RP和Q的有效结论。,练习 用形式证明方法证明：（1）PQ是前提（PQ）R，RS，S的结论。,因此，（PQ）R，RS，S P Q,CP规则：利用永真蕴含式：要证明P Q R，则等价于证明P Q R 将例3等价地改为证明由前提 推出结论 S。,例4 符号化下面语句的推理过程，并指出推理是否正确。“如果甲是冠军，则乙或丙将得亚军；如果乙得亚军，则甲不能得冠军；如果丁得亚军，丙不能得亚军；事实是甲已得冠军，可知丁不能得亚军”。,解 设 A：甲得冠军；B：乙得亚军；C：丙得亚军；D：丁得亚军。,推理过程符号化为 A（BC），B A，DC，A D,4、间接证明(或反证法),如果对于出现在公式H1，H2，,Hn中的命题变元的任何一组真值指派，公式H1，H2，,Hn中至少有一个为假，即它们的合取式H1 H2Hn是矛盾式，则称公式H1，H2，Hn是不相容的。否则称公式H1，H2,Hn是相容的。,若存在一个公式R，使得 H1H2 Hn R R则公式H1，H2，,Hn是不相容的。,证明 设H1 H2Hn=R R，,而RR是矛盾式，所以前件H1Hn必永假。因此，H1，H2，,Hn是不相容的。,则意味着（H1 H2Hn）（RR）是重言式，,为了证明H1、H2、H nC，利用定理2.7.1，将C添加到这一组前提中，转化为证明 H1H2HnC RR,于是得出H1、H2、Hn、C是不相容的。,即H1H2HnC是永假公式。,这意味着当H1H2Hn为真时，C必为假，因而C必为真。,例5 证明：R Q、RS、S Q、PQ P,用反证法，将（P）作为附加前提，添加到前提集合中，然后推出矛盾。证明,因此（RQ）（RS）（S Q）（PQ)P,习题2-71判断下列推理是否正确 如果这里有球赛，则通行是困难的；如果他们按指定的时间到达，则通行是不困难的；他们按指定时间到达了，所以这里没有球赛。,解 先将已知条件符号化,令P：这里有球赛；Q：通行是困难的；R：他们按指定的时间到达了。,编 号 公 式 依 据（1）RQ P,因此上述推理正确。,（2）R P,（3）Q T（1），（2）,I,（4）PQ P,（5）P T（3），（4）,I,则上述推理过程符号化为P Q，R Q，R P,2.张三说李四在说谎，李四说王五在说谎，王五说张三、李四都在说谎。问张三、李四、王五三人，到底谁说真话，谁说假话？,解 先将简单命题符号化。令P：张三说真话；Q：李四说真话；R：王五说真话，由题意知推理的前提为：P Q，PQ，QR，QR，R（P Q），R（PQ）。下面根据已知前提进行形式推理。,因此，由上述推理知张三说假话，王五说假话，只有李四说真话。,