离散数学教案设计

PAGEPAGE210滁州学院计算机与信息工程学院课程教案课程名称：离散数学授课教师：授课对象：授课时间：

《离散数学》教学大纲（DiscreteMathematic）课程代码：学时：48学分：3一、课程简介 本大纲根据2009版应用型人才培养方案制订。（一）教学对象：网络工程、计算机科学与技术专业本科学生（二）开课学期：第三学期（三）课程类别：专业基础课（四）考核方式：考试（五）参考教材：《离散数学》第2版邓辉文清华大学出版社2010.主要参考书目：[1]邵学才,叶秀明.离散数学[M].北京电子工业出版社，2009.[2]邵志清,虞慧群.离散数学[M].北京电子工业出版社，2003.[3]屈婉玲.离散数学习题解析[M].北京大学出版社，2008.本课程的先修课程是高等数学、线性代数，后续课程包含数据结构、数据库原理及应用、操作系统、数字逻辑、人工智能、算法分析与设计等。二、教学基本要求与内容安排（一）教学目的与要求离散数学是研究离散量的结构及其相互关系的学科,它在各学科领域特别在计算机科学领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程必不可少的先行课程。本课程的教学目的旨在通过对离散数学的教学，让学生不但可以掌握处理如集合、代数结构和图等离散结构的描述工具和方法，为后续课程的学习创造条件，而且为学生今后提高专业理论水平，从事计算机行业的实际工作提供必备的抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。（二）教学内容安排教学内容教学要求教学方法重点(☆)难点(Δ)学时分配备注讲课实验上机其他第一部分数理逻辑讲授15.51命题逻辑的基本概念21.1命题与联接词B☆11.2命题公式及其赋值A☆Δ12命题逻辑等值演算3.52.1等值式B☆12.2析取范式与合取范式A☆Δ12.3联接词的完备集C0.52.4可满足性与消解法B13命题逻辑的推理理论23.1推理的形式结构A☆13.2自然推理系统PBΔ14一阶逻辑基本概念24.1一阶逻辑命题符号化A☆14.2一阶逻辑公式及解释A☆Δ15一阶逻辑等值演算与推理35.1一阶逻辑等值式与置换规则A☆15.2一阶逻辑前束范式A☆15.3一阶逻辑的推理理论A☆Δ16数理逻辑在计算机中的应用3第二部分集合论讲授131集合代数21.1集合的基本概念B0.51.2集合的运算A☆0.51.3有穷集的计数C0.51.4集合恒等式A☆0.52二元关系62.1有序对与笛卡尔积A☆12.2二元关系A☆12.3关系的运算A☆12.4关系的性质A☆Δ12.5关系的闭包A☆12.6等价关系与划分A☆Δ13函数33.1函数的定义与性质A☆0.53.2函数的复合与反函数A☆0.53.3双射函数与集合的基数CΔ13.4一个电话系统的描述实例CΔ14集合论在计算机中的应用2第三部分代数结构讲授61.51代数系统31.1二元运算及其性质A☆11.2代数系统A☆11.3代数系统的同态与同构BΔ12群与环32.1群的定义及其性质A☆12.2循环群与置换群A☆Δ2第四部分图论讲授121图的基本概念2.51.1图A☆0.51.2连通与回路A☆0.51.3图的连通性A☆0.51.4图的矩阵表示A☆0.51.5图的运算A☆Δ0.52欧拉图与哈密顿图22.1欧拉图A☆0.52.2哈密顿图A☆0.52.3最短路问题与货郎担问题CΔ13树1.53.1无向树及其性质A☆0.53.2生成树A☆0.53.3根树及其应用B0.54平面图34.1平面图的基本概念B0.54.2欧拉公式B☆0.54.3平面图的判断B14.4平面图的对偶图C15图论在计算机中的应用3（教学要求：A—熟练掌握；B—掌握；C—了解）三、实验内容本课程无实验制订人（签字）：审核人（签字）：教学进度2012～2013学年第1学期周数周数16周计划学时48学时讲课48学时课堂讨论0学时实验课0学时习题课0学时其他环节0学时授课教师姓名赵欢欢职称助教授课专业网络工程班级2011级课程名称离散数学教材名称离散数学出版社清华大学出版社周次日期周学时其中教学内容摘要（章节名称、讲述的内容提要、实验的名称、课堂讨论的题目等）讲课实验课习题课课堂讨论其他环节第一周9月344第一讲集合、映射与运算（一）1.1集合的基本概念理论：集合、子集、幂集、n元组、笛卡尔积第二讲集合、映射与运算（二）1.2映射的有关概念理论：映射的定义、映射的性质、逆映射、复合映射第二周9月1022第三讲集合、映射与运算（三）1.3运算的定义和性质理论：运算的定义、运算的性质第三周9月144第四讲集合、映射与运算（四）1.4集合的运算1.5集合的划分1.6集合的对等理论：集合的并、交、差、补、对称差等基本运算，集合的划分与覆盖、集合对等、可数集合、不可数集合第五讲关系（一）2.1关系的概念理论：n元关系的定义、2元关系、关系的定义域和值域、关系的表示、函数的关系定义第四周9月222第六讲关系（二）2.1关系的运算理论：关系的集合运算、逆运算、复合运算、关系的其他运算第五周10月1日44国庆放假第七讲关系（三）2.3关系的性质2.4关系的闭包理论：关系的性质：自反性、反自反性、对称性、反对称性、传递性；自反闭包r(R)、对称闭包s(R)、传递闭包t(R)第六周10月822第八讲关系（四）2.5等价关系2.6相容关系2.7偏序关系理论：等价关系的定义、等价类；相容关系的定义；偏序关系的定义、哈斯图的、偏序集中的特殊元素第七周10月1544第九讲命题逻辑（一）3.1命题的有关概念3.2逻辑联接词理论：命题的定义与真值、原子命题和复合命题、各种逻辑连接词的含义，真假的判断第十讲命题逻辑（二）3.3命题公式及其真值表理论：命题公式的定义、命题的符号化、命题公式的真值表、命题公式的类型第八周10月22日22第十一讲命题逻辑（三）3.4逻辑等值的命题公式理论：逻辑等值的定义、基本等值式、等值演算法、对偶原理第九周10月29日44第十二讲命题逻辑（四）3.5命题公式的范式理论：命题公式的析取范式和合取范式的定义域求法命题公式的主析取范式及主合取范式的定义和求法第十三讲命题逻辑（五）3.7命题逻辑中的推理理论：推理形式有效性的定义；基本推理规则；命题逻辑的自然推理系统第十周11月522第十四讲谓词逻辑（一）4.1个体、谓词、量词和函词理论：谓词逻辑概念，谓词的概念与表示，量词的概念与表示，个体域，辖域，约束变元和自由变元的含义第十一周11月144第十五讲谓词逻辑（二）4.2谓词公式及命题的符号化4.3谓词公式的解释及类型理论：谓词公式的定义，将命题用用符号（个体，量词，谓词）来表示，消去量词的逻辑等值式，永真式，科满足式，永假式及中性式的概念第十六讲谓词逻辑（三）4.4逻辑等值的谓词公式4.5谓词公式的前束范式理论：谓词公式等值的定义，基本等值式，前束范式第十二周11月1922第十七讲图论（一）6.1图的基本概念6.2节点的度数6.3子图，图的运算和图同构理论：图的定义，邻接，关联，简单图，节点的度数，子图第十三周11月2644第十八讲图论（二）6.4路与回路6.5图的连通性理论内容：路，回路，无向图的连通性，无向连通图的点连通度与边连通度，有向图的连通性第十九讲图论（三）6.6图的矩阵表示6.7赋权图及最短路径理论内容：图的邻接矩阵，可达矩阵，关联矩阵，赋权图，最短路径第十四周12月322第二十讲图论（四）7.1欧拉图理论内容：欧拉图的有关概念，欧拉定理，中国邮递员问题、Hamilton图第十五周12月844第二十一讲图论（五）7.2无向树7.3有向树理论内容：树的基本概念，最小生成树，二叉树的遍历与表达式的计算第二十二讲代数结构（一）5.1代数结构简介理论内容：代数结构的定义，半群及独异点，子代数，代数结构的同态与同构第十六周12月1722第二十三讲代数结构（二）5.2群的定义及性质理论内容：群的有关概念，子群，群的同态第十七周12月2422第二十四讲总复习系主任签名：院长签名：年月日年月日说明：1．本教学进度表由主讲教师负责填写，于每学期开学第一周内送交教师所在系，经领导审定、签字后备查。2．此表一式三份，其中，任课教师一份，教师所在系一份，教务处一份。第一讲：集合、映射和运算（一）一、教学目标1.掌握集合的概念与表示2.理解子集、幂集、n元组与笛卡儿积的概念3.掌握子集，幂集，笛卡尔积的求法二、重点与难点分析1.重点：集合的概念，子集，幂集，笛卡尔积的概念及求法2.难点：幂集三、教学内容与教学过程1.进行自我介绍（5分钟）姓名，联系方式，专业方向。建议学生用电子邮件方式联系。2.进行课程简介（10分钟）离散数学是研究离散量的结构及相互之间关系的学科是一门专业基础课，是数据结构、操作系统、计算机组成原理、数据库原理等课程的数学基础。特点：知识点集中，概念，定理多；方法性强；学数学就要做数学成绩评定：平时成绩(到课情况，书面作业，平时测验)占30%,期末考试占70%3.进入主题，开始第一讲(1)集合的有关概念(20分钟)①集合定义：集合是具有某种特定性质的对象汇集成的一个整体，通常用大写字母A,B,C,D表示。例如：滁州学院全体学生计算机与信息工程学院所有女生常见的数的集合：N,N+,Z,Q,R,C②元素集合中的每一个对象称为该集合的元素，通常用小写字母a,b,c,d,x,等表示例如：滁州学院的每个学生计算机与信息工程学院的每个女生N：0、1、2、3…③集合的表示方法列举法：Z={…,-2,-1,0,1,2,…}描述法：{x|x是自然数且x小于10}递归法文氏图：特殊集合：全集U,空集④元素与集合x∈A或|A|表示集合A中的元素个数注意：集合中的元素可以是集合，如A={a,{a,b},b,c},|A|=4,{a,b}∈A注：集合中的元素无顺序；集合中无重复元素例：指出下列哪些是集合，哪些不是集合？中国人的集合；百货商店里好看的花布的集合；1000以内的素数的集合；26个英文字母组成的集合；这个班里高个子学生的集合；直线y＝2x-5上的点的集合。(2)集合之间的关系 ①子集（15分钟）定义：若A中的任意元素都属于B，则A是B的子集，称A包含于B或B包含A，，包括的两层含义：包含与真包含（A≠B），，A是B的真子集注意：属于（元素与集合的关系）与包含于（集合与集合的关系）的区别例：A={1,2,3,4}，B={2,4}或定理1-1：A定理1-2：（自反性）则A=B则（传递性）用定义进行证明定理1-3：A=B的充要条件是注：该定理是证明两个集合相等的基本方法该定理与定理1-2中的(2)的区别例1-2注：A中有一个元素不属于C，则，反证法是一种很好的方法②幂集（15分钟）定义：由X的所有子集组成的集合，例：x={1,2}，Y={a,b,c}例1-3 注：若|X|=n,P(x)的元素有：；由一个元素构成的子集；由两个元素构成的子集；…由n个元素构成的子集计数的基本原理：加法原理：图示乘法原理：图示定理1-4：若|X|=n,|P(X)|=2n证明：加法原理：二项式定理：乘法原理：注：每个元素的参与与否构成不同的子集③n元组（5分钟）定义：论域U中选取的n个元素按照一定的顺序排列，得到n元有序组，称n元组，记为：(x1,x2,x3,…,xn)或<x1,x2,x3,…,xn>例：平面直角坐标系中点的坐标是2元组；空间直角坐标系中点的坐标是3元组；n元组在数据结构中是一个表有序对，序偶：2元组注：(x,y)≠(y,x)④笛卡尔积（10分钟）定义：设是集合，称为A1,A2,…An的笛卡尔积（直积，叉积），记为：例：A={a,b},B={1,2}，例1-4注：一般来说，定理1-5：若|A|=m,|B|=n,则||=m×n4.教学小结（5分钟）本讲首先介绍了集合的概念与表示方法，接着介绍了集合之间的关系——子集与幂集，n元组，笛卡尔积的概念及相关定理。四、作业与实验（5分钟）1.书面作业：习题1.11、2、3、7、102.上机作业：无

