《离散数学题库-选题》由会员分享，可在线阅读，更多相关《离散数学题库-选题（46页珍藏版）》请在金锄头文库上搜索。
1、离散数学题库答案1 主要知识点：（1）命题与悖论：我说的是谎话 （2）相容或与排斥或的命题符号化：张三是山东人或浙江人。 （3） “除非 才” 、 “除非否则不” 、 “只有 才” （4）蕴涵式的真值 （前件与后件） （5）命题公式的分类：（6）判定公式是否等值：p(q r) 与(p q)r 与 (p q)r （7）蕴涵等值式 pq pq （8）(p q) r (pr) (q r) （9）判断下列各公式的类型，比如：(p q)pq；(p(pq) r； p(p q) p) q)；p(p q) （10）极小项与极大项、主析取范式与主合取范式 比如：求 (pq)的主析取范式与主合取范式 （11）在自
2、然推理系统中构造推理证明：(1) 前提： pq,qr,p s, s 结论： r(p q) (2) 前提： pq, r q,r s 结论： ps 前提： (p q) r, sp, q 结论： sr 证明：用 附加前提证明法 前提： (p q)r, rs, s ,p 结论：q 证明： 用归谬法 （12）量词及其否定、量词消去 （13）判断下列公式中哪些是永真式？哪些是矛盾式？ (1)x(F(x) G(x) (2)x(F(x) G(x) (3)F(x) (x yG(x,y) xF(x) (4) (xF(x) yG(y) yG(y) （14）一阶逻辑公式的值、前束范式 、推理（ EG 、UG 、EI、
3、UI） （15）集合基本运算、集合等式证明ABAB （16）二元关系的表示方法、相关概念（定义域、值域、逆、复合、限制 与象、幂运算）、基本性质（反）自反、（反）对称、传递） 、闭包的含义 及构造 、等价关系与划分、偏序关系与哈斯图 （17）判断函数是否为单射、满射、双射 （18）二元运算的主要性质、代数系统 （19）半群、独异点、群：元素（逆）的阶的性质、元素的阶与群的阶、 子群、生成子群、相关定理的基本含义、陪集与拉格朗日定理及推论、循 环群及生成元、求循环群子群 （20）图中顶点度的概念、 握手定理 、度数列与可图化（构造图） 、图同构 与等价、 完全图边的个数 、正则图、 割点割边、连
4、通度 、二部图、 图的矩 阵表示、判定欧拉图 、哈密顿图离散数学题库答案2 离散数学题库答案一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？( ) (1)Q=Q P (2)Q=P Q (3)P=PQ (4)P (PQ)= P 答： （1） ， （4）2、下列公式中哪些是永真式？( ) (1)( P Q)(QR) (2)P (QQ) (3)(PQ)P (4)P(PQ) 答： （2） ， （3） ， （4）3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=PQ (2) PQ=P (3) PQ=P Q (4)P(PQ)=Q (5) (PQ)=P (6) P (PQ)= P 答：
5、 （2） ， （3） ， （4） ， （5） ， （6）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 （2） 是，F （3） 不是（4） 是，T （5） 不是（6） 不是离散数学题库答案3 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的
6、否定是 ( )。答：所有人都不是大学生，有些人不会死7、设 P：我生病， Q ：我去学校，则下列命题可符号化为( )。(1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校(3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答： （1）PQ（2）QP（3）QP（4）QP8、设个体域为整数集，则下列公式的意义是( )。(1) x y(x+y=0) (2) yx(x+y=0) 答： （1）对任一整数 x 存在整数 y 满足 x+y=0（2）存在整数 y对任一整数 x 满足 x+y=0 9、设全体域 D是正整数集合，确定下列命题的真值：(1) x y (xy=y) (
7、 ) (2) x y(x+y=y) ( ) (3) xy(x+y=x) ( ) (4) x y(y=2x) ( ) 答： （1） F （2） F （3）F （4）T 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、公式(P Q)(PQ)化
8、简为（） ，公式 Q(P(PQ)可化简为（） 。答：P ，QP 离散数学题库答案4 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) 17、在 0（）之间写上正确的符号。(1) = (2) (3) (4) 答：(4) 18、若集合 S的基数 |S|=5 ，则 S的幂集的
9、基数 |P(S)|= （） 。答：32 19、设 P=x|(x+1)24 且 x R,Q=x|5x2+16 且 x R, 则下列命题哪个正确（）(1) QP (2) QP (3) PQ (4) P=Q 答： （3）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=，则下列哪个结论不可能正确？( ) (1) A= (2) B=(3) AB (4)
10、BA 答： （4）22、判断下列命题哪个为真?( ) 离散数学题库答案5 (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） ， （4）24、判断下列命题哪几个正确？( ) (1) 所有空集都不相等 (2) (4) 若 A为非空集，则A A成立。答： （2）25、设AB=A C，AB=AC，则 B( )C。答：=（等于）26、判断下列命题哪几个正确？( ) (1) 若 A
11、BAC，则 BC (2) a,b=b,a (3) P(A B)P(A)P(B) （P(S)表示 S的幂集）(4) 若 A为非空集，则 A AA成立。答： （2）27、，是三个集合，则下列哪几个推理正确：(1) AB，B C= A C (2) AB，B C= AB (3) A B，BC= AC 答： （1）（二元关系部分）28、 设1,2,3,4,5,6 ， B=1,2,3 ， 从到 B的关系 x,y |x=y2 ，求(1)R (2) R-1 。答： （1）R=, (2) R1=, 29、举出集合 A上的既是等价关系又是偏序关系的一个例子。( ) 离散数学题库答案6 答：A上的恒等关系30、集合
12、 A上的等价关系的三个性质是什么？( ) 答：自反性、对称性和传递性31、集合 A上的偏序关系的三个性质是什么？( ) 答：自反性、反对称性和传递性32、设 S=, , ,，上的关系 1,2 ， 2,1 ， 2,3 ， 3,4 求(1)RR (2) R-1。答：R R = 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
13、 。答： （1）R=, (2) R1=,(36 35、 设1,2,3,4,5,6 ， B=1,2,3 ， 从到 B的关系 x,y |x=y2 ，求 R和 R-1的关系矩阵。答：R的关系矩阵 =000000001000000001R1的关系矩阵 =00000001000000000136、集合 A=1,2, ,10 上的关系 R=|x+y=10,x,yA，则 R 的性质为（） 。(1) 自反的(2) 对称的 (3) 传递的，对称的 (4) 传递的答： （2）（代数结构部分）离散数学题库答案7 37、设 A=2,4,6 ，A 上的二元运算 *定义为： a*b=maxa,b ，则在独异点中，单位元是
14、 ( )，零元是 ( )。答：2，6 38、设 A=3,6,9 ，A 上的二元运算 *定义为： a*b=mina,b ，则在独异点中，单位元是 ( )，零元是 ( )；答：9，3 （半群与群部分）39、设 G,*是一个群，则(1) 若 a,b,x G ，a x=b，则 x=( )；(2) 若 a,b,x G ，a x=a b，则 x=( )。答： （1） a1b （2） b 40、设 a 是 12 阶群的生成元，则 a2是( )阶元素， a3是( )阶元素。答： 6,4 41、代数系统 是一个群，则G的等幂元是 ( )。答：单位元42、设 a 是 10 阶群的生成元，则 a4是( )阶元素， a3是( )阶元素。答：5，10 43、群的等幂元是 ( ) ，有( )个。答：单位元， 1 44、素数阶群一定是 ( )群, 它的生成元是 ( )。答：循环群，任一非单位元45、设 G,*是一个群， a,b,c G ，则(1) 若 c a=b，则 c=( )；(2) 若 c a=b a，则 c=( )。答： （1） b1a (2)
