1. 命题逻辑

命题具有确定真值，真值只有两种：

真： $T$ 或 $1$
假： $F$ 或 $0$

1.1 什么是命题

命题是具有确切真值的陈述句。

不是命题的典型情况：

祈使句
感叹句
疑问句
二义性陈述句
含自由变量而未限定取值范围的开语句

例如：

“这句话是假的”不是命题
“ $x+y>0$ ”若未说明 $x,y$ 的范围，则不是命题

1.2 原子命题与复合命题

原子命题：不能再分解为更简单命题的命题
复合命题：由原子命题借助逻辑联结词组合而成

1.3 命题联结词

1. 基本联结词

否定： $\neg$
合取： $\land$
析取： $\lor$
蕴含： $\to$
等价： $\leftrightarrow$

2. 其他常见联结词

异或： $\oplus$
同或： $\odot$

1.4 常见自然语言转化

“除非 $A$ ，否则不 $B$ ”：

B\to A

“只有 $A$ 才 $B$ ”：

B\to A

“只要 $A$ 就 $B$ ”：

A\to B

“如果 $A$ 就 $B$ ”：

A\to B

1.5 联结词优先级

优先级从高到低：

\neg \;>\; \land \;>\; \lor \;>\; \to \;>\; \leftrightarrow

同级通常按从左到右结合。

1.6 命题公式与真值表

1. 命题变元

命题变元是没有赋予具体内容的原子命题，通常记为 $P,Q,R,\dots$ ，取值范围为：

\{T,F\} \quad \text{或} \quad \{1,0\}

命题变元本身也是命题公式，称为原子公式。

2. 命题公式

由命题变元和联结词按规则形成的表达式称为命题公式。

例如：

G=(P\land Q)\to \neg R

3. 公式的解释

给公式中每个命题变元指定一个真值，称为该公式的一个解释。

若在某解释下 $G$ 为真，则称该解释满足 $G$
若在某解释下 $G$ 为假，则称该解释弄假于 $G$

4. 真值表

公式在所有可能解释下的真值构成真值表。

1.7 公式的分类与等价

1. 公式分类

永真公式（重言式）
永假公式（矛盾式）
可满足公式

2. 逻辑等价

若公式 $G,H$ 在所有解释下真值都相同，则称 $G,H$ 等价，记作：

G\equiv H

并且：

G\equiv H \iff G\leftrightarrow H \text{ 是永真公式}

1.8 基本等价关系

1. 蕴含等价式

G\to H \equiv \neg G\lor H

2. 等价等价式

G\leftrightarrow H \equiv (G\to H)\land(H\to G)

也即

G\leftrightarrow H \equiv (\neg G\lor H)\land(\neg H\lor G)

3. 等价否定

G\leftrightarrow H \equiv \neg G \leftrightarrow \neg H

4. 归谬式

(G\to H)\land(G\to \neg H)\equiv \neg G

5. 常见律

分配律
吸收律
德摩根律
双重否定律

1.9 公式的标准型：范式

1. 基本术语

文字：命题变元或其否定，如 $P,\neg P$
短语（项）：有限个文字的合取
子句：有限个文字的析取
互补对： $P$ 与 $\neg P$

2. 析取范式（DNF）

有限个短语的析取称为析取范式。

3. 合取范式（CNF）

有限个子句的合取称为合取范式。

要求：

只含 $\neg,\lor,\land$
否定只作用于命题变元

4. 求范式的一般步骤

消去 $\to,\leftrightarrow$
将否定号内移到命题变元前
利用分配律化为析取范式或合取范式

1.10 主范式

1. 极小项与极大项

设公式含有变元 $P_1,P_2,\dots,P_n$ 。

极小项

满足以下条件的短语称为极小项：

每个变元或其否定都出现且只出现一次
出现顺序与 $P_1,P_2,\dots,P_n$ 一致

极大项

满足相应条件的子句称为极大项。

2. 编码关系

例如对变元 $P,Q$ ：

极小项：

\neg P\land \neg Q = m_0

P\land Q = m_3

极大项：

P\lor Q = M_0

\neg P\lor \neg Q = M_3

并且：

m_i=\neg M_i,\qquad M_i=\neg m_i

3. 主析取范式与主合取范式

主析取范式：由若干极小项析取而成
主合取范式：由若干极大项合取而成

每个命题公式都存在与其等价的主析取范式和主合取范式。

