《离散数学》试卷及答案

1、优秀学习资料欢迎下载得一、选择题（每小题2 分，共 30 分）分1、设 A、B 和C 是任意三个集合，并且AB=AC，则（C ）A.BCB.CBC. B=CD. B和 C的关系无法确定2、若 R 是传递的，则(A ).A. r(R)是传递的B. r(R)不是传递的3、设论域为整数集，谓词F (x,y) :xyC. r(R)可能是传递的，也可能不是传递的0 。以下为真命题的是（B）。A. ( y)(x) F (x, y) ;C. (x)(y) F ( x, y) ;B.D.( x)( y) F ( x, y) ; ( x)( y)F (x, y).4、下面的命题公式中，重言式是（B）。A.(PC

2、.(PQ )Q )(Q(PP)；Q )B.D.(PQ)PP(QQ .P)；5、任何集合与其真子集均（C ）。A.等势 ;B.不能等势 ;C.无法确定6、下面 ( B )是极小项。A. PQB. PQC.P QD.Q P7、 公式xP( x, y)Q(x, z),使用改名规则后,所得到的谓词公式为( B).A.C.xP( x, y)uP( x, y)Q(u, z)Q(u, z)B.D.uP(u, y)xP( x, u)Q( x, z)Q ( x, z)8、设集合 A=a,b,c,d,B=1,2,3,4,f=<a,2 >,<b,1 >,<c,3 >,<d,

3、2 >A. f是双射函数B. fC. f是满射函数D. f9、下列蕴含式为真的是（B ）则从 A到 B的函数是（D）是入射函数即不是满射又不是入射函数A.x( A( x)B( x)xA(x)xB( x)B.xA( x)xB( x)x( A(x)B(x)Cx( A( x)xB( x)x( A( x)B( x)D.x( A( x)B(x)xA( x)xB( x)10、设是 A 到 B 的映射，A.是满射，是单射是 B 到BC 的映射，是单射，是双射，则（是满射B）C是满射，也是满射D是单射，也是单射11、设集合A. SS 是集合 Q的子集， Q是可数集，则（必是不可数集B.S 必是可数集C.

4、B ）。S可能是可数集，也可能是不可数集12、设 A=1 ，2，3，4，5 ， A上二元关系R= 1，2，3，4， 2，2 ，S= 2，优秀学习资料欢迎下载，则- 1-1的运算结果是（ A ）S·R43142A 4，1，2，3，4，2B 2，4，2，3，4，2C 4，1，2，3，2，4D 2，2，3，1，4，413、设 N 是自然数集， R是实数集，于是在下列集合中，基数为0的是（ C ）A 1 ，2， ,n ；B x 2|xR； C 有理数集； D (N)14、论断：“命题变元不是命题” （ A）命题。A 是； B. 不是； C.不可判定15、设 S=a,b,c ，T=p,q ，作

5、 f:ST, 则这样的 f 一共有（ C ）个。A. 9B.10C.8D.7得二、填空题 ( 每空 2 分, 共 20分)分1、设 P:2+5=3,Q: 日本在亚洲 ; 于是， PQ 的真值为 1。2、数理逻辑中，进行推理的常用规则有前提引入规则 ， 结论引入规则和置换规则。3、设集合 |A|=101 ，S A, 且 |S| 为奇数，则这样的 S 有2101/2 或 2100个。4、设 mi 是公式 G的的主析取范式中的一个极小项， 则 mi的对偶式 不一定是（填“是”/ “不是” / “不一定是” ） G 的主合取范式中的一个极大项。5、由 3 个元素组成的有限集上所有的等价关系有5个6、给

6、定解释 I 如下 : (1) Di:=2,3； (2)a =3；(3)函数 f(x) 为 f(2)=2 ，f(3)=3 ；(4)谓词： F(x) 为 F(2):=1,F(3):=0;G(x,y)为当 i=j时， G(i,j):=1；当 i j时， G(i,j):=0；其中 i,j=2,3;L(x,y) 为 L(2,2)=L(3,2):=0, L(2,3)=L(3,3):=1，在该解释下(1)x(F ( x)G (x, a)的真值为0.(2) x( F ( x)G ( x, a)L ( x, a)的真值为17、设谓词的论域D=a ，b，c ，试将x y( R(x)S( y) 中的量词消除 ,写成

7、与之等值的命题公式为S( a)S(b)S(c)(R(a)R(b)R(c)得三、计算与简答 ( 共 20 分 )分1、 AB, AB 是可能的吗？说明你的理由。 （ 4 分）解答：可能。如：定 B=a,aA=a优秀学习资料欢迎下载2. 设 A=1,2, 3 10 ，定义 A 上的二元关系 R=<x,y>|x,y A x+y=10 ，试讨论 R 关于关系的五个方面的性质并说明理由（ 5 分）解答： R=<1,9>,<9,1>,<2,8>,<8, 2 >,<3,7>,<7,3>,<4,6>,<6,

8、4 >,<5, 5 >R 具有非自反、非反自反、对称、非反对称和非传递性。（每一项 1 分）3、求命题公式( pq) r ) 的主析取范式和主合取范式。( 要求：主析取范式和主合取范式并分别用和 mi ， Mi形式表示，并写出推导过程 ) （5 分）解( pq)r )( pq)r )( ( p q)r )( p q) r )( pr )(qr )( pr )( qr )( pr )( qr )(pr )(qq)( qr )( pp)(prq)(prq)( qrp) (qrp)除去重复项得主析取范式为(p qr )( pqr )( pqr )=m0 m2m4根据主析取范式和主合

9、取范式的对应关系得主合取范式为M1M3M5M6M7=( pqr )( pqr )(pqr )(pqr )(pqr )4、 在一阶逻辑中将下列命题符号化：(6 分)（1）参加考试的人未必都能取得好成绩。解： P(x):x 是参加考试的人； Q(x):x 取得好成绩x( P( x)Q (x)（2）对任意的正实数，都存在大于该实数的实数。P（ x） : x 是实数；G（x, y）：:x 大于 y。解：x( P( x)G ( x,0)y(P( y)G ( y, x)（3）请把高等数学中函数f(x) 在 x=a 处连续的定义符号化 .解：令R( x) : x是实数 , G( x, y) : xy(R(

10、)G( ,0)(R()G( ,0)x(R( x)G( , | xa |)G( ,| f (x)f (a) |)得四、证明题（ 30 分）分优秀学习资料欢迎下载*1、设 C 是实数部分非零的全体复数组成的集合，上关系R定义为：（ a+bi ）R（c+di ） ac>0, 证明 R是等价关系。（15 分）证明 : （1）对于任意非零实数a，有2a >0（ a+bi ） R（ a+bi ）*所以 R 在 C 是自反的。（ 2）对任意（ a+bi ） R（ c+di ）ac>0因为 ca=ac>0（c+di ）R（a+bi ）*所以 R 在 C 是对称的。（ 3）设（ a+bi ）R（c+di ）且（ c+di ） R（u+vi ），则有：ac>0并且 cu>0若 u>0, 则 c>0,a>0, 因此有 ac>0; 若 u<0, 则 c<0,a<0, 也有 ac>0; 因此有（ a+bi ）R（u+vi ）*所以R 在C 是传递的。所以R是C 上的等价关系。