请勿使用手机竖屏浏览该文章，否则会遇到算式显示不全的BUG我懒得改了

命题逻辑等值演算

吸收率

A∨(A∧B)⇔AA∧(A∨B)⇔AA\vee(A\wedge B)\Leftrightarrow A \\ A\wedge(A\vee B)\Leftrightarrow A

等值式①

p→(q→r)⇔(p∧q)→rp\rightarrow(q\rightarrow r)\Leftrightarrow (p\wedge q)\rightarrow r

主合取范式 → 极大项 → 成假赋值 | 重言式的主合取范式为 1

主析取范式 → 极小项 → 成真赋值 | 矛盾式的主析取范式为 0

命题逻辑的推理理论

构造性二难

(A→B)∧(C→D)∧(A∨B)⇒(B∨D)(A\rightarrow B)\wedge (C\rightarrow D)\wedge (A\vee B) \Rightarrow (B\vee D)

破坏性二难

(A→B)∧(C→D)∧(¬B∨¬D)⇒(¬A∨¬C)(A\rightarrow B)\wedge (C\rightarrow D)\wedge (\neg B\vee\neg D) \Rightarrow (\neg A\vee\neg C)

一阶逻辑基本概念

谓词常项 / 谓词变项

闭式 :不含自由出现的个体变项的公式; 闭式在任何解释下都能成为命题;

永真式也是 可满足式

量词辖域收缩扩张

∀x(A(x)→B)⇔∃xA(x)→B\forall x(A(x)\rightarrow B) \Leftrightarrow \exist xA(x)\rightarrow B

量词分配

∀x(A(x)∨B(x))⇐∀xA(x)∨∀B(x)∃x(A(x)∧B(x))⇒∃xA(x)∧∃B(x)∀x(A(x)→B(x))⇒∀xA(x)→∀xB(x)∀x(A(x)→B(x))⇒∃xA(x)→∃xB(x)∃xA(x)→∃xB(x)⇒∃x(A(x)→B(x))\forall x(A(x)\vee B(x))\Leftarrow\forall xA(x)\vee\forall B(x) \\ \exist x(A(x)\wedge B(x))\Rightarrow\exists xA(x)\wedge\exist B(x) \\ \forall x(A(x)\rightarrow B(x))\Rightarrow\forall xA(x)\rightarrow\forall xB(x) \\ \forall x(A(x)\rightarrow B(x))\Rightarrow\exist xA(x)\rightarrow\exist xB(x) \\ \exist xA(x)\rightarrow\exist xB(x)\Rightarrow\exist x(A(x)\rightarrow B(x))

消去/引入规则(只能对前束范式使用)

UI:∀xA(x)⇒A(y)orA(c)UG:A(y)⇒∀xA(x)EG:A(c)⇒∃xA(x)EI:∃xA(x)⇒A(c)UI:\forall xA(x)\Rightarrow A(y) orA(c) \\ UG:A(y)\Rightarrow\forall xA(x) \\ EG:A(c)\Rightarrow\exist xA(x) \\ EI:\exist xA(x)\Rightarrow A(c)

EI要求A(x)中只有x这一个自由个体变项

集合代数

幂集中包含空集

A−B=A∩∼B(A⊕B)⊕C=A⊕(B⊕C)A⊕B=A⊕C⇒B=CA-B=A\cap\sim B \\ (A\oplus B)\oplus C=A\oplus(B\oplus C) \\ A\oplus B=A\oplus C\Rightarrow B=C

二元关系

笛卡尔积对交并补满足分配律

定义域: domR; 值域:ranR; 域:fldR;

几个很乱的东西

F∘(G∪H)=F∘G∪F∘HF∘(G∩H)⊆F∘G∩F∘HF[(A∪B)]=F[A]∪F[B]F[(A∩B)]⊆F[A]∩F[B]F\circ(G\cup H)=F\circ G\cup F\circ H \\ F\circ(G\cap H)\sube F\circ G\cap F\circ H \\ F[(A\cup B)]=F[A]\cup F[B] \\ F[(A\cap B)]\sube F[A]\cap F[B]

