一、单项选择题（本大题共10小题，每小题2分，共20分）
1．下列命题公式中不是重言式的是（ ）
a．p→(q→r) b．p→(q→p)
c．p→(p→p) d．(p→(q→r))(q→(p→r))
2．设个体域是整数集，则下列命题的真值为真的是（ ）
a．yx(x·y=1) b．xy (x·y≠0)
c．xy (x·y=y2) d．yx(x·y=x2)
3．关于谓词公式（x）(y)(p(x,y)∧q(y,z))∧x)p(x,y),下面的描述中错误的是（ ）
a．（x）的辖域是（y）（p（x,y）∧q(y,z)）
b．z是该谓词公式的约束变元。
c．（x）的辖域是p（x,y） d．x是该谓词公式的约束变元。
4．设有代数系统g=〈a，*〉其中a是所有命题公式的集合，*为命题公式的合取运算，则g的幺元是（ ）
a．矛盾式 b．重言式。
c．可满足式 d．公式p∧q
5．设a={}b=p（p（a）），以下不正确的式子是（ ）
a包含于b b．}}包含于b
c包括于b d包含于b
6．设z是整数集，e=，f：z→e，f（x）=2x，则f（ ）
a．仅是满射 b．仅是入射。
c．是双射 d．无逆函数。
7．设a=，a上二元关系r=，s=，则s-1r-1的运算结果是（ ）
a． b．c． d．
8．在实数集合r上，下列定义的运算中不可结合的是（ ）
a．a*b=a+b+2ab b．a*b=a+b
c．a*b=a+b+ab d．a*b=a-b
9．设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（ ）
a．3 b．4
c．5 d．6
10．设无向图g的边数为m，结点数为n，则g是树等价于（ ）
a．g连通且m=n+1 b．g连通且n=m+1
c．g连通且m=2n d．每对结点之间至少有一条通路。
二、填空题（本大题共10小题，每小题2分，共20分）
11．不能再分解的命题称为至少包含一个联结词的命题称为。
12．在命题演算中，五个联结词的含义是由其表唯一确定的，而不是由其类似的语言的含义确定。
13．使公式（x）（y）（a（x）→b（y））（x）a（x）→（y）b（y））成立的条件是不含有y不含有x。
14．设a为任意集合，请填入适当的运算符，使式子aa=；aa=成立。
15．设a=，r=，则domrranr
16．称集合s是给定非空集合a的覆盖：若s=，其中sia，si≠，i=1，2，…，n，且进一步若则s是集合a的划分。
17．对实数的普通加法和乘法是加法的幂等元是乘法的幂等元。
18．在代数系统〈a，*〉中，a=，*是a上二元运算，则该代数系统的单位元是零元是。
19．设〈a，≤〉是偏序集，若a中都有最小上界和则称a关于偏序≤构成格。
20．若一条路中，所有边均不相同，则此路称作若一条路中所有的结点均不相同，则称此路为。
三、计算题（本大题共5小题，每小题6分，共30分）
21．求命题公式的真值表。
22．试求谓词公式中，x,x,y的辖域，试问r(x,y)和a(x,y)中x,y是自由变元，还是约束变元？
23．求命题公式（p→q）→（q∨p）的主析取范式。
24．设代数系统(z,*)其中z是整数集，二元运算定义为， ，求a的逆元。
25．已知图d(如下图)的邻接矩阵为。
a(d)=
求从v2到v4长度为2和从v3到v3长度为2的通路条数，并将它们具体写出。
四、证明题（本大题共2小题，每小题6分，共12分）
26．设〈,*是半群，其中a*a=b，证明：（1）a*b=b*a；（2）b*b=b。
27．若一棵树恰有2个结点的度数为1，则它必是一条欧拉路。
五、应用题（本大题共3小题，每小题6分，共18分）
28．设i是整数集，<，是ｉ上的二元关系，分别表示小于，大于、等于、小于等于，大于等于，不等于，那么这些关系会满足什么性质？试填写下表。
29. 完成下列推理：只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考。
场，考试才能准时进行。所以，如果考试准时进行，那么天气就好。
30．75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这。
三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场。
总共收入70元，求有多少儿童没有乘坐过其中任何一种。
离散数学试题A卷
2010 至 2011 学年第 2 学期 课程名称 离散数学b考试时间 110 分钟 课程 7304159试卷总分 100 分。考试形式 闭卷学生自带普通计算器 否 一 填空题 每空2分，共30分 1 设e a b c 则 a b c p a p cab a c2 设m x x是人，d x x是长寿...
离散数学试题A卷
2010 至 2011 学年第 2 学期 课程名称 离散数学b考试时间 110 分钟 课程 7304159试卷总分 100 分。考试形式 闭卷学生自带普通计算器 否 一 填空题 每空2分，共30分 1 设e a b c 则 a b c p a p cab a c2 设m x x是人，d x x是长寿...
离散数学试题A卷
中国石油大学 北京 2008 2009学年第二学期。离散数学 期末考试试卷a 班级 姓名 学号 分数 一 判断题 只写 是 或 不是 对 或 错 或 即可，不用写过程及依据。每小题1分，共10分 请问下列命题是否正确？1 命题联结词集是联结词完备集。2 当r和s都是集合a上的反自反关系时，则rs也是...