离散数学模拟习题与解析(18)

离散数学考试题(十八)

一、

选择：（满分20分，每小题2分）

1．下列语句中不是命题的有（ ）

⑴ 9+5

12 ； ⑵ x+3=5；

⑶我用的计算机CPU主频是1G吗？； ⑷ 我要努力学习。 2．命题“我不能一边听课，一边看小说”的符号化为（ ）

⑴ P??Q ； ⑵ ?P?Q；

⑶ ?Q??P ； ⑷ ?(P?Q)。 3．下列表达式正确的有（ ）

⑴ ?(P?Q)??Q； ⑵ P?Q?P ； ⑶ (P?Q)?(P??Q)?P； ⑷ P?(P?Q)?T。 4．n个命题变元可产生（ ）个互不等价的小项。

⑴ n ； ⑵ n2 ； ⑶ 2n ； ⑷ 2n。

5．若公式(P?Q)?(?P?R)的主析取范式为

m001?m011?m110?m111则它的主合取范式为（ ⑴ m001?m011?m110?m111 ； ⑵ M000?M010?M100?M101 ；⑶M001?M011?M110?M111； ⑷ m000?m010?m100?m101 。 6．命题“尽管有人聪明，但未必一切人都聪明”的符号化

（P(x)：x是聪明的，M(x)：x是人） （ ） ⑴ ?x(M(x)?P(x))??(?x(M(x)?P(x))) ⑵ ?x(M(x)?P(x))??(?x(M(x)?P(x))) ⑶ ?x(M(x)?P(x))??(?x(M(x)?P(x))) ⑷?x(M(x)?P(x))??(?x(M(x)?P(x)))

7．设A={?} ，B=Р(Р(A)) 下列（ ）表达式成立。 ⑴ ??B ； ⑵ ????B； ⑶ ??????B； ⑷ ??????B。 8．A是素数集合，B是奇数集合，则A-B=（ ） ⑴ 素数集合； ⑵ 奇数集合； ⑶ ?； ⑷ {2}。

9．集合A={2，3，6，12，24，36}上偏序关系R的Hass图为

则集合B={2，3，6，12}的上确界 。

117

） 离散数学考试题(十八)

B={2，3，6，12}的下界 。 B={6，12，24，36}的下确界 。

B={6，12，24，36}的上界 。

⑴ 2； ⑵ 3； ⑶ 6； ⑷ 12； ⑸ 无。

10．若函数g和f的复合函数gf 是双射，则（ ）一定是正确的。 ⑴ g是入射； ⑵ f是入射； ⑶ g是满射； ⑷ f是满射。 二、

填空：（满分20，每小题2分）

1．设P：它占据空间，Q：它有质量，R：它不断运动，

S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的符号化为 。 2．设A，B是两命题公式，A?B当且仅当

。

3．要证R?C为前提H1,H2,?,Hm的有效结论，运用CP规则

是 。

4．对谓词公式??yP(x,y)??zQ(x,z)???xR(x,y)的自由变元代入

得 。 5．设S={a1,a2,…,a8},Bi是S的子集，则

