《《离散数学》.doc》由会员分享，可在线阅读，更多相关《《离散数学》.doc（68页珍藏版）》请在金锄头文库上搜索。
1、 离散数学一、选择或填空（数理逻辑部分）1、下列哪些公式为永真蕴含式？()(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）类似附
2、加律，（4）是假言推理，（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) 若我生病
4、，则我不去学校(3)当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1） （注意“只有才”和“除非就”两者都是一个形式的） （2） （3） （4）8、设个体域为整数集，则下列公式的意义是( )。(1) x$y(x+y=0) (2) $yx(x+y=0)答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数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
5、 对所有的x都成立，显然这个与前提条件相矛盾) （2） F （同理） （3）F （同理） （4）T（对任一整数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)
6、 (1)-(3)均有可能答：（2）（这个记住就行了）13、公式(PQ)(PQ)化简为（ ），公式 Q(P(PQ)可化简为（ ）。答：P ，QP（考查分配率和蕴含等值式知识的掌握）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是P（A）的一个元素）17
7、、在0（ ）之间写上正确的符号。(1) =(2) (3) (4) 答：(4)（空集没有任何元素，且是任何集合的子集）18、若集合S的基数|S|=5，则S的幂集的基数|P(S)|=（ ）。答：32（2的5次方 考查幂集的定义，即幂集是集合S的全体子集构成的集合）19、设P=x|(x+1)4且xR,Q=x|5x+16且xR,则下列命题哪个正确（ ） (1) QP(2) QP(3) PQ(4) P=Q答：（3）（Q是集合R，P只是R中的一部分，所以P是Q的真子集）20、下列各集合中，哪几个分别相等( )。(1) A1=a,b (2) A2=b,a (3) A3=a,b,a (4) A4=a,b,c(
8、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答：（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,
9、b,a,b答：（2），（4）24、判断下列命题哪几个正确？()(1) 所有空集都不相等 (2) (4) 若A为非空集，则AA成立。答：（2）25、设AB=AC，B=C，则B()C。答：=（等于）26、判断下列命题哪几个正确？()(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 很明显结论不对）（二元关系
10、部分）28、设1,2,3,4,5,6，B=1,2,3，从到B的关系x,y|x=y2求(1)R (2) R-1 答：（1）R=, (2) R=,（考查二元关系的定义，R为R的逆关系，即R=| R）29、举出集合A上的既是等价关系又是偏序关系的一个例子。()答：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 =|
11、$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 。答：（1）R=, (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）（考查自反 对称 传递的定义）（
12、代数系统部分）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，则在独异点中，单位元是( )，零元是( )；答：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是( )阶元素。答：
13、 6,441、代数系统是一个群，则G的等幂元是()。答：单位元（由a2=a,用归纳法可证an=a*a(n-1)=a*a=a，所以等幂元一定是幂等元，反之若an=a对一切N成立，则对n=2也成立，所以幂等元一定是等幂元，并且在群中，除幺元即单位元e外不可能有任何别的幂等元）42、设a是10阶群的生成元， 则a4是( )阶元素，a3是( )阶元素答：5，10（若一个群G的每一个元都是G的某一个固定元a的乘方，我们就把G叫做循环群；我们也说，G是由元a生成的，并且用符号G=表示，且称a为一个生成元。并且一元素的阶整除群的阶）43、群的等幂元是()，有()个。答：单位元，1 （在群中，除幺元即单位元e
