海伯伦定理

article/2025/7/3 20:35:24

谓词公式通过等价关系及推理规则化成相应的子句集

在谓词逻辑中,把原子谓词公式及其否定统称为文字。
定义3.5:任何文字的析取式称为子句。     例如: P(x)∨Q(x), ¬P(x,f(x))∨Q(x,g(x))
定义3.6:不包含任何文字的子句称为空子句。 空子句不含有文字,不能被任何解释满足,所以空子句是永假的,不可满足的。
任何谓词公式都可通过等价关系及推理规则化成相应的子句集。

1. 利用等价关系消去“→”和“↔”  ,例如公式

可等价变换成

2. 利用等价关系把“¬”移到紧靠谓词的位置上 ,上式经等价变换后

3. 重新命名变元,使不同量词约束的变元有不同的名字 ,上式经变换后

4. 消去存在量词
a.存在量词不出现在全称量词的辖域内,则只要用一个新的个体常量替换受该量词约束的变元,然后把存在量词删除。
    
b.存在量词位于一个或者多个全称量词的辖域内,此时要用Skolem函数f(x1,x2,…,xn)替换受该存在量词约束的变元。     
上式中存在量词(\existsy)及(\existsz)都位于(\forallx)的辖域内,所以需要用Skolem函数替换,设替换y和z的Skolem函数分别是f(x)和g(x),则替换后得到

5. 把全称量词全部移到公式的左边
6. 利用等价关系把公式化为Skolem标准形

Skolem标准形的一般形式是

其中,M是子句的合取式,称为Skolem标准形的母式。     上式化为Skolem标准形后得到

7. 消去全称量词
8. 对变元更名,使不同子句中的变元不同名 上式化为


9. 消去合取词,就得到子句集

等价性

定理3.1: 设有谓词公式F,其标准形的子句集为S,则F不可满足性的充要条件是S不可满足。 所以: 如果要证明一个谓词公式是不可满足的,则只要证明其相应的子句集是不可满足的就可以了

海伯伦域

判断一个子句的不可满足性,需要对个体域上的一切解释逐个进行判定,只有当子句对任何非空个体域上的任何一个解释都是不可满足的,该子句才是不可满足的。 海伯伦构造了一个特殊的域(海伯伦域),并证明只要对这个特殊域上的一切解释进行判定,就可知子句集是否不可满足。

定义3.7 :设S为子句集,则按下述方法构造的域H∞称为海伯伦域,记为H域。   
 (1)令H0是S中所有个体常量的集合,若S中不包含个体常量,则令H0={a},其中a为任意指定的一个个体常量。   
 (2)令Hi+1=Hi∪{S中所有n元函数f(x1,…,xn)|xj(j=1,…,n)是Hi中的元素},其中i=0,1,2,…。

例. 求子句集S={P(x)∨Q(x),R(f(y))}的H域。
解:此例中没有个体常量,任意指定一个常量a作为个体常量,得到
H0={a}
H1={a,f(a)}
H2={a,f(a),f(f(a))}
H3={a,f(a),f(f(a)),f(f(f(a)))}

H∞={a,f(a),f(f(a)),f(f(f(a))),…}


http://chatgpt.dhexx.cn/article/XZ8TUIJA.shtml

相关文章

费马小定理、欧拉定理与扩展欧拉定理(含证明)

这里就以自己做好的PPT图片的形式给出了:

量子笔记:单比特量子门、泡利矩阵

目录 0. 概要 1. 量子门基本性质 1.1 量子门与布洛赫球面的关系 1.2 量子门与幺正矩阵的关系 2. 泡利矩阵: 量子X,Y,Z,ID门 2.1 量子X门(量子非门) 2.2 量子Z门 2.3 量子Y门 2.4 量子ID门 6. 量子H门 7. 量子Z旋转门 7.1 量子S门 7.2 量子S…

图论之毕克定理证明

毕克定理是小学四年级奥赛内容,无意间从一本教材上看到,觉得定理蛮有意思,也和自己从事的工作有一些关联,就在网上找了一些证明资料,结合自己的思考,稍微挖掘了以下,聊以记录。 毕克定理是指一…

chapter 4 能带理论 energy band

