离散数学试卷（三） 一、 填空20%（每空2分） 1、设f,g是自然数集N上的函数x∈N,fx)=x+1,g(x)=2x, 则fg(x)= 2、设A={a,b,c,A上二元关系R=<a,a>,<ab>,<a,c>,<cc}, 则s(R)= 3、A={1,2,3,4,5,6,A上二元关系T={Kxy>x÷y是素数，则用列举法 T= T的关系图为 T具有 性质。 4、集合A={D,2,{2}的幂集2= 5、P,Q真值为0：R,S真值为1。则w矿(PA(RVS)→(PVQ)A(RAS)的真值 为 6、w(PAQ)VR)→R的主合取范式为 7、设P(x:x是素数，Ex:x是偶数，O(x:x是奇数N(Ky):x可以整数y。则谓词 wfx(Px)→(Oy)AN(y,x)》的自然语言是 8、谓词wfx(3(P(x,)AP(y,z》→3uQ(x,八，》的前束范式为 二、选择20%（每小题2分） 1、下述命题公式中，是重言式的为()。 A、(pAq)→(pvq):B、(p)q)(p→q)A(g→p): C、(p→q)Ag: D、(pAp)g 2、wf一(p人g)→r的主析取范式中含极小项的个数为()。 16
离散数学试卷（三） 16 一、 填空 20% （每空 2 分） 1、 设 f，g 是自然数集 N 上的函数 x N, f (x) = x +1 , g(x) = 2x ， 则 f g(x) = 。 2、 设 A={a，b，c}，A 上二元关系 R={< a, a > , < a, b >,< a, c >, < c, c>} , 则 s（R）= 。 3、 A={1，2，3，4，5，6}，A 上二元关系 T ={ x, y | x y 是素数} ，则用列举法 T= ； T 的关系图为 ； T 具有 性质。 4、 集合 A = {{, 2},{2 }} 的幂集 A 2 = 。 5、 P，Q 真值为 0 ；R，S 真值为 1。则 wff (P (R S)) → ((P Q) (R S)) 的真值 为 。 6、 wff ((P Q) R) → R 的主合取范式为 。 7、 设 P（x）：x 是素数， E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整数 y。则谓词 wff x(P(x) → y(O( y) N( y, x))) 的自然语言是 。 8、 谓词 wff xy(z(P(x,z) P( y,z)) → uQ(x, y,u)) 的前束范式为 。 二、 选择 20% （每小题 2 分） 1、 下述命题公式中，是重言式的为（ ）。 A、 ( p q) → ( p q) ； B、( p q) (( p → q)) (q → p)) ； C、 ( p → q) q ； D、( p p) q 。 2、 wff ( p q) → r 的主析取范式中含极小项的个数为（ ）
离散数学试卷（三） A、2:B、3:C、5:D、0:E、8。 3、给定推理 ①Vx(F(x)→G(x)》 ②Fy)→G) Us① ③3xF(x) ④Fy) ES③ ⑤Gy) T②④I ⑥xGx) UG⑤ x(F(x)→G(x)》一xG(x) 推理过程中错在()。 A、①->②：B、②->③：C、③->④：D、④->6：E、⑤->@ 4、设S1=1,2,8,9%,S2={2,4,6,8},S=1,3,5,7,9,S4=3,4,5, S=3,5},在条件X∈S,且X工S,下X与()集合相等。 A、X=S2或S5:B、X=-S4或S5: C、X=S1,S2或S4:D、X与S1,Ss中任何集合都不等 5、设R和S是P上的关系，P是所有人的集合，R={Kxyx,y∈PAx是的父亲， S=(Kx,yx,yEPAx是的母亲则S。R表示关系（ A、{Kx,yx,y∈PAx是y的丈夫}： B、(<xyxx.y∈PAx是的孙子或孙： C中：D、Kx,y>x,y∈PAx是的祖父或祖母。 6、下面函数(）是单射而非满射。 A、f:R→Rfx)=-x2+2x-1: B、f:Z→R,fx)=nx: C、f:R→Z,fx)=[x[x表示不大于x的最大整数：
离散数学试卷（三） 17 A 、2； B、 3； C、5； D、0； E、 8 。 3、 给定推理 ① x(F(x) → G(x)) P ② F( y) → G( y) US① ③ xF(x) P ④ F( y) ES③ ⑤ G( y) T②④I ⑥ xG(x) UG⑤ x(F(x) → G(x)) xG(x) 推理过程中错在（ ）。 A、①->②; B、②->③; C、③->④; D、④->⑤; E、⑤->⑥ 4、 设 S1={1，2，.，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}， S5={3，5}，在条件 X S1 且 X S3 下 X 与（ ）集合相等。 A、 X=S2 或 S5 ； B、X=S4 或 S5； C、X=S1，S2 或 S4； D、X 与 S1，.，S5 中任何集合都不等。 5、 设 R 和 S 是 P 上的关系，P 是所有人的集合， R ={ x, y | x, yP x是y的父亲}， S ={ x, y | x, y P x是y的母亲} 则 S R −1 表示关系 （ ）。 A、{ x, y | x, yP x是y的丈夫} ； B、{ x, y | x, yP x是y的孙子或孙女} ； C、 ； D、{ x, y | x, yP x是y的祖父或祖母}。 6、 下面函数（ ）是单射而非满射。 A、 : , ( ) 2 1 2 f R → R f x = −x + x − ； B、 f : Z → R, f (x) = ln x + ； C、 f : R → Z, f (x) = [x],[x]表示不大于x的最大整数 ；
离散数学试卷（三） D、f:R→R,f(x)=2x+1。 其中R为实数集，Z为整数集，R,Z分别表示正实数与正整数集。 7、设S={1,2,3,R为S上的关系，其关系图为 ⊙ ④® 则R具有( )的性质。 A、自反、对称、传递： B、什么性质也没有： C、反自反、反对称、传递： D、自反、对称、反对称、传递。 8、设S-{中，{1}，1,2}，则有()S。 A、{1,2};B、1,2}:C、{1):D、{2}。 9、设A={12,3,则A上有()个二元关系. A、23;B、32C、22:D、2。 10、全体小项合取式为()。 A、可满足式：B、矛盾式：C、永真式：D、A,B,C都有可能。 三、用CP规则证明16%（每小题8分） 1、AVB→CAD,DVE→F三A→F 2、x(P(x)vQ(x)→xPx)v3xQx) 四、(14%) 集合X=f1,2>,<3,4>,<5,6>,.},R={<,y1>,2,y2>k+y2-xty}· 1、证明R是X上的等价关系。(10分) 2、求出X关于R的商集。(4分) 五、(10%) 设集合A={a,b,c,d}上关系R={<ab>,<b,a>,<b,c>,<c,d>}
离散数学试卷（三） 18 D、 f : R → R, f (x) = 2x +1。 其中 R 为实数集，Z 为整数集，R +，Z +分别表示正实数与正整数集。 7、 设 S={1，2，3}，R 为 S 上的关系，其关系图为 则 R 具有（ ）的性质。 A、 自反、对称、传递； B、什么性质也没有； C、反自反、反对称、传递； D、自反、对称、反对称、传递。 8、 设 S = {,{1},{1, 2}} ，则有（ ） S 。 A、{{1,2}} ；B、{1,2 } ； C、{1} ； D、{2} 。 9、 设 A={1 ,2 ,3 }，则 A 上有（ ）个二元关系。 A、2 3 ； B、3 2 ； C、 3 2 2 ； D、 2 3 2 。 10、全体小项合取式为（ ）。 A、可满足式； B、矛盾式； C、永真式； D、A，B，C 都有可能。 三、 用 CP 规则证明 16% （每小题 8 分） 1、 A B → C D , D E → F A → F 2、x(P(x) Q(x)) x P(x) x Q(x) 四、（14%） 集合 X={<1,2>, <3,4>, <5,6>,. }，R={<<x1,y1>,<x2,y2>>|x1+y2 = x2+y1} 。 1、 证明 R 是 X 上的等价关系。 （10 分） 2、 求出 X 关于 R 的商集。（4 分） 五、（10%） 设集合 A={ a ,b , c , d }上关系 R={< a, b > , < b , a > , < b , c > , < c , d >}
离散数学试卷（三） 要求1、写出R的关系矩阵和关系图。(4分) 2、用矩阵运算求出R的传递闭包。(6分) 六、(20%) 1、(10分)设f和g是函数，证明fng也是函数。 2、(10分)设函数g:S→Tf:T→S,证明∫：T→S有一左逆函数当且仅当f是入射函 数
离散数学试卷（三） 19 要求 1、写出 R 的关系矩阵和关系图。（4 分） 2、用矩阵运算求出 R 的传递闭包。（6 分） 六、（20%） 1、（10 分）设 f 和 g 是函数，证明 f g 也是函数。 2、（10 分）设函数 g : S → T f :T → S ，证明 f :T → S 有一左逆函数当且仅当 f 是入射函 数