主析取范式
-
2023年2月27日发(作者：英语导游词)“离散数学”实验报告
（求给定命题公式的真值表并根据真值表求公式的主范式）
专业网络工程
班级1202班
学号12407442
姓名张敏慧
2013.12.14
-1-
目录
一.实验目的.......................................................3
二.实验内容……………………………………………………………………….3
求任意一个命题公式的真值表..............................................................................3
三.实验环境.......................................................3
四.实验原理和实现过程（算法描述）............................3
1.实验原理................................................................................................................3
2.实验流程图............................................................................................................5
五.实验代码.............................................6
六.实验结果...........................................14
七.实验总结....................................................19
-2-
一.实验目的
本实验课程是网络工程专业学生的一门专业基础课程，通过实验，帮助学生
更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提
高学生编写实验报告、总结实验结果的能力；使学生具备程序设计的思想，能够
独立完成简单的算法设计和分析。
熟悉掌握命题逻辑中的真值表、主范式等，进一步能用它们来解决实际问题。
二.实验内容
求任意一个命题公式的真值表，并根据真值表求主范式
详细说明：
求任意一个命题公式的真值表
本实验要求大家利用C/C＋＋语言，实现任意输入公式的真值表计算。一般
我们将公式中的命题变元放在真值表的左边，将公式的结果放在真值表的右边。
命题变元可用数值变量表示，合适公式的表示及求真值表转化为逻辑运算结果；
可用一维数表示合式公式中所出现的n个命题变元，同时它也是一个二进制加法
器的模拟器，每当在这个模拟器中产生一个二进制数时，就相当于给各个命题变
元产生了一组真值指派。算法逻辑如下：
（1）将二进制加法模拟器赋初值0
（2）计算模拟器中所对应的一组真值指派下合式公式的真值。
（3）输出真值表中对应于模拟器所给出的一组真值指派及这组真值指派所对应
的一行真值。
（4）产生下一个二进制数值，若该数值等于2n-1，则结束，否则转（2）。
三.实验环境；
使用visualC++6.0为编程软件，采用C语言为编程语言实现。
四.实验原理和实现过程（算法描述）；
1.实验原理
（1）真值表:表征逻辑事件输入和输出之间全部可能状态的表格。列出命题公
-3-
式真假值的表。通常以1表示真，0表示假。命题公式的取值由组成命题公式的
命题变元的取值和命题联结词决定，命题联结词的真值表给出了真假值的算法。
真值表是在逻辑中使用的一类数学表，用来确定一个表达式是否为真或有效。
（2）主范式：
主析取范式：在含有n个命题变元的简单合取式中,若每个命题变元与其否
定不同时存在,而两者之一出现一次且仅出现一次,称该简单合取式为小项。由若
干个不同的小项组成的析取式称为主析取范式;与A等价的主析取范式称为A的
主析取范式。任意含n个命题变元的非永假命题公式A都存在与其等价的主析取
范式,并且是惟一的。
主合取范式：在含有n个命题变元的简单析取式中,若每个命题变元与其否
定不同时存在,而两者之一出现一次且仅出现一次,称该简单析取式为大项。由若
干个不同的大项组成的合取式称为主合取范式;与A等价的主合取范式称为A的
主合取范式。任意含n个命题变元的非永真命题公式A都存在与其等价的主合取
范式,并且是惟一的。
（2）首先是输入一个合理的式子，然后从式子中查找出变量的个数，开辟一个
二进制函数，用来生成真值表，然后用函数运算，输出结果，并根据结果归类给
范式，最后输出范式。
函数部分，主要是3个函数，一个为真值表递加函数，通过二进制的加法原
理递进产生，一个为分级运算函数，这个函数是通过判断括号，选出最内级括号
的内容执行运算函数，这样一级一级向外运算，最后得出最终结果，剩下一个为
主运算函数，按照运算符号的优先级按顺序进行运算，如先将所有非运算运算完，
再执行与运算。如此运算。
-4-
2.实验流程图如下：
开始
输入式子
计算变量个数
生成真值表
输出真值表
变量赋值
运算式子
输出结果
归类主范式
输出主范式
结束
循环是否结束
Y
N
主函数
-5-
开始
检查括号
是否是最内级
括号
运算内容
是否是最后结
果
返回结果
结束
开始
结束
Y
Y
N
N
非运算
与运算
或运算
蕴含运算
等值运算
返回结果
主运算函数
分级运算函数
-6-
五.实验代码
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include"conio.h"
#include"math.h"
#defineN50
voidpanduan(intb[N],intf);//赋值函数
inttkh(charsz[N],charccu[N],inticu[N],inth0);//分级运算函数
intfkh(charsz[N],charccu[N],inticu[N],inth0);//主运算函数
main()
{
inti1,i2,d=1,icu[N],kh=0,jg,j=0,h0;//icu[N]用于存放变量值,kh括号计
数,jg存放结果
intbj=0,hq[N],h=0,x=0,xq[N];//hq[N]存放合取结果xq[N]存放析取结果
charsz[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("***************************************nn");
printf("请输入一个合法的命题公式:n");//输入式子
gets(sz);//读取式子
strcpy(sz0,sz);//复制式子
for(i1=0;i1 { if(sz[i1]==')'||sz[i1]=='(')//存储括号数量 kh++; if(sz[i1]>='a'&&sz[i1]='A'&&sz[i1]<='Z') { for(i2=0;i2 if(ccu[i2]==sz[i1])//去除重复变量 -7- d=0; if(d==1) { ccu[j]=sz[i1]; j++; } d=1; } } printf("nd该式子中的变量个数为：%dn",j);//输出变量个数 h0=j; printf("n输出真值表如下：nn");//输出真值表表头 for(i1=0;i1 printf("%c",ccu[i1]); printf(""); puts(sz); printf("n"); for(i1=0;i1 icu[i1]=0; for(i2=0;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("%dn",jg);//输出运算结果 strcpy(sz,sz0); for(i1=0;i1<(int)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 printf("%d",icu[i2]);//输出真值表前项 printf("%dn",jg);//输出运算结果 } if(hq[0]==-1)//不存在合取范式时 printf("n该命题公式不存在主合取范式。n"); -8- else { printf("n该命题公式的主合取范式：nt"); for(i1=0;i1 { if(i1>0)//判断并添加符号 printf(""); printf("M(%d)",hq[i1]);//输出主合取范式 } } if(xq[0]==-1)//不存在析取范式时 printf("n该命题公式不存在主析取范式。n"); else { printf("nn该命题公式的主析取范式：nt"); for(i1=0;i1 { if(i1>0)//判断并添加符号 printf("/"); printf("m(%d)",xq[i1]);//输出主析取范式 } } printf("n"); printf("n欢迎下次再次使用！n");//结束 getch(); } voidpanduan(intb[N],intf)//二进制赋值。 { inti; i=f; if(b[f]==0)//加1 b[f]=1; else//进位 { b[f]=0; panduan(b,--i); } } inttkh(charsz[N],charccu[N],inticu[N],inth0)//分级运算函数 { inti,j,h,s,kh=0,wz[N],a; charxs1[N],ckh[N];//xs1用来保存括号内的字符ckh用来保存括号。 -9- s=strlen(sz); for(i=0;i if(sz[i]=='('||sz[i]==')')//判断括号 { wz[kh]=i;//存储括号位置 ckh[kh]=sz[i];//存储括号类型 kh++; } if(kh==0) returnfkh(sz,ccu,icu,h0);//如果无括号，直接运行 else { for(i=0;i if(ckh[i]==')')//找到第一个） break; for(j=wz[i-1]+1,h=0;j 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 sz[j]=sz[j+wz[i]-wz[i-1]]; sz[j]='0'; returntkh(sz,ccu,icu,h0);//循环执行 } } intfkh(charsz[N],charccu[N],inticu[N],inth0)//主运算函数 { inti,h=0,j=0,j1=0,j2=0,j3=0,j4=0,j5=0,i1,i2,p1=-1,p2=-1,s; chardt[N]; s=strlen(sz); if(s==1) if(sz[0]==-2)//判断是否是最后一项 return0; else return1;//1就是sz[0]的值、 else { for(i=0;i if(sz[i]=='!') -10- { for(i1=0;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]; dt[j+2]=!p1;//非运算 sz[i]=j+2; j++; p1=0; for(i1=i+1;i1 sz[i1]=sz[i1+1];//将后续式子前移一项 } p1=-1; j1=j; for(i=0;i if(sz[i]=='&') { for(i1=0;i1 { if(sz[i-1]==ccu[i1])//将变量赋值并给P1 p1=icu[i1]; if(sz[i+1]==ccu[i1])//将变量赋值并给P2 p2=icu[i1]; } for(i2=2;i2 { if(sz[i-1]==i2)//如果为前计算结果，将结果赋值并给P1 p1=dt[i2]; if(sz[i+1]==i2)//如果为前计算结果，将结果赋值并给P2 p2=dt[i2]; } if(sz[i-1]==-2)//如果是前运算结果的0，则P1等于0 p1=0; if(sz[i+1]==-2)//如果是前运算结果的0，则P2等于0 p2=0; if(p1==-1)//如果是数字，直接给P1 p1=(int)(sz[i-1]); if(p2==-1)//如果是数字，直接给P2 p2=(int)(sz[i+1]); dt[j+2]=p1&&p2;//与运算 sz[i-1]=j+2; -11- j++; j2++; p1=-1; p2=-1; for(i1=i;i1 sz[i1]=sz[i1+2]; i=i-1; } for(i=0;i if(sz[i]=='|') { for(i1=0;i1 { if(sz[i-1]==ccu[i1])//将变量赋值并给P1 p1=icu[i1]; if(sz[i+1]==ccu[i1])//将变量赋值并给P2 p2=icu[i1]; } for(i2=2;i2 { if(sz[i-1]==i2)//如果为前计算结果，将结果赋值并给P1 p1=dt[i2]; if(sz[i+1]==i2)//如果为前计算结果，将结果赋值并给P2 p2=dt[i2]; } if(sz[i-1]==-2)//如果是前运算结果的0，则P1等于0 p1=0; if(sz[i+1]==-2)//如果是前运算结果的0，则P2等于0 p2=0; if(p1==-1)//如果是数字，直接给P1 p1=sz[i-1]; if(p2==-1)//如果是数字，直接给P2 p2=sz[i+1]; dt[j+2]=p1||p2;//或运算 sz[i-1]=j+2; j++; j3++; p1=-1; p2=-1; for(i1=i;i1 sz[i1]=sz[i1+2]; i--; } for(i=0;i -12- if(sz[i]=='^') { for(i1=0;i1 { if(sz[i-1]==ccu[i1])//将变量赋值并给P1 p1=icu[i1]; if(sz[i+1]==ccu[i1])//将变量赋值并给P2 p2=icu[i1]; } for(i2=2;i2 { if(sz[i-1]==i2)//如果为前计算结果，将结果赋值并给P1 p1=dt[i2]; if(sz[i+1]==i2)//如果为前计算结果，将结果赋值并给P2 p2=dt[i2]; } if(sz[i-1]==-2)//如果是前运算结果的0，则P1等于0 p1=0; if(sz[i+1]==-2)//如果是前运算结果的0，则P2等于0 p2=0; if(p1==-1)//如果是数字，直接给P1 p1=sz[i-1]; if(p2==-1)//如果是数字，直接给P2 p2=sz[i+1]; dt[j+2]=!p1||p2;//蕴含运算 sz[i-1]=j+2; j++; j4++; p1=-1; p2=-1; for(i1=i;i1 sz[i1]=sz[i1+2]; i--; } for(i=0;i if(sz[i]=='~') { for(i1=0;i1 { if(sz[i-1]==ccu[i1])//将变量赋值并给P1 p1=icu[i1]; if(sz[i+1]==ccu[i1])//将变量赋值并给P2 p2=icu[i1]; } -13- for(i2=2;i2 { if(sz[i-1]==i2)//如果为前计算结果，将结果赋值并给P1 p1=dt[i2]; if(sz[i+1]==i2)//如果为前计算结果，将结果赋值并给P2 p2=dt[i2]; } if(sz[i-1]==-2)//如果是前运算结果的0，则P1等于0 p1=0; if(sz[i+1]==-2)//如果是前运算结果的0，则P2等于0 p2=0; if(p1==-1)//如果是数字，直接给P1 p1=sz[i-1]; if(p2==-1)//如果是数字，直接给P2 p2=sz[i+1]; dt[j+2]=(!p1||p2)&&(!p2||p1);//等值运算 sz[i-1]=j+2; j++; j5++; p1=-1; p2=-1; for(i1=i;i1 项 sz[i1]=sz[i1+2]; i--; } returndt[j+1];//返回结果 } } 六.实验结果 结果分析： 这道题第一部分比较简单，主要是读取值并进行计算，同时要注意输入的值 要是0或1，如果不是，则进行错误提示，并进行重新输入。 -14- 欢迎界面 非运算 -15- 与运算 -16- 或运算 -17- 蕴含运算 等值运算 -18- 综合运算 带括号的综合运算 -19- 结果分析： 这个程序从功能上来说，达到了题目要求的各个功能，可以运算与，或，非， 蕴含，等值条件组成的表达式，并且支持括号运算，所以，总体上来说，虽然还 有一些不完善的部分，但是整体是比较可以的。 七.实验总结 这个实验相对来说是一个不困难的题，一开始想用中序表达式转变为逆波 兰式的方法来解决，但是总有一些零零散散的问题困扰，况且对于栈和二叉树之 类的东西在学习C语言时接触很少，所以困难更大，经过多次失败后，还是最后 用最简单同时也是最麻烦的方法来解决这个问题。利用函数一步步来解决，所以 在个别功能上来说有一些不完美，比如纠错，因为时间有限，有个别地方没有设 置出错提示。 也许是很久没看C语言了，导致很多基本的语句都已经并不熟练了，通过 这次实验，让我从一定程度上找回了一点以前做课程设计时的感觉。在编程过程 中，最重要的其实是对细节方面的把握。 在设计上主要有以下几个问题： 1.优先级的问题，要如何解决优先级的问题，最后我直接用先后执行来解 决。 2.括号问题，对于运算来说，解决括号问题很重要，而我是从最内级括号 向外层层运算，最后得出结果。 3.真值表问题，真值表利用二进制的原理，递加得到。 4.赋值问题，一开始这个问题困扰了我很久，后来发现直接用一个赋值函 数，每次运行都直接运行一次就可以很好的解决了。 这些是在做题时主要遇到的问题。 其实这个题在得出真值的结果之后就可以比较简单的解决了，因为已经有真 值表，只要将最后结果分类，并将其分类列出就可以了。 总的来说，本次实验总体上是比较成功的，也让我学到了很多东西。