离散数学试题第一部分选择题一、单项选择题1．下列是两个命题变元p，q的小项是（C ）A．p∧┐p∧q B．┐p∨qC．┐p∧q D．┐p∨p∨q2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）A．p→┐q B．p∨┐qC．p∧q D．p∧┐q3．下列语句中是命题的只有（ A ）A．1+1=10 B．x+y=10C．sinx+siny<0 D．x mod 3=24．下列等值式不正确的是（ D ）A．┐(∀x)A⇔(∃x)┐AB．(∀x)(B→A(x))⇔B→(∀x)A(x)C．(∃x)(A(x)∧B(x))⇔(∃x)A(x)∧(∃x)B(x)D．(∀x)(∀y)(A(x)→B(y))⇔(∀x)A(x)→(∀y)B(y)5．谓词公式(∃x)P(x,y)∧(∀x)(Q(x,z)→(∃x)(∀y)R(x,y,z)中量词∀x的辖域是（C ）A．(∀x)Q(x,z)→(∃x)(∀y)R(x,y,z))B．Q(x,z)→(∀y)R(x,y,z)C．Q(x,z)→(∃x)(∀y)R(x,y,z)D．Q(x,z)6．设A={a,b,c,d}，A上的等价关系R={<a,b>,<b,a>,<c,d>,<d,c>}∪I A，则对应于R的A的划分是（ D ）A．{{a},{b,c},{d}} B．{{a,b},{c},{d}}C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}7．设A={Ø}，B=P(P(A))，以下正确的式子是（A ）A．{Ø,{Ø}}∈B B．{{Ø,Ø}}∈BC．{{Ø},{{Ø}}}∈B D．{Ø,{{Ø}}}∈B8．设X，Y，Z是集合，一是集合相对补运算，下列等式不正确的是（A ）A．(X-Y)-Z=X-(Y∩Z)B．(X-Y)-Z=(X-Z)-YC．(X-Y)-Z=(X-Z)-(Y-Z)D．(X-Y)-Z=X-(Y∪Z)9．在自然数集N上，下列定义的运算中不可结合的只有（ D ）A．a*b=min(a,b)B．a*b=a+bC．a*b=GCD(a,b)(a,b的最大公约数)02324# 离散数学试题第1 页共4页02324# 离散数学试题 第 2 页 共4页D ．a*b=a(mod b)10.设R 和S 是集合A 上的关系,R ∩S 必为反对称关系的是( ) A ．当R 是偏序关系,S 是等价关系; B ．当R 和S 都是自反关系; C ．当R 和S 都是等价关系; D ．当R 和S 都是传递关系11.设R 是A 上的二元关系,且R ·R ⊆R,可以肯定R 应是( D ) A ．对称关系; B ．全序关系; C ．自反关系; D ．传递关系 12．设R 为实数集，函数f ：R →R ，f(x)=2x ，则f 是（ ） A ．满射函数 B ．单射函数 C ．双射函数 D ．非单射非满射CDACCDAADADB第二部分 非选择题二、填空题1．设论域是{a,b,c}，则(∀x)S(x)等价于命题公式 S(a)∧S(b)∧S(c) ；(x ∃)S(x)等价于命题公式 S(a)∨S(b) ∨S(c) 。

2．设R 为A 上的关系，则R 的自反闭包r(R)= _R ∪A I _ ，对称闭包s(R)= _R ∪R ~。

3．某集合A 上的二元关系R 具有对称性，反对称性，自反性和传递性，此关系R 是 A I _ ，其关系矩阵是 只有主对角线上元素为1 。

