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

《离散数学-命题逻辑教学课程.ppt》由会员分享，可在线阅读，更多相关《离散数学-命题逻辑教学课程.ppt（82页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散数学离散数学命题逻辑命题逻辑(Proposition)主讲教师：吴旭第一章第一章命题逻辑命题逻辑数理逻辑是用数学方法研究思维规律的一门学科。数理逻辑是用数学方法研究思维规律的一门学科。所谓数学方法是指所谓数学方法是指:用一套数学的符号系统来描述和用一套数学的符号系统来描述和处处理思维的形式与规律。因此理思维的形式与规律。因此,数理逻辑又称为符号逻辑。数理逻辑又称为符号逻辑。本章介绍数理逻辑中最基本的内容命题逻辑。首先引入本章介绍数理逻辑中最基本的内容命题逻辑。首先引入命题、命题公式等概念。然后命题、命题公式等概念。然后,在此基础上研究命题公式在此基础上研究命题公式间的等值关系和蕴含关系间的

2、等值关系和蕴含关系,并给出推理规则并给出推理规则,进行命题演进行命题演绎。绎。主要内容如下：主要内容如下：命题和命题联结词命题和命题联结词命题公式与翻译命题公式与翻译命题公式的等值关系和蕴含关系命题公式的等值关系和蕴含关系对偶与范式对偶与范式命题演算的推理理论命题演算的推理理论命题和命题联结词命题和命题联结词一、一、命题的概念命题的概念命题命题：是能分辨真假的陈述句。是能分辨真假的陈述句。例例1判断下列语句是否是命题。判断下列语句是否是命题。（1）空气是人生存所必需的。）空气是人生存所必需的。（2）请把门关上。）请把门关上。（3）南京是中国的首都。）南京是中国的首都。（4）你吃饭了吗？）你吃饭

3、了吗？（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：小王是我的好朋友；：小王是我的好朋友；

4、解解 P、Q是命题是命题二、命题联结词二、命题联结词 原子命题原子命题：由简单句形成的命题。由简单句形成的命题。复合命题：复合命题：由一个或几个原子命题通过联结词由一个或几个原子命题通过联结词的联接而构成的命题。的联接而构成的命题。例例3A：李明既是三好学生又是足球队员。：李明既是三好学生又是足球队员。B：张平或者正在钓鱼或者正在睡觉。：张平或者正在钓鱼或者正在睡觉。C：如果明天天气晴朗，那么我们举行运动会。：如果明天天气晴朗，那么我们举行运动会。定义五种联结词（或称命题的五种运算）。定义五种联结词（或称命题的五种运算）。1.否定否定“”定义定义1-1设设P是一个命题，利用是一个命题，利用“”

5、和和P组成的组成的复合命题称为复合命题称为P的否命题，记作的否命题，记作“P”(读作读作“非非P”)。命题命题P P取值为真时，命题取值为真时，命题PP取值为假；命题取值为假；命题P P取值为假时，取值为假时，命题命题PP取值为真。取值为真。例例4设设P：上海是一个城市；：上海是一个城市；Q：每个自然数都是偶数。：每个自然数都是偶数。则有则有 P：上海不是一个城市：上海不是一个城市;Q：并非每个自然数都是偶数。：并非每个自然数都是偶数。PPP10012合取合取“”定义定义1-2设设P和和Q是两个命题，由是两个命题，由P、Q利用利用“”组成的复合命题，称为合取式复合命题，记作组成的复合命题，称为

6、合取式复合命题，记作“PQ”（读作（读作“P且且Q”）。）。当且仅当命题当且仅当命题P P和和Q Q均取值为真时，均取值为真时，P P Q Q才取值为真。才取值为真。例例5 5 设设P P：我们去看电影。：我们去看电影。Q Q：房间里有十张桌子。则：房间里有十张桌子。则P P Q Q表示表示“我们去看电影并且房间里有十张桌子。我们去看电影并且房间里有十张桌子。”PQPQ0000101001113.析取析取“”定义定义1-31-3 由命题由命题P P和和Q Q利用利用“”“”组成的复合命题，称组成的复合命题，称为析取式复合命题，记作为析取式复合命题，记作“PQ”PQ”（读作（读作“P P或或Q”

