离散数学课件Thefirstcourse.ppt

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

1、 集合论与数理逻辑南京邮电大学计算机学院江苏省无线传感网高技术研究重点实验室江苏省无线传感网高技术研究重点实验室My E-mail:My E-mail:黄 海 平教材：离散数学左孝凌 编著概概 述述关于这门课程，有两点要提醒大家注意的：关于这门课程，有两点要提醒大家注意的：本身比较抽象，概念多，比较枯燥，内容一环扣本身比较抽象，概念多，比较枯燥，内容一环扣一环，难学好。一环，难学好。要学好也不难。建议各位上课认真听讲，踏踏实要学好也不难。建议各位上课认真听讲，踏踏实实地学好每一个基本概念，基本内容，这样课后实地学好每一个基本概念，基本内容，这样课后就不用花太多的时间复习。就不用花太多的时间复习

2、。作业建议独立完成，不会解答的可以讨论，但不作业建议独立完成，不会解答的可以讨论，但不可以不做，一定要向别人请教，直到弄懂为止。可以不做，一定要向别人请教，直到弄懂为止。千万不要抄作业！千万不要抄作业！说明说明总学时：总学时：64学时学时本课程为考试本课程为考试+限选科目限选科目答疑时间：答疑时间：每周一晚上，每周一晚上，17:3019:00答疑地点：行政南楼答疑地点：行政南楼432室室总评成绩：平时成绩占总评成绩：平时成绩占10%，期中考试占，期中考试占20%，期末考试成绩占，期末考试成绩占70%。（每周上课后。（每周上课后交作业）交作业）教学网站的选课密钥是教学网站的选课密钥是 discr

3、ete 主要参考书：主要参考书：（1）上海科技文献出版社）上海科技文献出版社 离散数学离散数学 理论理论.分析分析.题解题解 左孝凌等编著左孝凌等编著（2）清华大学出版社）清华大学出版社 离散数学学练考全面冲刺离散数学学练考全面冲刺 王海艳编著王海艳编著（3）清华大学出版社）清华大学出版社 离散数学习题与解析离散数学习题与解析 胡新启等编著胡新启等编著（4）高等教育出版社）高等教育出版社 离散数学及其应用第五版影印版离散数学及其应用第五版影印版 Discrete Mathematics and Its Applications Kenneth H.Rosen 等著等著说明说明离散数学是现代数学

4、的一个重要分支，是计算机科学中的基础课程，离散数学是现代数学的一个重要分支，是计算机科学中的基础课程，它具有两个特点：它具有两个特点：(1)以离散量为研究对象，以讨论离散量的结构和相互之间的以离散量为研究对象，以讨论离散量的结构和相互之间的关系为主要目标，这些对象一般是有限个或可数个元素，充分描述关系为主要目标，这些对象一般是有限个或可数个元素，充分描述了计算机科学离散性的特点，与我们以前学过的连续数学如高等数了计算机科学离散性的特点，与我们以前学过的连续数学如高等数学、数学分析、函数论形成了鲜明对比。学、数学分析、函数论形成了鲜明对比。(2)它是数学中的一个分支，因而它有数学的味道，比如用一

5、它是数学中的一个分支，因而它有数学的味道，比如用一些符号、引进一些定义、运用定理推导等等。因而学习离散数学，些符号、引进一些定义、运用定理推导等等。因而学习离散数学，对提高我们的抽象能力，归纳能力、逻辑推理能力将有很大帮助。对提高我们的抽象能力，归纳能力、逻辑推理能力将有很大帮助。离散数学的内容很多，由于学时有限，我们只介绍其基本内容：离散数学的内容很多，由于学时有限，我们只介绍其基本内容：数理逻辑、集合论、代数结构与希尔代数，图论与代数系统。数理逻辑、集合论、代数结构与希尔代数，图论与代数系统。课程简介课程简介第一篇数理逻辑第一篇数理逻辑 逻辑学是研究思维形式和规律的科学。它包括辨证逻辑和形