继承自chapter 3 的自由电子模型: 4.1 单电子近似 One electron approximation 列出电子运动的薛定谔方程: E Ψ − ℏ 2 2 m ∇ 2 Ψ U Ψ E \Psi -\frac{\hbar^2}{2m} \nabla^2 \Psi U \Psi EΨ−2mℏ2​∇2ΨUΨ 根据电子在晶体中运动的实际情…

能带图最好的理解——克朗尼格-朋奈模型(Kronig-Penney模型)

布洛赫波函数 整体的思想还是基于建模,大家应该都知道在自由电子模型中,能量和波矢的关系 那么大家的第一个疑问首先是,空间结构的周期性应该反应在空间坐标上,为什么K空间也会满足周期性呢? 这里面就不得不说&…

固体物理-复习重点

晶体:是由离子,原子或分子(统称为粒子)有规律的排列而成的,具有周期性和对称性 非晶体:有序度仅限于几个原子,不具有长程有序性和对称性 点阵:格点的总体称为点阵 晶格:晶…

图书馆管理系统用例图

第一次画用例图,多多指教

网上选课系统用例图

转载于:https://www.cnblogs.com/whs2818388/p/4925219.html

学生成绩系统用例图模型

在uml模型共享平台上发布了一个学生成绩系统的需求,并且绘制出了用例图,如下图,欢迎大家参与讨论,该系统全部模型查看连接http://euml.trufun.net/ 本文转自 trufun 51CTO博客,原文链接:http://blog.51cto.…

UML用例图分析——铁路售票系统

该文档就是对简单铁路售票系统,写的用例图和用例规约。下面是目录个人水平有限,有需要的可以下载参考。有事可留言。下载链接:点击下载文档

简单的图书管理系统用例图(UML)

运用工具:Presson 自我评价:简单肤浅还可能是不规范的,初次接触用例图若有 错误请指出! 此外:本人至今是软件工程大一新生,希望能认识更多志同道合的人共同努力,交流学习经验&#xff0c…

“远程网络教学系统”UML用例图(练习题)

“远程网络教学系统”UML用例图(练习题) 题目用例图学生用户教师用户系统管理员 用例文档的示例学生用户的示例:学生用户查找课件教师用户的示例:教师用户登录系统管理员的示例:系统管理员维护网站页面 题目 “远程网…

UML基础、建模与设计实战笔记03第3、4章建模工具简介,常见uml建模工具,创建模块,创建类,用例图,参与者,用例,用例描述,用例之间的可视化表示,用例图建模技术及应用,进销存系统用例图

1、常见uml建模工具 建模工具应该具有的功能 绘图存储一致性检查对模型进行组织导航写作支持代码生成逆向项目集成支持多种抽象层和开发过程文档生成脚本编程 工具主要有 Rose PowerDesinger 2、StarUML的模型、视与图 starUML中清晰地区分了模型(model&#x…

UML实例(二):在线购物系统用例图

2019独角兽企业重金招聘Python工程师标准>>> 一、用例图 二、用例描述 用例名:添加购物车商品 简述:顾客有购买商品的意图,但是觉得需要考虑时,可执行添加购物车商品操作。 参与者:消费者 包含:无 扩展:无 继承:无 前置条件:顾客必须登录成功。 细节:在主…

使用Rational Rose创建BBS论坛用例图

📚文章目录 📫实训任务:创建BBS论坛用例图和类图。 📫任务:根据以上描述文字以及“会员相关的功能操作”图,构思并画出会员用户功能操作用例图。 📫实训任务:创建BBS论坛用例图和类…

网上投稿系统用例图

---------------------------------------------------------------------------------------------------------------------------- 也许你感兴趣的是我画这个图的工具: EA下载地址: EA8.0(Enterprise Architect)汉化版注册码中文教程.zip EA备份地址: E…

学生选课系统用例图,以及部分代码实现

上学期软件导论做的文档,学生选课系统,在文档的基础上,再代码实现以下 背景——用例图:一个基础的学生选课系统 ER图设计如下:(学生和课程是n - m的关系,可修改的原图找不到了,悉知) 库表设计&…

棋牌管理系统用例图

转载于:https://www.cnblogs.com/pgone/p/7867810.html

Rational Rose学习笔记02:创建用例图

文章目录 一、用例图概念二、用例图三元素(一)参与者(Actor)(二)用例(Use Case)(三)关系(Relation)1、关联关系(Associati…