# 量词实例化
定义置换就是用一个变量替换另一个变量，如
$$
\theta=\{a/b\}
$$
是说这个置换的名字叫$\theta$，它将语句中的变量$a$都换成变量$b$。应用一个变换可以这样表示
$$
SUBSET(\theta,\alpha)
$$
表示对语句$\alpha$应用置换$\theta$



**全称量词实例化**可以用任意的变量置换全称量化的变量，如对于
$$
\forall x \, (King(x) \land Greedy(x) \Rightarrow Evil(x))
$$
令置换 $\theta = \{x / John\}$，可得到
$$
King(John) \land Greedy(John) \Rightarrow Evil(John)
$$

**存在量词实例化**同样使用置换，不过置换的变量应当是从未出现的，称为**斯科伦常量**，如
$$
\exists x \, (Crown(x) \land OnHead(x, John))
$$
可得
$$
Crown(C_1) \land OnHead(C_1, John)
$$
其中$C_1$是斯科伦常量，它从未出现过。在进行实例化后，得到的语句应取代原先的语句，意为**存在量词实例化只能进行一次**。但是全称量词可以多次实例化，可以获得多种不同的结果

# 量词约简为命题推断
量词的约简分为两步

1. 对全称量词的语句，枚举所有的对象进行实例化
2. 对存在量词的语句，用斯科伦常量进行一次实例化

不过此处会出现问题，函数作用与对象上会得到对象，它还能再被函数作用一次得到新的对象。这回陷入无限的嵌套中

对于该问题有**Herbrand定理**

:::info{title="Note"}
如果有限的一阶语句蕴含某个语句$\alpha$，则一定存在有限步的推导。即将这些一阶语句命题化后存在一个有限嵌套深度的子集可以完成证明
:::

这说明一阶逻辑的蕴含问题是半可判定的，也就是说存在有限步内能判断语句成立，却不能判断语句不成立

不过即便不考虑函数，对于$n$个对象和一个$k$元谓词，实例化的复杂度也是指数级的
$$
n^k
$$
其中有大量无关的语句。为了只实例化需要的实例，需要引入**一般化肯定前件**（GMP）

# 一般化肯定前件
对于$n$个原子语句$p_1,p_2,\cdots,p_n$和$1$个蕴含语句，更准确来说应该是**一阶确定子句**，只有一个正文字
$$
p_1'\land p_2'\land\cdots\land p_n'\Rightarrow q
$$

