一阶逻辑合式公式及解释

命题逻辑和一阶逻辑

称为一个推理( sequent )，如果使用Natural Deduction的方式进行推导( derivation )，可以由 得到 ，那么这个推理是有效的。
定义：

对于合理的推理 ，能否在真值表的语义下，保证当 为T时， 不可能是F。

若 中，当全 部成立时， 也成立，则称 语义蕴含 。

soundness：若 是合理的，则$$

completeness：若 ，则是 合理的

证明：太长不看

实际是想说：一个逻辑系统需要满足soundness和completeness的一致性。

signature：三个部分

分别是函数名、常数名、谓词名

一般省略 ，因为其可看作无参数的

一阶逻辑的公式中，两类：

一阶逻辑的语义：

proof-based logic：给出一个operative的，通过Natural Deduction方式的 证明

优点：一旦找到一个证明方式成功推导，即可证明

缺点：难以证明 ，需要遍历全部可能的证明方式，才能够得到结论

semantic-based logic：通过真值表验证 的正确性

优点：更容易证明 ，只要找到一个左侧为T的assignment，而右侧为F即可

缺点：想要证明 更困难，需要遍历全部的真值组合。

一阶逻辑evaluate的难点：每一个变量都是一个可能的具体值的占位符

对 ，每个x， 都为真，则最终取值为真

对 ，找到一个x0， 为真，则最终取值为真

如果 的结构为 等（解析树根节点），那么最终的真值可以按照各谓词公式的真假，遵循命题逻辑中的连接词运算进行求解

问题进一步转为求解 的真值。对此需要明确谓词常量的含义和term的含义。

的模型 ：

例， ，R是二元谓词，F是一元谓词， 包含：

环境：将变量映射到具体值的look-up table

对于在l环境下的满足性定义：

给出模型解释的时候，需要使用扩展签名，否则将会出现bug：

用解释的方式定义：

函数常量alma，

在解释空间中取值替换变量y（例如a），替换变量：

，此时出现问题， 没有定义，因为Interpretation的domain必须是 的子集。

于是扩展 为 ，此处的*是abc实际值的名字，

并且，原有定义下 为真，当且仅当对所有的 ， 为真

改为：

当且仅当对所有的 ， 为真

这一解释就没有问题了。

Logic in CS中的定义下，虽然未考虑 。对于模型的映射直接是

一个全局的具体取值A

其实是相同的，因为函数和谓词就是signature的组成部分。

检查任意性和存在性时，

变量：直接替换为A中的元素，相当于隐性定义了对于非signature中的元素，映射的结果是元素值自身。

在谓词逻辑中是重载的，对模型而言表示满足，对两个formula而言表示语义蕴含。

for all

一个模型满足一个公式组，当且仅当这一模型满足公式组中的每一个公式，如果这一公式组的每个模型都还满足另一个公式 ,那么这个公式组蕴含这一公式。

存在一个模型，使得 ，则 可满足

一阶逻辑无法表达传递闭包：

能否找到一个公式 ，公式中只包含两个自由变量u和v，一个谓词关系R，通过这个公式可以表达：

这样的R无法找到，这样的公式是无止尽的。

一阶逻辑公式的合理性是undecidable的：给定一个FOL公式 ， 是否成立？

这个问题无法解答。

==》FOL的满足性问题也是undecidable的

证明： 是合理的 当且仅当 是不可满足的（可满足：存在一个interpretation I，

一阶逻辑的生成规则

