离散数学课程改革的实例阐释

王宁 董广华

摘要：根据离散数学的内容特点，通过大量实例阐述本课程改革的重点，包括课程连贯性、实用性、与其他学科的关联性等方面，引导并激发学生的学习兴趣，提高逻辑思维和发散思维能力。

关键词：离散数学实例；课程改革；实用性；学科关联

中图分类号：G642.0 文献标志码：A 文章编号：1674-9324（2018）13-0181-03

离散数学是现代数学的重要分支，它在数学与计算机等领域的学习中具有承上启下的重要作用。然而因为离散数学理论性较强，部分内容较为抽象。另外，从内容结构上看，离散数学主要包括数理逻辑、集合论、代数结构、图论等四个基本部分，这四个部分均可自成体系，体现了离散数学课程本身具有较为“离散”的特点。这些原因都有可能限制学生在学习中发挥主观能动性。因此，在离散数学课程改革中教师需要格外注重引导学生的学习兴趣。在教学中，通过引入生动的实例，培养学生掌握处理离散结构的工具和方法，学习抽象的思维模式和严格的逻辑推理能力，帮助计算机相关专业的学生建立起学习和使用“0-1”来建模解决问题的思想，并进行发散思维的训练。

为了达到上述目标，根据离散数学的学科特点，在课程改革中应将以下几个方面贯穿教学始终，引导学生学习与思考：（1）{0，1}的学习和使用；（2）离散数学各部分间的紧密关联；（3）实用性与实践性；（4）离散数学与其他学科的关联。

一、{0，1}的作用

{0，1}的运用贯穿离散数学课程的始终。比如，在逻辑学中表示命题的真假，集合论中表示元素与集合的隶属关系，图论中表示两结点之间是否有边相连，等等。目前大部分计算机系统都是二进制系统，{0，1}在计算机相关专业中具有重要地位。在教学中应当让学生体会到，恰当引入{0，1}构造的模型会带来研究中的便利。

实例1：引进{0，1}编码表示有限集S的所有子集。

S（i∈J），J={i|i是n位二进制数，00…0≤i≤11…1}

以S={a，b，c}为例，子集的符号表达形如S=S={b，c}，S=S={a，b}等。

本例的解读与启发：在集合论中元素与集合之间具有明确的隶属关系，即只有{不属于，属于}两种，因此可用{0，1}来简练表达，方便输入计算机处理计算等问题。例如计算{b，c}∩{a，b}={b}，通过编码可转化为逻辑学中的按位合取运算S∩S=S=S={b}。将本例引申关联到隶属函数概念，脚码实际体现出了特征函数的定义，例如集合S的特征函数为：χ：S→{0，1}

χ（a）=0，χ（b）=1，χ（c）=1

实例2：极小项的二进制与十进制编码。

在求命题公式的主析取范式和主合取范式时需要用到极大项与极小项的概念。为了方便使用，引入符号表达。例如具有两个变元的四个极小项的真值表（见表1）。

根据其成真赋值唯一的性质，将成真赋值作为其特征，引入编码表达，得到m00=m0=?P∧?Q，m01=m1=?P∧Q，m10=m2=P∧?Q，m11=m3=P∧Q

类似的也可定义具有多个变元的极小项与极大项的符号表达，其结果同样适用于计算机描述和处理大规模问题。

实例3：有向图的邻接矩阵。

设G=〈V，E〉是一个简单图，它有n个结点依序排列V={v，v，…，v}，则n阶方阵A（G）=（a）称为图G的邻接矩阵。其中

a=1

v与

v邻接

0

v与

v不邻接或i=j

例如图1中，图G的邻接矩阵为

A（G）=

本例的启发：结点之间是否有边相连使用1或0表达，并写入矩阵的方法简单易行，同时使用矩阵表示图，便于计算机存储和后续计算，已成为图论中广泛使用的经典研究方法。

类似的实例还有很多。通過实例可以提高学生的学习兴趣，加深对{0，1}应用的广泛性的认识，启发学生对{0，1}建模进行思考，并为用计算机解决实际问题开拓思路。

二、离散数学的各部分紧密关联

离散数学课程主要包含数理逻辑、集合论、代数系统、图论四个部分。各部分独立存在，自成体系，在学习的过程中很容易切割其内在联系。但这四个部分也互相渗透，因此在教学中强调各部分之间的关联，既有助于加深对课程内容的理解，也对培养学生的发散思维大有裨益。

实例1：逻辑等价式与集合运算的内在关系。

在学习命题逻辑时需要掌握一系列的命题逻辑等值式，同样，在学习集合的运算时，也有系列的性质。将二者对照会发现其内容、体系虽然不同，但结构完全相似。

例如：设集合A={x|x∈P（x）}，对应谓词公式P（x）表示集合的属性：x具有性质P；类似的定义集合B={x|x∈Q（x）}。可以观察到集合论中的交换律A∪B=B∪A，在逻辑学中的含义为：x∈P（x）∨x∈Q（x）?x∈Q（x）∨x∈P（x）。

本例体现出数理逻辑和集合论可以看作是对同一个问题在两个体系下的阐述。该实例将数理逻辑、集合论与代数系统三部分内容建立关联，有助于学生从宏观角度把握离散数学课程的内容。

