数理逻辑

1. 命题逻辑
   1. 命题及其表示 (1-1)
   2. 联结词及其他联结词 (1-2，1-6)
   3. 命题公式与翻译 (1-3)
   4. 真值表与等价公式 (1-4)
   5. 重言式与蕴含式 (1-5)
   6. 对偶与范式 (1-7)
   7. 推理理论 (1-8)
2. 谓词逻辑
   1. 谓词概念与表示 (2-1)
   2. 命题函数与量词 (2-2)
   3. 谓词公式与翻译 (2-3)

主要知识点

• 命题的概念、表示、类型（重言式、矛盾式、可满足式）、联结词的定义
• 命题变元、命题公式的概念及公式的正确翻译
• 真值表（$2^n$行）、等价式、蕴含式的概念
• 常用的等价式、蕴含式
• 对偶式的概念
• 范式、小（大）项、主合（析）取范式
• 命题演算的推理方法：真值表法、直接证法（P规则、T规则）、间接证法（反证法、CP规则）要求简单
• 谓词、量词、个体域
• 原子谓词公式、谓词演算的合式公式的概念、谓词公式的翻译

命题逻辑

基础概念

只有具有确定真值的陈述句，才是命题。

原子命题与复合命题：

• 原子命题：不能分解为更简单的陈述语句。
• 复合命题：由联结词、标点符号和原子命题复合结构组成的命题。

悖论不是命题，如：我正在说谎。

命题标识符：使用大写字母或者带下标的大写字母和数字，如；
$$
\begin{align*}
&P：今天下雨 \newline
&P_i：今天下雨 \newline
&\left[ 1 \right]：今天下雨
\end{align*}
$$

如果命题标识符表示确定的命题，则称为命题常量（有确定的真值）
如果命题标识符只表示任意命题的为指标值，则称为命题变元（没有确定的真值）

因为命题变元没有确定的真值，所以：$命题变元 \neq 命题$
当命题变元表示原子命题的时候称为 原子变元
真值指派：用特定命题将 $P$ 取代，使其具有确定的真值，称为对 $P$ 进行指派。

以 $P \vee Q$ 为例，$P$ $Q$ 是命题变元，被称为命题公式的分量，当我们为 $P$ $Q$ 进行真值指派（用确定的命题替代）后，$P \vee Q$ 就成为了一个有确定真值的命题了。

在命题公式中将分量的所有真值指派情况汇列成表，就形成了真值表。这里以 $P \vee Q$为例：

$P$	$Q$	$P \vee Q$
$T$	$T$	$T$
$T$	$F$	$T$
$F$	$T$	$T$
$F$	$F$	$F$

对于拥有 $n$ 个命题变元的命题公式，共有 $2^n$ 种真值指派情况。

合式公式？？有必要吗

联结词

常用的联结词

名称	符号
否定	$\neg$
合取	$\wedge$
析取	$\vee$
条件	$\rightarrow$
双条件	$\leftrightarrow$ 或 $\leftrightarrows$

其他的联结词：

名称	符号	解释
不可兼析取	$\overline{\vee}$	表示语义中的“不可兼或”，对于命题 $P \overline{\vee} Q$ 当且仅当$P$和$Q$的真值为$T，F$或者$F，T$时结果为$T$。也就是两者只能同时有一种为真。
条件否定	$\overset{c}{\rightarrow}$	其真值等于 $\rightarrow$运算真值的否定。$P \overset{c}{\rightarrow} Q \Leftrightarrow \neg(P \rightarrow Q)$
与非	$\uparrow$	对于命题 $P \uparrow Q$，当且仅当 $P$ $Q$ 均为 $T$ 时其真值为 $F$，否则真值为 $T$。
或非	$\downarrow$	对于命题 $P \downarrow Q$，当且仅当 $P$ $Q$ 均为 $F$ 时其真值为 $T$，否则真知为 $F$。换言之，对于 $P$ $Q$ 的真值，只要有至少一个为 $T$ 则 $P \downarrow Q$ 的真值为 $F$

