谓词演算在JavaScript中的应用

[Jocs]

谓词演算在JavaScript中的应用

相关概念

谓词

在离散数学中这样定义谓词：句子中表示主语属性的那部分。比如语句"x > 3"，其中变量x是语句的主语，第二部分“ > 3”表示了主语的“大于3”的属性，也就是谓词。上面的语句也可以表示为P(X),含义是命题函数P在X的值。其中P就是谓词。

在JavaScript中也有谓词的概念，JavaScript是一个只会返回true 或者 false的纯函数（对于唯一的输入只会有唯一的输入，除了通过传参不会引入外部变量，并且也不会改变外部对象）。比如下面的函数都是谓词：

const gt2 = x => x > 2
const lt2 = x => x <= 2
const isNumber = x => typeof x === 'number' && !isNaN(x) // 该方法可能考虑不周全

量词

在数学中主要有两种量词，一种是全称量词，一种是存在量词，下面将分别定义这两种量词：

全称量词：许多数学命题断言某一性质对于变量在某一特定域内所有值均为真，这一特定的域称为论域，这类语句可以用全称量词表示。

P(X)的全称量化是语句

​ ”P(X)对于x在其论域的所有值为真“。

可用符号∀xP(x)表示P(x)的全称量化，其中∀称为全称量词，其中命题∀xP(x)可以读作“对于所有的x，P(x)”。

存在量词：有一个个体使得某种性质成立，就可以用存在量化来表示。

P(X)的存在量化是命题

​ “论域中存在一个个体x满足P(x)”

可用符号∃xP(x)表示P(x)的存在量化，其中∃为存在量词。

在JavaScript中有与之相对应的概念，JavaScript数组中两个函数式的方法，every和some分别就是全称量词和存在量词。举个例子：

const array = [1, 2, 3, 4]
array.every(gt2) 
array.some(lt2) 

上面的例子中，论域是定义的数组array，其中为[1, 2, 3, 4]。全称量化every就表示在论域array中，每一个元素都需要满足谓词gt2，这样整个语句才为真。当然上面的全称量化的真值为假。因为存在反例，当取array中元素1时，gt2就是false。

同样存在量化some表示在论域array中，只要存在一个元素满足谓词lt2,那么整个语句就为真。上面的存在量化真值为真。当去array中元素1时，满足谓词lt2。

量词的逻辑等价

首先我们需要定义什么是逻辑等价：

涉及谓词和量词的语句是逻辑等价当且仅当无论用什么谓词带入这些语句，也无论为这些命题函数变量指定什么论域，它们都具有相同的真值。

在数学中，∀ x (P(x) ∧ Q(x)) 逻辑等价于 ∀ x P(x) ∧ ∀ x Q(x)。其中∧表示取两个语句的合取，也就是汉语中"且"。（证明略）

上面的的逻辑等价翻译成JavaScript如下：

const a = [1, 2, 3, 4]

const gt0 = x => x > 0
const lt5 = x => x < 4

const and = (f1, f2) => x => f1(x) && f2(x)
const or = (f1, f2) => x => f1(x) || f2(x)

a.every(and(gt0, lt5)) // true
a.every(gt0) && a.every(lt5) // true

最后两个语句是逻辑等价的，在某一论域，对一个合取表达式进行全称量化逻辑等价于分别对合取表达式的每一个语句进行全称量化然后再取合取。

同样的，在数学中，∃ x (P(x) ∨ Q(x)) 逻辑等价于 ∃ x P(x) ∨ ∃ x Q(x)，其中∨表示取两个语句的析取，也就是汉语中的‘或’。（证明略）

上面的逻辑等价翻译成JavaScript如下：

const a = [1, 2, 3, 4]
const gt2 = x => x >= 2 
const lt2 = x => x < 2

const and = (f1, f2) => x => f1(x) && f2(x)
const or = (f1, f2) => x => f1(x) || f2(x)

a.some(or(gt2, lt2))// true
a.some(gt2) || a.some(lt2) // true

上面最后两个语句是逻辑等价的，对于某一论域取析取得存在量化等价于分别对每一个析取语句进行存在量化然后在析取。

量化表达式的否定

量化表达式的规则成为量词的德.摩根律。可以用如下表达式表示：

┐∀ x P(x) 逻辑等价于 ∃ x ┐P(x).

┐∃ x Q(x) 逻辑等价于 ∀ x ┐Q(x).

我们可以这样理解第一个逻辑等价式，令P(X)表示x是鸟人，那么第一个等价式左边就是"不是所有的人都是鸟人"而等价式右边的含义是"至少存在一个人他不是鸟人",细想这两句话是等价的。

第二个逻辑等价式我们也可以同上面的方法解释，这儿就不赘述了。

上面两个逻辑等价式也可以翻译为Javascript。

const a = [1, 2, 3, 4]
const gt2 = x => x >= 2 
const lt2 = x => x < 2

!a.some(gt2) // false
a.every(lt2) // false

我们可以使用上面的逻辑等价式在全称量化和存在量化中相互转化，在JavaScript中，也就是可以在every 和some两个方法中通过一些逻辑运算符进行相互 。