资源描述：
《离散数学考试试题a》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一.(8分)求与公式(x2ornotxl)->x3逻辑等值的主合取范式和主析取范式.二.(8分)判断下列各公式是：1・永真式2•永假式3•其它(1)(p->(q->r))->(q->(p->r))(2)(notporq)<->(pand(pandq))(3)(notporq)andnot(qornotr)andnot(rornotpornotq)(4)(qandp)->(porq)三.(9分)问anyxexistyP(x,y)->existyanyxP(x,y)是否谓词演算的有效式?证明你的结论.四.(9分)将下列推理符号化并给出
2、形式证明：鸟会飞，猴子不会飞;所以,猴子不是鸟.五.(12分)令X二{xl,x2,..・，xm},Y二{yl,y2,...,yn},问：(1)有多少不同的由X到Y的关系？(2)有多少不同的由X到Y的影射？(3)有多少不同的由X到Y的单射，双射？六.(8分)设e是奇数阶交换群G的单元位，试证:G的所有元素之积为c.一.(15分)①是个群,H,K是其了群，在G上定义二元关系R:anya,binG,aRb〈二〉存在h,kink,使得b二h*a*k,证明：只是6上的等价关系.②在①中，若IH
3、=m,
4、K
5、=n,
6、G
7、=mn,m与n互素，且
8、R的某个等价类在G的乘法运算下构成G的一个了群，则R二G*G・二.(8分)把平面分成B个区域，每两个区域都相邻，问B最大为几？三.(11分)设G为非平凡有向图,V(G)为G的结点集合，若对V(G)的任意非空子集S,G中起始结点在S中，终止结点在V(G)S中的有向边都至少有k条，则称G是k边连通的•证明：非平凡有向图G是强连通的充要条件是他是1边连通的.十•(12分)设G是一无向加权图且各边的权不相等,V,E分别是G的结点集合和边的集合，(VI,V2)是V的划分，即VIorV2=V,VIandV2=null,且Vl!=null,V2
9、!=null,则VI与V2间的放短边一定在G的最小生成树上.离散数学参考答案一・主合取范式：(notxlornotx2orx3)and(xlornotx2orx3)and(xlorx2orx3)主析取范式：(xlandnotx2andnotx3)or(xlandx2andx3)or(xlandnotx2andx3)or(notxlandx2andx3)or(notxlandnotx2andx3)二.(1)1⑵3⑶2⑷1三•不是•取一特定解释域I如下・[P(x,y)]I二〃x〈二y〃,论域D二N(自然数集)则显然有[anyxexis
10、tyP(x,y)]I=t[existyanyxP(x,y)]I二f故给定公式在I中为假，因此它不是谓词公式的有效式.四.(1)anyx(bird(x)->fly((x))//前提1(2)anyx(monkey(x)->notfly(x))//前提2(3)bird(a)->fly(a)//(l)脱帽(4)monkey(a)->notfly(a)//(2)脱帽(5)notfly(a)->notbird(a)//逆否律(3)(6)monkey(a)->notbird(a)//传递律(4)(5)(7)anyx(monkey(x)->not
11、bird(x))//(6)戴帽五.解：(1)一个x到y的关系对应于x*y的一个子集•因此，不同的x到y的关系数二
12、(x*y)
13、=2"(mn)⑵不同的由x到y的映射个数二I{f
14、f:x_>y}1=1{(f(xl),f(x2),.・・，f(xin)),f(xi)iny,1=15、{f(xk)f(xk)iny}(3)若m!=n,则双射的个数为0若m=n,则双射的个数为m!若m>n,则单射个数0若mm!种不同的双射，共有单射Cn(m)*m!种.六.证明：由于G为奇数阶交换群，由拉格朗LI定理,其屮不可能有
16、2阶元，因此anyainG(a!=e),a!=a^(-1)，即a与a"(-1)是两个不同元素(a!=e),因此G的所有元素之积二e*al*a「(T)*a2*a2,(T)*・・・*am*anf(~l)=ealinG-{e},a2inG—{al,a八(一1),e},・・・,aminG~{e,al,a「(-1),a2,a2^(-1),・・・,a(m~l),a(m-l)(-1)G=2m+l七.(1)1.自反性:anyainG有:a二e*a*e.(e为单位元)，而H,k为G的子群，从而einH,einkso:aRa・2.对称性:若aRb,二
17、〉存在hinH,kinK使b二h*a*k二＞aFh"(T)*k“(T)，由于H,K为G的子群二〉FT(T)inH,(-1)inK,所以bRa.3•传递性：若aRb,bRc=＞存在hl,h2inH,kl,k2inK,使b二hl*a*kl,c二h2*b
