离散数学 Q&A

本篇又称为《30分钟离散数学从入门到被锁在门里》，《降金忠三十八问》。

金忠三十八问的链接
要是看了这篇文章然后挂科了请不要怪我。

命题演算的推理理论

命题演算的假设推理证明方法是什么？

也叫自然推理系统🙃
注意以下知识点：

反证法
分离规则，拒取规则
化简

2010年例题：
已知公理
$ A: (P \wedge Q) \rightarrow P$
$ B: (P \wedge Q) \rightarrow Q$
$ C: P\rightarrow (Q\rightarrow (P \wedge Q))$
及分离规则和代入规则，试用假设推理证明下面公式为本系统的定理:
$ (P\rightarrow R) \rightarrow (((Q\rightarrow S) \wedge (P\wedge Q))\rightarrow (S \wedge R)) $

证明： PPT03-59

命题演算的归结推理证明方法是什么？

$A \rightarrow B$，归结为$A \wedge \neg B$。
归结证明过程：

建立子句集
归结…

若干重要的归结规则：

父辈子句	归结式	说明
$P$和$\neg P\vee Q$	$Q$	三段论
$P\vee Q$和$\neg P\vee Q$	$Q$	子句合并
$P\vee Q$和$\neg P\vee \neg Q$	$\neg P\vee P$或$\neg Q\vee Q$	重言式
$\neg P$和 $P$	□	空子句归结结束
$P\vee Q$和$\neg Q\vee \neg R$	$P \vee \neg R$	一般归结

在命题演算归结推理证明过程中容易犯的错误有哪些？

信仰不坚定
对结论没有取否定

谓词演算基础

在知识翻译时，紧跟在量词之后的主联结词是怎么规定的？

紧跟在全称量词$\forall x$之后的主联结词为“$\rightarrow$”，
紧跟在存在量词$\exists x$之后的主联结词为“$\wedge $”。

翻译常见错误：

量词后的主联结词错误
将集合名词简单化为常个体. 例如,“人”是集合名词
引入谓词来限定常个体. 例如,“我”是常个体
谓词中含有联结词

谓词演算公式的前束范式是什么？

改名规则：自由变元不能改名。改名前后不能改变变元的约束关系。新名字未被使用。
代入规则：处处进行。不能改变原式和代入式的约束关系。可以对谓词填式或命题变元进行。
书P39-例3.
前束范式：谓词演算公式中的一切量词都在公式的最前面，且其作用域一直衍生到公式的末端。
求前束范式四步：

利用等值公式删去$\rightarrow$和$\leftrightarrow$等;
否定深入
改名
前移量词
书45-例4

谓词演算公式的SKOLEM(斯柯伦)标准形是什么？

SKOLEM标准形：仅含有全称量词的前束范式。
求SKOLEM标准形的步骤：

求前束范式。
从左到右逐个处理前束范式中的存在量词：假设这个存在量词前面有n个全称量词，就把公式中对应的变元化为n元函数f(…)。(n == 0时，引入常量a)
书P46-例5

谓词演算的推理理论

此部分内容需要补充

谓词演算的假设推理证明方法是什么？

存在量词的删除、引入。
全称量词的消去、引入。
全0规则

然后书上乱七八糟的解释一大堆。。
如果不大冷静了，快去刷题。

常见错误：
PPT06-45

谓词演算的归结推理证明方法是什么？

置换准则：置换必须处处进行。要求没有变量被含有同一变量的项代替。
错误的例子：
$P(x,g(x),b)$置换为$P(a,g(x),b)$。错误原因：没有处处进行。
$P(x,g(x),b)$置换为$P(f(x),g(f(x)),b)$。错误原因：x被含有同一变量的项代替了。

谓词演算的归结证明方法类似前面命题演算的归结推理证明方法，即将目标公式(结论)的否定加入公式集中，归结出空子句。

霍恩子句逻辑程序？ 三十八问里没有这一条但还是去看看吧 ~~（我猜今年不考）~~

递归函数论

把函数化为(m,n)标准迭置的方法是什么？

这道题年年都考。
设有一个$m$元函数 $f(x_1, x_2, \cdots , x_m)$ , $m$个$n$元函数$g_1{\{ \cdots \}}$，$g_2{\{ \cdots \}}$，$g_m{\{ \cdots \}}$。由$f$和$g$如下作出的函数： $$h(x_1,x_2,\cdots ,x_n) = f(g_1{\{x_1,\cdots ,x_n\}},g_2{\{x_1,\cdots ,x_n\}},g_n{\{x_1,\cdots ,x_n\}})$$ 称为$(m,n)$标准迭置。简记为： $$h = f(g_1,g_2,\cdots ,g_n)$$

