《离散数学（微课版第2版）》 第1章 命题逻辑-教案

二、课程教案第5次课授课单元（章节)第1章命题逻辑授课学时2授课类型讲授课(√)实践课()其它()授课周次第3周教学目标知识目标：1.系统回顾本章知识：命题与联结词、命题变元与合式公式、等价性与重言式、对偶原理与范式。2.掌握有效结论的定义，理解推理的形式结构。3.掌握真值表法证明有效结论的方法。4.理解一致性（相容性）的概念，掌握直接证法（P规则、T规则）、CP规则和间接证明法（F规则）。5.熟记常用等价式与永真蕴含式，了解命题逻辑在人工智能自动推理中的应用。6.了解命题逻辑在信息检索、自动推理与约束求解等领域的典型应用案例（布尔检索、SAT、MaxSAT、CP-SAT、SMT等）。能力目标：1.能利用真值表法、直接证法、CP规则、反证法证明推理题，正确构造推理序列。2.能根据结论的形式选择合适的证明方法。3.能综合运用常用等价式与蕴含式解决问题。素质目标：1.培养严密的逻辑思维能力和严谨的论证习惯。2.提升综合归纳与知识整合能力，形成系统的知识框架。课程思政目标：1.通过推理规则"有据可依"的特点，引导学生理解遵守规则、依规办事的重要性，树立规则意识与法治观念。2.结合命题逻辑在人工智能自动推理（SAT求解、程序验证）中的应用，激发学生的专业学习兴趣与创新意识。教学重点、难点1.教学重点：（1）有效结论的判定与推理证明方法：直接证法（P、T规则）、CP规则、间接证明法（F规则）。（2）本章核心知识体系的系统梳理。2.教学难点：（1）构造推理序列时等价式与蕴含式的准确选用。（2）反证法证明中矛盾的导出。（3）CP规则的理解与使用。教学方法1.讲授法：系统梳理全章知识脉络，讲解推理理论。2.例题演示法：完整演示直接证法、CP规则、反证法的证明过程，规范推导格式（序号、公式、依据）。3.归纳总结法：以知识结构图的方式总结全章内容，帮助学生形成整体知识框架。4.讲练结合法：安排课堂练习推理证明题，及时巩固。教学手段1.多媒体课件：展示全章知识结构图、推理规则及典型例题的推导过程。2.板书：演示推理序列的规范写法（公式序号、依据规则及相关公式编号）。3.线上教学平台辅助：上传全章知识点总结与习题资料，供学生复习自测。教学内容一、本章知识要点回顾1.命题与命题逻辑联结词：命题的判断（非真必假的陈述句）；6种逻辑联结词¬、∧、∨、▽、→、↔的定义、真值表与自然语言符号化；联结词的优先次序为¬、∧、∨、→、↔。2.命题变元、合式公式与真值表：合式公式的递归定义与判断；真值表的构造；命题、命题变元与命题公式的区别（前者有真假意义，后两者需经真值指派才有真值）。3.公式等价性与重言式：等价定义A⇔B及两种判定方法（真值表法、等价变换法）；常用逻辑恒等式；替换规则；重言式、永假式、可满足式；代入规则；永真蕴含式；等价式与蕴含式的关系（P⇔Q当且仅当P⇒Q且Q⇒P）。4.对偶原理与范式：对偶式的定义与对偶原理（定理1.1~1.3）；基本积与基本和；析取范式与合取范式；极小项与极大项；主析取范式与主合取范式及其与真值表的对应关系；利用主范式判定公式类型。5.判定公式性质的四种方法：真值表法、等价公式变换法、利用对偶原理、通过求主范式的方法。二、命题演算的推理理论（要点回顾）1.推理的意义数理逻辑的主要任务之一就是提供一套推理规则：给定一些前提，利用推理规则推导出结论，这个过程称为演绎或证明。生活中，若从前提推导出结论的论证遵守了逻辑推理规则，则认为结论是真的、论证是合法的；数理逻辑中不关心前提的真实真值，而把注意力集中于推理规则的研究，依据推理规则推导出的任何结论称为有效结论，这样的论证称为有效论证。2.有效结论的定义设A和B是两个命题公式，当且仅当A→B是永真式（即A⇒B）时，称B是A的有效结论，或称B由A可逻辑地推出。该定义可推广到n个前提：当H1∧H2∧…∧Hm⇒C时，称C是前提集合{H1，H2，…，Hm}的有效结论。例：H1：今天周一或者今天下雨；H2：今天不是周一；C：今天下雨。符号化为H1：P∨Q，H2：¬P，C：Q。由于(P∨Q)∧¬P⇒Q是永真蕴含式，故C是前提集合的有效结论。3.证明有效结论的方法（1）真值表法：思路是"证明使前提集合取值为真的那些组真值指派，也一定使结论取值为真"。例：考察C：Q是否为H1：P→Q、H2：P的有效结论。由真值表可知，使H1、H2同时为真的指派只有P=1、Q=1一组，此时C也为真，故C是有效结论。（2）直接证法：使用推理规则和给定的等价式及永真蕴含式进行推导证明。推理过程是一个公式的有限序列C1，C2，…，Cn，其中Ci或者属于前提集合S，或者是某些Cj（j<i）的有效结论，并且Cn就是C。推理规则：①P规则——在推导过程中，任何时候都可以引入前提；②T规则——在推导中，如果前面有一个或多个公式永真蕴含公式S，则可以把S引进推导过程。例：证明¬P是¬(P∧¬Q)、¬Q∨R、¬R的有效结论。证明：（1）¬(P∧¬Q)P规则；（2）¬P∨QT规则，(1)，德·摩根律；（3）P→QT规则，(2)，蕴含等值式；（4）¬Q∨RP规则；（5）Q→RT规则，(4)，蕴含等值式；（6）P→RT规则，(3)(5)，假言三段论；（7）¬RP规则；（8）¬PT规则，(6)(7)，拒取式。得证。（3）CP规则：如果能从R和前提集合中推导出S来，则就能够从前提集合中推导出R→S。即当结论是R→S的形式时，可以把结论的前件R作为附加前提使用，与前提一起若能推出后件S，则问题得证。例：证明R→S是P→(Q→S)、¬R∨(P∧Q)的有效结论。证明：（1）RP规则（附加前提）；（2）¬R∨(P∧Q)P规则；（3）P∧QT规则，(1)(2)，析取三段论；（4）PT规则，(3)，简化式；（5）P→(Q→S)P规则；（6）Q→ST规则，(4)(5)，假言推理；（7）QT规则，(3)，简化式；（8）ST规则，(6)(7)，假言推理；（9）R→SCP规则，(1)(8)。得证。（4）间接证明法（反证法）：设公式H1，…，Hm中的原子变元是P1，…，Pn。如果存在真值指派使H1∧H2∧…∧Hm为真，则称公式集合{H1，H2，…，Hm}是一致的（相容的）；如果对每一个真值指派，H1，…，Hm中至少有一个为假，则称是不一致的（不相容的）。例如P与¬P是不相容的。若存在公式R使得H1∧H2∧…∧Hm⇒R∧¬R，则{H1，H2，…，Hm}是不相容的。定理1.6：设命题公式集合{H1，H2，…，Hm，¬C}是非一致的（即它蕴涵一个永假式），则可以从前提集合{H1，H2，…，Hm}中推导出命题公式C来。F规则：如果前提集合和¬S不相容，那么可以从前提集合中推出S。例：证明¬(P∧Q)是¬P∧¬Q的有效结论。证明：（1）¬¬(P∧Q)P规则（假设前提）；（2）P∧QT规则，(1)，对合律；（3）PT规则，(2)，简化式；（4）¬P∧¬QP规则；（5）¬PT规则，(4)，简化式；（6）P∧¬PT规则，(3)(5)，合取；（7）¬(P∧Q)F规则，(1)(6)。得证。（5）证明方法的选用规律：当要证明的结论是条件式时，可考虑使用CP规则；当结论比较简单而仅用前提推导不明显时，可考虑使用间接证明法（F规则），使推导过程变得简捷。三、命题逻辑应用案例集锦1.逻辑难题——骑士与流氓：岛上骑士总说真话，流氓总说谎话。A说"B是骑士"，B说"我们两个不是一类人"。设P：A是骑士，Q：B是骑士，A、B的话分别符号化为Q和(P∧¬Q)∨(¬P∧Q)。枚举4种真值组合可知，只有A、B都是流氓时不产生矛盾，故A、B都是流氓。2.逻辑难题——侦探与四证人：侦探调查罪案时从四位证人的话得出：如果男管家说真话，那么厨师也说真话；厨师和园丁不可能都说真话；园丁和杂役不可能都在说谎；如果杂役说真话，那么厨师在说谎。设M：男管家说真话，C：厨师说真话，G：园丁说真话，Z：杂役说真话，四个条件符号化为M→C、¬(C∧G)、G∨Z、Z→¬C。用真值表逐组检验可知：男管家和厨师都在说谎，园丁和杂役至少有一人说真话。3.应用——系统规范性说明的一致性检查：某系统的三条规范为"诊断消息存放在缓冲区中或是被重传""诊断消息没有存储在缓冲区中""如果诊断消息存储在缓冲区中，那么它被重传"。设P：诊断消息存储在缓冲区中，Q：诊断消息被重传，三条规范符号化为P∨Q、¬P、P→Q。通过真值表可知，当P=0、Q=1时三条公式都为真，说明该规范集合是一致的。将自然语言需求翻译为逻辑表达式并检查一致性，是软硬件系统开发的基础工作。4.应用——逻辑部件与汽车报站系统：非门、与门、或门分别对应¬、∧、∨运算，是计算机电路的基本部件。汽车报站系统中，令P：汽车运行的方向（上行0、下行1），Q：当前站点，R：下一站点，其逻辑表达式为(P∧Q)→R⇔¬P∨¬Q∨R，请学生完成该表达式的逻辑部件图示。5.应用——布尔逻辑与信息检索：用布尔逻辑运算符"与（and或*）、或（or，Google中用OR或|）、非（not或-）"可把检索词连接成检索式。例如检索"计算机辅助设计"文献时，输入"CADORComputerAidedDesign"可避免漏检、保证查全率；"乙肝病毒-人类"表示检索含"乙肝病毒"但不含"人类"的内容。运算优先级由高到低为not、and、or。检索技巧：把出现频率低的检索词放在"与"的左边、出现频率高的放在"或"的左边，可提高检索速度。6.应用——命题逻辑与可满足性问题（SAT）：SAT问题是指给定一个命题公式，问是否存在一组真值赋值使公式为真。推理问题可转化为SAT判定：知识库KB能否推出结论q，等价于检查KB∧¬q是否不可满足。SAT常用于知识表示与自动推理中的一致性检查、反例搜索，以及经典规划、调度、配置管理、形式化验证等场景；实际使用中常把公式改写为CNF后交给SAT求解器求解。7.案例一——MaxSAT用于可解释AI的规则学习：在可解释AI中，把必须满足的逻辑条件写成硬约束，把"尽量满足"的偏好（如少用规则、尽量分类正确）写成带权重的软约束，用MaxSAT（最大可满足性）或加权MaxSAT求解，可得到硬约束可行前提下软约束最优的解，从而学习出"人能读懂"的规则模型。开源求解器Open-WBO可直接使用；已有研究把MaxSAT作为核心技术学习可解释的决策树模型。8.案例二——GoogleOR-Tools的CP-SAT：员工排班、生产调度、资源分配等现实任务可建模为"离散决策＋约束"问题。GoogleOR-Tools的CP-SAT求解器把约束规划（CP）的建模与传播能力同SAT求解器的搜索与学习机制结合起来：CP侧通过约束传播缩小变量取值范围，搜索冲突时进行冲突分析并学习新约束，从而减少重复搜索，是工业界常用的整数与组合优化求解器。9.案例三——Microsoft的Z3：程序分析中"某段程序是否存在触发断言失败的输入""两个实现是否等价"等问题，可形式化为SMT（可满足性模理论）求解。Z3是广泛使用的SMT求解器，能处理纯命题逻辑以及算术、位向量、数组等理论结构；其求解仍以SAT布尔搜索为核心：先在命题层面猜测真假组合，再由理论求解器检查一致性，发现矛盾则回传冲突信息剪枝，广泛用于软件验证与分析。10.综合推理案例——足坛比赛：已知（1）若大连万达获冠军，则北京国安和上海申花获得亚军；（2）若上海申花获亚军，则大连万达不能获冠军；（3）若陕西国力获亚军，则北京国安不能获亚军；（4）大连万达获冠军。结论：陕西国力未获亚军。设P：大连万达获冠军，Q：北京国安获亚军，R：上海申花获亚军，S：陕西国力获亚军，问题符号化为P→(Q▽R)、R→¬P、S→¬Q、P⇒¬S（自然语言中的"和"表示排斥或）。用反证法：假设S真，则推出¬Q与R，由R→¬P推出¬P，与P矛盾，故¬S是有效结论。四、课堂小结与复习建议本章知识体系：命题与联结词→合式公式与真值表→等价性与重言式→对偶原理与范式→推理理论。重点掌握：联结词的真值；合式公式的判定与真值表；等价变换与主范式；四条推理规则（P、T、CP、F）及推理证明的规范书写。复习建议：熟记常用等价式与蕴含式；独立完成教材第一章习题；对照知识结构图自查薄弱环节。预习：第2章谓词逻辑（个体、谓词与量词），思考"命题逻辑在刻画“所有”“存在”等语句时有什么局限？"。教学设计及时间安排教学设计时间分配（分钟）（一）复习及提问1.复习回顾（3分钟）：回顾上次课的范式与主范式求法，检查作业完成情况。2.提问检查（2分钟）：提问"判定公式性质有哪四条途径？"，引入全章回顾。5（二）课程引入3.课程导入（5分钟）：提出"命题逻辑在信息检索、自动推理等场景中如何发挥作用？"，回顾全章知识脉络，导入本章总结与应用案例学习。5（三）课程内容课程内容讲授与案例讲评（75分钟）：1.本章知识要点回顾（15分钟）：以知识结构图梳理命题与联结词、合式公式与真值表、等价性与重言式、对偶原理与范式等全章内容。2.推理理论要点回顾（20分钟）：回顾有效结论、真值表法、直接证法（P、T规则）、CP规则、间接证明法（F规则）与证明方法选用规律。3.应用案例集锦讲评（35分钟）：讲评逻辑难题（骑士与流氓、侦探与四证人）、系统规范性说明、逻辑部件与汽车报站、布尔逻辑与信息检索、SAT、MaxSAT、CP-SAT、Z3及足坛比赛综合案例。4.全章总结与复习建议（5分钟）：梳理"四种判定方法、四条推理规则"两条主线，明确复习自测要求。75（四）融入课程思政设计融入课程思政设计（3分钟）：通过推理规则"有据可依"的特点，引导学生理解遵守规则、依规办事的重要性；结合命题逻辑在人工智能自动推理中的应用，激励学生学好基础理论、勇于创新。3（包含在课程内容讲授的75分钟内）（五）互动环节设计互动环节设计（5分钟）：组织学生讨论"学习生活中还有哪些地方用到了命题逻辑"，并现场演示布尔逻辑检索式的构造，教师点评总结。5（包含在课程内容讲授的75分钟内）课堂小结（5分钟）：梳理本次课核心知识点，明确重点与需掌握的内容，帮助学生构建知识框架。5课后作业或思考题一、简答题1.什么是有效结论？什么是公式集合的一致性（相容性）？2.P规则、T规则、CP规则、F规则的含义分别是什么？二、证明题3.用直接证法证明：¬(P→Q)→¬(R∨S)，(Q→P)∨¬R，R⇒P↔Q。4.用CP规则证明：P→(Q→R)，¬S∨P，Q⇒S→R。5.用反证法证明：P→Q，¬Q∨R，¬R⇒¬P。三、复习与拓展任务完成教材第一章全部习题的整理与订正；系统复习全章内容，熟记常用等价式与永真蕴含式，为本课程后续内