6、式逻辑学是研究思维形式和规律的科学。它包括辨证逻辑和形式逻辑。而数理逻辑是：用数学方法来研究形式逻辑的推理规则。这逻辑。而数理逻辑是：用数学方法来研究形式逻辑的推理规则。这里所指的数学方法，就是指引进一套符号体系，所以又称为符号逻里所指的数学方法，就是指引进一套符号体系，所以又称为符号逻辑。下面介绍数理逻辑的最基本的内容：命题逻辑和谓词逻辑。辑。下面介绍数理逻辑的最基本的内容：命题逻辑和谓词逻辑。第一章第一章 命题逻辑命题逻辑 1-1 命题及其表示法命题及其表示法 所谓所谓命题命题是指能够判别真假的陈述句。一个命题，总是具有是指能够判别真假的陈述句。一个命题，总是具有一个确定的一个确定的“值值

7、”，称之为，称之为“真值真值”。一种是。一种是True,记为记为T，另一，另一种是种是False,记为记为F。只有能够判别真假的陈述句才是命题。只有能够判别真假的陈述句才是命题。例（例（1）：你是小可爱。）：你是小可爱。这是一个命题这是一个命题 ，其真值为，其真值为T。第一篇数理逻辑第一篇数理逻辑（4）：）：本句是假的。本句是假的。若它是命题，若其值为若它是命题，若其值为T，则本句是真的；若说它是假，则本，则本句是真的；若说它是假，则本句是真的。这是悖论，不能算是命题。（不能确定真假）句是真的。这是悖论，不能算是命题。（不能确定真假）（2）：）：芙蓉姐姐是大美女么？（疑问句）芙蓉姐姐是大美女么

8、？（疑问句）（3）：）：我勒个去！（感叹句）我勒个去！（感叹句）（5）：）：我正在说谎。我正在说谎。若它是命题，则应有确定的真值。若它是命题，则应有确定的真值。若为若为T，则我确定说谎，我讲的是真话，与说谎矛盾。，则我确定说谎，我讲的是真话，与说谎矛盾。若为若为F，则我不在说谎，我说的是真话，则，则我不在说谎，我说的是真话，则“我确实是在说谎我确实是在说谎”1-1 命题及其表示法命题及其表示法成立，与成立，与“不在说谎不在说谎”矛盾。所以它不是命题，不能确定真假，是矛盾。所以它不是命题，不能确定真假，是悖论。悖论。（6）：X=3 不是命题不是命题 不能判断真假。不能判断真假。命题有两种类型。一

9、是原子命题（不能分解为更简单的陈述句）命题有两种类型。一是原子命题（不能分解为更简单的陈述句）二是复合命题二是复合命题（由原子命题、联结词和标点符号复合构成的命题）（由原子命题、联结词和标点符号复合构成的命题）如：我学英语，或者我学日语。如：我学英语，或者我学日语。由两个原子命题，联结词由两个原子命题，联结词“或者或者”，标点符号，标点符号“，”构成。构成。又如又如：格格巫和阿滋猫是难兄难弟。格格巫和阿滋猫是难兄难弟。它是原子命题。它是原子命题。关于联结词我们下一节将做详细介绍。关于联结词我们下一节将做详细介绍。1-1 命题及其表示法命题及其表示法 在数理逻辑中，用大写英文字母在数理逻辑中，用

10、大写英文字母P，Q，R,表示命题，或表示命题，或带下标的大写字母如带下标的大写字母如Pi ，P j,或数字如或数字如12等表示命题，这等表示命题，这些表示命题的符号称为命题标识符。些表示命题的符号称为命题标识符。如果一个命题标识符表示确定的命题，称之为如果一个命题标识符表示确定的命题，称之为命题常量命题常量；如果一个命题标识符表示任意的命题，称之为如果一个命题标识符表示任意的命题，称之为命题变元命题变元；命题变元不能确定真值，不是命题，就如函数中自变量不代命题变元不能确定真值，不是命题，就如函数中自变量不代表特定值一样，只是变量。但当命题变元用一个特定命题取代表特定值一样，只是变量。但当命题变