7、Q”）。）。当且仅当当且仅当P P和和Q Q至少有一个取值为真时，至少有一个取值为真时，PQPQ取值为真。取值为真。PQPQ000011101111例例6将命题将命题“他可能是他可能是100米或米或400米赛跑的冠军。米赛跑的冠军。”符号化。符号化。解解令令P：他可能是：他可能是100米赛跑冠军；米赛跑冠军；Q Q：他可能是：他可能是400400米赛跑冠军。米赛跑冠军。则命题可表示为则命题可表示为PQ。设设P P、Q Q是两个命题，是两个命题，P P异或异或Q Q是一个复合命题，记作是一个复合命题，记作PQPQ。例例7今天晚上我在家看电视或去剧场看戏。今天晚上我在家看电视或去剧场看戏。令令P：

8、今天晚上我在家看电视。：今天晚上我在家看电视。Q：今天晚上我去剧场看戏：今天晚上我去剧场看戏例例7中的命题可表示为中的命题可表示为PQ，或者表示为，或者表示为（PQ(PQ)。由于由于“”可用可用“”，“”和和“”表示，故表示，故我们不把它当作基本联结词。我们不把它当作基本联结词。PQPQ0000111011104.蕴含蕴含“”定义定义1-41-4由命题由命题P P和和Q Q利用利用“”“”组成的复合命题，组成的复合命题，称为蕴含式复合命题，记作称为蕴含式复合命题，记作“PQ”PQ”（读作（读作“如果如果P P，则，则Q”Q”）。）。当当P为真，为真，Q为假时，为假时，PQ为假，否则为假，否则P

9、QPQ为真。为真。PQPQ001011100111例例8将命题将命题“如果我得到这本小说，那么我今夜如果我得到这本小说，那么我今夜就读完它。就读完它。”符号化。符号化。解解令令P：我得到这本小说；：我得到这本小说；Q：我今夜就读完它。：我今夜就读完它。于是上述命题可表示为于是上述命题可表示为PQPQ。例例9若若P：雪是黑色的；：雪是黑色的；Q：太阳从西边升起；：太阳从西边升起；R：太阳从东边升起。：太阳从东边升起。则则PQPQ和和PRPR所表示的命题都是真的所表示的命题都是真的.5等值等值“”定义定义1-5由命题由命题P和和Q，利用，利用“”组成的复合组成的复合命题，称为等值式复合命题，记作命

10、题，称为等值式复合命题，记作“PQ”（读作（读作“P当且仅当当且仅当Q”）。）。当当P P和和Q Q的真值相同时的真值相同时,P,PQ Q取真取真,否则取假。否则取假。PQPQ001010100111例例10非本仓库工作人员，一律不得入内。非本仓库工作人员，一律不得入内。解解令令P：某人是仓库工作人员；：某人是仓库工作人员；Q Q：某人可以进入仓库。：某人可以进入仓库。则上述命题可表示为则上述命题可表示为PQ。例例1111 黄山比喜马拉雅山高，当且仅当黄山比喜马拉雅山高，当且仅当3 3是素数是素数 令令P P：黄山比喜马拉雅山高；：黄山比喜马拉雅山高；Q Q：3 3是素数是素数 本例可符号化为

