第九章离散数学PPT学习教案

1、会计学1第九章离散数学第九章离散数学 9.1 命题和命题联结词命题和命题联结词 一、一、 命题的概念命题的概念 命题命题：是能分辨真假的陈述句。是能分辨真假的陈述句。 例例1 判断下列语句是否是命题。判断下列语句是否是命题。 （1）空气是人生存所必需的。）空气是人生存所必需的。 （2）请把门关上。）请把门关上。 （3）南京是中国的首都。）南京是中国的首都。 （4）你吃饭了吗？）你吃饭了吗？ （5）x=3。（。（6）啊，真美呀！）啊，真美呀！ (7) 明年春节是个大晴天。明年春节是个大晴天。 解解 语句（语句（1）,（3）,（5），），(7)(7)是陈述句是陈述句 （1）、（）、（3）、）、(7

2、)(7)是命题是命题 用真值来描述命题是用真值来描述命题是“真真” 还是还是“假假”。分别用。分别用“1”和和“0 0”表示表示 命题用大写的拉丁字母命题用大写的拉丁字母A、B、C、P、Q、或者带下标的大写的字母来表示。或者带下标的大写的字母来表示。 例例2 判断下列陈述句是否是命题。判断下列陈述句是否是命题。 P：地球外的星球上也有人；：地球外的星球上也有人； Q：小王是我的好朋友；：小王是我的好朋友； 解解 P、Q是命题是命题 第1页/共80页 二、命题联结词二、命题联结词 原子命题原子命题 ：由简单句形成的命题。由简单句形成的命题。 复合命题：复合命题：由一个或几个原子命题通过联结词的由

3、一个或几个原子命题通过联结词的联接而构成的命题。联接而构成的命题。 例例3 A：李明既是三好学生又是足球队员。：李明既是三好学生又是足球队员。 B：张平或者正在钓鱼或者正在睡觉。：张平或者正在钓鱼或者正在睡觉。 C：如果明天天气晴朗，那么我们举行运动会：如果明天天气晴朗，那么我们举行运动会。第2页/共80页定义五种联结词（或称命题的五种运算）定义五种联结词（或称命题的五种运算）。1. 否定否定“” 定义定义9-1 设设P是一个命题，利用是一个命题，利用“”和和P组成的复合命题称为组成的复合命题称为P的否命题，记作的否命题，记作“P” (读作读作“非非P”)。命题命题P P取值为真时，命题取值为

4、真时，命题P P取值为假；命题取值为假；命题P P取值为假时，命题取值为假时，命题P P取值为真。取值为真。 例例4 设设P：上海是一个城市；：上海是一个城市；Q：每个自然数都是偶数。则有：每个自然数都是偶数。则有 P：上海不是一个城市：上海不是一个城市; Q：并非每个自然数都是偶数。：并非每个自然数都是偶数。 P P P 1 0 0 1第3页/共80页 2合取合取“” 定义定义9-2 设设P和和Q是两个命题，由是两个命题，由P、Q利用利用“”组成的复合命题，称为合取式复合命题，记作组成的复合命题，称为合取式复合命题，记作“P Q”（读作（读作“P且且Q”）。）。 当且仅当命题当且仅当命题P

5、P和和Q Q均取值为真时，均取值为真时，P P Q Q才取值为真。才取值为真。 例例5 5 设设P P：我们去看电影。：我们去看电影。Q Q：房间里有十张桌子。则：房间里有十张桌子。则P P Q Q表示表示“我们去看电影并且房间里有十张桌子。我们去看电影并且房间里有十张桌子。” PQPQ000010100111第4页/共80页3. 析取析取“” 定义定义9-39-3 由命题由命题P P和和Q Q利用利用“”组成的复合命题，称为析取式复合命题，记作组成的复合命题，称为析取式复合命题，记作“PQPQ”（读作（读作“P P或或Q Q”）。）。 当且仅当当且仅当P P和和Q Q至少有一个取值为真时，至

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

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

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

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

