第1章命题逻辑。
1．基本概念：命题，成真赋值、成假赋值，真值表，公式的三种类型。
2．用真值表判断公式的类型。
3．重要的基本等值式(16个，常用的有分配律、条件式等值式、德摩根律等)
4．求主析取范式、主合取范式。
例求(pq) (qp)的主析取范式、主合取范式。
5．证明一个等值式的三种证明方法(真值表法、等值演算法、主范式(相同)法)
例证明： q(pr)(pq) r
6．求公式成真成假赋值、判断公式类型的计算方法(真值表法、等值演算法、主范式法)
7．真值表与主析取范式、主合取范式的相互转换。
8. 推理定律(九条)
9．自然推理系统中推理的证明(四种证明方法：直接证明法、附加前提证明法、归谬法、消解法)
例证明： pq, pr, qs rs
*10. 综合应用题（见习题）
第2章谓词逻辑。
1．谓词逻辑公式及解释。
2．封闭的公式及性质，重言式、矛盾式的代换实例的性质。
3．进行等值演算的谓词逻辑等值式(四类)、转换规则(三种)
4．求前束范式的计算。
5．构造谓词逻辑推理的证明。
例证明 x(f(x) g(x)) xf(x)zg(z)
第3章集合与关系。
1．用容斥原理进行计算。
2．用文氏图表示和验证集合等式。
3．重要集合恒等式（分配律、德摩根律、吸收律等）
4．笛卡儿集a×b，二元关系，集合a上的全域关系ea、恒等关系ia，5．关系r的逆、两关系的复合及其计算，关系的自反性、对称性、反对称性、传递性概念。
6. 关系的自反闭包、对称闭包、传递闭包的计算。
7．等价关系、划分的概念，等价关系与划分的转换； 偏序关系，极小元、极大元、上界、下界。
8．证明一个关系是等价关系；求一个等价关系的所有等价类。
9．画出一个偏序集的哈斯图。
例设a=, 为a上的整除关系，画出偏序集 的哈斯图。
第3章代数系统。
1．基本概念：二元运算，交换律、结合律、分配律，单位元、零元、逆元。
2．单位元、零元、逆元的唯一性。
3．常见半群的单位元、零元、逆元。
4．求一个二元运算的单位元，证明x的逆元为y
5．半群、独异点、群的概念，同态、同构概念。
6．子群的判定(三个判定定理)，群的基本性质。
例设g为群，ag. 证明 na=为子群。
7. （有限群的）拉格朗日定理及两个推论。
8. 求循环群的所有生成元（分无限群、有限群两种情形）
9. 置换群及其单位元、逆置换。
第4章图论。
1．图的各种基本概念(较重要的有：简单图、多重图，各种度，完全图，图的同构，连通图，连通分支等)
2．握手定理。
3．图的关联矩阵、邻接矩阵，邻接矩阵a的幂am的意义。
4．warshall算法（判断连通性或传递性）
5．欧拉图及哈密顿图相关概念欧拉回路、欧拉通路存在的充要条件。
6．哈密顿通路、哈密顿回路的必要条件和充分条件及应用。
7．平面图与对偶图极大平面图平面图的欧拉公式 *powell着色算法。
例 8．树及相关概念，树的性质图的生成树。
*最小生成树的求法(kruskal算法，prim算法)
例。9．求最短路长度及路线（dijkstra算法、动态规划法） 例。
*10. 最优树及最佳前缀码的求法(huffman算法)
例。11. 求最大流的edmonds-karp算法。
离散数学2019秋复习本科
一 命题逻辑部分。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...
离散数学复习试卷
一 填空题。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...