离散复习资料.docx

离散复习资料.docx

《离散复习资料.docx》由会员分享，可在线阅读，更多相关《离散复习资料.docx（19页珍藏版）》请在冰点文库上搜索。

离散复习资料

离散复习资料（绝密版）

选择填空题

命题常项（命题常元）：

命题的真值不依赖于变量。

命题变项（命题变元）：

命题的真值依赖于变量。

命题连接词的优先级（高到低）：

取反>合取>析取>蕴含>等价。

其中蕴含只有当真中含假时才为假。

即真推出了假。

为假。

合式公式（命题公式，公式）：

基本的命题变项，常项是合式公式。

合式公式经过有限次的命题连接词运算后还是合式公式。

我们常见的都是合式公式。

命题公式的类型：

重言式，矛盾式，可满足式。

∧∨

∀∃≤≥

计算题：

常见的等值演算公式：

长中含短留下短；

长中含反去掉反；

蕴含等值式：

A

B

A`∧B蕴含要逆析

假言易位：

A

B

B`

A`不逆袭就要逆天。

归谬论：

（A

B）∧（A

B`）

A`既说他是真的又说是假的，那么你是真的么？

摩根定律：

整体反变局部反，那么析取和合取就要相互变换。

析取式：

由有限个命题变项或常项及其否定组成析取成的式子。

合取式：

同理。

由简单析取（合取）式再合取（析取）就变成了对应的合取（析取）范式。

由上理解为合取范式=（`∨）∧（∨）∧（∨）∧（`∨）

析取范式=（∧）∨（∧）∨（∧）∨（∧）

∧∨

任意公式都存在对应的范式，但是不唯一。

计算题：

求范式的一般步骤：

1：

去掉

2：

内移或消去`

3：

分配变形

主析取范式：

在析取范式中的简单合取范式全是极小项。

主析取范式=（∧）∨（∧）∨（∧）∨（∧）（∧）为极小项。

主析取范式唯一

推理证明题

判断推理是否正确一般采用两种方法：

1：

等值演算法。

2：

真值表法。

推理定律：

P23

方法：

附加前提证明法：

将结论中的前提放到式子前提中去。

归谬法：

将结论以反变量方式引入。

一阶逻辑：

（选择填空）

∀xAx为指导变项，A为量词的辖域。

求前束范式：

（可能考计算题）

二元关系和函数：

可能用到的选择填空关键词：

空关系，全域关系，恒等关系。

反函数

复合函数

A相当于定义域

在定义域A下的值域

选择填空或后面大题的小问可能会涉及的关系判断

可能涉及画图的

等价关系和偏序关系

考哈斯图：

极大极小最大最小元

函数的性质：

选择填空

单射：

类似于单调

满射：

值域充满给定的值域

图：

可能考的填空题：

欧拉通路：

走遍每个顶点，但每条边只走一次的通路。

欧拉回路：

走遍每个顶点，但每条边只走一次的回路。

判定是否存在欧拉通路回路：

无向图：

回路：

1：

连通图。

2：

无奇度顶点。

通路：

1：

连通图。

2：

恰好两个奇度顶点。

（这两个就是通路的端点）

有向图：

回路：

1：

连通图。

2：

每个顶点入度等于出度。

通路：

1：

连通图

2：

除去两个特殊的顶点外，其他点出度等于入度

3：

这两个特殊的点，一个的入度比出度大一，一个出度比入度大一。

哈密顿通路：

经过每个顶点有且仅有一次的通路。

哈密顿路：

经过每个顶点有且仅有一次的通路。

判断是否存在哈密顿通路回路：

无向图：

哈密顿回路：

1：

p（G-V1）≤|V1|（必要条件）

1：

G中任意两个不相邻顶点度数之和大于顶点数。

哈密顿通路：

1：

p（G-V1）≤|V1|+1（必要条件）

1：

G中任意两个顶点度数之和大于等于顶点数-1

大题：

∧∨

∀∃≤≥