离散数学之谓词逻辑

2020-02-25

前面总结了命题的逻辑，这篇文章将会对谓词的逻辑进行总结。

什么是谓词的逻辑

前面总结命题逻辑有一个很大的缺陷，就是无法准确的表达自然语言或数学语言中所有语句的确切意思，例如，命题逻辑无法判断“3号计算机正在运行”的真假。
谓词逻辑相较于命题逻辑具有更加强大的表达能力，谓词逻辑可以准确的表达出自然语言和数学语言中所有语句的意思，并且可以允许我们对各个对象直接的关系进行推理。

谓词

所谓的谓词与英语语法中的谓词的作用差不多，表达的都是个体性质或彼此之间的关系，
一个谓词一般用一个命题函数p(x1,x2…xn)表示，表示xn具有p的性质。
例如：

p(x)表示 X>3。那么p(4)就为真，p(2)就为真

量词

跟函数差不多，谓词逻辑就好比是一个函数，函数的变量一定需要有一个取值范围，而在谓词逻辑中量词就表示的是谓词所适用的范围(称为论域)，主要有两种量词：

全称量词∀：表示的是每一个个体都满足谓词函数的性质
存在量词∃：表示在所有的个体中至少有一个满足谓词函数的性质

其真值情况如下
|命题|为真|为假|
|:-:|:-:|:-:|
|∀xp(x)|每一个x都满足p|有一个x不满足p|
|∃xp(x)|有一个x满足p|没有满足p的x|

∀xp(x)相当于合取式p(1)∧p(2)∧…∧p(n)
∃xp(x)相当于析取式p(1)∨p(2)∨…∨p(n)
量词∀和∃比命题题演算中所有的逻辑运算符都具有更高的优先级，∃xp(x)∨q(x)其表示的是（∃xp(x)）∨q(x)

变量绑定

当量词作用于变量x时，我们就说这个变量的这次出现时约束的，反之，如果一个变量的出现没有非量词约束或设置为某一个确定的值，那么就可以说这个变量的出现是自由的
在逻辑表达式中一个量词作用到的部分称为这个量词的作用域。因此如果变量在公式中处于所有量词的作用域之外，那么这个变量就是自由的。

例如：∃x（x+y=1），中x就是约束的，而y是自由的。

又如：∃x(P(x)∧Q(x)) ∨∀xR(x)，第一个量词∃x的作用域是表达式P(x)∧Q(x)，而第二个量词∀x的作用域是表达式R(x)

逻辑等价式

所谓的谓词和量词的语句是逻辑等价的，意思是说，无论用什么谓词代入这些语句，也无论这些命题函数里的变量指定什么论域，它们都用相同的真值。我们用S≡T表示。

这里又中类型的等价式：

在有限个体域D={a1a2…an}中消去量词等值式：
- ∀XA(x)↔A(a1)∧A(a2)…∧A(an)
- ∃xA(x)↔A(a1)vA(a2)v…VA(an)
量词否定等值式
- ┐∀A(x)↔∃x┐A(x)
- ┐∃xA(x)↔∀x┐A(x)
量词辖域收缩与扩张等值式（B中不含x）
- ∀x(A(x)vB) ↔ ∀xA(x)vB,
- ∀x(A(x)∧B) ↔ ∀xA(x)∧B
- ∀x(A(x)→B) ↔ ∃xA(x)→B,
- ∀x(B→A(x) ↔ B→∀xA(x)
- ∃x(A(x)vB) ↔ ∃xA(x)VB,
- ∃x(A(x)∧B) ↔ ∃xA(x)∧B
- ∃x(A(x)→B) ↔ ∀xA(x)→B,
- ∃x(B→A(x)) ↔ B→∃xA(x)
量词分配等值式
- ∀x(A(x)∧B(x)) ↔ ∀xA(x)∧∀xB(x)
- ∃x(A(x)∨B(x)) ↔ ∃xA(x)∨∃xB(x)
  
  全称量词对“∧”有分配律,存在量词对“∨”有分配律

语句到逻辑表达式的翻译

例1 使用逻辑表达式翻译“班上每个学生都学过微积分”

首先，我们可以先对这句话进行重写，使得量词和谓词更加明显：对于班上每一个学生x来说，x一定学过微积分（设论域是班上的全体学生），那么这里很明显应该选取全称量词∀，只有一个谓语P(x)：学过微积分。那么这句话就可以翻译成：∀xp(x)。
如果论域是更为广泛的人群的话，这句话可以改写为：对于每个人x来说，如果x是班上的学生，那么x一定学过微积分，显然这个涉及到两个谓词：P(X)表示x学过微积分，Q(x)表示x是班上的学生，那么这句话就可以翻译为：∀x(Q(x)→P(x))

上面是涉及到一个变量的情况，更多的时候还需要考虑到又多个变量的情况。

例如翻译：两个正数的和一定是正数。假设论域是所有的实数。