离散数学题库及复习资料.doc

《离散数学题库及复习资料.doc》由会员分享，可在线阅读，更多相关《离散数学题库及复习资料.doc（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品文档 ?离散数学?题库与答案一、选择或填空数理逻辑局部1、以下哪些公式为永真蕴含式？(A)(1)Q=QP (2)Q=PQ (3)P=PQ (4)P(PQ)=P 答：在第三章里面有公式1是附加律，4可以由第二章的蕴含等值式求出注意与吸收律区别2、以下公式中哪些是永真式？( )(1)(PQ)(QR) (2)P(QQ) (3)(PQ)P (4)P(PQ)答：2，3，4 可用蕴含等值式证明3、设有以下公式，请问哪几个是永真蕴涵式?( )(1)P=PQ (2) PQ=P (3) PQ=PQ (4)P(PQ)=Q (5) (PQ)=P (6) P(PQ)=P答：2是第三章的化简律，3类似附加律，4是假

2、言推理，3，5，6都可以用蕴含等值式来证明出是永真蕴含式4、公式x(A(x)B(y，x) $z C(y，z)D(x)中，自由变元是( )，约束变元是( )。答：x,y, x,z考察定义在公式x A和$x A中，称x为指导变元，A为量词的辖域。在x A和$x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项那么称为自由变元。于是A(x)、B(y，x)和$z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元5、判断以下语句是不是命题。假设是，给出命题的真值。( )(1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。(3) 你喜

3、欢唱歌吗？ (4) 假设7+818，那么三角形有4条边。(5) 前进！ (6) 给我一杯水吧！ 答：1 是，T 2 是，F 3 不是 4 是，T 5 不是 6 不是 命题必须满足是陈述句，不能是疑问句或者祈使句。6、命题“存在一些人是大学生的否认是( )，而命题“所有的人都是要死的的否认是( )。答：所有人都不是大学生，有些人不会死命题的否认就是把命题前提中的量词“换成存在$，$换成，然后将命题的结论否认，“且变或 或变且7、设P：我生病，Q：我去学校，那么以下命题可符号化为( )。(1)只有在生病时，我才不去学校 (2) 假设我生病，那么我不去学校(3)当且仅当我生病时，我才不去学校(4)

4、假设我不生病，那么我一定去学校答：1 注意“只有才和“除非就两者都是一个形式的 2 3 48、设个体域为整数集，那么以下公式的意义是( )。(1) x$y(x+y=0) (2) $yx(x+y=0)答：1对任一整数x存在整数 y满足x+y=02存在整数y对任一整数x满足x+y=09、设全体域D是正整数集合，确定以下命题的真值：(1) x$y (xy=y)()(2) $xy(x+y=y)()(3) $xy(x+y=x) ()(4) x$y(y=2x) ()答：1 F (反证法：假假设存在，那么x- 1*y=0 对所有的x都成立，显然这个与前提条件相矛盾) 2 F 同理 3F 同理 4T对任一整数

5、x存在整数 y满足条件 y=2x 很明显是正确的10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式 $x(P(x)Q(x)在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)-(3)均成立答：1在某个体域中满足不是奇数就是偶数，在整数域中才满足条件，而自然数子整数的子集，当然满足条件了11、命题“2是偶数或-3是负数的否认是 。答：2不是偶数且-3不是负数。12、永真式的否认是 (1) 永真式(2) 永假式(3) 可满足式(4) (1)-(3)均有可能答：2这个记住就行了13、公式(PQ)(PQ)化简为 ，公式 Q(P(PQ)可化简为 。答：P ，QP考查

6、分配率和蕴含等值式知识的掌握14、谓词公式x(P(x) $yR(y)Q(x)中量词x的辖域是 。答：P(x) $yR(y)一对括号就是一个辖域15、令R(x):x是实数，Q(x):x是有理数。那么命题“并非每个实数都是有理数的符号化表示为 。答：x(R(x)Q(x)集合论局部16、设A=a,a，以下命题错误的选项是 。(1) aP(A)(2) aP(A)(3) aP(A)(4) aP(A)答：(2) a是PA的一个元素17、在0 之间写上正确的符号。(1) =(2) (3) (4) 答：(4)空集没有任何元素，且是任何集合的子集18、假设集合S的基数|S|=5，那么S的幂集的基数|P(S)|=

7、 。答：322的5次方 考查幂集的定义，即幂集是集合S的全体子集构成的集合19、设P=x|(x+1)4且xR,Q=x|5x+16且xR,那么以下命题哪个正确 (1) QP(2) QP(3) PQ(4) P=Q答：3Q是集合R，P只是R中的一局部，所以P是Q的真子集20、以下各集合中，哪几个分别相等( )。(1) A1=a,b (2) A2=b,a (3) A3=a,b,a (4) A4=a,b,c(5) A5=x|(x-a)(x-b)(x-c)=0 (6) A6=x|x2-(a+b)x+ab=0答：A1=A2=A3=A6， A4=A5集合具有无序性、确定性和互异性21、假设A-B=，那么以下哪

8、个结论不可能正确？( )(1) A= (2) B=(3) AB (4) BA答：4差集的定义22、判断以下命题哪个为真?( )(1) A-B=B-A = A=B (2) 空集是任何集合的真子集(3) 空集只是非空集合的子集 (4) 假设A的一个元素属于B，那么A=B答：1考查空集和差集的相关知识23、判断以下命题哪几个为正确？()(1) , (2) , (3) (4) (5) a,ba,b,a,b答：2，424、判断以下命题哪几个正确？()(1) 所有空集都不相等 (2) (4) 假设A为非空集，那么AA成立。答：225、设AB=AC，B=C，那么B()C。答：=等于26、判断以下命题哪几个正

9、确？()(1) 假设ABAC，那么BC (2) a,b=b,a (3) P(AB)P(A)P(B) P(S)表示S的幂集(4) 假设A为非空集，那么AAA成立。答：2 27、，是三个集合，那么以下哪几个推理正确：(1) AB，BC= AC (2) AB，BC= AB (3) AB，BC= AC答：1 3的反例 C为0，1，0 B为0，1，A为1 很明显结论不对二元关系局部28、设1,2,3,4,5,6，B=1,2,3，从到B的关系x,y|x=y2求(1)R (2) R-1 答：1R=, (2) R=,考查二元关系的定义，R为R的逆关系，即R=| R29、举出集合A上的既是等价关系又是偏序关系的

10、一个例子。()答：A上的恒等关系30、集合A上的等价关系的三个性质是什么？( )答：自反性、对称性和传递性31、集合A上的偏序关系的三个性质是什么？( )答：自反性、反对称性和传递性(题29，30，31全是考查定义)32、设S=,，上的关系1,2，2,1，2,3，3,4求(1)RR (2) R-1 。答：RR =1,1，1,3，2,2，2,4考查FG =|$t(FG)R-1 =2,1，1,2，3,2，4,333、设1，2，3，4，5，6，是A上的整除关系，求R= ()R=,34、设1,2,3,4,5,6，B=1,2,3，从到B的关系x,y|x=2y，求(1)R (2) R-1 。答：1R=,

11、(2) R=,(3635、设1,2,3,4,5,6，B=1,2,3，从到B的关系x,y|x=y2，求R和R-1的关系矩阵。答：R的关系矩阵= R的关系矩阵=36、集合A=1,2,10上的关系R=|x+y=10,x,yA，那么R 的性质为 。(1) 自反的(2) 对称的 (3) 传递的，对称的 (4) 传递的答：2考查自反 对称 传递的定义代数系统局部37、设A=2,4,6，A上的二元运算*定义为：a*b=maxa,b，那么在独异点中，单位元是( )，零元是( )。答：2，6单位元和零元的定义，单位元：e。x=x 零元：。x=38、设A=3,6,9，A上的二元运算*定义为：a*b=mina,b，

12、那么在独异点中，单位元是( )，零元是( )；答：9，3半群与群局部39、设G,*是一个群，那么(1) 假设a,b,xG，ax=b，那么x=( )；(2) 假设a,b,xG，ax=ab，那么x=( )。答： 1 ab 2 b 考查群的性质，即群满足消去律40、设a是12阶群的生成元， 那么a2是( )阶元素，a3是( )阶元素。答： 6,441、代数系统是一个群，那么G的等幂元是()。答：单位元由a2=a,用归纳法可证an=a*a(n-1)=a*a=a，所以等幂元一定是幂等元，反之假设an=a对一切N成立，那么对n=2也成立，所以幂等元一定是等幂元，并且在群中，除幺元即单位元e外不可能有任何别

13、的幂等元42、设a是10阶群的生成元， 那么a4是( )阶元素，a3是( )阶元素答：5，10假设一个群G的每一个元都是G的某一个固定元a的乘方，我们就把G叫做循环群；我们也说，G是由元a生成的，并且用符号G=表示，且称a为一个生成元。并且一元素的阶整除群的阶43、群的等幂元是()，有()个。答：单位元，1 在群中，除幺元即单位元e外不可能有任何别的幂等元44、素数阶群一定是( )群, 它的生成元是( )。答：循环群，任一非单位元证明如下：任一元素的阶整除群的阶。现在群的阶是素数p，所以元素的阶要么是1要么是p。G中只有一个单位元，其它元素的阶都不等于1，所以都是p。任取一个非单位元，它的阶等

14、于p，所以它生成的G的循环子群的阶也是p，从而等于整个群G。所以G等于它的任一非单位元生成的循环群45、设G,*是一个群，a,b,cG，那么(1) 假设ca=b，那么c=( )；(2) 假设ca=ba，那么c=( )。答：1 b (2) b群的性质46、是的子群的充分必要条件是( )。答：是群 或 a，b G， abH，a-1H 或 a,b G，ab-1H 47、群A,*的等幂元有()个，是()，零元有()个。答：1，单位元，048、在一个群G,*中，假设G中的元素a的阶是k，那么a-1的阶是( )。答：k49、在自然数集N上，以下哪种运算是可结合的？ (1) a*b=a-b(2) a*b=m

15、axa,b(3) a*b=a+2b(4) a*b=|a-b|答：(2)50、任意一个具有2个或以上元的半群，它 。(1) 不可能是群(2) 不一定是群(3) 一定是群 (4) 是交换群答：(1)51、6阶有限群的任何子群一定不是 。(1) 2阶(2) 3 阶 (3) 4 阶 (4) 6 阶答：(3)格与布尔代数局部52、以下哪个偏序集构成有界格 (1) N,(2) Z, (3) 2,3,4,6,12,|整除关系 (4) (P(A),)答：(4)考查幂集的定义53、有限布尔代数的元素的个数一定等于 。(1) 偶数(2) 奇数 (3) 4的倍数 (4) 2的正整数次幂答：(4)图论局部54、设G是

16、一个哈密尔顿图，那么G一定是( )。(1) 欧拉图 (2) 树 (3) 平面图 (4)连通图 答：(4)考察图的定义55、下面给出的集合中，哪一个是前缀码？()(1) 0，10，110，101111(2) 01，001，000，1(3) b，c，aa，ab，aba (4) 1，11，101，001，0011答：256、一个图的哈密尔顿路是一条通过图中( )的路。答：所有结点一次且恰好一次57、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示( )。答：以v为起点的边的条数， 以v为终点的边的条数58、设G是一棵树，那么G 的生成树有( )棵。(1) 0(2) 1(3)

17、2(4) 不能确定答：159、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。答：, n-160、一棵无向树的顶点数n与边数m关系是()。答：m=n-161、一个图的欧拉回路是一条通过图中( )的回路。答：所有边一次且恰好一次62、有n个结点的树，其结点度数之和是()。答：2n-2结点度数的定义63、下面给出的集合中，哪一个不是前缀码( )。(1) a，ab，110，a1b11 (2) 01，001，000，1(3) 1，2，00，01，0210 (4) 12，11，101，002，0011答：(1)64、n个结点的有向完全图边数是( )，每个结点的度数是( )。答：n(n-1),

18、2n-265、一个无向图有生成树的充分必要条件是( )。答：它是连通图66、设G是一棵树，n,m分别表示顶点数和边数，那么(1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。答：367、设T=V,E是一棵树，假设|V|1，那么T中至少存在( )片树叶。答：268、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。答：1， 树69、设G是有n个结点m条边的连通平面图，且有k个面，那么k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。答：170、设T是一棵树，那么T是一个连通且( )图。答：无简单回路71、

19、设无向图G有16条边且每个顶点的度数都是2，那么图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16答：472、设无向图G有18条边且每个顶点的度数都是3，那么图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12答：(4)73、设图G=，V=a，b，c，d，e，E=,那么G是有向图还是无向图？答：有向图74、任一有向图中，度数为奇数的结点有()个。答：偶数75、具有6 个顶点，12条边的连通简单平面图中，每个面都是由()条边围成？(1) 2(2) 4(3) 3(4) 5答：376、在有n个顶点的连通图中，其边数 。(1) 最多有n-1条(2) 至少有n-

20、1 条(3) 最多有n条 (4) 至少有n 条答：277、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，那么其1度顶点为 。(1) 5(2) 7 (3) 8 (4) 9答：478、假设一棵完全二元叉树有2n-1个顶点，那么它 片树叶。(1) n(2) 2n (3) n-1 (4) 2答：179、以下哪一种图不一定是树 。(1) 无简单回路的连通图(2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图答：380、连通图G是一棵树当且仅当G中 。(1) 有些边是割边(2) 每条边都是割边(3) 所有边都不是割边 (4) 图中存在一条欧拉路径

21、答：2数理逻辑局部二、求以下各公式的主析取范式和主合取范式： 1、(PQ)R 解：(PQ)R(PQ )R(PR)(QR) 析取范式(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)主析取范式(PQ)R)(PQR)(PQR)(PQR) (PQR)( PQR)原公式否认的主析取范式(PQ)R(PQR)(PQR)(PQR)(PQR)(PQR)主合取范式2、(PR)(QR)P 解： (PR)(QR)P析取范式(P(QQ)R)(PP)QR)(P(QQ)(RR)(PQR)(PQR)(PQR)(PQR)( PQR)( PQR)(PQR)(PQR) (PQR)

22、(PQR)(PQR)(PQR) (PQR)(PQR) (主析取范式)(PR)(QR)P(PQR)(PQR原公式否认的主析取范式(PR)(QR)P (PQR)(PQR)主合取范式3、(PQ)(RP)解：(PQ)(RP)(PQ)(RP)合取范式(PQ(RR)(P(QQ)R)(PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)主合取范式 (PQ)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)原公式否认的主合取范式(PQ)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)主析取范式4、Q(PR) 解：Q(PR)QPR主合取范式Q(PR)(PQR)(PQR)(PQ

23、R)(PQR)(PQR)(PQR)(PQR原公式否认的主合取范式Q(PR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR主析取范式5、P(P(QP) 解：P(P(QP)P(P(QP)PP T (主合取范式)(PQ)(PQ)(PQ)(PQ)主析取范式6、(PQ)(RP)解： (PQ)(RP)(PQ)(RP)(PQ)(RP)析取范式(PQ(RR)(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)主析取范式(PQ)(RP)(PQR)(PQR)(PQR)(PQR)(PQR)原公式否认的主析取范式(PQ)(RP)(PQR)(PQR)(PQR)(P

24、QR)(PQR)主合取范式7、P(PQ) 解：P(PQ)P(PQ)(PP)QT(主合取范式)(PQ)(PQ)(PQ)(PQ)主析取范式8、(RQ)P解：(RQ)P(RQ )P(RP)(QP) 析取范式(R(QQ)P)(RR)QP)(RQP)(RQP)(RQP)(RQP)(PQR)(PQR)(PQR)主析取范式(RQ)P)(PQR)(PQR(PQR) (PQR)(PQR)原公式否认的主析取范式(RQ)P(PQR)(PQR)(PQR)(PQR)(PQR)主合取范式9、PQ 解：PQPQ主合取范式(P(QQ)(PP)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)主析取范式10、PQ 解

25、： PQ 主合取范式(P(QQ)(PP)Q(PQ)(PQ)(PQ)(PQ(PQ)(PQ)(PQ)主析取范式11、PQ解：PQ主析取范式(P(QQ)(PP)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)主合取范式12、PRQ解：PRQ(PR)Q(PR)Q(PQ)(RQ)合取范式(PQ(RR)(PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)主合取范式PRQ (PQR)(PQR)(PQR)(PQR)(PQR) 原公式否认的主析取范式PRQ(PQR)(PQR)(PQR)(PQR)(PQR)主析取范式13、PQR解

26、：PQR(PQ)R(PQ)R(析取范式)(PQ(RR)(PP)(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式PQR(PQ)R(PQ)R(析取范式)(PR)(QR)(合取范式)(P(QQ)R)(PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)14、(P(QR)(P(QR)解：(P(QR)(P(QR)(P(QR)(P(QR)(PQ)(PR)(PQ)(PR)合取范式(PQ(RR)(P(QQ)R)(PQ(RR)(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(

27、PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)(P(QR)(P(QR)(PQR)(PQR)(原公式否认的主合取范式)(P(QR)(P(QR)(PQR)(PQR)(主析取范式)15、P(P(Q(QR)解：P(P(Q(QR) P(P(Q(QR) PQR(主合取范式)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(原公式否认的主合取范式)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)16、(PQ)(PR)解、(PQ)(PR)(PQ)(PR) (合取范式)

28、(PQ(RR)(P(QQ)R)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主合取范式)(PQ)(PR)(PQ)(PR)P(QR)(合取范式)(P(QQ)(RR)(PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(主析取范式)三、证明：1、PQ，QR，R，SP=S证明：(1) R 前提(2) QR 前提(3) Q 1，2(4) PQ 前提(5) P 3，4(6) SP 前提(7) S 5，62、A(BC)，C(DE)，F(DE),A=BF证明： (1) A 前提(2) A(BC) 前提 (3)

29、BC 1，2(4) B 附加前提(5) C 3，4(6) C(DE) 前提(7) DE 5，6(8) F(DE) 前提(9) F 7，8(10) BF CP 3、PQ， PR, QS = RS证明：(1) R 附加前提(2) PR 前提(3) P 1，2(4) PQ 前提(5) Q 3，4(6) QS 前提(7) S 5，6(8) RS CP，1，84、(PQ)(RS)，(QW)(SX)，(WX)，PR = P证明： 1 P 假设前提2 PR 前提3 R 1，24 (PQ)(RS) 前提5 PQ 46 RS 57 Q 1，58 S 3，69 (QW)(SX) 前提10 QW 911 SX 10

30、12 W 7，1013 X 8，1114 WX 12，1315 (WX) 前提16 (WX)(WX) 14，155、(UV)(MN), UP, P(QS)，QS =M 证明：(1) QS 附加前提（2） P(QS) 前提 （3） P 1，2（4） UP 前提（5） U 3，4（6） UV 5（7） (UV)(MN) 前提 （8） MN (6),(7)（9） M 86、BD，(EF)D，E=B证明：(1) B 附加前提(2) BD 前提 (3) D 1，2(4) (EF)D 前提(5) (EF) 3，4(6) EF 5(7) E 6(8) E 前提(9) EE 7，87、P(QR)，R(QS)

31、= P(QS)证明：1 P 附加前提2 Q 附加前提3 P(QR) 前提4 QR 1，35 R 2，46 R(QS) 前提7 QS 5，68 S 2，79 QS CP，2，810 P(QS) CP，1，98、PQ，PR，RS =SQ 证明：1 S 附加前提2 RS 前提3 R 1，24 PR 前提5 P 3，46 PQ 前提7 Q (5，68 SQ CP，1，79、P(QR) = (PQ)(PR)证明：(1) PQ 附加前提(2) P 附加前提(3) Q (1),(2)(4) P(QR) 前提(5) QR (2),(4)(6) R (3),(5)(7) PR CP,(2),(6)(8) (PQ

32、) (PR) CP,(1),(7)10、P(QR)，QP,SR,P =S证明：1 P 前提2 P(QR) 前提3 QR (1)，(2)4 QP 前提5 Q (1)，(4)6 R (3),(5)7 SR 前提8 S (6)，(7)11、A，AB， AC， B(DC) = D证明：1 A 前提2 AB 前提3 B (1)，(2)4 AC 前提5 C (1)，(4)6 B(DC) 前提7 DC (3)，(6)8 D (5)，(7)12、A(CB)，BA，DC = AD证明：1 A 附加前提(2) A(CB) 前提 (3) CB 1，2(4) BA 前提(5) B 1，4(6) C 3，5(7) DC

33、 前提(8) D 6，7(9) AD CP，1，813、(PQ)(RQ) PRQ证明、(PQ)(RQ) (PQ)(RQ)(PR)Q PRQ(PR)Q14、P(QP)P(PQ)证明、P(QP)P(QP)(P)(PQ)P(PQ)15、PQPR，(QR)，SPS证明、(1) PQPR 前提 2 P (QR) (1) 3 (QR) 前提 4 P 2，(3) (5) SP 前提 (6) S (4),(5)16、PQ，QR，RS P证明、(1) P 附加前提 2 PQ 前提 3 Q 1，2 4 QR 前提 (5) R 3，4 (6 ) RS 前提 7 R 6 8 RR 5，717、用真值表法证明 ()()

34、证明、列出两个公式的真值表：P Q PQ PQQP F FF TT FT TT TF FF FT T由定义可知，这两个公式是等价的。18、PQP(PQ)证明：设P(PQ)为F，那么P为T，PQ为F。所以P为T，Q为F ，从而PQ也为F。所以PQP(PQ)。19、用先求主范式的方法证明(PQ)(PR) (PQR证明：先求出左右两个公式 的主合取范式(PQ)(PR) (PQ)(PR)(PQ(RR)(P(QQ)R) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR) (PQR) (PQR) (PQ)(PR)(PQ(RR)(P(QQ)R) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR