定义
元谓词 中每个 叫作个体。如果每个个体都是常量、变量或者函数,就叫作一阶谓词,如果阶数最高的那个 是 阶谓词,则 叫作 阶谓词。
IMPORTANT
谓词的阶是从 开始编号的,一阶谓词没有被 R 过。而常见的自由 代数 中 的 ,或是 中函数的阶,都是从 开始编号的。
相比命题逻辑,还增加了存在量词和全称量词。
变元和项
所有个体变元 构成个体变元集 。所有个体常元 组成个体常元集 ,它们也是 的元素。项集 是 通过 中的 元运算 得到的东西,其中不含个体变元的称为闭项。
集合 叫作函数词集合。
谓词和原子公式
谓词 是一个 元关系,其中 。谓词逻辑中的原子公式是给谓词中的 以确定的个体得到的公式,比如 是一个谓词,但是 是一个原子公式。不含个体变元的公式称为闭式。
NOTE
谓词和原子公式的关系类似函数和函数值的关系。
谓词公式和谓词代数
谓词代数 是原子公式集 上的自由 -代数,其中 。把 叫作谓词公式集,里面的每个公式叫作谓词公式。谓词公式不是谓词。
IMPORTANT
谓词代数和项集都是自由 代数,但是它们的生成集不同, 也不同。
项集 的生成集是个体集 , 是函数词集合 , 中是所有的项;
谓词代数 的生成集是原子公式集 , 是 , 中是所有的谓词公式。
NOTE
不需要考虑 ,因为可以定义
量词深度和层次
谓词公式 的
- 量词深度 :遇到 取两边最深的,然后每次增加一个真的起约束作用的 就加
- 量词层次 :遇到 取两边最层的加 ,然后每次增加任意一个 就加
TIP
遇到存在量词,需要先转成全称量词。
NOTE
例如,考虑 ,则 ,而
自由
变元的自由
如果有 这样的式子,称 在这个谓词公式中约束出现,否则是自由出现。
NOTE
例如,在谓词公式 中, 约束出现,而 自由出现。
项的自由
设 是一个谓词公式,而 是一个自由变元。如果一个项 替换掉 之后, 里面的变元不会受到约束,就称 对于 自由。
NOTE
例如,设 ,则项 对于 中的 不自由,因为用 替换掉 中的 之后, 变成了 ,这时 里面的变元 受到了全称量词 的约束。
解释
解释域 负责把形式的个体常元集 、函数词集合 、谓词集合 全都转换到论域 上相关内容。
给定一个变元指派 ,可以唯一产生一个项解释 。
NOTE
这里 是 生成的自由 -代数,而 是一个 -代数。
对于谓词公式的赋值,只需要考虑原子公式即可,因为对原子公式的赋值可以唯一扩张为 的同态映射 。定义对原子公式的赋值 ,其中 ,而 是解释域 把关系 映到的另一个关系。
NOTE
可以说,有了项解释之后,谓词公式的赋值就确定了。
则 满足运算规则:
NOTE
和命题逻辑中的演算规则差不多,多了一个 。
若 并且 ,则称 和 语义等价 。若 ,则 ,并可以推广至将一个谓词公式中任何 的出现修改为 前后两个谓词公式语义等价。
证明方法
一阶谓词的演算用 表示。公理:
全称推广规则:对一般的 证明 之后,有 。
演绎定理也成立。
可以使用的结论:
其中,定义 和 。
TIP
证明含 的式子时,可以证明它的逆否式,因为公理里没有 ,所以转换成逆否式里的 会简化证明。
前束范式
前束范式 是具有这个形式的谓词公式:,其中 不含量词。斯柯伦范式在此基础上要求 都在 前面。
TIP
将谓词公式转化成前束范式的方法:把箭头转化成 、 和 ,然后把量词逐步移到所有东西之前。
性质
谓词演算也具有完备性等性质,略。