B31= 。 6．设I为整数集合，R={∣x?y(mod3) 则

[1]= 。

7．偏序集〈Ρ（{a,b}），?〉的Hass图为

。 8．对集合X和Y，设|X|=m ，|Y|=n ，则从X到Y的函数有 个。

9．设R为实数集，S={x|0

f(x)= 为双射。

118

离散数学考试题(十八)

10．设K[N]=

0

，K[(0,1)]= ，则

K[N×(0,1)]= 。

三、

证明：（48分）

1．不构造真值表证明蕴涵式

(Q?(P??P))?(R?(R?(P??P)))?R?Q （7分） 2．用逻辑推演下式

(A?B)?C ，?D ，?C?D ? ?A??B （7分） 3．用CP规则证明

?x(P(x)?Q(X))??xP(x)??xQ(x) （7分）

4．符号化并证明其结论：“所有有理数是实数，某些有理数是整数，因此某些实

数是整数”（设R(x)：x是实数，Q(x)：x是有理数，I(x)：x是整数） （7分）

5． 设R是集合X上的一个自反关系，求证：R是对称的和传递的当且仅当＜a,b＞和＜a,c＞在R中，则有＜b,c＞在R中 (8分)。

6． 设f和g是函数，则f∩g也是函数。 （6分） 7． 证明 [0，1]～（0，1） （6分）

四、（6分）集合S={1，2，3，4，5}，找出S上的等价关系，

此关系能产生划分{{1，2}，{3}，{4，5}}，并画出关系图。

五、（6分）求(Q?P)?(?P?Q)的主合取范式。

119

离散数学考试题(十八)

一、选择：（满分20，每小题2分）

1．⑵ ⑶；2．⑴ ⑷；3．⑴ ⑶；4．⑷；5． ⑵ 6．⑶； 7．⑴ ⑵ ⑶；8．⑷；9．⑷ ⑸ ⑶ ⑸；10．⑵ ⑶。 二、1．S?P?Q?R；2．A?B?T；

3．由前提H1，H2，?，Hm和R推出C即可；4． ??yP(u,y)??zQ(u,z)???xR(x,w)；5．B00011111={a4，a5，a6，a7，a8}； 6．{?，-8，-5，-2，1，4，7，10，?}；7．

8．nm ；9．三、证

1．设R?Q为F，则R为T，Q为F。因P??P为F，所以

Q?(P??Q)为T，R?(P??Q)为F，于是R?(R?(P??Q))为F，因此(Q?(P??P))?(R?(R?(P??P)))为F。

即：(Q?(P??P))?(R?(R?(P??P)))?R?Q成立。 2．

⑴ ?C?D P ⑺ ?A??B T⑹E ⑵ ?D??C T⑴E ⑶ ?D P ⑷ ?C T⑵⑶I ⑸ (A?B)?C P ⑹ ?(A?B) T⑷⑸I

3．?xP(x)??xQ(x)??(?xP(x))??xQ(x)

⑴ ?(?xP(x)) P(附加前提) ⑸ P(c)?Q(c) US⑷ ⑵ ?x(?P(x)) T⑴E ⑹ Q(c) T⑶⑸I ⑶ ?P(c) ES⑵ ⑺ ?xQ(x) EG⑹ ⑷ ?x(P(x)?Q(x)) P ⑻ ?(?xP(x))??xQ(x) CP 4．符号化为：

?x(Q(x)?R(x))，?x(Q(x)?I(x))1?a,b??b???a??arctanx?12 ；10． 。

? ?x(R(x)?I(x))

120

离散数学考试题(十八)

⑴ ?x(Q(x)?I(x)) P ⑹ R(c) T⑷⑸I ⑵ Q(c)?I(c) ES⑴ ⑺ I(c) T⑵I ⑶ ?x(Q(x)?R(x)) P ⑻ R(c)?I(c) T⑹⑺I ⑷ Q(c)?R(c) US⑶ ⑼ ?x(R(x)?I(x)) EG⑻ ⑸ Q(c) T⑵I

5．⑴R是对称的和传递的??R，?R则?R。

?a,b,c?X，若?R，由R对称性有?R，而?R，由R传递性得

?R。

⑵?R，?R则?R? R是对称的和传递的

?a,b,c?X，若?R，因R自反，所以?R，由已知?R，即R具有对

称性。

若?R，?R，由R对称性知?R，再由已知?R 即R具有传递性。

6．f?g?{?x,y?x?domf?x?domg?y?f(x)?g(x)} ?{?x,y?x?domf?domg?y?f(x)?g(x)}

dom(f?g)?{xx?domf?domg,f(x)?g(x)}

若y1≠y2，因f是函数，故必有y1=f(x1)，y2=f(x2)且x1≠x2 所以f?g是函数。

7．证：设A?{0,1,,,?} 令f：[0,1]?(0,1)

2311?1?2,x?0?A;?1?1f(x)??,x??A,n?1,2,?;

n?n?1?x,x?[0,1]?A.??则f是[0,1]?(0,1)的双射函数。所以[0，1]～（0，1） 四、解：

R1={1,2}×{1,2}={<1,1>,<1,2>,<2,1>,<2,2>} R2={3}×{3}={<3,3>}

121

离散数学考试题(十八)

R3={4,5}×{4,5}={<4,4>,<4,5>,<5,4>,<5,5>} R=R1?R2?R3

={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>} 五、解：

(Q?P)?(?P?Q)?(?Q?P)?(?P?Q))?(?Q??P?Q)?(P??P?Q)?F?(P?Q)?(P??Q)?(?P?Q)?(?P??Q)

122

本文来源：https://www.bwwdw.com/article/azfd.html