关于“与非”和“或非”：
我们可以将“非”理解为真值中的“假”，“与”、“或”和逻辑与逻辑或进行关联。
因此“与非”也就是当命题变元 $P$ $Q$ 均为 $T$ 时才为 $F$；同理，“或非”就是 $P$ $Q$ 至少有一个为 $T$ 时为 $F$。
可以类比“合取（逻辑与）（$\wedge$）”和“析取（逻辑或）（$\vee$）”的规则，实际上与非和或非分别为他们真值的否定（可参考下面联结词的等价表）。

对应的真值表：

联结词的等价

最小的全功能联结词组为 $ \lbrace \neg , \vee \rbrace $ 或者 $ \lbrace \neg , \wedge \rbrace $，通常我们使用的为 $ \lbrace \neg , \vee , \wedge \rbrace $。，

其他联结词的出现是为了能够广泛而直接的表示命题之间的关系，这里我们将其他联结词的一种（或多种）等价公式列举出来以便理解。

名称	符号	等价公式
条件	$\rightarrow$	$P\rightarrow Q \Leftrightarrow ( \neg P \vee Q ) $
双条件	$\leftrightarrow$ 或 $\leftrightarrows$	$P\leftrightarrow Q \Leftrightarrow (P \wedge Q ) \vee (\neg P \wedge \neg Q)$
不可兼析取	$\overline{\vee}$	$A \overline{\vee} B \Leftrightarrow (P \wedge \neg Q )\vee(\neg P \wedge Q)$
条件否定	$\overset{c}{\rightarrow}$	$P\overset{c}{\rightarrow} Q \Leftrightarrow \neg ( P \rightarrow Q) \Leftrightarrow (P \wedge \neg Q)$
与非	$\uparrow$	$P \uparrow Q \Leftrightarrow \neg (P \wedge Q)$
或非	$\downarrow$	$P \downarrow Q \Leftrightarrow \neg (P \vee Q)$

命题的翻译

命题的翻译就是将自然语言转换为命题。

一般来说就分为两步：

1. 找到原子命题并用 $P$ $Q$ 表示。
2. 用合适的联结词表示出来

在自然语言中常包含“或”，但是在不同的语境下分为“排斥或”与“可兼或”，两者的翻译是不同的。
排斥或：例如：晚上我在家看电视或去剧场看戏

• 晚上在家和晚上去剧场不可能同时发生，因此为排斥或，可以对应联结词中的不可兼或。
• 令$P=在家看电视$ $Q=去剧场看戏$，若该命题为真，则应当将其翻译为： $ \left( P \wedge \neg Q \right) \vee \left( \neg P \wedge Q \right) $或者 $P \overline{\vee} Q$
  可兼或：例如：他是100米或400米赛跑冠军
• 他即可以获得 100 米冠军，也可以获得 400 米冠军，两者互不影响。
• 和上述情况相反，此处对应了普通的逻辑或 $\vee$

若在自然语言当中包含 “如果……那么”、“只有……才” 等词语，我们可以考虑使用 $\rightarrow$ 进行翻译。
在语义中“如果”表示的是前提条件，当前提条件为 $T$ 的时候之后的才有意义，才能整体判断这句话的真假；但当这个前提条件不满足时，整句话处在一种不确定的状态，在条件命题里规定为 “善意的推定”，因而讲这种情况确定为 $T$。

例：如果雪是黑的，那么太阳从东边出来。
我们令：$$P = 雪是黑的，Q=太阳从东边出来$$
则这句话可以用 $P \rightarrow Q$ 来表示

对于 $\leftrightarrow$ 来说则对应语义中的 “当且仅当”。因为“当且仅当”将两个命题紧密的结合在一起，而 $\leftrightarrow$ 从真值表上可以看出两个命题同真同假时才为真，也是紧密结合在一起的。

命题的类型及关系

命题公式的类型

有些命题公式无论进行何种真值指派，其结果恒为 $T$ 或 $F$，我们称这种命题公式为“重言式（永真式）”或者“矛盾式（永假式）”。

所有的非矛盾式均为可满足式，换言之，当存在至少一种真值指派使命题公式的结果为 $T$ 时，这个命题公式就是可满足式。

命题的关系

等价：
等价也称为“逻辑相等”，当命题公式 $A$ $B$ 中存在的原子变元相同，并且对于任意一组真值指派两者的真值永远相等，则 $A$ $B$ 是等价的，记作$A \Leftrightarrow B$。

