离散数学 - 谓词逻辑

一、对比

1. 命题逻辑是研究不同简单命题间关系的，但谓词逻辑是研究简单命题内部结构的，是更加深入的考察。

2. 命题逻辑形成的公式只需要赋值就可以确定真值，但是谓词逻辑就不行。这是因为谓词逻辑将简单命题拆为量词、主词、谓词。量词和主词要求指明论域，谓词要求指明具体含义。这些都使原来 p=1 的简单事情变成了 $\forall xP(x,f(a))=1$ 的复杂事情。我必须规定论域、谓词含义、常元值（命题逻辑中只有 1 和 0，还被零元联结词的概念掩盖了，但是这里的 a 可以取一大堆值。本质是命题逻辑中的常元代表一个命题，而谓词逻辑里的 a 代表一个个体）、函数符号含义（在命题逻辑中不会出现普通函数，因为普通函数属于命题内部，命题逻辑不研究）。这就是解释存在的意义。

3. 赋值也有不同，在命题逻辑中赋值，是将命题变元赋成 0 或 1。在谓词逻辑中，是将自由变元赋成论域中的某个个体，说不定是苹果还是西瓜呢。

二、直观理解

1. 谓词可以有两种理解，对于一元谓词，可以理解为他描述了主体的一种性质。对于多元谓词，可以理解为不同主词间关系的描述。进一步来讲，对于关系来讲，大多关系都是可以用一个相等关系或者不等关系表达的。这些类方程可以简化思考，还便于找反例。一整个公式就像一个方程组一样。

2. 永真式和等值演算紧密联系，两者可以说是逻辑中最重要的部分。即恒等变形。

3. 逻辑中概念很多，对晦涩的概念应当有以下认识：

   • 有些概念难是难在书写形式没有具体定义，这种搞懂就好了，要是老师书写也不规范，没必要纠结。比如赋值，推论。

   • 有些概念为了更加 “数学”，所以不近人情，这种概念不可纠结。比如联结词。

   • 有些概念就为了使要描述的其他定理和定义更加简洁，本身没有存在的必要。比如初等公式，其提出可能只是为了更好的描述重言式。

   • 有些概念理解懂了基本含义不是结束，一定要理解概念提出是为了解决什么问题的，通俗的解释这个概念描述的现象，这才是正确方式。比如许多定理、某些等值演算。

   • 有些概念现在觉得画蛇添足，其实是为了后面的知识铺垫，所以不必纠结，有些概念理解不了，不如塌下心来做些题，在题中理解概念。

4. 我们分析一个公式，应当有两方面的意识：

   • 语法：具体的有代换
   • 语义：具体的有赋值

三、书写规范

1. $v$ 和 $v[x_1/d_1,...,x_n/d_n]$ 是两个不同的东西。原来就有一个赋值 $v$，然后我替换掉一些变元

2. 对公式求值有如下规则：$I(\forall xA(t))(v)$

   先利用合取展开成 $I(A(t))(v)$，然后在展开成 $I(t)(v)$，然后在展开成 $I(x)(v)$，然后又有 $I(x)(v[x/d])$。

四、重要定理

4.1 赋值与逻辑联结词交换顺序

比如 $I(A\vee B)(v)=I(A)(v)\vee I(B)(v)$ 这一类定理，说明了要想分析公式内部，可以通过，也必须通过赋值赋值的方式分析内部，这个定理看似平凡，但是是后面证明其他定理的重要基石。

这里还涉及到一个去量词的问题，当论域为有限集合的时候，就直接展开讨论就好了。当论域为无限集合的时候，对于全称量词，进行如下转化

$$\begin{aligned} I(\forall xA)(v)=1\leftrightarrow对于每个d\in D_I,I(A)(v[x/d])=1\\ I(\forall xA)(v)=0\leftrightarrow存在d\in D_I,I(A)(v[x/d])=0 \end{aligned}$$

存在量词也类似。

4.2 代换和赋值可交换顺序

$$I(A^{x_1,...,x_n}_{t_1,...,t_n})(v)=I(A)(v[x_1/I(t_1),...,x_n/I(t_n)])$$

这个公式也是跟上一条公式一样是基础，但是好像没有上一条有用，但是它本身的证明是一个归纳证明。

4.3 量词否定转换

$$\neg\forall A\leftrightarrow\exist x\neg A$$

这个定理完成了全称量词和存在量词之间的转换，但是会产生一个 $\neg A$ 结构，所以要分析的话，就需要借助赋值和逻辑联结词交换顺序来进行下一步的分析。

这个定理也可以用于进行定理证明中的等值演算，尤其是那些具有对偶性质的公式，比如下面的量词辖域收缩扩张，用赋值与逻辑联结词交换顺序证明了一个量词的定理，另一个一般用量词否定转换得到。

4.4 量词分配等值式

$$\forall x(A(x)\wedge B(x))\leftrightarrow \forall xA(x)\wedge \forall xB(x)$$

$$\exist x(A(x)\vee B(x))\leftrightarrow \exist xA(x)\vee \exist xB(x)$$

这是最通用的公式，没有对变元的限制，而且还十分容易理解。全称量词和合取、存在量词和析取的对照关系，有很好体现。

4.5 辖域的收缩与扩张

第一组

$$\forall x(A(x) \rightarrow B)\leftrightarrow \exist xA(x)\rightarrow B$$

$$\exist x(A(x) \rightarrow B)\leftrightarrow \forall xA(x)\rightarrow B$$

第二组

$$\forall x(A \rightarrow B(x))\leftrightarrow A\rightarrow \forall xB(x)$$

$$\exist x(A \rightarrow B(x))\leftrightarrow A\rightarrow \exist xB(x)$$

再次强调，$B$ 不代表 $B$ 中不含有 x，而是 x 不是 $B$ 的自由变元。

第三组

$$\forall x(A(x)\wedge B)\leftrightarrow \forall xA(x)\wedge B$$

$$\forall x(A(x)\vee B)\leftrightarrow \forall xA(x)\vee B$$

$$\exist x(A(x)\wedge B)\leftrightarrow \exist xA(x)\wedge B$$

$$\exist x(A(x)\vee B)\leftrightarrow \exist xA(x)\vee B$$

这些定理比前面的量词分配要普适性更高，析取和合取不再对应存在和全称，每一个量词都可以进行分配，然后可以用这组定理结合量词转换进行等值演算导出第一组和第二组。

4.6 量词交换顺序

$$\forall x\forall yA(x,y)\leftrightarrow \forall y\forall x A(x,y)$$

$$\begin{aligned} \exist x\exist yA(x,y)\leftrightarrow \exist y\exist x A(x,y)\\ \exist x\forall yA(x,y)\rightarrow \forall y\exist x A(x,y) \end{aligned}$$

证明在习题中有，而且两个定理是可以互推的。

4.7 换名规则

$$\forall xA(x) \leftrightarrow \forall yA(y)$$

$$\forall xA(x) \leftrightarrow \forall yA_y^x$$

下面那个是正确的，上面那个是错误的。因为可替换是个要求。这个定理主要用于转换前束范式，因为不同约束变元随着辖域的扩张，要换名防止重名，也可以使辖域的收缩与扩张的使用更加自然。注意这里只给了全程量词的换名规则，存在量词的换名规则需要自己推导。

五、概念串

5.1 项

• 不涉及谓词和量词的字符串，可以有变元、常元、函数。注意像并不等同于论域中的所有元素，常元也是需要解释才能被赋予具体意义的，所以只要解释不把常元取遍论域，有的元素就没办法是项。总的来说，常元是 a，而不是苹果。
• 基项：不出现变元的项，这个概念的提出主要是为了说明赋值可能会影响项的值，但不会影响基项的值。
• 项不一定是 1 或 0，它依然是可以使苹果，梨。但是经过谓词映射以后，就一定是 0 或 1 了。

5.2 公式

• 将一个谓词与对应项的组合成为原子公式，即 $P(t_1$,$t_2$,...,$t_n)$。
• 加上全称量词 $\forall x$ 修饰的原子公式和原子公式被称为初等公式。
• 原子公式经逻辑联结词、量词修饰过后被称为公式。
• 可以看到公式是比较完整的一个结构，我们一般讨论的也是公式的性质。

5.3 自由约束

• 有量词限制的变元被称为约束变元，没有量词限制的变元被称为自由变元。
• 被量词约束的范围成为辖域。
• 没有自由变元的公式被称为语句，语句就像基项一样，是为了不受赋值影响提出的，而且语句才有讨论的可能，还是一个挺重要的概念啊。
• 没有量词的公式被称为开公式。
• 将所有自由变元都用全称量词 $\forall$ 修饰后加在原公式之前，就获得了原公式的闭包。闭包可以理解为在进行某种操作后得到的结果还在这个集合中，就说该集合在该运算下闭合。闭包概念可能使为了在永真式中应用，因为有这样的结论：A 是永真式的充要条件是 A 的闭包是永真式。
• 自由变元才是真正通过赋值决定公式取值的因素，我们写 A(x)，是因为 x 是 A 的自由变元。有的时候 $A$ 里面含有 x，但因为 x 是约束出现，所以公式还是不是 A (x)。

六、冷门概念

6.1 二阶谓词逻辑

我们研讨的公式中，唯一可以变化的就是个体变元，被称为一阶谓词逻辑，也称狭谓词逻辑。当除了个体变元外还有函数变元时，就成了二阶谓词逻辑。

6.2 模型

如果对每个 $I$ 中的每个赋值 $v$ ，都有 $I(A)(v)=1$ ，就称 $A$ 在 $I$ 中为真，也称 $I$ 满足 $A$ ，$I$ 是 $A$ 的模型，记为 $I\models A$。

七、难题

7.1 符号化

• 表示唯一

  $$\exist x( P(x)\wedge\forall y(P(y)\rightarrow x=y) )$$

  $P(x)$ 即对具有性质的描述，公式表达的意思即所有满足性质的 y 都是 x

• 表示最大

  $$\exist x(P(x)\wedge\forall y(P(x)\rightarrow y<x\vee y=x)$$

  $P(x)$ 即对具有性质的描述，公式表达的就是所有满足性质的 y 都有 y$\leq$x 。

• 表示 z 是 x 和 y 的公约数

  $$\exist v (v*z = x)\wedge\exist v(v*z=y)$$

• D (x,y):x 能被 y 整除

  $$\exist v(v*y=x)$$

• x 是素数

  $$\neg (x=1)\wedge\forall u(\exist v(v*u=x)\leftrightarrow u=1\vee u=x)$$

  即 x 不等于 1，且任何能整除 x 的数只有 1 或者 x。别看写了这么多，这其实是个一元谓词

7.2 归纳证明

这个就是在有归纳定义的东西的浅浅的应用，证明时就有底向上，先证明基准情况，然后最后一步是把复杂情况用基准情况表示，这个好像动态规划啊。那么什么是复杂情况呢，在项中，基准情况就是常元和变元，而复杂情况就是将项用函数符号连接。在公式中，原子公式是基准情况，用联结词和量词修饰的就是复杂情况。但是在对情况进行讨论的时候，要注意即使值讨论比如说变元，也要区分是跟题目有关的变元还是跟题目无关的变元。这样往往讨论的情况要多一些。

7.3 永真式证明

对于含有 $\leftrightarrow$ 的式子，可以令 $\leftrightarrow$ 的一端为 1 或 0，然后得出子公式内部结论，用当且仅当连接，进行推导，直至得出另一侧的值为 1 或 0。

对于含有 $\rightarrow$ 的式子，可以令后件为 0，前件为 1，因为这是唯一一种取值为 0 的情况，然后得出矛盾。也可只令前件为 1，然后用推理定律得出后件。

当举反例的时候，一般只用在论域中放两个元素，因为其实是两种元素的代表。最常用的反例是是 “0110”

$$D^I=\{a,b\}\quad P^I(a)=0\quad P^I(b)=1\quad Q^I(a)=1\quad Q^I(b)=0\quad$$