离散数学教案范本.docx
《离散数学教案范本.docx》由会员分享，可在线阅读，更多相关《离散数学教案范本.docx（31页珍藏版）》请在冰点文库上搜索。
离散数学教案范本
《离散数学》教案
课目：
第一章命题逻辑
教师：
熊建英
学时：
12课时
Ⅰ教学提要
一、教学对象（人数）
学生：
信息安全专业本科二年级学生50人
二、教学目标（任务）
各小结中知识点掌握程度（*理解；**基本掌握；***熟练掌握）
知识点
程度
1.1命题及联接词
（1）命题的概念、表示方法及基本分类
*
（2）五种联接词的逻辑关系
***
（3）复合命题符号化
***
（4）复合命题的真值判断
***
1.2命题公式及其赋值
（1）合式公式的概念、层次及不同的解释
**
（2）求公式的真值表的方法
***
（3）判断命题公式的类别:
永真式、永假式、可满足式
***
（4）公式与真值表之间的关系
**
1.3等值式
（1）等值式的概念
*
（2）通过等值演算判断两个公式是否等值
***
（3）通过真值表判断两个公式是否等值
***
1.4析取范式与合取范式
（1）简单析取与简单合取的定义
*
（2）析取范式与合取范式定义
**
（3）大项与小项定义
*
（4）主析取范式与主合取范式定义
**
（5）利用等值演算与真值表求得主范式
***
1.5推理理论与消解法
（1）推理定义、规则
*
（2）推理证明的方法
***
（3）消解法
***
1.6应用案例
（1）命题逻辑应用领域
***
（2）典型应用案例
**
（3）编写程序求解复杂命题
**
三、教学要求
（一）学生：
着重知识点的学习，积极思考，参与提问。
（二）教官：
严格纪律，严密组织、保持良好教学秩序，确保教学效果。
四、教官分工
主讲教师1名：
负责教案编写，课堂的组织教学，教学总结编写。
五、本章重点
1、利用联接词构造复合命题公式
2、真值表的构建
3、等值演算
4、复合命题公式转化为主析取范式、主合取范式的方法
5、推理证明
六、本章难点
1、利用命题公式演算、真值表进行等值判断和公式类型判断
2、利用命题公式演算、真值表转化主析取范式、主合取范式
3、将现实背景下的条件约束构造为命题公式
七、教学方法
采用课堂教授，主要使用多媒体课件，部分内容及例题用黑板解释。
八、课时分配
1.1命题及联接词2课时；
1.2命题公式及其赋值2课时；
1.3等值式2课时；
1.4析取范式与合取范式2课时；
1.5推理理论与消解法2课时；
1.6命题逻辑应用案例2课时；
九、场地器材
多媒体教室
十、参考书目
1、杨圣洪、张英杰、陈义明：
《离散数学》，科学出版社，2011年。
2、屈婉玲、耿素云、张立昂：
《离散数学》，高等教育出版社，2008年。
3、屈婉玲、耿素云、张立昂：
《离散数学学习指导与习题解析》，高等教育出版社，2008年。
Ⅱ教学进程
1.1命题及联接词（2课时）
一、教学内容
1、命题的概念表示与分类
2、五种基本的联接词的逻辑关系
3、复合命题的符号化
4、复合命题的真值判断
二、课程时间安排
1、首先介绍本课程的性质，任务和教学安排，对学生明确提出教学上的要求（10分钟）
2、介绍离散数学学科的发展历史（20分钟）
3、命题与真值、命题的分类、简单命题符号化（15分钟）
4、联结词与复合命题（35分钟）
5、本次课小结（10分钟）
三、教学实施
（一）创设意境、导入课程（10分钟）
目的
体会离散数学理论在现实生活中的应用、是计算机专业多门核心课程的基础，让学生明白“离散数学”课程作用和意义。
1、从生活应用中理解逻辑推理作用，及离散数学学习意义；
如：
犯罪推理、电路设计、人事安排的最优方案、网络中最优路径等；
（1）逻辑推理问题范例（PPT展示一个犯罪推理案例）
（2）离散数学是一门可以对逻辑推理规律建立相应的符号运算系统，解决此类问题的科学。
2、离散数学与其他专业课程的联系；
（1）涉及多门计算机专业中很多专业课程，如：
编程语言、数据结构、操作系统、数据数据加密。
通过事先了解“教学计划”中学生已经学过的专业课程，后面将着重以计算机基础与C语言编程为例
（2）以C语言编程中算法、条件判断为例
（3）以计算机基础中逻辑运算为例
总结：
计算机在日常生活中的用途是非常大的，进一步说明该课程的任务和教学安排，对学生明确提出教学上的要求。
（二）离散数学的发展史（20分钟）
1、利用多媒体向学生简要介绍离散数学学科的发展历史，了解离散数学的起源和一些重要的人物资料。
2、介绍第一章命题逻辑的主要内容、及在生活中的应用、引发同学们对离散数学的兴趣。
（三）命题与真值、命题的分类、简单命题符号化（15分钟）
1、命题与联接词
（1）数理逻辑研究的中心问题是推理。
（2）推理的前提和结论都是表达判断的陈述句。
（3）表达判断的陈述句构成了推理的基本单位。
2、命题概念
（1）称能判断真假而不是可真可假的陈述句为命题
（2）作为命题的陈述句所表达得的判断结果称为命题的真值。
（3）真值只取两个:
真与假。
真值为真的命题称为真命题。
真值为假的命题称为假命题。
说明:
感叹句、疑问句、祈使句都不能称为命题。
判断结果不唯一确定的陈述句不是命题。
陈述句中的悖论不是命题。
但现在不知道真假，未来有一天必定会知道真假的陈述句是命题。
3、命题的表示
（1）用小写英文字母p,q,r...,pi,qi,ri…表示命题
（2）用“1、T”表示真，用“0、F”表示假
（3）不能被分解成更简单的陈述句，称这样的命题为简单命题或原子命题。
（4）由简单陈述句通过联结词而成的陈述句，称这样的命题为复合命题。
课堂练习：
判断教材中的例1.1中语句是否是命题
目的：
检验学生是否学会如何判断命题
（四）联结词与复合命题（35分钟）
1、五种联结词
（1）否定
设P为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作﹁p，符号﹁称作否定联结词，并规定﹁p为真当且仅当p为假。
注意：
否定之否定是肯定，即﹁﹁p等价于p
（2）合取
设p,q为二命题，复合命题“p并且q（或“P与q”）称为p与q的合取式，记作p∧q，∧称作合取联结词，规定p∧q为真当且仅当P与q同时为真。
使用合取联结词时要注意的两点:
✓描述合取式的灵活性与多样性。
自然语言中的“既……又……”、“不但……而且……”、“虽然……但是……”、“一面·····一面……”等联结词都可以符号化为∧。
✓分清简单命题与复合命题。
不要见到“与”或“和”就使用联结词∧。
（3）析取
设p,q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q，∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假。
自然语言中的“或”具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应的联结词分别称为相容或和排斥或（排异或）。
（4）蕴涵
设p，q为二命题，复合命题“如果p，则q”称作p与q的蕴涵式，记作P->q，并称p是蕴涵式的前件，q为蕴涵式的后件，->称作蕴涵联结词，并规定p->q为假当且仅当P为真q为假。
p->q的逻辑关系表示q是p的必要条件。
q是p的必要条件有许多不同的叙述方式：
只要p，就q；因为p，所以q；p仅当q；只有q才p；除非q才p；除非q，否则非p。
作为一种规定，当p为假时，无论q是真是假，p->q均为真。
也就是说，只有p为真q为假这一种情况使得复合命题p->q为假，称为实质蕴含。
从现实案例中理解
范例1：
爸爸的承诺为：
如果儿子考上大学，爸爸就送IPAD
我们只有在儿子考上大学，爸爸没送IPAD时，才能说爸爸的承诺无效，其他时候任何情况都不能否定承诺的有效性。
（5）等价
设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作p<->q，<->称作等价联结词，并规定p<->q为真当且仅当p与q同时为真或同时为假。
2.复合命题符号化
通过范例理解如何将现实中的表达进行符号化
范例:
2条件联接
爸爸的承诺为：
如果儿子考上大学，爸爸就送IPAD
用p表示儿子考上大学，q表示爸爸送IPAD，承诺可以表示为：
p->q；
注意如果承诺为：
只有儿子考上大学，爸爸才买IPAD；
这句话也表明当我们看见爸爸送了IPAD时，也可以推理出儿子考上了大学，即q->p；用一个表达式将p->q和q->p表达，则为p<->q。
范例3析取合取
子题
超过1.8
不超过1.8
男性
女性
超过1.6
不超过1.6
符号
p
﹁p
q
s
r
﹁r
复合命题1：
身高超过1.8米的男性：
p∧q
复合命题2：
身高超过1.6米的女性：
r∧s
复合命题3：
身高超过1.8米的男性或者身高超过1.6米的女性：
（p∧q）∨（r∧s）
课堂练习：
复合命题4：
身高超过1.8米的女性
复合命题5：
身高不超过1.6米的男性
复合命题6：
身高不超过1.6米的女性并且身高不超过1.8米的男性；
目的：
检验学生是否学会利用连接词和命题符号构造复合命题
2.复合命题的真值判断
通过范例理解命题真假
范例4析取、合取
复合命题1：
身高超过1.8米的男性：
p∧q
如果当前判断对象状态为身高为1.7米，男性，明显判断为假；
即p=0，q=1，p∧q为0∧1，结果为0；
范例5条件联接
对于“如果儿子考上大学，爸爸就送IPAD”会出现4种情况：
（1）如果儿子考上大学，爸爸送了IPAD，承诺有效，即p->q为真；
（2）如果儿子考上大学，爸爸没买IPAD，承诺无效，即p->q为假；
（3）如果儿子没考上大学，爸爸买或没买IPAD，之前承诺本身都是有效的，即p->q为真；
所以：
只有p成立，q不成立，p->q为假。
注意如果承诺为：
只有儿子考上大学，爸爸才买IPAD；那么：
儿子没考上大学，爸爸没买IPAD；遵守了承诺，即p->q为真1；
儿子没考上大学，爸爸买了IPAD；违背了承诺，即p->q为假0；
课堂练习：
如果p=0,q=1;计算下面复合表达式的值；
p∧q；p∨q；（p∧q）∨（p∨q）；p->q；p<->q；
目的：
让学生掌握各种联接词联接命题的值。
（五）课堂小结（10分钟）
1、命题符号化
2、熟记五种命题联结词及运用。
3、命题符号化后求真值：
一般地，规定的联结词优先顺序为:
（），﹁，∧，∨，->，<->，对于同一优先级的联结词，先出现者先运算。
易犯错误：
p->q真值表中，p为0时，q为0或1，p->q为1不是0；
p<->q为真时，与p->q不同，p为0时，q为0，p<->q为1，否则为0；
解决方法：
p->q理解p不是q的唯一条件，p不成立，其他条件也可能使q成立；p<->q理解是p是q唯一条件，前提不成立，结论也不该成立；
1.2命题公式及其赋值（2课时）
一、教学内容
1、合式公式的概念、层次、解释
2、求公式的真值表
3、命题公式的分类
二、课程时间安排
1、章节导入（5分钟）
2、介绍与讲解合式公式（40分钟）
3、讲解真值表（35分钟）
4、本次课小结（10分钟）
三、教学实施
（一）章节导入（5分钟）
目的
判断一个合法的复合命题，通过真值表熟练掌握不同命题取值下计算复合命题的值。
（1）回顾初等数学中的加减乘除混合运算
（2）混合运算式的书写规则，即合法性判断；
如：
5+*9-2为不合法表达式
（3）联接词对应运算符号、变元为数字，引导出命题表达式也存在合法性问题；
（4）由四则运算有最终结果去理解命题运算存在结果值；
（二）合式公式（40分钟）
1、基本概念：
（1）简单命题是命题逻辑中最基本的研究单位，也称为命题常项或者命题常元。
（2）将命题变项用联结词和圆括号按一定的逻辑关系联接起来的符号串叫作命题公式或者合式公式。
2、定义
（1）单个命题变项是合式公式，并称为:
原子命题公式。
（2）若A是合式公式，则﹁A也是合式公式。
（3）若A,B是合式公式，则（A∧B）,（A∨B）,（A->B）,（A<->B）也是合式公式。
（4）只有有限次地使用
（1）一（3）形成的符号串才是合式公式
若A为合式公式，B是A的一部分，且B也是合式公式，则称B为A的子公式。
注意:
（l）若公式A是单个的命题变项，则称A为0层公式;
（2）称A是n+1层公式是指有以下几种情形之一的:
（a）A=﹁B,B是n层公式;
（b）A=B∧C,B、C分别是i,j层公式，且m=max（i,j）
（c）A=B∨C,B、C分别是i,j层公式，且m=max（i,j）
（d）A=B->C,B、C分别是i,j层公式，且m=max（i,j）
（e）A=B<->C,B、C分别是i,j层公式，且m=max（i,j）
若公式A的层次是k，则称A为k层公式。
定义1.8设pl，p2，…，pn，是出现在公式A中的全部命题变项，给pl，p2，…，pn各指定一个真值，称为对A的一个赋值或者解释。
若设定的一组值使A的真值为1，则称这组值为成真赋值，反之则称为成假赋值。
课堂练习：
利用合式定义判断以下不是合式公式
p∧q->；p∨q；（p∧q）∨﹁（p∨q）；p->q﹁；∧p<->q；
目的：
判断复合命题公式的合法性
（三）真值表（35分钟）
1、定义将命题公式A在所有赋值下取值情况列成表，称作A的真值表。
注意：
含n个命题变项的公式共有2n个不同的赋值。
2、构造步骤:
（1）列出2"个赋值，一般从000…0开始直到111…1结束;
（2）按从低到高的顺序写出公式的各个层次;
（3）对应各个赋值计算出各个层次的值，直到计算出最后结果。
3、定义
设A为公式:
（1）如果A在所有解释下取值均为真，则称A是永真式或重言式;
（2）如果A在所有解释下取值均为假，则称A是永假式或矛盾式;
（3）如果至少存在一种解释使公式A取值为真，称A是可满足式。
注意:
（1）可满足式的定义至少有一个为真;
（2）重言式一定是可满足式，但是可满足不一定是重言式;
（3）真值表最后一列判断公式的类型。
例题讲解
利用板书形式，逐步讲解过程，并进行以下引导
讲解例题1.2.2，引导学生思考问题:
问题1.3个变元时，真值表需要构造多少行？
问题2.含有n个命题变项的所有公式与n个命题变项构成的所有真值表之间具有什么样的关系?
课后作业：
课本P7习题2,4,8；
（四）课堂小结（10分钟）
1、合式公式、层次
2、构造真值表
3、判断命题公式的类别:
永真式、永假式;
易犯错误：
命题公式书写错误；解决方法：
参照C语言中单目、双目运算符记忆书写
易犯错误：
真值表的行数确定错误；解决方法：
记住是2的n次方数，n为变元数量
1.3等值式（2课时）
一、教学内容
1、等值式定义
2、等值式的两种判别方法
3、等值演算的简单应用
二、教时安排
1、章节导入（5分钟）
2、等值式定义（15分钟）
3、等值判定（45分钟）
4、等值演算的应用（15分钟）
5、本次课小结（10分钟）
三、教学实施
（一）章节导入（5分钟）
目的
判断两个表达式是否是相等，或求表达式的值。
我们同样在小学就学过计算式转化，如99*89等价于（100-1）*89、99*（10+2）=99*10+99*2等等，也就是一个计算式可以有很多表达形式，活在我们为了计算表达式值也会进行很多等价的转化。
同理对于命题表达式来说，也可以根据我们的判断或求值的目的，采用一些转化的方法，这种等价的转化后的表达式就和原来的是等值的，即等值式。
本节需要利用像小学学过的交换律、分配律等把我们的命题公式进行等值转化，当然我们现在是大学，转化规律也会有所增加，但是有初等数学做基础，求命题等值式并不是一个完全陌生的问题。
（二）等值式（15分钟）
1、定义
设A,B是两个命题公式，若A,B构成的等价式A<->B为重言式，则称A,B是等值的，记作AB。
注意：
A<->B与AB的区别
基本等值式理解记忆
原命题逆否命题；双条件等值式；双重否定；交换律；结合律；分配律；吸收律（多吃少）；德摩根律；
（三）等值判定（45分钟）
1、真值表法
注意:
（1）最后一列可以不写出，可以看两个公式的值是否相同
（2）公式按照运算优先规则分层写出，熟悉了可以简化
（3）运用真值表应该熟练基本逻辑联结词的真值情况。
其中前者等值，后者不是等值的，这一也说明了，蕴含运算是不满足结合律的。
2、等值演算法
（1）验证等值
（2）判断公式类型
例题讲解
利用板书形式，逐步讲解、完成推理，并进行以下引导
（1）通过例题1.3.1的讲解引导学生掌握进行等值演算的基本步骤；
（2）通过记忆技巧掌握基本等值式，其中较容易混淆有：
（a）命题交换律：
p∨（q∧r）=（p∨q）∧（p∨r）
或p∧（q∨r）=（p∧q）∨（p∧r）
可套用3*（2+3）=（3*2）+（3*3）
（b）命题结合律：
p∨（q∨r）=p∨q∨r）
可套用3*（2*3）=3*2*3
（c）德摩根律：
﹁（q∨r）=﹁p∧﹁q；﹁（q∧r）=﹁p∨﹁q
整体否定表示里面每个元素都取反面，即肯定变否定，析取变合取，合取变析取；
课堂练习：
利用等值演算判断公式：
（（p->q）∧p）->q
目的：
检验学生是否可以灵活应用常用的等值变换规律。
（四）等值演算的应用（15分钟）
通过生活推理案例引导学生思考
范例1：
在某次研讨会的体息时间，3名与会者根据王教授的口音分别作出下述判断:
甲说:
王教授不是苏州人，是上海人。
乙说:
王教授不是上海人，是苏州人。
丙说:
王教授既不是上海人，也不是杭州人。
王教授听后，笑曰:
你们3人中有一人全说对了，有一人全说错了，还有一人对错各半。
试用逻辑演算法判断王教授是哪里人?
利用板书形式，逐步讲解、完成推理，并进行以下引导
引导过程:
（1）首先命题符号化：
如何将甲乙丙的话用命题公式描述？
是上海人
不是上海人
是苏州人
不是苏州人
王教授
p
﹁p
p
﹁p
（2）然后进行命题演算:
如何将所有约束条件联接，化简公式？
（3）最后根据结果判断。
目的：
（1）通过生活中一个推理问题让学生体会命题推理知识的应用；
（2）重点引导掌握将现实问题转化为命题推理问题
通过生活推理案例引导学生思考
范例一的另一种解法：
在生活实例中，这样判断往往比较复杂，不妨换一种角度来想，我们可以设想王教授只可能是这三个城市的其中之一，或者不是这三个城市中的任何一个，
设王教授是苏州人，则甲错乙全对丙全对与题意不符合;
设王教授是上海人，则甲全对乙全错并对一半与题意相符合;
至此我们可以判定王教授是上海人，这样判断速度会快好多。
课堂练习：
利用真值表判断：
（（p->q）∧p）->q
目的：
检验学生是否可以通过构造真值表计算公式值
（五）教终小结（10分钟）
1、基本等值式
2、利用命题演算判断等值式
3、利用真值表判断等值式
易犯错误：
命题公式的分配律的展开，及与交换律差异；
解决方法：
用乘法分配律去记忆
1.4析取范式与合取范式（2课时）
一、教学内容
1、文字、简单析（合）取式、析（合）取范式、极小（大）项、主析（合）取范式
2、求命题公式的主析（合）取范式
3、主析（合）取范式的简单应用
二、课程时间安排
1、章节导入（5分钟）
2、基本概念（25分钟）
3、求主析取范式和主合取范式（25分钟）
4、主析取范式的作用（25分钟）
5、本次课小结（10分钟）
三、教学实施
（一）章节导入（5分钟）
目的
理解范式是一种规定的表示形式，为什么需要规定命题范式。
1、利用范例说明为什么需要将公式转化为一种统一的样式，即范式；
如：
化妆舞会上同一个人有多种装扮，很难区分是否为同一人；
2、利用例子让学生理解范式的分类
如：
穿红衣的男生或穿绿衣的女生，（主析取范式公式表达）
3、转化为范式的作用
如：
书上例题1.4.6中描述的问题
（二）基本概念（25分钟）
1、简单式定义
命题变项及其否定称作文字。
仅由有限个文字构成的析取式称作简单析取式。
仅有有限个文字构成的合取式称作简单合取式。
注意:
单个文字即是简单析取式一也是简单合取式
2、简单式定理
（1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式;
（2）一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定式。
3、范式定义
（1）由有限个简单合取式构成的析取式称为析取范式;
（2）由有限个简单析取式构成的合取式称为合取范式;
（3）析取范式与合取范式统称为范式。
4、范式定理
（1）一个析取范式是矛盾式当且仅当它的每一个简单合取式都是矛盾式;
（2）一个合取范式是重言式当且仅当它的每一个简单析取式都是重言式。
（3）任一命题公式都存在着与之等值的析取范式与合取范式
5、大项小项定义
在含有一n个命题变项的简单合（析）取式中，若每个命题变相和它的否定式不同时出现，而两者之一必出现且仅出现一次，且第1个命题变项或它的否定出现在从左起的第1个位置上（若命题变元没有脚标，就按字典序排列），称这样的简单合（析）取式为极小（大）项。
6、大项小项定理
设mi与Mi是命题变项pl，p2，…，pn形成的极小项与极大项，则miMi
9、主范式定义
设有n个命题变项构成的析（合）取范式中所有的简单合（析）取式都是极小（大）项，则称该析（合）取范式为主析（合）取范式。
10、主范式定理
任何命题公式都存在着与之等值的主析取范式和主合取范式，并且是唯一的。
（三）求主析取范式和主合取范式（25分钟）
例题讲解：
（1）利用等值演算求例题1.4.1的主析取范式、主合取范式
通过板书形式，逐步讲解、完成推理，并进行以下引导
1）引导学生按照等值演算转化条件联接与否定到底；
2）引导学生主析取时，如果外层不是∨符号，利用分配律将∨转到外层；
3）引导学生主合取时，如果外层不是∧符号，利用分配律将∧转到外层；
4）引导学生在简单式中缺少变元时，析取添加∨0，合取添加∧1；即利用缺少的变元及其否定构成0,1，进行分配结合演算；
注意:
在求命题公式的主析取和主合取的时候一定要根据公式中所含有的命题个数区决定极大项和极小项。
（2）利用真值表转化1.4.1的主析取范式、主合取范式
通过PPT展示构造真值表，并进行如下引导
1）引导学生如何根据命题构造真值表；
2）让我们理解真值表规模与变元个数关系；
3）可以根据主析取、主合取选择小项、大项；
4）如何根据大项、小项编号构造命题公式
注意:
永真式、永假式在范式上的特殊性
（四）主范式的作用（25分钟）
（1）求公式的成真与成假赋值
（2）判断公式的类型
（3）判断两个公式是否等值
（4）应用其解决实
升级会员 