11、本例可符号化为P PQ Q 从汉语的语义看，从汉语的语义看，P与与Q之间并无联系，但就联结之间并无联系，但就联结词词的定义来看，因为的定义来看，因为P的真值为假，的真值为假，Q的真值为真，的真值为真，所以所以PQ的真值为假。的真值为假。对于上述五种联结词，应注意到：对于上述五种联结词，应注意到：复合命题的真值只取决于构成它的各原子命题的真复合命题的真值只取决于构成它的各原子命题的真值，而与这些原子命题的内容含义无关。值，而与这些原子命题的内容含义无关。三、命题符号化三、命题符号化利用联结词可以把许多日常语句符号化。基本步骤如下：利用联结词可以把许多日常语句符号化。基本步骤如下：（1 1）从语句

12、中分析出各原子命题，将它们符号化；）从语句中分析出各原子命题，将它们符号化；（2）使用合适的命题联结词，把原子命题逐个联结起）使用合适的命题联结词，把原子命题逐个联结起来，组成复合命题的符号化表示。来，组成复合命题的符号化表示。例例12用符号形式表示下列命题。用符号形式表示下列命题。（1）如果明天早上下雨或下雪，那么我不去学校）如果明天早上下雨或下雪，那么我不去学校（2）如果明天早上不下雨且不下雪，那么我去学校。）如果明天早上不下雨且不下雪，那么我去学校。（3）如果明天早上不是雨夹雪，那么我去学校。）如果明天早上不是雨夹雪，那么我去学校。（4）只有当明天早上不下雨且不下雪时，我才去学校。）只有

