第九章离散数学课件

1 1第九章第九章命题逻辑命题逻辑数理逻辑是用数学方法研究思维规律的一门学科。数理逻辑是用数学方法研究思维规律的一门学科。所谓数学方法是指所谓数学方法是指:用一套数学的符号系统来描述和用一套数学的符号系统来描述和处处理思维的形式与规律。因此理思维的形式与规律。因此,数理逻辑又称为符号逻辑。数理逻辑又称为符号逻辑。本章介绍数理逻辑中最基本的内容命题逻辑。首先引入本章介绍数理逻辑中最基本的内容命题逻辑。首先引入命题、命题公式等概念。然后命题、命题公式等概念。然后,在此基础上研究命题公在此基础上研究命题公式间的等值关系和蕴含关系式间的等值关系和蕴含关系,并给出推理规则并给出推理规则,进行命题进行命题演绎。演绎。主要内容如下：主要内容如下：9.1命题和命题联结词命题和命题联结词9.2命题公式命题公式9.3命题公式的等值关系和蕴含关系命题公式的等值关系和蕴含关系9.4范式范式9.5命题演算的推理理论命题演算的推理理论2 29.1命题和命题联结词命题和命题联结词一、一、命题的概念命题的概念命题命题：是能分辨真假的陈述句。是能分辨真假的陈述句。例例1判断下列语句是否是命题。判断下列语句是否是命题。（1）空气是人生存所必需的。）空气是人生存所必需的。（2）请把门关上。）请把门关上。（3）南京是中国的首都。）南京是中国的首都。（4）你吃饭了吗？）你吃饭了吗？（5）x=3。（。（6）啊，真美呀！啊，真美呀！(7)明年春节是个大晴天。明年春节是个大晴天。解解 语句（语句（1）,（3）,（5），），(7)(7)是陈述句是陈述句（1）、（）、（3）、）、(7)(7)是命题是命题 用真值来描述命题是用真值来描述命题是“真真”还是还是“假假”。分别用。分别用“1”和和“0”0”表示表示命题用大写的拉丁字母命题用大写的拉丁字母A、B、C、P、Q、或或者带下标的大写的字母来表示。者带下标的大写的字母来表示。例例2判断下列陈述句是否是命题。判断下列陈述句是否是命题。P：地球外的星球上也有人；地球外的星球上也有人；Q：小王是我的好朋友；小王是我的好朋友；解解 P、Q是命题是命题3 3二、命题联结词二、命题联结词 原子命题原子命题：由简单句形成的命题。由简单句形成的命题。复合命题：复合命题：由一个或几个原子命题通过联结词由一个或几个原子命题通过联结词的联接而构成的命题。的联接而构成的命题。例例3A：李明既是三好学生又是足球队员。李明既是三好学生又是足球队员。B：张平或者正在钓鱼或者正在睡觉。张平或者正在钓鱼或者正在睡觉。C：如果明天天气晴朗，那么我们举行运动会。如果明天天气晴朗，那么我们举行运动会。4 4定义五种联结词（或称命题的五种运算）。定义五种联结词（或称命题的五种运算）。1.否定否定“”定义定义9-1设设P是一个命题，利用是一个命题，利用“”和和P组成的组成的复合命题称为复合命题称为P的否命题，记作的否命题，记作“P”(读作读作“非非P”)。命题命题P P取值为真时，命题取值为真时，命题PP取值为假；命题取值为假；命题P P取值为假时，取值为假时，命题命题PP取值为真。取值为真。例例4设设P：上海是一个城市；上海是一个城市；Q：每个自然数都是偶数。每个自然数都是偶数。则有则有 P：上海不是一个城市上海不是一个城市;Q：并非每个自然数都是偶数。并非每个自然数都是偶数。PPP10015 52合取合取“”定义定义9-2设设P和和Q是两个命题，由是两个命题，由P、Q利用利用“”组成的复合命题，称为合取式复合命题，记作组成的复合命题，称为合取式复合命题，记作“PQ”（读作读作“P且且Q”）。）。当且仅当命题当且仅当命题P P和和Q Q均取值为真时，均取值为真时，P P Q Q才取值为真。才取值为真。例例5 5 设设P P：我们去看电影。我们去看电影。Q Q：房间里有十张桌子。则房间里有十张桌子。则P P Q Q表示表示“我们去看电影并且房间里有十张桌子。我们去看电影并且房间里有十张桌子。”PQPQ0000101001116 63.析取析取“”定义定义9-39-3 由命题由命题P P和和Q Q利用利用“”组成的复合命题，称组成的复合命题，称为析取式复合命题，记作为析取式复合命题，记作“PQ”PQ”（读作读作“P P或或Q”Q”）。）。当且仅当当且仅当P P和和Q Q至少有一个取值为真时，至少有一个取值为真时，PQPQ取值为真。取值为真。PQPQ000011101111例例6将命题将命题“他可能是他可能是100米或米或400米赛跑的冠军。米赛跑的冠军。”符号符号化。化。解解令令P：他可能是他可能是100米赛跑冠军；米赛跑冠军；Q Q：他可能是他可能是400400米赛跑冠军。米赛跑冠军。则命题可表示为则命题可表示为PQ。7 7设设P P、Q Q是两个命题，是两个命题，P P异或异或Q Q是一个复合命题，记作是一个复合命题，记作PQPQ。例例7今天晚上我在家看电视或去剧场看戏。今天晚上我在家看电视或去剧场看戏。令令P：今天晚上我在家看电视。今天晚上我在家看电视。Q：今天晚上我去剧场看戏今天晚上我去剧场看戏例例7中的命题可表示为中的命题可表示为PQ，或者表示为或者表示为（PQ(PQ)。由于由于“”可用可用“”，“”和和“”表示，故表示，故我们不把它当作我们不把它当作基本基本联结词。联结词。PQPQ0000111011108 84.蕴含蕴含“”定义定义9-49-4由命题由命题P P和和Q Q利用利用“”组成的复合命题，组成的复合命题，称为蕴含式复合命题，记作称为蕴含式复合命题，记作“PQ”PQ”（读作读作“如果如果P P，则，则Q”Q”）。）。当当P为真，为真，Q为假时，为假时，PQ为假，否则为假，否则PQPQ为真。为真。PQPQ001011100111例例8将命题将命题“如果我得到这本小说，那么我今夜如果我得到这本小说，那么我今夜就读完它。就读完它。”符号化。符号化。解解令令P：我得到这本小说；我得到这本小说；Q：我今夜就读完它。我今夜就读完它。于是上述命题可表示为于是上述命题可表示为PQPQ。例例9若若P：雪是黑色的；雪是黑色的；Q：太阳从西边升起；太阳从西边升起；R：太阳从东边升起。太阳从东边升起。则则PQPQ和和PRPR所表示的命题都是真的所表示的命题都是真的.9 95等值等值“”定义定义9-5由命题由命题P和和Q，利用利用“”组成的复合组成的复合命题，称为等值式复合命题，记作命题，称为等值式复合命题，记作“PQ”（读作读作“P当且仅当当且仅当Q”）。）。当当P P和和Q Q的真值相同时的真值相同时,P,PQ Q取真取真,否则取假。否则取假。PQPQ001010100111例例10非本仓库工作人员，一律不得入内。非本仓库工作人员，一律不得入内。解解令令P：某人是仓库工作人员；某人是仓库工作人员；Q Q：某人可以进入仓库。某人可以进入仓库。则上述命题可表示为则上述命题可表示为PQ。1010例例1111 黄山比喜马拉雅山高，当且仅当黄山比喜马拉雅山高，当且仅当3 3是素数是素数 令令P P：黄山比喜马拉雅山高；黄山比喜马拉雅山高；Q Q：3 3是素数是素数 本例可符号化为本例可符号化为P PQ Q 从汉语的语义看，从汉语的语义看，P与与Q之间并无联系，但就联结之间并无联系，但就联结词词的定义来看，因为的定义来看，因为P的真值为假，的真值为假，Q的真值为真，的真值为真，所以所以PQ的真值为假。的真值为假。对于上述五种联结词，应注意到：对于上述五种联结词，应注意到：复合命题的真值只取决于构成它的各原子命题的真复合命题的真值只取决于构成它的各原子命题的真值，而与这些原子命题的内容含义无关。值，而与这些原子命题的内容含义无关。1111三、命题符号化三、命题符号化利用联结词可以把许多日常语句符号化。基本步骤如下：利用联结词可以把许多日常语句符号化。基本步骤如下：（1 1）从语句中分析出各原子命题，将它们符号化；）从语句中分析出各原子命题，将它们符号化；（2）使用合适的命题联结词，把原子命题逐个联结起）使用合适的命题联结词，把原子命题逐个联结起来，组成复合命题的符号化表示。来，组成复合命题的符号化表示。例例12用符号形式表示下列命题。用符号形式表示下列命题。（1）如果明天早上下雨或下雪，那么我不去学校）如果明天早上下雨或下雪，那么我不去学校（2）如果明天早上不下雨且不下雪，那么我去学校。）如果明天早上不下雨且不下雪，那么我去学校。（3）如果明天早上不是雨夹雪，那么我去学校。）如果明天早上不是雨夹雪，那么我去学校。（4）只有当明天早上不下雨且不下雪时，我才去学校。）只有当明天早上不下雨且不下雪时，我才去学校。解解 令令P：明天早上下雨；明天早上下雨；Q：明天早上下雪；明天早上下雪；R：我去学校。我去学校。（2）（）（PPQQ）R；（1）（）（PQ）R；（4 4）RR（PP Q Q）（3）(PQ）R；1212例例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）。1313练习练习7-11.判断下列语句哪些是命题，若是命题，则指出其真值。判断下列语句哪些是命题，若是命题，则指出其真值。（1）只有小孩才爱哭。只有小孩才爱哭。（2）X+6=Y（3）银是白的。银是白的。（4）起来吧，我的朋友。起来吧，我的朋友。(是是假假)(不是不是)(是是真真)(不是不是)2将下列命题符号化将下列命题符号化 （1 1）我看见的既不是小张也不是老李。）我看见的既不是小张也不是老李。解解 令令P：我看见的是小张；我看见的是小张；Q：我看见的是老李。我看见的是老李。则该命题可表示为则该命题可表示为 P Q（2）如果晚上做完了作业并且没有其它的事，他就会如果晚上做完了作业并且没有其它的事，他就会看电视或听音乐。看电视或听音乐。解解令令P：他晚上做完了作业；他晚上做完了作业；Q：他晚上有其它的事；他晚上有其它的事；R：他看电视；他看电视；S：他听音乐。他听音乐。则该命题可表示为则该命题可表示为（P Q）（RS）14149.2命题公式命题公式一一、命题公式的概念命题公式的概念1.命题常元命题常元一个表示确定命题的大写字母。一个表示确定命题的大写字母。2命题变元命题变元一个没有指定具体内容的命题符号。一个没有指定具体内容的命题符号。一个命题变元当没有对其赋予内容时，它一个命题变元当没有对其赋予内容时，它的真值不能确定，一旦用一个具体的命题代入，的真值不能确定，一旦用一个具体的命题代入，它的真值就确定了。它的真值就确定了。15153.命题公式命题公式命题公式（或简称公式）是由命题公式（或简称公式）是由0、1和命题变元以及和命题变元以及命题联结词按一定的规则产生的符号串。命题联结词按一定的规则产生的符号串。定义定义9-6（命题公式的递归定义。）（命题公式的递归定义。）（1）0，1是命题公式；是命题公式；（2）命题变元是命题公式；命题变元是命题公式；（3）如果如果A是命题公式，则是命题公式，则A是命题公式；是命题公式；（4）如果如果A和和B是命题公式，则（是命题公式，则（AB），），（AB）,(AB）,(AB）也是命题公式；也是命题公式；有限次地利用上述（有限次地利用上述（1）（4）而产生的符号串是命题公式。）而产生的符号串是命题公式。例例1下列符号串是否为命题公式。下列符号串是否为命题公式。（1）P(QPR）；）；（2）（）（PQ）（QR）解解（1）不是命题公式。不是命题公式。（2 2）是命题公式。是命题公式。1616二、真值指派二、真值指派命题公式代表一个命题，但只有当公式中的每一命题公式代表一个命题，但只有当公式中的每一个命题变元都用一个确定的命题代入时，命题公式才个命题变元都用一个确定的命题代入时，命题公式才有确定的真值，成为命题。有确定的真值，成为命题。定义定义97设设F F为含有命题变元为含有命题变元P P1 1，P P2 2，,P Pn n的命题公式，对的命题公式，对P P1 1，P P2 2，,P Pn n分别指定一个真值分别指定一个真值,称称为对公式为对公式F F的一组的一组真值指派真值指派。公式与其命题变元之间的真值关系，可以用真值公式与其命题变元之间的真值关系，可以用真值表的方法表示出来。表的方法表示出来。1717例例2给给出公式出公式 F=(F=(（PQPQ）（QRQR）)(P(PR R）的真值的真值表。表。解解 公式公式F F的真值表如下：的真值表如下：PQRRPQQR(PQ)(QR)PRF0 0 00 0 00 0 10 0 10 1 00 1 00 1 10 1 11 0 01 0 01 0 11 0 11 1 01 1 01 1 11 1 11 10 01 10 01 10 01 10 00 00 01 11 11 11 11 11 10 00 00 01 10 00 00 01 11 11 10 01 10 00 00 01 10 00 00 00 01 10 01 10 00 00 01 10 01 11 11 10 01818三、公式类型三、公式类型定义定义9-8如果对于命题公式如果对于命题公式F所包含的命题变元的任所包含的命题变元的任何一组真值指派，何一组真值指派，F的真值恒为真，则称公式的真值恒为真，则称公式F为为重言式重言式（或（或永真公式永真公式），常用），常用“1”表示。相反地，若对于表示。相反地，若对于F所包含所包含的命题变元的任何一组真值指派，的命题变元的任何一组真值指派，F的真值恒为假，则称公的真值恒为假，则称公式式F为为矛盾式矛盾式（或（或永假公式永假公式），常用），常用“0”表示。如果至少有表示。如果至少有一组真值指派使公式一组真值指派使公式F的真值为真，则称的真值为真，则称F为为可满足公式可满足公式。例例3构造下列命题公式的真值表，并判断它们是何构造下列命题公式的真值表，并判断它们是何种类型的公式种类型的公式（1）（）（PQ）（PQ）；）；（2）（）（QP）（PQ）；）；（3 3）（）（PQPQ）（QRQR）（PPR R）。）。1919 解解 令令F F1 1=（PPQ Q）（P P Q Q），），F F2 2=（Q QP P）（PQ PQ）F F1 1和和F F2 2的真值表如下：的真值表如下：PQ P PQPQ(PQ)F1QP PQF20010101100011101101010010111001100101100由上由上可知：可知：F F1 1是是重言式重言式,F F2 2是是矛盾式。矛盾式。(3)的真值表如第的真值表如第4页所示，它是可满足公式。页所示，它是可满足公式。20209.3命题公式的等值关系和蕴含关系命题公式的等值关系和蕴含关系一、命题公式的等值关系一、命题公式的等值关系定义定义9-9设设A和和B是两个命题公式是两个命题公式,P1,P2,Pn是所有出现于是所有出现于A和和B中的命题变元，如果对于中的命题变元，如果对于P1,P2,Pn的任一组真值指派，的任一组真值指派，A和和B的真值都相同的真值都相同,则称公式则称公式A和和B等值等值，记为，记为AB,称称AB为等值式为等值式。注意注意：（1 1）符号）符号“”与与“”的区别与联系。的区别与联系。“”不是联结词，不是联结词，A AB B不表示一个公式，它表示两不表示一个公式，它表示两个公式间的一种关系，即等值关系。个公式间的一种关系，即等值关系。“”是联结词，是联结词，A AB B是一个公式。是一个公式。AB当且仅当当且仅当AB是永真公式。是永真公式。2121（2）可以验证等值关系是等价关系。可以验证等值关系是等价关系。即即自反性自反性：对任意公式：对任意公式A，有，有AA。对称性对称性：对任意公式：对任意公式A，B，若，若AB，则，则BA。可传递性可传递性：对任意公式：对任意公式A A、B B、C C，若，若A AB B，B BC C，则，则A AC C。（3）当）当A是重言式时，是重言式时，A1；当；当A是矛盾式时是矛盾式时，则，则A0。2222二、基本的等值式二、基本的等值式设设P、Q、R是命题变元，下表中列出了是命题变元，下表中列出了24个最基本的等值式个最基本的等值式:编号公公式式E1E1E2E2E3E3E4E4E5E5E6E6E7E7PQQP交换律PQQP交换律(PQ)RP(QR)结合律(PQ)RP(QR)结合律P(QR)(PQ)(PR)分配律P(QR)(PQ)(PR)分配律P0P同一律P1P同一律PP1互否律PP0互否律（P）P双重否定律PPP等幂律PPP等幂律2323编号公公式式E8E8E9E9E10E10E11E12E13E14E15P11零一律P00零一律P（PQ）P吸收律P（PQ）P吸收律（PQ）PQ德.摩根定律（PQ）PQ德.摩根定律PQPQPQ(PQ)(PQ)P(QR)(PQ)RPQ(PQ)(QP)PQQP2424三、等值式的判别三、等值式的判别有两种方法：真值表方法，命题演算方法有两种方法：真值表方法，命题演算方法1、真值表方法、真值表方法例例1用真值表方法证明用真值表方法证明E10：(P Q)PQ解解令：令：A=(P Q)，B=PQ，构造构造A，B以及以及AB的真值表如下：的真值表如下：PQP Q(P Q)P Q PQAB000111110110100111100101 由于公式由于公式AB所标记的列全为所标记的列全为1，因此，因此AB。101000012525例例2 2 用真值表方法证明用真值表方法证明E E1111：P PQ QP P Q Q解解 令令A=PA=PQ Q，B=B=P P Q Q 构造构造A A，B B以及以及A AB B的真值表如下：的真值表如下：PQ P P QPQAB001111011111100001由于公式由于公式AB所标记的列全为所标记的列全为1，因此，因此AB.1101112626例例3用真值表方法判断用真值表方法判断PQPQ是否成立是否成立.解解 令令A=PA=PQ Q，B=B=P PQ Q 构造构造A A，B B以及以及A AB B的真值表的真值表PQ P Q PQPQAB0011111011001001100由由于于公公式式A AB B所所标标记记的的列列不不全全为为1 1，A AB B不不是是永永真公式，因此真公式，因此A AB B不成立。不成立。1011001112727(1)代入规则代入规则代入规则代入规则对于重言式中的任一命题变元出现的对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。每一处均用同一命题公式代入，得到的仍是重言式。2等值演算方法等值演算方法例如例如F=（PQ）（QP）是重言式，若是重言式，若用公式用公式AB代换命题变元代换命题变元P得公式得公式F1=（AB）Q）（Q（AB），），F1仍是重言式。仍是重言式。注意：因为注意：因为AB当且仅当当且仅当AB是重言式。所以，是重言式。所以，若对于等值式中的任一命题变元出现的每一处均用同若对于等值式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等值式。一命题公式代入，则得到的仍是等值式。2828(2)置置换规则换规则 定义定义9-109-10 设设C C是命题公式是命题公式A A的一部分（即的一部分（即C C是是公式公式A A中连续的几个符号），且中连续的几个符号），且C C本身也是一个命题本身也是一个命题公式，则称公式，则称C C为公式为公式A A的的子公式。子公式。例如例如 设公式设公式A=A=（PQPQ）（P PQ Q）（RR S S）。）。则则 PQ，PQ，（，（PQ）（R S）等均是等均是A的的子公式，子公式，但但 PP，P P和和Q Q等均不是等均不是A A的子公式，的子公式，置换规则置换规则 设设C C是公式是公式A A的子公式，的子公式，C CD D。如如果将公式果将公式A A中的子公式中的子公式C C置换成公式置换成公式D D之后，得到的公式之后，得到的公式是是B B，则，则A AB B。2929(3)(3)等值演算等值演算 等值演算是指利用已知的一些等值式，根据置换等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。一些等值式的过程。由代入规则知前述的基本等值式，不仅对任意的命由代入规则知前述的基本等值式，不仅对任意的命题变元题变元P P，Q Q，R R是成立的，而且当是成立的，而且当P P，Q Q，R R分别为命题公分别为命题公式时，这些等值式也成立式时，这些等值式也成立 例例2证明命题公式的等值关系：证明命题公式的等值关系：（PQ）（RQ）（PR）Q；证明证明（PQ）（RQ）（PQ）(RQ)E11（P R）QE3(分配律分配律)(PR)QE10(德德.摩根定律摩根定律)(PR)QE11所以（所以（PQ）（RQ）（PR）Q3030例例3证明下列命题公式的等值关系证明下列命题公式的等值关系(P Q)(P(P Q)P Q证明证明(P Q)(P(P Q)(P Q)(P P)Q)E2(结合律结合律)(P Q)(P Q)E7(等幂律等幂律)(P Q)(P Q)E1(交换律交换律)P(Q(P Q)E2(结合结合律律)P QE 1，E9(交换律，吸收律交换律，吸收律)3131例例4判别下列公式的类型。判别下列公式的类型。（1）Q(P（PQ）)（2）（）（PQ）P解解（1）Q（P（PQ）Q（P（PQ）E11,E6Q（P P）（PQ）E3Q（1（PQ）E5Q（PQ）E4Q P QE10（Q Q）PE1,E20E5,E8所以所以Q(P(PQ)是矛盾式。是矛盾式。（2）（PQ）P（PQ）P E11 P E9 于是该公式是可满足式。于是该公式是可满足式。3232三、命题公式的蕴含关系三、命题公式的蕴含关系 定义定义9-119-11 设设A A，B B是两个公式，若公式是两个公式，若公式A AB B是重是重言式，即言式，即A AB B1 1，则称公式则称公式A A蕴含公式蕴含公式B B，记作记作A AB B。称称“A AB”B”为为蕴含式蕴含式。注意：注意：符号符号“”和和“”的区别和联系与符号的区别和联系与符号“”与与“”的区别和联系类似。的区别和联系类似。“”不是联结词，不是联结词，“AB”不是公式，它表示公式不是公式，它表示公式A与与B之间存在蕴之间存在蕴含关系。含关系。“”是联系词，是联系词，AB是一个公式。是一个公式。AB当且仅当当且仅当AB是永真公式是永真公式。3333 A AB B是偏序关系是偏序关系即即自反性自反性：AA。反对称反对称：若：若AB，BA，则，则AB。传递性传递性：若：若AB，BC，则则AC。反对称性的证明：反对称性的证明：设设AB且且BA，由定义由定义7-11AB1且且BA1于是于是AB(AB)(BA)E141 11因此因此AB3434传递性的证明：传递性的证明：设设A AB B，B BC C，则则A AB B1 1，B BC C1 1 (A A B B C)C)(A AB B C)C)(A(AB)B)C)C)(A A(B(BC)C)(1(1 C)C)(A A 1)1)1 1 1 1 1 1 因此因此 A AC.C.于是于是 A AC C A A C C (A A C)C)(B(BB)B)3535四、基本的蕴含式四、基本的蕴含式编号蕴蕴含含式式I1PQPI2PQQI3PPQI4QPQI5PPQI6QPQI7(PQ)PI8(PQ)Q 设设P P、Q Q、R R是是命命题题变变元元，下下表表中中列列出出了了1616个个最最基本的蕴含式。基本的蕴含式。3636编号蕴蕴含含式式I9PQPQ或表示为或表示为：P、QPQI10 P(P Q)Q P、(P Q)QI11P(PQ)QP、PQQI12 Q(PQ)P Q、PQPI13(PQ)(QR)PRPQ、QRPRI14(P Q)(PR)(QR)RP Q、PR、QRRI15PQ(P R)(Q R)I16PQ(P R)(Q R)3737五、蕴含式的判别五、蕴含式的判别判定判定“AB”是否成立的问题可转化为判定是否成立的问题可转化为判定AB是否为重言式，有下述判定方法：是否为重言式，有下述判定方法：（1）真值表；）真值表；（2）等值演算；）等值演算；（3）假定前件）假定前件A为真；为真；（4）假定后件）假定后件B为假。为假。1.真值表方法真值表方法例例4证明证明I14：(（PQ）（PR）（QR）)R证明证明令公式令公式F=（PQ）（PR）（QR）R，其真值表如下：其真值表如下：3838公式公式F对任意的一组真值指派取值均为对任意的一组真值指派取值均为1，故，故F是重言式。是重言式。P Q RP Q RPQPQPRPRQ RQ R(PQ)(PR(PQ)(PR）（Q R Q R）F0 0 00 0 00 0 10 0 10 1 00 1 00 1 10 1 11 0 01 0 01 0 11 0 11 1 01 1 01 1 11 1 10 00 01 11 11 11 11 11 11 11 11 11 10 01 10 01 11 11 10 01 11 11 10 01 10 00 00 01 10 01 10 01 11 11 11 11 11 11 11 11 139392.等值演算方法等值演算方法例例5证明证明 I I1111：PP（P PQ Q）Q Q 证明证明（PP（P PQ Q）Q Q （PP（PQPQ）Q Q E E1111 （PP（PQPQ）E E1010（PQPQ）（PQPQ）E E2 2 1 1 代入规则代入规则,E,E5 5 因此因此 PP（P PQ Q）Q Q 40403.假定前件假定前件A真真 假定前件假定前件A A为真，检查在此情况下，其后件为真，检查在此情况下，其后件B B是否也为真。是否也为真。ABAB001011100111例例6证明证明I12:Q（PQ）P证明证明令前件令前件 Q（PQ）为真，为真，则则 Q为真为真,且且PQ为真。为真。于是于是Q为假，因而为假，因而P也为假。由此也为假。由此 P为真。为真。故蕴含式故蕴含式I12成立。成立。41414、假定后件假定后件B假假 假定后件假定后件B B为假，检查在此情况下，其前件为假，检查在此情况下，其前件A A是否也为假是否也为假.例例7证明蕴含式证明蕴含式(PQ)(RS)(P R)(Q S)证证明明令令后后件件(P R)(Q S)为为假假，则则P R为为真真，Q S为为假假,于是于是P、R均为真，而均为真，而Q和和S至少一个为假。至少一个为假。由此可知由此可知PQ与与RS中至少一个为假中至少一个为假,因此因此(PQ)(RS)为假为假.故上述蕴含式成立。故上述蕴含式成立。4242练习练习7-31判断下列等值式是否成立判断下列等值式是否成立（1）（）（PQ）（RQ）（PR）Q（2）（PQ）（P Q）（PQ）解解（1）（）（PQ）（RQ）（PQ）（RQ）E11（P R）QE3（PR）QE10（2）（）（P Q）（PQ）(（PQ）（QP）)E6，E10(（PQ）（QP）)E11（PQ）E14（PR）QE1143432 2判定蕴含式判定蕴含式P P（Q QR R）（P PQ Q）（P PR R）是否成立是否成立解解假定后件（假定后件（PQ）（PR）为假，为假，则则PQ为真，为真，PR为假。为假。由由P PR R为假为假,得得P P为真，为真，R R为假。为假。又又PQ为真，故得为真，故得Q为真。为真。于是于是P为真，为真，QR为假。为假。从而从而P（QR）为假。为假。因此蕴含式成立。因此蕴含式成立。44449.49.4范式范式一、析取范式和合取范式析取范式和合取范式定义定义9-129-12一个命题公式若它具有一个命题公式若它具有P P1 1*PP2 2*P Pn n*的形式（的形式（n1n1），），其中其中P Pi i*是命题变是命题变元元P Pi i或其否定或其否定PPi i，则称其为则称其为质合取式质合取式。例如例如,PQRS,PQRS是由命题变元是由命题变元P P、Q Q、R R、S S组成组成的一质合取式。的一质合取式。定义定义9-139-13一个命题公式若具有一个命题公式若具有P P1 1*PP2 2*P Pn n*（n1n1）的形式，其中的形式，其中P P*i i是命题变是命题变元元P Pi i或是其否定或是其否定PPi i ，则称其为则称其为质析取式质析取式。例如例如,QPRQPR是由命题变元是由命题变元P P、Q Q、R R组成的组成的一质析取式。一质析取式。4545定理定理9-49-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也是永真式。也是永真式。4646定义定义9-149-14质合取式的析取称为析取范式。即质合取式的析取称为析取范式。即具有具有A A1 1AA2 2AAn n(n1)(n1)的形式的公式，其中的形式的公式，其中A Ai i是是质合取式。质合取式。例如例如，F F1 1=P(PQ)R(=P(PQ)R(PP QR)QR)是一析是一析取范式。取范式。定义定义9-15质析取式的合取称为合取范式。质析取式的合取称为合取范式。即具有即具有A A1 1AA2 2AAn n (n1)(n1)的形式的公式，其的形式的公式，其中中AiAi是质析取式。是质析取式。例如例如，F F2 2=P(PQ)R(PP(PQ)R(P QR)QR)是一合取是一合取范式。范式。F F3 3=(=(PRQ)(PQ)R(PPRQ)(PQ)R(P R)R)也是一合也是一合取范式。取范式。4747二、求公式的析取范式和合取范式二、求公式的析取范式和合取范式任何一个命题公式都可以变换为与它等值的析任何一个命题公式都可以变换为与它等值的析取范式或合取范式。取范式或合取范式。按下列步骤进行：按下列步骤进行：（1 1）利用）利用E E1111，E E1212和和E E1414消去公式中的运算符消去公式中的运算符“”和和“”；(2)(2)利用德利用德 摩根定律将否定符号摩根定律将否定符号“”向内深向内深入，使之只作用于命题变元；入，使之只作用于命题变元；（3 3）利用双重否定律）利用双重否定律E E6 6将将 (P)P)置换成置换成P P；（4 4）利用分配律、结合律将公式归约为合取范）利用分配律、结合律将公式归约为合取范式或析取范式。式或析取范式。4848例例1求求F1=(P(QR)S的合取范式和析取范式的合取范式和析取范式解解F1(P(QR)SE11 P(QR)SE10 P(Q R)S(析取范式析取范式)E10,E6又又F1 P(Q R)S(PS)(Q R)E1,E2(PSQ)(PS R)（合取范式）合取范式）E3另外由另外由F1(PSQ)(PS R)(P(PS R)(S(PS R)(Q(PS R)E3PS(Q P)(QS)(Q R)（析取范式）析取范式）E9,E134949例例2 2 求求 F F2 2=(PQ)(PQ)(PQ)(PQ)的析取范式、合的析取范式、合取范式。取范式。解解F2(PQ)(PQ)(PQ)(PQ)E14(PQ)(PQ)(PQ)(PQ)E11,E6(P(Q(PQ)(P Q(P Q)E2,E10,E10(PQ)(P Q)（合取范式）合取范式）E2,E9(P(P Q)(Q(P Q)E3(P P)(P Q)(PQ)(Q Q)（析取范式）析取范式）E35050定理定理9-59-5（1）公式）公式A为永真式的充分必要条件是，为永真式的充分必要条件是，A的合取范式中的合取范式中每一质析取式至少包含一对互为否定的析取项。每一质析取式至少包含一对互为否定的析取项。三、利用范式判定公式类型三、利用范式判定公式类型证明证明（2）必要性必要性（用反证法）：（用反证法）：假设假设AA1A2An中某个中某个Ai不包含一对互为否不包含一对互为否定的合取项，定的合取项，（2）公式）公式A为永假式的充分必要条件是，为永假式的充分必要条件是，A的析取范式中的析取范式中每一质合取式至少包含一对互为否定的合取项。每一质合取式至少包含一对互为否定的合取项。则由定理则由定理9-4知，知，Ai不是矛盾式。不是矛盾式。于是存在一组真值指派使于是存在一组真值指派使Ai取值为真。取值为真。对同一组真值指派，对同一组真值指派，A的取值也必为真，这与的取值也必为真，这与A是矛盾是矛盾式不符，假设不成立。式不符，假设不成立。充分性充分性：假设任一：假设任一Ai(1in)中含有形如中含有形如PP合取式，合取式，其中其中P为命题变元。于是由定理为命题变元。于是由定理9-4知，每一知，每一Ai(1in)都为都为矛盾式，因此矛盾式，因此A1A2An必为矛盾式，即必为矛盾式，即A为矛盾式。为矛盾式。因此因此A的析取范式中每一质合取的析取范式中每一质合取式至少包含一对互为否定的合取项。式至少包含一对互为否定的合取项。5151例例3 3判别公式判别公式A=PA=P(P(Q(P(QP)P)是否为重言式或矛是否为重言式或矛盾式。盾式。解解A A P(P(P(P(QP)EQP)E1111 P(PP(P Q)(PP)(Q)(PP)(析取范式析取范式)E)E3 3根据定理根据定理9-59-5，A A不是矛盾式。不是矛盾式。又又A AP(P(P(P(QP)QP)（PPPP）（PP QP)QP)（合取范式）合取范式）E E3 3由定理由定理9-59-5知，知，A A是重言式。是重言式。5252例例4 4利用范式判断公式利用范式判断公式P(P Q)的类型。的类型。解解 P(P Q)(P(P Q)(P(P Q)E12(P Q)(P(PQ)E 10(P Q)P(析取范式析取范式)E 9由定理由定理9-5，该公式不是永假公式。，该公式不是永假公式。(PP)(P Q)（合取范式）合取范式）E1，E 3由定理由定理9-5，该公式也不是永真公式。，该公式也不是永真公式。由上可知，该公式是一可满足公式。由上可知，该公式是一可满足公式。又又P(P Q)(P Q)P5353四、主析取范式和主合取范式四、主析取范式和主合取范式定义定义9-169-16设有命题变元设有命题变元P P1 1，P P2 2，,P Pn n ，形形如如 的命题公式称为是由命题变元的命题公式称为是由命题变元P P 1 1，P P2 2，P Pn n所产生所产生的最小项。而形如的最小项。而形如 的命题公式称为是由命题变元的命题公式称为是由命题变元P P1 1，P P2 2，P Pn n所产生的最大项所产生的最大项 。其中。其中P Pi i*为为P Pi i或为或为 P Pi i(i=1,2,n).(i=1,2,n).例如例如,P P1 1PP2 2PP3 3，P P1 1PP2 2 P P3 3均是由均是由P P1 1，P P2 2，P P3 3所所产生的最小项。产生的最小项。P P1 1 P P2 2PP3 3是由是由P P1 1，P P2 2，P P3 3产生的一个最大项。产生的一个最大项。5454定义定义9-179-17由不同最小项所组成的析取式，由不同最小项所组成的析取式，称为称为主析取范式主析取范式。定义定义9-189-18由不同最大项所组成的合取式，由不同最大项所组成的合取式，称为称为主合取范式主合取范式。例如例如(P P1 1P P2 2 P P3 3)(P P1 1 P P2 2 P P3 3)(P(P1 1 P P2 2 P P3 3)是一个是一个主析取范式。主析取范式。(P(P1 1P P2 2 P P3 3)(P(P1 1 P P2 2 P P3 3)(P P1 1P P2 2P P3 3)(P P1 1 P P2 2P P3 3)是一个主合取范式。是一个主合取范式。5555例例4求公式求公式F1=P(P(QP)和公式和公式F2=(PQ)(PQ)的主析取范式的主析取范式.解解F1P(P(QP)E11 P(P Q)(PP)E3(P(Q Q)(P Q)(P(Q Q)E7,E4,E5(PQ)(P Q)(P Q)(PQ)(P Q)E3(PQ)(P Q)(P Q)(PQ)E1,E7五、求公式的主析取范式和主合取范式五、求公式的主析取范式和主合取范式对任一给定的公式除了用求范式时的四个步骤外，还要对任一给定的公式除了用求范式时的四个步骤外，还要利用同一律、等幂律、互否律、分配律等进一步将质合取式利用同一律、等幂律、互否律、分配律等进一步将质合取式（质析取式）变换为最小项（最大项）的形式。（质析取式）变换为最小项（最大项）的形式。5656F2(PQ)(PQ)(P Q)(PQ)E11(P PQ)(Q PQ)E30 0E 1,E 50定理定理9-6每一个不为永假的命题公式每一个不为永假的命题公式F F（P P1 1,P P2 2,P Pn n）必与一个由必与一个由P P1 1，P P2 2，P Pn n所产生的主所产生的主析取范式等值。析取范式等值。永真公式永真公式的主析取范式包含所有的主析取范式包含所有2 2n n个最小项。个最小项。永假公式永假公式的主析取范式是一个空公式。用的主析取范式是一个空公式。用0 0表示。表示。5757例例5求公式求公式 F F1 1=(P=(PQ)Q)(P(PQ)Q)和和 公式公式F F2 2=P=P(P(P(Q(QP)P)的主合取范式的主合取范式F F1 1(P P Q)Q)(P(PQ)Q)E E1111 (P P Q)Q)(P(P(Q(QQ)Q)(Q Q(P(PP)P)E E 5 5,E,E4 4 (P P Q)Q)(P(P Q)Q)(P(PQ)Q)(P(PQ)Q)(P PQ)Q)E E 3 3 (P(P Q)Q)(P(PQ)Q)(P P Q)Q)(P PQ)Q)E E 7 75858解解F2P(P(QP)E11(PP)(P QP)E311E5,E11定理定理9-7每一个不为永真的公式每一个不为永真的公式 F(PF(P1 1,P,P2 2,P Pn n）必与一个由必与一个由P P1 1,P,P2 2,P Pn n所产生的主合取范式等值。所产生的主合取范式等值。永假公式永假公式的主合取范式包含所有的主合取范式包含所有 2 2n n个最大项。个最大项。永真公式永真公式的主合取范式是一空公式，用的主合取范式是一空公式，用1 1表示。表示。5959六、利用主范式判定公式类型六、利用主范式判定公式类型1.利用主析取范式判定利用主析取范式判定 (1)(1)若公式若公式 F(PF(P1 1,P,P2 2，P Pn n)的主析取的主析取范式包含所有范式包含所有2 2n n个最小项，则个最小项，则 F F是永真公式。例是永真公式。例如，例如，例4 4中的中的 F F1 1。(2)(2)若若 F F的主析取范式是一空公式且为的主析取范式是一空公式且为0 0，则，则 F F是永假公式。例如，例是永假公式。例如，例4 4中的中的 F F2 2。(3)(3)否则，否则，F F为可满足的公式。为可满足的公式。60602 2 利用主合取范式判定利用主合取范式判定 (1)(1)若若公公式式F F（P P1 1,P P2 2,P Pn n）的的主主合合取取范范式式包包含含所所有有2 2n n个个最最大大项项，则则F F是是永永假假公式。例如，例公式。例如，例5 5中的中的F F1 1。(2)(2)若若F F的的主主合合取取范范式式是是一一空空公公式式且且为为1 1，则，则F F是永真公式。例如，例是永真公式。例如，例5 5中的中的F F2 2。(3)(3)否则，否则，F F为可满足公式为可满足公式6161例例6求求公公式式F=(QF=(Q(P(PQ)Q)P P的的主主范范式式并并判判定定公公式式的类型的类型.解解(1)(1)求求F F的主析取范式的主析取范式F(Q(P Q)P Q(PQ)P(Q(PP)(PQ)(P(QQ)（PQ)(PQ)(PQ)(P Q)(PQ)(P Q)(PQ)(PQ)由此可知由此可知F是可满足公式。是可满足公式。6262(2)(2)求求F F的主合取范式的主合取范式F F（Q Q(P(PQ)Q)P P P PQ Q由前分析和举例可知：由前分析和举例可知：仅仅需需求求出出公公式式F F的的任任一一种种主主范范式式即即可可判判定定F F的的类型。类型。6363练习练习7-4 1 1判断公式判断公式F=(F=(PP Q)(PQ)(P Q)Q)是否为重言式是否为重言式或矛盾式？或矛盾式？解解F(P Q)(P Q)(QP)E11 (PQ)(PQ)(PP Q)(QP)EQ)(QP)E1010,E,E6 6,E,E1111(PQ)(P(QP)(Q(QP)E3(PQ)(PQ)(PP)(QQ)(QP)E3(PQ)(PQ)(QP)E5,E8F的主析取范式既非空公式，又未包含的主析取范式既非空公式，又未包含22=4个个项，故项，故F不是重言式和矛盾式，只是可满足式。不是重言式和矛盾式，只是可满足式。64649.5命题演算的推理理论命题演算的推理理论一、推理一、推理 推理是由已知的命题得到新命题的思维过程。推理是由已知的命题得到新命题的思维过程。定义定义9-19设设A A和和B B是两个命题公式，如果是两个命题公式，如果A AB B，即如果命题公式即如果命题公式A AB B为重言式，则称为重言式，则称B B是前提是前提A A的结的结论或从论或从A A推出结论推出结论B B。一般地设一般地设H H1 1，H H2 2，,H Hn n和和C C是一是一些命题公式些命题公式,若蕴含式若蕴含式H H1 1HH2 2H Hn n C C(*)(*)成立，则称成立，则称C C是前提集合是前提集合 H H1 1，H H2 2，,H,Hn n 的结论，或的结论，或称从前提称从前提H H1 1，H H2 2，,H Hn n能推出结论能推出结论C C。有时也记作有时也记作H H1 1，H H2 2，,H Hn n C C65651、真值表法、真值表法对于命题公式对于命题公式 中所有命题变元的每一组真值指派作出该公式的真值表，中所有命题变元的每一组真值指派作出该公式的真值表，看是否为永真看是否为永真。PQ00011011解解构造其真值表如下：构造其真值表如下：P QPQ（PQ）P(（PQ）P)QQ11101101010100100111例例1考察结论考察结论C是否是下列前提是否是下列前提H1，H2的结论。的结论。（1）H1：PQ，H2：P，C：Q二、如何判断由一个前提集合能否推出某个结论二、如何判断由一个前提集合能否推出某个结论 6666 （2 2）H H1 1：PQPQ，H H2 2：P P，C C：Q Q解解 构造其真值表如下：构造其真值表如下：P QPQ（PQ）P1111101101000010(（PQ）P)Q1011P QP Q0 00 00 10 11 01 01 11 1 在这里，我们不关心结论是真还是假，而主要关心在这里，我们不关心结论是真还是假，而主要关心由给定的前提是否能推出这个结论来。由给定的前提是否能推出这个结论来。67672、等值演算方法、等值演算方法例例证明证明分析分析根据题意，需证明根据题意，需证明证明证明6868 3 3、“形式证明形式证明”方法方法（1）基本述语）基本述语形式证明形式证明：一个描述推理过程的命题序列，其中每个：一个描述推理过程的命题序列，其中每个命题或者是已知的命题，或者是由某些前提所推得的结论，命题或者是已知的命题，或者是由某些前提所推得的结论，序列中最后一个命题就是所要求的结论，这样的命题序列称序列中最后一个命题就是所要求的结论，这样的命题序列称为形式证明。为形式证明。有效的证明有效的证明：如果证明过程中的每一步所得到的结论：如果证明过程中的每一步所得到的结论都是根据推理规则得到的，则这样的证明称作是有效的。都是根据推理规则得到的，则这样的证明称作是有效的。有效的结论有效的结论：通过有效的证明而得到结论，称作是有效：通过有效的证明而得到结论，称作是有效的结论。的结论。合理的证明合理的证明：一个证明是否有效与前提的真假没有关系。：一个证明是否有效与前提的真假没有关系。如果所有的前提都是真的，那么通过有效的证明所得到的结论如果所有的前提都是真的，那么通过有效的证明所得到的结论也是真的。这样的证明称作是合理的。也是真的。这样的证明称作是合理的。合理的结论合理的结论：一个结论是否有效与它自身的真假没有关：一个结论是否有效与它自身的真假没有关系。通过合理证明而得到的结论称作合理的结论。系。通过合理证明而得到的结论称作合理的结论。6969(2)推理规则推理规则前提引用规则前提引用规则：在证明的任何步骤上都可以引在证明的任何步骤上都可以引用前提。用前提。结论引用规则结论引用规则：在证明的任何步骤上所得到的在证明的任何步骤上所得到的结论都可以在其后的证明中引用。结论都可以在其后的证明中引用。置换规则置换规则：在证明的任何步骤上，命题公式的在证明的任何步骤上，命题公式的子公式都可以用与它等值的其它命题公式置换。子公式都可以用与它等值的其它命题公式置换。代入规则代入规则：在证明的任何步骤上，重言式中的在证明的任何步骤上，重言式中的任一命题变元都可以用一命题公式代入，得到的仍是任一命题变元都可以用一命题公式代入，得到的仍是重言式。重言式。7070 例例2 2 证明证明 RR（PQPQ）是前提是前提PQPQ，Q QR R，P PS S，S S的结论。的结论。所以所以PQ，QR，PS，SR（PQ)编号编号公公式式依依据据（1）（2）（3）（4）（5）（6）（7）（8）PS S PPQQQRRR（PQ）前提（前提引入规则）前提（前提引入规则）前提（前提引入规则）前提（前提引入规则）（1），（），（2）；）；I12前提前提（3），（），（4）；）；I10前提前提（5），（），（6）；）；I11（4），（），（7）；）；I97171例例3 3 证明证明RSRS是前提是前提PP（QSQS），），RP RP和和Q Q的有效结论。的有效