一．前言
《离散数学》是现代数学的一个重要分支，是计算机科学与技术专业的基础理论课，也是该专业的核心课程和主干课程。“离散数学”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。该课程一方面为后继课程如数据结构、编绎原理、操作系统、数据库原理、人工智能和形式语言与自动机等提供必要的理论基础；同时，更为重要的是培养学生的抽象思维能力和逻辑推理能力，为今后的学习和工作打好基础。无论从计算机学科发展的过去、现在和未来看，《离散数学》都是计算机科学与技术专业不可缺少的重要组成部分。这门课程有着其它课程不可替代的地位和作用，是一门承前启后的课程。
根据《离散数学》课程本身的理论性较强的特性，设置《离散数学实验》实践环节十分重要。通过实验实践内容的训练，突出逻辑性思维训练的特征, 目的是提高学生学习的兴趣及实际动手的能力。
为了帮助学生更好地学习本课程，理解和掌握所学基本概念和方法，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题.本指导书根据本课程要求编写这本指导书。以期为同学作实验提供帮助！ 二．目录
第一部分 实验内容
实验1： 真值表判断
实验2：集合运算及关系运算
实验3：求最短路径或平面图的判断（二选取一）
第二部分 实验指导
实验1： 真值表判断
实验2：集合运算及关系运算
实验3：求最短路径或平面图的判断（二选取一）
第三部分 实验报告
三．正文
第一部分 实验内容
实验1：真值表
1． 实验目的：通过试验，了解命题的有关概念，真值表技术，连接词的作用与意义 2． 实验类型：验证型实验 3． 实验学时：2学时 4． 实验原理及知识点
掌握命题公式及其类型的概念，熟悉逻辑连接词的运算规则，熟悉命题公式真值表的构成，并可用计算机实现
5． 实验环境（硬件环境、软件环境）
1、 试验环境visual C＋＋ 6.0 2、 操作系统 window 2000、xp
6． 实验内容及步骤
1、编写操作界面
使用MFC提供的DLG类，在面板上添加一个输入文本框作为输入公式的实例输入。添加两个按钮分别表示在程序面板上显示结果和利用输出文本文件显示并保存结果。
2、按照运算规则编写求真值表函数
在对应按钮的触发事件中添加对应的处理函数 3、测试与修改
7． 思考与练习
利用真值表技术和公式的演算方法，如何求得公式对应的主析取范式和主合取范式，如何判断两公式是否相等，是否为永真式、永假式、可满足式？
实验2：集合运算及关系运算
1．实验目的：通过试验，了解集合运算有关概念及计算技术，撑握合成关系运算条件与运算特点。
2．实验类型：验证型实验 3．实验学时：2学时 4．实验原理及知识点：
交运算：设A，B是两个集合，则A∩B={x｜(xA)并且(xB)}
? 并运算：设A，B是两个集合，则A∪B={x｜(xA)或(xB)} ? 差运算：设A，B是两个集合，则A?B={x｜(x
A)并且(xB)}
A)∧(y
B)}
? 笛卡儿集合：设A，B是两个集合，称集合A×B={
为集合A与B的笛卡儿积 ? 求子集或求幂集
设A有ｎ个元素，则ρ(A)有2n个元素。
证明：A的所有由ｋ个元素组成的子集个数为从ｎ个元素中取ｋ个元素的
组合数：
? 求关系合成运算:
设R是X到Y的关系，S是Y到Z的关系，则R?S称为R和S的复合关系，
定义为：
R?S= {
5．实验环境（硬件环境、软件环境）
1、 试验环境visual C＋＋ 6.0 2、 操作系统 window 2000、xp
6．实验内容及步骤
1、编写操作界面
使用MFC提供的DLG类，在面板上添加两个输入文本框作为输入集合A、B的实例输入。添加四个按钮分别表示求交集，求并集，求差集和求笛卡儿积。
2、按照运算规则编写运算函数
在对应按钮的触发事件中添加对应的处理函数。
3、编译程序，连调发现程序中存在的问题并修改
7、思考与练习
1、在掌握集合运算与关系合成的基础上，思考如何使用集合的运算来证明集合间的包含、相等和真包含的关系？
实验3：求最短路径或平面图的判断
1．实验目的：通过求最短路径与对平面图的判断，撑握路与图在计算中处理与表示，同时撑握求最短路径的方法，另理解对平面图有关原理。 2．实验类型：验证型实验 3．实验学时：2学时 4．实验原理及知识点： 平面图判断的知识点
1、设G是连通平面图，有v个结点，e条边，r个面，则 v-e+r=2 (欧拉公式)
2、设G是有v个结点、e条边的连通简单平面图，且v?3，则 e?3v-6
3、设G是v个结点、e条边的连通平面图，且G的各面的次数大于等于4，则
e?2v-4
4推论2给出了各面次数大于等于4的连通平面图应满足的必要条件，所以可用来判断某些图不是平面图
例如，应用推论1可知K3，3不是平面图 。因K3，3是连通平面图，每个面由四条边围成，v=6, 2v-4=8，而e=9，不满足推论给出的条件。
最短路径的算法：
设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：
1) 初始化。起源点设置为：① ds=0, ps为空;② 所有其他点: di=∞, pi=?;③ 标记起源点s，记k=s,其他所有点设为未标记的。
2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：
dj=min［dj, dk+lkj］
式中，lkj是从点k到j的直接连接距离。
3) 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i：
di=min［dj, 所有未标记的点j］
点i就被选为最短路径中的一点，并设为已标记的。
4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j，作为前一点,设置：
*
i=j
*
5) 标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2) 再继续。
5．实验环境（硬件环境、软件环境）
1、 试验环境visual C＋＋ 6.0 2、 操作系统 window 2000、xp
6．．实验内容及步骤
1、编写操作界面
2、按照求最短路径算法编写求短路径函数； 按照判断平面图的算法原理求平面图算法函数。
3、编译程序，连调发现程序中存在的问题并修改
第二部分 实验指导
具体写实验方法，实验步骤及补充的实验知识。
实验1 真值表判断实验指导
? 实验所属系列：离散数学课后实验 ? 实验对象：本科
? 相关课程及专业：离散数学，计算机专业 ?
实验目的
公式是由命题变元、逻辑联结词、括号组成的合法的符号串，而命题变元是一个抽象的概念，若不指定命题变元的真值，则公式没有真值可言。反之，若对所有的命题变元都指定一定的真值，则公式就变成了一个具有确切真值的命题。将所有的这些命题变元的可能取值一一列出形成一个表格的形式，这个表格称为该公式的真值表。利用真值表技术和公式的演算方法，能够求得一公式对应的主析取范式和主合取范式，还能够判断两公式是否相等，是否为永真式、永假式、可满足式。