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

《离散数学讲义第二章命题逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学讲义第二章命题逻辑.ppt（88页珍藏版）》请在三一办公上搜索。

1、第二章 命题逻辑 数理逻辑是用数学方法研究思维规律的一门学科。所谓数学方法是指:用一套数学的符号系统来描述和 处理思维的形式与规律。因此,数理逻辑又称为符号逻辑。本章介绍数理逻辑中最基本的内容命题逻辑。首先引入命题、命题公式等概念。然后,在此基础上研究命题公式间的等值关系和蕴含关系,并给出推理规则,进行命题演绎。主要内容如下：2.1 命题的概念和表示 2.2 逻辑联结词 2.3 命题演算的合适公式 2.4 等价与蕴含 2.5 对偶与范式 2.6 命题演算的推理理论,例1 判断下列语句是否是命题。（1）空气是人生存所必需的。（2）请把门关上。（3）南京是中国的首都。（4）你吃饭了吗？（5）x=3

2、。（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：如果明天天气晴朗，那么我们举行运

3、动会。,解 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

4、 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：

5、太阳从西边升起；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的

6、真值为假，Q的真值为真，所以PQ的真值为假。,对于上述五种联结词，应注意到：复合命题的真值只取决于构成它的各原子命题的真值，而与这些原子命题的内容含义无关。,命题符号化 利用联结词可以把许多日常语句符号化。基本步骤如下：,（1）从语句中分析出各原子命题，将它们符号化（2）使用合适的命题联结词，把原子命题逐个联结起来，组成复合命题的符号化表示。,例12 用符号形式表示下列命题。（1）如果明天早上下雨或下雪，那么我不去学校（2）如果明天早上不下雨且不下雪，那么我去学校。（3）如果明天早上不是雨夹雪，那么我去学校。（4）只有当明天早上不下雨且不下雪时，我才去学校。,解 令P：明天早上下雨；Q：明天早

7、上下雪；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：李明是文艺爱好者

8、。则命题可表示为（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：他听音乐。则该命题可

9、表示为（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）而产生的符号串是

10、命题公式。,例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不是,二、真值指派 命题公式代表一个命题，但只有当公式中的每一个命题变元

11、都用一个确定的命题代入时，命题公式才有确定的真值，成为命题。,定义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所

12、包含的命题变元的任何一组真值指派，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为等价式。,注

13、意：（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，因此A

14、B。,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是重言式。所以，若对于等价式中的任一命题变元出现的每一处均用同一命题公式

15、代入，则得到的仍是等价式。,(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分

16、别为命题公式时，这些等价式也成立,例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（

17、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是三个命题公式，

18、且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

19、代入规则,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判断下列等值式是否成立（

20、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功能完备集、其他联结词,问题：为了能构造任何意义的命题公式，究竟需要定义多少逻辑联结词？

21、,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的对偶式，

22、记为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 一个命题公式若具有P

23、1*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含命题变

24、元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)

25、利用德摩根定律将否定符号“”向内深入，使之只作用于命题变元；,（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

26、)(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不是矛盾式。,于是存在一组

27、真值指派使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)的类

28、型。,解 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所产生的极小项。P

29、1P2P3是由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,极小项、极小项的简记

30、：,极小项的性质：,1）每一个极小项mk在与其下标相对应的真值指派下真值为真，而在其余2n-1种真值指派下真值为假。,2）任意两个不同的极小项的合取式是一个永假式。,3）全部2n个极小项的析取式是一个重言式,极大项的性质：,1）每一个极大项Mk在与其下标相对应的真值指派下真值为假，而在其余2n-1种真值指派下真值为真。2）任意两个不同的极大项的析取式是一个永真式3）全部2n个极大项的合取式是一个矛盾式,由不同极小项所组成的析取式，称为主析取范式。,定义7-18由不同极大项所组成的合取式，称为主合取范式。,例如(P1P2P3)(P1P2P3)(P1P2P3)是一个主析取范式。,(P1P2P3)(

31、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所产生的主合取范式等价。,永假公式的主合取范式包含

32、所有 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)

33、(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）的主合取范式包含所有2

34、n个最大项，则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)(

35、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、如果李敏出差到学校，若王军不生病，则王军一定去看望李敏。如果李敏出差到长沙，那么李敏一定来学校。王军没有生病。所以，_,一、推理 推理是由已

36、知的命题得到新命题的思维过程。,设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、真

37、值演算方法例 证明,分析根据题意，需证明,证明,3、“形式证明”方法（1）基本述语 形式证明：一个描述推理过程的命题序列，其中每个命题或者是已知的命题，或者是由某些前提所推得的结论，序列中最后一个命题就是所要求的结论，这样的命题序列称为形式证明。,有效的证明：如果证明过程中的每一步所得到的结论都是根据推理规则得到的，则这样的证明称作是有效的。有效的结论：通过有效的证明而得到结论，称作是有效的结论。,合理的证明：一个证明是否有效与前提的真假没有关系。如果所有的前提都是真的，那么通过有效的证明所得到的结论也是真的。这样的证明称作是合理的。合理的结论：一个结论是否有效与它自身的真假没有关系。通过合理

38、证明而得到的结论称作合理的结论。,(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的结论。,因此，（P

39、Q）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 H2H

40、n是矛盾式，则称公式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、P

41、Q 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）。下面根据已知前提进行形式推理。,因此，由上述推理知张三说假话，王五说假话，只有李四说真话。,