1、利用真值表法求取主析取范式以及主合取范式的实现实 验 报 告2016 / 2017 学年 第 一 学期课程名称离散数学实验名称利用真值表法求取主析取式以及主合取式的实现实 验 报 告实验名称利用真值表法求取主析取式以及主合取式的实现指导教师实验类型验证实验学时4实验时间一、实验目的和要求容：编程实现用真值表法求取任意数量变量的合式公式的主析取式和主合取式。要求：能够列出任意合式公式的真值表并给出相应主析取和主合取式。二、实验环境(实验设备)X86架构计算机操作系统：Windows 7 32bitIDE: CodeBlokcs 16.02编程语言：C+编译器：GCC三、实验原理及容容：编程实现用
2、真值表法求取任意数量变量的合式公式的主析取式和主合取式。原理：先将中缀表达式转换成后缀表达式，再将后缀表达式中每一个字母变量一一赋值，用递归枚举的方法枚举所有赋值情况，并且用map映射将每一个字母变量与当前被枚举的值一一映射，对每一种赋值情况调用后缀表达式计算函数计算后缀表达式的值，打印真假情况。如果是真，记录到名为zhen的vector不定长数组中，如果是假，记录到名为jia的vector不定长数组中。最后根据zhen和jia的不定长数组来打印主析取式和主合取式。此程序可以实现任意数量的字母变量的主析取式求取和主合取式求取，以及真值表打印。实 验 报 告第一步：预处理预处理，去除中缀表达式中
3、条件-中的,和双条件中的= 和 ，这样，所有的运算符只是一个字符，后期处理起来更加方便。void ddd() string:iterator i=zhong.begin(); /string类迭代器，需在头文件参加#include int flag=1; while(flag) flag=0; for(i=zhong.begin();i!=zhong.end();+i) if(*i=) zhong.erase(i); flag=1; break; if(*i=) zhong.erase(i); flag=1; break; 第二步：将中缀表达式转换后缀表达式 利用栈和优先级函数来将中缀表达式转
4、换成后缀表达式，此函数另一个功能是将中缀表达式中所有出现过的字母变量都保存包名为alpha的string类中string类为STL中的string，需要在头文件参加#include，并且alpha中不出现重复字母，这样，通过alpha.size()函数就可以得到所有字母变量的个数，并且方便后面枚举赋值映射。全局变量：string zhong; /中缀表达式char hou1000; /后缀表达式string alpha; /存放所有字母变量优先级函数： int icp(char a) /栈外优先级 if(a=#) return 0; if(a=() return 12; if(a=!) ret
5、urn 10; if(a=&) return 8; if(a=|) return 6; if(a=-) return 4; if(a=) return 2; if(a=) return 1;int isp(char a) /栈优先级 if(a=#) return 0; if(a=() return 1; if(a=!) return 11; if(a=&) return 9; if(a=|) return 7; if(a=-) return 5; if(a=) return 3; if(a=) return 12; void change() /中缀表达式转换后缀表达式 int j=0; st
6、ack s; /定义临时栈，需要在头文件参加#include char ch,y; s.push(#); char t1,t2; stringstream ss(zhong); /字符串流，需要在头文件参加#include while(ssch,ch!=#) if(isalpha(ch) /判断是不是字母，如果是，参加到alpha字符串中 houj+=ch; /并且参加到后缀表达式字符串中 if(alpha.find(ch)=-1) alpha.push_back(ch); else if(ch=) for(y=s.top(),s.pop();y!=(;y=s.top(),s.pop() ho
7、uj+=y; else for(y=s.top(),s.pop();icp(ch)=isp(y);y=s.top(),s.pop() houj+=y; s.push(y); s.push(ch); while(!s.empty() y=s.top(); s.pop(); if(y!=#) houj+=y; houj=#; 第三步：递归枚举每一个字母变量的取值情况用深度优先搜索dfs的思想进展递归枚举，如果当前递归深度已经到达字符串长度，就说明所有字母已经取值成功，字母的值用map进展映射需要在头文件参加#include，所有字母都已经枚举后调用cal函数对当前取值情况的后缀表达式进展计算，因为
8、map M对象是全局变量，所以cal函数可以查看到相应字母的取值情况。计算完成后，打印真值，如果当前计算结果是true，那么参加到zhen数组中，以待后面的主析取式打印调用，如果是false，参加到jia数组，以待后面的主合取式打印调用。全局变量：map M; /映射，将字母变量与0或1一一对应struct note int a100;vector zhen; /不定长数组，存放主析取式对应字母变量的01情况，也就是表达式真值为Tvector jia; /不定长数组，存放主合取式对应字母变量的01情况，也就是表达式真值是Fvoid dfs(int cur) /递归枚举每一种字符变量的取值情况
9、if(cur=alpha.size() int ans=cal(); for(int i=0;ialpha.size();i+) if(Malphai) printf(Tt); else printf(Ft); if(ans=1) /真值为T 计入到zhen数组，以待后面主析取式使用 printf(Tn); note t; for(int i=0;ialpha.size();i+) t.ai=Malphai; zhen.push_back(t); else /真值为F 计入到jia数组，以待后面主合取式使用 printf(Fn); note t; for(int i=0;ialpha.size
10、();i+) t.ai=Malphai; jia.push_back(t); return ; Malphacur=1; /深度优先搜索dfs进展递归枚举 dfs(cur+1); Malphacur=0; dfs(cur+1);int cal() /对赋值后的后缀表达式进展计算，返回计算结果 stack s; char ch; int j=0; int t1,t2; while(1) ch=houj; if(ch=#) break; if(ch=0) break; j+; if(ch=A&ch=a&ch=z) s.push(Mch); else if(ch=!) t1=s.top(); s.p
11、op(); s.push(!t1); else if(ch=&) t1=s.top(); s.pop(); t2=s.top(); s.pop(); if(t1=1&t2=1) s.push(1); else s.push(0); else if(ch=|) t1=s.top(); s.pop(); t2=s.top(); s.pop(); if(t1=0&t2=0) s.push(0); else s.push(1); else if(ch=-) t1=s.top(); s.pop(); t2=s.top(); s.pop(); if(t1=0&t2=1) s.push(0); else s
12、.push(1); else if(ch= ,双条件我 ,非运算为 !n); printf(请输入表达式,回车完毕n); cinzhong; zhong.append(#); ddd(); change(); for(i=0;ialpha.size();i+) printf(%ct,alphai); printf(表达式真值n); dfs(0); printf(主析取式为n); int lena=zhen.size(); for(i=0;ilena;i+) if(i!=0) printf(); int *p=zheni.a; printf(); for(int j=0;jalpha.size(
13、);j+) if(j!=0) printf(); if(pj=1) printf(%c,alphaj); else printf(%c,alphaj); printf(); printf(n); printf(主合取式为n); for(i=0;ijia.size();i+) if(i!=0) printf(); int *p=jiai.a; printf(); for(int j=0;j ,双条件我 ,非运算为 !测试一：输入P&Q运行截图：结果：正确测试二：输入书上第37页下方例题 (P&Q)|(!P&R)结果：正确测试三：课本39页4d(P-(Q&R)&(!P-(!Q&!R)测试四输入A&B&C&D&E正确测试五输入课本39页2bP-(Q&R)-S)正确测试六：输入：课本39页4a (!P|!Q)-(P!Q)正确实 验 报 告四、实验小结包括问题和解决方法、心得体会、意见与建议等五、指导教师评语成 绩批阅人日 期
