离散数学及其应用第3章-命题演算与推理(下)课件.ppt

1、2022-8-5计算机应用技术研究所计算机应用技术研究所11离散数学离散数学Discrete Mathematics汪荣贵汪荣贵 教授教授合肥工业大学计算机与信息学院合肥工业大学计算机与信息学院2022-8-5计算机应用技术研究所计算机应用技术研究所2第第3 3章章 命题演算与推理命题演算与推理（下）（下）2022-8-52022-8-5 命题逻辑的演绎推理命题逻辑的演绎推理5 5 命题公式的范式命题公式的范式4 4&本章学习内容本章学习内容(下下)6 6 命题逻辑的应用命题逻辑的应用2022-8-5计算机应用技术研究所计算机应用技术研究所4命题公式的范式命题公式的范式&命题公式的范式命题公式

2、的范式J 范式的基本概念范式的基本概念4 主析取范式主析取范式4 主合取范式主合取范式4 主范式间的联系主范式间的联系2022-8-5计算机应用技术研究所计算机应用技术研究所6&范式的基本概念范式的基本概念【定义】设P是任意一个命题变量，则P和P均称为文字文字，且称P和P为互补对互补对。【定义】有限个文字的析取称为析取式析取式，也称为子句子句；有限个文字的合取称为合取式合取式，也称为短语短语。2022-8-5计算机应用技术研究所计算机应用技术研究所7&范式的基本概念范式的基本概念【定义】有限个短语的析取式称为析取范式析取范式；有限个子句的合取式称为合取范式合取范式。析取范式与合取范式统称为范式

3、范式。2022-8-5计算机应用技术研究所计算机应用技术研究所8&范式的基本概念范式的基本概念2022-8-5计算机应用技术研究所计算机应用技术研究所9&范式的基本概念范式的基本概念2022-8-5计算机应用技术研究所计算机应用技术研究所10&范式的基本概念范式的基本概念【解】（1）P、P是析取范式也是合取范式。（2）PQR是析取范式也是合取范式，但(PQR)仅是合取范式。（3）PQR是析取范式也是合取范式。（4）(PQ)(PQ)仅是析取范式。（5）(PR)(PQ)仅是合取范式。（6）P(PQ)不是析取范式，也不是合取范式。（7）(PQ)不是析取范式，也不是合取范式。2022-8-5计算机应用

4、技术研究所计算机应用技术研究所11&范式的基本概念范式的基本概念【定理】【定理】对于任意命题公式，都存在与其等值的析取范式和合取范式。2022-8-5计算机应用技术研究所计算机应用技术研究所12&范式的基本概念范式的基本概念2022-8-5计算机应用技术研究所计算机应用技术研究所13&范式构造举例范式构造举例2022-8-5计算机应用技术研究所计算机应用技术研究所14&范式构造举例范式构造举例2022-8-5计算机应用技术研究所计算机应用技术研究所15&范式构造举例范式构造举例【解】(PQ)(PR)(PQ)(PR)(RP)(PQ)(PR)(RP)(PQ)(PR)(PQ)(RP)(PQPR)(P

5、QRP)-合取范式(PQR)-化简后的合取范式PQR -析取范式。&命题公式的范式命题公式的范式4 范式的基本概念范式的基本概念J 主析取范式主析取范式4 主合取范式主合取范式4 主范式之间的联系主范式之间的联系2022-8-5计算机应用技术研究所计算机应用技术研究所17&主析取范式主析取范式2022-8-5计算机应用技术研究所计算机应用技术研究所18&主析取范式主析取范式2022-8-5计算机应用技术研究所计算机应用技术研究所19&主析取范式主析取范式这4个小项的真值取值情况如表所示：2022-8-5计算机应用技术研究所计算机应用技术研究所20&主析取范式主析取范式2022-8-5计算机应用