如果能找到一个置换$\theta$使得对应语句**相同**
$$
SUBSET(\theta,p_i)=SUBSET(\theta,p_1')
$$
注意等值表示的是相同而不是逻辑上的相等。那么给定前件为$p_1',p_2',\cdots,p_n'$的该蕴含语句
$$
p_1',p_2',\cdots,p_n',(p_1'\land p_2'\land\cdots\land p_n'\Rightarrow q)
$$
可以被替换为结论的置换
$$
SUBSET(\theta,q)
$$
一个简单的例子是
$$
\forall x \, (King(x) \land Greedy(x) \Rightarrow Evil(x))\\
King(John)\\
\forall y \, Greedy(y)\\
Brother(John, Richard)
$$
由于取置换
$$
\theta = \{x/John, y/John\}
$$
各语句被置换后有
$$
Subst(\theta, p_1') = Subst(\theta, p_1) = King(John)
$$
$$
Subst(\theta, p_2') = Subst(\theta, p_2) = Greedy(John)
$$
那么原来的蕴含语句$Subst(\theta, q)$就应被实例化为
$$
Evil(John)
$$
没有多余的实例化

GMP的核心在于那个置换，称为**合一子**。两个语句的合一子可能不止一种，但是会存在一个最一般的合一子，其他所有的何意子都可以在其基础上再施加置换得到，称为**最一般合一子MGU**

不过使用GMP的条件是所有的变量假设均为全称量词，并且只能作用于一阶确定子句。在这个条件下，GMP是可靠且完备的

# 一阶逻辑的归结
## 一阶逻辑转换为合取范式
要对一阶逻辑使用归结，应当先将一阶逻辑语句转换为合取范式CNF。要将语句转化为CNF，应当**先消去蕴含**，利用逻辑等值式
$$
A\Rightarrow B\equiv \neg A\lor B
$$
使用时需要注意，虽然需要对$\forall,\exists$取反，但是内层的$\Rightarrow$取反时不应影响外层的量词，如
$$
\forall x [\forall y \, Animal(y) \Rightarrow Loves(x, y)] \Rightarrow [\exists y \, Loves(y, x)]
$$
$$
\rightarrow \forall x\neg [\forall y \neg  Animal(y) \lor Loves(x, y) \lor (\exists y \, Loves(y, x))]
$$
其中$\forall x$是外层的量词，作用于蕴含的两端，不受取反影响；而蕴含的前提中$\exists y$不作用于结论，应当取反

第二步是**将非号移到量词作用域的内部**，形成一系列由`与`和`或`连接的原子语句，如
$$
\forall x\neg [\forall y \neg  Animal(y) \lor Loves(x, y) \lor (\exists y \, Loves(y, x))]
$$
$$
\rightarrow \forall x \, [\exists y \, Animal(y) \land \neg Loves(x, y) \lor (\exists y \, Loves(y, x))]
$$

第三步是变量标准化，不同语句间如果不是同一个对象应使用不同的名字，虽然量词的修饰允许，但为了后续步骤还是需要这样做，如此处将蕴含结论的$y$换为了另一个名称$z$
$$
\forall x \, [\exists y \, Animal(y) \land \neg Loves(x, y) \lor (\exists y \, Loves(y, x))]
$$
$$
\rightarrow \forall x \, [\exists y \, Animal(y) \land \neg Loves(x, y) \lor \exists z \, Loves(z, x)]
$$

第四步是将**存在量词实例化**。需要注意的是，此处实例化并不是化为斯科伦常量，而是**斯科伦函数**。它是所有基本对象的函数，代表未知的确定函数，这是因为斯科伦常量太过一般，至少斯科伦函数能提供自变量的信息。如
$$
\forall x \, [\exists y \, Animal(y) \land \neg Loves(x, y) \lor \exists z \, Loves(z, x)]
$$
$$
\rightarrow \forall x \, [Animal(F(x)) \land \neg Loves(x, F(x)) \lor Loves(G(x), x)]
$$
不一样的变量应替换为不一样的斯科伦函数

最后将全称量词去除，因为斯科伦函数可以是所有基本对象的任意函数，本身就是对所有基本对象的实例化。上面的例子中，最后将得到语句
$$
Animal(F(x)) \land \neg Loves(x, F(x)) \lor Loves(G(x), x)
$$
不过为了得到CNF的形式，还需将其转为合取
$$
[Animal(F(x)) \lor Loves(G(x), x)] \land [\neg Loves(x, F(x)) \lor Loves(G(x), x)]
$$

## 一阶逻辑的归结规则

:::info{title="Note"}
对于两个一阶逻辑的CNF语句，若其中各有一个文字，在某种置换规则$\theta$作用下互为反文字，则这两个文字可以被消去
:::

具体来说，对于一阶逻辑语句
$$
a_0\land a_1\land a_2\land\cdots\land a_n
$$
$$
b_0\land b_1\land b_2\land\cdots\land b_m
$$
若存在一个置换规则使得$\theta$使得
$$
SUBSET(\theta,b_0)=\neg a_0
$$
则它们两个等价于
$$
SUBSET(\theta,a_1\land a_2\land\cdots\land a_n\land b_1\land b_2\land\cdots\land b_m
$$
归结是可靠且完备的

逻辑学（四）——一阶逻辑的推断

# 一阶逻辑(FOL: First Order Logic)

一阶逻辑用下面的形式描述世界
- 对象：人、房屋、数字、颜色、游戏、战争、披萨
- 关系：可以是一元关系或属性, 如红色的、圆的、伪造的；更普适的是n元关系, 如大于、…和…是兄弟、在…里
- 函数:  有唯一值, 如…的父亲, …最好的朋友, …的左胳膊, …加1 等

关系又可称为**谓词**





# FOL的语法

- 常量/Constants: `KingJohn, 2, USTC, ...`
- 谓词/Predicates: `Brother, >, ...`
- 函数/Function: `Sqrt, LeftLegOf, ...`
- 变量/Variables: $x, y, a, b, \dots$

FOL还需要表示逻辑的符号（就跟命题逻辑一样）
- 联结词/Connectives: $\neg, \land, \lor, \Rightarrow, \Leftrightarrow$
- 等词/Equality: $=$
- 量词/Quantifiers: $\forall, \exists$

常量和变量称为**项**，即对象。对项应用函数也会得到项，称为**复合项**。如有$n$元函数$\varphi$
$$
\varphi(x_1,x_2,\cdots,x_n)
$$
将其作用到$n$个项$t_1,t_2,\cdots,t_n$上会得到复合项
$$
\varphi(t_1,t_2,\cdots,t_n)
$$

:::info{title="Note"}
所有项都是0次或有限次复合得到的
:::

谓词作用在项上形成**原子语句**，项也可以是复合项，如
$$
>(Length(LeftLegOf(Richard)), Length(LeftLegOf(KingJohn)))
$$

原子语句由逻辑词链接得到**复合语句**，如
$$
> (1,2) \land \neg >(1,2)
$$

# 一阶逻辑语句的真值与数据库语义
语句的真值是由一个**模型**和对句子符号的**解释**来判定，其中模型包含**对象域和对象的关系**，解释是指对FOL语句中的三类符号(常量符号、谓词符号、函数符号)指代的对象、关系和函数进行解释

如对于
$$
Brother (Richard, John) 
$$

根据`Brother`，`Richard`，`John`解释的不同，该语句的真值也不同。 FOL语言中，3类符号在模型中的对应数量可以从1到无穷大，**无法枚举**，因而需要引入**数据库**

**数据库语义**定义为
  - 唯一名称假设：每个常量符号指代一个唯一对象
  - 封闭世界假设：假设未知的所有原子语句均为假
  - 论域闭包：每个模型只包含常量符号指代的对象


# 全称量词与存在量词

- **量词**: 表示数量的词
- **全称量词 $\forall$**: 表示任意的，所有的，一切的
- **存在量词 $\exists$**: 表示存在，有的，至少有一个

量词的使用需要注意避免两类错误

:::warning{title="全称量词"}
全称量词$\forall$和`与`$\land$逻辑混合使用，如记$M(x)$表示`x是人`，$F(x)$表示`x爱美`
$$
\forall x(M(x)\land F(x))
$$
它的语义是任何事物$x$都是人并且任何事物$x$都爱美。事实上如果希望表达`人都爱美`，应当使用蕴含逻辑
$$
\forall x(M(x)\Rightarrow F(x))
$$
:::

:::warning{title="存在量词"}
存在量词$\exists$和`蕴含`$\Rightarrow$逻辑混合使用，如记$M(x)$表示`x是人`，$F(x)$表示`x爱美`
$$
\exists x(M(x)\Rightarrow F(x))
$$
它的语义是存在事物`x`，如果`x`是人`x`就爱美。事实上如果想表示`有的人爱美`应该使用与
$$
\exists x(M(x)\land F(x))
$$
:::

# 量词的性质
**两个相同的量词可以交换**
$$
\forall x\forall y,~\forall y \forall x
$$
它们是等价的，因而可以简写为$\forall x,y$。同样`存在量词`也有相同的等价关系
$$
\exists x\exists y,~\exists y \exists x
$$
它们是等价的，因而可以简写为$\exists x,y$。但是注意

:::warning{title="注意"}
$\forall x\exists y$ 和 $\exists y\forall x$ 不等价。随便找个函数试试就能发现了
:::

**量词否定等值式**

对含量词的逻辑表达式取反时应先将量词取反
$$
\neg \forall x A(x)\equiv \exists x\neg A(x)\\
\neg\exists x A(x)\equiv\forall x\neg A(x)
$$

**量词可以分配**

$\forall$对`与`$\land$可以分配，$\exists$对`或`$\lor$可以分配
$$
\forall x(A(x)\land B(x))\equiv \forall xA(x)\land\forall xB(x)\\
\exists x(A(x)\lor B(x))\equiv \exists xA(x)\lor\exists xB(x)\\
$$
反过来则不成立

# 等词`=`
等词`=`意为**相同的对象**而不是值相同，表征它俩就是同一个东西。例如可以用父母关系定义兄弟姐妹
$$
\forall x, y \, Sibling(x, y) \iff \\
[\neg(x = y) \land \exists m, f \, (\neg(m = f) \land Parent(m, x) \land Parent(f, x) \land Parent(m, y) \land Parent(f, y))]
$$

逻辑学（三）——一阶逻辑

# 触发器

锁存器是对电平敏感的，而**触发器**是对边沿敏感的。意思是说触发器的状态更新发生在时钟脉冲的边沿

以$CP$命名上升沿触发的时钟信号，$\overline{CP}$命名下降沿触发的时钟信号



# 主从D触发器
 用主从两个D锁存器可以实现一个D触发器，它的结构如图所示
 
 
![image.png](/static/img/85ab62d4f175d560cde847d85bafe847.image.webp)

当时钟信号$CP$为零时，$C=0$，使得$TG_1$导通而$TG_2$断开，$D$进入主锁存器中；同时$TG_4$导通而$TG_3$断开，从锁存器进入自锁状态，输出信号仍然由自锁的从锁存器决定

当CP从0跳1时，主锁存器进入自锁状态，锁存的值为前一个瞬间的$D$，同时从锁存器打开使得信号$Q'$进入从锁存器中，输出信号是上升沿时刻的$D$

当CP从1跳0时，从锁存器进入自锁状态，同时主锁存器打开。不过此时输出信号仍然由自锁的从锁存器决定

D触发器

# 推理的形式结构

推理有`前提`和`结论`。记前提为$A_1,A_2,\cdots,A_n$，结论为$B$，则由前提推出结论可以抽象地表示为一个逻辑表达式
$$
A_1\land A_2\land\cdots\land A_n\Rightarrow B
$$

该推理正确等价于上式无条件为真，也就是说

:::info{title="Note"}
前提为$A_1,A_2,\cdots,A_n$，结论为$B$的推理正确等价于表达式
$$
A_1\land A_2\land\cdots\land A_n\Rightarrow B
$$
为重言式
:::



推理有以下几种方法
- 真值表枚举法：对所有的变量枚举所有可能的取值，证明该表达式恒为真
- 等值演算法：根据逻辑学定理将该表达式变形，直到可以确定其为真
- 构造证明法: 从前提出发，严格按照推理规则构造命题序列，序列的最后一条是结论

包含蕴涵的重言式可以列举如下，供推理使用。`蕴含`符号的左侧为真就意味着右侧为真，欲证明右侧为真可以证明左侧为真

| 定律名称       | 表达式                                                                 |
| :-------------: | :------------------------------------------------------------------: |
| 附加律         | $A \vDash (A \lor B)$                                               |
| 化简律         | $(A \land B) \vDash A$                                              |
| 假言推理       | $(A \Rightarrow B) \land A \vDash B$                                |
| 拒取式         | $(A \Rightarrow B) \land \neg B \vDash \neg A$                      |
| 析取三段论     | $(A \lor B) \land \neg B \vDash A$                                  |
| 假言三段论     | $(A \Rightarrow B) \land (B \Rightarrow C) \vDash (A \Rightarrow C)$ |
| 等价三段论     | $(A \Leftrightarrow B) \land (B \Leftrightarrow C) \vDash (A \Leftrightarrow C)$ |
| 构造性二难     | $(A \Rightarrow B) \land (C \Rightarrow D) \land (A \lor C) \vDash (B \lor D)$ |
| 构造性二难(特殊) | $(A \Rightarrow B) \land (\neg A \Rightarrow B) \vDash B$          |
| 破坏性二难     | $(A \Rightarrow B) \land (C \Rightarrow D) \land (\neg B \lor \neg D) \vDash (\neg A \lor \neg C)$ |

# 推理规则
| 规则名称       | 表达式                                                         | 描述                         |
| -------------- | ------------------------------------------------------------ | ---------------------------- |
| 前提引入规则   | $\begin{aligned} A \\ \therefore A \end{aligned}$            | 一个命题可以直接推出自身     |
| 结论引入规则   | $\begin{aligned} \vdash B \\ \therefore A \vdash B \end{aligned}$ | 如果结论成立，则添加前提无影响 |
| 置换规则       | $\begin{aligned} A \iff B \\ \therefore B \iff A \end{aligned}$ | 等价命题可以交换位置         |
| 假言推理规则   | $\begin{aligned} A \Rightarrow B \\ A \\ \therefore B \end{aligned}$ | 前提成立则结论必然成立       |
| 附加规则       | $\begin{aligned} A \\ \therefore A \lor B \end{aligned}$     | 单个命题可以推出或关系       |
| 合取消去规则   | $\begin{aligned} A \land B \\ \therefore A \end{aligned}$    | 合取中的某一项可以被单独推出 |
| 拒取式规则     | $\begin{aligned} A \Rightarrow B \\ \neg B \\ \therefore \neg A \end{aligned}$ | 如果结论不成立，则前提必然不成立 |
| 假言三段规则   | $\begin{aligned} A \Rightarrow B \\ B \Rightarrow C \\ \therefore A \Rightarrow C \end{aligned}$ | 前提的传递性推导出最终结论   |

# 归结证明

:::tip{title="归结(消解)规则"}
若已知 $p\lor q$ 与 $\neg p \lor r$都为真，则$q\lor r$为真
:::
形式上看是消去了变量 $p$ ，利用它可以从条件中消去结论中不出现的变量进而完成证明

证明$A_1\land\cdots\land A_n\Rightarrow B$恒为真等价于证明下式为假
$$
A_1\land\cdots\land A_n\land \neg B
$$

利用反证法，假定它是真的，推出矛盾（0）即可。由此归结证明的过程可以描述如下
1. 将每个前提都转化为合取范式，即一些简单析取式以“或”的形式连接，进而得到一系列简单析取式形式的前提，记为$A_1,A_2,\cdots,A_t$
2. 将结论的反 $\neg B$ 转化为合取范式，即$\neg B=B_1\land B_2\land\cdots\land B_s$
3. 认为这些$B$都是真的，以$A_1,A_2\cdots A_t,B_1,\cdots B_s$为条件，使用归结推出矛盾（0）

一个证明的例子是
$$
前提：(p\Rightarrow q)\Rightarrow r,~r\Rightarrow s,~\neg s~~结论：p\land\neg q
$$

首先将前提转化为合取
$$
(p\lor r)\land(\neg q\lor r),~\neg r\lor s,~\neg s
$$

将结论转化为合取
$$
\neg p\lor q
$$

希望利用前提和结论推出0
$$
p\lor r,~\neg q\lor r,~\neg r\lor s,~\neg s,~\neg p\lor q
$$

先消去$p$
$$
p\lor r+~\neg p\lor q\rightarrow q\lor r
$$

那么就有$~\neg q\lor r,~\neg r\lor s,~\neg s,~q\lor r$，消去$q$
$$
~\neg q\lor r+~q\lor r\rightarrow r
$$

那么$~\neg r\lor s,~\neg s,~r$，再消去$r$
$$
~\neg r\lor s+r\lor 0\rightarrow s
$$

那么$s,~\neg s$。实际上到这里已经出现矛盾了，不过从程序上来说还是推导到$0$为止
$$
s\lor 0 + \neg s\lor 0\rightarrow 0
$$

即完成了证明。关于归结法有定理

:::info{title="Note"}
归结法是完备且可靠的
:::

不过它的时间复杂度是指数级的

# 前向链接与反向链接

逻辑学中将命题抽象为符号，称其为**正文字**，将其否定称为**负文字**。鉴于蕴含等值式

>$$
>A\Rightarrow B\equiv \neg A\lor B
>$$

若$A$是一些正文字的与，即简单合取式$A=a_1\land a_2\cdots \land a_n$，那么由于摩根定律有
$$
\neg A=\neg a_1\lor\neg a_2\lor\cdots\lor\neg a_n
$$
也就是说，如果一个析取式中只有一个正文字
$$
B\lor\neg a_1\lor\neg a_2\lor\cdots\lor\neg a_n
$$
它会等价于一个蕴含式
$$
a_1\land a_2\cdots \land a_n\Rightarrow B
$$

称其为**确定子句**

:::info{title="Note"}
**确定子句**：只有一个正文字的析取式
:::

若允许全是负文字，则得到了**霍恩子句**

:::info{title="Note"}
**霍恩子句**：最多一个正文字构成的析取式
:::

由于归结会消去两个子句中的一个正文字和对应负文字，因而**确定子句或霍恩子句的归结是封闭的**，即任意两个确定子句或霍恩子句归结，得到的仍是确定子句或霍恩子句

前向链接算法用于处理确定子句（即蕴涵式）构成的知识库推理问题。如果已知了一个知识库KB，其中是一系列的确定子句。为了描述方便，定义蕴涵式中
$$
a_1\land a_2\cdots \land a_n\Rightarrow B
$$

$a_1, a_2\cdots , a_n$为**前件**，$B$为结论。希望查询命题Q是否能被推理，可以依照下面的步骤

0. 初始化一个确定事件集合，用于保存已经确认为真的事实。对于知识库中每一个确定子句，维护其不在确定事件集合中的前件数目
1. 取出知识库中全部前件已知的确定子句（即不在确定事件集合中的前件数目为零），将其结论添加入已知事件集中，将其从知识库中删除
2. 重复`1`直到命题Q被添加入已知事件集或是知识库为空

也可以采取**反向链接**算法，它是自顶向下的，即查询以Q为结论的所有蕴涵式是否存在一个其前提都为真，尝试递归证明它们。反向链接算法是目标驱动的，适合解决明确的问题，有时复杂度会远远小于前向链接

逻辑学（二）——推理与证明

# 命题与联结词
命题是真假性唯一的陈述句，不能可真可假。若陈述句中存在悖论，或者分情况确定真假，也不构成命题

最简单的命题是**原子命题**，它是由简单陈述句构成的命题，将其抽象为符号，如`p`,`q`,`r`。它的作用和地位可以类比于单词，具有最基本的语义，也称为**原子语句**



由原子命题通过**联结词**联结而成的陈述句称为**复合命题**。逻辑联结词可以如下列出
- $\neg p$ ：**非**，否定联结词，称$\neg p$为**否定式**。$p$为正文字，$\neg p$为负文字
- $p\wedge q$：**与**，合取联结词，称$p\wedge q$为**合取式**
- $p\vee q$：**或**，析取联结词，称$p\vee q$为**析取式**
- $p\Rightarrow q$：**蕴含**，蕴含联结词，称$p\Rightarrow q$为**蕴含式**，$p$为前件，$q$为后件
- $p\Leftrightarrow q$：**双向蕴含**，等价联结词，当且仅当

规定联结词具有优先级
$$
()\to \neg\to\wedge,\vee\to\Rightarrow,\Leftrightarrow
$$
同级联结词从左到右结合。联结词的真假如下表

| $p,q$ | $\neg p$ | $p\wedge q$ | $p\vee q$ | $p\Rightarrow q$ | $p\Leftrightarrow q$ |
| :---: | :---: | :---: | :---: | :---: | :---: |
|啥啊|  $p$假时真   |  $pq$都真时真   |  $pq$都假时假   |  $p$真$q$假时假   |  $pq$真假相同时真   |
|0 0| 1|0|0|1|1|
|0 1| 1|0|1|1|0|
|1 0| 0|0|1|0|0|
|1 1| 0|1|1|1|1

比较难以理解的是蕴含联结词。可以这样理解：$p\Rightarrow q$为真意味着p蕴含q，即当p为真时q一定为真，而不要求p为假时q的真假性。也就是说p蕴含q不成立仅有一种可能，即p为真时q为假

# 逻辑等价
在所有的模型中两个语句真假相同称为**逻辑等价**。基本的逻辑等价可以列出如下表

| 定律         | 表达式1                                   | 表达式2                                   |
| ------------ | :----------------------------------------: | :----------------------------------------: |
| 双重否定律   | $\neg \neg A \equiv A$                   |                                          |
| 恒等律       | $A \lor A \equiv A$                      | $A \land A \equiv A$                     |
| 交换律       | $A \lor B \equiv B \lor A$               | $A \land B \equiv B \land A$             |
| 结合律       | $(A \lor B) \lor C \equiv A \lor (B \lor C)$ | $(A \land B) \land C \equiv A \land (B \land C)$ |
| 分配律       | $A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$ | $A \land (B \lor C) \equiv (A \land B) \lor (A \land C)$ |
| 德·摩根律    | $\neg (A \lor B) \equiv \neg A \land \neg B$ | $\neg (A \land B) \equiv \neg A \lor \neg B$ |

存在一些为常数的情况

| 定律   | 表达式1                  | 表达式2                  |
| ------ | :---------------------: | :----------------------: |
| 零律   | $A \lor 1 \equiv 1$      | $A \land 0 \equiv 0$     |
| 同一律 | $A \lor 0 \equiv A$      | $A \land 1 \equiv A$     |
| 排中律 | $A \lor \neg A \equiv 1$ |                          |
| 矛盾律 |                          | $A \land \neg A \equiv 0$|

此外还有一些常用的逻辑恒等式

| 定律             | 表达式                                  |
| ---------------- | --------------------------------------- |
| 蕴涵等值式       | $A \Rightarrow B \equiv \neg A \lor B$ |
| 等价等值式       | $A \Leftrightarrow B \equiv (A \Rightarrow B) \land (B \Rightarrow A)$ |
| 假言易位         | $A \Rightarrow B \equiv \neg B \Rightarrow \neg A$ |
| 等价否定等值式   | $A \Leftrightarrow B \equiv \neg A \Leftrightarrow \neg B$ |
| 归谬论           | $(A \Rightarrow B) \land (A \Rightarrow \neg B) \equiv \neg A$ |

# 合取范式与析取范式

首先需要定义**简单析取式**和**简单合取式**

:::tip{title="简单析取式"}
有限个文字用“或”连接形成的析取式
:::
简单析取式的例子可以列出如下
- $p$
- $\neg p$
- $p\lor q$
- $p\lor \neg q$
- ...


:::tip{title="简单合取式"}
有限个文字用“与”连接形成的合取式
:::
简单合取式的例子可以列出如下
- $p$
- $\neg p$
- $p\land q$
- $p\land \neg q$
- ...

进一步定义**析取范式**与**合取范式**

:::tip{title="析取范式DNF（与或式，先与再或）"}
有限个简单合取式用“或”连接形成的析取式
$$
A_1\lor A_2\lor\cdots\lor A_n
$$
其中$A_i$是简单合取式
:::

:::tip{title="合取范式CNF（或与式，先或再与）"}
有限个简单析取式用“与”连接形成的合取式
$$
A_1\land A_2\land\cdots\land A_n
$$
其中$A_i$是简单析取式
:::

可以利用逻辑等价将命题改为析取范式或是合取范式

# 有效性和可满足性

**重言式**：在所有模型都为真的语句，又称为**有效的**语句，如
$$
A\lor \neg A
$$

**矛盾式**：在所有模型都为假的语句，如
$$
A\land \neg A
$$

**可满足式**：非矛盾式的语句。重言式是可满足式，但是可满足式不是重言式

重言式的反是矛盾式，可以利用这个关系证明命题，即**反证法**
$$
A\Rightarrow B 等价于 A\land \neg B 矛盾
$$