10、山比喜马拉雅山高；：黄山比喜马拉雅山高；Q Q：3 3是素数是素数 本例可符号化为本例可符号化为P PQ Q 从汉语的语义看，从汉语的语义看，P与与Q之间并无联系，但就联结之间并无联系，但就联结词词的定义来看，因为的定义来看，因为P的真值为假，的真值为假，Q的真值为真，的真值为真，所以所以PQ的真值为假。的真值为假。 对于上述五种联结词，应注意到：对于上述五种联结词，应注意到： 复合命题的真值只取决于构成它的各原子命题的真复合命题的真值只取决于构成它的各原子命题的真值，而与这些原子命题的内容含义无关。值，而与这些原子命题的内容含义无关。第9页/共80页 三、命题符号化三、命题符号化 利用联结词

11、可以把许多日常语句符号化。基本步骤如下：利用联结词可以把许多日常语句符号化。基本步骤如下： （1 1）从语句中分析出各原子命题，将它们符号化；）从语句中分析出各原子命题，将它们符号化； （2）使用合适的命题联结词，把原子命题逐个联结起来，组成复合命题的符号化表示。）使用合适的命题联结词，把原子命题逐个联结起来，组成复合命题的符号化表示。 例例12 用符号形式表示下列命题。用符号形式表示下列命题。 （1）如果明天早上下雨或下雪，那么我不去学校）如果明天早上下雨或下雪，那么我不去学校 （2）如果明天早上不下雨且不下雪，那么我去学校。）如果明天早上不下雨且不下雪，那么我去学校。 （3）如果明天早上不