13、当明天早上不下雨且不下雪时，我才去学校。解解 令令P：明天早上下雨；：明天早上下雨；Q：明天早上下雪；：明天早上下雪；R：我去学校。：我去学校。（2）（）（PPQQ）R；（1）（）（PQ）R；（4 4）RR（PP Q Q）（3）(PQ）R；例例13将下列命题符号化将下列命题符号化（1）派小王或小李出差；派小王或小李出差；（2）我们不能既划船又跑步；我们不能既划船又跑步；（3）如果你来了，那么他唱不唱歌将看你是否伴奏而定；如果你来了，那么他唱不唱歌将看你是否伴奏而定；（4）如果李明是体育爱好者，但不是文艺爱好者，那么如果李明是体育爱好者，但不是文艺爱好者，那么李明不是文体爱好者；李明不是文体爱好

14、者；（5）假如上午不下雨，我去看电影，否则就在家里看书。假如上午不下雨，我去看电影，否则就在家里看书。解解（1）令令P：派小王出差；：派小王出差；Q：派小李出差。：派小李出差。命题符号化为命题符号化为PQ。（2）令令P：我们划船；：我们划船；Q：我们跑步。则命题可：我们跑步。则命题可表示为表示为(PQ）。（3）令令P：你来了；：你来了；Q：他唱歌；：他唱歌；R：你伴奏。：你伴奏。则命题可表示为则命题可表示为P（QR）（4）令令P：李明是体育爱好者；：李明是体育爱好者；Q：李明是文艺爱好者。：李明是文艺爱好者。则命题可表示为则命题可表示为（PQ）（PQ）（5）令令P：上午下雨；：上午下雨；Q：我

15、去看电影；：我去看电影；R：我在家读书。：我在家读书。则命题可表示为则命题可表示为（PQ）（PR）。练习练习1-11.判断下列语句哪些是命题，若是命题，则指出其真值。判断下列语句哪些是命题，若是命题，则指出其真值。（1）只有小孩才爱哭。只有小孩才爱哭。（2）X+6=Y（3）银是白的。银是白的。（4）起来吧，我的朋友。起来吧，我的朋友。(是是假假)(不是不是)(是是真真)(不是不是)2将下列命题符号化将下列命题符号化 （1 1）我看见的既不是小张也不是老李。）我看见的既不是小张也不是老李。解解 令令P：我看见的是小张；：我看见的是小张；Q：我看见的是老李。：我看见的是老李。则该命题可表示为则该命

16、题可表示为 P Q（2）如果晚上做完了作业并且没有其它的事，他就会如果晚上做完了作业并且没有其它的事，他就会看电视或听音乐。看电视或听音乐。解解令令P：他晚上做完了作业；：他晚上做完了作业；Q：他晚上有其它的事；：他晚上有其它的事；R：他看电视；：他看电视；S：他听音乐。：他听音乐。则该命题可表示为则该命题可表示为（P Q）（RS）卡盟 卡盟 Microsoft Office PowerPoint，是微软公司的演示文稿软件。用户可以在投影仪或者计算机上进行演示，也可以将演示文稿打印出来，制作成胶片，以便应用到更广泛的领域中。利用Microsoft Office PowerPoint不仅可以创建

17、演示文稿，还可以在互联网上召开面对面会议、远程会议或在网上给观众展示演示文稿。Microsoft Office PowerPoint做出来的东西叫演示文稿，其格式后缀名为：ppt、pptx；或者也可以保存为：pdf、图片格式等命题公式命题公式一一、命题公式的概念命题公式的概念1.命题常元命题常元一个表示确定命题的大写字母或一个表示确定命题的大写字母或T和和F。2命题变元命题变元一个没有指定具体内容的命题符号。一个没有指定具体内容的命题符号。一个命题变元当没有对其赋予内容时，它一个命题变元当没有对其赋予内容时，它的真值不能确定，一旦用一个具体的命题代入，的真值不能确定，一旦用一个具体的命题代入，

18、它的真值就确定了。它的真值就确定了。3.命题公式命题公式命题公式命题公式(或简称公式或简称公式)是由是由0(F)、1(T)和命题变元以和命题变元以及命题联结词按一定的规则产生的符号串。及命题联结词按一定的规则产生的符号串。定义定义1-6(命题公式的递归定义。命题公式的递归定义。)0(F)，1(T)是命题公式；是命题公式；命题变元是命题公式；命题变元是命题公式；如果如果A是命题公式，则是命题公式，则A是命题公式；是命题公式；如果如果A和和B是命题公式，则是命题公式，则(AB),(AB),(AB),(AB)也是命题公式；也是命题公式；有限次地利用上述有限次地利用上述而产生的符号串是命题公式。而产生

19、的符号串是命题公式。例例1下列符号串是否为命题公式。下列符号串是否为命题公式。P(QPR)；(PQ)(QR)解解不是命题公式。不是命题公式。是命题公式。是命题公式。二、真值指派二、真值指派命题公式代表一个命题，但只有当公式中的每一命题公式代表一个命题，但只有当公式中的每一个命题变元都用一个确定的命题代入时，命题公式才个命题变元都用一个确定的命题代入时，命题公式才有确定的真值，成为命题。有确定的真值，成为命题。定义定义17设设F F为含有命题变元为含有命题变元P P1 1，P P2 2，,P,Pn n的命题公式，对的命题公式，对P P1 1，P P2 2，,P,Pn n分别指定一个真值分别指定一

20、个真值,称称为对公式为对公式F F的一组的一组真值指派真值指派。公式与其命题变元之间的真值关系，可以用真值公式与其命题变元之间的真值关系，可以用真值表的方法表示出来。表的方法表示出来。例例2给给出公式出公式 F=(F=(（PQPQ）（QRQR）)(P(PR R）的真值）的真值表。表。解解 公式公式F F的真值表如下：的真值表如下：三、公式类型三、公式类型定义定义1-8如果对于命题公式如果对于命题公式F所包含的命题变元的任所包含的命题变元的任何一组真值指派，何一组真值指派，F的真值恒为真，则称公式的真值恒为真，则称公式F为为重言式重言式(或或永真公式永真公式)，常用，常用“1”(T)表示。相反地

21、，若对于表示。相反地，若对于F所包含的所包含的命题变元的任何一组真值指派，命题变元的任何一组真值指派，F的真值恒为假，则称公式的真值恒为假，则称公式F为为矛盾式矛盾式(或或永假公式永假公式)，常用，常用“0”(F)表示。如果至少有表示。如果至少有一组真值指派使公式一组真值指派使公式F的真值为真，则称的真值为真，则称F为为可满足公式可满足公式。例例3构造下列命题公式的真值表，并判断它们是何构造下列命题公式的真值表，并判断它们是何种类型的公式种类型的公式(PQ)(PQ)；(QP)(PQ)；(PQ)(PQ)(QR)QR)(PPR)R)。解解 令令F F1 1=(P=(PQ)Q)(P(P Q)Q)，F

22、 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)的真值表自己做一下，它是可满足公式。的真值表自己做一下，它是可满足公式。命题公式的等值关系和蕴含关系命题公式的等值关系和蕴含关系一、命题公式的等值关系一、命题公式的等值关系定义定义1-9设设A和和B是两个命题公式是两个命题公式,P1,P2,Pn是所有出现于是所有出现于A和和B中的命题变元

23、，如果对于中的命题变元，如果对于P1,P2,Pn的任一组真值指派，的任一组真值指派，A和和B的真值都相同的真值都相同,则称公式则称公式A和和B等等值值，记为，记为AB,称称AB为等值式为等值式。注意注意：（1 1）符号）符号“”与与“”的区别与联系。的区别与联系。“”不是联结词，不是联结词，A AB B不表示一个公式，它表示两不表示一个公式，它表示两个公式间的一种关系，即等值关系。个公式间的一种关系，即等值关系。“”是联结词，是联结词，A AB B是一个公式。是一个公式。AB当且仅当当且仅当AB是永真公式。是永真公式。（2）可以验证等值关系是等价关系。可以验证等值关系是等价关系。即即自反性自反

24、性：对任意公式：对任意公式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。二、基本的等值式二、基本的等值式设设P、Q、R是命题变元，下表中列出了是命题变元，下表中列出了24个最基本的等值式个最基本的等值式:编号公公式式E1E1E2E2E3E3E4E4E5E5E6E6E7E7PQQP交换律PQQP交换律(PQ)RP(QR)结合律(PQ)RP(QR)结合律P(Q

25、R)(PQ)(PR)分配律P(QR)(PQ)(PR)分配律P0P同一律P1P同一律PP1互否律PP0互否律（P）P双重否定律PPP等幂律PPP等幂律编号公公式式E8E8E9E9E10E10E11E12E13E14E15P11零一律P00零一律P（PQ）P吸收律P（PQ）P吸收律（PQ）PQ德.摩根定律（PQ）PQ德.摩根定律PQPQPQ(PQ)(PQ)P(QR)(PQ)RPQ(PQ)(QP)PQQP三、等值式的判别三、等值式的判别有两种方法：真值表方法，命题演算方法有两种方法：真值表方法，命题演算方法1、真值表方法、真值表方法例例1用真值表方法证明用真值表方法证明E10：(P Q)PQ解解令：

26、令：A=(P Q)，B=PQ，构造，构造A，B以及以及AB的真值表如下：的真值表如下：PQP Q(P Q)P Q PQAB000111110110100111100101 由于公式由于公式AB所标记的列全为所标记的列全为1，因此，因此AB。10100001例例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.110

27、111例例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不成立。不成立。101100111(1)代入规则代入规则代入规则代入规则对于重言式中的任一命题变元出现的对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。每一处均用同一命题公式代入，得到的仍是重言式。

28、2等值演算方法等值演算方法例如例如F=(PQ)(QP)是重言式，若是重言式，若用公式用公式AB代换命题变元代换命题变元P得公式得公式F1=(AB)Q)(Q(AB)，F1仍是重言式。仍是重言式。注意：因为注意：因为AB当且仅当当且仅当AB是重言式。所以，是重言式。所以，若对于等值式中的任一命题变元出现的每一处均用同若对于等值式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等值式。一命题公式代入，则得到的仍是等值式。(2)置置换规则换规则 定义定义1-101-10 设设C C是命题公式是命题公式A A的一部分的一部分(即即C C是是公式公式A A中连续的几个符号中连续的几个符号)，

29、且，且C C本身也是一个命题公本身也是一个命题公式，则称式，则称C C为公式为公式A A的的子公式。子公式。例如例如 设公式设公式A=(A=(PQ)PQ)(P PQ)Q)(R(R 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。(3)(3)等值演算等值演算 等值演算是指利用

30、已知的一些等值式，根据置换等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。一些等值式的过程。由代入规则知前述的基本等值式，不仅对任意的命由代入规则知前述的基本等值式，不仅对任意的命题变元题变元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(分配律分配律

31、)(PR)QE10(德德.摩根定律摩根定律)(PR)QE11所以所以(PQ)(RQ)(PR)Q例例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(交换律，吸收律交换律，吸收律)例例4判别下列公式的类型。判别下列公式的类型。（1）Q(P(PQ)（2）(PQ)P解解（1）Q(P(PQ)Q(P(PQ)E11,E6Q(P P)(PQ)E3Q(1(PQ)E5Q

32、(PQ)E4Q P QE10(Q Q)PE1,E20E5,E8所以所以Q(P(PQ)是矛盾式。是矛盾式。（2）(PQ)P(PQ)P E11 P E9 于是该公式是可满足式。于是该公式是可满足式。三、命题公式的蕴含关系三、命题公式的蕴含关系 定义定义1-111-11 设设A A，B B是两个公式，若公式是两个公式，若公式A AB B是重是重言式，即言式，即A AB B1 1，则称公式，则称公式A A蕴含公式蕴含公式B B，记作，记作A AB B。称称“A AB”B”为为蕴含式蕴含式。注意：注意：符号符号“”和和“”的区别和联系与符号的区别和联系与符号“”与与“”的区别和联系类似。的区别和联系类似

33、。“”不是联结词，不是联结词，“AB”不是公式，它表示公式不是公式，它表示公式A与与B之间存在蕴之间存在蕴含关系。含关系。“”是联系词，是联系词，AB是一个公式。是一个公式。AB当且仅当当且仅当AB是永真公式是永真公式。A AB B是偏序关系是偏序关系即即自反性自反性：AA。反对称反对称：若：若AB，BA，则，则AB。传递性传递性：若：若AB，BC，则，则AC。反对称性的证明：反对称性的证明：设设AB且且BA，由定义由定义7-11AB1且且BA1于是于是AB(AB)(BA)E141 11因此因此AB传递性的证明：传递性的证明：设设A AB B，B BC C，则则A AB B1 1，B BC C

34、1 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)四、基本的蕴含式四、基本的蕴含式编号蕴蕴含含式式I1PQPI2PQQI3PPQI4QPQI5PPQI6QPQI7(PQ)PI8(PQ)Q 设设P P、Q Q、R R是是命命题题变变元元，下下表表中中列列出出了了1616个个最最基本的蕴含式。基本的蕴含式。编号蕴蕴含含式式I9PQPQ或表示为或表示为：P、QPQI10 P(P Q)Q P

35、、(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)五、蕴含式的判别五、蕴含式的判别判定判定“AB”是否成立的问题可转化为判定是否成立的问题可转化为判定AB是否为重言式，有下述判定方法：是否为重言式，有下述判定方法：（1）真值表；）真值表；（2）等值演算；）等值演算；（3）假定前件）假定前件A为真；为真；（4）假定后件）假定后件B为假。为假。1.真值表方法真值表方法例例4证明证明I14：(PQ)(PR)(QR)R证明证明

36、令公式令公式F=(PQ)(PR)(QR)R，其真值表如下：其真值表如下：公式公式F对任意的一组真值指派取值均为对任意的一组真值指派取值均为1，故，故F是重言式。是重言式。2.等值演算方法等值演算方法例例5证明证明 I I1111：PP（P PQ Q）Q Q 证明证明(P(PP(PQ)Q)Q Q (P(P(PQ)PQ)Q Q E E1111 (PP(PQ)PQ)Q Q E E1010(PQ)PQ)(PQ)PQ)E E2 2 1 1 代入规则代入规则,E,E5 5 因此因此 PP（P PQ Q）Q Q 3.假定前件假定前件A真真 假定前件假定前件A A为真，检查在此情况下，其后件为真，检查在此情况

37、下，其后件B B是否也为真。是否也为真。ABAB001011100111例例6证明证明I12:Q（PQ）P证明证明令前件令前件 Q（PQ）为真，）为真，则则 Q为真为真,且且PQ为真。为真。于是于是Q为假，因而为假，因而P也为假。由此也为假。由此 P为真。为真。故蕴含式故蕴含式I12成立。成立。4、假定后件假定后件B假假 假定后件假定后件B B为假，检查在此情况下，其前件为假，检查在此情况下，其前件A A是否也为假是否也为假.例例7证明蕴含式证明蕴含式(PQ)(RS)(P R)(Q S)证证明明令令后后件件(P R)(Q S)为为假假，则则P R为为真真，Q S为为假假,于是于是P、R均为真，

38、而均为真，而Q和和S至少一个为假。至少一个为假。由此可知由此可知PQ与与RS中至少一个为假中至少一个为假,因此因此(PQ)(RS)为假为假.故上述蕴含式成立。故上述蕴含式成立。练习练习1-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)QE112 2判定蕴含式判定蕴含式P P(Q QR)R)(P PQ)Q)(P PR)R)是是否成立否成立解解假定后件假定后件

39、(PQ)(PR)为假，为假，则则PQ为真，为真，PR为假。为假。由由P PR R为假为假,得得P P为真，为真，R R为假。为假。又又PQ为真，故得为真，故得Q为真。为真。于是于是P为真，为真，QR为假。为假。从而从而P(QR)为假。为假。因此蕴含式成立。因此蕴含式成立。范式范式一、析取范式和合取范式析取范式和合取范式定义定义1-121-12一个命题公式若它具有一个命题公式若它具有P P1 1*PP2 2*PPn n*的形式（的形式（n1n1），其中），其中P Pi i*是命题变是命题变元元P Pi i或其否定或其否定PPi i，则称其为，则称其为质合取式质合取式(基本积基本积)。例如例如,P

40、QRS,PQRS是由命题变元是由命题变元P P、Q Q、R R、S S组成组成的一质合取式的一质合取式(基本积基本积)。定义定义1-131-13一个命题公式若具有一个命题公式若具有P P1 1*PP2 2*PPn n*（n1n1）的形式，其中）的形式，其中P P*i i是命题变是命题变元元P Pi i或是其否定或是其否定PPi i ，则称其为，则称其为质析取式质析取式(基本和基本和)。例如例如,QPRQPR是由命题变元是由命题变元P P、Q Q、R R组成的一组成的一质析取式质析取式(基本和基本和)。定理定理1-41-4(1)一质合取式为永假式的充分必要条件是，它同时包含某一质合取式为永假式的

41、充分必要条件是，它同时包含某个命题变元个命题变元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的

42、真值取的真值取0，这与，这与A为永为永真式矛盾。真式矛盾。例如例如A=P1P2P3.则则(P1,P2,P3)=(0,1,0)的指派，使的指派，使A的真值为的真值为0.充分性充分性：设：设A含命题变元含命题变元Pi和和Pi，而，而PiPi是永真式，是永真式，由结合律和零一律，由结合律和零一律，A的真值必为的真值必为1，故，故A也是永真式。也是永真式。定义定义1-141-14质合取式的析取称为析取范式。即质合取式的析取称为析取范式。即具有具有A A1 1AA2 2AAn n(n1)(n1)的形式的公式，其中的形式的公式，其中A Ai i是是质合取式。质合取式。例如例如，F F1 1=P(PQ)R(

43、=P(PQ)R(PP QR)QR)是一析是一析取范式。取范式。定义定义1-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)也是一也是一合取范式。合取范式。二、求公式的析取范式和合取范式二、求公式的析取范式和合取范式任何一个命题公式都可以变换为与它等值的析任何一个命题公式都可以变换为与它

44、等值的析取范式或合取范式。取范式或合取范式。按下列步骤进行：按下列步骤进行：（1 1）利用）利用E E1111，E E1212和和E E1414消去公式中的运算符消去公式中的运算符“”和和“”；(2)(2)利用德利用德 摩根定律将否定符号摩根定律将否定符号“”向内深向内深入，使之只作用于命题变元；入，使之只作用于命题变元；（3 3）利用双重否定律）利用双重否定律E E6 6将将 (P)P)置换成置换成P P；（4 4）利用分配律、结合律将公式归约为合取范）利用分配律、结合律将公式归约为合取范式或析取范式。式或析取范式。例例1求求F1=(P(QR)S的合取范式和析取范式的合取范式和析取范式解解F

45、1(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,E13例例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,E1

46、0(PQ)(P Q)（合取范式）（合取范式）E2,E9(P(P Q)(Q(P Q)E3(P P)(P Q)(PQ)(Q Q)（析取范式）（析取范式）E3定理定理1-51-5（1）公式）公式A为永真式的充分必要条件是，为永真式的充分必要条件是，A的合取范式中的合取范式中每一质析取式至少包含一对互为否定的析取项。每一质析取式至少包含一对互为否定的析取项。三、利用范式判定公式类型三、利用范式判定公式类型证明证明（2）必要性必要性（用反证法）：（用反证法）：假设假设AA1A2An中某个中某个Ai不包含一对互为否不包含一对互为否定的合取项，定的合取项，（2）公式）公式A为永假式的充分必要条件是，为永假式

47、的充分必要条件是，A的析取范式中的析取范式中每一质合取式至少包含一对互为否定的合取项。每一质合取式至少包含一对互为否定的合取项。则由定理则由定理7-4知，知，Ai不是矛盾式。不是矛盾式。于是存在一组真值指派使于是存在一组真值指派使Ai取值为真。取值为真。对同一组真值指派，对同一组真值指派，A的取值也必为真，这与的取值也必为真，这与A是矛盾是矛盾式不符，假设不成立。式不符，假设不成立。充分性充分性：假设任一：假设任一Ai(1in)中含有形如中含有形如PP合取式，其合取式，其中中P为命题变元。于是由定理为命题变元。于是由定理7-4知，每一知，每一Ai(1in)都为矛盾都为矛盾式，因此式，因此A1A

48、2An必为矛盾式，即必为矛盾式，即A为矛盾式。为矛盾式。因此因此A的析取范式中每一质合取的析取范式中每一质合取式至少包含一对互为否定的合取项。式至少包含一对互为否定的合取项。例例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根据定理根据定理7-57-5，A A不是矛盾式。不是矛盾式。又又A AP(P(P(P(QP)QP)（PPPP）（PP QP)QP)（合取范式）（合取范式）E E3 3由定理由定理1-51-5知，

49、知，A A是重言式。是重言式。例例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由定理由定理1-5，该公式不是永假公式。，该公式不是永假公式。(PP)(P Q)（合取范式）（合取范式）E1，E 3由定理由定理7-5，该公式也不是永真公式。，该公式也不是永真公式。由上可知，该公式是一可满足公式。由上可知，该公式是一可满足公式。又又P(P Q)(P Q)P四、主析取范式和主合取范式四、主析取范式和主合取范式定义定义1-161-16设有命题变元设有命题变元P P

50、1 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