6、技术研究所计算机应用技术研究所21&主析取范式主析取范式2022-8-5计算机应用技术研究所计算机应用技术研究所22&主析取范式主析取范式【定义定义】析取范式析取范式 A1A2.An,其中每个其中每个Ai(i=1,2.n)都都是是小项，称之为小项，称之为主析取范式主析取范式。2022-8-5计算机应用技术研究所计算机应用技术研究所23&主析取范式主析取范式 与析取范式相比，主析取范式对其析取运算形式做了进一步规范，具有更加规整的表达形式。2022-8-5计算机应用技术研究所计算机应用技术研究所24&主析取范式主析取范式【定理】【定理】任何一个命题公式都有与之等价的主析取范式。【证明】（1）求出

7、该公式所对应的析取范式，并去重；（2）去掉析取范式中的所有永假式，例如PP；（3）若析取范式某个短语中缺少该命题公式中的命题变元，如缺少P，则可用公式 (P P)HH （3-3）（4）合并相同的小项，并用交换律进行顺序调整，得到标准的主析取范式。该定理的证明其实给出了构造主析取范式的一种具体方法，称之为等值演算法等值演算法。2022-8-5计算机应用技术研究所计算机应用技术研究所25&主析取范式主析取范式【小结】：对于任一给定的命题公式，其主析取范式的构造方法主要有两种，即真值表法真值表法和等值演算法等值演算法。真值表法真值表法：在真值表中选出公式为真的所有行，并在选出的每一行中找到该行解释所

8、对应的小项，将所有这些小项进行析取即可得到相应的主析取范式。2022-8-5计算机应用技术研究所计算机应用技术研究所26&主析取范式主析取范式【解】列如下真值表：2022-8-5计算机应用技术研究所计算机应用技术研究所27&主析取范式主析取范式2022-8-5计算机应用技术研究所计算机应用技术研究所28&主析取范式主析取范式2022-8-5计算机应用技术研究所计算机应用技术研究所29&主析取范式主析取范式2022-8-5计算机应用技术研究所计算机应用技术研究所30&主析取范式主析取范式2022-8-5计算机应用技术研究所计算机应用技术研究所31&主析取范式主析取范式2022-8-5计算机应用技

9、术研究所计算机应用技术研究所32&主析取范式主析取范式&命题公式的范式命题公式的范式4 范式的基本概念范式的基本概念4主析取范式主析取范式J 主合取范式主合取范式4 主范式之间的联系主范式之间的联系2022-8-5计算机应用技术研究所计算机应用技术研究所34&主合取范式主合取范式2022-8-5计算机应用技术研究所计算机应用技术研究所35&主合取范式主合取范式2022-8-5计算机应用技术研究所计算机应用技术研究所36&主合取范式主合取范式2022-8-5计算机应用技术研究所计算机应用技术研究所37&主合取范式主合取范式2022-8-5计算机应用技术研究所计算机应用技术研究所38&主合取范式主

10、合取范式2022-8-5计算机应用技术研究所计算机应用技术研究所39&主合取范式主合取范式2022-8-5计算机应用技术研究所计算机应用技术研究所40&主合取范式主合取范式根据真值表：2022-8-5计算机应用技术研究所计算机应用技术研究所41&主合取范式主合取范式【定理定理】任何一个命题公式都有与之等价的主合取范式。任何一个命题公式都有与之等价的主合取范式。【证明证明】（1）求出该公式所对应的合取范式）求出该公式所对应的合取范式,并去重；并去重；（2）去掉合取范式中的所有永真式）去掉合取范式中的所有永真式 (PP)（3）若合取范式的某一个短语）若合取范式的某一个短语 H 中缺少该命题公式中中

11、缺少该命题公式中的命题变元的命题变元 P，则用公式：，则用公式：()H=H将命题将命题变元变元P补进去，并用分配律展开补进去，并用分配律展开;（4）合并相同的大项，并用交换律进行顺序调整。）合并相同的大项，并用交换律进行顺序调整。该定理的证明其实给出了求主合取范式一个具体方法，称之为等值演算法等值演算法。2022-8-5计算机应用技术研究所计算机应用技术研究所42&主合取范式主合取范式 与主析取范式类似，对于任一给定的命题公式，其主合取范式的构造方法主要有两种，即真值表真值表法法和等值演算法等值演算法。真值表法真值表法：在真值表中选出公式真值为假的所有行，并在选出的每一行中找到该行解释所对应的

