数理逻辑归结法原理

16
3.2.2原子集
定义 3.2.2 下列集合称为子句集 S 的原子集： A＝｛所有形如 P(t1, t2,…,tn)的元素｝ 其中，P(t1, t2,…,tn)是出现在 S 中的任一谓词符号，而 t1，t2，…，tn 则是 S 的 H 域上的 任意元素。 定义 3.2.3 将没有变元出现的原子、文字、子句和子句集分别称作基原子、基文字、基 子句和基子句集。 定义 3.2.4 当子句集 S 中的某个子句 C 中的所有变元符号均以其 H 域中的元素替换时， 所得到的基子句称作 C 的一个基例。 例 3.2.2 对于子句集 S＝{P(a),P(x)∨P(f(x))},它的 H 域为{a,f(a),f(f(a)),…}。 对于子句 P(a)，因为其中不含有变元，所以它已是基子句，而且 aH，所以它也是基例。
20
3.3.1.2 置换的合成
置换的合成是将两个置换合成为一个置换。 定义 3.3.3 假设 ={t1/x1,t2/x2,…,tn/xn}, ={u1/y1,u2/y2,…,um/ym}是两个置换， 则它们的合成是一个新置换， 其作用于公式 E 时， 相当于先 后 λ 对 E 的作用。 它的定义如下： 先作置换{t1· /x1,t2· /x2,…,tn· /xn,u1/y1,u2/y2,…,um/ym}。 若 yi{ x1,…,xn}时，先从上述集合中删除 ui/yi。 若 ti· =xi 时，再从上述集合中删除 ti· /xi 。 删除以后剩下元素所构成的集合称作 与 的乘积，记作 · 。
17
3.2.3 H域上的解释
定义 3.2.5 如果子句集 S 的原子集为 A，则对 A 中各元素的真假值的一个具体设定都是 S 的一个 H 解释。 可以证明，在给定域 D 上的任一个解释 I，总能在 H 域上构造一个解释 I*与之对应，使得如果 D 域上 的解释能满足子句集 S，则在 H 域的解释 I*也能满足 S（即若 S|I=T，就有 S|I*=T） 。 定理 3.2.1 设 I 是子句集 S 在域 D 上的一个解释，则存在对应于 I 的 H 域解释 I*，使得若有 S|I=T，就 必有 S|I*=T。 定理 3.2.2 子句集 S 不可满足的充要条件是 S 对 H 域上的一切解释都为假。 证明 充分性：若 S 在一般域 D 上是不可满足的，必然在 H 域上是不可满足的，从而对 H 域上的一 切解释都为假。 必要性：若 S 在任一 H 解释 I*下均为假，必然会使 S 在 D 域上的每一个解释为假。否则，如果存在一 个解释 I0 使 S 为真，那么依据定理 3.2.1 可知，一定可以在 H 域找到相对应的一个解释 I*0 使 S 为真。这与 S 在所有 H 解释下均为假矛盾。

2 命题逻辑中的归结原理
归结原理的提出 归结原理(PrinciPle of resolution)又
称消解原理,1965年鲁滨逊（J.A.Robinson） 提出，从理论上解决了定理证明问题。归结原 理提出的是一种证明子句集不可满足性，从而 实现定理证明的一种理论及方法。
2 命题逻辑中的归结原理
一个公式的合一一般不唯一
3 替换与合一
定义10 设σ是原子公式集S的一个合一，如果对S的任何 一个合一θ都存在一个替换λ，使得
θ ＝ σ •λ 则称σ为S的最一般合一(Most General Unifier),简称MGU。
¬P(x，f(x)) [Q(x,g(x)) ¬R(x,g(x))]
[¬P(x，f(x)) Q(x,g(x))] [¬P(x，f(x)) ¬R(x,g(x))] 7、适当改名，使子句间无同名变元 [¬P(x，f(x)) Q(x,g(x))] [¬P(y，f(y)) ¬R(y,g(y))]
2 命题逻辑中的归结原理
推出空子句就说明子句集不可满足，原因是： – 空子句就是F，推出空子句就是推出了F。 由归结原理可知 ：L ∧¬ L ＝NIL 另外我们知道：L ∧¬ L ＝F（假），也就是 NIL F – 归结原理是正确的推理形式，由正确的推理形式 推出了F，则说明前提不真，即归结出空子句的 两个亲本子句至少有一个为假。
2 命题逻辑中的归结原理
– 而这两个亲本子句可能都是原子句集S中不可满 足的子句。
– 如果这两个亲本子句不是或不全是S中的子句， 那么它们必定是某次归结的结果。
– 同样的道理向上回溯，一定会推出原子句集中至 少有一个子句为假，从而说明S不可满足。
2 命题逻辑中的归结原理
推论: 设C1， C2是子句集S的两个子句，C1 2是它们 的归结式，则 （1）若用C1 2来代替C1， C2 ，得到新的子句集S1 ， 则由S1不可满足性可以推出原子句集S的不可满足 性。即