合式公式（wff）的集合按如下规则递归的定义：
简单和复杂的谓词 如果 P 是 n 元（n ≥ 0）谓词，则 Pa_1,...,a_n是合式的。如果 n ≤ 1，则 P 是原子。
归纳条款 I: 如果 Φ 是 wff，则 ┐ Φ 是 wff。
归纳条款 Ⅱ： 如果 Φ 和 ψ 是 wff，则 Φ∧ ψ， Φ∨ ψ，（Φ → ψ）和（Φψ） 是 wff。
归纳条款 Ⅲ： 如果 φ 是 包含变量 x 的一个自由实例的 wff，则 砢，φ和x，φ 是 wff。（此后在x，φ 和x，φ 中x 的任何实例都被称为约束的 — 而不是自由的。）
闭包条款： 其他东西都不是 wff。 下列四个公理是谓词演算的特征：
PRED-1:x Z(x) → Z(y)
PRED-2:Z(y) →x Z(x)
PRED-3:x (W → Z(x)) → (W →x Z(x))
PRED-4:x (Z(x) → W) → (x Z(x) → W)
它们实际上是公理模式，因为其中的谓词字母 W 和 Z 可以被任何谓词字母所替代，而不改变这些公式的有效性。 叫做全称普遍化的推理规则是谓词演算的特征。它可以陈述为
|- Z(x),x Z(x)
这里的 Z(x) 假定表示谓词演算的一个已证明的定理，而 砢娀（x) 是它针对于变量 x 的闭包。谓词字母 Z 可以被任何谓词字母所替代。
注意：全称普遍化类似于模态逻辑的必然性规则，它是
- P,- □ P 在公告板中列出了一些重要的元逻辑定理。
不像命题演算，一阶逻辑是不可判定性的。对于任意的公式 P，可以证实没有判定过程，判定 P 是否有效，（参见停机问题）。（结论独立的来自于邱奇和图灵。）
有效性的判定问题是半可判定的。按哥德尔不完备定理所展示的，对于任何有效的公式 P,P 是可证明的。
单体谓词逻辑（就是说，谓词只有一个参数的谓词逻辑）是可判定的。

什么是一阶逻辑

一阶逻辑是区别于高阶逻辑的数理逻辑，它不允许量化性质。性质是一个物体的特性；所以一个红色物体被表述为有红色的特性。 一阶谓词演算或一阶逻辑（FOL）允许量化陈述的公式，比如"存在着 x，..." (x) 或 "对于任何 x，..." （砢），这里的 x 是论域(domain of discourse)的成员。一阶（递归）公理化理论是通过增加一阶句子/断定的递归可枚举集合作为公理，可以被公理化为一阶逻辑扩展的理论。这里的"..."叫做谓词并表达某种性质。谓词是适用于某些事物的表达。所以，表达"是黄色"或"喜欢椰菜"分别适用于是黄色或喜欢椰菜的那些事物。 一阶逻辑是区别于高阶逻辑的数理逻辑，它不允

什么是一阶逻辑

一阶逻辑是研究数学中由个体、函数及关系构成的命题以及由这些命题经使用量词和命题连接词构成的更复杂的命题和这类命题之间的推理关系。在为数学的语言和推理建立形式系统的过程中，一阶逻辑处于核心地位，多数常见的数学公理系统都可在一阶逻辑中表述。（F.L.）G.弗雷格首先建立了一阶逻辑的形式系统(1897)。人们也称之为谓词演算。其后，A.N.怀特海和B.A.W.罗素使其进一步精确化(1910)。 1 正文 回到顶部意见反馈 相关搜索 大家都在搜 一阶逻辑公式 一阶逻辑与一阶理论 一阶逻辑的推理理论 离散数学 一阶逻辑 正文折叠编辑本段 在一阶逻辑中描述一个数学理论，首先会涉及这个理论所讨论的对象、定义

什么是一阶逻辑

实际上，一阶逻辑是一种形式系统（Formal System)，即形式符号推理系统，也叫一阶谓词演算、低阶谓词演算(Predicate Calculus）、限量词（Quantifier）理论，也有人称其为“谓词逻辑”，虽然这种说法不够精确。总之，不管怎么说，一阶逻辑就是一种形式推理的逻辑系统，是一种抽象推理的符号工具。 要注意的是，一阶逻辑不同于单纯的“命题逻辑”（Proposition Logic），因为，一阶逻辑里面使用了大量所谓“限量词变量”（Quantified variables），比如：∃x（意思是存在一个变量x），限量词符号“∃”是把字母“E”从左向右反转过来产生的，其原本的意思的