离散数学实验指导
2017年9月
目 录
实验一、真值表计算
一、实验目的
熟悉联结词合取、析取、蕴涵和等值的概念，编程求其真值。
二、实验项目性质
设计性
三、实验内容
1. 从键盘输入两个命题P和Q的真值，求它们的合取、析取、蕴涵和等值的真值。用C语言实现。
2. 求任意一个给定命题公式的真值表，并根据真值表求主范式。
四、实验要求
1. 独立完成实验内容；
2. 实验完成后需提交实验报告。
3. 实验报告要有详细的算法步骤、实验结果讨论与分析、真实的个体心得体会。
实验二、集合运算
一、实验目的
1. 通过编程实现求给定集合A和B的并集C（C=A∪B）的运算。
2. 通过编程实现求给定集合A和B的交集C（C=A∩B）的运算。
3. 通过编程实现求给定集合A和B的差集C（C=A-B）的运算。
二、实验项目性质
设计性
三、实验内容
1. 已知所给集合A和B，求A与B 的并集C（C=A∪B）。
2. 已知所给集合A和B，求A与B 的交集C（C=A∩B）
3. 已知所给集合A和B，求A与B的差集C（C=A-B）。
四、实验原理
1、因为并集的定义为：C={x|x∈A∨x∈B}，所以，只要将集合A与B合在一起就得到了并集C。但是，在一个集合中，同样的元素没必要出现两次或两次以上，所以，在将集合A送入并集C后，应将集合B中与A中相同的元素删除，再将集合B送入并集C之中。
2、根据交集的定义：C={x|x∈A∧x∈B}，我们将集合A的各个元素与集合B的元素进行比较，若在集合B中存在某个元素并和集合A中一元素相等，则将该元素送入交集C之中。
3、差集C的定义：差集C={x|x∈A∧x
B}，即对于集合A中的元素ai，若不存在bj∈B（j=1，2，…..，m），使得ai=bj，则ai ∈差集C。
五、实验仪器设备或软件环境及工具
运行Windows 或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。
六、实验步骤及注意事项
1、并集
（1） 集合B的元素个数送M，集合A的元素个数送N。
（2） AC。
（3） 1i。
（4） 若i> M,则结束。
（5） 否则，对于j=1，2，…….，n，判断：bi=aj，若相等，则转（7）。
（6） 否则，biC。
（7） i+1i，转（4）。
2、交集
（1） 将集合A的元素送N。
（2） 1i
（3） 若i>N,则结束。
（4） 否则，将ai与集合B中的每个元素进行比较，若ai与集合B中所有元素均不相同，则转（6）。
（5） 否则，aiC。
（6） i+1i，转（3）。
3、差集
（1） 将集合A的元素个数送N。
（2） 1i。
（3） i>N，则结束。
（4） 否则，将ai与集合B中的每个元素相比较，若ai 与集合B中的某个元素相同，则转（6）。
（5） 否则，aiC。
（6） i+1i，转（3）。
六、实验要求
1. 复习集合运算中交集、并集、差的定义。
2. 独立完成实验，所编程序能够通过编译，并能够实现求两个给定集合的并、交、差集。
3. 实验完成后需提交实验报告。
4. 实验报告要有详细的算法步骤、实验结果讨论与分析、真实的个体心得体会。
实验三、关系的性质实验
一、实验目的
1、 通过算法设计并编程实现对给定集合上的关系是否为自反关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法。
2、 通过算法设计并编程实现对给定集合上的关系是否为对称关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法。
3、 通过算法设计并编程实现对给定集合上的关系是否为传递关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法。
4、 通过算法设计并编程实现对给定集合上的关系是否为自反的、对称的和传递关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断等价关系的方法。
二、实验项目性质
设计性
三、实验内容
1、 已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为自反关系。
2、 已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为对称关系。
3、 已知关系R由关系矩阵M给出，要求判断由M表示的这个关系是否为传递关系。
4、 给定R的关系矩阵，据此判断所给关系R是否为等价关系。
四、实验原理
1、从给定的关系矩阵来断判关系R是否为自反是很容易的。若M（R的关系矩阵）的主对角线元素均为1，则R是自反关系；若M（R的关系矩阵）的主对角线元素均为0，则R是反自反关系；若M（R的关系矩阵）的主对角线元素既有1又有0，则R既不是自反关系也不是反自反关系。本算法可以作为判等价关系算法的子程序给出。
2、从给定的关系矩阵来判断关系R是否为对称是很容易的。若M（R的关系矩阵）为对称矩阵，则R是对称关系；若M为反对称矩阵，则R是反对称关系。因为R为对称的是等价关系的必要条件，所以，本算法可以作为判等价关系算法的子程序给出。
3、一个关系R的可传递性定义告诉我们，若关系R是可传递的，则必有：mik=1∧mkj=1 mij=1。这个式子也可改写成为： mij =0 mik =0∨mkj=0。我们可以根据后一个公式来完成判断可传递性这一功能的。可传递性也是等价关系的必要条件，所以，本算法也可以作为判等价关系算法的子程序给出。
4、设R为非空集合A上的关系. 如果R是自反的、对称的和传递的, 则称R为A上的等价关系。
五、实验仪器设备或软件环境及工具
运行Windows 或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。
六、实验步骤及注意事项
1、自反性判定
（1） 输入关系矩阵M（M为n阶方阵）。
（2） 判断自反性，对于i=1，2，….，n；若存在mii=0，则R不是自反的；若存在mii=1，则R是自反的；否则R既不是自反关系也不是反自反关系。
（3） 输出判断结果。
2、对称性判定
（1） 输入关系矩阵M（M为n阶方阵）；
（2） 判断对称性，对于i=2，3，….，n；j=1，2,……，i-1，若存在mij=mji，则R是对称的；
（3） 判断反对称性；
（4） 判断既是对称的又是反对称的；
（5） 判断既不是对称的又不是反对称的；
（6） 输出判断结果。
七、实验要求
1. 复习关系的性质。
2. 独立完成实验，所编程序能够通过编译，并能够实现对给定集合上的关系性质的判定。
3. 实验完成后需提交实验报告。
4. 实验报告要有详细的算法步骤、实验结果讨论与分析、真实的个体心得体会。
实验四、关系的闭包运算
一、实验目的
通过算法设计并编程实现求给定关系的各种闭包运算，加深学生对闭包运算的概念的理解。
二、实验项目性质
设计性
三、实验内容
给定关系R，求R的自反闭包及R的对称闭包。
四、实验原理
若关系R的关系矩阵为M，而自反闭包为A（即r（R）=A），对称闭包为B（即S（R）=B），则A=M∨I B=M∨MT 其中，I为恒等矩阵，MT为M的转置矩阵。
五、实验仪器设备或软件环境及工具
运行Windows 或Linux操作系统的PC机，具有gcc(Linux)、Turboc、Vc(Windows)等C语言的编译环境。
六、实验要求
1. 复习关系闭包的定义。
2. 独立完成实验，所编程序能够通过编译，并能求出给定关系的闭包。
3. 实验完成后需提交实验报告。
4. 实验报告要有详细的算法步骤、实验结果讨论与分析、真实的个体心得体会。
七、思考题
设计出求关系R的传递闭包的Warshall