▪ 例如，Q1是子句pqr，Q2是子句pqws，q和q 是相反文字，子句prws是Q1和Q2的归结子句。
▪ 例如，Q1是子句q，Q2是子句q，q和q是相反文字， 子句□是Q1和Q2的归结子句。
▪ 例如，Q1是子句pqr，Q2是子句pws，在子句Q1 和Q2中没有相反文字出现，子句Q1Q2，即 pqrws不是Q1和Q2的归结子句。
▪ 有σ(q1…qn r1…rm)=1，即σ(Q)=1。 ▪ 证毕
反驳
▪ 定义：设Ω是子句集合，如果子句序列 Q1,…,Qn满足如下条件，则称子句序列 Q1,…,Qn为子句集合Ω的一个反驳。
▪ (1).对于每个1≤k<n，QkΩ
• Qk是Qi和Qj的归结子句，i<k，j<k。
▪ (2). Qn是□。
▪ Q1=q
Q1Ω
▪ Q2=q
Q2Ω
▪ Q3=□
▪ 因此，Q1, Q2,Q3是反驳.
▪ (3).根据命题逻辑紧致性定理，若子句集合Ω 不可满足，则有有穷子句集合Ω0，Ω0Ω，使 得Ω0是不可满足的。
▪ 若有穷子句集合Ω0是不可满足的，则Ω0中的子句必 出现相反文字。
▪ 假设有穷子句集合Ω0是不可满足的，且Ω0中的子句 不出现相反文字，那么，对于Ω0中子句的每个文字 qk，有赋值函数σ使得σ(qk)=1，因此，σ(Ω0)=1，Ω0是 可满足的，这样与Ω0是不可满足的相矛盾。
机械式方法
▪ 若证明Q1,…,Qn|=R，只要证明Q1…QnR 不可满足。
▪ 机械式证明：
• 公式Q1…QnR的合取范式； • 合取范式的所有简单析取范式，即Ω； • 证明Ω不可满足
▪ 则有Q1,…,Qn|=R。 ▪ 机械式地证明Ω不可满足是关键问题
子句与空子句

归结原理和闭算子的关系
归结原理和闭算子的关系可以概括为以下几点:
一、归结原理
归结原理是量子力学中的一个基本原理。

它表明,任何测量之和都可等效地被单一测量所代替。

二、闭算子
在量子力学中,作用在态向量上的线性算子如果对所有的本征值构成完备的本征向量集,则称其为闭算子。

三、测量与算子
量子力学中,对物理量的测量对应于某个线性赫密特算子在本征值基下的谱分解。

四、闭算子和测量
一个测量过程对应的算子是闭算子,其本征值和本征向量可提供量子系统的全要信息。

五、归结原理的数学表达
设A和B是两个kommutleierende算子,则两个测量过程的运算顺序可以交换: BA = AB
这reflectSTM Vertraty运行间的归结性。

六、闭算子满足归结性
任意两个闭算子都满足交换律,因此对闭算子的测量顺序可以任意交换,这正是归结原理的数学表达。

综上所述,在量子力学框架下,对物理量的测量由对应的闭算子描述,而闭算子满足交换律,这反映了量子测量中归结原理的本质要求。

归结原理与闭算子密不可分,是理解量子力学的关键。