离散数学期末考试题(和含解析1)

一.填空2．A,B,C示意三个齐集,文图中阴影部分的齐集表达式为(B⊕C)-AAC4．公式的主合取范式为.5．若说明I的论域D仅包括一个元素,则在I下真值为1.6．设A={1,2,3,4},A上关系图以下,则R^2={(1,1),(1,3),(2,2),(2,4)}.备注：7．设A={a,b,c,d},其上偏序关系R的哈斯图以下,则R={(a,b),(a,c),(a,d),(b,d),(c,d)}U{(a,a),(b,b)(c,c)(d,d)}.备注：偏序满足自反性,反对称性,传达性8．图的补图为.补图:给定一个图G,又G中全部结点和全部能使G成为完好图的增添边组成的图,成为补图.自补图:一个图假好像构于它的补图,则是自补图9．设A={a,b,c,d},A上二元运算以下：*abcdaabcdbbcdaccdabddabc那么代数系统<A,*>的幺元是a,有逆元的元素为a,b,c,d,它们的逆元分别为a,b,c,d.//备注：二元运算为x*y=max{x,y},x,yA.10．以下图所示的偏序分别,是格的为c.（注：什么是格？即任意任性两个元素有最小上界和最大下界的偏序）二.选择题1.以下是真命题的有（

C.D

）A．

;

B．

;C．

;

D

．

.以下聚分别相等的有（B.C）A．{4,3}

;B．{

,3,4};C

．{4,

,3,3};D

．

{3,4}.3.设

A={1,2,3},

则A上的二元关系有（

C）个.A．

23;

B

．32;

C

．

;D

．

.//备注：A的二元关系个数为：个.设R,S是齐集A上的关系,则以下说法正确的是（A）A．若

R,S

是自反的

,则

是自反的

;B．若

R,S

是反自反的

,则

是反自反的

;XC．若

R,S

是对称的

,则

是对称的

;XD．若

R,S

是传达的

,则

是传达的

.X//备注：设R={<3,3>,<6,2>},S={<2,3>},则={<6,3>},={<2,3>}设A={1,2,3,4},P（A）（A的幂集）上划定二元系以下,则P（A）/R=（D）A．A;B．P(A);C．{{{1}},{{1,2}},{{1,2,3}},{{1,2,3,4}}};D．{{},{2},{2,3},{{2,3,4}},{A}}6.设A={,{1},{1,3},{1,2,3}}则A上包括关系“”的哈斯图为C）例题：画出以下各关系的哈斯图1）P={1,2,3,4},<P,≤>的哈斯图.2）A={2,3,6,12,24,36},<A,整除>的哈斯图.3）A={1,2,3,5,6,10,15,30},<A,整除>的哈斯图以下函数是双射的为（A）//双射既是单射又是满射A．f:IE,f(x)=2x;B．f:NNN,f(n)=<n,n+1>;C．f:RI,f(x)=[x];//x的象D．f:IN,f(x)=|x|.（注：I—整数集,E—偶数集,N—天然数集,R—实数集）8.图中从v1到v3长度为3的通路有（D）条.//备注：分别是v1->v1->v1->v3,v1->v4->v1->v3,v1->v3->v1->v3A．0;B．1;C．2;D．3.以下图中既不是Eular（欧拉）图,也不是Hamilton（哈密顿）图的图是（B）在一棵树中有7片树叶,3个3度结点,其他都是4度结点则该树有（A）个4度结点.A．1;B．2;C．3;D．4.//备注：树的极点数=边数+17+3×3+4n=2（7+3+n-1）解得n=1三.证明题1.R是齐集X上的一个自反关系,求证：R是对称和传达的,当且仅当<a,b>和<a,c>在R中有<b,c>在R中.证：“”

若

由R对称性知

,由

R传达性得“”若

,

有

任意任性

,因

若因此

R是对称的若

,

则

即R是传达的2.f和g都是群<G1,★>到<G2,*>证明<C,★>是<G1,★>的一个子群

的同态映照.其中C=

.证：,有

,又★

★★

<C,

★>

是

<G1,

★>的子群

.3.G=<V,E>(|V|=v,|E|=e)

是每一个面起码由

k（k

3）条边围成的连通平面图图长短平面图.（11证：①设G有r个面,则

,则分）

,由此证明彼得森图（,即.而故

Peterson

）即得

.

（8

分）②彼得森图为

,这样

不建立

,因此彼得森图非平面图为：四.逻辑推演用CP规矩证明下题①P（附带前提）US①③P④US③⑤

T②④IUG⑤⑦CP五.筹算题1.设齐集

A={a,b,c,d}

上的关系

R={<a,b>,<b,a>,