11、元用一个特定命题取代时，就能确定真值，如时，就能确定真值，如P用一特定命题取代，称对用一特定命题取代，称对P进行指派。进行指派。另外，当命题变元表示原子命题时，称为原子变元。另外，当命题变元表示原子命题时，称为原子变元。1-1 命题及其表示法命题及其表示法将介绍五个联结词（基本的）将介绍五个联结词（基本的）（1）否定）否定 若若P是一命题，则是一命题，则P的否定是一个新的命题，的否定是一个新的命题，记作记作 P，读作，读作“非非P”，其取值情况如下：，其取值情况如下：P PT FF T如如 P：上海是一个大城市。：上海是一个大城市。P：上海不是一个大城市。：上海不是一个大城市。或：上海是个不大

12、的城市。或：上海是个不大的城市。P取值为取值为T，而，而 P取值为取值为F。1-2 联结词联结词又如又如 Q：南京是一个小城市。：南京是一个小城市。Q：南京不是个小城市。：南京不是个小城市。Q值为值为F，Q取值为取值为T“”是一元运算，相当于数学中的是一元运算，相当于数学中的“求相反数求相反数”运算。运算。（2）合取（与）合取（与）P，Q是命题，是命题，P，Q的合取是一个复合命题，记做的合取是一个复合命题，记做P Q，读，读作作“P与与Q”，或，或“P且且Q”。P Q当且仅当当且仅当P与与Q的值都真时，其值的值都真时，其值为为T，否则为，否则为F。1-2 联结词联结词P Q P QT T TT

13、 F FF T FF F F注意：这里的“与”运算与日常生活中的“与”意义不尽相同。注注：列表时列表时P，Q均是先取均是先取T后后取取F如如P：今天下雨；：今天下雨；Q：明天下雨：明天下雨P Q：今天下雨且明天下雨。：今天下雨且明天下雨。又如，又如，P：我们去看电影；：我们去看电影；Q：房间里有张桌子。：房间里有张桌子。P Q：我们去看电影和房间里有张桌子。：我们去看电影和房间里有张桌子。上述命题上述命题P Q在日常生活中无意义，无联系，但在数理逻辑中，在日常生活中无意义，无联系，但在数理逻辑中，P Q是一新的命题。是一新的命题。“”是二元运算。是二元运算。1-2 联结词联结词（3）析取（或）

14、析取（或）P，Q是命题，是命题，P与与Q的析取是复合命题，的析取是复合命题，记做记做P Q，读作，读作“P或或Q”。P Q：只要：只要PQ之一之一T，则则P Q值为值为T，否则为，否则为F。P Q P QT T TT F TF T TF F F从取值可以看出，这里的或是指从取值可以看出，这里的或是指“可兼或可兼或”，即，即P，Q均可都为均可都为T，也，也可一个为可一个为T，另一为，另一为F。1-2 联结词联结词 例如例如1：菲尔普斯是：菲尔普斯是200米蝶泳或米蝶泳或400米个人混合泳冠军。米个人混合泳冠军。P:菲尔普斯是菲尔普斯是200米蝶泳冠军。米蝶泳冠军。Q:菲尔普斯是菲尔普斯是400米

15、个人混合米个人混合泳冠军。泳冠军。则原命题：则原命题：P Q 可兼或可兼或但实际中也有不可兼或的例子但实际中也有不可兼或的例子.例如例如2:今天晚上我在家看电视或去剧场看戏今天晚上我在家看电视或去剧场看戏.P:今晚我在家看电视。今晚我在家看电视。Q:今天晚上我去剧场看戏。今天晚上我去剧场看戏。用用PQ表示是否正确呢？表示是否正确呢？P Q PQ 原命题原命题 T T T F1-2 联结词联结词排斥或、不可兼或，不能用排斥或、不可兼或，不能用PQ表示，具体表示法以后再学。表示，具体表示法以后再学。同学可以自己先思考。又如同学可以自己先思考。又如3：他昨天做了二十或三十道习题。或：他昨天做了二十或

