1、 1 离散数学题库 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？ ( ) (1) Q=Q P (2) Q=P Q (3)P=P Q (4) P (P Q)= P 2、下列公式中哪 些是永真式？ ( ) (1)( P Q) (Q R) (2)P (Q Q) (3)(P Q) P (4)P (P Q) 3、设有下列公式，请问哪几个是永真蕴涵式 ?( ) (1)P=P Q (2) P Q=P (3) P Q=P Q (4)P (P Q)=Q (5) (P Q)=P (6) P (P Q)= P 4、公式 x(A(x)B(y， x) z C(y， z)D(x)中，自由变元是 ( )
2、，约束变元是 ( )。 5、判断下列语句是不是命题。若是，给出命题的真值。 ( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若 7+8 18，则三角形有 4条边。 (5) 前进！ (6) 给我一杯水吧！ 6、命题“存在一些人是大学生”的否定是 ( )，而命题“所有的人都是要死的”的否定是 ( )。 7、设 P：我生病， Q：我去学校，则 下列命题可符号化为 ( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校 (4) 若我不生病，则我一定去学校 8、设个体域为整数集，则下
3、列公式的意义是 ( )。 (1) xy(x+y=0) (2) yx(x+y=0) 9、设全体域 D是正整数集合，确定下列命题的真值： (1) xy (xy=y) ( ) (2) xy(x+y=y) ( ) 2 (3) xy(x+y=x) ( ) (4) xy(y=2x) ( ) 10、设谓词 P(x)： x 是奇数， Q(x)： x 是偶数，谓词公式 x(P(x)Q(x)在哪个个体域中为真 ?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)-(3)均成立 11、命题“ 2是偶数或 -3是负数”的否定是（ ）。 12、永真式的否定是（ ） (1) 永真式 (2) 永假式 (3)
4、 可满足式 (4) (1)-(3)均有可能 13、公式 ( P Q) ( P Q)化简为（ ），公式 Q (P (P Q)可化简为（ ）。 14、谓词公式 x(P(x) yR(y)Q(x)中量词 x的辖域是（ ）。 15、令 R(x):x是实数， Q(x):x 是有理数。则命题“并非每个实数都是有理数”的符号化表示为（ ）。 （集合论部分） 16、设 A=a,a，下列命题错误的是（ ）。 (1) aP(A) (2) a P(A) (3) aP(A) (4) a P(A) 17、 在 0（ ） 之间写上正确的符号。 (1) = (2) (3) (4) 18、若集合 S的基数 |S|=5，则 S的
5、幂集的基数 |P(S)|=（ ）。 19、设 P=x|(x+1)2 4且 xR,Q=x|5 x2 +16 且 xR,则下列命题哪个正确（ ） (1) QP (2) Q P (3) P Q (4) 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 3 21、若 A-B=，则下列哪个结论不可能正确？ ( ) (1) A= (2) B= (3) A B (4) B A 22、判断下列命题哪个为真 ?(
6、 ) (1) A-B=B-A = A=B (2) 空集是任何集合的真子集 (3) 空集只是非空集合的子集 (4) 若 A 的一个元素属于 B，则 A=B 23、判断下列命题哪几个为正确？ ( ) (1) , (2) , (3) (4) (5) a,b a,b,a,b 24、判断下列命题哪几个正确？ ( ) (1) 所有空集都不相等 (2) (4) 若 A为非空集，则 A A成立。 25、设 A B=A C， A B=A C，则 B( )C。 26、判断下列命题哪几个正确？ ( ) (1) 若 A B A C，则 B C (2) a,b=b,a (3) P(A B) P(A) P(B) （ P(
7、S)表示 S的幂集） (4) 若 A 为非空集，则 A A A成立。 27、，是三个集合，则下列哪几个推理正确： (1) A B， B C= A C (2) A B， B C= A B (3) A B， B C= A C （二元关 系部分） 28、设 1,2,3,4,5,6， B=1,2,3，从到 B的关系 x,y |x=y2，求 (1)R (2) R-1 。 29、举出集合 A上的既是等价关系又是偏序关系的一个例子。 ( ) 30、集合 A上的等价关系的三个性质是什么？ ( ) 31、集合 A上的偏序关系的三个性质是什么？ ( ) 32、设 A= , , , ，上的关系 1,2， 2,1，
8、2,3， 3,4 4 求 (1)R R (2) R-1 33、设 1， 2， 3， 4， 5， 6，是 A上的整除关系，求 R= ( )。 34、设 1,2,3,4,5,6， B=1,2,3，从到 B的关系 x,y |x=2y，求 (1)R (2) R-1 。 35、设 1,2,3,4,5,6， B=1,2,3，从到 B的关系 x,y |x=y2，求 R 和 R-1的关系矩阵。 36、集合 A=1,2, ,10上的关系 R=|x+y=10,x,yA，则 R 的性质为（ ）。 (1) 自反的 (2) 对称的 (3) 传递的，对称的 (4) 传递的 （代数结构部分） 37、设 A=2,4,6， A
9、 上的二元运算 *定义为： a*b=maxa,b，则在独异点中，单位元是 ( )，零元是 ( )。 38、设 A=3,6,9， A 上的二元运算 *定义为： a*b=mina,b，则在独异点中，单位元是 ( )，零元是 ( )； （半群与群部分） 39、设 G,*是一个群，则 (1) 若 a,b,x G， a x=b，则 x=( )； (2) 若 a,b,x G， a x=a b，则 x=( )。 40、设 a是 12 阶群的生成元， 则 a2是 ( )阶元素， a3是 ( )阶元素。 41、代数系统 是一个群，则 G的等幂元是 ( )。 42、设 a是 10 阶群的生成元， 则 a4是 (
10、)阶元素， a3是 ( )阶元素。 43、群 的等幂元是 ( )，有 ( )个。 44、素数阶群一定是 ( )群 , 它的生成元是 ( )。 5 45、设 G,*是一个群， a,b,c G，则 (1) 若 ca=b，则 c=( )； (2) 若 c a=b a，则 c=( )。 46、 是 的子群的充分必要条件是 ( )。 47、群 A,*的等幂元有 ( )个，是 ( )，零元有 ( )个。 48、在一个群 G,*中，若 G中的元素 a的阶是 k，则 a-1的阶是 ( )。 49、在自然数集 N上，下列哪种运算是可结合的？（ ） (1) a*b=a-b (2) a*b=maxa,b (3) a
11、*b=a+2b (4) a*b=|a-b| 50、任意一个具有 2个或以上元的半群，它（ ）。 (1) 不可能是群 (2) 不一定是群 (3) 一定是群 (4) 是交换群 51、 6阶有限群的 任何子群一定不是（ ）。 (1) 2 阶 (2) 3 阶 (3) 4 阶 (4) 6 阶 （格与布尔代数部分） 52、下列哪个偏序集构成有界格（ ） (1) （ N,） (2) （ Z,） (3) （ 2,3,4,6,12,|（整除关系） (4) (P(A), ) 53、有限布尔代数的元素的个数一定等于（ ）。 (1) 偶数 (2) 奇数 (3) 4 的倍数 (4) 2 的正整数次幂 （图论部分） 54
12、、设 G是一个哈密尔顿图，则 G一定是 ( )。 (1) 欧拉图 (2) 树 (3) 平面图 (4) 连通图 55、下面给出的集合中，哪一个是前缀码？ ( ) (1) 0， 10， 110， 101111 (2) 01， 001， 000， 1 6 (3) b， c， aa， ab， aba (4) 1， 11， 101， 001， 0011 56、一个图的哈密尔顿路是一条通过图中 ( )的路。 57、在有向图中，结点 v的出度 deg+(v)表示 ( )，入度 deg-(v)表示 ( )。 58、设 G是一棵树，则 G 的生成树有 ( )棵。 (1) 0 (2) 1 (3) 2 (4) 不能
13、确定 59、 n阶无向完全图 Kn 的边数是 ( )，每个结点的度数是 ( )。 60、一棵无向树的顶点数 n与边数 m关系是 ( )。 61、一个图的欧拉回路是一条通过图中 ( )的回路。 62、有 n个结点的树，其结点度数之和是 ( )。 63、下面给出的集合中，哪一个不是前缀码 ( )。 (1) a， ab， 110， a1b11 (2) 01， 001， 000， 1 (3) 1， 2， 00， 01， 0210 (4) 12， 11， 101， 002， 0011 64、 n个结点的有向完全图边数是 ( )，每个结点的度数是 ( )。 65、一个无向图有生成树的充分必要条件是 ( )
14、。 66、设 G是一棵树， n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 67、设 T= V,E是一棵树，若 |V|1，则 T中 至少存在 ( )片树叶。 68、任何连通无向图 G至少有 ( )棵生成树，当且仅当 G 是 ( )，G 的生成树只有一棵。 69、设 G是有 n个结点 m条边的连通平面图，且有 k个面，则 k等于 : (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 70、设 T是一棵树，则 T是一个连通且 ( )图。 71、设无向图 G有 16 条边且每个顶点的度数都是 2，则图 G有
15、( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 72、设无向图 G有 18 条边且每个顶点的度数都是 3，则图 G有 ( )个顶点。 7 (1) 10 (2) 4 (3) 8 (4) 12 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)
16、最多有 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 79、下列哪一种图不一定是树（ ）。 (1) 无简单回路的连通图 (2) 有 n 个顶点 n-1条边的连通图 (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图 80、连通图 G是一棵树当且仅当 G中（ ）。 (1) 有些边是割边 (2) 每条边都是割边 (3) 所有边都不是割
17、边 (4) 图中存在一条欧拉路径 （数理逻辑部分） 二、求下列各公式的主析取范式和主合取范式： 1、 (P Q) R 2、 (P R) (Q R) P 8 3、 ( P Q) (R P) 4、 Q (P R) 5、 P (P (Q P) 6、 (P Q) (R P) 7、 P (P Q) 8、 (R Q) P 9、 P Q 10、 P Q 11、 P Q 12、（ P R） Q 13、（ P Q） R 14、 (P(Q R) ( P ( Q R) 15、 P ( P (Q ( Q R) 16、 (PQ) (P R) 三、 证明： 1、 P Q， Q R， R， S P= S 2、 A (B C
18、)， C ( D E)， F (D E),A=B F 3、 P Q， P R, Q S = R S 4、 (P Q) (R S)， (Q W) (S X)， (W X)， P R = P 5、 (U V) (M N), U P, P (Q S)， Q S =M 6、 B D， (E F) D， E= B 7、 P (Q R)， R (Q S) = P (Q S) 8、 P Q， P R， R S =S Q 9、 P (Q R) = (P Q) (P R) 10、 P ( Q R)， Q P,S R,P = S 9 11、 A， A B， A C， B (D C) = D 12、 A (C B)
19、， B A， D C = A D 13、 (PQ) (R Q) （ P R） Q 14、 P (Q P) P (P Q) 15、 （ P Q） （ P R）， (Q R)， S PS 16、 P Q， Q R， R S P 17、用 真值表法证明 ( ) ( ) 18、 P QP (P Q) 19、用先求主范式的方法证明 (P Q) (P R) (P（ Q R） 20、 (P Q) (Q R) P 21、 为庆祝九七香港回归祖国，四支足球队进 行比赛，已知情况如下，问结论是否有效 ? 前提 : (1) 若 A 队得第一，则 B队或 C队获亚军 ; (2) 若 C 队获亚军，则 A队不能获冠军
20、; (3) 若 D 队获亚军，则 B队不能获亚军 ; (4) A 队获第一 ; 结论 : (5) D 队不是亚军。 22、用推理规则证明 P Q, (Q R),P R不能同时为真。 (集合论部分 ) 四、设，是三个集合，证明： 1、 A (B C) (AB) (AC) 2、 (A B)(A C)=A (BC) 3、 AB=AC， A B=A C，则 C=B 4、 AB=A(B-A) 5、 A=B A B= 6、 AB = AC， AB=AC，则 C=B 7、 AB=AC， A B=A C，则 C=B 10 8、 A (B C) (A B) C 9、 (A B)(A C)=A (BC) 10、
21、A-B=B，则 A=B= 11、 A=(A-B) (A-C) AB C= 12、 (A-B)(A-C)= A B C 13、 (A-B)(B-A)=A B= 14、 (A-B)-C A-(B-C) 15、 P(A)P(B) P(AB) （ P(S)表示 S的幂集） 16、 P(A)P(B)=P(AB) （ P(S)表示 S的幂集） 17、 （ A-B） B=（ AB） -B当且仅当 B= 。 n，则 c的阶整除 m与 n的最大公因子 (m,n)。 五、证明或解答： （数理逻辑、集合论与二元关系部分） 1、设个体域是自然数，将下列各式翻译成自然语言： (1) x y（ xy=1） ; (2) x
22、 y(xy=1); (3) x y (xy=0); (4) x y（ xy=0） ; (5) x y (xy=x); (6) x y（ xy=x） ; (7) x y z (x-y=z) 2、设 A(x,y,z): x+y=z, M（ x,y,z） : xy=z, L(x,y): xy， 个体域为自然数。将下列命题符号化： （ 1）没有小于 0的自然数 ; （ 2） xyz; （ 4）存在 x，对任意 y 使得 xy=y; （ 5）对任意 x，存在 y使 x+y=x。 3、 列出下列二元关系的所有元素： （ 1） A=0,1,2,B=0,2,4,R=|x,y BA ; （ 2） A=1,2,3,4,5,B=1,2,R=|2 x+y 4且 x A 且 yB; （ 3） A=1,2,3,B=-3,-2,-1,0,1,R=|x|=|y|且 x A 且 yB; 4、对任意集合 A,B， 证明：若 AA=BB，则 B=B。
