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

更新时间：2024-03-03 23:15:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

离散数学模拟试题及答案推荐度：
相关推荐

离散数学试卷（十一）

一、填空 20% （每小题 2分）

1、称为命题。 2、命题P→Q的真值为0，当且仅当。 3、一个命题含有4个原子命题，则对其所有可能赋值有种。 4、所有小项的析取式为。 5、令P（x）：x是质数，E（x）：x是偶数，Q（x）：x是奇数，D（x，y）：x除尽y. 则

?x(E(x)??y(D(x,y)?E(y)))的汉语翻译为

。 6、设S={a，b, c} 则S6的集合表示为。 7、P（P(?)）= 。 8、A?B= 。 9、设R为集合A上的关系，则t（R）= 。 10、若R 是集合A上的偏序关系，则R满足。

二、选择 20% （每小题 2分）

1、下列命题正确的有（）。

A、若g,f是满射，则g?f是满射； B、若g?f是满射，则g,f都是满射； C、若g?f是单射，则g,f都是单射；D、若g?f单射，则f是单射。 2、设f，g是函数，当（）时，f=g 。

A、?x?domf 都有 f(x)?g(x)； B、domg?domf 且 f?g； C、f与g的表达式相同； D、domg?domf,rangef?rangef。

3、下列关系，（）能构成函数。

A、f?{?x1,x2?|x1,x2?N且x1?x2?10}； B、f?{?x1,x2?|x1,x2?R,x1?x2}；

C、f?{?x1,x2?|x1,x2?N,x2为小于x1的素数的个数}；

2 68

离散数学试卷（十一）

D、f?{?x,x?|x?R}。

4、下列函数（）满射；（）单射；（）双射（）；

一般函数（）。

A、f:N?N,f(x)?x2?2； B、f:N?N,f(x)?x(mod3)（x除以3的余数）；

C、f:N?{0,1},f(x)???1x?偶数集；D、f:R?R,f(x)?2x?5。

?0x?奇数集5、集合A={1，2，3，4}上的偏序关系为，则它的Hass图为（

6、设集合A={1，2，3，4，5}上偏序关系的Hass图为

则子集B={2，3，4}的最大元（）；最小元（）；极大元（极小元（）；上界（）；上确界（）；下界（）；下确界（ A、无，4，2、3，4，1，1，4，4； B、无，4、5，2、3，4、5，1，1，4，4；C、无，4，2、3，4、5，1，1，4，4； D、无，4，2、3，4，1，1，4，无。 7、设R，S是集合A上的关系，则下列（）断言是正确的。

A、 R,S自反的，则R?S是自反的；B、若R,S对称的，则R?S是对称的；

。

；。

）））离散数学试卷（十一）

C、若R,S传递的，则R?S是传递的；D、若R,S反对称的，则R?S是反对称的 8、设X为集合，|X|=n，在X上有（）种不同的关系。 A、n2； B、2n； C、22； D、2n。 9、下列推导错在（）。 ①?x?y(x?y) ②?y(z?y) ③(z?Cz) ④?x(x?x)

P US① ES② UG③

n2A、②； B、③； C、④； D、无。

10、“没有不犯错误的人”的逻辑符号化为（）。设H（x）：x是人， P（x）：x犯错误。

A、?x(H(x)?P(x))； B、?(?x(H(x)??P(x)))； C、?(?x(H(x)??P(x)))； D、?x(H(x)?P(x))。

三、命题演绎28%

1、（10分）用反证法证明(P?Q)?(P?R)?(Q?S)?S?R。 2、（8分）用CP规则证明P?(Q?R),R?(Q?S)?P?(Q?S)。

3、（10分）演绎推理：所有的有理数都是实数，所有的无理数也是实数，虚数不是实数。因此，

虚数既不是有理数，也不是无理数。

四、

将wff8%

?x(?(?yP(x,y))?(?zQ(z)?R(x)))化为与其等价的前束范式。

五、8%

A={a,b,c,d}，R={,,,}为A上的关系，利用矩阵乘法求R的传递闭包，并画出t（R）的关系图。

离散数学试卷（十一）

六、证明16%

1、（8分）设A={1，2，3，4}，在 P（A）上规定二元关系如下：

R?{?s,t?|s,t? P（A）?(|s|?|t|)}