实例2：等价关系与集合划分的关联。

引入一个生活中的实例“商贩的苹果”：市场的商贩贩售苹果遵循统一进货，分档次售出的方法，如图2所示。

将苹果编号，记作集合A={1，2，…，8}。

（1）从划分的角度考虑记S={1，4，7}，S={2，5，8}，S={3，6}，则集族S={S，S，S}为A的一个划分，意为将苹果按照大、中、小分为三个子集。

（2）从关系的角度考虑：定义苹果集合A上的关系R：“售价相同关系”。不难验证：关系R满足自反、对称、传递性，为A上的等价关系。

本例再次体现了同一个问题从两个不同角度阐述和建模的思想，并得到“等价关系与划分一一对应，可相互求解”这一结论。同时，还可在本例的基础上继续引申：设A={1，2，…，8}，定义A上的模3同余关系：R={|x，y∈A∧x≡y（mod 3）}，也可得到相同的划分

S={1，4，7}，S={2，5，8}，S={3，6}。可见其与“商贩的苹果”二例本质完全相同，或者可以说，前者是后者的数学模型，体现了建模并用数学模型解决实际应用的思路。

三、离散数学课程的实用性

对于一些抽象的概念，如果脱离实用性，则难以激发学生的学习兴趣；反之，如果使学生看到其实用价值，则对概念的领悟与记忆会更为深刻。

实例1：将抽象概念“关系闭包”具化为应用案例。

引入简单的编码实例：设字母表V={A，B，C，D，e，d，f}，并且给定规则A→Af，B→Dde，C→e，A→B，B→De，D→Bf，R为定义在V上的二元关系：xRx，满足从x出发使用一条规则推出一串字符，使其第一个字符恰为x。求解每个字母连续应用上述规则可能推出的头字符。

本例实质是求关系的传递闭包，且正是闭包这一抽象概念的实用案例。

实例2：代数系统中关于运算封闭的解释。

在表3所给出的运算中，运算*不是封闭的。

而在表4的代数系统中，运算“o”是封闭的。

这两个实例均来自生活中，通俗易懂，可使学生对认识和接受抽象概念变得容易。

四、离散数学与其他学科的关联

离散数学课程本身具有承上启下的作用，课程内容中有些引申自数学分析、线性代数等学科，有些可以应用于数据结构、数字电路、概率论、模糊数学等课程。以下列举一些启发性实例，帮助学生建立各学科之间的关联，并在学习中体会融会贯通。

实例1：关系闭包的概念与数学分析中开集的闭包对照，可见闭包的本质含义是一致的。

在数学分析中，例如开区间（a，b）的闭包A。其定义包含三层含义：（1）A包含开区间（a，b）；（2）A是闭区间；（3）A是同时满足（1）和（2）的“最小”集合，即若有集合B满足（1）和（2），则A?B，因此A=[a，b]。

在集合论中：例如关系R的自反闭包R′也包含三层含义：（1）R′包含關系R；（2）R′自反；（3）R′是同时满足（1）和（2）的“最小”关系，即若有集合R"满足（1）和（2），则R′?R″。

实例2：关系矩阵的复合运算对比线性代数中的矩阵乘法，二者完全类似。

普通矩阵的乘法运算：矩阵A=[a]与B=[b]的乘积C=A×B=[c] 其中c=（a·b）。

关系矩阵的复合运算：关系矩阵M=[r]与M=[s]的复合矩阵M=M·M=[w]，其中w=

（r∧s）。

实例3：集合论与模糊数学。模糊集将元素与集合的隶属关系由{0，1}扩展到闭区间[0，1]，用隶属度函数定义，因此可以看作集合论的推广。

实例4：集合论中的“容斥原理”与概率论中的“加法公式”同出一辙。

容斥原理：|A∪A∪…∪A|=

A-|A∩A|+…+（-1）|A∩A∩…∩A|

将容斥原理变形得到如下公式：=-+…+

（-1）

此公式可理解为概率论中的加法公式的雏形，并可写成概率论中的加法公式，如下：P{A∪A∪…

∪A}=P{A}-P{A∩A}+…+（-1）P{A∩A∩…∩A}

五、结语

在离散数学授课过程中，对上述四部分内容与观点应加以强调，并贯穿教学始终，同时要尽量通过实例阐释使学生在学习过程中对课程的内容有一些宏观地把握，培养其逻辑思维和发散思维，并获得应用体验，最大程度的激发出学生的学习热情，学好本门课程。

参考文献：

[1]杨炳儒，谢永红，刘宏岚，洪源，罗雄.离散数学[M].北京：高等教育出版社，2012.

[2]屈婉玲，王元元，傅彦，张桂芸.“离散数学”课程教学实施方案[J].中国大学教学，2011，（1）：39-41.

[3]王霞，顾勋梅，潘祝山.离散数学教学改革及课程建设研究[J].计算机教育，2011，（6）：8-10.

[4]王全，陈桦.“离散数学”课程教学改革研究与实践[J].计算机科学，2006，33（8）：36-38.

[5]常亮，徐周波，古天龙，董荣胜.离散数学教学中的计算思维培养[J].计算机教育，2011，（14）：90-94.