第二讲：集合、映射和运算（二）一、教学目标1.掌握映射的概念与表示2.理解映射的三种性质：单射、满射、双射，会判断某个具体映射是否具有这些性质3.掌握逆映射的含义，复合映射的定义及性质二、重点与难点分析1.重点：理解和判断映射的三种性质，逆映射，复合映射2.难点：映射三种性质的判断，复合映射的性质三、教学内容与教学过程1.习题讲解（10分钟）2.上讲内容回顾（3分钟）集合的概念：集合、元素、集合的表示方法集合间的关系：子集、幂集、n元组、笛卡尔积(1)映射的定义（15分钟）定义：对于A,B,若存在对应法则f，对于，唯一的与它对应，称f是A到B的一个映射或一个函数。记为：f:A→B（图示）例：CeilingfunctionFloorfunction取整函数定义域：自变量x的取值范围值域：函数值y的取值范围像：为X在映射f下的像原像：为Y在映射f下的原像注：全函数即=A；为x在映射f下的像：A到B的所有映射组成的集合定理1-6：|A|=m,|B|=n,则（证明）(2)映射的性质①单射(一对一映射)（10分钟）定义：，可推出x1=x2或，若x1≠x2，可得出例1-6：设则f是N到N的单射，试证明之。证：对于，由得出，进而x1=x2(使用定义证明)②满射（10分钟）定义：对于，使得y=f(x)充要条件：=B例1-7：设，则f是Z到N的满射，试证明之。证：对于取,显然有（使用定义证明）③双射（一一对应）（5分钟）定义:既单射又满射例1-8例1-9：建立一个（0,1）到R的一一对应解：置换：A到A的双射(3)逆映射（逆函数，反函数）（10分钟）定义：f:A→B，将f的方向逆转后，得到的集合B到集合A的映射定理1-7：f的逆映射存在的充要条件是f是双射（加以说明解释）注：若f是双射，则也是双射，且例1-11：判断所给出的映射是否有逆射，若有，求出其逆映射①②解：①∵f(2)=f(-2)=4,∴根据单射定义知f不是单射，进而其不是双射，根据定理1-7知其不存在逆映射②显然g是双射，其逆映射为(4)复合映射（20分钟）定义:设对于，令，则h是A到C的映射，h为f和g的复合映射或复合函数，记为（图示）注：条件:例1-12例1-13注：一般来说即使和都有意义，也不能保证成立恒等映射(IA)：定理1-9：若是双射，则若是双射，则定理1-10：若f和g是单射，则是单射（证明）若f和g是满射，则是满射（证明）若f和g是双射，则是双射且定理1-11：设若是单射，则f是单射，但g不一定（证明）若是满射，则g是满射，而f不一定（证明）定理1-12设，则4.教学小结（5分钟）本讲首先介绍了映射（函数）的定义及定义域、值域、像、原像等相关概念；接着介绍了映射的三种性质：单射，满射，双射；最后介绍了逆映射的定义及复合映射的定义及其具有的相关性质。四、作业与实验（2分钟）1.书面作业：习题1.21、2、6、11、14.2.上机作业：无第三讲：集合、映射和运算（三）一、教学目标 1.理解运算的定义2.掌握运算的表示及常用运算3.理解运算的性质并能判断具体运算是否具有某些性质二、重点与难点分析1.重点：运算的定义，运算的性质2.难点：运算性质的判定三、教学内容与教学过程1.习题讲解（5分钟）2.上讲内容回顾（5分钟）映射的定义映射的性质：单射，满射，双射逆映射复合映射3.进入主题，开始第二讲。本讲知识点概括(1)运算的定义（25分钟）①定义:设和B是集合，若，称f为到B的n元运算。A到B的n元运算，或A上的n元运算：A上的n元封闭运算（代数运算）：，有例：判定取绝对值运算||、加法运算+、取大运算max是否是自然数集合N(Z)上的代数运算。解：例：判定减法运算-,取小运算min是否是自然数集合N上的代数运算。解：例：判断数的加法运算是否是集合A={2n|n∈N}上的代数运算？解：例：将十进制数273转换成八进制解：273=,,②模运算定义：，是使成立的整数r,即x除以m的余数。例：16(mod3)、-8(mod5)、9(mod2)模m加法，模m乘法例：m=5,③最大公约数，最小公倍数若d|m且d|n,则d是m,n的公约数，用gcd(m,n)表示m,n的最大公约数若m|d且n|d，则d是m,n的公倍数，用lcm(m,n)表示m,n的最小公倍数。注：Gcd与lcm分别记为[,]和（，）gcd(m,n)=gcd(|m|,|n|)且lcm(m,n)=lcm(|m|,|n|)素因数分解：（对于大于1的正整数n都可以分解成一些素数乘积）Euclid算法例1-19若gcd(m,n)=1,称m和n互素。欧拉函数：表示小于等于n且与n互素的正整数的个数④运算表给定集合A，则集合A上的1元或2元运算可以用运算表来表示例：A={a,b,c},**abcabcababccbca思考：A上的封闭的1元，2元，3元运算的个数是多少？3339327(2)运算的性质①对合性（5分钟）定义：设*是A上的一元代数运算，例：？②幂等性（5分钟）幂等元：定义：A中的每个元素对于*都是幂等元例：*123112322323313例：③交换性（5分钟）定义：对于A上的二元运算*,,均有例：R上的+具有交换性R上的-，映射的复合运算?④结合性（5分钟）定义：例:映射的复合运算具有结合性R上的+具有结合性R上的-？⑤单位元素（幺元素）（5分钟）定义：对于A上的二元运算*，，使得对于例：R关于加法运算+的单位元素是0R关于乘法运算的单位元素是1R关于减法运算-的单位元素是？定理1-3：若A关于*有单位元素，则单位元素是唯一的证明：设e1,e2是A关于*的单位元素，则e1=e1*e2=e2⑥零元素（5分钟）定义：对于A上的二元运算*，，使得对于例:R关于乘法运算的零元素是0R关于减法运算-的零元素是？R关于加法运算的零元素是？定理1-4：若A关于*有零元素，则零元素是唯一的证明：设e1,e2是A关于*的零元素，则e1=e1*e2=e2⑦逆元素（5分钟）前提：A关于二元运算*有单位元素e定义：，使得：例：R上的加法运算+：x+(-x)=0=(-x)+xR上的乘法运算：注：逆元不一定存在，存在不一定唯一，参见表1-5定理1-5：若A关于*运算有单位元素为e且*运算满足结合律，若对于A中的x有左逆元y与右逆元z，则y=z,此逆元唯一证明：y*x=e,x*z=ey=y*e=y*(x*z)=(y*x)*z=e*z=z⑧消去性（分钟）定义：若A关于*有零元，则记为，对于，若例1-31Z上的加法运算+和乘法运算×均满足消去律.⑨分配性（5分钟）定义：是A上的两个二元运算，对于则称*关于是可分配的⑩吸收性（2分钟）定义：是A上的两个二元运算，对于则称*关于是可吸收的eq\o\ac(○,⒒)德摩根律（3分钟）定义：是A上的一元运算，是A上的两个二元运算，对于4.教学小结（3分钟）本讲首先介绍了运算的定义并介绍了几种常用的运算，接着介绍了运算的性质：对合性、幂等性、交换性、结合性、单位元素、零元素、逆元素、消去性、分配性、吸收性、德·摩根律，并结合之前所学知识讲解运算的性质。四、作业与实验（2分钟）书面作业：习题1.3：1、3、5、6、82.上机作业：无

