速通一阶逻辑

发表于 2025-03-07 阅读次数： 3

联结词

$p \to q \Leftrightarrow \neg p \lor q$
$p \leftarrow q \Leftrightarrow q \to p$
$p \leftrightarrow q \Leftrightarrow (p \to q) \land (q \to p)$ （同或）

逻辑公式

保留几个不是常识的：

$p \land (q \lor r) \Leftrightarrow (p \land q) \lor (p \land r)$
$p \lor (q \land r) \Leftrightarrow (p \lor q) \land (p \lor r)$
$\neg (p \land q) \Leftrightarrow \neg p \lor \neg q$
$\neg (p \lor q) \Leftrightarrow \neg p \land \neg q$

层次

记住单项是 0 层公式。

赋值

对于 $u = (b_{1} b_{2} b_{3} \dots)_{2}$ ，按照顺序给 $p, q, r, \dots$ 赋值为 $b_{1}, b_{2}, b_{3}, \dots$ ，称为命题公式的一个赋值。

让命题为真的赋值 $u$ 叫成真赋值，反之叫成假赋值。

真值表

有 $n$ 个变元的公式有 $2^{n}$ 种赋值。将这 $2^{n}$ 种赋值的真值结果列出来，就称为真值表。

不难想到，真值表相同的公式在任何输入下行为相同，则两公式等价。

所以，本质不同的公式只有 $2^{2^{n}}$ 种。（即 ${0, 1}^{n}$ 到 ${0, 1}$ 的映射数）

逻辑范式

极大项

$u = (110)_{2}, M_{u} = (\neg p_{1} \lor \neg p_{2} \lor p_{3})$ 。

容易看出， $u$ 是唯一使得 $M_{u}$ 为假的赋值

合取范式

对于所有的成假赋值 $u_{i}$ ：

$M_{u_{1}} \land M_{u_{2}} \land \dots \land M_{u_{k}}$

是命题的合取范式。

极小项

$u = (110)_{2}, m_{u} = (p \land q \land \neg r)$ 。

容易看出， $u$ 是唯一使得 $m_{u}$ 为真的赋值

析取范式

对于所有的成真赋值 $u_{i}$ ：

$m_{u_{1}} \lor m_{u_{2}} \lor \dots \lor m_{u_{k}}$

是命题的析取范式。

图灵完备（全功能集）

$↑$ 与非和 $↓$ 或非都是全功能集。

推理

$p \to q$ 是重言式，则 $p \Rightarrow q$ 正确。

定律

析取三段论（合取应该取反来证）
构造性二难

谓词公式

个体域

个体变项和常项的定义域。默认为万事万物。

谓词

也有常变项，似乎靠是否抽象区分。

谓词是几元取决于参数有几个个体变项。

量词

$\forall x F (x)$ ，对于个体域内所有 $x$ 都有 $F (x)$ 。

$\exists x F (x)$ ，个体域内至少有一个 $x$ 满足 $F (x)$ 。

指导变项

跟在量词后面的项是指导变项。指导变项受约束出现。约束范围称为量词辖域。

量词的优先级很高，若没有括号，只有紧随其后的才是辖域。比如 $\forall x F (x) \land G (x)$ ，只有 $F (x)$ 是辖域。

自由出现

不被量词约束的个体变项自由出现。

没有自由出现的式子叫闭式。

解释

指定个体域；
对所有的个体常项、函数、谓词给出定义；

完成解释后，所有闭式都是命题。

赋值

对所有自由出现的个体变项赋值。

完成解释和赋值后，所有谓词公式都是命题。

存在解释和赋值能称为真命题的叫 逻辑有效式。重言和矛盾的定义是平凡的。

代换实例

把逻辑公式中的逻辑变项代换成解释赋值后的谓词公式，称为逻辑公式的代换实例。

重言逻辑公式的代换实例是重言式，矛盾逻辑公式的代换实例是矛盾式。这样不必进行解释也可能判断谓词公式的类型。

逻辑等值式

定义比较自然：如果 $A \leftrightarrow B$ 是重言式，则 $A \Leftrightarrow B$ 。其中 $A, B$ 是谓词公式。

量词否定

$\neg \forall x F (x) \Leftrightarrow \exists x \neg F (x)$
$\neg \exists x F (x) \Leftrightarrow \forall x \neg F (x)$

全称辖域变形

$\forall x (F (x) \lor G) \Leftrightarrow \forall x F (x) \lor G$
$\forall x (F (x) \land G) \Leftrightarrow \forall x F (x) \land G$

这两个最基础。下面的思考方法是把 $\to$ 看成一个 $\lor$ ，同时注意 $\neg$ 在前项的作用。

$\forall x (F (x) \to G) \Leftrightarrow \forall x \neg F (x) \lor G \Leftrightarrow \neg \exists x F (x) \lor G (x) \Leftrightarrow (\exists x F (x)) \to G$

我多打了一个括号方便观察。

最后一个简单：

$\forall x (G \to F (x)) \Leftrightarrow G \to \forall x F (x)$

存在辖域变形

$\exists x (F (x) \lor G) \Leftrightarrow \exists x F (x) \lor G$
$\exists x (F (x) \land G) \Leftrightarrow \exists x F (x) \land G$

同样的，把 $\to$ 看成一个 $\lor$ ：

$\exists x (F (x) \to G) \Leftrightarrow \neg \forall x F (x) \lor G (x) \Leftrightarrow \forall F (x) \to G$
$\exists x (G \to F (x)) \Leftrightarrow G \to \exists x F (x)$

量词分配

$\forall x (F (x) \land G (x)) \Leftrightarrow \forall x F (x) \land \forall x G (x)$
$\exists x (F (x) \lor G (x)) \Leftrightarrow \exists x F (x) \lor \exists x G (x)$

前束范式

通过逻辑等值变形，把所有的量词提到公式开头，得到的公式被称为前束范式。

同一个公式的前束范式可能有很多个，甚至量词的类型都可以不同。