计科系普本2005级离散数学期中试题及答

1、计科系普本2005级离散数学期中试题（2006学号 姓名 成绩选择题（每小题2分，共30分）1由N 个命题变元组成不等值的命题公式的个数为 （ ）A2N B2N CN 2 D22n 2设P：我将去镇上，Q：我有时间。命题“我将去镇上，仅当我有时间时。”符号化为 （ ）APQ BQP CPQ DQ P3设P:我们划船，Q：我们跑步，命题“我们不能既划船又跑步” 符号化为 （ ）AP Q BP Q C（PQ） DP Q4下列语句中哪个是真命题 （ ）A我正在说谎 B严禁吸烟 C如果1+2=3，那么雪是黑的。 D如果1+2=5，那么雪是黑的。5下面哪个联结词运算不可交换 （ ）A B C D 6命题

2、公式P（Q P）是 （ ）A重言式 B可满足式 C矛盾式 D等值式7命题公式 （PQ） R 的主析取范式中含极小项的个数为 （ ）A8 B3 C5 D08命题公式 （PQ） R 的成真赋值为 （ ）A000，001，110 B001，011，101，111C全体赋值 D无9设F（x）：x 是运动员， G（x）：x 是强壮的。命题“没有一个运动员不是强壮的”可符号化为 （ ）Ax（ F（x） G（x） Bx（ F（x） G（x）C x（ F（x） G（x） D x（ F（x） G（x）10设Z（x）：x是整数，N（x）：x是负数，S（x，y）：y是x的平方，则“任何整数的平方非负”可符号化为 （

3、 ）Ax y（Z（x）S（x，y） N（y） Bx y（Z（x）S（x，y） N（y）Cx y（Z（x）S（x，y） N（y）Dx（Z（x）S（x，y） N（y）11设个体域A= a , b ，公式 x P（x） x S（x）在A中消去量词后应为 （ ）AP（x） S（x） BP（a） P（b）（ S（a）S（b）CP（a） S（b） DP（a） P（b） S（a）S（b）12下面谓词公式哪个是前束范式 （ ） Ax y z （B（x , y） A（z） Bx y B（x , y）C x y x （A（x , y） B（x , y） Dx（A（x , y） y B（y）13. 设A B = ，

4、则应该有 （ ）AB = BB CA B DA B14设M= x | f ( x ) = 0 , N = x | g ( x ) = 0 , 则方程f ( x ) . g ( x )= 0 的解集为 （ ）AM N BM N CM N DM N15设A=a , a , 下列选项错误的是 （ ）A a P（A） B a P（A）C a P（A） D a P（A）填空题（每空2分，共20分）1 A 、B为两个命题公式，A B 当且仅当 。2 任意两个不同极小项的合取为 式，全体极小项的析取式必为 式。3已知命题公式A（p , q , r）的主合取范式为M0 M3 M5 它的主析取范式的编码形式为：

5、 。4对于前提：S Q ，S R ， R ， P Q ，其有效结论为 。5设G（x）：x是金子，F（x）：x是闪光的，则命题：“金子是闪光的，但闪光的不一定是金子”符号化为： 。6对公式 x（P（x） Q（x），其中P（x）：x = 1 ，Q（x）：x = 2 ，当个体域为 1，2 时，其真值为 ，当个体域为 0，1，2 时，其真值为 。7 若集合A的基数 | A | =10，则其幂集的基数 | P（A）| = 。8 已知A= a , b , c , B= c , d ，则A B = .判断题（每小题2分，共20分）1“ 王兰和王英是姐妹”是复合命题。 （ ）2 凡陈述语句都是命题。 （ ）3

6、若 A B：张明和李红都是运动员，则 (A B)：张明和李红都不是运动员。 （ ）4命题公式（P （PQ）Q 是重言式。 （ ）5公式 x（P（x）Q（x） R（y）中， x 辖域是P（x）。 （ ）6xy（P（x）Q（y） x P（x） y Q（y） （ ）7任意一个谓词公式都与一个前束范式等价。 （ ）8若A B = A C ，则B = C 。 （ ）9对每个集合A，都有 A P（A）。 （ ）10若A B ，则 B A 。 （ ）四、解析题（每小题5分，共10分）1. 设N表示自然数集（含 0），R ：NN 。R= | x , y N x+2y=10 ，试求dom（R）、ran（R）对集

7、合S= 0 , 1 , 2 , 3 上的关系R= | x , y S x+y=3 ，写出它的元素，作出对应的关系图及关系矩阵。五、 证明题（每小题10分，共20分）1证明等值式（PQ）（Q P）R R2航海家都教育自己的孩子成为航海家，有一个人教育他的孩子去做飞行员，证明：这个人一定不是航海家。参考答案：选择题 15. D A B D B B C B C A B A C B B填空题A B 为重言式矛盾式重言式m1m2m4m6m7Px( G(x) F(x)y ( F(y) G(y) 1 0210 a , b , d 判断题110 四、解析题（每小题5分，共30分）dom R = 0, 2，4，6，8，10 3分ran R = 0，1，2，3，4，5 2分R = ,2分 1 0 0 0 0 1 0 0 1 0 2 3 0 1 0 0 1 0 0 0 1分2分五、 证明题证：左( PQ