离散数学综合练习题
一、多项选择题（每题3分，共33分）
1．下列语句中不是命题的有（ ）
⑴ 9+5?12 ； ⑵ x+3=5； ⑶我用的计算机CPU主频是1G吗？ ⑷ 我要努力学习。 2．命题“我不能一边听课，一边看小说”的符号化为（ ）
⑴ P??Q ； ⑵ ?P?Q； ⑶ ?Q??P ； ⑷ ?(P?Q)。 3．下列表达式正确的有（ ）
⑴ ?(P?Q)??Q； ⑵ P?Q?P ； ⑶ (P?Q)?(P??Q)?P； ⑷ P?(P?Q)?T。 4．n个命题变元可产生（ ）个互不等价的极小项。
⑴ n ； ⑵ n2
； ⑶ 2n ； ⑷ 2n
。 5．若公式(P?Q)?(?P?R)的主析取范式为
m001?m011?m110?m111则它的主合取范式为（ ）
⑴ m001?m011?m110?m111 ； ⑵ M000?M010?M100?M101 ；
⑶
M001?M011?M110?M111； ⑷ m000?m010?m100?m101 。
6．命题“尽管有人聪明，但未必一切人都聪明”的符号化 （P(x)：x是聪明的，M(x)：x是人） （ ）
⑴ ?x(M(x)?P(x))??(?x(M(x)?P(x))) ⑵ ?x(M(x)?P(x))??(?x(M(x)?P(x))) ⑶ ?x(M(x)?P(x))??(?x(M(x)?P(x))) ⑷?x(M(x)?P(x))??(?x(M(x)?P(x)))
7．求在1和100之间（1和100包含在内）能被5整除，但不能被4和6整除的数的个数为（ ）
(1) 18； （2）19； （3）20； （4） 21 8．A是素数集合，B是奇数集合，则A-B=（ ）
⑴ 素数集合； ⑵ 奇数集合； ⑶ ?； ⑷ {2}。 9．若函数g和f的复合函数f?g 是双射，则（ ）一定是正确的。 ⑴ g是单射； ⑵ f是单射； ⑶ g是满射； ⑷ f是满射。 10．下列偏序集（ ）能构成格。
11111．设s?{1,2,2,3,3,4,4}，*为普通乘法，则[S，*]是（ ）。
⑴ 代数系统； ⑵ 半群； ⑶ 群； ⑷ 都不是。
二、填空题（每小题2分，共12分）。
1．对谓词公式
??yP(x,y)??zQ(x,z)???xR(x,y)的自由变元代入
得 。 2．由Huffman算法求出的带权为2、3、5、7、8、11的最优树的权为 。 3．设I为整数集合，R={
则集合 B={2，3，6，12}的上确界 。
B={2，3，6，12}的下界 。
B={6，12，24，36}的下确界 。
B={6，12，24，36}的上界 。
三、简答题（每题5分，共25分）
1．设A?{0,1}，B?{a,b,c}，求P(A)?B。 2．今有a,b,c,d,e,f,g7个人，已知下列事实：
a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲日语和汉
语；e会讲德语和意大利语；f会讲法语、日语和俄语；g会讲法语和德语，试问这7
个人要围成]一圈，应如何排座位，才能使每个人都能和他身边的人交谈？ 3．设Z为整数集合，在Z上定义二元运算?，?x,y?Z，
有x?y?x?y?xy，
那么Z与运算?能否构成代数系统？若能，请具体指出是那个代数系统。
4．集合S={1，2，3，4，5}，找出S上的等价关系，此关系能产生划分{{1，2}，{3}，
{4，5}}，并画出关系图。
5．求公式(Q?P)?(?P?Q)的主合取范式。
四、公安人员审问一件盗窃案，查明了以下事实：
（1）罪犯就是A, B, C三人中的一个或一伙； （2）不伙同A，C绝不会作案；
（3）罪犯带着脏物是坐着汽车逃掉的，而B不会开汽车。
现推断出A参与了作案，请问该推断是否合理？（符号化命题,并证明其结论）。（8分）
五、(7分)设集合A??1,2,3,4,5?上的关系为R??(1,2),(2,1),(2,4),(3,4),(3,5)?。求R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R)。
六、(8分)设集合S?{1,2,3}，则S上所有6种不同的置换为：
??123??123??123??123?1????123???,?2????132???,?3????213???,?4????231???,??123??123?5????312???,?6????321???.则?{?1,?2,?3,?4,?5,?6},??构成置换群
（1）求这个群的单位元及每个元素的逆元； （2）计算?1??5,?2??4。
七、(7分)（1）写出下图的邻接矩阵；
（2）求出下图中长度为3的通路有多少条？其中回路有多少条？
v1 v4 v2 v3
离散数学综合练习题
