《离散数学》题库及答案.docx

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

1、离散数学题库及答案 离散数学题库与答案 一、选择或填空 1、下列哪些公式为永真蕴含式？( A ) (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 答：是第三章的化简律，类似附加律，是假言推理，都可以用蕴

2、含等值式来证明出是永真蕴含式 4、公式x(A(x)B(y，x) $z C(y，z)D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+818，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 1 答： 是，T 是，F 不是 是，T 不是 不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P：我生病，Q：我去学校，

3、则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答： 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) ( ) 答：

4、F (反证法：假若存在，则*y=0 对所有的x都成立，显然这个与前提条件相矛盾) F F T 10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式 $x(P(x)Q(x)在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)-(3)均成立 答： 11、命题“2是偶数或-3是负数”的否定是。 2 答：2不是偶数且-3不是负数。 12、永真式的否定是 (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)-(3)均有可能 答： 13、公式(PQ)(PQ)化简为，公式 Q(P(PQ)可化简为。 答：P ，QP 14、谓词公式x(P(x) $yR(y)

5、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) 的一个元素） 17、在0F之间写上正确的符号。 (1) = (2) (3) (4) 答：(4) 18、若集合S的基数|S|=5，则S的幂集的基数|P(S)|=。 答：32 19、设P=x|(x+1)24且xR,Q=x|5x2+16且xR,则下列命题哪个正确 (1) QP (2) QP

6、(3) PQ (4) P=Q 答： 20、下列各集合中，哪几个分别相等( )。 3 (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=，则下列哪个结论不可能正确？( ) (1) A= (2) B= (3) AB (4) BA 答： 22、判断下列命题哪个为真?( ) (1) A-B=B-A = A=B (2) 空集是任何集合的真子集 (3) 空集只是非空集合的子集 (4) 若A的一个元素属于

7、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、判断下列命题哪几个正确？( ) (1) 若ABAC，则BC (2) a,b=b,a (3) P(AB)P(A)P(B) (4) 若A为非空集，则AAA成立。 答： 27、，是三个集合，则下列哪几个推理正确： (1) AB，BC= AC (2) AB，BC= AB (3) AB，BC=

8、AC 答： 的反例 C为0，1，0 B为0，1，A为1 很明显结论不对） 4 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上的等价关系的三个性质是什么？( ) 答：自反性、对称性和传递性 31、集合A上的偏序关系的三个性质是什么？( ) 答：自反性、反对称性和传递性(题29，30，31全是考查定义) 32、设S=,，上的关系1,2，2,1，2,3，3,4 求(1)RoR (2) R-1 。 答：RoR =1,

9、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的关系矩阵。 5 100答：R的关系矩阵=000000010000000 000100 R-1的关系矩阵=10000000000036、集合A=1,2,10上的关系R=|x+y=10,x,yA，则R 的性质为。 (1)

10、 自反的 (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 39、设G,*是一个群，则 (1) 若a,b,xG，a*x=b，则x=( )； (2) 若a,b,xG，a*x=a*b，则x=( )。 答： a-1*b b 40、设a是12阶群的生成元， 则a2是( )阶元素，a3是( )阶元素。 答： 6,4 41、代数系统是一个群，

11、则G的等幂元是( )。 答：单位元 42、设a是10阶群的生成元， 则a4是( )阶元素，a3是( )阶元素 6 答：5，10 43、群的等幂元是( )，有( )个。 答：单位元，1 44、素数阶群一定是( )群, 它的生成元是( )。 答：循环群，任一非单位元 45、设G,*是一个群，a,b,cG，则 (1) 若c*a=b，则c=( )；(2) 若c*a=b*a，则c=( )。 答： b*a-1 (2) b 46、是的子群的充分必要条件是( )。 答：是群 或 a，b G， a*bH，a-1H 或 a,b G，a*b-1H 47、群A,*的等幂元有( )个，是( )，零元有( )个。 答：1

12、，单位元，0 48、在一个群G,*中，若G中的元素a的阶是k，则a-1的阶是( )。 答：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阶有限群的任何子群一定不是。 7 (1) 2阶 (2) 3 阶 (3) 4 阶 (4) 6 阶 答：(3) 52、下列哪个偏序集构成有界格 (1) (2) (3) ） (4) (P(A),) 答：(

13、4) 53、有限布尔代数的元素的个数一定等于。 (1) 偶数 (2) 奇数 (3) 4的倍数 (4) 2的正整数次幂 答：(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，aba (4) 1，11，101，001，0011 答： 56、一个图的哈密尔顿路是一条通过图中( )的路。 答：所有结点一次且恰好一次 57、在有向图中，结点v的出度deg+(v)表示( )，入度d

14、eg-(v)表示( )答：以v为起点的边的条数， 以v为终点的边的条数 58、设G是一棵树，则G 的生成树有( )棵。 (1) 0 (2) 1 (3) 2 (4) 不能确定 答：1 59、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。 8 。 答：n(n-1), n-1 260、一棵无向树的顶点数n与边数m关系是( )。 答：m=n-1 61、一个图的欧拉回路是一条通过图中( )的回路。 答：所有边一次且恰好一次 62、有n个结点的树，其结点度数之和是( )。 答：2n-2 63、下面给出的集合中，哪一个不是前缀码( )。 (1) a，ab，110，a1b11 (2) 01，00

15、1，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) 不能确定。 答： 67、设T=V,E是一棵树，若|V|1，则T中至少存在( )片树叶。 答：2 68、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。 答：1， 树 69、设G是有

16、n个结点m条边的连通平面图，且有k个面，则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 答： 9 70、设T是一棵树，则T是一个连通且( )图。 答：无简单回路 71、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 答： 72、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12 答：(4) 73、设图G=，V=a，b，c，d，e，E=,则G是有向图还是无向图？ 答：有向图 74、任一有向图中，度数为奇数的结点有

17、( )个。 答：偶数 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 (4) 9 答： 78、若一棵完全二元树有2n-1个顶点，则它片树叶。 (1) n (2) 2n (3) n-1 (4) 2 10 答： 79、下列哪一种图不一定是树。 (1) 无简单回路的连通

18、图 (2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图 答： 80、连通图G是一棵树当且仅当G中。 (1) 有些边是割边 (2) 每条边都是割边 (3) 所有边都不是割边 (4) 图中存在一条欧拉路径 答： 二、求下列各公式的主析取范式和主合取范式： 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)(P

19、QR) 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) (主析取范式) 11 (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

20、) (PQR)(PQR)(PQR)(PQR)(PQR) 4、Q(PR) 解：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 T (主合取范式) 12 (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)

21、(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）(PQR) (PQR)(PQR) (RQ)P(PQR)(PQR)(PQR) (PQR)(PQR) 9、PQ 解：PQPQ (P(QQ)(PP)Q) (PQ)(PQ)(PQ)(PQ) 13 (P

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

23、(析取范式) 14 (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(QR)(P(QR) (P(QR)(P(QR) (PQ)(PR)(PQ)(PR) (PQ(RR)(P(QQ)R)(PQ(RR) (P(QQ)R) (PQR)(PQR)(PQR)(PQ

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

25、、(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，QR，R，SP=S 证明： (1) R 前提 (2) QR 前提 (3) Q ， 16 (4) PQ 前提 (5) P ， (6) SP 前提 (7) S ， 2、A(BC)，C

26、(DE)，F(DE),A=BF 证明： (1) A 前提 (2) A(BC) 前提 (3) BC ， (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 ， (8) RS CP， 4、(PQ)(RS)，(QW)(SX)，证明： P 假设前提 17 (WX)，PR = P PR 前提 R ， (PQ)(RS) 前提 PQ RS Q ，

27、S ， (QW)(SX) 前提 QW SX W ， X ， WX ， (WX) 前提 (WX)(WX) ， 5、(UV)(MN), UP, P(QS)，QS =M 证明： (1) QS 附加前提 P(QS) 前提 P ， UP 前提 U ， UV (UV)(MN) 前提 MN (6),(7) M 6、BD，(EF)D，E=B 证明： (1) B 附加前提 18 (2) BD 前提 (3) D ， (4) (EF)D 前提 (5) (EF) ， (6) EF (7) E (8) E 前提 (9) EE ， 7、P(QR)，R(QS) = P(QS) 证明： P 附加前提 Q 附加前提 P(QR)

28、 前提 QR ， R ， R(QS) 前提 QS ， S ， QS CP， P(QS) CP， 8、PQ，PR，RS =SQ 证明： S 附加前提 RS 前提 R ， PR 前提 P ， PQ 前提 Q (5）， 19 SQ CP， 9、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) (PR) CP,(1),(7) 10、P(QR)，QP,SR,P =S 证明： P 前提 P(QR) 前提

29、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) 前提 20 DC (3)，(6) D (5)，(7) 12、A(CB)，BA，DC = AD 证明： A 附加前提 (2) A(CB) 前提 (3) CB ， (4) BA 前提 (5) B ， (6) C ， (7) DC 前提 (8) D ， (9) AD CP， 13、(PQ)(RQ) Q 证明、 (PQ)(RQ) (PQ)(RQ) (PR)Q

30、Q (PR)Q 14、P(QP)P(PQ) 证明、 P(QP) P(QP) (P)(PQ) P(PQ) 15、，(QR)，SPS 证明、 (1) 前提 21 P (QR) (1) (QR) 前提 P ，(3) (5) SP 前提 (6) S (4),(5) 16、PQ，QR，RS P 证明、 (1) P 附加前提 PQ 前提 R 前提 Q ， Q (5) R ， (6 ) RS 前提 R ， R R17、用真值表法证明 ()() 证明、 列出两个公式的真值表： P Q PQ F F F T T F T T T T F F F F T T 由定义可知，这两个公式是等价的。 18、PQP(PQ)

31、证明： 设P(PQ)为F，则P为T，PQ为F。所以P为T，Q为F ，从而PQ也为F。所以PQP(PQ)。 22 19、用先求主范式的方法证明(PQ)(PR) (P 证明： 先求出左右两个公式 的主合取范式 (PQ)(PR) (PQ)(PR) (PQ(RR)(P(QQ)R) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR) (P) (P) (PQ)(PR) (PQ(RR)(P(QQ)R) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR) 它们有一样的主合取范式，所以它们等价。 20、(PQ)(QR) P 证明： 设(PQ)(QR)为T，则PQ和(QR)都为T。即PQ和QR都为T。故PQ，Q和R)都为T，即PQ为T，Q和R都为F。从而P也为F，即P为T。从而(PQ)(QR) P 21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效?