4. 用真值表求主范式

对于主析取范式：取公式值为 $1$ 的各行，对应极小项做析取
对于主合取范式：取公式值为 $0$ 的各行，对应极大项做合取

5. 常见结论

主析取范式包含全部极小项 $\iff$ 公式为永真式
主合取范式包含全部极大项 $\iff$ 公式为永假式
两个公式主析取范式相同或主合取范式相同 $\iff$ 它们等价

1.11 命题蕴含与演绎推理

1. 命题蕴含

G_1,G_2,\dots,G_n \Rightarrow H

有效，当且仅当

(G_1\land G_2\land \cdots \land G_n)\to H

是永真公式。

2. 推理规则

P：前提引用
T：逻辑结果引用
CP：附加前提规则

3. 引入与消去规则

合取消去：

P\land Q \vdash P

P\land Q \vdash Q

合取引入：

P,Q \vdash P\land Q

其他联结词同理可结合引入规则和消去规则使用。

2. 谓词逻辑

2.1 谓词逻辑的引入

命题逻辑不能分析原子命题内部结构，因此引入谓词逻辑。

1. 个体词

原命题中可独立存在的客体称为个体词。

个体常量： $a,b,c,\dots$
个体变量： $x,y,z,\dots$

2. 论域

个体变量的取值范围称为论域或个体域。

3. 谓词

刻画个体性质或个体之间关系的表达式称为谓词。

例如：

一元谓词： $P(x)$
二元谓词： $R(x,y)$

含变量的谓词表达式本身不是命题，只有当变量被量词约束或被常量替代后，才成为命题。

2.2 量词

两种基本量词：

全称量词： $\forall x$
存在量词： $\exists x$

符号化准则

“所有”“任意”“每个”常用全称量词
“存在”“有些”“某个”常用存在量词

常见模式：

“所有满足 $P$ 的对象都满足 $Q$ ”：

(\forall x)(P(x)\to Q(x))

“存在某个对象既满足 $P$ 又满足 $Q$ ”：

(\exists x)(P(x)\land Q(x))

2.3 谓词公式

1. 四类符号

常量
变量
函数符号
谓词符号

2. 项

项包括：

常量和变量
若 $f$ 是 $n$ 元函数符号， $t_1,\dots,t_n$ 是项，则 $f(t_1,\dots,t_n)$ 也是项

3. 原子公式

若 $P$ 是 $n$ 元谓词符号， $t_1,\dots,t_n$ 是项，则：

P(t_1,\dots,t_n)

是原子公式。

4. 合式公式

由原子公式经过有限次使用逻辑联结词和量词构造出的公式，称为合式公式。

2.4 自由变元与约束变元

被量词约束的变量称为约束变元
未被量词约束的变量称为自由变元

不含自由变元的公式称为闭式。

闭式具有确定真值，因此可看作命题。

2.5 谓词公式的解释与分类

谓词公式也可分为：

有效公式
矛盾公式
可满足公式

补充：

一般谓词逻辑不可判定
只含一元谓词变项的某些情形可判定
个体域有穷时，可转化为有限命题逻辑问题处理

2.6 前束范式

1. 定义

若一个公式中所有量词都位于最前端，后接不含量词的母式，则称其为前束范式。

一般形式：

(Q_1x_1)(Q_2x_2)\cdots(Q_nx_n)\,M

其中 $Q_i$ 是量词， $M$ 是母式。

2. 求前束范式步骤

消去 $\to,\leftrightarrow$
将否定内移
把量词左移
必要时改名，避免变量冲突

2.7 谓词逻辑推理规则

1. 全称特指（US）

(\forall x)G(x)\Rightarrow G(c)

其中 $c$ 为任意个体常量。

2. 存在特指（ES）

(\exists x)G(x)\Rightarrow G(c)

其中 $c$ 为新引入的特指常量。

3. 全称推广（UG）

由 $G(c)$ 推出 $(\forall x)G(x)$ 时要满足相应限制条件。

4. 存在推广（EG）

G(c)\Rightarrow (\exists x)G(x)

2.8 常见有效推理式

以下推理有效：

(\forall x)(G(x)\to H(x)) \Rightarrow (\forall x)G(x)\to (\forall x)H(x)

以及：

(\forall x)(G(x)\to H(x)) \Rightarrow (\exists x)G(x)\to (\exists x)H(x)

