實現(xiàn)基于謂詞邏輯的歸結(jié)原理

1、For personal use only in study and research; not forcommercial use河南城建學(xué)院人工智能實驗報告實驗名稱：實現(xiàn)基于謂詞邏輯的歸結(jié)原理成 績：_專業(yè)班級：_學(xué) 號：_姓 名：實驗日期：20 14 年 05 月 13 日實驗器材：一臺裝PC機。、實驗?zāi)康氖炀氄莆帐褂脷w結(jié)原理進行定理證明的過程，掌握基于謂詞邏輯的歸結(jié)過 程中，子句變換過程、替換與合一算法、歸結(jié)過程及簡單歸結(jié)策略等重要環(huán)節(jié)， 進一步了解機器自動定理證明的實現(xiàn)過程。二、實驗要求對于任意給定的一階謂詞邏輯所描述的定理，要求實現(xiàn)如下過程:(1) 謂詞公式到子句集變換；(2) 替

2、換與合一算法；(3) 在某簡單歸結(jié)策略下的歸結(jié)。、實驗步驟步 1 設(shè)計謂詞公式及自居的存儲結(jié)構(gòu)，即內(nèi)部表示。注意對全稱量詞-X 和存在量詞 X 可采用其他符號代替；步 2 實現(xiàn)謂詞公式到子句集變換過程；步 3 實現(xiàn)替換與合一算法；步 4 實現(xiàn)某簡單歸結(jié)策略；步 5 設(shè)計輸出，動態(tài)演示歸結(jié)過程，可以以歸結(jié)樹的形式給出；步 6 實現(xiàn)謂詞邏輯中的歸結(jié)過程，其中要調(diào)用替換與合一算法和歸結(jié)策略。四、代碼謂詞公式到子句集變換的源代碼：#in clude#in clude#in clude#in cludeusing n amespace std;一些函數(shù)的定義void in itStri ng(stri

3、ng &ini);/初始化string del_inlclue(string temp);/消去蘊涵符號string dec_neg_rand(string temp);/減少否定符號的轄域string standard_var(string temp);/對變量標準化string del_exists(string temp);/消去存在量詞string convert_to_front(string temp);/化為前束形string convert_to_and(string temp);/把母式化為合取范式string del_all(string temp);/消去全稱量詞

4、string del_and(string temp);/消去連接符號合取%string change_name(string temp);/更換變量名稱/輔助函數(shù)定義bool isAlbum(char temp);/是字母string del_null_bracket(string temp);/刪除多余的括號string del_blank(string temp);/刪除多余的空格void checkLegal(string temp);/檢查合法性char numAfectChar(int temp);/數(shù)字顯示為字符/主函數(shù)void mai n()system(colorOA);/o

