离散数学试卷(22) 一、单项选择题：（每小题1分，本大题共15分） 1.设A={1,2,3,4,5,下面( )集合等于A。 A、{1,2,3,4,5,6}: B、{xx是整数且r2≤25： C、{xx是正整数且x≤5：D、{xx是正有理数且x≤5。 2.设A-{1,2,3,{4,5,{6,7,8},下列各式中( ）是错的。 A、④SA: B、{6,7,8}∈A: C、{4,5}cA: D、1,2,3ycA 3.六阶群的子群的阶数可以是( 。 A、1,2,5:B、2,4: C、3,6,7: D、2,3。 4.设SSA×B,下列各式中( )是正确的。 A、domSCB:B、domSA:C、ranSA:D、domSrans=S。 5.设集合X≠，则空关系中x不具备的性质是( A、自反性：B、反自反性：C对称性： D、传递性。 6.下列函数中，( )是入射函数。 A、世界上每个人与其年龄的序偶集：B、世界上每个人与其性别的序偶集： B、一个作者的专著与其作者的序偶集：D、每个国家与其国旗的序偶集。 7.<G,*>是群，则对*( )。 A、满足结合律、交换律： B、有单位元，可结合： C、有单位元、可交换： D、每元有逆元，有零元。 8.下面( )哈斯图所描述的偏序关系构成分配格。 (B) (c) (D) 9.下列( ）中的运算符都是可交换的。 A、A,V,→： B、→，：C、U,n,: D、V,A· 142
离散数学试卷（22） 142 一、单项选择题：（每小题 1 分，本大题共 15 分） 1．设 A={1，2，3，4，5}，下面（ ）集合等于 A 。 A、{1，2，3，4，5，6}； B、{ 25} 2 x x是整数且x ； C、{x x是正整数且x 5} ； D、{x x是正有理数且x 5}。 2．设 A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中（ ）是错的。 A、 A ； B、{6，7，8} A； C、{{4，5}} A； D、{1，2，3} A 。 3．六阶群的子群的阶数可以是（ ）。 A、1，2，5； B、2，4； C、3，6，7； D、2，3 。 4．设 S A B ，下列各式中（ ）是正确的。 A、 domS B ； B、domS A； C、ranS A； D、domS ranS = S。 5．设集合 X ，则空关系 X 不具备的性质是（ ）。 A、自反性； B、反自反性； C、对称性； D、传递性。 6．下列函数中，（ ）是入射函数。 A、世界上每个人与其年龄的序偶集； B、世界上每个人与其性别的序偶集； B、一个作者的专著与其作者的序偶集； D、每个国家与其国旗的序偶集。 7． G,* 是群，则对*（ ）。 A、满足结合律、交换律； B、有单位元，可结合； C、有单位元、可交换； D、每元有逆元，有零元。 8．下面（ ）哈斯图所描述的偏序关系构成分配格。 9．下列（ ）中的运算符都是可交换的。 A、 , , → ； B、→ , ； C、 , , ； D、 ,
离散数学试卷(22) 10.设G是n个结点、m条边和r个面的连通平面图，则m等于( A、tr-2:B、n-rt2;C、n-r-2:D、ntr+2。 11.n个结点的无向完全图K的边数为( A、ma+):B、+D:Ca-):D、,-D 2 12.下列图中( )是根树。 A、G1=<{a,b,c,d,{ka,a>,<a,b>,<c,d>}>: B、G2=<{a,b,c,d,{ka,b>,<b,d>,<c,d>}>t C、G=<{a,b,c,d,{ka,b>,<ad>,<c,a>}>: D、G4=<{a,b,c,d},{ka,b>,<a,c>,<d,d>}>。 13.设P:2x2=5,Q:雪是黑的，R:2×4=8,S:太阳从东方升起，下列( )命题的真 值为真。 A、P→QAR；B、R→PAS；CS→QAR:D、(PAR)V(QAS). 14.下面( )命题公式是重言式。 A、P→QvR: B、(PR)A(P→Q): C、(PVQ)(QvR):D、(P→(Q→R)→(P→Q)→(P→R)。 15.设L(x):x是演员，Jx):x是老师，Ax,y沙：x钦佩y,命题“所有演员都软佩某些老师” 符号化为( )。 A、x(L(x)→A(x,y》: B、x(L(x)→3(Jy)AA(x,y》: C、xa(L(x)AJy)A4(x,y):D、xL(x)AJy)→4Ax,y》。 二、填空题：（每空1分，本大题共15分） 1.设M={x≤x≤12，x被2整除，x∈Z,N={1≤x≤12，x被3整除，x∈Z, 则MnN= ,M-N= 2.在一个有n个元素的集合上，可以有 种不同的关系，有 种 不同的函数。 3.若关系R是反对称的，当且仅当关系矩阵中」 在 143
离散数学试卷（22） 143 10．设 G 是 n 个结点、m 条边和 r 个面的连通平面图，则 m 等于（ ）。 A、n+r-2 ； B、n-r+2 ； C、n-r-2 ； D、n+r+2 。 11．n 个结点的无向完全图 Kn 的边数为（ ）。 A、 n(n +1) ； B、 2 n(n +1) ； C、 n(n −1) ； D、 2 n(n −1) 。 12．下列图中（ ）是根树。 A、G1 ={a,b,c,d},{ a,a , a,b , c,d } ； B、G2 ={a,b,c,d},{ a,b , b,d , c,d } ； C、G3 ={a,b,c,d},{ a,b , a,d , c,a } ； D、G4 ={a,b,c,d},{ a,b , a,c , d,d } 。 13．设 P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列（ ）命题的真 值为真。 A、P → Q R ； B、 R → P S ； C、S → Q R ； D、(P R) (Q S) 。 14．下面（ ）命题公式是重言式。 A、 P → Q R ； B、(P R) (P → Q) ； C、 (P Q) (Q R) ； D、(P → (Q → R)) → ((P → Q) → (P → R)) 。 15．设 L(x)：x 是演员，J(x)：x 是老师，A(x , y)：x 钦佩 y，命题“所有演员都钦佩某些老师” 符号化为（ ）。 A、x(L(x) → A(x, y)) ； B、x(L(x) → y(J ( y) A(x, y))) ； C、xy(L(x) J ( y) A(x, y)) ； D、xy(L(x) J ( y) → A(x, y)) 。 二、填空题：（每空 1 分，本大题共 15 分） 1．设 M ={x1 x 12, x被2整除，xZ}， N ={x1 x 12, x被3整除，xZ}， 则 M N = ， M − N = 。 2．在一个有 n 个元素的集合上，可以有 种不同的关系，有 种 不同的函数。 3．若关系 R 是反对称的，当且仅当关系矩阵中 ，在
离散数学试卷(22) 关系图上 4.设g∫是一个复合函数，若g和∫都是满射，则g∫为 ,若g和 都是入射，则g∫是 ，。 5.三阶群有」 ,个（不同构），其运算表为 (0101Y 1011 6.设图G=<V,E>,V={,2,Y,v4}的邻接矩阵A= 1100 ,则，的入度 1000 deg-(v)=_ 一，y4的出度deg(y4)= ,从y2到的长 度为2的路有 一条。 7.命题公式A一PV(一P→(QA(一Q→R)》的主合取范式为 一，其编码表示为 三、判断改正题：判断下列各题是否正确，正确的划“√”，错误的划“×”，并加以改正。 (每小题2分，本大题共20分) 1.A,B,C为任意集合，若AUB=AUC,则B=C。 2.设R是实数集，R上的关系={Kx,y>x-<2,xy∈R,R是相容关系。( 3.设<A,≤>是偏序集，B∈A,则B的极大元b∈B且唯一。 4.谓词公式3xPx)→xCx)V3vR(y)的前束范式是xV(P(x)→O()VR(y)。 5.在代数系统<S,>中，若一个元素的逆元是唯一的，其运算*必是可结合的。( 6.每一个有限整环一定是域，反之也对。 7.有割点的连通图可能是哈密尔顿图。 8.Vx(A(x)A B(x))xx)VxB(x). 9.无多重边的图是简单图。 10.设<A,A,V>是布尔代数，则<A,A,V>一定为有补分配格 四、简答题：（每小题5分，本大题共20分） 144
离散数学试卷（22） 144 关系图上 。 4．设 g f 是一个复合函数，若 g 和 f 都是满射，则 g f 为 ，若 g 和 f 都是入射，则 g f 是 。 5．三阶群有 个（不同构），其运算表为 。 6．设图 G = < V，E >， { , , , } 1 2 3 4 V = v v v v 的邻接矩阵 = 1 0 0 0 1 1 0 0 1 0 1 1 0 1 0 1 A ，则 1 v 的入度 deg ( )1 v − = ， 4 v 的出度 deg ( ) 4 v + = ，从 2 v 到 4 v 的长 度为 2 的路有 条。 7．命题公式 A P (P → (Q (Q → R))) 的主合取范式为 ，其编码表示为 。 三、判断改正题：判断下列各题是否正确，正确的划“√”，错误的划“×”，并加以改正。 （每小题 2 分，本大题共 20 分） 1．A，B，C 为任意集合，若 AB = AC ，则 B = C 。 （ ） 2．设 R 是实数集，R 上的关系 f ={ x, y x − y 2, x, y R}，R 是相容关系。（ ） 3．设< A ，≤ > 是偏序集， B A ，则 B 的极大元 bB 且唯一。 （ ） 4．谓词公式 xP(x) → xQ(x) yR( y) 的前束范式是 xzy(P(x) → Q(z) R( y)) 。 （ ） 5．在代数系统< S , > 中，若一个元素的逆元是唯一的，其运算必是可结合的。 （ ） 6．每一个有限整环一定是域，反之也对。 （ ） 7．有割点的连通图可能是哈密尔顿图。 （ ） 8．x(A(x) B(x)) x A(x) x B(x) 。 （ ） 9．无多重边的图是简单图。 （ ） 10．设 A , , 是布尔代数，则 A , , 一定为有补分配格。 （ ） 四、简答题：（每小题 5 分，本大题共 20 分）
离散数学试卷(22) 1.设R和R是A上的任意二元关系，如果R和R是自反的，R。R,是否也是自反的，为什 么？如果R和R,是对称的，R。R是对称的吗？ 2.如图给出的赋权图表示六个城市a,b,c,d,e,∫及架起城市间直接通讯线路的预测造价。试给 出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。 3.设S=R-{-1}(R为实数集)，a*b=a+b+ab (1)说明<S,*>是香构成群：(2)在S中解方程2*x*3=7。 4.将公式(PVQ)AR)→(PAR)划为只含有联结词一，A的等价公式。 五、证明题：（共30分） 1.设A=I,2,3,.,9},在A×A上定义关系R:<a,b>,<c,d>eR当且仅当 a+d=b+c,证明R是A×A上的等价关系，并求出[<2,5>]R=? 2.用CP规则证明A→(BAC),(E→F)→C,B→(AAS)ZB→E。 3.将下列命题形式化，并证明结论的有效性：所有有理数都是实数，某些有理数是整数。因此， 某些实数是整数。 5.证明：若T是有n个结点的完全二叉树，则T有”'片叶子。 2
离散数学试卷（22） 145 1．设 R1 和 R2 是 A 上的任意二元关系，如果 R1 和 R2 是自反的， R1 R2 是否也是自反的，为什 么？如果 R1 和 R2 是对称的， R1 R2 是对称的吗？ 2．如图给出的赋权图表示六个城市 a,b,c,d,e, f 及架起城市间直接通讯线路的预测造价。试给 出一个设计方案使得各城市间能够通讯且总造价最小，并计算出最小总造价。 3．设 S = R - {-1}（R 为实数集）， ab = a +b + ab。 （1）说明 S, 是否构成群； （2）在 S 中解方程 2 x 3 = 7 。 4．将公式 ((P Q) R）→ (P R) 划为只含有联结词 ， 的等价公式。 五、证明题：（共 30 分） 1 ． 设 A = {1 , 2 , 3 , , 9} ， 在 A A 上定义关系 R : a,b , c,d R 当且仅当 a + d = b + c ，证明 R 是 A A 上的等价关系，并求出 [ 2,5 ] = ? R 2．用 CP 规则证明 A → (B C)，(E → F) → C ， B → (A S) B → E 。 3．将下列命题形式化，并证明结论的有效性：所有有理数都是实数，某些有理数是整数。因此， 某些实数是整数。 5．证明：若 T 是有 n 个结点的完全二叉树，则 T 有 2 n +1 片叶子