实验2：集合运算及关系运算
一、实验目的：
通过试验，了解集合运算有关概念及计算技术，撑握合成关系运算条件与运算特点。
二、实验类型：验证型实验
三、实验学时：2学时
四、实验原理及知识点：
交运算：设A，B是两个集合，则A∩B={x｜(xA)并且(xB)} 并运算：设A，B是两个集合，则A∪B={x｜(xA)或(xB)} 差运算：设A，B是两个集合，则A?B={x｜(xA)并且(xB)} 笛卡儿集合：设A，B是两个集合，称集合A×B={
求子集或求幂集
设A有ｎ个元素，则ρ(A)有2n个元素。
证明：A的所有由ｋ个元素组成的子集个数为从ｎ个元素中取ｋ个元素的组合数： 求关系合成运算:
设R是X到Y的关系，S是Y到Z的关系，则R?S称为R和S的复合关系，定义为： R?S= {
五、实验环境（硬件环境、软件环境）
1、试验环境visual C＋＋ 6.0 2、 操作系统 window 2000、xp
六、实验内容及步骤
1、编写操作界面
使用MFC提供的DLG类，在面板上添加两个输入文本框作为输入集合A、B的实例输入。添加四个按钮分别表示求交集，求并集，求差集和求笛卡儿积。
2、按照运算规则编写运算函数
在对应按钮的触发事件中添加对应的处理函数。 3、编译程序，连调发现程序中存在的问题并修改
七、思考与练习
在掌握集合运算与关系合成的基础上，思考如何使用集合的运算来证明集合间的包含、相等和真包含的关系？
3
实验3：求最短路径或平面图的判断
一、实验目的：
通过求最短路径与对平面图的判断，撑握路与图在计算中处理与表示，同时撑握求最短路径的方法，另理解对平面图有关原理。
二、实验类型：验证型实验
三、实验学时：2学时
四、实验原理及知识点：
平面图判断的知识点
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*，作为前一点,设置：
4
i=j*
5) 标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2) 再继
续。
五、实验环境（硬件环境、软件环境）
1、 试验环境visual C＋＋ 6.0 2、 操作系统 window 2000、xp
六、实验内容及步骤
1、编写操作界面
2、按照求最短路径算法编写求短路径函数； 按照判断平面图的算法原理求平面图算法函数。 3、编译程序，连调发现程序中存在的问题并修改
5
第二部分 实验指导
6
实验1 真值表判断实验指导
一、实验目的
公式是由命题变元、逻辑联结词、括号组成的合法的符号串，而命题变元是一个抽象的概念，若不指定命题变元的真值，则公式没有真值可言。反之，若对所有的命题变元都指定一定的真值，则公式就变成了一个具有确切真值的命题。将所有的这些命题变元的可能取值一一列出形成一个表格的形式，这个表格称为该公式的真值表。利用真值表技术和公式的演算方法，能够求得一公式对应的主析取范式和主合取范式，还能够判断两公式是否相等，是否为永真式、永假式、可满足式。
二、实验内容与要求
设是命题变元P1、P2、P3、?、Pn是出现在公式G中的所有命题变元，指定P1、P2、P3、?、Pn一组真值，则这组真值称为G的一个解释（Explanation），常记为I。
因此，设G是一个公式，I是G的一个解释，显然，G在I下有真值。由于每一个公式可能存在着不止一种解释，这种解释的多少与公式中的命题变元的个数有关。对每一个命题变元都有“真”、“假”两种不同的解释，若有两个命题变元，按组合的方法，应有四种不同的解释。一般来说，若有n个命题变元，则应有2n个不同的解释。为了能直观地表示一个公式所有可能的解释与公式在此解释下的结果，可定义：
公式G在其所有可能的解释下所取真值的表，称为G的真值表（Truth）。
本实验要求大家利用C＋＋语言，实现任意输入公式的真值表计算。一般我们将公式中的命题变元放在真值表的左边，将公式的结果放在真值表的右边。有时为了清楚起见，也可将求公式的中间结果也依次放在真值表中；或者将求公式的中间结果放在公式的相应的每个联结词的下方。有时也可将具有相同变元个数的公式之真值结果依次放在同一个真值表中。显然，对任何一公式都有一真值表。
请注意以下约定：
输入公式要由（ ）确定优先级\\n\\n 同时为了方便键盘输入做如下规定： (1) 用 ! 代替 非 操作 (2) 用 && 代替 ∧ 操作 (3) 用 || 代替 ∨ 操作 (4) 用 <> 代替 <=> 操作 (5) 保持操作 -> 不变
要求依据上述运算规则，实现任意给定公式真值表的计算，并显示运算结果。
三、实验器材（设备、元器件）：
1、 试验环境visual C＋＋ 6.0 2、 操作系统 window 2000、xp
7