山东大学离散数学题库及答案.docx

资源描述

《山东大学离散数学题库及答案.docx》由会员分享，可在线阅读，更多相关《山东大学离散数学题库及答案.docx（107页珍藏版）》请在三一办公上搜索。

1、山东大学离散数学题库及答案离散数学题库答案一、选择或填空 1、下列哪些公式为永真蕴含式？( ) (1)Q=QP (2)Q=PQ (3)P=PQ (4)P(PQ)=P 答：， 2、下列公式中哪些是永真式？( ) (1)(PQ)(QR) (2)P(QQ) (3)(PQ)P (4)P(PQ) 答：， 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=PQ (2) PQ=P (3) PQ=PQ (4)P(PQ)=Q (5) (PQ)=P (6) P(PQ)=P 答：， 4、公式x(A(x)B(y，x) $z C(y，z)D(x)中，自由变元是( )，约束变元是( )。答：x,y, x,

2、z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+818，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！答：是，T 是，F 不是是，T 不是不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )答：所有人都不是大学生，有些人不会死 7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则

3、我一定去学校答： QP PQ PQ PQ 8、设个体域为整数集，则下列公式的意义是( )。 (1) x$y(x+y=0) (2) $yx(x+y=0) 答：对任一整数x存在整数 y满足x+y=0存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值： (1) x$y (xy=y) ( ) (2) $xy(x+y=y) ( ) (3) $xy(x+y=x) ( ) (4) x$y(y=2x) ( ) 答： F F F T 10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式 $x(P(x)Q(x)在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (

4、3) 复数 (4) (1)-(3)均成立答： 11、命题“2是偶数或-3是负数”的否定是。答：2不是偶数且-3不是负数。 12、永真式的否定是 (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)-(3)均有可能答： 1 。 13、公式(PQ)(P答：P ，QP ，公式 Q(P(PQ)可化简为。 Q)化简为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

6、=A5 21、若A-B=，则下列哪个结论不可能正确？( ) (1) A= (2) B= (3) AB (4) BA 答： 22、判断下列命题哪个为真?( ) (1) A-B=B-A = A=B (2) 空集是任何集合的真子集 (3) 空集只是非空集合的子集 (4) 若A的一个元素属于B，则A=B 答： 23、判断下列命题哪几个为正确？( ) (1) , (2) , (3) (4) (5) a,ba,b,a,b 答：， 24、判断下列命题哪几个正确？( ) (1) 所有空集都不相等 (2) (4) 若A为非空集，则AA成立。答： 25、设AB=AC，AB=AC，则B( )C。答：= 26、判

7、断下列命题哪几个正确？( ) (1) 若ABAC，则BC (2) a,b=b,a 2 ）(3) P(AB)P(A)P(B) (4) 若A为非空集，则AAA成立。答： 27、，是三个集合，则下列哪几个推理正确： (1) AB，BC= AC (2) AB，BC= AB (3) AB，BC= AC 答： 28、设1,2,3,4,5,6，B=1,2,3，从到B的关系x,y|x=y2，求(1)R (2) R-1 。答：R=, (2) R-1=, 29、举出集合A上的既是等价关系又是偏序关系的一个例子。( ) 答：A上的恒等关系 30、集合A上的等价关系的三个性质是什么？( ) 答：自反性、对称性和传

8、递性 31、集合A上的偏序关系的三个性质是什么？( ) 答：自反性、反对称性和传递性 32、设S=,，上的关系1,2，2,1，2,3，3,4 求(1)RoR (2) R-1 。答：RoR =1,1，1,3，2,2，2,4 R-1 =2,1，1,2，3,2，4,3 33、设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 。答：R=, (2) R-1=,(36 35、设1,2,3,4,5,6，B=1,2,3，从到B的关系x,y|x=y2，求R和R-1的关系矩阵。

9、 100000答：R的关系矩阵=00010000010 R-1的关系矩阵=000100 000000000000036、集合A=1,2,10上的关系R=|x+y=10,x,yA，则R 的性质为。 (1) 自反的 (2) 对称的 (3) 传递的，对称的 (4) 传递的答： 37、设A=2,4,6，A上的二元运算*定义为：a*b=maxa,b，则在独异点中，单位元是( )，零元是( )答：2，6 38、设A=3,6,9，A上的二元运算*定义为：a*b=mina,b，则在独异点中，单位元是( )，零元是( )答：9，3 3 。； 39、设G,*是一个群，则 (1) 若a,b,xG，a*x=b，则x

10、=( )； (2) 若a,b,xG，a*x=a*b，则x=( )。答： a-1*b b 2340、设a是12阶群的生成元，则a是( )阶元素，a是( )阶元素。答： 6,4 41、代数系统是一个群，则G的等幂元是( )。答：单位元 42、设a是10阶群的生成元，则a是( )阶元素，a是( )阶元素。答：5，10 43、群的等幂元是( )，有( )个。答：单位元，1 44、素数阶群一定是( )群, 它的生成元是( )。答：循环群，任一非单位元 45、设G,*是一个群，a,b,cG，则 (1) 若c*a=b，则c=( )；(2) 若c*a=b*a，则c=( )。答： b*a-14

11、3 (2) b 46、是的子群的充分必要条件是( )。答：是群或 a，b G， a*bH，a-1H 或 a,b G，a*bH -147、群A,*的等幂元有( )个，是( )，零元有( )个。答：1，单位元，0 48、在一个群G,*中，若G中的元素a的阶是k，则a的阶是( )。答：k 49、在自然数集N上，下列哪种运算是可结合的？ (1) a*b=a-b (2) a*b=maxa,b (3) a*b=a+2b (4) a*b=|a-b| 答：(2) 50、任意一个具有2个或以上元的半群，它。 (1) 不可能是群 (2) 不一定是群 (3) 一定是群 (4) 是交换群答：(1) 51、6

12、阶有限群的任何子群一定不是。 (1) 2阶 (2) 3 阶 (3) 4 阶 (4) 6 阶答：(3) 52、下列哪个偏序集构成有界格 (1) (2) (3) ） (4) (P(A),) 答：(4) 53、有限布尔代数的元素的个数一定等于。 (1) 偶数 (2) 奇数 (3) 4的倍数 (4) 2的正整数次幂 4 -1答：(4) 54、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图 (2) 树 (3) 平面图 (4) 连通图答：(4) 55、下面给出的集合中，哪一个是前缀码？( ) (1) 0，10，110，101111 (2) 01，001，000，1 (3) b，c，aa，ab

13、，aba (4) 1，11，101，001，0011 答： 56、一个图的哈密尔顿路是一条通过图中( )的路。答：所有结点一次且恰好一次 57、在有向图中，结点v的出度deg(v)表示( )，入度deg(v)表示( )。答：以v为起点的边的条数，以v为终点的边的条数 58、设G是一棵树，则G 的生成树有( )棵。 (1) 0 (2) 1 (3) 2 (4) 不能确定答：1 59、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。答：+-n(n-1)2, n-1 60、一棵无向树的顶点数n与边数m关系是( )。答：m=n-1 61、一个图的欧拉回路是一条通过图中( )的回路

14、。答：所有边一次且恰好一次 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),2n-2 65、一个无向图有生成树的充分必要条件是( )。答：它是连通图 66、设G是一棵树，n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。答

15、： 67、设T=V,E是一棵树，若|V|1，则T中至少存在( )片树叶。答：2 68、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。答：1，树 69、设G是有n个结点m条边的连通平面图，且有k个面，则k等于: 5 (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。答： 70、设T是一棵树，则T是一个连通且( )图。答：无简单回路 71、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 答： 72、设无向图G有18条边且每个顶点的度数都是3，则图G有( )

16、个顶点。 (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 答： 76、在有n个顶点的连通图中，其边数。 (1) 最多有n-1条 (2) 至少有n-1 条 (3) 最多有n条 (4) 至少有n 条答： 77、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为。 (1) 5 (2) 7 (3) 8

17、 (4) 9 答： 78、若一棵完全二元树有2n-1个顶点，则它片树叶。 (1) n (2) 2n (3) n-1 (4) 2 答： 79、下列哪一种图不一定是树。 (1) 无简单回路的连通图 (2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图答： 80、连通图G是一棵树当且仅当G中。 (1) 有些边是割边 (2) 每条边都是割边 (3) 所有边都不是割边 (4) 图中存在一条欧拉路径答：二、求下列各公式的主析取范式和主合取范式： 1、(PQ)R 解：(PQ)R(PQ )R (PR)(QR) 6 (P(QQ)R)(PP)QR) (P

18、QR)(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)(PQR)(PQR)(PQR) (PQR)(PQR) (主析取范式) (PQR)(PQR）(PR)(QR)P (PQR)(PQR) 3、(PQ)(RP) 解：(PQ)(RP) (PQ)(RP) (P

19、Q(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) R) 解：Q(PR) QPR (PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR） Q(PR) (PQR)(PQR)(PQR)(PQR)(PQR) (PQR)(PQR） 5、P(P(QP) 解：P(P(QP) P(P(QP) PP 4、Q(P 7 T (主合取范式) (PQ)(PQ)(PQ)(PQ) 6、(PQ)(RP) 解： (PQ

20、)(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) 7、P(PQ) 解：P(PQ)P(PQ)(PP)Q T(主合取范式) (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）(P

21、QR) (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 解： 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、Q 解：Q 8 (PR)Q (PR)Q (PQ)(RQ) (PQ(RR)(PP)QR) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR)

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

23、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) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(主合取范式) (P(QR)(P(QR) (PQR)(PQR)(原公式否定的主合取范式) (P(QR)(P(QR) (PQR)(PQR)(主析取范式) 9 15、P(P(Q(QR) 解：P(P(Q(QR) P(P(Q(QR) PQR(主合取范式) (PQR) (PQR)(PQR)(PQR)(PQR) (PQR

24、)(PQR)(PQR) (原公式否定的主合取范式) (PQR) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(主析取范式) 16、(PQ)(PR) 解、(PQ)(PR) (PQ)(PR) (合取范式) (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，

25、QR，R，SP=S 证明： (1) R 前提 (2) QR 前提 (3) Q ， (4) PQ 前提 (5) P ， (6) SP 前提 (7) S ， 2、A(BC)，C(DE)，F(D证明： (1) A 前提 (2) A(BC) 前提 (3) BC ， 10 E),A=BF (4) B 附加前提 (5) C ， (6) C(DE) 前提 (7) DE ， (8) F(DE) 前提 (9) F ， (10) BF CP 3、PQ， PR, QS = RS 证明： (1) R 附加前提 (2) PR 前提 (3) P ， (4) PQ 前提 (5) Q ， (6) QS 前提 (7) S ，

26、(8) RS CP， 4、(PQ)(RS)，(QW)(SX)，(WX)，PR = P 证明： P 假设前提 PR 前提 R ， (PQ)(RS) 前提 PQ RS Q ， S ， (QW)(SX) 前提 QW SX W ， X ， WX ， (WX) 前提 (WX)(WX) ， 5、(UV)(MN), UP, P(QS)，Q证明： (1) Q S =M S 附加前提 P(QS) 前提 P ， UP 前提 U ， 11 UV (UV)(MN) 前提 MN (6),(7) M 6、BD，(EF)D，E=B 证明： (1) B 附加前提 (2) BD 前提 (3) D ， (4) (EF)D 前提

27、(5) (EF) ， (6) EF (7) E (8) E 前提 (9) EE ， 7、P(QR)，R(QS) = P(QS) 证明： P 附加前提 Q 附加前提 P(QR) 前提 QR ， R ， R(QS) 前提 QS ， S ， QS CP， P(QS) CP， 8、PQ，PR，RS =SQ 证明： S 附加前提 RS 前提 R ， PR 前提 P ， PQ 前提 Q (5）， SQ CP， 9、P(QR) = (PQ)(PR) 证明： (1) PQ 附加前提 (2) P 附加前提 (3) Q (1),(2) 12 (4) P(QR) 前提 (5) QR (2),(4) (6) R (3

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

29、 B ， (6) C ， (7) DC 前提 (8) D ， (9) AD CP，13、(PQ)(RQ) Q 证明、 (PQ)(RQ) (PQ)(RQ) (PR)Q Q 13 (PR)Q 14、P(QP)P(PQ) 证明、 P(QP) P(QP) (P)(PQ) P(PQ) 15、，证明、 (1) 前提 P (QR) (1) (QR)，SPS (QR) 前提 P ，(3) (5) SP 前提 (6) S (4),(5) 16、P证明、 (1) P 附加前提 P Q，QR，RS P Q 前提 Q ， QR 前提 (5) R ， (6 ) RS 前提 R RR ， 17、用真值表法证明 ()()

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

31、(PQR) (PQR)(PQR)(PQR) 它们有一样的主合取范式，所以它们等价。 20、(PQ)证明、 (PQ(R(QR) P (QR)为T，则PQ和(QR)都为T。即PQ和QR都为T。故PQ，Q和R)都为T，即PQ为T，Q和R都为F。从而P也为F，即P为T。从而(PQ)(QR) P 设(PQ)21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效? 前提: (1) 若A队得第一，则B队或C队获亚军; (2) (3) (4) 若C队获亚军，则A队不能获冠军; 若D队获亚军，则B队不能获亚军; A 队获第一; 结论: (5) D队不是亚军。证明、设A：A队得第一;B: B队获亚军;C: C队获亚军;D: D队获亚军;则前提符号化为A，C符号化为 D。本题即证明 A，C A 前提 A前提 BC ， C A，DB，A；结论A，DB，AD。 A 前提 C ， B 前提 B ， D D ，

展开阅读全文