12、大项，将所有这些大项进行合取即可得到相应的主合取范式。2022-8-5计算机应用技术研究所计算机应用技术研究所43&主合取范式主合取范式2022-8-5计算机应用技术研究所计算机应用技术研究所44&主合取范式主合取范式2022-8-5计算机应用技术研究所计算机应用技术研究所45&主合取范式主合取范式2022-8-5计算机应用技术研究所计算机应用技术研究所46&主合取范式主合取范式2022-8-5计算机应用技术研究所计算机应用技术研究所47&主合取范式主合取范式&命题公式的范式命题公式的范式4 范式的基本概念范式的基本概念4 主析取范式主析取范式4 主合取范式主合取范式J 主范式之间的联系主范式

13、之间的联系2022-8-5计算机应用技术研究所计算机应用技术研究所49&主范式间关系主范式间关系2022-8-5计算机应用技术研究所计算机应用技术研究所50&主范式间关系主范式间关系2022-8-5计算机应用技术研究所计算机应用技术研究所51&主范式间关系主范式间关系2022-8-5计算机应用技术研究所计算机应用技术研究所52&主范式间关系主范式间关系2022-8-5计算机应用技术研究所计算机应用技术研究所53&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所54&例例 题题2022-8-5计算机应用技术研究所计算机应用技术研究所55&例例 题题2022-8-5计算机应用技术

14、研究所计算机应用技术研究所56&主范式的性质主范式的性质（1）命题公式是永真公式）命题公式是永真公式当且仅当当且仅当它的主析取它的主析取范式包含所有的极小项，此时无主合取范式或范式包含所有的极小项，此时无主合取范式或者说主合取范式为者说主合取范式为“空空”。（2）命题公式是永假公式）命题公式是永假公式当且仅当当且仅当它的主合取它的主合取范式包含所有的极大项，此时无主析取范式或范式包含所有的极大项，此时无主析取范式或者说主析取范式为者说主析取范式为“空空”。（3）两个命题公式是相等的）两个命题公式是相等的当且仅当当且仅当它们对应它们对应的主析取范式相等，或者它们对应的主合取范的主析取范式相等，或

15、者它们对应的主合取范式相等。式相等。2022-8-5计算机应用技术研究所计算机应用技术研究所57&主范式的应用主范式的应用判断两个命题公式是否等值：2022-8-5计算机应用技术研究所计算机应用技术研究所58&主范式的应用主范式的应用2022-8-5计算机应用技术研究所计算机应用技术研究所59&主范式的应用主范式的应用判断命题公式的类型：2022-8-5计算机应用技术研究所计算机应用技术研究所60&主范式的应用主范式的应用2022-8-5计算机应用技术研究所计算机应用技术研究所61&主范式的应用主范式的应用2022-8-5计算机应用技术研究所计算机应用技术研究所62&主范式的应用主范式的应用【

16、例题】一家航空公司为了保障安全，用计算机复核飞行计划。每台计算机能给出飞行计划正确或有误的回答。由于计算机也可能发生故障，因此采用了三台计算机同时复核，再根据“少数服从多数”的原则作出判断。假设三台计算机中同时有一台以上的计算机出现故障的概率为0，试将判断结果用命题公式表示，并设计一个尽可能简单的电路图。2022-8-5计算机应用技术研究所计算机应用技术研究所63&主范式的应用主范式的应用2022-8-5计算机应用技术研究所计算机应用技术研究所64&主范式的应用主范式的应用2022-8-5计算机应用技术研究所计算机应用技术研究所65&主范式的应用主范式的应用相应的电路图如下：2022-8-5计

17、算机应用技术研究所计算机应用技术研究所66&主范式的应用主范式的应用【例题】某单位要从A,B,C这三名科研骨干中挑选1到2名出国进修，根据工作业务上的需要，选派人员需满足如下条件：（1）若A去,则C必须去；（2）若B去,则C不能去；（3）若C不去，则A或B都可以去。问如何选派？【分析】首先将问题通过符号化表示成命题公式，由于可行的方案对应于命题公式的成真赋值，故可将命题公式化为主析取范式，然后通过小项析取得到所有可行的选派方案。2022-8-5计算机应用技术研究所计算机应用技术研究所67&主范式的应用主范式的应用2022-8-5计算机应用技术研究所计算机应用技术研究所68&主范式的应用主范式的

