离散数学补充习题.docx

一、填空题：（每空1分，本大题共15分）

1．设A?{2,a,{3},4}，B?{{a},3,4,1}，请在下列每对集合中填入适当的符号：? , ?。

（1）{a} B , (2){a,4,{3}} A。

?0，x是奇数，

2．设A?{0,1}，N为自然数集，f(x)?? 若f：A?A，则f是

?1，x是偶数。

射的，若f：N?A，则f是 射的。

3．设图G=V，E中有7个结点，各结点的次数分别为2，4，4，6，5，5，2，则G中有 条边，根据 。

两个重言式的析取是 ，一个重言式和一个矛盾式的合取是 。

设个体域为自然数集，命题“不存在最大自然数”符号化为 。

6．

7 ． 设 P 、 Q 为 两 个 命 题 ， 其 De-Morden 律 可 表 示 为

?(P?Q)??P??Q，?(P?Q)??P??Q；

8．

二、单项选择题：（每小题1分，本大题共15分）

1．设A?{xx是整数且x2?16}，下面哪个命题为假（ ）。

A、{0,1,2,4}?A ； B、{?3,?2,?1}?A ；

C、??A ； D、{xx是整数且x?4}?A。

2．设A??, B?{?,{?}}，则B－A是（ ）。

A、{{?}} ； B、{?}； C、{?,{?}}； D、?。

下图描述的偏序集中，子集{b,e,f}的上界为（ ）。

A、b,c ； B、a,b ；

C、b ； D、a,b,c。

设f和g都是X上的双射函数，则(f?g)?1为（ c ）。

A、f

5．

6．

7．

?1?g?1 ； B、(g?f)?1 ； C、g?1?f?1 ； D、g?f?1。

8．

9．设V?{a,b,c,d,e,f}，

E?{?a,b?,?b,c?,?c,a?,?a,d?,?d,e?,?f,e?}，则有向图

G??V,E?是（ ）。

A、强连通的； B、单侧连通的； C、弱连通的； D、不连通的。10．下面那一个图可一笔画出（ ）。

在任何图中必定有偶数个（ ）。

A、度数为偶数的结点； B、入度为奇数的结点；

C、度数为奇数的结点； D、出度为奇数的结点。

含有3个命题变元的具有不同真值的命题公式的个数为（ ）。

A、23

； B、32

； C、223 ； D、232 。

下列集合中哪个是最小联结词集（ ）。

A、{?,?}； B、{?,?}； C、{?,?}； D、{?,?,?}。

下面哪个命题公式是重言式（ b ）。

A、(P?Q)?(Q?R) ； B、(P?Q)?P ；

C、(?P?Q)??(P??Q) ； D、?(P?Q)?P 。

在谓词演算中，下列各式哪个是正确的（ ）。

A、?x?yA(x,y)??y?xA(x,y) ； B、?x?yA(x,y)??y?xA(x,y) ；

C、?x?yA(x,y)??y?xA(x,y) ； D、A(a)??xA(x) 。

三、判断改正题：（每小题2分，本大题共20分）

1．设A?{1,2}，B?{a}，则2A?2B?2A?B。（其中2A为?（A） ( )

2．设A?{0,1}，B?{1,2}，则

A2?B?{?0,1,1?,?0,1,2?,?1,0,1?,?1,0,2?}。 （ ）

3．集合A上的恒等关系是一个双射函数。 （ ）

4．（ ）

5． （ ）

6． （ ）

能一笔画出的图不一定是欧拉图。 （ ）

设P，Q是两个命题，当且仅当P，Q的真值均为T时，P?Q的值为T。（ ）

命题公式(P?(P?Q))?Q是重言式。 （ ）

设P(x)：x是研究生，Q(x)：x曾读过大学，命题“所有的研究生都读过大学”符号化为：?x(P(x)?Q(x))。 （ ）

四、简答题：（25分）

1．

2．集合A?{2,3,6,12,24,36}上的偏序关系?为整除关系。设B?{