1、离散数学学校教案设计安徽理工大学教案首页第 1 次课 授课时间 2017 年 9 月 14 日 教案完成时间: 2017 年 9 月 10 日课程名称离散数学年 级2017 级专业、层次计算机学院(本科)教 师专业技术职 务讲师授课方式(大、小)大学时2授课题目(章、节)4.1谓词和量词,4.2一阶语言基本教材或主要参考书离散数学 刘爱民 北京邮电大学出版社教学目的和要求:1.全称量词,存在量词,存在唯一量词;2. 一阶语言、解释和赋值大体内容与时间安排,教学方法:1. 介绍全称量词,存在量词,存在唯一量词,练习将命题符号化(45min);2.介绍一阶语言,对于具体的公式,给出解释和赋值(45
2、min);教学重点、难点:1. 命题符号化2. 公式的解释和赋值(主要内容题纲)4.1谓词和量词1.全称量词,全称量词(Universal Quantifier):在自然语言中“所有的”、“一切”、“任意的”、“每一个”等表示数量的词,称为全称量词。它用于描述讨论范围中的全部个体,用符号“”表示。2.存在量词,存在量词(Existential Quantifier):用符号“”表示,对应自然语言中“存在一些”、“至少有一个”等表示数量的词。xF(x)表示个体域中存在个体具有性质F。3.存在唯一量词4.将具体命题符号化例2.1-6 将下列命题符号化。好人自有好报。 有会说话的机器人;没有免费的午
3、餐;在北京工作的人未必都是北京人。解 在本题中没有指定个体域,故取个体域为全总个体域。设F(x):x是好人;G(x):x会有好报,则命题符号化为:x(F(x)G(x)。设F(x):x是机器人;G(x):x是会说话的,则命题符号化为:x(F(x)G(x)。设M(x):x是午餐;F(x): x是免费的,则命题符号化为:x(M(x)F(x)。这句话可作如下叙述,“所有的午餐都不是免费的”,故命题可符号化为:x(M(x)F(x)。因为在含义上这句话和题目的是一样的,所以可以看出,x(M(x)F(x)和x(M(x)F(x)是等价的,后面还将给出具体的证明。设F(x):x在北京工作;G(x): x是北京人
4、,则命题符号化为: x(F(x)G(x)。这句话也可作如下叙述,“存在着在北京工作的非北京人”,故可符号化为:x(F(x) G(x)。因为在含义上这句话和题目是一样的。所以可以看出, x(F(x)G(x)和x(F(x) G(x)是等价的,后面也将给出具体的证明。4.2一阶语言1.一阶语言2.解释和赋值一个公式A的一个解释(Interpretation) I 应由以下四部分组成:非空个体域D;公式A中的每个个体常元指定为D中一个特定元素;公式A中的n元函数指定为Dn到D的一个特定的函数;公式A中的n元谓词指定为Dn到0,1的一个特定的谓词(命题函数)。3.公式的分类设A为一个谓词公式,如果A在任
5、何解释下都是真的,则称A为逻辑有效式(Universal)或称为永真式;如果A在任何解释下都是假的,则称A为矛盾式(Contradiction)或称为永假式;若至少存在一个解释使A为真,则称A为可满足式(Satisfable)。4.将具体的公式解释和赋值(教案末页)本节课小结1. 全称量词,存在量词,存在唯一量词(2min);2. 一阶语言、解释和赋值(2min);复习思考题作业题课后习题1,3安徽理工大学教案首页第 1 次课 授课时间 2017 年 9 月 14 日 教案完成时间: 2017 年 9 月 10 日课程名称离散数学年 级2017 级专业、层次计算机学院(本科)教 师专业技术职
6、务讲师授课方式(大、小)大学时2授课题目(章、节)4.3 一阶逻辑等值演算,4.4一阶逻辑形式推理基本教材或主要参考书离散数学 刘爱民 北京邮电大学出版社教学目的和要求:1.等值演算;前束范式2.推理定律,推理规则 大体内容与时间安排,教学方法:1. 介绍等值演算;前束范式,将具体公式化为前束范式(45min);2. 介绍推理定律,推理规则,将具体推理符号化并加以证明(45min);教学重点、难点:1. 将公式化为前束范式;2. 推理的证明(主要内容题纲)4.3 一阶逻辑等值演算1.等值演算;设A、B是谓词逻辑中任意的两谓词公式,若AB为逻辑有效式,则称A与B是等值的,记作AB,称“AB”为谓
7、词逻辑等值式(Equivalent)定理 量词辖域收缩与扩张等值式。x(A(x)B)xA(x)B;x(A(x)B)xA(x)B;x(A(x)B)xA(x)B;x(BA(x)BxA(x)。x(A(x)B)xA(x)B;x(A(x)B)xA(x)B;x(A(x)B)xA(x)B;x(BA(x)BxA(x)。定理 量词分配等值式。x(A(x)B(x)xA(x)xB(x);x(A(x)B(x)xA(x)xB(x)。其中称为对的分配;称为对的分配。定理 量词移位等值式。xyA(x,y)yxA(x,y);xyA(x,y)yxA(x,y)。注意 不同名量词间的次序是不可随意变更的。2.前束范式,3.公式化为
8、前束范式4.4一阶逻辑形式推理1.推理定律,2.推理规则,全称量词消去规则(简称US):; 。全称量词引入规则(简称UG):。存在量词引入规则(简称EG):; 3.推理符号化并加以证明;(教案末页)本节课小结1. 等值演算;前束范式(2min);2. 推理定律,推理规则(2min);复习思考题作业题课后习题5,7,8,9安徽理工大学教案首页第 1 次课 授课时间 2017 年 9 月 14 日 教案完成时间: 2017 年 9 月 10 日课程名称离散数学年 级2017 级专业、层次计算机学院(本科)教 师专业技术职 务讲师授课方式(大、小)大学时2授课题目(章、节)5.1集合的概念及表示,5
9、.2 集合运算基本教材或主要参考书离散数学 刘爱民 北京邮电大学出版社教学目的和要求:1.集合的基本概念;2. 集合的常见运算大体内容与时间安排,教学方法:1. 集合的定义,元素与集合的关系,集合与集合的关系,幂集(45min);2.并集,交集,差集,对称差集,广义交,广义并(45min);教学重点、难点:1.幂集2.差集,对称差集,广义交,广义并(主要内容题纲)5.1集合的概念及表示1.集合的定义,集合是不能精确定义的基本概念。直观地说,把一些事物汇集到一起组成一个整体就叫集合,而这些事物就是这个集合的元素或成员。2.元素与集合的关系,元素和集合之间的关系是隶属关系,即属于或不属于,属于记作
10、,不属于记作,3.集合与集合的关系,设A,B为集合,如果B中的每个元素都是A中的元素,则称B是A的子集合,简称子集。这时也称B被A包含,或A包含B,记作BA。4.幂集设A为集合,把A的全部子集构成的集合叫做A的幂集,记作P(A)5.2 集合运算1.并集,设A,B为集合,A与B的并集AB,ABx|xAxB 2.交集,设A,B为集合,交集AB, ABx|xAxB 3.差集,对称差集,设A,B为集合,B对A的相对补集AB,ABx|xAxB 设A,B为集合,A与B的对称差集AB定义为: AB(AB)(BA) 4.广义交,广义并(教案末页)本节课小结1. 集合的基本概念(2min);2. 集合的常见运算
11、(2min); 复习思考题作业题课后练习1,4安徽理工大学教案首页第 1 次课 授课时间 2017 年 9 月 14 日 教案完成时间: 2017 年 9 月 10 日课程名称离散数学年 级2017 级专业、层次计算机学院(本科)教 师专业技术职 务讲师授课方式(大、小)大学时2授课题目(章、节)5.3 集合定律,5.4有限集的计数问题基本教材或主要参考书离散数学 刘爱民 北京邮电大学出版社教学目的和要求:1. 集合定律;2. 有限集的计数问题大体内容与时间安排,教学方法:1. 集合定律:等幂律,排中律,矛盾律,吸收律(45min);2. 有限集的计数问题:容斥原理,及其推广(45min);教
12、学重点、难点:1. 容斥原理,及其推广(主要内容题纲)5.3 集合定律1.幂等律 AAA (6.1) AAA (6.2)2.结合律 (AB)CA(BC) (6.3) (AB)CA(BC) (6.4)3.交换律 ABBA (6.5) ABBA (6.6)4.分配律 A(BC)(AB)(AC) (6.7) A(BC)(AB)(AC) (6.8)5.同一律 AA (6.9) AEA (6.10)6.零律 AEE (6.11) A (6.12)7.排中律 AAE (6.13)8.矛盾律 AA (6.14)9.吸收律 A(AB)A (6.15) A(AB)A (6.16)10.德摩根律 A(BC)(AB)(AC) (6.17) A(BC)(AB)(AC) (6.18) (BC)=BC (6.19) (BC)=BC (6.20) E (6.21) E (6.22)11.双重否定律 (A)A (6.23)5.4有限集的计数问题容斥原理: card(AB)= card(A)+ card(B) card(AB)(教案末页)本节课小结1. 集合定律(2min);2. 容斥原理,及其推广(2min);复习思考题作业题课后练习5,7,8,9