文档介绍：离散数学(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)Û∧Û∨∨∨∨∨(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上的二元关系,,tsr(R)是包含R的且具有自反性、对称性和传递性的关系。若是包含R的且具有自反性、对称性和传递性的任意关系,则由闭包的定义知r(R)Í。(R)Ís()=,进而有tsr(R)Ít()=。综上可知,tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。四、(15分)集合A={a,b,c,d,e}上的二元关系R为R={<a,a>,<a,b>,<a,c>,<a,d>,<a,e>,<b,b>,<b,c>,<b,e>,<c,c>,<c,d>,<c,e>,<d,d>,<d,e>,<e,e>},(1)写出R的关系矩阵。(2)判断R是不是偏序关系,为什么?解(1)R的关系矩阵为:(2)由关系矩阵可知,对角线上所有元素全为1,故R是自反的;+≤1,故R是反对称的;可计算对应的关系矩阵为:由以上矩阵可知R是传递的。(10分)设A、B、C和D为任意集合,证明(A-B)×C=(A×C)-(B×C)。证明:因为<,>∈(A-B)×CÛ∈(A-B)∧∈CÛ(∈A∧ÏB)∧∈CÛ(∈A∧∈C∧ÏB)∨(∈A∧∈C∧ÏC)Û(∈A∧∈C)∧(ÏB∨ÏC)Û(∈A∧∈C)∧Ø(∈B∧∈C)Û<,>∈(A×C)∧<,>Ï(B×C)Û<,>∈(A×C)-(B×C)所以,(A-B)×C=(A×C-B×C)。(10分)设f:A®B,g:B®C,h:C®A,证明:如果hogof=IA,fohog=IB,gofoh=IC,则f、g、h均为双射,并求出f-1、g-1和h-1。解因IA恒等函数,由hogof=IA可得f是单射,h是满射;因IB恒等函数,由fohog=IB可得g是单射,f是满射;因IC恒等函数,由gofoh=IC可得h是单射,g是满射。从而f、g、h均为双射。由hogof=IA,得f-1=hog;由fohog=IB,得g-1=foh;由gofoh=IC,得h-1=gof。(15分)设<G,*>是一代数系统,运算*满足交换律和结合律,且a*x=a*yÞx=y,证明:若G有限,则G是一群。证明因G有限,不妨设G={,,…,}。由a*x=a*yÞx=y得,若x≠y,则a*x≠a*y。于是可证,对任意的a∈G,有aG=G。又因为运算*满足交换律,所以aG=G=Ga。令e∈G使得a*e=a。对任意的b∈G,令c*a=b,则b*e=(c*a)*e=c*(a*e)=c*a=b,再由运算*满足交换律得e*b=b,所以e是关于运算*的幺元。对任意a∈G,由aG=G可知,存在b∈G使得a*b=e,再由运算*满足交换律得b*a=e,所以b是a的逆元。由a的任意性知,G中每个元素都存在逆元。故G是一群。(20分)(1)证明在n个结点的连通图G中,至少有n-1条边。证明不妨设G是无向连通图(若G为有向图,可略去边的方向讨论对应的无向图)。设G中结点为、、…、。由连通性,必存在与相邻的结点,不妨设它为(否则可重新编号),连接和,得边,还是由连通性,在、、…、中必存在与或相邻的结点,不妨设为,将其连接得边,续行此法,必与、、…、中的某个结点相邻,得新边,由此可见G中至少有n-1条边。(2)给定简单无向图G=<V,