16、三十道习题。或：“大概大概”，不是复合命题。，不是复合命题。(4)条件条件P、Q是命题，是命题，P 和和Q的条件是一个复合命题，记作的条件是一个复合命题，记作PQ，读作读作“若若P 则则Q”或或“如果如果P，那么，那么Q”，P前件，前件，Q后件。后件。PQ仅当仅当P为为T，Q为为F时，其值为时，其值为F，其余情况皆为，其余情况皆为T。如：如：P:我借到这本小说。我借到这本小说。Q:我今夜读完这本小说。我今夜读完这本小说。PQ:如果我借到这本小说，那么今夜我就读完它。如果我借到这本小说，那么今夜我就读完它。1-2 联结词联结词1-2 联结词联结词P Q PQT T TT F FF T TF F

17、T注注：P为为F时，时，PQ总为总为T。而在日常生活中往往无法判断，在数理。而在日常生活中往往无法判断，在数理逻辑中，我们作逻辑中，我们作“善意的推定善意的推定”，确定值为，确定值为T。另外在数理逻辑中，。另外在数理逻辑中，PQ前后中可根本毫无联系也能构成条件式。前后中可根本毫无联系也能构成条件式。如如 P:1+1=2 Q:今天下雨。今天下雨。PQ:如果如果1+1=2，那么今天下雨。，那么今天下雨。1-2 联结词联结词(5)双条件双条件 P、Q是命题，其双条件命题是一复合命题，记作是命题，其双条件命题是一复合命题，记作P Q，读作，读作“P当且仅当当且仅当Q”,仅当仅当P、Q真假值相同时，真假

18、值相同时，P Q为为T,否则为否则为F。P Q P Q (P、Q同为同为F时，时，P Q值为值为T)T T T 如：如：P:两个三角形全等。两个三角形全等。T F F Q:两个三角形对应边相等。两个三角形对应边相等。F T F R:两个三角形对应角相等。两个三角形对应角相等。F F T P Q:两个三角形全等当且仅当它们对应边相等。两个三角形全等当且仅当它们对应边相等。P R:两个三角形全等当且仅当它们对应角相等。两个三角形全等当且仅当它们对应角相等。1-2 联结词联结词总结：共介绍了五个联结词。总结：共介绍了五个联结词。一元运算一元运算 P，P 否定式否定式 二元运算二元运算 P,Q P Q

19、 合取式合取式 P Q 析取式析取式 P Q 条件式条件式 P Q 双条件式双条件式 又如又如 P：2+2=4,Q：雪是白的。：雪是白的。P Q：2+2=4当且仅当雪是白的。当且仅当雪是白的。P、Q可毫无联系。可毫无联系。前面我们介绍了命题的概念，它是可以判别真假的陈述句。前面我们介绍了命题的概念，它是可以判别真假的陈述句。学习了其表示方法，介绍了五种基本联结词：否定、合取、析取、学习了其表示方法，介绍了五种基本联结词：否定、合取、析取、条件、双条件。我们将日常生活中的命题用原子命题以及这些联条件、双条件。我们将日常生活中的命题用原子命题以及这些联结词表达，将之符号化为公式。但是许多日常生活中

20、的命题是不结词表达，将之符号化为公式。但是许多日常生活中的命题是不能用这五个联结词单独写出，而且不是所有一些命题变元、联结能用这五个联结词单独写出，而且不是所有一些命题变元、联结词组成的符号串都有意义的公式。而数理逻辑首先就要引进一些词组成的符号串都有意义的公式。而数理逻辑首先就要引进一些符号体系，将实际生活中的命题符号化，给出其命题公式，也就符号体系，将实际生活中的命题符号化，给出其命题公式，也就是翻译。是翻译。下面我们来介绍下面我们来介绍 1-3命题公式与翻译命题公式与翻译首先给出命题公式的定义首先给出命题公式的定义 定义：命题公式（合式公式），按规律构成：定义：命题公式（合式公式），按规

