定义

元谓词 中每个 叫作个体。如果每个个体都是常量、变量或者函数,就叫作一阶谓词,如果阶数最高的那个 阶谓词,则 叫作 阶谓词。

IMPORTANT

谓词的阶是从 开始编号的,一阶谓词没有被 R 过。而常见的自由 代数 ,或是 中函数的阶,都是从 开始编号的。

相比命题逻辑,还增加了存在量词和全称量词。

变元和项

所有个体变元 构成个体变元集 。所有个体常元 组成个体常元集 ,它们也是 的元素。项集 通过 中的 元运算 得到的东西,其中不含个体变元的称为闭项。

集合 叫作函数词集合。

谓词和原子公式

谓词 是一个 元关系,其中 。谓词逻辑中的原子公式是给谓词中的 以确定的个体得到的公式,比如 是一个谓词,但是 是一个原子公式。不含个体变元的公式称为闭式。

NOTE

谓词和原子公式的关系类似函数和函数值的关系。

谓词公式和谓词代数

谓词代数 是原子公式集 上的自由 -代数,其中 。把 叫作谓词公式集,里面的每个公式叫作谓词公式。谓词公式不是谓词。

IMPORTANT

谓词代数和项集都是自由 代数,但是它们的生成集不同, 也不同。

项集 的生成集是个体集 是函数词集合 中是所有的项;

谓词代数 的生成集是原子公式集 中是所有的谓词公式。

NOTE

不需要考虑 ,因为可以定义

量词深度和层次

谓词公式

  • 量词深度 :遇到 取两边最深的,然后每次增加一个真的起约束作用的 就加
  • 量词层次 :遇到 取两边最层的加 ,然后每次增加任意一个 就加

TIP

遇到存在量词,需要先转成全称量词。

NOTE

例如,考虑 ,则 ,而

自由

变元的自由

如果有 这样的式子,称 在这个谓词公式中约束出现,否则是自由出现。

NOTE

例如,在谓词公式 中, 约束出现,而 自由出现。

项的自由

是一个谓词公式,而 是一个自由变元。如果一个项 替换掉 之后, 里面的变元不会受到约束,就称 对于 自由。

NOTE

例如,设 ,则项 对于 中的 不自由,因为用 替换掉 中的 之后, 变成了 ,这时 里面的变元 受到了全称量词 的约束。

解释

解释域 负责把形式的个体常元集 、函数词集合 、谓词集合 全都转换到论域 上相关内容。

给定一个变元指派 ,可以唯一产生一个项解释

NOTE

这里 生成的自由 -代数,而 是一个 -代数。

对于谓词公式的赋值,只需要考虑原子公式即可,因为对原子公式的赋值可以唯一扩张为 的同态映射 。定义对原子公式的赋值 ,其中 ,而 是解释域 把关系 映到的另一个关系。

NOTE

可以说,有了项解释之后,谓词公式的赋值就确定了。

满足运算规则:

NOTE

和命题逻辑中的演算规则差不多,多了一个

并且 ,则称 语义等价 。若 ,则 ,并可以推广至将一个谓词公式中任何 的出现修改为 前后两个谓词公式语义等价。

证明方法

一阶谓词的演算用 表示。公理:

全称推广规则:对一般的 证明 之后,有

演绎定理也成立。

可以使用的结论:

其中,定义

TIP

证明含 的式子时,可以证明它的逆否式,因为公理里没有 ,所以转换成逆否式里的 会简化证明。

前束范式

前束范式 是具有这个形式的谓词公式:,其中 不含量词。斯柯伦范式在此基础上要求 都在 前面。

TIP

将谓词公式转化成前束范式的方法:把箭头转化成 ,然后把量词逐步移到所有东西之前。

性质

谓词演算也具有完备性等性质,略。