三、计算题 1．（4分）如果论域是集合{a,b,c}，试消去给定公式中的量词：)0y x )(x )(y (=+∀∃。

2．用等值演算求下面公式的主析取范式。

)()(P Q Q P ∨⌝→→⌝3．用等值演算法求公式)()(QPQP⌝→↔→⌝的主合取范式。

4．（6分）在偏序集<Z,≤>中，其中Z={1,2,3,4,6,8,12,14}，≤是Z中的整除关系，求集合D={2,3,4,6}的极大元，极小元，最大元，最小元，最小上界和最大下界。

02324# 离散数学试题第3 页共4页5．设集合A={1,2,3,4,5},A上的划分为π＝{{1,2,3},{4,5}},试求：1)写出划分π诱导的等价关系R；M；2)写出关系矩阵R3)画出关系图。

6. 设A＝{a，b，c，d}，R是A上的二元关系，且R＝{<a，b>，<b，a>，<b，c>，<c，d>}，求r(R)、s(R)和t(R)。

解r(R)＝R∪I A＝{<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<b，b>，<c，c>，<d，d>}s(R)＝R∪R-1＝{<a，b>，<b，a>，<b，c>，<c，d>，<c，b>，<d，c>}02324# 离散数学试题第4 页共4页02324# 离散数学试题 第 5 页 共4页R 2＝{<a ，a >，<a ，c >，<b ，b >，<b ，d >} R 3＝{<a ，b >，<a ，d >，<b ，a >，<b ，c >} R 4＝{<a ，a >，<a ，c >，<b ，b >，<b ，d >}＝R 2t (R )＝ii R ∞=1 ＝{<a ，b >，<b ，a >，<b ，c >，<c ，d >，<a ，a >，<a ，c >，<b ，b >，<b ，d >，<a ，d >}7．已知集合A 和B 且|A|=n ，|B|=m ，求A 到B 的二元关系数是多少？A 到B 的函数数是多少？解：因为|P(A ×B)|=2|A ×B|=2|A||B|=2mn ，所以A 到B 的二元关系有2mn 个。

因为|BA|=|B||A|=mn ，所以A 到B 的函数mn 个。

四、证明题1．设R 和S 是二元关系，证明111)(---=S R S R2．设A={a,b,c},R={(a,a),(a,b),(b,c)},验证rs(R)=sr(R)。

3．设R 是A 上的二元关系，试证：R 是传递的当且仅当R R ⊆2，其中2R 表示R R ∙。

4．证明下列结论：（1）R∧⇒P→∨→PQRQ（2）D∧⌝→),→)∧(),((CD∨BAA⇒CBA解：（1）1 P∧Q P附加前提2 P T，1，I23 P∨Q T，2，I14 P∨Q→R P5 R T，3，4，I36 P∧Q→R CP（2）1 ⌝D P假设前提2 D∨A P3 A T，1，2，I54 (A→B)∧(A→C) P5 A→B T，4，I26 B T，3，5，I37 A→C T，4，I28 C T，3，7，I39 B∧C T，6，8 ，合取式10 ⌝（B∧C）P11 （B∧C）∧⌝（B∧C） T，9，10，合取式，矛盾5.已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，02324# 离散数学试题第6 页共4页[a]R∩S=[a]R∩[a]S。

解：∀x∈A，因为R和S是自反关系，所以<x,x>∈R、<x,x>∈S，因而<x,x>∈R∩S，故R∩S是自反的。

∀x、y∈A，若<x,y>∈R∩S，则<x,y>∈R、<x,y>∈S，因为R和S是对称关系，所以因<y,x>∈R、<y,x>∈S，因而<y,x>∈R∩S，故R∩S是对称的。

∀x、y、z∈A，若<x,y>∈R∩S且<y,z>∈R∩S，则<x,y>∈R、<x,y>∈S且<y,z>∈R、<y,z>∈S，因为R和S是传递的，所以因<x,z>∈R、<x,z>∈S，因而<x,z>∈R∩S，故R∩S 是传递的。

总之R∩S是等价关系。

2）因为x∈[a]R∩S⇔<x,a>∈R∩S⇔<x,a>∈R∧<x,a>∈S⇔ x∈[a]R∧x∈[a]S⇔ x∈[a]R∩[a]S所以[a]R∩S=[a]R∩[a]S。

五、应用题1．所有的主持人都很有风度。

李明是个学生并且是个节目主持人。

因此有些学生很有风度。

请用谓词逻辑中的推理理论证明上述推理。

（论述域：所有人的集合）02324# 离散数学试题第7 页共4页。