21、律构成：1-3命题公式与翻译命题公式与翻译例如：判别下列式子是否是公式？例如：判别下列式子是否是公式？(P Q)(P Q (P (P Q)(P Q)(P Q)R)(P Q)(PQ R)(P Q)R)其中（其中（1）为基础，（）为基础，（2），（），（3）为归纳，（）为归纳，（4）为界限，这是一个）为界限，这是一个递归的定义。递归的定义。是是 否是否否是否否否否否否否1-3命题公式与翻译命题公式与翻译(1)单个命题变元是合式公式单个命题变元是合式公式(2)若若P是一公式，则是一公式，则 P也是公式；也是公式；(3)若若P,Q是公式，则是公式，则(P Q),(P Q),(P Q),(P Q)也是公

22、式：也是公式：(4)只有有限次地应用（只有有限次地应用（1）、（）、（2）、（）、（3）所得的结果才是公式。）所得的结果才是公式。注意：注意：“（”，“）”必须成对出现。必须成对出现。从定义可以看出：从定义可以看出：（1）为了减少括号的数目，我们约定：）为了减少括号的数目，我们约定：1.最外层括号可以省略：最外层括号可以省略：2.运算优先级为：运算优先级为：3.具有相同优先级的联结词，按其出现的次序进行运算。具有相同优先级的联结词，按其出现的次序进行运算。1-3命题公式与翻译命题公式与翻译（2）命题公式实际上是一函数，值域为）命题公式实际上是一函数，值域为T,F),每一个命题变元每一个命题变元

23、取值也是取值也是T,F,因而它没有真假值，只有当公式中命题变元因而它没有真假值，只有当公式中命题变元用确定的命题代入后，才得到一个命题，才能判断其真假。用确定的命题代入后，才得到一个命题，才能判断其真假。例例1：他既聪明又用功。他既聪明又用功。1-3命题公式与翻译命题公式与翻译如如(P Q)R)(P Q)可改写为：可改写为：P Q R P Q有了命题公式的定义后，我们如何将日常生活中的命题用具体的公有了命题公式的定义后，我们如何将日常生活中的命题用具体的公式表示呢？也就是说，如何将之翻译成公式呢？举例说明：式表示呢？也就是说，如何将之翻译成公式呢？举例说明：首先找出原子命题，有两个：他聪明，用

24、首先找出原子命题，有两个：他聪明，用P表示；他用表示；他用功，用功，用Q表示。表示。P：他聪明。：他聪明。Q：他用功。：他用功。联结词联结词“既既又又”和联结词和联结词“与与”意思一致。意思一致。所以原命题所对应的命题公式为：所以原命题所对应的命题公式为：P Q因而翻译一个命题，关键有两个：因而翻译一个命题，关键有两个：1-3命题公式与翻译命题公式与翻译例例2：他虽聪明但不用功。他虽聪明但不用功。这里原子命题也是这里原子命题也是P.Q.联结词联结词“虽虽但但”也也是是“与与”，所以公式应为：，所以公式应为：PQ。(1)找出所有原子命题，并符号表示出来。找出所有原子命题，并符号表示出来。(2)找

25、出原子命题之间关系对应的联结词。找出原子命题之间关系对应的联结词。例例3：如果明天上午七点不下刀子，则我去学校。如果明天上午七点不下刀子，则我去学校。P：明天上午七点下刀子；：明天上午七点下刀子；Q：我去学校。：我去学校。“如果如果则则”与与“若，则若，则”一致，所以公式为：一致，所以公式为：PQ。例例4：除非你努力，否则你将失败。除非你努力，否则你将失败。P：你努力；：你努力；Q：你将失败。：你将失败。“除非除非否则否则”相当于相当于“如果不如果不那么那么”，所以译为：，所以译为：PQQP1-3命题公式与翻译命题公式与翻译例例5：说数理逻辑枯燥无味或毫无价值，那是不对的。说数理逻辑枯燥无味或