而以下形式一般不成立：

(\forall x)(G(x)\lor H(x)) \Rightarrow (\forall x)G(x)\lor (\forall x)H(x)

(\exists x)G(x)\land (\exists x)H(x) \Rightarrow (\exists x)(G(x)\land H(x))

原稿中这一部分有些公式方向写反或条件不足，这里只保留稳定成立的结论。

3. 二元关系

3.1 序偶与笛卡尔积

1. 序偶

\langle a,b\rangle=\langle c,d\rangle \iff a=c,\ b=d

2. 笛卡尔积

A\times B = \{\langle a,b\rangle \mid a\in A,\ b\in B\}

性质：

一般不满足交换律与结合律
对并、交满足分配律
若 $A,B$ 有限，则

|A\times B|=|A|\cdot |B|

并且

A\times B=\emptyset \iff A=\emptyset \text{ 或 } B=\emptyset

3.2 关系的定义

设 $A,B$ 为非空集合，则 $A\times B$ 的任意子集称为从 $A$ 到 $B$ 的一个二元关系。

若 $A=B$ ，则称为 $A$ 上的一个二元关系。

记法：

$\langle x,y\rangle\in R$ 记作 $xRy$
$\langle x,y\rangle\notin R$ 记作 $x\not R y$

特殊关系：

空关系： $\emptyset$
全关系： $A\times B$
恒等关系：

I_A=\{\langle x,x\rangle\mid x\in A\}

关系总数：

2^{|A|\cdot |B|}

定义域与值域

定义域：

\operatorname{dom}(R)=\{x\in A\mid \exists y\in B,\ xRy\}

值域：

\operatorname{ran}(R)=\{y\in B\mid \exists x\in A,\ xRy\}

3.3 关系的表示

集合表示
关系图表示
关系矩阵表示

若 $R\subseteq A\times B$ ，其关系矩阵（布尔矩阵）用 $M_R$ 表示。

3.4 关系的运算

1. 集合运算

2. 复合运算

R\circ S = \{\langle x,z\rangle \mid (\exists y)(\langle x,y\rangle\in R \land \langle y,z\rangle\in S)\}

对应矩阵运算为布尔乘积。

3. 逆关系

R^{-1} = \{\langle b,a\rangle\mid \langle a,b\rangle\in R\}

矩阵表示上，逆关系对应转置矩阵。

3.5 关系运算定律

1. 结合律

(R\circ S)\circ T = R\circ (S\circ T)

2. 同一律

I\circ R = R,\qquad R\circ I = R

3. 分配律

对并：

R\circ (S_1\cup S_2) = (R\circ S_1)\cup (R\circ S_2)

(S_1\cup S_2)\circ T = (S_1\circ T)\cup (S_2\circ T)

对交一般只有包含关系，不必随意写成恒等式。

原稿中把交对复合也写成恒等分配律，这一般不成立。

4. 逆运算与复合

(R\circ S)^{-1}=S^{-1}\circ R^{-1}

3.6 幂运算

若 $R$ 是 $A$ 上的关系，则：

R^0=I_A,\qquad R^1=R,\qquad R^{n+1}=R^n\circ R

并有：

R^{m+n}=R^m\circ R^n

(R^m)^n=R^{mn}

当 $A$ 有限时，关系幂最终会稳定。

4. 关系的性质

4.1 五种基本性质

1. 自反性

(\forall x)\ \langle x,x\rangle\in R

矩阵特征：主对角线元素全为 $1$ 。

2. 反自反性

(\forall x)\ \langle x,x\rangle\notin R

矩阵特征：主对角线元素全为 $0$ 。

3. 对称性

\langle x,y\rangle\in R \Rightarrow \langle y,x\rangle\in R

4. 反对称性

\langle x,y\rangle\in R \land \langle y,x\rangle\in R \Rightarrow x=y

5. 传递性

\langle a,b\rangle\in R \land \langle b,c\rangle\in R \Rightarrow \langle a,c\rangle\in R

注意：

\langle a,c\rangle\in R \Rightarrow \langle a,b\rangle\in R \land \langle b,c\rangle\in R

不是传递性的定义。

4.2 关系性质的保守性

设 $R,S$ 为关系：

