本科离散数学复习题(20120629)

一、填空题1、对于所有的真值指派，命题公式_______________，这种命题叫做重言式。对于所有的真值指派，命题公式_______________，这种命题叫做矛盾式。2、具有_______________________的______________________是命题。3、一个命题标识符如表示确定的命题，就称为_____________，如果命题标识符只表示任意命题的位置标志，就称为______________。4、设有命题“如果天不下雨，我就去游泳”。则其逆换式为__________________________；反换式为______________________________；逆反式为______________________________。5、已知原命题为：“如果天不下雨，我就去。”则该命题的反换式是___________________________________________，逆换式是___________________________________________，逆反式是___________________________________________。其中意义相同的命题是___________________________________。6、已知原命题为：“如果风不大，我就去打羽毛球。”则该命题的反换式是___________________________________________，逆换式是___________________________________________，逆反式是___________________________________________。7、班长组织同学们星期日旅游，征求大家意见。意见如下：①刘同学说：“如果天不下雨，我就去”；②曲同学说：“如果天下雨，我就不去”；③于同学说：“如果我去，天就没下雨”；④张同学说：“如果我不去，天就下雨了”；⑤李同学说：“星期日或者天下雨，或者我去公园”。班长总结共有2种意见，其中_______________的意见相同，而_______________的意见一致。8、命题公式QP的主析取范式是____________________________9、命题公式QP的主合取范式是____________________________10、命题公式((P∧Q)∨R)↑0的对偶式是________________________11、命题公式(P∨Q)→R的对偶式为____________________________12、对于前提QS，RS，R，QP，其有效结论是________________13、对于前提RQp)(，SR，S，其有效结论是_____________________14、用谓词表达命题，必须包括__________和__________两个部分。15、设G(x):x是金子，F(x):x是闪光的，则命题“金子是闪光的，但闪光的不一定是金子”可以符号化为________________________________________16、设C(x):x是计算机，P(x,y):x能做y，I(x):x是智能工作，则命题“并非所有智能工作都能由计算机来做”可以符号化为________________________________________17、设C(x):x是计算机，P(x,y):x能做y，I(x):x是智能工作，则命题“并非所有智能工作都能由计算机来做”可以符号化为________________________________________18、一个谓词公式，如果量词均在全式的开头，而且它们的作用域延伸到整个公式的末尾，则该公式叫做____________________。19、谓词公式)()()(yyRxxQxxP的前束范式为_______________________20、谓词公式)()),(),()((xSzyzRyxQxPx的前束范式为______________21、谓词公式)()()()(xQxxPx的前束范式为______________________22、谓词公式)()()()(xQxxPx的前束范式为_______________________23、通常，一元谓词表达了客体的__________多元谓词表达了客体之间的__________。24、设集合}5,4,3,2,1{},,2|{},,3|{CZkkxxBZxxxA。则CA_______________________，CBA)(_______________________25、设集合}5,4,3,2,1{},,2|{},,3|{CZkkxxBZxxxA。则BB_______________________，)(BCA______________________26、设A={x|100＜x＜200,x=7n＋3,n∈N,x∈N}，则|A|=___________________27、若集合A的基数是10，则其幂集的基数是________________________________28.设A={1,2,3,4,5}S1={{1},{3,5},{2,4}}，S2={{1,2},{3},{3,4,5}}S3={{1},{3},{5},{2,4}}S4={{1,2},{3},{3,4,5}}A上的覆盖集合是_________________，A上的划分集合是_________________。29.序偶x,y=a,b当且仅当_______________30．A={1,2,3,4}上的二元关系R={1,2,2,1,2,4,1,4}具有_______________性质。31．设集合A={1,2,3,4}上的等价关系R={1,1,2,2,3,3,4,4,1,2,2,1,3,4,4,3}，对应A上的一个划分是_______________32、关系R是反自反的，当且仅当在关系矩阵中__________________________33、关系R是反自反的，当且仅当在关系图中____________________________34、关系R是反对称的，当且仅当在关系矩阵中__________________________35、关系R是反对称的，当且仅当在关系图中____________________________36、设R={2,2,3,1,1,2,2,3}，S={1,2,2,2,3,1}则s(R)=_______________________t(R)=______________________37．设集合A={1,2,3}上的关系R={1,2,2,1,3,3}，S={1,3,2,2,3,2}则R·S＝________________________，S·R＝________________________。38、设R={2,2,3,1,1,2,2,3}，S={1,2,2,2,3,1}则SR=_______________________，Rc=_______________________。39、设R是定义在集合A上的一个关系，若R是_________________________________的，则称R为等价关系。40、设r是定义在集合A上的一个关系，若r是______________________________的，则称r为相容关系。41、在偏序集合的一个子集中，如果______________________________，则称这个子集为链。如果______________________________，则称这个子集为反链。42、对于一个偏序集合，如果______________________________，则称其为良序集。43、定义在集合A上的一个关系，若满足______________________________，则称其为偏序关系。二、选择题2、设P：我将去镇上，Q：我有时间。命题“我将去镇上，仅当我有时间时”符号化为（）。AA、P→QB、Q→PC、QPD、﹁Q∨﹁P4、设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（）。BA、﹁P∧﹁QB、﹁P∨﹁QC、﹁(QP)D、QP5、设P：张三可以做这件事，Q：李四可以做这件事。命题“张三或李四可以做这件事”符号化为（）。AA、P∨QB、P∨﹁QC、QPD、﹁(﹁P∨﹁Q)6、命题公式(P∧(P→Q))→Q是（）。CA、矛盾式B、蕴含式C、重言式D、等值式7、P→Q的逆反式是（）。DA、Q→﹁PB、P→﹁QC、﹁Q→PD、﹁Q→﹁P8、﹁P→Q的逆换式是（）。AA、Q→﹁PB、P→﹁QC、﹁Q→PD、﹁Q→﹁P9、已知A是B的充分条件，B是C的必要条件，D是B的必要条件，则A是D的（）。AA、充分条件B、必要条件C、充要条件D、A，B，C都不对10、﹁P→Q的反换式是（）。DA、Q→﹁PB、﹁P→﹁QC、﹁Q→﹁PD、P→﹁Q11、重言式的否定式是（）。BA、重言式B、矛盾式C、可满足式D、蕴含式12、命题公式P→Q∧R的对偶式为（）。DA、P→(Q∨R)B、P∧(Q∨R)C、﹁P∨(Q∧R)D、﹁P∧(Q∨R)13、命题公式P→(Q↓P)是（）。BA、重言式B、可满足式C、矛盾式D、等值式14、P﹁Q（）。DA、﹁P→(P→﹁Q)B、(﹁P∨Q)∧(﹁Q∨P)C、(﹁P∨﹁Q)∧(﹁Q∨P)D、(﹁P∨﹁Q)∧(Q∨P)18、谓词公式(x)(P(x)∨(y)R(y))→Q(x)中量词x的作用域是（）。CA、(x)(P(x)∨(y)R(y))B、P(x)C、P(x)∨(y)R(y)D、P(x),Q(x)19、谓词公式(x)(P(x)∨(y)R(y))→Q(x)中变元x是（）。DA、自由变量B、约束变量C、既不是自由变量也不是约束变量D、既是自由变量也是约束变量20、设谓词P(x):x是奇数，Q(x):x是偶数，谓词公式(x)(P(x)Q(x))在下面哪个论域中是可满足的？（）DA、自然数集B、整数集C、实数集D、以上均不成立21、设C(x):x是运动员，G(x):x是强壮的。命题“没有一个运动员不是强壮的”可符号化为（）。CA、﹁(x)(C(x)﹁G(x))B、﹁(x)(C(x)→﹁G(x))C、﹁(x)(C(x)﹁G(x))D、﹁(x)(C(x)→﹁G(x))22、设A(x):x是人，B(x):x犯错误，命题“没有不犯错误的人”符号化为（）。DA、(x)(A(x)B(x))B、﹁(x)(A(x)→﹁B(x))C、﹁(x)(A(x)B(x))D、﹁(x)(A(x)﹁B(x))23、设Z(x):x是整数，N(x):x是负数，S(x,y):y是x的平方，则“任何整数的平方非负”可表示为下述谓词公式：（）。AA、(x)(y)(Z(x)S(x,y)→﹁N(y))B、(x)(y)(Z(x)S(x,y)→﹁N(y))C、(x)(y)(Z(x)→S(x,y)﹁N(y))D、(x)(Z(x)S(x,y)→﹁N(y))24、令F(x):x是火车，G(y):y是汽车，H(x,y):x比y快。则语句“某些汽车比所有的火车慢”可表示为：（）。BA、(y)(G(y)→(x)(F(x)H(x,y)))B、(y)(G(y)(x)(F(x)→H(x,y)))C、(x)(y)(G(y)→(F(x)H(x,y)))D、(y)(G(y)→(x)(F(x)→H(x,y)))25、设个体域A={a,b}，公式(x)P(x)(x)S(x)在A中消去量词后应为（）。BA、P(