18、应用2022-8-5计算机应用技术研究所计算机应用技术研究所69本节内容到此结束本节内容到此结束2022-8-52022-8-5 命题公式的范式命题公式的范式4 45 5 命题逻辑的演绎推理命题逻辑的演绎推理&本章学习内容本章学习内容(下下)6 6 命题逻辑的应用命题逻辑的应用2022-8-5计算机应用技术研究所计算机应用技术研究所71命题逻辑的演绎推理命题逻辑的演绎推理&命题逻辑的演绎推理命题逻辑的演绎推理J 永真蕴含关系与判定永真蕴含关系与判定4 命题公式推演系统命题公式推演系统4 命题推证的基本策略命题推证的基本策略2022-8-5计算机应用技术研究所计算机应用技术研究所73&永真蕴含关

19、系与判定永真蕴含关系与判定2022-8-5计算机应用技术研究所计算机应用技术研究所74&永真蕴含关系与判定永真蕴含关系与判定2022-8-5计算机应用技术研究所计算机应用技术研究所75&永真蕴含关系与判定永真蕴含关系与判定2022-8-5计算机应用技术研究所计算机应用技术研究所76&永真蕴含关系与判定永真蕴含关系与判定2022-8-5计算机应用技术研究所计算机应用技术研究所77&永真蕴含关系与判定永真蕴含关系与判定2022-8-5计算机应用技术研究所计算机应用技术研究所78&永真蕴含关系与判定永真蕴含关系与判定2022-8-5计算机应用技术研究所计算机应用技术研究所79&基本永真蕴含关系基本永

20、真蕴含关系2022-8-5计算机应用技术研究所计算机应用技术研究所80&基本永真蕴含关系基本永真蕴含关系2022-8-5计算机应用技术研究所计算机应用技术研究所81&永真蕴含关系判定法永真蕴含关系判定法基本方法基本方法：真值表法真值表法和和等值演算法等值演算法。每种方法。每种方法都对应三种不同的解法：都对应三种不同的解法：证明蕴含逻辑算式的永真性证明蕴含逻辑算式的永真性 假设前件为真，则后件也为真假设前件为真，则后件也为真 假设后件为假，则前件也为假。假设后件为假，则前件也为假。2022-8-5计算机应用技术研究所计算机应用技术研究所82&永真蕴含关系判定法永真蕴含关系判定法2022-8-5计

21、算机应用技术研究所计算机应用技术研究所83&永真蕴含关系判定法永真蕴含关系判定法2022-8-5计算机应用技术研究所计算机应用技术研究所84&永真蕴含关系判定法永真蕴含关系判定法【分析】方法二：若前件为真，则后件也为真【证明】列出如表所示的真值表。由真值表可知，当P、Q的真值指派都为0时，前件Q(PQ)为真，此时后件P也为真。因此Q(PQ)P成立。【分析】方法三：若后件为假，则前件也为假【证明】现出如所示的真值表。由真值表可知，当P、Q的真值指派分别为1、1或1、0时，后件P为假，此时前件Q(PQ)也都为假。因此Q(PQ)P成立。2022-8-5计算机应用技术研究所计算机应用技术研究所85&永

22、真蕴含关系判定法永真蕴含关系判定法2022-8-5计算机应用技术研究所计算机应用技术研究所86&永真蕴含关系判定法永真蕴含关系判定法2022-8-5计算机应用技术研究所计算机应用技术研究所87&永真蕴含关系判定法永真蕴含关系判定法 对于永真蕴含关系的判定和证明，对于永真蕴含关系的判定和证明，公式演算法公式演算法与与真值表法真值表法的基本思路几乎一样，二者的差别仅的基本思路几乎一样，二者的差别仅仅在于仅在于求解的表现形式不同求解的表现形式不同，一个通过，一个通过真值表的真值表的枚举枚举，另外一个是通过，另外一个是通过命题公式的逻辑演算命题公式的逻辑演算。&命题逻辑的演绎推理命题逻辑的演绎推理4