若 $R,S$ 自反，则 $R\cup S,\ R\cap S$ 自反
若 $R,S$ 对称，则 $R\cup S,\ R\cap S,\ R^{-1}$ 对称
若 $R$ 传递，则 $R^{-1}$ 传递
$R,S$ 传递时， $R\cup S$ 、 $R\cap S$ 不一定都传递
$R\circ S$ 也不自动保持这些性质

原稿中“自反/对称/传递在并交差复合下普遍保守”的说法过强，这里改成稳妥结论。

4.3 关系的闭包

对原关系作最小扩充，使之满足某种性质：

自反闭包：

r(R)=R\cup I_A

对称闭包：

s(R)=R\cup R^{-1}

传递闭包：

t(R)=\bigcup_{i=1}^{|A|}R^i

（ $A$ 有限时）

5. 等价关系与划分

5.1 等价关系

定义在非空集合上的自反、对称、传递关系称为等价关系。

5.2 等价类

若 $R$ 是 $A$ 上的等价关系，则对任意 $x\in A$ ：

[x]_R=\{y\in A\mid \langle x,y\rangle\in R\}

称为 $x$ 关于 $R$ 的等价类。

性质

任一等价类非空
任意两个等价类要么相等，要么不交
所有等价类的并是整个集合

5.3 商集

由所有等价类构成的集合称为商集，记作：

A/R=\{[x]_R\mid x\in A\}

5.4 集合的划分

设

\pi=\{S_1,S_2,\dots,S_m\}

若满足：

$S_i\subseteq A$
$S_i\cap S_j=\emptyset\ (i\ne j)$
$\bigcup_{i=1}^m S_i=A$

则称 $\pi$ 是 $A$ 的一个划分。

等价关系与划分的对应

每个等价关系都导出一个划分
每个划分都对应一个等价关系

6. 偏序、拟序、全序与良序

6.1 偏序关系

同时满足自反、反对称、传递的关系称为偏序关系。

记作：

\langle A,\le \rangle

称为偏序集。

可比

若 $x\le y$ 或 $y\le x$ ，则称 $x$ 与 $y$ 可比。

覆盖

若 $x<y$ 且不存在 $z$ 使得 $x<z<y$ ，则称 $y$ 覆盖 $x$ 。

6.2 哈斯图

哈斯图由偏序关系图简化而来：

去掉自环
去掉由传递性可推出的边
边默认向上，不再画箭头

6.3 最大元、最小元、极大元、极小元

设 $B\subseteq A$ 。

最大元

若

(\forall x\in B)(x\le b)

则 $b$ 为 $B$ 的最大元。

最小元

若

(\forall x\in B)(a\le x)

则 $a$ 为 $B$ 的最小元。

极大元

若

(\forall x\in B)(b\le x \Rightarrow x=b)

则 $b$ 为极大元。

极小元

若

(\forall x\in B)(x\le b \Rightarrow x=b)

则 $b$ 为极小元。

6.4 上界、下界、上确界、下确界

上界

若

(\forall x\in B)(x\le a)

则 $a$ 为 $B$ 的上界。

上确界

若 $a$ 是 $B$ 的上界，且任一上界 $a'$ 都满足：

a\le a'

则 $a$ 为 $B$ 的上确界。

下界

若

(\forall x\in B)(a\le x)

则 $a$ 为 $B$ 的下界。

下确界

若 $a$ 是 $B$ 的下界，且任一下界 $a'$ 都满足：

a'\le a

则 $a$ 为下确界。

6.5 拟序、全序、良序

拟序（严格偏序）

满足反自反和传递的关系称为拟序关系。

偏序与拟序之间有如下对应：

从偏序去掉对角线得到拟序
给拟序补上恒等关系得到偏序

全序

在偏序关系中，若任意两个元素都可比，则称为全序关系。

良序

在全序关系中，若任意非空子集都有最小元，则称为良序关系。

7. 函数

7.1 定义与术语

设 $f:A\to B$ 。

定义域： $\operatorname{dom}f=A$
值域： $\operatorname{ran}f\subseteq B$

7.2 类型

单射

(\forall x_1,x_2\in A)\ (x_1\ne x_2 \Rightarrow f(x_1)\ne f(x_2))

满射

\operatorname{ran}f = B

双射

同时是单射和满射。

7.3 复合

若 $f:A\to B,\ g:B\to C$ ，则：

(g\circ f)(x)=g(f(x))

这是函数复合的标准方向，原稿中此处是对的，值得特别记住。

7.4 逆函数