5、rign = Q(x,y)%(P(y);/orign = (x)(P(y)P);/orign = (#x)y(x);/orign = (x)x!b(x);/orign = (x!y);/orign = (a(b);stri ng orig n,temp;char comma nd,comma nd0,comma nd1,comma nd2,comma nd3,comma nd4,comma nd5, comma nd6,command7,comma nd8,comma nd9,comma nd10;/=cout請輸入(Y/y)初始化謂詞演算公式 comma nd;if(comma nd = y

6、 | comma nd = Y)in itStri ng(orig n);elseexit(0);/= cout請輸入(Y/y)消除空格 comma nd0;if(comma nd0 = y | comma nd0 = Y)/del_bla nk(orig n);undonecout消除空格后是endlorig nen dl;elseexit(0);/= cout請輸入(Y/y)消去蘊涵項 comma nd1;cout求子句集九步法演示endl;if(comma nd1 = y | comma nd1 = Y)orig n =del_i nl clue(orig n);cout消去蘊涵項后是e

7、ndlorig nen dl;elseexit(O);/= cout請輸入(Y/y)減少否定符號的轄域 comma nd2;if(comma nd2 = y | comma nd2 = Y)dotemp = orig n;orig n = dec_ neg_ra nd(orig n);while(temp != orig n);cout減少否定符號的轄域后是e ndlorig nen dl;elseexit(0);/= cout請輸入(Y/y)對變量進行標準化 comma nd3;if(comma nd3 = y | comma nd3 = Y)orig n = sta ndard_var(o

8、rig n);cout對變量進行標準化后是e ndlorig nen dl; elseexit(O);/: cout請輸入(Y/y)消去存在量詞 comma nd4;if(comma nd4 = y | comma nd4 = Y)orig n = del_exists(orig n);cout消去存在量詞后是(w = g(x)是一個Skolem函數(shù))endlorig nen dl;elseexit(0);/= cout請輸入(Y/y)化為前束形 comma nd5;if(comma nd5 = y | comma nd5= Y)orig n = con vert_to_fro nt(orig

9、 n);cout化為前束形后是endlorig nen dl;elseexit(0);/= cout請輸入(Y/y)把母式化為合取方式 comma nd6;if(comma nd6 = y | comma nd6 = Y)orig n = con vert_to_a nd(orig n);cout把母式化為合取方式后是e ndlorig nen dl;elseexit(O);/：cout”請輸入(Y/y)消去全稱量詞 comma nd7;if(comma nd7 = y | comma nd7 = Y)orig n= del_all(orig n);cout消去全稱量詞后是endlorig n

10、en dl;elseexit(0);/=cout請輸入(Y/y)消去連接符號 comma nd8;if(comma nd8 = y | comma nd8 = Y)orig n = del_a nd(orig n);cout消去連接符號后是endlorig nen dl;elseexit(0);/=cout請輸入(Y/y)變量分離標準化 comma nd9;if(comma nd9 = y | comma nd9 = Y)orig n = cha nge_n ame(orig n);cout變量分離標準化后是(x1,x2,x3代替變量x)endlorig nen dl; elseexit(O)

11、;/=cout-完畢-e ndl;cout(請輸入Y/y)結(jié)束endl;dowhile(y = getchar() | Y=getchar();exit(0); void in itStri ng(stri ng &ini)char comma nda,comma ndb;cout請輸入您所需要轉(zhuǎn)換的謂詞公式e ndl;cout需要查看輸入幫助(Y/N)? comma nda;if(comma nda = Y | comma nda = y)cout，全稱量詞為,存在量詞為#,endl取反為,吸取為!,合取為%,左右括號分別為(、)，函數(shù)名請用一個字母e ndl;cout請輸入(y/n

12、)選擇是否用戶自定義 comma ndb;if(comma ndb =Y| comma ndb=y)ci nini;elseini = (x)(P(x)(y)(P(y)P(f(x, y)%(y)(Q(x,y)P(y);cout原始命題是endlinib變?yōu)閍!bchar ctemp100=;stri ng output;int len gth = temp.le ngth();int i = O,right_bracket = 0,falg= 0;stack stack1,stack2,stack3;strcpy(ctemp,temp.c_str(); while(ctempi != 0 &a

13、mp; i = ctempi+1) 如果是ab則用a!b替代falg = 1;if(isAlbum(ctempi) 如果是字母則把ctempi彈出stack1.pop();stack1.push();stack1.push(ctempi);stack1.push(!);i = i + 1;else if() = ctempi)right_bracket+;doif( = stack1.top()right_bracket-; stack3.push(stack1.top(); stack1.pop();while(right_bracket != 0);stack3.push(stack1.t

14、op();stack1.pop();stack1.push();while(!stack3.empty()stack1.push(stack3.top();stack3.pop();stack1.push(!);i = i + 1;i+；while(!stack1.empty()stack2.push(stack1.top();stack1.pop();while(!stack2.empty()output += stack2.top();stack2.pop();if(falg = 1)return output;elsereturn temp;string dec_neg_rand(str

15、ing temp)/減少否定符號的轄域char ctemp100,tempc;stri ng output;int flag2 = 0;int i = 0,left_bracket = 0,le ngth = temp .len gth(); stack stack1,stack2;queue queue1;strcpy(ctemp,temp.c_str(); 復(fù)制到字符數(shù)組中while(ctempi != 0 & i =0); queuel.push();while(!queue1.empty()tempc = queue1.fro nt();queue1.pop(); stack1

16、.push(tempc);i +;while(!stack1.empty()stack2.push(stack1.top();stack1.pop();while(!stack2.empty()output += stack2.top();stack2.pop();if(flag2 = 1)temp = output;/*/char ctemp1100;stri ng output1;stack stack11,stack22;int falg1 = 0;int times = 0;int len gth1 = temp .len gth(),i nl eftbackets = 1,j = 0

17、;strcpy(ctemp1,temp.c_str();while(ctemp1j != 0 & j =0 & times = 0)stack11.push(ctemp1j);if(ctemp1j=()ini eftbackets +;else if(ctemp1j=)ini eftbackets -;if(i nleftbackets = 1 & ctemp1j+1 = ! & ctemp1j+2 != & ctemp1j+2 !=#)falgl =1;stackll.push();/stack11.push(%);stack11.push();sta

18、ck11.push();/j =j+1;if(i nleftbackets = 1 & ctemp1j+1 = % & ctemp1j+2 != & ctemp1j+2 !=#)falg1 =1;stack11.push();/stack11.push(!);stack11.push();stack11.push();/j =j+1；j = j +1；if(falg1 = 1)stackll.push(); stack11.pop();stackll.push();/此處有bug stackll.push();/此處有bugj +;while(!stack11.empt

19、y()stack22.push(stack11.top(); stack11.pop();while(!stack22.empty()output1 += stack22.top();stack22.pop();if(falg1 = 1)temp = output1;/* char ctemp3100;stri ng output3;int k = 0,left_bracket3 = 1,le ngth3 = temp.le ngth(); stack stack13,stack23;int flag = 0,bflag = 0;strcpy(ctemp3,temp.c_str(); 復(fù)制到字

20、符數(shù)組中while(ctemp3k != 0 & k =0) stack13.push(ctemp3k+1); if(ctemp3k+1=()left_bracket3 +;if(ctemp3k+1=)left_bracket3 -;if(ctemp3k+1 = ! | ctemp3k+1 = %)bflag = 1;k +;stack13.pop();k +;while(!stack13.empty()stack23.push(stack13.top();stack13.pop();while(!stack23.empty()stack23.pop();output3 += stac

21、k23.top();if(flag = 1 & bflag = 0)temp = output3;return temp;string standard_var(string temp)/對變量標準化，簡化，不考慮多層嵌套char ctemp100,des10= ;strcpy(ctemp,temp.c_str();stack stack1,stack2;int l_bracket = 1,falg = 0,bracket = 1;int i = 0,j = 0;stri ng output;while(ctempi != 0 & i temp.le ngth()stack1.

22、push(ctempi);if(ctempi = | ctempi = #)stack1.push(ctempi+1);desj = ctempi+1;j+;stack1.push(ctempi+2);i = i + 3;stack1.push(ctempi);i+;if(ctempi-1=()while(ctempi != 0 & l_bracket != 0)if(ctempi=()stack23.pop();l_bracket +;if(ctempi=)l_bracket -;if(ctempi = ( & ctempi+1 = )i +;desj = ctempi+2;

23、j+；if(ctempi+1 = ( & ctempi+2 = #) falg = 1;int kk = 1;stack1.push(ctempi);stack1.push();stack1.push(ctempi+2);i = i+3;if(ctempi = y)ctempi =w;stack1.push(ctempi);stack1.push();stack1.push();i = i+3;while(kk != 0)if(ctempi=()kk+;if(ctempi =)kk-;if(ctempi = y)ctempi =w;stack1.push(ctempi);i+;i +;

24、stack1.push(ctempi);i +；while(!stack1.empty()stack2.push(stack1.top(); stack1.pop();while(!stack2.empty()output += stack2.top();stack2.pop();if(falg = 1)return output;elsereturn temp;string del_exists(string temp)/消去存在量詞char ctemp100,u nknow;strcpy(ctemp,temp.c_str();int left_brackets = 0,i = 0,falg

25、 = 0;queue queue1;stri ng output;while(ctempi != 0 & i temp.le ngth()if(ctempi =( & ctempi+1 =#) falg = 1;unknow = ctempi+2;i = i+4;doif(ctempi=()left_brackets +;if(ctempi=) left_brackets -;if(ctempi = unknow)queuel.push(g);queue1.push();queue1.push(x);queue1.push();if(ctempi != unknow)queue

26、1.push(ctempi);i+;while(left_brackets != 0);queue1.push(ctempi);i+;while(!queue1.empty()output+= queue1.fr on t();queue1.pop();if(falg = 1)return output;elsereturn temp;string convert_to_front(string temp)/化為前束形char ctemp100;strcpy(ctemp,temp.c_str();int i = 0;stri ng out_var = output =;while(ctempi

27、 != 0 & i temp.le ngth()if(ctempi = ( & ctempi+1 = )out_var =out_var+ ctempi ;/()out_var = out_var+ ctempi+1out_var =out_var+ctempi+2;out_var =out_var+ctempi+3;i = i + 4;output = output + ctempi;i+；output = out_var + output;return output;string convert_to_and(string temp)/把母式化為合取范式，Q/A?temp

28、= (x)(y)(P(x)!(P(y)!P(f(x,y)%(P(x)!Q(x,g(x)%(P(x)!(P(g(x); return temp;string del_all(string temp)/消去全稱量詞char ctemp100;strcpy(ctemp,temp.c_str();int i = 0,flag = 0;stri ng output =;while(ctempi != 0 & i temp.le ngth()if(ctempi = ( & ctempi+1 = )i = i + 4;flag = 1; else output = output + ctem

29、pi;i +；return output;string del_and(string temp)/消去連接符號合取char ctemp100; strcpy(ctemp,temp.c_str(); int i = 0,flag = 0;stri ng output =;while(ctempi != 0 & i temp.le ngth()if(ctempi = %)ctempi = n;output = output +ctempi;i+;return output;stri ng cha nge_n ame(stri ng temp)/更換變量名稱char ctemp100; st

30、rcpy(ctemp,temp.c_str(); stri ng output =;int i = 0,j = 0,falg = 0;while(ctempi != 0 & i temp.le ngth()falg+;while(n != ctempi & i temp.le ngth()if(x = ctempi)output = output + ctempi;output = output + nu mAfectChar(falg);elseoutput = output + ctempi;i+;output = output + ctempi;i +;return ou

31、tput;bool isAlbum(char temp)if(temp = A | temp = a) return true;return false;char numAfectChar(int temp)/數(shù)字顯示為字符int t;switch (temp)case 1:t = 1;break;case 2:t = 2;break;case 3:t = 3;break;case 4:t = 4;break;default:t = 89;break;return t;五、結(jié)果分析(1)非用戶自定義時:M *D:XPrograB FilesMicrosoft Visual Studio9Deb

32、ug9aeze請輸入餐灼初始化謂詞演算公式-y逋輸入您所需要特換的謂詞公式需宴查看輸入幫M?鶴輸入 5 如選擇是否用戶自定義怎始命題是請輸入小消除空格y消除空格后是請輸入消去蘊涵項藕去蘊涵項后是(,Tf*C(ey!Pz,(ey*P(u?請輸入弊減少否定符號的轄域 養(yǎng)少否定符號的轄域后是請輸入小對變量進行標準化c：v*D;XPrograa FilesMicrosaft Visual Studio9DEbu、9*Ge附變量逬行標準化后是*eyX,vP*PF(x,情輸入 S、消去存在量詞消去存在量詞后是 0 -乳小是1個Skolem函數(shù) 請輸入炸化為前束形化為前東形后是請輸入把母式化為合取方式把母式化為合取方式后是 請輸入“如肖去全稱臺詞消去全稱量詞后是HWP*PCf iCxfQx,gxTJtC,TH請輸入 S 皤去連接符昌