例如：$h(x_1,x_2,x_3)=f(3,g_1(x_1,2),g_2(x_1,x_2),x_3)$

解：
$h(x_1,x_2,x_3)=f(h_1,h_2,h_3,h_4)$ 其中，
$h_1(x_1,x_2,x_3)=S^3OI_{31}(x_1,x_2,x_3)$ $h_2(x_1,x_2,x_3)=g_1(I_{31}(x_1,x_2,x_3),S^2OI_{32}(x_1,x_2,x_3))$ $h_3(x_1,x_2,x_3)=g_2(I_{31}(x_1,x_2,x_3)，I_{32}(x_1,x_2,x_3))$ $h_4(x_1,x_2,x_3)=I_{33}(x_1,x_2,x_3)$ 故函数$h_1(x_1,x_2,x_3)$是由函数$h_1,h_2,h_3,h_4$对$f$作$(4，3)$迭置而得。

$h(x_1,x_2,x_3) = f(S^3OI_{31},g_1(I_{31},S^2OI_{32}),g_2(I_{31},I_{32}),I_{33})$

集合关系

什么是集合的包含关系？

you know…

集合的基本运算有哪些？

并、交、差、补，对称差。
不作详细说明。

$A×B$是什么？

笛卡尔积集。
$$A×B={(a,b)|a\in A,b\in B}$$

$2^A$是什么

幂集合。也记为$\rho (A)$。
$\rho (\varnothing )={\varnothing }$ 。
$\rho ({\varnothing })={\varnothing ,{\varnothing } }$。
$\rho ({a,b })={\varnothing ,a,b,{a,b } }$。

集合等式的证明方法有哪些？形如($A=B$)

证明$A \subseteq B$且$B \subseteq A$。即证明对于任何$x \in A$,有$x \in B$，并且反过来也成立。
使用集合的运算。

什么是二元关系的自反性、反自反性、对称性、反对称性和传递性？

自反性：$\forall x \in A$,有$(x,x)\in R$
反自反性： $\forall x \in A$，有$(x,x)\notin R$
对称性 ：$\forall x,y \in A$,若$(x,y)\in R$，则$(y,x)\in R$
反对称性：$\forall x,y \in A$,若$(x,y)\in R$，且$(y,x)\in R$，则$x=y$
传递性：$\forall x,y,z \in A$,若$(x,y)\in R$，且$(y,z)\in R$，则$(x,z)\in R$

空关系具有反自反性，对称性，反对称性，传递性。
书P102第二张表格比较有帮助。

什么是等价关系？什么是集合的划分？两者有什么联系？

什么是函数的单射性、满射性、双射性？

函数的复合=关系的复合,但记号顺序相反。
额这里先跳过一些。（一些？

图树

简单无向图的定义是什么？补图的定义是什么？

无向图：设$G=(V,E)$ 是一个无向图，若其中$V$是一个非空有限集合，$E$是一个集合，$E$中的元素为$V$中 仅含二个元素 的多重子集。
简单图：没有多重边，没有自环，没有孤立点的图。
补图：设$G=(V,E)$是一个图，它没有自环和多重边。$\tilde{G}=(V,E’)$ 其中$E’={ {u,v} \mid u\neq v, u, v\in V, {u,v}\notin E}$ ，则称$\tilde{G}$为$G$的补图。
自互补图：一个无向简单图如果同构于它的补图，则称这个图为自互补图。

握手定理是什么？

$$\sum\limits_{v\in V} d(v)=2|E|$$

推论：任何一个无向图，度数为奇数的顶点有偶数个。
类似结论：

$$\sum\limits_{v\in V} d_{in}(v)= \sum\limits_{v\in V} d_{out}(v)=|E|$$

什么是连通性？什么是连通分支？