若 $f$ 是双射，则存在逆函数：

f^{-1}:B\to A

8. 图论基础

8.1 图的定义

图记作：

G=\langle V,E\rangle

其中：

$V$ 是顶点集
$E$ 是边集

8.2 图的表示

集合表示
图形表示
矩阵表示

8.3 图的分类

按边的方向

无向图
有向图
混合图

按是否有平行边和自环

简单图
多重图

按是否赋权

赋权图
无权图

特殊图

零图：只有顶点，没有边
平凡图：只有一个顶点的图

8.4 子图与补图

子图

子图
真子图
生成子图
导出子图

补图

若 $G=\langle V,E\rangle$ 是简单图，完全图为 $\langle V,E_1\rangle$ ，则其补图为：

\overline G = \langle V,E_1-E\rangle

8.5 度数与握手定理

1. 无向图

顶点 $v$ 的度记作 $\deg(v)$ 。

最大度： $\Delta(G)$
最小度： $\delta(G)$

2. 有向图

入度： $\deg^-(v)$
出度： $\deg^+(v)$

并且：

\deg(v)=\deg^-(v)+\deg^+(v)

3. 握手定理

无向图中：

\sum_{v\in V}\deg(v)=2|E|

推论：奇度顶点个数为偶数。

有向图中：

\sum_{v\in V}\deg^+(v)=\sum_{v\in V}\deg^-(v)=|E|

9. 树与生成树

9.1 树

无向树是无环连通图。

森林是每个连通分支都是树的图。

9.2 树的等价刻画

设图 $G=\langle V,E\rangle$ ， $|V|=n,\ |E|=m$ ，以下命题等价：

$G$ 是树
$G$ 连通且无回路
$G$ 无回路且 $m=n-1$
$G$ 连通且 $m=n-1$
任意两个顶点之间有且仅有一条基本通路
删除任意一条边后图不连通
向任意两个不邻接顶点加一条边，恰得一条基本回路

推论：

若 $m>n-1$ ，则图必有回路
若 $m<n-1$ ，则图必不连通
任意非平凡树至少有两片叶

9.3 生成树

若图 $G$ 的某个生成子图是树，则称其为 $G$ 的生成树。

生成树存在的充要条件

G \text{ 连通}

9.4 最小生成树

1. Kruskal 算法（选边）

每次选取当前不构成回路的最小权边，直到选满 $n-1$ 条边。

2. Prim 算法（扩点）

从任意顶点开始，每次选取连接当前树与外部顶点的最小权边。

9.5 根树与 $k$ 元树

1. 根树

恰有一个结点入度为 $0$ 、其余结点入度为 $1$ 的有向树称为根树。

入度为 $0$ ：根
出度为 $0$ ：叶
入度为 $1$ 且出度大于 $0$ ：内点或分支点

2. $k$ 元树

每个分支点至多有 $k$ 个儿子： $k$ 元树
每个分支点恰有 $k$ 个儿子：满 $k$ 元树

性质：

(k-1)\times \text{分支点数} = \text{叶数} - 1

3. 遍历

先根次序
中根次序
后根次序

9.6 Huffman 树

1. 前缀码

若任一编码都不是另一编码的前缀，则称为前缀码。

2. 最优树

使加权路径长度

WPL=\sum w_iL(w_i)

最小的树称为最优树。

3. Huffman 算法

每次合并权值最小的两个结点，反复进行，直到形成整棵树。

10. 特殊图

10.1 欧拉图

欧拉通路与欧拉回路

欧拉通路：经过每条边恰好一次的通路
欧拉回路：经过每条边恰好一次的回路

无向图判定

有欧拉回路：图连通且奇度顶点数为 $0$
有欧拉通路：图连通且奇度顶点数为 $0$ 或 $2$

有向图判定

有欧拉回路：忽略孤立点后连通，且对所有顶点

\deg^-(v)=\deg^+(v)

Fleury 算法

构造欧拉通路/回路时，尽量不先走桥。

10.2 哈密顿图

哈密顿通路与哈密顿回路

哈密顿通路：经过每个顶点恰好一次的通路
哈密顿回路：经过每个顶点恰好一次的回路

必要条件

若图有哈密顿回路，则对任意非空顶点子集 $V_1$ ：

p(G-V_1)\le |V_1|

其中 $p(\cdot)$ 表示连通分支数。

常见充分条件

