速通一阶逻辑
联结词
- \(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}} \]
是命题的析取范式。
图灵完备（全功能集）
\(\uparrow\) 与非和 \(\downarrow\) 或非都是全功能集。
推理
\(p \to q\) 是重言式，则 \(p \Rightarrow q\) 正确。
定律
- 析取三段论（合取应该取反来证）
- 构造性二难
谓词公式
个体域
个体变项和常项的定义域。默认为万事万物。
谓词
也有常变项，似乎靠是否抽象区分。
谓词是几元取决于参数有几个个体变项。
量词
\(\forall xF(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 xF(x) \Leftrightarrow \forall x \neg F(x)\)
全称辖域变形
- \(\forall x(F(x)\lor G) \Leftrightarrow \forall xF(x) \lor G\)
- \(\forall x(F(x) \land G) \Leftrightarrow \forall xF(x) \land G\)
这两个最基础。下面的思考方法是把 \(\to\) 看成一个 \(\lor\)，同时注意 \(\neg\) 在前项的作用。
- \(\forall x(F(x) \to G) \Leftrightarrow \forall x\neg F(x) \lor G \Leftrightarrow \neg\exists xF(x)\lor G(x) \Leftrightarrow (\exists xF(x)) \to G\)
我多打了一个括号方便观察。
最后一个简单：
- \(\forall x(G \to F(x)) \Leftrightarrow G \to \forall xF(x)\)
存在辖域变形
- \(\exists x(F(x)\lor G) \Leftrightarrow \exists xF(x)\lor G\)
- \(\exists x(F(x)\land G) \Leftrightarrow \exists xF(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 xF(x)\)
量词分配
- \(\forall x(F(x)\land G(x)) \Leftrightarrow \forall xF(x) \land \forall xG(x)\)
- \(\exists x(F(x)\lor G(x)) \Leftrightarrow \exists xF(x) \lor \exists xG(x)\)
前束范式
通过逻辑等值变形，把所有的量词提到公式开头，得到的公式被称为前束范式。
同一个公式的前束范式可能有很多个，甚至量词的类型都可以不同。