根据等价，我们可以对命题公式中的子公式进行“等价置换”，通过这种形式我们可以推证一些复杂的命题公式（范式中也有所应用）。

蕴含：
蕴含的定义是建立在重言式的基础之上的：
当且仅当 $P\rightarrow Q$ 为重言式时，我们称 $P$ 蕴含 $Q$ ，记作 $ P \Rightarrow Q $。

蕴含具有四个基本的性质：
设 $A$ $B$ $C$ 为合式公式

1. 若 $A \Rightarrow B$ 且 $A$ 为重言式，则 $B$ 必为重言式
2. 若 $A \Rightarrow B$，$B \Rightarrow C$，则 $A \Rightarrow C$。蕴含关系是可以传递的。
3. 若 $A \Rightarrow B$，且 $A \Rightarrow C$，那么 $A \Rightarrow (B \wedge C)$
4. 若 $A \Rightarrow B$ 且 $C \Rightarrow B$，那么 $(A \vee C) \Rightarrow B$

因此在逻辑推理中我们常利用蕴含的这四条性质进行推证。

等价的充分必要条件：
设 $P$ $Q$ 为任意两个命题公式，$P \Leftrightarrow Q$ 的充分必要条件为：$P \Rightarrow Q$ 且 $ Q \Rightarrow P$。
以上也可作为两个命题公式等价的定义。

注意：
$\Rightarrow$ 不是联结词，同时 $P \Rightarrow Q$ 也不是命题。

与“双条件”“条件”

我们可以尝试建立这样一种联系：
等价 <–> 双条件 $\leftrightarrow$
蕴含 <–> 条件 $\rightarrow$
对于等价来说，假设命题公式 $A$ $B$ ，当命题公式 $A \leftrightarrow B$ 为重言式时 $A$ $B$ 是等价的（此时两个命题公式的结果均为 $T$ 或者 $F$）。
对于蕴含是类似的（定义既是如此）。

常用的等价、蕴含表

可参考左孝凌版《离散数学》P42-p43

命题定律

命题逻辑和普通运算一样具有一些运算性质，具体可以参考左孝凌版《离散数学》P15。这里置列举几个比较重要的定律：

命题定律	表达式
德·摩根定律	$\neg(P \wedge Q) \Leftrightarrow \neg P \vee \neg Q $ $ \neg(P \vee Q) \Leftrightarrow \neg P \wedge \neg Q $ 注意否定移入后合取与析取的变化
同一律	$P \vee F \Leftrightarrow P $ $ P \wedge T \Leftrightarrow P $
零律	$P \vee T \Leftrightarrow T $ $ P \wedge F \Leftrightarrow F$
否定律	$ P \vee \neg P \Leftrightarrow T $ $ P \wedge \neg P \Leftrightarrow F $

后三个将在 “范式” 中有所应用。

对偶与范式

对偶

在命题规律中常可以看到合取和析取是成对出现的，这一类而式子称为对偶式。

常用的对偶词有两对：

1. $ \wedge $ 和 $ \vee$
2. $ \uparrow $ 和 $ \downarrow$

求一个命题公式的对偶式，应当将其中的对偶词互换，并将特殊的 $T$ 与 $F$ 互换。
对于命题公式 $A$，它的对偶式记作 $A^*$。

范式

范式是为了将命题公式规范化，共有两种不同的形式：合取范式 与 析取范式。
在范式中只包含 $\neg \wedge \vee$ 三种联结词，并且仅由命题变元及其否定构成。

求任何一个命题公式的范式，可以通过一下三个步骤：

1. 将所有联结词化归为 $\wedge \vee \neg$
2. 利用德·摩根定律将 $\neg$ 移动到每个命题变元之前
3. 利用分配律、结合律等将其归约为合取范式或析取范式。

	合取范式	析取范式
型式	$A_1 \wedge A_2 \wedge \dots \wedge A_n , (n \geq 1 )$	$A_1 \vee A_2 \vee \dots \vee A_n , (n \geq 1 ) $

小项/大项