证明R是P（A）上的等价关系并写出商集P（A）/R。 2、（8分）设f是A到A的满射，且f?f?f，证明f=IA 。

离散数学试卷（十一）

一、填空 20%（每小题2分）

1、能够断真假的阵述句；2、P的真值为1，Q的真值为0；3、24=16；4、永真式； 5、任意两数x、y,如果x是偶数且能除尽y，则y一定是偶数；6、S110={a,b}；

?7、{?,{?},{{?}},{?,{?}}}；8、(A?~B)?(~A?B)；9、?Ri；

i?110、自反性、反对称性、传递性

二、选择 20%（每小题 2分）

题目 1 2 B 3 4 5 C 6 A 7 A 8 D 9 C 10 B、D 答案 A、D

三、命题演绎 28% 1、（10分）证明： ⑴?(S?R) ⑵?S??R ⑶P?Q ⑷?P?Q ⑸Q?S ⑹?P?S ⑺?S?P

C、D C、D；A、D；D；B P（附加前提） T⑴E P T⑶E P T⑷⑸E T⑹E T⑺I T⑵⑻I P T⑽E T⑾E T⑼⑿I

⑻(?S??R)?(P??R) ⑼P??R ⑽P?R ⑾?P?R ⑿?(P??R) ⒀F 2、（8分）

离散数学试卷（十一）

①P

②P?(Q?R) ③Q?R ④R?(Q?S) ⑤Q?(Q?S) ⑥Q?S ⑦P?(Q?S)

P（附加前提） P T①②I P T③④I T⑤E CP

3、证明：设Q（x）：x是有理数，R(x)：x是实数，N(x)：x是无理数， C(x)：x是虚数。前提：?x(Q(x)?R(x)) ?x(N(x)?R(x)) ?x(C(x)??R(x)) 结论：?x(C(x)??Q(x)??N(x)) ⑴?x(Q(x)?R(x)) ⑵Q(c)?R(c) ⑶?x(N(x)?R(x)) ⑷N(c)?R(c) ⑸?x(C(x)??R(x)) ⑹C(c)??R(c) ⑺R(c)??C(c) ⑻Q(c)??C(c) ⑼N(c)??C(c)

⑽(Q(c)??C(c))?(N(c)??C(c)) ⑾C(c)??Q(c)??N(c) ⑿?x(C(x)??Q(x)??N(x))

P US⑴ P US⑶ P US⑸ T⑹E T⑵⑺I T⑷⑺I T⑻⑼I T⑽E UG⑾

离散数学试卷（十一）

四、 8% 解：

?x(?y(?P(x,y))?(?(?zQ(z))?R(x)))??x(?(?y(?P(x,y)?(?(?zQ(z))?R(x)))??x(?y(P(x,y)??z(?Q(z))?R(x)))??x?y?z(P(x,y)??Q(z)?R(x))

五、8%

解：

?0??0??0??0?101001000??1?0??0???0??0??0??0??0??0??0??0?1010MR10100100010001001010MR2?MR?MR0??0??1??0???00???0???01??0??0??0?1??0???0???00??0??1??0?0??0???0???01010101010100100010001000??0??1??0???00???0???00??0??1??0?0??0???0???00??0??1??0?0??0???0???00100010010101010101001001??0?1??0??

MR3?MR2?MR0??1??M0??0??1??0??M1??0??R

MR4?MR3?MR?0??0??0??0?R2

?Mt(R)?MR?MR2?0??0?MR3?MR4??0??0?111011101??1? 1??0??所以t（R）={,,,,,,,,}

关系图为

离散数学试卷（十一）

六、证明16% 1、（8分）

证明：⑴?s? P（A），由于|s|?|s|，所以?s,s??R，即R自反的。

⑵?s,t? P（A），若?s,t??R，则|s|?|t|?|t|?|s|，??t,s??R，R是对称的。 ⑶?s,t,u? P（A），若：?s,t??R且?t,u??R，即：|s|?|t|?|u|

?|s|?|u|,?s,u??R 所以R是传递的。

由⑴⑵⑶知，R是等价关系。

P（A）/R = {[?]R，[{1}]R，[{1，2}]R，[{1，2，3}]R，[{1，2，3，4}]R}

2、（8分）