利用真值表法求取主析取范式以及主合取范式的实现.docx
《利用真值表法求取主析取范式以及主合取范式的实现.docx》由会员分享，可在线阅读，更多相关《利用真值表法求取主析取范式以及主合取范式的实现.docx（18页珍藏版）》请在冰点文库上搜索。
利用真值表法求取主析取范式以及主合取范式的实现
实验报告
〔2016/2017学年第一学期〕
课程名称
离散数学
实验名称
利用真值表法求取主析取式以及主合取式的实现
实验报告
实验名称
利用真值表法求取主析取式以及主合取式的实现
指导教师
实验类型
验证
实验学时
4
实验时间
一、实验目的和要求
容：
编程实现用真值表法求取任意数量变量的合式公式的主析取式和主合取式。
要求：
能够列出任意合式公式的真值表并给出相应主析取和主合取式。
二、实验环境（实验设备）
X86架构计算机
操作系统：
Windows732bit
IDE:
CodeBlokcs16.02
编程语言：
C++
编译器：
GCC
三、实验原理及容
容：
编程实现用真值表法求取任意数量变量的合式公式的主析取式和主合取式。
原理：
先将中缀表达式转换成后缀表达式，再将后缀表达式中每一个字母变量一一赋值，用递归枚举的方法枚举所有赋值情况，并且用map映射将每一个字母变量与当前被枚举的值一一映射，对每一种赋值情况调用后缀表达式计算函数计算后缀表达式的值，打印真假情况。
如果是真，记录到名为zhen的vector不定长数组中，如果是假，记录到名为jia的vector不定长数组中。
最后根据zhen和jia的不定长数组来打印主析取式和主合取式。
此程序可以实现任意数量的字母变量的主析取式求取和主合取式求取，以及真值表打印。
实验报告
第一步：
预处理
预处理，去除中缀表达式中条件->中的>,和双条件<=>中的=和>，这样，所有的运算符只是一个字符，后期处理起来更加方便。
voidddd（）
{
string:
:
iteratori=zhong.begin（）;//string类迭代器，需在头文件参加#include
intflag=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;
}
}
}
}
第二步：
将中缀表达式转换后缀表达式
利用栈和优先级函数来将中缀表达式转换成后缀表达式，此函数另一个功能是将中缀表达式中所有出现过的字母变量都保存包名为alpha的string类中〔string类为STL中的string，需要在头文件参加#include〕，并且alpha中不出现重复字母，这样，通过alpha.size（）函数就可以得到所有字母变量的个数，并且方便后面枚举赋值映射。
全局变量：
stringzhong;//中缀表达式
charhou[1000];//后缀表达式
stringalpha;//存放所有字母变量
优先级函数：
inticp（chara）//栈外优先级
{
if（a=='#'）return0;
if（a=='（'）return12;
if（a=='!
'）return10;
if（a=='&'）return8;
if（a=='|'）return6;
if（a=='-'）return4;
if（a=='<'）return2;
if（a=='）'）return1;
}
intisp（chara）//栈优先级
{
if（a=='#'）return0;
if（a=='（'）return1;
if（a=='!
'）return11;
if（a=='&'）return9;
if（a=='|'）return7;
if（a=='-'）return5;
if（a=='<'）return3;
if（a=='）'）return12;
}
voidchange（）//中缀表达式转换后缀表达式
{
intj=0;
stacks;//定义临时栈，需要在头文件参加#include
charch,y;
s.push（'#'）;
chart1,t2;
stringstreamss（zhong）;//字符串流，需要在头文件参加#include
while（ss>>ch,ch!
='#'）
{
if（isalpha（ch））//判断是不是字母，如果是，参加到alpha字符串中
{
hou[j++]=ch;//并且参加到后缀表达式字符串中
if（alpha.find（ch）==-1）
{
alpha.push_back（ch）;
}
}
elseif（ch=='）'）
{
for（y=s.top（）,s.pop（）;y!
='（';y=s.top（）,s.pop（））
{
hou[j++]=y;
}
}
else
{
for（y=s.top（）,s.pop（）;icp（ch）<=isp（y）;y=s.top（）,s.pop（））
{
hou[j++]=y;
}
s.push（y）;
s.push（ch）;
}
}
while（!
s.empty（））
{
y=s.top（）;
s.pop（）;
if（y!
='#'）
{
hou[j++]=y;
}
}
hou[j]='#';
}
第三步：
递归枚举每一个字母变量的取值情况
用深度优先搜索〔dfs〕的思想进展递归枚举，如果当前递归深度已经到达字符串长度，就说明所有字母已经取值成功，字母的"值〞用map进展映射〔需要在头文件参加#include
计算完成后，打印真值，如果当前计算结果是true，那么参加到zhen数组中，以待后面的主析取式打印调用，如果是false，参加到jia数组，以待后面的主合取式打印调用。
全局变量：
mapM;//映射，将字母变量与0或1一一对应
structnote
{
inta[100];
};
vectorzhen;//不定长数组，存放主析取式对应字母变量的01情况，也就是表达式真值为T
vectorjia;//不定长数组，存放主合取式对应字母变量的01情况，也就是表达式真值是F
voiddfs（intcur）//递归枚举每一种字符变量的取值情况
{
if（cur==alpha.size（））
{
intans=cal（）;
for（inti=0;i{
if（M[alpha[i]]）
{
printf（"T\t"）;
}
else
{
printf（"F\t"）;
}
}
if（ans==1）//真值为T计入到zhen数组，以待后面主析取式使用
{
printf（"T\n"）;
notet;
for（inti=0;i{
t.a[i]=M[alpha[i]];
}
zhen.push_back（t）;
}
else//真值为F计入到jia数组，以待后面主合取式使用
{
printf（"F\n"）;
notet;
for（inti=0;i{
t.a[i]=M[alpha[i]];
}
jia.push_back（t）;
}
return;
}
M[alpha[cur]]=1;//深度优先搜索〔dfs〕进展递归枚举
dfs（cur+1）;
M[alpha[cur]]=0;
dfs（cur+1）;
}
intcal（）//对赋值后的后缀表达式进展计算，返回计算结果
{
stacks;
charch;
intj=0;
intt1,t2;
while
（1）
{
ch=hou[j];
if（ch=='#'）break;
if（ch==0）break;
j++;
if（（ch>='A'&&ch<='Z'）||（ch>='a'&&ch<='z'））
{
s.push（M[ch]）;
}
else
{
if（ch=='!
'）
{
t1=s.top（）;
s.pop（）;
s.push（!
t1）;
}
elseif（ch=='&'）
{
t1=s.top（）;
s.pop（）;
t2=s.top（）;
s.pop（）;
if（t1==1&&t2==1）
{
s.push
（1）;
}
else
{
s.push（0）;
}
}
elseif（ch=='|'）
{
t1=s.top（）;
s.pop（）;
t2=s.top（）;
s.pop（）;
if（t1==0&&t2==0）
{
s.push（0）;
}
else
{
s.push
（1）;
}
}
elseif（ch=='-'）
{
t1=s.top（）;
s.pop（）;
t2=s.top（）;
s.pop（）;
if（t1==0&&t2==1）
{
s.push（0）;
}
else
{
s.push
（1）;
}
}
elseif（ch=='<'）
{
t1=s.top（）;
s.pop（）;
t2=s.top（）;
s.pop（）;
if（（t1==1&&t2==1）||（t1==0&&t2==0））
{
s.push
（1）;
}
else
{
s.push（0）;
}
}
}
}
intans=s.top（）;
returnans;
}
最后一步：
打印主析取式和主合取式
最后一步，也是最简单的一步，打印主析取式和主合取式，由于前面在递归枚举dfs的过程中已经把真值表顺带打印了，所以就只剩下主析取式和主合取式了，在dfs过程中，所有取值为真的情况已经参加zhen的vector数组中了，所有取值为假的以及参加到了jia的vector数组中了，虽然存放的是01序列，但是alpha中字母顺序自始至终不变，所以根据下标可以形成一一对应关系。
main函数
intmain（）
{
while（true）
{
inti;
M.clear（）;
alpha.clear（）;
zhen.clear（）;
jia.clear（）;
printf（"或运算为|,与运算为&,单条件为->,双条件我<=>,非运算为!
\n"）;
printf（"请输入表达式,回车完毕\n"）;
cin>>zhong;
zhong.append（"#"）;
ddd（）;
change（）;
for（i=0;i{
printf（"%c\t",alpha[i]）;
}
printf（"表达式真值\n"）;
dfs（0）;
printf（"主析取式为\n"）;
intlena=zhen.size（）;
for（i=0;i{
if（i!
=0）printf（"∨"）;
int*p=zhen[i].a;
printf（"（"）;
for（intj=0;j{
if（j!
=0）printf（"∧"）;
if（p[j]==1）
{
printf（"%c",alpha[j]）;
}
else
{
printf（"￢%c",alpha[j]）;
}
}
printf（"）"）;
}
printf（"\n"）;
printf（"主合取式为\n"）;
for（i=0;i{
if（i!
=0）printf（"∧"）;
int*p=jia[i].a;
printf（"（"）;
for（intj=0;j{
if（j!
=0）printf（"∨"）;
if（p[j]==0）
{
printf（"%c",alpha[j]）;
}
else
{
printf（"￢%c",alpha[j]）;
}
}
printf（"）"）;
}
printf（"\n\n"）;
}
return0;
}
程序测试与分析：
由于使用了STL中vector数组和string类，所以可以实现计算含有任意数量的字母变量的表达式。
本程序中或运算为|,与运算为&,单条件为->,双条件我<=>,非运算为!
测试一：
输入P&Q
运行截图：
结果：
正确
测试二：
输入书上第37页下方例题（P&Q）|（!
P&R）
结果：
正确
测试三：
课本39页〔4〕d〕（P->（Q&R））&（!
P->（!
Q&!
R））
测试四
输入A&B&C&D&E
正确
测试五
输入课本39页〔2〕b〕
P->（（Q&R）->S）
正确
测试六：
输入：
课本39页〔4〕a〕（!
P|!
Q）->（P<=>!
Q）
正确
实验报告
四、实验小结〔包括问题和解决方法、心得体会、意见与建议等〕
五、指导教师评语
成绩
批阅人
日期
升级会员 