gmehcAAA离散数学实验报告
课程名称：离散数学课程设计指导教师：
班级：信软2014-2 姓名：学号：
实验项目名称：
若干代数系统的计算机判断--群的判定
实验目的及要求：
【实验目的】掌握群的判定方法。
【实验内容】输入代数系统(A,*)的集合A和*运算的运算表，判断(A，*)是否是群。
实验原理：
【实验原理和方法】
（1）用一维数组a[n]存贮集合A。
（2）用二维数组op[n][n]存贮运算表。
（3）根据群的定义，代数系统(A，*)若为群，除运算表已表明运算*封闭外，还应该满足下列三个条件：*运算可结合、有幺元e、 A中任何元素都有逆元。
*运算可结合：
for(i=0;i for(j=0;j for(k=0;k { for(l=0;l { if(op[i][j]==a[l]) x=l;/*op[i][j] 代表a*b*/ if(op[j][k]==a[l]) y=l;/*op[j][k] 代表b*c*/ } if(op[i][y]!=op[x][k])/*op[i][y]代表a*(b*c)*/ { printf("(%d*%d)*%d=%d,%d*(%d*%d)=%d,运算是不可结合！\n", a[i],a[j],a[k],op[x][k],a[i],a[j],a[k],op[i][y]); flag=0;/*不满足结合性*/ } } if(flag) printf("运算是可结合！\n"); 有幺元e: flag=0; for(i=0;i { for(j=0;j if(op[i][j]!=a[j] || op[j][i]!=a[j]) break; if(j==N) { printf("群有幺元%d！\n",a[i]); e=a[i]; flag=1; break; } } if(!flag) printf("群没有幺元！\n"); A中任何元素都有逆元： flag=1; for(i=0;i { for(j=0;j if(op[i][j]==e && op[j][i]==e) break;/*e是幺元*/ if(j==N) { flag=0; printf("A中元素%d没有逆元！\n",a[j]); } } if(flag) printf("A中任何元素都有逆元！\n"); 实验内容： 完整代码： #include "" #include "" #include "" #define OK 1 #define ERROR 0 #define N 2 typedef int Status ; typedef int ElemType; ElemType Vcomplete(ElemType x,ElemType y){//群对应的运算 return x*y; } Status juzhen(ElemType *a,ElemType ***op){//构造op矩阵 int i,j; for (i=0;i for (j=0;j { op[i][j]=Vcomplete(a[i],a[j]); } printf("complete: *"); return OK; } Status jiehe(ElemType **op,ElemType *a){///运算可结合 int i,j,k,l,x,y; int flag=0; for(i=0;i for(j=0;j for(k=0;k { for(l=0;l { if(op[i][j]==a[l]) x=l;///*op[i][j] 代表a*b*////矩阵中的位置，在群中找到相应的元素，保存这个元素位置； if(op[j][k]==a[l]) y=l;///*op[j][k] 代表b*c*/ } if(op[i][y]!=op[x][k])/*op[i][y]代表a*(b*c)*////通过找矩阵中元素的与剩下元素运算在矩阵中对应位置； { printf("(%d*%d)*%d=%d,%d*(%d*%d)=%d,运算是不可结合！\n",a[i],a[j],a[k],op[x][k],a[i],a[j],a[k],op[i][y]); flag=0;/*不满足结合性*/ } } if(flag) printf("运算是可结合！\n"); } Status yaoyuan(ElemType *a,ElemType **op,ElemType *e){//有幺元 int i,j; int flag=0; for(i=0;i { for(j=0;j if(op[i][j]!=a[j] || op[j][i]!=a[j]) break;//行和列对这个元素保持不变 if(j==N) { printf("群有幺元%d！\n",a[i]); e=a[i]; flag=1; break; } } if(!flag) printf("群没有幺元！\n"); return OK; } Status ni(ElemType *a,ElemType **op,ElemType e){//有逆int i,j; int flag=1; for(i=0;i { for(j=0;j if(op[i][j]==e && op[j][i]==e) break;/*e是幺元*/ if(j==N-1) { flag=0; printf("A中元素%d没有逆元！\n",a[j]); return ERROR; } } if(flag) printf("A中任何元素都有逆元！\n"); return OK; } int main(){ ElemType a[N]; int i,j; for (i=0;i { printf("Number %d :",i+1); scanf("%d",&a[i]); fflush(stdin); } printf("complete: *\n"); ElemType op[N][N]; ElemType e; for (i=0;i for (j=0;j { op[i][j]=Vcomplete(a[i],a[j]); printf("complete: *"); } jiehe(op,a); yaoyuan(a,op,&e); ni(a,op,e); } 实验结果与分析： 实验结果： Number 1:1 Number 2:2 complete: * 运算是可结合！ 群有幺元1！ A中任何元素都有逆元！ 结果分析： 1)效果挺好，也完美成功。 2)通过这个程序可以方便的判断是否在规定运算下是群,我还特意编写了一个 接受运算的函数,可以直接在那个里面修改成你要的运算。 3)程序很巧妙的用群的封闭性，对群的一些运算的判别直接运用现成的群中的 元素来替代。 成绩：批阅教师签名：年月日 离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、 数理逻辑部分的综合练习，基本上是按照考试的题型(除单项选择题外) 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1 .命题公式P (Q P)的真值是T或1 ______ . 2?设P:他生病了，Q:他出差了. R:我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P V Q)-R 3. ____________________________________________________________ 含有三个命题变项P，Q，R的命题公式P Q的主析取范式是__________________ _(P Q R) (P Q R)_ 4. 设P(x): x是人，Q(x): x去上课，则命题“有人去上课.” 可符号化为— x(P(x) Q(x))_ 5. 设个体域D = {a, b},那么谓词公式xA(x) yB(y)消去量词后的等值式为 (A(a) A(b)) (B(a) B(b))_ 6 .设个体域D = {1,2, 3}，A(x)为“x大于3”，则谓词公式(x)A(x)的真值为F 或0 ________________ . 7.谓词命题公式(x)((A(x) B(x)) C(y))中的自由变元为 ________ . 8 .谓词命题公式(x)(P(x) Q(x) R(x，y))中的约束变元为x _______ . 三、公式翻译题 1 .请将语句“今天是天晴”翻译成命题公式 《离散数学》实验报告专业网络工程 班级 姓名 学号 授课教师 二 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卷答案） 一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式 解：(P↓Q)→(P∧?(Q∨?R))??(?( P∨Q))∨(P∧?Q∧R)) ?(P∨Q)∨(P∧?Q∧R)) ?(P∨Q∨P)∧(P∨Q∨?Q)∧(P∨Q∨R) ?(P∨Q)∧(P∨Q∨R) ?(P∨Q∨(R∧?R))∧(P∨Q∨R) ?(P∨Q∨R)∧(P∨Q∨?R)∧(P∨Q∨R) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：?P∧Q 乙：?Q∧P 丙：?Q∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，， 离散数学实验报告（实验ABC） 专业班级 学生姓名 学生学号 指导老师 完成时间 目录 第一章实验概述..................................... 错误!未定义书签。 实验目的....................................... 错误!未定义书签。 实验内容....................................... 错误!未定义书签。 实验环境....................................... 错误!未定义书签。第二章实验原理和实现过程........................... 错误!未定义书签。 实验原理....................................... 错误!未定义书签。 建立图的邻接矩阵，判断图是否连通 ............ 错误!未定义书签。 计算任意两个结点间的距离 ................... 错误!未定义书签。 对不连通的图输出其各个连通支 ................ 错误!未定义书签。 实验过程（算法描述）........................... 错误!未定义书签。 程序整体思路 ............................... 错误!未定义书签。 具体算法流程 ................................ 错误!未定义书签。第三章实验数据及结果分析........................... 错误!未定义书签。 建立图的邻接矩阵并判断图是否连通的功能测试及结果分析错误!未定义书签。 输入无向图的边 .............................. 错误!未定义书签。 建立图的连接矩阵 ............................ 错误!未定义书签。 其他功能的功能测试和结果分析................... 错误!未定义书签。 计算节点间的距离 ............................ 错误!未定义书签。 判断图的连通性 .............................. 错误!未定义书签。 输出图的连通支 .............................. 错误!未定义书签。 退出系统 .................................... 错误!未定义书签。第四章实验收获和心得体会........................... 错误!未定义书签。 一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c) B.(a∧b)∨(a’∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交 运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z，ο〉，Z是整数集，ο定义为xοxy=xy,?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( ) A.R∪I A B.R C.R∪{〈c,a〉} D.R∩I A 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的 等价关系，R应取( ) A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x 离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1或T ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如 果他生病或出差了，我就同意他不参加学习”符号化的结果为 （P ∨Q ）→R ． 3．含有三个命题变项P ，Q ，R 的命题公式P ∧Q 的主析取范式是 (P ∧Q ∧R)∨(P ∧Q ∧?R) ． 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 ) 的真值为 0(F) ． 7．谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y ． 8．谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ，y ))中的约束变元为 x ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 设P ：今天是晴天。 姓 名： 学 号： 得 分： 教师签名： 一、填空 20% （每小题2分） 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为 。 2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。 3、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。 9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为 。 二、选择 20% （每小题2分） 1、在下述公式中是重言式为（ ） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→ 。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（ ）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、 设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有（ ）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为 离散数学作业7 离散数学数理逻辑部分形成性考核书 面作业 本课程形成性考核书面作业共3次,内容主要分别就是集合论部分、图论部分、数理逻辑部分的综合练习,基本上就是按照考试的题型(除单项选择题外)安排练习题目,目的就是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业就是第三次作业,大家要认真及时地完成数理逻辑部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”与“交卷”按钮,以便教师评分。 一、填空题 1.命题公式()P Q P →∨的真值就是 T 或1 . 2.设P :她生病了,Q :她出差了.R :我同意她不参加学习、 则命题“如果她生病或出差了,我就同意她不参加学习”符号化的结果为 (P ∨Q)→R . 3.含有三个命题变项P ,Q ,R 的命题公式P ∧Q 的主析取范式就是 )()(R Q P R Q P ?∧∧∨∧∧ . 4.设P (x ):x 就是人,Q (x ):x 去上课,则命题“有人去上课.” 可符号化为 ))()((x Q x P x ∧? . 5.设个体域D ＝{a , b },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 ))()(())()((b B a B b A a A ∧∨∨ . 6.设个体域D ＝{1, 2, 3},A (x )为“x 大于3”,则谓词公式(?x )A (x ) 的真值为 F 或0 . 7.谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y . 8.谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ,y ))中的约束变元为 x . 三、公式翻译题 1.请将语句“今天就是天晴”翻译成命题公式. P 。，P 则今天是天晴设答:: 2.请将语句“小王去旅游,小李也去旅游.”翻译成命题公式. Q 。P ；，Q P ∧则小李去旅游小王去旅游设答::: 3.请将语句“如果明天天下雪,那么我就去滑雪”翻译成命题公式. Q 。P ；，Q P →则我去滑雪明天下雪设答;:: 4.请将语句“她去旅游,仅当她有时间.”翻译成命题公式. 《离散数学》 课程设计 学院计算机学院 学生姓名 学号 指导教师 评阅意见 提交日期 2011 年 11 月 25 日 引言 《离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。 实验一、编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性） 一、前言引语：二元关系是离散数学中重要的内容。因为事物之间总是可以 根据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之间存在的关系。 二、数学原理：自反、对称、传递关系 设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合R 就是A×B的一个合于R={(x,y)∈A×B|xRy}的子集合 设R是集合A上的二元关系： 自反关系：对任意的x∈A,都满足 试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统 二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。 离散数学作业答案 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 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 离散数学实验报告 姓名： 学号： 班级： 实验地点： 实验时间： 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 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{ 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 ）： 《离散数学》实验报告 专业 班级 姓名 学号 授课教师 二 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");(完整版)离散数学作业答案一
离散数学实验报告
(完整版)离散数学试卷及答案
离散数学实验报告
离散数学试卷及答案一
电大 离散数学作业7答案
离散数学试卷及答案(2)
离散数学作业答案一
离散数学实验报告--四个实验!!!
离散数学试题与答案
离散数学作业答案完整版
离散数学实验报告()
离散数学作业答案
离散数学实验报告
离散数学期末试卷A卷及答案
离散数学实验报告
离散数学期末试卷及答案
离散数学 作业及答案
离散数学实验报告格式