26、毫无价值，那是不对的。P：说数理逻辑是枯燥无味的；：说数理逻辑是枯燥无味的；Q：说数理逻辑是毫无价值的。：说数理逻辑是毫无价值的。这里这里“或或”是是“可兼或可兼或”,与与“”意义一致，所以译为：意义一致，所以译为：（PQ）。）。例例6：上海到北京的上海到北京的14次列车是下午五点半或六点开。次列车是下午五点半或六点开。P：上海到北京的：上海到北京的14次列车是下午五点半开；次列车是下午五点半开；Q：上海到北京的：上海到北京的14次列车是下午六点开；次列车是下午六点开；这里的这里的“或或”是是“不可兼或不可兼或”,因而用因而用“PQ”是错误的。是错误的。1-3命题公式与翻译命题公式与翻译例例7

27、：张三或李四都可以做这件事。张三或李四都可以做这件事。P：张三可以做这件事；：张三可以做这件事；Q：李四可以做这件事：李四可以做这件事意为张三可以做，李四也能做这件事，所以意为张三可以做，李四也能做这件事，所以P Q我们对我们对P、Q取不同值看原命题的真值情况：取不同值看原命题的真值情况：PQ原命题原命题P Q（P Q）利用联结词组合起来利用联结词组合起来TT F T F P、Q真值相同时为真值相同时为F，否则为，否则为TTF T F T 原命题与原命题与(P Q)真值相同真值相同FT T F T (P Q)FF F T F1-3命题公式与翻译命题公式与翻译以上三个例子以上三个例子“或或”意义

28、各不相同，在翻译公式时，务必准确意义各不相同，在翻译公式时，务必准确理解其等价含义。理解其等价含义。例例8：我们要做到身体好、学习好、工作好、为祖国四化建设而奋我们要做到身体好、学习好、工作好、为祖国四化建设而奋斗。斗。P：我们要做到身体好；：我们要做到身体好；Q：我们要做到学习好；：我们要做到学习好；R：我们要做到工作好；：我们要做到工作好；S：我们要为祖国四化建设而奋斗。：我们要为祖国四化建设而奋斗。PQ RS对于命题翻译就举这么多例子，在做题时要针对具体情况而定。对于命题翻译就举这么多例子，在做题时要针对具体情况而定。1-3命题公式与翻译命题公式与翻译在介绍真值表前，先介绍分量定义：在介

29、绍真值表前，先介绍分量定义：公式公式PQS，其中，其中P、Q、S称为公式的分量。称为公式的分量。定义：命题公式中，对于分量指派真值的各种可能组合，就确定义：命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。公式的真值表。1、公式、公式P Q，PQ P P Q分量为：分量为：P、Q T T F T T F F F此表就称为公式此表就称为公式PQ的真值表的真值表 F T T T F F T T1-4真值表与等价公式真值表与等价公式2、（、（P Q）P，其真值表为：，其真值表为：P

30、Q P P Q（P Q）PT T F TFT F F FFF T T FFF F T FF1-4真值表与等价公式真值表与等价公式3、（、（PQ）（P Q），其真值表为：），其真值表为：P Q P Q P Q P Q （P Q)(P Q)T T T F FFTT F F F TFFF T F T FFFF F F T TTT4、（、（P Q）（PQ），其真值表为：），其真值表为：1-4真值表与等价公式真值表与等价公式P Q P Q (P Q)P Q P Q (P Q)(P Q)T T T F F F F TT F F T F T T TF T F T T F T TF F F T T T T T

31、（1）从上面看出，有一些公式，不论分量如何指派，真值永为真，从上面看出，有一些公式，不论分量如何指派，真值永为真，称为永真公式，记为称为永真公式，记为T；有些则真值永为假，记为；有些则真值永为假，记为F。（2）可以看出，在真值表中，命题公式真值的取值数目决定于分可以看出，在真值表中，命题公式真值的取值数目决定于分量的个数。一个分量，取值可能为量的个数。一个分量，取值可能为2；两个分量，取值可能为；两个分量，取值可能为4；n个分量，取值可能为个分量，取值可能为 。1-4真值表与等价公式真值表与等价公式5.再看再看 P Q，P Q这两个公式的真值表，（为便于比较，写这两个公式的真值表，（为便于比较

