一阶逻辑公式$A$与子句集$S$（命题规则）可相互转换。

一阶逻辑公式及“分拆”

本书讨论常用的两类规则：

（1）命题规则：由“原子命题”加“逻辑连词”构成；前述的式(15.5)即为命题规则，表现为“如果$\cdots$，那么$\cdots$。 ”的陈述句。 前面我们进行了讨论。

（2）一阶规则：由“原子公式”加“逻辑连词”构成；也叫一阶逻辑公式。
由于引入了“变量”故称为“公式”，它与平时所说的“公式”不同：它不是基于等号；也不一定成立（即不一定为真）。 当它在论域内总为真时，称为普遍有效；当它在论域内总为假时，称为不可满足的；当它在论域内的某个子集上为真时，称为可满足的。

我们看一些常见“原子公式”示例：

• 自然数$(X)$：表示“$X$是自然数”（一元关系谓词：谓词处于语法中的谓语地位。 ）；
• 父亲$(X,Y)$：表示“$X$是$Y$的父亲”（二元关系谓词）；
• $\sigma (X)=X+3$（运算公式，即函数表达式可作为原子公式）；
• $\forall X$：表示任意$X$（即对所有$X$，要求“全部”）（量词$\forall$：All）；
• $\exists X$：表示存在$X$（即至少有一个$X$）（量词$\exists$：Exist）。

有了“原子公式”，则可以构成更一般的“一阶规则”（以小写字母代表谓词、函数和常量；以大写字母代表变量和一阶逻辑公式；全称量词通常省去），如
$$\begin{array}{r}\forall X(\text{自然数(σ(X))}\leftarrow \text{自然数(X)})\end{array}\text{\hspace{1em}(15.16)}$$
其意思是：对于任意的$X$，括号中的规则成立，括号中的规则为： (若$X$是自然数，则$(X+3)$是自然数)。 由于一阶规则有变量，故它的表达比命题规则更丰富。

将“原子公式”称为正文字（其否定为负文字），文字用“或”字连接（析取）构成子句，子句用“且”字连接（合取）构成句子，但通常不去谈论由子句构成句子，而是讨论子句集（多个子句组成的集合）。

若子句集中有矛盾子句（它俩归结为空子句），则该子句集为空集（此时用“且”拼出的句子不能形成任何概念），即空子句是不可满足的、含有空子句的子句集是不可满足的。

若能把一阶逻辑公式$A$“分拆”成子句集$S$，则有定理：$A$是不可满足的当且仅当$S$是不可满足的。

“分拆”的技巧：

• 将公式调整成前束形范式：即对量词进行调整，使得量词均为非否定、出现在公式的最前面、辖域为整个公式体。
• 消去全部“存在量词”：因“$\exists X(A(X))$”等价于“$\forall X(\neg A(X))$”。
• 变形得到（合取型），称为司寇伦标准型。

若能将一阶逻辑公式$A$变为司寇伦标准型，则将其“全称量词”省去，用逗号代替合取符号，这便得到了一阶逻辑公式$A$的子句集$S$。这时，子句集$S$中的所有子句用“且”字连接形成句子，即为一阶逻辑公式$A$，故显然有二者的等价性：逗号代替合取符，则一阶逻辑公式“打破”成子句集；反之，将逗号改为合取符，则子句集“粘接”成一阶逻辑公式。

这样，就可以将“证明$A$是不可满足的”转化为“证明$S$是不可满足的”。

本文为原创，您可以：

• 点赞（支持博主）
• 收藏（待以后看）
• 转发（他考研或学习，正需要）
• 评论（或讨论）
• 引用（支持原创）
• 不侵权
  上一篇：15.5 剪枝优化(预剪枝（阻止生长）和后剪枝（“由长变短”）)
  下一篇：15.7 FOIL算法（找出含逻辑变量的公式）