-
2021-05-23 05:08:30
摘要:
广义上,程序设计过程就是定理证明过程,因而程序综合与机器定理证明关系密切.通过一般情况下,构造性的证明过程才能抽取程序.归结原理是一种反证法,人们早已知道可以从归结证明中抽取顺序程序,并且已经证明可以从归结证明树抽取分支程序.由于归结原理的反证法本质,不能保证其证明是构造性的,因此不能保证能够抽取循环程序,但是利用数学归纳法可以使用归结原理来抽取循环体,从而抽取循环程序.本文利用归结原理进行计算机定理证明,然后从归结证明树中抽取程序. 这篇论文主要做了如下工作:第一,用C/C++语言设计和实现基于归结原理的定理计算机证明系统,该系统能够证明一阶谓词逻辑公式,并构造归结证明树.第二,针对形如(?)(?)P((?),(?))的定理证明问题,设计并实现程序综合的程序,该程序可以从归结证明树中抽取程序,抽取的程序能够根据输入(?)计算输出(?)且满足P((?),(?)).该抽取程序的工作过程是变换归结证明树,从变换后的归结证明树的叶结点开始,向树根的方向逐个结点抽取程序,每个结点抽取的程序与其子结点抽取的程序和本身相关,最终根结点的程序就是计算输出(?)的程序.第三,本文阐述了如何利用数学归纳法抽取循环程序的方法,该方法能够从递归描述的问题中抽取循环程序. 本文的实现是考虑计算机资源限制的,并不对所有定理证明都能给予很好的解答,因此有些定理的程序可能无法抽取.本文提出了基于归结原理实现定理自动证明和程序抽取方面有待解决的问题,这些问题的解决将使得定理机器证明和程序综合从理论走向实用.
展开
更多相关内容 -
Resolution 归结原理
2020-11-15 13:20:27Resolution 归结原理 还是好久没写博客了,最近课太多了太忙了害,熬过这几个月,以后会慢慢恢复的。 和取范式 满足一种特殊形式的sentences,conjunction of disjunctions of literals(文字),一个原子命题的符号A...Resolution 归结原理
还是好久没写博客了,最近课太多了太忙了害,熬过这几个月,以后会慢慢恢复的。
合取范式
满足一种特殊形式的sentences,conjunction of disjunctions of literals(文字),一个原子命题的符号A或者他前面加上一个 ¬ A \neg A ¬A都称为文字。
disjunction of literals形式如:均用析取符号 ∨ \vee ∨连接,比如 A ∨ B ∨ C A\vee B \vee C A∨B∨C
conjunction of disjunction of literals(合取范式): 多个disjunction of literals用合取符号连接 ∧ \wedge ∧,比如: ( A ∨ B ∨ C ) ∧ ( D ∨ ¬ E ) (A\vee B\vee C)\wedge (D\vee \neg E) (A∨B∨C)∧(D∨¬E)
上面和的合取范式称为CNF。语义等价 ≡ \equiv ≡ 表示两个sentences可以互相转换(语义等价),比如 A ≡ B A \equiv B A≡B , 可以参考knowledge 1中提供的语义等价公式表来进行转换。
任何范式都是可以转换其他语义等价的合取范式。
将knowledge base中的任意一个sentence转换为一个CNF(通过语义等价),然后将合取去掉,分成一个个disjunction of literals,将分拆开的DOL(disjunction of literals简写)组成一个新的knowledge base。这样将一个原来的一个knowledge base转换为了一个新的 knowledge base(KB简写)。
即$KB \equiv KB' $
归结
A , ¬ A A, \neg A A,¬A 称为互补文字.
若 $l_{i} ‘ 和 ‘ `和` ‘和‘ m_{j}$ 为互补文字,则可以把 l 1 ∨ l i , m j ∨ m 1 l_{1}\vee l_{i}, m_{j}\vee m_{1} l1∨li,mj∨m1 使用归结原理可以将 $l_{i} $ 和 $ m_{j}$ 去掉可以化简为 l 1 ∨ m 1 l_{1}\vee m_{1} l1∨m1 从上述的式子中去掉.(归结规则)
每一次归结只能拿一对来进行归结,然后下一次还可以拿另外一对进行归结.对于一个KB可以将使用等价规则将每一个sentence转换为合取范式,然后再将合取范式转化为一个个全是析取的式子(DOL)组成一个新的KB’,然后对于KB’中的DOL进行归结可以得到一个新的DOL,加入到KB’中。
归结例子
S = K B , ¬ α S={KB,\neg \alpha} S=KB,¬α, 我们称S为Resolution closure
具体流程:将alpha变为 ¬ α \neg \alpha ¬α,后加入到KB(通过语义等价转换为一个合取范式然后生成一个KB’)中组成一个新的集合KB’,然后在这基础上进行归结, 由于归结是有限,总会有停止情况,如果最后能够归结出一个空子句则表示 K B ⊨ α KB\models \alpha KB⊨α,对于上述的归结,每归结一次将生成的句子放到S中,然后直到停止之后,得到的就是RC(S),如果要证明 K B ⊨ α KB\models \alpha KB⊨α,则RC(S)中一定存在一个空语句。
上述过程证明了规则是可靠(sound)的。
S(是KB和 ¬ α \neg \alpha ¬α)是永假的,则表示不存在一个真值使得每一个sentences为真,若S为永假,则可以推出RC(S)中包含一个空语句。
完备性可靠性得证。
A* Search
设计一个算法,任意给一个KB能否推出a。
- 初始状态 K B , ¬ a {KB,\neg a} KB,¬a
- 找两个子句归结得到一个新的 K B , ¬ a , n e w s e n t e n c e s {KB,\neg a,new sentences} KB,¬a,newsentences(可以分成很多种情况,类似一个树划分为无数个节点)
- 然后进行继续划分节点搜索
- 直到首次到达终止状态
Horn and Definite Clauses
- 正文字,负文字(带否符号的)
- Defineite clauses: 很多个文字的析取,而且这些文字中有且仅有一个是正的
- Horn Clauses: 很多文字的析取,至多有一个正的,也可以全是负的
- 两个Horn Clauses进行归结得到的Clauses一定是一个Hron Clauses
- 析取为disjunction,合取为conjunction
-
归结原理
2021-05-23 05:08:59相关文献1引言推理技术是实现人工智能的基本技术之一,其中...而归结演绎推理是基于归结原理的在计算机上得到了较好实现的一种推理技术,是一种有效的机器推理方法。归结原理的出现,使得自动定理证明成为了可能,同时...相关文献
1引言推理技术是实现人工智能的基本技术之一,其中自然演绎推理是基于常用逻辑等价式以及常用逻辑蕴含式(统称推理规则)的推理技术,即从已知事实出发,利用推理规则进行推出结论的过程。这种推理过程与人类的思维过程极其相似,但在计算机上实现起来存在诸多困难。而归结演绎推理是基于归结原理的在计算机上得到了较好实现的一种推理技术,是一种有效的机器推理方法。归结原理的出现,使得自动定理证明成为了可能,同时也使得人工智能技术向前迈进了一大步。2条件连接词及永真蕴含2.1条件连接词及其真值表图1真值表无论是命题逻辑还是谓词逻辑,均可用连接词把一些简单命题连接起来构成一个复合命题,以表示一个比较复杂的含义。其中条件连接词→:称为“条件”或“蕴含”。P→Q表示“P蕴含Q”,即“如果P,则Q”。其真值表如图1。2.2永真蕴含定义1:对于谓词公式P和Q,如果P→Q永真,则称P永真蕴含Q,且称Q为P的逻辑结论,称P为Q的前提,记作P Q。由以上定义1及真值表...
(本文共3页)
阅读全文>>
1 引 言 可扩展标识语言[1](extensiblemarkuplanguage,XML)是标准标识语言(standardmarkuplanguage,SGML)的一个子集,具有简洁、灵活和结构化的优点。它为Web上的信息提供统一的存储和交换格式,具有良好的应用前景,被看作是未来通用的数据格式[2]。尽管XML在诸多领域中得到了广泛的应用,然而XML只是从形式上统一了语法表示。作为一种定义文档结构的描述语言,XML在实现计算机信息交换的过程中存在很多局限,不支持语义完整性约束声明,对复杂对象语义的描述能力非常有限,而XML处理器本身也不能理解文档的语义。为了增强XML的数据交换和互操作计算能力,需要将XML语法同对象的语义结合起来。一种方法是将本体映射到XML文档结构上,利用XML文档结构与XML文档之间的关系使XML文档与本体相关联,从而使XML文档能够表达对象语义。文献[3]将本体中的概念和概念之间的关系映射到XML文档...
(本文共5页)
阅读全文>>
一、前言 为了保持使用有序子句的语义归结原理,即01一归结原理在归结过程中,唯一选择归结文字的优点,消除01一归结原理不完备的缺点,作者曾在文献〔7〕中提出了配锁的语义归结原理,即IDI一归结原理.在讨论ID工一归结原理时,对子句中文字的配锁和解释.1都不加任何限制.因此1型ID工一归结原理(在归结过程里的每一次归结中,一个亲本子句的归结文字是子句中有最小锁的文字,另一个亲本子句的归结文字是子句中有其例在I下为真的文字中有最小锁者)仅仅对基子句集是完备的.而对一般子句集完备的2型工D工一归结原理,已经将限制消弱到在归结过程里的每一次归结中,仅仅要求一个亲本子句的归结文字是子句中有最小锁的文字,而对另一个亲本子句中的归结文字没有要求. 文献〔7〕也指出了,如果在配锁的语义归结原理中,对每一次归结都限制为:在两个亲本子句中的归结文字都是该子句中有最小锁的文字,那么这种配锁的语义归结原理,甚至对于基子句集也是不完备的. 本文仍然讨论配...
(本文共8页)
阅读全文>>
-
离散数学——归结原理
2012-01-02 10:03:44归结原理是一种推理规则。从谓词公式转化为子句集的过程中看出,在子句集中子句之间是合取关系,其中只要有一个子句不可满足,则子句集就不可满足。若一个子句集中包含空子句,则这个子句集一定是不可满足的。归结... -
人工智能归结原理实验
2022-04-03 10:01:44归结原理运行结果1.2.代码简陋,还请包涵 前言 提示:这里可以添加本文要记录的大概内容: 考察 命题逻辑归结推理 要求 熟悉C++迭代器使用,有一定离散数学基础 复杂式子无法实现 提示:以下是本篇.提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档
文章目录
前言
考察 命题逻辑归结推理
要求 熟悉C++迭代器使用,有一定离散数学基础
复杂式子无法实现
一、流程
二、步骤
0.声明
typedef string Formula; typedef vector<string> SubsentenceSet; typedef string::iterator FormulaIter; typedef string::reverse_iterator FormulaRevIter; // 公式符号定义 const char EQ = '#'; // 存在量词符号 const char UQ = '@'; // 全称量词符号 const char IMPLICATION = '>'; // 蕴含符号 const char NEGATION = '~'; // 否定符号 const char CONJUNCTION = '&'; // 合取符号 const char DISJUNCTION = '|'; // 析取符号 const char CONSTANT_ALPHA[] = {'a', 'b', 'c', 'd', 'e', 'i', 'j', 'k'}; const char FUNC_ALPHA[] = {'f', 'g', 'h', 'l', 'm', 'n', 'o'};
1.消去蕴含词和等值词
//消去蕴含连接词 Formula &RemoveImplication(Formula &f) { FormulaIter iter; while ((iter = find(f.begin(), f.end(), IMPLICATION)) != f.end())//寻找蕴含符号 { *iter = DISJUNCTION; // 将蕴含符号替换为析取符号 FormulaRevIter revIter(iter); revIter = GetBeginOfFormula(revIter, f.rend()); // 查找蕴含前件 iter = revIter.base(); // 反向迭代器到正向迭代器 f.insert(iter, NEGATION); // 在前件前面插入否定 } return f; }
2.使否定词仅作用于原子公式
//将否定符号移到紧靠谓词的位置 Formula &MoveNegation(Formula &f) { FormulaIter iter = find(f.begin(), f.end(), NEGATION); while (iter != f.end()) { if (*(iter + 1) == '(') { // 否定不是直接修饰谓词公式,需要内移 // 否定符号修饰着带量词的谓词公式 if (*(iter + 2) == EQ || *(iter + 2) == UQ) { // 量词取反 *(iter + 2) == EQ ? *(iter + 2) = UQ : *(iter + 2) = EQ; string leftDonePart(f.begin(), iter + 5); // 移除否定符号 leftDonePart.erase(find(leftDonePart.begin(), leftDonePart.end(), NEGATION)); string rightPart(iter + 5, f.end()); // 否定内移 rightPart.insert(rightPart.begin(), NEGATION); // 递归处理右部分 MoveNegation(rightPart); string(leftDonePart + rightPart).swap(f); return f; } else { // 修饰着多个公式,形如~(P(x)|Q(x)) iter = f.insert(iter + 2, NEGATION); // 内移否定符号 while (1) { iter = FindFormula(iter, f.end()); //assert(iter != f.end() && "No Predicate Formula!"); FormulaIter iter2 = FindPairChar( iter, f.end(), '(', ')'); ++iter2; if (IsConnector(*iter2)) { *iter2 == DISJUNCTION ? *iter2 = CONJUNCTION : *iter2 = DISJUNCTION; iter = f.insert(iter2 + 1, NEGATION); } else break; } f.erase(find(f.begin(), f.end(), NEGATION)); // 清除原否定符号 return MoveNegation(f); } } else if (*(iter + 1) == NEGATION) { // 两个否定,直接相消 f.erase(iter, iter + 2); return MoveNegation(f); // 重新处理 } else { string leftDonePart(f.begin(), iter + 1); string rightPart(iter + 1, f.end()); MoveNegation(rightPart); string(leftDonePart + rightPart).swap(f); return f; //iter = find(iter + 1, f.end(), NEGATION); } } return f; }
3.使量词间不含同名指导变元
//适当改名使量词间不含同名指导变元,对变元标准化。 Formula &StandardizeValues(Formula &f) { set<char> checkedAlpha; FormulaIter iter = FindQuantifier(f.begin(), f.end()); while (iter != f.end()) { char varName = *++iter; // 获取变量名 if (checkedAlpha.find(varName) == checkedAlpha.end()) { checkedAlpha.insert(varName); } else { // 变量名冲突了,需要改名 // 获取新名子 char newName = FindNewLowerAlpha(checkedAlpha); checkedAlpha.insert(newName); // 查找替换右边界 FormulaIter rightBorder = FindPairChar( iter + 2, f.end(), '(', ')'); // 将冲突变量名替换为新的名子 *iter = newName; replace(iter, rightBorder, varName, newName); iter = rightBorder; // 移动到新的开始 } iter = FindQuantifier(iter, f.end()); } return f; }
4.化为前束范式
//化为前束范式。 Formula &TransformToPNF(Formula &f) { FormulaIter iter = FindQuantifier(f.begin(), f.end()); if (iter == f.end()) return f; else if (iter - 1 == f.begin()) { // 量词已经在最前面 iter += 3; string leftPart(f.begin(), iter); string rightPart(iter, f.end()); TransformToPNF(rightPart); // 递归处理右部分 (leftPart + rightPart).swap(f); } else { // 量词在内部,需要提到前面 string quantf(iter - 1, iter + 3); // 保存量词 f.erase(iter - 1, iter + 3); // 移除量词 f.insert(f.begin(), quantf.begin(), quantf.end()); return TransformToPNF(f); // 继续处理 } return f; }
5.消去存在量词
//消去存在量词。 Formula &RemoveEQ(Formula &f) { set<char> checkedAlpha; FormulaIter eqIter = find(f.begin(), f.end(), EQ); if (eqIter == f.end()) return f; FormulaRevIter left = leftleft(FormulaRevIter(eqIter), f.rend()); FormulaRevIter uqIter = findRev(left, f.rend(), UQ); if (uqIter == f.rend()) { // 该存在量词前没有任意量词 char varName = *(eqIter + 1); char newName = GetNewConstantAlha(f); auto rightBound = FindPairChar(eqIter + 3, f.end(), '(', ')'); //assert(rightBound != f.end()); replace(eqIter + 3, rightBound, varName, newName); // 常量化 f.erase(eqIter - 1, eqIter + 3); // 移除存在量词 } else { // 记录公式中已经存在的字母 copy_if(f.begin(), f.end(), checkedAlpha); const char oldName = *(eqIter + 1); // 准备任意量词的函数来替换该存在量词 const char funcName = FindFuncAlpha(checkedAlpha); string funcFormula; funcFormula = funcFormula + funcName + '(' + *(uqIter - 1) + ')'; f.erase(eqIter - 1, eqIter + 3); // 移除存在量词 ReplaceAlphaWithString(f, oldName, funcFormula); } //RemoveOuterBracket(f, f.begin()); return RemoveEQ(f); // 递归处理 }
6.消去全称量词
//消去全称量词。 Formula &RemoveUQ(Formula &f) { FormulaIter uqIter = find(f.begin(), f.end(), UQ); while (uqIter != f.end()) { uqIter = f.erase(uqIter - 1, uqIter + 3); // 直接移除全称量词 uqIter = find(uqIter, f.end(), UQ); // 继续扫描 } //RemoveOuterBracket(f, f.begin()); return f; }
7.化公式为合(&)取范式
//化为合取范式。 Formula &TransformToConjunction(Formula &f) { FormulaIter dis = find(f.begin(), f.end(), DISJUNCTION); FormulaRevIter left = leftfind((FormulaRevIter)dis, f.rend()); FormulaIter leftt = left.base() - 1; FormulaIter right = rightfind(dis + 1, f.end()); FormulaRevIter leftcon = findRev((FormulaRevIter)dis, left, CONJUNCTION); FormulaIter lefttcon = leftcon.base() - 1; FormulaIter rightcon = find(dis, right, CONJUNCTION); if (leftt != lefttcon && rightcon == right) { cout << string(dis + 1, right) << endl; cout << string(leftt + 1, lefttcon) << endl; cout << string(lefttcon + 1, dis) << endl; string temp = "(" + string(dis + 1, right) + "|" + string(leftt + 1, lefttcon) + ")&(" + string(dis + 1, right) + "|" + string(lefttcon + 1, dis - 1) + ")"; // cout << temp << endl; f.replace(leftt, right, temp); } else if (leftt == lefttcon && right != rightcon) { // cout << string(leftt + 1, dis) << endl; // cout << string(dis + 1, rightcon) << endl; // cout << string(rightcon + 1, right - 1) << endl; string temp = "(" + string(leftt + 1, dis) + "|" + string(dis + 1, rightcon) + ")&(" + string(leftt + 1, dis) + "|" + string(rightcon + 1, right - 1) + ")"; // cout << temp << endl; f.replace(leftt, right, temp); } else if (leftt != lefttcon && right != rightcon) { string str1 = string(leftt + 1, lefttcon); string str2 = string(lefttcon + 1, dis); string str3 = string(dis + 1, rightcon); string str4 = string(rightcon + 1, right); cout << str1 << endl; cout << str2 << endl; cout << str3 << endl; cout << str4 << endl; string temp; if (str1 == str3) { temp = str1 + "&(" + str2 + "|" + str4 + ")"; } else if (str1 == str4) { temp = str1 + "&(" + str2 + "|" + str3 + ")"; } else if (str2 == str3) { temp = str2 + "&(" + str1 + "|" + str4 + ")"; } else if (str2 == str4) { temp = str2 + "&(" + str1 + "|" + str3 + ")"; } f.replace(leftt, right + 1, temp); } return f; }
8.消去合取词,得到子句集
这里没有对子句做标准化,即不同的子句用不同的变元,和前面的标准化大同小异。
//消去合取词,以子句为元素组成一个集合S。 void ExtractSubsentence(SubsentenceSet &subset, Formula &f) { FormulaIter leftIter = f.begin(); FormulaIter middleIter = find(f.begin(), f.end(), CONJUNCTION); while (middleIter != f.end()) { if (*leftIter == '(' && *(middleIter - 1) == ')') subset.push_back(string(leftIter + 1, middleIter - 1)); else subset.push_back(string(leftIter, middleIter)); leftIter = middleIter + 1; middleIter = find(middleIter + 1, f.end(), CONJUNCTION); } if (*leftIter == '(' && *(middleIter - 1) == ')') subset.push_back(string(leftIter + 1, middleIter - 1)); else subset.push_back(string(leftIter, middleIter)); }
9.合一算法
合一代码,直接调用syncretism函数。
bool syncretism(const string tf1, const string tf2, vector<transform> &mgu) //合一方法,判断是否可进行合一 { string f1 = tf1, f2 = tf2; while (!same(f1, f2)) //f1与f2中的符号不完全相同时才进入while循环 { transform t = dif(f1, f2); //得到f1和f2的一个差异集,并把它赋给t int flag = legal(t); if (flag == 0) return false; else { mgu.push_back(t); f1 = change(f1, mgu.back()); f2 = change(f2, mgu.back()); cout << "after change:" << endl; cout << "f1:" << f1 << endl; cout << "f2:" << f2 << endl; if (same(f1, f2)) return true; //f1和f2相同时就停止循环 } } return false; } bool same(const string f1, const string f2) //判断两个谓词f1和f2是否相同 { if (f1.length() == f2.length()) { int i = 0; while (i < f1.length() && f1.at(i) == f2.at(i)) i++; if (i == f1.length()) return true; else { return false; } } else return false; } transform dif(const string f1, const string f2) //求解f1和f2的差异集 { int i = 0; transform t; while (f1.at(i) == f2.at(i)) //第i个相等时就转向比较i+1,直到遇到不相等时就跳出while循环 i++; int j1 = i; while (j1 < f1.length() - 1 && f1.at(j1) != ',') //从不相等的部分开始,直到遇到‘,’或到达结尾时跳出while循环 j1++; if (j1 - i == 0) return t; t.t_f1 = f1.substr(i, j1 - i); //将f1中的不相同的项截取出来放入变量t.t_f1中 int j2 = i; while (j2 < f2.length() - 1 && f2.at(j2) != ',') j2++; if (j2 - i == 0) return t; t.t_f2 = f2.substr(i, j2 - i); //将f2中的不相同的项截取出来放入变量t.t_f2中 while (t.t_f1[j1 - i - 1] == t.t_f2[j2 - i - 1]) //去除相同的部分 { t.t_f1.erase(j1 - 1 - i); t.t_f2.erase(j2 - i - 1); j1--; j2--; } return t; } int legal(transform &t) //判断置换t是否合法 { if (t.t_f1.length() == 0 || t.t_f2.length() == 0) return 0; if (var(t.t_f2)) { if (var(t.t_f1) && (varData(t.t_f1) == varData(t.t_f2))) //不能代换合一 return 0; else return 2; } if (!var(t.t_f1)) //若t_f1和t_f2都不是变量,也不能合一 return 0; string temp; temp = t.t_f1; t.t_f1 = t.t_f2; t.t_f2 = temp; //在t_f1是变量而t_f2不是变量的情况下,交换t_f1和t_f2 return 1; } string varData(string s) //该函数是剥去外层括号 { if (s.length() == 1 || s.length() == 0) return s; if (s.length() > 1) { int i = 0; while (i < s.length() && s.at(i) != '(') i++; int j = i; while (j < s.length() && s.at(j) != ')') j++; string ss = s.substr(i + 1, j - i - 1); return varData(ss); } } bool var(const string s) { if (s.length() == 0) return false; if (s.length() == 1 && s[0] >= 'A' && s[0] <= 'Z') return false; if (s.length() > 1) { int i = 0; while (i < s.length() && s.at(i) != '(') //略过不是'('的字符 i++; int j = i; while (j < s.length() && s.at(j) != ')') //略过')'前的字符 j++; string ss = s.substr(i + 1, j - i - 1); //取出'('和')'之间的串 return var(ss); //递归调用var } else { return true; } } string change(string f, transform q) //该函数查找t_f2在f中的位置并用t_f1替代f中相应的t_f2 { int i = f.find(q.t_f2); while (i < f.length()) { i = f.find(q.t_f2); if (i < f.length()) f = f.replace(i, q.t_f2.length(), q.t_f1); } return f; }
10.归结原理
int finditer(string s, char a, char b)//*iter.find("~P")的时候莫名报错,于是手写查找。 { for (int i = 0; i < s.length(); i++) { if (s[i] == a && s[i + 1] == b) { return i; } } return 0; } bool resolution(SubsentenceSet &subset) //归结 { for (vector<string>::reverse_iterator rbegin = subset.rbegin(); rbegin != subset.rend();) //从尾部,即目标公式开始归结 { bool f = false; bool rev = false; //是否取反 string s = *rbegin; string ss; FormulaIter left = s.begin(); FormulaIter middle = find(left, s.end(), DISJUNCTION); string goal = string(left, middle); //归结元素 string _goal = pdrev(goal, rev); //归结元素的逆 vector<string>::reverse_iterator iter; while (middle != s.end()) //寻找归结元素的逆,找到末尾结束 { iter = findreviter(subset, _goal, rev); if (iter == subset.rend()) //找不到继续循环 { left = middle + 1; middle = find(left, s.end(), DISJUNCTION); goal = string(left, middle); _goal = pdrev(goal, rev); } else { f = true; //找到标记 break; } } if (!f) //判断是否找到,前面最后一个left和middle没有处理,这里继续处理。 { iter = findreviter(subset, _goal, rev); if (iter == subset.rend()) { rbegin++; continue; } } ss = (*iter); char cc = goal[0]; int len = goal.length(); if (rev) { cc = goal[1]; len -= 1; } dosyncretism(s.substr(s.find(cc), len), ss.substr(ss.find(cc), len), *iter); //合一 //擦除归结了的式子 (*rbegin).erase((*rbegin).find(goal), goal.length()); string c = ""; if (rev) { c += _goal[0]; (*iter).erase((*iter).find(_goal[0]), _goal.length()); } else { c += _goal[0] + _goal[1]; (*iter).erase(finditer(*iter, _goal[0], _goal[1]), _goal.length());//这里~P找不到,于是手写寻找函数。 } //(*iter).erase(*iter.find(c),_goal.length());找不到, //合并剩余式子 string newstr = (*rbegin) + "|" + (*iter); //擦除多余析取符 for (int i = 0; i < newstr.length(); i++) { if ((i == 0 || i == newstr.length() - 1) && newstr[i] == DISJUNCTION) { newstr.erase(i, 1); i -= 1; } else if (newstr[i] == DISJUNCTION && newstr[i + 1] == DISJUNCTION) { newstr.erase(i + 1, 1); } } cout << endl; //删除旧的式子,添加新的式子。 subset.erase(subset.rbegin().base()); subset.erase(iter.base() - 1); subset.push_back(newstr); rbegin = subset.rbegin(); count(subset); //归结出空,则结论为真,归结结束。 if (newstr == "") { return true; } } return false; }
运行结果
1.
Input: (@x)(D(x)>(B(x)&F(x)))&(@x)(F(x)>N(x))&(@x)(G(x)>D(x))&~(@x)(G(x)>N(x)) Elimination of implied symbols://消去蕴含 (@x)(~D(x)|(B(x)&F(x)))&(@x)(~F(x)|N(x))&(@x)(~G(x)|D(x))&~(@x)(~G(x)|N(x)) Move the negation sign to the front of each predicate://处理非符 (@x)(~D(x)|(B(x)&F(x)))&(@x)(~F(x)|N(x))&(@x)(~G(x)|D(x))&(#x)(G(x)&~N(x)) Standardization of variables://变元标准化 (@x)(~D(x)|(B(x)&F(x)))&(@y)(~F(y)|N(y))&(@z)(~G(z)|D(z))&(#q)(G(q)&~N(q)) Eliminate existential quantifiers://消去存在 (@x)(~D(x)|(B(x)&F(x)))&(@y)(~F(y)|N(y))&(@z)(~G(z)|D(z))&(G(a)&~N(a)) Convert to a front bundle://化为前束 (@x)(@y)(@z)(~D(x)|(B(x)&F(x)))&(~F(y)|N(y))&(~G(z)|D(z))&(G(a)&~N(a)) Omit universal quantifiers://略去全称 (~D(x)|(B(x)&F(x)))&(~F(y)|N(y))&(~G(z)|D(z))&(G(a)&~N(a)) Standardization of Conjunction://化为合取式 (~D(x)|B(x))&(~D(x)|F(x))&(~F(y)|N(y))&(~G(z)|D(z))&G(a)&~N(a) Eliminate the conjunction://子集 ~D(x)|B(x) ~D(x)|F(x) ~F(y)|N(y) ~G(z)|D(z) G(a) ~N(a) after change://合一 f1:N(a) f2:N(a) mgu={ a/y } ~D(x)|B(x) ~D(x)|F(x) ~G(z)|D(z) G(a) ~F(a) after change: f1:F(a) f2:F(a) mgu={ a/x } ~D(x)|B(x) ~G(z)|D(z) G(a) ~D(a) after change: f1:D(a) f2:D(a) mgu={ a/z } ~D(x)|B(x) G(a) ~G(a) cannot be syncretized//相同变元无法合一 ~D(x)|B(x) //归结出空集,为真 Success
2.
Input: ~((#x)(P(x)&(@y)D(y))) Elimination of implied symbols: ~((#x)(P(x)&(@y)D(y))) Move the negation sign to the front of each predicate: ((@x)(~P(x)|(#y)~D(y))) Standardization of variables: ((@x)(~P(x)|(#y)~D(y))) Eliminate existential quantifiers: ((@x)(~P(x)|~D(f(x)))) Convert to a front bundle: (@x)((~P(x)|~D(f(x)))) Omit universal quantifiers: ((~P(x)|~D(f(x)))) Standardization of Skolem: ((~P(x)|~D(f(x)))) Eliminate the conjunction: (~P(x)|~D(f(x))) Failure
3.
Input: (~P(x)|Q(x))&(~P(y)|R(y))&S(a)&(~S(z)|~R(z))&P(a) Elimination of implied symbols: (~P(x)|Q(x))&(~P(y)|R(y))&S(a)&(~S(z)|~R(z))&P(a) Move the negation sign to the front of each predicate: (~P(x)|Q(x))&(~P(y)|R(y))&S(a)&(~S(z)|~R(z))&P(a) Standardization of variables: (~P(x)|Q(x))&(~P(y)|R(y))&S(a)&(~S(z)|~R(z))&P(a) Eliminate existential quantifiers: (~P(x)|Q(x))&(~P(y)|R(y))&S(a)&(~S(z)|~R(z))&P(a) Convert to a front bundle: (~P(x)|Q(x))&(~P(y)|R(y))&S(a)&(~S(z)|~R(z))&P(a) Omit universal quantifiers: (~P(x)|Q(x))&(~P(y)|R(y))&S(a)&(~S(z)|~R(z))&P(a) Standardization of Skolem: (~P(x)|Q(x))&(~P(y)|R(y))&S(a)&(~S(z)|~R(z))&P(a) Eliminate the conjunction: ~P(x)|Q(x) ~P(y)|R(y) S(a) ~S(z)|~R(z) P(a) after change: f1:P(a) f2:P(a) mgu={ a/y } ~P(x)|Q(x) S(a) ~S(z)|~R(z) R(a) after change: f1:R(a) f2:R(a) mgu={ a/z } ~P(x)|Q(x) S(a) ~S(a) cannot be syncretized ~P(x)|Q(x) Success
代码简陋,还请包涵
链接:https://pan.baidu.com/s/10yz6Yh83lEIpecEYdvhhuw
提取码:qwer当时做的时候没想那么多,所以前面化简和后面归结存在一些问题。
-
人工智能作业 鲁滨逊归结原理
2010-06-01 19:04:01人工智能作业 鲁滨逊归结原理 java 语言完成 -
人工智能基础——鲁宾孙归结原理
2020-09-20 00:01:50鲁宾孙归结原理: 命题逻辑中的归结原理: 若r1,r2是一个子句集中的两个子句,r1,r2中含有互补文字,那么把r1,r2拿出来,去掉互补文字,再把剩下的部分析取,得到的子句r12为r1,r2的归结式,r1,r2为r12的亲本子句。... -
AI:Robinson归结原理
2020-05-02 13:50:01文章目录承前基本原理Robinson的基本方法命题逻辑中的归结原理谓词逻辑中的归结原理归结原理推论1(充分)归结原理推论2(充要)重要 承前 谓词公式的不可满足性分析可通过把谓词公式转化为子句集后,对子句集中的... -
写出利用归结原理求解问题答案的步骤
2019-11-19 16:37:57写出利用归结原理求解问题答案的步骤 (1)写出谓词关系公式。(2)用反演法写出谓词表达式。(3)SKOLEM标准形式。(4)命题表示成合取范式并求子句集S。(5)将结论否定并加入S中,对S中可归结的子句做归结。(6)... -
消解归结原理
2020-11-21 16:44:231.规定原子公式 S(x, y) 表示 “x储蓄y” M(x) 表示 “x是钱” I(x) 表示 “x是利息” E(x, y) 表示 “x获得y” 2.基于原子公式表示前提和结论 前提: 结论: 3.把前提化为字句型 ①消去蕴含符号: ②减少否定符号... -
Knowledge 3命题逻辑形式推演(resolution归结原理- -- 1条规则)
2019-11-19 16:29:39二、resolution归结原理 2.1 什么是resolution归结原理 2.2 怎么将一个任何一个式子改写成CNF合取范式的形式 2.3 利用归结原理和反证法证明 KB |=a 2.4 归结原理的使用举个例子 三、resolution归结原理的特性 ... -
计算机人工智能 归结原理 为此逻辑 子句集
2010-10-22 00:21:58计算机人工智能 归结原理 为此逻辑 子句集 计算机人工智能 归结原理 为此逻辑 子句集 已经调试运行,并附有例子说明。 -
归结演绎推理
2020-11-28 14:46:38第三章归结演绎推理摘要:本文对归结对归结演绎推理进行了较为详细的介绍,描述了归结演绎推理的基本思路、使用步骤、并指明了其过程是完备的,还给出了运用归结原理进行归归结的具体例子,最后简单总结了其优缺点。... -
SVM(原理公式推导)
2020-03-10 16:44:45如下图x’,x’'是一个平面内的两点,W是平面内的法向量,则点到直线的距离公式为: 对于如下的一些训练样本: min求离直线最近的点,max使距离最远。1/w2的最大,转化为w2/2。 xi和xj是点积。例如(3,3)... -
人工智能 —— 归结演绎推理
2019-03-26 10:28:14谓词公式的范式 范式是公式的标准形式,公式往往需要变换为同它等价的范式,以便对它们进行一般性的处理。在谓词逻辑中,根据量词在公式中出现的情况,可将谓词公式的范式分为以下两种。 前束范式 任一含有量词的... -
归结演绎推理.ppt
2021-01-29 20:05:27归结演绎推理* (3)变量标准化:重新命名变元名,使不同量词约束的变元有不同的名字 (4)消去存在量词 存在量词不出现在全称量词的辖域内,此时只要用一个新的个体常量替换该存在量词的约束变元可消去存在量词 存在... -
人工智能——归结演绎推理
2020-11-28 14:46:401.子句1) 文字:原子谓词及其否定定义1:任何文字的析取式称为子句定义2:不包含任何文字的子句称为空子句,子句是永假的2) 由子句构成的集合称为子句集,谓词公式成子句集的步骤a) 利用等价关系消去谓词公式中的、 b... -
用Python实现命题逻辑归结推理系统--人工智能
2020-04-15 23:07:58使用代码之前,请根据自身情况对字符编码、文件路径进行修改 代码没有使用什么算法进行优化,姑且这样吧 文章目录 归结演绎推理 谓词公式化为子句集 鲁滨逊归结原理(消解原理) 1. 命题逻辑中的归结原理(基子句的... -
python基础归结
2020-12-19 13:12:53这是因为括号()既可以表示tuple,又可以表示数学公式中的小括号,这就产生了歧义,因此,Python规定,这种情况下,按小括号进行计算,计算结果自然是3。所以,只有1个元素的tuple定义时必须加一个逗号,,来消除歧义... -
谓词逻辑归结推理系统
2008-12-10 00:10:05输入一组合适公式,以及一个目标子句,输出归结树。 我奋斗了几乎5天总算弄出来了,放过bin出来show一下^_^。 至于代码,想要的可以联系我。 这里给出一个测试用例吧: ;假设:所有不贫穷且聪明的人都快乐。那些... -
AI:归结反演及问题求解
2020-05-06 10:55:54文章目录归结反演##########定义步骤示例1....应用归结原理(如Robinson)证明定理的过程称为归结反演 步骤 将已知前提表示为谓词公式F 将待证明的结论表示为谓词公式Q,并得到它的否定 非Q。 把谓词... -
人工智能推理——归结反演,学习记录
2021-12-24 19:23:581.归结反演的原理: 如果通过多个条件可以推出一个结论是恒对的,那么通过一样的条件一定推不出和正确结论相反的结论。即如果可以推出结论P,那么~P就一定推不出。同时~P如果和之前的条件们一起归... -
归结反演介绍
2020-12-15 15:47:31归结原理给出了证明子句集不可满足性的方法。 如欲证明Q为P1,P2,…,Pn的逻辑结论,只需证 (P1∧P2∧…∧Pn)∧¬Q 是不可满足的。 应用归结原理证明定理的过程称为归结反演。 设F为已知前提的公式集,Q为目标公式... -
机器学习-梯度下降算法原理及公式推导
2020-07-10 15:28:05最优化问题在机器学习中有非常重要的地位,很多机器学习算法最后都归结为求解最优化问题。最优化问题是求解函数极值的问题,包括极大值和极小值。在各种最优化算法中,梯度下降法是最简单、最常见的一种,在深度... -
python代码实现逻辑回归logistic原理
2021-01-20 05:29:24Logistic Regression Classifier逻辑回归主要思想就是用最大似然概率方法构建出方程,为最大化方程,利用牛顿梯度上升求解方程参数。 优点:计算代价不高,易于理解和实现。...我们直接用公式来说明。