离散数学题库及答案.docx

《离散数学》题库与答案一、选择或填空(数理逻辑部分)1、下列哪些公式为永真蕴含式( )(1) Ø Q=>Q→P (2) Ø Q=>P→Q (3)P=>P→Q (4) Ø P Ù (P Ú Q)=> Ø P答:在第三章里面有公式( 1)是附加律,(4)可以由第二章的蕴含等值式求出(注意与吸收律区别)2、下列公式中哪些是永真式( )(1)(┐P Ù Q)→(Q→ Ø R) (2)P→(Q→Q) (3)(P Ù Q)→P (4)P→(P Ú Q)答:(2),(3),(4) 可用蕴含等值式证明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答:(2)是第三章的化简律,(3)类似附加律,(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) 你喜欢唱歌吗 (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) ØQ ® P (注意“只有……才……”和“除非……就……”两者都是一个形式的) (2) P ® ØQ (3) P « ØQ (4) ØP ® Q8、设个体域为整数集,则下列公式的意义是( )。(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、公式( Ø P Ù Q) Ú ( Ø P Ù Ø Q)化简为( ),公式 Q ® (P Ú (P Ù Q))可化简为( )。答: Ø P ,Q ® P(考查分配率和蕴含等值式知识的掌握)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