第四讲：集合、映射和运算（四）一、教学目标1.掌握集合的各种运算2.理解各种集合运算所满足的性质3.掌握集合的划分与覆盖的概念4.了解集合的对等，集合的基数，可数集合等概念二、重点与难点分析1.重点：集合的运算——并、交、补、差、对称差集合运算性质2.难点：集合运算等值式的证明，集合的对等、基数三、教学内容与教学过程1.上讲内容回顾（5分钟）运算的定义运算的性质：对合性、幂等性、交换性、结合性、单位元素、零元素、逆元素、消去性、分配性、吸收性、德·摩根律2.进入主题、开始第四讲本讲知识点概括(1)集合的运算 ①并运算（15分钟）定义：定理1-16：是包含A和B的最小集合定理1-17：并运算满足的性质：（交换律）（结合律）（幂等律）（是∪运算的单位元素）（是∪运算的零元素）例1-38:设f:A®B,X,YÍA,则证明：证明：②交运算（15分钟）定义：定理1-18：是包含在A和B的最大集合定理1-19：交运算满足的性质：（幂等律）（交换律）（结合律）（是运算的零元素） （U是运算的单位元素）例：定理1-20：并运算与交运算之间满足的性质：

例1-41：证：③补运算（10分钟）定义：例1-42：（A的补集依赖于全集U的选取）A={a,b,c}U={a,b,c,d}定理1-21：定理1-22：德·摩根律：P25：④差运算（10分钟）定义：例1-43：定理1-23：证明：例1-45：证明：证：例1-46：例1-47：⑤对称差运算（10分钟）定义：例定理1-24：容斥原理形式：或：例：求1到1000之间（包含1和1000在内）既不能被5和6整除数有多少个？解：|S|=1000|A|=ë1000/5û=200,|B|=ë1000/6û=166|AÇB|=ë1000/lcm(5,6)û=ë1000/33û=33（2）集合的划分与覆盖（12分钟）①划分定义：其中：例1-53：设A={a,b,c},则A的所有不同的划分分别为:②覆盖设A是集合,由A的若干非空子集构成的集合称为A的覆盖,如果这些非空子集的并等于A.（3）集合的对等（10分钟）定义：A～B存在双射f:A®B.例：(0,1)～R集合的基数：无限集合A若集合A和B对等,则称这两个集合的基数相同.例：可数集合：能与自然数集合N对等的集合3.教学小结（2分钟）本讲首先介绍了集合的各种运算（并，交，补，差，对称差）及其满足的性质，接着介绍了集合的划分与覆盖的概念；最后介绍了集合对等、集合的基数及可数集合。四、作业与实验（1分钟）1.书面作业：习题1.45、8、10、13.习题1.5：1、72.上机作业：无第五讲：关系（一）一、教学目标1.掌握关系的概念尤其是二元关系的概念2.掌握关系的定义域和值域3.掌握关系的三种表示方法4.理解函数的关系定义二、重点与难点分析1.重点：二元关系概念、关系的三种表示方式、函数的关系定义2.难点：关系的概念三、教学内容与教学过程1.习题讲解（15分钟）2.上章内容回顾（5分钟）集合的有关概念映射的有关概念运算的定义与性质集合的运算、集合的划分与覆盖、集合的对等3.进入主题，开始第五讲本讲知识点介绍(1)关系的定义①关系的概念（15分钟）引例：A={张三,李四,王五};B={英语,C语言,离散数学,数据结构,汇编语言};C={优,良,合格,不合格}.A与B之间的关系R={(张三,离散数学),(张三,数据结构),(张三,英语),(李四,数据结构),(王五,C语言),(王五,汇编语言)}ÍA´B.A,B与C之间的关系S={(张三,离散数学,优),(张三,数据结构,良),(张三,英语,优),(李四,数据结构,优),(王五,C语言,合格),(王五,汇编语言,良)}ÍA´B´C.定义：是集合，，则R为间的n元关系特别的为A上的n元关系注（两层含义）：集合、关系例：A={王，李，张，黄}，B={100米，400米，铅球，跳远}，C={第一名，第二名，第三名，优秀奖}R={(王，100米，第二名)，（李，铅球，优秀奖），（张，100米，第一名），（黄，跳远，第二名）}二元关系的定义：两个集合A和B（可以相同）之间的关系称为二元关系A到B的关系：A上的关系：例：A={甲，乙，丙}R={(乙，甲)，（乙，丙），（甲，丙）}注：(x,y)表示x胜y例：A={张三，李四，王五}，B={教师，辅导员，导师}R={（张三，辅导员），（张三，教师），（李四，教师），（王五，导师），（王五，教师）}例2-1：例：A={a,b},R是P(A)上的包含关系，R={(x,y)|x,y∈P(A)且}P(A)=注意：关系的次序 定理2-1：若，则A到B的关系有若，则A上的关系有注：A到B的关系是A×B的子集②三种特殊的关系（5分钟）空关系：A到B的空关系A上的空关系全关系：A到B的全关系 A上的全关系恒等关系：例：A={0,1,2}={(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)}IA={(0,0),(1,1),(2,2)}③关系符号（10分钟）定义：若(x,y),则可记为例：实数集合R上的大于“>”关系：例：整数集Z上的整除关系“|”整除性质：例：模m同余关系性质：④关系的定义域和值域（5分钟）定义域:设,,即R中所有有序对中第一位置元素组成的集合,它显然是A的子集.值域：设RÍA´B,ranR={y|yÎB,存在xÎA,使得(x,y)ÎR},即R中所有有序对中第二位置元素组成的集合,它是B的子集.：R={(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4)},则domR={1,2,3,4}，ranR={1,2,3,4}.(2)关系的表示（20分钟）①集合表示法列举法：把关系内部的元素全部列举出来描述法：把关系内部成员的性质描述出来（同集合）②关系图表示法情形1R是A到B的关系A={a,b,c,d},B={1,2,3},R={(a,2),(a,3),(c,2),(d,2)}.情形2R是A上的关系A={a,b,c,d}，注：有向边③关系矩阵表示法定义：例2-13:A={a,b,c,d},B={1,2,3},R={(a,2),(a,3),(c,2),(d,2)}.例：A={a,b,c},(3)函数的关系定义（5分钟）①函数到关系的转换例：A={a,b,c},B={1,2,3},f:A®B,f(a)=2,f(b)=3,f(c)=3.②关系能够转换成函数的条件例：，不能转换成函数。例2-164.教学小结（3分钟）本讲首先讲解关系的概念与表示，特别介绍了二元关系，同时描述了三种特殊的关系：空关系、全关系、恒等关系，然后讲解了关系的三种表示方式：集合表示法、关系图表示法、关系矩阵表示法，接着讲解了关系与函数的区别与联系及它们间的转换。四、作业与实验（2分钟）1.书面作业：习题2.1：2、4(2)(4)(5)、13、14.上机作业：无 第六讲：关系（二）一、教学目标1.掌握关系的集合运算2.掌握关系的逆运算，逆关系的关系矩阵、关系图及逆关系的定理3.掌握复合关系、复合关系相关定理4.了解函数的复合运算二、重点与难点分析1.重点：复合关系、逆关系的概念及相关性质2.难点：复合关系、逆关系的性质三、教学内容与教学过程1.习题讲解（10分钟）2.上讲内容回顾（5分钟）N元关系的定义2元关系关系的定义域与值域关系的表示函数的关系定义3.进入主题，开始第六讲。(1)关系的集合运算（15分钟）关系的几种常见集合运算:注：解：例2-17(2)关系的逆运算（20分钟）为何考虑关系的逆运算?若x是y的老师,则y是x的学生,…①定义：注：就是将所有R中的有序对中的两个元素交换次序，例2-18：A={a,b,c,d},B={1,2,3},R={(a,3),(c,2),(a,2),(b,2)}.则②逆关系的关系图有向线条反向（图示例2-18）③逆关系的关系矩阵原关系的关系矩阵的转置（示例2-18）④逆运算的性质：定理2-2：（对合律）定理2-3：逆运算与关系的集合运算并,交,补的关系证明：（）：(3)关系的复合运算（35分钟）为何考虑关系的复合运算?若x是y的母亲,y是z的妻子,则x是z的岳母,…①关系R到关系S的复合运算（10分钟）例：，则：例2-19：借助关系图理解复合运算：关系矩阵：②复合关系的性质（10分钟）R◦S¹S◦R.例：R={(x,y)|x,yÎA,y=x+1或y=x/2}S={(x,y)|x,yÎA,x=y+2}≠定理2-4：证明思路：定理2-5：定理2-6：证明：注：本性质与矩阵的有关运算性质类似,请注意顺序定理2-7：③幂运算（10分钟）幂的表示方式：例2-23：设A={a,b,c},集合A上的关系R={(a,b),(b,c),(c,a)},试计算幂运算的性质：④函数的复合运算（5分钟）设f:A®B,g:B®C,函数f与函数g的复合记为f◦g:若f(x)=y且g(y)=z,则(f◦g)(x)=g(f(x))=z.由于fÍA´B,gÍB´C,关系f与关系g的复合记为f◦g:若(x,y)Îf且(y,z)Îg,则(x,z)Îf◦g.注：函数f与函数g的复合f◦g与将其看作关系时关系f与关系g的复合是一致的4.教学小结（3分钟）本讲分别介绍了关系的集合运算、逆运算，复合运算，并且对复合关系、逆关系的定义、表示方式、相应的关系矩阵进行了讲解，还介绍了它们之间满足的相关性质，最后介绍了函数的复合运算。四、作业与实验（2分钟）1.书面作业：习题2.21、3、6、8、12(选).2.上机作业：无 第七讲：关系（三）一、教学目标1.理解关系的各种性质2.掌握满足各种性质的关系的关系矩阵和关系图3.理解闭包的含义4.掌握闭包的几个关键5.掌握闭包的构造二、重点与难点分析1.重点：自反性、反自反性、对称性、反对称性、传递性概念的理解，闭包的理解与构造2.难点：同上三、教学内容与教学过程1.上讲内容回顾（5分钟）关系的集合运算关系的逆运算关系的复合运算2.进入主题，开始第七讲本讲知识点概括(1)关系的性质自反性（10分钟）定义：对于集合A上的元素a属于A，有(a,a)属于R,那么R就是一个自反关系例2-25：A={a,b,c,d},R={(a,a),(a,b),(b,b),(c,c),(c,a),(d,d)}?注：Z上的整除关系|是自反的;P(X)上的包含关系Í是自反的;R上的小于等于关系£是自反的;R上的小于关系<不是自反的.定理：R自反Û注：空关系Æ是空集Æ上的自反关系.关系矩阵：对角线元素都为1关系图：结点含有环反自反性（10分钟）定义：设RÍA´A,若对于任意xÎA,均有(x,x)ÏR,则称R是A上的反自反关系,或称R具有反自反性.例2-26：A={a,b,c,d},R={(b,a),(a,b),(b,c),(c,d),(c,a)}?注：Z上的整除关系|不是反自反的;P(X)上的包含关系Í不是反自反的;R上的小于等于关系£不是反自反的;R上的小于关系<是反自反的.定理：R反自反Û注：空关系Æ是空集Æ上的反自反关系.关系矩阵：对角线元素全为0关系图：结点没有环思考：A上的自反关系与反自反关系的区别与联系?对称性（10分钟） 定义：设RÍA´A,对于任意x,yÎA,若(x,y)ÎR,则(y,x)ÎR,则称R是A上的对称关系,或称R是对称的,或称R具有对称性例2-28：A={a,b,c,d},R={(b,a),(a,b),(b,b),(d,c),(c,d)}?注：Z上的整除关系|不是对称的;P(X)上的包含关系Í(一般来说)不是对称的;R上的小于等于关系£不是对称的;R上的小于关系<不是对称的;三角形之间的相似关系~是对称的;Z上的模k同余关系ºk是对称的.定理2-11：R对称ÛR=R-1 关系矩阵：关于对角线对称图关系图：要么有双向环、要么没有反对称性（10分钟）定义：设RÍA´A,对于任意x,yÎA,若(x,y)ÎR且(y,x)ÎR,一定有x=y,则称R是A上的反对称关系,或称R具有反对称性.例2-29：A={a,b,c,d},R={(a,a),(a,b),(b,b),(b,c),(d,c)}?注：Z上的整除关系|不是反对称的,因为2|-2且-2|2;P(X)上的包含关系Í是反对称的;R上的小于等于关系£是反对称的;R上的小于关系<是反对称的.定理2-12：R反对称Û关系矩阵:关于主对角线对称的元素不能同时为1关系图:两点之间要么无边，要么只有一条边思考：反对称性与对称性之间的区别与联系传递性（10分钟）定义：设RÍA´A,对于任意x,y,zÎA,若(x,y)ÎR且(y,z)ÎR,均有(x,z)ÎR,则称R是A上的传递关系,或称R具有传递性.例2-31：A={a,b,c,d},R=(a,a),(a,b),(b,b),(b,c),(a,c),(c,a)}?注：Z上的整除关系|是传递的;P(X)上的包含关系Í是传递的;R上的小于等于关系£是传递的;R上的小于关系<是传递的.定理2-13：R传递ÛR◦RÍR.证明:(Þ)设(x,z)ÎR◦R,则存在yÎA,使得(x,y)ÎR,(y,z)ÎR.因为R传递,所以(x,z)ÎR.(Ü)对于任意x,y,zÎA,若(x,y)ÎR且(y,z)ÎR,则(x,z)ÎR◦RÍR,(x,z)ÎR.例2-33:A={a,b,c,d},R1={(a,b),(a,c)}传递,R2={(a,b)}也传递?,传递性的关系图:定理2-13:R传递ÛR◦RÍR.(2)关系的闭包 ①自反闭包r(R)（10分钟）定义：设RÍA´A,称最小的包含R的自反关系为R的自反闭包,记为r(R).满足3个条件:包含R；自反性；最小性.例2-38：设A={a,b,c},R={(a,a),(b,a),(b,c),(c,a),(a,c)},求出R的自反闭包.解：r(R)=RÈ{(b,b),(c,c)}定理2-14:生成自反闭包关系图的变化：R中不含环的添加环生成自反闭包关系矩阵的变化：把对角线上是0的元素全部改成1 ②对称闭包s(R)（10分钟）定义：设RÍA´A,称最小的包含R的对称关系为R的对称闭包,记为s(R).满足3个条件:包含R；对称性；最小性.例2-15：解：定理2-15： 生成对称闭包关系图的变化：只有一边的添加一边生成对称闭包关系矩阵的变化：关于对角线对称的元素相等③传递闭包r(R)（10分钟）定义：设RÍA´A,称最小的包含R的传递关系为R的传递闭包,记为t(R).满足3个条件:包含R；传递性；最小性.例：设A={a,b,c},R={(a,b),(b,c),(b,a)},求t(R).解：t(R)={(a,b),(b,c),(b,a),(a,c),(a,a),(b,b)}.例:A={a,b,c,d}R={(a,b),(b,c),(c,d)}t(R)={(a,b),(b,c),(c,d),(a,c),(b,d),(a,d)}定理2-16：定理2-17：若|A|=n³1,RÍA´A,则传递闭包的关系图:从a到b的边存在，从b到c的边存在，那么添加从a到c的边3.教学小结（3分钟）本讲重点介绍了关系的几个性质：自反性、反自反性、对称性、反对称性、传递性的定义、及他们的关系矩阵、关系图；接着介绍了自反闭包，对称闭包，传递闭包的定义及构造。四、作业与实验（2分钟）1.书面作业：习题2.3：3、5、8、9习题2.4：2、3、9、102.上机作业：无第八讲：关系（四）一、教学目标1.掌握等价关系，等价类及商集的概念2.了解相容关系的概念3.掌握偏序关系，哈斯图的画法，会求偏序集上的特殊元素二、重点与难点分析1.重点：等价关系、等价类、偏序集、哈斯图2.难点：偏序关系三、教学内容与教学过程1.习题讲解（5分钟）2.上讲内容回顾（5分钟）关系的性质：自反性；反自反性；对称性；反对称性；传递性关系的闭包：自反闭包；对称闭包；传递闭包3.进入主题，开始第八讲。(1)等价关系（25分钟）①等价关系：设RÍA´A,若R具有自反性、对称性以及传递性,则称R为A上的等价关系.例2-47：设A={a,b,c},R={(a,a),(b,b),(c,c),(b,c),(c,b)},则R具有自反性、对称性以及传递性,因此R为A上的等价关系.例：Z上的模3同余关系是Z上的等价关系。定理2-21：设R和S为A上的等价关系,则R-1及RÇS为A上的等价关系.②等价类：定义：例：Z上的模3同余关系R：定理2-22：设R为A上的等价关系,对于任意x,yÎA,则证明：定理2-23：设R为A上的等价关系,对于任意x,yÎAÆ.证明：③商集：例2-47:A/R={{a},{b,c}}定理2-24：设R是集合A上的等价关系，则A关于R的商集A/R是集合A的划分.例2-51：设A={a,b,c},p={{a},{b,c}},则R={(a,a),(b,b),(c,c),(b,c),(c,b)},它是A上的一个等价关系..注：(x,y)ÎRÛx和y在划分p的同一个块中定理2-25：对于任意集合A,集合A上的所有划分组成的集合X与其上的所有等价关系组成的集合Y是对等的.(2)相容关系（10分钟）相容关系：设RÍA´A,若R具有自反性、对称性，则称R为A上的相容关系.等价关系Þ相容关系,但相容关系不一定是等价关系(3)偏序关系①偏序关系定义（10分钟）设RÍA´A,若R具有自反性、反对称性和传递性,则称R为A上的偏序.借用数的£表示偏序,可读作“小于等于”,(A,£)称为偏序集.例：R,£?P(X),Í?N+,|?线性序：设£是A上的偏序,若对任意x,yÎA,有x£y或y£x,则称£是线性序关系,简称线性序或全序。实数集R上的数的小于等于关系£是线性序.整除关系不是正整数集合上的全序关系.②偏序集的哈斯图（20分钟）覆盖：x,y∈A,如果x≺y且不存在z∈A使得x≺z≺y,则称y覆盖x.COV(A)={(x,y)|x,yÎA且y覆盖x}.例：{1,2,4,6}集合上的整除关系：R={(1,2)(1,4),(1,6),(2,4),(2,6)}则2覆盖1,4和6覆盖2,4不覆盖1.例2-62:设A={a,b},则P(A)={Æ,{a},{b},{a,b}},则P(X)上的包含关系“Í”是其上的偏序关系,求COV(A).解：根据定义知,{a}盖住Æ,{b}盖住Æ,{a,b}盖住{a},{a,b}盖住{b}.因此COV(A)={(Æ,{a}),(Æ,{b}),({a},{a,b}),({b},{a,b})}.哈斯图：利用偏序关系的自反、反对称、传递性进行简化的关系图哈斯图特点：a.每个结点没有环 b.两个连通的结点之间的序关系通过结点位置的高低表示，位置低的元素的顺序在前c.具有覆盖关系的两个结点之间连边哈斯图的画法：a.用黑点代表A中元素;b.y盖住x,y画在x的上方且用一条线段连接x和y.例：偏序集<{1,2,3,4,5,6,7,8,9},R整除>和<P({a,b,c}),RÍ>的哈斯图.③偏序集中的特殊元素：（10分钟）a.最小元、最大元、极小元、极大元若"x(x∈B→y≼x)成立,则称y为B的最小元若"x(x∈B→x≼y)成立,则称y为B的最大元若"x(x∈B∧x≼y→x=y)成立,则称y为B的极小元若"x(x∈B∧y≼x→x=y)成立,则称y为B的极大元b.上界、下界、上确界、下确界若"x(x∈B→x≼y)成立,则称y为B的上界若"x(x∈B→y≼x)成立,则称y为B的下界令C＝{y|y为B的上界},C的最小元为B的最小上界或上确界令D＝{y|y为B的下界},D的最大元为B的最大下界或下确界例：设偏序集(A,≼)，求A的极小元、最小元、极大元、最大元，设B＝{b,c,d},求B的下界、上界、下确界、上确界.解：极小元：a,b,c,g；极大元：a,f,h；没有最小元与最大元.B的下界和最大下界都不存在；上界有d和f,最小上界为d.4.教学小结（3分钟）本讲介绍了几种常见关系：等价关系，相容关系，偏序关系。与等价关系相关的介绍了等价关系，等价类，商集等；与相容关系相关的介绍了相容关系，相容类；与偏序关系相关的介绍了偏序关系，哈斯图，偏序集，以及特殊元素。四、作业与实验（2分钟）1.书面作业：习题2.5：1、2、3习题2.7：2、82.上机作业：无第九讲：命题逻辑（一）一、教学目标掌握命题的概念（真假命题）掌握命题逻辑的表示方式（对象语言与元语言）掌握连接词符号的表示以及真假的判定二、重点与难点分析1.重点：对命题概念的理解以及对象语言、元语言的区别，几种连接词的表示以及判定真假的方法2.难点：对命题概念的理解以及对蕴含词符号的理解三、教学内容与教学过程1.上章内容回顾（5分钟）2.1关系的概念2.2关系的运算2.3关系的性质2.4关系的闭包2.5等价关系2.7偏序关系2.进入主题，开始第九讲(1)命题的有关概念（25分钟）计算机的计算过程就是推理过程,而每一步推理离不开判断,判断的对象就是命题.①命题定义：能判断出真假的语句注：a,命题必须是一个完整的句子,包括用数学式子如代表的语句.这一点在后面的命题符号化时要注意;b,所给语句具有真假意义,即有是否符合客观实际或是否合理之分.一般来说,只有陈述句才具有真假意义,祈使句、疑问句和感叹句不具有真假意义;c,能判断出真假,不过,要是将来某时候能判断出真假也行例：你妈喊你回家吃饭.《建国大业》里面有很多大腕儿.x>3.(不是命题)立正！(不是命题)这朵花真漂亮！(不是命题)你喜欢网络游戏吗?(不是命题)火星上有生物.我说的都是假话.(不是命题)小王和小李是同学.你只有刻苦学习,才能取得好成绩我不去游泳仅当你走，我留下值班②命题的真值命题的真值就是命题的逻辑取值经典逻辑值只有两个:1和0,它们是表示事物状态的两个量。实际上在数理逻辑中,更多时候逻辑真是用T(True)或t,逻辑假用F(False)或f表示的③命题的表示a.对象语言的描述b.命题独享语言的描述：原子命题是不包含有更小的命题的命题，通常用小写英文字母p,q,r,s,…或带下标p1,p2,p3,…等来表示原子命题,如用p:2+3=5,q:今天我们上课.复合命题是由原子命题和联接词构成的命题，联接词类似于自然语言中的连词。注：“小王和小李是同学”是原子命题。例：“仅当你走，我留下值班”：p:你走，q:我留下值班“我不去游泳”：p：我去游泳命题常量、命题变量把1和0称为逻辑常量；在逻辑表达式中出现的p,q,r或p1,p2,p3等称为命题变元或逻辑变量.(2)连接词符号（55分钟）①否定联接词Ø：Øp （5分钟）p:2+3=5,Øp:2+3¹5.pØp1001真值表：