23、永真蕴含关系与判定永真蕴含关系与判定J 命题公式推演系统命题公式推演系统4 命题推证的基本策略命题推证的基本策略2022-8-5计算机应用技术研究所计算机应用技术研究所89&有效推理有效推理2022-8-5计算机应用技术研究所计算机应用技术研究所90&有效推理有效推理2022-8-5计算机应用技术研究所计算机应用技术研究所91&有效推理有效推理2022-8-5计算机应用技术研究所计算机应用技术研究所92&有效推理有效推理2022-8-5计算机应用技术研究所计算机应用技术研究所93&推演系统的基本结构推演系统的基本结构2022-8-5计算机应用技术研究所计算机应用技术研究所94&推演系统的基本结

24、构推演系统的基本结构2022-8-5计算机应用技术研究所计算机应用技术研究所95&有效结论有效结论2022-8-5计算机应用技术研究所计算机应用技术研究所96&有效结论有效结论2022-8-5计算机应用技术研究所计算机应用技术研究所97&有效结论有效结论2022-8-5计算机应用技术研究所计算机应用技术研究所98&有效结论有效结论【例题】若马会飞或羊吃草，则母鸡就会变飞鸟；如果母鸡变飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。所以羊儿不吃草。试给出上述推理的形式证明。【分析】首先找出句子中所有原子命题并用命题变量进行表示，然后确定推理的前提和结论并将整个推理进行符号化表示2022-8-5计算

25、机应用技术研究所计算机应用技术研究所99&有效结论有效结论2022-8-5计算机应用技术研究所计算机应用技术研究所100&有效结论有效结论&命题逻辑的演绎推理命题逻辑的演绎推理4 永真蕴含关系与判定永真蕴含关系与判定4 命题公式的推演系统命题公式的推演系统J 命题推证的基本策略命题推证的基本策略2022-8-5计算机应用技术研究所计算机应用技术研究所102&真值表法真值表法2022-8-5计算机应用技术研究所计算机应用技术研究所103&真值表法真值表法【例题】分析事实：“如果我有时间，那么我就去上街；如果我上街，那么我就去书店买书；但我没有去书店买书，所以我没有时间。”试指出这个推理前提和结论

26、，并证明结论是前提的有效结论。【分析】先将简单陈述句符号化，再写出前提和结论，并通过真值表法给出证明。2022-8-5计算机应用技术研究所计算机应用技术研究所104&真值表法真值表法2022-8-5计算机应用技术研究所计算机应用技术研究所105&真值表法真值表法2022-8-5计算机应用技术研究所计算机应用技术研究所106&命题推证的基本策略命题推证的基本策略2022-8-5计算机应用技术研究所计算机应用技术研究所107&直接证明法直接证明法2022-8-5计算机应用技术研究所计算机应用技术研究所108&直接证明法直接证明法2022-8-5计算机应用技术研究所计算机应用技术研究所109&直接证

27、明法直接证明法2022-8-5计算机应用技术研究所计算机应用技术研究所110&间接证明法间接证明法2022-8-5计算机应用技术研究所计算机应用技术研究所111&间接证明法间接证明法2022-8-5计算机应用技术研究所计算机应用技术研究所112&间接证明法间接证明法2022-8-5计算机应用技术研究所计算机应用技术研究所113&间接证明法间接证明法2022-8-5计算机应用技术研究所计算机应用技术研究所114&间接证明法间接证明法2022-8-5计算机应用技术研究所计算机应用技术研究所115&间接证明法间接证明法2022-8-5计算机应用技术研究所计算机应用技术研究所116&间接证明法间接证明

28、法2022-8-52022-8-5 命题公式的范式命题公式的范式4 45 5 命题逻辑的演绎推理命题逻辑的演绎推理&本章学习内容本章学习内容(下下)命题逻辑的应用命题逻辑的应用6 62022-8-5计算机应用技术研究所计算机应用技术研究所118命题逻辑的应用&命题逻辑的应用命题逻辑的应用J 刑侦推断问题刑侦推断问题4 组合逻辑电路问题组合逻辑电路问题4 加法器电路设计加法器电路设计2022-8-5计算机应用技术研究所计算机应用技术研究所120&命题逻辑的应用命题逻辑的应用【例题】某实验室一贵重仪器被盗，经公安人员调查得知事实如下：（1）是A或者B盗窃了仪器；（2）若A盗窃了仪器，则作案时间不可

