数理逻辑

参考资料

• 命题逻辑 - 维基百科
• 一阶逻辑 - 维基百科

引入

数理逻辑 用数学方法研究 推理。它是计算机科学的基础：电路设计、程序验证、数据库查询、人工智能。

本章先讲 命题逻辑，再讲 谓词逻辑。

命题逻辑

命题

能 判断真假 的陈述句。真值用 $1$（真）或 $0$（假）表示。

「明天会下雨」「$1+1=2$」是命题；「请关门！」「$x+1=3$」不是命题。

联结词

符号	名称	读法
$\neg p$	否定	非 $p$
$p\land q$	合取	$p$ 且 $q$
$p\lor q$	析取	$p$ 或 $q$
$p\to q$	蕴含	若 $p$ 则 $q$
$p\leftrightarrow q$	等价	$p$ 当且仅当 $q$

真值表

$p$	$q$	$\neg p$	$p\land q$	$p\lor q$	$p\to q$	$p\leftrightarrow q$
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

tip

蕴含 $p\to q$ 只有「前真后假」时为假，其余情形都真。 $0\to$ 任何 = 真，对应「错误前提可以推出任何结论」。

命题公式

由命题变元、联结词、括号按规则组成。按真值情况分类：

• 永真式（重言式）：恒为真。
• 永假式（矛盾式）：恒为假。
• 可满足式：至少存在一种赋值为真。

重要等值式

双重否定	$\neg\neg p\Leftrightarrow p$
交换律	$p\land q\Leftrightarrow q\land p$，$p\lor q\Leftrightarrow q\lor p$
结合律	$(p\land q)\land r\Leftrightarrow p\land(q\land r)$
分配律	$p\land(q\lor r)\Leftrightarrow(p\land q)\lor(p\land r)$
德摩根律	$\neg(p\land q)\Leftrightarrow\neg p\lor\neg q$
蕴含等价	$p\to q\Leftrightarrow\neg p\lor q$
逆否等价	$p\to q\Leftrightarrow\neg q\to\neg p$
吸收律	$p\lor(p\land q)\Leftrightarrow p$

范式

• 析取范式（DNF）：若干 合取式之析取，如 $(p\land q)\lor(\neg p\land r)$。
• 合取范式（CNF）：若干 析取式之合取。
• 主范式：每个子式都包含全部变元（每个变元恰出现一次），具有 唯一性。

推理

推理形式

从 前提 $p_1,\dots,p_n$ 推出 结论 $q$，记为：

$$p_1\land p_2\land\dots\land p_n\Rightarrow q$$

推理 有效 $\iff (p_1\land\dots\land p_n)\to q$ 是 重言式。

常用推理规则

名称	规则
假言推理	$(p\to q)\land p\Rightarrow q$
拒取式	$(p\to q)\land\neg q\Rightarrow\neg p$
析取三段论	$(p\lor q)\land\neg p\Rightarrow q$
假言三段论	$(p\to q)\land(q\to r)\Rightarrow p\to r$
构造性二难	$(p\to q)\land(r\to s)\land(p\lor r)\Rightarrow q\lor s$

谓词逻辑

命题逻辑无法描述「所有人都会死」与「苏格拉底是人」推出「苏格拉底会死」这种含「所有」「存在」的推理，于是引入 谓词 和 量词。

谓词与量词

• 个体词：被研究的对象，用 $a,b,c$ 表示常元，$x,y,z$ 表示变元。
• 谓词：刻画对象性质或关系，记 $P(x)$、$R(x,y)$。
• 全称量词 $\forall x$：「对所有 $x$」。
• 存在量词 $\exists x$：「存在 $x$」。

量词的德摩根律

$$\neg\forall x\,P(x)\Leftrightarrow\exists x\,\neg P(x)$$ $$\neg\exists x\,P(x)\Leftrightarrow\forall x\,\neg P(x)$$

含义：「不是所有」等价「存在不是」；「不存在」等价「所有都不是」。

约束变元与自由变元

被量词约束的变元称 约束变元，未被约束的称 自由变元。换名时只能换约束变元，且不能与已有变元冲突。