12、是雨夹雪，那么我去学校。）如果明天早上不是雨夹雪，那么我去学校。 （4）只有当明天早上不下雨且不下雪时，我才去学校。）只有当明天早上不下雨且不下雪时，我才去学校。 解解 令令P：明天早上下雨；：明天早上下雨； Q：明天早上下雪；：明天早上下雪； R：我去学校。：我去学校。 （2）（）（P P Q Q）R； （1）（）（PQ） R；（4 4）RR（P P Q Q） （3）(PQ）R；第10页/共80页 例例13 将下列命题符号化将下列命题符号化 （1） 派小王或小李出差；派小王或小李出差； （2） 我们不能既划船又跑步；我们不能既划船又跑步； （3） 如果你来了，那么他唱不唱歌将看你是否伴奏而定

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

14、表示为则命题可表示为 P（QR） （4） 令令P：李明是体育爱好者；：李明是体育爱好者；Q：李明是文艺爱好者。：李明是文艺爱好者。 则命题可表示为则命题可表示为（P Q）（P Q） （5） 令令P：上午下雨；：上午下雨；Q：我去看电影；：我去看电影；R：我在家读书。：我在家读书。 则命题可表示为则命题可表示为（P Q）（PR）。 第11页/共80页练习练习7-1 1. 判断下列语句哪些是命题，若是命题，则指出其真值。判断下列语句哪些是命题，若是命题，则指出其真值。 （1） 只有小孩才爱哭。只有小孩才爱哭。 （2） X+6=Y （3） 银是白的。银是白的。 （4） 起来吧，我的朋友。起来吧，我的

15、朋友。( 是是 假假 ) ( 不是不是 )( 是是 真真 ) ( 不是不是 ) 2 将下列命题符号化将下列命题符号化 （1 1）我看见的既不是小张也不是老李。）我看见的既不是小张也不是老李。 解解 令令P：我看见的是小张；：我看见的是小张；Q：我看见的是老李。：我看见的是老李。 则该命题可表示为则该命题可表示为PQ （2）如果晚上做完了作业并且没有其它的事，他就会看电视或听音乐。如果晚上做完了作业并且没有其它的事，他就会看电视或听音乐。 解解 令令 P：他晚上做完了作业；：他晚上做完了作业；Q：他晚上有其它的事；：他晚上有其它的事； R：他看电视；：他看电视； S：他听音乐。：他听音乐。 则该

16、命题可表示为则该命题可表示为（PQ）（RS）第12页/共80页 9.2 命题公式命题公式 一一 、 命题公式的概念命题公式的概念 1. 命题常元命题常元 一个表示确定命题的大写字母。一个表示确定命题的大写字母。 2命题变元命题变元 一个没有指定具体内容的命题符号。一个没有指定具体内容的命题符号。 一个命题变元当没有对其赋予内容时，它的真一个命题变元当没有对其赋予内容时，它的真值不能确定，一旦用一个具体的命题代入，它值不能确定，一旦用一个具体的命题代入，它的真值就确定了。的真值就确定了。 第13页/共80页3. 命题公式命题公式 命题公式（或简称公式）是由命题公式（或简称公式）是由0、1和命题变

17、元以及命题联结词按一定的规则产生的符号串。和命题变元以及命题联结词按一定的规则产生的符号串。 定义定义9-6 （命题公式的递归定义。）（命题公式的递归定义。） （1） 0，1是命题公式；是命题公式； （2） 命题变元是命题公式；命题变元是命题公式； （3） 如果如果A是命题公式，则是命题公式，则A是命题公式；是命题公式； （4） 如果如果A和和B是命题公式，则（是命题公式，则（AB），）， （AB）,(AB）,(A B）也是命题公式；）也是命题公式； 有限次地利用上述（有限次地利用上述（1）（4）而产生的符号串是命题公式。）而产生的符号串是命题公式。 例例1 下列符号串是否为命题公式。下列符号

18、串是否为命题公式。 （1） P(QPR）；）； （2）（）（PQ）（QR） 解解 （1） 不是命题公式。不是命题公式。 （2 2） 是命题公式。是命题公式。 第14页/共80页二、真值指派二、真值指派 命题公式代表一个命题，但只有当公式中的每一个命题变元都用一个确定的命题代入时，命题公式才有确定的真值，成为命题。命题公式代表一个命题，但只有当公式中的每一个命题变元都用一个确定的命题代入时，命题公式才有确定的真值，成为命题。 定义定义97 设设F F为含有命题变元为含有命题变元P P1 1，P P2 2，,P,Pn n的命题公式，对的命题公式，对P P1 1，P P2 2，,P,Pn n分别指定

19、一个真值分别指定一个真值, ,称为对公式称为对公式F F的一组的一组真值指派真值指派。 公式与其命题变元之间的真值关系，可以用真值表的方法表示出来。公式与其命题变元之间的真值关系，可以用真值表的方法表示出来。 第15页/共80页 例例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 0

20、1 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 0第16页/共80页 三、公式类型三、公式类型 定义定义9-8 如果对于命题公式如果对于命题公式F所包含的命题变元的任何一组真值指派，所包含的命题变元的任何一组真值指派，F的真值恒为真，则称公式的真值恒为真，则称公式F为为重言式重言式（或（或永真公式永真公式），常用），常用“1”表示。相反地，若对于表示。相反地，若对于F所包

21、含的命题变元的任何一组真值指派，所包含的命题变元的任何一组真值指派，F的真值恒为假，则称公式的真值恒为假，则称公式F为为矛盾式矛盾式（或（或永假公式永假公式），常用），常用“0”表示。如果至少有一组真值指派使公式表示。如果至少有一组真值指派使公式F的真值为真，则称的真值为真，则称F为为可满足公式可满足公式 。 例例3 构造下列命题公式的真值表，并判断它们是何种类型的公式构造下列命题公式的真值表，并判断它们是何种类型的公式 （1）（）（PQ） （PQ）；）； （2）（）（QP）（PQ）；）； （3 3）（）（PQPQ）（QRQR）（PPR R）。）。 第17页/共80页 解解 令令F F1 1=

22、 =（P PQ Q）（P P Q Q），），F F2 2= =（Q QP P）（ PQ PQ） F F1 1和和F F2 2的真值表如下：的真值表如下：P QPPQP Q(PQ)F1QPPQF20 0101011000 1110110101 0010111001 100101100由上可知：由上可知： F F1 1是是重言式重言式 , F F2 2是是矛盾式。矛盾式。 (3)的真值表如第的真值表如第4页所示，它是可满足公式。页所示，它是可满足公式。第18页/共80页9.3 命题公式的等值关系和蕴含关系命题公式的等值关系和蕴含关系一、命题公式的等值关系一、命题公式的等值关系 定义定义9-9 设设

23、A和和B是两个命题公式是两个命题公式, P1, P2, , Pn 是所有出现于是所有出现于A和和B中的命题变元，如果对于中的命题变元，如果对于P1, P2, , Pn 的任一组真值指派，的任一组真值指派，A和和B的真值都相同的真值都相同,则称公式则称公式A和和B等值等值，记为，记为A B,称称 AB为等值式为等值式。注意注意：（1 1）符号）符号“”与与“”的区别与联系。的区别与联系。 “”不是联结词，不是联结词，A AB B不表示一个公式，它表示两个公式间的一种关系，即等值关系。不表示一个公式，它表示两个公式间的一种关系，即等值关系。 “”是联结词，是联结词，A AB B是一个公式。是一个公

24、式。 AB当且仅当当且仅当AB是永真公式。是永真公式。第19页/共80页 （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。第20页/共80页二、基本的等值式二、基本的等值式 设设P、Q、R是命题变元，下表中列出了是命题变元，下表中列出了24个最基本的

25、等值式个最基本的等值式:编号 公公 式式E1E1E2E2E3E3E4E4E5E5E6E6E7E7 PQQP 交换律 PQQP 交换律 (PQ)R P(QR) 结合律 (PQ)R P(QR) 结合律 P(QR) (PQ)(PR) 分配律 P(QR) (PQ)(PR) 分配律 P0P 同一律 P1P 同一律 PP1 互否律 PP0 互否律 （P）P 双重否定律 PPP 等幂律 PP P 等幂律 第21页/共80页编号 公公 式式E8E8E9E9E10E10E11E12E13E14E15P11 零一律 P00 零一律P（PQ）P 吸收律P（PQ）P 吸收律 （PQ）PQ 德.摩根定律 （PQ）PQ

26、德.摩根定律PQPQPQ (PQ)(PQ)P (QR) (PQ) RPQ (PQ)(QP) PQQP第22页/共80页三、等值式的判别三、等值式的判别 有两种方法：真值表方法，命题演算方法有两种方法：真值表方法，命题演算方法 1、真值表方法、真值表方法 例例1 用真值表方法证明用真值表方法证明 E10： (P Q) PQ 解解 令：令：A= (P Q)，B= PQ，构造，构造A，B 以及以及A B的真值表如下：的真值表如下： PQP Q (P Q) P Q PQAB000111110110100111100101 由于公式由于公式AB所标记的列全为所标记的列全为1，因此，因此AB。 10100

27、001第23页/共80页例例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.110111第24页/共80页 例例3 用真值表方法判断用真值表方法判断PQPQ是否成立是否成立. 解解 令令A=PA=PQ Q，B=B= P PQ Q 构造构造A A，B B以及以及A AB B的真值表的真值表PQ P Q PQPQ

28、AB0011111011001001100 由于公式由于公式A AB B所标记的列不全为所标记的列不全为1 1，A AB B不是永真公式，因此不是永真公式，因此A AB B不成立。不成立。101100111第25页/共80页 (1) 代入规则代入规则 代入规则代入规则 对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。对于重言式中的任一命题变元出现的每一处均用同一命题公式代入，得到的仍是重言式。2等值演算方法等值演算方法 例如例如 F=（PQ）（ QP）是重言式，若）是重言式，若用公式用公式AB代换命题变元代换命题变元P得公式得公式 F1=（AB）Q）（ Q（AB）

29、，）， F1仍是重言式。仍是重言式。注意：因为注意：因为A B当且仅当当且仅当A B是重言式。所以，若对于等值式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等值式。是重言式。所以，若对于等值式中的任一命题变元出现的每一处均用同一命题公式代入，则得到的仍是等值式。第26页/共80页(2) 置置 换规则换规则 定义定义9-109-10 设设C C是命题公式是命题公式A A的一部分（即的一部分（即C C是公式是公式A A中连续的几个符号），且中连续的几个符号），且C C本身也是一个命题公式，则称本身也是一个命题公式，则称C C为公式为公式A A的的子公式。子公式。 例如例如 设公式

30、设公式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。 第27页/共80页(3)(3) 等值演算等值演算 等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。

31、等值演算是指利用已知的一些等值式，根据置换规则、代入规则以及等值关系的可传递性推导出另外一些等值式的过程。 由代入规则知前述的基本等值式，不仅对任意的命题变元由代入规则知前述的基本等值式，不仅对任意的命题变元P P，Q Q，R R是成立的，而且当是成立的，而且当P P，Q Q，R R分别为命题公式时，这些等值式也成立分别为命题公式时，这些等值式也成立 例例2 证明命题公式的等值关系：证明命题公式的等值关系： （PQ）（RQ）（PR）Q；证明证明 （PQ）（RQ） （ PQ）( RQ) E11 （ P R）Q E3( 分配律分配律) (PR)Q E10(德德.摩根定律摩根定律) (PR) Q E

32、11 所以（所以（PQ）（RQ）（PR）Q第28页/共80页 例例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 Q E 1，E9(交换律，吸收律交换律，吸收律) 第29页/共80页例例4 判别下列公式的类型。判别下列公式的类型。 （1） Q ( P（ PQ）) （2）（）（PQ）

33、 P解解（1） Q （ P（ PQ） Q （P（ PQ） E11,E6 Q （P P）（PQ） E3 Q （1（PQ） E5 Q （PQ） E4 Q P Q E10 （Q Q） P E1,E2 0 E5,E8 所以所以Q ( P ( PQ)是矛盾式。是矛盾式。 （2） （PQ） P （ PQ） P E11 P E9 于是该公式是可满足式。于是该公式是可满足式。 第30页/共80页三、命题公式的蕴含关系三、命题公式的蕴含关系 定义定义9-119-11 设设A A，B B是两个公式，若公式是两个公式，若公式A AB B是重言式，即是重言式，即A AB B1 1，则称公式，则称公式A A蕴含公式蕴含

34、公式B B，记作，记作A AB B。称。称“A AB B”为为蕴含式蕴含式。 注意：注意：符号符号“”和和 “”的区别和联系与符号的区别和联系与符号“”与与“”的区别和联系类似。的区别和联系类似。 “”不是联结词，不是联结词， “AB”不是公式，它表示公式不是公式，它表示公式A与与B之间存在蕴含关系。之间存在蕴含关系。 “”是联系词，是联系词，AB是一个公式。是一个公式。 AB当且仅当当且仅当AB是永真公式是永真公式 。第31页/共80页 A AB B是偏序关系是偏序关系 即即 自反性自反性：AA。 反对称反对称：若：若AB，BA，则，则AB。 传递性传递性：若：若AB，BC，则，则 AC。

35、反对称性的证明：反对称性的证明： 设设AB且且BA， 由定义由定义7-11 AB1且且BA1于是于是AB(AB) (BA) E14 1 1 1因此因此 AB第32页/共80页传递性的证明：传递性的证明： 设设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) 第3

36、3页/共80页 四、基本的蕴含式四、基本的蕴含式 编号蕴蕴 含含 式式I1PQPI2PQQI3P PQI4QPQI5P PQI6QPQI7 (PQ)PI8 (PQ) Q 设设P P、Q Q、R R是命题变元，下表中列出了是命题变元，下表中列出了1616个最基本的蕴含式。个最基本的蕴含式。第34页/共80页编号蕴蕴 含含 式式I9PQPQ 或表示为或表示为：P、QPQI10 P (P Q) Q P、(P Q)QI11P (PQ)Q P、PQQI12 Q (PQ)P Q、PQPI13(PQ) (QR)PR PQ、QRPRI14(P Q) (PR) (QR) R P Q、PR、QRRI15PQ(P

37、R)(Q R)I16PQ(P R)(Q R)第35页/共80页五、蕴含式的判别五、蕴含式的判别 判定判定“A B”是否成立的问题可转化为判定是否成立的问题可转化为判定A B是否为重言式，有下述判定方法：是否为重言式，有下述判定方法： （1）真值表；）真值表； （2）等值演算；）等值演算；（3）假定前件）假定前件A为真；为真； （4）假定后件）假定后件B为假。为假。 1. 真值表方法真值表方法 例例4 证明证明I14 ：(（PQ）（P R）（Q R）) R 证明证明 令公式令公式 F =（PQ）（PR）（QR）R， 其真值表如下：其真值表如下： 第36页/共80页 公式公式F对任意的一组真值指派

38、取值均为对任意的一组真值指派取值均为1，故，故F是重言式。是重言式。P Q RP Q RPQPQPRPRQ RQ R(PQ) (PR(PQ) (PR）（ Q RQ 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 1第37页/共80页 2. 等值

39、演算方法等值演算方法 例例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 第38页/共80页 3. 假定前件假定前件A真真 假定前件假定前件A A为真，检查在此情况下，其后件为真，检查在此情况下，其后件B B是否也为真。是否也为真。 ABAB001011100111 例例6证明证明 I12 : Q （PQ） P证明证明令前件令前件

40、 Q（PQ）为真，）为真，则则 Q为真为真, 且且PQ为真。为真。于是于是Q为假，因而为假，因而P也为假。由此也为假。由此 P为真。为真。故蕴含式故蕴含式 I12 成立。成立。第39页/共80页 4、 假定后件假定后件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与与R

41、S中至少一个为假中至少一个为假, 因此因此(PQ) (RS)为假为假.故上述蕴含式成立。故上述蕴含式成立。第40页/共80页练习练习 7-31判断下列等值式是否成立判断下列等值式是否成立 （1）（）（PQ） （R Q）（PR） Q （2） （PQ）（P Q）（ PQ）解解（1）（）（PQ）（RQ）（ PQ） （ RQ） E11（ P R）Q E3 （PR）Q E10（2）（）（P Q）（ PQ） (（ PQ）（ QP）) E6，E10 (（PQ）（QP）) E11 （PQ） E14（PR）Q E11第41页/共80页2 2判定蕴含式判定蕴含式P P（Q QR R） （P PQ Q）（P PR

42、R）是否成立）是否成立 解解假定后件（假定后件（PQ）（PR）为假）为假，则则PQ为真，为真，PR为假。为假。由由P PR R为假为假, ,得得P P为真，为真，R R为假。为假。 又又PQ为真，故得为真，故得Q为为真。真。于是于是P为真，为真，QR为假。为假。从而从而 P（QR）为假。）为假。因此蕴含式成立。因此蕴含式成立。第42页/共80页9.49.4范式范式一、 析取范式和合取范式析取范式和合取范式 定义定义9-129-12 一个命题公式若它具有一个命题公式若它具有P P1 1* *PP2 2* *PPn n* *的的形式（形式（n1n1），其中），其中P Pi i* *是命题变元是命题

43、变元P Pi i或其否定或其否定P Pi i ，则称其为则称其为质合取式质合取式。 例如例如, ,PQRSPQRS是由命题变元是由命题变元P P、Q Q、R R、S S组组成的一质合取式。成的一质合取式。 定义定义9-139-13 一个命题公式若具有一个命题公式若具有P P1 1* *PP2 2* *PPn n* *（n1n1）的形式，其中）的形式，其中P P* *i i是命题变元是命题变元P Pi i或是其否定或是其否定P Pi i ，则称其为，则称其为质析取式质析取式。 例如例如, , QPQPR R是由命题变元是由命题变元P P、Q Q、R R组成的组成的一质析取式。一质析取式。 第43

44、页/共80页 定理定理9-49-4 （1）一质合取式为永假式的充分必要条件是，它同时包含某个命题变元一质合取式为永假式的充分必要条件是，它同时包含某个命题变元P及其否定及其否定P。 （2）一质析取式为永真式的充分必要条件是，它同时包含某个命题变元一质析取式为永真式的充分必要条件是，它同时包含某个命题变元P及其否定及其否定P。 证明证明（2）必要性必要性：假设：假设A= P1*P2*Pn*为一质析取式，且为一质析取式，且A为一永真式。为一永真式。 (反证法反证法) 假设假设A式中不同时包含任一命题变元及其否定式中不同时包含任一命题变元及其否定， 则在则在A中，当中，当Pi*为为Pi时指派时指派P

45、i取取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也是永真式。也是永真式。 第44页/共80页定义定义9-149-14质合取式的析取称为析取范式。即质合取式的析取称为析取范式。即具有具有A A1

46、 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)

47、R)也是一合也是一合取范式。取范式。 第45页/共80页二、求公式的析取范式和合取范式二、求公式的析取范式和合取范式任何一个命题公式都可以变换为与它等值的析任何一个命题公式都可以变换为与它等值的析取范式或合取范式。取范式或合取范式。按下列步骤进行：按下列步骤进行：（1 1）利用）利用E E1111，E E1212和和E E1414消去公式中的运算符消去公式中的运算符“”和和“”； (2) (2) 利用德利用德摩根定律将否定符号摩根定律将否定符号“ ”向内向内深入，使之只作用于命题变元；深入，使之只作用于命题变元； （3 3）利用双重否定律）利用双重否定律E E6 6将将 ( ( P)P)置换成

48、置换成P P； （4 4）利用分配律、结合律将公式归约为合取范）利用分配律、结合律将公式归约为合取范式或析取范式。式或析取范式。第46页/共80页 例例1 求求F1=(P(QR)S的合取范式和析取范式的合取范式和析取范式 解解 F1 (P( QR)S E11 P ( QR)S E10 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

49、R) （析取范式）（析取范式） E9 ,E13第47页/共80页例例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)（析取范式）（析取范式） E3第48页/共80页 定理定理9-59-5（1）公式）公式A为永真式的

50、充分必要条件是，为永真式的充分必要条件是，A的合取范式中每一质析取式至少包含一对互为否定的析取项。的合取范式中每一质析取式至少包含一对互为否定的析取项。 三、利用范式判定公式类型三、利用范式判定公式类型 证明证明（2）必要性必要性（用反证法）：（用反证法）：假设假设AA1A2An中某个中某个Ai不包含一对互为否定的合取项，不包含一对互为否定的合取项， （2）公式）公式A为永假式的充分必要条件是，为永假式的充分必要条件是，A的析取范式中每一质合取式至少包含一对互为否定的合取项。的析取范式中每一质合取式至少包含一对互为否定的合取项。 则由定理则由定理9-4知，知，Ai不是矛盾式。不是矛盾式。 于是

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

52、/共80页 例例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是重言式。是重言式。第50页/共80页例例4 4 利用范式判断公式利用范式判断公式P(P Q)的类型。的类型。 解解

53、 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)P第51页/共80页四、主析取范式和主合取范式四、主析取范式和主合取范式 定义定义9-169-16 设有命题变元设有命题变元P P1 1，P P2 2，,P,Pn n

54、，形如形如 的的命题公式称为是由命题变元命题公式称为是由命题变元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,(i=1,2,n).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是由是由

55、P P1 1，P P2 2，P P3 3产生的一个最大项。产生的一个最大项。 *1iniP*1iniP第52页/共80页 定义定义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

56、(P1 1 P P2 2 P P3 3) ) ( ( P P1 1P P2 2P P3 3) ) ( ( P P1 1 P P2 2P P3 3) )是一个主合取范式。是一个主合取范式。第53页/共80页 例例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 五、求公式的主析取范式和主合取范式五、求公

57、式的主析取范式和主合取范式对任一给定的公式除了用求范式时的四个步骤外，还要利用同一律、等幂律、互否律、分配律等进一步将质合取式（质析取式）变换为最小项（最大项）的形式。对任一给定的公式除了用求范式时的四个步骤外，还要利用同一律、等幂律、互否律、分配律等进一步将质合取式（质析取式）变换为最小项（最大项）的形式。第54页/共80页 F2(PQ) (PQ) ( P Q) (PQ) E11 ( P PQ) (Q PQ) E3 0 0 E 1, E 5 0 定理定理9-6 每一个不为永假的命题公式每一个不为永假的命题公式F F（P P1 1, P, P2 2, , , P, Pn n）必与一个由）必与一

58、个由P P1 1，P P2 2，P Pn n所产生的主析所产生的主析取范式等值。取范式等值。 永真公式永真公式的主析取范式包含所有的主析取范式包含所有2 2n n个最小项。个最小项。 永假公式永假公式的主析取范式是一个空公式。用的主析取范式是一个空公式。用0 0表表示。示。第55页/共80页例例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( P Q ) Q ) E E1111 ( ( P P Q)Q) (P(P (Q(QQ)Q) (

59、( 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) EQ) E 3 3 (P (P Q)Q) (P(PQ)Q) ( ( P P Q)Q) ( ( P PQ) Q) E E 7 7第56页/共80页 解解 F2 P(P( QP) E11 ( PP)( P QP) E3 11 E5,E1 1 定理定理9-7 每一个不为永真的公式每一个不为永真的公式 F(PF(P1 1, P, P2 2, , , P, Pn n）必与一个由必与一个由P P1 1, P, P2 2, , , P, Pn

60、n所产生的主合取范式等值。所产生的主合取范式等值。永假公式永假公式的主合取范式包含所有的主合取范式包含所有 2 2n n个最大项。个最大项。永真公式永真公式的主合取范式是一空公式，用的主合取范式是一空公式，用1 1表示。表示。 第57页/共80页 六、利用主范式判定公式类型六、利用主范式判定公式类型 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