等价类

[x]R={y∣y∈A∧xRy}[x]_R=\{y|y\in A\wedge xRy\}

商集(所有等价类作为元素)

A/R={[x]R∣x∈A}A/_R=\{[x]_R|x\in A\}

划分中不含空集

第二类Stirling数: n元集所有k-划分的个数 → S(n,k)

S(n+1,k)=S(n,k−1)+kS(n,k)S(n,2)=2n−1−1S(n,n−1)=Cn2S(n+1,k)=S(n,k-1)+kS(n,k) \\ S(n,2)=2^{n-1}-1 \\ S(n,n-1)=C_n^2

格与布尔代数

分配格: 不含有与钻石格或五角格同构的子格

a的补元b(前提是有界格):

a∧b=0,a∨b=1a\wedge b=0, a\vee b=1

布尔格: 有补分配格

图的基本概念

邻域N 与 闭邻域 ：与其相邻的点集合，闭的包括其本身

关联集I ：与其关联的边集合

最大度 最小度

Δ(G)=max{d(v)}δ(G)=min{d(v)}\Delta(G)=max\{d(v)\} \\ \delta(G)=min\{d(v)\}

简单图 ：不含平行边也不含环

简单通路/迹 ：通路经过的所有边各异。 简单回路/闭迹 ：字面意思

初级通路/路径 和 初级回路/圈 ：通路/回路经过的所有顶点也各异（边更是了）

连通分支数 ：p(G)

点连通度/连通度

κ(G)=min{∣V′∣}\kappa(G)=min\{\lvert{V'}\rvert\}

边连通度

λ(G)=min{∣E′∣}κ(G)≤λ(G)≤δ(G)\lambda(G)=min\{\lvert{E'}\rvert\} \\ \kappa(G)\le\lambda(G)\le\delta(G)

连通图 ：D=(V,E) 是强连通的当且仅当D中存在经过每个顶点至少一次的回路；D=(V,E) 是单向连通的当且仅当D中存在经过每个顶点至少一次的通路

n阶零图为二部图

哈密顿图

G=<V,E>是哈密顿图 ⇒∀V1⊂V\Rightarrow\forall V_1\sub V 且 V1≠∅→p(G−V1)≤∣V1∣V_1\ne\empty\rightarrow p(G-V_1)\le\lvert{V_1}\rvert

G为半哈密顿图 ⇒p(G−V1)≤∣V1∣+1\Rightarrow p(G-V_1)\le\lvert{V_1}\rvert+1

二部图 G=<V1,V2,E>,2≤∣V1∣≤∣V2∣G=<V_1,V_2,E>, 2\le\lvert{V_1}\rvert\le\lvert{V_2}\rvert

  • G是哈密顿图 ⇒∣V1∣=∣V2∣\Rightarrow\lvert{V_1}\rvert=\lvert{V_2}\rvert

  • G是半哈密顿图 ⇒∣V1∣=∣V2∣或∣V1∣+1=∣V2∣\Rightarrow\lvert{V_1}\rvert=\lvert{V_2}\rvert或\lvert{V_1}\rvert+1=\lvert{V_2}\rvert

G是无向简单图,任意不相邻顶点u,v有 d(u)+d(v)≥n−1⇒d(u)+d(v)\ge n-1\Rightarrow G中存在哈密顿通路

G是无向简单图,任意不相邻顶点u,v有 d(u)+d(v)≥n⇒d(u)+d(v)\ge n\Rightarrow G是哈密顿图

若D是 n阶竞赛图 ，则D中具有 哈密顿通路

强连通的有向图不一定是哈密顿图

树

生成树 ：树枝（生成树的边）、弦（非生成树的边）、余树（非生成树的边组成的导出子图）

基本回路/基本圈 ：一条是弦，其余都是树枝

基本割集 ：一条是树枝，其余都是弦

根树 ：有向树，只有一个顶点入度为0，其余顶点入度均为1

平面图

欧拉公式 ：面数+点数-边数=k+1

若G为简单平面图，则 δ(G)≤5\delta(G)\le5

彼得森图 不是平面图