29、能发生在夜前；（3）若B的证词正确，则午夜时实验室灯光未灭；（4）若B的证词不正确，则作案时间发生在午夜前；（5）午夜时实验室灯光是灭的。证明：B盗窃了仪器。2022-8-5计算机应用技术研究所计算机应用技术研究所121&命题逻辑的应用命题逻辑的应用【分析】首先找出句子中所有原子命题并用命题变量进行表示，然后确定推理的前提和结论并将整个推理进行符号化表示，最后反证法进行证明2022-8-5计算机应用技术研究所计算机应用技术研究所122&命题逻辑的应用命题逻辑的应用2022-8-5计算机应用技术研究所计算机应用技术研究所123&命题逻辑的应用命题逻辑的应用2022-8-5计算机应用技术研究所计算

30、机应用技术研究所124&命题逻辑的应用命题逻辑的应用2022-8-5计算机应用技术研究所计算机应用技术研究所125&命题逻辑的应用命题逻辑的应用&命题逻辑的应用命题逻辑的应用4 刑侦推断问题刑侦推断问题J 组合逻辑电路设计组合逻辑电路设计4加法器电路设计加法器电路设计2022-8-5计算机应用技术研究所计算机应用技术研究所127&命题逻辑的应用命题逻辑的应用2022-8-5计算机应用技术研究所计算机应用技术研究所128&命题逻辑的应用命题逻辑的应用2022-8-5计算机应用技术研究所计算机应用技术研究所129&命题逻辑的应用命题逻辑的应用【例题】有时候灯具需要由多个开关来控制，因此有必要设计这

31、样的电路：当灯不亮时，敲击任意一个开关都可以使此灯变亮；反之，当灯是打开时，敲击任何一个开关都可以使灯不亮。在有三个开关两种情形下，请设计电路来完成这个任务。2022-8-5计算机应用技术研究所计算机应用技术研究所130&命题逻辑的应用命题逻辑的应用2022-8-5计算机应用技术研究所计算机应用技术研究所131&命题逻辑的应用命题逻辑的应用【解】根据题意及以上分析，可得真值表如表：2022-8-5计算机应用技术研究所计算机应用技术研究所132&命题逻辑的应用命题逻辑的应用进一步到的如图3-12所示逻辑电路设计图:&命题逻辑的应用命题逻辑的应用4 刑侦推断问题刑侦推断问题4 组合逻辑电路设计组合

32、逻辑电路设计J 加法器电路设计加法器电路设计2022-8-5计算机应用技术研究所计算机应用技术研究所134&命题逻辑的应用命题逻辑的应用加法器是产生数的和的装置。加数和被加数作为输入，和位与进位作为输出的装置称为半加法器半加法器；若加数、被加数与低位的进位数为输入，而和位与进位作为输出则称为全加法器全加法器。2022-8-5计算机应用技术研究所计算机应用技术研究所135&命题逻辑的应用命题逻辑的应用2022-8-5计算机应用技术研究所计算机应用技术研究所136&命题逻辑的应用命题逻辑的应用2022-8-5计算机应用技术研究所计算机应用技术研究所137&命题逻辑的应用命题逻辑的应用2022-8-5计算机应用技术研究所计算机应用技术研究所138&命题逻辑的应用命题逻辑的应用2022-8-5计算机应用技术研究所计算机应用技术研究所139&命题逻辑的应用命题逻辑的应用2022-8-5计算机应用技术研究所计算机应用技术研究所140&命题逻辑的应用命题逻辑的应用2022-8-5计算机应用技术研究所计算机应用技术研究所141&命题逻辑的应用命题逻辑的应用2022-8-5计算机应用技术研究所计算机应用技术研究所142&命题逻辑的应用命题逻辑的应用两个三位二进制整数相加的全加法器逻辑电路：2022-8-5计算机应用技术研究所计算机应用技术研究所143本章内容到此结束本章内容到此结束