简单通路：它的每一条边都不重复出现。
初等通路：它的每一个顶点都不重复出现。
连通图：$G=(V,E)$是一个无向图，若$G$中任意两个不同的顶点之间在$G$中都有通路存在，则称$G$是一个连通图，否则称$G$为不连通图。
有向连通：称一个有向图是连通的，如果去掉边的方向后所得无向图是连通的。
单侧连通：一个有向图任意二点之间都有单向通路。
强连通：如果一个有向图任意二点之间都有双向的通路，则称为强连通图。
连通分支：
设$G$为一个无向图, $R$是$G$中顶点之间的连通关系, 按着$R$可将$V(G)$划分成$k(k≥1)$个等价类,记成
$V_1,V_2,···,V_k,$
称由它们导出的子图$G[V_1],G[V_2],…,G[V_k]$ 为$G$的连通分支。

欧拉图的充分必要条件是什么？

欧拉通路：经过图中每条边一次且一次的通路。
具有欧拉回路的图叫欧拉图。

(一笔画)定理：一个没有孤立点的无向图具有欧拉通路，当且仅当它是连通的，并且或者没有奇数度的顶点，或者有且仅有两个奇数度的顶点。

定理：一个无向图有欧拉回路，当且仅当所有顶点均为偶数度。
德布鲁因序列问题

哈密尔顿图的充分条件是什么？必要条件是什么？

圈：初等回路。
哈密尔顿通路：经过图中每个顶点一次且一次的通路。
哈密尔顿圈：经过图中每个顶点一次且一次的圈。
哈密尔顿图：含有哈密尔顿圈的图。

必要条件：
若$G=(V,E)$ 是一个哈密尔顿图，则对于$V$的每一个非空子集$S$，均有$$W(G－S) ≤|S|$$
其中$W(G－S)$表示图$G$擦去属于$S$中的顶点后，剩下子图的连通分枝的个数。
（此条件不充分：Petersen图）

充分条件：
设$G=(V,E)$是一个无向简单图，$|V|=n, n\geq 3$，若对于任意的两个不相邻顶点$u，v\in V$，$$d(u)+d(v) \geq n$$ 那么, $G$是哈密尔顿图

又有：
设$G=(V,E)$是一个简单图，$|V|=n$，若对于任意的两个不相邻顶点$u，v\in V$，$$d(u)+d(v) \geq n-1$$ 那么, $G$含有哈密尔顿通路

典型的哈密尔顿图有哪些？

正十二面体

非哈密尔顿图(Herschel graph)

什么是二部图？二部图的边与顶点的关系是什么？

二部图：你懂它是什么的。
定理：一个图是二部图当且仅当它的所有回路的长度都是偶数

例题：
若$G$是一个二部图，若$|V|=n, |E|=m$，证明$m \leq \frac{n^2}{4} $
提示：基本不等式。
答案见 PPT19-12 或书P155例7

关于连通平面图的欧拉公式是什么？

对于任何一个连通的平面图$G=(V,E)，|V|=n，|E|=m$，有$$n-m+r=2$$其中r 代表G的区域数。
由于难以知道区域数r，此公式难以使用。故常用以下定理。

简单连通平面图的必要条件是什么？简单连通平面图的边与区域有什么关系？

对于任何一个简单的连通平面图$G=(V,E)，|V|=n，|E|=m$，有$$m \leq 3n-6$$
证明：任何一个区域至少由3条边围成，所以$2m \geq 3r$，结合欧拉公式证明。

对于任何一个区域至少由4条边围成的简单平面图，有$2m \geq 4r$，可证明$m \leq 2n-4$

还有一个很牛逼的定理：
一个图若不包含与$K5$或$K{3,3}$在2度顶点内同构的子图$\Leftrightarrow$它是平面图。

什么是树？树的等价定义有哪些？

一个无向图若连通且不含圈，则称它为一棵树，记为 $T=(V,E)$。
$$|E|=|V|-1$$

等价定义：
T=(V,E)是一个简单图，以下三条等价。

T是一棵树。
T连通, 且 $|V| - 1=|E|$。
T中无圈, 且 $|V| - 1=|E|$。

对于一棵树，顶点的度数与边数有什么关系？

树叶：度数为1的点。
分支点：度数大于等于2的点。

群

什么是半群、含幺半群？

半群：封闭性。结合律。
幺元：左幺元&&右幺元。
含幺半群：含有幺元的半群。

什么是群？

封闭性。结合律。幺元。逆元。

有哪些典型的群？

看作业作业里有张表。

什么是群的同态、群的同构？什么是群的自同构映射？

命题演算的推理理论

谓词演算基础

谓词演算的推理理论

递归函数论

集合 关系

图 树

群

集合关系

图树