例：p:下周开运动会，Øp：下周不开运动会注：Øp是数理逻辑中的标准符号,也可记为~p,C语言!p,在计算机其他课程中用,对应于逻辑门电路中的“非门”.②合取联接词Ù:pÙq（10分钟）p:小李能歌,q:小李善舞.pÙq:小李能歌且善舞.合取“Ù”相当于“并且”,“和”,“与”,“以及”等.pqpÙq111100010000真值表：注意：“小王和小李是同学”中的“和”没有合取之意.在数理逻辑中,合取联结词可以将任意两个命题联结起来以构造出新的命题,如用p:2+3=5,q:今天上课,则pÙq:2+3=5且今天上课.注：pÙq:p&q,p&&q,p×q=pq,对应于“与门”.③析取联接词Ú:pÚq（5分钟）p:这学期我选修人工智能课程,q:这学期我选修模式识别课程.pÚq:这学期我选修人工智能课程或者模式识别课程.析取“Ú”相当于“或者”.p|q,p||q,p+q(“或门”).pqpÚq111101011000真值表：

④异或联接词Å:pÅq（10分钟）自然语言中的“或”:“可兼或”(inclusiveor),它表示两者可同时为真,用析取表示即可；“不可兼或”,它表示两者不能同时为真,换句话说,两者同时为真是假命题.这就需要异或联结词.p:明天去深圳的飞机是上午八点起飞,q:明天去深圳的飞机是上午八点半起飞.pÅq:明天去深圳的飞机是上午八点或上午八点半起飞.pqpÅq110101011000真值表：