$n$ 个命题变元的合取式称为布尔合取或者小项；$n$ 个命题变元的析取式称为布尔析取或者大项；
对于 $n$ 个命题变元，共有 $2^n$ 个大项或者小项。
以命题变元 $P，Q，R$ 为例，其所有的小项（布尔合取）为：
$$
\begin{align*}
&P \wedge Q \wedge R，&& P \wedge Q \wedge \neg R，&& P \wedge \neg Q \wedge R，&& P \wedge \neg Q \wedge \neg R \newline
&\neg P \wedge Q \wedge R，&& \neg P \wedge Q \wedge \neg R，&& \neg P \wedge \neg Q \wedge R，&& \neg P \wedge \neg Q \wedge \neg R
\end{align*}
$$

我们以命题变元 $P，Q，R$ 的真值指派为基础对小项进行编码，对某一命题变元的指派 $T$ 和 $F$ 分别记为 $1$ 和 $0$，然后按照固定的顺序排列可以得到：
$$
m_{111},m_{110},m_{101},m_{100}
$$

小项具有如下的性质：

1. 当且仅当命题变元的真值指派和编码相同时小项的真值为 $T$，；
2. 任意两个不同的小项的合取式为 $F$；
3. 全体小项的析取为永真。

根据性质 1 我们可以通过编码写出对应的小项：
$$
\begin{align*}
&m_{111} = P \wedge Q \wedge R \newline
&m_{110} = P \wedge Q \wedge \neg R \newline
&m_{101} = P \wedge \neg Q \wedge R \newline
&m_{100} = P \wedge \neg Q \wedge \neg R
\end{align*}
$$

对于大项，整体上类似，但是在定义上有一些区别。
例如：

1. 大项是命题变元的析取式，同样也可以进行编码；
2. 当且仅当命题变元的真值指派与大项的编码相同时，其真值为 $F$；
3. 任意两个不同的大项的析取式为 $T$；
4. 全体大项的合取式为永假。

通过编码翻译出命题公式：：
简单的方式就是记住：
小项（合取式、主析取范式）中，编码为 $0$ 对应的命题变元添加否定， 为 $1$ 则不添加。
大项（析取式、主合取范式）中，编码为 $1$ 对应的命题变元添加否定， 为 $0$ 则不添加。

主析取范式/主合取范式

主析取范式：
对于一个命题公式，如果存在一个等价公式，并且这个公式仅由原式的小项的析取构成，则该等价公式称为原命题公式的主析取范式。

想要求出一个公式的主析取范式有两种方式：

1. 真值表法
2. 等价演算法

真值表法：
根据定理（P34），在真值表中命题公式为 $T$ 时的真值指派所对应的小项的析取即为公式的主析取范式。

因为使命题公式为 $T$ 的真值指派不止一种，所以主析取范式的形式形如：
$$
m_0 \vee m_1 \vee \dots \vee m_n
$$

等价演算法：
使用等价演算法需要利用前述的命题定律

通常的步骤为：

1. 化为析取范式（可参考“范式”中列出的步骤）
   1. 将所有联结词化归为 $\wedge \vee \neg$
   2. 利用德·摩根定律将 $\neg$ 移动到每个命题变元之前
   3. 利用分配律、结合律等将其归约为合取范式或析取范式。
2. 除去析取范式中所有永假的析取项
   • 根据命题定律$P \vee F \Leftrightarrow P$，因此去除并不影响真值。
3. 将析取式中重复出现的合取项以及相同的变元合并
4. 对合取项中没有出现的命题变元进行补充，即补充重言式 $P \vee \neg P$
   • 在一个有三个命题变元的公式中，其小项应当包含着三种命题变元，因此需要进行补充
   • 根据命题定律，$P \vee \neg P$ 为永真式，并且$ P \wedge T \Leftrightarrow P$，因此补充 $P \vee \neg P$ 并不会影响公式结果
5. 除去相同的小项，按编号排序。

当命题变元的个数和顺序固定以后，命题公式的主析取范式就是唯一的，因此可以使用主析取范式判断两个公式是否等价。

主合取范式：
与主析取范式类似，但是有一些不同。

在真值表法中，需要找到公式为 $F$ 时的真值指派所对应的大项；
在等价演算中，第二步需要去除所有永真的合取项；第四步中需要补充矛盾式 $P \wedge \neg P$。

成真/成假指派（赋值）

在一些题目中可能会要求写出命题的成真指派、成假指派，其定义比较简单：

