河南城建学院
《人工智能》实验报告
实验名称:实现基于谓词逻辑的归结原理
成绩:____
专业班级:
学号:
姓名:
实验日期:20 14 年 05 月 13日
实验器材:一台装PC机。
一、实验目的
熟练掌握使用归结原理进行定理证明的过程,掌握基于谓词逻辑的归结过程中,子句变换过程、替换与合一算法、归结过程及简单归结策略等重要环节,进一步了解机器自动定理证明的实现过程。
二、实验要求
对于任意给定的一阶谓词逻辑所描述的定理,要求实现如下过程:
(1) 谓词公式到子句集变换;
(2) 替换与合一算法;
(3) 在某简单归结策略下的归结。
三、实验步骤
步1 设计谓词公式及自居的存储结构,即内部表示。注意对全称量词?x和存在量词?x可采用其他符号代替;
步2 实现谓词公式到子句集变换过程;
步3 实现替换与合一算法;
步4 实现某简单归结策略;
步5 设计输出,动态演示归结过程,可以以归结树的形式给出;
步6 实现谓词逻辑中的归结过程,其中要调用替换与合一算法和归结策略。
四、代码
谓词公式到子句集变换的源代码:
#include
#include
#include
#include
using namespace std;
//一些函数的定义
void initString(string &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);//消去全称量词
string del_and(string temp);//消去连接符号合取%
string change_name(string temp);//更换变量名称
//辅助函数定义
bool isAlbum(char temp);//是字母
string del_null_bracket(string temp);//删除多余的括号
string del_blank(string temp);//删除多余的空格
void checkLegal(string temp);//检查合法性
char numAfectChar(int temp);//数字显示为字符
//主函数
void main()
{
cout<<"------------------求子句集九步法演示-----------------------"< system("color 0A"); //orign = "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))"; string orign,temp; char command,command0,command1,command2,command3,command4,command5, command6,command7,command8,command9,command10; //================================================================= ============ cout<<"请输入(Y/y)初始化谓词演算公式"< cin>>command; if(command == 'y' || command == 'Y') initString(orign); else exit(0); //================================================================= ============ cout<<"请输入(Y/y)消除空格"< cin>>command0; if(command0 == 'y' || command0 == 'Y') { //del_blank(orign);//undone cout<<"消除空格后是"< < } else exit(0); //================================================================= ============ cout<<"请输入(Y/y)消去蕴涵项"< cin>>command1; if(command1 == 'y' || command1 == 'Y') { orign =del_inlclue(orign); cout<<"消去蕴涵项后是"< < } else exit(0); //================================================================= ============ cout<<"请输入(Y/y)减少否定符号的辖域"< cin>>command2; if(command2 == 'y' || command2 == 'Y') { do { temp = orign; orign = dec_neg_rand(orign); }while(temp != orign); cout<<"减少否定符号的辖域后是"< < } else exit(0); //================================================================= ============ cout<<"请输入(Y/y)对变量进行标准化"< cin>>command3; if(command3 == 'y' || command3 == 'Y') { orign = standard_var(orign); cout<<"对变量进行标准化后是"< < } else exit(0); //================================================================= ============ cout<<"请输入(Y/y)消去存在量词"< cin>>command4; if(command4 == 'y' || command4 == 'Y') { orign = del_exists(orign); cout<<"消去存在量词后是(w = g(x)是一个Skolem函数)"< < } else exit(0); //================================================================= ============ cout<<"请输入(Y/y)化为前束形"< cin>>command5; if(command5 == 'y' || command5== 'Y') { orign = convert_to_front(orign); cout<<"化为前束形后是"< < } else exit(0); //================================================================= ============ cout<<"请输入(Y/y)把母式化为合取方式"< cin>>command6; if(command6 == 'y' || command6 == 'Y') { orign = convert_to_and(orign); cout<<"把母式化为合取方式后是"< < } else exit(0); //================================================================= ============ cout<<"请输入(Y/y)消去全称量词"< cin>>command7; if(command7 == 'y' || command7 == 'Y') { orign= del_all(orign); cout<<"消去全称量词后是"< < } else exit(0); //================================================================= ============ cout<<"请输入(Y/y)消去连接符号"< cin>>command8; if(command8 == 'y' || command8 == 'Y') { orign = del_and(orign); cout<<"消去连接符号后是"< < } else exit(0); //================================================================= ============ cout<<"请输入(Y/y)变量分离标准化"< cin>>command9; if(command9 == 'y' || command9 == 'Y') { orign = change_name(orign); cout<<"变量分离标准化后是(x1,x2,x3代替变量x)"< < } else exit(0); //================================================================= =========== cout<<"-------------------------完毕-----------------------------------"< cout<<"(请输入Y/y)结束"< do { }while('y' == getchar() || 'Y'==getchar()); exit(0); } void initString(string &ini) { char commanda,commandb; cout<<"请输入您所需要转换的谓词公式"< cout<<"需要查看输入帮助(Y/N)? "< cin>>commanda; if(commanda == 'Y' || commanda == 'y') cout<<"本例程规定输入时蕴涵符号为>,全称量词为@,存在量词为#,"< cout<<"请输入(y/n)选择是否用户自定义"< cin>>commandb; if(commandb =='Y'|| commandb=='y') cin>>ini; else ini = "(@x)(P(x)>((@y)(P(y)>P(f(x, y)))%~(@y)(Q(x,y)>P(y))))"; cout<<"原始命题是"< < } string del_inlclue(string temp)//消去>蕴涵项 { //a>b变为~a!b char ctemp[100]={""}; string output; int length = temp.length(); int i = 0,right_bracket = 0,falg= 0; stack strcpy(ctemp,temp.c_str()); while(ctemp[i] != '\0' && i <= length-1) { stack1.push(ctemp[i]); if('>' == ctemp[i+1])//如果是a>b则用~a!b替代 { falg = 1; if(isAlbum(ctemp[i]))//如果是字母则把ctemp[i]弹出 { stack1.pop(); stack1.push('~'); stack1.push(ctemp[i]); stack1.push('!'); i = i + 1; } else if(')' == ctemp[i]) { right_bracket++; do { if('(' == stack1.top()) right_bracket--; stack3.push(stack1.top()); stack1.pop(); }while((right_bracket != 0)); stack3.push(stack1.top()); 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; else return temp; } string dec_neg_rand(string temp)//减少否定符号的辖域{ char ctemp[100],tempc; string output; int flag2 = 0; int i = 0,left_bracket = 0,length = temp.length(); stack queue strcpy(ctemp,temp.c_str());//复制到字符数组中 while(ctemp[i] != '\0' && i <= length - 1) { stack1.push(ctemp[i]); if(ctemp[i] == '~')//如果是~否则什么都不做 { char fo = ctemp[i+2]; if(ctemp[i+1] == '(')//如果是(,否则什么都不做 { if(fo == '@' || fo =='#')//如果是全称量词 { flag2 = 1; i++; stack1.pop(); stack1.push(ctemp[i]); if(fo == '@') stack1.push('#'); else stack1.push('@'); stack1.push(ctemp[i+2]); stack1.push(ctemp[i+3]); stack1.push('('); stack1.push('~'); if(isAlbum(ctemp[i+4])) { stack1.push(ctemp[i+4]); i = i + 5; } else i = i + 4; do { queue1.push(temp[i]); if(temp[i] == '(') left_bracket ++; else if(temp[i] == ')') left_bracket --; i ++; }while(left_bracket != 0 && left_bracket >=0); queue1.push(')'); while(!queue1.empty()) { tempc = queue1.front(); queue1.pop(); stack1.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 ctemp1[100]; string output1; stack int falg1 = 0; int times = 0; int length1 = temp.length(),inleftbackets = 1,j = 0; strcpy(ctemp1,temp.c_str()); while(ctemp1[j] != '\0' && j <= (length1 -1)) { stack11.push(ctemp1[j]); if(ctemp1[j] == '~') { if(ctemp1[j+1] == '(' /*&& ctemp1[j + 2] != '~'*/) { j = j + 2; stack11.push('(');//////////////// while(inleftbackets != 0 && inleftbackets >=0 && times <= (length1 - j) && times >= 0) { stack11.push(ctemp1[j]); if(ctemp1[j] == '(') inleftbackets ++; else if(ctemp1[j] == ')') inleftbackets --; if(inleftbackets == 1 && ctemp1[j+1] == '!' && ctemp1[j+2] != '@' && ctemp1[j+2] != '#') { falg1 =1; stack11.push(')');////////// stack11.push('%'); stack11.push('~'); stack11.push('(');////////// j = j+1; } if(inleftbackets == 1 && ctemp1[j+1] == '%' && ctemp1[j+2] != '@' && ctemp1[j+2] != '#') { falg1 =1; stack11.push(')');////////// stack11.push('!'); stack11.push('~'); stack11.push('(');////////// j = j+1; } j = j +1; } if(falg1 == 1) stack11.push(')'); stack11.pop(); stack11.push(')');//此处有bug stack11.push(')');//此处有bug } } j ++; } while(!stack11.empty()) { stack22.push(stack11.top()); stack11.pop(); } while(!stack22.empty()) { output1 += stack22.top(); stack22.pop(); } if(falg1 == 1) temp = output1; /************************************************************/ char ctemp3[100]; string output3; int k = 0,left_bracket3 = 1,length3 = temp.length(); stack int flag = 0,bflag = 0; strcpy(ctemp3,temp.c_str());//复制到字符数组中 while(ctemp3[k] != '\0' && k <= length3-1) { stack13.push(ctemp3[k]); if(ctemp3[k] == '~') { if(ctemp3[k+1] == '(') { if(ctemp3[k + 2] == '~') { flag = 1; stack13.pop(); k =k + 2; while(left_bracket3 != 0 && left_bracket3 >=0) { stack13.push(ctemp3[k+1]); if(ctemp3[k+1] == '(') left_bracket3 ++; if(ctemp3[k+1] == ')') left_bracket3 --; if(ctemp3[k+1] == '!' || ctemp3[k+1] == '%') bflag = 1; k ++; } stack13.pop(); } } } k ++; } while(!stack13.empty()) { stack23.push(stack13.top()); stack13.pop(); } while(!stack23.empty()) { output3 += stack23.top(); stack23.pop(); } if(flag == 1 && bflag == 0) temp = output3; return temp; } string standard_var(string temp)//对变量标准化,简化,不考虑多层嵌套{ char ctemp[100],des[10]={" "}; strcpy(ctemp,temp.c_str()); stack int l_bracket = 1,falg = 0,bracket = 1; int i = 0,j = 0; string output; while(ctemp[i] != '\0' && i < temp.length()) { stack1.push(ctemp[i]); if(ctemp[i] == '@' || ctemp[i] == '#') { stack1.push(ctemp[i+1]); des[j] = ctemp[i+1]; j++; stack1.push(ctemp[i+2]); i = i + 3; stack1.push(ctemp[i]); i++; if(ctemp[i-1] == '(') { while(ctemp[i] != '\0' && l_bracket != 0) { if(ctemp[i] == '(') l_bracket ++; if(ctemp[i] == ')') l_bracket --; if(ctemp[i] == '(' && ctemp[i+1] == '@' ) { des[j] = ctemp[i+2]; j++; } if(ctemp[i+1] == '(' && ctemp[i+2] == '#' ) { falg = 1; int kk = 1; stack1.push(ctemp[i]); stack1.push('('); stack1.push(ctemp[i+2]); i = i+3; if(ctemp[i] == 'y') ctemp[i] ='w'; stack1.push(ctemp[i]); stack1.push(')'); stack1.push('('); i = i+3; while(kk != 0) { if(ctemp[i]=='(') kk++; if(ctemp[i] ==')') kk--; if(ctemp[i] == 'y') ctemp[i] ='w'; stack1.push(ctemp[i]); i++; } } stack1.push(ctemp[i]); i ++; } } } i ++; } while(!stack1.empty()) { stack2.push(stack1.top()); stack1.pop(); } while(!stack2.empty()) { output += stack2.top(); stack2.pop(); } if(falg == 1) return output; else return temp; } string del_exists(string temp)//消去存在量词{ char ctemp[100],unknow; strcpy(ctemp,temp.c_str()); int left_brackets = 0,i = 0,falg = 0; queue string output; while(ctemp[i] != '\0' && i < temp.length()) { if(ctemp[i] =='(' && ctemp[i+1] =='#') { falg = 1; unknow = ctemp[i+2]; i = i+4; do { if(ctemp[i] == '(') left_brackets ++; if(ctemp[i] == ')') left_brackets --; if(ctemp[i] == unknow) { queue1.push('g'); queue1.push('('); queue1.push('x'); queue1.push(')'); } if(ctemp[i] != unknow) queue1.push(ctemp[i]); i++; }while(left_brackets != 0); } queue1.push(ctemp[i]); i++; } while(!queue1.empty()) { output+= queue1.front(); queue1.pop(); } if(falg == 1) return output; else return temp; } string convert_to_front(string temp)//化为前束形{ char ctemp[100]; strcpy(ctemp,temp.c_str()); int i = 0; string out_var = "",output = ""; while(ctemp[i] != '\0' && i < temp.length()) { if(ctemp[i] == '(' && ctemp[i+1] == '@') { out_var = out_var + ctemp[i] ;//(@) out_var = out_var + ctemp[i+1] ; out_var = out_var +ctemp[i+2]; out_var = out_var +ctemp[i+3]; i = i + 4; } output = output + ctemp[i]; i++; } output = out_var + output; return output; } string convert_to_and(string temp)//把母式化为合取范式,Q/A? { temp = "(@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 ctemp[100]; strcpy(ctemp,temp.c_str()); int i = 0,flag = 0; string output = ""; while(ctemp[i] != '\0' && i < temp.length()) { if(ctemp[i] == '(' && ctemp[i+1] == '@') { i = i + 4; flag = 1; } else { output = output + ctemp[i]; i ++; } } return output; } string del_and(string temp)//消去连接符号合取% { char ctemp[100]; strcpy(ctemp,temp.c_str()); int i = 0,flag = 0; string output = ""; while(ctemp[i] != '\0' && i < temp.length()) { if(ctemp[i] == '%' ) { ctemp[i] = '\n'; } output = output +ctemp[i]; i++; } return output; } string change_name(string temp)//更换变量名称{ char ctemp[100]; strcpy(ctemp,temp.c_str()); string output = ""; int i = 0,j = 0,falg = 0; while(ctemp[i] != '\0' && i < temp.length()) { falg++; while('\n' != ctemp[i] && i < temp.length()) { if('x' == ctemp[i]) { #include } } j=count; if(k==j)return; count=k; for(int i=1;i 谓词逻辑习题 1. 将下列命题用谓词符号化。 (1)小王学过英语和法语。 (2)2大于3仅当2大于4。 (3)3不是偶数。 (4)2或3是质数。 (5)除非李键是东北人,否则他一定怕冷。 解: (1) 令)(x P :x 学过英语,Q(x):x 学过法语,c :小王,命题符号化为)()(c Q c P ∧ (2) 令),(y x P :x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P :x 是偶数,命题符号化为)3(P ? (4) 令)(x P :x 是质数,命题符号化为)3()2(P P ∨ (5) 令)(x P :x 是北方人;)(x Q :x 怕冷;c :李键;命题符号化为)()(x P c Q ?→ 2. 设个体域}{c b a D ,, =,消去下列各式的量词。 (1)))()((y Q x P y x ∧?? (2)))()((y Q x P y x ∨?? (3))()(y yQ x xP ?→? (4)))()((y yQ y x P x ?→?, 解: (1) 中))()(()(y Q x P y x A ∧?=,显然)(x A 对y 是自由的,故可使用UE 规则,得到 ))()(()(y Q y P y y A ∧?=,因此))()(())()((y Q y P y y Q x P y x ∧?∧?? ,再用ES 规则, )()())()((z Q z P y Q y P y ∧∧? ,D z ∈,所以)()())()((z Q z P y Q x P y x ∧∧?? (2)中))()(()(y Q x P y x A ∨?=,它对y 不是自由的,故不能用UI 规则,然而,对 )(x A 中约束变元y 改名z ,得到))()((z Q x P z ∨?,这时用UI 规则,可得: ))()((y Q x P y x ∨?? ))()((z Q x P z x ∨??? ))()((z Q x P z ∨? (3)略 (4)略 3. 设谓词)(y x P ,表示“x 等于y ”,个体变元x 和y 的个体域都是}321 {,,=D 。求下列各式的真值。 (1))3(,x xP ? (2))1(y yP ,? (3))(y x yP x ,?? (4))(y x yP x ,?? (5))(y x yP x , ?? (6))(y x xP y , ?? 解: 谓词演算的 推理理论 在谓词逻辑中,除了命题逻辑中的推理规则继续有效外,还有以下四条规则。设前提Г= {A 1,A 2,…,A k }. 1. 全称指定规则(全称量词消去规则)US : 例1 取个体域为实数域,F(x, y): x>y, P(x)=(?y) F(x,y), 则(?x)P(x) ?P(z)=(?y) F(z,y). 而不能(?x) P(x) ?P(y)=(?y) F(y,y). 其中x,y 是个体变项符号,c 为任意的个体常量. 或 (?x ) P (x ) ∴ P (y ) (?x) P (x ) ∴ P (c ) 2 . 全称推广规则(全称量词引入规则) UG: P(x) ∴ (?x)P(x) 其中x是个体变项符号,且不在前提的任何公式中 自由出现. 3. 存在指定规则(存在量词消去规则) ES: (?x)P(x) ∴ P(c) 1)c是使P(x)为真的特定的个体常量,不是任意的. 2)c不在前提中或者先前推导公式中出现或自由出现, 换句话说,此c是在该推导之前从未使用过的. 4. 存在推广规则(存在量词引入规则) EG: P(c) ∴ ( x)P(x) 其中x是个体变项符号, c是个体常项符号. 谓词逻辑的推理理论由下列要素构成. 1. 等价公式 2. 蕴含式 3. 推理规则: (1) 前提引入规则 (2) 结论引入规则 (3) CP推理规则 (4)归谬论 (5) US规则 (6) UG规则 (7) ES规则 (8) EG规则 1)在推导的过程中,可以引用命题演算中的规则P、规则T、 规则CP . 2)为了在推导过程中消去量词,可以引用规则US和规则ES来 消去量词. 3)当所要求的结论可能被定量时,此时可引用规则UG和规则 EG将其量词加入. 4)证明时可采用如命题演算中的直接证明方法和间接证明方法. 5)在推导过程中,对消去量词的公式或公式中没含量词的子公 式,完全可以引用命题演算中的基本等价公式和基本蕴涵公式. 6)在推导过程中,对含有量词的公式可以引用谓词中的基本等 价公式和基本蕴涵公式. 离散数学作业 作业11——第3章谓词逻辑 1. 符号化下列命题并推证其结论。 每个大学生不是文科学生就是理工科学生,小张不是理工科学生,因此如果小张是大学生,则他就是文科生。 解:a:小张;M(x):x是大学生;F(x): x是文科生;G(x): x是理工科学生,则符号化为 (x)(M(x)F(x)∨G(x)),┐G(a)M(a) F(a) (1) M(a) P(附加前提) (2) (x)(M(x)F(x)∨G(x)) P (3) M(a)F(a)∨G(a) (2),US (4) ┐M(a)∨F(a)∨G(a) (3),等值演算 (5) F(a)∨G(a) (1),(4),析取三段论 (6) ┐G(a) P (7) F(a) (5),(6),析取三段论 (8) M(a) F(a) (1),(7),CP规则 注:也可采用直接证法。 2. 符号化下列命题并推证其结论。 所有的主持人都是有风度的,黎明既是学生又是主持人,所以有一些学生是有风度的。 解:S(x): x是学生;Z(x): x是主持人;F(x):x是有风度的;a:黎明。 (x)(Z(x)F(x)),S(a)Z(a)(x) (S(x)F(x)) (1) (x)(Z(x)F(x)) P (2) Z(a)F(a) (1),US (3) S(a)Z(a) P (4) S(a) (3),化简 (5) Z(a) (3),化简 (6) F(a) (2),(5),假言推理 (7) S(a)F(a) (4),(6),合取引入 (8) (x) (S(x)F(x)) (7),EG 3.在一阶谓词逻辑中构造下面推理的证明。 前提:(x)(F(x)∨G(x)),(x)(F(x)→H(x)), 结论:(x)(H(x)→G(x))。 证明:反证法 (1)(x)(H(x)→G(x)) 附加前提 (2)(x)(H(x)→G(x)) (1),量词否定等值式 (3)(H(c)→G(c)) (2), ES (4)(H(c) ∨G(c)) (3), 等值演算 (5)H(c)G(c) (4), 等值演算 (6)H(c) (5),化简 (7)G(c) (5),化简 (8)(x)(F(x)∨G(x)) P (9)F(c)∨G(c) (8),US 数字逻辑课程作业_A 一、单选题。 1.(4分)如图x1-229 (D)。 A. (A) B. (B) C. (C) D. (D) 知识点:第五章 解析第五章译码器 2.(4分)如图x1-82 (C)。 A. (A) B. (B) C. (C) D. (D) 知识点:第二章 解析第二章其他复合逻辑运算及描述 3.(4分)N个触发器可以构成最大计数长度(进制数)为(D)的计数器。 A. N B. 2N C. N2次方 D. 2N次方 知识点:第九章 解析第九章计数器 4.(4分)n个触发器构成的扭环型计数器中,无效状态有(D)个。 A. A.n B. B.2n C. C.2n-1 D. D.2n-2n 知识点:第九章 解析第九章集成计数器 5.(4分)如图x1-293 (A)。 A. (A) B. (B) C. (C) D. (D) 知识点:第十一章 解析第十一章数字系统概述 6.(4分)如图x1-317 (D)。 A. (A) B. (B) C. (C) D. (D) 知识点:第二章 解析第二章其他复合逻辑运算及描述 7.(4分)EPROM是指(C)。 A. A、随机读写存储器 B. B、只读存储器 C. C、光可擦除电可编程只读存储器 D. D、电可擦可编程只读存储器 知识点:第十章 解析第十章只读存储器 8.(4分)如图x1-407 (B)。 A. (A) B. (B) C. (C) D. (D) 知识点:第十一章 解析第十一章数字系统概述 9.(4分)为实现将JK触发器转换为D触发器,应使(A)。 A. J=D,K=D非 B. B. K=D,J=D非 C. C.J=K=D D. D.J=K=D非 2.5 谓词演算的推理理论 1.推理定律 谓词演算中也存在一些基本的等价与蕴含关系,参见表2-2。我们以此作为推理的基础,即推理定律。 表2-2 序号 等价或蕴含关系 含义 E27 E28 ┐?xA(x)??x┐A(x) ┐?xA(x)??x┐A(x) 量词否定等值式 E29 E30?x(A(x)∧B(x))??xA(x)∧?xB(x) ?x(A(x)∨B(x))??xA(x)∨?xB(x) 量词分配等值式(量词分配律) E31 E32 E33 E34 E35 E36 E37 E38 E39 E40 E41 E42 E43?x(A(x)∨B)??xA(x)∨B ?x(A(x)∧B)??xA(x)∧B ?x(A(x)∨B)??xA(x)∨B ?x(A(x)∧B)??xA(x)∧B ?x(B∨A(x))? B∨?xA(x) ?x(B∧A(x))? B∧?xA(x) ?x(B∨A(x))? B∨?xA(x) ?x(B∧A(x))? B∧?xA(x) ?x(A(x)→B(x))??xA(x)→?xB(x) ?x(A(x)→B)??xA(x)→B ?xA(x)→B??x(A(x)→B) A→?xB(x)??x(A→B(x)) A→?xB(x)??x(A→B(x)) 量词作用域的扩张与收缩 I21 I22?xA(x)∨?xB(x)??x(A(x)∨B(x)) ?x(A(x)∧B(x))??xA(x)∧?xB(x) I23 ?xA(x)→?xB(x)??x(A(x)→B(x)) 表2-2中的I、E序号是接着表1-5和1-8排列的,表明它们都是谓词逻辑的推理定律。E31~E34与E35~E38只是A和B的顺序不同。 2.量词的消除与产生规则 谓词推理可以看作是对命题推理的扩充。除了原来的P规则(前提引入)、T规则(命题等价和蕴含)及反证法、CP规则外,为什么还需引入新的推理规则呢? 命题逻辑中只有一种命题,但谓词逻辑中有2种,即量词量化的命题和谓词填式命题。如果仅由表2-2的推理定律就可推证,并不需要引入新的规则,但这种情况十分罕见,也失去了谓词逻辑本身的意义。为此,要引入如下4个规则完成量词量化命题与谓词填式之间的转换,其中的A(x)表示任意的谓词。 (1) 全称指定(消去)规则US(Ubiquity Specification,或记为?-) 命题逻辑和谓词逻辑习题课的题目及参考 答案 说明:红色标注题目可以暂且不做 命题逻辑和谓词逻辑习题课的题目 一、填空 1、若P,Q,为二命题,Q P→真值为0 当且仅当。2、命题“对于任意给定的正实数,都存 在比它大的实数”令F(x):x为实数,:) , (则命题的逻辑谓词公式y L> x x y 为 。 3、谓词合式公式)( xP? ?的前束式 x → ) (x xQ 为。 4、将量词辖域中出现的 和指导变元交换为另一变元符号,公式 其余的部分不变,这种方法称为换名规 则。 5、设x是谓词合式公式A的一个客体变 元,A的论域为D,A(x)关于y是自由的,则 被称为存在量词消去规则,记为ES。 6.设P,Q 的真值为0,R,S的真值为1,则 → ∨ Q P? ∨ ?的真值 → ∧ ? (S ))) ( R ( ) P R ( = 。 7.公式P ∧) ( ) (的主合取式为 ∨ R S R P? ∨ ∧ 。 8.若解释I的论域D仅包含一个元素,则)( xP? → ?在I下真值为 xP ) (x x 。 9. P:你努力,Q:你失败。“除非你努力,否则你将失败”的翻译为 ;“虽然你努力了,但还是失败了”的翻译为 。 10. 论域D={1,2},指定谓词P 则公式),(x y ?真值 x? yP 为。 11.P,Q真值为0 ;R,S真值为1。则 ∧ wff∧ R ∨ → )) ∧的真值∨ S P )) P ) ( ( (( Q R (S 为 。 12. R ?) ) ((的主合取式 ∧ R Q ∨ P wff→ 为 。 13.设 P(x):x是素数, E(x):x 是偶数,O(x):x是奇数 N (x,y):x可以整数y。则谓词))) x y O P y ?的自然语言是 → ? wff∧ x ( ) ( N ( , y ( (x ) 。 14.谓词)),,( x y z P x z ?的前束 ? P ? ∧ → wff? y ) , ( , )) y ( z ( uQ x (u 式为 。 (1)(1011.10101)2 =(13.52)8=(0B.A8)16=(11.65625)10 (2)(1110.11001)2 =(16.62)8=(0E.C8)16=(14.78125)10 (3)(110110.111)2 =(66.7)8=(36.E )16=(54.875)10 (4)(10101.0011)2 =(25.14)8=(15.3)16=(21.1875)10 1-2 (1)(105.625)10 =(1101001.101)2=(69.A )16 (2)(27/64)10 =(0.011011)2=(0.6C )16 (3)(37.4)10 =(100101. 01100110)2=(25.66)16 (4)(42.375)10 =(101010. 011)2=(2A.6)16 (5)(62/128)10 =(0.0111110)2=(0.7C )16 (6)(9.46)10 =(1001. 01110101)2=(9.75)16 1-3 (1)(AB.7)16 =(10101011. 0111)2=(171.4375)10 (2)(3A.D )16 =(111010. 1101)2=(58.8125)10 (3)(5F.C8)16 =(1011111. 11001)2=(95.78125)10 (4)(2E.9)16 =(101110. 1001)2=(46.5625)10 1-4 (1)真值表 (2)真值表 逻辑函数表达式: 逻辑函数表达式: 1-5 (1)反函数: 对偶函数: (2)反函数: 对偶函数: (3)反函数: 对偶函数: (4)反函数: 对偶函数: AB BC F +++??=ABCD D C AB D C B A D C B A D BC A D C B A CD B A D C B A F +?++?++?+?+???=ABC C A B A A C B A F =?+=+?+=)()(A C B A F +?+=)('C B A C B A B A C B A B A F )()()()(⊕=??+?=?+?+=C B A B A F ?+?+=)()('))()(())((E D B C A C B A F ++?+??+=))()(()(B ++?+?++=))()(())(('E D B C A C B A F ++?+??+=) ()('D C A C B A C A F ++?+++?=D C A ??+?=)()(D C A C B A C A F ++?+++?= 习题4解答 4-1 试用与非门设计实现函数F(A,B,C,D)=Σm(0,2,5,8,11,13,15)的组合逻辑电路。 解:首先用卡诺图对函数进行化简,然后变换成与非-与非表达式。 化简后的函数 4-2 试用逻辑门设计三变量的奇数判别电路。若输入变量中1的个数为奇数时,输出为1,否则输出为0。 解:本题的函数不能化简,但可以变换成异或表达式,使电路实现最简。 真值表:逻辑函数表达式: C B A C B A C B A C B A Y? ? + ? ? + ? ? + ? ? = C B A⊕ ⊕ =) ( ACD D C B D B A D C B ACD D C B D B A D C B ACD D C B D B A D C B F ? ? ? ? ? ? ? = + + ? ? + ? ? = + + ? ? + ? ? = 逻辑图 B A C D F 4-3 用与非门设计四变量多数表决电路。当输入变量A 、B 、C 、D 有三个或三个以上为1时输出为1,输入为其他状态时输出为0。 解: 真值表: 先用卡诺图化简,然后变换成与非-与非表达式: 逻辑函数表达式: 4-4 用门电路设计一个代码转换电路,输入为4位二进制代码,输出为 4位循环码。 解:首先根据所给问题列出真值表,然后用卡诺图化简逻辑函数,按照化简后的逻辑函数画逻辑图。 ACD BCD ABC ABD ACD BCD ABC ABD ACD BCD ABC ABD Y ???=+++=+++=逻辑图 真值表: 卡诺图化简: 化简后的逻辑函数: Y 1的卡诺图 Y 2的卡诺图 Y 3的卡诺图 Y 4的卡诺图 A Y =1B A B A B A Y ⊕=+=2C B C B C B Y ⊕=+=3D C D C D C Y ⊕=+=4Y Y 逻辑图 2.4 归结原理 本节在上节的基础上,进一步具体介绍谓词逻辑的归结方法。谓词逻辑的归结法是以命题逻辑的归结法为基础,在Skolem 标准性的子句集上,通过置换和合一进行归结的。 下面先介绍一些本节中用到的必要概念: 一阶逻辑:谓词中不再含有谓词的逻辑关系式。 个体词:表示主语的词 谓词:刻画个体性质或个体之间关系的词 量词:表示数量的词 个体常量:a,b,c 个体变量:x,y,z 谓词符号:P,Q,R 量词符号:, 归结原理正确性的根本在于,如果在子句集中找到矛盾可以肯定命题是不可满足的。 2.4.1 合一和置换 置换:置换可以简单的理解为是在一个谓词公式中用置换项去置换变量。 定义: 置换是形如{t1/x1, t2/x2, …, t n/x n}的有限集合。其中,x1, x2, …, x n是互不相同的变量,t1, t2, …, t n是不同于x i的项(常量、变量、函数);t i/x i表示用t i置换x i,并且要求t i与x i不能相同,而且x i 不能循环地出现在另一个t i中。 例如 {a/x,c/y,f(b)/z}是一个置换。 {g(y)/x,f(x)/y}不是一个置换,原因是它在x和y之间出现了循环置换现象。置换的目的是要将某些变量用另外的变量、常量或函数取代,使其不在公式中出现。但在{g(y)/x,f(x)/y}中,它用g(y)置换x,用f(g(y))置换y,既没有消去x,也没有消去y。若改为{g(a)/x,f(x)/y}就可以了。 通常,置换用希腊字母θ、σ、α、λ来表示的。 定义:置换的合成 设θ={t1/x1, t2/x2, …, t n/x n},λ={u1/y1, u2/y2, …, u n/y n},是两个置换。则θ与λ的合成也是一个置换,记作θ·λ。它是从集合{t1·λ/x1, t2·l/x2, …, t n·λ/x n, u1/y1, u2/y2, …, u n/y n} 即对ti先做λ置换然后再做θ置换,置换xi 中删去以下两种元素: i. 当t iλ=x i时,删去t iλ/x i(i = 1, 2, …, n); ii. 当y i∈{x1,x2, …, x n}时,删去u j/y j(j = 1, 2, …, m) 最后剩下的元素所构成的集合。 例: 设θ={f(y)/x, z/y},λ={a/x, b/y, y/z},求θ与λ的合成。 解: 先求出集合 谓词逻辑习题 1. 将下列命题用谓词符号化。 (1)小王学过英语和法语。 (2)2大于3仅当2大于4。 (3)3不是偶数。 (4)2或3是质数。 (5)除非李键是东北人,否则他一定怕冷。 解: (1) 令)(x P :x 学过英语,Q(x):x 学过法语,c :小王,命题符号化为)()(c Q c P ∧ (2) 令),(y x P :x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P :x 是偶数,命题符号化为)3(P ? (4) 令)(x P :x 是质数,命题符号化为)3()2(P P ∨ (5) 令)(x P :x 是北方人;)(x Q :x 怕冷;c :李键;命题符号化为)()(x P c Q ?→ 2. 设个体域}{c b a D ,,=,消去下列各式的量词。 (1)))()((y Q x P y x ∧?? (2)))()((y Q x P y x ∨?? (3))()(y yQ x xP ?→? (4)))()((y yQ y x P x ?→?, 解: (1) 中))()(()(y Q x P y x A ∧?=,显然)(x A 对y 是自由的,故可使用UE 规则,得到 ))()(()(y Q y P y y A ∧?=,因此))()(())()((y Q y P y y Q x P y x ∧?∧?? ,再用ES 规则, )()())()((z Q z P y Q y P y ∧∧? ,D z ∈,所以)()())()((z Q z P y Q x P y x ∧∧?? (2)中))()(()(y Q x P y x A ∨?=,它对y 不是自由的,故不能用UI 规则,然而,对 )(x A 中约束变元y 改名z ,得到))()((z Q x P z ∨?,这时用UI 规则,可得: ))()((y Q x P y x ∨?? ))()((z Q x P z x ∨??? ))()((z Q x P z ∨? (3)略 (4)略 3. 设谓词)(y x P ,表示“x 等于y ”,个体变元x 和y 的个体域都是}321 {,,=D 。求下列各式的真值。 (1))3(,x xP ? (2))1(y yP ,? (3))(y x yP x , ?? (4))(y x yP x ,?? 习题五 1. 简述时序逻辑电路与组合逻辑电路的主要区别。 解答 组合逻辑电路:若逻辑电路在任何时刻产生的稳定输出值仅仅取决于该时刻各输入值的组合,而与过去的输入值无关,则称为组合逻辑电路。组合电路具有如下特征: ①由逻辑门电路组成,不包含任何记忆元件; ②信号是单向传输的,不存在任何反馈回路。 时序逻辑电路:若逻辑电路在任何时刻产生的稳定输出信号不仅与电路该时刻的输入信号有关,还与电路过去的输入信号有关,则称为时序逻辑电路。时序逻辑电路具有如下特征: ○1电路由组合电路和存储电路组成,具有对过去输入进行记忆的功能; ○2电路中包含反馈回路,通过反馈使电路功能与“时序”相关; ○3电路的输出由电路当时的输入和状态(过去的输入)共同决定。 2. 作出与表1所示状态表对应的状态图。 表1 状态表 现态y2 y1 次态y2 ( n+1)y1(n+1) /输出Z x2x1=00x2x1=01x2x1=11x2x1=10 A B C D B/0 B/0 C/0 A/0 B/0 C/1 B/0 A/1 A/1 A/0 D/0 C/0 B/0 D/1 A/0 C/0 解答 根据表1所示状态表可作出对应的状态图如图1所示。 图1 3. 已知状态图如图2所示,输入序列为x=,设初始状态为A,求状态和输出响应序列。 图2 解答 状态响应序列:A A B C B B C B 输出响应序列:0 0 0 0 1 0 0 1 4. 分析图3所示逻辑电路。假定电路初始状态为“00”,说明该电路逻辑 功能 。 图 3 解答 ○1 根据电路图可写出输出函数和激励函数表达式为 x K x,J ,x K ,xy J y xy Z 111121 2===== ○2 根据输出函数、激励函数表达式和JK 触发器功能表可作出状态表如表2所示, 状态图如图4所示。 表2 图4 现态 y 2 y 1 次态 y 2( n+1)y 1(n+1)/输出Z x=0 x=1 00 01 10 11 00/0 00/0 00/0 00/0 01/0 11/0 11/0 11/1 河南城建学院 《人工智能》实验报告 实验名称:实现基于谓词逻辑的归结原理 成绩:____ 专业班级: 学号: 姓名: 实验日期:20 14 年 05 月 13日 实验器材:一台装PC机。 一、实验目的 熟练掌握使用归结原理进行定理证明的过程,掌握基于谓词逻辑的归结过程中,子句变换过程、替换与合一算法、归结过程及简单归结策略等重要环节,进一步了解机器自动定理证明的实现过程。 二、实验要求 对于任意给定的一阶谓词逻辑所描述的定理,要求实现如下过程: (1) 谓词公式到子句集变换; (2) 替换与合一算法; (3) 在某简单归结策略下的归结。 三、实验步骤 步1 设计谓词公式及自居的存储结构,即内部表示。注意对全称量词?x和存在量词?x可采用其他符号代替; 步2 实现谓词公式到子句集变换过程; 步3 实现替换与合一算法; 步4 实现某简单归结策略; 步5 设计输出,动态演示归结过程,可以以归结树的形式给出; 步6 实现谓词逻辑中的归结过程,其中要调用替换与合一算法和归结策略。 四、代码 谓词公式到子句集变换的源代码: #include 数字逻辑课程作业_A 交卷时间:2016-05-04 16:55:11 一、单选题 1. (4分)如图x1-275 ? A. (A) ? B. (B) ? C. (C) ? D. (D) 纠错 得分:0 知识点:第一章 收起解析 答案D 解析第一章补码 2. (4分)以下电路中常用于总线应用的有() ? A. TSL门 B.OC门 C. 漏极开路门 D.CMOS与非门纠错 得分:0 知识点:第三章 收起解析 答案A 解析第三章其他类型的TTL与非门电路 3. (4分)如果异步二进制计数器的触发器为10个,则计数状态有()种 ? A. A:20 ? B. B:200 ? C. C:1000 ? D. D:1024 纠错 得分:0 知识点:第九章 收起解析 答案D 解析第九章计数器 4. (4分)用n个触发器构成的计数器,可得到的最大计数模是() ? A. (A) n ? B. (B) 2n ? C. (C) 2n ? D. (D)2n-1 纠错 得分:4 知识点:第六章 收起解析 答案C 解析第六章触发器电路结构和工作原理 5. ? A. (A) ? B. (B) ? C. (C) ? D. (D) 纠错 得分:0 知识点:第四章 收起解析 答案C 解析第四章组合逻辑电路的分析6. (4分)如图x1-229 ? A. (A) ? B. (B) ? C. (C) ? D. (D) 纠错 得分:0 知识点:第五章 收起解析 答案D 解析第五章译码器 7. ? A. (A) ? B. (B) ? C. (C) ? D. (D) 纠错 得分:0 知识点:第十一章 收起解析 答案C 解析第十一章数字系统概述8. (4分)化简如图h-d-1-22 ? A. A ? B. B ? C. C ? D. D 纠错 1. 将下列命题用谓词符号化。 4) 2 或 3 是质数。 5)除非李键是东北人,否则他一定怕冷。 解: (1) 令 P( x) :x 学过英语, Q(x) :x 学过法语, c :小王,命题符号化为 P(c) Q(c) (2) 令P(x,y):x 大于 y, 命题符号化为 P(2,4) P(2,3) (3) 令 P(x):x 是偶数,命题符号化为 P(3) (4) 令 P(x):x 是质数,命题符号化为 P(2) P(3) (5) 令 P(x):x 是北方人; Q(x):x 怕冷; c :李键;命题符号化为 Q(c) P(x) 2. 设个体域 D {a ,b ,c} ,消去下列各式的量词。 (1) x y(P(x) Q(y)) (2) x y(P(x) Q(y)) (3) xP(x) yQ(y) (4) x(P(x ,y) yQ(y)) 解: (1) 中 A(x) y(P(x) Q( y)) ,显然 A(x)对y 是自由的,故可使用 UE 规则,得到 A(y) y(P(y) Q(y)) , 因此 x y(P(x) Q(y)) y(P(y) Q( y)) ,再用 ES 规则, y( P( y) Q(y)) P(z) Q(z),z D ,所以 x y(P(x) Q(y)) P(z) Q(z) (2)中 A(x) y(P(x) Q( y)) ,它对 y 不是自由的,故不能用 UI 规则,然而,对 A( x)中约束变元 y 改名z ,得到 z(P(x) Q( z)) ,这时用 UI 规则,可得: x y(P(x) Q(y)) x z(P(x) Q(z)) z(P(x) Q(z)) 3) 略 4) 略 3. 设谓词 P(x ,y)表示“x 等于 y ”,个体变元 x 和y 的个体域都是 D {1,2,3} 。求下列各式 的真值。 (1) xP( x ,3) (2) yP(1,y) (3) x yP(x ,y) (4) x yP( x ,y) (5) x yP(x ,y) (6) y xP(x ,y) 解: (2) 当 x 3时可使式子成立,所以为 Ture 。 (3) 当 y 1 时就不成立,所以为 False 。 谓词逻辑习题 1) 小王学过英语和法语。 2) 2大于3仅当 2大于 4。 3) 3 不是偶数。 1、设)()()(),,(323221321x x x x x x x x x E ∧∨∧∨∧=是布尔代数],,},1,0[{-∧∨上的一个布尔表达式,试写出),,(321x x x E 的析取范式和合取范式。 答: 析取范式:)()() ()()(),,(321321321321321321x x x x x x x x x x x x x x x x x x E ∧∧∨∧∧∨∧∧∨∧∧∨∧∧= 合取范式:)()()(),,(321321321321x x x x x x x x x x x x E ∨∨∧∨∨∧∨∨∨= 2.设P(x):x 是大象,Q(x):x 是老鼠,R(x,y):x 比y 重,则命题“大象比老鼠重”的符号化为 答: ?x ?y ( (P(x) ∧ Q(x)) → R(x,y)) 3.设L(x):x 是演员,J(x):x 是老师,A(x , y):x 钦佩y ,命题“所有演员都钦佩某些老 师”符号化为( B )。 A 、)),()((y x A x L x →?; B 、))),()(()((y x A y J y x L x ∧?→? ; C 、)),()()((y x A y J x L y x ∧∧??; D 、)),()()((y x A y J x L y x →∧?? 。 4.下列各式中哪个不成立( A )。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ; B 、)()())()((x xQ x xP x Q x P x ?∨??∨?; C 、)()())()((x xQ x xP x Q x P x ?∧??∧?; D 、Q x xP Q x P x ∧??∧?)())((。 5.用推理规则证明)()(a G a P ∧?是 ))()((,)(,))()((, )))()(()((x G x S x a S a R a Q x R x Q x P x ??∧?∧→?的有效 结论。 证明:(1) ))()(()(x P x Q x xP ∧→? P (2) ))()(()(a P a Q a P ∧→ US(1) (3) ))()((a R a Q ∧? P 谓词逻辑-归结原理例题 习题3.5, 1. (1) ()P x :x 是大学生 ()Q x :x 是诚实的 则命题可表示为: 已知:1:(()())G x P x Q x ?→, 2:()G Q a ? 证明:()P a ? 习题3.5, 1. (2) 将下面的命题符号化,并证明之:已知每一个运动员都是强壮的,而每一个既强壮又聪明的人在他所从事的事业中都能获得成功,彼得是运动员并且是聪明的,证明彼得在他的事业中将会成功。 提示:定义谓词 ()P x :x 是运动员 ()Q x :x 是强壮的 ()R x :x 是聪明的 ()S x :x 在他所从事的事业中获得成功。 则命题可表示为: 已知:1:(()())G x P x Q x ?→, 2:(()()())G x Q x R x S x ?∧→,()P a ,()R a 证明:()S a 提示:可用归结原理证明:(1)先把公式都化成Skolem 范式,(2)然后利用US ,ES 将公式中的量词除去,(3)化成合取范式,(4)化成蕴涵式,(5)化成子句集(结论用否定加入), (6)进行归结,直至引出矛盾。 可化成如下子句集: {()()P x Q x →,()()()Q x R x S x ∧→,()P a →,()R a →,}()S a → 归结: (1)()()P x Q x → (2)()P a → (3)()Q a → 由(1)(2) (4)()()()Q x R x S x ∧→ (5)()()R a S a → 由(3)(4) (6)()R a → (7)()S a → 由(5)(6) (8)()S a → (9) 由(7)(8) 习题3.5, 1. (3) ()E x :x 进入国境 ()V x :x 是重要人物 ()C x :x 是海关人员 ()P x :x 是走私者 (,)S x y :y 检查x 已知: 1:((()())(()(,)))G x E x V x y C y S x y ?∧?→?∧, 2:(()()((,)()))G x P x E x y S x y P y ?∧∧?→ 3:(()())G x P x V x ?→? 证明:(()())x P x C x ?∧ 先化成子句集: {} 1((()())(()(,))) ((()())(()(,))) ((()()())(()()(,))) ()()(()),()()(,())G x E x V x y C y S x y x y E x V x C y S x y x y E x V x C y E x V x S x y E x V x C f x E x V x S x f x =??∧?∨?∧=???∨∨∧=???∨∨∧?∨∨?→∨→∨ {}2(()()((,)()))(),(),(,)()G x y P x E x S x y P y P a E a S a y P y =??∧∧→?→→→ 注意G2,如果理解成(()()(,)())x y P x E x S x y P y ??∧∧→,则还需有条件(()())x P x E x ?∧,最后同样能得到如上的子句集{}(),(),(,)()P a E a S a y P y →→→。不 谓词逻辑习题及答案 收集于网络,如有侵权请联系管理员删除 谓词逻辑习题 1. 将下列命题用谓词符号化。 (1)小王学过英语和法语。 (2)2大于3仅当2大于4。 (3)3不是偶数。 (4)2或3是质数。 (5)除非李键是东北人,否则他一定怕冷。 解: (1) 令)(x P :x 学过英语,Q(x):x 学过法语,c :小王,命题符号化为)()(c Q c P ∧ (2) 令),(y x P :x 大于y, 命题符号化为)3,2()4,2(P P → (3) 令)(x P :x 是偶数,命题符号化为)3(P ? (4) 令)(x P :x 是质数,命题符号化为)3()2(P P ∨ (5) 令)(x P :x 是北方人;)(x Q :x 怕冷;c :李键;命题符号化为)()(x P c Q ?→ 2. 设个体域}{c b a D ,,=,消去下列各式的量词。 (1)))()((y Q x P y x ∧?? (2)))()((y Q x P y x ∨?? (3))()(y yQ x xP ?→? (4) ))()((y yQ y x P x ?→?, 解: (1) 中))()(()(y Q x P y x A ∧?=,显然)(x A 对y 是自由的,故可使用UE 规则,得到 ))()(()(y Q y P y y A ∧?=,因此))()(())()((y Q y P y y Q x P y x ∧?∧??α,再用ES 规则, )()())()((z Q z P y Q y P y ∧∧?α,D z ∈,所以)()())()((z Q z P y Q x P y x ∧∧??α (2)中))()(()(y Q x P y x A ∨?=,它对y 不是自由的,故不能用UI 规则,然而,对 )(x A 中约束变元y 改名z ,得到))()((z Q x P z ∨?,这时用UI 规则,可得: ))()((y Q x P y x ∨?? ))()((z Q x P z x ∨??? ))()((z Q x P z ∨?α (3)略 (4)略 3. 设谓词)(y x P ,表示“x 等于y ”,个体变元x 和y 的个体域都是}321{,,=D 。求下列各式的真值。 (1))3(,x xP ? (2))1(y yP ,? (3))(y x yP x ,?? (4))(y x yP x ,?? 2.2命题逻辑的归结 2.2.1命题逻辑基础 逻辑可分为经典逻辑和非经典逻辑,其中经典逻辑包括命题逻辑和谓词逻辑。归结原理是一种主要基于谓词(逻辑)知识表示的推理方法,而命题逻辑是谓词逻辑的基础。因此,在讨论谓词逻辑之前,先讨论命题逻辑的归结,便于内容上的理解。 本节中,将主要介绍命题逻辑的归结方法,以及有关的一些基础知识和重要概念,如数理逻辑基本公式变形、前束范式、子句集等。 描述事实、事物的状态、关系等性质的文字串,取值为真或假(表示是否成立)的句子称作命题。 命题:非真即假的简单陈述句 在命题逻辑里,单元命题是基本的单元或作为不可再分的原子。下面所列出的是一些基本的数理逻辑公理公式和一些有用的基本定义,如合取范式、子句集,这些公式和定义在归结法的推理过程中是必不可少的,也是归结法的基础,应该熟练掌握。 -数理逻辑的基本定义 下面所列的是一些数理逻辑中重要的定义,在后面的分 析中要用到: ·合取式:p与q,记做p∧q ·析取式:p或q,记做p∨q ·蕴含式:如果p则q,记做p→q ·等价式:p当且仅当q,记做p q ·若A无成假赋值,则称A为重言式或永真式; ·若A无成真赋值,则称A为矛盾式或永假式; ·若A至少有一个成真赋值,则称A为可满足的; ·析取范式:仅由有限个简单合取式组成的析取式 ·合取范式:仅由有限个简单析取式组成的合取式 -数理逻辑的基本等值式 下面这些基本的等式在归结原理实施之前的公式转化过程中是非常重要的。只有将逻辑公式正确转换成为归结原理要求的范式,才能够保证归结的正常进行。 ·交换律:p∨q q∨p; p∧q q∧p ·结合律:(p∨q)∨r p∨(q∨r); (p∧q)∧r p∧(q∧r) ·分配律:p∨(q∧r)(p∨q)∧(p∨r); p∧(q∨r)(p∧q)∨(p∧r)·双重否定律:p~~p ·等幂律:p p∨p;p p∧p谓词逻辑归结原理源代码
谓词逻辑习题及答案
离散数学24谓词演算的推理理论
离散数学作业11_谓词逻辑答案
数字逻辑课程三套作业及答案课案
谓词演算的推理理论(牛连强)
命题逻辑和谓词逻辑习题课的题目与参考答案
数字逻辑第一章课后答案
数字逻辑第四章课后答案..
人工智能原理教案02章 归结推理方法2.4 归结原理
谓词逻辑习题及答案
数字逻辑课本习题答案
实现基于谓词逻辑的归结原理
数字逻辑课程作业答案
谓词逻辑习题及答案
谓词逻辑-习题与答案
谓词逻辑_归结原理习题
谓词逻辑习题及答案教学内容
人工智能原理教案02章 归结推理方法2.2 命题逻辑的归结