从命题到对象与关系

命题逻辑可以把整句陈述当作一个字母,一阶逻辑则允许进入句子内部。例如 P(a) 可表达对象 a 具有性质 P,R(a,b) 可表达 a 与 b 之间的某种二元关系。谓词的位置有顺序:R(a,b) 与 R(b,a) 一般不是同一断言。常量用来指称对象,变量则为对对象作一般性陈述提供位置。

公式按照明确的语法规则形成:从原子公式出发,应用否定、合取等联结词及量词。变量出现可以是自由的,也可以受量词约束;没有自由变量的公式称为语句。P(x) 留有待赋值的位置,∀xP(x) 则把 x 约束起来。语法合格只说明写法符合规则,并不保证内容为真。

“一阶”指变量的取值范围是论域中的对象;让变量对这些对象的性质或关系取值,则进入高阶逻辑的范围。

参考:[1]

解释与满足

解释给出论域以及非逻辑符号的含义;在通常的一阶语义中,论域非空,常量指向其中的对象,一元谓词对应对象集合,多元谓词对应关系。对含自由变量的公式,还需要指定变量所取的对象。所谓满足,就是在这些指定之下,公式所要求的条件成立。

例如取论域为数 1 和 2,令 P 表示“是偶数”,常量 a 指向 2。此时 P(a) 为真,∃xP(x) 也为真,但 ∀xP(x) 为假,因为 1 不满足 P。全称量词要求论域中每一个对象都满足条件,存在量词只要求至少一个。量词遍历对象,而不是只检查已经命名的对象。

参考:[2] [1]

量词次序不是装饰

∀x∃yR(x,y) 与 ∃y∀xR(x,y) 的要求不同。前者允许为不同的 x 选择不同的 y;后者要求找到一个统一的 y,使它对每个 x 都满足关系。只调换两个量词的位置,就可能把一个真命题变成假命题。

可在两元素论域 {1,2} 中直接核验:令 R(x,y) 表示 x 与 y 相等。每个元素都能选择自身,因此 ∀x∃yR(x,y) 为真;却没有一个元素同时等于 1 和 2,因此 ∃y∀xR(x,y) 为假。这样的有限模型能清楚显示量词次序造成的差异,无须依赖含混的日常措辞。

参考:[3]

模型中的真与逻辑有效性

一个语句可在某个解释中为真、在另一个解释中为假;逻辑有效则要求它在所有允许的解释中都为真。同样,前提蕴涵结论,是说不存在让全部前提为真而结论为假的解释。只展示一个支持结论的模型,不能证明这种普遍的逻辑关系。

从 ∀xP(x) 推出 P(a) 是有效推理,因为常量 a 指称论域中的对象;从 ∃xP(x) 推出 P(a) 则一般无效,满足 P 的对象未必就是 a。可满足性仅要求存在一个使语句成立的解释。将这些概念分开,才能避免把某个特定世界中的事实,误当作纯粹由逻辑形式保证的结论。

语义有效性还可与形式证明相联系:一阶逻辑的完备性定理表明,适当演算中的可证明性能够捕获所有解释下的有效性。但这不提供一个对任意公式都能停下来回答“有效或无效”的判定程序;一般的一阶有效性问题不可判定。逻辑规则是否足以证明每个有效公式,与某个自动过程是否能在所有输入上完成判断,是两种不同要求,不能因为存在完备证明系统就把后者也视为已经解决。

参考:[4] [5]