若对任意不相邻顶点 $u,v$ ：

\deg(u)+\deg(v)\ge n

则图有哈密顿回路。

若对任意顶点 $v$ ：

\deg(v)\ge \frac n2,\qquad n\ge 3

则图有哈密顿回路。

10.3 二分图（偶图）

定义

图的顶点集可分为两个不交子集 $V_1,V_2$ ，使每条边的两个端点分别属于两个不同子集，则称该图为二分图。

完全二分图

若 $V_1$ 中每个顶点都与 $V_2$ 中每个顶点相邻，则称为完全二分图，记为：

K_{i,j}

判定充要条件

图是二分图当且仅当它不含奇数长度回路。

匹配与完全匹配

匹配：任意两条边不共端点
完全匹配：覆盖一个部分或全部顶点的匹配

Hall 定理

二分图存在从 $V_1$ 到 $V_2$ 的完全匹配，当且仅当：

对 $V_1$ 的任意子集 $X$ ，其邻接点集 $N(X)$ 满足

|N(X)|\ge |X|

10.4 平面图

定义

若图可画在平面上，使任意两边只在公共端点相交，则称该图为平面图。

面与次数

面分为有限面和无限面
各面次数之和等于边数的两倍：

\sum D(r)=2m

欧拉公式

连通平面图满足：

n-m+r=2

其中：

$n$ ：顶点数
$m$ ：边数
$r$ ：面数

推论

若 $n\ge 3$ ，则：

m\le 3n-6

若所有面的次数都至少为 $k$ ，则：

m\le \frac{k}{k-2}(n-2)

同胚

通过反复插入或消去 $2$ 度顶点得到的图称为同胚图。

库拉托夫斯基定理

图是平面图，当且仅当它不含与 $K_5$ 或 $K_{3,3}$ 同胚的子图。

11. 真题型易错点总结

11.1 命题公式定义

命题公式可递归定义：

命题变元是公式
若 $G$ 是公式，则 $\neg G$ 是公式
若 $G,H$ 是公式，则 $(G\lor H),(G\land H),(G\to H),\dots$ 也是公式
仅由有限步使用上述规则构成的符号串才是公式

11.2 单射定义

f:A\to B,\quad \forall x_1,x_2\in A,\ x_1\ne x_2 \Rightarrow f(x_1)\ne f(x_2)

11.3 各类图的判定重点

欧拉图：看边
哈密顿图：看点
二分图：看奇圈
平面图：看欧拉公式与 $K_5,\ K_{3,3}$

11.4 上确界与下确界

上确界是“最小的上界”
下确界是“最大的下界”
都不一定存在

11.5 约束变元

只要某变量出现在某量词的辖域内并被其绑定，就是约束变元。

11.6 传递性

正确形式：

\langle a,b\rangle\in R \land \langle b,c\rangle\in R \Rightarrow \langle a,c\rangle\in R

11.7 有穷论域下量词展开

若论域有限，则：

(\forall x)G(x) \equiv G(a_1)\land G(a_2)\land \cdots \land G(a_n)

(\exists x)G(x) \equiv G(a_1)\lor G(a_2)\lor \cdots \lor G(a_n)

11.8 通路与回路数

使用邻接矩阵：

$A^m$ 的 $(i,j)$ 元表示长度为 $m$ 的从 $v_i$ 到 $v_j$ 的通路数
对角线元素表示回路数

11.9 补图

补图是相对于完全简单图而言，不考虑自环，因此补图矩阵处理中通常不补主对角线。

11.10 谓词逻辑演绎格式

常见写法：

US, ES, UG, EG
T, (i), I/E
P, CP

11.11 符号化问题

只要出现“所有”“存在”“有些”“某个”等字样，优先考虑用谓词逻辑表达，而不是仅用命题逻辑。

12. 符号化练习模板

12.1 全称命题模板

“所有满足 $P$ 的对象都满足 $Q$ ”：

(\forall x)(P(x)\to Q(x))

12.2 存在命题模板

“存在某个对象同时满足 $P,Q$ ”：

(\exists x)(P(x)\land Q(x))

12.3 演绎证明模板

常用套路：

写出前提（P）
用 US / ES 消量词
用 T、I、E 做逻辑推导
若要得到全称结论，再用 UG
若要得到存在结论，用 EG

Linked Notes

No outgoing note links.

Referenced By

No backlinks yet.