32、，写在一起）在一起）P Q P P Q P Q T T F T T T F F F F F T T T T F F T T T（3）对于任何指派，这两个公式的真值完全相同，我们把这样的对于任何指派，这两个公式的真值完全相同，我们把这样的两个公式称为是等价的。两个公式称为是等价的。1-4真值表与等价公式真值表与等价公式定义：两个公式定义：两个公式A和和B，设，设 ，为所有出现于为所有出现于A和和B中的中的原子变元，若给原子变元，若给 ，任一组真值指派，任一组真值指派，A 和和B的真值的真值相同，则称相同，则称A和和B是是等价等价的，或的，或逻辑相等逻辑相等。记做。记做A B所以，由上式可得所以，

33、由上式可得 P Q P Q 再由真值表可得再由真值表可得 （P Q）（P Q）P Q另外，利用真值表可验证下列命题定律：另外，利用真值表可验证下列命题定律：(非常重要非常重要)1，对合律，对合律：P P2，幂等律，幂等律：P P P，P P P3，结合律，结合律：（P Q）R P （Q R）（P Q）R P （Q R）1-4真值表与等价公式真值表与等价公式4，交换律，交换律：P Q Q P，P Q Q P5，分配律，分配律：P （Q R）（P Q）（P R）P （Q R）（P Q）（P R）6，吸收律，吸收律：P （P Q）P，P （P Q）P7，德，德.摩根律摩根律：（P Q）P Q，（P

34、Q）P Q8，同一律，同一律：P F P，P T P9，零律，零律：P T T，P F F10，否定律，否定律：P P T，P P F1-4真值表与等价公式真值表与等价公式“”对于对于“”的分配律，相当与数学中：的分配律，相当与数学中：x (y+z)=x y+x z有了这些等价的公式，我们就考虑能否将它们相互替代，以简化一有了这些等价的公式，我们就考虑能否将它们相互替代，以简化一些运算。首先引入子公式。些运算。首先引入子公式。定义定义：若：若X是公式是公式A的一部分，且的一部分，且X是公式，则称是公式，则称X是是A的子公式。的子公式。等价代换定理等价代换定理：设：设X是公式是公式A的子公式，且

35、的子公式，且X Y，如果将，如果将A中的中的X用用Y代替，得到公式代替，得到公式B，则，则A B。证明：证明：X Y，在相应变元的任意指派下，在相应变元的任意指派下，X 和和Y的真值相同的真值相同 A和和B 在相应变元指派下，也取相同的值，故在相应变元指派下，也取相同的值，故A B利用等价代换定理可以证明一些公式的等价性利用等价代换定理可以证明一些公式的等价性1-4真值表与等价公式真值表与等价公式例1：求证；Q （P （P Q）Q P 证：X=P （P Q）P=Y ，用P替换X得到Q P 两式等价。例2：求证（P Q）（P Q）P 证：（P Q）（P Q）P （Q Q）P T P 分配律 否定

36、律 同一律 1-4真值表与等价公式真值表与等价公式例3 求证：证：左1-4真值表与等价公式真值表与等价公式1-4真值表与等价公式真值表与等价公式讲完讲完1-3，1-4两节，我们来看书上几条习题。两节，我们来看书上几条习题。P12.(6)用命题形式进行分析。用命题形式进行分析。P：它占据空间。：它占据空间。R：它不断变化：它不断变化 Q：它有质量。：它有质量。S：它是物质。：它是物质。则这个人开始主张：则这个人开始主张：P Q R S 后来变为：后来变为：（P Q S）（S R）P19.(9)1.A C B C A B 否否.若有某种指派，使若有某种指派，使C的真值为的真值为T，但，但A为为T，B为为F。则则A C与与B C真值为真值为T，但，但A B不成立。不成立。复习复习如如 A：P Q.C ：Q B：P 2.A C B C?A B 否否 A：P Q C：Q B：P 3.A B?A B 是是 A B 则对任一组真值指派。则对任一组真值指派。A与与 B真值相真值相 同，则同，则A与与B的真值也必相同。的真值也必相同。由定义由定义A B。请同学们自己做请同学们自己做 P17(1)作业：作业：P12 (5)(7)P18(7)(8）复习复习