成真指派(赋值)	成假指派(赋值)
主析取范式中出现的小项对应的指派	主合取范式中出现的大项对应的指派

推理理论

进行逻辑推理的方式有三种：

1. 真值表法
2. 直接证法
   • P 规则 和 T 规则
3. 间接证法
   • 反证法
   • CP 规则

真值表法就是通过列举所有真值指派进行分析，这里不在详述。

无论是哪种证法都需要正确的翻译命题。

直接证法

直接证法就是利用一组前提以及公认的推理规则，根据已知的等价或蕴含推演到有效的结论。
常用的规则有两种：

1. $P$ 规则： 表示前提，可以是题目中存在的，也可以是前面推到中出现的
2. $T$ 规则： 当一个或多个公式、重言蕴含着公式 $S$ ，则公式 $S$ 可以被引入到推理中（也就是可以通过等价、蕴含的形式将新的命题公式引入到推理中）

间接证法

首先引入一个概念： 相容
对于若干命题 $H_1 ,H_2, \dots, H_m$，如果存在一些真值指派使 $H_1 \wedge H_2\wedge \dots\wedge H_m$ 为 $T$，则称这些命题是相容的，否则为不相容（任何一组真值指派都为 $F$）。

设 $S$ 为前提，$C$ 为结论，我们要证明的是 :
$$
\begin{gather*}
S \Rightarrow C \newline
即证明\quad S \rightarrow C \quad为重言式 \newline
又\because \quad S \rightarrow C \Leftrightarrow \neg S \vee C \Leftrightarrow \neg( S \wedge \neg C) \newline
\therefore 证明 \quad \neg( S \wedge \neg C) \quad 为重言式或 \quad S \wedge \neg C \quad 为矛盾式即可
\end{gather*}
$$

结合上述“相容”的概念，我们只需要证明前提（$S$）和结论的否定（$\neg C$）不相容（矛盾式）即可证明命题 $ S\rightarrow C $为重言式。

在间接证法中存在一个 $CP$ 规则：
如果有 $(S \wedge R) \Rightarrow C$，即得证 $S \Rightarrow (R \rightarrow C)$。（由条件式的等价替换证明）。
由 $(S \wedge R) \Rightarrow C$ 证得 $S \Rightarrow (R \rightarrow C)$ 称为 $CP$ 规则，这种规则可以将结论中的 $R$ 作为附加条件进行证明。

谓词逻辑

基础概念

在一般的句子中分为主语和谓语两部分，主语通常为客体；而用以刻画客体的性质或关系的即为谓词。

例如：
“张三是大学生，李四是大学生”，其中的“是大学生”即为谓词。
“5小于7”，其中的“小于”即为谓词。

使用谓词表达命题需要包括客体和谓词字母两部分。通常使用大写字母表示谓词，用小写字母表示客体。
一个单独的谓词不是完整的命题，因此需要在谓词字母和后面添加客体，这个式子就被称为谓词填式。

以上面的示例为例：
令 $A$ 表示 “是大学生”，$a,b$ 分别表示张三和李四，则上述命题可表示为：$A(a),A(b)$;
令 $B$ 表示“小于”，$c,d$ 分别表示“5”和“7”，则上述命题可以表示为： $B(c,d)$

$A(a)$ 称为一元谓词，$B(c,d)$ 称为二元谓词，以此类推可以有 $n$ 元谓词（多元谓词）。
注意，代表客体的字母的顺序是有意义的，与事先约定有关。

类比命题逻辑中，命题公式并不等于命题，在谓词逻辑中也有类似的概念：
当 $a$ 为客体变元时，$A(a)$ 则被称为命题函数，只有当客体变元取特定的客体时，命题函数才为命题。

客体变元的范围：
客体变元的论述范围称为个体域，各种个体域综合在一起作为论述范围的域称为全总个体域（只有一个）。

特性谓词对全总个体域加以限制，用来确定命题函数的个体域。

量词：

	全称量词	存在量词
符号	$\forall$	$\exists$
含义	通常表示每一个、任何一个	通常表示存在一些、至少有一个
与特性谓词	常作为蕴含的前件	常作为合取项
示例 （$M(x)$为特性谓词）	$(\forall x)(M(x)\rightarrow H(x))$	$(\exists x)(M(x)\vee H(x))$