计算机自动求解命题公式的主范式

计算机自动求解命题的主范式 一(需求 (1) 用户输入一任意命题公式，计算机程序自动输出其主析取范式和主合取范式。 (2)求任意一个命题公式的真值，并根据真值表求主范式。 (3)关于命题公式的形式和运算符(即联结词)的运算 首先根据离散数学的相关知识，命题公式由命题变元和运算符(即联结词)组成，命题变元用大写字母英文表示(本次试验没有定义命题常元T和F，即T、F都表示命题变元)，每个命题变元都有两种真值指派0和1，对应于一种真值指派，命题公式有一个真值，由所有可能的指派和命题公式相应的真值按照一定的规范构成的表格称为真值表。 目前离散数学里用到的包括扩充联结词总共有九种，即析取(或)、合取(与)、非、蕴含、等值、与非、或非、异或、蕴含否定，常用的为前五种，其中除了非运算为一元运算以外，其它四种为二元运算。所以本次实验时只定义了前五种运算符，同时用“/”表示非，用“*”表示合取，用“+”表示析取，用“>”表示蕴含，用“:”表示等值，且这五种运算符的优先级依次降低，如果需用括号改变运算优先级，则用小括号()改变。 以下为上述五种运算符运算时的一般真值表，用P和Q表示命题变元: 1( 非，用“/”表示 2( 合取(与)，用“*”表示 3(析取(或)，用“+”表示 4.蕴含，用“>”表示 5.等值，用“:”表示 下面是求取后缀表达式的规则: 1(从中缀表达式左边起逐个字符判断，如果是命题变元，则直接输出;如果是运算符，则将其与当前有效栈顶字符(即非空，可能为运算符或左半括号;如果栈为空，则直接入栈)的优先级比较，如果大于栈顶字符优先级，则直接入栈，如果小于或等于栈顶字符优先级，则弹出栈中字符并输出，直到大于栈顶字符优先级; 2(如果遇到左半括号，则直接入栈，也就是栈外左半括号的优先级最高，入栈以后，其优先级变为最低，也就是不管下一个字符是什么，该左半括号都不出栈，当且仅当遇到与其对应的右半括号时(遇到右半括号前，所有的字符按1中的规则或左半括号的入栈规则入栈或出栈)，将栈中该左半括号以上的字符按 照出栈规则弹出并输出，最后该左半括号出栈并和右半括号一起被丢掉(右半括号永不入栈)，余下的字符不出栈; 3(按照上述规则判断命题公式中的所有字符后，如果栈中还有有效字符，则依次弹出并输出。 以/A*(B+/C)为例，说明后缀表达式的求法: (二)概要分析 。 (三)详细设计 1、输入合法命题公式的地址。其流程图如下 四、调试分析 在输入命题公式时要注意输入格式区分大小写，要理解程序的含义 五、使用说明 输入任意命题公式，按回车结束，然后会列出真值表，根据真值表会 列出其主析取主合取范式。得到客户需要的结果。 六、源程序清单 #include <stdio.h> #include <stdlib.h> #include <string.h> /*-----------------------------------------------------------------------*/ //Read the propositional formula, and judges its validity, if the illegal to re-enter /*-----------------------------------------------------------------------*/ char *pp,formula[100]={0}; int valid=1; char *getformula() { char temp[100]={0},tempsign[3]={0}; int i,j,len,flag=0; printf("\nPlease enter a propositional formula\n"); printf("\n\"/\"said non,\"*\"to denote conjunction,\"and\"said disjunction,\",\"said contains,\"said:\"equivalent\n"); printf("\n brackets are\"\"()said:\n"); printf("\nPropositional variable uppercase English letters, to the end of the Enter key input:\n\n"); while(flag==0) { gets(temp); if(temp[0]=='\0') { valid=0; break; } for(j=0,i=0;*(temp+i);i++) if(*(temp+i)!=' ') { *(formula+j)=*(temp+i); j++; } len=strlen(formula); if(!(formula[len-1]>=65&&formula[len-1]<=90||formula[len-1]==')')|| !((formula[0]>=65&&formula[0]<=90)||formula[0]=='('||formula[0]=='/')) flag=0; else { for(pp=formula;*pp!='\0';pp++) { if(!((*pp>=65&&*pp<=90)||*pp=='/'||*pp=='*'||*pp=='+'||*pp=='>'||*pp==':'||*pp=='('||*pp==')')) { flag=0;break; } else { tempsign[0]=*pp; tempsign[1]=*(pp+1); tempsign[2]='\0'; if(strcmp(tempsign,"(+")==0||strcmp(tempsign,"(*")==0||strcmp(tempsign,"/)")==0|| strcmp(tempsign,"+)")==0||strcmp(tempsign,"*)")==0||strcmp(tempsign,")/") ==0|| strcmp(tempsign,"*+")==0||strcmp(tempsign,"/*")==0||strcmp(tempsign,")(")==0|| strcmp(tempsign,"+*")==0||strcmp(tempsign,"/+")==0||strcmp(tempsign,"()")==0|| strcmp(tempsign,">+")==0||strcmp(tempsign,"+>")==0||strcmp(tempsign,"*>")==0|| strcmp(tempsign,">*")==0||strcmp(tempsign,"(>")==0||strcmp(tempsign,">)")==0|| strcmp(tempsign,"/>")==0||strcmp(tempsign,"+:")==0||strcmp(tempsign,":+")==0|| strcmp(tempsign,"*:")==0||strcmp(tempsign,":*")==0||strcmp(tempsign,":>")==0|| strcmp(tempsign,">:")==0||strcmp(tempsign,"/:")==0||strcmp(tempsign,"(:")==0|| strcmp(tempsign,":)")==0) { flag=0;break; } if((tempsign[0]>=65&&tempsign[0]<=90)&&(tempsign[1]>=65&&tempsign[1]<=90)) { flag=0;break; } if(((tempsign[0]>=65&&tempsign[0]<=90)&&(tempsign[1]=='/'||tempsign[1]=='('))|| ((tempsign[1]>=65&&tempsign[1]<=90)&&tempsign[0]==')')) { flag=0;break; } else flag=1; } } } if(flag==0) { printf("Expression is in error, please enter again:\n"); for(i=0;*(temp+i)!='\0';i++) *(temp+i)='\0'; for(i=0;*(formula+i)!='\0';i++) *(formula+i)='\0'; } } pp=formula; // if(flag!=0)printf("%s",pp); return pp; } /*-----------------------------------------------------------------------*/ //Infix expression into a suffix expression is in error, please enter again /*-----------------------------------------------------------------------*/ char suf_formula[100]={0}; char *convert_suffix(char *formula) { // char plus,and,not,left,right; char stack[30],digit_stack[30]; char *pt; int i=0,j=0,top=1,digit_top=1; pt=formula; for(i=0;*pt;pt++) { if(*pt>=65&&*pt<=90) suf_formula[i++]=*pt; else switch(*pt) //优先级高低顺序，栈内(、:、>、+、*、/依次升高，分别用1、2、3、4、5、6表示 { case ':':// if(stack[0]=='\0') // { // stack[top++]='+'; // digit_stack[digit_top++]=2; // } // else { for(;2<=digit_stack[digit_top-1];top--,digit_top--) { suf_formula[i++]=stack[top-1]; stack[top-1]='\0'; digit_stack[digit_top-1]=0; } stack[top++]=':'; digit_stack[digit_top++]=2; } break; case '>':// if(stack[0]=='\0') // { // stack[top++]='+'; // digit_stack[digit_top++]=2; // } // else { for(;3<=digit_stack[digit_top-1];top--,digit_top--) { suf_formula[i++]=stack[top-1]; stack[top-1]='\0'; digit_stack[digit_top-1]=0; } stack[top++]='>'; digit_stack[digit_top++]=3; } break; case '+':// if(stack[0]=='\0') // { // stack[top++]='+'; // digit_stack[digit_top++]=2; // } // else { for(;4<=digit_stack[digit_top-1];top--,digit_top--) { suf_formula[i++]=stack[top-1]; stack[top-1]='\0'; digit_stack[digit_top-1]=0; } stack[top++]='+'; digit_stack[digit_top++]=4; } break; case '*': //if(stack[0]=='\0') // { // stack[top++]='+'; // digit_stack[digit_top++]=3; // } //else { for(;5<=digit_stack[top-1];top--,digit_top--) { suf_formula[i++]=stack[top-1]; stack[top-1]='\0'; digit_stack[digit_top-1]=0; } stack[top++]='*'; digit_stack[digit_top++]=5; } break; case '/':// if(stack[0]=='\0') // { // stack[top++]='+'; // digit_stack[digit_top++]=4; // } // else { for(;6<=digit_stack[top-1];top--,digit_top--) { suf_formula[i++]=stack[top-1]; stack[top-1]='\0'; digit_stack[digit_top-1]=0; } stack[top++]='/'; digit_stack[digit_top++]=6; } break; case '(': stack[top++]='('; digit_stack[digit_top++]=1; break; case ')': for(;stack[top-1]!='(';top--,digit_top--) { suf_formula[i++]=stack[top-1]; stack[top-1]='\0'; digit_stack[digit_top-1]=0; } stack[top-1]='\0'; digit_stack[top-1]=0; top--;digit_top--; break; default:; } } for(;top>=1;i++,top--) { if(stack[top-1]) suf_formula[i]=stack[top-1]; } printf("\n"); // printf("%s\n",suf_formula); return suf_formula; } /*---------------------------------------------------------------------------*/ // Statistical suffix expression the variable /*---------------------------------------------------------------------------*/ char var[16]={0}; void variable(char *suf_formula) { int i,j,len=0,flag=0; char temp; for(i=0;*(suf_formula+i);i++) //统计后缀表达式中的 { //变元 if(suf_formula[i]>=65&&suf_formula[i]<=90) // { // for(j=0;*(var+j);j++) if(suf_formula[i]==var[j]) { flag=1; break; } if(flag!=1) { len=strlen(var); var[len]=suf_formula[i]; } flag=0; } } for(i=0;*(var+i);i++) //从小到大排列变元 for(j=i+1;*(var+j);j++) if(var[i]>var[j]) { temp=var[i]; var[i]=var[j]; var[j]=temp; } // return var; } /*-----------------------------------------------------------------------*/ // Calculate the value of the suffix expressions /*-----------------------------------------------------------------------*/ char normal_form[100][16]={0}; void calc(char *suf_formula) { char bin_val[16]={0}; //指派真值 char //后缀表达式相应的变元真值、运算符构成的序列 int i,j,end=0,sum,result=1,index,temp_index,flag=0,xiqu_num=0,hequ_num=0; char *p,temp; int xiqu[50]={0},hequ[50]={0}; suf_val[100]={0}; variable(suf_formula); index=strlen(var); temp_index=index; if(index==0) //根据变元数计算指派的真值 的最大值 result=1; else for(;temp_index>0;temp_index--) result=result*2; printf("\nExpression of truth value table as follows\n\n"); for(i=0;*(var+i);i++) printf("%c ",*(var+i)); printf("\t\t"); printf("%s\n\n",formula); for(sum=0;sum<result;sum++) { j=sum; for(i=0;i<16;i++) bin_val[i]=0+'0'; for(i=0;j!=0;i++) //指派的真值以二进制字符串形式存储 { bin_val[i]=j%2+'0'; j=j/2; } // printf("%s\n",formula); // for(i=0;*(var+i);i++) //输出公式中所含变元 // printf("%c ",*(var+i)); // printf("\n"); for(j=index;j>0;j--) //输出指派的真值 printf("%d ",bin_val[j-1]-'0'); // printf("\n"); strcpy(suf_val,suf_formula); for(i=0;i<index/2;i++) //因变元(大写英文字母 )从小到大排列 ，以A为最高位， { //而上面指派的真值刚好从bin_val低位(对应A位)开始， temp=bin_val[i]; //故需将真值序列反序 bin_val[i]=bin_val[index-i-1]; bin_val[index-i-1]=temp; } for(i=0;suf_formula[i];i++) for(j=0;var[j];j++) if(var[j]==suf_formula[i]) suf_val[i]=bin_val[j]; // printf("\n%s",suf_val); p=suf_val; for(i=0;*(p+i);) //计算由变元和运算符构成的后缀表达式 { switch(*(p+i)) { case ':': if(*(p+i-1)==*(p+i-2)) { *(p+i-2)='1'; for(j=i+1;*(p+j);j++) *(p+j-2)=*(p+j); *(p+j-1)='\0'; *(p+j-2)='\0'; // printf("\n%s\n",suf_val); } else { *(p+i-2)='0'; for(j=i+1;*(p+j);j++) *(p+j-2)=*(p+j); *(p+j-1)='\0'; *(p+j-2)='\0'; // printf("\n%s\n",suf_val); } i=0; break; case '>': if(*(p+i-1)=='0'&&*(p+i-2)=='1') { *(p+i-2)='0'; for(j=i+1;*(p+j);j++) *(p+j-2)=*(p+j); *(p+j-1)='\0'; *(p+j-2)='\0'; // printf("\n%s\n",suf_val); } else { *(p+i-2)='1'; for(j=i+1;*(p+j);j++) *(p+j-2)=*(p+j); *(p+j-1)='\0'; *(p+j-2)='\0'; // printf("\n%s\n",suf_val); } i=0; break; case '+': if(*(p+i-1)=='1'&&*(p+i-2)=='1') { *(p+i-2)='1'; for(j=i+1;*(p+j);j++) *(p+j-2)=*(p+j); *(p+j-1)='\0'; *(p+j-2)='\0'; // printf("\n%s\n",suf_val); } else { *(p+i-2)=(*(p+i-2)-'0')+(*(p+i-1)-'0')+'0'; for(j=i+1;*(p+j);j++) *(p+j-2)=*(p+j); *(p+j-1)='\0'; *(p+j-2)='\0'; // printf("\n%s\n",suf_val); } i=0; break; case '*': *(p+i-2)= (*(p+i-2)-'0')*(*(p+i-1)-'0')+'0'; for(j=i+1;*(p+j);j++) *(p+j-2)=*(p+j); *(p+j-1)='\0'; *(p+j-2)='\0'; // printf("\n%s\n",suf_val); for(j=i+1;*(p+j);j++) *(p+j-1)=*(p+j); *(p+j-1)='\0'; // printf("\n%s\n",suf_val); i=0; break; default: i++; if(*(suf_val+1)=='\0') end=1; } if(end==1) break; } end=0; printf("\t\t%d\n",*p-'0'); if(*p-'0'==1) xiqu[xiqu_num++]=sum+1; else } printf("\nPrincipal disjunctive normal form is as follows:\n\n"); for(i=0;xiqu[i]!=0;i++) { printf("M%d",xiqu[i]-1); if(xiqu[i+1]!=0)printf("+"); // if((i+1)%6==0) printf("\n"); if(*p-'0'==0) hequ[hequ_num++]=sum+1; } printf("\n\nPrincipal conjunctive as follows:\n\n"); for(i=0;hequ[i]!=0;i++) { printf("m%d",hequ[i]-1); if(hequ[i+1]!=0)printf("*"); // if((i+1)%6==0) printf("\n"); } } /*-----------------------------------------------------------------------*/ // The main function /*-----------------------------------------------------------------------*/ int main() { char *formula; formula=getformula(); if(valid==1) //输入的表达式非空才可继续执行(即第一个字符不是回车符) { convert_suffix(formula); calc(suf_formula); } getchar(); return 0; } 七截图