实验报告
题目：求合式公式的主析取范式和主合取范式
陈何渊 B12041318 2013.11.9
一．问题陈述
设计一个程序，来达到输入一个正确的合式公式，求它的主析取范式和主合取范式。通过实验，更好地掌握离散数学中的概念、性质和运算。
二．详细设计
该程序包括四个函数，主函数，赋值函数，分级运算函数和主运算函数。在主函数中，先输出提示语和变量的个数，接着调用赋值函数输出变量的真值，调用分级运算函数和主运算函数输出合式公式的真值，最后通过合式公式的真值表借助课本上的定理1-7.3和定理1-7.4输出合式公式的主析取范式和主合取范式。赋值函数可按一定的顺序输出变量的真值指派。分级运算函数的作用是找出合式公式的最内层的括号内的公式，调用主运算函数判断它的真值情况直到公式中不含括号。在主运算函数中，按逻辑联结词优先次序先后处理否定合取析取条件和双条件运算。用1表示T，用0表示F。
三．核心算法和算法分析
赋值函数：在主函数中，先将所有的变量赋值为1，通过for(i1=0;i1<pow(2,j)-1;i1++)实现变量的所有先T后F的指派。如果最后一变量指派为1，则将其修改为0，否则，则将其修改为1，对前一变量进行同样的处理，通过循环执行pow(2,j-1次。
分级运算函数：对公式进行遍历，找出括号并且存储括号位置类型和数量，如果数量为0，则调用主运算函数求出其真值情况，否则，找到最内层的括号，并将其存储在数组xs1[h]中，调用 a=fkh(xs1,ccu,icu,h0);求出最内层括号的真值情况，将结果存储在sz[wz[i-1]]（即最内层括号的左括号的位置）中，若a为1，则sz[wz[i-1]]=1，否则，sz[wz[i-1]]=-2。最后将括号后的内容前移。通过递归处理完合式范式中的所有括号。
主运算函数：先判断字符的长度，1）s=1,，if(sz[0]==-2||p1==0)为真，则返回0；否则返回1。
2）s>1，则按逻辑联结次的优先次序先后处理否定合取析取条件和双条件运算。
以否定运算为例，先找到否定运算p1有3中可能情况，一一判断，然后进行否定运算并赋值给 sz[i]，否定运算次数加1，后续式子前移一项。通过循环处理完所有的否定运算。
主函数流程图：
四．测试用例和运行结果
五.实习小结
这个程序从功能上来说，可以运算逻辑联结词组成的表达式，并且支持括号运算,从而根据定理可轻松写出合式公式的主析取范式和主合取范式.在编程过程中，最重要的是对细节方面的把握。
1) 指示变量的使用。如程序中的d和sz[wz[i-1]]的使用和重要作用。
2) 逻辑联结词优先级的问题。程序中按优先次序先后处理否定合取析取条件和双条件运算。
3) 括号问题。对于运算来说，解决括号问题很重要，程序中从最内层括号向外层层运算，最后得出结果。
4) 真值表问题。真值表利用二进制的原理，递减得到。
5) 注意函数的递归的使用和for循环的使用等。
六．程序代码
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <math.h>
#define N 50
void panduan(int b[N],int f);//赋值函数
int tkh (char sz[N], char ccu[N], int icu[N], int h0);//分级运算函数
int fkh (char sz[N], char ccu[N], int icu[N], int h0);//主运算函数
void main()
{
int i1,i2,d=1,icu[N],kh=0,jg,j=0,h0;//icu[N]用于存放变量值,kh括号计数,jg存放结果
int bj=0,hq[N],h=0,x=0,xq[N];//hq[N]存放合取结果xq[N]存放析取结果
char sz[N],ccu[N],sz0[N],s;//sz[N]存放式子,ccu[N]存放变量,sz0[N]也是用于存放式子
hq[0]=-1;
xq[0]=-1;
printf("*****************************************\n");
printf("** **\n");
printf("** 欢迎进入逻辑运算软件 **\n");
printf("** (可运算真值表，主范式，支持括号) **\n");
printf("** **\n");
printf("** 用!表示否定 **\n");
printf("** 用&表示合取 **\n");
printf("** 用|表示析取 **\n");
printf("** 用^表示条件 **\n");
printf("** 用~表示双条件 **\n");
printf("** **\n");
printf("*****************************************\n\n");
printf("请输入一个合法的命题公式:\n");
gets(sz);//读取式子
strcpy(sz0,sz);
for(i1=0;i1<strlen(sz);i1++)
{
if(sz[i1]==')' || sz[i1]=='(')//存储括号数量
kh++;
if(sz[i1]>='a' && sz[i1]<='z' || sz[i1]>='A' && sz[i1]<='Z')
{
for(i2=0;i2<j;i2++) //判断并储存变量。
{ if(ccu[i2]==sz[i1])//去除重复变量
d=0;}
if(d==1)
{
ccu[j]=sz[i1];
j++;
}
d=1;
}
}
printf("\n该式子中的变量个数为：%d\n",j);//输出变量个数
h0=j;
printf("\n输出真值表如下：\n \n"); //输出真值表表头
for(i1=0;i1<h0;i1++)
printf(" %c ",ccu[i1]);
printf(" ");
puts(sz);
printf("\n");
for(i1=0;i1<j;i1++) //先将所有的变量赋值为1。
icu[i1]=1;
for(i2=0;i2<j;i2++)//输出真值表前项
printf(" %d ",icu[i2]);
jg=tkh(sz,ccu,icu,h0); //用函数求结果
if(jg==0)//结果为0，合取加1
hq[h++]=bj;
else //否则，析取加1
xq[x++]=bj;
printf(" %d\n",jg);//输出运算结果
strcpy(sz,sz0);
for(i1=0;i1<pow(2,j)-1;i1++)
{
++bj;
panduan(icu,j-1); //赋值变量
jg=tkh(sz,ccu,icu,h0);
if(jg==0)//结果为0，合取加1
hq[h++]=bj;
else //否则，析取加1
xq[x++]=bj;
strcpy(sz,sz0); //恢复被修改的数组。
for(i2=0;i2<j;i2++)
printf(" %d ",icu[i2]);//输出真值表前项
printf(" %d\n",jg);//输出运算结果
}
if(hq[0]==-1)//不存在合取范式时
printf("\n该命题公式不存在主合取范式。\n");
else
{
printf("\n该命题公式的主合取范式：\n\t");
for(i1=0;i1<h;i1++)
{
if (i1>0)
printf("/\\");
printf("M(%d)",hq[i1]); //输出主合取范式
}
}
if(xq[0]==-1)
printf("\n该命题公式不存在主析取范式。\n");
else
{
printf("\n\n该命题公式的主析取范式：\n\t");
for(i1=0;i1<x;i1++)
{
if (i1>0)
printf("\\/");
printf("m(%d)",xq[i1]);//输出主析取范式
}
}
printf("\n");
printf("\n欢迎下次再次使用！\n ");//结束
getch();
}
void panduan(int b[N],int f) // 二进制赋值。
{
int i;
i=f;
if(b[f]==1)//减1
b[f]=0;
else//进位
{
b[f]=1;
panduan(b,--i);
}
}
int tkh (char sz[N],char ccu[N],int icu[N],int h0)//分级运算函数
{
int i,j,h,s,kh=0,wz[N],a;
char xs1[N],ckh[N]; //xs1用来保存括号内的字符 ckh用来保存括号。
s=strlen(sz);
for(i=0;i<s;i++)
if(sz[i]=='(' || sz[i]==')')//判断括号
{
wz[kh]=i;//存储括号位置
ckh[kh]=sz[i];//存储括号类型
kh++;
}
if(kh==0)
return fkh(sz,ccu,icu,h0);//如果无括号，直接运行
else
{
for(i=0;i<kh;i++)
if(ckh[i]==')')//找到第一个）
break;
for(j=wz[i-1]+1,h=0;j<wz[i];j++,h++) //存储最内级括号中的内容
xs1[h]=sz[j];
xs1[h]='\0';
a=fkh(xs1,ccu,icu,h0);//运行最内层括号的式子，得到结果
if(a==1)//判断并存储结果
sz[wz[i-1]]=1;
else
sz[wz[i-1]]=-2;
for(j=wz[i-1]+1;j<s+wz[i-1]-wz[i];j++)//将括号后内容前移
sz[j]=sz[j+wz[i]-wz[i-1]];
sz[j]='\0';
return tkh(sz,ccu,icu,h0);//循环执行
}
}
int fkh(char sz[N],char ccu[N],int icu[N],int h0)//主运算函数
{
int i,h=0,j=0,j1=0,j2=0,j3=0,j4=0,j5=0,i1,i2,p1=-1,p2=-1,s;
char dt[N];
s=strlen(sz);
if(s==1)
{ for(i1=0;i1<h0;i1++)
if(sz[0]==ccu[i1])
p1=icu[i1];
if(sz[0]==-2||p1==0)//判断是否是最后一项
return 0;
else
return 1;} //1 就是sz[0]的值
else
{
for(i=0;i<s-j;i++) //先处理非
if(sz[i]=='!')
{
for(i1=0;i1<h0;i1++)
if(sz[i+1]==ccu[i1])//将变量赋值并给P1
p1=icu[i1];
if(sz[i+1]==-2)//如果是前运算结果的0，则P1等于0
p1=0;
if(p1==-1)//如果是数字，直接给P1
p1=sz[i+1];
sz[i]=!p1;
j++;
p1=-1;
for(i1=i+1;i1<s-j;i1++)
sz[i1]=sz[i1+1];//将后续式子前移一项
}
p1=-1;
j1=j;
for(i=0;i<s-j1-2*j2;i++) // 处理与
if(sz[i]=='&')
{
for(i1=0;i1<h0;i1++)
{
if(sz[i-1]==ccu[i1])//将变量赋值并给P1
p1=icu[i1];
if(sz[i+1]==ccu[i1])//将变量赋值并给P2
p2=icu[i1];
}
if(sz[i-1]==-2)//如果是前运算结果的0，则P1等于0
p1=0;
if(sz[i+1]==-2)
p2=0;
if(p1==-1) //如果是数字，直接给P1
p1=sz[i-1];
if(p2==-1)
p2=sz[i+1];
sz[i-1]=p1 && p2;
j2++;
p1=-1;
p2=-1;
for(i1=i;i1<s-j1-2*j2;i1++)//将后续式子前移两项
sz[i1]=sz[i1+2];
i=i-1;
}
for(i=0;i<s-j1-2*j2-2*j3;i++) // 处理或。
if(sz[i]=='|')
{
for(i1=0;i1<h0;i1++)
{
if(sz[i-1]==ccu[i1])//将变量赋值并给P1
p1=icu[i1];
if(sz[i+1]==ccu[i1])
p2=icu[i1];
}
if(sz[i-1]==-2)//如果是前运算结果的0，则P1等于0
p1=0;
if(sz[i+1]==-2)
p2=0;
if(p1==-1)//如果是数字，直接给P1
p1=sz[i-1];
if(p2==-1)
p2=sz[i+1];
sz[i-1]=p1 || p2;
j3++;
p1=-1;
p2=-1;
for(i1=i;i1<s-j1-2*j2-2*j3;i1++)//将后续式子前移两项
sz[i1]=sz[i1+2];
i--;
}
for(i=0;i<s-j1-2*j2-2*j3-2*j4;i++) // 处理条件
if(sz[i]=='^')
{
for(i1=0;i1<h0;i1++)
{
if(sz[i-1]==ccu[i1])//将变量赋值并给P1
p1=icu[i1];
if(sz[i+1]==ccu[i1])
p2=icu[i1];
}
if(sz[i-1]==-2)//如果是前运算结果的0，则P1等于0
p1=0;
if(sz[i+1]==-2)
p2=0;
if(p1==-1)//如果是数字，直接给P1
p1=sz[i-1];
if(p2==-1)
p2=sz[i+1];
sz[i-1]=!p1 || p2;
j4++;
p1=-1;
p2=-1;
for(i1=i;i1<s-j1-2*j2-2*j3-2*j4;i1++)//将后续式子前移两项
sz[i1]=sz[i1+2];
i--;
}
for(i=0;i<s-j1-2*j2-2*j3-2*j4-2*j5;i++) // 处理双条件
if(sz[i]=='~')
{
for(i1=0;i1<h0;i1++)
{
if(sz[i-1]==ccu[i1])//将变量赋值并给P1
p1=icu[i1];
if(sz[i+1]==ccu[i1])
p2=icu[i1];
}
if(sz[i-1]==-2)//如果是前运算结果的0，则P1等于0
p1=0;
if(sz[i+1]==-2)
p2=0;
if(p1==-1)//如果是数字，直接给P1
p1=sz[i-1];
if(p2==-1)
p2=sz[i+1];
sz[i-1]=(!p1 || p2)&&(!p2 || p1);
j5++;
p1=-1;
p2=-1;
for(i1=i;i1<s-j1-2*j2-2*j3-2*j4-2*j5;i1++)//将后续式子前移两项
sz[i1]=sz[i1+2];
i--;
}
return sz[0];
}
}