注：与异或联结词对应的门电路为“异或门”.对于自然语言中的“或”用还是需要仔细分析,一般来说,只要不是非常明显的不兼就使用Ú.⑤条件联接词®:p®q（10分钟）p:我有时间,q:我去看望我的父母.p®q:如果我有时间,那么我去看望我的父母.“®”相当于“如果…那么…”,“若…则…”,等.p®q可读作“(若)p则q”.pqp®q111100011001真值表：

在p®q中,p称为前件,q称为后件.当p=1,q=1时p®q=1;当p=1,q=0时p®q=0,这是比较好理解的两种情形.由于我们现在讨论的是实质蕴涵,规定当p=0,q=1时p®q=1;当p=0,q=0时p®q=1.规定的合理性见下面的例子.a.如果太阳从西边出来,那么2+3=5.b.如果太阳从西边出来,那么2+3=4.⑥双条件联接词«:p«q（10分钟）p:四边形是平行四边形,q:四边形的对边平行.p«q:四边形是平行四边形当且仅当四边形的对边平行.p«q:可读作“p当且仅当q”.双条件联结词“«”相当于自然语言中的“当且仅当”“p当且仅当q”有两层含义：(1)“p当q”是指q®p.(2)“p仅当q”是指p®q.正因为此,等价联结词又可以称为双蕴涵联结词或双条件联结词.pqp«q111100010001真值表：注：在数字逻辑等课程中,等价联结词称为“同”,并用“⊙”符号表示⑦与非联接词­:p­q（2分钟）pqp­q110101011001

