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

《离散数学》题库与答案一、选择或填空(数理逻辑部分)1、下列哪些公式为永真蕴含式?( A )(1)Q=>Q→P(2)Q=>P→Q(3)P=>P→Q(4)P(PQ)=>P答:在第三章里面有公式(1)是附加律,(4)可以由第二章的蕴含等值式求出(注意与吸收律区别)2、下列公式中哪些是永真式?()(1)(┐PQ)→(Q→R)(2)P→(Q→Q)(3)(PQ)→P(4)P→(PQ)答:(2),(3),(4)可用蕴含等值式证明3、设有下列公式,请问哪几个是永真蕴涵式?()(1)P=>PQ(2)PQ=>P(3)PQ=>PQ(4)P(P→Q)=>Q(5)(P→Q)=>P(6)P(PQ)=>P答:(2)是第三章的化简律,(3)类似附加律,(4)是假言推理,(3),(5),(6)都可以用蕴含等值式来证明出是永真蕴含式4、公式"x((A(x)®B(y,x))Ù$zC(y,z))®D(x)中,自由变元是(),约束变元是()。答:x,y,x,z(考察定义在公式"xA和$xA中,称x为指导变元,A为量词的辖域。在"xA和$xA的辖域中,x的所有出现都称为约束出现,即称x为约束变元,A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y,x)和$zC(y,z)中y为自由变元,x和z为约束变元,在D(x)中x为自由变元)5、判断下列语句是不是命题。若是,给出命题的真值。()北京是中华人民共和国的首都。(2)陕西师大是一座工厂。(3)你喜欢唱歌吗?(4)若7+8>18,则三角形有4条边。(5)前进!(6)给我一杯水吧!答:(1)是,T(2)是,F(3)不是(4)是,T(5)不是(6)不是(命题必须满足是陈述句,不能是疑问句或者祈使句。)6、命题“存在一些人是大学生”的否定是(),而命题“所有的人都是要死的”的否定是()。答:所有人都不是大学生,有些人不会死(命题的否定就是把命题前提中的量词“"换成存在$,$换成"”,然后将命题的结论否定,“且变或或变且”)7、设P:我生病,Q:我去学校,则下列命题可符号化为()。(1) 只有在生病时,我才不去学校(2)若我生病,则我不去学校(3) 当且仅当我生病时,我才不去学校(4)若我不生病,则我一定去学校答:(1)(注意“只有……才……”和“除非……就……”两者都是一个形式的)(2)(3)(4)8、设个体域为整数集,则下列公式的意义是()。(1)"x$y(x+y=0)(2)$y"x(x+y=0)答:(1)对任一整数x存在整数y满足x+y=0(2)存在整数y对任一整数x满足x+y=09、设全体域D是正整数集合,确定下列命题的真值:(1)"x$y(xy=y) ( ) (2)$x"y(x+y=y) ( )(3)$x"y(x+y=x) ( ) (4)"x$y(y=2x) ( )答:(1)F(反证法:假若存在,则(x-1)*y=0对所有的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)(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){a}P(A) (2){a}P(A) (3){{a}}P(A) (4){{a}}P(A)答:(2)({a}是P(A)的一个元素)17、在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中的一部