高阶逻辑(广义的谓词逻辑):

一阶逻辑,谓词变元的主目(对象)目前只用于个体变元,如果它能用于命题变元和谓词变元,那么便构成高阶逻辑。

eg. 数学归纳法: 对于任何公式F(x):头符合、可递推,便搞起来。

$\forall F((F(0) \wedge \forall x(F(x)\rightarrow F(x+1)))\rightarrow \forall x (F(x)))$

2.2.1 合式公式与翻译

合式公式:

引入函数,$f, g, h, ...$ 。自变量与因变量都属于 $D$ 的映射,或者应该说 $f(x_1, x_2, \cdots, x_n)$ 是 $D^n$ 到 $D$ 上的映射。

原子公式:

形如 $A(x_1, x_2, \cdots x_n)$ 的式子为谓词运算的原子(谓词)公式。

合式公式(谓词公式):

原子公式以 $\neg, \vee, \wedge, \rightarrow, \leftrightarrow , (), \forall x, \exists x$ 构成的公式。

<aside> 📌 符号化

① 指定这只、那些的时候,应该用常项了。

Untitled

②极限的定义

$P(x, y): x>y, \ \ \ Q(x, y): x < y$

$(\forall \epsilon)(\exists \delta)(\forall x) (((P(\epsilon, 0) \rightarrow P(\delta , 0)) \wedge Q(|x-a|, \delta) \wedge P(|x-a|, 0)) \rightarrow Q(|f(x)-A|, \epsilon))$

</aside>

2.2.2 约束变项与自由变项

$\forall xA, \exist xA$ 这类东西,称 $x$ 为指导变项,$A$ 为量词的辖域(作用域)。作用域中$x$ 的所有出现称为约束出现的(约束变项),其他非受量词约束的变项为自由出现的(自由变项)。

eg. $(\forall x)(F(x) \rightarrow G(x, y)) \wedge H(x, y)$,有约束x、自由x、自由y三个范畴的事物。

如约束变项和自由变项命名冲突,为了看起来方便,要么换掉约束项名字(换名规则),要么换掉自由项名字(代替规则)。

设 $A$ 为任意一个公式,若 $A$ 中无自由变项,则称 $A$ 为闭式,是命题。若 $A$ 有未被约束的自由变项,则 $A$ 可以看成它们的函数 $A(x_1, x_2, \cdots x_n)$。

2.2.3 谓词公式的解释(赋值)

一个解释要用非空个体域 $D$ 范畴下,一些特定的元素、函数、谓词来描述。

eg. $\forall x(F(x) \wedge G(x, a))$ ,如下解释$I$(注意0, 1是在表示真假哦):

$D=\{2, 3\}, \ \ a = 2, \ \ F:F(2)=0, F(3)=1, \ \ G:G(i, j)\equiv 1, \ \ i=2, \ \ j=3$

$A \Leftrightarrow \forall x(F(x) \wedge G(x, 2)) \Leftrightarrow (F(2) \wedge G(2, 2)) \wedge (F(3) \wedge G(3, 2)) \Leftrightarrow (0\wedge1)\wedge(1\wedge1) \Leftrightarrow 0$

结果是假的,也就是式子$A$在解释$I$下是假的。

谓词公式在任意解释下的永真、永假、可满足性,其判断相当于解决宇宙问题。

不过仍然,特殊情况下可以有一些规律。

2.2.4 代换实例

就是说把谓词公式的列表 $A_i$ 往命题公式的 $q_i$ 里挨个代。

永真式的代换实例仍为永真式(因为无论怎样结果都是真的啊),永假仍永假。

其余的判断,就构造几个解释说它可真可假,相当于构造几个命题变项的取值。

Untitled

e.g. $\forall x(F(x)) \rightarrow (\exists x\exists y(G(x, y)) \rightarrow \forall x(F(x)))$ 即 $p \rightarrow (q \rightarrow p)$ ,它永真。

Untitled