真值表：⑧或非联接词¯:p¯q（2分钟）pqp¯q110100010001真值表：⑨条件否定联接词：（1分钟）真值表：pq

1101010100004.教学小结（3分钟）本讲首先介绍了命题的概念及其表示方式，然后依次介绍了九种联接词，其中重点需要掌握否定联接词、合取联接词、析取联接词、异或联接词、条件联接词、双条件联接词等，重点注意条件联接词的表达方式。四、作业与实验（2分钟）书面作业：习题3.21、2、3、4、5、6.2.上机作业：无第十讲：命题逻辑（二）一、教学目标1.理解命题公式的概念2.掌握命题公式的组成符号、组成原则3.掌握变元真值指派的含义及命题公式的真值表4.理解命题公式的类型，掌握命题公式类型判断的方法二、重点与难点分析1.重点：命题公式的概念，命题公式的真值表，命题公式类型的判断2.难点：命题公式类型的判断三、教学内容与教学过程1.习题讲解（10分钟）2.上讲内容回顾（5分钟）命题的概念（真假命题）命题逻辑的表示方式（对象语言与元语言）连接词符号的表示以及真假的判定3.进入主题，开始第十讲本讲知识点概括(1)命题公式（15分钟）①命题公式的概念命题公式是由命题常量、命题变元、逻辑联结词、左圆括号(及由圆括号)构成的有意义(well-formed)的符号串,其严格定义需借助于递归定义方式给出.a.1,0,p,q,r,…b.AÞ(ØA)c.A,BÞd.有限次应用(1)(2)(3)所得到的符号串是仅有的命题公式.例:命题公式可称为合式公式或简称为公式,其全称为命题合式公式.这儿的公式实际上是书写正确、含义清楚的表达式或者说符号串可以省略括号的约定:a.最外层的括号可以省略.在形成最终的命题公式时,所有的中间过程得到的命题公式,包含其本身,都称为该命题公式的子公式.b.9个联结词运算的优先顺序依次为:符合本约定的有些括号可以不写.如命题公式注：这种规定不是唯一的.c.同级运算从左至右依次进行.如实际上,在对命题进行符号化时,只要书写正确的逻辑函数都是命题公式.(2)命题的符号化（15分钟）命题的符号化就是使用符号—命题变元、逻辑联结词和括号将所给出的命题表示出来.一方面说明,符号体系来源于实际问题,另一方面也是给出进一步学习逻辑演算系统的语义解释时的一种标准模型.命题的符号化的步骤:Step1找出所给命题的所有原子命题,并用小写英文字母或带下标表示；Step2确定应使用的联结词,进而将原命题用符号表示出来.例3-7(P86)将下列命题符号化.a.天气很好或很热.b.如果张三和李四都不去,那么我就去.c.仅当你走,我留下.e.我今天进城,除非天下雨.d.你只有刻苦学习,才能取得好成绩.解：a.或?b.“张三不去”是复合命题.c.p:你走,q:我留下,仅当?d.p:我今天进城,q:天下雨.除非=如果不.e.p:你刻苦学习,q:你取得好成绩.只有p,才q?(3)命题公式的真值表（20分钟）对于命题公式,若对中出现的每个命题变元都指定一个真值1或者0,就对命题公式A进行了一种真值指派或一个解释,而在该指派下会求出公式A的一个真值.将A的所有可能的真值指派以及在每一个真值指派下的取值列成一个表,就得到命题公式A的真值表.例3-8写出命题公式A=的真值表.pqrØpØpÚq(ØpÚq)®r111011110010101001100001011111010110001111000110例：B＝(q®p)Ùq®ppqq®p(q®p)Ùq(q®p)Ùq®p00011011101100011111例：C＝Ø(ØpÚq)ÙqpqØpØpÚqØ(ØpÚq)Ø(ØpÚq)Ùq000110111100110100100000注：由表知,含3个命题变元的命题公式有8=23种不同的真值指派.很显然,含2个命题变元的命题公式有4=22种不同的真值指派.一般来说,含n个命题变元的命题公式的不同的真值指派有2n种.（4）命题公式的类型（20分钟）a.在任何指派下均取真的命题公式称为永真式或重言式；b.在任何指派下均取假的命题公式称为永假式或矛盾式；c.至少有一种指派使其为真的命题公式称为可满足式；d.至少有一种指派使其为真同时至少有一种指派使其为假的命题公式称为中性式.判断公式种类的方法：①真值表法(求出公式的所有指派,判断公式的类型)例3-9pqp®qØpÚq111101011001②取值法：例：由A=1可推出B=1,则A®B永真.由B=0可推出A=0,则A®B永真.例：用真值表判断下面公式的类型(1)pÙrØÙ(q®p)(2)((p®q)®(ØqØ®p))Úr(3)(p®q)«(p®r)pqrq®pØ(q®p)pÙrØÙ(q®p)000001010011100101110111110011110011000000000000定理3-1(永真式的代入定理)如何使用？4.教学小结（3分钟）本讲首先介绍了命题公式的概念以及命题的符号化，接着介绍了命题公式的真值表及命题公式的类型，最后重点介绍了如何利用真值表法和取值法判断命题公式的类型。四、作业与实验（2分钟）1.书面作业：习题3.31(双),2(双),3(双),4,5,6(双).2.上机作业：无第十一讲：命题逻辑（三）一、教学目标 1.理解命题公式的逻辑等值的概念2.理解并掌握基本等值式及其他重要等值式3.掌握等值演算法及其应用二、重点与难点分析1.重点：基本等值式，等值演算法2.难点：应用等值演算法三、教学内容与教学过程1.习题讲解（5分钟）2.上讲内容回顾（5分钟）命题公式的定义命题的符号化命题公式的真值表命题公式的类型3.进入主题，开始第十一讲本讲知识点概括(1)逻辑等值定义：给定两个命题公式A和B,若在任何真值指派下A和B的真值都相同,则称命题公式A和B逻辑等价或逻辑等值或简称为等值或相等,记为A=B.注：A«B与A=B(AÛB)是不同的.A=B(AÛB)中的=是关系符号，A=B是等值式，«是运算符号，A«B是命题公式，运算结果可真可假。定理3-2：A=B的充要条件是A«B永真.证明：例3-11证明pqP→qØpØpÚq11101100000111100111

