一、 命题逻辑部分。
1．计算真值表、并由此写出主析取与主合取范式。
2．证明 p→(q→r)q→(p→r) ┐r→(q→ ┐p)
3．证明从前提pq，┐(q∨r)可演绎出┐p.
4．证明rs可从前提p(qs)，┐r∨p和q推出。├
5、使用推理规则或归结推理，论证推理形式。
1) pq, rq ,r∨s, sq ├p
2) pq, sq, r, r∨s ├ p
二、 谓词逻辑。
1、 写出谓词的含义、一个谓词公式的解释应包含什么内容？
2、 并非一切劳动都能用机器代替。
解设 l(x): x是一种劳动， m(x): x是一种机器，
r(x, y): x被y代替。命题表示为：
(x) (l(x) (y) (m(y)∧r(x,y)))
3、数学分析中函数f (x)在点a连续的定义为： 对任意的》0, 存在一个》0, 使得对所有x,
若|x – a|<,则 |f (x) –f (a)|<符号化此定义。
解令r(x): x是实数， g(x, y): x大于y。
() r()∧g(, 0)) r()∧g(, 0)∧(x) (r(x)∧g(, x – a|))
g(, f (x) –f (a)|
4、 证明等价式：┐(x)a(x)┐a
5、 证明等价式：(x)(a(x)∧b(x))(x)a(x)∧(x)b(x)
6、 证明蕴含式：(x)(a(x)→b(x))(x)a(x)→(x)b(x)
7、 证明蕴含式：(x)(y)a(x，y)(y)(x)a(x，y)
三、 集合与关系。
1、 ab ┐(ba)
2、 ∪a∪b)=(a)∪(b)
3、定理3.5.1 对于任意集合s，有ss。
证明：设有集合s使s ∈s，由此构造一个单元集，显然s ∈，即不空。由正则公理可知有极小元，而只有元素s，故s∩= 但由假设s ∈s，所以s∩ ≠矛盾。
4、定理3.5.2 对任何集合s1和s2，都有┐(s1∈s2∧s2∈s1)。
证明：设s=，假设有(s1∈s2)∧(s2∈s1)，则s1 ∈(s2 ∩s)且s2 ∈(s1 ∩s)。于是s2 ∩s ≠ s2 ∩s ≠ 而s1与s2都是s的极小元，故与正则公理矛盾。
因此对对任何集合s1和s2，都有┐(s1∈s2∧s2∈s1)
5、一个集合a是传递集当且仅当ap(a)。
6、从集合的观点来定义有序对=,}解释其合理性。
6、设r=，试求r(r)，s(r)和t(r)
7、设r、s、t、w为关系，证明。
1) (rs)-1=r-1s-1
2) rstw rtsw
3) r(st)=(rs) (rt)
4) (rs)-1=s-1r-1
8、设r是实数集合，定义rr上关系q： q 当且仅当 u+y=x+v，证明q是rr上等价关系。
四、 代数部分。
1、定理12.2.5 给定且 | s |＞1。如果θ，e∈s，其中θ和e分别为关于⊙的零元和幺元，则θ ≠e。
2、定理12.2.6 给定及幺元e∈s。如果⊙是可结合的并且一个元素x的左逆元xl-1和右逆元xr-1存在，则xl-1=xr-1。
3、定理12.2.7 给定及幺元e∈s。如果⊙是可结合的并且x的逆元x-1存在，则x-1是惟一的。
4、给定 ~ 且f为其满同态映射，则。
a)如果⊙和*满足结合律，则和也满足结合律。
b)如果⊙和*满**换律，则和也满**换律。
5、定理12.4.1 设与是同类型的且f为其同态映射。对应于f，定义关系ef如下：
xef y：=f(x)= f(y)， 其中x，y∈s
则ef是中的同余关系，并且称ef为由同态映射f所诱导的同余关系。
6、习题。
7、积代数：例题12.6.1.
五、 图论部分。
1、两个图的关系。
2写出dijkstra算法，并计算图中从v1到其他结点的最短链长度。
3、给定pert图，计算关键路径。
4、已知图的邻接矩阵，计算可达矩阵，再计算一个图的强分图，warshall算法。
离散数学复习试卷
一 填空题。1 使得公式p q r 成真的赋值是使得公式p q r 成假的赋值是2 设个体域为d 1,2,3，试消去公式 x p x y q y 中量词的等价式 个元素的集合共有 个不同的划分，4 设a 1,2，求 a p a 5 无向树t有8片树叶，2个3度分枝点，其余的分枝点都是4度结点，问t有...
2019《离散数学》A卷
2012级离散数学课程试题 a卷 合分人复查人。1 设谓词是实数，则语句 没有最小的实数 可符号化为。ab.cd.2.下列语句是真命题的是 a.雪是黑色的，当且仅当5 0b.自然数中存在最大素数。c.今天天气真好呀d.只有5 0，雪才是白色的。3 设，则下列陈述正确的是。abcd.4.设，则 abc...
《离散数学》2019试卷A
电子科技大学二零零九至二零壹零学年第一学期期末考试。离散数学课程考试题卷 120 分钟 考试形式 闭卷考试日期 200 9 年 11月日。课程成绩构成 平时分，期中分，实验分，期末分。一 填空题 每空4分，共20分 1 命题公式的成假赋值为 2 设个体域d为，将谓词公式xyg x,y 中的量词消去后...