离散数学实验报告
离散数学实验报告（实验ABC）
|
<
专业班级
学生姓名
{
学生学号
指导老师
完成时间
目录
第一章实验概述 (2)
实验目的 (2)
实验内容 (2)
实验环境 (2)
第二章实验原理和实现过程 (3)
实验原理 (3)
建立图的邻接矩阵，判断图是否连通 (3)
计算任意两个结点间的距离 (3)
对不连通的图输出其各个连通支 (4)
实验过程（算法描述） (4)
程序整体思路 (4)
具体算法流程 (4)
第三章实验数据及结果分析 (6)
建立图的邻接矩阵并判断图是否连通的功能测试及结果分析 (6)
输入无向图的边 (6)
建立图的连接矩阵 (7)
其他功能的功能测试和结果分析 (8)
计算节点间的距离 (8)
判断图的连通性 (8)
输出图的连通支 (9)
退出系统 (9)
第四章实验收获和心得体会 (10)
实验收获 (10)
心得体会 (11)
第五章实验源程序清单 (12)
程序代码 (12)
第一章实验概述
实验目的
理解图论的基本概念，图的矩阵表示，图的连通性，图的遍历，以及求图的连通支方法。
通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算，培养逻辑思维；通过实验提高学生编写实验报告、总结实验结果的能力，提高理论联系实际的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。
实验内容
以偶对的形式输入一个无向简单图的边，建立该图的邻接矩阵，判断图是否连通（A），并计算任意两个结点间的距离（B），对不连通的图输出其各个连通支（C）。
注意：题目类型分为A，B，C三类，其中A为基本题，完成A类题目可达到设计的基本要求，其他均为加分题，并按字母顺序分数增加越高。
基本要求如下：程序需具有基本的容错控制，在输入错误时有处理手段；程序界面友好，需要输入的地方有输入说明，说明输入的内容和格式要求等；实验原理和实现过程应该详细分析问题，给出解决思路，描述算法思想，不能用源程序代替算法；测试数据应全面，包括非法输入的处理结果等都应包含在内。
实验环境
C或C＋＋语言编程环境实现。
第二章实验原理和实现过程
实验原理
建立图的邻接矩阵，判断图是否连通
根据图的矩阵表示法建立邻接矩阵A，并利用矩阵的乘法和加法求出可达矩阵，从而判断图的连通性。
连通图的定义：在一个无向图G 中，若从顶点vi到顶点vj有路径相连(当然从vj到vi也一定有路径)，则称vi和vj是连通的。如果G 是有向图，那么连接vi和vj的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。
判断连通图的实现：在图中，从任意点出发在剩余的点中，找到所有相邻点循环，直到没有点可以加入为止，如果有剩余的点就是不连通的，否则就是连通的。或者也可用WallShell算法，由图的邻接矩阵判断图是否连通。
计算任意两个结点间的距离
图中两点i，j间的距离通过检验A l中使得a ij为1的最小的l值求出。
路径P中所含边的条数称为路径P的长度。在图G
设图的邻接矩阵是A，则所对应的aij的值表示，点Vi到点Vj距离为n的路径有aij条。
若aij(1)，aij(2)，…，aij(n-1)，中至少有一个不为0，则可断定Vi与Vj可达，使aij(l)≠0的最小的l即为d(Vi，Vj)。
问题求解原理为：
（1）先构造初始邻接矩阵A=Vij，Vij为顶点Vi到顶点Vj的权。如果Vi和Vj之间不存在弧段或者是负向回路或者是i=j，则令Vij其值为∞。
（2）再构造初始中间顶点矩阵。
（3）然后开始迭代计算（迭代的次数等于顶点的个数1）
（4）最后查找Vi到Vj的最短路径。
计算节点Vi与Vj之间的距离的方法为：
利用邻接矩阵相互间相乘后得到的矩阵来判断节点间的距离。如果
c2[s][i][j]==0，则这两个节点的距离为无穷大。如果c2[s-2][i][j]==0,c2[s-1][i][j]==1时，则这两点间的距离为s。
对不连通的图输出其各个连通支
图的连通支的求法则可采用图的遍历算法，图的遍历有深度优先和广度优先两种方法，其中深度优先算法又分为递归和非递归两种。
在无向图中，如果任何两点可达，则称图G是连通的，如果G的子图G’是连通的，没有包含G’的更大的子图G’’是连通的，则称G’是G的连通支。
当有判断出关系不是连通的之后，将需要求出分支模块
实现方法如下：先定义一个二维数组用来存放相应的分块，先选定一个点，并将它放在数组中，然后判断，如果后面的和他是联通的便将它也放在同一个数组中，否则将其存入其他的数组中，后面以此类推，在输出相应的数组，便可判断出连通分支。
实验过程（算法描述）
程序整体思路
本程序完成了实验所要求的全部功能，其基本思路是——“运用模块化的思想，将实现“求连通支”、“输入结点关系”、“输出邻接矩阵”、“显示两结点间的距离”、“求可达矩阵”和“图的遍历”的子函数分开编写，然后将它们以子函数的形式添加到主函数main的代码后面，在要使用相应的子函数时，进行子函数调用就可以实现相应的功能了。”
本程序的一大特色就是开发者灵活使用了C语言中的数组概念来进行开发，用数组来模拟矩阵的运算，通过相应的算法实现了全部的功能。
具体算法流程
在main(){系统界面显示；用do…while循环语句和switch语句实现功能
1,2,3……的选择，并调用相关的子程序；用start、goto start实现控制流的转移；} liantongzhi(){求连通支，此子函数通过一个for循环控制遍历每个结点，并调用函数DFS（）求每个结点的连通支；}
DFS（int a）{通过实参与形参，将结点数据代入函数；定义顺序栈变量；通过for循环初始化；为a置已访问标志，已经访问了的元素为1；定义顺序栈的第一个元素；通过while循环实现结点遍历，栈不为空时执行循环；栈顶元素赋值；通过for循环寻找v的下个未访问的邻接点；通过if条件句，若x,i是边和节点i未被访问过，处理结点的访问，并进行访问标志，进栈等操作；通过if条件句，若v已访问到的出点，则将其退栈；}
shuru(){输入结点关系；通过for循环先将矩阵所有元素赋值0；再通过另一for循环，根据输入结点的关系，将矩阵中相应的元素赋值，有关系则为1；} linjiejuzhen(){输出邻接矩阵；通过for循环，依次按格式输出邻接矩阵的元素；} julijuzhen(){根据A的n次方矩阵及其中元素，判断并显示两结点间的距离；调用子函数linjiejuzhen()，以确定并显示距离为1的两结点；通过for循环显示距离为1的结点对；再通过一系列的for循环，计算A的n次方矩阵并显示结果，根据其中的元素，判断并显示结点间的距离；详细算法请见附录相关部分的注释；}
kedajuzhen(){求可达矩阵；通过一系列for循环，根据公式，计算可达矩阵；通过for循环，将矩阵中不为0的一切值赋为1以生成可达矩阵并显示；通过for 循环和if条件句的组合，根据可达矩阵的元素特点，判断图的连通性，若可达矩阵矩阵中有0，则跳出循环，显示不可连接；根据判断结果显示内容，不可连通或可连通；}
第三章实验数据及结果分析
建立图的邻接矩阵并判断图是否连通的功能测试及结果分析简单无向图的输入界面友好，有清楚的操作说明，方便用户进行使用。
这就是集合的输入界面。
输入无向图的边
当“6,5”时，表示输入的是六个节点五条边的树。
程序会在屏幕上显示输入节点间关系的界面，输入的关系为“1,2；2,3；3,4；4,5；5,6”
建立图的连接矩阵
程序返回主界面后，选择“2”，程序会显示建立的连接矩阵。
其他功能的功能测试和结果分析
计算节点间的距离
当选择“3”时，程序便会输出各节点间的距离。
判断图的连通性
当选择“4”时，程序会根据可达矩阵判断图的连通性。
输出图的连通支
当选择“5”时，程序会输出个连通支。
退出系统
当选择“6”时，程序会退出系统。
第四章实验收获和心得体会
实验收获
这次离散数学实验是基于图论方面知识，以图的各种矩阵为基础，来研究图的一些性质、特点。
我独立完成了本次实验设计，实现了A、B、C三个功能，满足了实验的基本要求，心得如下。
通过这次实验，我学会了用C语言根据图的矩阵表示法建立邻接矩阵A，并利用矩阵的乘法和加法求出可达矩阵，从而判断图的连通性。巩固了课堂所学的图论方面的有关知识，并在实践中学到：图中两点i，j间的距离可以通过检验
A l中使得a ij为1的最小的l值求出；图的连通支的求法可采用图的遍历算法，图的遍历有深度优先和广度优先两种方法，其中深度优先算法又分为递归和非递归两种。我选择的算法是较为简单、易于实现的深度优先算法最简单，查阅了相关资料，掌握了此算法的核心，最后独立完成了本次实验设计。
这次离散数学实验，从拿到题目到完成整个编程，从理论到实践的日子里，我学到很多东西，不仅可以巩固了以前所学过的知识，而且通过查阅相关资料，学到了很多在书本上所没有学到过的知识。在这段时间里，我对于离散数学中的“逻辑”有了进一步的理解，对C语言的理解也更进了一步，并提高了编写实验报告、总结实验结果的能力，提高了理论联系实际的能力，初步具备程序设计的思想，能够独立完成简单的算法设计和分析。
感受最深的是，大量的上机实践是成为“编程高手”的必由之路，“质变”需要有“量”的积累。
完成程序的编写，决不意味着万事大吉。曾经自己认为万无一失的程序，实际上机运行时可能不断出现麻烦，如编译程序检测出一大堆错误。有时程序本身不存在语法错误，也能够顺利运行，但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误，只能靠自己的上机经验分析判断错误所在。有时候一个小小错误会消耗我好的时间去找，而高手一眼就看出错误所在，这就是熟练程度的不同，量变到质变的不同。
心得体会
这次真的使我意识到了很多原来没有意识到的问题，有时候一些很小的问题，也会令人很是头痛。
在刚开始编写程序的时候，为了实现最基本的输入和输出功能，我却花了大量的时间在那上面。原因在后来查阅的很多资料后才知道的，像scanf函数之类的小函数，其实是还有很多需要注意的地方的。
之后，在编写数组和指针的过程中，花了很大的一部分时间去研发算法，开发程序，在理论上反复证明没有问题之后，再在计算机上进行操作，编写代码，进行调试，反复了很久，才慢慢的实现了全部的功能，真的是来之不易。
在实验的过程中我们要培养自己的独立分析问题，和解决问题的能力。培养这种能力的前题是你对每次实验的态度。如果你在实验这方面很随便，抱着等老师教你怎么做，拿同学的报告去抄，尽管你的成绩会很高，但对将来工作是不利的。在写实验报告，对于思考题，有很多不懂，于是去问老师，老师的启发了我，其实答案早就摆在报告中的公式，电路图中，自己要学会思考。
最后，通过这次的实验我不但对理论知识有了更加深的理解，对于实际的操作和也有了质的飞跃。经过这次的实验，我们整体对各个方面都得到了不少的提高，希望以后学校和系里能够开设更多类似的实验，能够让我们得到更好的锻炼。
第五章实验源程序清单程序代码
#include <>/*头文件*/
#include<>
#include <>
#define MAX 100/*宏定义*/
typedef struct { int elem[MAX];
int top;
}SqStack;/*定义栈的结构体,顺序栈的类型标识符*/
void shuru();/*各子函数声明*/
void linjiejuzhen();
void julijuzhen();
void kedajuzhen();
void liantongzhi();
void DFS(int a);
int A[9][9],B[9][9],C[9][9],D[9][9];
int i,j,k,t,v,e;
int main()
{
int a1;
start:
do
{
printf("\n");
printf("********************************************************************* **********\n");
printf("\n");
printf("\t\t\t\t系统主菜单\n");
printf("\n\t\t1.输入无向图的边\n\t\t2.建立图的邻接矩阵\n\t\t3.计算节点间的距离\n");
printf("\t\t4.由可达矩阵判断图的连通性\n\t\t5.输出各个连通支（深度优先DFS法）\n\t\t6.退出系统\n");
printf("\n");
printf("********************************************************************* ***********\n");
printf("\n");
printf("\n\t\t\t\t请输入功能选项:");
fflush(stdin);/*清空输入缓冲区，通常是为了确保不影响后面的数据读取*/
scanf("%d",&a1);
switch(a1)/*switch语句实现选择功能*/
{
case 1:system("cls");shuru();break;/*输入节点关系，计算邻接矩阵*/
case 2:system("cls");fflush(stdin);linjiejuzhen();break;/*输出邻接矩阵*/
case 3:system("cls");fflush(stdin);julijuzhen();break;/*求距离矩阵*/
case 4:system("cls");fflush(stdin);kedajuzhen();break;/*求可达矩阵*/
case 5:system("cls");fflush(stdin);liantongzhi();break;/*求连通支*/
case 6:system("exit");exit(0);/*结束整个程序的运行*/
default:system("cls");
goto start;/*控制流转移到start处*/
}
}while(1);
}
void liantongzhi()/*求连通支，此子函数控制遍历每个结点*/
{
for(i=1;i<=v;i++)
{
printf("%d",i);
DFS(i);/*调用子函数求连通支*/
printf("\n");
}
}
void DFS(int a)/*由深度优先DFS法求出并显示各个连通支*/
{
int i,x;
int top=0;
int visited[MAX];
SqStack s;/*定义s为顺序栈变量*/
for (i=0;i<100;i++)
visited[i]=0;/*初始化为0*/
visited[a-1]=1;/*为a置已访问标志，已经访问了的元素为1*/
top=top+1;
[top]=a-1;/*顺序栈的第一个元素*/
while(top!=0)/*栈不为空时执行循环*/
{
x=[top];/*将栈顶元素付给x*/
for(i=0;i if(D[x][i]!=0 &&(!visited[i]))/*若x,i是边和节点i未被访问过*/ { printf("->%d",i+1); visited[i]=1;/*为i置已访问标准*/ top=top+1; [top]=i;/*i进栈*/ break; } if(i==v)/*若v已访问到的出点，则将其退栈*/ top--; } } void shuru()/*输入结点关系*/ { printf("********************************************************************* **********\n"); printf("\n"); printf("\t\t请输入结点数和边数（形式如6,5）：\n"); scanf("%d,%d",&v,&e);/*输入结点和边数*/ for(i=0;i { for(j=0;j { A[i][j]=0; C[i][j]=0; B[i][j]=0; D[i][j]=0; } } printf("\n"); printf("********************************************************************* **********\n"); printf("\t\t请输入结点间的关系（形式如：1,2）：\n"); printf("\n"); for(k=0;k { scanf("%d,%d",&i,&j); A[i-1][j-1]=1;/*根据输入结点的关系，将矩阵中相应的元素赋值*/ A[j-1][i-1]=1; B[i-1][j-1]=1; B[j-1][i-1]=1; D[i-1][j-1]=1; D[j-1][i-1]=1; } system("cls"); } void linjiejuzhen()/*输出邻接矩阵*/ { printf("邻接矩阵A为：\n"); for(i=0;i { for(j=0;j { printf("\t%5d",A[i][j]);/*显示邻接矩阵*/ } printf("\n"); } printf("\n"); } void julijuzhen()/*根据A的n次方矩阵及其中元素，判断并显示两结点间的距离*/ { linjiejuzhen();/*调用子函数，以确定并显示距离为1的两结点*/ for(i=1;i<=v;i++) { for(j=1;j<=v;j++) { if(A[i-1][j-1]==1) printf("结点%d与结点%d的距离为：%d\n",i,j,1); } } for(k=2;k<=v-1;k++)/*计算并显示距离大于1的两节点*/ { printf("\n\n"); printf("距离为%d的矩阵(即A%d)为：\n",k,k); { for(i=0;i for(j=0;j { for(t=0;t C[i][j]=C[i][j]+B[i][t]*A[t][j];/*计算矩阵中的元素*/ } for(i=0;i for(j=0;j { B[i][j]=C[i][j];/*将计算出的结果赋予B矩阵*/ C[i][j]=0; } } for(i=0;i 第一章命题逻辑的基本概念 一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）你去图书馆吗？ （7）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子?显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则3≥2。 （3）只有2<1，才有3≥2。 （4）除非2<1，才有3≥2。 （5）除非2<1，否则3≥2。 （6）2<1仅当3<2。 三、将下列命题符号化 (1)小丽只能从筐里拿一个苹果或一个梨。 (2)王栋生于1992年或1993年。 - 1 - 四、设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。（1）p∨(q∧r) （2）（p?r）∧(﹁q∨s) （3）（?p∧?q∧r）?(p∧q∧﹁r) (4)（?r∧s）→(p∧?q) 五．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 六、用真值表判断下列公式的类型： (1) p∧(p→q)∧(p→?q) (2) (p∧r) ?(?p∧?q) (2)((p→q) ∧(q→r)) →(p→r) - 2 - 第二章命题逻辑等值演算 一、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 二、用等值演算法证明下面等值式 (1)(p→q)∧(p→r)?(p→(q∧r)) (2)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) - 3 - 离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作， 《离散数学》实验报告专业网络工程 班级 姓名 学号 授课教师 二 O 一六年十二月 目录 实验一联结词的运算 实验二根据矩阵的乘法求复合关系 实验三利用warshall算法求关系的传递闭包实验四图的可达矩阵实现 实验一联结词的运算 一.实验目的 通过上机实验操作,将命题连接词运算融入到C语言的程序编写中,一方面加强对命题连接词运算的理解,另一方面通过编程实现命题连接词运算,帮助学生复习与锻炼C语言知识,将理论知识与实际操作结合,让学生更加容易理解与记忆命题连接词运算。 二.实验原理 (1) 非运算, 符号:? ,当P=T时 ,?P为F, 当P=F时 ,?P为T 。 (2) 合取, 符号: ∧ , 当且仅当P与Q的真值同为真,命题P∧Q的真值才为真;否则,P∧Q的真值为假。 (3) 析取, 符号: ∨ , 当且仅当P与Q的真值同为假,命题P∨Q的真值才为假;否则,P∨Q的真值为真。 (4) 异或, 符号: ▽ , 当且仅当P与Q的真值不同时,命题P▽Q的真值才为真;否则,P▽Q的真值为真。 (5) 蕴涵, 符号: →, 当且仅当P为T,Q为F时,命题P→Q的真值才为假;否则,P→Q 的真值为真。 (6) 等价, 符号: ? , 当且仅当P,Q的真值不同时,命题P?Q的真值才为假;否 则,P→Q的真值为真。 三.实验内容 编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。四．算法程序 #include 一、请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。（10分）解：A={1,2} R={（1,1），（2,2）} 二、请给出一个集合A，并给出A上既不具有对称性，又不具有反对称性的关系。（10分）集合A={1,2,3} A上关系{<1,2>,<2,1>,<1,3>}，既不具有对称性，又不具有反对称性 三、设A={1，2}，请给出A上的所有关系。（10分） 答：A上的所有关系: 空关系，{<1,1>,<1,2>,<2,1>,<2,2>} {<1,1>} {<1,2>} {<2,1>} {<2,2>} {<1,1>,<1,2>} {<1,1>,<2,1>} {<1,1>,<2,2>} {<1,2>,<2,1>} {<1,2>,<2,2>} {<2,1>,<2,2>} {<1,1>,<1,2>,<2,1>} {<1,1>,<1,2>,<2,2>} {<1,2>,<2,1>,<2,2>} {<1,1>,<2,1>,<2,2>} 四、设A={1，2，3}，问A 上一共有多少个不同的关系。（10分） 设A={1，2，3}，A 上一共有2^(3^2)=2^9=512个不同的关系。 五、证明： 命题公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。（10分） 证明：设公式G 的合取范式为：G ’=G1∧G2∧…∧Gn 若公式G 恒真，则G ’恒真，即子句Gi ；i=1,2,…n 恒真 为其充要条件。 Gi 恒真则其必然有一个原子和它的否定同时出现在Gi 中，也就是说无论一个解释I 使这个原子为1或0 ，Gi 都取1值。 若不然，假设Gi 恒真，但每个原子和其否定都不同时出现在Gi 中。则可以给定一个解释I ，使带否定号的原子为1，不带否定号的原子为0，那么Gi 在解释I 下的取值为0。这与Gi 恒真矛盾。 因此，公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。 六、若G=(P ，L)是有限图，设P(G)，L(G)的元数分别为m ，n 。证明：n ≤2m C ，其中2m C 表 示m 中取2的组合数。（10分） 证明：如果G=(P,L)为完全图，即对于任意的两点u 、v （u ≠v ）,都有一条边uv ，则此时对于元数为m 的P(G)，L(G)的元数取值最大为C m 2。因此，若G=(P,L)为一有限图，设P(G)的元数为m ，则有L(G) 离散数学实验报告（实验ABC） 专业班级 学生姓名 学生学号 指导老师 完成时间 目录 第一章实验概述..................................... 错误!未定义书签。 实验目的....................................... 错误!未定义书签。 实验内容....................................... 错误!未定义书签。 实验环境....................................... 错误!未定义书签。第二章实验原理和实现过程........................... 错误!未定义书签。 实验原理....................................... 错误!未定义书签。 建立图的邻接矩阵，判断图是否连通 ............ 错误!未定义书签。 计算任意两个结点间的距离 ................... 错误!未定义书签。 对不连通的图输出其各个连通支 ................ 错误!未定义书签。 实验过程（算法描述）........................... 错误!未定义书签。 程序整体思路 ............................... 错误!未定义书签。 具体算法流程 ................................ 错误!未定义书签。第三章实验数据及结果分析........................... 错误!未定义书签。 建立图的邻接矩阵并判断图是否连通的功能测试及结果分析错误!未定义书签。 输入无向图的边 .............................. 错误!未定义书签。 建立图的连接矩阵 ............................ 错误!未定义书签。 其他功能的功能测试和结果分析................... 错误!未定义书签。 计算节点间的距离 ............................ 错误!未定义书签。 判断图的连通性 .............................. 错误!未定义书签。 输出图的连通支 .............................. 错误!未定义书签。 退出系统 .................................... 错误!未定义书签。第四章实验收获和心得体会........................... 错误!未定义书签。 离散数学作业布置 第1次作业（P15） 1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0 （2）（p?r）∧(﹁q∨s)=（0?1）∧(1∨1)=0∧1 =0 （3）（﹁p∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（r∧s）→(p∧q)=（0∧1）→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2 也是无理数。另外只有6能被2整除，6才能被4整除。” 解：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 1.19 用真值表判断下列公式的类型： （4）(p→q) →(﹁q→﹁p) （5）(p∧r) ? (﹁p∧﹁q) （6）((p→q) ∧(q→r)) →(p→r) 解：（4） p q p→q q p q→p (p→q)→( q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111 命题逻辑的基本概念 一、单项选择题 1．下列语句中不是命题的有（ ）. A 9+5≤12 B. 1+3=5 C. 我用的电脑CPU 主频是1G 吗D.我要努力学习。 2. 下列语句是真命题为( )． A. 1+2=5当且仅当2是偶数 B. 如果1+2=3，则2是奇数 C. 如果1+2=5，则2是奇数 D. 你上网了吗 3. 设命题公式)(r q p ∧→?,则使公式取真值为1的p ，q ，r 赋值分别是 ( ) 0,0,1)D (0 ,1,0)C (1 ,0,0)B (0 ,0,0)A ( 4. 命题公式q q p →∨ )(为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 设p:我将去市里,q ：我有时间． 命题“我将去市里，仅当我有时间时”符号化为为( ) q p q p q p p q ?∨??→→)D ()C ()B ()A (6．设P ：我听课,Q ：我看小说. “我不能一边听课，一边看小说”的符号为（ ） A. Q P ?→ ； B. Q P →?； C. P Q ?∧? ； D. )(Q P ∧? 二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则32。 （3）只有2<1，才有32。 （4）除非2<1，才有32。 （5）除非2<1，否则32。 《离散数学》 课程设计 学院计算机学院 学生姓名 学号 指导教师 评阅意见 提交日期 2011 年 11 月 25 日 引言 《离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。 实验一、编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性） 一、前言引语：二元关系是离散数学中重要的内容。因为事物之间总是可以 根据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之间存在的关系。 二、数学原理：自反、对称、传递关系 设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合R 就是A×B的一个合于R={(x,y)∈A×B|xRy}的子集合 设R是集合A上的二元关系： 自反关系：对任意的x∈A,都满足 离散数学作业 软件0943 张凌晨38 李成16 1.设S={1,2,3,4}，定义S上的二元运算*如下： x*y=(xy) mod 5任意x,y属于S 求运算*的运算表. 解(xy) mod 5表示xy除以5的余数，所以运算表如下： 2.设*为Z+上的二元运算，任意x,y属于Z+， x*y=min(x,y),即x和y之中的较小数. (1)求4*6,7*3. (2)*在Z+上是否满足交换律、结合律和幂等律？ (3)求*运算的单位元、零元及Z+中所有可逆元素的逆元. 解 (1)由题得：4*6=min(4,6)=4； 7*3=min(7,3)=3. (2)由题分析知： *运算是取x和y之中的较小数，即x和y调换位置不影响结果，所以*在Z+上满足交换律. *运算满足结合律，因为任意x,y属于Z+，有 (x*y)*z=min(x,y)*z=min(min(x,y),z) x*(y*z)=x*min(y,z)=min(x,min(y,z)) 无论x,y,z三数中哪个较小，*运算的最终结果都是较小的那个，所以满足结合律. *运算满足幂等律，因为在Z+上任意 x*x=min(x,x)=x (3)在Z+中最小的数字是1 任意x属于Z+，有 x*1=1=1*x 所以1是*运算的零元，*运算没有单位元，也没有可逆元素的逆元。 3．令S={a,b},S 上有四个二元运算：*，&,@和#，分别由下表确定. (1)这四个运算中哪些运算满足交换律、结合律、幂等律？ (2)求每个运算的单位元、零元及所有可逆元素的逆元. 解 （1）*，&和@满足交换律；*，@和#满足结合律；#满足幂等律。 （2）*运算没有单位元和可逆元素，a 是零元；&运算的单位元为a ,没有零元,每个元素都是自己的逆元；@运算和#运算没有单位元, 零元和可逆元素. 离散数学作业答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数 理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题 目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识 点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地 完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答 过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在03任务界 面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)- A B P(B )={{3},{1,3},{2,3},{1,2,3}}，A? B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>} ． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝{<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={ 《离散数学》实验报告 专业网络工程 班级 姓名 学号 授课教师 二 O 一六年十二月 目录 实验一联结词的运算 实验二根据矩阵的乘法求复合关系 实验三利用warshall算法求关系的传递闭包实验四图的可达矩阵实现 实验一联结词的运算 一．实验目的 通过上机实验操作，将命题连接词运算融入到C语言的程序编写中，一方面加强对命题连接词运算的理解，另一方面通过编程实现命题连接词运算，帮助学生复习和锻炼C语言知识，将理论知识与实际操作结合，让学生更加容易理解和记忆命题连接词运算。二．实验原理 (1) 非运算, 符号: ,当P=T时，P为F, 当P=F时，P为T 。 (2) 合取, 符号: ∧ , 当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。 (3) 析取, 符号: ∨ , 当且仅当P和Q的真值同为假，命题P∨Q的真值才为假；否则，P∨Q的真值为真。 (4) 异或, 符号: ▽ , 当且仅当P和Q的真值不同时，命题P▽Q的真值才为真；否则，P▽Q的真值为真。 (5) 蕴涵, 符号: →, 当且仅当P为T,Q为F时，命题P→Q的真值才为假；否则，P→Q 的真值为真。 (6) 等价, 符号: ?, 当且仅当P,Q的真值不同时，命题P?Q的真值才为假；否则，P→Q的真值为真。 三．实验内容 编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。四．算法程序 #include 第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试 3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章 大连民族学院 计算机科学与工程学院实验报告 实验题目：判断关系的性质 课程名称：离散数学 实验类型：□演示性□验证性□操作性□设计性□综合性 专业：班级：学生姓名：学号： 实验日期：年月日实验地点： 实验学时：实验成绩： 指导教师签字：年月日 实验报告正文部分（具体要求详见实验报告格式要求） 实验报告格式 [实验题目] 判断关系的性质 [实验目的] 使学生掌握利用计算机语言实现判断关系性质的基本方法。[实验环境] Microsoft Visual C++6.0 [实验原理] 实验内容与要求：对给定表示有穷集上关系的矩阵，确定这个关系是否是自反的或反自反的；对称的或反对称的；是否传递的。 通过二元关系与关系矩阵的联系，可以引入N维数组，以数组的运算来实现二元关系的判断。 图示： 程序源代码： #include scanf("%d",&M[i][j]); for(i=0;i 华南理工大学网络教育学院 2014–2015学年度第一学期 《离散数学》作业 （解答必须手写体上传，否则酌情扣分） 1．设命题公式为?Q∧（P→Q）→?P。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （3）判断该命题公式的类型。 解：（1）真值表如下： P Q ?Q P →Q ?Q∧（P→Q）?P ?Q∧（P→Q）→?P 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 （2）?Q∧（P→Q）→?P??(?Q∧(?P∨ Q)) ∨? P ?( Q∨? (?P∨ Q)) ∨? P ?? ( ?P∨ Q) ∨ (Q∨?P) ?1（析取范式） ?(?P∧? Q) ∨ (?P∧ Q) ∨ (P∧? Q) ∨（P∧ Q）（主析取范式） （3）该公式为重言式 2．用直接证法证明 前提：P∨Q，P→R，Q→S 结论：S∨R 解：（1）?S P (2)Q →S P (3) ? Q (1)(2) (4)P∨ Q P (5)P (3)(4) (6) P → R P (7)R (5)(6) (8)?S→ R （1）（7） 即SVR得证 3．在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。 令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。 解：前题：?x (F (x) →?G(x)), ?x (G (x) ∨H (x)) ? x ?H (x) 结论:? x ?F (x) 证：（1）? x ?F (x) p (2) ?H (x) ES(1) (3) ?x (G (x) ∨H (x))P (4)G(c) vH(c)US(3) (5)G(c) T(2,4)I (6)?x (F (x) →?G(x)), p (7)F (c) →?G(c) US(6) (8) ?F (c) T(5,7)I (9)( ? x) ?F (x) EG(8) 4．用直接证法证明： 前提：（?x）（C（x）→W（x）∧R（x）），（?x）（C（x）∧Q（x）） 结论：（?x）（Q（x）∧R（x））。 证： （1）（?x）（C（x）∧Q（x））P (2) C (c) ∧Q（c）ES(1) (3)（?x）（C（x）→W（x）∧R（x））P 2011-2012学年第一学期离散数学作业及参考答案---信息安全10级5-1 1.利用素因子分解法求2545与360的最大公约数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最大公约数的方法 gcd(a,b) = p1min(a1,b1)p2min(a2,b2)pn min(an,bn) 360=2332515090 2545=2030515091 gcd(2545,360) =2030515090=5 2.求487与468的最小公倍数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最小公倍数的方法 lcm(a,b) = p1max(a1,b1)p2max(a2,b2)pn max(an,bn) ab=gcd(a, b)﹡lcm (a, b) 487是质数，因此gcd(487,468)=1 lcm(487,468)= (487*468)/1=487*468=227916 3.设n是正整数，证明：6|n(n+1)(2n+1) 证明：用数学归纳法： 归纳基础：当n=1时，n(n+1)(2n+1)=1*2*3=6，6|6 归纳假设：假设当n=m时，6|m(m+1)(2m+1) 归纳推导：当n=m+1时， n(n+1)(2n+1)=(m+1)(m+1+1)[2(m+1)+1] =(m+1)(m+2)(2m+3) = m(m+1)(2m+3)+2(m+1)(2m+3) = m(m+1)(2m+1+2)+2(m+1)(2m+3) = m(m+1)(2m+1)+2 m(m+1)+ 2(m+1)(2m+3) = m(m+1)(2m+1)+ 2(m+1)(m+2m+3) = m(m+1)(2m+1)+ 2(m+1)(3m+3) = m(m+1)(2m+1)+ 6(m+1)2 因为由假设6|m(m+1)(2m+1)成立。 而6|6(m+1)2 所以6|m(m+1)(2m+1)+ 6(m+1)2 故当n=m+1时，命题亦成立。 所以6| n(n + 1)(2n + 1) 5-2 1 已知 6x ≡7 (mod 23),下列式子成立的是( D ): A. x ≡7 (mod 23) B. x ≡8 (mod 23) C. x ≡6 (mod 23) D. x ≡5 (mod 23) 2 如果a ≡b (mod m) , c是任意整数，则（A ）： 离散数学实验报告 姓名： 学号： 班级： 实验地点： 实验时间： 1 实验目的和要求 运用最小生成树思想和求最小生成树程序解决实际问题。实际问题描述如下： 八口海上油井相互间距离如下表，其中1号井离海岸最近，为5km 。问从海岸经1号井铺设油管把各井连接起来，怎样连油管长度最短（为便于检修，油管只准在油井处分叉）？ 2 实验环境和工具 实验环境：Windows 7 旗舰版 工具：Dev-C++ 5.8.3 3 实验过程 3.1 算法流程图 3.2程序核心代码 //油管铺设问题Prim算法实现 #include /*输出邻接矩阵g*/ void DispMat(MGraph g){ int i,j; for (i=0;i 离散数学作业 一、选择题 1、下列语句中哪个就是真命题(C )。 A.我正在说谎。 B.如果1+2=3,那么雪就是黑色的。 C.如果1+2=5,那么雪就是白色的。 D.严禁吸烟！ 2、设命题公式))((r q p p G →∧→=,则G 就是( C )。 A 、 恒假的 B 、 恒真的 C 、 可满足的 D 、 析取范式 3、谓词公式),,(),,(z y x yG x z y x F ??→中的变元x ( C )。 A.就是自由变元但不就是约束变元 B.既不就是自由变元又不就是约束变元 C.既就是自由变元又就是约束变元 D.就是约束变元但不就是自由变元 4、设A={1,2,3},则下列关系R 不就是等价关系的就是(C ) A.R={<1,1>,<2,2>,<3,3>} B.R={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>} C.R={<1,1>,<2,2>,<3,3>,<1,4>} D.R={<1,1>,<2,2>,<3,3>,<1,2>,<1,3>,<2,3>,<2,1>, <3,1>,<3,2>} 5、设R 为实数集,映射σ=R →R,σ(x)= -x 2+2x-1,则σ就是( D )。 A.单射而非满射 B.满射而非单射 C.双射 D.既不就是单射,也不就是满射 6、下列二元运算在所给的集合上不封闭的就是( D ) A 、 S={2x-1|x ∈Z +},S 关于普通的乘法运算 B 、 S={0,1},S 关于普通的乘法运算 C 、 整数集合Z 与普通的减法运算 D 、 S={x | x=2n ,n ∈Z +},S 关于普通的加法运算 7、*运算如下表所示,哪个能使({a,b},*)成为含幺元半群( D ) b b b a a a b a * a b b b a a b a * 8( A ) 《离散数学》实验报告 专业 班级 姓名 学号 授课教师 二 O 一六年十二月 目录 实验一联结词的运算 实验二根据矩阵的乘法求复合关系实验三利用算法求关系的传递闭包实验四图的可达矩阵实现 实验一联结词的运算 一．实验目的 通过上机实验操作，将命题连接词运算融入到C语言的程序编写中，一方面加强对命题连接词运算的理解，另一方面通过编程实现命题连接词运算，帮助学生复习和锻炼C语言知识，将理论知识与实际操作结合，让学生更加容易理解和记忆命题连接词运算。二．实验原理 (1) 非运算, 符号: ,当时，P为F, 当时，P为T 。 (2) 合取, 符号: ∧ , 当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。 (3) 析取, 符号: ∨ , 当且仅当P和Q的真值同为假，命题P∨Q的真值才为假；否则，P∨Q的真值为真。 (4) 异或, 符号: ▽ , 当且仅当P和Q的真值不同时，命题P▽Q的真值才为真；否则，P▽Q的真值为真。 (5) 蕴涵, 符号: → , 当且仅当P为为F时，命题P→Q的真值才为假；否则，P→Q 的真值为真。 (6) 等价, 符号: ?, 当且仅当的真值不同时，命题P?Q的真值才为假；否则，P→Q 的真值为真。 三．实验内容 编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。四．算法程序 <> () { ; ("请选择运算方式\n"); ("1.析取\n"); ("2.合取\n"); ("3.非\n"); ("4.蕴含\n"); ("5.等价\n"); m; (""); ( m>=1 m<=4 ) { ("请输入P Q的值\n"); (" " ); = 1; (m) { 1( ( >= 1)( < 4 ) ) { (0 0) ("P 析取Q = 0\n"); ("P 析取Q = 1\n"); ; (4) ; ("请输入P Q的值\n"); (" " ); } ; 2( ( >= 0)( < 4 ) ) { (1 1) ("P 合取Q = 1\n"); ("P 合取Q = 0\n"); ; (4) ; ("请输入P Q的值\n"); (" " ); } ; 3( ( >= 0)( < 4 ) ) { (0) ("非Q = 1\n"); ("非Q = 0\n"); 1.【实验目的】 对称： 通过算法设计并编程实现对给定集合上的关系是否为对称关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法 自反： 通过算法设计并编程实现对给定集合上的关系是否为自反关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法。 2.【实验内容】 已知关系R 由关系矩阵M 给出，要求判断由M 表示的这个关系是否为对称关 系。假定R 的关系矩阵为：?????? ? ??=1234210330124321M 3.【实验要求】 C 语言编程实现 4.【算法描述】 对称： 从给定的关系矩阵来判断关系R 是否为对称是很容易的。若M （R 的关系矩阵）为对称矩阵，则R 是对称关系；若M 为反对称矩阵，则R 是反对称关系。因为R 为对称的是等价关系的必要条件，所以，本算法可以作为判等价关系算法的子程序给出。 算法实现： （1） 输入关系矩阵M （M 为n 阶方阵）； （2） 判断对称性，对于i=2，3，….，n ；j=1，2,……，i-1，若存在m ij =m ji ， 则R 是对称的； （3） 判断反对称性； （4） 判断既是对称的又是反对称的； （5） 判断既不是对称的又不是反对称的； （6） 输出判断结果。 自反： 从给定的关系矩阵来断判关系R是否为自反是很容易的。若M（R的关系矩阵）的主对角线元素均为1，则R是自反关系；若M（R的关系矩阵）的主对角线元素均为0，则R是反自反关系；若M（R的关系矩阵）的主对角线元素既有1又有0，则R既不是自反关系也不是反自反关系。本算法可以作为判等价关系算法的子程序给出。 算法实现 （1）输入关系矩阵M（M为n阶方阵）。 （2）判断自反性，对于i=1，2，….，n；若存在m =0，则R不是自反 ii =1，则R是自反的；否则R既不是自反关系也不是的；若存在m ii 反自反关系。 （3）输出判断结果。 源代码 #include 《离散数学》 实验报告 题目 专业 学号 姓名 指导教师 提交日期 实验一五种连结词的逻辑运算 一.实验目的 用C语言实现两个命题变元的合取、析取、蕴涵和等价表达式的计算。熟悉连接词逻辑运算规则，利用程序语言实现逻辑这几种逻辑运算。 二.实验内容 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、蕴涵和等价四种运算的的真值。要求对输入内容进行分析，如果不符合0、1条件需要重新输入，程序有良好的输入输出界面。 三. 实验过程 1. 算法分析： 编程语言为c语言 合取/\：p，q都为1的时候为1，其他为0 析取\/：p，q都为0的时候为0，其他为1 蕴含->：p为1，q为0时为0，其他为1 等价<->：p，q同真同假 流程图 2. 程序代码： #include do{ printf("请输入q的值(0或1)"); scanf("%d",&q); if(q!=0&&q!=1) printf("输入有误"); }while(q!=0&&q!=1); do{ printf("请选择要进行的操作\n"); printf("1:合取\n2:析取\n3:蕴含\n4:等价\n"); scanf("%d",&i); switch(i){ case 1:{ if(p&&q) printf("合取运算：p/\q=1\n"); else printf("合取运算：p/\q=0\n"); break; } case 2:{ if(p||q) printf("析取运算：p\/q=1\n"); else printf("析取运算：p\/q=0\n"); break; } case 3:{ if(p&&!q) printf("蕴含：p->q=0\n"); else printf("蕴含：p->q=1\n"); break;} case 4:{ if((p&&q)||(!p&&!q)) printf("等价运算：p<->q=1\n"); else printf("等价运算：p<->q=0\n"); break; } }printf("是否继续运算1\\0\n"); scanf("%d",&t); }while(t); return 0; }离散数学作业
离散数学作业答案
离散数学实验报告
离散数学(大作业)与答案
离散数学实验报告
离散数学作业(2)
离散数学作业
离散数学实验报告--四个实验!!!
离散数学作业
离散数学作业答案完整版
离散数学实验报告()
离散数学作业答案
离散数学实验报告
华南理工离散数学作业题2017版
离散数学 作业及答案
离散数学实验报告
离散数学作业标准答案
离散数学实验报告格式
离散数学关系性质的C++或C语言判断实验报告
离散数学实验报告