②模运算定理3-3：例如：定理3-4：逻辑等值是命题公式间的等价关系:(1)A=A（自反性）(2)若A=B，则B=A（对称性）(3)若A=B且B=C，则A=C（传递性）.(2)基本等值式①与Ø,Ù,Ú有关的等值式定理3-5：（对合律）（幂等律）（交换律）（结合律）（吸收律）注：与集合的有关性质类似.每条性质均可证明. 例3-12：证明对于任意命题公式A和B，有证明：只需证pq1111100101000000②其他重要等值式设A,B是任意的命题公式，则注：基本等值式有很多用途,如化简命题公式、判断命题公式的类型、证明等值式、计算命题公式的范式、命题逻辑中的推理等,要求大家要熟记,特别是定理3-5中的等值式.(3)等值演算法定理3-7（等值置换定理）：设C是命题公式A的子公式,若C=D,则将A中的C部分或全部替换为D所得到的命题公式与A等值.利用基本等值式以及等值置换定理求解问题的方法称为“等值演算法”.①化简命题公式例3-13(P92)化简下列命题公式并将最后结果用只含Ø和Ú表示.a.b.解：a.b.注：命题公式的化简是指将其化为一个与其等值的满足条件的含“联接词最少”的命题公式。②判断命题公式的类型例3-14：设A,B,C是任意的命题公式,判断下列命题公式的类型:解：故是中性式③证明命题公式等值例3-15：设A,B,C是任意的命题公式,证明下列等值式.a.b.证明：a.b.(4)对偶原理定义：设命题公式A中只含有3个逻辑联结词Ø,Ù,Ú,将A中的Ù换成Ú；A中的Ú换成Ù；A中的1换成0；A中的0换成1,所得到的命题公式称为是A的对偶式,记为A*.例：对偶原理：设A和B是命题公式,若A=B,则A*=B*.4.教学小结（3分钟）本讲首先介绍了命题公式等值的概念，然后介绍了基本等值式及其他重要等值式，在此基础上又介绍了等值演算法，并举例说明如何用等值演算法化简命题公式、判断命题公式类型、证明命题公式等值。最后介绍了命题公式的对偶原理。四、作业与实验（2分钟）1.书面作业：习题3.45(双),6,9(双),10,112.上机作业：无第十二讲：命题逻辑（四）一、教学目标1.理解命题公式的析取范式、合取范式、主析取范式、主合取范式、2.掌握命题公式的范式及主范式的求法3.掌握命题公式的范式的应用：求出真假指派4.掌握命题公式的主范式的应用：判断命题公式的类型、判断命题公式等值、由真值表求命题公式二、重点与难点分析1.重点：命题公式的范式的求法，范式的应用2.难点：同上三、教学内容与教学过程1.上讲内容回顾（5分钟）逻辑等值的定义基本等值式等值演算法对偶原理2.进入主题，开始第十二讲本讲知识点概括命题公式的析取范式（20分钟）①定义：设A是命题公式,若A=A1ÚA2Ú…ÚAn(n³1),其中Ai(1£i£n)是由命题变元或其否定组成的合取式,则称A1ÚA2Ú…ÚAn注：Ai=ØpÙØqÙr,pÙØq,ØqÙr,q,Ør?n=1?如A=ØpÙØqÙr=(ØpÙØqÙr).②求法Step1使用等值式,将命题公式中的联结词归约为Ø,Ù,Ú；Step2利用DeMorgan律将Ø移到命题变元的前面；Step3根据分配律得到命题公式的析取范式及合取范式：AÙ(BÚC)=(AÙB)Ú(AÙC).例3-17：设p,q和r是命题变元,求命题公式A=(p®q)«r的析取范式.解： 命题公式的合取范式（10分钟）①定义：设A是命题公式,若A=A1ÙA2Ù…ÙAn(n³1),其中Ai(1£i£n)是由命题变元或其否定组成的析取式,则称A1ÙA2Ù…ÙAn注：Ai=ØpÚØqÚr,pÚØq,ØqÚr,q,Ør?n=1?如A=ØpÚØqÚr=(ØpÚØqÚr).若A=ØpÚØqÚr,则ØpÚØqÚr也是A的析取范式.②求法Step1使用等值式,将命题公式中的联结词归约为Ø,Ù,Ú；Step2利用DeMorgan律将Ø移到命题变元的前面；Step3根据分配律得到命题公式的析取范式及合取范式：AÚ(BÙC)=(AÚB)Ù(AÚC)例3-17：设p,q和r是命题变元,求命题公式A=(p®q)«r的析取范式.解： 析取范式及合取范式的应用（20分钟）根据命题公式的析取范式及合取范式可分别得出该命题公式取真、假的指派.例：例3-18：从p,q,r,s四人中选派2人出差,求满足下列3个条件的选派方法有哪几种.a.若p去,则r和s中只去1人；b.q和r不能都去；c.若r去,则s不能去.解:p:p去出差,q:q去出差,r:r去出差,s:s去出差,则则：(a)p,s去;(b)q,s去;(c)p,r去.(4)命题公式的主析取范式（10分钟）①最小项：对于给定的命题变元,若由命题变元或其否定组成的合取式满足(1)每个命题变元或其否定二者之一只出现一次；(2)按字典顺序或按下标从小到大顺序出现。注：对于每一个最小项只有一种指派使